Optimizing flooding of information in link-state routing protocol

• US 6,820,134 B1
• Filed: 12/28/2000
• Issued: 11/16/2004
• Est. Priority Date: 12/28/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Zinin, Alexey Dimitrievich, Shand, Ian Michael Charles
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US09/749,858
• Time in Patent Office: 1,419 Days
• Field of Search: 709/238, 709/242
• US Class Current: 709/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458

Abstract

A technique modifies an asynchronous flooding algorithm associated with a link state routing protocol operating within an area of a computer network from a per-interface to a per-neighbor paradigm. A router executes the flooding algorithm to distribute its local state over its interfaces and throughout an area of the network to each neighboring router with whom it has an adjacency. The router maintains a list of neighbors within an area data structure. When a new neighbor (adjacency) arises on an interface belonging to the area, the router updates the neighbor data structure describing that adjacency by linking it to a corresponding entry in the list of neighbors. Utilizing information contained in the list of neighbors, as well as information describing the types of interfaces used by the neighbors in the list, the router marks each interface data structure within the area as either flooding-active or flooding-passive. Marking of the interface is performed in connection with an interface election process that selects a flooding-active interface on the basis of, e.g., interface cost, giving preference to faster interfaces. Thereafter, link state protocol data units (PDUs) are sent to the neighbors over those interfaces marked as flooding-active.

Claims

1. A method for modifying an asynchronous flooding algorithm executed by a router of a computer network and associated with a link state routing protocol operating within an area of the network, the flooding algorithm modified from a per-interface paradigm to a per-neighbor paradigm, the method comprising the steps of:

maintaining a list of neighbors within an area data structure of the router, the list of neighbors having a plurality of entries;

updating a neighbor data structure of the router when a neighbor appears on an interface of the router belonging to the area, the neighbor data structure describing an adjacency between the router and a neighboring router;

marking an interface data structure of the router as one of flooding-active and flooding-passive, the interface data structure provided for each interface having a router adjacency; and

sending link state protocol data units (PDUs) to the neighbor over the interface if the interface data structure is marked flooding-active.

2. The method of claim 1 wherein the step of sending comprises the step of obviating flooding of the PDUs back to the router via any interface.

3. The method of claim 1 wherein the step of sending comprises the step of retransmitting PDUs to the neighbor until a single acknowledgement is received over any interface.

4. The method of claim 1 wherein the step of updating comprises the step of linking the neighbor data structure to a corresponding entry in the list of neighbors.

5. The method of claim 4 wherein the step of marking comprises the step of selecting a flooding-active interface on the basis of interface cost, giving preference to faster interfaces.

6. The method of claim 5 wherein the step of selecting is performed in connection with an interface election process executed by the router.

7. The method of claim 6 further comprising the step of re-executing the interface election process when one of a number of entries in the list of neighbors changes and a state of the adjacency in the list changes.

8. The method of claim 1 further comprising the step of distributing a PDU loading process among multiple links between adjacent routers when more than one adjacency simultaneously arises between two routers.

9. Apparatus for modifying an asynchronous flooding algorithm executed by an intermediate device of a computer network and associated with a link state routing protocol operating within an area of the network, the flooding algorithm modified from a per-interface paradigm to a per-neighbor paradigm, the apparatus comprising:

means for maintaining a list of neighbors within an area data structure of the intermediate device, the list of neighbors having a plurality of entries;

means for updating a neighbor data structure of the intermediate device when a new neighbor appears on an interface of the device belonging to the area, the neighbor data structure describing an adjacency between the intermediate device and a neighboring intermediate device;

means for marking an interface data structure of the intermediate device as one of flooding-active and flooding-passive, the interface data structure provided for each interface having an intermediate device adjacency; and

means for sending link state protocol data units (PDUs) to the new neighbor over the interface if the interface data structure is marked flooding-active.

10. The apparatus of claim 9 wherein the updating means comprises means for linking the neighbor data structure to a corresponding entry in the list of neighbors.

11. The apparatus of claim 10 wherein the marking means comprises means for selecting a flooding-active interface on the basis of interface cost, giving preference to faster interfaces.

12. The apparatus of claim 11 further comprising means for executing an interface election process when one of a number of entries in the list of neighbors changes and a state of the adjacency in the list changes.

13. The apparatus of claim 9 wherein the intermediate device is a router.

14. A computer readable medium containing executable program instructions for modifying an asynchronous flooding algorithm executed by a router of a computer network and associated with a link state routing protocol operating within an area of the network, the flooding algorithm modified from a per-interface paradigm to a per-neighbor paradigm, the executable program instructions comprising program instructions for:

maintaining a list of neighbors within an area data structure of the router, the list of neighbors having a plurality of entries;

updating a neighbor data structure of the router when a new neighbor appears on an interface of the router belonging to the area, the neighbor data structure describing an adjacency between the router and a neighboring router;

marking an interface data structure of the router as one of flooding-active and flooding-passive, the interface data structure provided for each interface having a router adjacency; and

sending link state protocol data units (PDUs) to the new neighbor over the interface if the interface data structure is marked flooding-active.

15. The computer readable medium of claim 14 wherein the program instruction for updating comprises the program instruction for linking the neighbor data structure to a corresponding entry in the list of neighbors.

16. The computer readable medium of claim 15 wherein the program instruction for marking comprises the program instruction for selecting a flooding-active interface on the basis of interface cost, giving preference to faster interfaces.

17. The computer readable medium of claim 16 wherein the program instruction for selecting is performed in connection with an interface election process executed by the router.

18. The computer readable medium of claim 17 further comprising a program instruction for re-executing the interface election process when one of a number of entries in the list of neighbors changes and a state of the adjacency in the list changes.

19. A memory for storing software programs and data structures associated with an asynchronous flooding algorithm of a link state routing protocol executed by a router within an area of a computer network, the flooding algorithm defined by operation on the data structures comprising:

an area data structure containing a list of neighbors, the list of neighbors having a plurality of entries;

a neighbor data structure describing an adjacency between the router and a neighboring router, the neighbor data structure updated by the router when a new neighbor appears on an interface of the router belonging to the area;

an interface data structure provided for each interface having a router adjacency, the interface data structure marked by the router as one of flooding-active and flooding-passive; and

link state protocol data units (PDUs) transmitted by the router to the new neighbor over the interface if the interface data structure is marked flooding-active.

20. The memory of claim 19 wherein the list of neighbors comprises a NeighborList field having a list of entries, each entry created when a first neighbor data structure for the new neighbor is created within the area.

21. The memory of claim 20 wherein the neighbor data structure comprises a NeighborEntry field having a content set to reference a corresponding entry in the NeighborList when an instance of the neighbor data structure is created.

22. The memory of claim 21 wherein the interface data structure comprises a FloodingActive field and wherein the interface corresponding to the interface data structure is used for flooding if a value of the FloodingActive field is true.

23. The memory of claim 19 wherein the PDUs are one of link state advertisements (LSAs) and link state packets (LSP).

24. Apparatus for modifying an asynchronous flooding algorithm executed by an intermediate device of a computer network and associated with a link state routing protocol operating within an area of the network, the flooding algorithm modified from a per-interface paradigm to a per-neighbor paradigm, the apparatus comprising:

a memory configured to store a link state database describing a local state of the intermediate device; and

a processor coupled to the memory, the processor adapted to execute the modified flooding algorithm to distribute the local state to all adjacent intermediate devices within the area of the network rather than distributing the local state over all interfaces of the intermediate device.

25. The apparatus of claim 24 wherein the intermediate device is a router.