Pipelined packet switching and queuing architecture

• US 6,977,930 B1
• Filed: 02/14/2000
• Issued: 12/20/2005
• Est. Priority Date: 02/14/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Epps, Garry P., Laor, Michael
• Primary Examiner(s): Rao, Seema S.
• Assistant Examiner(s): Harper, Kevin C.
• Application Number:
  US09/503,552
• Time in Patent Office: 2,136 Days
• Field of Search: 370/392, 370/389, 370/412, 370/428, 370/429
• US Class Current: 370/392
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/21 using leaky-bucket
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 49/1546 using pipelined operation
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/3063 Pipelined operation
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element
• CPC Class Codes: H04L 49/552 by ensuring the integrity of packets received through redundant connections
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/9078 using an external memory or storage device

Abstract

A pipelined linecard architecture for receiving, modifying, switching, buffering, queuing and dequeuing packets for transmission in a communications network. The linecard has two paths: the receive path, which carries packets into the switch device from the network, and the transmit path, which carries packets from the switch to the network. In the receive path, received packets are processed and switched in an asynchronous, multi-stage pipeline utilizing programmable data structures for fast table lookup and linked list traversal. The pipelined switch operates on several packets in parallel while determining each packet'"'"'s routing destination. Once that determination is made, each packet is modified to contain new routing information as well as additional header data to help speed it through the switch. Each packet is then buffered and enqueued for transmission over the switching fabric to the linecard attached to the proper destination port. The destination linecard may be the same physical linecard as that receiving the inbound packet or a different physical linecard. The transmit path consists of a buffer/queuing circuit similar to that used in the receive path. Both enqueuing and dequeuing of packets is accomplished using CoS-based decision making apparatus and congestion avoidance and dequeue management hardware. The architecture of the present invention has the advantages of high throughput and the ability to rapidly implement new features and capabilities.

Claims

1. An apparatus for switching packets, each packet having a header portion, a corresponding tail portion, and a class of service indicator, said apparatus comprising:

a pipelined switch comprising;

a plurality of packet header buffers (PHBs);

an equal plurality of PHB pointers, each said PHB pointer pointing to a corresponding PHB; and

an equal plurality of pipeline stage circuits connected in a sequence, comprising at least a first stage circuit and a last stage circuit,

wherein;

each said stage circuit begins an operation substantially simultaneously with each other;

each said stage circuit passes data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed;

said first stage circuit reads said header portion and stores said header portion in said corresponding PHB using said corresponding PHB pointer; and

said last stage circuit outputs a modified header portion; and

a receive buffer manager (RBM) comprising;

a joining circuit connected to said pipelined switch wherein said modified header portion and said corresponding tail portion are joined to form a modified packet;

a receive queue manager connected to said joining circuit that buffers said modified packet in a receive packet buffer and enqueues said modified packet using said class of service indicator and a plurality of receive queues; and

a dequeue circuit connected to said receive queue manager and said receive packet buffer, wherein said dequeue circuit uses said class of service indicator to dequeue said modified packet to a switch fabric.

2. The apparatus as recited in claim 1, wherein said plurality of pipeline stage circuits further comprise:

a pre-process circuit connected to said first stage circuit, wherein said pre-process circuit uses a second said PHB pointer to record first data in said corresponding PHB;

a pointer lookup circuit connected to said pre-process circuit that compares said header portion to a first data structure and determines a leaf pointer using said second PHB pointer;

a table lookup circuit connected to said pointer lookup circuit that uses said leaf pointer to access one or more sets of linked data structures and to fetch second data, wherein said table lookup circuit uses a third said PHB pointer to record said second data in said corresponding PHB; and

a post-process circuit using said third PHB pointer and connected to said table lookup circuit, wherein said post-process circuit uses a fourth said PHB pointer to record third data in said corresponding PHB;

wherein said last pipeline stage circuit comprises a gather circuit connected to said post-process circuit, and wherein said gather circuit uses said fourth PHB pointer to assemble said modified header portion.

3. The apparatus as recited in claim 1, further comprising:

an input device that receives said packet; and

a first buffer connected between said input device and said first stage circuit, wherein said first buffer buffers said header portion and said tail portion.

4. The apparatus as recited in claim 3, further comprising a multiplexer interposed between said first buffer and said first stage circuit, wherein said multiplexer multiplexes said header portion and said corresponding tail portion together.

5. The apparatus as recited in claim 1, further comprising a second buffer interposed between said last stage circuit and said joining circuit.

6. The apparatus as recited in claim 5, further comprising a multiplexer interposed between said last stage circuit and said second buffer, wherein said multiplexer multiplexes said modified header portion and said corresponding tail portion together.

7. The apparatus as recited in claim 1, wherein said receive packet buffer comprises buffers of different sizes.

8. The apparatus as recited in claim 1, wherein said receive packet buffer comprises buffers of equal size.

9. The apparatus as recited in claim 1, wherein said receive queue manager comprises a congestion avoidance circuit utilizing a status of each said receive queue.

10. The apparatus as recited in claim 9, wherein said status comprises a measure of average queue depth.

11. The apparatus as recited in claim 1, further comprising a transmit buffer manager (TBM), said TBM comprising:

a third buffer that receives one or more packets from said switch fabric;

a transmit queue manager connected to said third buffer that buffers each said packet in a transmit packet buffer and enqueues said packet using said class of service indicator and a plurality of transmit queues; and

a dequeue circuit connected to said transmit queue manager and said transmit packet buffer, wherein said dequeue circuit uses said class of service indicator to dequeue each said packet.

12. The apparatus as recited in claim 11, wherein said transmit packet buffer comprises buffers of different sizes.

13. The apparatus as recited in claim 11, wherein said transmit packet buffer comprises buffers of equal size.

14. The apparatus as recited in claim 11, wherein said transmit queue manager comprises a congestion avoidance circuit utilizing a status of each said transmit queue.

15. The apparatus as recited in claim 14, wherein said status comprises a measure of average queue depth.

16. The apparatus as recited in claim 11, further comprising a transmit FIFO connected to an output of said dequeue circuit.

17. A method of switching packets, which comprises:

receiving a packet, said packet having a header portion, a corresponding tail portion, and a class of service indicator;

switching said packet through a pipelined switch having a plurality of packet header buffers (PHBs), an equal plurality of PHB pointers wherein each said PHB pointer points to a corresponding PHB, and an equal plurality of pipeline stages connected in a sequence, comprising at least a first stage and a last stage, said switching further comprising;

beginning an operation in each said stage substantially simultaneously with each other said stage;

passing data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed;

reading and storing said header in said corresponding PHB using said corresponding PHB pointer; and

outputting a modified header portion; and

buffering said modified header portion in a receive buffer manager (RBM), said buffering further comprising;

joining said modified header portion and said corresponding tail portion to form a modified packet;

buffering and enqueuing said modified packet using said class of service indicator; and

dequeuing said modified packet using said class of service indicator.

18. The method of claim 17, wherein said switching further comprises:

recording first data in said corresponding PHB using a second said PHB pointer;

comparing said header portion to a first data structure and determining a leaf pointer using said second PHB pointer;

fetching second data using said leaf pointer to access one or more sets of linked data structures and recording said second data in said corresponding PHB using a third said PHB pointer;

post-processing said header portion using said third PHB pointer and recording third data in said corresponding PHB using a fourth said PHB pointer; and

assembling said modified header portion using said fourth PHB pointer.

19. The method of claim 17, wherein said switching further comprises buffering said header portion and said tail portion prior to said switching.

20. The method of claim 19, wherein said switching further comprises multiplexing said header portion and said tail portion together prior to beginning said operation.

21. The method of claim 17, wherein said buffering further comprises buffering said header portion and said tail portion prior to said joining.

22. The method of claim 21, wherein said buffering further comprises multiplexing said header portion and said tail portion together prior to said joining.

23. The method of claim 17, further comprising:

receiving one or more packets;

buffering and enqueuing each said packet using said class of service indicator and a plurality of queues; and

dequeuing each said packet using said class of service indicator.

24. The method of claim 23, wherein said buffering uses a packet buffer comprising buffers of different sizes.

25. The method of claim 23, wherein said buffering uses a packet buffer comprising buffers of equal size.

26. The method of claim 23, wherein said buffering further comprises avoiding congestion using a status of each said queue.

27. The method of claim 26, wherein said status comprises a measure of average queue depth.

28. The method of claim 23, wherein said dequeuing uses a transmit FIFO.

29. A computer system for interfacing with a communications network, comprising computer instructions for:

receiving a packet, said packet having a header portion, a corresponding tail portion, and a class of service indicator;

switching said packet through a pipelined switch having a plurality of packet header buffers (PHBs), an equal plurality of PHB pointers wherein each said PHB pointer points to a corresponding PHB, and an equal plurality of pipeline stages connected in a sequence, comprising at least a first stage and a last stage, said switching further comprising;

beginning an operation in each said stage substantially simultaneously with each other said stage;

passing data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed;

reading and storing said header in said corresponding PHB using said corresponding PHB pointer; and

outputting a modified header portion; and

buffering said modified header portion in a receive buffer manager (RBM), said buffering further comprising;

joining said modified header portion and said corresponding tail portion to form a modified packet;

buffering and enqueuing said modified packet using said class of service indicator; and

dequeuing said modified packet using said class of service indicator.

30. The computer system of claim 29, wherein said switching further comprises:

recording first data in said corresponding PHB using a second said PHB pointer;

comparing said header portion to a first data structure and determining a leaf pointer using said second PHB pointer;

fetching second data using said leaf pointer to access one or more sets of linked data structures and recording said second data in said corresponding PHB using a third said PHB pointer;

post-processing said header portion using said third PHB pointer and recording third data in said corresponding PHB using a fourth said PHB pointer; and

assembling said modified header portion using said fourth PHB pointer.

31. The computer system of claim 29, further comprising:

receiving one or more packets;

buffering and enqueuing each said packet using said class of service indicator and a plurality of queues; and

dequeuing each said packet using said class of service indicator.

32. A computer readable storage medium, comprising computer instructions for:

receiving a packet, said packet having a header portion, a corresponding tail portion, and a class of service indicator;

switching said packet through a pipelined switch having a plurality of packet header buffers (PHBs), an equal plurality of PHB pointers wherein each said PHB pointer points to a corresponding PHB, and an equal plurality of pipeline stages connected in a sequence, comprising at least a first stage and a last stage, said switching further comprising;

beginning an operation in each said stage substantially simultaneously with each other said stage;

passing data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed;

reading and storing said header in said corresponding PHB using said corresponding PHB pointer; and

outputting a modified header portion; and

buffering said modified header portion in a receive buffer manager (RBM), said buffering further comprising;

joining said modified header portion and said corresponding tail portion to form a modified packet;

buffering and enqueuing said modified packet using said class of service indicator; and

dequeuing said modified packet using said class of service indicator.

33. The computer readable storage medium of claim 32, wherein said switching further comprises:

recording first data in said corresponding PHB using a second said PHB pointer;

comparing said header portion to a first data structure and determining a leaf pointer using said second PHB pointer;

fetching second data using said leaf pointer to access one or more sets of linked data structures and recording said second data in said corresponding PHB using a third said PHB pointer;

post-processing said header portion using said third PHB pointer and recording third data in said corresponding PHB using a fourth said PHB pointer; and

assembling said modified header portion using said fourth PHB pointer.

34. The computer readable storage medium of claim 32, further comprising:

receiving one or more packets;

buffering and enqueuing each said packet using said class of service indicator and a plurality of queues; and

dequeuing each said packet using said class of service indicator.

35. A computer data signal embodied in a carrier wave, comprising computer instructions for:

receiving a packet, said packet having a header portion, a corresponding tail portion, and a class of service indicator;

switching said packet through a pipelined switch having a plurality of packet header buffers (PHBs), an equal plurality of PHB pointers wherein each said PHB pointer points to a corresponding PHB, and an equal plurality of pipeline stages connected in a sequence, comprising at least a first stage and a last stage, said switching further comprising;

beginning an operation in each said stage substantially simultaneously with each other said stage;

passing data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed;

reading and storing said header in said corresponding PHB using said corresponding PHB pointer; and

outputting a modified header portion; and

buffering said modified header portion in a receive buffer manager (RBM), said buffering further comprising;

joining said modified header portion and said corresponding tail portion to form a modified packet;

buffering and enqueuing said modified packet using said class of service indicator; and

dequeuing said modified packet using said class of service indicator.

36. The computer data signal of claim 35, wherein said switching further comprises:

recording first data in said corresponding PHB using a second said PHB pointer;

comparing said header portion to a first data structure and determining a leaf pointer using said second PHB pointer;

fetching second data using said leaf pointer to access one or more sets of linked data structures and recording said second data in said corresponding PHB using a third said PHB pointer;

post-processing said header portion using said third PHB pointer and recording third data in said corresponding PHB using a fourth said PHB pointer; and

assembling said modified header portion using said fourth PHB pointer.

37. The computer data signal of claim 35, further comprising:

receiving one or more packets;

buffering and enqueuing each said packet using said class of service indicator and a plurality of queues; and

dequeuing each said packet using said class of service indicator.