US006480505B1
`(10) Patent No.:
`a2) United States Patent
`US 6,480,505 B1
`Johansson et al.
`(45) Date of Patent:
`Nov. 12, 2002
`
`
`(54) BATCHED FAIR EXHAUSTIVE POLLING
`SCHEDULER
`
`(75)
`
`Inventors: Per Johansson, Hagersten (SE); Niklas
`h
`Lund (SE
`Johansson,
`Lund
`(SE)
`(73) Assignee: Telefonaktiebolaget LM Ericsson
`(publ), Stockholm (SE)
`Subject to any disclaimer, the term ofthis
`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) Unt, CL.cceccccccceccccccssseesssteeseeeseesen HO4L 12/28
`
`(52) US. C1. cececneeeneeecscteneseneenees 370/449; 370/329
`,
`370/431, 449
`(58) Field of Search
`370/329, 346: 455/450
`,
`/
`1329,
`
`(56)
`
`rp
`EP
`EP
`EP
`GB
`WO
`WO
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,051,984 A
`9/1991 Mostafaetal.
`5,056,085 A
`10/1991 Vu
`5,065,399 A
`11/1991 Hasegawaetal.
`5,173,689 A
`12/1992 Kusano
`5,235,599 A
`8/1993 Nishimuraetal.
`5,719,861 A
`2/1998 Okanoue
`5,740,366 A
`4/1998 Mahanyetal.
`5,748,611 A
`5/1998 Allenet al.
`FOREIGN PATENT DOCUMENTS
`nooved A2 Stoo
`0715 478 A2
`11/1995
`0883265
`12/1998
`0913965
`5/1999
`2 229 895 A
`2/1990
`9911025
`3/1999
`9923799
`5/1999
`
`OTHER PUBLICATIONS
`
`Takagi, Hideaki, “Queuing Analysis of Polling Models”,
`ACM Computing Surveys, vol. 20, No. 1, Mar. 1988.
`Johansson, Per, et al., “Short Range Radio Based Ad-hoc
`an
`?
`Networking: Performance and Properties”, Proceedings of
`International Conference on Communications (ICC ’99),
`Jun. 6-10, 1999.
`List
`ti
`d
`t
`.
`;
`¢ ist continued on next page.)
`Primary Examiner—Nguyen T. Vo
`(74) Attorney, Agent, or Firm—Burns, Doane, Swecker &
`Mathis, L.L.P.
`ABSTRACT
`(57)
`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 havingat least
`an uplink (UL) channel and a downlink channel (DL) for
`cach master unit-slave unit pair. A group of 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 information associ-
`ated with the slave units may be evaluated. If a time out
`signal associated with a slave unite is received the slave unit
`may be scheduled for polling responsive to the time out
`signal.
`
`18 Claims, 4 Drawing Sheets
`
`100
`
`
`Ho
`
`
`0
`Wa
`
`
`
`
`
`i
`2
`
`L112
`
`TN
`
`3
`if
`
`
`
`
`
`CLIENTS
`(SLAVES)
`
`
`
`
`
`
`—
`
`H4
`
`SERVER (MASTER)
`
`‘ ila
`'
`
`
`
`
`
`132a
`
`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.,etal., “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
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 1 of 4
`
`US 6,480,505 B1
`
`OO!
`
`SLNH19
`
`(STAVTS)
`
`YINYTS
`
`fOA
`
`(YTLSVW)
`
`3
`
`

`

`LIVIVd Of!
`
`YINFISNVEL
`
`HILVG
`
`OGt
`
`OF
`
`oOA
`
`
`
`(YLLSYW)HINES
`
`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 2 of 4
`
`US 6,480,505 B1
`
`SLNT177
`
`(STAV7S)
`
`/E1
`
`OE!
`
`00¢
`
`Lhdlho
`
`SINFO
`
`LNH19Hid
`
`(INAVTS)
`
`4
`
`

`

`U.S. Patent
`
`Nov. 12, 2002
`
`Sheet 3 of 4
`
`US 6,480,505 B1
`
`OO£
`
`YTLNNOI
`
`NOISSINSNVELTY
`
`
`
`O¢£
`
`ALIAHIV
`LNH79
`
`NIVE0IF
`
`LIM
`
`GTHOLIMS
`
`SMOTI
`
`wl.
`
`SHOTS
`
`YUSIITY
`
`Mo-mlESE
`
`aLGUi
`
`
`
`
`
`(W)AVEEVLINDVE
`
`||o[o||4)o)o|%
`
`YINIFISWVYLOe
`
`5
`
`
`
`
`
`

`

`U.S. Patent
`
`Nov.12, 2002
`
`Sheet 4 of 4
`
`US 6,480,505 B1
`
`
`
`TE LOOP ON A PER SCHEDULED
`
`
`PACKET/POLL BASIS
`
`(MNFIAI
`4900Ne
`
`YES
`
`
`
`
`
`
`410
`
`420
`
`430
`
`SCHEDULE POLL
`OF ANY NODE
`
`(EG. RR)
`SCHEDULE
`NEXT PACKET
`(EG. RR)
`
`
`
`
`
` SCHEDULE
`TIMEOUT OF
`POLL OF THIS
`
`ANY NODE?
`Wwe
`
`FOR INSTANCE
`
`
`CHECKS: CLIENT
`ACTIVITY FEEDBACK
`
`
` ANY NEW ACTIVE NODES?
`
`ADO THIS/THESE
`NODE(S) TO AN
`
`
`THIS/THESEMODES)
`
`
`
`
`
`ANY NODE IN AN
`YES
`
`
`ANY NODE
`
`RETRAWSMIT>
`
`
`THRESHOLD ?
`
`
`
`ASSIGN THIS NODE
`AS A VIRTUAL
`ACTIVE NODE IW AN
`
`FIG. 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 moreclients. A server
`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 movesto the next client in
`sequenceto 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 mayalso 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 controlall 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 usefulfor interoffice
`wireless applications. While 802.11 wireless LANsoperate
`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.
`
`Awireless 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 packetsize
`used in either of the directions may occupy, for example, 1,
`3, or 5 slots, where oneslot is 0.625 ms wide. The Bluetooth
`specification, supra, may also support circuit switchedtraffic
`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 maybe in the form of a data packet, thus
`creating the possibility of a bidirectional data flow on an
`SCO linkat the polling instant if ULtraffic 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 circumstancesusing 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 BEtraffic.
`The particular manner in which a master maypoll 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 havingtraffic to send be given as much
`capacity as possible, while maintaining fairness in distribu-
`tion of channel resources.
`Polling algorithmsare fairly well known and documented,
`and several examples may be foundinthe 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 wayofpolling 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 maybefixed 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, Cagspair IN a
`pico-net with N nodesincluding a master node and no SCO
`traffic may be expressed by Equation (1) as follows:
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`Cc
`Cuspair = Wel’
`
`qd)
`
`45
`
`4
`greater capacity. EP algorithms conduct a poll ofall 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 dominantflow 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 numberof 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 nodesstarvation during bursty traffic
`conditions, however fairness must be considered on a per
`burst level, e.g. a node with long bursts queued uponpolling
`will transfer more data than nodes with smaller queue levels.
`whereCis the total link capacity in the piconet. If packets
`Moreover, overall delay variation may be higher than for EP
`occupy more than one timeslot, Cyys,.i- could be greater
`since data transfer flow is disrupted and delayed until the
`than that given in Equation (1) where Cy,<,,.;-
`May now be
`expressed by Equation (2).
`—
`next polling interval. Since the beginning of the nextinterval
`is dependent on queue levels associated with other slave
`nodes it will occur at a random time.
`
`Cspair =
`
`5c
`S+N-2
`
`50
`
`Q)
`
`Equation (2) may be applied to a case where one master-
`slave pair is active and packets occupying, for example, as
`many as 5 timeslots are used. Simulations have shownthat
`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, Proceedingsof International
`Conference on Communications (ICC’99), Jun. 6-10 1999.
`A second knownpolling algorithm maybereferred to as
`Exhaustive Polling (EP). EP allows channel capacity to be
`dynamically focused to a master-slave pair most in need of
`
`55
`
`60
`
`65
`
`It should be noted that channel utilization may be lower
`in GP than in EP schemessince polling after a “gated” flow
`may result in a sequenceof 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 knownpolling schemeshave 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
`someslave 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 mayarisein that additionaltraffic types
`other than BEtraffic 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 whenthe poll is
`actually conducted. Usually, this delay is seen as the delay
`between whena polling instant actually begins at the master
`and whena polling packet is sentto, or received at the slave
`unit. Such a delay maybethe result of batched information
`exchange, e.g. pre-scheduling a certain numberof packets
`before actually being queuedat 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 channelutilization.
`
`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 moreslaves.
`Therefore, in accordance with one aspect of the present
`invention, the foregoing and other objects are achieved in a
`method for improving channelutilization 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 correspondingto 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 embodimentof 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 mayalternately 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 maybe collected regarding the
`slaves and used to adjust polling.
`In accordance with still another embodimentof 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 morevirtual 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 madeby 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 exceededthe 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 embodimentof 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 moreslave 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 bereferred 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 N,,, 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
`Nuz=Nun-l.
`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 continueto 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,
`NULLpackets 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 tofill
`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 T,,,,; parameter may be
`individually maintained for each nodeand usedto 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
`howeverthat in such a case where a large amountof data is
`present, and a long packet length is likely to result, T,,,,
`should preferably be taken into account. It should be noted
`that since T,,,, may vary per node, the node with the shortest
`or smallest value for T,,,,, will have the most significant
`effect. Moreover, the numberof 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 embodimentof 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 maybeissued in accordance with the
`present embodimentfor 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 regardedasidle or if UL packet size
`should be increased or decreased. In accordance with the
`present embodiment,
`if a Bluetooth piconet system is
`involved, UL and DL packet size may be adapted to allow
`simultaneoususe of circuit emulation channels, such as SCO
`channels. As previously noted, short T,,,,, intervals may also
`place a practical limit on packet size. In addition, bit error
`rates associated with the communication channel may beat
`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
`embodimentof 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 towardsslave 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 could be due to delay
`constrained services as might be posed by, for example, SCO
`links in Bluetooth systems,
`represented in the present
`embodimentby circu