WO2000062457A2

WO2000062457A2 - Method and system for data traffic scheduling

Info

Publication number: WO2000062457A2
Application number: PCT/GB2000/001285
Authority: WO
Inventors: John David Porter; Walter Charles Vester
Original assignee: Adaptive Broadband Ltd.
Priority date: 1999-04-14
Filing date: 2000-04-06
Publication date: 2000-10-19
Also published as: GB9908559D0; GB2349053B; AU3977800A; WO2000062457A3; GB2349053A

Abstract

A method and system for performing data traffic scheduling in a point-multipoint time division duplex network is disclosed, wherein data to be sent to and from a central access point and multiple remote subscriber terminals is respectively queued in respective traffic queues held at each terminal and in the access point, further phantom traffic queues reflecting the queues held at each subscriber terminal being further maintained at the access point in order to provide knowledge of the traffic to be sent on the uplink. A cell scheduler is further provided in the access point which acts to schedule transmission slots to each subscriber terminal in both the upstream and downstream directions based on the queued data traffic, the transmission slot scheduling then being communicated to each subscriber terminal in a broadcast manner.

Description

METHOD AND SYSTEM FOR DATA TRAFFIC SCHEDULING

TECHNICAL FIELD

The present invention relates to a method and system for scheduling the transmission of data traffic on a network.

More particularly, the present invention relates to a data traffic scheduling method and system which allows for traffic prioritisation and multiple traffic queues to enable efficient usage of the network medium during periods of high network loading, and providing the ability to support varying qualities of service within a wireless network.

BACKGROUND OF THE INVENTION

The recent proliferation of data communications has introduced a number of design aspects which must be taken into account when contemplating the design and implementation of a data network. One aspect of particular relevance is the increase in the number of different types of data traffic that a data network must now be able to handle, each type imposing its own quality-of- service requirements which must be successfully met. Four important metrics for a particular type of data traffic are its latency, its required throughput, the cell- drop probability, and the time-of-arrival variance. Data latency refers to how long a particular data packet or cell takes to be transmitted across a network, that is, how long the cell actually resides in the network infrastructure after having been transmitted onto the network terminal by a sender terminal and before being received at an intended receiver terminal. Different data types will have different latency requirements. For example, an electronic mail type message, irrespective of content, may reside in a network for a substantial amount of time and hence have fairly loose data latency requirements without a user noticing. In contrast, data cells generated by a video-conferencing application will have stringent data latency requirements, as they must be delivered to the receiver terminal almost immediately if the conference is to appear as if it is live. Data throughput refers to the quantity of data that a particular application produces that must transit the network. Referring to the examples given above, an e-mail message may be of any size and hence may require a high throughput but with extremely loose latency requirements (i.e. it need not transit the network immediately). Contrariwise, video-conferencing data will require both a large throughput as well as low latency. More generally, a modern data network must be able to support traffic types ranging from those which make use of the available bit rate (ABR), and hence have little or no restrictions on data latency (e.g. e-mail), through to those requiring a continuous bit rate (CBR), and which have tight restrictions on latency, throughput and time-of-arrival variance (e.g. video-conferencing data). SUMMARY OF THE INVENTION

The present invention presents a data traffic scheduling method and system which is capable of handling a full range of different types of data traffic from ABR through to CBR. Furthermore, the present invention presents a data traffic scheduling method and system wherein all scheduling may be performed centrally for a particular network cell by the central control node for the cell. Such central control brings about a number of advantages as will become apparent from the following description. According to one aspect of the present invention, there is provided a method of data traffic scheduling for use in a data communications network comprising a central control node and one or more remote subscriber nodes, data traffic on said network being sent within a jimited number of available time slots per time frame, said method comprising the steps of: a) queuing data to be sent to or from the remote subscriber nodes in one or more traffic queues maintained at the central control node and at each subscriber node respectively; and characterised by further providing the steps of: b) mamtaining respective counts of the amounts of data to be sent to the central control node held in each subscriber node's traffic queue; and c) scheduling a time slot to at least one of those remote subscriber nodes which have queued data traffic to be sent thereto or received therefrom; wherein all scheduling of data traffic to be sent to or from the remote subscriber nodes is performed at the central control node.

The scheduling step c) may further comprise the steps of: a) maintaining a list of identifiers of those remote subscriber nodes which have pending data traffic queued in their respective traffic queues; b) assigning a time slot to the particular remote subscriber node whose identifier is at the top of said list in which at least a portion of the pending data traffic queued in the particular node's respective traffic queue will be sent; and c) removing the particular remote subscriber node's identifier from the top to the bottom of said list; wherein steps b) and c) are repeated until all of the pending data traffic in each traffic queue has been scheduled or until all of the available time slots in the present time frame have been scheduled. According to another aspect of the present invention, there is provided a system providing data traffic scheduling for use in a data communications network comprising a central control node and one or more remote subscriber nodes, data traffic on said network being sent within a limited number of available time slots per time frame, said system comprising: a) traffic queue means for queuing data to be sent to or from the one or more remote subscriber nodes, one or more of said traffic queue means being maintained at the central control node and at each subscriber node respectively; and characterised by further providing: b) count means for mamtaining respective counts of the amounts of data to be sent to the central control node held in each subscriber node's traffic queue; and c) scheduler means for scheduling a time slot to at least one of those remote subscriber nodes which have queued data traffic to be sent thereto or received therefrom; wherein said scheduler means are located at said central control node, wherein all scheduling of data traffic to be sent to or from the remote subscriber nodes is performed at the central control node. The scheduler means may further comprise: a) list means for mamtaining a list of identifiers of those remote subscriber nodes which have pending data traffic queued in their respective traffic queue means; b) assigner means for assigning a time slot to the particular remote subscriber node whose identifier is at the top of said list in which a portion or all of the pending data traffic queued in the particular respective traffic queue will be sent; and c) removal means for removing the particular remote subscriber node's identifier from the top to the bottom of the said list once the time slot has been assigned by said scheduler means; wherein said assigner means and said removal means each repeat their operations in turn until all of the pending data traffic in each traffic queue has been scheduled or until all of the available time slots in the present time frame have been assigned.

When all of the available time slots in the present frame have been filled, the pending data traffic not yet scheduled is retained in the traffic queues and the method steps or operations of the various system elements are repeated in a next subsequent time frame.

Each subscriber node with pending data traffic may be scheduled a substantially equal number of time slots as every other subscriber node with pending data traffic. In this way, the bandwidth of a communications channel over which the data traffic is sent is equally distributed between the various nodes.

Each portion of pending data traffic may have one of a multiple number of traffic priorities assigned to it, whereby multiple traffic priorities may be handled by the traffic scheduler of the present invention. Where there are multiple traffic priorities, each traffic queue is further sub-divided into individual priority traffic queues for each traffic priority type.

Similarly, where there are multiple traffic priorities, a separate list of subscriber node identifiers is maintained for each traffic type, each of said separate lists containing the identifiers of those remote subscriber nodes which have pending data traffic of the respective priority queued in their respective traffic queues.

Furthermore, in the event of multiple traffic priorities, higher priority data is always scheduled a time slot before lower priority data. Moreover, the central control may indicate to every remote subscriber node in the network which time slot has been assigned to which remote subscriber node. The central control node may therefore control access of each of the remote subscriber nodes to the network channel.

The data traffic may be ATM cells, ATM compatible cells, or any other type of data without departing from the scope of the present invention.

It is an advantage of the present invention that it provides a mechanism by which the network performance gracefully declines as it becomes more and more heavily loaded.

It is a further advantage that the present invention supports common qualities of service used in ATM data networks.

It is a still further advantage that the present invention may be implemented in a single programmable gate array.

There is a further feature in that the present invention provides a mechanism by which multiple traffic types originating from different subscriber terminals can be sent over a single shared medium. Furthermore, when the network becomes overloaded, the performance degradation is equal amongst all subscriber terminals.

BRIEF DESCRIPTION OF THE DRAWINGS Further features and advantages of the present invention will become apparent from the following detailed description of a particular preferred embodiment thereof, and especially by reference to the accompanying drawings, in which:

Figure 1 shows the overall structure of the data signals used in the present invention;

Figure 2 illustrates the frame structure of a control data portion used in the present invention;

Figure 3 illustrates the frame structure of a contention-based reservation interval used in the present invention; and Figure 4 shows various of the data structures and their interrelationships utilised in the present invention. DESCRIPTION OF THE PREFERRED EMBODIMENT

A particularly preferred embodiment of the present invention will now be described. Within the particularly preferred embodiment, the method and system of the present invention are employed within a wireless access network deployed in a cellular configuration. It will be apparent to those skilled in the art, however, that the present invention may also be applied to other network configurations, and in particular wired networks, without departing from the scope thereof. Within the presently described embodiment, however, each cell consists of a central access point and multiple subscriber units. Subscriber units communicate to the network only through the access points, making the network a point-multi point architecture. The access point is the centre of all wireless network communication for the particular cell, and thus is the locus of control of access to the wireless medium for the cell. One purpose of the wireless access network employing the invention is to act as a seamless extension to a wired ATM network. ATM networks support a wide variety of traffic types ranging from available bit rate (ABR), with no restrictions on data latency or throughput, to continuous bit rate (CBR), which has tight restrictions on both latency and throughput.

Communication can occur on the wireless medium in both directions, and hence a means of duplexing the wireless medium is required. Two common methods are frequency division duplexing (FDD) and time division duplexing (TDD). In the case of FDD, the medium is broken into a downstream (data originating from the access point) frequency band and an upstream frequency band (data originating at the subscriber unit). TDD breaks a single frequency band into downstream time slots and upstream time slots. The method of traffic scheduling of the present invention is suitable for use with TDD. In order to regulate subscriber unit access to the medium, the access point shares the medium among the multiple subscriber units. The network is designed to have less total capacity than the maximum capacity that could be required. As a result, the medium becomes a scarce commodity that must be carefully managed in order to provide suitable communication capacity to all subscriber units. Subscriber units may have multiple simultaneous streams of traffic to be sent over the air, each with separate requirements for latency and throughput. When the medium is being fully utilised, a choice must be made as to which traffic is passed over the air and which traffic is held off until a period of lighter loading. This choice is facilitated by the assignment of priorities to all traffic being sent. During times when multiple traffic priorities are to be sent over the network, the highest priority traffic is chosen before the lower priority traffic. When only one priority of traffic is to be sent but the total requested capacity still exceeds that available, the traffic scheduling mechanism divides the available network capacity equally among all subscriber terminals in the network.

In order to initiate communications over the network, a subscriber terminal must first register with an access point. During the registration process, a subscriber terminal negotiates with an access point to be assigned a temporary port identifier, referred to as a subscriber unit access identification (SU_AID). Once a subscriber terminal has been granted an SU_AID, it is capable of proceeding with higher layer signalling to gain access to the network medium.

Following registration, access of the subscriber terminals to the wireless medium is controlled through central control of the subscriber terminals by the access point. In order to achieve this the access point is provided with a medium access controller (MAC) which administers the medium control. Similarly, each remote subscriber teπninal is also provided with a compatible medium access controller for responding to the central MAC in a master-slave manner: the subscriber terminals request access to the medium and the access point has the ability to grant access or fail to grant access based on the current level of network utilisation. Access to the network is granted in the form of time slots - when a subscriber terminal is granted the ability to access the wireless network medium, it is granted one or more time slots in which it can transmit. Within the granted time slot the entire medium capacity is available to the subscriber node to transmit its payload data. By referring to a medium access controller, it is to be understood that either a hardware or software based control means is envisaged and that reference to a controller as such implicitly includes reference to those control means required at both the central access point and at the subscriber terminals. In this respect, the medium access controller (MAC) therefore corresponds to those network means, whether hardware or software based, that would approximate to the Network-level and/or Data-level of the ISO Open Systems Interconnection 7-layer Reference Model. The MAC may be implemented in a single field programmable gate array (FPGA). The MAC operates by controlling transmissions on the medium by the definition of a MAC frame, being the framework in which data transmissions take place. In order to fully understand the various features and advantages of the present invention, it is necessary to first describe those constituent parts of a MAC frame pertinent to the present invention and then follow with a description of the various data structures used in the MAC. This will be performed by reference to Figures 1 through 4.

Figure 1 shows the overall structure of a single MAC frame. The MAC frame consists of a downstream portion, generated by the access point and broadcast to all subscriber terminals, and an upstream portion, which consists of a contention interval and all data bursts being sent from subscriber terminals back to the access point.

The downstream portion consists first of a downstream preamble (2). The downstream preamble is a Physical layer synchronization sequence of fixed length, used for frame acquisition and channel estimation. Only one downstream preamble may occur per MAC frame. Immediately following the downstream preamble is the frame descriptor header (FDHDR) (4). The FDHDR describes the complete contents of the remainder of the MAC frame. The size of the FDHDR may vary. The FDHDR contains a map of all traffic, upstream and downstream, to occur within the MAC frame. After achieving bit synchronisation on the MAC frame via the preamble, subscriber terminals demodulate the FDHDR and from that gain complete knowledge of the traffic that will occur within the remainder of the frame. Only one FDHDR may occur per MAC frame. The precise contents of the FDHDR are shown in Figure 2 and described in detail in Table 1 below. Field Tag Description

SYNC Short 4 symbol sync burst. BD_cnt Bursts Downstream Count. Number of subscriber units having payload data sent to them in this MAC frame

BU_cnt Bursts Upstream Count. Number of subscriber units that will be sending payload data in this MAC frame.

AP_ID Access Point ID. Identifies the access point that originated the frame descriptor header.

RRA_cnt Reservation Request Acknowledgment Count. Number of acknowledgments being sent in response to previous requests.

DA_cnt Downstream Acknowledgment Count. Number of upstream cell acknowledgements being sent downstream in this MAC frame.

Downstream Identifies the subscriber unit being sent cells, the number of cells to

Map be sent, and the traffic type being sent.

RR_cnt Reservation Request count. Total number of reservation request slots that will be made available in this MAC frame.

UA cnt Upstream Acknowledgment count. Total number of downstream cell acknowledgments being sent upstream in this MAC frame.

Upstream Identifies the subscriber units that have been granted reservations,

Map the number of cells to be sent by each, and the traffic type allowed.

CRC Cyclic Redundancy Check. Allows each subscriber terminal to verify correct receipt of the frame descriptor.

SU_ID Subscriber Unit ID. Identifies the subscriber unit acting as the data source or sink in the burst.

Cell_Cnt Cell Count. Total number of ATM cells to be sent in this particular burst. Tr_type Traffic Type. Defines the type of traffic that the subscriber unit is allowed to send or will be receiving during the current frame. Table 1 : Frame Descriptor Header (FDHDR) Structure

Following the FDHDR is the reservation request acknowledgement (RRA) portion 6. The RRA acknowledges a request by a subscriber for upstream time slots and can also communicate signal propagation delay. There is a single RRA for each reservation request that was made diiring the contention interval from the previous MAC frame, although in the case where no reservation requests were made in the previous MAC frame, then no acknowledgements will be sent. Following the RRA comes the Downstream Acknowledgement (DACK) portion 8 containing DACK cells. Each DACK cell contains a downstream ack or nack of a single upstream burst from a previous MAC frame. There is a single DACK cell for each upstream burst from the previous MAC frame, although in the event that there were no previous upstream bursts then no DACKs will be sent. Following the DACK portion comes the Downstream Burst (9). The

MAC operates on a principle of cell bursts for communicating payload data between the access point and the subscriber terminals by allowing multiple cells of data to be sent to or from a particular subscriber unit at a time. A burst must always consist of at least one cell. In upstream bursts, this single cell must be an upstream cell with reservation request (UCELLR) (18). Additional cells in the upstream burst are in the format of a UCELL - an upstream cell without reservation request (20) . Upstream cells are discussed in more detail later. Downstream bursts can also consist of multiple cells, but there is only one type - the downstream cell (DCELL) 10. There can be many DCELLs - either several directed to a single subscriber terminal, or several directed to several subscriber terminals. Each DCELL contains one ATM cell of payload data. Currently the MAC allows bursts to have a maximum size of six cells, although more or less cells may be designated per burst if required in a future implementation without departing from the scope of the present invention. The downstream burst concludes the downstream portion transmitted by the access point and received at all subscriber terminals. There then follows a slight delay due to subscriber turnaround time (STT) 12. The STT varies with distance to the farthest subscriber unit. A typical maximum distance to a subscriber unit could be , for example, 5km, although this obviously depends on the network configuration and the size of each network cell.

Following the STT comes the Upstream Portion of the MAC frame, being data transmitted from the subscriber units to the access point. The entire expected structure of the upstream portion has already been communicated to each and every subscriber terminal in the FDHDR transmitted in the downstream portion. Therefore, each subscriber terminal knows whether or not it is permitted to transmit in the upstream portion, what data it is to transmit, and when it is to transmit this data. In this way absolute control of the contents of the upstream portion can be controlled by the access point. With such a mechanism, however, it becomes necessary to define a period in which subscriber terminals can first communicate a request for transmission permission to the access point, without which no subsequent permission would ever be granted. This period forms the first part of the upstream portion, being the subscriber reservation request (SRR) portion 14. The structure of the SRR is shown in detail in Figure 3, and described below in Table 2.

Field Tags Description

Preamble Physical layer synchronization sequence.

Sync 8 bit MAC framing synchronization burst

SU_ID ID of the subscriber unit requesting a reservation.

Cells Number of cell time slots being requested by the subscriber unit.

Tr_Type Traffic type of the data for which time slots are being requested.

CRC Cyclic redundancy code. Used to verify correct receipt of this upstream burst. Table 2: Subscriber Reservation Request (SRR) structure

The SRR is a contention based reservation request interval. If a subscriber terminal has been sitting idle with empty data queues, the arrival of a burst of data on its physical port will force it to request a time slot reservation from the access point. Because the subscriber terrninal has no active reservations, and because it is believed that at any given time the number of terminals making initial bandwidth requests will be small, it is reasonable to force the subscriber terminals to contend for reservations. This contention window is kept as small as possible while still allowing reasonable success probability by employing a novel implementation of aloha contention control schemes. Once the subscriber terminal's reservation request has been acknowledged by the access point, the subscriber terniinal ceases requesting bandwidth in the contention slots, allowing other terminals access to the contention interval. The number of SRR' s that may occur in one MAC frame is communicated to the subscriber teraύnals in the FDHDR. Multiple slots can be made available during times of heavy request traffic. Furthermore, the start of the contention interval can be calculated by the subscriber terminals by virtue of the FDHDR indicating to each teπninal the number of RRAs, DACKs and the structure of the downstream burst in the subsequent downstream portion of the MAC frame. The contention interval then begins immediately after the end of the downstream burst, allowing for the STT.

Following the contention interval comes the upstream acknowledgement portion 16 , containing upstream acknowledgement (UACK) cells of each downstream burst received during the downstream portion. Each UACK indicates upstream ack or nack of a single downstream burst from a previous MAC frame. As many UACKs may be transmitted in each upstream acknowledgement portion as there were downstream bursts in the downstream portion.

Following the upstream acknowledgement portion comes the upstream burst portion 22, containing cell bursts from subscriber units which were granted permission in the FDHDR to transmit payload data to the access point. The FDHDR from the downstream portion contains the instructions to the subscriber terminals on when to transmit a burst in the upstream burst portion, and what the burst is expected to contain. Each upstream burst contains one or more data cells with the same traffic type being sent from a particular subscriber terminal. Each upstream burst made in the upstream burst portion may be from a different subscriber unit, or alternatively may be from the same subscriber unit, depending upon the channel allocations granted to the subscriber units. In this way channel allocations can be dynamically arranged between the subscriber terminals from MAC frame to MAC frame, depending on the network traffic loading and the traffic priority. As mentioned earlier, each upstream burst must contain a single upstream cell with reservation request (UCELLR) 18, and zero or more upstream cells without reservation request (UCELL) 20. The condition that a burst must contain a UCELLR allows a subscriber terrninal to maintain its channel reservation until all of its payload data has been sent, thus meaning that the subscriber teπninal need not transmit again during the contention interval to request channel allocation to transmit the remainder of its data. This combination of the reservation maintenance request and the upstream cell into one message allows a single downstream acknowledgement to serve as both reservation maintenance request acknowledgement and payload cell acknowledgement, thus improving bandwidth efficiency.

The various data structures used within the MAC which are pertinent to the present invention will now be described with reference to Figure 4. Unless otherwise indicated, the following data structures are contained within the access point MAC.

The first relevant data structure is the subscriber unit list 102. The subscriber unit list contains a list of actively registered subscriber unit access IDs, with a pointer (104) from each entry to a set of traffic queues. The next structures are the downstream subscriber unit traffic queues

105, 106 and 107. For each subscriber unit that is actively registered with an access point, there is a set of traffic queues, each set containing one queue per traffic type. The downstream traffic queues are located within the MAC at the central control node. Similar upstream traffic queues are also located at each subscriber node, with one set of queues at each node . For each downstream queue there is a Cell acknowledgement map 109. Each time a cell is sent from the access point to a subscriber temiinal, the access point expects to receive a positive (ack) or negative acknowledgement (nack) of the cell's arrival. The acknowledgement bit map must contain as many bits as the maximum number of cells that can be sent in a burst. In a current implementation, as a non-limiting example, no more than six cells of a given traffic type for a particular subscriber unit can be sent within a single MAC frame, and hence it is not necessary to retain the acknowledgement status for more than six cells of a given traffic queue. Therefore, each queue has a six bit acknowledgement map coπesponding to the acknowledgement sξate of the most recently sent six cells. It is to be understood that more or less cells may be sent in a burst without departing from the scope of the present invention, in which case the acknowledgement bit map must contain the same number of bits.

The next relevant data structures are the downstream pending reservation queues 110, 111, 112, 113. For each traffic type, there is a circular buffer (the pending reservation queue) containing a single entry for each subscriber unit with traffic awaiting a reservation.

The next relevant data structures are the upstream phantom subscriber unit traffic queues 120, 122 and 124. For each subscriber unit that is actively registered with an access point, there is a set of phantom traffic queues for upstream traffic, one queue per traffic type. The actual upstream traffic queuing is performed at the subscriber terminals, as mentioned earlier. However, the access point retains information about the size of each subscriber terminal upstream queue in these phantom upstream queues.

The final data structure is the downstream frame reservation schedule 116. Contained witl in this structure is a map of all bursts to be sent during the subsequent downstream portion of the MAC frame. Entries for each burst include the subscriber unit access identifier (SU_AID), the traffic type of the burst, and the number of cells contained within the burst. There is a similar upstream reservation schedule, which is formed in an identical manner, but which is not shown here. Figure 2 and Table 1 (above) show more information regarding the burst schedules. The frame reservation schedule is identical in format to the burst map contained within the FDHDR, which helps to implement the present invention within a single FPGA. Having described the various signal and data structures used within the presently described embodiment of the present invention, the mechanism by which the method and system of traffic scheduling of the present invention is implemented will now be described in detail. For ease and brevity of description, the following description will concentrate on traffic scheduling in the downstream direction, although brief mention will also be made of those aspects particular to traffic scheduling in the upstream direction.. It will, however, be readily apparent to those skilled in the art how the following is also applied in detail to traffic scheduling in the upstream direction, without departing from the scope of the present invention. With reference to Figure 4, when a downstream cell enters the

MAC, it is de-multiplexed into the downstream traffic queue corresponding to its subscriber unit and traffic type. If the queue had been empty upon cell arrival, the subscriber unit's SU_AID is entered into the pending reservation buffer for the corresponding traffic type (thus opening up a bandwidth reservation between the access point and the subscriber unit for which the data is destined). With traffic in the subscriber unit queues a cell scheduling method and means (not shown) is then activated.

The cell scheduler first checks the pending reservation request buffer for the highest priority traffic type to see if any cells of that type are awaiting transmission. If there is an entry in the buffer (indicating that there may be traffic of that type queued up), the scheduler reads the SU_AID from the buffer and uses it as an index into the subscriber unit list to reference the subscriber unit's traffic queue for that traffic type. The scheduler then calculates the number of cells pending in the subscriber unit's traffic queue, and makes an entry in the frame descriptor. The entry describes the contents of a single downstream burst, and includes the SU_AID, the traffic type, and the number of cells contained in the burst (see Figure 3). The cell scheduler operates under the assumption that any bandwidth reservation between the access point and a subscriber terminal will need to remain in effect for subsequent MAC frames (in order to support additional cells that arrive during the MAC frame, and to support cell retransmission). As such, it will put the SU_AID at the tail end of the pending reservation queue in order to keep the reservation active for the next MAC frame, regardless of whether there are any cells to be sent in the next MAC frame or not. As stated above, when the cell scheduler reads an SU_ALD out of a pending reservation buffer, it first calculates the number of cells that are pending. If that number is zero, the reservation is dropped and no future entry is made in the pending reservation buffer, nor is a corresponding entry made in the frame descriptor header.

The traffic scheduler will continue to read reservations from the highest priority pending reservation buffer, until that buffer is empty. Once it is empty, the cell scheduler will begin reading pending reservations from the next highest priority buffer. Because reservations are serviced in a prioritized manner, the wireless network is able to support multiple qualities of service.

With regards to traffic scheduling in the upstream direction, as stated earlier, the access point MAC is responsible for scheduling upstream traffic as well as downstream. However, unlike the downstream traffic, the data queues are not physically located at the access point and usable as input to the scheduling method and means. Rather, the access point maintains "phantom" upstream traffic queues, which contain a count of the number of cells in each traffic queue at each subscriber teiminal. These counts are used in the traffic scheduling performed for the upstream traffic. Information concerning the contents of the upstream traffic queues is communicated via the upstream bandwidth reservation requests, which are sent up to the access point by a subscriber terrninal anytime new traffic arrives in the subscriber terminal traffic queues.

As one further feature of the present invention, it is possible that the network medium will be over allocated even though only a single priority of traffic is being sent. In this case, the scheduling mechanism of the present invention described above guarantees that each subscriber terrninal is granted an equal portion of the available bandwidth. This is due to the fact that after reading a pending reservation from the pending reservation buffer, the scheduler puts the same SU_AID at the tail end of the buffer. This allows the subscriber terminal's reservation to be kept open, but guarantees that it will not be serviced again until all other pending reservations in the buffer have been serviced.

As described above, the present invention presents a data traffic method and system which allows for network bandwidth to be efficiently partitioned amongst multiple network nodes, and to be further sub-partitioned within each node to allow for data traffic of different priorities. The present invention ensures that each node with pending data traffic of the same priority is allocated an equal share of the available bandwidth, and as such further ensures that performance degradation is spread equally between each network node as the network data traffic load increases. Furthermore, whilst the above description has made reference to the data traffic consisting of ATM cells, it should be understood that the present invention is not limited to the use of ATM cells, and that in fact various data packet formats may be used whether they be ATM cells, ATM-compatible cells, or any other format or standard.

Claims

CLAIMS:

1. A method of data traffic scheduling for use in a data communications network comprising a central control node and one or more remote subscriber nodes, data traffic on said network being sent within a limited number of available time slots per time frame, said method comprising the steps of: a) queuing data to be sent to or from the remote subscriber nodes in one or more traffic queues maintained at the central control node and at each subscriber node respectively; and characterised by further providing the steps of: b) mamtaining respective counts of the amounts of data to be sent to the central control node held in each subscriber node's traffic queue; and c) scheduling a time slot to at least one of those remote subscriber nodes which have queued data traffic to be sent thereto or received therefrom; wherein all scheduling of data traffic to be sent to or from the remote subscriber nodes is performed at the central control node.

2. A method according to claim 1, wherein the scheduling step c) further comprises the steps of: a) maintaining a list of identifiers of those remote subscriber nodes which have pending data traffic queued in their respective traffic queues; b) assigning a time slot to the particular remote subscriber node whose identifier is at the top of said list in which at least a portion of the pending data traffic queued in the particular node's respective traffic queue will be sent; and c) removing the particular remote subscriber node's identifier from the top to the bottom of said list; wherein steps b) and c) are repeated until all of the pending data traffic in each traffic queue has been scheduled or until all of the available time slots in the present time frame have been scheduled.

3. A method according to claims 1 or 2, wherein when all of the available time slots in the present time frame have been scheduled, the pending data traffic not yet scheduled is retained in the respective traffic queues, and the method steps are repeated in a next subsequent time frame.

4. A method according to any of the preceding claims, wherein each subscriber node with pending data traffic is scheduled a substantially equal number of time slots as every other subscriber node with pending data traffic, whereby the bandwidth of a communications channel on which the data traffic is sent is equally distributed between the subscriber nodes.

5. A method according to any of the preceding claims wherein each portion of data traffic is assigned a priority relative to every other portion of data traffic.

6. A method according to claim 5, wherein multiple levels of priority are available, and each portion of data traffic is assigned one of the multiple levels of priority depending upon the particular data latency and throughput requirements of each of the data portions.

7. A method according to claims 5 or 6, wherein each traffic queue is further sub-divided into individual priority traffic queues for each traffic priority type.

8. A method according to any of claims 5, 6 or 7, wherein the mamtaining step step a) further comprises the step of mamtaining a separate list of subscriber node identifiers for each traffic priority type, each of said separate lists containing the identifiers of those remote subscriber nodes which have pending data traffic of the respective priority queued in their respective traffic queues.

9. A method according to any of claims 5 to 8, wherein the data traffic of the highest priority type is scheduled first, and the data traffic of the lowest priority type is scheduled last.

10. A method according to claim 9, wherein each remote subscriber node with pending data traffic of the higher priority type is assigned one of the time slots before those remote subscriber nodes with pending data traffic of the lower priority types, whereby higher priority traffic is always scheduled before lower priority data traffic.

11. A method according to any of the preceding claims, wherein the central control node indicates to every remote subscriber node in the network which time slot has been assigned to which remote subscriber node.

12. A method according to any of the preceding claims, wherein the central control node controls access of each subscriber node to the network.

13. A method according to any of the preceding claims, wherein the scheduled data traffic is transmitted from or received at the central control node to/from at least one of the remote subscriber terminals over a wireless channel.

14. A method according to any of the preceding claims wherein the pending data traffic contains ATM compatible cells.

15. A system providing data traffic scheduling for use in a data communications network comprising a central control node and one or more remote subscriber nodes, data traffic on said network being sent within a limited number of available time slots per time frame, said system comprising: a) traffic queue means for queuing data to be sent to or from the one or more remote subscriber nodes, one or more of said traffic queue means being maintained at the central control node and at each subscriber node respectively; and characterised by further providing: b) count means for mamtaining respective counts of the amounts of data to be sent to the central control node held in each subscriber node's traffic queue; and c) scheduler means for scheduling a time slot to at least one of those remote subscriber nodes which have queued data traffic to be sent thereto or received therefrom; wherein said scheduler means are located at said central control node, wherein all scheduling of data traffic to be sent to or from the remote subscriber nodes is performed at the central control node.

16. A system according to claim 15, wherein said scheduler means further comprise: a) list means for mamtaining a list of identifiers of those remote subscriber nodes which have pending data traffic queued in their respective traffic queue means; b) assigner means for assigning a time slot to the particular remote subscriber node whose identifier is at the top of said list in which a portion or all of the pending data traffic queued in the particular respective traffic queue will be sent; and c) removal means for removing the particular remote subscriber node's identifier from the top to the bottom of the said list once the time slot has been assigned by said scheduler means; wherein said assigner means and said removal means each repeat their operations in turn until all of the pending data traffic in each traffic queue has been scheduled or until all of the available time slots in the present time frame have been assigned.

17. A system according to claims 15 or 16 wherein the scheduler means schedules each subscriber node with pending data traffic a substantially equal number of time slots as every other subscriber node with pending data traffic, whereby the bandwidth of a con--munications channel over which the data traffic is sent is equally distributed between the subscriber nodes.

18. A system according to claims 15-17, wherein said pending data traffic may have multiple priority types.

19. A system according to claim 18, wherein each of said traffic queue means further comprise a plurality of priority traffic queues, each priority traffic queue containing pending data traffic of one particular priority type.

20. A system according to claims 18 or 19, wherein said list means further includes a plurality of priority listing means, each of said priority listing means maintaining a separate list of subscriber node identifiers for each traffic priority type, each of said separate lists containing the identifier of those remote subscriber nodes which have pending data traffic of the respective priority queued in their respective traffic queues.

21. A system according to any of claims 18 to 20, wherein pending data traffic of a higher priority type is assigned to a time slot by the assigner means before pending data traffic of a lower priority type.

22. A system according to claims 15 to 21, wherein the scheduled data traffic is transmitted from or received at the central control node to/from at least one of the remote subscriber nodes over a wireless channel.

23. A system according to any of claims 13 to 18, wherein said data traffic contains ATM compatible cells.