Protocol for the determination of network topology

• US 7,729,337 B2
• Filed: 12/29/2000
• Issued: 06/01/2010
• Est. Priority Date: 01/15/1999
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Parsi, Vahid, Baghdasarian, Zareh, Zadikian, Haig Michael, Saleh, Ali Najib
• Primary Examiner(s): NGUYEN, HANH N
• Application Number:
  US09/751,999
• Publication Number:
  US 20010033548A1
• Time in Patent Office: 3,441 Days
• Field of Search: 370/389, 370/390, 370/392, 370/229, 370/216, 370/396, 370/400, 370/395.2, 370/220, 370/351, 370/218, 370/219, 370/255, 370/254, 370/252, 370/410, 370/397, 370/395.1, 709/218, 709/224, 709/231, 709/238, 709/227, 709/228, 709/229
• US Class Current: 370/351
• CPC Class Codes: H04J 14/0284 WDM mesh architectures
• CPC Class Codes: H04J 14/0295 Shared protection at the optical channel (1:1, n:m)
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/62 Wavelength based optical switching H04Q11/0062
• CPC Class Codes: H04Q 11/0062 Network aspects
• CPC Class Codes: H04Q 2011/0081 Fault tolerance; Redundancy; Recovery; Reconfigurability
• CPC Class Codes: H04Q 2011/0098 Mesh

Abstract

A method of operating a network is described. The network includes a number of nodes connected by a number of links. A method according to the present invention provisions a virtual path between a first and a second one of the plurality of nodes by: identifying the first and the second nodes, discovering a physical path from the first node to the second node, and establishing the virtual path. The method discovers a physical path from the first node to the second node by automatically identifying nodes forming the physical path. The method establishes the virtual path by configuring a set of connections between the nodes forming the physical path.

Claims

1. A method comprising:

receiving a protocol packet, wherein

said protocol packet is transmitted from an origin node,

said protocol packet is broadcast to a plurality of neighbors of said origin node to find a target node of said protocol packet,

said protocol packet comprises command-specific data,

said command-specific data comprises a link state advertisement count field,

said protocol packet is configured to record a protocol packet path history from said origin node to said target node, and

said protocol packet path history comprises information regarding a topology of at least a portion of said network; and

storing, in a memory, information regarding said protocol packet.

2. The method of claim 1, wherein said protocol packet comprises:

header data.

3. The method of claim 2, wherein said header data comprises:

a flush indicator field.

4. The method of claim 2, wherein said header data further comprises:

a terminate path indicator field.

5. The method of claim 2, wherein said header data further comprises:

a commit path indicator field.

6. The method of claim 2, wherein said header data comprises:

a request/response indicator field.

7. The method of claim 6, wherein said header data further comprises:

a negative response indicator field.

8. The method of claim 7, wherein said header data further comprises:

a terminate path indicator field.

9. The method of claim 7, wherein said header data further comprises:

a commit path indicator field.

10. The method of claim 7, wherein said header data comprises:

a flush indicator field.

11. The method of claim 1, wherein said protocol packet is an initialization packet.

12. The method of claim 11, wherein said command-specific data comprises:

information regarding a link between said node and a neighbor node.

13. The method of claim 11, wherein said command-specific data comprises:

a link cost field.

14. The method of claim 13, wherein said command-specific data further comprises:

at least a quality of service 3 capacity field.

15. The method of claim 13, wherein said command-specific data further comprises:

a hello interval field; and

a hello dead interval field.

16. The method of claim 1, wherein said protocol packet is a hello packet.

17. The method of claim 16, wherein said command-specific data further comprises:

an advertising node field;

an instance identifier field;

a hop count field; and

a neighbor count field.

18. The method of claim 16, wherein said command-specific data further comprises:

a neighbor field; and

a link cost field.

19. The method of claim 16, wherein said command-specific data further comprises:

at least a quality of service 3 capacity field.

20. The method of claim 1, wherein said protocol packet is a restore path packet.

21. The method of claim 20, wherein said command-specific data comprises:

a virtual path identifier field.

22. The method of claim 21, wherein said command-specific data comprises:

a path length field.

23. The method of claim 21, wherein said command-specific data comprises:

a path index field; and

a path array.

24. The method of claim 1, wherein said protocol packet is a create path packet.

25. The method of claim 24, wherein said command-specific data comprises:

a virtual path identifier field;

a path length field;

a path index field; and

a path array.

26. The method of claim 1, wherein said protocol packet is a delete path packet.

27. The method of claim 26, wherein said command-specific data comprises:

a virtual path identifier field;

a path length field;

a path index field; and

a path array.

28. The method of claim 1, wherein said protocol packet is a test path packet.

29. The method of claim 1, further comprising:

identifying a plurality of eligible neighbor nodes of said origin node, wherein said eligible neighbor nodes are nodes that are suitable for a virtual path between said origin node and said target node, and said protocol packet is broadcast to each of said plurality of eligible neighbor nodes.

30. The method of claim 1, wherein said protocol packet is a get link state advertisement packet.

31. The method of claim 1, wherein said protocol packet is a link down packet.

32. The method of claim 1, wherein said protocol packet is a configure packet.

33. The method of claim 1, further comprising:

receiving a subsequent protocol packet;

determining that said subsequent protocol packet has a common protocol packet path history as said protocol packet, wherein

said determining is based at least in part on said stored information regarding said protocol packet; and

rejecting said subsequent protocol packet in response to said determining.

34. The method of claim 33, wherein said determining comprises ascertaining that:

said subsequent protocol packet identifies a first virtual path,

said subsequent protocol packet was received from a first tandem node,

said protocol packet identified said first virtual path, and

said protocol packet was received from said first tandem node.

35. The method of claim 33, wherein said determining comprises ascertaining that:

said subsequent protocol packet was received over a first link,

said subsequent protocol packet was sent from a first origin node,

said protocol packet was received over said first link, and

said protocol packet was sent from said first origin node.

36. A method of processing a get link state advertisement packet comprising:

receiving said get link state advertisement packet at a downstream node, wherein

said get link state advertisement packet is sent by a sending node,

said get link state advertisement packet comprises at least one node identifier,

said at least one node identifier identifies a node in a network for which said sending node seeks a link state advertisement, and

said downstream node and said sending node are nodes in said network;

receiving at least one link state advertisement from a node other than said sending node;

sending said at least one link state advertisement from said downstream node to said sending node; and

receiving an acknowledgement of said at least one link state advertisement at said downstream node.

37. The method of claim 36, further comprising:

building a first list from a link state database maintained at said downstream node, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

38. The method of claim 37, further comprising:

building a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

39. The method of claim 38, further comprising:

sending a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

40. The method of claim 38, further comprising:

indicating link state advertisements in said second list are to be deleted.

41. The method of claim 40, further comprising:

deleting each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

42. The method of claim 36, further comprising:

identifying said at least one link state advertisement in a link state database maintained at said downstream node, wherein said identifying is based at least in part on said at least one node identifier.

43. The method of claim 42, further comprising:

building a first list from said link state database, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

44. The method of claim 43, further comprising:

building a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

45. The method of claim 44, further comprising:

sending a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

46. The method of claim 44, further comprising:

indicating link state advertisements in said second list are to be deleted.

47. The method of claim 46, further comprising:

deleting each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

48. The method of claim 36, further comprising:

building a first list from a link state database maintained at said downstream node.

49. The method of claim 36, wherein:

said at least one link state advertisement is a link state advertisement for a node other than said downstream node; and

said node other than said downstream node is said node for which said sending node seeks said link state advertisement.

50. The method of claim 36, wherein said node for which said sending node seeks said link state advertisement is a failed node.

51. A computer system comprising:

a processor;

computer readable medium coupled to said processor; and

computer code, encoded in said computer readable medium, configured to cause said processor to;

receive a get link state advertisement packet at a downstream node, wherein

said get link state advertisement packet is sent by a sending node,

said get link state advertisement packet comprises at least one node identifier,

said at least one node identifier identifies a node in a network for which said sending node seeks a link state advertisement, and

said downstream node and said sending node are nodes in said network;

receive at least one link state advertisement from a node other than said sending node;

send said at least one link state advertisement from said downstream node to said sending node; and

receive an acknowledgement of said at least one link state advertisement at said downstream node.

52. The computer system of claim 51, wherein said computer code is further configured to cause said processor to:

build a first list from a link state database maintained at said downstream node, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

53. The computer system of claim 52, wherein said computer code is further configured to cause said processor to:

build a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

54. The computer system of claim 53, wherein said computer code is further configured to cause said processor to:

send a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

55. The computer system of claim 53, wherein said computer code is further configured to cause said processor to:

indicate link state advertisements in said second list are to be deleted.

56. The computer system of claim 55, wherein said computer code is further configured to cause said processor to:

delete each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

57. The computer system of claim 51, wherein said computer code is further configured to cause said processor to:

identify, based at least in part on said at least one node identifier, said at least one link state advertisement in a link state database maintained at said downstream node.

58. The computer system of claim 57, wherein said computer code is further configured to cause said processor to:

build a first list from said link state database, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

59. The computer system of claim 58, wherein said computer code is further configured to cause said processor to:

build a second list from said link state database, wherein said second list comprises any link state advertisements received from said sending node.

60. The computer system of claim 59, wherein said computer code is further configured to cause said processor to:

send a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

61. The computer system of claim 59, wherein said computer code is further configured to cause said processor to:

indicate link state advertisements in said second list are to be deleted.

62. The computer system of claim 61, wherein said computer code is further configured to cause said processor to:

deleting each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

63. A computer program product encoded in computer readable media, said computer program product comprising:

a first set of instructions, executable on a computer system to receive a get link state advertisement packet at a downstream node, wherein

said get link state advertisement packet is sent by a sending node,

said get link state advertisement packet comprises at least one node identifier,

said at least one node identifier identifies a node in a network for which said sending node seeks a link state advertisement, and

said downstream node and said sending node are nodes in said network;

a second set of instructions, executable on said computer system to receive at least one link state advertisement from a node other than said sending node;

a third set of instructions, executable on said computer system to send said at least one link state advertisement from said downstream node to said sending node; and

a fourth set of instructions, executable on said computer system to receive an acknowledgement of said at least one link state advertisement at said downstream node.

64. The computer program product of claim 63, further comprising:

a fifth set of instructions, executable on said computer system to build a first list from a link state database maintained at said downstream node, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

65. The computer program product of claim 64, further comprising:

a sixth set of instructions, executable on said computer system to build a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

66. The computer program product of claim 65, further comprising:

a seventh set of instructions, executable on said computer system to send a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

67. The computer program product of claim 65, further comprising:

a seventh set of instructions, executable on said computer system to indicate link state advertisements in said second list are to be deleted.

68. The computer program product of claim 67, further comprising:

an eighth set of instructions, executable on said computer system to delete each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

69. The computer program product of claim 63, further comprising:

a fifth set of instructions, executable on said computer system to identify said at least one link state advertisement in a link state database maintained at said downstream node, wherein said identifying is based at least in part on said at least one node identifier.

70. The computer program product of claim 69, further comprising:

a sixth set of instructions, executable on said computer system to build a first list from said link state database, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

71. The computer program product of claim 70, further comprising:

a seventh set of instructions, executable on said computer system to build a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

72. The computer program product of claim 71, further comprising:

an eighth set of instructions, executable on said computer system to send a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

73. The computer program product of claim 71, further comprising:

an eighth set of instructions, executable on said computer system to indicate link state advertisements in said second list are to be deleted.

74. The computer program product of claim 73, further comprising:

a ninth set of instructions, executable on said computer system to deleting each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

75. An apparatus comprising:

means for receiving a get link state advertisement packet at a downstream node, wherein

said get link state advertisement packet is sent by a sending node,

said get link state advertisement packet comprises at least one node identifier,

said at least one node identifier identifies a node in a network for which said sending node seeks a link state advertisement, and

said downstream node and said sending node are nodes in said network;

means for receiving at least one link state advertisement from a node other than said sending node;

means for sending at least one link state advertisement from said downstream node to said sending node; and

means for receiving an acknowledgement of said at least one link state advertisement at said downstream node.

76. The apparatus of claim 75, further comprising:

means for building a first list from a link state database maintained at said downstream node, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

77. The apparatus of claim 76, further comprising:

means for building a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

78. The apparatus of claim 77, further comprising:

means for sending a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

79. The apparatus of claim 77, further comprising:

means for indicating link state advertisements in said second list are to be deleted.

80. The apparatus of claim 79, further comprising:

means for deleting each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

81. The apparatus of claim 75, further comprising:

means for identifying said at least one link state advertisement in a link state database maintained at said downstream node, wherein said identifying is based at least in part on said at least one node identifier.

82. The apparatus of claim 81, further comprising:

means for building a first list from said link state database, wherein

said first list comprises any link state advertisements received from a node other than said sending node, and

said at least one link state advertisement is included in said first list.

83. The apparatus of claim 82, further comprising:

means for building a second list from said link state database, wherein

said second list comprises any link state advertisements received from said sending node.

84. The apparatus of claim 83, further comprising:

means for sending a get link state advertisement packet to each node corresponding to one of said link state advertisements in said second list.

85. The apparatus of claim 83, further comprising:

means for indicating link state advertisements in said second list are to be deleted.

86. The apparatus of claim 85, further comprising:

means for deleting each one of said link state advertisements in said second list, if an updated link state advertisement is not received within a period of time.

87. A method comprising:

receiving a hello packet at a downstream node, wherein said hello packet comprises a link state advertisement;

processing said link state advertisement, wherein processing said link state advertisement comprises

sending said link state advertisement from said downstream node;

adding said link state advertisement to a link state database maintained at said downstream node; and

sending an acknowledgement from said downstream node, wherein said acknowledgement acknowledges all link state advertisements in said hello packet.

88. The method of claim 87, wherein said processing comprises:

determining if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node.

89. The method of claim 88, wherein said processing further comprises:

if said link state advertisement does not correspond to an entry in a link state database maintained at said downstream node,

adding said link state advertisement to said link state database.

90. The method of claim 89, wherein said processing further comprises:

if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node,

determining if a node originating said link state advertisement is a node originating a link state advertisement corresponding to said entry in said link state database.

91. The method of claim 90, wherein said processing further comprises:

if said node originating said link state advertisement is not said node originating said link state advertisement corresponding to said entry in said link state database,

adding said link state advertisement to said link state database.

92. The method of claim 90, wherein said processing further comprises:

if said node originating said link state advertisement is said node originating said link state advertisement corresponding to said entry in said link state database,

determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database.

93. The method of claim 92, wherein said processing further comprises:

if said link state advertisement is not more recent than said link state advertisement corresponding to said entry in said link state database,

discarding said link state advertisement.

94. The method of claim 92, wherein said processing further comprises:

if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database, adding said link state advertisement to said link state database.

95. The method of claim 92, wherein said determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database comprises:

determining if a link state identifier of said link state advertisement is the same as a link state identifier of said link state advertisement corresponding to said entry in said link state database.

96. The method of claim 95, wherein said determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

if said link state identifier of said link state advertisement is not the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database,

indicating a one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a higher link state identifier is more recent.

97. The method of claim 95, wherein said determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

if said link state identifier of said link state advertisement is the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database,

determining if a hop count of said link state advertisement is the same as a hop count of said link state advertisement corresponding to said entry in said link state database.

98. The method of claim 97, wherein said determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

if said hop count of said link state advertisement is the same as said hop count of said link state advertisement corresponding to said entry in said link state database,

indicating that said link state advertisement and said link state advertisement corresponding to said entry in said link state database are the same.

99. The method of claim 97, wherein said determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

if said hop count of said link state advertisement is not the same as said hop count of said link state advertisement corresponding to said entry in said link state database,

indicating that said one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a lower hop count is more recent.

100. The method of claim 87, further comprising:

determining if said link state advertisement corresponds to an entry in said link state database; and

determining if said link state advertisement is more recent than a link state advertisement corresponding to said entry in said link state database, wherein

said adding said link state advertisement to said link state database is performed only if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database.

101. A computer system comprising:

a processor;

computer readable medium coupled to said processor; and

computer code, encoded in said computer readable medium, configured to cause said processor to;

receive a hello packet at a downstream node, wherein said hello packet comprises a link state advertisement;

process said link state advertisement;

send said link state advertisement from said downstream node;

add said link state advertisement to a link state database maintained at said downstream node; and

send an acknowledgement from said downstream node, wherein said acknowledgement acknowledges all link state advertisements in said hello packet.

102. The computer system of claim 101, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

determine if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node.

103. The computer system of claim 102, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

if said link state advertisement does not correspond to an entry in a link state database maintained at said downstream node,

add said link state advertisement to said link state database.

104. The computer system of claim 103, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node,

determine if a node originating said link state advertisement is a node originating a link state advertisement corresponding to said entry in said link state database.

105. The computer system of claim 104, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

if said node originating said link state advertisement is not said node originating said link state advertisement corresponding to said entry in said link state database,

add said link state advertisement to said link state database.

106. The computer system of claim 104, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

if said node originating said link state advertisement is said node originating said link state advertisement corresponding to said entry in said link state database,

determine if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database.

107. The computer system of claim 106, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

if said link state advertisement is not more recent than said link state advertisement corresponding to said entry in said link state database,

discard said link state advertisement.

108. The computer system of claim 106, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database,

add said link state advertisement to said link state database.

109. The computer system of claim 106, wherein said computer code configured to cause said processor to process said link state advertisement is further configured to cause said processor to:

determine if a link state identifier of said link state advertisement is the same as a link state identifier of said link state advertisement corresponding to said entry in said link state database.

110. The computer system of claim 109, wherein said computer code configured to cause said processor to determine if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database is further configured to cause said processor to:

if said link state identifier of said link state advertisement is not the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database,

indicate a one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a higher link state identifier is more recent.

111. The computer system of claim 109, wherein said computer code configured to cause said processor to determine if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database is further configured to cause said processor to:

if said link state identifier of said link state advertisement is the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database,

determine if a hop count of said link state advertisement is the same as a hop count of said link state advertisement corresponding to said entry in said link state database.

112. The computer system of claim 111, wherein said computer code configured to cause said processor to determine if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database is further configured to cause said processor to:

if said hop count of said link state advertisement is the same as said hop count of said link state advertisement corresponding to said entry in said link state database,

indicate that said link state advertisement and said link state advertisement corresponding to said entry in said link state database are the same.

113. The computer system of claim 111, wherein said computer code configured to cause said processor to determine if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database is further configured to cause said processor to:

if said hop count of said link state advertisement is not the same as said hop count of said link state advertisement corresponding to said entry in said link state database,

indicating that said one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a lower hop count is more recent.

114. A computer program product encoded in computer readable media, said computer program product comprising:

a first set of instructions, executable on a computer system to receive a hello packet at a downstream node, wherein said hello packet comprises a link state advertisement;

a second set of instructions, executable on said computer system to process said link state advertisement and comprising instructions for sending said link state advertisement from said downstream node;

a third set of instructions, executable on said computer system to add said link state advertisement to a link state database maintained at said downstream node; and

a fourth set of instructions, executable on said computer system to send an acknowledgement from said downstream node, wherein said acknowledgement acknowledges all link state advertisements in said hello packet.

115. The computer program product of claim 114, wherein said second set of instructions comprises:

a first sub-set of instructions, executable on said computer system to determine if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node.

116. The computer program product of claim 115, wherein said second set of instructions further comprises:

a second sub-set of instructions, executable on said computer system to, if said link state advertisement does not correspond to an entry in a link state database maintained at said downstream node,

add said link state advertisement to said link state database.

117. The computer program product of claim 116, wherein said second set of instructions further comprises:

a third sub-set of instructions, executable on said computer system to, if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node,

determine if a node originating said link state advertisement is a node originating a link state advertisement corresponding to said entry in said link state database.

118. The computer program product of claim 117, wherein said second set of instructions further comprises:

a fourth sub-set of instructions, executable on said computer system to, if said node originating said link state advertisement is not said node originating said link state advertisement corresponding to said entry in said link state database,

add said link state advertisement to said link state database.

119. The computer program product of claim 117, wherein said second set of instructions further comprises:

a fourth sub-set of instructions, executable on said computer system to, if said node originating said link state advertisement is said node originating said link state advertisement corresponding to said entry in said link state database,

determine if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database.

120. The computer program product of claim 119, wherein said second set of instructions further comprises:

a fifth sub-set of instructions, executable on said computer system to, if said link state advertisement is not more recent than said link state advertisement corresponding to said entry in said link state database,

discard said link state advertisement.

121. The computer program product of claim 119, wherein said second set of instructions further comprises:

a sixth sub-set of instructions, executable on said computer system to, if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database,

add said link state advertisement to said link state database.

122. The computer program product of claim 119, wherein said second set of instructions further comprises:

a sixth sub-set of instructions, executable on said computer system to determine if a link state identifier of said link state advertisement is the same as a link state identifier of said link state advertisement corresponding to said entry in said link state database.

123. The computer program product of claim 122, wherein said fourth sub-set of instructions further comprises:

a first sub-sub-set of instructions, executable on said computer system to, if said link state identifier of said link state advertisement is not the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database,

indicate a one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a higher link state identifier is more recent.

124. The computer program product of claim 122, wherein said fourth sub-set of instructions further comprises:

a first sub-sub-set of instructions, executable on said computer system to, if said link state identifier of said link state advertisement is the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database,

determine if a hop count of said link state advertisement is the same as a hop count of said link state advertisement corresponding to said entry in said link state database.

125. The computer program product of claim 124, wherein said fourth sub-set of instructions further comprises:

a second sub-sub-set of instructions, executable on said computer system to, if said hop count of said link state advertisement is the same as said hop count of said link state advertisement corresponding to said entry in said link state database,

indicate that said link state advertisement and said link state advertisement corresponding to said entry in said link state database are the same.

126. The computer program product of claim 124, wherein said fourth sub-set of instructions further comprises:

a second sub-sub-set of instructions, executable on said computer system to, if said hop count of said link state advertisement is not the same as said hop count of said link state advertisement corresponding to said entry in said link state database,

indicating that said one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a lower hop count is more recent.

127. An apparatus comprising:

means for receiving a hello packet at a downstream node, wherein said hello packet comprises a link state advertisement;

means for processing said link state advertisement, wherein said means for processing said link state advertisement comprises means for sending said link state advertisement from said downstream node;

means for adding said link state advertisement to a link state database maintained at said downstream node; and

means for sending an acknowledgement from said downstream node, wherein said acknowledgement acknowledges all link state advertisements in said hello packet.

128. The apparatus of claim 127, wherein said means for processing comprises:

means for determining if said link state advertisement corresponds to an entry in a link state database maintained at said downstream node.

129. The apparatus of claim 128, wherein said means for processing further comprises:

means for adding said link state advertisement to a link state database, if said link state advertisement does not correspond to an entry in a link state database maintained at said downstream node.

130. The apparatus of claim 129, wherein said means for processing further comprises:

means for determining if a node originating said link state advertisement is a node originating a link state advertisement corresponding to an entry in a link state database, if said link state advertisement corresponds to said entry in said link state database maintained at said downstream node.

131. The apparatus of claim 130, wherein said means for processing further comprises:

means for adding said link state advertisement to said link state database, if said node originating said link state advertisement is not said node originating said link state advertisement corresponding to said entry in said link state database.

132. The apparatus of claim 130, wherein said means for processing further comprises:

means for determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database, if said node originating said link state advertisement is said node originating said link state advertisement corresponding to said entry in said link state database.

133. The apparatus of claim 132, wherein said means for processing further comprises:

means for discarding said link state advertisement, if said link state advertisement is not more recent than said link state advertisement corresponding to said entry in said link state database.

134. The apparatus of claim 132, wherein said means for processing further comprises:

means for adding said link state advertisement to said link state database, if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database.

135. The apparatus of claim 132, wherein said means for determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database comprises:

means for determining if a link state identifier of said link state advertisement is the same as a link state identifier of said link state advertisement corresponding to said entry in said link state database.

136. The apparatus of claim 135, wherein said means for determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

means for indicating a one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a higher link state identifier is more recent, if said link state identifier of said link state advertisement is not the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database.

137. The apparatus of claim 135, wherein said means for determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

means for determining if a hop count of said link state advertisement is the same as a hop count of said link state advertisement corresponding to said entry in said link state database, if said link state identifier of said link state advertisement is the same as said link state identifier of said link state advertisement corresponding to said entry in said link state database.

138. The apparatus of claim 137, wherein said means for determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

means for indicating that said link state advertisement and said link state advertisement corresponding to said entry in said link state database are the same, if said hop count of said link state advertisement is the same as said hop count of said link state advertisement corresponding to said entry in said link state database.

139. The apparatus of claim 137, wherein said means for determining if said link state advertisement is more recent than said link state advertisement corresponding to said entry in said link state database further comprises:

means for indicating that said one of said link state advertisement and said link state advertisement corresponding to said entry in said link state database having a lower hop count is more recent, if said hop count of said link state advertisement is not the same as said hop count of said link state advertisement corresponding to said entry in said link state database.