Managing routing information for a computer network

• US 8,370,523 B1
• Filed: 12/20/2002
• Issued: 02/05/2013
• Est. Priority Date: 12/20/2002
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (NortonLifeLock Inc.)
• Inventors: Slaughter, Gregory L., Saulpaugh, Thomas, Chen, Dawn
• Primary Examiner(s): EL CHANTI, HUSSEIN A
• Application Number:
  US10/324,496
• Time in Patent Office: 3,700 Days
• Field of Search: 370/274, 709/200, 709/214, 709/237, 709/242, 709/238, 709/240
• US Class Current: 709/240
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

A plurality of routing entries may be stored in a routing table. Each routing entry may include information usable for routing a message through a network. As new routing entries are received or created, each new routing entry may be added to the routing table. However, if there is not sufficient memory or storage to add the new routing entry to the routing table, then the least recently used existing routing entry in the routing table may be replaced with the new routing entry. In the event that the replaced routing entry is needed later, the replaced routing entry may be re-created.

Claims

1. A computer-readable memory medium comprising program instructions executable to implement a method comprising:

a first node determining that a first routing entry in a routing table is a least recently used routing entry, wherein the first routing entry specifies routing information for routing messages addressed to a first destination;

the first node replacing the first routing entry with a second routing entry in response to determining that the first routing entry is the least recently used routing entry;

the first node receiving a request to route a first message to the first destination after replacing the first routing entry with the second routing entry;

the first node determining whether the routing table includes a routing entry specifying routing information for routing messages addressed to the first destination, in response to the request to route the first message to the first destination;

the first node communicating with one or more other nodes to perform an algorithm to create routing information for routing the first message to the first destination in response to determining that the routing table does not include a routing entry specifying routing information for routing messages addressed to the first destination; and

the first node storing the created routing information in the routing table.

2. The computer-readable memory medium of claim 1, wherein the first node determines that the first routing entry is the least recently used routing entry and replaces the first routing entry with the second routing entry in response to one or more of

determining that a size of the routing table is greater than or equal to a maximum size;

and/or

determining that there is not sufficient memory to add the second routing entry to the routing table without replacing another routing entry in the routing table.

3. The computer-readable memory medium of claim 1, wherein the method further comprises:

the first node receiving a request to route a message to a second destination before said replacing the first routing entry with the second routing entry;

the first node communicating with one or more other nodes to perform an algorithm to create routing information for routing messages to the second destination in response to the request to route the message to the second destination; and

wherein the first node replaces the first routing entry with the second routing entry in response to the request to route the message to the second destination, wherein the second routing entry specifies the routing information for routing messages addressed to the second destination.

4. The computer-readable memory medium of claim 1, wherein the method further comprises:

the first node determining that a third routing entry in the routing table is a least recently used routing entry in response to the request to route the first message to the first destination; and

wherein said storing the created routing information in the routing table comprises the first node replacing the third routing entry with a fourth routing entry in response to determining that the third routing entry is the least recently used routing entry, wherein the fourth routing entry specifies the created routing information.

5. The computer-readable memory medium of claim 1, wherein the method further comprises:

the first node routing the first message to the first destination after said communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination.

6. The computer-readable memory medium of claim 1,

wherein the routing table is stored in volatile memory of the first node.

7. The computer-readable memory medium of claim 1, wherein the routing table is stored in non-volatile memory of the first node.

8. The computer-readable memory medium of claim 1, wherein the method further comprises:

the first node storing information indicating which routing entry in the routing table was least recently used; and

wherein the first node uses the information indicating which routing entry in the routing table was least recently used in determining that the first routing entry in the routing table is the least recently used routing entry.

9. The computer-readable memory medium of claim 1, wherein said first node communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination comprises the first node communicating with the one or more other nodes to perform the algorithm to create routing information for routing the first message to a plurality of instances of the first destination in a location-independent manner without directly specifying locations of the plurality of instances of the first destination.

10. The computer-readable memory medium of claim 1, wherein said first node communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination comprises the first node communicating with the one or more other nodes to perform the algorithm to create routing information for routing the first message along a plurality of tree edges to a plurality of instances of the first destination.

11. A first node comprising:

at least one processor;

a memory storing program instructions; and

wherein the at least one processor is operable to execute the program instructions to implement a method comprising

determining that a first routing entry in a routing table is a least recently used routing entry, wherein the first routing entry specifies routing information for routing messages addressed to a first destination;

replacing the first routing entry with a second routing entry in response to determining that the first routing entry is the least recently used routing entry;

receiving a request to route a first message to the first destination after replacing the first routing entry with the second routing entry;

determining whether the routing table includes a routing entry specifying routing information for routing messages addressed to the first destination, in response to the request to route the first message to the first destination;

communicating with one or more other nodes to perform an algorithm to create routing information for routing the first message to the first destination in response to determining that the routing table does not include a routing entry specifying routing information for routing messages addressed to the first destination; and

storing the created routing information in the routing table.

12. The first node of claim 11, wherein the at least one processor is operable to execute the program instructions to determine that the first routing entry is the least recently used routing entry and replace the first routing entry with the second routing entry in response to one or more of

determining that a size of the routing table is greater than or equal to a maximum size;

and/or

determining that there is not sufficient memory to add the second routing entry to the routing table without replacing another routing entry in the routing table.

13. The first node of claim 11, wherein the method further comprises:

receiving a request to route a message to a second destination before said replacing the first routing entry with the second routing entry;

communicating with one or more other nodes to perform an algorithm to create routing information for routing messages to the second destination in response to the request to route the message to the second destination; and

wherein the at least one processor is operable to execute the program instructions to replace the first routing entry with the second routing entry in response to the request to route the message to the second destination, wherein the second routing entry specifies the routing information for routing messages addressed to the second destination.

14. The first node of claim 11, wherein the method further comprises:

determining that a third routing entry in the routing table is a least recently used routing entry in response to the request to route the first message to the first destination; and

wherein said storing the created routing information in the routing table comprises replacing the third routing entry with a fourth routing entry in response to determining that the third routing entry is the least recently used routing entry, wherein the fourth routing entry specifies the created routing information.

15. The first node of claim 11, wherein the method further comprises:

routing the first message to the first destination after said communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination.

16. The first node of claim 11, wherein the memory comprises volatile memory;

wherein the routing table is stored in the volatile memory.

17. The first node of claim 11, further comprising:

a non-volatile memory device; and

wherein the routing table is stored on the non-volatile memory device.

18. The first node of claim 11, wherein the method further comprises:

storing information indicating which routing entry in the routing table was least recently used; and

wherein the at least one processor is operable to execute the program instructions to determine that the first routing entry in the routing table is the least recently used routing entry based on the stored information indicating which routing entry in the routing table was least recently used.

19. The first node of claim 11, wherein said communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination comprises communicating with the one or more other nodes to determine perform the algorithm to create routing information for routing the first message to a plurality of instances of the first destination in a location-independent manner without directly specifying locations of the plurality of instances of the first destination.

20. The first node of claim 11, wherein said communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination comprises communicating with the one or more other nodes to perform the algorithm to create routing information for routing the first message along a plurality of tree edges to a plurality of instances of the first destination.

21. A method comprising:

a first node determining that a first routing entry in a routing table is a least recently used routing entry, wherein the first routing entry specifies routing information for routing messages addressed to a first destination;

the first node replacing the first routing entry with a second routing entry in response to determining that the first routing entry is the least recently used routing entry;

the first node receiving a request to route a first message to the first destination after replacing the first routing entry with the second routing entry;

the first node determining whether the routing table includes a routing entry specifying routing information for routing messages addressed to the first destination, in response to the request to route the first message to the first destination;

the first node communicating with one or more other nodes to perform an algorithm to create routing information for routing the first message to the first destination in response to determining that the routing table does not include a routing entry specifying routing information for routing messages addressed to the first destination; and

the first node storing the created routing information in the routing table.

22. The method of claim 21, wherein the first node determines that the first routing entry is the least recently used routing entry and replaces the first routing entry with the second routing entry in response to one or more of

determining that a size of the routing table is greater than or equal to a maximum size;

and/or

determining that there is not sufficient memory to add the second routing entry to the routing table without replacing another routing entry in the routing table.

23. The method of claim 21, wherein the method further comprises:

the first node receiving a request to route a message to a second destination before said replacing the first routing entry with the second routing entry;

the first node communicating with one or more other nodes to perform an algorithm to create routing information for routing messages to the second destination in response to the request to route the message to the second destination; and

wherein the first node replaces the first routing entry with the second routing entry in response to the request to route the message to the second destination, wherein the second routing entry specifies the routing information for routing messages addressed to the second destination.

24. The method of claim 21, wherein the method further comprises:

the first node determining that a third routing entry in the routing table is a least recently used routing entry in response to the request to route the first message to the first destination; and

wherein said storing the created routing information in the routing table comprises the first node replacing the third routing entry with a fourth routing entry in response to determining that the third routing entry is the least recently used routing entry, wherein the fourth routing entry specifies the created routing information.

25. The method of claim 21, wherein the method further comprises:

the first node routing the first message to the first destination to after said communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination.

26. The method of claim 21, wherein the routing table is stored in volatile memory of the first node.

27. The method of claim 21, wherein the routing table is stored in non-volatile memory of the first node.

28. The method of claim 21, wherein the method further comprises:

the first node storing information indicating which routing entry in the routing table was least recently used;

wherein the first node uses the information indicating which routing entry in the routing table was least recently used in determining that the first routing entry in the routing table is the least recently used routing entry.

29. The method of claim 21, wherein said first node communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination comprises the first node communicating with the one or more other nodes to perform the algorithm to create routing information for routing the first message to a plurality of instances of the first destination in a location independent manner without directly specifying locations of the plurality of instances of the first destination.

30. The method of claim 21, wherein said first node communicating with the one or more other nodes to perform the algorithm to create the routing information for routing the first message to the first destination comprises the first node communicating with the one or more other nodes to perform the algorithm to create routing information for routing the first message along a plurality of tree edges to a plurality of instances of the first destination.