Pipelined multiple issue packet switch

• US 6,831,923 B1
• Filed: 04/17/2000
• Issued: 12/14/2004
• Est. Priority Date: 08/04/1995
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Laor, Michael, Cieslak, Martin
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Ho, Chuong
• Application Number:
  US09/549,875
• Time in Patent Office: 1,702 Days
• Field of Search: 370/394, 370/412, 370/389, 370/392, 370/401, 370/428, 370/429, 370/229, 370/230, 370/231, 370/235, 370/391, 370/465, 370/411, 370/413
• US Class Current: 370/412
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9042 Separate storage for different parts of the packet, e.g. header and payload
• CPC Class Codes: H04L 49/9047 including multiple buffers, e.g. buffer pools

Abstract

A pipelined multiple issue architecture for a link layer or protocol layer packet switch, which processes packets independently and asynchronously, but reorders them into their original order, thus preserving the original incoming packet order. Each stage of the pipeline waits for the immediately previous stage to complete, thus causing the packet switch to be self-throttling and thus allowing differing protocols and features to use the same architecture, even if possibly requiring differing processing times. The multiple issue pipeline is scaleable to greater parallel issue of packets, and tunable to differing switch engine architectures, differing interface speeds and widths, and differing clock rates and buffer sizes. The packet switch comprises a fetch stage, which fetches the packet header into one of a plurality of fetch caches, a switching stage comprising a plurality of switch engines, each of which independently and asychronously reads from corresponding fetch caches, makes switching decisions, and write to a reorder memory, a reorder engine which reads from the reorder memory in the packets'"'"' original order, and a post-processing stage, comprising a post-process queue and a post-process engine, which performs protocol-specific post-processing on the packets.

Claims

1. A system, comprising

a packet memory;

N switch engines coupled to said packet memory;

NK reorder memories coupled to said N switch engines; and

a reorder engine coupled to said plurality of reorder memories and disposed to receive packet headers from said reorder memories in an order in which they were originally received;

wherein each one of said switch engines is independently coupled to a corresponding K of said reorder memories.

2. The system of claim 1, wherein K equals 2.

3. The system of claim 1, wherein N equals 2.

4. The system of claim 1, wherein N equals 4.

5. The system of claim 1, wherein each one of said N switch engines writes in sequence to said corresponding K reorder memories.

6. The system of claim 1, wherein each one of said NK reorder memories is processed globally.

7. The system of claim 5, wherein said reorder engine reads in sequence from each of said NK reorder memories.

8. The system of claim 5, wherein said reorder engine reads from each of said NK reorder memories in parallel with said N switch engines writing in sequence to said corresponding K of said reorder memories.