Methods and system for efficient route lookup

• US 20030031167A1
• Filed: 01/02/2002
• Published: 02/13/2003
• Est. Priority Date: 02/28/2001
• Status: Abandoned Application

• Current Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Ericsson, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: Natchu, Vishnu, Singh, Abhishek Ranjan
• Application Number:
  US10/033,038
• Publication Number:
  US 20030031167A1
• Time in Patent Office: Days
• US Class Current: 370/352
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A method and system for performing a route lookup in a routing system, including a plurality of routes places a bound on the number of accesses to the memory necessary to perform a route lookup and guarantees the minimal amount of memory to achieve a particular bound. For each node the memory required to meet a bound on the depth of the tree rooted at that node is computed, given the distribution of routes in the network. A route can be added or deleted which changes the topology and hence the memory required to meet the bound, but not all nodes need to recalculate their costs, and an incremental algorithm minimizes the overall costs of performing a route topology change and the subsequent lookup

Claims

1. In a data network with router having memory for storing entries for a plurality of destinations from the router, a method of performing route lookup that places a bound on the number of accesses to the memory, the method comprising the steps of:

determining the costs of all possible lookup architectures that can be constructed given the distribution of destinations in the data network;

choosing a lookup architecture which requires the minimum amount of memory to obtain the next hop of any destination and that places a bound on the number of memory accesses to obtain the next hop; and

after receipt of a data packet, using the chosen lookup architecture to lookup a route for a destination address associated with the data packet.

2. The method of claim 1 wherein the step of determining the costs of all possible architectures further comprises the step of determining all possible lookup trees.

3. The method of claim 2 wherein the step of choosing a lookup architecture further comprises the step of choosing a lookup tree that requires the minimum amount of memory to obtain the next hop of any destination and that places a bound on the number of memory accesses to obtain the next hop

4. The method according to claim 1 further comprising the step of arranging the destinations supported by the router in a tree-like architecture.

5. The method according to claim 4 further comprising the step of arranging the destinations supported by the router in a radix tree architecture.

6. The method according to claim 1 further comprising the step of storing the destinations associated with data packets as addresses.

7. The method according to claim 6 further comprising the step of storing the destinations associated with data packets as IP addresses.

8. The method according to claim 1 further comprising the step of calculating the cost associated with performing the route lookup for a data packet.

9. The method according to claim 8 further comprising the step of determining if the cost associated with performing the route lookup is minimum.

10. The method according to claim 9 wherein the cost associated with performing the route lookup is based on the memory required to store the lookup architecture.

11. The method according to claim 9 wherein calculating the cost associated with performing the route lookup is calculated based on a length of a destination address for the data packet.

12. The method according to claim 9 wherein calculating the cost associated with performing the route lookup is calculated by summing values based on a height in which the node is located and costs associated with performing the route lookup of individual routes below the node for which the cost is being calculated.

13. The method according to claim 1 wherein an optimum value associated with performing the route lookup is a cost associated with minimum memory usage in performing the route lookup.

14. The method according to claim 1 wherein the number of accesses to the memory are used to locate a destination address associated with the route.

15. The method according to claim 14 wherein the destination address is an Internet Protocol (IP) destination address.

16. A method for performing a route lookup in a router for a data packet with an associated destination address, the method comprising the steps of:

inspecting the destination address associated with the data packet; and

using the destination address to access a memory space containing a lookup architecture to arrive at the next hop for the data packet which is serviced by the router, wherein the lookup architecture is adapted for bounding the number accesses to the memory space for any destination address of the data packet.

17. The method of claim 16 wherein lookup architecture is further adapted to minimize the amount of memory required to meet any bound on accesses to the memory space for any particular destination address.

18. The method of claim 16 further comprising the steps of”

determining the lookup architecture; and

storing the lookup architecture in the memory space.

19. The method of claim 18 wherein the step of determining the lookup architecture further comprises the steps of:

determining the costs of all possible lookup architectures that can be constructed given the distribution of destinations in the data network containing the router; and

choosing a lookup architecture which requires the minimum amount of memory to obtain the next hop of any destination and that places a bound on the number of memory accesses to obtain the next hop.

20. The method of claim 19 further comprising the step of using the chosen lookup architecture to lookup a route for a destination address associated with the data packet.

21. The method according to claim 18 wherein the step of storing the lookup architecture further comprises the step of storing the lookup architecture in a tree-like architecture.

22. The method according to claim 18 wherein the step of storing the lookup architecture further comprises the step of storing the lookup architecture in a radix tree architecture.

23. The method according to claim 16 further comprising the step of saving the lookup architecture in a routing table containing route information for any destination address serviced by the router.

24. The method according to claim 16 further comprising the step of calculating the cost associated with performing the route lookup for the data packet.

25. The method according to claim 24 further comprising the step of determining with the cost associated with performing the route lookup exceeds a specified value and, if so, replacing the route entry with a destination having a maximum route lookup size.

26. The method according to claim 24 wherein cost associated with performing the route lookup is calculated based on a length of the destination address.

27. The method according to claim 24 wherein the cost associated with performing the route lookup is calculated by summing values based on a height in which the destination is located and costs associated with performing the route lookup of individual routes below the destination for which the cost is being calculated.

28. The method according to claim 24 wherein an optimum value associated with performing the route lookup is a cost associated with a minimum memory usage in performing the route lookup.

29. The method according to claim 16 wherein the destination address is an Internet Protocol (IP) destination address.

30. In a data network including a plurality of destinations and a plurality of routes for reaching the destinations, a router adapted to minimize the costs of route lookup for data packets routed in the data network, the router comprising:

an interface to incoming links of the data network;

logic means for receiving incoming data packets from the data network through said interface and for determining the destination of data packets, determining the route to the next hop along a destination, and routing data packets on a route extending to a next hop; and

a memory space accessible by the logic means and adapted for storing a lookup architecture for routes;

wherein the lookup architecture that places a bound on the number accesses to the memory space for any destination address of the data packet.

31. The router of claim 30 wherein the lookup architecture is further adapted to minimize the amount of memory required to meet any bound on accesses to the memory space for any particular destination address.

32. The router of claim 30 wherein said lookup architecture is arranged as a compressed radix tree.

33. The router of claim 30 wherein the lookup architecture stores an optimum value associated with performing the route lookup in terms of the cost associated with a minimum memory required to meet a particular bound.