ROUTING IN A HYBRID NETWORK

• US 20170195218A1
• Filed: 12/30/2015
• Published: 07/06/2017
• Est. Priority Date: 12/30/2015
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Schrum, JR., Sidney Brower, Yonge, III, Lawrence Winston, Newman, Richard Ernest
• Application Number:
  US14/985,359
• Publication Number:
  US 20170195218A1
• Time in Patent Office: Days
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/484 using multiple routing trees
• CPC Class Codes: H04L 45/488 using root node determination

Abstract

A hybrid network may include a mix of different network technologies and devices. A multi-interface device, such as a hybrid device, may provide for bridging of frames between different networks. Some routing schemes may not be suitable for a hybrid network. In this disclosure are various concepts for a routing scheme suitable for a hybrid network. In accordance with a routing scheme, one or more routing trees may be determined based on a topology map for the hybrid network. The topology map may include nodes to represent different interfaces of at least one multi-interface device. A routing tree determined based, at least in part, on the topology map may be used to manage routing of frames in the hybrid network.

Claims

1. A method for communicating via a network, the method comprising:

determining, at a first device, a topology map for the network having a plurality of devices including at least one multi-interface device, wherein the topology map includes interface-specific nodes to represent different interfaces of the at least one multi-interface device;

determining a routing tree for the network based, at least in part, on the topology map, the routing tree having a root node associated with one of the plurality of devices, wherein the routing tree defines routes from the root node to one or more destination nodes;

determining, for a frame originated from the root node, whether the first device is in a route from the root node to the one or more destination nodes based, at least in part, on the routing tree; and

forwarding the frame from the first device to the one or more destination nodes in accordance with the routing tree in response to a determination that the first device is in the route.

2. The method of claim 1, wherein determining the topology map comprises:

obtaining topology information identifying the different interfaces of the at least one multi-interface device, the topology information including a list of neighbor devices associated with each of the different interfaces.

3. The method of claim 1, wherein the topology map includes link costs between the different interfaces of the at least one multi-interface device and each neighbor device of a list of neighbor devices.

4. The method of claim 1, wherein the topology map includes either a forwarding or non-forwarding capability associated with each of the interface-specific nodes.

5. The method of claim 1, wherein determining the routing tree comprises:

determining the routing tree using a shortest path algorithm for unicast routes;

determining broadcast delivery options in the topology map;

for each broadcast delivery option;

selecting a broadcast path with a lowest path cost from the first device to a target device, and

adding the broadcast path to the routing tree as a route from the first device to the target device in response to a determination that the broadcast path has a lower total cost to reach nodes associated with the broadcast path than existing routes to those nodes and that the broadcast path does not reach a legacy device that already has a unicast route in the routing tree, and

pruning any unicast routes that terminates at one of a plurality of nodes associated with the broadcast path, wherein the unicast route is pruned to a previous node not in the plurality of nodes.

6. The method of claim 1, wherein the topology map includes a first link cost from a first node representing a first interface of the at least one multi-interface device to a second node representing a second interface of the at least one multi-interface device.

7. The method of claim 6, wherein the first link cost is nominal when the first interface and the second interface are in a same multi-interface device.

8. The method of claim 1, wherein determining the routing tree comprises:

defining a set of unvisited nodes in the topology map, the set of unvisited nodes including only nodes that have forwarding capabilities;

selecting the root node as a current node;

determining routes from the current node to neighbor nodes of the current node, wherein determining the routes comprises, for each neighbor node that has at least one link to the current node;

determining a first link from the current node to the neighbor node,

adding the first link to the routing tree as a new route from the current node to the neighbor node in response to a determination that the routing tree does not have an existing route to the neighbor node or that the new route has a lower path cost from the root node to the neighbor node than an existing route to the neighbor node, wherein the existing route is replaced by the new route, and

removing the current node from the set of unvisited nodes; and

selecting, from the set of unvisited nodes, a next node having a lowest path cost to the root node; and

repeating said determining routes using the next node as the current node.

9. The method of claim 1, further comprising:

optimizing the routing tree, wherein said optimizing includes pruning a unicast route that terminates at a particular device in response to adding a broadcast route to the routing tree that will reach the particular device.

10. The method of claim 1, wherein determining whether the first device is in the route comprises:

receiving the frame at a first interface of the first device, the frame having a source address associated with the root node and having a destination address associated with the one or more destination nodes; and

determining whether the first interface is in one of the routes of the routing tree from the root node to the one or more destination nodes.

11. The method of claim 10, further comprising:

discarding the frame based, at least in part, on a determination that the first interface of the first device is not in one of the routes of the routing tree.

12. The method of claim 1, wherein the routing tree comprises a common routing tree that is used by the plurality of devices of the network to route a frame having at least one member of the group consisting of an unknown source address, an unknown destination address, a broadcast address, and an indicator associated with routing frames with an unknown address.

13. The method of claim 12, further comprising:

sending routing information from the first device to a second device, the routing information usable by the second device to determine the common routing tree.

14. The method of claim 1, wherein the routing tree comprises a first routing tree used for unicast traffic, the method further comprising:

determining a second routing tree for the network based, at least in part, on the topology map, the second routing tree used for broadcast traffic, wherein the second routing tree includes at least one broadcast node, wherein the at least one broadcast node can represent either a physical layer (PHY) broadcast domain or a broadcast-to-unicast conversion broadcast domain.

15. The method of claim 14, wherein the second routing tree is optimized to reach each device of the plurality of devices, without regard to which interface of each device is used to reach each device, and wherein the topology map comprises a device-internal node to represent each device separately from the interface-specific nodes.

16. The method of claim 1, wherein the first device is a central coordinator for the network, the method further comprising sending the routing tree from the central coordinator to the plurality of devices.

17. The method of claim 1, further comprising:

determining a plurality of routing trees, each routing tree having a different root node that is specific to a source interface of one of the plurality of devices; and

upon receiving the frame, selecting a first routing tree of the plurality of routing trees based, at least in part, on a source address in the frame being associated with the source interface corresponding to the root node for the first routing tree; and

routing the frame in accordance with the first routing tree.

18. The method of claim 17, further comprising:

receiving the frame and determining that the frame contains an address that is not in the topology map;

selecting one of the plurality of routing trees using a common selection algorithm that is also used by other devices of the plurality of devices; and

routing the frame in accordance with the selected one of the plurality of routing trees.

19. A first device for communicating via a network, the first device comprising:

a processor; and

memory for storing instructions which, when executed by the processor, cause the first device to;

determine a topology map for the network having a plurality of devices including at least one multi-interface device, wherein the topology map includes interface-specific nodes to represent different interfaces of the at least one multi-interface device;

determine a routing tree for the network based, at least in part, on the topology map, the routing tree having a root node associated with one of the plurality of devices, wherein the routing tree defines routes from the root node to one or more destination nodes;

determine, for a frame originated from the root node, whether the first device is in a route from the root node to the one or more destination nodes based, at least in part, on the routing tree; and

forward the frame from the first device to the one or more destination nodes in accordance with the routing tree in response to a determination that the first device is in the route.

20. The first device of claim 19, wherein the instructions that cause the first device to determine whether the first device is in the route comprises instructions which, when executed by the processor, cause the first device to:

receive the frame at a first interface of the first device, the frame having a source address associated with the root node and having a destination address associated with the one or more destination nodes; and

determine whether the first interface is in one or the routes of the routing tree from the root node to the one or more destination nodes.

21. The first device of claim 20, further comprising instructions which, when executed by the processor, cause the first device to:

discard the frame based, at least in part, on a determination that the first interface of the first device is not in one of the routes of the routing tree.

22. The first device of claim 19, wherein the routing tree comprises a first routing tree used for unicast traffic, the memory storing further instructions which, when executed by the processor, cause the first device to:

determine a second routing tree for the network based, at least in part, on the topology map, the second routing tree used for broadcast traffic, wherein the second routing tree includes at least one broadcast node, wherein the at least one broadcast node can represent either a physical layer (PHY) broadcast domain or a broadcast-to-unicast conversion broadcast domain.

23. The first device of claim 19, further comprising instructions which, when executed by the processor, cause the first device to:

determine a plurality of routing trees, each routing tree having a different root node that is specific to a source interface of one of the plurality of devices; and

upon receiving the frame;

select a first routing tree of the plurality of routing trees based, at least in part, on a source address in the frame being associated with the source interface corresponding to the root node for the first routing tree; and

routing the frame in accordance with the first routing tree.

24. The first device of claim 19, further comprising:

a first interface; and

a second interface,

wherein the memory stores instructions which, when executed by the processor, cause the first device to;

independently set frame forwarding configurations for each of the first interface and the second interface based, at least in part, on the routing tree.

25. A non-transitory computer-readable medium storing instructions which, when executed by a processor of a first device, cause the first device to:

determine a topology map for a network having a plurality of devices including at least one multi-interface device, wherein the topology map includes interface-specific nodes to represent different interfaces of the at least one multi-interface device;

determine a routing tree for the network based, at least in part, on the topology map, the routing tree having a root node associated with one of the plurality of devices, wherein the routing tree defines routes from the root node to one or more destination nodes;

determine, for a frame originated from the root node, whether the first device is in a route from the root node to the one or more destination nodes based, at least in part, on the routing tree; and

forward the frame from the first device to the one or more destination nodes in accordance with the routing tree in response to a determination that the first device is in the route.

26. The non-transitory computer-readable medium of claim 25, wherein the instructions that cause the first device to determine the routing tree comprises instructions which, when executed by the processor, cause the first device to:

determine the routing tree using a shortest path routing algorithm for unicast routes; and

determine broadcast delivery options in the topology map;

for each broadcast delivery option;

select a broadcast path with a lowest path cost from the first device to a target device,

add the broadcast path to the routing tree in response to a determination that the broadcast path has a lower total cost to reach a plurality of nodes associated with the broadcast path than existing routes to the plurality of nodes and that the broadcast path does not reach a legacy device that already has a unicast route in the routing tree, and

prune any unicast routes that terminates at one of the plurality of nodes associated with the broadcast path, wherein the unicast route is pruned to a previous node not in the plurality of nodes.

27. The non-transitory computer-readable medium of claim 25, wherein the instructions that cause the first device to determine whether the first device is in the route comprises instructions which, when executed by the processor, cause the first device to:

receive the frame at a first interface of the first device, the frame having a source address associated with the root node and having a destination address associated with the one or more destination nodes; and

determine whether the first interface is in one of the routes of the routing tree from the root node to the one or more destination nodes.

28. The non-transitory computer-readable medium of claim 27, wherein instructions, when executed by the processor, cause the first device to:

discard the frame based, at least in part, on a determination that the first interface of the first device is not in one of the routes of the routing tree.

29. The non-transitory computer-readable medium of claim 25, wherein the routing tree comprises a common routing tree that is used by the plurality of devices of the network.

30. The non-transitory computer-readable medium of claim 25, wherein the instructions, when executed by the processor, cause the first device to:

optimize the routing tree to minimize total path cost to reach all devices of the plurality of devices in the network, regardless of which interface is used to reach each device.