`(10) Patent N0.:
`US 6,480,505 B1
`
`Johansson et al.
`(45) Date of Patent:
`Nov. 12, 2002
`
`USOO6480505B1
`
`(75)
`
`(54) BATCHED FAIR EXHAUSTIVE POLLING
`SCHEDULER
`Inventors: Per Johansson, Hagersten (SE); Niklas
`h
`L d SE
`J0 ansson,
`un (
`)
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`( * ) Notice:
`
`(21) Appl. No.: 09/455,172
`
`(22)
`
`Filed:
`
`Dec. 6: 1999
`
`(51)
`
`Int. Cl.7 ................................................ H04L 12/28
`
`(52) US. Cl.
`
`(58) Field of Search
`
`........................................ 370/449: 370/329
`’
`370/431 449
`370 329 346‘ 455 450
`’
`/
`/
`’
`
`(56)
`
`References Cited
`
`U~S- PATENT DOCUMENTS
`5,051,984 A
`9/1991 Mostafa et a1.
`5,056,085 A
`10/1991 Vu
`5,065,399 A
`11/1991 Hasegawa et a1.
`5,173,689 A
`12/1992 Kusano
`5,235,599 A
`8/1993 Nishimura et a1.
`597199861 A
`2/1998 Okanoue
`57740366 A
`4/1998 Mahany et ‘11:
`5’748’611 A
`5/1998 Allen et al‘
`FOREIGN PATENT DOCUMENTS
`
`5;
`EP
`EP
`EP
`GB
`WO
`WO
`
`0033332431 A2
`0 715 478 A2
`0883265
`0913965
`2 229 895 A
`9911025
`9923799
`
`13133:
`11/1995
`12/1998
`5/1999
`2/1990
`3/1999
`5/1999
`
`OTHER PUBLICATIONS
`Takagi, Hideaki, “Queuing Analysis of Polling Models”,
`ACM Computing Surveys, V01‘ 20’ NO‘ 1’ Mar. 1988‘
`Johansson Per et al. “Short Range Radio Based Ad—hoc
`’
`’
`’
`Networking: Performance and Properties”, Proceedings of
`International Conference on Communications (ICC ’99),
`Jun 6-10, 1999
`L.
`t
`t.
`d
`t
`.
`.
`(
`IS con mue on neX page )
`PrLmary Exammer—Nguyen T- V0
`(74) Attorney, Agent, or Firm—Burns, Doane, Swecker &
`Mathis, L.L.P.
`
`(57)
`
`ABSTRACT
`
`A method and apparatus for improving channel utilization
`and throughput in an ad-hoc wireless communication system
`is provided. A master unit and one or more slave units are
`coupled to a shared communication channel having at least
`an uplink (UL) channel and a downlink channel (DL) for
`each master unit-slave unit pair. A group 0f active nodes is
`established corresponding to slave units having UL and/or
`DL data associated therewith for transfer. The group of
`active nodes may be polled according to Fair Exhaustive
`Polling (FEP) and information alternately transferred on a
`TDD. Accumulated information may be transferred in a
`batch and feedback information collected and used to adjust
`polling. One or more links may be identified as lossy links
`due to increased Bit Error Rate (BER) and accompanying
`information loss resulting in lower throughput. Virtual
`active nodes added to the group of active nodes to compen-
`sate therefor. A transmission parameter such as number of
`retransmissions may be evaluated against a predetermined
`threshold to identify lossy links. If lossy links improve,
`virtual active nodes may be removed from the group of
`active nodes. Information associated with the one or more
`slaves units may be circuit switched synchronous informa-
`tion or non-circuit switched asynchronous information.
`Feedback information such as timeout informationassoci-
`ated With the slave units may be evaluated. If a time out
`Signal assoc1ated With a slave unite is received the slave umt
`may be scheduled for polling responsive to the time out
`signal
`
`18 Claims, 4 Drawing Sheets
`
`my
`
`
`
`
`
`
`(Io
`
`/
`
`
`
`//l
`
`W
`
`S
`
`62/54/75
`{SM/f5}
`
`
`
`
`
`
`
`
`
`
`
`
`l *
`
`2—412
`
`
`J—r'
`II]
`
`M
`
`//4
`
`
`
`
`
`
`
`Ilia
`
`5M”)? (MS/Tl?)
`
`1
`
`APPLE 1011
`
`APPLE 1011
`
`1
`
`
`
`US 6,480,505 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`“Specification of the Bluetooth System”, Bluetooth SIG,
`vol. 0, Jul. 24, 1999; pp. 35—40 and pp. 121—122.
`Albrecht, M.,et al., “IP Services over Bluetooth: Leading the
`Way to a New Mobility”, Proceedings of the Conference on
`Local Computer Networks, Oct. 1999.
`Tode, H., et al., “A Routing Method Using a Tunable Cost
`Function to Obtain Required Communication Quality and
`
`Performance”, Electronics and Communications in Japan,
`Part 1. vol, 81, No. 5, 1998.
`
`Haartsen, J., “Bluetooth—The Universal Radio Interface for
`
`Ad Hoc, Wireless ConnectiVity”, Ericsson ReVieW No. 3
`
`(1998), pp. 110—117.
`
`Copy of European Search Report issued on Jun. 5, 2000.
`
`2
`
`
`
`US. Patent
`
`Nov. 12, 2002
`
`Sheet 1 0f 4
`
`US 6,480,505 B1
`
`ESdV.»
`
`3“.waa:
`
` Q3
`
`QfimwfiEta.
`
`\“gnx
`
`3
`
`
`
`US. Patent
`
`US 6,480,505 B1
`
`m\b
`
`mum
`
` Efifiw m§3:,2,w_%§E§$\mwwfiw-(.3.
`
`m.\Ha\mSVNe
`
`v.3%Exm5&stb§§
`EEQREE
`E\§
`
`QEMVS
`
`__
`
`N6\.u\
`
`4
`
`
`
`US. Patent
`
`Nov. 12, 2002
`
`Sheet 3 0f 4
`
`US 6,480,505 B1
`
`$§§§
`
`§Q§§m§§§<
`
`§M
`
`SN“.SQ,
`
`§$E
`
`QNM
`
`ESQQV
`
` §§§QK$4Sfixfim
`
`\SSSQ
`
`£3E$§$§w
`
`:EVE,
`
`bagk
`
`\§-w§\.\
`
`fixafik§
`
`gm.
`
`
`
`\3x§§x\SGVK
`
`fififiaflfifififi
`
`EENSQVmRSm.
`
`5
`
`
`
`
`
`
`
`
`
`US. Patent
`
`Nov. 12, 2002
`
`Sheet 4 0f4
`
`US 6,480,505 B1
`
`
`
`(ll/HM
`
`75 [000 00,4 050 500500150
`
`
`PAé‘lff/M/l 0145/5
`
`
`75.5
`
`
`
`
`50050015 001/
`05 MY 0005
`
`(50 00/
`
`
`
`400
`
`\
`
`4/0
`
`4Z0
`
`
`
`500500.45
`0517 040157
`(50 00/
`
`
`
`
`
`
`
`50050015
`
`7/1/5007 05
`
`00/1 05 70/5
`430
`M)’ my
`0005
`
`
`
`500 //V.5'<4//05
`
`
`005015 01/507
`,407/V/7)’ 55500140!
`
`
`
` M’)’ 050’ ,407/V5 00055?
`
`
`A00 70/5/70555
`0005/57 70 M
`
`
`[10/ 005
`
`0/77 0005 //7 M
`
`70/5/70555 0005/57
`
`000-A07/V5/
`500/! M’
`
`
`
`
`
`
`
`
`
`
`
`
`ASS/6W 70/5 0005
`AW 0005
`A5 4 00/70/11
`flffflA/lS/l/f>
`
`
`A07/V5 0005 /// '40
`mam a z
`
`
`
`
`
`'F/G. 4
`
`6
`
`
`
`US 6,480,505 B1
`
`1
`BATCHED FAIR EXHAUSTIVE POLLING
`SCHEDULER
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`invention is related to the following
`The present
`co-pending applications: Ser. No. 09/455,168 entitled
`“ROUTE
`UPDATING
`IN
`BLUETOOTH
`
`SCATTERNETS”, by T. Larsson, et al; Ser. No. 09/696,242,
`entitled “ROUTE DISCOVERY BASED PICONET
`
`FORMING”, by T. Larsson, et al; Ser. No. 09/455,460
`entitled “BROADCAST AS A TRIGGERING MECHA-
`NISM FOR ROUTE DISCOVERY IN BLUETOOTH
`
`SCATTERNETS”, by T. Larsson, et al; Ser. No. 09/454,758
`“INTER-PICONET SCHEDULING ALGORITHM”, by
`Per Johansson, all incorporated herein by reference.
`
`BACKGROUND
`
`invention relates to data communication
`The present
`systems for transferring information in packets and more
`particularly, to scheduling packets in a wireless communi-
`cations network using polling.
`In many conventional packet-oriented data communica-
`tions networks, the data traffic between units may be con-
`trolled 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, commu-
`nications channels between a server unit and client units are
`
`generally bidirectional and may use either wireline or wire-
`less 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. Aserver
`unit in such a network is therefore responsible for distrib-
`uting 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 oppor-
`tunity 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 con-
`nectivity. 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 com-
`munication.
`
`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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`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 con-
`trolled 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 connec-
`tions collision with 802.11 wireless LANs. Bluetooth sys-
`tems 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 con-
`nectionless 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
`7
`
`7
`
`
`
`US 6,480,505 B1
`
`3
`
`over, for example Quality of Service (QoS) levels, particu-
`larly 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 distribu-
`tion 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 utili-
`zation 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 distribu-
`tion 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 accord-
`ing to a circular list. During each polling contact by a master
`node, each slave node may be allowed to send one or more
`packets the size of which may be fixed at 1,3, or 5 time slots
`as previously described. Likewise, a master node may send
`one or more DL packets to a slave node only during a polling
`contact preferably in a one-for-one exchange as may be
`associated with, for example, a TDD channel as previously
`described. Assuming packets having single slot durations,
`the bandwidth share per master-slave pair, CMSpm-r in a
`pico-net with N nodes including a master node and no SCO
`traffic may be expressed by Equation (1) as follows:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`C
`CMSpair = N— 1,
`
`(1)
`
`45
`
`where C is the total link capacity in the piconet. If packets
`occupy more than one time slot, CMSpm-r could be greater
`than that given in Equation (1) where CMS
`may now be
`expressed by Equation (2).
`pm
`
`CMSpair =
`
`
`5C
`5+N—2
`
`(2)
`
`Equation (2) may be applied to a case where one master-
`slave pair is active and packets occupying, for example, as
`many as 5 time slots are used. Simulations have shown that
`the use of multislot packets may significantly improve the
`handling of bursty traffic, as may be described in,
`for
`example, “Short Range Radio Based Ad-hoc Networking:
`Performance and Properties”, P. Johansson, N. Johansson,
`U. Korner, J. Elg, G. Svennarp, Proceedings of International
`Conference on Communications (ICC’99), Jun. 6—10 1999.
`A second known polling algorithm may be referred to as
`Exhaustive Polling (EP). EP allows channel capacity to be
`dynamically focused to a master-slave pair most in need of
`
`50
`
`55
`
`60
`
`65
`
`4
`greater capacity. EP algorithms conduct a poll of all active
`slave nodes in a circular fashion similar to RR polling.
`However, when a slave node having data to transfer, e.g. a
`non-empty UL queue, is polled by a master, the EP algorithm
`allows the slave to continue transferring data until the UL
`queue has been emptied. If new packets are queued prior to
`emptying a queue, the new packets are also transferred. It is
`important to note that when conducting EP, for example, in
`a Bluetooth piconet,
`the sum of the UL and DL queue
`contents for a particular master-slave pair should be taken
`into consideration since the channel
`is bidirectional.
`Otherwise, a master node may be polled separately to
`complete the EP cycle. It should further be noted, however,
`that EP schemes have inherent fairness problems since a
`slave having dominant flow of data to transfer may seize the
`shared channel for a long period of time; since new packets
`may arrive continuously, the time period may be indefinite.
`If no admission control is performed on a per piconet
`basis, for example, by placing a limit on total traffic load
`between any particular master-slave pair,
`traffic streams
`associated with other master-slave pairs may get starved for
`indefinite time periods. If admission control is performed,
`the use of EP schemes may still result in very high delay
`variations, but will still provide high channel utilization. It
`should be noted that in order to achieve high throughput,
`packets should be as long as possible once data is sent
`to/from a slave. By increasing packet length, overhead per
`packet may be reduced thus increasing throughput for each
`master slave pair. Tradeoffs between packet size and packet
`overhead along with other link requirements may need to be
`considered to find optimal utilization and throughput. For
`example, packets occupying up to five time slots may
`provide good utilization, provided that, for example, SCO
`links are not present.
`A third known polling algorithm may be referred to as
`Gated Polling (GP). To counter starvation problems associ-
`ated with EP schemes, Gated Polling (GP) may be used.
`Polling characteristics similar to EP may be applied gener-
`ally in GP, however a slave’s UL queue may be emptied up
`to the number of packets that were present when the polling
`interval began. Thus, new packets queued after polling
`begins are not transferred until the next polling interval.
`Subsequent nodes are polled in a similar manner according
`to a predetermined sequence, e.g. circular.
`GP may prevent nodes starvation during bursty traffic
`conditions, however fairness must be considered on a per
`burst level, e.g. a node with long bursts queued upon polling
`will transfer more data than nodes with smaller queue levels.
`Moreover, overall delay variation may be higher than for EP
`since data transfer flow is disrupted and delayed until the
`next polling interval. Since the beginning of the next interval
`is dependent on queue levels associated with other slave
`nodes it will occur at a random time.
`
`It should be noted that channel utilization may be lower
`in GP than in EP schemes since polling after a “gated” flow
`may result in a sequence of polls of empty queues, or empty
`poll packets, until the previously gated flow is resumed
`again during the next poll interval of that queue. As with EP,
`packets should be as long as possible, e.g. occupy as many
`time slots as possibly, once data is sent from a queue.
`Although some shortcomings of the above described and
`well known polling schemes have been indicated in terms of
`delivering efficient and fair service to various slave nodes in
`a network, several additional problems arise when contem-
`plating which polling algorithm is best suited for use in a
`Bluetooth system.
`A first problem may arise in that it may be possible for
`some slave units to have delay tolerance requirements which
`8
`
`8
`
`
`
`US 6,480,505 B1
`
`5
`the maximum time between two successive poll
`affect
`intervals. Accordingly, any polling algorithm used must
`ensure that nodes having such delay tolerance requirements
`are serviced by a master unit within the required time limits.
`Asecond problem may arise in that additional traffic types
`other than BE traffic may generally be controlled by the
`master unit. For example, data packets carrying information
`for circuit emulation services or network management may
`be handled by a master unit. Accordingly, any polling
`algorithm used in such a situation must allow transmission
`of a diversity of packets types in accordance with the
`requirements unique to each particular service which means
`that assumptions related to BE transmission may not be
`valid when different data types are being handled.
`A third problem may arise in that a delay may exist
`between a point in time when a master unit decides to poll
`a particular slave unit and the point in time when the poll is
`actually conducted. Usually, this delay is seen as the delay
`between when a polling instant actually begins at the master
`and when a polling packet is sent to, or received at the slave
`unit. Such a delay may be the result of batched information
`exchange, e.g. pre-scheduling a certain number of packets
`before actually being queued at the master unit’s transceiver.
`Such a delay gives rise to cumulative delay in that an
`ultimate reaction by a master unit based on a delayed
`response from a slave unit will also be delayed. For any
`polling algorithm used in such a situation polling delay
`could mean that a master must handle the corresponding
`delays in any feedback information originating from the
`slave units.
`
`It would therefore be desirable to provide a polling
`method for conducting polling in, for example, a Bluetooth
`or similar ad-hoc wireless system, which fairly distributed
`channel access between a master and one or more slave
`
`units, and which provides improved channel utilization.
`
`SUMMARY
`
`It is therefore an object of the present invention to provide
`a method for improving the performance of polling based
`packet switching communication systems such as Bluetooth
`piconet systems.
`It is a further object of the present invention to improve
`delay factors by taking into account batched information
`exchange between a master and one or more slaves.
`Therefore, in accordance with one aspect of the present
`invention, the foregoing and other objects are achieved in a
`method for improving channel utilization and throughput in
`an ad-hoc wireless communication system having a master
`unit and one or more slave units, the master unit configured
`to control the one or more slave units, coupled with a shared
`communication channel having at
`least an uplink (UL)
`channel and a downlink channel (DL)
`for each master
`unit-slave unit pair. The method may have steps including
`establishing a group of active nodes corresponding to one or
`more of the one or more slave units having UL and/or DL
`data associated therewith for transfer; polling the group of
`active nodes according to Fair Exhaustive Polling (FEP);
`alternately transferring information between the master and
`a next slave unit as polled according to FEP. It should be
`noted that alternately transferring may be as a result of a
`Time Division Duplex link established therebetween.
`In accordance with another embodiment of the invention,
`information may be accumulated to be transferred to the
`next slave unit and one or more subsequently polled slave
`units in a batch, and respective portions the batch of infor-
`mation may alternately be transferred between the next slave
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`unit and the one or more subsequently polled slave units
`during a polling interval associated with each of the next
`slave unit and the one or more subsequently polled slave
`units. Feedback information may be collected regarding the
`slaves and used to adjust polling.
`In accordance with still another embodiment of the inven-
`tion one or more links associated with the one or more slave
`
`units may be identified as lossy links due to, for example,
`increased Bit Error Rate (BER) and accompanying infor-
`mation loss resulting in a lower throughput. Accordingly,
`one or more virtual active nodes may be added to the group
`of active nodes, wherein one or more of the one or more
`virtual active nodes is associated with the each of the
`
`identified one or more lossy links. Virtual active nodes may
`allow additional polling time to be allocated to lossy links.
`Such determination may be made by evaluating a transmis-
`sion parameter against a predetermined threshold for each of
`the one or more links and wherein if the threshold is
`
`exceeded the link is identified as lossy, and wherein if the
`threshold is not exceeded the link is not identified as lossy.
`The predetermined threshold may include for example, a
`retransmission parameter. When the one or more links
`associated with the one or more slave units are no longer
`lossy the one or more virtual active nodes corresponding
`thereto may be removed from the group of active nodes.
`In accordance with yet another embodiment of the present
`invention, information transferred between the master and
`one or more slaves may be associated with one or more of
`circuit switched synchronous information and non-circuit
`switched asynchronous information. It may further be pos-
`sible to evaluating feedback information associated with the
`one or more slave units to determine for example whether
`the UL queue is empty or the like and thus polling may be
`suspended for such a slave unit. Further, during polling, a
`time out signal may be received associated with one or more
`of the one or more slave units. Accordingly the correspond-
`ing timed out slave units may be scheduled for polling
`responsive to the time out signal.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The objects and advantages of the invention will be
`understood by reading the following detailed description in
`conjunction with the drawings, in which:
`FIG. 1 is a diagram illustrating an exemplary Fair Exhaus-
`tive Polling (FEP) embodiment
`in accordance with the
`present invention;
`FIG. 2 is a diagram illustrating an exemplary batched FEP
`scheduling system in accordance with the present invention;
`FIG. 3 is a block diagram illustrating portions of an
`exemplary FEP embodiment; and
`FIG. 4 is a flow chart illustrating exemplary steps in a
`method in accordance with the present invention.
`DETAILED DESCRIPTION
`
`invention a
`Therefore in accordance with the present
`method and apparatus are provided which improve perfor-
`mance of a polling based packet switched communication
`system.
`In order to introduce fair behavior into a polling scheme
`that also has high channel utilization, RR and EP polling
`schemes as described above may be combined in one
`embodiment of the present invention into a new scheme,
`which may be referred to herein as Fair Exhaustive Polling
`(FEP). In accordance with one embodiment of FEP as is
`illustrated in FIG. 1, communication network 100 is shown
`
`9
`
`9
`
`
`
`US 6,480,505 B1
`
`7
`having master 110, where FEP 120 may be implemented,
`and one or more slaves 130—132. A group of active nodes,
`AN 115, may be maintained containing Nan number of nodes
`which may correspond to, for example, DL queues 111—114
`containing one or more packets destined for, for example,
`slave nodes 130—132 and master node 110. It should be
`
`noted that packets destined for master 110 may be queued as
`appropriate at each slave node 130—132 in UL queues
`130a—132a respectively. Slave nodes 130—132 and master
`node 110 may have non-empty UL queues 130a—132a and
`DL queues 111—114 respectively and accordingly, a RR
`scheduling of UL queues 130a—132a and DL queues
`111—114 may be conducted by master 110 until exhausted.
`To best understand the present embodiment, an example
`may be presented. When, for example, output queue 112
`associated with, for example, a slave node has sent all
`packets stored therein and the corresponding DL queue is
`also empty, the node is withdrawn from group AN 115, thus
`Nan=Nan—1.
`If all DL queues 111—114 associated,
`for
`example, with slave nodes 130—132 and all corresponding
`UL queues 130a—132a associated with slaves 130—132
`become empty, FEP 120 in master 110 may continue to poll
`in a RR fashion until a node has something to send on either
`an UL or DL. It should be noted that in order for a node to
`
`be removed from group AN 115, both UL and DL queues
`must be empty. If, for example, an UL queue is emptied
`before its corresponding DL queue is empty, or vice versa,
`NULL packets may be sent from the slave node with an
`empty queue to ensure that something is sent for every
`interval in the TDD link. If a DL queue empties before the
`UL queue, the master may send empty POLL packets to fill
`the link. In the case when FEP 120 is applied to a Bluetooth
`network, AN 115 may consist of master-slave pairs with
`packets in either UL queues 130a—132a or DL queues
`111—114. In order to add new master-slave pairs into group
`AN 115, others of, for example, slaves 130—132 may be
`polled periodically to determine which slave have UL data
`or if master 110 has DL destined for one or more of slaves
`
`130—132, at which point a slave ID may be added to group
`AN 115. For a Bluetooth system, a TF0” parameter may be
`individually maintained for each node and used to define the
`longest polling interval
`for each particular one of,
`for
`example, slaves 130—132. Packet size selection may further
`be made in order to reduce or minimize overhead, e.g. set
`packet
`length equal
`to data length.
`It should be noted
`however that in such a case where a large amount of data is
`present, and a long packet length is likely to result, TF0”
`should preferably be taken into account. It should be noted
`that since TF0” may vary per node, the node with the shortest
`or smallest value for TF0” will have the most significant
`effect. Moreover, the number of nodes in group AN 115 will
`also have an effect since a correspondingly larger “distance”
`will be created between nodes from a polling standpoint.
`In another embodiment of the present invention, as illus-
`trated in FIG. 2, FEP 120 may be assumed to operate in an
`environment where packet transmissions may be delayed
`due to one of many possible implementations or transmis-
`sion protocols. Instead of scheduling packets in a continuous
`flow, packet batch 140 may be issued in accordance with the
`present embodiment for transmission to, for example, slave
`units 130—132 at a particular interval when, for example, a
`batch size limit, or similar parameter has been reached.
`While packet batch 140 is being transmitted by transceiver
`150, a next batch may be formed in accordance with, for
`example, an FEP algorithm, or the like which employs, for
`example, RR polling as described herein above on, for
`example, DL queues 111—114. The new packet batch 140
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`for example, on feedback
`may additionally be based,
`received via feedback block 160 which may accordingly
`include information obtained related to the current packet
`batch 140 being transmitted and possibly on earlier packet
`batches 140. For example, feedback block 160 may gather
`information about the activity level of slave units 130—132.
`Feedback gathered in this manner by feedback block 160
`may allow FEP 120 to decide, for example, which of slave
`units 130—132 may be regarded as idle or if UL packet size
`should be increased or decreased. In accordance with the
`
`if a Bluetooth piconet system is
`present embodiment,
`involved, UL and DL packet size may be adapted to allow
`simultaneous use of circuit emulation channels, such as SCO
`channels. As previously noted, short TF0” intervals may also
`place a practical limit on packet size. In addition, bit error
`rates associated with the communication channel may be at
`a level where shorter packet sizes may yield a better
`throughput than longer.
`FIG. 3 is a block diagram illustrating an exemplary
`communication network 300 with additional exemplary
`details of FEP block 350 in accordance with yet another
`embodiment of the present invention. It should be noted that
`the details described herein below with regard to FEP 350
`may also be applied to FEP 120 in the context of the
`descriptions of FIG. 1 and FIG. 2. In accordance with the
`present embodiment, data packets from non-empty buffers
`from, for example, buffer block 330 may be scheduled for
`transmission in scheduler 351 according to, for example, a
`RR algorithm as described herein above. In addition, poll
`packets may sent towards slave units having packets to send
`in the UL direction as described with reference to previous
`embodiments. AN group 356, may keep track of master-
`slave pairs where either a slave or a master has packets to
`send.
`In time-out register 353,
`time-out parameters for
`slaves that need to be polled within certain periods of time,
`as might be associated, for example, with special QoS
`requirements as described herein above, may be stored. In
`addition, time-out register 353 may initiate input to sched-
`uler 351 to interleave packet exchanges with special QoS
`requirement slaves when respective time-outs expire. Addi-
`tional reasons for slave time-outs coul