DISTRIBUTED PATH SELECTION IN HYBRID NETWORKS

• US 20140269691A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Abandoned Application

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Xue, Qi, Tinnakornsrisuphap, Peerapol
• Application Number:
  US13/828,776
• Publication Number:
  US 20140269691A1
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/38 Flow based routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A hybrid device may select a next hop for a packet stream based upon a path selection. The path selection includes calculating end-to-end path capacity for candidate paths to a destination device. End-to-end path capacity is calculated based upon contention groups of particular links in at least one of the plurality of paths. Selected paths are recorded in a stream forwarding table for use with subsequent packets of a packet stream. In some embodiments, each hybrid device independently performs path selection logic or path update logic for a packet stream.

Claims

1. A method comprising:

receiving an incoming packet at a first hybrid device;

determining a destination device based upon a destination address in the incoming packet;

determining path capacities for a plurality of paths through a hybrid network from a source device to the destination device, the determined path capacities based, at least in part, upon contention groups of particular links in at least one of the plurality of paths; and

selecting, at the first hybrid device, one of the plurality of paths to the destination device based, at least in part, upon the determined path capacities.

2. The method of claim 1, wherein the contention groups of particular links include a first contention group having more than one link that uses a same shared media.

3. The method of claim 1, further comprising:

collecting link metric information regarding particular links in at least one of the plurality of paths, said link metric information including at least link media type and link capacity.

4. The method of claim 3, wherein said collecting link metric information includes:

sending a link query message to a second hybrid device in at least one of the plurality of paths; and

receiving a link response message from the second hybrid device, the link response message including the link metric information.

5. The method of claim 1, wherein said determining path capacities includes:

identifying at least one contention group in said at least one of the plurality of paths, the contention group including two or more links that interfere with each other; and

determining contention group link capacity based upon a minimum link capacity of the two or more links in the contention group, wherein the contention group link capacity decreases as a quantity of links in the contention group increases,

wherein the path capacity is associated with a minimum capacity from of all contention groups and any ungrouped links in said at least one of the plurality of paths.

6. The method of claim 1, wherein said determining path capacities includes for each path to the destination device:

grouping links in the path that utilize a shared media to define contention groups;

defining contention groups for each remaining ungrouped link in the path;

determining link capacities for each contention group; and

determining a minimum link capacity from the determined link capacities, the minimum link capacity representing a determined path capacity for the path.

7. The method of claim 1, further comprising:

grouping paths of the plurality of paths to define at least one available path group, the available path group including paths to the destination device that share a legacy bridging device having paths to different relay hybrid devices;

defining available path groups for each remaining ungrouped path; and

defining an available path group path capacity for each available path group based upon path capacities for the paths in the available path group.

8. The method of claim 7, wherein said defining the available path group path capacity includes setting the available path group path capacity equal to the lowest path capacity of the path capacities for the paths in the available path group.

9. The method of claim 7, wherein said selecting includes:

selecting an available path group having the highest available path group path capacity; and

selecting one of the paths in the selected available path group based upon path capacity for the paths in the selected available path group.

10. The method of claim 1, wherein said selecting one of the plurality of paths to the destination device includes:

if the first hybrid device has a current path associated with another stream to the same destination, then prioritizing a first path that has a same egress interface and same next hop address over a second path that has the same egress interface but a different next hop address.

11. The method of claim 1, wherein said selecting one of the plurality of paths to the destination device includes:

selecting a path that has no more than a maximum hop count associated with the hybrid network.

12. The method of claim 1, further comprising:

forwarding the incoming packet via an egress interface of the first hybrid device to a target interface of a next hop device in the selected path.

13. The method of claim 1, further comprising:

determining stream identification information associated with the incoming packet; and

storing an entry with path forwarding information regarding the selected path in a forwarding table in relation to the stream identification information.

14. The method of claim 13, further comprising, prior to said selecting the selected path:

checking the forwarding table for the entry with the stream identification information; and

if the entry related to the stream identification information exists in the forwarding table, then forwarding the incoming packet in accordance with the path forwarding information in the entry.

15. The method of claim 13, wherein the path forwarding information regarding the selected path identifies an egress interface of the first hybrid device and a target destination address for a next hop device in the selected path.

16. The method of claim 13, wherein the stream identification information is determined from fields of the incoming packet, the fields including a source address, a destination address, a source port, a destination port, and a protocol identifier.

17. The method of claim 1, further comprising:

informing a second hybrid device about the selected one of the plurality of paths.

18. The method of claim 17, wherein the second hybrid device is a next hop device associated with the selected one of the plurality of paths.

19. The method of claim 17, wherein said informing the second hybrid device about the selected one of the plurality of paths comprises:

sending path information about more than one hop associated with the selected one of the plurality of paths.

20. A first hybrid device comprising:

at least one local interface capable of communicating via a hybrid network;

a memory configured to store topology information associated with the hybrid network; and

a path selection unit configured to select a path to a destination device based at least in part on the topology information, the path selection unit configured to

determine the destination device based upon a destination address in an incoming packet;

determine path capacities for a plurality of paths through the hybrid network from a source device to the destination device, the determined path capacities based, at least in part, upon contention groups of particular links in at least one of the plurality of paths; and

select one of the plurality of paths to the destination device based, at least in part, upon the determined path capacities.

21. The first hybrid device of claim 20, wherein the contention groups of particular links include a first contention group having more than one link that uses a same shared link media.

22. The first hybrid device of claim 20, wherein the path selection unit is further configured to:

collect link metric information regarding particular links in at least one of the plurality of paths, said link metric information including at least link media type and link capacity.

23. The first hybrid device of claim 20, wherein the path selection unit being configured to collect link metric information includes the path selection unit being configured to:

send a link query message to a second hybrid device in at least one of the plurality of paths; and

receive a link response message from the second hybrid device, the link response message including the link metric information.

24. The first hybrid device of claim 20, wherein the path selection unit being configured to determine path capacities includes the path selection unit being configured to:

identify at least one contention group in said at least one of the plurality of paths, the contention group including two or more links that interfere with each other; and

determine a contention group link capacity based upon a minimum link capacity of the two or more links in the contention group, wherein the contention group link capacity decreases as a quantity of links in the contention group increases,

wherein the determined path capacity for said at least one of the plurality of paths is associated with a minimum capacity from of all contention groups and any ungrouped links in said at least one of the plurality of paths.

25. The first hybrid device of claim 20, wherein the at least one local interface is configured to forward the incoming packet to a target interface of a next hop device in the selected path.

26. The first hybrid device of claim 20, wherein the path selection unit being configured to determine the path capacities includes the path selection unit being configured to, for each path to the destination device:

group links in the path that utilize a shared link media to define contention groups;

define contention groups for each remaining ungrouped link in the path;

determine link capacities for each contention group; and

determine a minimum link capacity from the determined link capacities, the minimum link capacity representing a determined path capacity for the path.

27. The first hybrid device of claim 20, wherein the path selection unit is further configured to:

group paths of the plurality of paths to define at least one available path group, the available path group including paths to the destination device that share a legacy bridging device having paths to different relay hybrid devices;

define available path groups for each remaining ungrouped path; and

define an available path group path capacity for each available path group based upon path capacities for the paths in the available path group.

28. The first hybrid device of claim 27, wherein the path selection unit being configured to define the available path group path capacity includes the path selection unit being configured to set the available path group path capacity equal to the lowest path capacity of the path capacities for the paths in the available path group.

29. The first hybrid device of claim 27, wherein the path selection unit is further configured to

select an available path group having the highest available path group path capacity;

and

select one of the paths in the selected available path group based upon path capacity for the paths in the selected available path group.

30. The first hybrid device of claim 27, wherein the path selection unit being configured to select one of the plurality of paths includes the path selection unit being configured to:

if the first hybrid device has a current path associated with another stream to the same destination, prioritize a first path that has a same egress interface and same next hop address over a second path that has the same egress interface but a different next hop address.

31. The first hybrid device of claim 27, wherein the path selection unit being configured to select one of the plurality of paths includes the path selection unit being configured to:

select a path that has no more than a maximum hop count associated with the hybrid network.

32. The first hybrid device of claim 27, wherein the path selection unit is further configured to

determine stream identification information associated with the incoming packet;

and

store an entry with path forwarding information regarding the selected path in a forwarding table in relation to the stream identification information.

33. The first hybrid device of claim 32, wherein the path selection unit is further configured to prior to selecting the selected path:

check the forwarding table for the entry with the stream identification information; and

if the entry related to the stream identification information exists in the forwarding table, then forward the incoming packet in accordance with the path forwarding information in the entry.

34. The first hybrid device of claim 32, wherein the path forwarding information regarding the selected path identifies an egress interface of the first hybrid device and a target destination address for a next hop device in the selected path.

35. The first hybrid device of claim 32, wherein the stream identification information is determined from fields of the incoming packet, the fields including a source address, a destination address, a source port, a destination port, and a protocol identifier.

36. A non-transitory computer readable medium storing computer program code, the computer program code comprising instructions which when executed by a processor of a hybrid device cause the hybrid device to:

determine a destination device based upon a destination address in an ingress packet;

identify a plurality of paths through a hybrid network from a source device to the destination device;

determine path capacities for each of the plurality of paths, the determined path capacities based, at least in part, upon contention groups of particular links in at least one of the plurality of paths; and

select, at the hybrid device, one of the plurality of paths to the destination device based, at least in part, upon the determined path capacities.