(12) United States Patent
`Young et al.
`
`(10) Patent No.:
`45) Date of Patent:
`
`US 6,965,942 B1
`NOW. 15, 2005
`9
`
`USOO6965942B1
`
`(54) METHOD AND SYSTEM FOR IMPROVING
`
`FOREIGN PATENT DOCUMENTS
`
`CONTENTION WINDOW
`
`woo1/33739 A - 11/2000 . H04B 7212
`ERS' wo
`OTHER PUBLICATIONS
`M. Natkaniec, Analysis of the backoff mechanism used in
`75
`(75) Inventors: SR.NEAGS, IEEE 802.11 networks, 2000, Fifth IEEE Symposium on
`O'Hara, Santa Clara, CA (US); Seema
`Computers and Communications, Vol., Iss., 2000 pp. 444
`449.*
`San J
`CA (US). T
`St. S. CA Rs)
`I. Aad, Introducing Service Differentiation into IEEE 802.
`s
`s
`11, Jul. 2000, Fifth Symposium on Computers and Com
`(73) Assignee: 3Com Corporation, Santa Clara, CA
`munications, pp. 438-443.
`(US)
`P. Barker, Performance comparison of the IEEE 802.11 and
`Air infrared wireless MAC protocols, Dec. 1998, IEEE
`Communications Magazine, vol. 36, Issue 12, pp. 113-117.*
`J. Conover, Anatomy of IEEE 802.11b Wireless, Aug. 2000,
`http://www.network.computing.com/1115/1115ws22.html.*
`cited by examiner
`Primary Examiner-Ario Etienne
`Assistant Examiner-Ramy Osman
`(57)
`ABSTRACT
`
`(*) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 645 days.
`(21) Appl. No.: 09/759,389
`
`Jan. 12, 2001
`(22) Filed:
`(51) Int. Cl." ......................... G06F 15/16, H04L 1243
`(52) U.S. Cl. ...................... 709/232; 709/224; 709/230;
`370/447; 370/458; 370/461
`(58) Field of Search
`709/105, 224
`709/228, 230, 232-235; 370/280, 347,445,
`370/447, 458, 461
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,630.264 A 12/1986 Wah et al. .................. 3704
`5,420,572 A 5/1995 Dolin et al. ............. 340/825.5
`5,819,028 A * 10/1998 Manghirmalani et al. ... 709/224
`5,864,558 A
`1/1999 Johnson ...................... 370/445
`6,078,568 A * 6/2000 Wright et al................ 370/445
`6,285,662 B1* 9/2001 Watanabe et al............ 370/280
`6,587,453 B1* 7/2003 Romans et al. ............. 370/347
`6,697,013 B2 * 2/2004 McFarland et al. ......... 370/332
`6,754,176 B1* 6/2004 Gubbi et al................. 370/230
`6,845,123 B1* 1/2005 Nyberg et al. .............. 375/133
`2002/0110085 A1
`8/2002 Ho et al. .................... 370/230
`
`A method and System for increasing the overall network
`throughput over a wireless local area network (WLAN).
`Specifically, in one embodiment of the present invention, the
`dynamic Selection of an initial value for a contention win
`dow in the Distributed Coordinated Function (DCF) mode is
`determined according to the load conditions over the WLAN
`in a method and System. Stations and access points within a
`WLAN monitor conditions within the network to establish
`an initial value for the contention window, also called a
`minimum contention window value, which is lower than that
`set by the IEEE 802.11 communication standard. Some
`factors to consider in determining the load conditions
`include but are not limited to the following: number of
`transmissions, number of receptions, and number of colli
`Sions.
`
`24 Claims, 5 Drawing Sheets
`
`400
`
`
`
`Calculate the Number of Transmissions over
`The Network
`41
`
`Calculate the Nurber of Collisions Over The
`Networkby Adding The Number of virtual
`Carrier Serse Collisions to the Numer of
`Physical Carriersense Collisions
`420
`
`Calculate A Ratio of Collisions As:
`Number of Collisios
`Nuber of Nurser Collisions
`Tasissils
`
`Set An initial contention Window According to
`The Ratio of Celsions
`44
`
`Ex. 1025 / Page 1 of 13
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`US. Patent
`
`Nov. 15, 2005
`Nov. 15, 2005
`
`Sheet 1 of 5
`Sheet 1 0f 5
`
`US 6,965,942 B1
`US 6,965,942 B1
`
`
`
`E2965:39sz
`
`
`
`
`
`Ex. 1025 / Page 2 of 13
`ERICSSON v. UNILOC
`
`Ex. 1025 / Page 2 of 13
`ERICSSON v. UNILOC
`
`
`
`

`

`US. Patent
`
`N
`
`Mm.u,
`
`whS
`
`1B2495,696,SU
`
`$5.55End
`
`0250
`
`22259
`
`m.I8.
`
`
`sam
`
`o__§o>
`
`M9.
`
`60..
`
`56¢
`
`o_=m_o>-=oz
`
`.oloH
`
`aLommwuoi
`
`559:0
`
`
`
`70.:5:—.955
`
`59:5:0
`
`o_._wE:z.m:a_<
`
`$230
`
`8—.
`
`an
`
`cosmoEsEEoo
`
`
`
`.9230.6950
`
`gSac.
`
`a8383:55
`
`N.0."—
`
`Ex 1025 / Page 3 of 13
`ERICSSON v. UNILOC
`
`Ex. 1025 / Page 3 of 13
`ERICSSON v. UNILOC
`
`
`
`
`

`

`U.S. Patent
`
`Nov. 15, 2005
`
`Sheet 3 of 5
`
`US 6,965,942 B1
`
`
`
`
`
`ldle
`
`Monitor
`the Medium
`310
`
`
`
`
`
`
`
`Monitor
`Medium for
`DIFS
`Period
`320
`
`
`
`
`
`
`
`ldle
`
`Set Contention WindoW Value
`and Random Backoff Period
`330
`
`
`
`
`
`Monitor Medium Until Medium is
`Not Busy
`340
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Monitor
`the Medium for
`DIFS Period
`350
`
`Busy
`
`DOWn Backoff Timer
`While Medium is Clear. When
`Suspended, is Backoff Timer
`Equal to Zero?
`360
`
`Transmit
`390
`
`FIG. 3
`
`Ex. 1025 / Page 4 of 13
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Nov. 15, 2005
`
`Sheet 4 of 5
`
`US 6,965,942 B1
`
`START
`
`
`
`Calculate The Number Of Transmissions Over
`The NetWork
`410
`
`Calculate The Number Of Collisions Over The
`Network By Adding The Number Of Virtual
`Carrier Sense Collisions To The Number Of
`Physical Carrier Sense Collisions
`420
`
`Calculate A Ratio Of Collisions AS:
`
`Number Of Collisions
`
`Number Of + Number Of Collisions
`Transmissions
`430
`
`Set An Initial Contention Window According To
`The Ratio Of Collisions
`440
`
`FIG. 4
`
`Ex. 1025 / Page 5 of 13
`ERICSSON v. UNILOC
`
`

`

`U.S. Patent
`
`Nov. 15, 2005
`
`Sheet 5 of 5
`
`US 6,965,942 B1
`
`TABLE 500
`
`Percentage Ratio
`of Collision Counts
`
`Minimum Value
`for initial
`Contention WindoW
`
`O-25%
`
`>25-50%
`
`>50-75%
`
`>75%
`
`3
`
`7
`
`15
`
`31
`
`FIG. 5
`
`Ex. 1025 / Page 6 of 13
`ERICSSON v. UNILOC
`
`

`

`1
`METHOD AND SYSTEM FOR IMPROVING
`THROUGHPUT OVER WIRELESS LOCAL
`AREA NETWORKS WITH A DYNAMIC
`CONTENTION WINDOW
`
`BACKGROUND OF THE INVENTION
`
`1O
`
`15
`
`25
`
`1. Field of the Invention
`The present invention relates to the field of increasing
`throughput in wireless local area network communications.
`2. Related Art
`A wireless local area network (WLAN) is a transmission
`System that provides for network access between electronic
`devices that are wireless end Stations using radio waves
`instead of direct cable connections. In the IEEE 802.11
`standard, the WLAN consists of a number of basic service
`sets (BSS) that are joined by a distribution system into an
`extended service set (ESS). Within the ESS, a mobile unit or
`end Station may roam at will while continuously maintaining
`a connection to the network.
`Each BSS is controlled by an access point (AP). Each AP
`communicates with the end Stations over the wireleSS
`medium in its BSS. The AP communicates with other APs
`and other nodes on the network via the distribution System.
`A function of the AP, among many others, is to relay network
`traffic from the end stations in its BSS through the distri
`bution system to the destination. The destination of this
`traffic may be another end Station in the Same, or different,
`BSS, or the destination may be a node on a wired LAN (Such
`as ethernet) connected to the distribution system. The AP
`provides this relaying function for multiple mobile units
`simultaneously. The relaying of traffic for multiple end
`Stations results in an asymmetric distribution of the load
`entering a BSS.
`The IEEE 802.11 standard uses a default or basic access
`35
`mechanism implemented in the 802.11 Media Access Con
`trol (MAC) layer. The 802.11 MAC layer protocol is called
`the Distributed Coordination Function (hereinafter referred
`to as “DCF"), that provides fair access to all users of the
`WLAN.
`For example, in a BSS where the AP is relaying traffic for
`nine end Stations, and where the traffic from each end Station
`generates an equal amount of returned traffic to that end
`station, the IEEE 802.11 standard provides for the default
`DCF acceSS mechanism to provide fair access to all users,
`including the AP, of the WLAN.
`In the foregoing example, the available bandwidth of the
`BSS would be shared equally among the nine end stations
`and the AP, with each approximately receiving a minimum
`of ten percent of the available bandwidth. In a sense, there
`is Symmetric access to the network, where none of the end
`Stations nor the AP have network acceSS priority over the
`other users.
`Basically when using the DCF acceSS mechanism, a
`Station that Senses that the transmission medium is available
`is allowed to transmit over the WLAN. If the medium is not
`free, then the Station waits for a certain time before trying to
`transmit again. This waiting period is a called a backoff
`period. The IEEE 802.11 standard and its variations uses
`Carrier Sense Multiple Access with Collision Avoidance
`(CSMA/CA) mechanism with a random backoff for wireless
`connectivity between fixed, portable, and moving Stations
`within a local area.
`Furthermore, the backoff period is a delay of a random
`length. The backoff period is determined whenever a station
`detects that the medium is busy at the time the Station
`attempts to begin a transmission, or if it determines that a
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,965,942 B1
`
`2
`collision event has occurred because its transmission is not
`acknowledged according to the protocol operating rules. The
`backoff period is also used after each Successful transmis
`Sion. This delay is randomly Selected from a “contention
`window” that begins with a fixed value. For each subsequent
`collision event or busy condition of the medium that is
`detected for a given or Subsequent attempted transmission,
`the contention window Size is approximately doubled and a
`new random delay is Selected from the contention window.
`In the 802.11b standard, the initial value of the contention
`window is 31 slots. The sequence of contention window
`values is as follows: 31, 63, 127, 255, 511, to a maximum of
`1023 slots.
`AS a compromise between higher performance when the
`network is lightly loaded and minimizing the number of
`consecutive collisions as the load increases, the initial value
`of the contention window is relatively large. The result of
`having a large initial value for the contention window is that
`transmissions are delayed significantly after determining the
`medium is busy, Suffering a collision event, or on a trans
`mission attempt that immediately follows a Successful trans
`mission by the same station. While this is the desired
`behavior when the network is operating with a significant
`offered load, in lightly loaded conditions the delay is exces
`Sive and results in reduced overall throughput. Thus, a need
`exists for increasing throughput in a wireless local area
`network especially during lightly loaded conditions.
`
`SUMMARY OF THE INVENTION
`
`The present invention provides an apparatus and method
`which increases the overall network throughput over a
`wireless local area network (WLAN) during periods where
`the load conditions are light.
`Specifically, in one embodiment of the present invention,
`the dynamic Selection of minimum values for a contention
`window in the Distributed Coordinated Function (DCF)
`mode is determined according to the conditions over a
`wireless local area network (WLAN) in a method and
`system. Stations and access points within a WLAN monitor
`conditions within the network to establish an initial value for
`the contention window, which is also called a minimum
`contention window value, that is lower than that set by the
`IEEE 802.11 communication standard and its variations.
`Some factors to consider in monitoring overall network
`conditions include but are not limited to the following:
`number of transmissions, number of receptions, and number
`of collisions.
`In another embodiment of the present invention, a ratio of
`collision counts for a specific period of time over a WLAN
`is calculated in order to Set the minimum initial value for the
`contention window. Factors that are calculated to determine
`the ratio of collision counts are as follows: the number of
`transmissions over the WLAN, the number of virtual carrier
`sense (VCS) collisions; and the number of physical carrier
`sense (PCS) collisions. The total number of collisions is the
`number of Virtual carrier Sense collisions added to the
`number of physical carrier Sense collisions. The collision
`count ratio is calculated as follows:
`
`collision
`ratio
`
`number of collisions
`number of transmissions-- number of collisions
`
`In one embodiment of the present invention, the minimum
`value of the contention window is determined in relation to
`
`Ex. 1025 / Page 7 of 13
`ERICSSON v. UNILOC
`
`

`

`3
`the collision count ratio as a percentage. For higher ratios,
`the minimum value of the contention window approaches
`the IEEE 802.11b standard value of thirty-one slots. For
`lower ratioS, the minimum value of the contention window
`can approach values as low as Zero slots.
`These and other objects and advantages of the present
`invention will no doubt become obvious to those of ordinary
`skill in the art after having read the following detailed
`description of the preferred embodiments which are illus
`trated in the various drawing figures.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 illustrates a block diagram of a communication
`network environment that follows the IEEE 802.11 protocol
`in accordance with one embodiment of the present inven
`tion.
`FIG. 2 is a Schematic diagram of an exemplary computer
`System used to perform Steps in determining a minimum
`value for a contention window, in accordance with one
`embodiment of the present invention.
`FIG. 3 is a flow chart of steps performed for the operation
`of the CSMA/CA contention based IEEE 802.11 distributed
`coordinated function (DCF) access mechanism.
`FIG. 4 is a flow chart of steps performed for dynamically
`determining a minimum value for a contention window, in
`accordance with one embodiment of the present invention.
`FIG. 5 is a table of values used in calculating a minimum
`value for a contention window, in accordance with one
`embodiment of the present invention.
`The drawings referred to in this description should be
`understood as not being drawn to Scale except if specifically
`noted.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`Reference will now be made in detail to the preferred
`embodiments of the present invention, a method and System
`for increasing throughput in a wireleSS local area network
`(WLAN), examples of which are illustrated in the accom
`panying drawings. While the invention will be described in
`conjunction with the preferred embodiments, it will be
`understood that they are not intended to limit the invention
`to these embodiments. On the contrary, the invention is
`intended to cover alternatives, modifications and equiva
`lents, which may be included within the Spirit and Scope of
`the invention as defined by the appended claims. Further
`more, in the following detailed description of the present
`invention, numerous Specific details are Set forth in order to
`provide a thorough understanding of the present invention.
`However, it will be recognized by one of ordinary skill in the
`art that the present invention may be practiced without these
`Specific details. In other instances, well known methods,
`procedures, components, and circuits have not been
`described in detail as not to unnecessarily obscure aspects of
`the present invention.
`Notation and Nomenclature
`Some portions of the detailed descriptions which follow
`are presented in terms of procedures, Steps, logic blocks,
`processing, and other Symbolic representations of operations
`on data bits that can be performed on computer memory.
`These descriptions and representations are the means used
`by those skilled in the data processing arts to most effec
`tively convey the substance of their work to others skilled in
`the art. A procedure, computer executed Step, logic block,
`process, etc., is here, and generally, conceived to be a
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,965,942 B1
`
`4
`Self-consistent Sequence of Steps or instructions leading to a
`desired result. The Steps are those requiring physical
`manipulations of physical quantities. Usually, though not
`necessarily, these quantities take the form of electrical or
`magnetic signals capable of being Stored, transferred, com
`bined, compared, and otherwise manipulated in a computer
`System. It has proven convenient at times, principally for
`reasons of common usage, to refer to these signals as bits,
`values, elements, Symbols, characters, terms, numbers, or
`the like.
`It should be borne in mind, however, that all of these and
`Similar terms are to be associated with the appropriate
`physical quantities and are merely convenient labels applied
`to these quantities. Unless Specifically Stated otherwise as
`apparent from the following discussions, it is appreciated
`that throughout the present invention, discussions utilizing
`terms Such as “accessing “processing or “computing” or
`“translating” or “calculating” or “determining” or “scroll
`ing” or “displaying or “recognizing” or the like, refer to the
`action and processes of a computer System, or Similar
`electronic computing device, that manipulates and trans
`forms data represented as physical (electronic) quantities
`within the computer System's registers and memories into
`other data Similarly represented as physical quantities within
`the computer System memories or registers or other Such
`information Storage, transmission or display devices.
`IEEE 802.11 Communication Standard
`Some embodiments of the present invention are discussed
`primarily in a context in which devices and Systems are
`coupled using wireleSS links, and Specifically with regard to
`devices and Systems compliant with the IEEE 802.11 com
`munication Standard. However, it is appreciated that the
`present invention may be utilized with devices and Systems
`coupled using technologies, Standards, and/or communica
`tion protocols other than the IEEE 802.11 communication
`Standard.
`The 802.11 standard defines two modes of operation:
`infrastructure mode and ad hoc mode. In the infrastructure
`mode as shown in FIG. 1, the communication network 50 is
`comprised of wired and wireless networks. The wireless
`network consists of at least one access point (AP) connected
`to the wired network infrastructure and a set of wireless end
`Stations. This configuration describes a cell unit called a
`basic service set (BSS). Furthermore, an Extended Service
`Set (ESS) is a set of two or more BSSs forming a single
`subnetwork. Most corporate WLANs require access to the
`wired LAN for services (file servers, printers, Internet links)
`and would operate in the infrastructure mode.
`The ad hoc mode (also called peer-to-peer mode or an
`Independent Basic service Set, or IBSS) is simply a set of
`802.11 wireless stations that communicate directly with one
`another without using an access point or any connection to
`a wired network. This mode is useful for quickly and easily
`Setting up a wireleSS network anywhere that a wireleSS
`infrastructure does not exist or is not required for Services,
`Such as a hotel room, convention center, or airport, or where
`access to the wired network is barred (Such as for consultants
`at a client site).
`FIG. 1 shows two basic Service Sets in a communication
`network 50 operating in infrastructure mode, BSS-A110 and
`BSS-B 150. In BSS-A 110, an access point AP-A 112 is
`wired to the distribution system 130. Various end stations,
`A-1 114, A-2116, on up to A-n 118 are connected to AP-A
`through a wireless connection. Similarly, in BSS-B 150, an
`access point AP-B 152 is wired to the distribution system
`130. Various end stations, B-1154, B-2 156, and on up to
`
`Ex. 1025 / Page 8 of 13
`ERICSSON v. UNILOC
`
`

`

`US 6,965,942 B1
`
`15
`
`25
`
`S
`B-n 158 are connected to AP-B 152 through a wireless
`connection. The network 50 could support and operate with
`more than two basic Service Sets.
`The 802.11 Standard defines two pieces of equipment, a
`wireless end Station, which is usually a personal computer
`(PC) equipped with a wireless network interface card (NIC),
`but could be any electronic device operable under the 802.11
`Standard, and an access point (AP), which acts as a bridge
`between the wireless and wired networks.
`Wireless end stations can be 802.11 PC Card, Peripheral
`Component Interconnect (PCI), or Industry Standard Archi
`tecture (ISA) NICs, or embedded solutions in non-PC clients
`(Such as an 802.11-based telephone handset).
`An access point usually consists of a radio, a wired
`network interface (e.g. 802.3), and bridging Software con
`forming to the 802.11 bridging standard. The AP acts as the
`base Station for the wireleSS network, aggregating access for
`multiple wireleSS Stations onto the wired network, Such as
`the distribution system 130 in FIG. 1.
`Each BSS is controlled by an access point (AP). Each AP
`communicates with the end Stations over the wireleSS
`medium in its BSS. The AP communicates with other APs
`and other nodes on the network 50 via the distribution
`system 130. A function of the AP, among many others, is to
`relay network traffic from the end stations in its BSS through
`the distribution system to the destination. The destination of
`this traffic may be another wireleSS end Station in the same,
`or different, BSS, or the destination may be a node on a
`wired LAN (Such as ethernet) connected to the distribution
`system. The AP provides this relaying function for multiple
`end stations simultaneously. The relaying of traffic for
`multiple end Stations results in an asymmetric distribution of
`the load entering a BSS.
`The IEEE 802.11 standard uses a default or basic access
`35
`mechanism implemented in the 802.11 Media Access Con
`trol (MAC) layer. The 802.11 MAC layer protocol is called
`the Distributed Coordination Function (hereinafter referred
`to as “DCF"), that provides fair access to all users of the
`WLAN.
`Additionally, Since Stations on a network using radio
`transceivers cannot transmit and receive simultaneously on
`a single channel, the IEEE 802.11 wireless local area net
`working Standard use a Carrier Sense Multiple Access/
`Collision Avoidance (CSMA/CA) method when operating
`under the DCF access mechanism. Also, the IEEE 802.11
`standard uses CSMA/CA collision avoidance mechanism
`together with a positive acknowledgment of packets
`received to determine access to the network.
`Referring to FIG. 2, portions of the methods and systems
`for Selection of the minimum initial value for a contention
`window are comprised of computer-readable and computer
`executable instructions which reside, for example, in com
`puter-usable media of a computer System. FIG. 2 illustrates
`an exemplary computer system 100 used to perform the
`dynamic Selection of the minimum value for a contention
`window in accordance with embodiments of the present
`invention. It is appreciated that system 100 of FIG. 2 is
`exemplary only and that the present invention can operate
`within a number of different computer Systems including
`general purpose networked computer Systems, embedded
`computer Systems, and Stand-alone computer Systems. Addi
`tionally, computer system 100 of FIG. 2 is well adapted to
`having computer readable media Such as, for example, a
`floppy disk, a compact disc, and the like coupled thereto.
`Such computer readable media is not shown coupled to
`computer system 100 in FIG. 2 for purposes of clarity.
`
`6
`System 100 can include any computer-controlled software
`application for determining the minimum value of a con
`tention window. In general, computer System 100 comprises
`an address/data bus or other communication means 120 for
`communicating information, a central processor 101
`coupled with the bus 120 for processing information and
`instructions, a volatile memory 102 (e.g., random access
`memory (RAM), static RAM dynamic RAM, etc.) coupled
`with the bus 120 for storing information and instructions for
`the central processor 101, a non-volatile memory 103 (e.g.,
`read only memory (ROM), programmable ROM, flash
`memory, EPROM, EEPROM, etc.) coupled with the bus 120
`for Storing Static information and instructions for the pro
`cessor 101, a data storage device 104 (e.g., memory card,
`hard drive, optical disk, etc.) coupled with the bus 120 for
`storing information and instructions. System 100 of the
`present invention also includes an optional display device
`105 coupled to the bus 100 for displaying information to the
`computer user. System 100 also optionally includes an
`alphanumeric input device 106 including alphanumeric and
`function keys coupled to the buS 120 for communicating
`information and command Selections to the central processor
`101. System 100 also optionally includes a cursor control
`device 107 coupled to the bus for communicating user input
`information and command Selections to the central processor
`101, and an Input/Output (I/O) device 108 coupled to the bus
`120 for providing a communication link between computer
`system 100 and a network environment.
`The display device 105 of FIG. 2 utilized with the
`computer system 100 of the present invention may be a
`liquid crystal device, cathode ray tube, or other display
`device Suitable for creating graphic images and alphanu
`meric characters recognizable to the user. The cursor control
`device 107 allows the computer user to dynamically signal
`the two dimensional movement of a visible symbol (pointer)
`on a display screen of the display device 105. Many imple
`mentations of the cursor control device are known in the art
`including a trackball mouse, joystick or Special keys on the
`alphanumeric input device 105 capable of Signaling move
`ment of a given direction or manner of displacement. It is to
`be appreciated that the cursor means 107 also may be
`directed and/or activated via input from the keyboard using
`Special keys and key Sequence commands. Alternatively, the
`cursor may be directed and/or activated via input from a
`number of Specially adapted cursor directing devices or by
`other means Such as, for example, Voice commands. A more
`detailed discussion of the dynamic Selection of minimum
`values for a contention window method and System embodi
`ments of the present invention is found below.
`Dynamic Selection of Initial Values for a Contention
`Window
`Local area networking standards, such as the IEEE 802.11
`Standard, use an acceSS mechanism called Distributed Car
`rier Sense Multiple Access with Collision Avoidance
`(CSMA/CA). The CSMA/CA protocol involves selecting a
`delay of a random length whenever a Station detects that the
`medium is busy. This random delay is Selected from a
`“contention window” that begins with an initial value, or
`initial number of slots, where each slot is a period of 20
`microseconds in the IEEE 802.11b standard. For each Sub
`Sequent collision event or busy condition of the medium that
`is detected for a given transmission, the contention window
`Size is approximately doubled and a new random delay is
`Selected from the new contention window. A random delay
`is also Selected after each Successful transmission by a
`Station to prevent contiguous transmissions by a single
`station. The IEEE 802.11 standard and its variations use the
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Ex. 1025 / Page 9 of 13
`ERICSSON v. UNILOC
`
`

`

`7
`CSMA/CA protocol for transmission over the wireless local
`area network where each of the Stations and the access point
`(AP) operate under a distributed coordination function
`(DCF) access mechanism.
`For contextual purposes, the methods and Systems for
`dynamically Selecting a minimum value for a contention
`window can be used in a wireless local area network that
`follows the IEEE 802.11 communication standard and its
`variations. However, the present invention is well Suited to
`being used with other types of communications protocols
`and Standards.
`FIG. 3 illustrates the DCF access mechanism in process
`300 in one embodiment of the present invention. When
`using the DCF access mechanism, a Station wanting to
`transmit a data frame Senses the transmission medium or
`channel in step 310. Following the case where the medium
`is completely idle through process 300, if the medium is idle
`in step 310, then the station waits for an interval called
`distributed interframe space (DIFS) in step 320. If the
`medium again remains idle, then the process 300 Skips to
`step 390 and transmits the data frame.
`However, if in step 310 or 320 the medium is busy, then
`process 300 proceeds to step 330 where the contention
`window is set in the present embodiment. A backoff period
`is also randomly set from within this contention window in
`step 330. This backoff period sets the amount of time for a
`backoff counter to decrement to allow the Station to transmit
`the data frame.
`After the backoff period is set, the process 300 proceeds
`to step 340 where the station defers transmission and moni
`tors the medium until the current transmission is completed.
`In step 350, the station monitors the transmission medium
`for another DIFS period. If the medium becomes busy, then
`process 300 goes back to step 340. However, if the medium
`remains idle, then the process proceeds to Step 360.
`In step 360, the station begins to count down or decrement
`the backoff period set in the backoff counter. Whenever the
`channel is clear, the countdown continues. If the Station
`Senses the channel is busy, then the backoff counter Suspends
`the countdown until the channel is clear again whereupon it
`waits again for a DIFS period, and then Starts to countdown
`again. When the backoff counter reaches Zero, then the
`station is allowed to transmit the data frame in step 390.
`Although specific steps are disclosed in process 300 of
`FIG. 3, Such steps are exemplary. That is, the present
`invention is well Suited to performing various other Steps or
`variations of the steps recited in FIG. 3.
`Additionally, it is understood that process 300 of FIG. 3
`is exemplary of the IEEE 802.11 communication standard.
`Any other proceSS by which a station delays its transmis
`Sions utilizing either local information only or a combination
`of local information and information received from other
`stations may be substituted for process 300 in the present
`invention.
`The receiving Station checks the cyclic redundancy check
`(CRC) of the received packet and sends an acknowledgment
`packet (ACK) back to the transmitting station. When the
`transmitting Station receives the ACK from the receiving
`Station, the transmission was Successful. However, if the
`transmitting Station does not receive the ACK, then it will
`continue to retransmit until the transmission is Successful up
`to a given number of retransmissions upon which point the
`packets are discarded.
`In process 300, the backoff algorithm provides a method
`for reducing the contention between different Stations want
`ing to access a transmission medium. The backoff algorithm
`in process 300 is executed in the following three cases in one
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,965,942 B1
`
`8
`embodiment of the present invention, as follows: 1) when
`the station senses the medium is busy before the first
`transmission of a data frame; 2) after each retransmission;
`and 3) after each Successful transmission.
`Process 300 relies on Physical Carrier Sense, where the
`assumption is made that each Station can hear all the other
`stations within a BSS. However, one station may not always
`be able to hear another station within its BSS. In order to
`reduce collisions because one Station cannot hear another
`station, the IEEE 802.11 standard defines a Virtual Carrier
`Sense mechanism.
`The Virtual Carrier Sense mechanism relies on the fact
`that the access point (AP) is able to hear all the stations
`within a BSS. In this mechanism, a station is able to reserve
`the transmission medium for a Specified period of time. The
`Station wanting to transmit a data frame first transmits a
`short request to send (RTS) control packet to the AP which
`includes the Source, destination, and duration of the follow
`ing transmission. Upon receipt of the RTS, the AP responds
`with a clear to send (CTS) frame which specifies the period
`of time for which the medium is reserved. All stations
`receiving either the RTS or CTS frames will set their
`network allocation vector (NAV) accordingly for the given
`duration and will use this information together with the
`physical carrier Sense when Sensing the medium to deter
`mine whether the medium is busy or idle.
`In one embodiment of the present invention, the minimum
`value for the initial contention window is dynamically
`Selected to be a value that is less than the IEEE 802.11
`Standard according to the load conditions over the network.
`