Hybrid distance vector protocol for wireless mesh networks
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G01R-031/08
G06F-011/00
G08C-015/00
H04J-001/16
H04J-003/14
H04L-001/00
H04L-012/26
출원번호
UP-0364020
(2006-02-27)
등록번호
US-7787361
(2010-09-20)
발명자
/ 주소
Rahman, Shahriar
O'Hara, Jr., Robert Bernard
Kruys, Johannes Petrus
출원인 / 주소
Cisco Technology, Inc.
대리인 / 주소
Stolowitz Ford Cowger LLP
인용정보
피인용 횟수 :
13인용 특허 :
67
초록▼
A method of hybrid route discovery in a mesh network is described. The method comprises the optional designation of a root node of the mesh network and formatting a route request message at an originating mesh point, where the route request messages include a hop limit parameter. If a root node has
A method of hybrid route discovery in a mesh network is described. The method comprises the optional designation of a root node of the mesh network and formatting a route request message at an originating mesh point, where the route request messages include a hop limit parameter. If a root node has been configured, the route request is responded to with a message that describes the route to the root. If a direct route between two nodes is required, the route request message is broadcast from the originating mesh point, and the hop limit parameter limits the number of times the route request message will be forwarded. The originating mesh point receives a unicast route reply message from a neighboring mesh point, after the neighboring mesh point received the route request message. Finally, a route connecting the originating mesh point and the destination mesh point is established.
대표청구항▼
What is claimed is: 1. A method comprising: receiving a unicast periodic message, said unicast periodic message for checking a validity of an established route between a mesh point and a destination point in a mesh network, wherein said mesh network comprises a spanning tree based routing topology
What is claimed is: 1. A method comprising: receiving a unicast periodic message, said unicast periodic message for checking a validity of an established route between a mesh point and a destination point in a mesh network, wherein said mesh network comprises a spanning tree based routing topology connecting said mesh point to said destination point via a pre-defined tree based route of said spanning tree based routing topology comprising more hops than said established route, and wherein said spanning tree based routing topology is defined by a root node that connects each node in said mesh network with an Internet connection; forwarding said unicast periodic message to a designated destination address associated with said destination point via said established route; identifying a route error when a reply to said unicast periodic message is not received; broadcasting a route request message to a plurality of mesh points in said mesh network comprising said mesh point and said destination point to determine a new optimal route between said mesh point and said destination point, wherein said route request message is broadcast using a hybrid ad-hoc on-demand distance vectoring (AODV) protocol that includes a maximum hop count comprising fewer hops than said pre-defined tree based route, and wherein said new optimal route replaces said established route; and transmitting a unicast data packet from said mesh point through said pre-defined tree based route to said destination point until said new optimal route is established. 2. The method of claim 1, further comprising: establishing said new optimal route based on a reply to said route request message, wherein said route request message is wirelessly broadcast; transmitting a unicast route error message to said root node of said spanning tree based routing topology for updating route information between said mesh point and said destination point, wherein said unicast route error message is propagated to each node using said spanning tree based routing topology, and wherein each node receives a single instance of said unicast route error message; and updating said route information maintained at said root node based on said unicast route error message. 3. The method of claim 1 wherein a common ancestor node of said mesh point and said destination point flags said unicast data packet as being transmitted intramesh within said mesh network, wherein said route request message is broadcast in response to receiving said flagged unicast data packet, and wherein said common ancestor node is communicatively located between said root node and said mesh point in said spanning tree based routing topology. 4. The method of claim 3 wherein said common ancestor node is configured to transmit said unicast data packet to said destination point without said unicast data packet having been received by said root node of said spanning tree based routing topology. 5. The method of claim 1 further comprising: identifying an origin of said unicast data packet; and flagging said unicast data packet if said origin is located inside outside of said mesh network. 6. The method of claim 1 further comprising: propagating a route error message throughout said spanning tree based routing topology to avoid flooding a network with duplicate route error messages, wherein said route error message is propagated to each mesh point in said spanning tree based routing topology; and updating route information maintained at said root node based on said route error message. 7. The method of claim 1 wherein said spanning tree based routing topology identifies a predetermined spanning tree routing path connecting said mesh point to said destination point, and wherein said predetermined spanning tree routing path comprises more hops than said established route. 8. An apparatus for maintaining a route in a mesh network comprising a plurality of mesh points, said apparatus comprising: means for transmitting a unicast periodic message from a source point, said unicast periodic message for checking a validity of an established route between said source point and a destination point in said mesh network; means for receiving a unicast route reply message, said unicast route reply message for confirming the validity of said established route; means for temporarily transmitting a unicast data packet through a spanning tree based routing topology of said mesh network if said established route is not valid, until a new route between said source point and said destination point is established, wherein said spanning tree based routing topology provides a pre-defined route between said source point and said destination point, wherein said spanning tree based routing topology is defined by a root node that connects said mesh network with a network gateway, and wherein said pre-defined route comprises more hops than said established route; means for flagging said unicast data packet as being transmitted intramesh; means for wirelessly broadcasting, responsive to receiving said flagged unicast data packet, a routing request to one or more of said plurality of mesh points to establish said new route, using a hybrid ad-hoc on-demand distance vectoring (AODV) protocol, wherein said one or more mesh points forward said routing request through said spanning tree based routing topology according to a hop limit parameter contained within said routing request; and means for identifying said new route based on responses to said routing request that indicate a shortest path between said source point and said destination point. 9. The apparatus of claim 8 wherein said hop limit parameter allows fewer hops than said pre-defined route. 10. The apparatus of claim 8, wherein each of the plurality of mesh points are connected through the spanning tree based routing topology, and wherein the spanning tree based routing topology only includes one root node. 11. An apparatus, comprising: means for receiving an anticipated unicast periodic message into a mesh point, said anticipated unicast periodic message for validating an established route between a source point and a destination point in a mesh network; means for transmitting a unicast route reply message in response to receiving said anticipated unicast periodic message, said unicast route reply message for confirming the validity of said established route; means for transmitting a unicast error message through a pre-defined route of a spanning tree based routing topology of said mesh network if said established route is not valid, wherein each node in said mesh network receives a single instance of said unicast error message, and wherein said spanning tree based routing topology is defined by a root node that connects said mesh network with a network gateway; means for receiving a wireless routing request comprising a hop limit parameter, wherein said wireless routing request is broadcast from said source point using a hybrid ad-hoc on-demand distance vectoring (AODV) protocol; means for transmitting a unicast data packet from said source point to said destination point along said pre-defined route until a new route between said source point and said destination point is identified, wherein said pre-defined route contains more hops between said source point and said destination point than said established route; and means for identifying said new route between said source point and said destination point based on responses to the wireless routing request, wherein said new route contains fewer hops than said pre-defined route. 12. The apparatus of claim 11, wherein said unicast data packet is flagged by a common ancestor node of both said source point and said destination point, and wherein said wireless routing request is broadcast in response to receiving said flagged unicast data packet. 13. A mesh point in a mesh network, said mesh point comprising: a transmitter configured to transmit a unicast periodic message, said unicast periodic message for checking a validity of an established ad hoc distance vector route between said mesh point and a destination point, wherein said mesh network is organized as a spanning tree routing topology connecting each mesh point in the mesh network, and wherein said spanning tree routing topology is defined by a root node that connects said mesh network with a network gateway; a memory, for storing information, coupled to said transmitter; and a receiver coupled to said memory, wherein said receiver, in response to said unicast periodic message, is configured to receive a unicast route reply message, said unicast route reply message for confirming the validity of said established ad hoc distance vector route, wherein upon a failure to receive said unicast route reply message, said mesh point is configured to: transmit a unicast data packet through a pre-configured path of said spanning tree routing topology connecting said mesh point to said destination point until a new route can be established that contains fewer hops than said pre-configured path; and receive a broadcast route request message, wherein said broadcast route request message is transmitted responsive to said unicast data packet being flagged as originating within said mesh network, wherein said broadcast route request message is transmitted using a hybrid ad hoc on-demand distance vector (AODV) protocol that includes a maximum hop count comprising fewer hops than said pre-configured path, and wherein said new route is determined based on route response messages to said broadcast route request message that indicate a shortest path between said mesh point and said destination point. 14. The mesh point of claim 13, wherein said broadcast route request message is forwarded throughout said spanning tree routing topology according to said maximum hop count. 15. The mesh point of claim 13 wherein said established ad hoc distance vector route contains fewer hops than said pre-configured path. 16. A mesh point in a mesh network comprising: a memory, for storing route information; a wireless receiver, coupled to said memory, for receiving messages, wherein said receiver is configured to receive an anticipated unicast periodic message, said anticipated unicast periodic message for validating an established ad hoc distance vector route between a source point and a destination point of said mesh network, wherein said mesh network is organized as a spanning tree routing topology connecting each mesh point in the mesh network, and wherein said spanning tree routing topology is defined by a root node that connects said mesh network with a network gateway; and a transmitter, coupled to said memory, for transmitting messages, wherein said transmitter is configured to transmit a unicast route reply message for confirming the validity of said established ad hoc distance vector route, wherein upon a failure to receive said anticipated unicast periodic message, said transmitter is configured to: transmit a unicast data packet through a pre-configured route of said spanning tree routing topology connecting said source point to said destination point until a new ad hoc distance vector route can be established between said source point and said destination point, and wherein said new ad hoc distance vector route contains fewer hops than said pre-configured route; flag said unicast data packet as being transmitted intramesh; and receive a broadcast route request message, responsive to said flagged unicast data packet, wherein said broadcast route request message is broadcast using a hybrid ad hoc on-demand distance vector (AODV) protocol that includes a hop limit parameter comprising fewer hops than said pre-configured path, and wherein said new route is determined based on route response messages to said broadcast route request message that indicate a shortest path between said source point and said destination point. 17. The mesh point of claim 16, wherein, if said hop limit parameter in said anticipated unicast periodic message is greater than one, said transmitter is configured to forward said anticipated unicast periodic message along said established ad hoc distance vector route, and wherein said established ad hoc distance vector route contains fewer hops than said pre-configured route. 18. The mesh point of claim 16, wherein, if said anticipated unicast periodic message is not received, said transmitter is configured to propagate a route error message from said mesh point throughout said spanning tree routing topology to avoid flooding said mesh network with duplicate route error messages, and wherein said memory is configured to update stored route information to reflect said route error message. 19. A method comprising: receiving, into a root node of a wireless mesh network, a packet from a mesh node within said wireless mesh network and directed towards a destination in a connected local area network (LAN), wherein said LAN is a separate network from said wireless mesh network; transmitting said packet to said LAN via a root portal, wherein said root portal connects said root node of said wireless mesh network to said LAN; forwarding said packet to one or more non-root nodes of said wireless mesh network, each of said one or more non-root nodes associated with a non-root portal, wherein said non-root portal connects said wireless mesh network to said LAN; receiving at said root node a gratuitous route reply from said one or more non-root nodes via a spanning tree based routing topology of said wireless mesh network defined by said root node, wherein said gratuitous route reply indicates that said destination was reached via said one or more non-root portals; and establishing a hybrid ad hoc on-demand distance vector (AODV) route between said destination and said mesh node, wherein said AODV route comprises a path including said one or more non-root nodes that sent said gratuitous route reply. 20. The method of claim 19 wherein said one or more non-root nodes communicate an existence of said non-root portal with said root node via said spanning tree based routing topology of said wireless mesh network.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (67)
Mazzola Mario ; Edsall Tom ; Cafiero Luca, Address translation mechanism for a high-performance network switch.
Videlock Gary B. (Foxborough MA) Gocht Russell C. (North Attleboro MA) Freitas AnneMarie (E. Walpole MA) Freitas Mark J. (E. Walpole MA), Apparatus and method for learning and filtering destination and source addresses in a local area network system.
Corbalis Charles M. (Milpitas CA) Bustini Lionel A. (Campbell CA) Daley Patrick D. (Belmont CA), Circuitry and method for fair queuing and servicing cell traffic using hopcounts and traffic classes.
Hosoe Makoto,JPX, Client-server system, server access authentication method, memory medium stores server-access authentication programs, and issuance device which issues the memory medium contents.
Hiller Thomas L. (Glen Ellyn IL) Phelan James J. (Downers Grove IL) Zola Meyer J. (Oak Park IL), Establishing telecommunications call paths between clustered switching entities.
Hiller Thomas L. (Glen Ellyn IL) Phelan James J. (Downers Grove IL) Zola Meyer J. (Oak Park IL), Establishing telecommunications call paths in broadband communication networks.
Doeringer Willibald (Langnau am Albis CHX) Dykeman Douglas (Rueschlikon NC CHX) Edwards Allan K. (Raleigh NC) Pozefsky Diane P. (Chapel Hill NC) Sarkar Soumitra (Cary NC) Turner Roger D. (Cary NC), Inter-domain multicast routing.
Behaghel Denis,FRX ; Burgain Alain,FRX ; Ould Ali Abdelhamid,FRX, Local area network interconnection system implementing a routing protocol of the "source routing" type and interconnec.
James E. Kracht, Mechanism for determining actual physical topology of network based on gathered configuration information representing true neighboring devices.
Oppenheimer Alan B. (Cupertino CA) Findley Sean J. (Gilroy CA) Sidhu Gursharan S. (Menlo Park CA), Method and apparatus for determining whether an alias is available to uniquely identify an entity in a communications sy.
Peterson John C. (Alta Loma CA) Chow Edward (San Dimas CA) Madan Herb S. (Marina del Rey CA), Method and apparatus for eliminating unsuccessful tries in a search tree.
Klausmeier Daniel E. (Sunnyvale CA) Corbalis Charles M. (Saratoga CA), Method and apparatus for implementing communication service contract using cell arrival information.
Cole Bruce A. ; Forster James Ronald, Method and apparatus for serverless internet protocol address discovery using source address of broadcast or unicast pac.
Nessett Danny M. ; Grabelsky David ; Borella Michael S. ; Sidhu Ikhlaq S., Method and system for locating network services with distributed network address translation.
Pohjakallio Pekka (Espoo FIX), Method and system for sending shorter service number in place of all but first packet, in place of longer destination ad.
Cidon Israel (Haifa NC ILX) Davenport David W. (Raleigh NC) Derby Jeffrey H. (Chapel Hill NC) Dudley John G. (Raleigh NC) Gopal Inder S. (Fort Lee NJ) Janniello James P. (Stamford CT) Kaplan Marc A. , Methods and apparatus for routing packets in packet transmission networks.
McKee Neil H.,GB2 ; Phaal Peter, Network anaysis method for identifying global and local node servers and for determining a reconfigured network to provi.
Markkula ; Jr. Armas C. (Woodside CA) Sander Wendell B. (Los Gatos CA) Evan Shabtai (Saratoga CA) Smith Stephen B. (Scotts Valley CA) Twitty William B. (Santa Cruz CA), Network and intelligent cell for providing sensing bidirectional communications and control.
Valizadeh Homayoun S. (San Ramon CA) Grandhi Madhu R. (Fremont CA), Network switch having network management agent functions distributed among multiple trunk and service modules.
Lamport Leslie B. (Palo Alto CA) Rodeheffer Thomas L. (Mountain View CA) Chandy K. Mani (Pasadena CA), Reconfiguration system and method for high-speed mesh connected local area network.
Brewer Jason M. ; Linn John C. ; Perrin Keith L. ; Tonsing Robert E., System with program for automating protocol assignments when newly connected to varing computer network configurations.
Lapuh,Roger; Zhao,Yili; Tawbi,Wassim; Regan,Joseph M.; Head,David, System, device, and method for improving communication network reliability using trunk splitting.
Chou, Chun-Ting, Method of discovering an ad-hoc on-demand distance vector route having at least a minimum set of available resources in a distributed wireless communications network.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.