Patent ID: 6343076
Filing Date: 2002-01-29
Classification: H04L,H04Q

Abstract:
Spacer of ATM cells transmitted according to a plurality of virtual connections, comprising:a cell memory to which incoming cells are written and from which outgoing cells are read; means for allocating a theoretical emission time to each cell stored in the cell memory, comprising means of recursive calculation of a theoretical emission time for each cell pertaining to a virtual connection on the basis of parameters including at least a time of arrival of said cell and a spacing interval allotted to said connection; spacing control means for managing the cell memory, with the aid of an associated pointer memory, in such a way that the cell memory comprises, for each virtual connection for which said cell memory contains cells, a list of locations where said cells are stored in first-in first-out mode between a start of list and an end of list; and sorting means for ordering data elements each comprising a virtual connection identity and a sort key consisting of the theoretical time of emission of the cell contained in the start of list relating to said virtual connection, and for selecting at least one data element having a minimum sort key, the spacing control means being devised so as to command the emission of a cell contained in the start of list relating to a virtual connection identified in a data element selected by the sorting means, said sorting means includes at least one sorting device having: storage means organized according to a binary tree with 2nâˆ’1 nodes numbered from 1 to 2nâˆ’1 which are each able to contain a data element and are distributed in n successive stages numbered from 0 to nâˆ’1, stage q comprising nodes 2q to 2q+1âˆ’1, and means of control of the binary tree for dispersing the elements to be sorted within the tree in such a way as to satisfy an ordering condition according to which, for each integer i lying between 1 and 2nâˆ’1âˆ’1 such that node i contains an element to be sorted, each of the nodes 2i and 2i+1 either contains no element to be sorted, or contains an element whose sort key is greater than or equal to the sort key of the element contained in node i, wherein the means of control of the binary tree respond to commands to modify the contents of the binary tree which include commands for inserting a new element to be sorted, wherein, upon the arrival of a cell pertaining to a virtual connection for which the cell memory contains no cell, the sorting means receive a new data element comprising the identity of said virtual connection and, as sort key, the theoretical time of emission of said cell supplied by the means of recursive calculation, and wherein, upon the emission of a first cell pertaining to a virtual connection for which the cell memory comprises a list of locations further containing at least one second cell, the sorting means receive a new data element comprising the identity of said virtual connection and, as sort key, a theoretical time of emission of said second cell equal to the theoretical time of emission of said first cell plus the spacing interval allotted to said connection.