Distributed path update in hybrid networks

• US 9,184,998 B2
• Filed: 03/14/2013
• Issued: 11/10/2015
• Est. Priority Date: 03/14/2013
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Xue, Qi
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Kaur, Pamit
• Application Number:
  US13/827,338
• Publication Number:
  US 20140269260A1
• Time in Patent Office: 971 Days
• Field of Search: 370/225, 370/252
• US Class Current: 1/1
• 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 for modifying paths in a hybrid network which includes at least one hybrid device that is capable of communicating via multiple communication media, said method comprising:

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

selecting a second path to replace the first path for the candidate stream, wherein said selecting the second path comprises,

for each of at least two available paths between a first hybrid device and a second hybrid device, determining an end-to-end path capacity from the first hybrid device to the second hybrid device, wherein said determining the end-to-end path capacity includes determining whether at least two links in the available path share a same medium; and

selecting one of the at least two available paths based, at least in part, on the determined end-to-end path capacities.

2. The method of claim 1, further comprising detecting network condition associated with the impaired link, where said detecting includes at least one member selected from the group comprising:

detecting a link failure associated with the impaired link,

receiving a topology change notification from a device in the first path,

receiving a message from a device in the first path, the message indicating a change in link metrics for the impaired link, and

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

3. The method of claim 1, wherein said identifying the candidate stream includes detecting at least one entry associated with an impacted stream in a stream forwarding table at the hybrid device, the entry having next hop path information associated with the impaired link.

4. The method of claim 1, wherein said identifying the candidate stream includes, for each entry in a stream forwarding table at the hybrid device, determining whether the entry is associated with a stream that uses a path that includes the impaired link.

5. The method of claim 1, wherein said identifying the candidate stream includes identifying a stream that is associated with an ingress media type different from an egress media type.

6. The method of claim 1, wherein said selecting the second path further comprises selecting a path having a greater end-to-end path capacity than a current stream data rate associated with the candidate stream.

7. The method of claim 1, further comprising:

gathering topology information about the hybrid network; and

analyzing the topology information to determine at least one available path for the candidate stream between the first hybrid device and the second hybrid device.

8. The method of claim 1, wherein said selecting the second path further includes:

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

determining a path capacity for the interface at the hybrid device based, at least in part, on a result of said difference between the SMU and the MU.

9. The method of claim 1, wherein, said selecting the second path further includes:

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

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

dropping packets for the candidate stream in response to the number of hops of each of the at least two available paths exceed a threshold.

11. 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.

12. 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.

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

14. The method of claim 1, further comprising:

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

updating the second stream to use the second path.

15. 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 second path; and

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

16. The method of claim 15, further comprising:

generating a pseudorandom number for the candidate stream; and

wherein said updating and forwarding are based, at least in part, on the pseudorandom number.

17. The method of claim 16, further comprising:

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

18. A hybrid device comprising:

at least one local interface capable of communicating via a hybrid network that includes at least one hybrid device that is capable of communicating via multiple communication media;

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

a path selection unit configured to,

identify a candidate stream that is using a first path that includes an impaired link; and

select a second path to replace the first path for the candidate stream by,

for each of at least two available paths between a first hybrid device and a second hybrid device, determining an end-to-end path capacity from the first hybrid device to the second hybrid device, wherein said determining the end-to-end path capacity includes determining whether at least two links in the available path share a same medium; and

selecting one of the at least two available paths based, at least in part, on the determined end-to-end path capacities.

19. The first hybrid device of claim 18, further comprising a topology management unit configured to detect a network condition associated with the impaired link, wherein said topology management unit is further configured to:

detect a link failure associated with the impaired link;

receive a topology change notification from a device in the first path;

receive a message from a device in the first path, the message indicating a change in link metrics for the impaired link; and

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

20. The hybrid device of claim 18, 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 hybrid device, the entry having next hop path information associated with the impaired link.

21. The hybrid device of claim 18, wherein the path selection unit is configured to:

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

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

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

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

24. The hybrid device of claim 18, wherein the impaired link is saturated due to overloading of elastic streams, and the path selection unit is configured to identify a stream that is elastic.

25. The hybrid device of claim 18, 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 second path.

26. The hybrid device of claim 18, 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 second path; and

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

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

generate a pseudorandom number for the candidate stream; and

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

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

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

29. 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, a network condition in a hybrid network which includes at least one hybrid device that is capable of communicating via multiple communication media, the network condition associated with an impaired link;

identify, a candidate stream that is using a first path that includes the impaired link; and

select a second path to replace the first path for the candidate stream by,

for each of at least two available paths between a first hybrid device and a second hybrid device, determining an end-to-end path capacity from the first hybrid device to the second hybrid device, wherein said determining an end-to-end path capacity includes determining whether at least two links in the available path share a same medium; and

selecting one of the at least two available paths based, at least in part, on the determined end-to-end path capacities.