Communication switching element and method for transmitting variable length cells

Claim 2

Communication switching element having X inputs and Y outputs, wherein X and Y are not both equal to one, for transferring cells from each of said inputs to at least one of said outputs, said cells being subdivided into subcells, said switching element comprising a buffer memory with a plurality of memory locations each having an identity, means for writing into said memory locations distinct subcells incoming on said inputs, a first storage means storing memory location identities of subcells, and means for reading said subcells out of said buffer memory under the control of said first storage means and for supplying these read subcells to said outputs, wherein said stored memory location identities are linked in identity groups, each of said identity groups corresponding to one of said cells.

Claim 3

Communication switching element according to claim 1, wherein said buffer memory is fully shared between said X inputs and said Y outputs.

Claim 4

Communication switching element according to claim 1, further comprising a second storage means for storing the identities of the free memory locations available for writing said subcells therein and for providing these identities to said writing means upon a subcell having to be written in said buffer memory.

Claim 5

Communication switching element according to claim 3, wherein said free memory location identity provided by said second storage means is also supplied to the first storage means.

Claim 6

Communication switching element according to claim 3, wherein said second storage means comprises a First-In-First-Out queue memory.

Claim 7

Communication switching element according to claim 3, wherein said second storage means comprises a third memory in which the identities of said free memory locations are stored in the form of a second linked list.

Claim 8

Communication switching element according to claim 6, wherein said second linked list has an associated write pointer indicative of the first free memory location of said second linked list to be provided to said writing means, and a read pointer indicative of the last free memory location received in said third memory, said write and read pointers each comprising a distinct register able to store one identity of a memory location of said buffer memory.

Claim 9

Communication switching element according to claim 3, wherein said second storage means comprises a Find-First-One circuit.

Claim 10

Communication switching element according to claim 1, wherein it is integrated in a single electronic chip.

Claim 11

Communication switching element according to claim 1, wherein each of said cells is subdivided into a variable plurality of subcells.

Claim 12

Communication switching element according to claim 1, wherein in said subcells are of equal length.

Claim 13

Communication switching element according to claim 1, wherein each of said. identity groups, said stored memory location identities are linked in an order equal to their order in the cell.

Claim 14

Communication switching element according to claim 12, wherein all the subcells of a cell are supplied to said outputs in the same chronological order as they are applied to said inputs.

Claim 15

Communication switching element according to claim 12, wherein the last of said linked identities has an associated end-of-list indication.

Claim 16

Communication switching element according to claim 1, wherein the memory location identities of all said subcells are stored in said first storage means.

Claim 17

Communication switching element according to claim 15, wherein the memory location identities of the subcells of a cell are stored in said first storage means such that each memory location identity refers to the memory location identity of the next subcell of a same cell.

Claim 18

Communication switching element according to claim 16, wherein said first storage means comprises a first memory wherein the memory location identity of the first subcell of each cell is stored and a second memory having a number of memory locations equal to that of said buffer memory and storing for each cell a linked list of the memory locations identities of the subcells, other than the first one, of said cell, said first subcell memory location identity referring to the first identity of said linked list.

Claim 19

Communication switching element according to claim 17, wherein said first memory includes a plurality of submemories each associated with one of said outputs and wherein said memory locations identities of the first subcells are stored, said submemories providing said identities to said reading means upon a first subcell having to be read from said buffer memory.

Claim 20

Communication switching element according to claim 18, wherein each of said submemories comprises a First-In-First-Out queue memory.

Claim 21

Communication switching element according to claim 18, wherein each of said cells contains a data block and is associated with routing data indicating to which of said outputs said cell has to be transferred, and the memory location identity of the first subcell of a cell to be transferred to one of said outputs is stored, under the control of said routing data, into the one of said submemories associated with said one output.

Claim 22

Communication switching element according to claim 18, wherein each of said cells contains a data block and is associated with routing data indicating to which of said outputs said cell has to be transferred, and the memory location identity of the first subcell of a cell to be transferred to a plurality of outputs is stored, under the control of said routing data, into a corresponding plurality of submemories each associated with one output of said plurality of outputs.

Claim 23

Communication switching element according to claim 21, wherein the number of outputs of said plurality of outputs to which a cell has to be transferred is provided by said routing data and is associated to each memory location identity of said linked list in said second memory.

Claim 24

Communication switching element according to claim 22, wherein the last of said linked identities has an associated end-of-list indication, said inputs are coupled via a multiplexer circuit to a single input of said buffer memory having an output which is coupled to said outputs through a demultiplexer circuit, said demultiplexer circuit which is controlled by a second clock circuit is coupled to said outputs via respective output reception means so as to supply during a subcell time interval one subcell from said buffer memory to each of said output reception means, in each of said identity groups, said stored memory location identities are linked in an order equal to their order in the cell, the last of said linked identities has an associated end-of-list indication, for a same cell to be read-out from said buffer memory, said first memory provides during a first of said subcell time intervals the memory location identity of the first subcell of said cell to said reading means, and said second memory provides during each immediately following of said subcell time intervals one memory location identity of the other subcells of said cell in the order indicated by said linked list until said end-of-list indication is detected, and when a memory location identity of a subcell is provided to said reading means by said second memory, said associated number of outputs is decreased by one.

Claim 25

Communication switching element according to claim 23, further comprising a second storage means for storing the identities of the free memory locations available for writing said subcells therein and for providing these identities to said writing means upon a subcell having to be written in said buffer memory, wherein, if, after being decreased by one, said number of outputs is equal to zero, the associated memory location identity is provided to said second storage means as a free memory location identity.

Claim 26

Communication switching element according to claim 17, wherein said first memory includes a plurality of submemories grouped in submemory groups, each of said submemory groups being associated with a corresponding group of said outputs.

Claim 27

Communication switching element according to claim 25, wherein each of said cells contains a data block and is associated with routing data indicating to which of said outputs said cell has to be transferred, and under the control of said routing data, said memory location identity of the first subcell of a cell is stored in a randomly selected one of said submemories forming part of said submemory group associated with said group of outputs to which said first subcell has to be transferred.

Claim 28

Communication switching element according to claim 17, wherein each subcell contains a subcell header in order to distinguish said first subcell of a cell from other subcells.

Claim 29

Communication switching element according to claim 27, wherein the last of said linked identities has an associated end-of-list indication, and said subcell header of the last subcell of a cell is different from the subcell headers of other subcells.

Claim 30

Communication switching element according to claim 17, wherein it includes a subcell logic able to detect a succession of a subcell pertaining to a cell and a subcell not pertaining to any cell in order to recognize said subcell pertaining to a cell as the last subcell of said cell.

Claim 31

Communication switching element according to claim 17, wherein it includes a subcell logic able to detect a succession of a subcell pertaining to a first cell and of a first subcell pertaining to a second cell without any other intervening subcells to identify said subcell pertaining to said first cell as the last subcell of said first cell.

Claim 32

Communication switching element according to claim 17, further comprising a second storage means for storing the identities of the free memory locations available for writing said subcells therein and for providing these identities to said writing means upon a subcell having to be written in said buffer memory, wherein said first memory also provides said memory location identities of said first subcells to said second storage means as free memory location identities upon the corresponding first subcells are read from said buffer memory.

Claim 33

Communication switching element according to claim 1, wherein said inputs are coupled via a multiplexer circuit to a single input of said buffer memory having an output which is coupled to said outputs through a demultiplexer circuit.

Claim 34

Communication switching element according to claim 32, wherein said inputs are coupled via respective input reception means to said multiplexer circuit which is controlled by a first clock circuit so as to supply to said buffer memory during a subcell time interval one subcell from each of said input reception means.

Claim 35

Communication switching element according to claim 32, wherein said demultiplexer circuit which is controlled by a second clock circuit is coupled to said outputs via respective output reception means so as to supply during a subcell time interval one subcell from said buffer memory to each of said output reception means.

Claim 36

Communication switching element according to claim 34, wherein said inputs are coupled via respective input reception means to said multiplexer circuit which is controlled by a first clock circuit so as to supply to said buffer memory during a subcell time interval one subcell from each of said input reception means, and X write- in operations and Y read- out operations are performed on said buffer memory during a single one of said subcell time intervals.

Claim 37

Communication switching element according to claim 34, wherein in each of said identity groups, said stored memory location identities are linked in an order equal to their order in the cell, the last of said linked identities has an associated end-of-list indication, and for a same cell to be read- out from said buffer memory, said first memory provides during a first of said subcell time intervals the memory location identity of the first subcell of said cell to said reading means, and said second memory provides during each immediately following of said subcell time intervals one memory location identity of the other subcells of said cell in the order indicated by said linked list until said end-of-list indication is detected.

Claim 38

Communication switching element according to claim 1, wherein each of said cells contains a data block and is associated with routing data indicating to which of said outputs said cell has to be transferred.

Claim 39

Communication switching element according to claim 37, wherein under the control of said routing data, all the cells which have to be transferred to a same output are supplied to this output in the same order as they are incoming in said switching element.

Claim 40

Communication switching element according to claim 37, wherein each of said cells further contains a control header of which part contains said routing data.

Claim 41

Communication switching element according to claim 39, wherein said control header forms part of the first subcell of each cell.

Claim 42

Communication switching element according to claim 1, further comprising a subcell logic for detecting a succession in either order of a subcell pertaining to a cell and of a subcell not pertaining to any cell so as to recognize said subcell pertaining to a cell as the last/first subcell of said cell.

Claim 43

Communication switching element according to claim 1, further comprising a subcell logic for detecting a succession in either order of a subcell pertaining to a first cell and of a subcell pertaining to a second cell without any other intervening subcells so as to recognize said subcell pertaining to said first cell as the last/first subcell of said first cell.

Claim 44

Communication switching element having X inputs and Y outputs and wherein X and Y are not both equal to one, for transferring cells from each of said inputs to at least one of said outputs, said cells being subdivided into subcells and said switching element comprising a buffer memory with a plurality of memory locations each having an identity, means for writing into said memory locations distinct subcells incoming on said inputs, means for reading said subcells out of said buffer memory and for supplying these read subcells to said outputs, and a buffer memory management means for controlling said writing means and said reading means, wherein said buffer memory is fully shared between said X inputs and said Y outputs, and under the control of said buffer memory management means, said writing means write said subcells in any free ones of said memory locations of said buffer memory and said reading means rebuild each cell in function of the identities of said memory locations into which the subcells pertaining to said cell are written.

Claim 45

Communication switching element having X inputs and Y outputs and wherein X and Y are not both equal to one, for transferring cells from each of said inputs to at least one of said outputs, said cells being subdivided into subcells and said switching element comprising a buffer memory with a plurality of memory locations each having an identity, means for writing into said memory locations distinct subcells incoming on said inputs, means for reading said subcells out of said buffer memory and for supplying these read subcells to said outputs, and a buffer memory management means for controlling said writing means and said reading means, wherein said buffer memory is fully shared between said X inputs and said Y outputs, and under the control of said buffer memory management means, said writing means write said subcells in any free ones of said memory locations of said buffer memory and said reading means rebuild each cell in function of the identities of said memory locations into which the subcells pertaining to said cell are written.

Claim 46

Communication switching element according to claim 43, wherein X and Y are not both equal to one, for transferring cells from each of said inputs to at least one of said outputs, said cells being subdivided into subcells and said switching element including a buffer memory with a plurality of memory locations each having an identity, means for writing into said memory locations distinct subcells incoming on said inputs, a storage means storing memory location identities of subcells, and means for reading said subcells out of said buffer memory under the control of said storage means and for supplying these read subcells to said outputs, wherein said stored memory location identities are linked in identity groups, each of said identity groups corresponding to one of said cells, and said buffer memory management means includes said storage means.

Claim 47

Method for transmitting variable length communication messages using cells divided into subcells, each of said subcells containing a subcell header, comprising the steps: using the subcell headers to distinguish subcells pertaining to a cell from subcells not pertaining to any cell, recognizing a subcell pertaining to a cell that follows a subcell not pertaining to any cell as a first subcell of a variable length message, and p1 recognizing a subcell pertaining to a cell that is followed by a subcell not pertaining to any cell as a last subcell of a variable length message.

Claim 48

Method for transmitting variable length communication messages using cells divided into subcells, each of said subcells containing a subcell header, comprising the steps: using the subcell headers to distinguish subcells pertaining to a cell from subcells not pertaining to any cell, recognizing a subcell pertaining to a cell that follows a subcell not pertaining to any cell as a first subcell of a variable length message, and p1 recognizing a subcell pertaining to a cell that is followed by a subcell not pertaining to any cell as a last subcell of a variable length message.

Claim 49

Method for transmitting variable length communication messages using cells divided into subcells, each of said subcells containing a subcell header, comprising the steps: using the subcell headers to distinguish subcells pertaining to one of said cells from subcells pertaining to another of said cells, recognizing a subcell distinguished by its subcell header as pertaining to said one cell that follows a subcell distinguished by its subcell header as pertaining to said another cell without any other intervening subcells as the first subcell of said one cell, and recognizing a subcell distinguished by its subcell header as pertaining to said one cell that is followed by a subcell distinguished by its subcell header as pertaining to said another cell without any other intervening subcells as the last subcell of said another cell.

Claim 50

Method for transmitting variable length communication messages using cells divided into subcells, each of said subcells containing a subcell header, comprising the steps: using the subcell headers to distinguish subcells pertaining to one of said cells from subcells pertaining to another of said cells, recognizing a subcell distinguished by its subcell header as pertaining to said one cell that follows a subcell distinguished by its subcell header as pertaining to said another cell without any other intervening subcells as the first subcell of said one cell, and recognizing a subcell distinguished by its subcell header as pertaining to said one cell that is followed by a subcell distinguished by its subcell header as pertaining to said another cell without any other intervening subcells as the last subcell of said another cell.