Scaleable route redistribution mechanism

• US 6,643,706 B1
• Filed: 06/29/1999
• Issued: 11/04/2003
• Est. Priority Date: 06/29/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Marques, Pedro M., Lin, Steven P.
• Primary Examiner(s): Etienne, Ario
• Assistant Examiner(s): SALAD, ABDULLAHI ELMI
• Application Number:
  US09/343,145
• Time in Patent Office: 1,589 Days
• Field of Search: 709/238, 709/242, 709/226, 709/231, 709/247, 709/230, 370/392, 370/394, 707/100, 707/101, 707/103, 707/3, 707/7
• US Class Current: 709/242
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/563 Software download or update
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of distributing route information is described. The method includes maintaining a number of entries, indicating that at least one of the entries, requiring processing by a first process, has been processed by the first process, and causing the first process to process another of the entries requiring processing by the first process based on the indication. In doing so, the first process uses the indication to decide which of the entries requiring processing the process has already processed and which of those entries remain to be processed. Each one of the entries preferably corresponds to at least one characteristic of a network connection between a number of network elements, such as a route between network elements.

Claims

1. A method of distributing route information comprising:

maintaining a plurality of entries, wherein;

said plurality of entries is a plurality of route entries, and

each one of said plurality of route entries corresponds to a route in a network;

indicating an entry of said plurality of entries requiring processing by a first process has been processed by said first process, said indicating comprises maintaining a marker configured to indicate which of said plurality of route entries requiring processing by said first process have not been processed by said first process, said marker corresponding to said first process, wherein said marker is configured to store an index;

storing said plurality of route entries as nodes in a radix tree;

incrementing a master index upon performing an addition operation or a modification operation, said addition operation adding a new route entry to said plurality of route entries and said modification operation modifying a one of said plurality of route entries;

storing said master index in a node index of said new route entry, if an addition operation is performed;

storing said master index in a node index of said one of said plurality of route entries, if a modification operation is performed; and

causing said first process to process another of said plurality of entries requiring processing by said first process based on said indication.

2. The method of claim 1, further comprising:

comparing said index with a node index of each one of said plurality of route entries by traversing said radix tree; and

processing said each one of said plurality of route entries, if said index is less than said node index of said each one of said plurality of route entries.

3. The method of claim 1, further comprising:

storing a node index of each leaf node in said radix tree in an alternate index of said each leaf node;

storing a highest alternate node index in an alternate node index of a non-leaf node of said radix tree, wherein said highest alternate node index is a maximum value of a node index of said non-leaf node and an alternate node index of any child node of said non-leaf node; and

for each one of said nodes requiring processing by said first process, said each one of said nodes requiring processing by said first process having an alternate node index greater than said index, comparing a node index of said each one of said nodes requiring processing by said first process to said index, and

if said node index of said each one of said nodes requiring processing by said first process is greater than said index, processing said each one of said nodes requiring processing by said first process.

4. A computer program product encoded in computer readable media, the computer program product comprising:

a first set of instructions, executable by a processor and configured to cause said processor to maintain a plurality of entries, wherein said plurality of entries is a plurality of route entries, and each one of said plurality of route entries corresponds to a route in a network;

a second set of instructions, executable on said processor and configured to cause said processor to indicate an entry of said plurality of entries requiring processing by a first process has been processed by said first process, wherein said second set of instructions comprises a third set of instructions, executable on said processor and configured to cause said processor to maintain a marker configured to indicate which of said plurality of route entries requiring processing by said first process have not been processed by said first process, said marker corresponding to said first process, wherein said marker is configured to store an index;

a fourth set of instructions, executable on said processor and configured to cause said processor to cause said first process to process another of said plurality of entries requiring processing by said first process based on said indication;

a fifth set of instructions, executable on said processor and configured to cause said processor to increment a master index upon performing an addition operation or a modification operation, said addition operation adding a new route entry to said plurality of route entries and said modification operation modifying a one of said plurality of route entries;

a sixth set of instructions, executable on said processor and configured to cause said processor to store said master index in a node index of said new route entry, if an addition operation is performed;

an seventh set of instructions, executable on said processor and configured to cause said processor to store said master index in a node index of said one of said plurality of route entries, if a modification operation is performed; and

an eight set of instructions, executable on said processor and configured to cause said processor to store said plurality of route entries as nodes in a radix tree.

5. The computer program product of claim 4, further comprising:

a ninth set of instructions, executable on said processor and configured to cause said processor to compare said index with a node index of each one of said plurality of route entries by traversing said radix tree; and

a tenth set of instructions, executable on said processor and configured to cause said processor to process said each one of said plurality of route entries, if said index is less than said node index of said each one of said plurality of route entries.

6. The computer program product of claim 4, further comprising:

a ninth set of instructions, executable on said processor and configured to cause said processor to store a node index of each leaf node in said radix tree in an alternate index of said each leaf node;

a tenth set of instructions, executable on said processor and configured to cause said processor to store a highest alternate node index in an alternate node index of a non-leaf node of said radix tree, wherein said highest alternate node index is a maximum value of a node index of said non-leaf node and an alternate node index of any child node of said non-leaf node; and

an eleventh set of instructions, executable on said processor and configured to cause said processor to, for each one of said nodes requiring processing by said first process, said each one of said nodes requiring processing by said first process having an alternate node index greater than said index, compare a node index of said each one of said nodes requiring processing by said first process to said index, and

if said node index of said each one of said nodes requiring processing by said first process is greater than said index, cause said first process to process said each one of said nodes requiring processing by said first process.

7. A method of distributing route information comprising:

maintaining a plurality of entries, wherein

said plurality of entries is a plurality of route entries,

each one of said plurality of route entries corresponds to a route in a network, and

said plurality of entries comprises a routing table;

indicating an entry of said plurality of entries requiring processing by a first process has been processed by said first process;

detecting a change made to said routing table by a second process;

notifying said first process of said change;

updating a marker corresponding to said first process, said marker indicating which of said plurality of entries requiring processing by said first process have been processed by said first process; and

causing said first process to process another of said plurality of entries requiring processing by said first process based on said indication.

8. The method of claim 7, further comprising:

storing said plurality of route entries in a linked list.

9. The method of claim 8, wherein said marker is a pointer, further comprising:

causing said marker to point to a current route entry of said plurality of route entries, said current route entry and ones of said plurality of route entries previous to said current route entry in said linked list having been processed by said first process.

10. The method of claim 8, wherein said marker is an entry in said linked list, further comprising:

positioning said marker in said linked list after a current route entry of said plurality of route entries, said current route entry and ones of said plurality of route entries previous to said current route entry in said linked list having been processed by said first process.

11. A computer program product encoded in computer readable media, the computer program product comprising:

a first set of instructions, executable by a processor and configured to cause said processor to maintain a plurality of entries, wherein

said plurality of entries is a plurality of route entries,

each one of said plurality of route entries corresponds to a route in a network, and

said plurality of entries comprises a routing table;

a second set of instructions, executable on said processor and configured to cause said processor to indicate an entry of said plurality of entries requiring processing by a first process has been processed by said first process;

a third set of instructions, executable on said processor and configured to cause said processor to detect a change made to said routing table by a second process;

a fourth set of instructions, executable on said processor and configured to cause said processor to notify said first process of said change; and

a fifth set of instructions, executable on said processor and configured to cause said processor to update a marker corresponding to said first process, said marker indicating which of said plurality of entries requiring processing by said first process have been processed by said first process

a sixth set of instructions, executable on said processor and configured to cause said processor to cause said first process to process another of said plurality of entries requiring processing by said first process based on said indication.

12. The computer program product of claim 11, wherein said marker is a pointer, further comprising:

a fifth set of instructions, executable on said processor and configured to cause said processor to store said plurality of route entries in a linked list; and

a sixth set of instructions, executable on said processor and configured to cause said processor to cause said marker to point to a current route entry of said plurality of route entries, said current route entry and ones of said plurality of route entries previous to said current route entry in said linked list having been processed by said first process.

13. The computer program product of claim 11, wherein said marker is an entry in said linked list, further comprising:

a fifth set of instructions, executable on said processor and configured to cause said processor to store said plurality of route entries in a linked list; and

a sixth set of instructions, executable on said processor and configured to cause said processor to position said marker in said linked list after a current route entry of said plurality of route entries, said current route entry and ones of said plurality of route entries previous to said current route entry in said linked list having been processed by said first process.