Method and apparatus for generating routing information in a data communications network

• US 7,580,360 B2
• Filed: 10/14/2003
• Issued: 08/25/2009
• Est. Priority Date: 10/14/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Shand, Ian Michael Charles, Bryant, Stewart Frederick
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US10/685,621
• Publication Number:
  US 20050078656A1
• Time in Patent Office: 2,142 Days
• Field of Search: 370/400, 370/255, 370/238, 370/237, 370/238.1, 370/230.1, 370/231, 370/252, 370/253, 370/256, 370/258, 370/254, 370/235, 370/248, 370/251, 370/389, 370/411, 370/236
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/037 Routes obligatorily traversing service-related nodes
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08

Abstract

A method and apparatus are disclosed for generating routing information in a data communications network. A first network element (such as a router) receives information relating to a second network element, such as another node or a network link. In response, the first network element determines whether the information relating to the second network element indicates a change in the network. When information relating to a second network element indicates a change in the network, the first network element determines a new shortest path through the network from the first network element for each network element in the network. After a delay, the first network element updates routing information for the first network element based on the new shortest path for the first network element. Preferably the delay is proportional to the distance of the first network element from the second network element.

Claims

1. A method of generating routing information in a data communications network having, as elements, nodes and links, the method comprising the steps performed at a first network element of:

receiving at the first network element information relating to a change in the network at a second network element,

determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element,

determining a furthest network element in the affected set as located at a furthest distance from the first network element,

identifying a sequence in which updating of routing information at each network element in the affected set should occur, and

updating the routing information at the first element in sequence.

2. A method as claimed in claim 1 further comprising the steps of:

determining if the updated routing information differs from the routing information prior to the network change; and

maintaining the prior routing information at the first network element upon receipt of the information relating to the change if not.

3. A method as claimed in claim 1 in which the first network element updates after a delay derived from the updating sequence.

4. A method as claimed in claim 3

wherein the affected set of network elements further comprises the set of nodes from which a target network element is reachable via the second network element.

5. A method as claimed in claim 4 in which the second network element is a link and the target network element is an adjacent node.

6. A method as claimed in claim 4 further comprising the step of updating the first network element upon receipt of the information relating to the change if the first network element is not in the affected set.

7. A method as claimed in claim 4 in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set.

8. A method as claimed in claim 7 in which the delay is derived to ensure that the first network element only updates its routing information after all preceding network elements in the sequence have updated their routing information.

9. A method as claimed in claim 7 further comprising the step of:

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly; and

disregarding any network elements on the identified branches as the furthest network element.

10. A method as claimed in claim 4 further comprising the step of:

deriving a delay for data for a destination as a function of the number of hops to the furthest node in the respective affected set for that destination.

11. A method as claimed in claim 10 in which the change in the second network element comprises a link cost increase and the affected set of network elements further comprises the set of network elements from which the target network element is reachable prior to the network change.

12. A method as claimed in claim 11 in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set upstream of the first network element relative to the second network element.

13. A method as claimed in claim 11 further comprising the step of identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly and disregarding any network elements on the identified branches as the furthest network element.

14. A method as claimed in claim 4 further comprising the step of determining if the first network element forwards directly or indirectly data to nodes of the affected set upstream of the first network element relative to the second network element and, if not, identifying the first network element as the furthest node.

15. A method as claimed in claim 9 in which the change in the second network element comprises a link cost decrease and the affected set comprises the set of network elements from which the target network element is reachable after the network change.

16. A method as claimed in claim 1 further comprising the step of receiving a notification from a preceding network element in the sequence and updating the routing information upon receipt of the notification.

17. An apparatus for generating routing information in a data communications network having, as elements, nodes and links, comprising:

means for receiving at a first network element information relating to a change in the network at a second network element,

means for determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element,

means for determining a furthest network element in the affected set as located at a furthest distance from the first network element,

means for identifying a sequence for updating of routing information at each network element in the affected set, and

means for updating the routing information at the first element in sequence.

18. An apparatus as claimed in claim 17, in which the means for identifying an updated sequence determines if the updated routing information differs from the routing information prior to the network change and the means for updating maintains the prior routing information at the first network element upon receipt of the information relating to the change if not.

19. An apparatus as claimed in claim 17 in which the means for updating updates after a delay derived from the updating sequence.

20. An apparatus as claimed in claim 19 wherein the affected set of network elements further comprises the set of nodes from which a target network element is reachable via the second network element.

21. An apparatus as claimed in claim 20 in which the second network element is a link and the target network element is an adjacent node.

22. An apparatus as claimed in claim 20 in which the means for updating updates the first network element upon receipt of the information relating to the change if the first network element is not in the affected set.

23. An apparatus as claimed in claim 20 in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set.

24. An apparatus as claimed in claim 23 in which the delay is derived to ensure that the first network element only updates its routing information after all preceding network elements in the sequence have updated their routing information.

25. An apparatus as claimed in claim 23 further comprising means for identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly and disregarding any network elements on the identified branches as the furthest network element.

26. An apparatus as claimed in claim 20 further comprising means for:

deriving a delay for data for a as a function of the number of hops to the furthest node in the respective affected set for that destination.

27. An apparatus as claimed in claim 20 in which the change in the second network element comprises a link cost increase.

28. An apparatus as claimed in claim 27 in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set upstream of the first network element relative to the second network element.

29. An apparatus as claimed in claim 28 further comprising means for identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly and disregarding any network elements on the identified branches as the furthest network element.

30. An apparatus as claimed in claim 28 further comprising means for determining if the first network element forwards directly or indirectly data to nodes of the affected set upstream of the first network element relative to the second network element and, if not, identifying the first network element as the furthest node.

31. An apparatus as claimed in claim 20 in which the change in the second network element comprises a link cost decrease and the affected set comprises the set of network elements from which the target network element is reachable after the network change.

32. An apparatus as claimed in claim 17 further comprising means for receiving a notification from a preceding network element in the sequence and updating the routing information upon receipt of the notification.

33. An apparatus for generating routing information in a data communications network having as elements links and nodes, the apparatus comprising:

one or more processors;

a network interface communicatively coupled to the processor and configured to communicate one or more packet flows among the processor and a network; and

a computer readable medium comprising one or more sequences of instructions for generating routing information which instructions, when executed by one more processors, cause the one or more processors to generate routing information in a data communications network having, as elements, nodes and links, the method comprising the steps performed at a first network element of;

receiving at the first network element information relating to a change in the network at a second network element,

determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element,

determining a furthest network element in the affected set as located at a furthest distance from the first network element,

identifying a sequence in which updating of routing information at each network element in the affected set should occur, and

updating the routing information at the first element in sequence.

34. The apparatus of claim 33, in which the first network element updates after a delay derived from the updating sequence.

35. The apparatus of claim 34, in which the delay is:

(a) a function of the number of hops from the first network element to the furthest network element in the affected set in which the delay is; and

(b) derived to ensure that the first network element only updates its routing information after all preceding network elements in the sequence have updated their routing information.

36. The apparatus of claim 34, in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set in which the delay is;

further comprising the steps of;

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly; and

disregarding any network elements on the identified branches as the furthest network element.

37. The apparatus of claim 34, in which the change in the second network element comprises a link cost increase and the affected set comprises the set of network elements from which the target network element is reachable prior to the network change, further comprising the steps of:

deriving a delay for data for a destination as a function of the number of hops to the furthest node in the respective affected set for that destination; and

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly; and

disregarding any network elements on the identified branches as the furthest network element.

38. The apparatus of claim 34, further comprising the steps of:

determining if the first network element forwards directly or indirectly data to nodes of the affected set upstream of the first network element relative to the second network element and, if not, identifying the first network element as the furthest node.

39. The apparatus of claim 34, in which the change in the second network element comprises a link cost decrease and the affected set comprises the set of network elements from which the target network element is reachable after the network change;

and in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set in which the delay is and;

further comprising the steps of;

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly; and

disregarding any network elements on the identified branches as the furthest network element.

40. A computer readable storage medium storing one or more sequences of instructions for a data communications network having, as elements, links and nodes, which instructions, when executed by one or more processors, cause the one or more processors to generate routing information in a data communications network having, as elements, nodes and links, the computer-readable storage medium comprising the steps performed at a first network element of:

receiving at the first network element information relating to a change in the network at a second network element,

determining an affected set of network elements, wherein the affected set comprises network elements which are reachable from the second network element,

determining a furthest network element in the affected set as located at a furthest distance from the first network element,

identifying a sequence in which updating of routing information at each network element in the affected set should occur, and

updating the routing information at the first element in sequence.

41. The computer readable storage medium of claim 40, in which the first network element updates after a delay derived from the updating sequence.

42. The computer readable storage medium of claim 41 in which the delay is:

(a) a function of the number of hops from the first network element to the furthest network element in the affected set in which the delay is; and

(b) derived to ensure that the first network element only updates its routing information after all preceding network elements in the sequence have updated their routing information.

43. The computer readable storage medium of claim 41, in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set in which the delay is;

further comprising the steps of;

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly and;

disregarding any network elements on the identified branches as the furthest network element.

44. The computer readable storage medium of claim 41, in which the change in the second network element comprises a link cost increase and the affected set comprises the set of network elements from which the target network element is reachable prior to the network change, further comprising the steps of:

determining an affected set for each destination network element reachable via the second network element and deriving a delay for data for a destination as a function of the number of hops to the furthest node in the respective affected set for that destination; and

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly; and

disregarding any network elements on the identified branches as the furthest network element.

45. The computer readable storage medium of claim 41, further comprising the steps of:

determining if the first network element forwards directly or indirectly data to nodes of the affected set upstream of the first network element relative to the second network element and, if not, identifying the first network element as the furthest node.

46. The computer readable storage medium of claim 41, in which the change in the second network element comprises a link cost decrease and the affected set comprises the set of network elements from which the target network element is reachable after the network change;

and in which the delay is a function of the number of hops from the first network element to the furthest network element in the affected set in which the delay is and;

further comprising the steps of;

identifying branches of the affected set upstream of the first network element relative to the second network element to which the first network element does not forward data directly or indirectly; and

disregarding any network elements on the identified braches as the furthest network element.