Routing table lookup implemented using M-trie having nodes duplicated in multiple memory banks

• US 6,308,219 B1
• Filed: 07/31/1998
• Issued: 10/23/2001
• Est. Priority Date: 07/31/1998
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Hughes, John H.
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): CALDWELL, ANDREW T
• Application Number:
  US09/127,253
• Time in Patent Office: 1,180 Days
• Field of Search: 709/238, 709/242, 370/392, 370/422, 707/101, 707/103
• US Class Current: 709/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof

Abstract

The invention provides a method and system for rapid access to one or more M-tries for responding to header information. The M-tries are stored in a plurality of memory banks, which are accessed in parallel to provide relatively greater access throughput. Parts of the M-tries that are (or are expected to be) frequently referenced are stored in multiple banks of the memory, to provide concurrent simultaneous access for those parts of the M-tries for parallel lookup of multiple routes. Regions of the multiple banks of the memory can be dynamically reallocated to provide improved access through-put to those multiple banks. The invention can be applied to routing decisions in response to destination addresses, to combinations of destination and source addresses (either for unicast or multicast routing), to access control decisions, to quality of service decisions, to accounting, and to other administrative processing in response to header information.

Claims

1. A system comprising:

a plurality of memory banks, said plurality of memory banks collectively recording at least one M-trie responsive to header information in a set of packets; and

means for dynamically reallocating said nodes within said plurality of banks;

wherein at least one node of said M-trie is recorded in at least two of said banks.

2. A system as in claim 1, wherein said plurality of memory banks are disposed for concurrent access.

3. A system as in claim 1, comprising means for dynamically reallocating said nodes within said plurality of banks responsive to changes in relative frequency of access to said nodes.

4. A system as in claim 1, comprising means for dynamically reallocating said nodes within said plurality of banks responsive to improving access throughput for references to said nodes.

5. A system as in claim 1, comprising means for dynamically reallocating said nodes within said plurality of banks responsive to relative frequency of access to said nodes.

6. A system as in claim 1, wherein said at least one node is a node expected to be referenced frequently.

7. A system as in claim 1, wherein said at least one node is a root node for one of said at least one M-tries.

8. A system as in claim 1, wherein said at least one node is disposed for a plurality of concurrent accesses.

9. A system as in claim 1, wherein said one M-trie comprises access control information.

10. A system as in claim 1, wherein said one M-trie comprises accounting information.

11. A system as in claim 1, wherein said one M-trie comprises information for responding to packets.

12. A system as in claim 1, wherein said one M-trie comprises quality of service information.

13. A system as in claim 1, wherein said one M-trie comprises multicast routing information.

14. A system as in claim 1, wherein said one M-trie comprises information for routing decisions.

15. A system as in claim 1, wherein said one M-trie comprises information for routing decisions responsive to destination addresses and to source addresses.

16. A system as in claim 1, wherein said one M-trie comprises information for routing decisions responsive to source addresses.

17. A system as in claim 1, wherein said one M-trie comprises unicast routing information.

18. A method comprising the step of:

recording, in a plurality of memory banks, at least one M-trie responsive to header information in a set of packets; and

dynamically reallocating said nodes within said plurality of banks;

wherein at least one node of said M-trie is recorded in at least two of said banks.

19. A method as in claim 18, further comprising the step of accessing said plurality of memory banks in parallel.

20. A method as in claim 18, further comprising the step of dynamically reallocating said nodes within said plurality of banks, said step of allocating being responsive to changes in relative frequency of access to said nodes.

21. A method as in claim 18, further comprising the step of dynamically reallocating said nodes within said plurality of banks, said step of reallocating being responsive to improving access throughput for references to said nodes.

22. A method as in claim 18, further comprising the step of dynamically reallocating said nodes within said plurality of banks, said step of reallocating being responsive to relative frequency of access to said nodes.

23. A method as in claim 18, wherein said at least one node is a node expected to be referenced frequently.

24. A method as in claim 18, wherein said at least one node is a root node for one of said at least one M-tries.

25. A method as in claim 18, wherein said at least one node is disposed for a plurality of concurrent accesses.

26. A method as in claim 18, wherein said one M-trie comprises access control information.

27. A method as in claim 18, wherein said one M-trie comprises accounting information.

28. A method as in claim 18, wherein said one M-trie comprises information for responding to packets.

29. A method as in claim 18, wherein said one M-trie comprises quality of service information.

30. A method as in claim 18, wherein said one M-trie comprises multicast routing information.

31. A method as in claim 18, wherein said one M-trie comprises information for routing decisions.

32. A method as in claim 18, wherein said one M-trie comprises information for routing decisions responsive to destination addresses and to source addresses.

33. A method as in claim 18, wherein said one M-trie comprises information for routing decisions responsive to source addresses.

34. A method as in claim 18, wherein said one M-trie comprises unicast routing information.