Techniques for entry lookups

• US 7,877,504 B2
• Filed: 08/29/2002
• Issued: 01/25/2011
• Est. Priority Date: 08/29/2002
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Vipat, Harshawardhan
• Primary Examiner(s): Dharia; Rupal D
• Assistant Examiner(s): Nguyen; Van Kim T
• Application Number:
  US10/231,542
• Publication Number:
  US 20040044787A1
• Time in Patent Office: 3,071 Days
• Field of Search: 709/232, 709236-238, 709/239, 709242-247, 709/249, 711/202, 711/206, 711/207, 370/395.5, 370/409, 370/470, 370/471
• US Class Current: 709/238
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 69/00 Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass networks security protocols H04L9/40; wireless communication networks H04W

Abstract

Techniques to store entries so that minimal sequential memory accesses are used to determine all relevant entries. Entries may be grouped into blocks. The order of entries within blocks may be set in a manner so that entry locations can be determined using an input value, such as a destination address. Blocks may be ordered into levels. Blocks of each level may be stored in consecutive storage locations. Accordingly, entry locations may be determined and retrieved with minimal sequential memory accesses by storing entries in a predetermined manner.

Claims

1. A method comprising:

storing entries in storage locations of a memory device;

determining storage locations of entries associated with a destination address; and

simultaneously retrieving entries associated with the destination address from multiple storage locations, wherein entries are derived from routing information and wherein determining the location of the entries is to comprise determining a storage location of an entry based on the following relationship;

Root+(1+a first portion of the destination address)*BlockSize+a second portion of the destination address, wherein the Root is to comprise a storage location of a first storage location of a first block, and the BlockSize is to comprise an amount of storage locations allocated to entries in a first group of the entries.

2. The method of claim 1, wherein the storing comprises storing the first and a second group of entries.

3. The method of claim 2, wherein the storing comprises storing the first and second group of entries in storage locations according to a linear order.

4. The method of claim 1, wherein the determining further comprises determining a storage location of an entry among the first group of entries using the first portion.

5. The method of claim 1, wherein the determining further comprises determining a storage location of an entry among the second group of entries using the first and second portions.

6. The method of claim 5, wherein the determining the storage location of the entry among the second group of entries further comprises using an amount of storage locations allocated to entries in the first group of entries.

7. The method of claim 5, wherein the determining the location of the entry among the second group comprises using the following relationship:

Root+(1+first portion of the destination address)*BlockSize+second portion of the destination address, wherein

Root comprises a storage location of a first storage location of the first block, and

BlockSize comprises an amount of storage locations allocated to entries in the first group.

8. The method of claim 1, wherein the storing comprises storing the first, a second, and a third group of entries.

9. The method of claim 8, wherein the storing comprises storing the first, second, and third group of entries in neighboring storage locations.

10. The method of claim 8, wherein the storing comprises storing the first, second, and third group of entries in storage locations according to a linear order.

11. The method of claim 8, wherein the destination address includes a first, second, and third portions.

12. The method of claim 11, wherein the determining further comprises using the first portion to determine a storage location of an entry among the first group of entries.

13. The method of claim 11, wherein the determining further comprises determining a storage location of an entry among the second group of entries using the first portion and the second portion.

14. The method of claim 11, wherein the determining further comprises determining a storage location of an entry among the third group of entries using the first portion, second portion, and third portion.

15. The method of claim 14, wherein the determining the storage location of the entry among the third group of entries further comprises using an amount of storage locations allocated to entries in the first and second groups and number of blocks within the first and second groups.

16. The method of claim 14, wherein the determining the storage location of the entry among the third group of entries comprises using the following relationship:

Root+(1+N+first portion*N+second portion)*BlockSize+third portion, wherein

Root comprises a storage location of a first storage location of the first block,

BlockSize comprises an amount of storage locations allocated to entries in the first group, and

N comprises a number of blocks in the first and second groups.

17. The method of claim 1, further comprising using at least one of the retrieved entries to determine an output interface port number.

18. The method of claim 17, wherein each entry includes a next hop.

19. The method of claim 18, wherein each entry includes next block pointer.

20. The method of claim 1, wherein the storing further comprises:

receiving routing information; and

allocating routing information into entries of at least two Trie-blocks.

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

allocating routing information into Trie-blocks;

portioning Trie-blocks into at least a first, second and third group of Trie-blocks;

associating a Trie-block of the first group with multiple Trie-blocks of the second group;

associating each Trie-block of the second group with multiple Trie-blocks of the third group;

storing Trie-blocks of each group in sequential storage locations; and

storing Trie-blocks associated with the same Trie-block in sequential storage locations.

22. An apparatus comprising:

a storage device to store entries in storage locations; and

an output interface provider to retrieve simultaneously multiple entries associated with a destination address and to determine an output interface port number associated with the destination address,

wherein entries are derived from routing information and wherein the output interface provide is to determine location of the entries based on the following relationship;

Root+(1+a first portion of the destination address)*BlockSize+a second portion of the destination address, wherein the Root is to comprise a storage location of a first storage location of a first block, and the BlockSize is to comprise an amount of storage locations allocated to entries in a first group of the entries.

23. The apparatus of claim 22, wherein the output interface provider further comprises:

a storage location determiner to determine storage locations of entries associated with the destination address, and

an output interface determiner to determine the output interface port number using at least one of the retrieved entries.

24. The apparatus of claim 22, wherein the storage device is to store the first and a second group of entries.

25. The apparatus of claim 24, wherein the storage device is to store the first and second group of entries in storage locations according to a linear order.

26. The apparatus of claim 22, wherein the output interface provider is to determine a storage location of an entry among the first group of entries using the first portion.

27. The apparatus of claim 22, wherein the output interface provider is to determine a storage location of an entry among the second group of entries using the first and second portions.

28. The apparatus of claim 27, wherein the output interface provider is to determine the storage location of the entry among the second group of entries using an amount of storage locations allocated to entries in the first group of entries.

29. The apparatus of claim 27, wherein the output interface provider is to determine the location of the entry among the second group using the following relationship:

Root+(1+first portion of the destination address)*BlockSize+second portion of the destination address, wherein

Root comprises a storage location of a first storage location of the first block, and

BlockSize comprises an amount of storage locations allocated to entries in the first group.

30. The apparatus of claim 22, wherein the storage device is to store a first, second, and third group of entries.

31. The apparatus of claim 30, wherein the storage device is to store the first, second, and third group of entries in neighboring storage locations.

32. The apparatus of claim 30, wherein the storage device is to store the first, second, and third group of entries in storage locations according to a linear order.

33. The apparatus of claim 30, wherein the destination address includes first, second and third portions.

34. The apparatus of claim 33, wherein the output interface provider is to determine a storage location of an entry among the first group of entries using the first portion.

35. The apparatus of claim 33, wherein the output interface provider is to determine a storage location of an entry among the second group of entries using the first and second portions.

36. The apparatus of claim 33, wherein the output interface provider is to determine a storage location of an entry among the third group of entries using the first portion, second portion, and third portion.

37. The apparatus of claim 36, wherein the output interface provider is to determine the storage location of the entry among the third group using an amount of storage locations allocated to entries in the first and second groups and number of blocks within the first and second groups.

38. The apparatus of claim 36, wherein the output interface provider is to determine the storage location of the entry among the third group using the following relationship:

Root+(1+N+first portion*N+second portion)*BlockSize+third portion, wherein

Root comprises a storage location of a first storage location of the first block,

BlockSize comprises an amount of storage locations allocated to entries in the first group, and

N comprises a number of blocks in the first and second groups.

39. The apparatus of claim 22, wherein each entry includes a next hop.

40. The apparatus of claim 39, wherein each entry includes next block pointer.

41. The apparatus of claim 22, further comprising an entry storage location allocator to receive routing information and to allocate routing information into entries of at least two Trie-blocks.

42. A system comprising:

an input interface port to receive a packet;

at least one output interface port to transmit the packet; and

an output interface determiner to identify an output interface port number to which to transfer the packet, the output interface determiner comprising;

a storage device to store entries in storage locations, and

an output interface provider to retrieve simultaneously multiple entries associated with a destination address of the packet and to determine the output interface port number associated with the destination address,

wherein entries are derived from routing information and the output interface provider is to determine location of the entries based on the following relationship;

Root+(1+a first portion of the destination address)*BlockSize+a second portion of the destination address, wherein the Root is to comprise a storage location of a first storage location of a first block, and the BlockSize is to comprise an amount of storage locations allocated to entries in a first group of the entries.

43. The system of claim 42, wherein the output interface provider further comprises:

a storage location determiner to determine storage locations of entries associated with the destination address, and

an output interface determiner to determine the output interface port number using at least one of the retrieved entries.

44. The system of claim 42, wherein the packets are encoded in compliance with IEEE 802.3.

45. The system of claim 42, wherein the packets are encoded in compliance with SONET.

46. The system of claim 42, wherein the packets are encoded in compliance with SDH.

47. The system of claim 42, wherein the output interface port number comprises a media access control (MAC) address.

48. The system of claim 42, further comprising a switch fabric, wherein:

the switch fabric is to receive the packet and the output interface port number and to transfer the packet to an output interface port associated with the output interface port number.