Single-chip architecture for shared-memory router

• US 6,343,072 B1
• Filed: 12/31/1997
• Issued: 01/29/2002
• Est. Priority Date: 10/01/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cheriton, David R., Bechtolsheim, Andreas V.
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US09/002,122
• Time in Patent Office: 1,490 Days
• Field of Search: 370/229, 370/230, 370/235, 370/236, 370/237, 370/252, 370/254, 370/400, 370/401, 370/402, 370/466, 370/389, 370/392, 370/351, 370/412, 370/413, 370/414, 370/415, 370/416, 370/366, 711/216, 709/240, 709/242, 709/244
• US Class Current: 370/351
• CPC Class Codes: H04L 49/103 using a shared central buffer; using a shared memory
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches

Abstract

The invention provides a single-chip method. The method includes a memory shared among packet buffers for receiving packets, packet buffers for transmitting packets, and packet header buffers for packet forwarding lookup. Accesses to that shared memory are multiplexed and prioritized. Packet reception is performed with relatively high priority, packet transmission is performed with medium priority, and packet forwarding lookup is performed with relatively low priority. The single-chip method includes circuits for serially receiving packet header information, converting that information into a parallel format for transmission to an SRAM for lookup, and queuing input packets for later forwarding at an output port. Similarly, the single-chip method includes circuits for queuing output packets for transmission at an output port, receiving packet forwarding information from the SRAM in a parallel format, and converting packet header information from output packets into a serial format for transmission. The single-chip method also includes a region in its shared memory for a packet forwarding table, and circuits for performing forwarding lookup responsive to packet header information.

Claims

1. A router, including

at least one port disposed for receiving packets;

at least one port disposed for transmitting packets; and

processing circuits integrated into a single monolithic integrated circuit, said processing circuits including

circuits for accessing a shared memory, said circuits including

(a) circuits disposed for copying packets between at least one region of said shared memory and said processing circuits, and

(b) circuits disposed for performing packet lookup in at least one region of said shared memory, said packet lookup being responsive to packet headers of said packets

wherein said circuits disposed for copying packets comprise first circuits for receiving packet information in a serial format and converting said packet information into a parallel format and second circuits for receiving said packet information in a parallel format and converting said packet information into a serial format, and

wherein said circuits for accessing said shared memory include circuits disposed for multiplexing and prioritizing requests for copying incoming packets to said shared memory, requests for copying outgoing packets from said shared memory, and requests for performing packet lookup.

2. A router as in claim 1, wherein said at least one port disposed for receiving packets includes a plurality of ports disposed for receiving packets.

3. A router as in claim 1, wherein said at least one port disposed for transmitting packets includes a plurality of ports disposed for transmitting packets.

4. A router as in claim 1, wherein said circuits disposed for multiplexing and prioritizing assign relatively high priority to said requests for copying incoming packets to said shared memory.

5. A router as in claim 1, wherein said circuits disposed for multiplexing and prioritizing assign relatively low priority to said requests for copying outgoing packets from said shared memory.

6. A router as in claim 1, wherein said circuits disposed for multiplexing and prioritizing assign priority to said requests in a manner so as to maximize throughput and minimize routing latency.

7. Apparatus including

a shared memory, said shared memory including packet buffers for packets and packet lookup information;

a router coupled to said shared memory, said router including processing circuits

integrated into a single monolithic integrated circuit, said processing circuits including

circuits for accessing said shared memory, said circuits including

(a) circuits disposed for copying packets between at least one region of said shared memory and said processing circuits, and

(b) circuits disposed for accessing said shared memory for performing packet lookup

wherein said circuits disposed for copying packets comprise first circuits for receiving packet information in a serial format and converting said packet information into a parallel format and second circuits for receiving said packet information in a parallel format and converting said packet information into a serial format, and

wherein said circuits for accessing said shared memory include circuits disposed for multiplexing and prioritizing requests for copying incoming packets to said shared memory, requests for copying outgoing packets from said shared memory, and requests for performing packet lookup.

8. Apparatus as in claim 7, including a processor coupled to said router.

9. Apparatus as in claim 7, wherein said circuits disposed for multiplexing and prioritizing assign relatively high priority to said requests for copying incoming packets to said shared memory.

10. Apparatus as in claim 7, wherein said circuits disposed for multiplexing and prioritizing assign relatively low priority to said requests for copying outgoing packets from said shared memory.

11. Apparatus as in claim 7, wherein said circuits disposed for multiplexing and prioritizing assign priority to said requests in a manner so as to maximize throughput and minimize routing latency.

12. A method, including the steps of

receiving packets using at least one input port;

transmitting packets using at least one output port; and

routing said packets from said at least one input port to said at least one output port, using processing circuits integrated into a single monolithic integrated circuit,

wherein said routing comprises multiplexing and prioritizing requests for copying incoming packets to said shared memory, requests for copying outgoing packets from said shared memory, and requests for performing packet lookup.

13. A method, including the steps of

receiving packets using at least one input port;

transmitting packets using at least one output port;

copying packets between at least one region of a shared memory and a set of processing circuits integrated into a single monolithic integrated circuit; and

performing packet lookup using said shared memory and said processing circuits, and

wherein said steps of copying packets and performing packet lookup include the steps of multiplexing and prioritizing requests for copying incoming packets to said shared memory, requests for copying outgoing packets from said shared memory, and requests for performing packet lookup.

14. A method as in claim 13, wherein said at least one input port includes a plurality of ports disposed for receiving packets.

15. A method as in claim 13, wherein said at least one output port includes a plurality of ports disposed for transmitting packets.

16. A method as in claim 13, wherein said steps of multiplexing and prioritizng assign relatively high priority to said requests for copying incoming packets to said shared memory.

17. A method as in claim 13, wherein said steps of multiplexing and prioritizing assign relatively low priority to said requests for copying outgoing packets from said shared memory.

18. A method as in claim 13, wherein said steps of multiplexing and prioritizing assign priority to said requests in a manner so as to maximize throughput and minimize routing latency.

19. A method, including the steps of

recording packets and packet lookup information in a shared memory;

copying packets to and from at least one region of said shared memory;

accessing said shared memory to perform packet lookup, using processing circuits which are integrated into a single monolithic integrated circuit, and

wherein said steps of copying packets and accessing said shared memory include the steps of multiplexing and prioritizing requests for copying incoming packets to said shared memory, requests for copying outgoing packets from said shared memory, and requests for performing packet lookup.

20. A method as in claim 19, including coupling a processor to said processing circuits.

21. A method as in claim 19, wherein said steps of multiplexing and prioritizing assign relatively high priority to said requests for copying incoming packets to said shared memory.

22. A method as in claim 19, wherein said steps of multiplexing and prioritizing assign relatively low priority to said requests for copying outgoing packets from said shared memory.

23. A method as in claim 19, wherein said steps of multiplexing and prioritizing assign priority to said requests in a manner so as to maximize throughput and minimize routing latency.