Multiplex communications – Communication over free space – Combining or distributing information via time channels
Reexamination Certificate
2000-03-24
2003-12-02
Ngo, Ricky (Department: 2697)
Multiplex communications
Communication over free space
Combining or distributing information via time channels
C370S230000, C370S412000, C370S449000
Reexamination Certificate
active
06657987
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to Time Division Duplex (TDD) indoor wireless communication networks and, more particularly, to a scheduling algorithm for providing Quality of Service (QoS) by controlling medium access in communication networks. In particular, it can be applied to Master-driven TDD wireless systems for maximizing the schedulable utilization (i.e., maximizing utilization under QoS constraints) of the system and for meeting QoS requirements like token rate and latency (maximum delay).
2. Background Description
Bluetooth™ is a computing and telecommunications industry specifications that describes how mobile phones, computers, personal digital assistants (PDAs), and other devices can interconnect using a short range wireless connection. Each device is equipped with a microchip transceiver that transmits and receives in the frequency band of 2.45 GHz. Each device will have a unique 48-bit address from the Institute of Electrical and Electronics Engineers (IEEE) 802 standard. Connections are one-to-one, and the maximum range is ten meters. Data can be exchanged at a rate of one megabits per second (Mbs) and up to two Mbs in the second generation of the technology. The five founding companies of the Bluetooth™ Special Interest Group (SIG) are Ericsson, International Business Machines (IBM), Intel, Nokia; and Toshiba. Additional information may be had by reference to the Web site www.bluetooth.com and an article by Andrew Seybold entitled “Bluetooth Technology: The Convergence of Communications and Computing”, reprinted from
Andrew Seybold's Outlook
, May 1998, on the World Wide Web at www.gsmdata.com/artblue.htm.
Indoor wireless networks based on standards such as Bluetooth™ use frequency hopping to combat the problem of interference from sources such as microwave ovens and cordless telephones, which also use frequencies in the same band. In practical environments, in addition to active interfering sources, there can also be objects such as water fountains and racks of bottles with water content which absorb much of the radiation in the 2.45 GHz band and obstruct communication between master and slave units in the vicinity. Therefore, a master unit needs to detect such problems in communication and take necessary actions to prevent loss of packets during the periods of interference.
In the current Bluetooth™ standard, due to frequency hopping, the carrier frequency used in consecutive time slots is a different one of several different frequencies within the 2.45 GHz band of frequencies. Therefore, an interference in sub-bands centered around one of these frequencies will only affect communication during that time-slot in which the frequency sub-band is used. Further, in the Bluetooth™ standard, a packet can occupy one, three or five time slots, and in the case of multiple size packets, the same frequency as fixed for the first time slot is used. Because of this, it is possible to mask the effect of an interference by transmitting a packet of appropriate size. For example, if it is known that there is high chance of interference in one of the second through fifth time slots, and very low probability of the first time slot being bad, it is possible to skip the frequencies corresponding to second through fifth time slots by transmitting a five time-slot packet instead of one or three time-slot packets.
The characterization of link between any Slave unit and the Master can be done by the Master unit based on the receipt or otherwise of acknowledgments received from the Slave unit. Alternatively, all the Slaves can record the number of times they detect good packet headers sent by the Master to any Slave. This information can be transmitted from the Slaves to the Master at periodic intervals of time. The Master can use this information along with frequency look-ahead to determine the next Slave for communication and also the appropriate packet size.
Master-driven TDD can be described briefly as follows in the context of a pico-cellular system, such as the Bluetooth™ standard. Each cell or pico-net comprises of a Master device and several Slave devices. Each device can either send or receive in a slot. The Master controls the traffic on the pico-net and schedules the Slaves on the wireless channel. The Master schedules a Slave by sending a packet addressed to it, and the Slave replies with its own transmission in the next slot. Thus, Master and Slave transmissions are coupled and controlled by the Master.
Providing Quality of Service (QoS) to the connections makes the scheduling policy very important. QoS is defined by various parameters for different systems. These parameters are negotiated between the Master and the Slave at the time of connection establishment. The link layer QoS parameters for data sessions that we consider are described below:
Token Rate: This is the rate at which data should be drained from the buffer corresponding to a data connection.
Token Bucket size: This is the maximum buffer size that the connection might require. It is assumed that when the buffer is full, any new incoming data is discarded.
Peak Bandwidth: This is the maximum rate at which a burst of data enters the buffer.
Latency: This is the maximum delay that can be tolerated by a single packet.
Maximum burst size: This is the maximum size of a single burst.
Average arrival rate: This is the maximum rate at which data can arrive after a burst has arrived, while the buffer is not empty.
All the above parameters are mapped to a Polling Interval (PI), which is the only parameter that is known to the scheduler, implemented at the Master. The polling interval is defined as the maximum time between two consecutive polls to the same connection. The right choice of this parameter would ensure that data is emptied from the buffer at the required token rate, and the scheduling method which uses this polling interval would ensure that the latency requirement of each connection is met. The polling interval is also dependent on the maximum packet size for a session, and has to be re-calculated every time the maximum packet size changes.
It is assumed that there are two types of sessions—guaranteed and best-effort. For guaranteed sessions, a violation of the QoS parameters results in an exception and the parameters are renegotiated. For best-effort sessions, a temporary violation of the QoS parameters is not that serious. However, even for best-effort sessions, whenever there is a buffer overflow, a violation is raised and the parameters are renegotiated.
Existing Scheduling Policies
There has been a considerable amount of research on scheduling algorithms for communication networks. However, none of these consider the problem of scheduling connections with QoS constraints on a polling based Media Access Control (MAC) layer which does not allow reservations. Some of them are listed below:
S. Lu, V. Bliargavan and R. Srikant, in “Fair Scheduling in Wireless Packet Networks”, ACM SIGCOMM'97, August 1997, describe a model for wireless fair scheduling based on an adaptation of fluid fair queueing to handle location-dependent error blasts. They describe an algorithm which provides a packetized implementation of the fluid model while assuming full knowledge of the current channel conditions.
D. Ferrari and D. Verma, in “A Scheme for Real-Time Channel Establishment in Wide-Area Networks”,
IEEE Journal on Selected Areas in Communications
, pp. 368-379, April 1990, explore the feasibility of providing real-time services on a packet-switched store-and-forward wide-area network with general topology. The describe a scheme for the establishment of channels with deterministic or statistical delay bounds.
R. L. Cruz, in “Quality of Service Guarantees in Virtual Circuit Switched Networks”,
IEEE Journal on Selected Areas in Communications
, vol. 13, no. 6, August 1995, reviews some recent results regarding the problem of providing deterministic quality of service guarantees in slot-based virtual circuit switched networks.
Manish Kalia, Deepa
Kumar Apurva
Ramachandran Lakshmi
Coca T. Rao
Ngo Ricky
Swickhamer Christopher M
Whitham Curtis & Christofferson, P.C.
LandOfFree
Scheduling methodology for connections with quality of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Scheduling methodology for connections with quality of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling methodology for connections with quality of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3116883