Reducing and load balancing link-state requests in OSPF

• US 7,957,377 B1
• Filed: 07/30/2004
• Issued: 06/07/2011
• Est. Priority Date: 07/30/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Roy, Abhay
• Primary Examiner(s): Kumar; Pankaj
• Assistant Examiner(s): SWEET, LONNIE V
• Application Number:
  US10/903,742
• Time in Patent Office: 2,503 Days
• Field of Search: 709/224, 370/248, 370/254, 370/351
• US Class Current: 370/392
• 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 47/125 by balancing the load, e.g. traffic engineering

Abstract

A method of administering a plurality of routers in a computer network, comprising initializing a router in the plurality; receiving initial database description packets from at least first and second neighboring routers; processing the data description packet received from the first neighboring router; generating a request for link state advertisements from the first neighboring router; processing the database description packet received from the second neighboring router; if requesting link state advertisements from the second neighboring router that were not requested from the first neighboring router.

Claims

1. In a computer network having a plurality of routers that communicate link state information to each other, a method of reducing link state request traffic across the network, the method comprising:

receiving at a router a first database description packet from a first neighboring router communicating with the router, the first database description packet describing link state advertisements available from the first neighboring router;

examining the packet to determine what, if any, link state advertisements to request from the first neighboring router;

requesting link state advertisements from the first neighboring router;

receiving at the router a second database description packet from a second neighboring router communicating with the router, the second database description packet describing link state advertisements available from the second neighboring router; and

determining if the second neighboring router has additional link state advertisements available that are not available from the first neighboring router and, if the second is neighboring router does have additional link state advertisements available that are not available from the first neighboring router, then requesting by the router only the additional link state advertisements from the second neighboring router, and suppressing generating requests at the router for link state advertisements from the second neighboring router that have already been requested by the router from the first neighboring router but that have not yet been received from the first neighboring router.

2. The method of claim 1, further comprising placing a request for the link state advertisements that have already been requested but that have not yet been received on a retransmit list, and, if an update containing the requested link state advertisements is not received within a period of time, then requesting the requested link state advertisements from a plurality of routers.

3. The method of claim 2, wherein the requesting from a plurality routers is repeated if an update containing the requested link state advertisements is not received within a period of time.

4. The method of claim 2, wherein the requesting the requested link state advertisements from the plurality of routers is performed serially, in a round robin fashion, until the requested link state advertisements are received by the router.

13. The method of claim 1, wherein requesting link state advertisements from the first neighboring router comprises sending a first link state request (LSREQ) packet, and requesting only the additional link state advertisements from the second neighboring router comprises sending a second LSREQ packet.

14. The method of claim 13, further comprising receiving one or more link state update (LSUPD) packets.

15. The method of claim 1, further comprising determining if the sec- and neighboring router does not have any additional link state advertisements available that are not available from the first neighboring router, and, if so, not requesting any link state advertisements from the second neighboring router.

16. The method of claim 15, further comprising placing a request for link state advertisements from the second neighboring router on a retransmit list even if the router did not already request link state advertisements from the second neighboring router.

17. The method of claim 1, further comprising placing a request on a retransmit list, and, if an update containing the link state advertisements that have already been requested from the first neighboring router is not received from the first neighboring router within a period of time, then requesting from the second neighboring router the requested link state advertisements.

5. A non-transitory computer-readable medium containing instructions which, when executed by a router, reduce link state request traffic across a computer network having a plurality of routers that communicate link state information to each other, by:

receiving at the router a first database description packet from a first neighboring router communicating with the router, the first database description packet describing link state advertisements available from the first neighboring router;

examining the packet to determine what, if any, link state advertisements to request from the first neighboring router;

requesting link state advertisements from the first neighboring router;

receiving at the router a second database description packet from a second neighboring router communicating with the router, the second database description packet describing link state advertisements available from the second neighboring router; and

is determining if the second neighboring router has additional link state advertisements available that are not available from the first neighboring router and, if the second neighboring router does have additional link state advertisements available that are not available from the first neighboring router, then requesting by the router only the additional link state advertisements from the second neighboring router, and suppressing generating requests at the router for link state advertisements from the second neighboring router that have already been requested by the router from the first neighboring router but that have not yet been received from the first neighboring router.

6. The non-transitory computer-readable medium of claim 5, further comprising instructions for placing a request for the link state advertisements that have already been requested but that have not yet been received on a retransmit list, and, if an update containing the requested link state advertisements is not received within a period of time, then requesting the requested link state advertisements from a plurality of routers.

7. The non-transitory computer-readable medium of claim 6, wherein the requesting from a plurality of routers is repeated if an update containing the requested link state advertisements is not received within a period of time.

8. The non-transitory computer-readable medium of claim 6, wherein requesting the requested link state advertisements from the plurality of routers is performed serially, in a round robin fashion, until the requested link state advertisements are received by the router.

18. The non-transitory computer-readable medium of claim 5, further comprising instructions for determining if the second neighboring router does not have any additional link state advertisements available that are not available from the first neighboring router, and, if so, not requesting any link state advertisements from the second neighboring router.

19. The non-transitory computer-readable medium of claim 5, further comprising instructions for placing a request for link state advertisements from the second neighboring router on a retransmit list even if the router did not already request link state advertisements from the second neighboring router.

20. The non-transitory computer-readable medium of claim 5, further comprising instructions for placing a request on a retransmit list, and, if an update containing the link state advertisements that have already been requested from the first neighboring router is not received from the first neighboring router within a period of time, then requesting from the second neighboring router the requested link state advertisements.

9. A router for use in a computer network having a plurality of routers that communicate link state information to each other, the router comprising:

means for receiving a first database description packet from a first neighboring router, the first database description packet describing link state advertisements available from the first neighboring router;

means for examining the packet to determine what, if any, link state advertisements to request from the first neighboring router;

means for requesting link state advertisements from the first neighboring router;

means for receiving a second database description packet from a second neighboring router, the second database description packet describing link state advertisements available from the second neighboring router; and

means for determining if the second neighboring router has additional link state advertisements available that are not available from the first neighboring router and, if the second neighboring router does have additional link state advertisements available that are not available from the first neighboring router, then requesting by means at the router only the additional link state advertisements from the second neighboring router, and suppressing generating requests for link state advertisements from the second neighboring router that have already been requested from the first neighboring router but that have not yet been received from the first neighboring router.

10. The router of claim 9, further comprising means for placing a request for the link state advertisements that have already been requested but that have not yet been received on a retransmit list, and, if an update containing the requested link state advertisements is not received within a period of time, then requesting the requested link state advertisements from a plurality of routers.

11. The router of claim 10, further comprising means for repeating the requesting from a plurality of routers if an update containing the requested link state advertisements is not received within a period of time.

12. The router of claim 10, further comprising means for requesting the requested link state advertisements from the plurality of routers serially, in a round robin fashion, until the requested link state advertisements are received by the router.

21. A method comprising:

receiving at a router a first database description packet from a first neighboring router, the first database description packet describing link state advertisements available from the first neighboring router;

examining the first database description packet to determine one or more link state advertisements to request from the first neighboring router;

requesting the one or more link state advertisements from the first neighboring router;

receiving at the router a second database description packet from a second neighboring router, the second database description packet describing link state advertisements available from the second neighboring router; and

in response to receiving the second database description packet from the second neighboring router, requesting, by the router, any link state advertisements from the second neighboring router that have not been requested from the first neighboring router, and not requesting link state advertisements from the second neighboring router that have already been requested from the first neighboring router but that have not yet been received from the first neighboring router.

22. The method of claim 21, further comprising determining if the second neighboring router does not have any link state advertisements available that are not available from the first neighboring router, and, if so, not requesting any link state advertisements from the second neighboring router.

23. The method of claim 22, further comprising placing a request for link state advertisements from the second neighboring router on a retransmit list even if the router did not request link state advertisements from the second neighboring router.

24. The method of claim 22, further comprising placing a request on a retransmit list, and, if an update containing the link state advertisements that have already been requested from the first neighboring router is not received from the first neighboring router within a period of time, then requesting from the second neighboring router the requested link state advertisements.