Multicast and unicast messages in a virtual cell communication system

Description

INCORPORATED DISCLOSURES

This application claims priority of the following disclosures, hereby incorporated by reference as if fully set forth herein:

• • U.S. Provisional Patent Application 61/308,839, filed Feb. 26, 2010, in the name of Mohan RAM and Saravanan BALASUBRAMANIAN, titled “Multicast and Unicast Messages in a Virtual Cell Communication System”, assigned to the same assignee,
  • U.S. patent application Ser. No. 11/715,287, filed Mar. 7, 2007, in the name of Vaduvur BHARGHAVAN, Sung-Wook HAN, Joseph EPSTEIN, Berend DUNSBERGEN, and Saravanan BALASUBRAMANIAN, titled “Seamless Mobility in Wireless Networks”, assigned to the same assignee,
  • which itself claims the priority of, and hereby incorporates by reference as if fully set forth herein, the following: U.S. patent application Ser. No. 11/298,864, filed Dec. 9, 2005, in the name of Vaduvur BHARGHAVAN, Sung-Wook HAN, Joseph EPSTEIN, Berend DUNSBERGEN, and Saravanan BALASUBRAMANIAN, titled “Seamless Mobility in Wireless Networks”, and assigned to the same assignee,
  • which itself claims the priority of, and hereby incorporates by reference as if fully set forth herein, the following: U.S. patent application Ser. No. 11/294,673, filed Dec. 5, 2005, in the name of Rajendran VENUGOPALACHARY, Senthil PALANISAMY, Srinith SARANG, and Vaduvur BHARGHAVAN, titled “Omni-Directional Antenna Supporting Simultaneous Transmission and Reception of Multiple Radios with Narrow Frequency Separation”, and assigned to the same assignee.
  • U.S. patent application Ser. No. 11/396,400, filed Mar. 31, 2006, in the name of inventors Senthil PALANISAMY, titled “Security in Wireless Communication Systems”, and assigned to the same assignee.
  • U.S. patent application Ser. No. 12/035,925, filed Feb. 22, 2008, in the name of inventors Berend DUNSBERGEN and Anand Prakash POOMAGAME, titled “Associating mobile stations with virtual cells using key search”. and assigned to the same assignee.
  • U.S. Provisional Patent Application Ser. No. 61/095,578, filed Sep. 9, 2008, in the name of inventors Vaduvur BHARGHAVAN and Berend DUNSBERGEN, titled “Seamless Roaming in Wireless Networks”, and assigned to the same assignee.

This application claims priority of any and all disclosures whose priority is claimed by the foregoing, or which are incorporated by reference by the foregoing. These disclosures are sometimes referred to herein as the “Incorporated Disclosures”.

BACKGROUND

In wireless communication systems, each mobile station might be coupled to a communication network by associating that mobile station with a particular AP (access point). In some IEEE wireless communication standards, wireless packets may be sent unicast (to a single destination) or multicast (to more than one destination). “Broadcast” packets are that special case of multicast packets where the designated “more than one destination” includes substantially all destinations in the wireless communication system.

In some IEEE wireless communication standards, such as the IEEE 802.11 family of communication protocols, multicast packets are not reliably delivered. In wireless communication systems following an IEEE 802.11 protocol, unicast packets must be responded to by the destination, with an acknowledgement (ACK) packet. A higher-level protocol is able to ensure reliable delivery by known techniques that are employed when a message is sent to, but no ACK packet is received from, the destination.

While this technique is generally adequate to assure delivery of unicast packets, many communication protocols, including the IEEE 802.11 family of communication protocols, do not require the destination to respond with an ACK packet when it receives a multicast packet. This could be due to concern that the sender would be flooded with ACK packets, or might be due to the nature of traffic using multicast packets. For example, multicast packets are often used to broadcast streaming audio, video, or audio-video, signals to a recipient audience. In some cases, such as election news, sports events, and the first episode of the “Victoria's Secret” modeling show, that audience may be numbered in millions.

While the loss of some fraction of packets for streaming audio-video (for example) is not necessarily crippling, it can have a noticeable effect for a user at the destination. Missing even 50 milliseconds of audio, for example, can be noticed by many human ears, with the effect that loss of even a small fraction of packets may make the streaming signal seem broken-up or jumpy.

SUMMARY OF THE DESCRIPTION

This description includes techniques, including methods, physical articles, and systems, which provide reliable multicast delivery in a wireless communication system. This has the effect that the sender can be assured that those multicast messages it sends are reliably received by substantially every destination, without having to accept the possibility of some fraction of those messages being lost without notice to the sender.

For example and without limitation, in a wireless communication system similar to those described in the Incorporated Disclosures (as described below), or employing similar principles, the description includes techniques, including methods, physical articles, and systems, which provide reliable multicast delivery even when a wireless station (WS) is not aware of which access point (AP) it is assigned to. This has the effect that reliable delivery of those messages can be determined at the AP, without generating unnecessary traffic between the AP and the sending device, and without possibly overwhelming the sending device with ACK messages.

For example and without limitation, multicast packets in a wireless communication system (such as, for example, streaming audio-video) might be received at each AP for which there are one or more destination stations assigned thereto. Without altering any of those multicast packets, the AP might encapsulate each of them as a subframe in an aggregated MAC service data unit (A-MSDU) packet. Each such A-MSDU packet might be sent individually to each individual recipient destination station. This has the effect that the AP can substantially guarantee delivery of substantially each such multicast packet to substantially every one of its designated destinations.

This description includes techniques, including methods, physical articles, and systems, which provide for more than one such multicast packet to be encapsulated, each as a separate subframe, within each such A-MSDU packet. Note that as each such A-MSDU packet is sent directly to its individual destination, the selection of which, and how many, multicast packets to include within each such A-MSDU packet might be made by the AP. For example and without limitation, if a destination station is concurrently receiving streaming messages from multiple sources, multicast packets from each, or at least more than one, of those sources, might be differently encapsulated for distinct destinations. This has the effect that a destination might receive two or more such streaming messages encapsulated in a single A-MSDU packet.

If those two or more such streaming messages are originally from distinct sources, the destination might thus receive those streaming messages superior to if those two or more such streaming messages were sent separately. If those two or more such streaming messages are originally from a single source, the destination might again thus receive those streaming messages superior to if those two or more such streaming messages were sent separately. The invention includes the possibility that an AP, when generating an A-MSDU packet for a particular individual destination, might choose a 1^st set of multiple multicast packets from a 1^st source, a 2^nd set of multiple multicast packets from a 2^nd source, where the multiple number in the 2^nd set differs from the 1^st set, and perhaps, a single multicast packet from a 3^rd source, any combination or conjunction thereof, or by some other technique.

This description includes techniques, including methods, physical articles, and systems, which provide individualized optimization of transmission parameters for substantially each such A-MSDU packet. Note that as each such A-MSDU packet is separately sent to its individual destination, the selection of transmission parameters for each multicast packet encapsulated in the A-MSDU packet might be chosen individually for substantially each such multicast packet, and the selection of transmission parameters for the entire A-MSDU packet might be chosen individually for substantially each such destination. The invention includes the possibility that some multicast packets are delivered, when encapsulated, more slowly than if they had been otherwise transmitted multicast, so that the AP might deliver other multicast packets, when encapsulated, more quickly than if they had been otherwise transmitted multicast. This has the effect that a multicast packet to a 1^st destination need not slow down the same multicast packet sent to a 2^nd destination. This also has the effect that a 1^st multicast packet might be sent slower than if multicast, so that the AP can collectively optimize delivery of both 1^st and 2^nd multicast packets, in different numbers, to different destinations.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows a conceptual drawing of a wireless communication system.

REAL-WORLD NATURE

The invention includes techniques, including methods, physical articles, and systems, that receive real-world information dictated by real-world conditions (not mere inputs to a problem-solving technique). The techniques provided by the invention are transformative of the information received, at least in the sense that incoming data is reordered and allocated to particular times and priorities. This has the effect that a 1^st type of information (e.g., incoming message units) is transformed into a 2^nd type of information (e.g., relative priority of outgoing message units).

The invention includes techniques that are tied to a particular machine, at least in the sense that allocation of time and bandwidth is performed in a communication system. While this description is primarily directed to that portion of the invention in which an AP plays a prominent role, this description also shows that an AP alone (i.e., without appropriate instructions) would not necessarily be sufficient to perform methods, or comprise systems, within the scope and spirit of the invention.

DESCRIPTION

Generality of the Description

This application should be read in the most general possible form. This includes, without limitation, the following:

• • References to specific techniques include alternative and more general techniques, especially when discussing aspects of the invention, or how the invention might be made or used.
  • References to “preferred” techniques generally mean that the inventors contemplate using those techniques, and think they are best for the intended application. This does not exclude other techniques for the invention, and does not mean that those techniques are necessarily essential or would be preferred in all circumstances.
  • References to contemplated causes and effects for some implementations do not preclude other causes or effects that might occur in other implementations.
  • References to reasons for using particular techniques do not preclude other reasons or techniques, even if completely contrary, where circumstances would indicate that the stated reasons or techniques are not as applicable.

The invention is not in any way limited to the specifics of any particular examples disclosed herein. Many other variations are possible which remain within the content, scope and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.

Definitions and Notations

The following definitions and notations are exemplary, and not intended to be limiting in any way:

When a computation or determination is said to be “at the AP”, “at the access point”, and the like, there is no particular requirement that a computing device included in, or substantially co-located with, the AP perform that computation or determination. The AP might have access, for example and without limitation, by a wire-line connection, to other computing resources which are able to supply an answer to the computation or determination.

The terms “destination”, and the like, when used with respect to information or messages, generally refer to either an immediate next hop in a communication chain, or to an intended recipient of the information in the message.

The phrases “reliable multicast delivery”, and the like, generally refer to delivery of multicast packets in such manner that (presuming that higher-level protocols make proper use of ACK packets) a sender can substantially guarantee that each and every multicast packet will be delivered to each and every designated destination.

The terms “send”, and the like, when used with respect to information or messages, generally refer to constructing and uttering a message to another element in a communication system. In the context of the invention, when a message is received and “sent”, there is no particular requirement that the original signal or exact original bits of the message be included in the new message that is “sent”.

The terms “stream”, “streaming”, and the like, and the phrases “streaming (some type of) data”, and the like, generally refer to a sequence of messages intended to be received and used to present a time-varying signal. For example and without limitation, such a time-varying signal might include audio-visual data for presentation as part of a movie or television show.

The terms “superior”, and the like, and the phrases “superior to”, and the like, when used with respect to messages sending or transmission, generally refer to any set of transmission parameters which are preferred. For example, a 1^st set of transmission parameters might be superior to a 2^nd such set, in any one or more the following cases: faster per-bit throughput, lower bit-error rate, lower power required.

The phrases “wireless communication system”, and the like, generally refer to any communication system including computing devices, in which at least some portion of the communication (such as between access points and wireless stations) is performed using a wireless technique.

After reading this application, those skilled in the art would recognize that these definitions and notations would be applicable to techniques, methods, physical elements, and systems—not currently known, or not currently known to be applicable by the techniques described herein—including extensions thereof that would be inferred by those skilled in the art after reading this application, even if not obvious to those of ordinary skill in the art at the time of reading this application.

Figures and Text

Where described as shown in a FIGURE, an element might include:

• • Other items shown in the FIGURE in addition to, or operating in combination or conjunction with, that particular element (or that particular element in combination or conjunction with other elements, whether shown or not shown in the FIGURE, and whether described or not described with respect to the FIGURE).
  • Other items not shown in the FIGURE, but whose inclusion would be known to those skilled in the art, or which would be known after reasonable investigation, without further invention or undue experimentation.
  • Subparts of that element, whether shown or not shown in the FIGURE, which might be convenient for operation of the element, but which are not necessarily required in the described context, or which might be necessary for operation of the element in the described context, but which are not necessary for description at a level understandable to those skilled in the art.

FIG. 1

FIG. 1 shows a conceptual drawing of a wireless communication system.

A system 100 includes elements shown in the FIG. 1, including at least a control element 110, access points 120, wireless stations 130, and a communicating device 140 to an external network 150. These elements might cooperate in one or more of the ways described in the Incorporated Disclosures, or as in another operational wireless communication system.

Incorporated Methods

The control element 110 directs the access points 120 regarding which wireless stations 130 are assigned thereto. In general, IEEE standard 802.11 provides that each wireless station 130 should determine its best access point 120 to communicate with and should operate with the wireless communication system using that access point 120. In the FIG. 1, the control element 110 directs the access points 120 to respond (or not respond) to wireless stations 130 in compliance with a relevant standard; however, it directs the access points 120 to react in a way that causes the wireless station 130 (also in compliance with a relevant standard) to believe that its best access point 120 is the one assigned to it by the control element 110.

The Incorporated Disclosures describe at least two distinct ways by which this might be accomplished:

• • In a 1^st way, each access point 120 is supplied with the basic service set identifier (BSSID) of all authorized wireless stations 130; as a particular wireless station 130 moves about within the wireless communication system 100 (or if electromagnetic conditions change to prompt a similar change), the control element 110 determines, from time to time, which access point 120 is best for that particular wireless station 130, and directs the wireless communication system 100 to react as if that best access point 120 were the only one available to the wireless station 130.
  • In a 2^nd way, each access point 120 is supplied with the BSSID of only those authorized wireless stations 130 with which it might best communicate; as a particular wireless station 130 moves about within the wireless communication system 100 (or if electromagnetic conditions change to prompt a similar change), the control element 110 directs each particular access points 120 to add or remove such BSSID values from its memory, with the effect that the wireless communication system 100 should react as if the best particular access point 120 were the only one available to the wireless station 130.

In either case, each particular wireless station 130 is able to communicate with only the access point 120 to which it has been assigned by the control element 110. If a particular wireless station 130 desires to send a unicast message 160, that unicast message 160 is transmitted, received by its assigned access point 120, routed within the wireless communication system 100, possibly to the communicating device 140 toward a destination accessible using the external network 150. Similarly, if a unicast message 160 is directed to a particular wireless station 130, possibly from a sender accessible using the external network 150 to the communicating device 140, that unicast message 160 is routed within the wireless communication system 100 to the access point 120 assigned to that particular wireless station 130, which delivers that unicast message 160 to that particular wireless station 130.

One having skill in the art will appreciated that the control element 110 may be integrally formed as part of an access point 120 or be otherwise communicably coupled to an access point to effectuate the control element 110 functionality.

Receipt of Multicast Messages

If a particular wireless station 130 desires to send, or is one of the designated recipients of, a multicast message 160, that multicast message 160 first reaches an access point 120. That multicast message 160 would reach the access point 120 assigned to the sender, possibly the communicating device 140 if the sender is accessible using the external network 150.

When the multicast message 160 first reaches an access point 120, that access point 120 recognizes the message 160 as being multicast (as distinguished from unicast), and determines a set of designated destinations for that multicast message 160. Designated destinations might include one or more selected wireless stations 130, might include one or more destinations addressable using the external network 150, some combination or conjunction thereof, or otherwise.

While this description is primarily directed to cases in which the multicast message 160 explicitly designates all its recipients, in the context of the invention, there is no need for any such limitation. For example and without limitation, it might occur that a 1^st access point 120 reviews the multicast message 160, determines some number of destination wireless stations 130 assigned to it, and in addition, constructs and sends a revised multicast message 160 to a 2^nd access point for further processing.

In a case in which the wireless station 130 is a sender, the multicast message 160 reaches the access point 120 assigned to the wireless station. That access point 160 determines those destinations toward which the multicast message is directed.

The sending access point 120 constructs an A-MSDU packet 161, a type of message 160, including a packet header 162, packet body 163, and packet end-marker 164. The sending access point 120 constructs one such A-MSDU packet 161 for each destination it determines the multicast message 160 is directed toward. Note that an A-MSDU packet 161 is unicast to a particular wireless station 130, or possibly to the communicating device 140 if its destination is to be accessed using the external network 150. The packet header 162 of the A-MSDU packet 161 includes the MAC address of the particular destination, while the packet body 163 includes (a copy of) the original multicast message 160.

Construction of A-MSDU Packet

A-MSDU packets 161 provide for agglomerated transport of (copies of) multiple messages 160, so that multiple such messages 160 might be sent in a single message 160. The A-MSDU packet 161 including a (copy of) the multicast message 160 might also include (copies of) other multicast messages 160, and might include copies of other messages 160. For example and without limitation, an A-MSDU packet 161 might include copies of unicast messages 160 that the access point 120 has queued-up for sending.

In the case in which streaming audio-video data is sent to multiple destinations using multicast messages 160, it might occur that several of such multicast messages 160, each marked with its transmission order, are all (eventually, but hopefully sooner rather than later) sent to the destination. The access point 120 that constructs the A-MSDU packet 161 might choose to include multiple such multicast messages 160, with the effect that multiple such multicast messages 160 are combined into a single transport packet.

In the case in which streaming audio-video data, or other data, is sent from multiple senders to a single destination (for example and without limitation, when a television channel includes a picture-within-picture or split-screen feature), it might occur that several of such multicast messages 160, each marked with the MAC address of its sender, are all sent to the destination. The access point 120 that constructs the A-MSDU packet 161 might choose to include multiple such multicast messages 160, with the effect that multicast messages 160 from disparate senders are combined into a single transport packet.

There is no particular requirement that the access point 120 balance the number of multicast messages 160 it encapsulates (copies of) within the packet body 163 of the A-MSDU packet 161. A 1^st such A-MSDU packet 161 might include only one such multicast message 160; a 2^nd such A-MSDU packet 161 might include two or more multicast messages 160 from the same sender; a 3^rd such A-MSDU packet 161 might include single or multiple ones of multicast messages 160 from more than one sender, and might also include any “stray” unicast messages 160 the access point 120 happens to have available when constructing some particular A-MSDU packet 161.

Reliable Delivery of A-MSDU Packet

When each particular device for which the multicast message 160 was designated (for example and without limitation, each particular wireless station 130 or the communicating device 140) receives the A-MSDU packet 161, that A-MSDU packet 161 includes the specific MAC address for that particular wireless station 130. The destination wireless station 130 (hopefully) receives the A-MSDU packet 161 and responds with an ACK packet 171, another type of message 160. When the access point 120 associated with that destination wireless station 130 receives the ACK packet 171, it can reliably assure the sender of the multicast message 160 of receipt by that particular destination wireless station 130.

In the event that one or more of these ACK packets 171 is lost, stolen, or otherwise unaccounted for, the access point 120 might retry sending the A-MSDU packet 161 to those destination wireless stations 130 for which no ACK packet 171 was received. Acknowledgement and retry, together with backoff are techniques known in the art of computer communication to assure reliable delivery of messages 160 to destinations. The access point 120 might use acknowledgement and retry, or some other technique, to assure reliable delivery even if one or more such ACK packets 171 goes awry.

Reliable Acknowledgment of A-MSDU Packet

As noted above, the access point 120 waits for, and should receive, an ACK packet 171 for each individual destination, for each individual A-MSDU packet 161. Each particular ACK packet 171 has the effect of showing that its particular destination has received the A-MSDU packet 161, and by implication, that it has received each of the multicast messages 160 included in the packet body 130 of that A-MSDU packet 161. This has the effect that multicast messages 160 are reliably delivered, notwithstanding that the IEEE 802.11 standard provides for no such mechanism.

While this description is primarily directed to cases in which ACK packets 171 might be agglomerated into A-MSDU packets 161, in the context of the invention, there is no particular requirement for any such limitation. For example and without limitation, access points 120 and other routing elements on a communication pathway back from the destination access point 120 might receive such A-MSDU packets 161, parse them, and extract or insert other data in the packet data 163.

Such other data might include ACK packets 171 produced by distribution of other multicast messages 160, individualized ACK packets 171 produced by sending unicast messages 160, stray unicast messages 160 an intermediate access point 120 has ready for sending, other multicast messages 160 for delivery in a different communication direction, some combination or conjunction thereof, or otherwise.

Transmission Parameters

As noted above, a distributing access point 120 might choose to combine more than one multicast message 160 from the same source, or multicast messages 160 from more than one source, or some combination or conjunction thereof.

In the case that more than one multicast message 160 is encapsulated in a single A-MSDU packet 161, a particular access point 120 might be able to achieve superior communication with a particular wireless station 130, notwithstanding that multiple unicast messages 160 (the A-MSDU packets 171) are constructed in response to each such multicast message 160.

Other cases might also provide for superior communication between an access point 120 and its assigned wireless stations 130:

• • The access point 120 might alter the transmission parameters for the A-MSDU packet 161 to differ from the spawning multicast message 160. This might have the effect that multicast messages 160 distributed using the least generally-available communication paths could have superior communication for cases in which there is a subset of superior communication paths.
  • The access point 120 might alter the transmission parameters for the A-MSDU packet 161 when combining more than one multicast message 130 from the same source to a particular one destination into a single A-MSDU packet 161. This might have the effect that communication is superior to sending those more than one multicast messages 130 separately (even if they are multicast).
  • The access point 120 might alter the transmission parameters for the A-MSDU packet 161 when combining multicast messages 130 from more than one source to a particular one destination into a single A-MSDU packet 161. This might have the effect that communication is superior to sending those more than one multicast messages 130 separately.
  • The access point 120 might alter the transmission parameters for the A-MSDU packets 161, as they are constructed, in response to movement by wireless stations 130, reassignment of wireless stations 130 by the control element 110, changes in electromagnetic or other transmission characteristics, changes in alternative traffic contending for the same communication path, some combination or conjunction thereof, or otherwise.
  • The access point 120 might alter the transmission parameters for the A-MSDU packets 161, as they are constructed, in response to other communication traffic, such as the possibilities that more or fewer wireless stations 130 choose to be recipients of multicast messages 160, in response to bursty or other time-varying characteristics of the multicast messages 160.
  • The access point 120, or the control element 110, might consider whole-network optimization of sending multicast messages 160. This has the effect that individual A-MSDU packets 161, even between the same access point 120 and the same wireless device 130, under the same conditions, might have different transmission parameters. This might also have the effect that some multicast messages 160 are actually delivered in an inferior manner (for example, slower) so that other multicast messages 160 can be delivered in a superior manner (for example, with less bit-error rate).

ALTERNATIVE EMBODIMENTS

The invention has applicability and generality to other aspects of wireless communication. It is not limited to wireless communication based upon 802.11 standards, nor is it limited to any particular IEEE standard, to any particular communication standard, or even to wireless communication. One having skill in the art will recognize that the systems and methods disclosed herein may be effectuated using other techniques.