also take QoS-awareness into account when constructing
overlay in which NICE and Zigzag are tree-based, and
mOverlay, Narada, and Bullet are mesh-based. Although
these works are not proposed specially for layered
streaming, their key ideas are still useful to overlay
construction for layered streaming.
For the data scheduling part, so far some valuable works
have been proposed. LION [8] utilizes alternative paths and
network coding to improve throughput. PALS [1] adopts a
diagonal buffer distribution and employs Round-R obin
method to request data from partners. It also distinguishes
long-term and short-term bandwidth variations to avoid
overreaction to bandwidth fluctuation. Cui and Nahrstedt
[9] study the on-demand media distribution problem and
proposed a peer-to-peer streaming solution in which how to
allocates the desired layers among multiple senders were
addressed. Shi et al. [10] address the broadcast of on-
demand video too in which the delivery of layered encoded
file is part of their work, mainly investigating how the clients
adjust subscription layers according to the bandwidth with
the server, so as to achieve adaptation video quality. Some
other works address the application of layered video in
specific environment, such as TrustStream [19] and [20].
In short, these works make effort to maximize the system
throughput, deliver satisfying video layers according to the
available bandwidth, or apply layered video in particular
scenario, whereas the distinct characteristics caused by
layered encoding have not been fully and systematically
addressed . Therefore, we propose the fou r scheduling
objectives and the LayerP2P mechanism in this paper to
address the optimal data scheduling for layered streaming.
3LAYERP2P: MODEL,STRATEGY, AND
DISCUSSION
At the very beginning, we first present the core idea of
LayerP2P: to maximize the throughput, the blocks far from
their playback time need to be fetched as many as possible,
in an optimal order based on the importance of data block.
To ensure high layer delivery ratio and low useless packets
ratio, proper layers should be subscribed when the blocks
are close to their playback time. Besides, sudden bandwidth
drop may induce the absence of blocks in subscribed layers;
to combat this, there should be a remedy mechanism to
request the minor missing blocks with most urgent play-
back time. In short, different scheduling goal should be
accomplished at different time based on the data blocks’
playback deadline.
To address such unique requirement in layered stream-
ing, we model the data scheduling scheme as a three-stage
problem according to the data blocks’ playback time, and
then, design corresponding strategies for each stage to
achieve its scheduling goal. We also make some analysis to
why our LayerP2P method can perform better than existing
schemes in this section.
3.1 Three-Stage Model
In typical P2P streaming scenario, each node has buffering
windows containing the blocks it is interested in. And they
periodically declare to the neighbors on the blocks avail-
ability in their buffering windows, and request the absent
blocks from neighbors according to their declarations (see
Fig. 1). With layered coding introduced, the video stream is
encoded i nto several layers, e ach of which is then
partitioned into blocks. Thus, each block has a layer ID
(LID) and a block ID (BID). The right bound of the buffering
widows is the maximum block ID owned by the node. And
the leftmost part contains the blocks that have just been
played or will be played soon; thus, these blocks are read-
only. Periodically, the buffering windows slide forward by
a window’s length (see Fig. 2).
Our scheduling model mainly concerns with the win-
dows on the right side of the read-only buffer, and
according to the their playback time, these windows are
divided into three stages: the remedy stage, which contains
the blocks with smallest BIDs, i.e., the most urgent playback
time; the free stage, which contains the blocks with the
largest BIDs, i.e., the latest playback time; and the medium
stage is called decision stage. When the blocks enter the
buffering windows, they first enter the free stage. With the
periodical sliding forward of the buffering windows, they
will arrive at the decision stage, and finally, reach the
remedy stage. In each period, the node needs to allocate
band width to request the absent data in every stage
properly, which is addressed in the following sections.
3.2 The Remedy Stage
The blocks in the remedy stage have higher priorities than
those in the decision and free stage, for they’re the closest to
the playback time. Therefore, the available bandwidth is
first allocated to request the minor absent blocks in this
stage. The remedy mechanism is simple: suppose the
remedy stage is of k-windows length, and the number of
missing blocks within the subscribed layers in the window
that newly enters remedy stage from decision stage is n;
XIAO ET AL.: TOWARD SYSTEMATICAL DATA SCHEDULING FOR LAYERED STREAMING IN PEER-TO-PEER NETWORKS: CAN WE GO... 687
Fig. 1. The partial view of the layered streaming overlay. N
i
denotes the
participating nodes and the blocks indicate their buffered data.
Fig. 2. The buffering windows in each node and the three-stage model.
The numbers marked in the figure are the subscribed layers in each
window.