Pipelined packet switching and queuing architecture
A pipelined linecard architecture for receiving, modifying, switching, buffering, queuing and dequeuing packets for transmission in a communications network is disclosed. The linecard has two paths: a receive path and a transmit path. In the receive path, received packets are processed and switched in an asynchronous, multi-stage pipeline. 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. Each packet is buffered and enqueued for transmission over the switching fabric to a destination linecard. The transmit path includes a buffer/queuing circuit similar to that used in the receive path. Both enqueuing and dequeuing of packets is accomplished using a CoS-based decision making apparatus.
1. A network device comprising:
a receive buffer manager (RBM), configured to transmit a packet of a plurality of packets to a switch fabric by virtue of comprising
an RBM packet receive stage, wherein
the RBM packet receive stage is configured to be coupled to a pipelined switch, and
the RBM packet receive stage is further configured to receive a plurality of portions of each of the plurality of packets,
an RBM packet transmit stage, wherein
the RBM packet transmit stage is configured to be coupled to the switch fabric,
an RBM buffer, coupled to the RBM packet receive stage and the RBM packet transmit stage, wherein
the RBM buffer is configured to receive the plurality of packets from the pipelined switch, and
an RBM queue manager, coupled to control the RBM packet receive stage and the RBM packet transmit stage, wherein
the RBM queue manager is configured to cause the packet to be conveyed from the pipelined switch to the switch fabric via the RBM buffer, using at least one of the plurality of portions of the packet.
2. The network device of claim 1 , wherein
the RBM packet receive stage is configured to be coupled to the pipelined switch by virtue of being configured to receive the plurality of portions of each of the plurality of packets from the pipelined switch.
3. The network device of claim 2 , wherein the RBM packet receive stage is configured to receive the plurality of portions of the each of the plurality of packets by virtue of comprising:
a packet header buffer, and
a packet tail buffer.
4. The network device of claim 2 , wherein the RBM buffer comprises a plurality of RBM queues, and the RBM queue manager further comprises:
an RBM enqueue unit, coupled to the RBM buffer, wherein
the RBM enqueue unit is configured to cause the packet to be enqueued into an RBM queue of the plurality of RBM queues by virtue of being coupled to control the RBM packet receive stage; and
an RBM dequeue unit, coupled to the RBM buffer, wherein
the RBM dequeue unit is configured to cause the packet to be dequeued from the RBM queue by virtue of being coupled to control the RBM packet transmit stage.
5. The network device of claim 4 , wherein
the packet comprises a class of service indicator,
the RBM enqueue unit is further configured to cause the packet to be enqueued according to the class of service indicator, and
the RBM dequeue unit is further configured to cause the packet to be dequeued according to a bandwidth sharing scheme.
6. The network device of claim 2 , wherein
the RBM buffer comprises a plurality of RBM queues, and
the RBM queue manager is further configured to cause the packet to be enqueued into an RBM queue of the plurality of RBM queues, and dequeued from the RBM queue.
7. The network device of claim 6 , wherein
the packet comprises a class of service indicator,
the RBM queue manager is further configured to cause the packet to be enqueued according to the class of service indicator, and
the RBM queue manager is further configured to cause the packet to be dequeued according to a bandwidth sharing scheme.
8. The network device of claim 2 , further comprising:
a transmit buffer manager (TBM), configured to receive the packet from the switch fabric by virtue of comprising
a TBM packet receive stage, configured to be coupled to the switch fabric,
a TBM buffer, coupled to the TBM packet receive stage and the TBM packet transmit stage,
a TBM packet transmit stage, and
a TBM queue manager, configured to cause the packet to be conveyed from the TBM packet receive stage to the TBM packet transmit stage via the TBM buffer.
9. The network device of claim 8 , further comprising:
a pipelined switch, wherein
at least one of the plurality of portions is a class of service indicator, and
the pipelined switch is configured to control processing of the plurality of packets using the class of service indicators.
10. The network device of claim 9 , wherein the plurality of portions comprise a header portion and a tail portion, and the RBM packet receive stage comprises:
a packet header buffer, configured to store at least one of the header portions, and
a packet tail buffer, configured to store at least one of the tails portions.
11. The network device of claim 8 , wherein the TBM buffer comprises a plurality of TBM queues, and the TBM queue manager further comprises:
a TBM enqueue unit, coupled to the TBM buffer, wherein
the TBM enqueue unit is configured to cause the packet to be enqueued into an TBM queue of the plurality of TBM queues by virtue of being coupled to control the TBM packet receive stage; and
a TBM dequeue unit, coupled to the TBM buffer, wherein
the TBM dequeue unit is configured to cause the packet to be dequeued from the TBM queue by virtue of being coupled to control the TBM packet transmit stage.
12. The network device of claim 11 , wherein
the packet comprises a class of service indicator,
the TBM enqueue unit is further configured to cause the packet to be enqueued according to the class of service indicator, and
the TBM dequeue unit is further configured to cause the packet to be dequeued according to a bandwidth sharing scheme.
13. The network device of claim 11 , wherein
each of the plurality of RBM queues is a virtual RBM queue, and
each of the plurality of TBM queues is a virtual TBM queue.
14. The network device of claim 11 , wherein
each virtual RBM queue of the each of the plurality of RBM queues and each virtual TBM queue of the each of the plurality of TBM queues corresponds to one another in a one-to-one relationship.
15. The network device of claim 2 , wherein the packet comprises a class of service indicator, and the RBM enqueue unit is further configured to cause the packet to be enqueued according to the class of service indicator.
16. A method comprising:
receiving a packet at a pipelined switch, wherein
the packet comprises a header portion, and
the pipelined switch comprises a plurality of pipeline stages coupled to one another sequentially; and
processing the packet, wherein
the processing comprises
reading the header portion of the packet,
generating a modified header portion, wherein
the generating comprises replacing at least a portion of the header portion, and
the at least the portion of the header portion comprises label information,
storing the modified header portion, and
outputting the packet from the pipelined switch, and
the outputting outputs the packet with the modified header portion.
17. The network device of claim 16 , wherein
the packet comprises a class of service indicator, and
at least one of the pipeline stages is configured to perform the generating using at least the class of service indicator of the packet.
18. The network device of claim 16 , wherein the generating further comprises:
extracting the label information from the header portion;
performing one or more lookup operations, wherein
at least one of the one or more lookup operations uses the label information; and
creating the modified header portion using a result of the lookup operation.
19. The network device of claim 18 , wherein
the creating the modified header portion comprises
performing a gather operation,
the performing the one or more lookup operations comprises
performing a pointer lookup operation by traversing a data structure, wherein
the traversing uses the label information; and
performing a table lookup operation to determine a queue to which to send the packet, wherein
the pipelined switch comprises a plurality of queues,
the plurality of queues comprises the queue,
the table lookup operation uses a result of the pointer lookup operation, and
the packet comprises a class of service indicator, and
the generating further comprises
performing a post-processing operation using the class of service indicator.
20. A network device comprising:
a pipelined switch;
means for receiving a packet at the pipelined switch, wherein
the packet comprises a header portion, and
the pipelined switch comprises a plurality of pipeline stages coupled to one another sequentially; and
means for processing the packet, wherein
the means for processing comprises
means for reading the header portion of the packet from the means for receiving,
means for generating a modified header portion, wherein
the means for generating comprises
means for extracting the label information from the header portion,
means for performing a lookup operation using the label information, and
means for creating the modified header portion using a result of the lookup operation, and
the at least the portion of the header portion comprises label information,
means for storing the modified header portion, and
means for outputting the packet from the pipelined switch, and
the means for outputting is configured to output the packet with the modified header portion.