USOO7079508B2
`
`(12) Unlted States Patent
`(10) Patent No.:
`US 7,079,508 B2
`
`Ayyagari et a].
`(45) Date of Patent:
`Jul. 18, 2006
`
`(54) QUALITY OF SERVICE OVER PATHS
`HAVING A ‘VIRELESS-LINK
`
`(75)
`
`Inventors; Arun Ayyagaria Seattle, WA (US);
`Yoram Bernet, Seattle, WA (US);
`(Tlig’thy M' Moore: Belle/“lea WA
`
`(73) Assignee: Microsoft Corporation, Redmond, WA
`(US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent 15 extended or adjusted under 35
`U'S'C' 154(1)) by 700 days.
`
`.
`(21) Appl. No.. 09/792,765
`(22)
`Filed:
`Feb. 22, 2001
`
`6,522,661 B1*
`6,553,006 B1 *
`6,714,987 B1 *
`
`2/2003 Min ........................... 370/445
`4/2003 Kalliokulju et al.
`........ 370/310
`3/2004 Amin et al.
`............ 709/249
`
`6,721,331 B1*
`4/2004 Agrawal et al.
`...... 370/448
`6,738,361 B1 *
`5/2004 lmmonen et al.
`........... 370/328
`FOREIGN PATENT DOCUMENTS
`WO 99/21313 A2
`4/1999
`
`W0
`
`(Continued)
`
`OTHER PUBLICATIONS
`.1050 L., et al., Quality-of—Service in Ad Hoc
`Sobrinho,
`Carrier Sense Multiple Access Wirelss Networks, IEEE
`Journal on Selected Areas in Communications, 17(8):353-
`1368, (Aug. 1999).
`
`.
`(Continued)
`
`(65)
`
`Prior Publication Data
`US 2001/0024434 A1
`Sep. 273 2001
`
`Primary ExamineriAlpus H. Hsu
`(74) Attorney, Agent, or Firm7Wolf, Greenfield, & Sacks,
`P.C.
`
`Related US. Application Data
`(60) Provisional application No. 60/184,290, filed on Feb.
`23, 2000.
`
`57
`
`(
`
`)
`
`ABSTRACT
`
`(51)
`
`Int C1
`(2006 01)
`H04L 12/413
`(2006.01)
`H04Q 7/00
`.
`.
`/
`.
`.
`(52) US. Cl.
`...................... 370/329, 37034222015132,
`_
`_
`_
`'
`(58) Fleld 0f (33;?)s/szlgi9c1130811 4%??28236447 5170/33
`’370/3’49.
`’709/é49 £00. ’455/252 2’
`fil
`f
`’
`1
`’
`h h
`’
`.
`1.
`e or comp ete searc
`1story.
`ee app 1catron
`References Cited
`U.S. PATENT DOCUMENTS
`
`S
`
`(56)
`
`The invention provides Quality of Service assurances in a
`manner expected in other media to communications over
`paths that include one or more wireless links. The invention
`combines a subnet bandwidth manager (“SBM”) at an
`access point (“AP”) to track allocations of wireless band-
`width. The invention further incorporates multiple priority
`levels for packet transmission in a two-prong stochastic
`scheme. The first prong reserves bandwidth at each of the
`intermediate nodes in a transmission path subject to a veto
`by any intermediate node. The second prong modulates the
`transmission probability of a packet based on the previous
`failed attempts at transmission and the priority level of the
`packet. The overall result of this hybrid scheme is to not shut
`out users with the lowest priority, e.g., “best effort” priority,
`while assuring adequate bandwidth to higher priority appli-
`cations.
`
`29 Claims, 6 Drawing Sheets
`
`505
`
`510
`
`7/1994 Diepstraten et al.
`5,329,531 A *
`........ 370/347
`5,572,528 A * 11/1996 Shuen ..................... 370/402
`
`2/2000 Turina ........................ 370/348
`6,031,832 A *
`6,069,882 A *
`5/2000 Zellner et al.
`.............. 370/329
`6,282,429 B1 *
`8/2001 Baiyor et al.
`............... 455/512
`
`Request Resources [or Performing a Task Requiring Transmission DI
`Packers re a Reeeiving Node From a SBM Hasiing Slam'ng Node
`_—v—_—
`slan Resource Reservatlon For The Desired Priorily Level al the Starting
`Nude Having rne SBM Functionality
`Generate a Message Requeeiing Resources From Nodes orManaged
`
`Are Resources
`
`Corresponding To The Deslred
`Pronly Level Available At The
`Current Node ’?
`
`
`ND
`
`Inlarm The Nude Previous
`
`To The Current Nude of
`Denial orThe Resource
`
`
`
`Request
`Reserve Resources
`
`At The currenr Node ‘\
`
`
` \
`
`subnet: on a Patti m the Reoelvlng Node
`
`
`
`
` Nov
`
`
`
`
`Dmrmlne And Move
`Deny the
`Return an Aeknnwiedgemenl to lhe
`
`Requesr
`To The Next Made In
`Starting Node to Confirm Resavroe
`
` The Pain
`Availabiliiy Along me Path
`
`
`
`
`
`545
`K 550
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 1
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 1
`
`

`

`US 7,079,508 B2
`Page 2
`
`FOREIGN PATENT DOCUMENTS
`
`W0
`W0
`W0
`W0
`
`WO 99/33301 A1
`WO 99/39480 A2
`WO 99/50999 A1
`WO 00/10357 A1
`
`7/1999
`8/1999
`10/1999
`2/2000
`
`OTHER PUBLICATIONS
`
`Weinmiller, Jost, et al., Analyzing and Improving the IEEE
`802.11-MAC Protocol for Wireless LANs,
`in the IEEE
`Proceedings ofMASCOTS 1996, pp. 200-206.
`O’hara et al., “The IEEE 802.11 Handbook: A Designer’s
`Companion,” Standards Information Network, IEEE Press,
`Copyright © 2001 (174 pages).
`Durham et al., “Inside the Intemet’s Resource reSerVation
`Protocol: Foundations for Quality of Service,” Wiley Come
`puter Publishing, Copyright © 1999 (363 pages).
`“Whitecap TM network protocols,” retrieved from http://
`WWW. sharewave .com/Products/WhiteCap/Whitecap .html on
`Nov. 21, 2000 (12 pages).
`“Quality of Service Technical Overview,” Microsoft Win-
`dows 2000 Server, retrieved from http://WWW.microsoft.
`com/Windows2000/1ibrary/howitworks/communications/
`traffi.../qos.as on Mar. 29, 2001 (6 pages).
`Bemet, “The Complementary Roles of RSVP and Differen-
`tiated Services in the Full-Service QoS Network,” IEEE
`Communications Magazine, Feb. 2000, pp. 154-162.
`
`“QoS: Assigning Priority in IEEE 802-style Networks,”
`Microsoft Windows Device Fundamentals > Networking and
`Communications, retrieved from http://WWW.microsoft.com/
`thc/device/network/qos/qos.mspx?pffirue on Oct. 20,
`2004 (3 pages).
`SpectraLink
`Priority,”
`Voice
`“SpectraLink
`Wireless@workTM, © Copyright 2000 SpectraLink Corpo-
`ration (2 pages).
`Yavatkar et al., “SBM (Subnet Bandwidth Manager); A
`Protocol for RSVP-based Admission Control over IEEE
`
`802-style networks,” RFC 2814, retrieved from http://WWW.
`ietf.org/rfc/rfc2814.txt?number:2814 on Oct. 15, 2004 (57
`pages).
`Protocol
`ReSerVation
`“Resource
`al.,
`et
`Braden
`(RSVP)7Version 1 Functional Specification” RFC 2205,
`retrieved
`from
`http://WWW.ietf.org/rfc/rfc2205.
`txt?number:2205 on Oct. 15, 2004 (105 pages).
`“Information technologyiTelecommunications and infor-
`mation exchange between systemsiLocal and metropolitan
`area networksiSpecific requirementsiPart 11:Wireless
`LAN Medium Access Control (MAC) and Physical Layer
`(PHY) Specifications,” ANSI/IEEE std 802.1], 1999 Edition
`(5 12 pages).
`
`* cited by examiner
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 2
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 2
`
`

`

`11mm'S'fl
`
`
`
`900Z‘811“?
`
`9JOImus
`
`Z8809‘6L0‘Lso
`
`€— ______________________________________ I”“MIIIJ
`SYSTEM ME MD R‘I'
`
`191
`
`MONITOR
`
`
`PROEESEING
`
`
`196
`UNIT
`OUTPUT
`
`
`
`1II'IDEO
`PERIPHERAL
`
`
`
`INTERFACE
`INTERFACE
`'
`
`
`OPERATING
`SYSTEM __
`
`APPLICATION
`PROGRAMS
`
`r
`‘33
`
`
`Jfl
`
`
`PROGRAM
`
`OPERATING
`SYSTEM
`
`APPLICATION
`PROGRIQMS
`
`OTHER PROGRAM
`MODULES
`
`145
`
`14g
`
`FIG. 1
`
`
`REMOTE
`RPF’LFCATIOI'J
`PROGRPJ'IIE
`
`f
`100 “'
`
`
`185
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 3
`
`
`
`
`
`
`197
`198
`
`WIRELESS
`INTERFACE “L
`
`l I
`
`I“
`
`SYSTEM BLIS
`
`OTHER mew
`MODULES
`1&6.
`I
`
`I
`LDGAL AREA NETWORK
`RON REMC‘IWBLE
`REMOVABLE
`I
`
`
`NON 1IIIIIL. MEMORY
`NON VOL MEMORY
`INPUT
`
`
`INTERFME
`INTERFACE
`INTERFACE
`
`
`1?1
`
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 3
`
`

`

`US. Patent
`
`Jul. 18, 2006
`
`Sheet 2 of 6
`
`US 7,079,508 B2
`
`210
`
`Web Enabled
`
`
`
`Cellular
`
`Telephone
`
`215
`
`-
`
`1%:
`‘
`
`‘1.
`
`Laptop computer
`
`,./W
`
`,7
`
`”/
`ll
`:5
`5’5
`5%
`’4?
`
`Access Point 200
`
` Resource
`
`Database 265
`
`FIGURE 2
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 4
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 4
`
`

`

`U.S. Patent
`
`Jul. 18, 2006
`
`Sheet 3 of 6
`
`US 7,079,508 B2
`
`305
`
`Wireless Device 300
`
`
`
`Wireless Device 310
`
`Wireless Device 320
`
`
`
`325
`
`FIGURE 3
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 5
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 5
`
`

`

`U.S. Patent
`
`Jul. 18, 2006
`
`Sheet 4 of 6
`
`US 7,079,508 B2
`
`
`Priority Level
`Indicating Tag
`
`@
`
`
`Frame For A Data Packet
`400
`
`
`
`FIGURE 4
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 6
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 6
`
`

`

`U.S. Patent
`
`Jul. 18, 2006
`
`Sheet 5 of 6
`
`US 7,079,508 B2
`
`Request Resources for Performing a Task Requiring Transmission of
`Packets to a Receiving Node From a SBM Hosting Starting Node
`
`Start Resource Reservation For The Desired Priority Level at the Starting
`Node Having the SBM Functionality
`
`Generate a Message Requesting Resources From Nodes or Managed
`Subnets on a Path to the Receiving Node
`
`
`
` Are Resources
`Corresponding To The Desired
`
`Priority Level Available At The
`
`500
`
`505
`
`510
`
`Current Node ?
`
`
` Current Node The Receiving
`
`
`
`Reserve Resources
`At The Current Node
`
`Inform The Node Previous
`
`To The Current Node Of
`Denial Of The Resource
`
`Request
`
`520
`
`Current Node The Starting YES
`
`
`
`Move To The
`
`Previous Node
`
`Determine And Move Return an Acknowledgement to the
`To The Next Node ln
`Starting Node to Confirm Resource
`
`
`The Path
`Availability Along the Path
`
`
`
`End
`
`Deny the
`Request
`
`550
`
`545
`
`FIGURE 5
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 7
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 7
`
`

`

`U.S. Patent
`
`Jul. 18, 2006
`
`Sheet 6 of 6
`
`Us 7,079,508 B2
`
`Is The Channel Available For
`
`Transmission?
`
`Transmit Packet
`
`Register a Failure and
`Enter Backoff State
`
`Was An Ack Packet
`
`Generate A Random Number
`
`
`
`Received?
`
`Discard the Packet
`
`Based Upon Both Prior
`Number of Failures To
`Transmit The Packet And
`
`The Priority Level Of the
`Packet
`
`Generate A Future Time For
`
`Transmitting The Packet
`Corresponding To The
`Random Number
`
`Discontinue Retries?
`
`Wait Until the Packet is
`
`Ready for Transmission
`
`640
`
`FIGURE 6
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 8
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 8
`
`

`

`US 7,079,508 B2
`
`1
`QUALITY OF SERVICE OVER PATHS
`HAVING A WIRELESS-LINK
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application is related to the provisional US. Patent
`application Ser. No. 60/184,290 filed on Feb. 23, 2000.
`
`
`
`TECHNICAL FIELD
`
`This invention relates generally to providing Quality of
`Service assurances in a network having wireless links. In
`particular,
`the invention relates to providing Quality of
`Service assurances in networks having at least one wireless
`link connecting a wireless device to a LAN and/or a WAN
`and/or a PAN.
`
`BACKGROUND OF THE INVENTION
`
`Wireless devices communicate with each other either
`
`directly or via one or more base stations over a radio
`channel. The base station receives communications from
`
`one device and then forwards them, possibly over a network,
`to another device. The risk of disruption of any given
`wireless connection makes it difficult for a given base station
`to provide assurance to a communicating device that suffi-
`cient resources are available for the projected needs of the
`device. Moreover, wireless devices are mobile devices that
`are capable of moving out of range or losing signal strength
`due to other factors.
`
`Many wireless devices use carrier sense multiple access
`with collision avoidance (“CSMA/CA”)
`technology.
`In
`accordance with CSMA each node monitors the carrier, e.g.,
`a radio channel of interest, to detect if any other node is
`transmitting prior to attempting a transmission since CSMA/
`CA is based on the “listen before talk” paradigm. Carrier
`sense wireless network nodes can sense the carrier,
`i.e.,
`transmissions over the common radio channel, from a trans-
`mitter in a larger range than the range at which receivers are
`willing to accept a packet from that same transmitter. In
`addition, the range for sensing the carrier is beyond the
`range within which the transmitter may cause interference.
`The detection of a transmitting node can be actual or based
`on a parameter declaring the time interval for which the
`transmitting node intends to transmit, i.e., virtual.
`Every packet is sent by a node in contention-free periods
`to inform other nodes of the intended transmission. In
`
`transmission
`response other nodes regulate their packet
`attempts based only on their local perception of the statei
`idle or busyiof the radio channel. Such sensing results in
`the given node waiting for the radio channel to be idle for a
`prescribed period of time prior to attempting transmission.
`Detection of transmissions by another node in the radio
`channel results in a node that is currently waiting to transmit
`entering a “backofi‘” state. The duration of the backolf state,
`representing the time for which the common radio channel
`is required to be idle,
`is preferably set using a random
`number selected from a range, termed contention window in
`the IEEE 802.11 standard specifications, determined by the
`prior failed attempts to transmit. See, e.g., O’ Hara, Bob and
`Al Peterick, “IEEE 802.11 handbook: A Designer’s Com-
`panion,” IEEE Press New York (1999). However, CSMA/
`CA does not provide Quality of Service (“QoS”) guarantees.
`QoS refers to a reservation of resources, such as band-
`width, time slices, relative priority, memory, ports and the
`like that are required for the execution of a desired task in
`
`2
`
`a specified time period. Default QoS level, typically termed
`“best effort,” represents execution of a task if resources are
`available when needed, but not necessarily providing reser-
`vation of resources. In other words, “best effort” represents
`providing otherwise idle resources for carrying out the task.
`Higher levels of assurance provide better than “best effort”
`and can include several
`levels of relative priority as is
`discussed next.
`
`Merely reserving resources such as bandwidth is not
`sufficient for efficiently providing QoS assurances. An added
`complication is the enhanced possibility of packet collisions
`due to two or more nodes attempting to transmit during
`overlapping time intervals over the common radio channel
`resulting in unsuccessful transmission. Packet collisions are
`unavoidable with wireless links connecting nodes because
`each node has a significantly delayed perception of other
`nodes’ activity. Collisions also take place due to hidden
`nodes. For example,
`two transmitting nodes outside the
`sensing range of each other may interfere at a common
`receiver if they are within the sensing range of the common
`receiver.
`
`Following a determination of an anticipated level of the
`resources required by a task, often by the task itself, it is
`possible to reliably request a reservation of the resources,
`which may be distributed, at future times. Non-exhaustive
`examples of tasks requiring differing levels of anticipated
`resource needs include transmitting a large file, providing
`voice links, audio-video links and real-time execution of an
`interactive gaming application.
`New wireless applications, such as news updates, emer-
`gency services and the like may benefit from a reservation
`mechanism, i.e., availability of non-default QoS that ensures
`satisfactory functioning of real-time applications. However,
`due to the transient nature of wireless links, which may be
`a part of a larger communication path, it is difficult to reserve
`resources without a significant likelihood of under-utiliza-
`tion of the transmission medium.
`
`Some suggestions for providing QoS over wireless links
`include the black-burst (“BB”) contention mechanism dis-
`cussed in Sobrinho, J. L. and A. S. Krishnakumar “Quality-
`of-Service in Ad Hoc Carrier Sense Multiple Access Wire-
`less Networks” in IEEE Journal on Selected Areas in
`
`Communications, Volume 1, No. 8, 135371368 (1999). In
`accordance with BB, nodes contend for access to the com-
`mon radio channel with pulses of duration proportional to
`the time spent waiting for the common radio channel to
`become idle. Id. Furthermore, BB provides priority to real-
`time traffic.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`BB recognizes three types of links between nodes. First,
`a communication link between two nodes reflects successful
`
`transmission and receipt of a packet from one node to the
`other node. Second, an interfering link between two nodes
`due to transmissions from one of the nodes colliding with
`any other transmission to the other node during the same
`time interval. Finally, a sensing link between two nodes
`reflecting that one of the nodes can sense if the other node
`is transmitting. Naturally, if two nodes have a communica-
`tion link between them then they also have interfering and
`sensing links between them.
`CSMA/CA, in accordance with the IEEE 802.11 standard,
`allows for a backolf mode for a node that is otherwise ready
`for transmit a packet. A node in the backolf mode chooses
`a random number s uniformly distributed between zero and
`min{32><2C—1, 1, 255}, where c is the number of collisions
`experienced by the node since its last successful transmis-
`sion. The node, then, sets a timer that counts down only
`while the channel has been perceived idle for more than a
`
`55
`
`60
`
`65
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 9
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 9
`
`

`

`US 7,079,508 B2
`
`3
`threshold for transmitting on the common radio channel and
`(re)transmits the packet when the timer reaches zero. Fur-
`thermore, a node learns of the success or failure of its
`transmission following reception of a positive acknowledg-
`ment scheme. The recipient of a correctly received packet
`sends back an acknowledgment packet within a bounded
`interval of time. Id.
`Contention between nodes, in accordance with BB allows
`resolution of collisions between nodes. Nodes contend for
`
`the common radio channel prior to the time when they would
`be allowed to transmit. Contending nodes transmit bursts of
`energy (hereinafter “burst transmission”) of duration pro-
`portional to the individual delay experienced by a node.
`Following a burst transmission a node monitors the common
`radio channel to determine if its burst was the longest. The
`successful node proceeds with its transmission while the
`other nodes wait to contend for the common radio channel
`
`to become idle again. The successful node also selects a
`future time for transmission of the next transmission. Thus,
`the various nodes transmit in staggered time intervals that
`are more likely to be collision free.
`However, this scheme requires transmission of bursts of
`energy, an expensive scheme for devices with limited power
`resources. Using additional hardware and/or software to
`detect that such bursts are not packet transmissions is also
`required for implementing the BB proposal. Furthermore,
`the transient nature of wireless and other failure prone
`connections is likely to repeatedly invoke the burst mecha-
`nism to resynchronize real-time transmissions.
`A further limitation of proposals for providing QoS,
`including BB discussed above and WHITECAPTM over
`transient
`links is the widely perceived need to extend
`existing standards such as IEEE 802.11. Both the BB and the
`WHITECAPTM proposals seek to extend existing standards.
`In other words, agreement has to be reached among the
`standards consortia members to accept a particular solution.
`Furthermore, the proposed direction for standards is not
`efficiently addressed by the current proposals to provide
`QoS over wireless links. For instance the IEEE 802.1p
`proposal includes multiple priority levels for packet trans-
`missionias many as eight priority levels have been pro-
`posed. Thus, QoS protocols need to accommodate several
`priority levels in addition to best-effort and real-time con-
`straints in resolving collisions with the aim of honoring QoS
`guarantees.
`
`SUMMARY OF THE INVENTION
`
`The invention described herein addresses the problem of
`providing the Quality of Service assurances, in a manner
`expected in other media, to communications over paths that
`include one or more wireless links. The invention provides
`improved Quality of Service over end-to-end connections
`including at least one wireless link or hop by combining the
`subnet bandwidth manager
`(“SBM”) with a stochastic
`scheme for assuring that data packets are transmitted based
`on priority and prior failure to transmit due to a collision.
`The wireless link includes an access point (“AP”) having an
`SBM to track allocations of wireless bandwidth. The AP
`allows transmission in allocated time intervals to stations
`
`(“STA”) that succeed in competing for the right to transmit.
`In effect, a two-prong resource deployment scheme is
`employed as described below.
`The first prong includes reserving bandwidth and/or
`memory and additional resources for, by way of example, a
`prescribed time interval at each of the intermediate nodes in
`a transmission path. This reservation allows the STA to use
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`an approved tag on the packets. The reservation scheme
`requires all intervening nodes to fail to object to the pro-
`posed reservation. The reservation further implements an
`SBM to account for bandwidth at each stage of the path.
`The second prong includes modulating a retransmission
`window by a particular STA based on a previous failure to
`transmit due to the STA failing in an attempt to transmit.
`Thus, failing to transmit results in changing the retransmis-
`sion window. Such a failure could be due to a collision
`
`and/or another node taking control of the carrier earlier than
`the particular STA.
`Moreover, the stochastic scheme for managing priority
`does not shut out the lower priority clients, but, instead, a
`hybrid scheme allows them to attempt to transmit with a
`lower probability of being first to attempt transmission.
`Furthermore, a stochastic scheme for recovering from col-
`lisions allows staggering of packets having the same priority.
`The overall result of this hybrid scheme is to not shut out
`users and resolve collisions while allowing real-time ser-
`vices adequate bandwidth with statistically higher probabil-
`ity of access.
`Additional features and advantages of the invention will
`be made apparent from the following detailed description of
`illustrative embodiments, which proceeds with reference to
`the accompanying figures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`While the appended claims set forth the features of the
`present invention with particularity, the invention, together
`with its objects and advantages, may be best understood
`from the following detailed description taken in conjunction
`with the accompanying drawings of which:
`FIG. 1 is a block diagram generally illustrating an exem-
`plary computer system on which the present
`invention
`resides;
`FIG. 2 is an illustration of the general computing envi-
`ronment in which an embodiment of the invention functions;
`FIG. 3 illustrates unavoidable collisions between packets
`transmitted over wireless links;
`FIG. 4 illustrates an exemplary packet with a priority level
`field;
`FIG. 5 illustrates exemplary steps in a method for reserv-
`ing resources for honoring a requested QoS; and
`FIG. 6 illustrates transmission of a packet with collision
`avoidance using a stochastic scheme that manages transmis-
`sion of packets having different priority levels and failed
`transmission attempts.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`In a network connected to wireless devices there are
`possible paths having one or more wireless links. Providing
`QoS is limited by the wireless links because of the lower
`wireless bandwidth and higher error rates compared to a
`wired link. Furthermore, wireless transmission of frames
`over a wireless link typically requires retransmission if an
`acknowledgment is not received within a prescribed time
`period. In view of the transitory and failure-prone nature of
`wireless links, the overhead due to a wireless link is sig-
`nificantly greater than the wired link overhead.
`Instead of extending or changing the wireless link c011-
`taining local area network specifications, an embodiment of
`the disclosed invention provides QoS by implementing a
`subnet bandwidth manager (“SBM”). The SBM preferably
`conforms to existing specifications, e.g., RFC 2814, which
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 10
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 10
`
`

`

`US 7,079,508 B2
`
`5
`is incorporated herein by reference in its entirety, and is in
`close association with the access point (“AP”). The SBM is
`instrumental in receiving QoS requests, generating reserva-
`tion messages,
`also termed RSVP RESV,
`to request
`resources at each node to accommodate the requested QoS.
`The reservation message is sent to the next node in the path,
`following a reservation of the requested resources, if the
`current node can accommodate the requested level of QoS.
`If a node in the path cannot accommodate the reservation
`request then the reservation request is denied and returned
`along the path with each node freeing the previously
`reserved resources. In an exemplary embodiment of the
`invention each node need not affinnatively approve the
`request since failing to deny the request implies approval.
`Moreover, some of the nodes in the path may be managed
`together. In such a case the management software advanta-
`geously tracks the resource allocation using suitable book-
`keeping algorithms.
`The nodes defining the wireless link also support a
`stochastic strategy to avoid collisions by staggering the time
`at which a frame is transmitted. The nodes defining the
`wireless link generate delays in the event of collisions. For
`example, two nodes attempting to transmit during overlap-
`ping time periods use a random number to effect collision
`avoidance with little overhead. In addition,
`the random
`number range for generating a time point for transmitting is
`obtained by the SBM a packet such that the probability of
`transmitting a packet changes during a next period of time
`following a failure to transmit. This increase in probability
`may have an upper bound. Furthermore, packets with a
`similar priority level are queued together to ensure earlier
`transmission of higher priority packets than packets having
`lower priority.
`Compatibility of the invention with existing standards is
`an advantage over proposals to extend various specifications
`due to lowered transaction costs, but it is not intended to be
`a limitation. The invention is intended to be operable with a
`wide variety of existing and future standard specifications,
`in part, because it combines several features in a novel
`manner to provide QoS. Preferably, the invention is carried
`out, at least in part, by programming computing devices to
`create a suitable computing environment. The following
`detailed description of the invention includes a description
`of a general computing environment suitable for implement-
`ing the invention.
`Some of the devices, whether in the piconet or remote to
`the piconet, provide computing environments similar to the
`computing environment illustrated in FIG. 1. Of course, the
`invention does not require the resources and sub-devices
`illustrated in FIG. 1. In fact, the piconet devices will not
`include many of the components depicted in FIG. 1 such as
`a hard drive for data storage.
`Turning to the drawings, wherein like reference numerals
`refer to like elements, the invention is illustrated as being
`implemented in
`a
`suitable
`computing
`environment.
`Although not required, the invention will be described in the
`general context of computer-executable instructions, such as
`program modules, being executed in a computing environ-
`ment. Generally, program modules include routines, pro-
`grams, objects, components, data structures, etc. that per-
`form particular tasks or implement particular abstract data
`types. Moreover, those skilled in the art will appreciate that
`the invention may be practiced with other computer system
`configurations, including hand-held devices, multi-proces-
`sor systems, microprocessor based or programmable con-
`sumer electronics, network PCs, minicomputers, mainframe
`computers, and the like. The invention may also be practiced
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`in distributed computing environments where tasks are
`performed by remote processing devices that are linked
`through a communications network. In a distributed com-
`puting environment, program modules may be located in
`both local and remote memory storage devices.
`FIG. 1 illustrates an example of a suitable computing
`system environment 100 on which the invention may be
`implemented. The computing system environment 100 is
`only one example of a suitable computing environment and
`is not intended to suggest any limitation as to the scope of
`use or functionality of the invention. Neither should the
`computing environment 100 be interpreted as having any
`dependency or requirement relating to any one or combina-
`tion of components illustrated in the exemplary operating
`environment 100.
`
`The invention is operational with numerous other general-
`purpose or special-purpose computing system environments
`or configurations. Examples of well-known computing sys-
`tems, environments, and configurations that may be suitable
`for use with the invention include, but are not limited to,
`personal computers, server computers, hand-held or laptop
`devices, multiprocessor systems, microprocessor-based sys-
`tems, set top boxes, programmable consumer electronics,
`network PCs, minicomputers, mainframe computers, and
`distributed computing environments that include any of the
`above systems or devices.
`The invention may be described in the general context of
`computer-executable instructions, such as program modules,
`being executed by a computer. Generally, program modules
`include routines, programs, objects, components, data struc-
`tures, etc. that perform particular tasks or implement par-
`ticular abstract data types. The invention may also be
`practiced in distributed computing environments where
`tasks are performed by remote processing devices that are
`linked through a communications network. In a distributed
`computing environment, program modules may be located
`in both local and remote computer storage media including
`memory storage devices.
`With reference to FIG. 1, an exemplary system for imple-
`menting the invention includes a general -purpose computing
`device in the form of a computer 110. Components of the
`computer 110 may include, but are not limited to, a pro-
`cessing unit 120, a system memory 130, and a system bus
`121 that couples various system components including the
`system memory to the processing unit 120. The system bus
`121 may be any of several types of bus structures including
`a memory bus or memory controller, a peripheral bus, and a
`local bus using any of a variety of bus architectures. By way
`of example, and not limitation, such architectures include
`Industry Standard Architecture (ISA) bus, Micro Channel
`Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video
`Electronics Standards Association (VESA) local bus, and
`Peripheral Component Interconnect (PCI) bus, also known
`as Mezzanine bus.
`
`The computer 110 typically includes a variety of com-
`puter-readable media. Computer-readable media can be any
`available media that can be accessed by the computer 110
`and include both volatile and nonvolatile media, removable
`and non-removable media. By way of example, and not
`limitation, computer-readable media may include computer
`storage media and communications media. Computer stor-
`age media includes volatile and nonvolatile, removable and
`non-removable media implemented in any method or tech-
`nology for storage of information such as computer-readable
`instructions, data structures, program modules, or other data.
`Computer storage media include, but are not limited to,
`random-access memory (RAM), read-only memory (ROM),
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 11
`
`Petitioner Motorola Mobility LLC - Exhibit 1003 - Page 11
`
`

`

`US 7,079,508 B2
`
`7
`flash memory, or other memory technology,
`EEPROM,
`CD-ROM, digital versatile disks (DVD), or other optical
`disk storage, magnetic cassettes, magnetic tape, magnetic
`disk storage, or other magnetic storage devices, or any other
`medium which can be used to store the desired information
`
`and which can accessed by the computer 110. Communica-
`tions media typically embody computer-readable instruc-
`tions, data structures, program modules, or other data in a
`modulated data signal such as a carrier wave or other
`transport mechanism and include any information delivery
`media. The term “modulated data signal” means a signal that
`has one or more of its characteristics set or changed in such
`a manner as to encode information in the signal. By way of
`example, and not limitation, communications media include
`wired media such as a wired network and a direct-wired
`
`connection and wireless media such as acoustic, RF, optical,
`and infrared media. Combinations of the any of the above
`should also be included within the scope of computer-
`readable media.
`
`The system memory 130 includes computer storage media
`in the form of volatile and nonvolatile memory such as ROM
`131 and RAM 132. Abasic input/output system (BIOS) 133,
`containing the basic routines that help to transfer informa-
`tion between elements within the computer