Scalable WiFi Media Delivery through Adaptive Broadcasts

Sayandeep Sen, Neel Kamal Madabhushi, Suman Banerjee

University of Wisconsin-Madison

Abstract multicast scenarios, the biggest advantage of the system

arises in the multicast case where multiple users are in-
Current WiFi Access Points (APs) choose transmission
terested in the same content.
parameters when emitting wireless packets based solely
A target campus application and challenges: The IT
on channel conditions. In this work we explore the
department of the UW-Madison campus is interested in
benefits of deciding packet transmission parameters in a
providing high quality broadcast of specific educational
content-dependent manner. We demonstrate the benefits
content through its intranet. Such capability would allow
specifically for media delivery applications in WiFi en-
students sitting in dormitory rooms, in union buildings,
vironments by designing, implementing and evaluating a
in cafeterias, and in libraries, to follow the classroom.
system, called Medusa. In order to keep the APs rela-
Further, the system would also allow easy and conve-
tively simple, we implement the Medusa functions in a
nient dissemination of live guest lectures from remote
media-aware proxy. More specifically, when forwarding
locations, without requiring the guest lecturer to visit the
our media traffic, Medusa requires that APs simply use
campus. While the wired backhaul has sufficient capac-
the WiFi broadcast feature, and that they refrain from
ity to carry such media traffic, initial experiments by the
making decisions on which wireless packets to retrans-
IT department revealed obvious performance problems
mit, or what PHY rates such packets should be trans-
on the WiFi based last hop. In particular, they observed
mitted at. Instead we combine these typical link layer
that even if 3 users connected to a single 802.11g AP
functions with a few other content-specific choices, in
attempted to watch the same HD video stream, the per-
the proxy. Through detailed experiments across diverse
formance of the system was abysmally poor 1 .
mobility and interference conditions we demonstrate the
The poor performance of media delivery over WiFi
advantages of this scheme for both unicast and multicast
for multiple users requesting the same content, is a com-
media delivery applications. The advantages are partic-
bined effect of three factors: (i) HD quality video places
ularly substantial in multicast scenarios, where Medusa
a high bandwidth demand on the wireless medium —
was able to deliver a 20 Mbps HD video stream simul-
commercial HD encoders, such such as the Streambox
taneously to 25 clients, using a single 802.11 AP, with
SBT3-9200 [6], create content with data rates ranging
good to excellent PSNR.
from 512 Kbps to 30 Mbps, (ii) WiFi typically employs
1 Introduction 802.11 unicast mode for sending similar content sepa-
Robust delivery of rich media content over wireless links rately to each user, and (iii) the WiFi transmitter makes
is an increasingly important service today. As more various configuration choices, e.g., PHY transmission
and more high quality media content becomes available rates, number of re-transmission attempts, etc., for each
through the Internet, the user expectation of accessing wireless packet, without any knowledge of the relevance
such content over their wireless enabled devices continue of its(packet’s) contents to end applications. In this pa-
to grow. Examples include users watching on-demand per, we design and implement a system called Medusa —
shows and movies from sources such as Hulu and Net- Media delivery using adaptive (pseudo)-broadcasts, that
Flix, students in a university campus interested in fol- can efficiently address issues (ii) and (iii).
lowing online lectures while sitting in the cafeteria, and
employees in a company watching a company-wide pre- 1.1 Medusa approach
sentation by their CEO, whether at home, at work, or The 802.11 transmitter typically transmits packets in
while sitting in a coffee shop. While the widely deployed the FIFO order and makes multiple decisions for each
WiFi technology can provide adequate performance for wireless packet transmission. This include channel con-
relatively lower quality media streams, the user experi- tention, i.e., when to attempt wireless transmission, se-
ence when watching high quality streams (e.g., HD qual- lection of the PHY rate for the packet, and the number
ity content) leaves much to be desired. In this paper, we of re-transmission attempts to make in case of failures.
attempt to push the envelope of media delivery perfor- In this paper we contend that many of these decisions,
mance for WiFi systems, by exploiting some knowledge namely PHY rate selection, number of re-transmission
of media content in making transmission parameter se-
1 An 802.11n AP can potentially scale performance to upto 10-12
lection at the wireless transmitter (APs). While our pro- users watching such HD content simultaneously. The typical number
posed approach applies equally to unicast as well as to of users in busy parts of campus is often much higher.
attempts for each packet, and the order of packet trans- 1) Priority estimation 2) Packet ordering
missions, are better made by taking the “value” of the 3) Network coding 4) Recp. report processing
wireless packet to the application into account as well.
Let us consider MPEG-encoded [4] video content that Medusa Packets Medusa Proxy
consists of I-, P-, and B- video frames. Given that a
packet carrying I-bits is more important, the PHY rate Client Video Packets
of such a packet can be picked more conservatively, than
value-unaware rate adaptation algorithms, e.g., Sam-
pleRate [8]. This would ensure that the loss probability Client Reception report
of packets carrying I-bits are particularly low. Similarly,
Client Client
if the wireless channel capacity is scarce and packet er- Video Server
rors are high, then it is more important to devote greater
re-transmission effort for packets carrying I-bits, than Figure 1: Schematic of the Medusa shared media deliv-
packets carrying P- and B-bits. ery system.
Hence in Medusa, we offload these decisions for our
media traffic to a media-aware proxy that can inter- PHY rate adaptation mechanism. Hence, we incorpo-
pret the value of the data. More specifically, APs in rate higher layer acknowledgments from the clients to
Medusa no longer perform link-layer re-transmissions or the proxy, that help the latter in making these decisions
PHY rate selections. Instead, the proxy examines the for the APs in a content-dependent manner.
value of each packet to applications, and instructs APs to In a single user scenario, we could use 802.11 unicast
(re)transmit these packets in a certain order and at speci- transmissions. However, even in such settings, it is pos-
fied PHY rate. sible to exploit ER-style network coding opportunities
Prior work, e.g., Trantor [21], has considered a model when transmitting wireless packets [23]. Such network
in which a centralized controller decides transmission coded packets, by definition, have multiple intended re-
parameters, e.g., PHY rates, transmit power, etc. for dif- cipients. Broadcast-based 802.11 packets are suitable to
ferent APs and clients in an entire enterprise WLAN. At facilitate this enhancement as well.
a high level, our proposal of proxy-based PHY rate se- Lack of MAC-layer acknowledgments is problematic,
lection and re-transmissions may appear similar. How- however, for one more link layer decision that has to
ever, there is a fundamental difference between the two be taken by the APs — channel contention. Lack of
proposals. Trantor suggests a centralized rate selec- acknowledgments indicating packet losses, prevent APs
tion in a content-agnostic manner, based solely on po- from inferring how the MAC layer backoff counters
tential interferences between different conflicting wire- should be adjusted. Given the lack of MAC-layer ac-
less links. The approach in Medusa augments this de- knowledgments for broadcast packets, the existing meth-
cision by incorporating knowledge about value of the ods for channel contention are likely to fail. Hence, we
packet contents to applications in deciding the PHY rate use pseudo-broadcast packets in Medusa to communi-
of packets, the order in which they should be transmit- cate all broadcast media content, analogous to what was
ted, and the number of re-transmission attempts to be proposed in COPE to deliver network coded multicast
made. It also optionally utilizes simple network coding data [18]. In pseudo-broadcast, 802.11 unicast mode is
approaches [23] to improve efficiency. used where one of the receivers is picked at random to
Unicast vs broadcast vs pseudo-broadcast: In a sce- be the explicitly stated (unicast) recipient, while other
nario where multiple users are requesting the same con- intended recipients simply overhear the packet. MAC-
tent (the same media stream, for example), we advocate layer acknowledgments arrive from the explicit recipient,
the use of 802.11 standard’s broadcast mode of opera- and backoff parameters can be appropriately adjusted.
tion. The choice is motivated by the observation that Note that these MAC-layer acknowledgments are inter-
a 802.11 broadcast packet can be used to communicate preted by the APs solely for the backoff adjustment func-
content simultaneously to all receivers. This would sub- tion, and not used by the proxy to decide PHY rate, trans-
stantially reduce the load on the wireless medium. How- mission order, or eligibility for re-transmission of pack-
ever, MAC-layer broadcast packets do not elicit MAC- ets.
layer acknowledgments from receivers, leaving the trans- Medusa system overview: Figure 1 shows a
mitter unaware of losses on the wireless channel. This is schematic of different aspects of the Medusa system,
a problem for any broadcast-based wireless system, as including an unchanged media server, a media-aware
the transmitter can no longer decide which packets re- Medusa proxy, and APs and clients with minor software-
quire re-transmissions. Further, absence of loss infor- level changes. The Medusa proxy intercepts all IP pack-
mation makes it impossible to determine an appropriate ets corresponding to various video frames and relays
them to the AP for transmission. The proxy instructs range of channel conditions and mobility scenarios. Our
the AP to use 802.11 pseudo-broadcast for each wireless technique is applicable to unicast media delivery scenar-
packet (irrespective of whether it is part of a multicast ios as well.
or a unicast stream) and also informs the AP what spe-
cific PHY rate to transmit the packet at. The Medusa 2 Medusa design overview
proxy makes these decisions, using a combination of We describe the design of Medusa by using the exam-
four mechanisms: (i) WiFi reception reports: Each client ple of MPEG4-encoded [4] video delivery over wireless.
provides a periodic reception report to the proxy about In MPEG4 the video content is partitioned in an inde-
various wireless packets that it did or did not receive. pendently decodable sequence of pictures, called Group
While analogous to Reception Reports in RTCP [24], of Pictures (GOP). Each GOP has frames of three dif-
the reception reports in Medusa differs from those in ferent types: I, P and B. Each frame, in turn are broken
RTCP in the detailed MAC layer information that is car- down into multiple packets which are then transmitted
ried in Medusa for rate adaptation and re-transmission over wireless channel.
purposes. (ii) Estimating the value of a packet to me- At the receiver, the I frames can be correctly decoded,
dia applications: Not all packets are of equal impor- as long as all constituent packets are received. For decod-
tance to receivers. When the wireless channel capacity ing P packets, the successful reception of previous I or P
is scarce, the value of each packet determines the choice frame in sequence is also necessary. Finally, to decode a
of PHY rate and the number of re-transmission attempts B frame, the previous as well as the next I or P frame in
to be made to deliver the packet. We use a simple per sequence are needed. Put another way, an I frame does
packet value assignment function at the Medusa proxy not depend on any other frame, while P frames depend on
to determine the priority level of each packet encapsu- another frame and B frames depend on two other frames.
lating a media stream. (iii) PHY rate adaptation and re- As described, Medusa involves an unchanged media
transmissions for broadcast packets: We design a PHY server, a media-aware proxy, and APs and clients, with
rate adaptation and re-transmission strategy for broad- small software modification. The only change in the
cast wireless packets that cannot depend on MAC-layer AP is to create a single functionality — for each packet
acknowledgments. Our rate adaptation scheme is two- forwarded by the proxy to the AP, the proxy should be
paced. A conservative baseline PHY rate is identified at able to specify the PHY rate of transmission. The AP
a slow timescale, and an individual PHY rate for each simply accepts each such packet (which can be an orig-
packet is chosen subsequently using an algorithm called inal packet, a previously transmitted packet, or a net-
Inflate-Deflate. (iv) Packet order selection and network work coded packet) and transmits them using the pseudo-
coded re-transmissions: We modify the ordering of me- broadcast mode using the PHY rate specified by the
dia packets from traditional FIFO, especially when the proxy. The AP continues to perform back-off decisions
channel quality is poor. Under bad channel conditions, independently based on MAC-layer acknowledgments
it is beneficial to prioritize packet transmission based received for its pseudo-broadcasts. The client is modi-
on packet “value”. This would increase the probability fied to incorporate WiFi reception reports targeted to the
of successful reception of important packets. Further, proxy. These reception reports include a higher layer ac-
the transmission order is also selected such that there knowledgment (ACK) bitmap, and is sent infrequently
are proxy-initiated re-transmission opportunities for the by the clients, roughly once every 100 packets or 100 ms.
more important packets. During re-transmissions, we Since the proxy knows the PHY rates at which different
also leverage the gains of ER-style network coding. packets were transmitted, it can use these reception re-
Key contributions: Summarizing, the key contribu- ports to infer packet losses observed by different clients
tions of this work is two-fold: at different PHY rates.
(i) We propose an intuitive design of a pseudo- Based on this simple setup, the design problem of
broadcast based WiFi system for media delivery at high Medusa can be stated as,
video rates. The design incorporates various aspects of For a set of k video packets (including both original
rate adaptation, re-transmission, and packet priorities, packets and packets that need re-transmissions), deter-
coupled with higher-layer feedback. mine the order of transmission and PHY rates for the
packets, and pass this information along with the pack-
(ii) We integrate all of these ideas together into a func- ets to the APs. Further, determine whether some of these
tional Medusa system and present detailed evaluation of packets should be network coded, and whether some of
this system. Our results show that Medusa provides ro- them should be discarded.
bust, high-bandwidth (upto 20 Mbps), HD quality me- We present a particular solution to the above problem
dia delivery to tens of co-located WiFi users interested in in the rest of this section that exploits knowledge of the
the same content, all sharing the same WiFi AP, across a value of each packet to applications.
 While we describe our scheme for MPEG4 video, our successful reception. However, if the channel is error
approach generalizes to any other media encoding, where prone, then some of these rates will be updated, as de-
the content is structured in layers, and there are different scribed in Section 2.3. The timescale for adapting base
levels of priority (value) for each layer. PHY rate depends on the reception report frequency of
clients (roughly every 100 ms in our current implemen-
2.1 Determining value of packets tation).
As mentioned above successful decoding of video frames We pick the highest PHY rate such that the expected
might need reception of other video frames. Hence, all error probability of the packets at all clients would be
else being equal, the value of each video packet depends below a certain threshold (set to a low value) as the
on how many other packets (or bytes) depend on this base PHY rate. By retaining PHY rate information for
packet for correct decoding of various video frames. Nat- all transmitted packets, the proxy, on receiving ACK
urally, I-frame packets become more important than P- or bitmaps from client, can infer the necessary error rates.
B-frame packets. The value of video packets is also in- In case statistics for certain PHY rates are missing (pos-
fluenced by its impending playback deadline and that of sibly because no packets are sent at these rates), standard
other dependent video frames. Packets for video frames interpolation techniques can be used to estimate the ex-
that are approaching display deadline are more impor- pected error rates.
tant. Finally, given that many packets are relevant to An important distinction of our broadcast rate assign-
more than one client (true for original and re-transmitted ment from typical 802.11 unicast rate assignment algo-
and network coded packets), the value of a packet should rithms( [8, 30]) is that, it does not favor a higher rate to
also grow with the number of intended recipients. merely increase the channel utilization. Instead it tries to
Previous research on video encoding for streaming [9, ensure high reception probability across multiple broad-
12, 19, 26] has proposed LP based techniques for deter- cast receivers (who might have diverse channel condi-
mining the priority of video frames. Such techniques tions).
typically utilize a directed acyclic graph (DAG) of video Another distinction of Medusa rate adaptation from
frame dependencies along with a (empirical/theoretical) unicast stems from inability of Medusa to adapt quickly
channel error model to determine relative value for to changed network conditions, due to delayed ACKs.
frames. This can result in Medusa persisting at high data rate
While such sophisticated designs of packet value can even when channel quality has deteriorated resulting in
certainly be used, in this paper we consider a relatively high errors. To ensure that such a situation does not
easy to compute function to determine packet value to occur, we update the error characteristic of the PHY
applications that illustrates its usefulness in making rate rates with a EWMA function with heavy weight on his-
adaptation, re-transmission, packet ordering, and net- tory(thus preventing it from reacting to transient fades of
work coding decisions based on the worth of packet con- the channel).
tents. Transmitting packets at base PHY rate ensures that
In our scheme, we assign a weight, X, to each video the packets have a good likelihood of successful recep-
frame, based on how many bytes the frame can help de- tion. However, if the base rate of the system is too low
code (including itself). This weight is given to all con- (say, due to presence of clients with bad channel quality)
stituent packets of this frame. Our media-aware proxy which limits successful transmission of all video packets
knows the video encoding process, and can calculate before their respective deadlines. Under such circum-
X by buffering and observing packets corresponding to stances, we selectively increase the transmit rate of dif-
each GOP before making transmission decisions. We ferent packets in a certain order as described next.
next assign a weight, C, proportional to the number of
intended recipients of each packet. Finally, we assign 2.3 Packet order and actual PHY rate
a third weight, D, based on the delay until the display The problem of deciding the video packet schedule while
deadline of this frame. We normalize all these weights to maximizing the delivered quality across a group of users
the same scale, and assign the value of the packet to be is known to be NP-complete [12]. Hence, we use a
the product of these normalized weights, thus, heuristic algorithm for packet ordering. We now de-
Value = X̄ × C̄/D̄. scribe our mechanism to determine the transmission or-
der and PHY rate of packets, using an algorithm, we call
2.2 Determining a base PHY rate Inflate-Deflate. The heuristic schedules a batch of pack-
Our PHY rate selection process is two paced. Initially, ets in each round. For ease of exposition we assume the
we compute a conservative PHY rate for all the packets. presence of a virtual timeline and our goal is to place
If channel capacity is abundant, all packets will simply packets on this timeline and determine their PHY rate.
be transmitted at this rate to enhance the possibility of Placing the packets at a given timeslot signifies schedul-
 packets would mean that scheduling all packets at their
ideal slot might not be possible. We depict such a sit-
uation in Figure 2(b), in this case scheduling packet D
at its ideal slot would lead to an overlap with packet C.
We mandate that the packet with the lower value be the
one which gets moved around. We find a best fit timeslot
in the schedule for the lower valued packet D. Note by
considering packets in order of their value implies that
only the current packet needs to be moved.
Case-III (No slots left at current PHY rate): In ex-
treme case, we might be unable to find a big enough time
slot for a packet, for example in Figure 2(c) we are un-
able to find a timeslot big enough to fit packet F at its
base rate, before its deadline. In such a case, we increase
the data-rate of the packet, we call this operation Deflate
as it results in shortening the packet dimensions on the
transmission timeline. For example, we were able to fit
F on the timeline after deflating operation. In this op-
eration, we keep trying to find a best-fit timeslot for the
Figure 2: Packet ordering and final rate assignment car- packet by increasing its rate. This process continues till
ried out by Medusa. we find a slot to fit the packet, or we exhaust all rates
ing the transmission of the packet at that instant. Packets without being able to fit the packet on the timeline. This
(including retransmission candidates) are added onto the would imply the inability to schedule the packet in the
timeline in the decreasing order of packet value (as cal- current round. We show this in Figure 2(d). Packet G
culated in Section 2.1), i.e., higher valued packets are could not be placed in the timeline even at the highest
placed first, and lower valued packets later. PHY rate and hence, had to be left out from current iter-
We describe our algorithm for ordering packets next ation.
and illustrate it with a toy example. We consider Case-IV (Compensating for rate optimization):
A, B, C, D, E, F and G as the seven packets which need Packets with only a few intended recipients(say, ones
to be transmitted (Figure 2). The width of a packet sig- with bad channel quality) would have lower value. Thus,
nifies the time required to transmit the packet at its base such packets would potentially be transmitted at higher
PHY rate. Initially we try to place each packet at its ideal rates. This might lead to drastic degradation in received
timeslot — a time by which it needs to be transmitted video at clients with bad channel quality. To remedy this,
so that it can be re-transmitted multiple times in case of we carry out a round of rate re-assignment before send-
consecutive losses. Also, the latest timeslot at which a ing out the packets. We call this operation Inflate as it
packet can be placed is when it just makes its playback decreases the rate of some packets, thus, increasing their
deadline for the slowest client, called the deadline slot size on the transmission timeline. Note that the inflate
for the packet. The reason for not placing a packet at process does not increase the size of the timeline itself.
the earliest available slot, is to ensure that packets which Inflating is carried out by going through the list of active
have lower value but have an earlier deadline than the clients and calculating the expected distortion in video
more important packets still get a chance to be scheduled. quality, they would suffer if the packets are sent out ac-
When the current time is past a packet’s deadline slot, cording to current plan. In case the expected quality of a
and it is not required for decoding any other packet at client falls below a certain minimum threshold, we find
any receiver, the packet can be discarded. We now walk out the packet which can increase the expected quality of
through the example of how different packets get placed reception the most and we decrease the rate of transmis-
on the scheduling timeline using the following cases. sion of the packet. We then try and compensate by deflat-
Case-I (Sufficient time is available to schedule all ing a few other packets which would minimally decrease
packets at ideal time-slot): This scenario is depicted in the quality of video at clients. This process is illustrated
Figure 2(a). Here, packets A, B, and C are scheduled at in Figure 2(e). In this example packet F is deemed a
their ideal timeslot. Also, the packets are assigned their valuable packet for a client with poor channel quality and
base rates. hence, its rate is reduced, while the transmission rates of
Case-II (Ideal slot occupied by a higher valued D and E are increased as a compensation.
packet): Under realistic settings, contention from other Note that Inflate, might lead to overall reduction in
traffic sources and the necessity to retransmit different quality of video received over all clients. We keep it in
order to ensure that a minimal quality of video is served
to each client. Algorithm 2.1: N ETCODE(P )
We would like to note that once this order has been
determined, we do not delay the transmission of pack- INPUT P: set of coding candidates,
ets until the scheduled timeslot. Instead the packets are arranged in decreasing order of packet values
sent out at the next transmission opportunity. This en- Coding set: Set of packets to be coded
sures that we get even more opportunities to retransmit Pi .client set: Set of clients interested in Pi
the packets before its deadline expires. The virtual time- OUTPUT S: set of coded packets
line and time slots are, thus, used only to determine the for each Pi ∈ P
order of transmissions and the corresponding rates. do Coding set ← φ
An interesting aspect of the PHY rate selection using
Inflate-Deflate is that many packets can get transmitted  Pj ∈ P, j > i
for each
if is coding worthy(Pj , Coding set) = true
at distinct rates based on the rate assignment algorithm. do
then Coding set ← Pj
As a consequence, the proxy can get feedback on a large if Coding
range of PHY rates from the clients, without having to  set 6= φ
X ← make coded packet(Pi , Coding set)
explicitly raise the base PHY rate. This is another dif- then X.rate ← Pi .rate
ference between the rate adaptation and error rate esti- 
S←X
mation technique employed by Medusa from unicast rate else S ← Pi
adaptation techniques such as SampleRate [8]. return (S)
procedure IS CODING WORTHY(Pj , Coding set)
2.4 Re-transmission planning
 Ci ∈ Coding set
for each
We discuss the three inter-related components of re- if Pj .client set ∩ Ci .client set 6= φ
transmission planning next. do
do return ( false )
Timeout estimation: A key issue in planning for re- return ( true )
transmissions is to determine the timeouts accurately —
under-estimating would lead to redundant packet trans-
mission, while over-estimation would lead to video pack- decided. This is done to keep the packet ordering algo-
ets missing their playback deadline. Since each client rithm simple, as otherwise the algorithm would have to
reception report acknowledges a block of packets, we deal with coded packets (with multiple constituent pack-
have to adjust the round trip time and the timeout cal- ets of different values), while deciding the sending order
culations, to account for additional delays incurred in and rate. A coded packet is always transmitted with the
clients. We adopt a TCP-like Exponentially Weighted intended PHY rate of the first packet in the set. This en-
Moving Average (EWMA) mechanism for RTT estima- sures that the probability of error in receiving the first
tion, which takes into account this change. Furthermore, packet at its intended receivers is not hampered, while
we re-compute the value for all packets that become eli- opportunistically delivering other packets in the coded
gible for re-transmissions, and use this new value to de- set to their respective clients. At the client side all re-
termine the packet transmission ordering and PHY rate. ceived packets (natively or from network coded packets)
Network coded re-transmissions: As packet errors at packets are maintained till their deadline expires. This
different locations occur independently, multiple clients is done to ensure that packets coded with previously re-
would potentially (not) receive different packets from a ceived packets can be recovered. The client sends back
set of consecutive transmissions. This allows us to de- acknowledgment for packets which are successfully de-
ploy a simple XOR-based coding [23] of packets to be coded as part of reception reports.
re-transmitted, to further optimize channel utilization. In Delayed Packet discard: The deadline for packet
our system, we XOR-code a group of packets, only if delivery shifts over the duration of a streaming session.
they satisfy the following rule: Out of a set of packets to We initially set it to the playback deadline of the frame,
be re-transmitted, if a subset of packets can be found such which is calculated using the following formula,
that each intended recipient of a specific packet has re- Frameseqno
ceived all other packets in the subset , then the subset can Deadline = Frame Rate + Playback buffer size + δ,
be network coded. Such coding opportunities occur fre-
quently in the proxy, as MAC-layer re-transmissions are where, the deadline is number of seconds from the
not used in Medusa . The algorithm for network coded transmission time of the first video frame, Frame seqno
re-transmissions is shown in Algorithm 2.1. is the sequence number of the frame. Frame Rate is the
A key decision in our design is to determine the set number of frames that the video player needs to display
of packets to be coded after the packet order has been in a second. Playback buffer size is the amount of time
(in seconds) that the receiver can store the video before MOS Rating of video quality PSNR range
it needs to start decoding the frames. And, δ is a small Excellent > 37
time constant added to account for initial frame delay. Good 31-37
Once the playback deadline of a packet expires, we re- Fair 25-31
set the deadline for delivering its constituent packets to Poor 20-25
that of the next frame which depends on the successful Bad < 20
reception of the packet for decoding. This goes on until
the packet is delivered to all clients, or the deadlines of Table 1: Table mapping the MOS based user perception
all the frames which depend on the current packet have of video quality to the PSNR range
expired. We drop the packet from our system at that in-
stant.
Similarly, at client, we discard a packet only if its play- Video setup: We experimented with different video
back deadline has expired and the packet is not useful for clips, in this paper we present results for the Mobile cal-
decoding any other frame. ender video clip [3] replayed back to back to run for 2
minutes. The video was encoded at rates of 5, 10, 15 and
3 Putting it all together 20 Mbps using FFmpeg [2] tool with H264 codec. We
We have implemented the Medusa proxy and client. The have repeated each experiment for 20 runs. For our ex-
implementation consists of about 3.5K lines of C code. periments, we used a fixed playback buffer of 10 seconds
We stream video using the Evalvid tools package [1]. at clients. We intend to evaluate the benefits of adaptively
We modified Evalvid to provide information about de- modifying the playback buffer size in future.
pendency structure of video frames, frame type of the Metrics: We compare the performance of different
generated packet and the deadline of the packet. The schemes in terms of Peak Signal-to-Noise Ratio (PSNR),
Medusa proxy runs as an application level process. We jitter, and overall network load imparted.
modified the MadWiFi driver to carry out per-packet rate PSNR: Is a standard metric for measuring the relative
assignment. Per packet rate assignment is achieved by quality of video streams [13,20]. The PSNR of a video is
specifying the target rate in a header of the video packet well correlated with the perceived quality of video expe-
and then extracting it out of the packet inside the AP’s rienced by the user. The relationship between user per-
driver. ception expressed in Mean Opinion Score (MOS)and the
At the client, the Medusa module keeps information PSNR range were detailed in [17, 22] and are summa-
regarding number of packets received and the channel rized in Table 1.
quality. The module passes the received video pack- Jitter: We measure the Instantaneous Packet Delay
ets to video playback software such as VLC [7] and Variation(IPDV) [14] of received packets as a measure
MPlayer [5], for displaying. It also keeps a copy of re- of jitter of the delivered video stream. This metric com-
ceived packets, till the expiry of their deadline for decod- plements the PSNR metric which is oblivious to the de-
ing other packets. lay and jitter of the delivered video, as it assumes the
presence of an infinite playback buffer. High jitter value
4 Evaluation signifies a bad performance.
To study the performance of Medusa we have experi- Network load: We measure the load placed on the
mented with upto 25 users that are associated to a sin- network by different schemes in terms of the a) num-
gle AP(operating in 802.11g mode) and attempting to ber of packets transmitted in air and also in terms of
receive HD quality video from the Medusa proxy. Our amount of air-time occupied by the packets sent by dif-
setup consists of 30 laptops with Atheros wireless driver ferent schemes.
running Linux operating system. Compared schemes: We compare the performance of
Wireless conditions: The experiments were done on a Medusa to the following alternate schemes.
university building floor. We broadly classify our wire- BDCST: This scheme uses WiFi broadcast to transmit
less environment into three types: (i) Low-loss environ- packets. However, unlike normal WiFi broadcast, the
ment - corresponding to specific client locations where PHY rate is chosen to maximize the video PSNR per-
the packet error rates were 5% or less; (ii) Medium-loss formance averaged across all clients. The PHY rate is
environment - corresponding to locations where packet selected by sending about 30 seconds of traffic at differ-
error rates were in the range of 5-15%; and (iii) High-loss ent rates.
environment - corresponding to locations where packet UCAST-INDIV: In this scheme we send the video
error rates were in excess of 15%. For the set of experi- stream to each client using isolated WiFi unicast, in se-
ments reported, an experiment location did not shift from quence. For example, if there are two clients, we first
one to another in the course of experiment. send the entire video to client 1 and then the same video
 45 creased from 1 to 25. But even with 25 clients, the aver-
40 age PSNR value is around 37 while BDCST performance
35 is around 27 (a 10 dB difference). The gradual degrada-
tion in performance of BDCST is because of the almost
PSNR(dB)

30
25 similar nature of errors experienced at each client(10-
20 UCAST_INDIV 15% packet error).
15 MEDUSA The performance of UCAST-SIMUL suffers as
BDCST
10 UCAST_SIMUL 802.11a/g technology cannot support more than 2
5 streams with 20 Mbps rate(20 + 20 = 40 Mbps net load).
0 Scalability in video rate: We fix the number of clients
0 5 10 15 20 25
to 10 and evaluate how the performance scales with in-
Client count
creasing video rate — from 1 Mbps to 20 Mbps. We
show the results separately for clients in good, medium
Figure 3: Plot showing the average per client PSNR of
and bad channel conditions in Figures 4(a), (b) and (c)
different scheme when serving 25 clients with a 20 Mbps
respectively.
video stream, under medium loss conditions. The mean
For good channel condition we observe that UCAST-
and the variance (errorbars) are shown.
SIMUL quickly degrades in performance with increase in
video rates. Even at 5 Mbps (where the aggregate load is
expected to be 5 × 10 Mbps = 50 Mbps), a lot of packet
separately to client 2 using WiFi unicast. This scheme losses and buffer underflows occur. BDCST performs
gives a quality bound for Medusa. better and provides a more gradual performance degra-
UCAST-SIMUL: In this scheme we send the video traf- dation across the different rates. However, Medusa out-
fic to all the clients simultaneously using normal WiFi performs both and performs identical to UCAST-INDIV.
unicast with SampleRate rate adaptation. This is the tra- With worsening channel condition as shown in Fig-
ditional method for wireless data delivery. ure 4(c) the performance of all schemes suffered. An in-
Note that in all of these alternate schemes described teresting observation is that the performance of UCAST-
above, there is no proxy and the APs and clients are INDIV became worse than Medusa as the traffic load
unmodified, i.e., the APs take PHY rate adaptation and (video rate) increased above 15 Mbps. This is due
packet re-transmission decisions, while clients do not to “head-of-line” blocking in AP wireless NICs in the
need to send out reception reports. UCAST-INDIV case. Essentially, when various P- or B-
To evaluate Medusa we first look at the overall system packets are encountering losses, the AP spent significant
performance in the multicast (Section 4.1) and the uni- effort in re-transmitting these packets, while more im-
cast (Section 4.2) cases. We then look at contribution of portant I-packets waited behind. The lack of knowledge
various Medusa components to the overall performance about the value of different packets, prevented the AP
in Section 4.3. Specifically, we investigate benefits of from devoting an appropriate amount of re-transmission
rate adaptation in Section 4.3.1 and the performance ben- effort for more important packets. Medusa explicitly ad-
efits due to retransmissions in Section 4.3.2. dresses this problem and hence, led to improved perfor-
mance.
4.1 Overall performance (multicast)
We begin by evaluating the performance of the Medusa 4.1.1 Jitter variation of Medusa
system in terms of its scalability for multicast traffic sce- We present the results for Jitter(measured as IPDV) in
narios. We do so by — increasing number of clients and Figure 5. The experiment involved 10 users. Jitter in-
increasing video rates. creases with an increase in the number of clients, for
Scalability in the number of clients: We compare all the schemes. However, the jitter of Medusa is sig-
how different schemes can support HD video delivery nificantly lower than both BDCST and UCAST-SIMUL.
to a large number of co-located WiFi clients. Figure 3 The jitter of UCAST-SIMUL increases exponentially with
shows the performance of a highly loaded system with the number of clients. This can be attributed to the fact
25 clients (all receiving the same 20 Mbps video stream) that with increasing number of clients the amount of data
at medium loss locations. We find that Medusa performs necessary to be transmitted becomes more than the net-
close to UCAST-INDIV (difference of 3-4 dB with 25 work capacity. This results in a cascade of video packet
clients) with increasing client count, and is significantly drops in AP buffers and missing of deadlines. The jit-
superior to all other schemes. ter for BDCST also grows with the number of clients, as
Also, we find that there is a graceful degradation in the number of candidates who can loose packets has also
Medusa performance when the number of clients is in- increased. Also, we note that the slope of increasing jit-
 50 50 50

40 40 40
PSNR(dB)

PSNR(dB)

PSNR(dB)
30 30 30

20 20 20
UCAST_SIMUL UCAST_SIMUL UCAST_SIMUL
10 MEDUSA 10 MEDUSA 10 MEDUSA
BDCST BDCST BDCST
UCAST_INDIV UCAST_INDIV UCAST_INDIV
0 0 0
1 5 10 15 20 1 5 10 15 20 1 5 10 15 20
Video Rate(in Mbps) Video Rate(in Mbps) Video Rate(in Mbps)

(a) Good channel (b) Medium channel (c) Bad channel

Figure 4: Average PSNR for 10 clients averaged over 20 runs as a function of the video rate under varying channel
conditions.

Channel
200
UCAST_INDIV Cond. BDCST UCAST-INDIV Medusa
BDCST Good 1 10.12 1.04
Jitter(in msec)

150 MEDUSA Medium 1 10.26 1.1

UCAST_SIMUL
Bad 1 11.40 1.3
100
Table 2: Airtime occupied by different schemes normal-
50 ized to that of BDCST for 10 clients watching a 5 Mbps
video, averaged over 20 runs, under varying channel con-
0 ditions.
1 2 3 4 5 6 7 8 9 10
Number of Clients The above observation would seem to contradict with
the fact that Medusa uses a conservative rate-adaptation
Figure 5: Average jitter experienced by 10 clients under
mechanism which should significantly increase its net-
medium channel conditions for 20 runs.
work resource usage. However, we find that conservative
rate-adaption while increasing the relative time occupied
by individual packets also suffers less packet loss. Thus,
keeping the overall network utilization low. We present
ter for Medusa is lower than that of BDCST, signifying a further results in support of this statement in Section 4.3.
more gradual increase.
4.1.3 Interaction with other traffic
4.1.2 Induced network load We investigate the performance of Medusa in presence
Apart from providing video quality commensurate with of multiple uncorrelated traffic sources in Section 4.1.3.
each user’s channel quality, a good video multicast sys- Since we do not introduce any new end-to-end conges-
tem should induce minimal additional network load. We tion control mechanism in Medusa we do not present
compare the network load imparted by BDCST, UCAST- in depth results on the interaction of Medusa with TCP
INDIV and Medusa in Table 2. We calculate the addi- flows. In our experiments, introducing a Medusa flow
tional load placed in terms of the amount of airtime occu- without congestion control along with multiple TCP
pied by the packets (product of data-rate and packet size) flows results in Medusa flow forcing the TCP flows to
which were transmitted using the different schemes. The share only the residual bandwidth amongst themselves.
results are normalized by the amount of airtime taken by We plan to implement a congestion controlled version of
BDCST. Table 2 shows that Medusa has an overhead of Medusa as part of our future work. We depict the impact
4% for good channel conditions, which goes up to 30% of UDP flows on Medusa performance, in Figure 4.1.3.
under bad channel conditions. This overhead is to com- We vary the number of background UDP flows, each
pensate for the 1-5% of errors that occur in good channel at 4 Mbps, and compare the behavior of Medusa operat-
conditions. The channel induced losses go upto 15%- ing with a 10 Mbps video for 10 clients. The presence
25% when the channel conditions are bad in our settings, of multiple UDP streams causes a reduction in the qual-
forcing Medusa to inject an extra 30% traffic into the net- ity of video seen at the clients for all schemes. How-
work. Hence, Medusa does not place unecessarily high ever, Medusa outperforms UCAST-INDIV as the number
traffic load over the network. of background flows is increased (around 7dB better for
 50 tions in Section 4.3.1. The performance of network
coded retransmissions is evaluated in Section 4.3.2 and
40 the overall contribution of different components is sum-
marized in Section 4.3.3.
PSNR(dB)

30 4.3.1 Rate adaptation in Medusa

An important aspect of Medusa is its ability to adapt the
20
PHY rate based on channel conditions. We investigate
MEDUSA
UCAST_INDIV the performance of these mechanisms next.
10
MED-noORDER Impact of conservative base PHY rate adaptation: We
BDCST look at the effects of using a conservative rate adaptation
0
4 8 12 16 20 algorithm in Medusa on the overall system performance.
Background traffic(in Mbps) We conduct experiments with a 5 Mbps video rate to 10
clients in good, medium and bad channel conditions. We
Figure 6: Average PSNR for 10 clients averaged over ran Medusa with a conservative (err thresh = 0.02)
20 runs in presence of background UDP flows under and an aggressive (err thresh = 0.18) rate adaptation
medium channel conditions. Video rate is 10 Mbps. algorithm. Here, err thresh signifies the maximum ex-
pected error rate which we are willing to tolerate for
4 background flows). We find that these gains of Medusa any PHY rate. We also ran the experiment with UCAST-
are mainly due to our intelligent packet (re)-transmission INDIV. All the experiments we repeated for 20 runs. Fig-
ordering that mitigates the head-of-line blocking prob- ure 8(a, b) show the CDF of PHY rates assigned by dif-
lem in UCAST-INDIV. We show this explicitly by also ferent schemes under the good and the bad channel con-
introducing a new scheme, called Medusa-noORDER, ditions. We observe, Medusa-conservative assigns lower
in which the packet re-ordering mechanism of Medusa PHY rates to packets than unicast, while the aggressive
is disabled. The performance of Medusa-noORDER is algorithm assigns data rates higher than the conservative
quite similar to that of UCAST-INDIV. scheme, but lower than the unicast scheme. To highlight
the benefits of conservative rate adaptation, we plot the
4.2 Overall performance (unicast) number of extra bytes transmitted, as a fraction of over-
To evaluate the performance of Medusa in serving multi- all video size, and the PSNR of the resulting video under
ple unicast video streams, we have increased the num- different channel conditions when using conservative,
ber of video flows from one to four in increments of aggressive and unicast rate adaptation in Figure 8(c). For
one. We select the client randomly from a pool of 15 the UCAST-INDIV we plot the number of packets aver-
clients. Each experiment was run 20 times with a 5 Mbps aged by number of clients present. The following obser-
video stream. There were other uncorrelated background vations can be made from the plot,
flows (total of 5 Mbps) running during each experiment
• Under good channel conditions, an aggressive as
We plot the results of our observation in Figure 7. In
well as a conservative scheme would lead to similar
unicast traffic settings, the gains in Medusa arrive from number of packet losses(1%). Under such circum-
content-dependent rate selection, intelligent packet or-
stances, all three schemes offer similar video quality
dering and re-transmissions, as well as network coded and send similar amount of traffic over the network.
re-transmissions. The broadcast advantage is available From Figure 8(a), we find that around 80% (74%)of
only for these network-coded re-transmissions, and not
packets were transmitted at 24 Mbps or higher rate
for original packets. With unicast video destined to 4 in UCAST-INDIV(Medusa-aggressive), in contrast
clients, the aggregate load is 20 Mbps, which is quite
to only 30% form Medusa-conservative. Hence, us-
significant. Under good channel conditions, Medusa still
ing an aggressive rate adaptation would had been
delivers an average PSNR of 40 dB, which is very sim- beneficial in this case, as it would lead to network
ilar to UCAST-INDIV and is 9 dB greater than UCAST-
bandwidth conservation.
SIMUL. This gain is even larger (18 dB) under bad chan-
nel conditions. • For medium and bad loss environments, Medusa-
conservative sends around 20% and 10% packets
4.3 Micro-benchmarks of Medusa compo- at 24 Mbps or higher. UCAST-INDIV sends about
nents 40% and 11% packets at 24 Mbps of higher. In
We now evaluate the effect of individual design choices contrast, Medusa-aggressive sends about 60% and
on overall system performance. We look into perfor- 20% of its packets at 24 Mbps or higher. This is be-
mance of rate adaptation under diverse channel condi- cause of the slowness of the feedback process which
 50 50 50

40 40 40

PSNR(dB)

PSNR(dB)

PSNR(dB)
30 30 30

20 20 20

10 UCAST_INDIV 10 UCAST_INDIV 10 UCAST_INDIV

MEDUSA MEDUSA MEDUSA
UCAST_SIMUL UCAST_SIMUL UCAST_SIMUL
0 0 0
1 1.5 2 2.5 3 3.5 4 1 1.5 2 2.5 3 3.5 4 1 1.5 2 2.5 3 3.5 4
Number of streams Number of streams Number of streams

(a) Good channel (b) Medium channel (c) Bad channel

Figure 7: Overall performance of Medusa for unicast-only media traffic. Upto 4 clients shown, each requesting a
separate media stream with 5 Mbps video rate, under different channel conditions.

100 100 70
Medusa-conservative Medusa-conservative
90 Medusa-aggressive 90 60 Medusa-aggressive
80 UCAST-INDIV 80 UCAST
70 50 1.01 1.06 1.1 1.32
70 1.21
Percentile

Percentile

PSNR(dB)
1.01 1.01 1.17 1.22
60 40
60
50
50 30
40
40 30 20
30 20 Medusa-conservative
20 10 Medusa-aggressive 10
UCAST-INDIV
10 0 0
12 18 24 36 48 54 6 12 18 24 36 Good Medium Bad
Data Rate (in Mbps) Data Rate (in Mbps) Channel condition

(a) Good channel (b) Bad channel (c) Performance under various channel condi-
tions

Figure 8: CDF of packet rates assigned when transmitting 5 Mbps video to 10 clients in different channel conditions
using different rate adaptation mechanisms. The bars in plot (c) shows performance of the schemes in terms of PSNR.
The numbers in plot (c), on top of each bar, depict the normalized extra traffic in number of bytes sent by each scheme,
relative to BDCST.

makes the Medusa-aggressive algorithm slow to re-

act to changes in channel conditions. The perfor-
mance of the Medusa-aggressive scheme suffers be-
cause of its inability to adapt quickly as shown in
Figure 8(c). The number of packets transmitted by
the conservative algorithm is around 15% less than
Medusa-aggressive. This is expected, as the high
threshold value ensures that we would make very
few errors. The aggressive algorithm also leads to
Figure 9: Adaptation of different scheme with targeted
worse video quality(in PSNR) when the network re-
mobility, for video at 20 Mbps rate.
souces are scarce, precisely because of their inef-
ficient network resource usage. Worsening chan-
nel conditions makes the difference in video qual- low-loss location, while all the other clients stayed sta-
ity about 6-12 dB(Medusaconservative and UCAST- tionary at the low-loss location. The mobile client moved
INDIV have an advantage over Medusa-aggressive). from the low loss to the high loss location (across a wall)
quickly, stayed there for about 4 seconds, and returned.
Thus, except under good channel conditions, keeping a We show the adaptation performance of Medusa in com-
conservative rate leads to better network resource utiliza- parison to UCAST-INDIV and BDCST in Figure 9. The
tion, while the quality is maximized in all conditions by UCAST-INDIV scheme running its MAC-layer rate adap-
adopting a conservative rate adaptation. tation technique adapts the fastest. Medusa with its in-
Impact of mobility on rate adaptation: To study the ef- tent of making rate adaptation decisions (of its PHY base
fect of mobility and its impact of adaptation mechanisms, rate) slowly, adapts somewhat slower. It takes Medusa
we performed targeted mobility experiments, where we about 0.4 seconds to adapt to the change in channel con-
repeatedly moved one user between a high-loss and a dition for the mobile user. This occurs in both cases —
 % Network load reduction
when the user moves away from the low loss location, 16
14
18
16

% Coding opp.
and when it returns to the low loss location. This can be 12
10
14
12
10
attributed to the higher layer reception reports and slower 8
6
8
6
timescales in which they occur. However, once Medusa 4
2
4
2
adapts, it provides the user with the same performance as 0
1 2 3 4 5 6 7 8 9 10
0
1 2 3 4 5 6 7 8 9 10
the UCAST-INDIV in this case. The BDCST scheme has Number of Clients Number of Clients

no adaptation mechanism and does not adapt when the (a) Coding opportunities (b) Traffic savings
user moves.
Impact of interference on rate adaptation: We next Figure 11: Coding opportunities and percentage traf-
study the performance of these schemes under targeted fic reduction as a function of number of clients under
interference from an external 802.11 source, that was medium channel condition with 5 Mbps video averaged
a hidden terminal to the Medusa clients. Figure 10(a) over 20 runs.
shows the relative performance of Medusa, UCAST-
INDIV, and BDCST, when the video rate was 5 Mbps. Chnl. cond. Good Medium Bad
The interferer used UDP to download a large file starting % of coded packets 3.1 7.4 12.6
at time 2 seconds. The performance impact of this inter- % Airtime load
ference is similar to that of mobility. Medusa performed reduction 5 8 13
similar to UCAST-INDIV and much superior to BDCST.
However, it experienced a slight delay in adapting its rate Table 3: Coding opportunities and normalized traffic in-
when compared to UCAST-INDIV. jected as a function of channel condition for five clients
As shown in Figure 10(b), at a video rate of 20 Mbps, with 5 Mbps video averaged over 20 runs.
a similar effect happens with the hidden terminal inter-
ference. However, hidden terminal has a significantly
greater interference impact and at this high video rate, the tion due to the network coded scheme in Table 3. The
PSNR of both Medusa and UCAST-INDIV drops. Fur- table shows that worsening channel condition leads to
ther, at 20 Mbps and with hidden terminal interference, higher benefits from network coding. This is expected,
the performance of UCAST-INDIV falls slightly below as the number of packet losses increases as the channel
Medusa. Examining this performance of Medusa more condition becomes bad, this in turn leads to higher num-
closely, we see that at time 2.4 seconds, the inflate-deflate ber of retransmissions and thus more coding opportuni-
algorithm kicks in to help improve performance. The ties.
table in Figure 10(c) shows the number of I, P, and B We note that using network coding also leads in im-
frames that Medusa had to discard, inflate, deflate, and proving PSNR with increasing number of clients or
their channel occupancy time in the three phases (ini- worsening channel error conditions. We do not present
tial no interference, interference starts, and inflate-deflate the results for sake of brevity.
starts). 4.3.3 Component contribution
The Medusa system employs content aware rate
4.3.2 Network coded re-transmissions
adaptation, selective retransmissions and transmission
We evaluate the benefits of using network coded re- (re)ordering to provide quality enhancements over
transmissions with varying number of clients in the sys- broadcast based media delivery. Figure 12 shows the
tem (Figure 11). Panel (a) figure shows the percentage relative contribution of different design components in
of all packet transmissions in each case that were actu- Medusa, over and above standard WiFi broadcast. In the
ally network coded. As can be seen from the plot with low-loss and the high-loss environments various mecha-
increasing number of clients the number of network cod- nisms in Medusa (re-transmissions, rate adaptations, or-
ing opportunities increases. Also, we would like to note dering, rest – from integration of all the components).
that the computation overhead is never more than 1% of provides a nearly 9 and 10 dB improvement in PSNR
CPU time in any of our experiments. The actual perfor- over plain BDCST.
mance gains from network coding can be seen in Fig-
ure 11(b) which indicates the reduction in airtime load 5 Related Work
that occurred due to network coding opportunities. There has been a significant amount of research in the
Finally, we evaluate the benefits of network coded re- area of video streaming over wireless networks, both in
transmissions under varying channel conditions. We ex- video and systems community (see [29] for a summary).
periment with 5 clients receiving a 5 Mbps video under We comment on the most related pieces in this section.
good, medium, and bad channel conditions respectively. Dynamic transcoding is a standard technique for en-
We report the coding opportunities and the airtime reduc- hancing the quality of the streaming video. It involved
 (a) Video at 5 Mbps rate. (b) Video at 20 Mbps rate. (c) Video at 20 Mbps rate.

Figure 10: Adaptation of different schemes with external hidden terminal interference with video at 5 and 20 Mbps
rate. The table shows the number of I, P, and P frames that were discarded, inflated, deflated, and the channel occu-
pancy time for Medusa in the three phases.

focus on rate adaptation and re-transmission based tech-

niques for WiFi broadcasts in video delivery systems.
Rest
In general wide-area network settings, the OxygenTV
Order
Rate project [15,16] has considered performing selective end-
Retx. to-end re-transmissions of packets based on the video
frame type, focusing more on unicast video delivery.
They propose the SR-RTP protocol for the such selec-
BDCST
tive retransmissions [16]. In contrast, our work explores
various wireless link adaptation mechanisms that lever-
Channel Condition
age packet content information.
In [31], authors present a measurement study different
Figure 12: Performance breakdown between rate adap-
application-layer video streaming mechanisms in multi-
tation and retransmission components of Medusa system
hop wireless context. They do not explore interactions
for 10 clients averaged over 10 runs under varying chan-
between the value of content to applications, and link
nel conditions.
adaptation mechanisms as we do in this work. In [27],
authors present mechanisms to improve the quality of the
estimating the bandwidth available in the medium and video while operating in a lossy wireless environment.
then change the video rate itself to ensure the best qual- However they focus on low bit-rate video streams, while
ity video that the channel can support is delivered to the our solutions are stylized to deliver HD quality video in
receivers. Chou et.al. [9, 11, 12] in their seminal work WiFi environments.
propose a rate-distortion optimization technique to adjust The authors of [28] present an end-to-end video rate
the rate of the transmitted video based on channel qual- control protocol for mobile media streaming on Internet
ity. However, this body of work depends on the wire- paths involving wireless links. They implement the con-
less hardware to pick the rate at which the video is to trol functionalities in the receiver, which is charged with
be transmitted. A second set of prior work dealing with proving feedback to the server. The video server uses this
identifying the optimal video rate as well as the amount information to change the video codecs used to match
of redundancy to be added to the video stream is repre- the available capacity of the end to end path. The pro-
sented by the [25, 26]. The authors formulate a complex posed approach is complementary to ours, as we focus
optimization problem for the same and provide heuris- on adapting video delivery on the WiFi link, by making
tic algorithms which show the performance benefits of link adaptation decisions for WiFi transmitters.
the designed algorithms. Such FEC based mechanisms A recent mechanism, SoftCast [17], uses the notion of
are orthogonal to the set of techniques used in our work. compressed sensing to create equal priority video pack-
In Medusa we mostly leverage understanding from such ets. This allows users to extract information proportional
prior work, and tailor our solutions to the needs of WiFi- with their own channel quality. The core of this work fo-
based media delivery and specific issues therein. cuses on the complementary aspect of compressed sens-
Authors in [19] use a scalable video codec and opti- ing. Furthermore, SoftCast also requires changes to the
mally determine the amount of FEC required. This is wireless radio hardware (and the PHY layer), while our
a representative of a large body of literature in the area. system makes no changes to the current 802.11 stan-
This approach is, however, complementary to ours, as we dards.
 Finally, DirCast [10] also design and implement a CNS-0855201, CNS-0751127, CNS-0627589, CNS-
system for WiFi multicast. They advocate the use of 0627102, and CNS-0747177.
pseudo-broadcasts in their system. However, the main
difference between our Medusa approach and DirCast References
[1] Evalvid - a video quality evaluation tool-set. www.tkn.
is that we propose a content-dependent PHY rate selec- tu-berlin.de/research/evalvid/.
tion, re-transmissions, and packet order selection. This [2] Ffmpeg - digital audio converter. www.ffmpeg.org/.
[3] Mpeg-2 hd test patterns. www.w6rz.net/.
is an issue that is not considered by DirCast. DirCast [4] Mpeg-4, moving picture experts group-4 standard.
focuses on some complementary problems for the multi- www.chiariglione.org/mpeg/standards/mpeg-4/
mpeg-4.htm.
cast case only (e.g., intelligent client-AP association de- [5] Mplayer - the movie player. www.mplayerhq.hu.
cisions, FECs, etc.), and is agnostic of value of packets [6] Streambox. www.streambox.com/products/hd/hd\
9200\ main.html.
to applications. [7] Vlc media player. www.videolan.org/vlc/.
We believe that the main contribution of Medusa is in [8] B ICKET, J. Bit-rate selection in wireless networks. MIT Master’s
Thesis, 2005.
combining some understanding of packet contents with [9] C HAKARESKI, J., AND C HOU , P. A. Radio edge: rate-
various WiFi link layer functions to improve the qual- distortion optimized proxy-driven streaming from the network
edge. IEEE/ACM Transactions on Networking (2006).
ity of media delivery. WiFi link layer decisions, until [10] C HANDRA , R., K ARANTH , S., M OSCIBRODA , T., N AVDA , V.,
now, have been considered in a mostly content-agnostic PADHYE , J., R AMJEE , R., AND R AVINDRANATH , L. Dircast:
A practical and efficient wi-fi multicast system. ICNP 2009.
manner. Medusa suggests an interesting design point for [11] C HOU , P., AND M IAO , Z. Rate-distortion optimized streaming
of packetized media. IEEE Transactions on Multimedia (2006).
combining application-layer information in making de- [12] C HOU , P., M OHR , A., WANG , A., AND M EHROTRA , S. Fec
cisions at the link layer. and pseudo-arq for receiver-driven layered multicast of audio and
video. Proceeding of Data Compression Conference (2000).
Various other new techniques can be brought to im- [13] D AVID , S. A guide to data compression methods, 2002.
prove performance of Medusa even further. In the future [14] D EMICHELIS , C., AND C HIMENTO , P. Ip packet delay variation
metric for ip performance metrics (ippm). RFC 3393, IETF.
we therefore plan to investigate the use of other com- [15] F EAMSTER , N. Adaptive delivery of real-time streaming video.
plementary but related mechanisms, such as application MIT M.Eng. Thesis, 2001.
[16] F EAMSTER , N., AND BALAKRISHNAN, H. Packet loss recovery
layer FEC for proactive error recovery, and a congestion for streaming video. 12th International Packet Video Workshop,
control mechanism for co-existence with TCP flows. 2002.
[17] JAKUBCZAK , S., R ABUL , H., AND K ATABI , D. Softcast: One
video to serve all wireless receivers. MIT-CSAIL-TR-2009-005,
6 Conclusions 2009.
[18] K ATTI , S., R AHUL , H., H U , W., K ATABI , D., M ÉDARD , M.,
Media delivery over wireless systems is a growing area AND C ROWCROFT, J. Xors in the air: practical wireless network
of importance. We present the design and implementa- coding. IEEE/ACM Transaction Networking.
[19] M AJUMDAR , A., S ACHS , D., KOZINTSEV, I., R AMCHAN -
tion of the Medusa system which allows efficient deliv- DRAN , K., AND Y EUNG , M. Multicast and unicast real-time
ery of high quality media to one or more WiFi clients. video streaming over wireless lans. IEEE Transactions on Cir-
cuits and Systems for Video Technology, (2002).
The key contribution of this work is in recognizing that [20] M ARTINEZ -R ACH , M., AND ET. AL . Quality assessment met-
certain link layer functions, e.g., re-transmissions, PHY rics vs. PSNR under packet loss scenarios in MANET wireless
networks.
rate selection, packet transmission order, can be imple- [21] M URTY, R., W OLMAN , A., PADHYE , J., AND W ELSH , M. An
mented better by having some knowledge about the value architecture for extensible wireless lans. HOTNETS-VII (2008).
[22] O RLOV, Z. Network-driven adaptive video streaming in wireless
of packets to applications. In order to be minimally inva- environments. PIMRC (2008).
sive to existing systems, we implement this function in [23] ROZNER , E., I YER , A. P., M EHTA , Y., Q IU , L., AND JAFRY,
M. ER: efficient retransmission scheme for wireless lans.
a proxy. Our results indicate that our collection of tech- [24] S CHULZRINNE , H., C ASNER , S., F REDERICK , R., AND JA -
niques can facilitate HD video delivery of 20 Mbps to 25 COBSON , V. RTP: A transport protocol for real-time applications.
RFC 3350, IETF.
clients while maintaining a good viewing quality. [25] S EFEROGLU , H., A LTUNBASAK , Y., G URBUZ , O., AND
E RCETIN , O. Rate distortion optimized joint arq-fec scheme for
real-time wireless multimedia.
7 Acknowledgements [26] S EFEROGLU , H., G URBUZ , O., E RCETIN , O., AND A LTUN -
BASAK , Y. Rate-distortion based real-time wireless video
We thank Sanjeev Mehrotra for initial discussions on streaming. Image Communications (2007).
the state-of-art in media streaming. We acknowledge [27] TAN , K., R IBIER , R., AND L IOU , S.-P. Content-sensitive video
Sateesh Addepalli for his comments and suggestions on streaming over low bitrate and lossy wireless network.
[28] TAN , K., Z HANG , Q., AND Z HU , W. An end-to-end rate control
our evaluation plan that helped improve the quality of protocol for multimedia streaming in wired-cum-wireless envi-
this paper. We also acknowledge Sriram Subramanian ronments. ISCAS ’03..
[29] WANG , Y., AND Z HU , Q.-F. Error control and concealment for
for co-developing a preliminary version of this system video communication: a review. Proceedings of the IEEE (1998).
from which we learned a number of important lessons. [30] W ONG , S. H. Y., YANG , H., L U , S., AND B HARGHAVAN , V.
Robust rate adaptation for 802.11 wireless networks.
Finally, we thank our shepherd Srinivasan Seshan and [31] X IAOLIN , C., P RASANT, M., S UNG -J U , L., AND S UJATA , B.
other anonymous reviewers whose feedback helped bring Performance evaluation of video streaming in multihop wireless
mesh networks.
the paper to its final form.
Sayandeep Sen and Suman Banerjee were supported
in part by the US NSF through awards CNS-0916955,