Distributed path selection in hybrid networks

• US 9,705,747 B1
• Filed: 11/25/2013
• Issued: 07/11/2017
• Est. Priority Date: 12/04/2012
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Tinnakornsrisuphap, Peerapol, Xue, Qi
• Primary Examiner(s): Ly, Anh-Vu
• Assistant Examiner(s): Reyes Ortiz, Hector
• Application Number:
  US14/089,086
• Time in Patent Office: 1,324 Days
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth

Abstract

A hybrid device may independently select a next hop for a packet stream based upon a path selection algorithm. The path selection algorithm 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.

Claims

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

receiving an incoming packet at a first hybrid device;

determining a destination device based, at least in part on, a destination address in the incoming packet;

determining a plurality of path capacities corresponding to a plurality of paths through the hybrid network from a source device associated with the incoming packet to the destination device, wherein the plurality of paths comprises at least a first path and determining a first path capacity for the first path comprises;

determining that the first path comprises a plurality of links that traverses a same communication medium leading to self-contention for resources of the same communication medium,

grouping the plurality of links as a first contention group, and

determining a first contention group link capacity for the first contention group, wherein the first path capacity is determined based, at least in part, on the first contention group link capacity; and

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

2. The method of claim 1, wherein determining the plurality of path capacities comprises determining contention groups, and wherein each contention group comprises a group of links that are associated with a same path and that use a same communication medium as other links in the group of links.

3. The method of claim 1, further comprising:

determining link metric information of one or more links in each path, the link metric information comprising link media type or link capacity or a combination thereof.

4. The method of claim 3, wherein determining the link metric information comprises:

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 comprising the link metric information.

5. The method of claim 1, wherein determining the first path capacity comprises:

determining the first contention group link capacity as a minimum media availability of the plurality of links in the first contention group divided by a sum of an inverse of a link rate for each of the plurality of links in the first contention group.

6. The method of claim 1, wherein determining the plurality of path capacities comprises, for each path of the plurality of paths:

grouping links in the path to define contention groups, wherein each contention group comprises a group of links that utilize a same communication medium as other links in the group of links;

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

determining link capacities for each contention group and for each of the additional contention groups; and

determining a minimum link capacity of the determined link capacities, wherein a determined path capacity for the path is based, at least in part, on the minimum link capacity.

7. The method of claim 1, further comprising:

grouping paths of the plurality of paths to define at least one available path group, the at least one 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, at least in part, on path capacities for the paths in the available path group.

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

9. The method of claim 7, wherein selecting comprises:

selecting one of the at least one available path group having a highest available path group path capacity; and

selecting one of the paths in the selected available path group based, at least in part on, path capacities for paths in the selected available path group.

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

in response to the first hybrid device having a current path associated with an existing stream to the destination device, selecting the current path.

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

selecting a path that has a hop count that does not exceed a maximum hop count of 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 in a forwarding table, the entry comprising path forwarding information of the incoming packet and at least a portion of the stream identification information.

14. The method of claim 1, further comprising:

determining stream identification information associated with the incoming packet;

checking a forwarding table for an entry with at least a portion of the stream identification information; and

in response to the entry with at least a portion of the stream identification information existing in the forwarding table, forwarding the incoming packet in accordance with path forwarding information in the entry.

15. The method of claim 13, wherein the path forwarding information comprises an identifier of 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 comprising:

a source address, the destination address, a source port, a destination port, and a protocol identifier.

17. A first hybrid device comprising:

at least one local interface for communicating via a hybrid network;

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

a processor configured to execute instructions stored in the memory that cause a path selection unit of the first hybrid device to;

determine a destination device based, at least in part, on a destination address in an incoming packet;

determine a plurality of path capacities corresponding to a plurality of paths through the hybrid network from a source device associated with the incoming packet to the destination device, wherein the plurality of paths comprises at least a first path and the instructions to determine a first path capacity for the first path comprise instructions to;

determine that the first path comprises at least a plurality of links that traverses a same communication medium leading to self-contention for resources of the same communication medium,

group the plurality of links as a first contention group, and

determine a first contention group link capacity for the first contention group, wherein the first path capacity is determined based, at least in part, on the first contention group link capacity; and

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

18. The first hybrid device of claim 17, wherein the instructions that cause the path selection unit to determine the plurality of path capacities comprises instructions that cause the path selection unit to determine contention groups, wherein each contention group comprises a group of links that are associated with a same path and that use a same communication medium as other links in the group of links.

19. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

determine link metric information of one or more links in each path, the link metric information comprising link media type or link capacity or a combination thereof.

20. The first hybrid device of claim 19, wherein the processor is configured to execute additional instructions that cause the path selection unit 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.

21. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

determine the first contention group link capacity as a minimum media availability of the plurality of links in the first contention group divided by a sum of an inverse of a link rate for each of the plurality of links in the first contention group.

22. The first hybrid device of claim 17, 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.

23. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to, for each path of the plurality of paths:

group links in the path to define contention groups, wherein each contention group comprises a group of links that utilize a same communication medium as other links in the group of links;

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

determine link capacities for each contention group and for each of the additional contention groups; and

determine a minimum link capacity of the determined link capacities, wherein a determined path capacity for the path is based, at least in part, on the minimum link capacity.

24. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

group paths of the plurality of paths to define at least one available path group, the at least one 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, at least in part, on path capacities for the paths in the available path group.

25. The first hybrid device of claim 24, wherein the processor is configured to execute additional instructions that cause the path selection unit to set the available path group path capacity equal to a lowest path capacity of the path capacities for the paths in the available path group.

26. The first hybrid device of claim 24, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

select one of the at least one available path group having a highest available path group path capacity; and

select one of the paths in the selected available path group based, at least in part, on path capacities for paths in the selected available path group.

27. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

when the first hybrid device having a current path associated with an existing stream to the destination device, select the current path.

28. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

select a path that has a hop count that does not exceed a maximum hop count of the hybrid network.

29. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

determine stream identification information associated with the incoming packet; and

store an entry in a forwarding table, the entry comprising path forwarding information of the incoming packet and at least a portion of the stream identification information.

30. The first hybrid device of claim 17, wherein the processor is configured to execute additional instructions that cause the path selection unit to:

determine stream identification information associated with the incoming packet;

check a forwarding table for an entry with at least a portion of the stream identification information; and

in response to the entry with at least a portion of the stream identification information existing in the forwarding table, forward the incoming packet in accordance with path forwarding information in the entry.

31. The first hybrid device of claim 29, wherein the path forwarding information comprises an identifier of an egress interface of the first hybrid device and a target destination address for a next hop device in the selected path.

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

33. 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, at least in part, on a destination address in an ingress packet;

identify a plurality of paths through a hybrid network from a source device associated with the ingress packet to the destination device;

determine a plurality of path capacities corresponding to the plurality of paths, wherein the plurality of paths comprises at least a first path and the instructions to determine a first path capacity for the first path comprise instructions to;

determine that the first path comprise at least a plurality of links that traverses a same communication medium leading to self-contention for resources of the same communication medium,

group the plurality of links as a first contention group, and

determine a first contention group link capacity for the first contention group, wherein the first path capacity is determined based, at least in part, on the first contention group link capacity; and

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