System and method for spanning tree cross routes

• US 20070110024A1
• Filed: 11/14/2005
• Published: 05/17/2007
• Est. Priority Date: 11/14/2005
• Status: Abandoned Application

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Meier, Robert
• Application Number:
  US11/273,118
• Publication Number:
  US 20070110024A1
• Time in Patent Office: Days
• US Class Current: 370/351
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/42 Centralised routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership

Abstract

A spanning tree cross-route protocol for establishing mesh-like cross routes in an underlying wireless spanning tree topology. A cross route spans branches of the tree topology to provide a more optimal route between any two nodes in the wireless network. The cross route can span multiple spanning trees. Each mesh node maintains a cross route table. When a packet is received, the node determines whether there is an entry for the destination node in the cross route table. If there is an entry for the destination node in the cross route table, the packet is forwarded via the cross route; otherwise, the packet is forwarded via the spanning tree.

Claims

1. A wireless network node, comprising:

a wireless transceiver;

a cross route table;

at least one port coupled to a spanning tree network;

wherein the wireless network node is configured to be responsive to receiving a packet sent from a source node addressed to a destination node to determine whether an entry exists for the destination node;

wherein the network node is responsive to route the packet on a cross route responsive to an entry existing in the cross route table for the destination node; and

wherein the network node is responsive to route the packet on the at least one spanning tree port responsive to no entry existing in the cross route table for the destination node.

2. A wireless network node according to claim 1, further comprising the wireless network node configured to store a path instance for every descendant node in the spanning tree network.

3. A wireless network node according to claim 2, further comprising the wireless network node configured to be responsive to a request for establishing a cross route from a source node to a destination node to determine a path from the source node to the destination node.

4. A wireless network according to claim 3, wherein the source node and the destination node are descendant nodes of the wireless network node.

5. A wireless network node according to claim 4, wherein the network node is a root node coupled to the root of the spanning tree.

6. A wireless network node according to claim 5, wherein the wireless network node uses Dijsktra shortest path algorithm to determine cross routes.

7. A wireless network node according to claim 5, wherein the root node is not in the data path

8. A wireless network node according to claim 5, wherein the wireless network node is configured to route the packet on the distribution network responsive to determining the destination node is not in the spanning tree of the root node.

9. A wireless network node according to claim 5, wherein the wireless network node is a root node coupled to a distribution node.

10. A wireless network node according to claim 8, wherein the frame is marked as a mesh frame, the wireless network node configured not to forward the mesh frame on the distribution network.

11. A wireless network node according to claim 9, wherein the distribution network is one of the group consisting of an Ethernet network and an Internet Protocol network.

12. A wireless network node according to claim 1, further comprising the wireless network node configured to delete a cross route responsive to one of the group consisting of the source node and the destination node roaming.

13. A wireless network node according to claim 1, wherein the wireless network node is a mesh node configured to provide cross route for a non-mesh node a sub-tree of the spanning tree network below the wireless network node.

14. A wireless network node according to claim 1, wherein the wireless network node is a common ancestor to the source node and the destination node, wherein the wireless network node is configured to establish a cross route between the source node and the destination node.

15. A wireless network node according to claim 1, further comprising the wireless network node configured to route a unicast frame on the spanning tree when the destination node is a descendant of the wireless network node.

16. A wireless network node according to claim 1, further comprising the wireless network node configured to forward a frame received on a cross route inbound on the spanning tree if the destination node is unknown.

17. A wireless network node according to claim 1, further comprising the wireless network node configured to propagate discovery messages only on the spanning tree.

18. A wireless network node according to claim 1, further comprising:

the wireless network node configured to establish a cross route identification for a cross route; and

the wireless network node configured to cache the cross route identification in the cross route table;

wherein the cross route identification comprises a path identification that is established by a nearest common ancestor of the source node and the destination node, and a sequence number.

19. A wireless network node according to claim 18, further comprising the wireless network node configured to discard a message with a cross route identification that is older that the cross route identification stored in the cross route table.

20. A wireless network node according to claim 1, wherein the wireless network node is a nearest common ancestor to the source node and the destination node, further comprising:

the wireless network node configured to establish security credentials for the source node and the destination node to communicate with each other; and

the wireless network node configured to establish the security credentials to the source node and the destination node.

21. A wireless network node according to claim 20, wherein the wireless network node establishes security credentials for the source node and the destination node to communicate with each other responsive to receiving a request to establish a cross route between the source node and the destination node.

22. A wireless network node according to claim 1, further comprising:

the wireless network node configured to reserve bandwidth for a quality of service stream on an inbound path of the spanning tree; and

the wireless network node configured to releasing the bandwidth reserved for the quality of service stream on an inbound path of the spanning tree responsive to the quality of service stream moved to a cross route.

23. A wireless network node according to claim 1, further comprising the wireless node configured to propagate a cross route discovery message on an inbound port except for when the node knows that the destination node is in its spanning tree path.

24. A wireless network node according to claim 1, further comprising the wireless node configured to propagate a cross route discovery message on all cross route ports and inbound ports except for the port the cross route discovery message was received and a port coupled to the distribution network.

25. A method, comprising:

maintaining a cross route table;

receiving a packet on a wireless network port, the packet having a source node address and a destination node address;

determining whether a cross route entry exists for the destination node in the cross route table;

forwarding the packet on a spanning tree port responsive to determining no cross route entry exists for the destination node address in the cross route table; and

forwarding the packet on a cross link port responsive to determining a cross route entry exists for the destination node address.

26. A method according to claim 25, further comprising storing a path instance for every descendant node.

27. A method according to claim 26, further comprising:

receiving a request to establish a cross route between the source node and the destination node;

determining a path from the source node to the destination node; and

establishing the cross route from the source node to the destination node.

28. A method according to claim 27, wherein the source node and the destination node are descendant nodes.

29. A method according to claim 27, wherein the determining a path from the source node to the destination node uses a Dijsktra shortest path algorithm.

30. A method according to claim 25, further comprising routing the packet on the distribution network responsive to determining the destination node is not in a spanning tree.

31. A method according to claim 25, wherein the frame is a mesh frame, the method further comprising preventing the frame from being sent on a distribution network coupled to the spanning tree.

32. A method according to claim 25, further comprising deleting a cross route inte the cross route table responsive to one of the group consisting of the source node and the destination node roaming.

33. A method according to claim 25, further comprising routing a unicast frame on the spanning tree when the destination node is a descendant.

34. A method according to claim 25, further comprising forwarding a frame received on a cross route inbound on the spanning tree if the destination node address is unknown.

35. A method according to claim 25, further propagating a cross route discovery message only on the spanning tree.

36. A method according to claim 25, further comprising:

establishing a cross route identification for a cross route; and

caching the cross route identification in the cross route table;

wherein the cross route identification comprises a path identification that is established by a nearest common ancestor of the source node and the destination node, and a sequence number

37. A method according to claim 25, further comprising discarding a message with a cross route identification that is older that the cross route identification stored in the cross route table.

38. A method according to claim 25, further comprising establishing security credentials for the source node and the destination node to communicate with each other by a nearest common ancestor to the source node and the destination node.

39. A method according to claim 25, further comprising:

reserving bandwidth for a quality of service stream on an inbound path of the spanning tree; and

releasing the bandwidth reserved for the quality of service stream on an inbound path of the spanning tree responsive to the quality of service stream moved to a cross route.

40. A method according to claim 25, further comprising the

receiving a cross route discover message on an outbound port;

determining whether the destination node address is in the spanning tree;

forwarding the cross route discovery message on an inbound port responsive to determining the destination node is not in the spanning tree; and

establishing the cross route responsive to the destination node address being in the spanning tree path.

41. A method according to claim 25, further comprising:

receiving a cross route discovery message; and

propagating the cross route discovery message on all cross route ports, all outbound ports and the inbound port except for the port the cross route discovery message was received on and a port coupled to the distribution network.

42. A wireless network topology, comprising

an underlying tree topology, with a single root node;

and

at least one cross link that exist between branches of the tree topology;

wherein the tree topology provides default data forwarding paths and a cross route, comprised of the at least one cross link, is established to provide more optimal forwarding paths.

43. The network topology of claim 42, wherein nodes in the wireless network are reliably registered with the root node and cross routes are established for registered nodes.

44. The network topology of claim 43, further comprising:

a wireless node configured to register a set of neighbor nodes with the root node, wherein each neighbor node is directly reachable via a single wireless link; and

wherein the root node maintains a database that contains entries for wireless nodes and neighbor sets for wireless nodes.

45. The network topology as in claim 44 wherein the root node is at one of the group consisting of the root of the entire wireless network topology tree and the root of a sub tree in the network topology tree.

46. The network topology as in claim 45, wherein the root node determines that a cross route can be established for two registered nodes, which are actively communicating, by examining the set of neighbors for registered nodes in its database and where the root node sends a cross route to one of the registered nodes.

47. The network topology as in claim 46, further comprising

a first originator node configured to send a query to the root node for a cross route to a second target node;

the root node configured to determine if a cross route to the target node can be established responsive to the query;

the root node responsive to send a reply message to the originator node, which contains an indication if the cross route exists; and

,

the root node configured to send the cross route to the originator node, when the cross route exists, wherein the cross route is comprised of an ordered list of registered nodes.

48. The network topology as in claim 47, wherein the originator node is one of the group consisting of a node that is communicating with the target node, and a parent node in the topology tree of a node that is communicating with the target node.

49. The network topology as in claim 46, further comprising:

an originator node configure to send a cross route setup request message to a second target node after it receives the cross route from the root node; and

the target node configured to send a cross route setup reply message to the originator node;

wherein the cross route setup request and reply messages establish a cross route from to the target node;

where data packets are forwarded on the cross route after it is established, and where nodes on the cross route maintain cross route information for the target node.

50. The network topology as in claim 49, wherein the cross route setup request and reply messages also establish a cross route to the originator node and corresponding cross route information in nodes on the cross route.

51. The network topology as in claim 46, wherein wireless nodes establish security credentials with the root node, further comprising:

the root node configured to allocate security credentials for a first node and a second neighbor node; and

wherein the security credentials shared by the first node and the second neighbor node are used to protect messages that are used to establish a cross route that includes the two nodes.

52. The network topology as in claim 45,

wherein at least one portal is used to relay data frames between a wireless network and a distribution network;

where the root of the network topology tree is located on the distribution network;

wherein a logical link exists between each portal and the root of the network topology; and

wherein a wireless spanning sub tree is rooted at each portal.

53. The network topology as in claim 50, further comprising

a node coupled to a branch of the tree topology;

wherein the node maintains a route table that is comprised of spanning tree route entries for descendant nodes in the topology tree, and cross route entries for nodes that are accessible via a cross route;

where the node examines the route table responsive to receiving a unicast message;

wherein the node is responsive to forward the message on a corresponding cross route to the destination responsive to finding a cross route entry for the destination node;

wherein the node forwards the message outbound on a corresponding spanning tree path to the destination responsive to the node having a spanning tree route entry for the destination node; and

wherein the node performs one of the group consisting of forwarding the message inbound on the spanning tree path to the root and discarding the message responsive to the node not having a route entry for the destination.

54. The network topology as in claim 53,

wherein the route table comprises a cross route entry and a spanning tree route entry for the same destination node;

and

wherein the node is responsive to selectively forwards traffic streams destined to the destination node on both the cross route path and the spanning tree path.

55. The network topology as in claim 50,

wherein a cross route for a node is uniquely identified by a node identifier and a cross route identifier;

wherein a high-order component of the cross route identifier is comprised of a spanning tree path instance identifier allocated for the node by the network topology root; and

wherein the spanning path instance identifier uniquely identifies the node'"'"'s spanning tree path instance within the network tree topology.

56. The network topology as in claim 55,

wherein the cross route identifier is contained in messages that are used to establish and delete cross routes and cross route table entries;

wherein nodes use cross route identifiers to order cross route messages; and

wherein a node does not update a cross route table entry when it receives a cross route message responsive to the cross route identifier in the table entry for the respective node is newer than the cross route identifier in the message.

57. A wireless networking node, comprising:

means for receiving a wireless frame, the wireless frame having a source address and a destination address;

means for maintaining a cross route table; and

means for routing the wireless frame coupled to the means for receiving and the means for maintaining, the means for routing responsive to determining whether a cross route entry exists for the destination node in the cross route table to forwarding the packet on a cross link port responsive to determining a cross route entry exists for the destination node address, and the means for routing responsive to forwarding the packet on a spanning tree port responsive to determining no cross route entry exists for the destination node address in the cross route table.