Traffic Scheduling Method, System and Article of Manufacture for a Wireless Access to an Asynchronous Transfer Mode Network

1. Field of the Invention

The invention relates to data communication systems and methods of operation. More particularly, the invention relates to a delay-oriented traffic scheduling method for the control of such communication between an Asynchronous Transfer Mode (ATM) network and a synchronous transfer mode network.

2. Background Art

Recently, ATM and wireless technologies have gained a high visibility as they provide efficient and economical answers to requirements raised by new telecommunication services and by new end-user behaviours.

ATM has been recognised as the common base on which different types of services and network can operate. ATM technology can efficiently combine the transmission of speech, video, hi-fi sound (what is commonly called the multimedia traffic) and computer data into the wired network. Furthermore, ATM has proven to scale well from very high speed network infrastructure (the information highways) to customer premises networks. One of the great advantages of the ATM technology is the fact that it can guarantee some level of service when an ATM connection is set up. Such guarantees can correspond to transmission rate, transmission latency and information loss. Guarantees can be achieved mainly because the ATM architecture assumes that the transmission media are almost error free.

Wireless technology is currently becoming more and more successful as it allows mobile end-users to remain connected to their network and applications while being freed from a wired attachment. Different approaches are currently proposed for wireless communications: they differentiate by the services and the coverage they provide. Wireless Wide Area Networks (WAN) like the so-called Global System For Mobile Communications (GSM) provide nation-wide coverage to the end-user, with modem equivalent transmission speeds. Wireless Data Packet networks provide nation-wide coverage to the end-user, with the Cellular Digital Packet Data (CDPD) transmission services. Finally, Wireless Local Area Networks (LAN) provide establishments wide coverage with conventional LAN (e.g. Ethernet) equivalent communication services.

By marrying these two technologies, wireless ATM networks provide ATM benefits to users working with portable terminals, supporting multimedia applications for mobile users.

But the wireless and ATM technologies significantly differ on several important transmission characteristics:

the wireless channel is a low quality channel in the sense that the typical Bit Error Rate (BER) falls in the range 10.sup.-3 -10.sup.-5, whereas the wired ATM transmission media provide a BER in the range of 10.sup.-9,

the nature of the electromagnetic waves is such that any receiver within range of a transmitter beam can get enough energy to receive information sent by the transmitter. Thus, the wireless channel topology must be seen as point-to-multipoint. On the contrary, the wired ATM links have a point-to-point topology,

the only technically and economically viable approach with a wireless channel is to use it in half-duplex mode whereas full-duplex transmissions are commonly used on wired ATM networks.

Some known techniques are intended to fill the gap between the wireless and ATM technologies.

A first solution based on high speed point-to-point radio links may meet the requirements of a Wireless ATM network in term of channel capacity, but cannot provide a satisfying answer to other needs. The main limitation is the point-to-point topology preventing wireless end-users to be mobile. In addition, the scheduling policies commonly used on such radio links have not been built to meet the Quality of Service (QoS) requirements of ATM connections.

A solution based on the conventional wireless LAN technique is to some extent in line with some requirements of a wireless access to an ATM network without addressing all of them. Such a solution disclosed in patent publication EP 709 982 is directed to a Medium Access Control (MAC) protocol for wireless access of a plurality of remote stations on a LAN. This system gives a solution to the support of conventional LAN traffic, but cannot guarantee all the QoS requirements imposed by any type of ATM traffic. In addition to this limitation, the design point of traditional wireless LAN products is optimised for conventional LAN traffic (based on large packets: 1.5 Kbytes or more) and therefore presents very poor efficiency figures if packets are replaced by ATM cells.

The best solution is described in the European patent application 96 480047.8 which relates to a MAC protocol for wireless radio frequency access for a plurality of ATM mobile terminals to an ATM access point. This protocol is based on a time division structure in which time is slotted, and time slots are grouped into variable length time frames consisting of downlink time slots and uplink time slots. The variable length time frames consists of three periods (DOWN, UP.sub.-- RESERVED, UP.sub.-- CONTENTION). The first period, the DOWN period, is the downlink channel which is used exclusively for data transfer from the Access Point to the Mobile Terminals. The following period, the UP.sub.-- RESERVED period, is the uplink channel that is used for contention-free data transfer from the Mobile Terminals to the Access Point. The allocation of the time slots in the DOWN and UP.sub.-- RESERVED periods is performed by the Access Point, and depends on the service class and QoS parameters of each established ATM connection between the Mobile Terminals and any ATM station according to different priority levels derived from the ATM contract parameters. But, such a system does not take into account the cell delay tolerance depending on the arrival time of the cells. In other words, this system takes only the priority to each connection into account based on its service class, but not the delay constraints of the individual connections in the order of slot allocation per connection.

A primary object of the invention is a delay-oriented scheduling method overcoming the deficiencies of prior systems by using the arrival time of the data cells for determining a deadline of each cell before which the cell has to be transmitted in order to meet a required quality of service.

Accordingly, in a digital communication system comprising a first network based on an asynchronous transfer mode and comprising at least one asynchronous terminal, a second network based on a synchronous transfer mode and comprising a plurality of synchronous terminals and at least a base station having a transceiver for carrying out the exchange of data cells consistently communicating data from the asynchronous terminal to at least one of the plurality of synchronous terminals and data cells from one of the plurality of synchronous terminals to at least one asynchronous terminal, the base station defining a sequence of time frames during which data is exchanged, with each time frame being divided into a down period for contention-free downlink transmission, an up period for contention-free uplink transmission and a contention period for contention-based uplink transmission, a method for scheduling the contents of each time frame, comprising the steps of:

a) allocating slots to the data cells to be exchanged during a connection between one of the synchronous and one of the asynchronous terminals, with said slots being the closest possible in time of a deadline for the connection determined as being the time after which the required quality of service of the connection is not met,

b) building the down period by using the cell trains which have been formed for each connection during step a),

c) building the up period by using the cell trains which have been formed for each connection during step a), and

d) providing a predetermined number of time slots for the contention period .

FIG. 1 is a block diagram of a system wherein the scheduling method of the invention is implemented.

FIG. 2 is a diagram of the time frame used to implement the scheduling method of the invention.

FIG. 3 is a diagram of a sequence of cell trains which are transmitted on a wireless network.

FIG. 4 is a flow chart representing all the possible sub-steps of STEP A implemented in the scheduling method of the invention.

FIG. 5 to FIG. 9 are diagrams schematically representing the implementation of the scheduling method according to the invention for each of the sub-steps of STEP A.

FIG. 10 is a diagram schematically representing the implementation of the scheduling method according to the invention in STEP B.

FIG. 11 is a diagram schematically representing the implementation of the scheduling method according to the invention in STEP C.

Referring to FIG. 1, a wireless network is shown allowing communication between a plurality of Terminals 10, 12, 14, 16 and applications hosted by ATM Terminals such as Terminal 18 belonging to the ATM network 20. A computing system including an ATM Switch 22 or equivalent equipment and the attached monitor station 24 is connected to the ATM network through a conventional ATM link 26, and to Access Points (AP) 28 and 30 through conventional ATM links 32 and 34. These Access Points are featured according to the invention with radio system management functions which coordinate the Terminals access to the shared radio channel.

Each access point 28 or 30 which may be a conventional ATM concentrator or a microcomputer, includes a transceiver provided with an antenna 36 or 38 by which a radio link is established with Terminals 10, 12, 14 or 16.

Terminals 10, 12, 14 or 16 are any type of conventional computer provided also with a transceiver and its antenna 40, 42, 44 or 46 respectively. These terminals are generally Mobile Terminals (MT) like Terminals 10, 12, 16, but also concentrator points like Terminal 14 interfacing with another ATM network 48.

The time frame

The protocol used in the present invention is built around the concept of MAC Time Frame (TF) as disclosed in European patent application 96 480047.8.

As the architecture of the system described in FIG. 1 is unbalanced between MTs and APs, the latter are central points for all wireless communications coming from or ending to MTs, it is thus advantageous to operate the MAC protocol in a hierarchical mode where an AP is a master station and a MT a slave. This mastery is evidenced in the task given to the AP to schedule all traffic flowing on the air, and allocate bandwidth dynamically. The efficient performance of the latter requires knowledge of the real-time needs of all (uplink and downlink) connections. Downlink needs are immediately derived from the arriving downlink ATM cells, while uplink needs are either expressed through reservation requests that are piggybacked in the MAC Protocol Data Units (MPDU) or derived from ATM service and QoS parameters. This technique offers the advantage of avoiding collisions, when accessing the wireless communication medium. To deal with the part of traffic that cannot be anticipated by the AP, a contention-based method must be nevertheless considered. As it suffers from limited channel efficiency (due to collision resolution schemes), the protocol limits the use of the contention-based method to the strict minimum. Regarding the downlink traffic, contention can be avoided as the scheduling responsibility is tied to the AP. For the uplink traffic, contention is only used to issue reservation requests in order to receive (in a subsequent TF) some reserved bandwidth, or to transmit control information.

Although it is not part of the present invention, it is necessary to recall that the time frame shown in FIG. 2 starts with a Frame Header (FH) and is composed of three periods of a variable length depending on the instantaneous traffic to be carried out on the wireless channel. For the two periods operating in reservation mode, down and up periods, it is possible that they are empty when no traffic is present. For the third period or contention period, a minimum size is kept to allow any new MT to signal its presence by sending a dedicated control packet. The TF is always beginning with the Frame Header (FH) period which is used to broadcast, from the AP to the MTs, a descriptor of the current TF. As the size of the TF and of its periods can evolve from one TF to the next one, it is necessary that each MT can learn when each period begins and how long it lasts.

Each TF period is split into a variable number of Time Slots (TS) corresponding to the smallest time granularity. The physical layer overload of the wireless medium is considerably larger than that of wired media. Hence, efficient data transmission can only be achieved if the length of transmitted data packets is not too small. On the other hand, the high BER, characterising the wireless media ask for not-too-large data packets to keep the packet error rate below maximum acceptable values. In the ATM world, the information granularity corresponds to an ATM cell which is 53 bytes long. The protocol defines the concept of "cell train" which is a sequence of ATM cells sent as the payload of a MDPU. As illustrated in FIG. 3, each MPDU is constituted by a MPDU header, followed by a MPDU payload containing ATM cells generated by the same MT/AP. In terms of duration, the time required by the physical layer to initiate a MPDU transmission (referred to as physical header) plus the time needed to send the MPDU header is equal to the transmission time of a single ATM cell. This allows the definition of the time slot size that guarantees high protocol efficiency, whatever the size of a MPDU is. In other words, the size of the time slot has been chosen equal to the time required to transmit a single ATM cell. It is therefore possible to follow the TS-based timing structure, whatever the number of transmitted cells contained in a MPDU. For example, in FIG. 3, the cell train includes 4 MPDUs. The first MPDU 50 comprises 3 time slots, the second MPDU 52 comprises 4 time slots, the third MPDU 54 comprises 2 time slots and the fourth MPDU 56 only comprises 1 time slot, each MPDU being preceded by its header H.

The scheduler

This entity which is a program located in the transceiver, is responsible for scheduling the traffic transmitted trough the wireless medium. In other words, it is the component that decides on the time at which a cell will be given to the MPDU handler for the next transmission time period. The information on the assignment of all time slots, together with the relative size of the three periods of the TF, form the slot map. This piece of information is shared with all MTs, as it is broadcast within the FH control MPDU at the beginning of each TF. By recording which time slots are allocated to them, each MT is able to determine when it is allowed to either receive or transmit during the TF. This approach enables therefore efficient power saving capabilities as each MT has the opportunity to enter into some sleeping mode when no traffic is scheduled for it.

There are two kinds of schedulers: a master scheduler 29, which runs in the APs, and a slave scheduler 13 which runs in the MTs. The master scheduler compiles various information, such as the service class and traffic and Quality of Service (Qos) parameters of active ATM connections, and the amount of outstanding traffic, to determine how the TSs of each TF are allocated to the associated MTs. (i.e., it builds the corresponding slot map). With this scheme, a MT is allowed to further identify which part of its outstanding traffic will be sent during the up period. This process is performed by the slave scheduler. In this way, protocol efficiency is optimised since each MT sends, within the TSs allocated to it, the part of its traffic that must be serviced first.

Before the beginning of each frame, the master scheduler must determine the MT that each TS will be allocated to, and formulate the slot map, according to short term requests, traffic characteristics, and QoS agreements. As already mentioned, uplink requests may be piggybacked into the data MPDUs, while downlink requests are immediately derived by the ATM cells arriving in the AP. Since both uplink and downlink share the same radio channel and traffic is usually unbalanced, a single slot allocation mechanism should be used, handling both directions equally. The only thing that differentiates the two directions is that all downlink allocations are performed before all uplink allocations according to the time frame structure.

The scheduler gives a priority to each connection based on its service class. The greater the priority number, the greater the priority of a connection. Additionally, a token pool is introduced for each connection, located at the AP. Tokens are generated at a fixed rate equal to the mean cell rate, and the size of the pool is equal to the "burstiness" of the connection. For every slot allocated to a connection a token is removed from the corresponding pool.

Starting from priority 5 Constant Bit Rate (CBR), and down to priority 2 Available Bit Rate (ABR), the scheduler satisfies requests of the connections of each service class (CBR, rt-VBR or real time Variable Bit Rate, nrt-VBR or non real time Variable Bit Rate and ABR), as long as tokens are available. Unspecified Bit Rate (UBR) connections have no guaranteed bandwidth, thus no token pools are maintained for them. For connections whose traffic can be anticipated by the scheduler, such as CBR, there is no need for transmission of requests from the MT. Therefore, for such connections, the MT does not transmit requests and the scheduler allocates slots to such connections on the basis of anticipated (in other words, the scheduler "generates" imaginary requests for the MT). For the purposes of describing the operation of the scheduler, real and imaginary requests on the uplink, as well as cell arrivals for the downlink will be referred to and treated as "requests".

At every priority class, it is very probable to have more than one connection requesting slots. In that case, the scheduler gradually allocates one slot at a time to the connection (or connections) with the most tokens (i.e., highest token variable), decreasing the token variable by one. The rationale is that the connection with the most tokens has consumed less bandwidth than declared, and thus, has higher priority for getting slots allocated. When the satisfaction of "conforming" requests is completed, and if there are still available slots, the scheduler tries to satisfy "exceeding" requests. At this state, the token variables of all connections requesting slots are less than or equal to zero. The scheduler follows the same procedure as before, starting from priority 5 (CBR), down to priority 1 (UBR). If more than one connection belonging to the same priority class request slots, one slot at a time is allocated to the connection with the highest token variable. Since this is excess traffic, decreasing will result in negative values for the token variables. The procedure stops when all requests are satisfied or all available slots are allocated.

What is not specified with the above algorithm is the exact order of allocation of TSs per MT. To do that, the scheduler should consider the traffic and QoS characteristics of the connections. An arbitrary order of allocation, in accordance with some properties of the protocol, such as cell train construction and uplink/downlink separation, can alter the traffic pattern of a connection. This may result in violation of contractual values of QoS and traffic characteristics, such as Peak Cell Rate (PCR), Cell Delay Tolerance (CDT), and Cell Delay Variation Tolerance (CDVT), and cause discarding of ATM cells deeper in the network, or late arrival at the receiver.

The scheduling algorithm

Cell Delay Tolerance (CDT) values for both the uplink and downlink can only be controlled by a delay-oriented scheduling algorithm that takes into account delay constraints of the individual connections in the order of allocation of slots per connection.

Scheduling in the radio interface should enforce the wireless hop CDT of each connection and allocate slots so that the fraction of ATM cells whose delay exceeds this CDT is minimized. Wireless hop CDT can be evaluated by disassembling end-to-end CDT into CDT for each hop of the ATM connection path. The implementation of a delay-oriented scheduling method requires knowledge of the arrival time of ATM cells in the output queues of the APs and MTs. Due to the location of the master scheduler, the arrival time of downlink ATM cells can be logged and used in the scheduling algorithm. But this is not the case for the uplink ATM cells. Uplink requests are either piggybacked in the data or control MPDUs, or generated by the scheduler (for example for CBR connections). In this way, the exact creation time of the corresponding ATM cells is not specified. Thus, this time should be estimated. For piggybacked requests, if M.sub.i.sup.T is the i-th transmitted MPDU of connection C.sub.n, it is assumed that requests in M.sub.i.sup.n correspond to cells created in the interval , [M.sub.i-1.sub.n, M.sub.i.sup.n ]. Then, a worst case estimation for the creation time of these cells is M.sub.i-1.sup.n. The estimated deadline, i.e. the latest time up to which these cells should be transmitted is W.sub.n time units after M.sub.i-1.sup.n, where W.sub.n is the wireless hop CDT for connection C.sub.n.

It must be noted that, for generated requests, their number, arrival time and deadline time are derived from the cell rate and from the last regularly scheduled cell.

From the above, it is clear that the deadline is not an absolute threshold but rather an indication of how quickly an ATM cell should be scheduled for transmission. The scheduler should try to schedule ATM cells before their deadline, but if that is not possible, some maximum extra delay may be allowed.

Construction of cell trains and separation of uplink and downlink periods, inside each frame, play an important role in the operation of the algorithm. In that sense, cell trains are constructed gradually, according to the algorithm based on the priorities, and ordered according to their deadlines. The deadline of a train cell is considered equal to the deadline of its first ATM cell. An ATM cell is attached at the end of the corresponding cell train if this does not cause a deadline violation of the existing cell trains.

The proposed algorithm is based on the principle that, in order to maximize the fraction of ATM cells that are transmitted before their deadlines, each ATM cell is initially scheduled for transmission as close to its deadline as possible. To attain high utilization of the radio channel, the algorithm is "work-conserving", meaning that "the channel never stays idle as long as there are ATM cells requesting transmission". Consequently, the final transmission time of a cell will be the earliest possible given the cell's initial ordering. This way the deadline of a cell in effect determines the transmission order of that cell with respect to the others.

The description of the scheduling method of the invention requires definition of some parameters. For sake of simplicity, all times are measured in slot time units. At the beginning of each frame, the slots following or preceding the frame header are numbered from 1 and -1 respectively and the parameters are adjusted accordingly. If c.sub.n (i) is the i-th cell of a connection C.sub.n, the parameters are defined as below:

a(c.sub.n (i))=the arrival time of c.sub.n (i). For downlink ATM cells, this is the actual arrival time, while for uplink ATM cells, it is estimated.

m(c.sub.n (i))=the maximum waiting time that c.sub.n (i) can wait before being transmitted in the radio interface. Here we assume that m(c.sub.n (i))=W.sub.n which is the same for all ATM cells of connection C.sub.n. But the algorithm can also be used for different m(c.sub.n (i))'s.

d(c.sub.n (i))=a(c.sub.n (i))+m(c.sub.n (i)), the latest time by which c.sub.n (i) can be transmitted without missing its deadline.

D.sub.n =min {d(c.sub.n (i))}. D.sub.n is the earliest deadline of all ATM cells of C.sub.n requesting slots in this frame k.

F.sub.n =0 if no slots are allocated to connection C.sub.n, and the first slot allocated to connection C.sub.n otherwise

L.sub.n =0 if no slots are allocated to connection C.sub.n, and the last slot allocated to connection C.sub.n otherwise

O(x)=0 if slot x is empty, and n if F.sub.n .ltoreq.x.ltoreq.L.sub.n (i.e., O(x) is the identifier of the connection that slot x is allocated to) ##EQU1## (i.e., E, is the number of free slots in the interval [1,D.sub.n ]

.DELTA..sub.n is the maximal authorised delay, for connection C.sub.n, for allocating slots after the deadline D.sub.n.

N(x) is the first empty slot after slot x.

.PHI. is the "MPDU overhead": for each MPDU transmitted over the air, a number of .PHI. time slots must be reserved for transmission of the Physical and MPDU headers. In the preferred embodiment, this overhead consumes only one slot (.psi.=1), but it would be possible to take any constant value to this overhead.

P is the "Period overhead": at the boundary between DOWN and UP periods, the RF modem must switch between transmit and receive mode, an operation which lasts some time, equal to P time slots. In the preferred embodiment, this overhead consumes only one slot (P=1), but it would be possible to take any constant value to this overhead.

It is assumed that, at the beginning of each time frame, a number of requests are pending at the scheduler. At the end of the operation, the exact position of the slots allocated for each request should be specified.

The scheduling algorithm is divided into three steps A, B, C.

Step A is the step during which the scheduler tries to allocate one slot for each C.sub.n (i), the allocated slots forming a cell train which is the closest possible in time of the earliest deadline of all cells of connection C.sub.n. This step A is divided in several sub-steps which are represented by the flow chart of FIG. 4.

Each sub-step is schematically illustrated on FIG. 5 to FIG. 11 by means of an example wherein a new slot for the connection C, is to be allocated while slots for connections C.sub.k, C.sub.l, C.sub.m have already been allocated.

Step A

In FIG. 4, when a request corresponding to cell c.sub.n (i), either for downlink transmission or for uplink contention-free transmission, is selected for service, the scheduler allocates one slot for the transmission of c.sub.n (i). Two cases have to be considered.

1. In step 401, the request is the first serviced request for connection C.sub.n in the current time frame. If all the slots in the interval [D.sub.n -.PHI., D.sub.n.sup.- ]are empty, then these .psi.+1 slots are allocated by the scheduler to cell cn(i) and the overhead. Otherwise, there are two sub-steps to be considered in step 403.

a) En>.PHI.

In step 405, there are at least .PHI.+1 empty slots in the interval [1, D.sub.n ].

From the definition of D.sub.n.sup.-, it can be proved that all E.sub.n empty slots are in the interval [1, D.sub.n.sup.- ]. In this case, the algorithm has to free .PHI.+1 positions, as close as possible, without splitting any existing cell train, to place the new ATM cell as shown in FIG. 5. These positions are D.sub.n.sup.- -.PHI. up to D.sub.n.sup.-. For instance, when .PHI. is equal to 1, all allocations between the two last empty slots and D.sub.n.sup.- shift one position to the left and all allocations between the last empty slot and D.sub.n.sup.- shift two positions to the left to leave D.sub.n.sup.- -1 and D.sub.n.sup.- empty for the new allocation. Since the allocations move to the left, none of them exceeds its deadline.

b) E.sub.n .ltoreq..PHI.

Returning to FIG. 4, there are .PHI. or less empty slots in the interval [1, D.sub.n.sup.- ] as shown in step 407. In this case, there is not enough available "free space" prior to the deadline to allocate slots for connection C.sub.n. Therefore the allocation can only be done on the "right side" of the deadline, while ensuring that the introduced delay does not exceed the maximum "extended delay" as shown in FIG. 6. The proposed approach is first to fill the E.sub.n empty slots before the deadline D.sub.n by shifting to the left the allocations before D.sub.n.sup.+ and then start the allocation on the new position of D.sub.n.sup.+, ensuring that shifting to the right existing allocations, if needed, does not violate their maximum extended delays. Therefore the strategy consists in the following steps:

a. Verify that D.sub.n.sup.+ +.PHI.-E.sub.n .ltoreq.D.sub.n +.DELTA..sub.n, to ensure that the maximum accepted delay of C.sub.n is not exceeded. If found false, no allocation is performed. For example, in FIG. 6, D.sub.n.sup.+ +.PHI.-E.sub.n =12+1-1.ltoreq.16=D.sub.n +.DELTA..sub.n.

b. For all connections C.sub.i having allocations on the right of D.sub.n, that need to be shifted to the right to make some space for the new allocation, verify that, after the shifting L.sub.i .ltoreq.D.sub.i +.DELTA..sub.i for all connections. If this is not the case, even for one connection, no allocation is performed.

For example, in FIG. 6, L.sub.m =16.ltoreq.19=D.sub.m +.DELTA.m. Otherwise:

c. Allocations up to D.sub.n.sup.+ -1 are moved to the left up to fill all the empty E.sub.n time slots, while allocations after D.sub.n.sup.+ -1 are shifted to the right, to make .PHI.+1 slots available for the new allocation.

d. The allocation is performed starting at slot D.sub.n.sup.+ (it must be noted that the value of D.sub.n.sup.+ after step "b" differs from the value before step "b", as it has been decreased by a value E.sub.n).

2. Returning to FIG. 4 and step 409, the request is not the first serviced request for connection C.sub.n in the current frame. There are three sub-steps.

a) In step 411, there is at least one empty slot in [1,L.sub.n ]. All allocations between the last empty slot before L.sub.n and L.sub.n shift one position to the left to leave L.sub.n empty for the new allocation as shown in FIG. 7. Moving to the left does not violate any deadline.

b) In step 413 there no empty slots in [1,L.sub.n ] and the slot L.sub.n +1 is empty. In this case, the allocation is performed in slot L.sub.n +1 if L.sub.n +1.ltoreq.D.sub.n +.DELTA..sub.n in step 415 and shown in FIG. 8, for example, L.sub.n +1=8+1.ltoreq.13=D.sub.n +.DELTA..sub.n. Otherwise, it is not performed.

c) In step 417, there are no empty slots in [1,L.sub.n ] and the slot L.sub.n +1 is not empty, as shown in FIG. 9. In this case, the allocation can only be performed in slot L.sub.n +1 if all the connections occupying the slots up to the first empty slot have not yet reached their maximum "extended deadline" (defined as the sum of D.sub.i and .DELTA..sub.i for each connection). The strategy consists of the following steps:

1. Check that the following relation is true, after shifting to the right by one position for all connections C.sub.i occupying slots in the interval [L.sub.n +1,N(L.sub.n +1)-1]:

If found false, even for only one connection, then no allocation is performed.

Otherwise:

2. Shift to the right by one position the previous allocations in the interval [L.sub.n +1,N(L.sub.n +1)-1] (this step frees the slot L.sub.n +1).

3. The Allocation is performed in slot L.sub.n +1.

Step B

After step A has been completed, the second step consists in building the DOWN period of the time frame, as shown in FIG. 10.

This operation consists in three sub-steps, as follows.

1. When all requests have been processed, the scheduler packs as close to the beginning of the frame as possible, all allocations between the beginning of the frame and the first slot allocated to an uplink connection (clearly all these allocations correspond to downlink connections).

2. As a result of the former sub-step, some empty slots may be left before the first uplink slot. If this number of empty slots is equal to N, then a comparison is made between N and P:

If N.gtoreq.P, then the last P slots before the first uplink slot are allocated for the so-called "Period overhead".

If N<P, then the last P-N slots of the last downlink cell train preceding the first uplink slots are re-allocated to the Period overhead. If the resulting slot train is less than .PHI.+1 slots long, then this whole slot train must be de-allocated (to avoid keeping an incomplete MPDU).

It must be noted that stealing some slots of the last MPDU may not be the optimal strategy, depending on the traffic class of the corresponding connection. Another more complex approach would be to steal slots to the connection which is last sensitive to cell loss.

3. To the space left empty between the last downlink allocation and the period overhead, the algorithm tries to pack as much downlink allocations as possible by moving them to the left.

Note that when allocations are shifted to the left, a given cell train may be broken if not enough free slots are available for the whole cell train. In this case, the procedure must ensure that the number of shift allocations is at least equal to .PHI.+1 (otherwise it would result in a MPDU with an empty payload or even with an incomplete header).

Step C

This step consists in building the UP period by shifting the slots(s) comprising the period overhead to the left to fill empty slot(s) following the DOWN period, and shifting the uplink allocation to the left just after the period overhead, as shown in FIG. 11. Of course, moving to the left does not result in any deadline violation. If some downlink allocations follow the UP period, they will be postponed to the next time frame (if they do not exceed the deadline).

Packing in steps B and C preserves the "work-conserving" property already mentioned since no slot are left empty.

At the end of the algorithm, added space composed of several slots are kept after the UP period in order to constitute the CONTENTION period.

Different aspects of the scheduling method can be modified and enhanced at the cost of some complexity, while remaining within the scope of the invention. Thus, in the embodiment described above, the deadline for uplink ATM cells is estimated according to the time of reception of the MPDU preceding the reception of a reservation request. This estimation is quite conservative, so that the real deadline may be later than estimated, potentially resulting in the absence of allocation for this connection, even if the real deadline is not exceeded. Another solution would consist of carrying some time stamp information along with the reservation request, so that the scheduler knows exactly when the uplink ATM cell was received for transmission in the MT. By using this timing information, the estimation is no longer needed, so that both the downlink and uplink traffic will be treated the same way as far as their deadline is concerned.

Another enhancement relates to the arrangement of a cell train to form the time frame. Indeed, in the preferred embodiment, the final arrangement of the cell train must respect the time frame structure where the downlink transmission always precedes the uplink transmission. This constraint may result in postponing the transmission of some cell trains in a subsequent time frame, for instance in a situation where the output of step A is a sequence of alternate DOWN and UP cell trains. As there is some overhead associated to each new time frame (the period during which the FH must be built and sent by the AP and then received and analysed by all the MTs.), it may lead to some situations where a given ATM cell will finally not be allocated for deadline reasons. One way to solve this problem is to allow interleaving of the UP and DOWN periods during the time frame, taking into account both the overhead associated to the turn-around time of the physical channel (lasting P slots) and the overhead associated to the time frame (the FH period lasting F time slots). This results in building a period interleaving if and only if it allows to issue a cell train that would be aged out if transmitted in the next time frame to come. This condition is fulfilled if the following relation is found true for a connection C.sub.n :

Though the scheduling method of the invention is appropriate to be used by the master scheduler of an Access Point, it is clear that it can also be used by the slave scheduler in each Mobile Terminal to determine the ordering of the uplink traffic which is to be transmitted during the UP period allocated by the master scheduler.

It must be noted that the scheduling method of the invention is well adapted to be implemented when the network based upon a synchronous transfer mode is a wireless network such as a radio network. However, it is in the scope of the invention to implement the scheduling method in any other network having characteristics and constraints similar to the ones of a wireless network.