SRAM based cache for DRAM routing table lookups

• US 7,286,534 B2
• Filed: 11/02/2001
• Issued: 10/23/2007
• Est. Priority Date: 11/02/2001
• Status: Active Grant

• Current Assignee: Maxlinear Incorporated
• Original Assignee: Infineon Technologies North America Corporation (Infineon Technologies AG)
• Inventors: Kloth, Axel K.
• Primary Examiner(s): Duong; Frank
• Application Number:
  US10/052,793
• Publication Number:
  US 20030086434A1
• Time in Patent Office: 2,181 Days
• Field of Search: 370/351, 370/392, 370/395.31, 370/395.32, 370/401, 370/389
• US Class Current: 370/392
• 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/54 Organization of routing tables

Abstract

A router (101) includes one or more input ports (104) and one or more output ports (112). The router (101) includes a lookup table (105) to determine routing of the incoming packets or cells. The lookup table is implemented in dynamic random access memory (DRAM) with a portion implemented as static random access memory (SRAM) (202, 204). The SRAM (204) is used to store a first search level of destination addresses. Once the first search level in SRAM (204) has been exhausted, the search moves to the DRAM portion (202).

Claims

1. A data and telecommunications switch, comprising:

one or more input ports for receiving data from one or more input devices;

a router adapted to route said data to one or more output devices, said router including a router table, the router table implemented as a DRAM and SRAM lookup table; and

a switch control unit for conducting a search of said SRAM and DRAM lookup table when said data are received,

wherein conducting a search of said SRAM and DRAM lookup table includes searching an SRAM portion of said SRAM and DRAM lookup table for routing information,

wherein if routing information is found in the SRAM portion, no search is performed in an DRAM portion of said SRAM and DRAM lookup table, and

wherein if no routing information is found in the SRAM portion, searching only the DRAM portion of said SRAM and DRAM lookup table.

2. The data and telecommunications switch in accordance with claim 1, said lookup table search comprising an interval bisection search, wherein a predetermined number of levels of said interval bisection search are stored in the SRAM portion, and a remaining number of levels are stored in the DRAM portion.

3. The data and telecommunications switch in accordance with claim 1, said lookup table search comprising a binary tree search, wherein a predetermined number of levels of said binary tree search are stored in the SRAM portion, and a remaining number of levels are stored in the DRAM portion.

4. A method, comprising:

receiving a data packet at an input port;

reading a header of said data packet for routing identification information;

using said routing identification information for accessing an SRAM portion of a routing table for routing information, and if no entry corresponding to said routing identification information is found in said SRAM portion, accessing only a DRAM portion of said routing table; and

routing said data packet using said routing information.

5. The method in accordance with claim 4, wherein said accessing comprises performing an interval bisection search, wherein a predetermined number of levels of said interval bisection search are stored in the SRAM portion, and a remaining number of levels are stored in the DRAM portion.

6. The method in accordance with claim 4, wherein said accessing comprises performing a binary tree search, wherein a predetermined number of levels of said binary tree search are stored in the SRAM portion, and a remaining number of levels are stored in the DRAM portion.

7. A method, comprising:

providing one or more input ports for receiving data from one or more input devices;

providing a router adapted to route said data to one or more output devices, said router including a router table, the router table implemented as a DRAM and SRAM lookup table; and

providing a switch control unit for conducting a search of said SRAM and DRAM lookup table when said data are received,

wherein conducting a search of said SRAM and DRAM lookup table includes searching an SRAM portion of said SRAM and DRAM lookup table for routing information,

wherein if routing information is found in the SRAM portion, no search is performed in an DRAM portion of said SRAM and DRAM lookup table,

wherein if no routing information is found in the SRAM portion, searching the DRAM portion of said SRAM and DRAM lookup table, and

wherein a predetermined number of levels of said search is stored in the SRAM portion, and a remaining number of levels of said search is stored in the DRAM portion.

8. The method in accordance with claim 7, said lookup table search includes an interval bisection search.

9. The method in accordance with claim 8, said lookup table search.

10. A router for a data and telecommunications system, comprising:

a routing controller for reading routing identification information from incoming data packets;

and a routing table for storing routing information, said routing table having a DRAM portion and an SRAM cache, wherein said routing controller uses said routing identification information to access said routing table for said routing information,

wherein a first portion of a search of said routing table is conducted in said SRAM cache and a second portion is conducted in said DRAM portion, and

wherein only said second portion of said search in said DRAM portion is conducted if no routing information is found in the SRAM portion.

11. The router in accordance with claim 10, wherein said search comprises an interval bisection search.

12. The router in accordance with claim 10, wherein said search comprises a binary tree search.