Address learning to enable high speed routing table lookups

• US 7,408,930 B2
• Filed: 02/07/2003
• Issued: 08/05/2008
• Est. Priority Date: 02/07/2003
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Shimizu, Takeshi, Pathi, Sridhar
• Primary Examiner(s): Pham; Chi
• Assistant Examiner(s): Chou; Albert T.
• Application Number:
  US10/360,004
• Publication Number:
  US 20040156362A1
• Time in Patent Office: 2,006 Days
• Field of Search: 370/401, 370/389, 370/428, 370/392, 370/395.32, 365/202
• US Class Current: 370/389
• CPC Class Codes: H04L 2012/5679 Arbitration or scheduling
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/201 Multicast operation; Broadcast operation
• CPC Class Codes: H04L 49/255 Control mechanisms for ATM switching fabrics
• CPC Class Codes: H04L 49/309 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A switch includes multiple ports, a switching fabric, and a routing table module. The routing table module includes a multi-bank memory structure for maintaining routing information. The routing information enables the switching fabric to route packets between the ports based upon addresses within the packets.

Claims

1. A switch comprising:

a plurality of ports that communicate packets;

a switch fabric that transports received packets between the ports;

a plurality of memory banks logically divided into a plurality of rows, wherein each of the rows comprises a storage location from each of the memory banks, wherein each of the storage locations maintains a routing entry;

an arbitration module that receives lookup requests and learn requests from the ports and to schedule memory access operations based upon the lookup requests and the learn requests, wherein the memory access operations comprise at least one address; and

a memory access module that receives the memory access operations, to determine a hash key from the address, wherein the hash key indicates a particular one of the rows, and to access the indicated row to perform at least one of the memory access operations.

2. The switch of claim 1, wherein the arbitration module schedules memory access operations to service any outstanding lookup requests before scheduling memory access operations to service any outstanding learn requests.

3. The switch of claim 1, wherein the arbitration module schedules the memory access operations to service a lookup request that identifies a destination address, wherein the memory access operations comprise a read operation that indicates the destination address from the lookup request.

4. The switch of claim 3, wherein the arbitration module further determines if the destination address is a multicast address and, if so, to insure that the memory access operations do not include a write operation.

5. The switch of claim 3, wherein the arbitration module further schedules the memory access operations to include a write operation that indicates a particular one of the storage locations within a selected one of the memory banks.

6. The switch of claim 1, wherein a routing entry comprises address information and routing information, wherein the routing information indicates one or more of the ports.

7. The switch of claim 1, wherein the arbitration module schedules the memory access operations to service a learn request that identifies a source address, wherein the memory access operations comprise a read operation that indicates the source address from the lookup request.

8. The switch of claim 1, wherein the memory access operations comprise at least one of a write operation and a read operation.

9. The switch of claim 1, wherein to service a learn request the arbitration module;

schedules first memory access operations that include a read operation indicating a source address from the learn request;

determines whether the read operation detected a miss in the memory banks; and

if the miss is detected, schedules second memory access operations that include a write operation indicating the source address and a port mapping from the learn request.

10. The switch of claim 9, wherein the arbitration module further insures that the first memory access operations do not include any write operations.

11. A method for performing routing table operations comprising:

monitoring for lookup requests and learn requests received from any of a plurality of ports;

detecting a lookup request comprising a destination address;

determining a hash key based on the destination address;

accessing a memory module using the hash key, wherein the memory module comprises a plurality of memory banks logically divided into a plurality of rows, wherein each of the rows comprises a storage location from each of the memory banks, wherein each of the storage locations maintains a routing entry, wherein the hash key indicates one of the row;

determining whether one of the entries from the indicated row includes address information matching the destination address;

if the indicated row includes a matching entry, returning routing information from the matching entry, the routing information identifying one or more of the ports.

12. The method of claim 11, further comprising servicing any outstanding lookup requests prior to servicing any outstanding learn requests.

13. The method of claim 11, further comprising determining that the destination address is a multicast address and, in response, insuring that none of the memory banks perform a write operation while accessing the memory module using the hash key.

14. The method of claim 11, further comprising performing a write operation while accessing the memory module using the hash key, the write operation indicating a particular one of the storage locations within a selected one of the memory banks, wherein accessing the memory module using the hash key reads the entries from the indicated row in all of the memory banks except for the memory bank indicated in the write operation.

15. The method of claim 11, further comprising detecting a learn request that identifies a source address and routing information, determining a second hash key based on the source address, and accessing the memory module using the second hash key, wherein the second hash key indicates a second one of the rows.

16. The method of claim 15, further comprising insuring that none of the memory banks perform a write operation while accessing the memory module using the second hash key.

17. The method of claim 15, further comprising:

determining whether one of the entries from the second indicated row includes address information matching the source address;

if none of the entries match, determining whether the second indicated row includes an empty entry; and

if the second indicated row includes an empty entry, writing the source address and the routing information to the empty entry.

18. A switch comprising:

means for monitoring for lookup requests and learn requests received from any of a plurality of ports;

means for detecting a lookup request comprising a destination address;

means for determining a hash key based on the destination address;

means for accessing a memory module using the hash key, wherein the memory module comprises a plurality of memory banks logically divided into a plurality of rows, wherein each of the rows comprises a storage location from each of the memory banks, wherein each of the storage locations maintains a routing entry, wherein the hash key indicates one of the row;

means for determining whether one of the entries from the indicated row includes address information matching the destination address;

means for, if the indicated row includes a matching entry, returning routing information from the matching entry, the routing information identifying one or more of the ports.

19. The switch of claim 18, further comprising means for determining that the destination address is a multicast address and, in response, insuring that none of the memory banks perform a write operation while accessing the memory module using the hash key.

20. The switch of claim 18, further comprising means for performing a write operation while accessing the memory module using the hash key, the write operation indicating a particular one of the storage locations within a selected one of the memory banks, wherein the means for accessing the memory module using the hash key reads the entries from the indicated row in all of the memory banks except for the memory bank indicated in the write operation.

21. The switch of claim 18, further comprising:

means for detecting a learn request that identifies a source address and routing information;

means for determining a second hash key based on the source address; and

means for accessing the memory module using the second hash key, wherein the second hash key indicates a second one of the rows.

22. The switch of claim 21, further comprising means for insuring that none of the memory banks perform a write operation while accessing the memory module using the second bash key.

23. The switch of claim 21, further comprising:

means for determining whether one of the entries from the second indicated row includes address information matching the source address;

means for, if none of the entries match, determining whether the second indicated row includes an empty entry; and

means for, if the second indicated row includes an empty entry, writing the source address and the routing information to the empty entry.