Selectively sending link state messages in a network link state protocol based on interest of network nodes

• US 20060133298A1
• Filed: 12/22/2004
• Published: 06/22/2006
• Est. Priority Date: 12/22/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Nalawade, Gargi, Ng, Sandy, Luong, Steven V.
• Granted Patent: US 7,742,431 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols

Abstract

In a link state protocol such as an interior gateway protocol (IGP), link state advertisements or link state packets (LSA/LSPs) are sent only to network nodes that have expressed interest in them, rather than always flooding them.

Claims

1. In a link state protocol that conventionally floods link state advertisements or link state packets (“

LSA/LSPs”

) to all of a plurality of nodes in a network, a method of selectively sending the LSA/LSP, comprising;

receiving interest information for a first node in the network;

determining that a second node needs to send a LSA/LSP; and

generating and sending a LSA/LSP from the second node to the first node only if the interest information indicates that the first node is interested in the LSA/LSP.

2. The method of claim 1, wherein interest information is in any one of a router capabilities message type of the link state protocol, a router capabilities link state advertisement of the link state protocol, or a router capabilities link state packet of the link state protocol.

3. The method of claim 1, wherein generating and sending the LSA/LSP comprises determining, based on the interest information, whether the first node is capable of interpreting a message of the same type as the LSA/LSP.

4. The method of claim 3, wherein the determining step further comprises determining, based on the interest information, whether the second node is configured to receive messages conforming to the link state protocol used for the LSA/LSP.

5. A method as recited in claim 1, wherein the link state protocol is an interior gateway protocol comprising Open Shortest Path First protocol or Intermediate System-to-Intermediate System protocol.

6. The method of claim 1, wherein generating and sending the LSA/LSP comprises determining, based on the interest information, whether the first node has expressed an interest in a particular type of link state information carried in the LSA/LSP.

7. The method of claim 6, wherein the particular type of link state information comprises a change in router capabilities for routers in a particular network tunnel.

8. The method of claim 1, wherein generating and sending the LSA/LSP comprises determining, based on the first set of interest information, whether the first node is in a particular group of routers.

9. The method of claim 8, wherein generating and sending the LSA/LSP comprises determining whether the first node is part of a network tunnel.

10. The method of claim 1, wherein generating and sending the LSA/LSP to the second node comprises determining, based on the first set of interest information, whether the first node is on a path to a certain router in a particular group of routers.

11. The method of claim 10, wherein the particular group of routers comprises two or more nodes in a network tunnel.

12. The method of claim 1, wherein the LSA/LSP corresponds to any one of a change in state for the first node, a change in router capability for the first node, a change in configuration for the first node, a change in tunnel configuration for the first node, or a change in ability to receive a particular type of message.

13. The method of claim 1, further comprising altering the interest information based on the LSA/LSP.

14-24. -24. (canceled)

25. A machine-readable medium carrying one or more sequences of instructions for controlling link state message flow for a first node in a network of nodes, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:

receiving a first set of interest information corresponding to a second node in the network of nodes;

determining that the first node needs to send a link state message;

determining whether the link-state message corresponds to a limited-interest link state message type, wherein the limited-interest link state message type corresponds to one or more message which a subset of nodes in the network of nodes are interested in receiving;

if the link-state message corresponds to the limited-interest link state message type, then determining, based on the first set of interest information and the link state message, whether to send the link state message to the second node;

if the link state message should be sent to the second node, then generating a particular link state message based on the link state message;

sending the particular link state message to the second node; and

if the link-state message does not correspond to the limited-interest link state message type,then

generating and flooding a second particular link state message to all nodes in the network of nodes.

26. The machine-readable medium of claim 25, wherein the limited-interest link state message type corresponds to a router capabilities message type.

27. The machine-readable medium of claim 25, wherein the link-state message corresponds to a change in link state for the first node.

28. An apparatus for controlling link state message flow for a first node in a network of nodes, comprising:

a network interface that is coupled to a data network for receiving one or more packet flows therefrom;

a processor;

one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of;

receiving a first set of interest information corresponding to a second node in the network of nodes;

determining that the first node needs to send a link state message;

determining whether the link-state message corresponds to a limited-interest link state message type, wherein the limited-interest link state message type corresponds to one or more message which a subset of nodes in the network of nodes are interested in receiving;

if the link-state message corresponds to the limited-interest link state message type, then determining, based on the first set of interest information and the link state message, whether to send the link state message to the second node;

if the link state message should be sent to the second node, then

generating a particular link state message based on the link state message;

sending the particular link state message to the second node; and

if the link-state message does not correspond to the limited-interest link state message type, then

generating and flooding a second particular link state message to all nodes in the network of nodes.

29. The apparatus of claim 28, wherein the limited-interest link state message type corresponds to a router capabilities message type.

30. The apparatus of claim 28, wherein the link-state message corresponds to a change in link state for the first node.

31. An apparatus for controlling link state message flow for a first node in a network of nodes, comprising:

means for receiving a first set of interest information corresponding to a second node in the network of nodes;

means for determining that the first node needs to send a link state message;

means for determining whether the link-state message corresponds to a limited-interest link state message type, wherein the limited-interest link state message type corresponds to one or more message which a subset of nodes in the network of nodes are interested in receiving;

means for, if the link-state message corresponds to the limited-interest link state message type, then

determining, based on the first set of interest information and the link state message, whether to send the link state message to the second node;

if the link state message should be sent to the second node, then

generating a particular link state message based on the link state message;

sending the particular link state message to the second node; and

means for, if the link-state message does not correspond to the limited-interest link state message type, then

generating and flooding a second particular link state message to all nodes in the network of nodes.

32. The apparatus of claim 31, wherein the limited-interest link state message type corresponds to a router capabilities message type.

33. The apparatus of claim 31, wherein the link-state message corresponds to a change in link state for the first node.

34. (canceled)