Method and apparatus for disseminating topology information and for discovering new neighboring nodes
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
H04L-012/28
H04Q-007/24
출원번호
US-0307267
(2002-11-29)
등록번호
US-7327683
(2008-02-05)
발명자
/ 주소
Ogier,Richard G.
Templin,Fred L.
Lewis,Mark G.
출원인 / 주소
SRI International
대리인 / 주소
Tong, Esq.,Kin Wah
인용정보
피인용 횟수 :
78인용 특허 :
16
초록▼
A proactive link-state routing protocol designed for mobile ad-hoc networks is disclosed, which provides hop-by-hop routing along shortest paths to each destination. Each node running the present protocol will compute a source tree (providing paths to all reachable nodes) based on partial topology i
A proactive link-state routing protocol designed for mobile ad-hoc networks is disclosed, which provides hop-by-hop routing along shortest paths to each destination. Each node running the present protocol will compute a source tree (providing paths to all reachable nodes) based on partial topology information stored in its topology table. To minimize overhead, each node reports only "part" of its source tree to neighbors. The present invention employs a combination of periodic and differential updates to keep all neighbors informed of the reportable part of its source tree. The present invention performs neighbor discovery using "differential" HELLO messages that report only "changes" in the status of neighbors. This results in HELLO messages that are much smaller than those of other link-state routing protocols.
대표청구항▼
What is claimed is: 1. Method for communicating between a plurality of nodes, said method comprising the steps of: a) allowing a predefined time interval to elapse; and b) sending a differential message by a sending node to at least one neighboring node of said sending node, wherein said differenti
What is claimed is: 1. Method for communicating between a plurality of nodes, said method comprising the steps of: a) allowing a predefined time interval to elapse; and b) sending a differential message by a sending node to at least one neighboring node of said sending node, wherein said differential message comprises only changes in link state status of neighboring nodes of said sending node with respect to link state statuses reported in a last differential message sent by the sending node. 2. The method of claim 1, further comprising the step of: c) sending said differential message for a certain number of times for ensuring that said at least one neighboring node will either receive said differential messages or will deem a link to said sending node is lost for failing to receive said differential messages. 3. The method of claim 1, wherein said differential message comprises a plurality of message subtypes. 4. The method of claim 3, wherein said plurality of message subtypes comprise a neighbor request subtype that indicates said sending node's presence to a receiving neighbor node. 5. The method of claim 4, wherein said plurality of message subtypes further comprise a neighbor reply subtype that indicates a receipt of a neighbor node's neighbor request message. 6. The method of claim 5, wherein said plurality of message subtypes further comprise a neighbor lost subtype that indicates a loss of a neighbor node by said sending node. 7. The method of claim 1, wherein said predefined time interval defines a duration between successive differential messages that are sent to one or more neighbor nodes and wherein said predefined time interval is dynamically adjusted. 8. The method of claim 7, wherein said predefined time interval is dynamically adjusted in accordance with a current velocity of said sending node. 9. The method of claim 7, wherein said predefined time interval is dynamically adjusted in accordance with a bandwidth demand of said sending node. 10. he method of claim 7, wherein said predefined time interval is dynamically adjusted in accordance with a measure of network traffic of a network where said plurality of nodes are members of said network. 11. The method of claim 1, wherein an adjustment of said predefined time interval is communicated within said differential message. 12. Method for communicating between a plurality of nodes, said method comprising the steps of: a) receiving a differential message from a sending neighbor node, wherein said differential message comprises only changes in link state status of neighboring nodes of said sending neighbor node with resoect to link state statuses respect in a last differential message sent by the sending neighbor node; and b) sending a reply message to said sending neighbor node. 13. The method of claim 12, wherein said differential message comprises a plurality of message subtypes. 14. The method of claim 13, wherein said plurality of message subtypes comprise a neighbor request subtype that indicates saId sending node's presence to a receiving neighbor node. 15. The method of claim 14, wherein said plurality of message subtypes further comprise a neighbor reply subtype that indicates a receipt of a neighbor node's neighbor request message. 16. The method of claim 15, wherein said plurality of message subtypes further comprise a neighbor lost subtype that indicates a loss of a neighbor node of said sending neighbor node. 17. The method of claim 12, further comprising the step of: c) waiting for a predefined time interval for a subsequent message from said sending neighbor node. 18. The method of claim 17, wherein said predefined time interval is dynamically adjusted. 19. The method of claim 18, wherein said predefined time interval is dynamically adjusted in accordance with a current velocity of said sending neighbor node. 20. The method of claim 18, wherein said predefined time interval is dynamically adjusted in accordance with a bandwidth demand of said sending neighbor node. 21. The method of claim 18, wherein said predefined time interval is dynamically adjusted in accordance with a measure of network traffic of a network where said plurality of nodes are members of said network. 22. The method of claim 18, wherein an adjustment of said predefined time interval is communicated within said differential message. 23. Apparatus for communicating with a plurality of nodes, said apparatus comprising: means for allowing a predefined time interval to elapse; and means for sending a differential message to at least one neighboring node of said apparatus, wherein said differential message comprises only changes in link state status of neighboring nodes of said apparatus with resriect to link state statuses reported in a last differential message sent by the apparatus. 24. The apparatus of claim 23, wherein said differential message is sent for a certain number of times for ensuring that said at least one neighboring node will either receive said differential messages or will deem a link to said apparatus is lost for failing to receive said differential messages. 25. The apparatus of claim 23, wherein said differential message comprises a plurality of message subtypes. 26. The apparatus of claim 25, wherein said plurality of message subtypes comprise a neighbor request subtype that indicates said apparatus presence to a receiving neighbor node. 27. The apparatus of claim 26, wherein said plurality of message subtypes further comprise a neighbor reply subtype that indicates a receipt of a neighbor node's neighbor request message. 28. The apparatus of claim 27, wherein said plurality of message subtypes further comprise a neighbor lost subtype that indicates a loss of a neighbor node by said apparatus. 29. The apparatus of claim 23, wherein said predefined time interval defines a duration between successive differential messages that are sent to one or more neighbor nodes and wherein said predefined time interval is dynamically adjusted. 30. The apparatus of claim 29, wherein said predefined time interval is dynamically adjusted in accordance with a current velocity of said apparatus. 31. The apparatus of claim 29, wherein said predefined time interval is dynamically adjusted in accordance with a bandwidth demand of said apparatus. 32. The apparatus of claim 29, wherein said predefined time interval is dynamically adjusted in accordance with a measure of network traffic of a network where said apparatus is a member of said network. 33. The apparatus of claim 23, wherein an adjustment of said predefined time interval is communicated within said differential message. 34. The apparatus of claim 23, wherein said apparatus is a router. 35. Apparatus for communicating with a plurality of nodes, said apparatus comprising: means for receiving a differential message from a sending neighbor node, wherein said differential message comprises only changes in link state status of neighboring nodes of said sending neighbor node with resDect to link state statuses reported in a last differential message also sent by the sending neighbor node; and means for sending a reply message to said sending neighbor node. 36. The apparatus of claim 35, wherein said differential message comprises a plurality of message subtypes. 37. The apparatus of claim 36, wherein said plurality of message subtypes comprise a neighbor request subtype that indicates said sending node's presence to a receiving neighbor node, a neighbor reply subtype that indicates a receipt of a neighbor node's neighbor request message and a neighbor lost subtype that indicates a loss of a neighbor node of said sending neighbor node. 38. The apparatus of claim 35, further comprising: means for waiting for a predefined time interval for a subsequent message from said sending neighbor node. 39. The apparatus of claim 38, wherein said predefined time interval is dynamically adjusted. 40. The apparatus of claim 39, wherein said predefined time interval is dynamically adjusted in accordance with a current velocity of said sending neighbor node, a bandwidth demand of said sending neighbor node or a measure of network traffic of a network where said apparatus is a member of said network. 41. The apparatus of claim 39, wherein an adjustment of said predefined time interval is communicated within said differential message. 42. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a computer, cause the computer to perform the steps comprising of: a) allowing a predefined time interval to elapse; and b) sending a differential message by a sending node to at least one neighboring node of said sending node, wherein said differential message comprises only changes in link state status of neighboring nodes of said sending node with respect to link state statuses reported in a last differential message sent by the sending node. 43. A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a computer, cause the computer to perform the steps comprising of: a) receiving a differential message from a sending neighbor node, wherein said differential message comprises only changes in link state status of neighboring nodes of said sending neighbor node with respect to link state statuses reported in a last differential message sent by the sending neighbor node; and b) sending a reply message to said sending neighbor node. 44. Method for a sending node in a communication network to report topology information to one or more neighbor nodes, said method comprising the steps of: a) computing a source tree providing paths to all reachable nodes in the communication network using a minimum-hop path tree; b) computing a reportable node set comprising only a part of the source tree that the sending node reports to the one or more neighbor nodes to minimize overhead; c) computing a reportable subtree of said source comprising one or more links in accordance with said reportable node set; and d) reporting said reportable subtree to said one or more neighbor nodes, wherein said reportable subtree is reported to said one or more neighbor nodes in a differential update, wherein said differential update is generated in accordance with only a change in a node's topology table. 45. The method of claim 44, wherein said change in a node's topology table is caused by receiving a topology update from a neighbor node. 46. The method of claim 44, wherein said change in a node's topology table is caused by detecting a status change for a link to one of its neighbor nodes. 47. Apparatus for a sending node in a communication network to report topology information to one or more neighbor nodes, said apparatus comprising: means for computing a source tree providing paths to all reachable nodes in the communication network using a minimum-hop path tree; means for computing a reportable node set comprising only a part of the source tree that the sending node reports to the one or more neighbor nodes to minimize overhead; means for computing a reportable subtree of said source comprising one or more links in accordance with said reportable node set; and means for reporting said reportable subtree to said one or more neighbor nodes, wherein said reportable subtree is reported to said one or more neighbor nodes in a differential update, wherein said differential update is generated in accordance with only a change in a node's topology table.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (16)
Hodzic Migdat I. ; Brennan James M., Adaptive digital wireless communications network apparatus and process.
Mahany Ronald L. ; Meier Robert C. ; Luse Ronald E., Communication network having a plurality of bridging nodes which transmit a beacon to terminal nodes in power saving s.
Raychaudhuri Dipankar ; Li Jun ; Acharya Arup, Handoff method for an ATM wireless network wherein both the switch and the mobile buffer cells and the mobile controls when the handoff will occur.
Perlman Radia J. (Acton MA) Kaufman Charles W. (Northborough MA) Gunner Christopher W. (Harvard MA), Method of neighbor discovery over a multiaccess nonbroadcast medium.
Kato Naotaka,JPX ; Kanada Yoshihisa,JPX, Methods and apparatus for downloading data between an information processing device and an external device via a wireless communications technique.
Quigley, Thomas; MacInnis, Alexander G.; Behzad, Arya; Karaoguz, Jeyhan; Walley, John; Buer, Mark, Method and system for establishing a connection outside a mesh by including network connectivity information in router configuration messages.
Quigley, Thomas; MacInnis, Alexander Garland; Behzad, Arya Reza; Karaoguz, Jeyhan; Walley, John; Buer, Mark, Method and system for establishing a connection outside a mesh by including network connectivity information in router configuration messages.
Choi, Wook; Lee, Yong; Choi, Hyo-Hyun; Park, Yong-Seok, Multi-radio mesh network system supporting at least two different wireless communication standards and method of controlling the same.
Wei, Wright; Ding, Xin; Fung, Hardy; Liu, Jason, Multiple devices communicating on a single communication channel with a consecutively sequenced signal.
Chandra, Madhavi W.; Cook, David A.; Retana, Alvaro E.; White, Russell I.; Yang, Yi, System and method for exchanging awareness information in a network environment.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.