30-07-2013, 02:41 PM
Multi-Path Routing and Rate Allocation for Multi-Source Video On-Demand Streaming in Wireless Mesh Networks
Multi-Path Routing and Rate.pdf (Size: 553.21 KB / Downloads: 25)
Abstract
We study the multi-source video on-demand ap-
plication in multi-channel multi-radio wireless mesh networks.
When a user initiates a new video request, the application can
stream the video not only from the media servers, but also from
the peers that have buffered the video. The multi-path multi-
source video on-demand streaming has been applied in wired
networks with great success. However, it remains a challenging
task in wireless networks due to wireless interference. In this
paper, we first focus on the problem of finding the maximum
number of high-quality and independent paths from the user to
the servers or peers for each V oD request by considering the
effect of wireless interference. We formulate it as a constrained
maximum independent paths problem, and propose two efficient
heuristic path discovery algorithms. Based on the multiple paths
discovered, we further propose a joint routing and rate allocation
algorithm, which minimizes the network congestion caused by the
new V oD session. The algorithm is aware of the optimization
for both existing and potential V oD sessions in the wireless
mesh network. We evaluate our algorithms with real video
traces. Simulation results demonstrate that our algorithm not
only improves the average video streaming performance over all
the coexisting V oD sessions in the network, but also increases the
network’s capacity of satisfying more subsequent V oD requests.
INTRODUCTION
The video on-demand application (V oD) has become a pop-
ular Internet service recently. There have already been several
commercial products developed to support V oD applications,
such as PPLive and PPStream. Most of them use peer-to-peer
(P 2P ) technology to improve the V oD performance. Such
architecture has been discussed in [1] [2]. Assume users can
store the videos that they have recently watched in their local
storage (e.g., PPLive and PPStream buffers 1G bytes of the
most recently watched videos, which is enough for over two
2-hour movies, in a peer’s local storage). When a client wants
to watch a new video, he or she first discovers which peer
clients have buffered the video, and then streams the video
from both the servers and peer clients through multiple paths.
The multi-path multi-source video on-demand streaming has
been applied in wired networks with great success. However,
it remains a challenging task in wireless networks due to the
effect of wireless interference.
Multi-Source VoD in WMN
Consider the V oD application in a large community net-
work constructed by wireless mesh networking technology.
The network is composed of a number of multi-channel multi-
interface wireless mesh routers. Each mesh router can establish
wireless connectivity with neighboring mesh routers, so that a
static multi-hop wireless network is formed. There are some
special mesh routers working as gateways, which are directly
connected to the Internet. Previous static channel allocation
algorithms, such as [18] [19], can be used to assign each
interface of each router with a channel so as to minimize the
network interference while maintaining the network connec-
tivity.
Iterative Path Discovery
The Iterative Path Discovery algorithm (IP D) finds paths
one by one from the senders to the receiver. In each iteration,
we find one path from a sender to the receiver, and then update
the topology accordingly. This process continues until no new
paths can be found from the remaining topology. There are two
critical steps in the algorithm, which we will explain below.
1) Path Selection: Let S be the set of senders and T be the
initial topology. Let S ′ be the set of remaining senders, for
which we have not found paths yet, and T ′ be the remaining
topology. Initially, S ′ = S and T ′ = T . In this step, for each
s ∈ S ′ , we first find a minimum W CET T path p from s to
r in T ′ if such a path exists and W CET T (p) ≤ γ ⋅ w T (s, r),
where w T (s, r) is the W CET T value of the optimal path
from s to r in T and γ is a constant to control the quality
of each path (we set γ = 1.5 in our experiment).
Discussion
If we want to find strictly edge-disjoint paths, the number
of paths that can be found will be limited by the number of
interfaces that the receiver has. In order to find more paths to
enhance the robustness of the application and provide more
flexibility for rate allocation, we can relax this constraint by
allowing paths to merge at the last hop towards the receiver.
Both the iterative and parallel path discovery algorithms can
be easily modified to deal with this case. When taking off a
selected path from the remaining topology, we do not remove
the edge that is directly connected with the receiver. It will be
taken off from the remaining topology only when its l value
is over the threshold α. In this way, we have still guaranteed
the path independency constraint on the last hop.
JOINT ROUTING AND R ATE A LLOCATION
As the wireless mesh network is designed to be shared
among multiple users, the routing and rate allocation for each
V oD request should not only consider the performance of
itself, but also take into account the existing V oD sessions
and the network’s ability of satisfying more subsequent V oD
requests. Note that the performance of each existing V oD
session is dramatically affected by the traffic load on each
link used by the session. If the traffic load on a link is high,
the application may experience high queuing delay and jitter
due to the congestion on this link. In addition, the increase
in the number of congested links may disrupt the network’s
connectivity, thereby causing the network to be incapable of
finding routes with required bandwidth for new V oD requests.
Therefore, we take our optimization goal as minimizing the
network congestion.
CONCLUSION
In this paper, we first proposed two heuristic multipath
discovery algorithms, IP D and P P D, to find multiple inde-
pendent paths from senders to the receiver for each V oD re-
quest. The proposed algorithms consider wireless interference
in the multipath discovery, so it is able to balance the video
streaming traffic both spatially and on different channels in
the network. Based on the multipath discovery algorithms, we
then proposed a joint routing and rate allocation algorithm to
find the routes and rate allocation with the goal of minimizing
the network congestion. We performed simulations in N S2
using real video traces, and evaluated the performance of our
algorithms using both network layer metrics and application
layer metrics for video streaming. Simulation results have
shown that IP D and P P D not only increase the maximum
number of concurrent V oD sessions that can be supported in
the network, but also improve the video streaming quality of
each session, compared to previous work. Moreover, P P D
achieves better video streaming performance than IP D, be-
cause it is able to discover more paths than IP D under the
same constraint.