ATM cell spacer

Details ATM cell spacer ATM cell spacer

1998-05-08

2002-01-29

Chin, Wellington (Department: 2664)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S389000

Reexamination Certificate

active

06343076

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to an ATM cell spacer.
A general description of this kind of facility can be found in the article by P. E. BOYER et al.: “Spacing Cells Protects and Enhances Utilization of ATM Network Links” (IEEE Network, September 1992, pages 38-49).
ATM cells are 53-byte information packets transmitted over high-speed physical links (bit rate of 155 or 622 Mbit/s). Each physical link supports a multiplex of cells belonging to various virtual connections. The virtual connection to which each cell pertains is identified by a pair of identifiers VPI-VCI contained in the header of the cell. Certain facilities differentiate between virtual connections according to the virtual path identifier (VPI), while other facilities differentiate between the virtual connections on the basis of the virtual channel identifiers (VCI), or of both identifiers VPI, VCI.
In the present description, each ATM call will be regarded as pertaining to a virtual connection identified by an identity IdCx internal to the facility provided with the spacer. This internal identity can correspond to the VPI, to the VCI, to the pair VPI-VCI, or else, more conveniently, to a specific identity individual to the facility and comprising a smaller number of bits than the VPI-VCI, so as to facilitate accesses to memory modules of reasonable size. An appropriate way of associating such identities IdCx with the ATM cells is described in French Patent Application No. 97 01222.
The ATM spacer is a unit whose main function is to regularize the bit rate of cells over the various connections supported by a physical link. In general, each source emitting on a virtual connection negotiates a peak bit rate with the operator. If this peak bit rate is not complied with by the source, there is a risk of congestions occurring in the network, and the operator is empowered to destroy cells on the connection.
In a spacer, a spacing interval T is allotted to each connection IdCx, in such a way that two consecutive cells relating to the same virtual connection are generally separated by at least the time interval T which typically corresponds to the inverse of the peak bit rate. We then speak of a real spacer. The real spacer calculates a theoretical emission time TET for each cell and then stores the cell in memory so as to emit it only at the desired time. The spacing interval T is then complied with for all the connections. In a so-called virtual spacer, a theoretical emission time TET is firstly calculated for each cell according to the same methods as before, and then the cell is stored in memory. The difference with the real spacer is that the virtual spacer emits the cells immediately in the order of the theoretical emission times. The virtual spacer does not degrade the cell delay variation (CDV). However, it does not allay the possible degradation of the bit rate by queues located upstream of the spacer.
The spacing function is frequently associated with the policing function which consists in eliminating cells transmitted in accordance with a virtual connection at a bit rate greater than the peak bit rate, when this excess bit rate is such that it is no longer possible to produce an output multiplex in which the cells pertaining to the connection are correctly spaced without the CDV exceeding a limit value depending on the quality of service negotiated with the operator. The policing function usually enters into the way of calculating the theoretical emission times TET of the cells.
A conventional way of allotting theoretical emission times to the cells and of performing the policing function is to apply the GCRA algorithm (“Generic Cell Rate Algorithm”) defined in Annex 1 of ITU-T Recommendation I.371 (see M. DE PRYCKER: “Asynchronous Transfer Mode, Solution for Broadband ISDN”, 2nd Edition, 1993, Chapter 7, paragraph 7.3.4, pages 292-293). For each virtual connection, this algorithm always satisfies the following relation: ta≦TET≦ta+&tgr;, where ta denotes the time of arrival of the cell, at which its theoretical emission time TET is calculated, and &tgr; denotes the CDV tolerance of the connection.
Cells pertaining to different virtual connections may find themselves allotted the same theoretical emission time. As a result it is necessary to provide a mechanism for resolving such conflicts.
A first solution, described in the document EP-A-0 438 009, consists in storing each incoming cell at an address of the cell memory corresponding to its actual time of emission. At the output of the spacer, a time counter serves as address pointer for designating the cells to be emitted. After assigning a theoretical emission time to the cell, the latter is stored at the first available address after this theoretical time, thereby avoiding conflicts.
A second solution, described in the document EP-A-0 498 092 (see also E. Wallmeier et al.: “The Spacing Policer, an Algorithm for Efficient Peak Bit Rate Control in ATM Networks”, Proc. of ISS'92, October 1992, Vol. 2, pages 22-26), consists in associating, with each emission period, a list of cells chained by means of pointers. When an emission period is reached, the cells of the associated list are read and output one by one during this period and during the required number of succeeding periods.
A third solution, described in the article “A Real Time Sorter with Application to ATM Traffic Control” by J. W. Roberts et al. (Proc. of ISS'95, April 1995, Vol. 1, pages 258-262), consists in utilizing a sorting technique: with the arrival of each cell, a data element made up of the cell storage address and of a sort key corresponding to its theoretical emission time is introduced into a sorting device, which at each emission period produces an element, having a minimum sort key. The cell whose address is contained in this element is emitted if the minimum key is less than or equal to the current time in the case of a real spacer, or immediately in the case of a virtual spacer. The sorting device must be capable of sorting a number N of elements equal to the maximum number of cells stored in the spacer. Moreover, it is noted that the sorting device advocated has the drawback that the number of logic circuits operating in parallel so as to perform the sorting function at a sufficient rate is proportional to N. Once the number N of elements to be sorted becomes large (a few thousand or tens of thousands as in the case of the application to an ATM cell spacer), the hardware complexity of the sorting device becomes prohibitive.
In the three solutions above, the spacer ignores the concept of virtual connection once a theoretical emission time has been allotted to an incoming cell. As a result, the procedure for determining a stored cell to be emitted is the choosing of a cell from a number corresponding to the maximum storage capacity of the spacer. This implies superfluous complexity from the moment that in principle the order of reception of the cells pertaining to one and the same virtual connection must be complied with on emission.
Should there be a risk of traffic congestion on the link equipped with the spacer, the operator sometimes has the option of increasing the spacing intervals T allotted to certain connections. However, such a modification of T acts only on the cells which have not yet been received, and not on those already written to the buffer memory of the spacer, given that the theoretical emission times calculated previously are no longer modifiable without knowing the connections concerned; yet, a sufficient number of cells may already have been written to the buffer memory for the increase in the intervals T to be ineffective in preventing congestion. The above spacers lack flexibility in this respect.
An ATM spacer, in which the selecting of the cell to be emitted is effected on the basis of the theoretical emission times assigned to the cells stored in the starts of FIFO lists allotted to the various virtual connections, is described in EP-A-0 710 046. This document describes a particular method of calculating th

Affiliated with

Also associated with

Rating

ATM cell spacer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with ATM cell spacer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and ATM cell spacer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2849710