US007136392B2
`
`United States Patent
`
`(12)
`(10) Patent No.:
`US 7,136,392 B2
`
`Wentink
`(45) Date of Patent:
`Nov. 14, 2006
`
`(54) SYSTEM AND METHOD FOR ORDERING
`DATA MESSAGES HAVING DIFFERING
`LEVELS OF PRIORITY FOR
`TRANSMISSION OVER A SHARED
`COMMUNICATION CHANNEL
`
`6,470,025 B1 * 10/2002 Wilson et a1.
`.............. 370/462
`6,483,846 B1 *
`11/2002 Huang et al. ........... 370/445
`
`2/2004 Wang ...................... 370/401
`6,693,912 B1*
`
`6,741,559 B1 *
`5/2004 Smeulders et al.
`..... 370/230
`..... 370/235
`6,760,308 B1*
`7/2004 Ghanma et a1.
`
`............ 370/235
`6,859,438 B1 *
`2/2005 Haddock et a1.
`
`(75)
`
`Inventor: Maarten Menzo Wentink, Utrecht
`(NL)
`
`2002/0163933 A1* 11/2002 Benveniste ................. 370/465
`2003/0012167 A1 *
`1/2003 Benveniste ................. 370/338
`
`P rt
`6W 0
`
`<
`
`(
`
`*
`
`73 A '
`: C
`t S
`t
`I
`. N
`> W nggfagA ($511“, "Ci
`.
`.
`.
`.
`.
`) Notice:
`SlleeCt.t0 any (31153121111135). the fungi“ fig;
`31:13 1155:)(b3nb; 8S5 gaggle un er
`(21) Appl. No.: 09/943,803
`
`(22)
`
`Filed:
`
`Aug. 31, 2001
`
`(65)
`
`Prior Publication Data
`
`Mar. 20’ 2003
`
`US 2003/0053469 A1
`Int C1
`I
`I
`(2006.01)
`H04L 12/413
`(52) US. Cl.
`..................................'..... 370/445- 370/412
`58
`F' 1d
`fCl
`'fi
`_
`S
`h
`’370/445
`(
`)
`1e
`0 3707481216 c2470144ga461 46239541 395 42’
`370;455 ’412 ’413 3428 ’429 .4638 395 2’
`’
`’
`’
`’
`’ 370;”5 21’
`f
`1 t
`h h' t
`’
`t'
`1.
`e or comp e e searc
`ls ory.
`ee app ica ion
`References Cited
`US. PATENT DOCUMENTS
`
`(51)
`
`(56)
`
`S
`
`fil
`
`* eiiee by eeiiiiiiei
`Primary ExamineriAjit Patel
`(74) Allumey, Age/11,
`or FirmiThOinas, Kayden,
`Horstemeyer & Risley, LLP
`57
`ABSTRACT
`(
`)
`
`Stations of a communication network have internal queues
`for accumulating and transmitting data messages over a
`shared communication channel. Each queue within a station
`accumulates and transmits data messages that have a differ-
`ent level of priority than those accumulated and transmitted
`by other internal queues of that station. While preferential
`access to t e s are
`0 anne is
`iven to
`ata messa es
`h
`h
`d h
`1
`g
`d
`g
`haVing higher leVels 0f Pfiori‘y’ datamessages haVing the
`same priority are transmitted according to a set of rules
`common to all ofthe stations. That is, a queue in one ofthe
`stations is configured to delay and/or transmit data messages
`of a given priority level according to a set of rules that
`applies identically to the queue of any other station that
`handles data messages of that same priority level. Trans-
`mission opportunities are thus fairly allocated between all
`queues containing data messages of the same priority level.
`
`5,812,526 A *
`
`9/1998 Chang et a1.
`
`............... 370/230
`
`21 Claims, 6 Drawing Sheets
`
`
`
`i
`
`x
`
`cm
`m
`
`_
`
`I
`
`
`
`Y
`
`Mic
`
`m
`
`
`1
`
`CPU
`2E:
`
`1 i
`
`MWV
`-3“—
`12:
`
`NIC
`
`m
`
`“my
`12“
`
`*
`
`—_'L_7
`11]
`
`
`
`
`
`
`
`
`
`
`
`
`.12.
`
`
`211: F"
`
`I
`‘
`
`
`MBAORY
`L
`Y m
`
`
`
`.
`
`
`
`
`
`
`
`
`
`CPU
`m H
`
`MC
`
`1h
`
`I
`MW)!
`21!
`
`12:
`
`
`
`
`
`
`
`NIC
`.151
`
`12‘
`
`1 Y
`
`
`
`
`
`
`
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 1
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 1
`
`

`

`U.S. Patent
`
`Nov. 14, 2006
`
`Sheet 1 of 6
`
`US 7,136,392 B2
`
`
`
`.223;
`
`A
`
`V
`
`182
`E
`v
`
`
`
`‘ m
`
`MEMORY
`
`a;
`
`12—“
`
`mCPU
`
`
`
`
` MEMORY
`
`
`
`
`
`m MEMORY
`
`
`
`
` 22_e.
`
`
`
`
`
`MEMORY
`
`12$
`
`HQ 1
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 2
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 2
`
`

`

`U.S. Patent
`
`NOV. 14, 2006
`
`Sheet 2 of 6
`
`US 7,136,392 B2
`
`
`
`.055092
`
`gs:
`
`5283.3.
`
`
`
`ESE?
`
`
`Bmwmooi1i
`
`thzm9ND
`
`
`
` amino:3:50«.602H«a32.0ch
`
`2255288
`
`mazzumfiw
`
`226:2“.
`
`
`
`N.OE
`
`cozfiw
`
`mEEmEa
`
`EmEEoo
`
`$33.2
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 3
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 3
`
`

`

`U.S. Patent
`
`Nov. 14, 2006
`
`Sheet 3 of 6
`
`US 7,136,392 B2
`
`Data Buffers
`
`& ‘-,
`
`m
`
`
`
`Media
`Access and
`Scheduling
`Coordination
`Function
`
`'
`
`l
`
`
`
`
`,
`
`i
`5
`
`w i
`
`‘
`
`‘
`
`‘=
`
`.
`
`‘
`
`é
`
`'
`
`i
`
`Queue”
`
`,
`
`,
`
`'
`
`l
`
`‘
`
`£9411
`
`Queuem
`
`m |
`t
`‘
`
`Queue-[n]
`
`5
`
`E
`
`CFSchdl
`
`0
`
`‘
`
`1
`
`s
`
`mil
`
`CF Schedulerfi]
`
`1
`
`1 5
`
`[
`
`!
`
`.
`
`,
`
`5.2m
`
`CF Scheduierml
`
`
`
` Mfi
`euert] U
`' W
`.
`!24a
`
`
`
`t
`;
`j
`‘
`
`‘ EA
`I
`
`L
`
`Communication
`
`=
`4
`
`Communication
`,
`Modules
`‘
`.___.___.._.__-_-————i
`
`
`
`
`
`
`1%» To Transceiver
`
`~—
`
`
`
`;
`
`,
`
`' Media Access
`Control
`
`
`
`{
`
`I
`z
`l
`,
`
`FIG. 3
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 4
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 4
`
`

`

`U.S. Patent
`
`Nov. 14, 2006
`
`Sheet 4 of 6
`
`US 7,136,392 B2
`
`
`
`
`Next Message Uni!
`
`Select Stot and Decrement
`Backofi Counter White
`Medium is Idle
`
`Defer Access
`
`FIG. 4
`
`CWmin
`
`
`
`Third Retransmission
`
`Second Retransmission
`
`First Retransmission
`
`
`
`initial Attempt
`
`FtG. 5
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 5
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 5
`
`

`

`U.S. Patent
`
`Nov. 14, 2006
`
`Sheet 5 of 6
`
`US 7,136,392 B2
`
`Frame
`
`
`cwm
`
`
`FIG.6
`
`Frame
`
`StationA
`
`StationB
`
`Station0
`
`StationD
`
`StationE
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 6
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 6
`
`

`

`U.S. Patent
`
`Nov. 14, 2006
`
`Sheet 6 of 6
`
`US 7,136,392 B2
`
`
`
`
`
`
`
`
`
`TRANSMIT
`
`1%
`
`
`
`
`
`
`Decrement
`
`Fail Packet
`
`BACKOFF
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 7
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 7
`
`

`

`US 7,136,392 B2
`
`2
`
`internal queues for accumulating and transmitting data mes-
`sages over the shared communication channel. Each internal
`queue of a station individually accumulates and releases, for
`transmission during an appropriate transmission opportu-
`nity, data messages that have a specific traffic classification
`and, hence, a different level of priority than those accumu-
`lated and released by other internal queues of that station. At
`both the local (i.e., within each station) and the network-
`wide (i.e., among all stations) level, preferential access to
`the shared communication channel is given to data messages
`having higher levels of priority over those having lower
`levels of priority. However, in accordance with an illustra-
`tive embodiment of the present invention, the release, for
`transmission, of data messages having the same level of
`priority is governed by a set of parameters that is common
`for all stations of the network. That is, an internal queue in
`any one of the stations is configured to delay and/or release
`data messages of a given priority level according to a set of
`rules that applies identically to the internal queue of any
`other station that handles data messages of that same priority
`level. Transmission opportunities are thus fairly allocated
`between all queues containing data messages of the same
`priority level.
`A method according to an illustrative embodiment of the
`invention comprises directing, to a first output queue at a
`first station of a communication network, data message units
`that are to be transmitted over a communication medium and
`that have a first traffic classification. The method further
`
`10
`
`15
`
`20
`
`25
`
`30
`
`comprises directing to a second output queue at the first
`station, data message units that are to be transmitted over the
`communication medium and that have a second traffic
`
`1
`SYSTEM AND METHOD FOR ORDERING
`DATA MESSAGES HAVING DIFFERING
`LEVELS OF PRIORITY FOR
`TRANSMISSION OVER A SHARED
`COMMUNICATION CHANNEL
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to media control in
`communication networks and, more particularly,
`to a
`method and apparatus for classifying and ordering data
`messages prior to their transmission over a shared commu-
`nication channel.
`
`BACKGROUND OF THE INVENTION
`
`Quality of service (QoS) mechanisms allocate transmis-
`sion resources to different types or classes of data trafiic so
`that certain traffic classes can be preferentially served over
`other classes. For example,
`in a network that supports
`multimedia services like video-on-demand, video confer-
`encing, online brokerage, and electronic commerce, a QoS
`mechanism can prioritize time-sensitive multimedia data
`streams so that their packets are transmittediover a com-
`munication medium or channel shared by two or more
`terminals or stationsiwith less delay and/or at a higher rate
`than packets of data streams less affected or unaffected by
`delay.
`Local area networks (LANs) are increasingly used to
`transfer data, including multimedia data streams that have
`various QoS requirements. A multiple layer communication
`protocol “stack” such as the OSI reference model imple-
`ments communication over the typical LAN. According to
`this model, the media access layer (MAC) is responsible for
`access control of a shared communication channel. A sig-
`nificant objective of any LAN is to allocate access to a
`shared communication channel as equitably as possible
`between the stations competing for it. A straightforward
`realization of this would be to implement, via the media
`access layer, a QoS scheme in which each of two time-
`sensitive streams of multimedia trafficiwith each originat-
`ing at a different station on the LANiis assigned an
`identical level of transmission priority.
`Consider, however, a scenario in which the first station
`has two distinct classes of traffic to transmit (e.g., from both
`a high priority class and a lower priority class) while the
`second station has only traffic from the lower priority class
`to transmit. At the first station, the higher priority class of
`traffic would be preferentially treated to the detriment of the
`lower priority class of traffic since both classes compete for
`the same transmission opportunity. The lack of any higher
`priority class of trafiic to transmit at the second station, on
`the other hand, benefits the lower priority class of traffic
`insofar as there is no need to yield a transmission opportu-
`nity to a higher priority data message. As such, a need arises
`for a system and method of ordering data messagesiprior
`to their transmission over a shared communication chan-
`
`35
`
`40
`
`45
`
`50
`
`55
`
`the communication
`senses
`classification. Each queue
`medium for an opportunity to transmit data message units
`according to the aforementioned set of rules. An attempt is
`made to retransmit, after a respective interval defined dif-
`ferently for each corresponding traffic classification, any
`message data unit
`transmitted by the first station that
`destructively interferes with a message data unit transmitted
`by another station over the communication medium, or with
`other causes of interference.
`
`If the first and second output queues at the first station
`each contain data message units that are scheduled to be
`transmitted during the same sensed transmit opportunity,
`they could benefit from that prior knowledge and, by way of
`illustrative example, at least one message data unit from the
`first output queue can be preferentially transmitted over a
`message data unit from the second queue. For purposes of
`this specification, preferential treatment encompasses one or
`more measures that guaranteeifor streams of higher prior-
`ity data message unitsian average transmission rate that is
`higher and/or a maximum delay before transmission that is
`lower than that which is guaranteed to streams of lower
`priority data message units. Such measures include, by way
`of illustrative example, deferring transmission of (i.e., “pre-
`empting”) a lower priority message data unit from the
`second output queue to ensure that
`the higher priority
`message data unit can be transmitted during a specific
`transmit opportunity.
`According to the present invention, however, an effort is
`made to fairly allocate transmission opportunities among
`every queue having data message units of the same traffic
`classification to transmit-regardless of where each queue
`happens to be among the stations of the network. Specifi-
`cally, each station is configured so that a queue containing
`higher priority data message units has no more impact on the
`scheduling order of a local queue (i.e., a queue in the same
`station) than it does on the scheduling order of any external
`
`nelisuch that traffic of equal priority is handled in a fair and
`equitable manner by all stations contending for access to the
`shared communication channel.
`
`60
`
`SUMMARY OF THE INVENTION
`
`The aforementioned need is addressed, and an advance is
`made in the art, by a communication network having a
`plurality of stations that share a communication medium or
`channel. Each station of the network has a plurality of
`
`65
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 8
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 8
`
`

`

`US 7,136,392 B2
`
`3
`queue (a queue at any other station) that contains data
`message units of the same, lower priority level. To this end,
`in the illustrative embodiment of the invention, at least one
`attempt is made to transmit a data message unit, from the
`second output queue, that has been pre-empted by a higher
`priority message data unit from the first output queue, as if
`that pre-empted message data unit had already been trans-
`mitted and had experienced destructive interference. As
`such, the probability that a message data unit of a given
`priority level will be transmitted during a subsequent trans-
`mission opportunity is substantially the same regardless of
`whether it was actually transmitted and destructively inter-
`fered with a message data unit from another station or it was
`internally pre-empted by a higher priority message data unit
`before it could be transmitted
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The various features and functions of the present inven-
`tion will be better understood by reference to both the
`detailed description of the various illustrative embodiments
`which follows and the accompanying drawings, in which
`FIG. 1 depicts an exemplary embodiment of a commu-
`nication network adapted for operation in accordance with
`the teachings of the present invention;
`FIG. 2 shows elements of an individual station of the
`communication network of FIG. 1;
`FIG. 3 is a block diagram depicting, in greater detail, the
`software implementation of media access control in accor-
`dance with the illustrative embodiment of FIGS. 1 and 2.
`
`FIG. 4 is a graphical representation depicting the assign-
`ment of minimum idle times and back of periods to dilferent
`queues of a station in accordance with an illustrative
`embodiment of the present invention;
`FIG. 5 is a graphical representation depicting the expo—
`nential
`increase in a queue’s contention window during
`successive efforts to transmit a particular data message unit,
`as when either an actual collision with a transmission by
`another station or preemption by a higher queue (i.e., a
`“virtual collision”) occurs;
`FIG. 6 is a graphical representation depicting multiple
`stations sensing a medium and waiting during the appropri-
`ate idle time and back off period according to an illustrative
`embodiment of the present invention; and
`FIG. 7 is a flow chart depicting a state machine for an
`access method implemented in accordance with an illustra-
`tive embodiment of the present invention.
`
`DETAILED DESCRIPTION
`
`Initially, it should be noted that it may be desirable to
`increase the probability of successful transfer of (MSDUs)
`across a shared channel such, for example, as the wireless
`medium employed by the illustrative embodiment of the
`present invention. In such cases, message data units can be
`partitioned into a sequence of smaller data units prior to
`transmission. The process of recombining a set of fragment
`data units into an MSDU is known as defragmentation. For
`the purposes of the present specification, the terms message
`data units are intended to encompass each of the aforemen-
`tioned units, as well as any other units, which can be
`transmitted and received as delimited frames of digital bits.
`An illustrative embodiment of a communication network
`
`invention is
`10 employing the teachings of the present
`shown in FIG. 1 and includes a plurality of stationsi
`generally indicated at 12a71267that are configured to
`receive and transmit message units over a shared commu-
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`
`nication medium. As will be readily appreciated by those
`skilled in the art, various types of wired communication
`media such as, for example, coaxial cable, twisted wire pairs
`of electrical conductors, and/or optical fiber, might be used
`to
`implement
`the
`requisite network interconnections
`between stations. In the illustrative example of FIG. 1,
`however, the stations form a wireless local area network
`(WLAN) and are adapted to communicate over a wireless
`medium 14 such as radio or optical frequency propagation
`through the interior space of an office building. Coupling of
`the stations in a WLAN arrangement, because it does not
`require physical or “hard-wired” connections, will often be
`especially advantageous when installing a new communica-
`tion network within existing ofiices.
`Although a network in which a wireless medium func-
`tions as a shared channel is illustrated and described in detail
`
`in the present specification, this is for pedagogical purposes
`only and it should be understood that the teachings of the
`present invention are also applicable to any other network in
`which two or more stations share a common transmission
`
`channel. It should also be understood that while a point to
`multipoint (e.g., a hub) topology is shown in FIG. 1, the
`present invention is applicable to other network architec-
`tures (e.g., ring networks, mesh networks, etc.) as well. The
`stations themselves can be a variety of devices such, for
`example,
`as personal computers,
`computer peripheral
`devices, gateway devices to other networks, or any other
`devices that require data communication services.
`Embodiments of the invention use a variety of radio or
`optical frequencies and transmission methods. In the illus-
`trative embodiment of FIG. 1, the stations communicate
`using radio frequency spread spectrum transmissions in the
`Industrial Scientific and Medical (ISM) band in the range of
`2.4 GHZ using an overall bandwidth of approximately 83
`MHz. The transmission technique provides a raw system
`data rate of 1 Mb/s between stations. As will be readily
`ascertained by those skilled in the art,
`the transmission
`characteristics of the individual stations 12117126 can vary
`according to such factors as the transmission power level,
`the physical distance between stations, the presence of any
`interfering structures betweens, and the proximity to any
`interfering signal
`sources. Accordingly,
`the achievable
`throughput over the communication medium may be sub-
`stantially lower than the raw data rate.
`In any event, and with continued reference to the illus-
`trative communication network of FIG. 1, it will be seen that
`each of wireless stations 12117126 includes a respective
`network interface controller (NIC) 16117166 that is coupled
`to a corresponding antenna 18117186. Each wireless station
`further includes a general-purpose processing unit (CPU)
`20a7206 and a memory 22117226. Application programs
`stored within the memory at each wireless station are
`executed by its CPU and communicate over the WLAN
`through its NIC.
`With reference now to FIG. 2, there is shown an arrange-
`ment of the hardware components of an exemplary network
`stationiindicated generally at 126. General purpose CPU
`206 executes application programs 24 and communication
`modules 26 stored in working memory 28 such as dynamic
`RAM. Prior to initialization of the station, the application
`programs and communication modules are stored within a
`non-volatile memory 30 such as, for example, a magnetic
`disk or read only memory (ROM). CPU 206 communicates
`with NIC 166,
`these components being coupled to one
`another by, for example, a PCMCIA or ISA bus.
`NIC 166 comprises a control processor 32 used for data
`bulfers 34 and media access control and queue scheduling
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 9
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 9
`
`

`

`US 7,136,392 B2
`
`5
`function modules 38 which reside in memory 39, and which
`execute on control processor 32. Control processor 32
`communicates with transceiver 40 that, in turn, is coupled to
`antenna 182.
`In a conventional manner,
`transceiver 40
`converts a baseband data signal into a radio frequency signal
`that is transmitted through antenna 18e. Transceiver 40 also
`converts a radio frequency signal present invention, trans-
`ceiver 28 implements a direct sequence (spread spectrum)
`transmission technique to reduce interference from other
`transmission sources. Such a transceiver may be constructed
`using, for example, a “PRISM” chipset (not shown) com-
`mercially available from Intersil Corporation that includes a
`quadrature modem, a voltage controlled oscillator, a radio
`frequency to infrared frequency converter, an RF power
`amplifier with transmit/receive switch, and a low noise RF
`amplifier.
`FIG. 3 exemplifies, in greater detail, the software imple-
`mentation of media access control in accordance with the
`illustrative embodiment of FIGS. 1 and 2. As seen in FIG.
`
`
`
`3, the application programs 24 residing in station memory 28
`include, for example, a user interface program 24a that is
`used by a network administrator (or other authorized user) to
`interactively specify QoS requirements. Also residing in
`station memory 28 a‘e communication programs 24b which
`communicate with similar communication programs execut-
`ing at other stations. Each communication session comprises
`a single, unidirectional data stream between two stations.
`In a conventional manner, each session communicates
`through a standard communication protocol stack 26a,
`implementing a suitable network transmission protocol
`such, for example, as TCP/IP, UDP/IP or the like. In the
`illustrative example of FIG. 3, each station operates using a
`commercially available operating system such as Microsoft
`Windows 2000 (NT) or Windows 98. Microsoft Corporation
`furnishes a protocol stack 26a specifically configured for use
`with those operating systems. Application programs 24,
`such as user interface program 24a and communication
`programs 24b communicate with protocol stack 26a in a
`conventional manner.
`
`In the Microsoft Windows-based implementation of FIG.
`3, protocol stack 26a also communicates with a Network
`Driver Interface Specification (NDIS) driver 26b that pro-
`vides the interface to media control module 38 executed by
`control processor 32 of a station’s network interface con-
`troller (NIC) as NIC 166 of station 126. As will be readily
`appreciated by those skilled in the art, an NDIS driver
`contains operating code that controls the NIC and provides
`a standard interface for higher level protocols implemented
`in protocol stack 26a. Calls are made, by the higher level
`protocols, to the NDIS driver to submit data message units
`for transmission to network 10 and to retrieve data received
`
`from the network. As data message units arrive from net-
`work 10, media control module 38 directs them to lower
`level controller code in the operating system. This lower
`level controller code calls NDIS driver routines to forward
`
`the arriving data message units to protocol stack 26a for
`processing.
`In order to support QoS sessions, a virtual device driver
`(VxD) 260 is included within communication module 26.
`VxD 6 accepts QoS parameters specified via user interface
`program 24b and directs it
`to NDIS driver 26b. Using
`interface program 24b, a network administrator can specify
`that data streams addressed to a particular port on other
`stations have a particular minimum data rate and maximum
`delay requirement. Within NDIS driver 26b, data message
`units arriving from protocol stack 26a are tagged in a way
`that allows QoS and non-QoS sessions to be distinguished
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`from one another and these tagged message units are then
`transferred to media control module 38. The manner in
`
`which this tagging procedure is carried out admits of sub-
`stantial variation. For example, in accordance with an illus-
`trative embodiment of the present invention, a number n of
`discrete traffic classifications are established for the data
`
`message units constituting the various data streamsiwith
`each traffic classification having, as will be explained in
`greater detail shortly, a corresponding contention window
`that circumscribes the QoS criteria specifiable for each
`session. Using the information received via VxD 260, data
`message units from a given session are mapped to one of
`these 11 traffic classifications and placed in a corresponding
`one of queues 500 through 50” within data buffers 34. Once
`placed within one of the queues, the data message units are
`released in accordance with a coordination function (CF)
`implemented in a scheduler 52 which prioritizes the trans-
`mission of data message units from each queue in accor-
`dance with a defined access control algorithm
`In the illustrative communication network 10 of FIG. 1,
`the media access control (MAC) algorithm employed is a
`distributed coordination function known as carrier sense,
`multiple access with collision avoidance or CSMA/CA. This
`function is implemented at all stations, so that any of stations
`12117126 having data messages to transmit must first sense
`the medium to determine if another station is already trans-
`mitting. As will be explained in greater detail
`later, the
`CSMA/CA distributed algorithm employed by the illustra-
`tive embodiment of the present
`invention specifies that
`sequences of data messages be separated by a gap having an
`established minimum duration. Only when a station has
`determined that the medium has been idle for this required
`duration may it attempt to transmit any of the data messages
`within its data buffers 34.
`A wireless local area network constructed in accordance
`
`with an illustrative embodiment of the present invention
`provides differentiated access, to the wireless communica-
`tion medium, for eight traffic categories. Accordingly, each
`station has no more than eight prioritized output queues (as
`queues 501 through 50" of FIG. 3), one for each category. A
`station may, of course, implement fewer than eight physical
`queues in data bulfers 34. In such event, the system can be
`configured to map the eight exemplary traffic categories into
`the smaller number of queues.
`In the exemplary embodiment of the present invention,
`each output queue competes for transmission opportunities
`(“TxOPs”) using a coordinated scheduling function. Accord-
`ing to this scheduling function, the minimum specified idle
`duration periodiseparating a message data unit which has
`already been transmitted over the wireless medium from a
`subsequent message data unit to be transmitted from one of
`the output queuesiis a distinct value that differs for each
`traffic classification and, hence, each queue The correspond-
`ing minimum specified idle duration period specified for
`each traffic category can, for example, be set as a default at
`each station or assigned by a remote administrator. The
`scheduling function of the illustrative embodiment further
`specifies a contention window CWmin from which a random
`back off is computed for each queue. In accordance with an
`illustrative embodiment of the present invention, the con-
`tention window is not fixed but, rather, is a variable window,
`assigned to each queue on the basis of traffic classification.
`After the aforementioned medium idle time, a random back
`off period is generated for each queue for an additional
`deferral time before transmitting, unless the corresponding
`back off timer already contains a non-zero value. In that
`event, the selection of a random number is not needed and
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 10
`
`Petitioner Motorola Mobility LLC - Exhibit 1001 - Page 10
`
`

`

`US 7,136,392 B2
`
`8
`7
`in FIG. 5, the contention window CW[i] of a queue takes the
`not performed. This process minimizes collisions during
`next value in a series every time an unsuccessful attempt to
`contention between multiple stations that have been defer-
`transmit a message data unit causes either Retry Counter of
`ring to the same event.
`that queue to increment, until CW[i] reaches the value of
`To both accommodate QoS services and ensure a fair
`5 CWmax. A retry iS defined as an entire sequence 0f frames
`allocation of transmission opportunities to all stations hav-
`sent, separated by QIFS intervals, in an attempt to deliver a
`ing trafiic of the same priority level
`to transmit,
`lower
`message data unit. Once it reaches CWmax, the contention
`priority queues defer to higher priority queues within the
`window Of a queue remains at the Value Of CWmax until it
`same stationa collisions between competing queues within a
`is reset. This improves the stability of the access protocol
`station are resolved within the station such that the higher
`priority queue receives the TXOP, and the lower priority 10 under high load conditions. It should be noted that although
`colliding queue(s) behave as if there were an external
`a Single value 0f CWmax common to all stations iS sug-
`collision on the wireless medium.
`gested in FIG. 5, it is also possible to provide differentiated
`With particular reference to FIG. 4, it will be appreciated
`CWmax[i] values for the respective queues.
`that a station is allowed a TxOP for a message unit of a
`In accordance with the illustrative embodiment of the
`particular traffic class if its carrier sense mechanism deter-
`15 present invention, the CWmin[i] values are set and updated
`mines that the medium is idle at a corresponding time slot
`by a QoS Parameter Set element that provides information
`boundary after a correctly-received frame, and the back olf
`needed by the stations for proper operation of the QoS
`time for that traffic class/queue has expired. According to the
`facility during each contention period (CP). This informa-
`illustrative embodiment of the invention, the highest priority
`tion includes the CP TXOP limit and the contention window
`traffic class is directed to a queue that waits for a minimum 20 values and QIFS values for prioritized channel access. The
`interframe space interval QIFSO before decrementing its
`format of the QoS Parameter Set element is shown in Table
`back olf counter while the lowest priority traffic class is
`I
`
`TABLE I
`
`QOS Parameter Settlement Format
`
`Element
`ID
`
`Length
`
`CP
`TXOP
`Limit
`
`(12)
`
`(26)
`
`(2 octets)
`
`35
`
`CWmin[TC] values QIFS[TC] values
`
`CWPFactor[TC]
`values
`
`.
`
`CWmin[O]. .
`CWmin[7]
`(8 octets)
`
`.
`
`.
`
`QIFS[O].
`QIFS[7]
`(8 octets)
`
`.
`
`CWPFactor[O].
`CWPFactor[7]
`(8 octets)
`
`.
`
`The Contention Period TxOP limit is a 2-octet field that
`directed to a queue that waits for a minimum interframe
`specifies the time limit on TxOPs by the stations.All TxOPs
`space interval QIFS7 before decrementing its back 01f
`during the CP last no longer than the number of 16-micr0-
`counter. As will be readily appreciated by those skilled in the
`second periods specified by the CP TxOP limit value. A CP
`art, the precise number 0f queues can vary from network to
`network 50 long as some mechanism exists for mapping the 40 TxOP limit value of 0 indicates that each TxOP during the
`message data units. to the. existing. queues in a manner that
`CP can be used to transmit a single at any rate in the
`accommodates their relative priorities.
`operational rate set of the QBSS.
`A station adapted for use in a QoS-enabled network in
`The CWmin[TC] values field contains 8 octets which
`accordance with an illustrative embodiment of the present
`specify,
`in the illustrative embodiment, eight contention
`invention calculates and maintains a back olf time and 45
`window values, for the eight traffic categories 0 through 7,
`respectively. Each contention window value is 1 octet in
`length and contains an unsigned integer. CWmin[TC] values
`update the CWmin[TC] values when received by a station.
`
`contention window for a queue when there are message data
`units to be transmitted from that queue. The back of
`calculation draws from differentiated intervals and replicates
`a contention window state for each queue i as follows:
`Back 01f Time[i]:Random(i)><aSlotTime
`
`Where:
`Rand0m(i):PseudO random integer drawn from a uniform
`distribution over the interval [1,CW[i1+ll;
`CW[i] is an integer within the range of values CWmin[i]
`and CWmax (or optionally aCWmax[i] if available); and
`CWmin[i]§CW[i]§CWmax.
`In accordance with the illustrative embodiment of the
`present invention, every station maintains, for each queue, a
`contention window (CW[i]) parameter and also Queue Short 60
`and Long Retry Counts (QSRC[i] and QLRC[i], respec-
`tively) that take an initial value of zero. A QSRC[i] is
`incremented whenever a respective Queue Short Retry
`Cotmt associated with a message data unit in a correspond-
`ing queue is incremented. A QLRC[i] is incremented when-
`ever a respective Queue Long Retry Count associated with
`a data in a corresponding queue is incremented. As be