Scalable switch fabric cell reordering

Patent metadata

Field	Value
Publication number	US-10164906-B1
Application number	US-201514871669-A
Country	US
Kind code	B1
Filing date	Sep 30, 2015
Priority date	Sep 30, 2015
Publication date	Dec 25, 2018
Grant date	Dec 25, 2018

Abstract

In some examples, a switching system includes a plurality of fabric endpoints and a multi-stage switching fabric. A fabric endpoint of the system is configured to receive, via the switch fabric, a plurality of cell streams, wherein each cell of a cell stream of the plurality of cell stream is associated with a sequence number that defines a correct ordering of cells of the cell stream; assign subsequences of each cell stream of the plurality of cell streams to respective reorder engines of the fabric endpoint; concurrently reorder the assigned respective subsequences to produce respective ordered subsequences for the subsequences, wherein the ordered subsequences are ordered according to the correct ordering of the corresponding cell stream; interleave the respective ordered subsequences for each cell stream to produce reordered cell streams each having correctly ordered cells; and process each reordered cell stream according to the corresponding correct ordering of cells.

First claim

What is claimed is:

1. A method of reordering cells switched by a multi-stage switch fabric having a plurality of stages to switch cells between any of a plurality of fabric endpoints, the method comprising:
receiving, by a fabric endpoint of the plurality of fabric endpoints and via the switch fabric, a plurality of cell streams, wherein each cell of a cell stream of the plurality of cell streams is associated with a sequence number that defines a correct ordering of cells of the cell stream;
assigning, by the fabric endpoint, different subsequences of each cell stream of the plurality of cell streams to different, respective reorder engines of the fabric endpoint;
concurrently reordering, by the reorder engines, the assigned respective subsequences to produce respective ordered subsequences for the subsequences, wherein the ordered subsequences are ordered according to the correct ordering of the corresponding cell stream;
interleaving, by the fabric endpoint, the respective ordered subsequences for each cell stream to produce reordered cell streams each having correctly ordered cells; and
processing, by the fabric endpoint, each reordered cell stream according to the corresponding correct ordering of cells.

2. The method of claim 1 ,
wherein each reorder engine of the reorder engines is associated with a set of queues, each queue of the set of queues for a reorder engine corresponding to a different cell stream of the plurality of cell streams,
wherein the reorder engines are associated with reorder ready vectors, wherein a reorder ready vector associated with a reorder engine includes respective values for the set of queues associated with the reorder engine, each value for a queue indicating whether the next expected cell for the cell stream corresponding to the queue is reordered and ready for processing,
wherein interleaving the ordered subsequences comprises reading, by the fabric endpoint, the reorder ready vectors to determine whether a next expected cell for a cell stream is reordered and ready for processing.

3. The method of claim 2 , further comprising:
storing, by the fabric endpoint, a sequence number for the next expected cell for a cell stream of the plurality of cell streams according to the correct ordering for the cell stream; and
determining, by the fabric endpoint based on the sequence number, a reorder engine of the reorder engines assigned the subsequence that includes the next expected cell, wherein interleaving the ordered subsequences comprises determining, by the fabric endpoint based on the reorder ready vector associated with the reorder engine and a value of the reorder ready vector for a queue corresponding to the cell stream, the next expected cell for the cell stream has been reordered by the reorder engine.

4. A method of reordering data units switched by a multi-stage switch fabric having a plurality of stages to switch data units between any of a plurality of fabric endpoints, the method comprising:
sending, by a first fabric endpoint of the plurality of fabric endpoints to a second fabric endpoint of the plurality of fabric endpoints and via the switch fabric, a plurality of data units in a first order;
receiving, by the second fabric endpoint, the plurality of data units in a second order, the second order different than the first order;
separately reordering, by the second fabric endpoint, a plurality of subsequences of the plurality of data units, each subsequence of the plurality of subsequences including a different subsequence of the data units according to the second order, to produce respective ordered subsequences each ordered according to the first order; and
interleaving, by the second fabric endpoint, the ordered subsequences to process the plurality of data units in the first order.

5. The method of claim 4 , further comprising:
assigning, by the second fabric endpoint, every Nth data unit of the data units in the first order to a subsequence of the plurality of subsequences, wherein N is a number of the plurality of subsequences,
wherein separately reordering the plurality of subsequences comprises ordering, by the second fabric endpoint, the subsequence assigned every Nth data unit of the data units to produce the ordered subsequence corresponding to the sequence and ordered according to the first order.

6. The method of claim 4 , further comprising:
assigning, by the second fabric endpoint, the plurality of subsequences to respective reorder engines of the second fabric endpoint,
wherein separately reordering the plurality of subsequences comprises concurrently reordering, by the reorder engines, the subsequences assigned to the reorder engines to produce respective ordered subsequences each ordered according to the first order.

7. The method of claim 6 , wherein interleaving the ordered subsequences comprises determining, by the second fabric endpoint, that a next expected data unit in a subsequence of the plurality of subsequences has been reordered by a reorder engine of the reorder engines assigned the subsequence, the method further comprising:
processing, by the second fabric endpoint in response IQ the determining, the next expected data unit in the subsequence prior to processing any other unprocessed data unit of the plurality of data units.

8. The method of claim 6 ,
wherein the plurality of data units comprise respective sequence numbers that indicate the first order, and
wherein interleaving the ordered subsequences comprises:
storing, by the second fabric endpoint, a next expected sequence number according to the first order; and
determining, by the second fabric endpoint based on the next expected sequence number, a reorder engine of the reorder engines assigned the subsequence that includes a next expected data unit comprising a sequence number matching the next expected sequence number, the method further comprising:
processing, by the second fabric endpoint in response to determining the next expected data unit has been reordered by the reorder engine, the next expected data unit in the subsequence.

9. The method of claim 6 , further comprising:
determining, by the second fabric endpoint, a second data unit of the plurality of data units has been received by a second reorder engine of the reorder engines assigned the second data unit and a first data unit of the plurality of data units has not been received by a first reorder engine of the reorder engines assigned the first data unit, the second data unit subsequent to the first data unit according to the first order;
issuing, by the second fabric endpoint in response to determining the second data unit has been received by the second reorder engine and the first data has not been received by the first reorder engine, a timeout trigger to the first reorder engine to cause the first reorder engine to wait a pre-defined timeout time to receive the first data unit before directing the second fabric endpoint to skip the first data unit.

10. The method of claim 9 ,
wherein the plurality of data units comprise respective sequence numbers that indicate the first order, and
wherein the timeout trigger comprises a sequence number for the first data unit, the method further comprising:
waiting, by the first reorder engine in response to comparing the sequence number of the timeout trigger to data units received by the first reorder engine, the pre-defined timeout time only if the first reorder engine has not received the first data unit when the first reorder engine receives the timeout trigger.

11. The method of claim 4 ,
wherein the plurality of data units comprises a first plurality of data units,
wherein the plurality of subsequences comprises a

Assignees

• Juniper Networks Inc

Inventors

• Ramanujam Rohit Sunkam
• Goel Deepak
• Thomas Sarin
• Pandey Sudhir
• Basu Arghajit

Classifications

• H04L49/1515 Primary

  Non-blocking multistage, e.g. Clos · CPC title

• H04L49/90

  Buffering arrangements · CPC title

• H04L49/30

  Peripheral units, e.g. input or output ports · CPC title

• H04L47/18

  End to end · CPC title

• H04L49/1523 Primary

  Parallel switch fabric planes · CPC title