Patent Publication Number: US-6704315-B1

Title: Method for generating ATM cells for low bit rate applications

Description:
BACKGROUND OF THE INVENTION 
     The present invention is generally concerned with telecommunication systems. 
     The present invention is more particularly concerned with telecommunication systems using ATM (Asynchronous Transfer Mode). ATM is a commonly used standard for transmission of high bit rate data in telecommunication systems, which is based on an asynchronous time multiplexing of packets of fixed length called cells. 
     Telecommunication systems using ATM may be modelized by an ATM layer and an interface layer, or ATM Adaptation Layer (AAL), between the ATM layer and users. 
     A specific ATM Adaptation Layer has been provided for low bit rate applications such as in particular mobile communication systems, especially third generation mobile communication systems (such as in particular UMTS: “Universal Mobile telecommunication System”). 
     Such a specific layer, or AAL2, is defined in ITU-T Recommendation 1.363.2. AAL2 is subdivided into a Service Specific Convergence Sublayer (SSCS) and a Common Part Sublayer (CPS) which allows several low bit rate connections to share a same ATM connection, by multiplexing several short packets called CPS packets into a same ATM cell. 
     AAL2 layer thus receives different incoming streams of low bit rate data units which, besides, may have different rates and/or lengths, in particular depending on the associated type of traffic (voice, data, images, signalling . . . etc.). Each incoming data unit stream is converted into an incoming short packet stream, by packetizing data units into short packets (or CPS packets). These different incoming short packet streams are multiplexed into a single outgoing short packet stream to be packed into a same ATM connection. 
     To be efficient, the process carried out at CPS level should simultaneously achieve a number of objectives, in particular: 
     this process should be bandwidth efficient, i.e. ATM cells should be sent with as least padding as possible, 
     this process should meet quality of service requirements, in particular it should introduce as least delay variations as possible, 
     this process should meet different quality of service requirements for the different types of traffic to be multiplexed; in particular voice traffic is time sensitive and requires stringent delay variations objectives, while data or signalling traffic are usually tolerant to transfer delay variations. 
     A special cause of delay variations is the processing of long data units (i.e. in practice of data units of length higher than 45 octets ). 
     Long data units are currently segmented prior to packetization into short packets. In this context, WO 97/48251 considers the case of two types of traffics of different priorities (i.e. voice and data traffic) and teaches to interrupt segmentation and packetisation of a long data unit (i.e. data traffic) upon the arrival of a short and more prioritary user data unit (i.e. voice traffic), in order to reduce the cell delay variations that might result of the processing of such long data units on such high priority traffic. 
     However this reference does not provide any solution in the general case of any number of incoming streams, and of any types of traffic carried by the different incoming streams; in particular it does not provide any solution to the problem of delay variations that might result, in the case of a plurality of incoming streams carrying long data units, of the processing of long data units of a given stream, on each of the other incoming streams. 
     The present invention in particular enables to avoid such drawbacks. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is therefore a method for generating ATM cells for low bit rate applications, said method including: 
     a segmentation and packetization step, for converting a plurality of incoming data unit streams into a plurality of incoming short packet streams, said step including a segmentation of long data units prior to the packetisation of data units into short packets, 
     a multiplexing and scheduling step, for multiplexing said plurality of incoming short packet streams into a single outgoing short packet stream to be packed into a same ATM connection, and for scheduling the different incoming short packet streams into said single outgoing short pocket stream, in a way that short packets corresponding to long data units of different incoming data unit streams con be interleaved in said single outgoing short pocket stream. 
     According to another object of this invention, said step of multiplexing and scheduling is further carried out in a way that short packets corresponding to long data units of different lengths and/or rates can be interleaved in said outgoing short packet stream as a function of their respective lengths and/or rates. 
     According to another object of this invention, scheduling of a given incoming short pocket stream is determined so that short pockets of this stream are spaced of T i  in said single outgoing short packet stream, where T i  is the ratio between the transmission time interval, or data unit repetition period of the corresponding incoming data unit stream, and the number of short packets after segmentation of a data unit of this incoming data unit stream. 
     According to another object of this invention, said step of multiplexing and scheduling is further carried out in a way that short packets corresponding to short data units can be inserted in said outgoing short packet stream, as a function of their respective length and/or rate. 
     According to another object of this invention, said method further includes a step of scheduling ATM cell transmission times in a way as to keep ATM cell spacing as constant as possible, and a step of packing said single outgoing short packet stream into a some ATM connection having the thus scheduled ATM cell transmission times. 
     According to another object of this invention, said ATM cell spacing is kept as close as possible to a cell rote negociated for the corresponding ATM connection. 
     Depending on the type of traffic agreement for the ATM connection, and according to various embodiments, said cell rate may be: 
     a PCR (Peak Cell Rate) in the case of service category of DBR (Deterministic Bit Rate) or CBR (Constant Bit Rate) type, 
     a BCR (Block Cell Rate) in the case of service category of ABT (ATM Block Transfer) type, 
     a ACR (Allowed Cell Rate) in the case of service category of ABR (Available Bit Rate) type. 
     According to another embodiment, said cell rate may be re-negociated, to optimise resource utilisation in the network. 
     According to another embodiment, no ATM cell is sent when there is no data available from said single outgoing short packet stream, and said method includes a further step of referencing said scheduling step with respect to the next availability of data from said single outgoing short packet stream. 
     Another object of the present invention is a device for generating ATM cells for low bit rate applications, said device including 
     segmentation and packetization means, for converting a plurality of incoming data unit streams into a plurality of incoming short packet streams, said means including means for segmenting long data units prior to packetizing data units into short packets, 
     multiplexing and scheduling means, for multiplexing said plurality of incoming short packet streams into a single outgoing short packet stream to be packed into a same ATM connection, and for scheduling the different incoming short packet streams into said single outgoing short packet stream, in a way that short packets corresponding to long data units of different incoming data unit streams can be interleaved in said single outgoing short packet stream. 
     The present invention also has for its object an entity such as a base station (or Node B in UMTS) for a mobile radiocommunication network, comprising such a device. 
     The present invention also has for its object an entity such as a base station controller (or Radio Network Controller, or RNC, in UMTS) for a mobile radiocommunication network, comprising such a device. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects of the present invention will become more apparent from the following description taken in conjunction with the accompanying drawings: 
     FIG. 1 is a diagram intended to illustrate an example of a method according to the present invention, 
     FIG. 2 is a diagram intended to illustrate an example of application of a method according to the present invention. 
    
    
     MORE DETAILED DESCRIPTION OF THE INVENTION 
     The following notations will be used hereinafter: 
     Scheduler: contains the scheduling times of each incoming short packet stream 
     GLL: Global Linked List, contains all the addresses of CPS packets competing for packing into ATM cells 
     t: current time 
     T i : spacing period between short packets of a given incoming stream n o i, in said outgoing stream 
     LVST i : current scheduling time of incoming short packet stream n o i. 
     As an example FIG. 1 illustrates one of a plurality of incoming data unit streams, noted STi, and one of the data units, noted AAL SDU, of this incoming data unit stream. 
     Conversion of each data unit stream such as STi into a short packet stream such as STi′ is performed in segmentation and packetization means noted  1 . Such a conversion includes a segmentation and a packetization of a data unit such as AAL SDU into a number of short packets, or CPS packets, such as the ones noted CPS 1  and CPS 2 . 
     Queuing of the thus obtained CPS packets is carried out using a common buffer memory CB wherein the CPS packets of the different streams such as STi′ are stored, as illustrated at  2  for stream STi′. 
     Determination of the scheduling times noted LVST of the thus queued CPS packets, into a single outgoing short packet stream obtained by multiplexing a plurality of incoming short packet streams like STi′, is performed in computation means noted  3  in FIG.  1 . 
     The address @ in the common buffer CB of a CPS packet having a thus determined scheduling time is written in that line of a scheduler noted SCH which corresponds to this time, as illustrated for example at  4  for packet CPS 1  or at  5  for packet CPS 2 . 
     According to the invention, scheduling of the different short packet incoming streams into said single outgoing short packet stream is carried out in a way that short packets corresponding to long data units of different incoming data unit streams can be interleaved in said single outgoing short packet stream. 
     In this way, delay variations that might result, in the case of a plurality of incoming streams carrying long data units, of the processing of long data units of a given stream, on each of the other incoming streams, may be reduced, and the efficiency of the process can thus be improved. 
     Besides, such a scheduling may be carried out in a way that short packets corresponding to long data units of different lengths and/or rates can be interleaved in said outgoing short packet stream as a function of their respective lengths and/or rates. 
     Besides, such a scheduling may be carried out in a way that short packets corresponding to short data units can be inserted in said outgoing short packet stream, as a function of their respective length and/or rate. 
     Let LVSTi be the scheduled time of a current CPS packet of incoming stream STi′. 
     LVSTi may be determined according to the following relation: 
     
       
         
           LVST 
           i 
           =LVST 
           i 
           +T 
           i 
         
       
     
     In other words, LVSTi may be determined so that short packets of incoming stream STi′ are spaced of T i  in said outgoing stream; T i  could be for example the ratio between the transmission time interval (or repetition period of data units) for stream STi, and the number N of CPS packets after segmentation of a data unit of stream STi. T i  may vary according to time; in other words spacing may be dynamically determined, in order to allow the capability to adjust CPS spacing rate to a new rate each time necessary. When a spacing modification occurs for a given AAL2 connection, it is effective for the newly arrived CPS packets, not for the already stored packets of this AAL2 connection. 
     Besides, to take into account the arrival time “t” of each data unit stream STi, the following algorithm may be used instead to determine scheduled times LVSTi: 
     If LVST i +T i ≦t, LVST i =t 
     If LVST i +T i &gt;t, LVST i =LVST i +T i    
     In other words, if necessary LVSTi=t may be considered as serving as a new reference for the computation of a new LVSTi according to relation LVST i =LVST i +T i  used otherwise. 
     Scheduling of incoming short packet streams according to the thus determined scheduling times is performed by sequentially reading the different lines of the scheduler SCH and selecting for each line the short packet(s) whose address(es)are stored in this line. If several short packets are to be scheduled at a given time corresponding to a same line of the scheduler, their addresses form a linked list of addresses of CPS packets having that time as scheduled time. The resulting sequence of addresses of CPS packets competing for packing into ATM cells form the global linked list noted GLL. 
     Any packing process, such as illustrated at 6, may be used for packing said single outgoing short packet stream noted ST into a same ATM connection. For example, according to a current packing process, an ATM cell can be sent when it is full for “immediate” transmission or when a timer expires (timer being reset at each departure of an ATM cell). Such a current method however has the drawback of introducing in its turn delay variations. 
     A new packing process is now disclosed, which enables in particular to avoid such delay variations. 
     The following notations will be used for the description of this new packing process: 
     T: ATM emission interval (or ATM cell rate) 
     AST: ATM Scheduling Time (or ATM cell scheduled transmission time). 
     SLI: Sum of Length Indicators (or sum of the lengths of all CPS packets of global linked list GLL) 
     Let AST be a current ATM cell scheduled transmission time. 
     At each scheduled cell transmission time AST: 
     If SLI≧47 octets (i.e. if SLI≧number of octets of an ATM cell payload), the addresses in the common buffer of the first received 47 octets are read in global linked list GLL , the common buffer CB is “emptied” from these 47 first octets, SLI is set to SLI−47, and these octets are mapped into an ATM cell (no padding in this case). 
     If SLI&lt;47 octets (with SLI=x), the addresses in the common buffer of the “x” first received octets of high priority are read in global linked list GLL, the common buffer CB is “emptied” from these “x” octets, and SLI is set to SLI=0. Then these “x” octets are mapped into the ATM cell and padding is used in this case to fill the cell. 
     An ATM cell such as for example the one noted ATM n  is currently composed of a header field noted H, a so-called STF field, and CPS packets such as CPS 1 , CPS 2  in this example. 
     Besides, at each scheduled ATM cell transmission time AST, if after this process, the global linked list GLL is empty, i.e. if no CPS packet is available for transmission in ATM cells, no new AST is scheduled, i.e. no new ATM cell is sent. Otherwise, if the global list is not empty, a new AST is scheduled. According to this new packing process, this new AST is determined in a way as to keep ATM cell spacing as constant as possible. Advantageously, AST may be computed using the following relation: 
     
       
         
           AST=AST+T 
         
       
     
     where T is the cell rate negociated for the corresponding ATM connection. 
     Ensuring compliance with the negociated cell rate constitutes a simple and efficient way of avoiding delay variations, while at the same time simplifying traffic management in the network. 
     Depending on the type of traffic agreement for the ATM connection, and according to various embodiments, cell rate may be: 
     a PCR (Peak Cell Rate) in the case of service category of DBR (Deterministic Bit Rate), or CBR (Constant Bit Rate) type 
     a BCR (Block Cell Rate) in the case of service category of ABT (ATM Block Transfer) type 
     a ACR (Allowed Cell Rate) in the case of service category of ABR (Available Bit Rate) type. 
     Besides, the following computation of a new AST may be performed in the case where a new CPS packet arrives at a time “t” where global linked list GLL is empty, i.e. in the case of a next availability of a CPS packet for transmission in ATM cells, further to a period of non availabilty: 
     if AST+T≦t, AST=t 
     if AST+T&gt;t, AST=AST+T 
     In other words, AST=t may be considered as serving as a new reference for the computation of a new AST according to relation AST=AST+T used otherwise. 
     Computation means (not shown) may be used for scheduling of AST times according to such a method. 
     FIG. 2 is a diagram intended to illustrate an example of application of the present invention, corresponding to a given example of incoming data streams. 
     FIG. 2 considers three incoming data unit streams, and shows three data units “a”, “b”, “c” received respectively for these different incoming data unit streams. 
     Besides, in this example data units “a” and “c” are assumed to be long data units (corresponding in particular to data traffic) and data unit “b” a short data unit (corresponding in particular to voice traffic). Data units “a” and “c” are therefore converted into a plurality of short packets, in this example three short packets, respectively a 1 , a 2 , a 3  and c 1 , c 2 , c 3 . Transmission time interval (or data unit repetition period) is noted Ta for data units such as “a”, and Tc for data units such as “c”. Besides, in this example Ta=Tc=2 tc. 
     In this example: 
     at time t of reception of data unit “a”, the addresses @a 1 , @a 2 , @a 3  of short packets a 1 , a 2 , a 3  are stored in that lines of scheduler SCH which correspond respectively to t+2tc, t+4tc, t+6tc, 
     at time t+tc of reception of data unit “b”, the address @b of short packet “b” is stored in that line of scheduler SCH which corresponds to t+2tc, 
     at time t+2tc of reception of data unit “c”, the addresses @c 1 , @c 2 , @c 3  of short packets c 1 , c 2 , c 3  are stored in that lines of scheduler SCH which correspond respectively to t+2tc, t+4tc, t+6tc. 
     Therefore, in this example: 
     The addresses of short packets a 1 , b, c 1  are added to global linked list at time t+2tc, 
     The addresses of short packets a 2 , c 2  are added to global linked list at time t+4tc, 
     The addresses of short packets a 3 , c 3  are added to global linked list at time t+6tc, 
     Therefore, in this example: 
     short packets a 1 , b, c 1  are scheduled at time t+2tc into the outgoing short packet stream, 
     short packets a 2 , c 2  are scheduled at time t+4tc into the outgoing short packet stream, 
     short packets a 3 , c 3  are scheduled at time t+6tc into the outgoing short packet stream. 
     A method or device for generating ATM cells for low bit rate applications according to the present invention may in particular be used in mobile communication systems, in particular 
     in a base station, or node B in UMTS, for multiplexing low bit rate traffic from a plurality of sources into a same ATM connection, for transmission to a base station controller, 
     in a base station controller, or radio network controller or RNC in UMTS, for multiplexing low bit rate traffic from a plurality of sources into a same ATM connection, for transmission to a base station