Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-11-04
2004-01-20
Pham, Chi (Department: 2667)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
Reexamination Certificate
active
06680909
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to wireless communication systems and, more particularly, to a scheduling method that gives high system throughput and fairness among different connections in a wireless network.
2. Background Description
Most of the emerging pico-cellular wireless communication systems are Master driven Time Division Duplex (TDD) based systems. Conventional data packet scheduling strategies based on a Round Robin scheduling protocol perform poorly in these systems.
The physical constraints of the wireless medium often lead naturally to a Master-Slave configuration. In a Master-Slave configuration, one of the stations in a cell is the Master (this could be a fixed Access Point or a Base Station) and the other remote stations are Slaves (e.g., the handheld devices such as palmtop computers, cell phones, pagers).
The need for simplicity and low complexity has made Time Division Duplex (TDD) one of the promising candidates for medium access control (MAC) in wireless systems having a Master-Slave configuration. In TDD MAC, the forward (i.e., Master to Slave) and the reverse (i.e., Slave to Master) slots occur in pairs; that is, once data is sent by the Master in the forward slot, the subsequent slot is reserved for the Slave to transmit data, as illustrated in FIG.
1
. Further, the asymmetry of base stations and mobile units and the resource scarcity at mobile units make it desirable in wireless systems to have most of the complexity at the Master. This mode of operation makes multiple access straight forward, since the Master provides a single point of coordination. Proposed standards for low-power, low-cost wireless mobile communication systems have adopted centralized TDD scheduling as the MAC protocol for scheduling access to the wireless medium.
Master driven TDD scheduling poses several challenges since the traditional scheduling policies do not perform well over this kind of a MAC. Once a Master polls a Slave, the next slot is reserved for the Slave irrespective of whether the Slave has data to send or not (see again FIG.
1
). An efficient scheduling methodology would depend upon (i) the state of the queues at the Master and at the Slaves, (ii) the traffic arrival process at these queues, and (iii) the packet length distribution at the Master and the Slave. It is with this in mind that we propose a new scheduling method adapted for TDD MAC at the Master. The parameters of interest that we have studied are (i) system throughput, (ii) packet delays and (iii) fairness. Throughput is defined as number of slots utilized for transmitting data. Fairness is defined as equal bandwidth for different connections.
Scheduling methods which involve a-priori reservation of slots by the slaves have been proposed. See for example, U.S. Pat. No. 5,506,848 to Drakopoulos et al. for “Demand Assignment System and Method for Mobile Users in a Community of Interest ”. However, in some systems, reservation of slots for data packets is not allowed. Due to the Master driven TDD structure, a Slave packet can only be transmitted after a Master packet.
In U.S. Pat. No. 5,274,841 to Natarajan et al. for “Methods for Polling Mobile Users in a Multiple Cell Wireless Network ”, methods for polling mobile users have been discussed. However, the uplink wireless communication is done using CSMA (Carrier Sensing, Multiple Access) protocol.
A two stage non-contention based Multiple Access protocol is discussed in U.S. Pat. No. 5,297,144 to Gilbert et al. for “Reservation-based Polling Protocol for A Wireless Data Communications Network ”. This protocol is based on Reservation based polling. The slot restrictions in some systems make such an approach infeasible.
In U.S. Pat. No. 4,763,322 to Eizenhofer for “Digital Radio Transmission System with Variable Duration Time Slots in the Time-Division Multiplex Frame ”, a scheduling method with variable duration of the time slots in the time-division multiplex frame is discussed. However, the methodology is not applicable to a TDD system and has variable duration time slots (as opposed to systems having fixed size slots).
A scheduling method for providing proportional use of network bandwidth is proposed in U.S. Pat. No. 5,844,890 to Delp et al. for “Communications Cell Scheduler and Scheduling Method for Providing Proportional Use of Network Bandwidth. However, this method is not suited to some systems as it does not tackle the issues posed by Master driven TDD systems.
Scheduling Challenges in Master Driven
TDD Wireless Pico Cellular Systems
In Master Driven TDD wireless systems, Master and Slave queues are served in pairs. If a Master has data to send and Slave has no data to send, the reverse slot is wasted, as illustrated in FIG.
2
. In such systems, each Slave has a queue of data packets to be sent to the Master (we refer to this as the Slave queue from now onwards). Similarly, there is a queue at the Master for each Slave, containing data packets to be sent to the Slave.
We observe that different connections can have different slot utilization. To increase system throughput, we need to give more service to connections with less slot wastage. However, by doing so we are introducing unfairness (in terms of slots received by a connection) among different connections. We need scheduling methods that increase system throughput yet provide fairness. See, for example, C. Fragouli, V. Sivaraman and M. B. Srivastava; “Controlled Multimedia Wireless Link Sharing via Enhanced Class-Based Queueing and Channel-State-Dependent Packet Scheduling ”,
IEEE INFOCOM '
98, San Franscisco, Calif., March, 1998; S. Lu, V. Bharghavan and R. Srikant, “Fair Scheduling in Wireless Packet Networks ”, ACM SIGCOMM '97, August, 1997; and S. Lu, T. Nandagopal and V. Bharghavan, “A Wireless Fair Service Algorithm for Packet Cellular Networks ”,
ACM MOBICOM '
98, Dallas, Tex., 1998.
Conventional Scheduling Policies: Round Robin
The conventional scheduling policies are based on Round Robin (RR) Scheduling. In RR scheduling, different connections are visited in a cyclic order.
FIG. 3
illustrates the scenario in RR scheduling.
In TDD Master driven systems the scheduling is done in pairs of queues rather than a single queue (Forward slot for the Master queue followed by the Reverse slot for the Slave queue). Conventional strategies like Round-Robin scheduling will give equal slot allocation to all the connections. Since different connections have different slot utilization, this can lead to significant slot wastage in RR scheduling.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide a scheduling method that provides high throughput and at the same time fairness in Master driven TDD wireless systems.
The scheduling policies that we propose can be labeled as Master-Slave Queue-State-Dependent Packet Schedulihng Policies. These policies use the information about Master and Slave queues to achieve better system performance. The scheduling methodology is implemented at the Master and therefore has access to information about the Master queues. Different kinds of information about the queues such as backlog, size, delays can be used.
As an example, in our scheduling policies we use the “backlog ” information at the Master and Slave queues. A Queue is backlogged if it has packets to send. Denote by “1” the state in which a queue (Master or Slave) has data to send and by “0” when there is no data to send. Clearly, this leads to four distinct states of the Master-Slave queue pairs. For example, the Master-Slave “pair ” is in the “1-1” state if both the Master and the Slave of a connection have data to send (are backlogged); if both Master and Slave have no data, this pair is in the “0-0” state.
The queue information about the Slaves can be communicated by various mechanisms to the Master. The communication may be through piggybacking information on packets or implicit mechanisms such as observing the system. In our policies, we convey the backlog information about the Slave q
Bansal Deepak
Kalia Manish
Shorey Rajeev
Coca T. Rao
International Business Machines - Corporation
Jones Prenell
Whitham Curtis & Christofferson, P.C.
LandOfFree
Media access control scheduling methodology in master driven... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Media access control scheduling methodology in master driven..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Media access control scheduling methodology in master driven... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3208709