Non-blocking network

Patent metadata

Field	Value
Publication number	US-10289598-B2
Application number	US-201615096982-A
Country	US
Kind code	B2
Filing date	Apr 12, 2016
Priority date	Apr 12, 2016
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

A described embodiment of the present invention includes a network having a first, second and third plurality of routers connected to a plurality of endpoints. At least one of the first plurality of routers includes a plurality of interposers having a number of queues. The at least one of the first plurality of routers has a demultiplexer for each interposer configured to receive multiplexed data from the interposer and provide demultiplexed data on to a plurality of second queues corresponding to the first queues of the number of queues. The at least one of the first plurality of routers also includes a number multiplexers, each of the number multiplexers having inputs configured to receive data from the number of queues.

First claim

What is claimed is:

1. A circuit for routing network communications between a plurality of endpoints, comprising:
a plurality of n interposers, each interposer serving one endpoint, each interposer including:
a first demultiplexer having an input and m outputs, the input of the first demultiplexer configured to receive data from the endpoint served by the interposer;
m first queues, each first queue having an input and an output, the input of the first queue configured to receive data from respective ones of the m outputs of the first demultiplexer; and
a first multiplexer having m inputs and an output, each input of the first multiplexer configured to receive data from the output of one of the m first queues;

at least one router including n input ports, each input port of the n input ports connecting to a respective interposer the plurality of n interposers and including:
a separate second demultiplexer configured to receive data from the output of the first multiplexer of the respective one of the plurality of n interposers and including m outputs;
m second queues, each second queue having an input and an output, the input of the second queue configured to receive data from a respective one of the m first queues on a respective one of the m outputs of a respective second demultiplexer; and

the at least one router further including a plurality of m second multiplexers, each having n inputs and an output, each input of a respective m second multiplexer configured to receive data on a corresponding one of the m outputs of the m second queues of a respective input port of the n input ports of the at least one router.

2. The circuit of claim 1 wherein each of the first queues is configured to not provide output data to the first multiplexer until a credit signal is provided from a corresponding one of the m second queues indicating that space is available in the corresponding one of the m second queues to store the output data.

3. The circuit of claim 1 wherein the circuit and the endpoints are formed on a monolithic substrate.

4. The circuit of claim 1 wherein the first and second queues each include at least two storage positions.

5. The circuit of claim 1 wherein the n input ports each include a bus having one lead for each data bit.

6. The circuit of claim 5 wherein the n input ports include control signal leads.

7. A network comprising:
a plurality of n interposers, each interposer including:
a first demultiplexer having an input and m outputs, the input of the first demultiplexer connected to an endpoint;
m first queues, each first queue having an input and an output, the input of the first queue of the m first queues configured to receive data from respective ones of the m outputs of the first demultiplexer; and
a multiplexer having m inputs and an output, each input of the m inputs of the multiplexer configured to receive data from the output of one of the m first queues;

a first plurality of routers, each of the first plurality of routers having n input ports connected to an output port of one of the plurality of n interposers and having m output ports,
a second plurality of m routers having a plurality of input ports, each input port of the plurality of input ports connected to one of the m output ports of the first plurality of routers, and having a plurality of output ports; and
a third plurality of routers, each of the third plurality of routers having a plurality of input ports, one input port connected to one of the output ports of a corresponding one of the second plurality of routers, and having a plurality of output ports connected to a portion of the plurality of interposers such that each interposer is connected to at least one output of one of the third plurality of routers;
wherein at least one of the first plurality of routers comprises:
a separate second demultiplexer for each interposer, each separate second demultiplexer having an input and m outputs, the input of the second demultiplexer configured to receive data from the output of the multiplexer of a respective one of the plurality of n interposers; and
m second queues, each second queue having an input configured to receive data from a respective one of the m outputs of a respective second demultiplexer and an output configured to provide data on respective ones of the m output ports of the at least one of the first plurality of routers.

8. The network of claim 7 wherein the network has an odd number of stages greater than or equal to three, each stage including a plurality of routers, and is formed in a folded Clos-type network and each of the first plurality of routers is combined with a corresponding one of a last plurality of routers.

9. The network of claim 7 wherein each of the first queues of an interposer of the n interposers is configured to not provide output data to the multiplexer of the interposer until a credit signal is provided from a corresponding one of the m second queues indicating that space is available in the corresponding one of the m second queues to store the output data.

10. The network of claim 7 wherein:
each output port of the m output ports of the first plurality of routers includes:
a first demultiplexer having an input configured to receive data and k outputs;
k first queues, each first queue having an input configured to receive data and an output; and
a multiplexer having k inputs and an output, each input of the multiplexer configured to receive data from the output of one of the k first queues; and

each of the second plurality of routers comprises:
a second demultiplexer for each of the first plurality of routers, the second demultiplexer having an input and k outputs, the input of the second demultiplexer configured to receive data from an output port of the m output ports of one of the first plurality of routers; and
k second queues, each having an input configured to receive data from a respective one of the k outputs of the second demultiplexer and an output configured to provide data on respective ones of k output ports of the second plurality of routers.

11. The network of claim 10 wherein each of the k first queues is configured to not provide output data to the multiplexer of the output port of the first plurality of routers until a credit signal is provided from a corresponding one of the k second queues indicating that space is available in the corresponding one of the m second queues to store the output data.

12. The network of claim 7 wherein the first and second queues each include at least two storage positions.

13. The network of claim 7 wherein the input ports each include a bus having one lead for each data bit.

14. The network of claim 13 wherein the input ports include control signal leads.

15. The network of claim 11 wherein:
each of the second plurality of routers includes:
a first demultiplexer having an input configured to receive data and m outputs;
n first queues, each first queue having an input and an output, the input of the first queue configured to receive data from respective ones of the m outputs of the first demultiplexer of the router of the second plurality of routers; and
a multiplexer having n inputs and an output, each input of the multiplexer configured to receive data from an output of one of the n first queues of the router of the second plurality of routers; and

each of the third plurality of routers includes:
a second demultiplexer for each of the second plurality of routers, each second demultiplexer having an input and m outputs, the input of the second demultiplexer configured to receive data from the outpu

Assignees

• Futurewei Technologies Inc

Inventors

• Yan Peter
• Chandra Alex Elisa
• Harn YwhPyng
• Chen Xiaotao
• Gatherer Alan
• Yu Fang
• Chen Xingfeng
• Wang Zhuolei
• Zhou Yang

Classifications

• G06F13/4265 Primary

  on a point to point bus (G06F13/4247, G06F13/4282 take precedence) · CPC title

• G06F13/4045

  where the bus bridge performs an extender function · CPC title

• Y02D10/151

  Cross-Sectional Technologies · mapped topic

• G06F13/4022

  using switching circuits, e.g. switching matrix, connection or expansion network (G06F13/4009 takes precedence) · CPC title

• Y02D10/14

  Cross-Sectional Technologies · mapped topic