Method and apparatus for exchange of routing database information

• US 6,557,044 B1
• Filed: 06/01/1999
• Issued: 04/29/2003
• Est. Priority Date: 06/01/1999
• Status: Expired due to Term

• Current Assignee: Avaya Management L.P. (Avaya Incorporated)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Cain, Brad, Hardjono, Thomas
• Primary Examiner(s): Geckil, Mehmet B.
• Assistant Examiner(s): Thompson, Marc D.
• Application Number:
  US09/322,905
• Time in Patent Office: 1,428 Days
• Field of Search: 709/238, 709/242, 709/243, 370/395, 370/397, 370/395.3, 370/395.31, 370/395.32, 379/219, 379/220.01, 379/221.14, 379/377, 707/203, 707/200, 707/201, 707/202, 707/204
• US Class Current: 709/242
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A route table providing a list of pointers to checksum values computed across routes of interest to a particular protocol. A method of updating the route table when a route is changed and also updating the checksum values is further described. Updates to the checksum value may be done using an exclusive OR process allowing for relatively fast, incremental updates to the checksum value.

Claims

1. A method of maintaining a routing table in a router, the routing table including a first plurality of route entries, the method comprising:

a) accepting registration by a first routing protocol, the registration including identification of routes of interest; and

b) establishing a registration set change field associated with the registration and with a second plurality of route entries for indication of changes in the routes of interest.

2. The method as recited by claim 1 wherein each of the route entries have an associated sequence number.

3. The method as recited by claim 2 wherein the registration set change field is computed as a function of the sequence numbers for each of the route entries.

4. The method as recited by claim 3 wherein the function is an exclusive OR function.

5. The method as recited by claim 1 wherein the routes of interest are identified by protocol type.

6. The method as recited by claim 1 wherein the routes of interest are identified by IP prefix.

7. A method of indicating that a route entry in a route table has been updated comprising:

a) incrementing a route sequence number for the route entry;

b) walking a list of pointers associated with the route entry, the pointers pointing to checksum fields associated with the route entry, a checksum field being associated with a plurality of route entries; and

c) for each checksum value, recompute the checksum as a function of the sequence number and the original checksum value.

8. The method as recited by claim 7 wherein the function is an exclusive OR function.

9. A method of determining if a route of interest in a route table has been changed comprising:

a) comparing a registration set change field for a plurality of routes of interest with a stored registration set change field value; and

b) if the registration set change field values match, assume no route of interest has changed and, otherwise, examining change values associated with each of the plurality of routes of interest to determine if the route of interest has changed.

10. The method as recited by claim 9 wherein the change values are sequence numbers.

11. The method as recited by claim 9 wherein the method is carried out on a periodic polling basis.

12. The method as recited by claim 9 wherein the method is carried in response to an interrupt.