Method and apparatus for an attribute oriented routing update

• US 6,968,393 B1
• Filed: 11/19/2001
• Issued: 11/22/2005
• Est. Priority Date: 11/19/2001
• Status: Active Grant

• Current Assignee: Ericsson AB (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Redback Networks Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Marques, Pedro Miguel Martins Roque, Chen, Enke
• Primary Examiner(s): LIN, WEN TAI
• Application Number:
  US09/992,354
• Time in Patent Office: 1,464 Days
• Field of Search: 709237-238, 709/224, 709/229, 709/242, 370/317, 370351-352, 370/400, 370/395.31, 370/392
• US Class Current: 709/242
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/54 Organization of routing tables

Abstract

A computer implemented method and apparatus for an attribute-oriented routing update is described. The method comprises selecting an updated set of attributes in a routing table before selecting a set of updated destinations associated with the selected set of attributes, wherein the attributes are stored in an attribute table as a portion of the routing table and the attributes do not include the conventional network prefixes. An update message that includes the set of updated destinations for the set of attributes is then generated. The method is also extended to extraction of unreachable destinations by using a dummy attribute in the routing table, wherein the dummy attribute is selected first, followed by extracting the unreachable destinations.

Claims

1. A computer implemented method comprising:

selecting an updated set of attributes in a routing table before selecting a set of updated destinations associated with the selected set of attributes, wherein the selected set of attributes does not include a network prefix;

generating an update message that includes the set of updated destinations;

selecting a dummy attribute in the routing table before selecting a second set of updated destinations associated with the dummy attribute; and

generating a second update message indicating the second set of updated destinations as unreachable.

2. The computer implemented method of claim 1 wherein the routing table includes a destination data structure and an attribute data structure, wherein the destination data structure includes the set of updated destinations and a set of path data structures, and wherein an attribute data structure includes an entry indicating the updated set of attributes.

3. The computer implemented method of claim 2 wherein the destination data structure is a radix trie.

4. The computer implemented method of claim 2 wherein the destination data structure is a hash table.

5. The computer implemented method of claim 1 wherein the updated set of attributes reference the set of updated destinations.

6. The computer implemented method of claim 1 wherein the updated destinations is a linked list and the updated attributes reference the linked list'"'"'s head.

7. The computer implemented method of claim 1 wherein the updated destinations is a linked list and the updated attributes reference the linked list'"'"'s head and tail.

8. A computer implemented method comprising:

selecting a first data structure, the first data structure corresponding to a best path to a destination;

referencing a first element of a second data structure from the selected first data structure, the first element indicating a set of attributes of the best path, wherein the set of attributes does not include a network prefix;

referencing a second element of a third data structure from the first element, the second element indicating the destination;

determining a second destination to be unreachable; and

referencing a third element of the third data structure from a dummy element of the second data structure, the third element indicating the second destination.

9. The computer implemented method of claim 8 further comprising:

selecting the first element in the second data structure;

tracing a chain of elements of the third data structure from the selected first element;

creating an update message, the update message indicating the set of attributes;

indicating a set of destinations that are indicated by the chain of elements in the update message; and

transmitting the network update message.

10. The computer implemented method of claim 8 wherein the second data structure is a hash table.

11. The computer implemented method of claim 8 wherein the third data structure is a radix trie.

12. A network device comprising:

a memory to host a routing table, the routing table to include a first data structure to indicate a set of destinations and a second data structure to indicate a set of attributes; and

a set of one or more processors coupled with the memory, the set of processors to process a network update message that indicates one of the set of destinations and a subset of the set of attributes and to insert the one of the set of destinations into a chain of elements of the first data structure in accordance with the network update message, the chain to be referenced by an element of the second data structure that indicates the subset of the set of attributes, wherein the set of attributes does not include a network prefix,

wherein the set of processors is to insert a second element of the first data structure into a second attribute-oriented chain that is referenced by a dummy element of the second data structure.

13. The network device of claim 12 wherein the first data structure is a radix trie.

14. The network device of claim 12 wherein the second data structure is a hash table.

15. A network device comprising:

a memory to host a routing table, the routing table to include a first data structure to indicate a set of destinations and a second data structure to indicate a set of attributes; and

a set of one or more processors coupled with the memory, the set of processors to process a network update message that indicates one of the set of destinations and a subset of the set of attributes and to insert the one of the set of destinations into a chain of elements of the first data structure in accordance with the network update message, the chain to be referenced by an element of the second data structure that indicates the subset of the set of attributes, wherein the set of attributes does not include a network prefix,

wherein the set of processors is to trace the attribute-oriented chain of elements, to generate a second network update message, and to indicate a subset of the set of destinations in the second network update message, the subset of destinations indicated by the attribute-oriented chain of elements.

16. A network device comprising:

a line card to receive an update message that indicates a destination and a set of attributes; and

a control card coupled with the line card, the control card to host a routing table, the routing table to include a first data structure to indicate a set of destinations and a second data structure to indicate a plurality of attributes, the control card to process the update message and to insert the destinations into a chain of elements of the first data structure in accordance with the update message, the chain to be referenced by an element of the second data structure, the element of the second data structure to indicate the set of attributes, wherein the set of attributes does not include a network prefix,

wherein the line card is to receive an unreachability update message indicating a second destination, and wherein the control card is to process the unreachability update message, to select a second element of the first data structure that indicates the second destination and to insert the selected second element into a dummy attribute-oriented chain.

17. The network device of claim 16 wherein the first data structure is a radix trie.

18. The network device of claim 16 wherein the second data structure is a hash table.

19. A network device comprising:

a line card to receive an update message that indicates a destination and a set of attributes; and

a control card coupled with the line card, the control card to host a routing table, the routing table to include a first data structure to indicate a set of destinations and a second data structure to indicate a plurality of attributes, the control card to process the update message and to insert the destinations into a chain of elements of the first data structure in accordance with the update message, the chain to be referenced by an element of the second data structure, the element of the second data structure to indicate the set of attributes, wherein the set of attributes does not include a network prefix,

wherein the control card is to trace the chain of elements, to generate a second network update message, and to indicate a subset of the set of destinations in the second network update message, the subset of destinations indicated by the chain of elements.

20. A machine readable storage medium, which when executed by a set of one or more processors, cause said set of processors to perform operations comprising:

selecting an updated set of attributes in a routing table before selecting a set of updated destinations associated with the selected set of attributes, wherein the set of attributes does not include a network prefix;

generating an update message that includes the set of updated destinations for the set of attributes;

selecting a dummy attribute in the routing table before selecting a second set of updated destinations associated with the dummy attribute; and

generating a second update message indicating the second set of updated destinations as unreachable.

21. The machine readable medium of claim 20 wherein the routing table includes a destination data structure that includes the set of updated destinations, a set of path data structures, and an attribute data structure that includes an entry indicating the updated set of attributes.

22. The machine readable medium of claim 21 wherein the destination data structure is a radix trie.

23. The machine readable medium of claim 21 wherein the destination data structure is a hash table.

24. The machine readable medium of claim 20 wherein the updated set of attributes reference the set of updated destinations.

25. The machine readable medium of claim 20 wherein the set of updated destinations is a linked list and the updated set of attributes reference the linked list'"'"'s head.

26. The machine readable medium of claim 20 wherein the set of set of updated destinations is a linked list and the updated set of attributes reference the linked list'"'"'s head and tail.

27. A machine readable storage medium, which when executed by a set of one or more processors, cause said set of processors to perform operations comprising:

selecting a first data structure, the first data structure corresponding to a best path to a destination;

referencing a first element of a second data structure from the selected first data structure, the first element indicating a set of attributes of the best path, wherein the set of attributes does not include a network prefix;

referencing a second element of a third data structure from the first element, the second element indicating the destination;

determining a second destination to be unreachable; and

referencing a third element of the third data structure from a dummy element of the second data structure, the third element indicating the second destination.

28. The machine readable medium of claim 27 further comprising:

selecting the first element in the second data structure;

tracing a chain of elements of the third data structure from the selected first element;

creating an update message, the update message indicating the set of attributes;

indicating a set of destinations that are indicated by the chain of elements in the update message; and

transmitting the network update message.

29. The machine readable medium of claim 27 wherein the second data structure is a hash table.

30. The machine readable medium of claim 27 wherein the third data structure is a radix trie.

31. A machine readable storage medium, which when executed by a set of one or more processors, cause said set of processors to perform operations comprising:

selecting an element of a first data structure that is marked, the element indicating a set of attributes, wherein the set of attributes does not include a network prefix;

creating a network update message;

indicating the set of attributes in the message;

indicating a set of one or more destinations in the update message, the set of destinations indicated by a set of linked elements of a second data structure, the element of the first data structure referencing the set of linked elements;

determining a second destination to be unreachable; and

referencing a fourth element of the second data structure from a dummy element of the first data structure, the fourth element indicating the second destination.

32. The machine readable medium of claim 31 further comprising:

selecting a third data structure, the third data structure corresponding to a best path to a destination;

referencing a second element of the first data structure from the selected third data structure, the second element indicating a second set of attributes, the second set of attributes describing the best path; and

referencing a third element of the second data structure from the second element, the third element indicating the destination.

33. The machine readable medium of claim 31 wherein the first data structure is a hash table.

34. The machine readable medium of claim 31 wherein the third data structure is a radix trie.