Multiplex communications – Channel assignment techniques – Polling
Reexamination Certificate
1999-12-06
2002-11-12
Vo, Nguyen T. (Department: 2682)
Multiplex communications
Channel assignment techniques
Polling
C370S329000
Reexamination Certificate
active
06480505
ABSTRACT:
BACKGROUND
The present invention relates to data communication systems for transferring information in packets and more particularly, to scheduling packets in a wireless communications network using polling.
In many conventional packet-oriented data communications networks, the data traffic between units may be controlled by one centralized unit. In such networks, the central unit may be referred to as a server and the remaining units are denoted as clients. All data packets destined for a particular unit or “node” in the network pass through the central node. Moreover, a client node may not generally send data without first being polled by the server unit.
In client-server oriented network architectures, communications channels between a server unit and client units are generally bidirectional and may use either wireline or wireless transmission technology. In the case of a shared channel in either a wireline or wireless network, total data transfer capacity may be shared among one or more clients. A server unit in such a network is therefore responsible for distributing channel capacity among the various clients according to some predefined rule or algorithm. Common methods for distributing channel capacity may include known polling algorithms.
According to typical polling algorithms, the server may address each client in a predetermined sequence. When a client is polled by a server, the polled client has an opportunity to transfer any data which may be queued. If no data is queued, then the server simply moves to the next client in sequence to see if the next client has data for transfer and so on.
One example of a wireless communication system which uses polling to facilitate channel sharing is described in the publication entitled “Specification of the Bluetooth System”, published by the Bluetooth SIG, v1.0, Jul. 26 ,1999. The Bluetooth (BT) system is an exemplary technology for ad-hoc networking developed for short range wireless connectivity. Bluetooth is based on a short-range, universal radio link, and it provides a mechanism to form small ad-hoc groupings of connected devices, without a fixed network infrastructure, including such devices as printers, PDAs, desktop computers, FAX machines, keyboards, joysticks, telephones, or virtually any device capable of digital communication.
To better appreciate the operation of a Bluetoothstyle system, the following definitions may be useful.
Piconet: a sub-network that is part of a larger Bluetooth (BT) network, a piconet generally includes one master node and one or more slave nodes. The description of the centrally controlled network in the previous section may be applied generally to a Bluetooth piconet with a series of piconets making up a Bluetooth network.
Bluetooth node: a network node in a piconet which may take on the role of either master or slave. A Bluetooth node may also act as a master and simultaneously as a slave in more than one piconet, however, may be master in only one piconet.
Master: a Bluetooth node which may control all traffic in a piconet and which may act as a server node in accordance with the description of the centrally controlled network given above.
Slave: a Bluetooth node which may be controlled by one master and which may act as a client node in the introductory description above. A piconet may host several slaves simultaneously.
As previously described, Bluetooth systems allow for wireless connectivity between, for example, mobile PCs, phones, digital cameras, proximity detectors, and other portable devices. Bluetooth systems may operate on the unlicensed 2.4 Ghz band which poses some risk of connections collision with 802.11 wireless LANs. Bluetooth systems are nevertheless desirable however due to their low power requirements coupled with the shortness of their range, e.g. up to 10 meters making them useful for interoffice wireless applications. While 802.11 wireless LANs operate with ranges up to several hundred feet. It may be important therefore for Bluetooth systems to be tolerant of possible interference from 802.11 wireless LANs.
A wireless channel in a typical Bluetooth system may use time division duplex (TDD) to achieve a bidirectional link between a master and a slave. When data is transferred on the Bluetooth TDD channel, one packet may first be sent from a master to a slave directly followed by a packet sent from a slave to a master. Moreover, the Bluetooth packet size used in either of the directions may occupy, for example, 1, 3, or 5 slots, where one slot is 0.625 ms wide. The Bluetooth specification, supra, may also support circuit switched traffic on a dedicated logical link denoted synchronous connection oriented (SCO) link, as may typically be used for voice applications. Packets associated with an SCO link may be carried periodically, for example, in every slot, in every second slot, or in every third slot. In contrast, traffic on a dedicated logical link not necessarily associated with circuit switching and more oriented toward data transfer as opposed to voice transfer may be denoted as an asynchronous connectionless link (ACL),
In order to control bandwidth utilization and achieve high levels thereof, within, for example, a Bluetooth piconet, a master may control data flow on a communication channel by polling slaves for every data packet sent on the channel in an up-link (UL) direction from the controlled unit to the controlling unit, e.g., slave to master. However, traffic on SCO links is generally sent on an UL without polling in contrast to ACL links where polling is a necessity. A poll from a master node may be in the form of a data packet, thus creating the possibility of a bidirectional data flow on an SCO link at the polling instant if UL traffic is present. In the downlink (DL) direction from the controlling unit to the controlled unit, e.g., master to slave, no polling is generally required to send a packet since slaves are expected to be normally idle unless being polled.
In addition to controlling data flow to and from slaves in most circumstances using polling as described, a master may control packet size used by a slave to achieve precise control of bandwidth and delay in the piconet. Accordingly, control over, for example Quality of Service (QoS) levels, particularly as they relate to delay factors may be achieved. It may be assumed, however, for simplicity in the foregoing and following description unless otherwise noted, that a typical piconet supports best effort (BE) traffic only. Fair distribution of the available resources may nevertheless be applied to the use of polling algorithms even in support of BE traffic.
The particular manner in which a master may poll one or more slaves, is important to ensure proper bandwidth utilization in a piconet. Generally, data traffic within a piconet may exhibit bursty characteristics stemming from, for example, user behavior, application, and protocol mechanisms, e.g., TCP flow control, retransmissions, and the like. For such bursty data traffic, and given that assumption, as described that a Bluetooth piconet supports BE packets, fair distribution of channel resources becomes an important consideration. I may further be important that master-slave pairs having traffic to send be given as much capacity as possible, while maintaining fairness in distribution of channel resources.
Polling algorithms are fairly well known and documented, and several examples may be found in the literature, see, for example, “Queuing Analysis of Polling Models”, Hideaki Takagi, ACM Computing Surveys, Vol. 20, No. 1, March 1988. For a better understanding of however, particularly in the context of Bluetooth piconets, short descriptions of three generic polling algorithms are provided herein below.
A first polling algorithm known in the art is the Round Robin (RR) polling algorithm. RR polling represents a simple way of polling slaves in a piconet. In accordance with RR polling, slave nodes may be polled in sequence according to a circular list. During each polling contact by a master node, each slave node may be allowed to send on
Johansson Niklas
Johansson Per
Burns Doane Swecker & Mathis L.L.P.
Telefonaktiebolaget LM Ericsson (publ)
Vo Nguyen T.
LandOfFree
Batched fair exhaustive polling scheduler does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Batched fair exhaustive polling scheduler, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Batched fair exhaustive polling scheduler will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2938314