Devices, softwares, and methods for wireless devices to form a network on the fly by performing admission control in the second layer

CROSS REFERENCE TO RELATED APPLICATIONS

P-0001[0001] This application claims priority from U.S. Provisional Application No. 60/233,366, filed on Sep. 18, 2000, which is hereby incorporated by reference.

BACKGROUND OF THE INVENTION

P-0002[0002] 1. Field of the Invention

P-0003[0003] The present invention is related to the field of communication through wireless networks, and more specifically to devices, softwares, and methods for wireless devices to form a network on the fly by performing admission control in the second layer, without invoking the network layer.

P-0004[0004] 2. Description of the Related Art

P-0005[0005] Local area networks (LANs) are increasingly used to transfer data. A relatively new application is wireless LANs, also known as WLANs. These can provide the benefits of a wired LAN, without requiring the different stations to be physically coupled to each other. There is no need for procuring transmission wires such as coaxial conductors, twisted prayers of wires, optical fibers, etc. for transferring the data. Instead, the data is transferred through space, either using radio frequency (RF) waves (which are also known as microwaves), or optical frequency waves, such as infrared (IR) light. A network may be formed by bringing components close together, without the need to connect transmission wires to them.

P-0006[0006] Radio based WLANs have several characteristics which differ from those of wired LANs. These characteristics include lower achievable data capacity, which is due to a number of factors. These factors include bandwidth and power limitations, higher error rates, and a communication capacity that changes with time and may depend on the particular source and destination of the transmission. The latter may be due to interfering signals.

P-0007[0007] A number of characteristics remain the same. One of them is the predominant software architecture for implementing communication. WLANs may use a multi-layer communication protocol stack such as the standard open systems interconnection (OSI) management compatible architecture, which is also used for the internet. Much of this architecture is documented in literature produced by the Internet Engineering Task Force (IETF).

P-0008[0008] An example of the OSI architecture is given below. Unless stated otherwise the terms in this document are to be interpreted consistently with the definitions of the IETF. (IETF maintains a website where the standards may be researched. The website has an address of http://www.ietf.org/ as of the date that this document is initially filed with the USA Patent Office.)

P-0009[0009] Referring to FIG. 1, an Access Point (AP) device <b>110</b> includes a physical medium <b>120</b>. Medium <b>120</b> may be a transmitting antenna, a receiving antenna, etc. Medium <b>120</b> is for performing wireless exchange of data with other wireless communication devices in a WLAN.

P-0010[0010] AP device <b>110</b> also includes a software structure that includes a number of layers prescribed by OSI. These layers include a layer L<b>1</b><b>130</b> which is also called a physical layer <b>130</b>, and is for controlling medium <b>120</b>. A layer L<b>2</b><b>140</b> is on top of layer L<b>1</b><b>130</b>, and a layer L<b>3</b><b>150</b> is on top of layer L<b>2</b><b>140</b>. Layer L<b>3</b><b>150</b> is also called network layer <b>150</b>. Other layers (not shown in FIG. 1) may also be present.

P-0011[0011] Another characteristic that remains the same is the need to prevent many peripheral stations from transmitting at once. Concurrent transmission would, if permitted, corrupt the data being received.

P-0012[0012] Concurrent transmission is typically avoided by polling techniques, once a communication scheme has been established. In such polling techniques, peripheral stations transmit in response to being polled by AP device <b>110</b>. In this way, multiple stations are prevented from transmitting concurrently.

P-0013[0013] For establishing the communication scheme, requests are received from contending peripheral devices. These are requests for reserving resources, such as bandwidth and memory, and are therefore also known as reservation requests.

P-0014[0014] Continuing to refer to FIG. 1, network layer <b>150</b> includes an admission control module <b>160</b>. Module <b>160</b> receives each reservation request, examines it, and then grants or denies it. When it grants it, a network has been formed on the fly.

P-0015[0015] In addition, AP device <b>110</b> includes a path <b>165</b> that starts from physical medium <b>120</b>, goes through physical layer L<b>1</b><b>130</b>, layer L<b>2</b><b>140</b>, and ends in admission control module <b>160</b>. Path <b>165</b> is an iconic way of depicting the fact that a physical signal received by physical medium <b>120</b> is converted into a software signal as it is ushered in layers L<b>1</b><b>130</b>, L<b>2</b><b>140</b>, L<b>3</b><b>150</b>, etc.

P-0016[0016] A first wireless peripheral communication device <b>180</b> may be wishing to transmit data to AP device <b>110</b>. Accordingly, wireless communication device <b>180</b> transmits data group <b>184</b> to AP device <b>110</b> over a communication link <b>182</b>.

P-0017[0017] Data group <b>184</b> is a reservation request frame that contains an encoded reservation request. The reservation request is transferred along path <b>165</b>, where it is received in admission control module <b>160</b>. Admission control module <b>160</b> then determines whether to grant or deny the requested reservation.

P-0018[0018] A problem remains where reservation requests are conflicting, by asking for the resource at the same time. Various approaches for WLANs have been proposed for resolving conflicting reservation requests. They use techniques including random access, in which each wireless station is allocated a portion of the total available communication capacity. For example, the IEEE 802.11 media access control standard is a random access technique, which uses a carrier sense with a collision avoidance (CSMA/CA) scheme.

P-0019[0019] Devices that are compatible with the IEEE 802 standard are also known as type 802 devices. They face the problem that the reservation request must include data that makes it specific to level L<b>3</b><b>150</b>. This renders the reservation request too long, which delays in setting up a communication scheme.

BRIEF SUMMARY OF THE INVENTION

P-0020[0020] The present invention overcomes these problems and limitations of the prior art.

P-0021[0021] Generally, the present invention provides devices, softwares and methods for wireless devices to form a network on the fly by performing admission control while in the second layer.

P-0022[0022] A peripheral station according to the invention encodes a priority of data in a tag that is transmitted in a reservation request frame. A cooperating complementary access point receives the reservation request frame and reads the tag. The request is finally resolved (granted or denied) at the second level, using the priority information of the tag.

P-0023[0023] The invention offers the advantage that the admission control process need not reach the network layer of the access point. As such, the reservation request frame need not be specific to the third level of the access point. This way the reservation request frame may be shorter.

P-0024[0024] The invention will become more readily apparent from the following Detailed Description, which proceeds with reference to the drawings, in which:

BRIEF DESCRIPTION OF THE DRAWINGS

P-0025[0025]FIG. 1 is a diagram of an architecture of an AP device in the prior art resolving a reservation request from a peripheral station.

P-0026[0026]FIG. 2 is a diagram of architectures for an AP device made according to an embodiment of the invention that resolves a reservation request, and for a cooperating peripheral station made according to an embodiment of the present invention that generates reservation request.

P-0027[0027]FIG. 3 is a block diagram of components of the access point and the peripheral station of FIG. 2.

P-0028[0028]FIG. 4 is a block diagram illustrating different embodiments for a wireless access point and a wireless base station according to the invention.

P-0029[0029]FIG. 5 is a flowchart illustrating a method according to an embodiment of the present invention.

P-0030[0030]FIG. 6 is a flowchart illustrating a method according to an embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT(S)

P-0031[0031] As has been mentioned, the present invention provides devices, softwares and methods for wireless devices to perform admission control while in the second layer. The invention is now described in more detail.

P-0032[0032] Referring now to FIG. 2, an access point (AP) device <b>210</b> made according to the invention is described. AP device <b>210</b> includes a physical medium <b>220</b>. Medium <b>220</b> may be a transmitting antenna, a receiving antenna, etc. Medium <b>220</b> is for performing wireless exchange of data with other wireless communication devices in a WLAN.

P-0033[0033] AP device <b>210</b> also includes a software structure that includes a number of layers prescribed by OSI. These layers include a layer L<b>1</b><b>230</b> that is also called a physical layer <b>230</b>, and is for controlling medium <b>220</b>. A layer L<b>2</b><b>240</b> is on top of layer L<b>1</b><b>230</b>, and a layer L<b>3</b><b>250</b> is on top of layer L<b>2</b><b>240</b>, and is also called network layer L<b>3</b><b>250</b>. Other layers (not shown in FIG. 2) may also be present.

P-0034[0034] Layer L<b>2</b><b>240</b> typically includes a MAC sublayer (not shown separately in FIG. 2). The importance of the MAC sublayer is such that sometimes the entire second layer L<b>2</b><b>24</b> is called a medium access control (MAC) layer.

P-0035[0035] Layer L<b>2</b><b>240</b> includes an admission control module <b>260</b>. Module <b>260</b> receives each reservation request, and determines whether to grant or deny it.

P-0036[0036] In addition, AP device <b>210</b> includes a path <b>265</b> that starts from physical medium <b>220</b>, goes through physical layer <b>230</b>, and ends in admission control module <b>260</b>. Path <b>265</b> is an iconic way of depicting the fact that a physical signal received by physical medium <b>220</b> is converted into a software signal as it is ushered in layers L<b>1</b><b>230</b>, L<b>2</b><b>240</b>, etc.

P-0037[0037] Physical signals are received over a communication link <b>282</b>, established with a peripheral device <b>310</b>. A physical signal includes a reservation request frame <b>284</b>. The reservation request (RR) is encoded in reservation request frame <b>284</b>.

P-0038[0038] A tag <b>286</b> is encoded within reservation request frame <b>284</b>. Tag <b>286</b> has been encoded according to the IEEE 802.11 standard by device <b>310</b>.

P-0039[0039] Importantly, according to the invention, tag <b>286</b> is used to additionally encode a priority of the data that is to be transmitted from device <b>310</b>. Admission control module <b>260</b> makes its determination by interpreting the priority encoded in tag <b>286</b>.

P-0040[0040] Peripheral station device <b>310</b> is also made according to the invention. Device <b>310</b> includes a physical medium <b>320</b>. Medium <b>320</b> may be a transmitting antenna, a receiving antenna, etc. Medium <b>320</b> is for performing wireless exchange of data with other wireless communication devices in a WLAN.

P-0041[0041] Device <b>310</b> also includes a software structure that includes a number of layers prescribed by OSI. These layers include a layer L<b>1</b><b>330</b> that is also called a physical layer <b>330</b>, and is for controlling medium <b>320</b>. A layer L<b>2</b><b>340</b> is on top of layer L<b>1</b><b>330</b>, and a layer L<b>3</b><b>350</b> is on top of layer L<b>2</b><b>340</b>, and is also called network layer L<b>3</b><b>350</b>. Other layers (not shown in FIG. 2) may also be present.

P-0042[0042] Importantly, layer L<b>3</b><b>350</b> includes a tag generation module <b>360</b>. Module <b>360</b> generates tag <b>286</b> according to the IEEE 802.1Q standard, defined as of the day this document is initially submitted to the USA Patent Office. In addition, tag <b>286</b> includes a priority of the data that is to be transmitted along link <b>282</b>. As such, the priority will be finally resolved based on QoS considerations.

P-0043[0043] As can be seen, the reservation request is resolved by admission control module <b>260</b> at layer L<b>2</b><b>240</b>. Accordingly, the reservation request need not comply with any requirements of layer L<b>3</b><b>250</b>. In other words, the RR may be higher level agnostic.

P-0044[0044] Referring now to FIG. 3, components of the devices of FIG. 2 are seen in more detail. This art involves many standardized terms, and acronyms according to the terms. Still, for the benefit of the reader, a list of the most useful acronyms is given below.

P-0045[0045] AP—Access Point

P-0046[0046] BME—Buffer Management Entity

P-0047[0047] CCI—Centralized Contention Interval

P-0048[0048] CE—Classification Entity

P-0049[0049] CTS—Clear To Send

P-0050[0050] DCF—Distribution Coordination Function

P-0051[0051] DSBM—Designated Subnet Bandwidth Manager

P-0052[0052] E-SME—Enhanced Station Management Entity

P-0053[0053] LLC—Logic Link Control

P-0054[0054] MAC—Medium Access Control

P-0055[0055] MLME—MAC Layer Management Entity

P-0056[0056] PCF—Point Coordination Function

P-0057[0057] PE—Policing Entity

P-0058[0058] PLCP—Physical Layer Convergence Protocol

P-0059[0059] PLME—Physical Layer Management Entity

P-0060[0060] PM—Physical Medium

P-0061[0061] PMD—Physical Medium Dependent

P-0062[0062] QoS—Quality of Service

P-0063[0063] RR—Reservation Request

P-0064[0064] SE—Scheduling Entity

P-0065[0065] STA—Station

P-0066[0066] As can be seen in FIG. 3, in AP device <b>210</b>, layer L<b>1</b><b>230</b> includes a PLCP <b>232</b>, a PMD <b>234</b> and a PLME <b>236</b>. Layer L<b>2</b><b>240</b> includes a LLC <b>241</b>, a Medium Access Control (MAC) sublayer <b>243</b>, and a MLME <b>244</b>. MAC sublayer <b>243</b> includes a BME <b>246</b>, a SE <b>247</b> and a RME <b>248</b>. Layer L<b>3</b><b>250</b> includes, among others, a CE <b>252</b> and a DSBM <b>254</b>. All three layers L<b>1</b><b>230</b>, L<b>2</b><b>240</b> and L<b>3</b><b>250</b> are spanned by an E-SME <b>258</b>.

P-0067[0067] In addition, in peripheral station <b>310</b>, layer L<b>1</b><b>330</b> includes a PLCP <b>332</b>, a PMD <b>334</b> and a PLME <b>336</b>. Layer L<b>2</b><b>340</b> includes a LLC <b>341</b>, a Medium Access Control (MAC) sublayer <b>343</b>, and a MLME <b>344</b>. Layer L<b>2</b><b>340</b> is also called a medium access control (MAC) layer, because it includes MAC sublayer <b>343</b>. MAC sublayer <b>343</b> includes a BME <b>346</b>. Layer L<b>3</b><b>350</b> includes, among others, a CE <b>352</b>. Classification entity (CE) <b>352</b> is preferably the tag generation module <b>360</b> of FIG. 2. All three layers L<b>1</b><b>330</b>, L<b>2</b><b>340</b> and L<b>3</b><b>350</b> are spanned by an E-SME <b>358</b>.

P-0068[0068] It is readily apparent that the present invention may be implemented by one or more devices that include logic circuitry. It may also be implemented by a device that includes a dedicated processor system, which may include a microcontroller or a microprocessor. Examples of such alternate embodiments are seen below.

P-0069[0069] Referring now to FIG. 4, an Access Point AP <b>420</b> made according to an embodiment of the invention is described in more detail. AP <b>420</b> may be any communication device, such as a wireless communication device (a station, a peripheral, etc.)

P-0070[0070] Access Point AP <b>420</b> has a processor <b>422</b>, which may be implemented as a Digital Signal Processor (DSP), Central Processing Unit (CPU), or any other equivalent way known in the art.

P-0071[0071] Access Point AP <b>420</b> additionally includes a memory <b>424</b>, on which a program <b>426</b> may reside. Functions of processor <b>422</b> may be controlled by program <b>426</b>, as will become apparent from the below.

P-0072[0072] Continuing to refer to FIG. 4, a peripheral station STA <b>440</b> made according to an embodiment of the invention is described in more detail. Station STA <b>440</b> may be any communication device, such as a wireless communication device (a station, a peripheral, etc.)

P-0073[0073] Station STA <b>440</b> has a processor <b>442</b>, which may be implemented as a Digital Signal Processor (DSP), Central Processing Unit (CPU), or any other equivalent way known in the art.

P-0074[0074] Station STA <b>440</b> additionally includes a memory <b>444</b>, on which a program <b>446</b> may reside. Functions of processor <b>442</b> may be controlled by program <b>446</b>, as will become apparent from the below.

P-0075[0075] Access Point AP <b>420</b> and peripheral station STA <b>440</b> may establish a communication connection link <b>482</b>, for exchanging data between them.

P-0076[0076] The invention additionally provides methods, which are described below. Moreover, the invention provides apparatus that performs, or assists in performing the methods of the invention. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computer selectively activated or reconfigured by a computer program stored in the computer. The methods and algorithms presented herein are not necessarily inherently related to any particular computer or other apparatus. In particular, various general-purpose machines may be used with programs in accordance with the teachings herein, or it may prove more convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these machines will appear from this description.

P-0077[0077] Useful machines or articles for performing the operations of the present invention include general-purpose digital computers or other similar devices. In all cases, there should be borne in mind the distinction between the method of operating a computer and the method of computation itself. The present invention relates also to method steps for operating a computer and for processing electrical or other physical signals to generate other desired physical signals.

P-0078[0078] The invention additionally provides a program, and a method of operation of the program. The program is most advantageously implemented as a program for a computing machine, such as a general-purpose computer, a special purpose computer, a microprocessor, etc.

P-0079[0079] The invention also provides a storage medium that has the program of the invention stored thereon. The storage medium is a computer-readable medium, such as a memory, and is read by the computing machine mentioned above.

P-0080[0080] A program is generally defined as a sequence of steps leading to a desired result. These steps, also known as instructions, 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, combined, compared, and otherwise manipulated or processed. When stored, they may be stored in any computer-readable medium. It is convenient at times, principally for reasons of common usage, to refer to these signals as bits, data bits, samples, values, elements, symbols, characters, images, terms, numbers, or the like. It should be borne in mind, however, that all of these and similar terms are associated with the appropriate physical quantities, and that these terms are merely convenient labels applied to these physical quantities.

P-0081[0081] This detailed description is presented largely in terms of flowcharts, display images, algorithms, and symbolic representations of operations of data bits within a computer readable medium, such as a memory. Such descriptions and representations are the type of convenient labels used by those skilled in programming and/or the data processing arts to effectively convey the substance of their work to others skilled in the art. A person skilled in the art of programming may use this description to readily generate specific instructions for implementing a program according to the present invention. For the sake of economy, however, flowcharts used to describe methods of the invention are not repeated in this document for describing software according to the invention.

P-0082[0082] Often, for the sake of convenience only, it is preferred to implement and describe a program as various interconnected distinct software modules or features, collectively also known as software. This is not necessary, however, and there may be cases where modules are equivalently aggregated into a single program with unclear boundaries. In any event, the software modules or features of the present invention may be implemented by themselves, or in combination with others. Even though it is said that the program may be stored in a computer-readable medium, it should be clear to a person skilled in the art that it need not be a single memory, or even a single machine. Various portions, modules or features of it may reside in separate memories, or even separate machines. The separate machines may be connected directly, or through a network, such as a local access network (LAN), or a global network, such as the Internet.

P-0083[0083] In the present case, methods of the invention are implemented by machine operations. In other words, embodiments of the program of the invention are made such that they perform methods of the invention that are described in this document. These may be optionally performed in conjunction with one or more human operators performing some, but not all of them. As per the above, the users need not be collocated with each other, but each only with a machine that houses a portion of the program. Alternately, some of these machines may operate automatically, without users and/or independently from each other.

P-0084[0084] Methods of the invention are now described.

P-0085[0085] Referring now to FIG. 5, a flowchart <b>500</b> is used to illustrate a method according to an embodiment of the invention. The method of flowchart <b>500</b> may be practiced by a peripheral station seeking to transmit data to an Access Point device.

P-0086[0086] According to a box <b>510</b>, a reservation request is generated for transmitting data.

P-0087[0087] According to a next box <b>520</b>, a priority is determined for transmitting the data. The priority may be determined through a Classification Entity. The priority may be either according to a default class, or according to an AP-designated class. In such classes, the priority may be designated by a number, such as 7, 6, 4, etc.

P-0088[0088] According to a next box <b>530</b>, a tag is generated. The tag is according to the IEEE 802.1Q standard. Importantly, the tag also encodes the priority.

P-0089[0089] According to a next box <b>540</b>, the data and the tag are passed to the second layer of the OSI architecture, which is often called the MAC sublayer. If an LLC intervenes, the data is passed to the MAC sublayer.

P-0090[0090] According to an optional next box <b>550</b>, the data is stored in a buffer.

P-0091[0091] According to a next box <b>560</b>, the data is examined to determine a required bandwidth for transmission. The address is also examined. Examination is preferably by a BME.

P-0092[0092] According to an optional next box <b>570</b>, the tag and the bandwidth are encoded in a reservation request frame. The reservation request frame need not be specific to any type of a network layer of the access point. In other words, it may be 3rd layer independent, or 3rd layer agnostic.

P-0093[0093] According to an optional next box <b>580</b>, the reservation request frame is transmitted, so that it will be received by the AP device. Transmission is preferably during a Centralized Contention Interval. Transmission may be in the DCF mode or in the PCF mode.

P-0094[0094] Referring now to FIG. 6, a flowchart <b>600</b> is used to illustrate a method according to another embodiment of the invention. The method of flowchart <b>600</b> may be practiced by an access point device that receives and resolves reservation requests.

P-0095[0095] According to a box <b>610</b>, a reservation request frame is received.

P-0096[0096] According to a next box <b>620</b>, the reservation request frame is decomposed to extract a reservation request.

P-0097[0097] According to a next box <b>630</b>, an IEEE 802.1Q tag is decoded from the reservation request. Decoding is performed while in the MAC layer, without advancing to the network layer. This is a first part of admission control.

P-0098[0098] According to an optional next box <b>640</b>, the tag is read to identify requested priority. Additionally, the reservation request is also read to further determine a bandwidth requirement. These are second parts of admission control.

P-0099[0099] According to an optional next box <b>650</b>, the priority is examined. It is inquired whether there are sufficient resources for meeting the reservation request. The request is examined against the available resources.

P-0100[0100] If not, then according to a next box <b>660</b>, a reservation request reject frame is generated and transmitted. This takes place while still in the MAC layer.

P-0101[0101] If yes, then according to a next box <b>670</b>, a transmission opportunity is scheduled based on the priority. This scheduling is performed while still in the MAC layer. In the preferred embodiment, the scheduling is performed by a scheduling entity (SE) in the second layer. Then an exchange takes place, to announce the scheduling, the size of buffer window, etc.

P-0102[0102] Accordingly, regardless of the outcome, admission control is thus performed exclusively in the second layer. This involves also a BME and a RME in the second layer.

P-0103[0103] A person skilled in the art will be able to practice the present invention in view of the description present in this document, which is to be taken as a whole. Numerous details have been set forth in order to provide a more thorough understanding of the invention. In other instances, well-known features have not been described in detail in order not to obscure unnecessarily the invention.

P-0104[0104] While the invention has been disclosed in its preferred form, the specific embodiments as disclosed and illustrated herein are not to be considered in a limiting sense. Indeed, it should be readily apparent to those skilled in the art in view of the present description that the invention may be modified in numerous ways. The inventor regards the subject matter of the invention to include all combinations and subcombinations of the various elements, features, functions and/or properties disclosed herein.

P-0105[0105] The following claims define certain combinations and subcombinations, which are regarded as novel and non-obvious. Additional claims for other combinations and subcombinations of features, functions, elements and/or properties may be presented in this or a related document.