Communication switching element and method for transmitting variable length cells

• US 5,214,639 A
• Filed: 08/09/1990
• Issued: 05/25/1993
• Est. Priority Date: 08/09/1989
• Status: Expired due to Term

• Current Assignee: Alcatel NV (Nokia Corporation)
• Original Assignee: Alcatel NV (Nokia Corporation)
• Inventors: Herion, Michel A. R.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Chin, Wellington
• Application Number:
  US07/565,310
• Time in Patent Office: 1,020 Days
• Field of Search: 370/94.1, 370/94.2, 370/94.3, 370/60, 370/60.1, 370/58.1, 370/58.2, 370/58.3
• US Class Current: 370/412
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 49/108 using shared central buffer
• CPC Class Codes: H04L 49/608 ATM switches adapted to switch variable length packets, e.g. IP packets

Abstract

The switching element is used for transferring, between X inputs (I1-IX) and Y outputs (O1-OY), cells divided into subcells of which only the first contains information about the destination output(s) of the cell. This switching element includes: a buffer memory (BM) with a plurality (C) of memory locations each having an address (K); and a memory management means (BMMU) for providing (FMLMC) addresses of free memory locations for storing the subcells therein, and for storing (BQ1-BQY, SLM), under the form of linked lists, the memory location addresses used by the subcells, each list being associated to a distinct cell. The method is adapted to process variable length cells divided into subcells each containing a header (SCH) to distinguish a first/last subcell (FSC/LSC) of a cell from other subcells (ISC, LSC). Use is made of a subcell logic (SL) to detect the succession in either order of a subcell pertaining to a cell and of either a first/last subcell (FSC/LSC) of another cell or an idle subcell so as to identify the last/first subcell (LSC/FSC) of a cell.

Claims

1. 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.

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

3. 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.

4. 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.

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

6. 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.

7. 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.

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

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

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

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

12. 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.

13. 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.

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

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

16. 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.

17. 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.

18. 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.

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

20. 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.

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 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

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 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.

31. 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.

32. 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.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

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

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

41. 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.

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 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.

43. 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.

44. 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.

45. 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.

46. 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.