DISTRIBUTED PATH UPDATE IN HYBRID NETWORKS

• US 20140269260A1
• Filed: 03/14/2013
• Published: 09/18/2014
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Xue, Qi
• Granted Patent: US 9,184,998 B2
• Time in Patent Office: Days
• US Class Current: 370/225
• CPC Class Codes: H04L 41/0654 using network fault recovery ring fault isolation or reconfiguration in loop networks without recovery actions by a network management system H04L12/437
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/38 Flow based routing

Abstract

A network condition prompts a hybrid device to select a new path for a packet stream. A path update may occur in response to a change in network topology or a traffic loading condition (e.g., congestion or saturation of a link in the current path). Path selections may be made at each hybrid device in the path from a source hybrid device to a destination hybrid device. A path update procedure may be dependent upon path selection procedures that are optimized for a hybrid network in which multiple hybrid devices may be utilized for a particular path. Path update for load balancing may be dependent upon whether a packet stream is elastic or non-elastic.

Claims

1. A method comprising:

detecting, at a first hybrid device, a network condition in a hybrid network, the network condition associated with an impaired link between at least two devices in the hybrid network;

identifying, at the first hybrid device, a candidate stream that is using a current path that includes the impaired link; and

selecting a new path for the candidate stream, the new path selected based, at least in part, upon a position of the first hybrid device in the current path.

2. The method of claim 1, wherein the position of the first hybrid device in the current path is based, at least in part, upon a hop count from a source device to the first hybrid device or from the first hybrid device to a destination device.

3. The method of claim 1, further comprising:

determining a path capacity for a potential new path, wherein the determined path capacity for the potential new path is based, at least in part, upon an extended end-to-end path from a source device to a destination device.

4. The method of claim 1, wherein said detecting includes one or more of

detecting a link failure associated with a link in a path from the first hybrid device to a destination device,

receiving a topology change notification from the destination device or another hybrid device in the path from the first hybrid device to the destination device,

receiving a message from the destination device or another hybrid device in the path from the first hybrid device to the destination device, the message indicating a change in link metrics for the link in the path from the first hybrid device to the destination device, and

determining a loading condition for a local interface of the first hybrid device.

5. The method of claim 1, wherein identifying the candidate stream includes

detecting at least one entry associated with an impacted stream in a stream forwarding table at the first hybrid device, the entry having next hop path information associated with the impaired link.

6. The method of claim 1, wherein identifying the candidate stream includes

for each entry in a stream forwarding table at the first hybrid device, determining whether the entry is associated with a stream that uses a path that includes the impaired link.

7. The method of claim 1, wherein identifying the candidate stream includes

identifying the candidate stream that is associated with an ingress media type different from an egress media type.

8. The method of claim 1, wherein said selecting the new path comprises selecting the new path when a path capacity associated with the new path is greater than a current stream data rate associated with the candidate stream.

9. The method of claim 1, further comprising:

gathering topology information about the hybrid network; and

analyzing the topology information to determine at least one potential new path for the candidate stream from a source device to a destination device.

10. The method of claim 1, further comprising:

determining a path capacity for a potential new path based, at least in part, upon link metric information for at least one link in the potential new path,

wherein selecting the new path includes selecting, as the new path, the potential new path if the path capacity for the potential new path is greater than a current path capacity associated with the current path.

11. The method of claim 1, wherein said selecting the new path includes:

determine a difference between a stream medium utilization (SMU) associated with the candidate stream and a medium utilization (MU) measured for an interface at the first hybrid device that is in the current path associated with the candidate stream; and

determining a path capacity for a potential new path, wherein a determined path capacity for the interface at the first hybrid device is based in part upon a result of said difference between the SMU and the MU for the interface.

12. The method of claim 1, wherein, said selecting the new path includes:

selecting a path that does not exceed a maximum hop count associated with the hybrid network.

13. The method of claim 1, wherein said selecting the new path includes:

determining an end-to-end path capacity for a potential new path, the end-to-end path capacity based, at least in part, upon contention group link capacities for links in the potential new path; and

selecting the potential new path when the end-to-end path capacity for the potential new path is greater than a current stream data rate associated with the candidate stream.

14. The method of claim 1, wherein the method further comprises:

dropping packets for the candidate stream if end-to-end hybrid hops of every potential new path exceeds the maximum hop count associated with the hybrid network.

15. The method of claim 1, wherein the impaired link is congested due to overloading of non-elastic streams, and said identifying the candidate stream includes identifying a stream that is non-elastic.

16. The method of claim 1, wherein the impaired link is saturated due to overloading of elastic streams, and said identifying the candidate stream includes identifying a stream that is elastic.

17. The method of claim 1, wherein a stream forwarding table at the first hybrid device includes a forwarding decision timestamp for each entry, and wherein identifying the candidate stream includes identifying a stream associated with forwarding decision timestamp greater than a minimum time period.

18. The method of claim 1, further comprising:

identifying, at the first hybrid device, a second stream to a same destination as the candidate stream; and

updating the second stream to use the same selected new path as the candidate stream.

19. The method of claim 1, further comprising:

updating an entry for the candidate stream in a stream forwarding table, the updated entry indicating updated next hop information associated with the selected new path; and

forwarding subsequent packets for the candidate stream based, at least in part, upon the updated entry.

20. The method of claim 19, further comprising:

generating a random or pseudorandom number for the candidate stream; and

wherein said updating and forwarding are based, at least in part, upon the random or pseudorandom number

21. The method of claim 20, further comprising:

comparing the random or pseudorandom number to a configurable threshold value to determine whether to perform said updating and forwarding.

22. 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;

a topology management unit configured to detect, at the first hybrid device, a network condition in the hybrid network, the network condition associated with an impaired link between at least two devices in the hybrid network; and

a path selection unit configured to

identify, at the first hybrid device, a candidate stream that is using a current path that includes the impaired link responsive to the topology management unit detecting the network condition; and

select a new path for the candidate stream, the new path selected based, at least in part, upon a position of the first hybrid device in the current path.

23. The first hybrid device of claim 22, wherein the position of the first hybrid device in current path is based, at least in part, upon a hop count from a source device to the first hybrid device or from the first hybrid device to a destination device.

24. The first hybrid device of claim 22, wherein the path selection unit is further configured to determine a path capacity for a potential new path, wherein the determined path capacity for the potential new path is based, at least in part, upon an extended end-to-end path from a source device to a destination device.

25. The first hybrid device of claim 22, wherein the topology management unit is configured to:

detect a link failure associated with a link in a path from the first hybrid device to a destination device;

receive a topology change notification from the destination device or another hybrid device in the path from the first hybrid device to the destination device;

receive a message from the destination device or another hybrid device in the path from the first hybrid device to the destination device, the message indicating a change in link metrics for the link in the path from the first hybrid device to the destination device; and

determine a loading condition for a local interface of the first hybrid device.

26. The first hybrid device of claim 22, wherein the path selection unit is configured to detect at least one entry associated with an impacted stream in a stream forwarding table at the first hybrid device, the entry having next hop path information associated with the impaired link.

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

for each entry in a stream forwarding table at the first hybrid device, determine whether the entry is associated with a stream that uses a path that includes the impaired link.

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

identify the candidate stream that is associated with an ingress media type different from an egress media type.

29. The first hybrid device of claim 22, wherein the impaired link is congested due to overloading of non-elastic streams, and the path selection unit is configured to identify the candidate stream that is non-elastic.

30. The first hybrid device of claim 22, wherein the impaired link is saturated due to overloading of elastic streams, and the path selection unit is configured to identify the candidate stream that is elastic.

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

identify a second stream to a same destination as the candidate stream; and

update the second stream to use the same selected new path as the candidate stream.

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

update an entry for the candidate stream in a stream forwarding table, the updated entry indicating updated next hop information associated with the selected new path; and

forward subsequent packets for the candidate stream based, at least in part, upon the updated entry.

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

generate a random or pseudorandom number for the candidate stream; and

update the entry in a stream forwarding table based, at least in part, upon the random or pseudorandom number.

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

compare the random or pseudorandom number to a configurable threshold value to determine whether to update the entry.

35. 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:

detect, at the hybrid device, a network condition in a hybrid network, the network condition associated with an impaired link between at least two devices in the hybrid network;

identify, at the hybrid device, a candidate stream that is using a current path that includes the impaired link; and

select a new path for the candidate stream, the new path selected based, at least in part, upon a position of the hybrid device in the current path.