Method and apparatus to minimize database exchange in OSPF by using a SHA-1 digest value

• US 7,664,789 B2
• Filed: 12/02/2005
• Issued: 02/16/2010
• Est. Priority Date: 12/02/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Roy, Abhay, Mirtorabi, Sina, Weis, Brian E., Fluhrer, Scott Roy
• Primary Examiner(s): Ton; Dang T
• Assistant Examiner(s): Kavleski; Ryan C
• Application Number:
  US11/292,534
• Publication Number:
  US 20070127457A1
• Time in Patent Office: 1,537 Days
• Field of Search: 709/223, 709/238, 709/242, 707/1, 707/201
• US Class Current: 707/610
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

The present invention provides a method of determining whether database located on a first router is synchronized with the database located on a second router by performing a hash function on the values contained in a link state database to derive a SHA-1 digest value. In an embodiment, the digest value is based on LSA type. The digest value is exchanged initially during a database description packet swap between the first router and second router. If the digest values are the same, the databases are already synchronized. The routers thus skip the database description packet exchange of LSAs in the database and go directly to FULL state, indicating full synchronization between databases on the first and second router and announcing adjacency to each other. If the digest differs, normal database description packet exchange is performed as specified in OSPF.

Claims

1. A method of synchronizing router databases in a network, the method comprising:

producing a first digest value incrementally from a first database that is local to a first router by conducting separate digest calculations on individual contents of the first database as additions and deletions are made to the first database and combining results of the separate digest calculations to form the first digest value;

sending the first digest value to a second router;

receiving a second digest value from the second router, the second digest value produced from a second database that is local to the second router;

performing at least a partial database-synchronizing packet exchange with the second router if the first digest value is not within a range of difference from the second digest value; and

transitioning the first router to a full state if the first digest value is within the range of difference from the second digest value.

2. The method of claim 1, wherein the first digest value is computed from link-state advertisements (LSAs) of a same type contained in entries of the first database.

3. The method of claim 1, wherein the first digest value is sent to the second router during a database description packet exchange between the first router and second router.

4. The method of claim 1, wherein the range of difference is zero.

5. The method of claim 1, wherein a difference between the first digest value and the second digest value indicates specific content in the first database to exchange with the second router.

6. The method of claim 5, wherein the specific content in the first database is exchanged with the second router during the at least partial database synchronizing packet exchange between the second router.

7. The method of claim 1, wherein the at least partial database synchronizing packet exchange comprises exchanging database description packets with the second router.

8. The method of claim 1 wherein at least some of the separate digest calculations use Secure Hash Algorithm-1 (SHA-1).

9. A first router, configured to synchronize a first database that is local to the first router to a second database located on a second router, comprising:

means for producing incrementally a first digest value from the first database that is local to the first router by conducting separate digest calculations on individual contents of the first database as additions and deletions are made to the first database and combining results of the separate digest calculations to form the first digest value;

means for sending the first digest value to the second router;

means for receiving a second digest value from the second router, the second digest value produced from the second database that is local to the second router;

means for performing at least a partial packet exchange with the second router if the first digest value is not within a range of difference from the second digest value; and

means for transitioning the first router to a full state if the first digest value is within the range of difference from the second digest value.

10. The router of claim 9, wherein the first digest value is computed from LSAs of a same type contained in entries of the first database.

11. The router of claim 9, wherein the first digest value is sent to the second router during a database description packet exchange between the first router and second router.

12. The router of claim 9, wherein the range of difference is zero.

13. The router of claim 9, wherein a difference between the first digest value and the second digest value indicates specific content in the first database to exchange with the second router.

14. The router of claim 13, wherein the specific packets are exchanged with the second router during the at least partial database-synchronizing packet exchange between the second router.

15. The router of claim 9, wherein the at least partial database synchronizing packet exchange comprises exchanging database description packets with the second router.

16. A computer-readable medium containing instructions, which, when executed by a computer, synchronizes a first database that is local to a first router with a second database that is local to a second router, by performing the acts of:

producing a first digest value incrementally from the first database that is local to the first router by conducting separate digest calculations on individual contents of the first database as additions and deletions are made to the first database and combining results of the separate digest calculations to form the first digest value;

sending the first digest value to the second router;

receiving a second digest value from the second router, the second digest value produced from the second database that is local to the second router;

performing at least a partial database-synchronizing packet exchange with the second router if the first digest value is not within a first range of difference; and

transitioning the first router to a full state if the first digest value is within a second range of difference from the second digest value.

17. An apparatus comprising:

a communication connection configured to enable communication with a second apparatus;

a first database configured to contain link state information; and

a processor configured to

incrementally calculate a first digest value by conducting separate digest calculations on individual contents of the first database as additions and deletions are made to the first database and combining results of the separate digest calculations to form the first digest value,

compare the first digest value with a second digest value received from the second apparatus, the second digest value descriptive of a second database that contains link state information at the second apparatus,

perform at least a partial database-synchronizing packet exchange with the second apparatus if the first digest value does not match the second digest value, and

transition the first router to a full state if the first digest value matches the second digest value.

18. The apparatus of claim 17 wherein the apparatus is a first router and the second apparatus is a second router and the at least partial database-synchronizing packet exchange includes a database description packet exchange between the first router and the second router.

19. The apparatus of claim 17, wherein a difference between the first digest value and the second digest value indicates specific content in the first database to exchange with the second apparatus.

20. The apparatus of claim 19, wherein the at least partial database-synchronizing packet exchange exchanges the specific content in the first database with the second apparatus.

21. The apparatus of claim 17 wherein at least some of the separate digest calculations use Secure Hash Algorithm-1 (SHA-1).