Method and apparatus for managing a network component change

• US 7,496,644 B2
• Filed: 11/05/2004
• Issued: 02/24/2009
• Est. Priority Date: 11/05/2004
• 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): Nguyen; Phuoc H
• Application Number:
  US10/981,823
• Publication Number:
  US 20060101158A1
• Time in Patent Office: 1,572 Days
• Field of Search: 709/220, 709/221, 709/223, 709/238, 709/239
• US Class Current: 709/221
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A method is disclosed of managing a network component change in a data communications network having as components nodes and links defining a pre-change topology. A transitioning node forwards all data assigned to the pre-change topology via the pre-change topology. The transitioning node defines a post-change topology. The transitioning node transitions from the pre-change to the post-change topology. Data assigned to the pre-change topology is assigned to the post-change topology, and the transitioning node forwards the data via the post-change topology.

Claims

1. A method of managing a network component change in a data communications network having as components nodes and links defining a pre-change topology, comprising the steps, performed at a transitioning node, of:

forwarding all data assigned to the pre-change topology via the pre-change topology;

defining a post-change topology;

assigning all data assigned to the pre-change topology to the post-change topology;

transitioning from the pre-change to the post-change topology;

forwarding the data assigned to the post-change topology via the post-change topology;

assigning the pre-change topology to a first topology space and the post-change topology to a second topology space;

after transition to the post-change topology, rendering the first topology space congruent with the second topology space; and

transitioning from the post-change topology in the second topology space to the first topology space.

2. A method as claimed in claim 1 in which the network component change comprises at least one of a single or multiple component failure, additional or planned removal of a component, or variation of a component metric.

3. A method as claimed in claim 1 in which the step of defining a post-change topology comprises the step of converging a post-change topology.

4. A method as claimed in claim 1 further comprising the step of ceasing marking when all transitioning nodes have implemented the marking step and subsequently forwarding data via the post-change topology.

5. A method as claimed in claim 1 in which a data packet to be forwarded carries a marking representing a pre-change topology or a post-change topology.

6. A method as claimed in claim 1 in which the transitioning step is synchronized to an epoch.

7. A method as claimed in claim 6 further comprising the steps, performed at the transitioning node, of:

receiving a synchronization signal from a master node; and

commencing a transition epoch on receipt of the synchronization signal.

8. A method as claimed in claim 6 further comprising the step, performed at the transitioning node, of detecting a network clock signal and commencing a transition epoch upon said detection.

9. A method as claimed in claim 6 further comprising the steps, performed at a transitioning node, of:

commencing a transition epoch;

during a hold-down period receiving all notifications concerning network changes during the epoch;

terminating the hold-down period;

during a processing period, defining a post-change topology representing all network changes during the epoch;

terminating the processing period; and

transitioning to the post-change topology.

10. A method as claimed in claim 9 in which the transitioning node commences the transition epoch upon receipt of a notification of a network change in that epoch.

11. A method as claimed in claim 9 in which the transitioning node terminates the hold-down stage upon receipt of notification of a network change in a later epoch.

12. A method as claimed in claim 1 in which the network component change comprises a traffic volume dependent component metric change and in which the post-change topology represents the topology with the changed component metric.

13. A method as claimed in claim 1 in which the transitioning step comprises the steps of:

defining a transition topology;

marking data to be transitioned as assigned to the transition topology; and

forwarding marked data via the transition topology.

14. A method of managing a network having traffic dependent metrics in a data communications network having as components nodes and links defining a first traffic dependent topology comprising the steps, performed at a transitioning node of:

forwarding data via the first traffic dependent topology;

defining a second traffic dependent topology representing a traffic dependent network component change;

transitioning from the first to the second traffic dependent topology;

forwarding data via the second traffic dependent topology;

assigning the first traffic dependent topology to a first topology space and the second traffic dependent topology to a second topology space;

after transition to the second traffic dependent topology, rendering the first topology space congruent with the second topology space; and

transitioning from the post-change topology in the second topology space to the first topology space.

15. A method as claimed in claim 14 in which the transitioning step comprises the steps of:

defining a transition topology;

marking data to be transitioned as assigned to the transition topology; and

forwarding marked data via the transition topology.

16. A computer readable storage medium comprising one or more sequences of instructions for managing a network component change in a data communications network which, when executed by one or more processors, cause the one or more processors to perform:

forwarding all data assigned to the pre-change topology via the pre-change topology;

defining a post-change topology;

assigning all data assigned to the pre-change topology to the post-change topology;

transitioning from the pre-change to the post-change topology;

forwarding the data assigned to the post-change topology via the post-change topology;

assigning the pre-change topology to a first topology space and the post-change topology to a second topology space;

after transition to the post-change topology, rendering the first-topology space congruent with the second topology space; and

transitioning from the post-change topology in the second topology space to the first-topology space.

17. The computer readable medium of claim 16 in which the network component change comprises at least one of a single or multiple component failure, additional or planned removal of a component, or variation of a component metric.

18. The computer readable medium of claim 16 in which defining a post-change topology comprises converging a post-change topology.

19. The computer readable medium of claim 16, further comprising:

ceasing marking when all transitioning nodes have implemented the marking step and subsequently forwarding data via the post-change topology.

20. The computer readable medium of claim 16 in which a data packet to be forwarded carries a marking representing a pre-change topology or a post-change topology.

21. The computer readable medium of claim 16 in which the transitioning step is synchronized to an epoch.

22. The computer readable medium of claim 21, further comprising:

receiving a synchronization signal from a master node; and

commencing a transition epoch on receipt of the synchronization signal.

23. The computer readable medium of claim 21, further comprising:

detecting a network clock signal and commencing a transition epoch upon said detection.

24. The computer readable medium of claim 21, further comprising:

commencing a transition epoch;

during a hold-down period receiving all notifications concerning network changes during the epoch;

terminating the hold-down period;

during a processing period, defining a post-change topology representing all network changes during the epoch;

terminating the processing period; and

transitioning to the post-change topology.

25. The computer readable medium of claim 24 in which the transition epoch is commenced upon receipt of a notification of a network change in that epoch.

26. The computer readable medium of claim 24 in which the hold-down stage is terminated upon receipt of notification of a network change in a later epoch.

27. The computer readable medium of claim 16 in which the network component change comprises a traffic volume dependent component metric change and in which the post-change topology represents the topology with the changed component metric.

28. An apparatus for managing a network component change in a data communications network having as components nodes and links defining a pre-change topology, comprising:

means for forwarding all data assigned to the pre-change topology via the pre-change topology;

means for defining a post-change topology;

means for transitioning from the pre-change to the post-change topology;

means for assigning all data assigned to the pre-change topology to the post-change topology; and

means for forwarding the data assigned to the post-change topology via the post-change topology;

means for assigning the pre-change topology to a first topology space and the post-change topology to a second topology space;

means, after transition to the post-change topology, for rendering the first topology space congruent with the second topology space; and

means for transitioning from the post-change topology in the second topology space to the first topology space.

29. An apparatus as claimed in claim 28 in which the network component change comprises at least one of a single or multiple component failure, additional or planned removal of a component, or variation of a component metric.

30. An apparatus as claimed in claim 28 in which the means for defining a post-change topology comprises the means for converging on a post-change topology.

31. An apparatus as claimed in claim 28 further comprising means for ceasing marking when all transitioning nodes have implemented the marking step and subsequently forwarding data via the post-change topology.

32. An apparatus as claimed in claim 28 in which a data packet to be forwarded carries a marking representing a pre-change topology or a post-change topology.

33. An apparatus as claimed in claim 28 in which the means for transitioning is synchronized to an epoch.

34. An apparatus as claimed in claim 33 further comprising:

means for receiving a synchronization signal from a master node; and

means for commencing a transition epoch on receipt of the synchronization signal.

35. An apparatus as claimed in claim 33 further comprising means for detecting a network clock signal and commencing a transition epoch upon said detection.

36. An apparatus as claimed in claim 33 further comprising:

means for commencing a transition epoch;

means, during a hold-down period, for receiving all notifications concerning network changes during the epoch;

means for terminating the hold-down period;

means, during a processing period, for defining a post-change topology representing all network changes during the epoch;

means for terminating the processing period; and

means for transitioning to the post-change topology.

37. An apparatus as claimed in claim 36 in which the transitioning means commences the transition epoch upon receipt of a notification of a network change in that epoch.

38. An apparatus as claimed in claim 36 in which the transitioning means terminates the hold-down stage upon receipt of notification of a network change in a later epoch.

39. An apparatus as claimed in claim 28 in which the network component change comprises a traffic volume dependent component metric change and in which the post-change topology represents the topology with the changed component metric.

40. An apparatus as claimed in claim 28 in which the means for transitioning step comprises:

means for defining a transition topology;

means for marking data to be transitioned as assigned to the transition topology; and

means for forwarding marked data via the transition topology.

44. The apparatus as recited in claim 34 in which the network component change comprises at least one of a single or multiple component failure, additional or planned removal of a component, or variation of a component metric.

41. An apparatus of managing a network haying traffic dependent metrics in a data communications network having as components nodes and links defining a first traffic dependent topology comprising:

means for forwarding data via the first traffic dependent topology;

means for defining a second traffic dependent topology representing a traffic dependent network component change;

means for transitioning from the first to the second traffic dependent topology; and

means for forwarding data via the second traffic dependent topology;

means for assigning the first traffic dependent topology to a first topology space and the second traffic dependent topology to a second topology space;

means, after transition to the second traffic dependent topology, for rendering the first topology space congruent with the second topology space; and

means for transitioning from the post-change topology in the second topology space to the first topology space.

42. An apparatus as claimed in claim 41 in which the transitioning means comprises:

means for defining a transition topology;

means for means for marking data to be transitioned as assigned to the transition topology; and

means for forwarding marked data via the transition topology.

43. An apparatus for managing a network component change in a data communications network, the apparatus comprising:

one or more processors; and

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

a computer readable medium comprising one or more sequences of instructions for managing a network component change in a data communications network which, when executed by one or more processors, cause the one or more processors to perform;

forwarding all data assigned to the pre-change topology via the pre-change topology;

defining a post-change topology;

assigning all data assigned to the pre-change topology to the post-change topology;

transitioning from the pre-change to the post-change topology;

forwarding the data assigned to the post-change topology via the post-change topology;

assigning the pre-change topology to a first topology space and the post-change topology to a second topology space;

after transition to the post-change topology. rendering the first-topology space congruent with the second topology space; and

transitioning from the post-change topology in the second topology space to the first-topology space.

45. The apparatus as recited in claim 43 in which defining a post-change topology comprises converging a post-change topology.

46. The apparatus as recited in claim 43, further comprising:

ceasing marking when all transitioning nodes have implemented the marking step and subsequently forwarding data via the post-change topology.

47. The apparatus as recited in claim 43 in which a data packet to be forwarded carries a marking representing a pre-change topology or a post-change topology.

48. The apparatus as recited in claim 43 in which the transitioning step is synchronized to an epoch.

49. The apparatus as recited in claim 48, further comprising:

receiving a synchronization signal from a master node; and

commencing a transition epoch on receipt of the synchronization signal.

50. The apparatus as recited in claim 48, further comprising:

detecting a network clock signal and commencing a transition epoch upon said detection.

51. The apparatus as recited in claim 48, further comprising:

commencing a transition epoch;

during a hold-down period receiving all notifications concerning network changes during the epoch;

terminating the hold-down period;

during a processing period, defining a post-change topology representing all network changes during the epoch;

terminating the processing period; and

transitioning to the post-change topology.

52. The apparatus as recited in claim 51 in which the transition epoch is commenced upon receipt of a notification of a network change in that epoch.

53. The apparatus as recited in claim 51 in which the hold-down stage is terminated upon receipt of notification of a network change in a later epoch.

54. The apparatus as recited in claim 43 in which the network component change comprises a traffic volume dependent component metric change and in which the post-change topology represents the topology with the changed component metric.