Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 1 of 19
`
`
`
`
`Exhibit C
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 2 of 19
`I 1111111111111111 11111 1111111111 111111111111111 IIIII IIIII lll111111111111111
`US007027465B2
`
`c12) United States Patent
`Hautala
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 7,027,465 B2
`Apr. 11, 2006
`
`(54) METHOD FOR CONTENTION FREE
`TRAFFIC DETECTION
`
`(75)
`
`Inventor: Petri Hautala, Tampere (Fl)
`
`(73) Assignee: Nokia Corporation, Espoo (Fl)
`
`( *)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 433 days.
`
`(21)
`
`Appl. No.: 10/167,986
`
`(22)
`
`Filed:
`
`Jun. 11, 2002
`
`(65)
`
`Prior Publication Data
`
`US 2004/0013134 Al
`
`Jan. 22, 2004
`
`Related U.S. Application Data
`
`(63) Continuation of application No. PCT/EP99/10097,
`filed on Dec. 17, 1999.
`
`(51)
`
`Int. Cl.
`H04J 3107
`(2006.01)
`(52) U.S. Cl. ....................................... 370/506; 370/350
`(58) Field of Classification Search ................ 370/252,
`370/286, 304, 324, 349, 350, 395.43, 444,
`370/506, 509, 512, 229, 230, 230.1, 235,
`370/241
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,627,051 A
`4,716,407 A
`4,930,124 A
`5,594,738 A
`
`12/1986 Shimizu
`12/1987 Borras et al.
`5/ 1990 de Boisseron et al.
`l/ 1997 Crisler et al.
`
`5,675,617 A *
`5,678,188 A
`5,822,361 A
`5,857,092 A *
`5,881,242 A *
`6,658,363 Bl *
`
`10/1997 Quirk et al ................. 375/365
`10/1997 Hisamura
`10/1998 Nakamura et al.
`1/1999 Nakamura et al ............. 710/62
`3/1999 Ku et al.
`.................... 709/238
`12/2003 Mejia et al ................. 702/125
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`
`0491494
`0584667
`0749254
`0782297
`0804006
`0917317
`0959398
`
`6/1992
`3/1994
`12/1996
`7 /1997
`10/1997
`5/1999
`11/1999
`
`OTHER PUBLICATIONS
`
`"Wireless LANs and Mobile Networking: Standards and
`Future Directions" by R.O. LaMaire, et al, IEEE Commu(cid:173)
`nications Magazine, 'Online! Aug. 1996, pp. 1-15.
`
`* cited by examiner
`
`Primary Examiner-Dang Ton
`Assistant Examiner-Phuc Tran
`
`(57)
`
`ABSTRACT
`
`The invention discloses a method for detecting priority of
`data frames comprising the steps of extracting (Sl) a bit
`pattern from a predetermined position in a frame, comparing
`(S2, S3) the extracted bit pattern with a search pattern, and
`identifying (S4) the received frame as a priority frame in
`case the extracted bit pattern (BP) matches with the first
`search pattern (SP). By this method, the priority of a data
`frame can easily be detected. The invention also proposes a
`corresponding device for detecting priority of data frames.
`
`18 Claims, 10 Drawing Sheets
`
`START
`
`S1
`
`EXTRACT BIT PATTERN BP
`FROM FRAME
`
`COMPARE BIT PATTERN
`BP WITH SEARCH
`PATTERN SP
`
`NO
`
`S2
`
`S3
`
`S4
`
`PRIORITY FRAME
`
`NO PRIORITY FRAME
`
`S5
`
`RETURN
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 3 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 1 of 10
`
`US 7,027,465 B2
`
`•
`
`C) -u.
`
`Wz
`IO
`I-_
`C) I-~
`z<C <C
`0:: 0:::
`-
`z ::> C)
`z C) 0
`::> u:: 0::
`0::: z 0...
`<Co
`1-o
`Cf)
`
`<(
`I-(cid:173)
`Cf)
`
`Cl)
`
`Cl) w
`...J ~
`0::: 0:::
`3;: 0
`0:: ~
`
`QI-ow Wz
`
`0::
`~
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 4 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 2 of 10
`
`US 7,027,465 B2
`
`START
`
`S
`
`1
`
`EXTRACT BIT PATTERN BP
`FROM FRAME
`
`COMPARE BIT PATTERN
`BP WITH SEARCH
`PATTERN SP
`
`NO
`
`S2
`
`S3
`
`S4
`
`PRIORITY FRAME
`
`NO PRIORITY FRAME
`
`S5
`
`RETURN
`
`FIG. 2
`
`MAC FRAME
`
`OS
`
`COMPARE
`
`SP
`
`FIG. 3
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 5 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 3 of 10
`
`US 7,027,465 B2
`
`TO/FROM NETWORK
`
`H
`
`'
`
`22
`
`FRAME
`RECEIVER
`
`I
`
`INFORMATION
`ELEMENT
`RECEIVER
`
`28
`
`I
`
`23
`
`BIT PATTERN
`EXTRACTOR
`
`-
`
`OFFSET
`MEMORY
`
`27
`
`I
`COMPARATOR -
`I
`
`PRIORITY
`IDENTIFYING
`MEANS
`
`24
`
`26
`
`SEARCH
`PATTERN
`MEMORY
`
`-
`
`25
`
`FIG. 4
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 6 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 4 of 10
`
`US 7,027,465 B2
`
`~
`(/}
`<(
`2
`I a
`
`I- 0 s8
`(9 ..... z8
`~o
`(/} II
`N
`<(N
`D..
`co 22
`
`0
`0
`0
`.....
`0
`0
`0
`0
`
`N
`Cl.
`CD
`
`.....
`.....
`.....
`0
`.....
`.....
`.....
`
`0
`
`It)
`•
`(!)
`LL
`
`-
`
`.....
`0
`..-
`.....
`..-
`0
`0
`..-
`.....
`0
`0
`...-
`.....
`0
`.....
`0
`
`..-
`D..
`en
`
`(f)
`w
`~
`m
`._,.
`0
`......
`II
`N
`(/)
`0
`
`(f)
`w
`I-
`>-
`m
`
`I{)
`
`N ...-
`II
`......
`(/)
`0
`
`u..
`
`N
`D..
`(f)
`
`0
`0
`0
`.....
`0
`0
`0
`0
`
`.....
`.....
`0
`.....
`.....
`0
`.....
`0
`.....
`0
`.....
`0
`.....
`0
`.....
`0
`
`T'""
`Cl.
`(f)
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 7 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 5 of 10
`
`US 7,027,465 B2
`
`CFPACTIVE
`
`S61
`
`NO
`
`YES
`
`S62
`
`EXTRACT BIT PATTERNS
`BP1 AND BP2 FROM
`FRAME F
`
`S63
`
`MASK BP2 WITH MASK M2
`TO OBTAIN BP2'
`
`S64
`
`MATCH OF
`SP1 WITH BP1 AND
`SP2 WITH BPZ'?
`
`NO
`
`YES
`
`S65
`
`FRAME TO PRIORITY
`QUEUE
`
`FRAME TO NORMAL
`QUEUE
`
`S66
`
`RETURN
`
`FIG. 6
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 8 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 6 of 10
`
`US 7,027,465 B2
`
`PRIORITY FRAMES
`
`212
`
`PRIORITY
`FRAMES
`COUNTER (PFC)
`
`213
`
`PFOCFP
`COUNTER
`
`PC
`CONTROLLER
`
`214
`
`CFP DTIM
`COUNTER
`
`NORMAL
`QUEUE
`
`215
`
`PRIORITY
`QUEUE
`
`216
`
`211
`
`FIG. 7
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 9 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 7 of 10
`
`US 7,027,465 B2
`
`CFPACTIVE
`
`S81
`
`FRAME RECEIVED?
`
`NO
`
`S82
`
`EXTRACT BIT PATTERNS
`BP1 AND BP2 FROM
`FRAME F
`
`S83
`
`MASK BP2 WITH MASK M2
`TO OBTAIN BP2'
`
`S84
`
`MATCH OF
`SP1 WITH BP1 AND
`SP2 WITH BP2'?
`
`NO
`
`YES
`
`S85
`
`FRAME TO HIGH PRIORITY
`QUEUE
`
`FRAME TO NORMAL
`QUEUE
`
`S86
`
`S87
`
`PFC= PFC+ 1
`
`RETURN
`
`FIG. 8
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 10 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 8 of 10
`
`US 7,027,465 B2
`
`NO
`
`NO
`
`NO
`
`CFP INACTIVE
`
`S91
`
`S92
`
`S93
`
`PFOCFP = PFOCFP + 1
`
`S94
`
`PFC= PFC+ 1
`
`S95
`
`S96
`
`CFP DTIM COUNTER=
`CFP DTIM COUNTER+ 1
`
`S97
`
`FRAME TO NORMAL
`QUEUE
`
`RETURN
`
`FIG. 9
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 11 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 9 of 10
`
`US 7,027,465 B2
`
`START
`
`S101
`
`DTIM AFTER CFP END
`
`>HAL
`
`ELSE
`
`S107
`
`CFPINTERVAL=(CFP
`INTERVAL x 2) OR (MAX.
`CFPINTERVAL
`
`S104
`
`CFPDTIM
`COUNTER/({PFC -
`(PFOCFP - CFP DTIM
`S105
`OUNTER})/10
`
`ELSE
`
`CFP DURATION= (CFP
`DURATION/2) OR MIN. CFP
`DURATION
`
`S106
`
`CFP INTERVAL= (CFP
`INTERVAL/ 2) OR (MIN.
`CFPINTERVAL
`
`S108
`
`CFP DTIM
`COUNTER/((PFC(cid:173)
`(PFOCFP - CFP DTIM
`OUNTER))/10
`
`CFP DURATION= {CFP
`DURATION x 2) OR MAX.
`CFP DURATION
`
`S1010
`
`PFC=0
`PFOCFP=O
`CFP DTIM COUNTER = 0
`
`S1011
`
`RETURN
`
`FIG. 10
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 12 of 19
`
`U.S. Patent
`
`Apr. 11, 2006
`
`Sheet 10 of 10
`
`US 7,027,465 B2
`
`SlART
`
`S111
`
`IDENTIFY BIT PATTERN
`CONTAINING PRIORITY
`INFORMATION
`
`S112
`
`STORE IDENTIFIED BIT
`PATTERN AS SEARCH
`PATTERN
`
`S113
`
`DETERMINE OFFSET OF
`BIT PATTERN LOCATION
`
`S114
`
`PRODUCE INFORMATION
`ELEMENT CONTAINING
`OFFSET AND SEARCH
`PATTERN
`
`S115
`
`SEND INFORMATION
`ELEMENT TO AP
`
`RETURN
`
`FIG. 11
`
`BEACO_N_S~1-------.-,-FP_...---_,__r-l ----r---.---+-1--C--.-FP __
`
`~M
`
`~M
`
`~M
`
`CFP REPETITION INTERVAL
`
`FIG. 12
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 13 of 19
`
`US 7,027,465 B2
`
`1
`METHOD FOR CONTENTION FREE
`TRAFFIC DETECTION
`
`CROSS-REFERENCE TO RELATED
`APPLICATION
`
`This application is a continuation of International Appli(cid:173)
`cation PCT/EP99/10097 having an international filing date
`of Dec. 17, 1999 and from which priority is claimed under
`all applicable sections of Title 35 of the United States Code
`including, but not limited to, Sections 120, 363 and 365(c).
`
`FIELD OF THE INVENTION
`
`The present invention relates to a method and a device for 15
`detecting priority of data frames in a network.
`
`2
`have to be known. Hence, the amount of information needed
`for identifying the data is huge. This huge amount of
`information is typically too heavy to handle in quite small
`and low price equipment like WLAN access points (AP).
`In addition, it has to be considered that every time new
`protocols are introduced, the access point has to be updated,
`at least by software updates. This is also required in case
`protocols already used are changed.
`Thus, conventionally such a transmission differentiation
`10 based on priority was not conducted at all. That is, the
`existing systems according to the IEEE 802.11 standard do
`not separate traffic based on priority. In these conventional
`systems, the Content Free Period (CFP) is only used to
`deliver traffic from the Access Point (AP) to stations, treat(cid:173)
`ing all frames equally.
`
`BACKGROUND OF THE INVENTION
`
`SUMMARY OF THE INVENTION
`
`This invention relates in general to the field of telecom(cid:173)
`munications, more precisely to Wireless Local Area Net(cid:173)
`works (WLAN) and Electrical and Electronics Engineers
`(IEEE) 802.11 WLAN standard.
`The IEEE 802.11 Wireless Local Area Network specifi(cid:173)
`cation specifies a so-called Contention Free Period (CFP),
`which is a period of transmission time that is free from the
`normal contention based airtime reservation. The length and
`duration of CFP are configurable parameters in Access Point
`(AP), so that the start of CFP is repeated after one or more
`Delivery Traffic Indication Message (DTIM) intervals (see 30
`IEEE 802.11 standard). The CFP and its relationship to the
`so-called Content Period (CP) is schematically illustrated in
`FIG. 12. As can be seen, a CFP repetition interval contains
`a Content Free Period (CFP) and a Content Period (CP).
`Each CFP begins with a beacon frame that contains a DTIM
`element.
`The purpose of this CFP is that it can be used for
`delivering high priority traffic, which has higher real time
`requirements than normal traffic. The CFP is controlled by
`the so-called Point Coordination Function (PCF) in an
`Access Point (AP). The standard specifies the PCF operation
`in basic level, but does not specify how the PCF should be
`controlled or how some traffic should be identified as high
`priority traffic. These things are considered to be out of the
`scope of the standard.
`Information within data frames is marked as having a high
`priority by using certain fields in some protocol frames or
`headers. However, the Access Point (AP) usually processes
`only frames on the Medium Access Control (MAC) layer
`such that the AP can not easily access information regarding
`the priority of certain data blocks within the frames, since
`this information is processed in higher layers.
`Thus, for getting priority information, conventionally the
`frames which are to be transmitted through an Access Point
`(AP) had to be searched for these fields which indicate the
`priority state of the actual data frame. This means that in all
`frames all fields had to be checked, all the headers had to be
`analyzed, starting from the outer most headers, until the
`right field in the header had been found.
`Since all frame headers are parsed when detecting prior- 60
`ity, this measure has a high reliability.
`However, this measure is very complex, takes a long time
`and requires a large amount of processing. Furthermore, the
`traffic transferred in WLAN can be practically anything,
`including complex tunneling protocols.
`Therefore, all the frame headers and protocols which can
`be included in the data frames transmitted via the network
`
`Therefore, the object underlying the invention resides in
`20 removing the above drawbacks of the prior art and to
`provide a method by which priority traffic can easily be
`distinguished from normal traffic without the need of a
`complex processing.
`This object is solved by a method for detecting priority of
`25 data frames in a network comprising the steps of extracting
`a bit pattern from a predetermined position in a frame,
`comparing the extracted bit pattern with a search pattern,
`and identifying the received frame as a priority frame in case
`the extracted bit pattern matches with the first search pattern.
`Alternatively, the above object is solved by a device for
`detecting priority of data frames in a network comprising a
`receiving means for receiving data frames, an extracting
`means for extracting a bit pattern from a predetermined
`position of a data frame, a comparing means for comparing
`35 the extracted bit pattern with a predetermined search pattern,
`and an identifying means for identifying the received frame
`as a priority frame in case the extracted bit pattern matches
`with the first search pattern.
`Thus, a priority which is defined in a higher-level layer
`40 can easily be detected by comparing a corresponding bit
`pattern with a search pattern without further processing of
`the received frame. By the method and the device according
`to the invention, simply a bit pattern is extracted at a position
`in the frame, where the priority information is known to be
`45 located. This bit pattern is compared with a search pattern
`which corresponds to that bit pattern, which would be
`located at the above position in case that a priority is set for
`the actual frame. Thus, it is not necessary to process and
`analyze the received frame, i.e., to process higher-level
`50 layers in order to obtain priority information.
`Hence, when adopting the IEEE 802.11 WLAN standard,
`the priority can be detected in the Medium Access Control
`(MAC) layer which is a low-level layer. That is, the method
`can easily find higher priority traffic from the stream of
`55 MAC layer frames. Therefore, the method does not need any
`knowledge of the upper layer protocols.
`Consequently, according to the method of the invention,
`certain traffic can be defined to have higher priority than
`other traffic when it is handled in an IEEE 802.11 WLAN
`Access Point (AP). The method is designed so that it is as
`lightweight as possible to execute in a low cost and possibly
`low performance AP.
`Furthermore, the method is protocol-independent and so
`flexible that all the configuration may be done in external
`65 configuration program and the Access Point does not need to
`know anything about the processed traffic.
`Further advantageous developments are set out below.
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 14 of 19
`
`US 7,027,465 B2
`
`4
`transmitting priority frames in case of a symmetrical high
`priority traffic between the Access Point and stations in the
`network.
`Furthermore, the invention proposes a method for gener(cid:173)
`ating priority detecting information necessary for the above
`method and device. This method comprises the steps of
`analyzing a data frame, identifying a bit pattern indicating a
`priority state, defining the identified bit pattern as a search
`pattern, and locating the bit pattern within the data frame. By
`this method, the necessary priority detection information can
`easily be provided. For example, this method can be
`employed by a configuration program that is externally run,
`for example, in one of the wireless stations which are
`connected by air with the Access Point.
`The above method for generating priority detecting infor-
`mation may further comprise the steps of determining the
`offset of the location, and producing an information element
`including the offset and the search pattern. Optionally, also
`the mask for masking the bit pattern mentioned above can be
`20 determined and included in the information element.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`3
`In particular, the predetermined position in the frame is
`defined by the offset of the bit pattern in the frame. Thus, the
`position of the bit pattern to be extracted and examined can
`accurately be defined.
`Furthermore, the offset and the search pattern are included 5
`in an information element. This information element can be
`produced by an external program such that the device
`according to the invention and the device performing the
`method according to the invention does not have to generate
`the search pattern and the offset. Thus, the structure of the 10
`device does not have to be complex.
`In addition, in case new protocols or modified protocols
`are introduced in the network, it is not necessary to recon(cid:173)
`figure the network element (i.e., the device) performing the
`method. It is only necessary to provide new information 15
`elements including the new offset and the new search
`pattern, which can be effected by an external configuration
`program. For this, it is not necessary to install new software
`in the network element or to install new hardware. It is not
`even necessary to shut down the network element for a new
`configuration. Hence, the method is very flexible.
`Moreover, the bit pattern can be masked by using a mask.
`Then, the masked bit pattern is compared with the search
`pattern instead of comparing the bit pattern with the search
`pattern. By this measure, single bits can easily be extracted 25
`from the bit pattern. This is advantageous in case the bit
`pattern is extracted in form of bytes. For example, a bit
`pattern can include two bytes, whereas for the priority
`detection only two bits of each byte are required. These two
`bits can easily be extracted by using the mask.
`The mask can also be included in the information element
`described above.
`If necessary, also a plurality of different bit patterns,
`search patterns, offsets and----optionally-masks can be used
`to detect priority of the frames. By this measure, priority
`information can be detected which is located at different
`positions within a data frame.
`Alternatively, a plurality of different priority levels can be
`provided for the frames. For detecting different priority
`levels, a plurality of different bit patterns, search patterns,
`offsets and----optionally-masks can be used to detect the
`plurality of different priority levels. By this measure, also
`different priority levels can easily be detected.
`Hence, a plurality of different information elements can
`be used. For example, one certain priority can require a
`plurality of information elements, while another certain
`priority can require only one particular information element.
`A received frame can be forwarded to a priority queue in
`case the frame is detected to be a priority frame during a 50
`special period for sending priority traffic. The priority queue
`serves to transmit the data priority frames in the network
`faster than normal frames. This measure is especially advan(cid:173)
`tageous in an IEEE 802.11 WLAN since in this standard, a
`Contention Free Period is defined, as described above.
`In addition, the duration of the special period for sending
`priority traffic can be adjusted according statistical informa(cid:173)
`tion regarding the priority frames sent. Thus, the special
`period, i.e., the Contention Free Period, can be adjusted
`corresponding to the load of priority traffic on the network. 60
`Furthermore, for obtaining the statistical information, the
`total number of priority frames and the number of priority
`frames outside the special period can be counted. Then, it
`can be decided on the basis of the count values obtained
`whether the special period has to be increased or decreased.
`In addition, in the IEEE 802.11, a data+CF-poll frame is
`defined. Preferably, this data+CF-poll frame can be used for
`
`The present invention will be more readily understood
`with reference to the accompanying drawings in which:
`FIG. 1 shows a main system overview;
`FIG. 2 shows a process for checking priority of frames
`according to a first embodiment;
`FIG. 3 shows an example for a frame to be examined by
`30 the process according to the first embodiment;
`FIG. 4 shows a frame priority detecting device according
`to the first embodiment;
`FIG. 5 shows an example of pattern matching with two
`different information elements according to a second
`35 embodiment;
`FIG. 6 illustrates a flow chart of a frame sending proce(cid:173)
`dure during Content Free Period (CFP) according to the
`second embodiment;
`FIG. 7 shows relevant parts of a Point Coordinator (PC)
`40 according to a third embodiment;
`FIG. 8 illustrates a flow chart of a frame sending proce(cid:173)
`dure during Content Free Period (CFP) according to the
`third embodiment;
`FIG. 9 illustrates a flow chart of a frame sending proce-
`dure during contention period according to the third embodi(cid:173)
`ment; and
`FIG. 10 illustrates a flow chart of a procedure for CFP
`parameter tuning according to the third embodiment;
`FIG. 11 shows a flow chart of a method for obtaining
`priority detection information; and
`FIG. 12 illustrates the relationship between Content Free
`Periods (CFP) and Content Periods (CP) according to IEEE
`802.11.
`
`45
`
`55
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`In the following, preferred embodiments of the invention
`are described in more detail with reference to the accom(cid:173)
`panying drawings.
`FIG. 1 shows an overview of the main system used in the
`embodiments. The system is a normal IEEE 802.11 Basic
`Service Set (BSS) containing one Access point (AP) 2 and
`65 one or more wireless stations (STA) 3 to 5. The AP may or
`may not be connected to another wired or wireless network
`1. The purpose of the AP 2 is to transmit the traffic between
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 15 of 19
`
`US 7,027,465 B2
`
`5
`the wireless stations or between wireless stations and the
`network 1 which is connected to the AP 2.
`All the network components function according to the
`IEEE 802.11 standard. This presented set-up is a typical
`representation of the coverage area of one AP. The whole
`wireless network usually consists of several of these kinds of
`subsystems. An external configuration program may run in
`one of the stations in the wireless network or it may reside
`in some other host and be connected to AP with a wire. In
`this example, the configuration program is executed in the 10
`wireless station 3.
`In the following, a first embodiment which shows the
`basic idea of the invention is described with respect to the
`flow chart shown in FIG. 2 and an example for a Medium
`Access Control (MAC) layer frame shown in FIG. 3.
`The procedure shown in FIG. 2 is executed by the Access
`Point AP 2 every time a Medium Access Control (MAC)
`layer frame has been received.
`In step Sl, the AP 2 extracts a bit pattern from a given
`position in the received frame. The bit pattern can be a 20
`pattern of two bytes, for example. However, the length of the
`bit pattern can be selected arbitrarily. The extracted bit
`pattern is indicated by BP in FIG. 2. In step S2, the extracted
`bit pattern BP is compared with a predetermined search
`pattern SP. If in step S3 it is decided that both patterns match, 25
`it is determined in step S4 that the actual frame is a priority
`frame. On the other hand, if it is decided in step S3 that both
`patterns do not match, it is determined in step S5 that the
`actual frame is not a priority frame. After identifying the
`priority of the frame, the frame can be treated according to 30
`the identified priority.
`Thus, the frame can easily be examined whether it is a
`priority frame or not without the need for analyzing the data
`format in the MAC layer frame itself, i.e., without knowing
`protocols of the higher layers.
`The position of the bit pattern to be extracted is defined by
`the offset OS from the start of the MAC frame, as shown in
`FIG. 3. Thus, the AP 2 requires only information regarding
`the offset OS and the search pattern SP for checking priority
`of certain MAC frames.
`This information can be provided by an external configu(cid:173)
`ration program. The configuration program can be executed
`in one of the wireless stations, for example. Alternatively, it
`can be executed in any suitable network element, including
`the Access Point itself. For this configuration program it is 45
`necessary that the bit positions of the priority information
`which are usually set in higher layers are known. Thus, by
`providing the AP with the offset, the AP does not have to
`process the frame in order to identify priority information. It
`is only necessary to obtain the corresponding bit pattern.
`In the first embodiment, the configuration program is
`executed in the wireless station STA 3. The configuration
`program produces information elements which contain the
`above-described information regarding the offset OS and the
`search pattern SP necessary to identify the priority state of 55
`certain MAC frames. These information elements are trans(cid:173)
`mitted to the AP 2.
`FIG. 4 shows the relevant parts of the Access Point 2 in
`more detail. Reference numeral 22 denotes a frame receiver
`by which frames are received from the wired or wireless
`network 1 and also from the wireless stations 2 to 5.
`Reference numeral 23 denotes a bit pattern extractor by
`which the bit pattern BP described above is extracted from
`a predetermined position. The position is defined by the
`offset OS, as mentioned above, and the offset is stored in an
`offset memory 27 which is accessed by the bit pattern
`extractor 23. The extracted bit pattern BP is forwarded to a
`
`6
`comparator 24 which compares the extracted bit pattern BP
`with the search pattern SP. The search pattern SP is stored in
`a search pattern memory 25 which is accessed by the
`comparator 24. The comparison result is supplied to a
`5 priority identifying means 26 which identifies the actual
`frame F as a priority frame in case the comparison results
`indicates that the bit pattern BP matches the search pattern
`SP. Thus, the Access Point (AP) 2 can detect priority frames
`and can treat them correspondingly.
`As mentioned above, the external configuration program
`provides information elements which each comprise an
`offset OS and a search pattern SP. These information ele(cid:173)
`ments are received by an information element receiver 28.
`The receiver 28 analyzes the information element and sup-
`15 plies the detected offset OS to the offset memory 27 and the
`detected search pattern SP to the search pattern memory 25.
`The first embodiment described above illustrates the basic
`operation according to the invention. The second embodi(cid:173)
`ment described in the following describes a further, more
`detailed example for the high priority traffic detection
`method in which the Content Free Period (CFP) defined in
`IEEE 802.11 standard is used for transmitting detected high
`priority frames.
`According to IEEE 802.11, the Content Free Period (CFP)
`is a period which is reserved for transmitting high priority
`traffic, as described above in the introductory part with
`respect to FIG. 12. The CFP is controlled by a Point
`Coordinator (PC) 21 which is arranged in the Access Point
`(AP) 2 shown in FIG. 1. If the high priority traffic is
`transferred only from the AP 1 to the wireless stations (i.e.,
`in a typical client-server application case), the CFP may be
`used only for delivering data from the AP to wireless
`stations. But, if the nature of the high priority traffic is
`interactive (like a videoconference, for example), the PC 21
`35 must also poll wireless stations to permit them to transmit
`also during the CFP. See IEEE 802.11 standard for more
`detailed description about this basic functionality of IEEE
`802.11 standard.
`The AP 2 receives MAC layer frames either from the
`40 wireless station or from the connected wired network. If the
`destination of the frame is in the wireless network, the AP
`will check whether the frame is high or normal priority
`traffic. The priority detection requires that the AP 2 is
`configured with the external configuration program to detect
`the priority and the required configuration information ele(cid:173)
`ments are configured to the AP by the external configuration
`program. The AP also needs to reformat the MAC level
`header of the frame or encapsulate the frame inside a
`separate IEEE 802.11 MAC header which is defined in IEEE
`50 802.11. The point when the priority detection check is
`performed (before or after IEEE 802.11 MAC header for(cid:173)
`matting) can be left implementation specific.
`If the BSS is in a so-called Contention Free (CF) state
`(i.e., currently there is a Contention Free Period (CFP)) and
`the frame is a priority frame, the frame is put in a priority
`transmit queue, otherwise the frame is treated like the
`normal traffic. During the CFP, all the frames in the priority
`queue are transmitted before any frames from the normal
`queue. When the CFP ends, remaining frames in the priority
`60 queue are moved to the normal queue and priority queue is
`flushed.
`According to this embodiment, the priority of a MAC
`layer frame is detected by using one or more information
`elements which are transmitted to the Access Point (AP) 1.
`65 That is, one or more bit patterns with corresponding different
`offsets are checked whether they match with one or more
`different search patterns. Furthermore, the bit patterns
`
`

`

`Case 1:20-cv-07529 Document 1-3 Filed 09/14/20 Page 16 of 19
`
`US 7,027,465 B2
`
`5
`
`7
`extracted from the MAC layer frame are also masked by
`using a mask. The mask is also contained in an information
`element. Thus, the information element according to the
`second embodiment comprises the offset and the search
`pattern as according to the first embodiment, and in addition
`a mask. The mask serves to obtain only particular bits in the
`extracted bit pattern and is optional.
`The operation according to the second embodiment is
`described by referring to FIGS. 5 and 6. It is noted that for
`simplifying the illustration, the second embodiment is 10
`described with reference to the case that the priority is
`detected by using two information elements.
`In FIG. 5 it is shown that two bit patterns BPl and BP2
`are extracted from the MAC layer frame F. The first bit
`pattern BPl is extracted with an offset OSl. As illustrated, 15
`the first bit pattern matches with the first search pattern SPl.
`For the first bit pattern BPl, no mask has been specified (i.e.,
`no masking is performed).
`However, for the second bit pattern BPl a mask M2 is
`specified. In this example, the mask is M2=00010000 such 20
`that only the fourth bit is passed through. The resultant bit
`pattern BP2' is then compared with the second search pattern
`SP2. Here, the second search pattern SP2 and the masked bit
`pattern BP2' match. Since also the first search pattern SPl
`matches with the first bit pattern BPl, it is decided that the 25
`actual frame F is a high priority frame.
`According to the second embodiment, the frame F which
`has been detected as a priority frame, is transmitted in the
`Contention Free Period (CFP). That is, it is put on a high
`priority queue. This process is described in the following by 30
`referring to the flow chart shown in FIG. 6.
`The process shown in this flow chart is performed during
`the Content Free Period, i.e., in case the CFP is active. In
`step S61, the Access Point (AP) 2 waits for receiving a frame
`which is to be transmitted further to the wireless stations 3 35
`to 5 (FIG. 1). In step S62, the bit patterns BPl and BP2 are
`extracted from the frame F, as shown in FIG. 5. In step S63,
`the bit pattern BP2 is masked with the mask M2 to obtain a
`bit pattern BP2', as described above. Since no mask has been
`specified for the first bit pattern BPl, no corresponding step 40
`for the first bit pattern BPl is performed.
`Then, in step S64, it is checked whether both bit patterns
`BPl and BP2' match with the search patterns SPl and SP2,
`respectively. lfSPl and BPl, and SP2 and BP2' respectively
`match, it is decided that the received frame F is a high 45
`priority frame, and the frame F is put in the priority queue
`(step S65). This is effected by the Point Coordinator (PC) 21
`arranged in the Access Point (AP) 2. If the patterns do not
`match (NO in step S64), the received frame F is put in the
`normal queue, as shown in step S66.
`As described above, the Point Coordinator (PC) 21 puts a
`priority frame in the priority queue in case the Contention
`Free Period (CFP) is active. However, in case the CFP is
`inactive, the frame goes to the normal queue so that it does
`not have to wait for the CFP to start. When the CFP starts, 55
`the PC flushes the normal queue and places the unsent high
`priority frames in the priority queue. Thus, when the Point
`Coordinator (PC) 21 notices that the frame which s