Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 1 of 20
`
`
`
`
`Exhibit I
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 2 of 20
`I 1111111111111111 lllll lllllll llll llll 111111111111111 lllll 111111111111111111
`US00RE44904E
`
`c19) United States
`c12) Reissued Patent
`Karhula
`
`US RE44,904 E
`(10) Patent Number:
`(45) Date of Reissued Patent:
`May 20, 2014
`
`(54) METHOD FOR CONTENTION FREE
`TRAFFIC DETECTION
`
`(75)
`
`Inventor: Petri Karhula, Tampere (FI)
`
`(73) Assignee: Calton Research L.L.C., Wilmington,
`DE (US)
`
`(21) Appl. No.: 13/171,882
`
`(22) Filed:
`
`Jun.29,2011
`
`Related U.S. Patent Documents
`
`7,555,014
`Jun.30,2009
`11/402,621
`Apr. 11, 2006
`
`Reissue of:
`(64) Patent No.:
`Issued:
`Appl. No.:
`Filed:
`U.S. Applications:
`(63) Continuation of application No. 10/167,986, filed on
`Jun. 11, 2002, now Pat. No. 7,027,465, which is a
`continuation of application No. PCT/EP99/10097,
`filed on Dec. 17, 1999.
`
`(51)
`
`(2006.01)
`
`Int. Cl.
`H04J3/07
`(52) U.S. Cl.
`USPC ........................................... 370/506; 370/350
`( 58) Field of Classification Search
`USPC .......................................... 370/350, 503-506
`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,541,919 A *
`5,594,738 A
`
`12/1986 Shimizu
`12/1987 Borras et al.
`5/ 1990 de Boisseron et al.
`7/1996 Yong et al. .................... 370/416
`l/ 1997 Crisler et al.
`
`5,675,617 A
`5,678,188 A
`5,682,386 A *
`5,822,361 A
`5,857,092 A
`5,881,242 A
`6,347,087 Bl*
`6,633,564 Bl *
`6,658,363 B2
`7,027,465 B2
`
`10/ 1997 Quirk et al.
`10/1997 Hisamura
`............... 370/468
`10/1997 Arimilli et al.
`10/1998 Nakamura et al.
`1/1999 Nakamura et al.
`3/1999 Ku et al.
`................ 370/392
`2/2002 Ganesh et al.
`10/2003 Steer et al. .................... 370/389
`12/2003 Mejia et al.
`4/2006 Hautala
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`
`6/1992
`0491494
`3/1994
`0584667
`12/1996
`0749254
`(Continued)
`
`OTHER PUBLICATIONS
`
`R.O. Lamaire et al.; "Wireless LANs and Mobile Networking: Stan(cid:173)
`dards and Future Directions"; IEEE communications Magazine
`'Online!'; Aug. 1996; p. 1-15.
`
`(Continued)
`
`Primary Examiner - Phuc Tran
`(74) Attorney, Agent, or Firm - Stolowitz Ford Cowger
`LLP
`
`ABSTRACT
`(57)
`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) said extracted bit pattern with a search pattern, and
`identifying (S4) said received frame as a priority frame in case
`said extracted bit pattern (BP) matches with said first search
`pattern (SP). By this method, the priority of a data frame can
`easily be detected. The invention also proposes a correspond(cid:173)
`ing device for detecting priority of data frames.
`
`18 Claims, 10 Drawing Sheets
`
`START
`
`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-9 Filed 09/14/20 Page 3 of 20
`
`US RE44,904 E
`Page 2
`
`(56)
`
`References Cited
`
`OTHER PUBLICATIONS
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`EP
`EP
`EP
`WO
`
`0782297
`0804006
`0917317
`0959398
`01045328
`
`7 /1997
`10/1997
`5/1999
`11/1999
`6/2001
`
`European Patent Office; International Search Report WO01045328;
`Apr. 4, 2001; 7 pages.
`Stolowitz Ford Cowger LLP; Related Case Listing; Aug. 24, 2011, 1
`Page.
`
`* cited by examiner
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 4 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 1 of 10
`
`US RE44,904 E
`
`1~
`
`<{
`I-
`{/)
`
`I
`
`•
`
`~
`
`~
`•
`
`(!) -u.
`
`<(
`I(cid:173)
`C/}
`
`U)
`
`(/) w
`.....J~
`0:: 0::
`3:o
`0:: ~ ow
`Oz w
`0::
`~
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 5 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 2 of 10
`
`US RE44,904 E
`
`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
`
`COMPARE
`
`SP
`
`OS
`
`FIG. 3
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 6 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 3 of 10
`
`US RE44,904 E
`
`TO/FROM NETWORK
`
`~
`
`'
`
`22
`
`FRAME
`RECEIVER
`
`I
`
`INFORMATION
`ELEMENT
`RECEIVER
`
`28
`
`I
`
`23
`
`BIT PATTERN
`EXTRACTOR
`
`~
`
`OFFSET
`MEMORY
`
`27
`
`24
`
`26
`
`I
`
`SEARCH -
`
`25
`
`COMPARATOR ~ PATTERN
`MEMORY
`
`I
`
`PRIORITY
`IDENTIFYING
`MEANS
`
`FIG. 4
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 7 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 4 of 10
`
`US RE44,904 E
`
`Y'.
`(/)
`<{
`2
`Io
`I- 0 s8
`C) -,-z8
`
`~o
`(/) H
`N
`N
`n.
`<{ N
`Cl..
`co 22 m
`
`0
`0
`0
`0
`-,-
`0
`0
`0
`
`.,-
`-.-
`0
`-.-
`-,-
`,-
`0
`..--
`
`U')
`•
`-
`C)
`u.
`
`..-
`0
`..-
`..--
`..-
`C>
`0
`..-
`C>
`..--
`......
`C>
`C>
`..-
`C>
`..--
`
`..-
`n.
`co
`
`Cf)
`w
`!;::
`m
`0
`....
`'1"
`
`II
`N
`Cf)
`0
`
`en
`w
`!;::
`
`[D
`
`U)
`N
`,-
`II
`...-
`en
`0
`
`lL
`
`N n..
`
`Cl)
`
`0
`0
`0
`C)
`..-
`0
`0
`0
`
`.....
`0
`..-
`...--
`..-
`0
`0
`..-
`0
`..-
`.....
`0
`.....
`0
`.....
`0
`
`..-
`Cl..
`en
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 8 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 5 of 10
`
`US RE44,904 E
`
`CFPACTIVE
`
`S61
`
`NO
`
`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 BP2'?
`
`NO
`
`S65
`
`FRAME TO PRIORITY
`QUEUE
`
`FRAME TO NORMAL
`QUEUE
`
`S66
`
`RETURN
`
`FIG. 6
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 9 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 6 of 10
`
`US RE44,904 E
`
`PRIORITY FRAMES
`
`212
`
`PRIORITY
`FRAMES
`COUNTER (PFC)
`
`>------
`
`,___
`
`NORMAL
`QUEUE
`
`215
`
`213
`
`PFOCFP
`COUNTER
`
`.__
`
`PC
`CONTROLLER
`
`214
`
`CFP DTIM
`COUNTER
`
`>------
`
`-
`
`PRIORITY
`QUEUE
`
`216
`
`211
`
`FIG. 7
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 10 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 7 of 10
`
`US RE44,904 E
`
`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
`
`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-9 Filed 09/14/20 Page 11 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 8 of 10
`
`US RE44,904 E
`
`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-9 Filed 09/14/20 Page 12 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 9 of 10
`
`US RE44,904 E
`
`ST.ART
`
`S101
`
`DTIM AFTER CFP END
`
`ELSE
`
`ELSE
`
`CFPINTERYAL=(CFP
`INTERVAL x 2} OR (MAX_
`CFPINTERVAL
`
`CFP INTERVAL = (CFP
`INTERVAL/ 2) OR {MIN.
`CFPINTERVAL
`
`S108
`
`ELSE
`
`ELSE
`
`CFP DURATION= (CFP
`DURATION/2) OR MIN_ CFP
`DURATION
`
`S106
`
`CFP DURATION = {CFP
`DURATION x 2) OR MAX_
`CFP DURATION
`
`S1010
`
`PFC =O
`PFOCFP=O
`CFP DTIM COUNTER= 0
`
`S1011
`
`RETURN
`
`FIG. 10
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 13 of 20
`
`U.S. Patent
`
`May 20, 2014
`
`Sheet 10 of 10
`
`US RE44,904 E
`
`START
`
`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---.c.-F_P_-r--.....__-r-l-~---.,------1-1 __ cT""FP __
`
`DTIM
`
`DTIM
`
`DTIM
`
`CFP REPETITION INTERVAL
`
`FIG. 12
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 14 of 20
`
`US RE44,904 E
`
`1
`METHOD FOR CONTENTION FREE
`TRAFFIC DETECTION
`
`Matter enclosed in heavy brackets [ ] appears in the 5
`original patent but forms no part of this reissue specifica(cid:173)
`tion; matter printed in italics indicates the additions
`made by reissue.
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a reissue of U.S. patent application Ser.
`No. 11/402,621,filed on Apr. 11, 2006, issued as U.S. Pat. No.
`7,555,014, which is a continuation ofU.S. patent application 15
`Ser. No. 10/167,986, filed Jun. 11, 2002, now U.S. Pat. No.
`7,027,465, which is a continuation of International Applica(cid:173)
`tion 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).
`
`2
`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 priority,
`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
`1 o frames transmitted via the network 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
`20 based on priority was not conducted at all. That is, the existing
`systems according to the IEEE 802.11 standard do not sepa(cid:173)
`rate 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, treating all frames
`equally.
`
`25
`
`SUMMARY OF THE INVENTION
`
`FIELD OF THE INVENTION
`
`The present invention relates to a method and a device for
`detecting priority of data frames in a network.
`
`BACKGROUND OF THE INVENTION
`
`This invention relates in general to the field of telecommu(cid:173)
`nications, more precisely to Wireless Local Area Networks
`(WLAN) and Electrical and Electronics Engineers (IEEE)
`802.11 WLAN standard.
`The IEEE 802 .11 Wireless Local Area Network specifica(cid:173)
`tion 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
`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 ele(cid:173)
`ment.
`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 60
`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
`
`Therefore, the object underlying the invention resides in
`30 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
`data frames in a network comprising the steps of extracting a
`35 bit pattern from a predetermined position in a frame, compar(cid:173)
`ing the extracted bit pattern with a search pattern, and iden(cid:173)
`tifying 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
`40 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 posi(cid:173)
`tion of a data frame, a comparing means for comparing the
`extracted bit pattern with a predetermined search pattern, and
`45 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 can
`easily be detected by comparing a corresponding bit pattern
`50 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
`located. This bit pattern is compared with a search pattern
`55 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 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 MAC
`layer frames. Therefore, the method does not need any knowl-
`65 edge of the upper layer protocols.
`Consequently, according to the method of the invention,
`certain traffic can be defined to have higher priority than other
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 15 of 20
`
`US RE44,904 E
`
`5
`
`4
`period, i.e., the Contention Free Period, can be adjusted cor(cid:173)
`responding to the load of priority traffic on the network.
`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
`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 ana(cid:173)
`lyzing 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 con(cid:173)
`nected by air with the Access Point.
`The above method for generating priority detecting infor(cid:173)
`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
`determined and included in the information element.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`3
`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 perfor(cid:173)
`mance AP.
`Furthermore, the method is protocol-independent and so
`flexible that all the configuration may be done in external
`configuration program and the Access Point does not need to
`know anything about the processed traffic.
`Further advantageous developments are set out below.
`In particular, the predetermined position in the frame is 10
`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 15
`in an information element. This information element can be
`produced by an external program such that the device accord(cid:173)
`ing 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 device 20
`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 reconfigure
`the network element (i.e., the device) performing the method.
`It is only necessary to provide new information elements 25
`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. 30
`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 35
`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 infor(cid:173)
`mation 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 lev(cid:173)
`els, 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 pri(cid:173)
`ority levels can easily be detected.
`Hence, a plurality of different information elements can be
`used. For example, one certain priority can require a plurality 55
`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
`special period for sending priority traffic. The priority queue 60
`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 65
`priority traffic can be adjusted according statistical informa(cid:173)
`tion regarding the priority frames sent. Thus, the special
`
`40
`
`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 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
`embodiment;
`FIG. 6 illustrates a flow chart of a frame sending procedure
`during Content Free Period (CFP) according to the second
`45 embodiment;
`FIG. 7 shows relevant parts of a Point Coordinator (PC)
`according to a third embodiment;
`FIG. 8 illustrates a flow chart of a frame sending procedure
`during Content Free Period (CFP) according to the third
`50 embodiment;
`FIG. 9 illustrates a flow chart of a frame sending procedure
`during contention period according to the third embodiment;
`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.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`In the following, preferred embodiments of the invention
`are described in more detail with reference to the accompa(cid:173)
`nying drawings.
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 16 of 20
`
`US RE44,904 E
`
`5
`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
`one or more wireless stations (STA) 3 to 5. The AP may or
`may not be connected to another wired or wireless network 1. 5
`The purpose of the AP 2 is to transmit the traffic between 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 wire(cid:173)
`less 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 25
`position in the received frame. The bit pattern can be a 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 30
`step S3 it is decided that both patterns match, 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, 35
`the frame can be treated according to 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
`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 60
`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. Refer(cid:173)
`ence numeral 23 denotes a bit pattern extractor by which the
`
`6
`bit pattern BP described above is extracted from a predeter(cid:173)
`mined 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 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 priority identifying means
`10 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
`15 provides information elements which each comprise an offset
`OS and a search pattern SP. These information elements are
`received by an information element receiver 28. The receiver
`28 analyzes the information element and supplies the
`detected offset OS to the offset memory 27 and the detected
`20 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 Coordi-
`nator (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(cid:173)
`server application case), the CFP may be used only for deliv(cid:173)
`ering data from the AP to wireless stations. But, if the nature
`of the high priority traffic is interactive (like a videoconfer(cid:173)
`ence, for example), the PC 21 must also poll wireless stations
`to permit them to transmit also during the CFP. See IEEE
`40 802.11 standard for more detailed description about this basic
`functionality ofIEEE 802.11 standard.
`The AP 2 receives MAC layer frames either from the wire(cid:173)
`less station or from the connected wired network. If the des-
`tination of the frame is in the wireless network, the AP will
`45 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 elements are configured
`to the AP by the external configuration program. The AP also
`50 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 802.11. The point when the
`priority detection check is performed (before or after IEEE
`802.11 MAC header formatting) can be left implementation
`55 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 queue are
`moved to the normal queue and priority queue is flushed.
`According to this embodiment, the priority of a MAC layer
`65 frame is detected by using one or more information elements
`which are transmitted to the Access Point (AP) 1. That is, one
`or more bit patterns with corresponding different offsets are
`
`

`

`Case 1:20-cv-07529 Document 1-9 Filed 09/14/20 Page 17 of 20
`
`US RE44,904 E
`
`7
`checked whether they match with one or more different
`search patterns. Furthermore, the bit patterns 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 5
`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 10
`described by referring to FIGS. 5 and 6. It is noted that for
`simplifying the illustration, the second embodiment is
`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 15
`extracted from the MAC layer frame F. The first bit pattern
`BPl is extracted with an offset OSl. As illustrated, 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
`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 25
`pattern BP2' match. Since also the first search pattern SPl
`matches with the first bit pattern BPl, it is decided that the
`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 30
`Contention Free Period (CFP). That is, it is put on a high
`priority queue. This process is described in the following by
`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 35
`S61, the Access Point (AP) 2 waits for receiving a frame
`which is to be transmitted further to the wireless stations 3 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 40
`pattern BP2', as described above. Since no mask has been
`specified for the first bit pattern BPl, no corresponding step
`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, 45
`respectively. If SPl and BPl, an