Per formance Evaluation for Multicasting Video over OpenFlow-based Small-scale Network

Journal of Korea Multimedia Society.
2014.
Aug,
17(9):
1084-1091

- Received : March 10, 2014
- Accepted : July 22, 2014
- Published : August 28, 2014

Download

PDF

e-PUB

PubReader

PPT

Export by style

Share

Article

Metrics

Cited by

TagCloud

When demand for transmitting multimedia data increases, network congestion is more likely to occur and users will suffer high loss rate as well as high delay. In order to enhance quality-of-service (QoS) of video multicasting, we need to raise transmission reliability and reduce end-to-end delay. This paper proposes a routing mechanism for a OpenFlow-based small-scale network in order to multicast video reliably with low delay. In our method, multipath routing will be applied to Multiple Description (MD) Coded video to exploit its multi-description property. Through performance evaluation, our method shows improvement on loss rate, delay and video distortion.
OpenFlow-based network for video multicast.
r
transmits data with distortion
D
(
r
).
r
* denotes one of two optimal paths. The problem can be stated as finding
subject to
where
E
is link set;
R
is path set;
v
and
u
are nodes;
l
(
u
,
v
) = 1 if the link (
u
,
v
) is on path
r
; similarly,
l
(
v
,
u
) = 1 if the link (
v
,
u
) is on path
r
. First constraint guarantees that play-back delay rerequirement is met, i.e, expected end-to-end delay
t_{e}
(
r
) must be less than or equal to play-back deadline
Δ
. The value of
Δ
is estimated as in
[8]
. Second constraint guarantees that every path
r
is formed by connected links and each path connects source node
s
and destination node
d
.
This paper proposes a model for the encoding mode that generates two descriptions. Routing algorithm will find two paths for two descriptions.
As in
[4]
, distortion D of each pair of paths (
r
_{1}
,
r
_{2}
) is
D
_{1,1}
is distortion of a pixel when its data from two descriptions are lost.
D
_{0,0}
is is central distortion when non of descriptions is loss;
D
_{1,0}
,
D
_{0,1}
are side distortions obtained when first description, second description is lost, respectively. Similarly,
p
_{0,0}
,
p
_{1,0}
,
p
_{0,1}
,
p
_{1,1}
are probabilities with which non of descriptions is loss, first description is lost, second description is lost, both description are lost, respectively.
In order to estimate distortion, we use ROPE as in
[9]
and make formulation as in
[4]
.
p_{i,j}
in (2) is calculated as
where
Equations (3) and (4) are described as follows. First, in order for both packets to arrive at destination without loss (
p
_{0,0}
), we need all following conditions:
Second, when there is only second packet arrives at client (
p
_{1,0}
), we expect that loss occurs at joint part, first disjoint part or first packet arrives late with probabilities
p
_{A1}
,
p
_{B1}
,
p
_{C1}
, respectively. In this case, there are three possibilities as follows.
Probability
p
_{0,1}
of event when first packet arrived at destination successfully and second packet gets lost is obtained from
p
_{A2}
,
p
_{B2}
,
p
_{C2}
by the same way with obtaining
p
_{1,0}
.
p
_{1,1}
is probability when both packets are lost.
Packet loss in wired connection mainly comes from drop due to congestion. In this two-state Gilbert-Elliott model, we use up-state and down-state to denote the good and bad condition of the joint part. Loss rate on disjoint parts is formulated by multiplication law of probability.
After collecting burst length and packet loss rate from forwarders, controller is able to estimate
p_{up}
,
p_{down}
of joint part and
p_{int1}
,
p_{int2}
of disjoint parts as in
[5]
.
Queuing is the main cause of delay in our network. In order to measure delay, Discrete Time Markov Chain (DTMC) (
Fig. 2
) is adopted and applied to queuing process at all nodes
[10]
. At each node’s queue, we examine the number of packets of the description that we want to estimate delay. This number changes over time and forms the states of a Markov chain. This chain is {X} and its state set is Z{
Z_{nz}
,
Z_{nz}
_{-1}
, …,
Z_{z}
, …,
Z
_{0}
}, where
n_{Z}
is queue size. We estimate the waiting time of a packet in node's queue in order to model queuing delay. {Y} is an absorbing Markov chain derived from {X} by ignoring all arrival after the considered packet arrives.
DTMC in a node.
Our formulation is based on
[10]
. However, for video multicast in wired links, we do not consider retransmission mechanism. Therefore, each time unit, a node always transmits a packet successfully.
P_{Z}
is probability that {X} stays at the same state between two time units. In our model,
P_{Z}
is probability with which the node is serving another packet rather than a packet of examined description.
From modelled DTMC, we have probability that
i
-th description is transmitted on-time by path
r
. This probability is
p_{onti}
and it is calculated as
where
f
_{e(r)}
(
k
) is probability that end-to-end delay on path
r
equals to
k
time unit(s)
T
.
Now,
p_{onti}
in (5) is put into (3) and (4) to fully derive (2).
t
_{(i,1)}
that {X} transits from state
Z_{i}
to state 1 is calculated as shown below
where
P
_{X(i,j)}
is element (
i
,
j
) in transition probability matrix of chain {X}.
Based on
t
_{(i,1)}
, we can estimate delay on link (
u
,
v
). This delay is queuing delay
t
(
u
,
v
) of node
v
. It is given as
where
t
_{(v)(i,1)}
is amount of time for
v
-th node to transit from state
Z_{i}
to state
Z
_{1}
,
∏
_{X(v)(i)}
is
i
-th element in steady-state probability matrix
∏_{X}
of chain {X} of
v
-th node.
Finally, we can estimate end-to-end delay
t_{e}
(
r
) based on (6).
t_{e}
(
r
) is the sum of queuing delay
t
_{(u,v)}
at all nodes in path
r
. It is given as
where
n_{V}
is number of nodes in the network.
Then Lagrangian relaxation dual has following form
The relaxed form (7) is a routing problem. We can use objective function to estimate routing cost, we can solve this problem by using a basic routing algorithm (e.g., Dijkstra's algorithm). An idea to deal with discrete optimization problems is exploiting its structure in order to speed up the search for the solution. We exploit Dijkstra's Shortest Path Algorithm to find routing solutions for the Lagrangian relaxation dual. The idea of Dijkstra's algorithm is spreading out from the source node until destination node is met. When the graph of network is represented by a tree rooted at source node, our algorithm runs along the branches on tree from the root.
Conventional Dijkstra's algorithm will run from source node and gradually add more nodes to a set of selected nodes. For each iteration, it examines all unselected nodes that directly link to at least one of its selected nodes. The set of those examined nodes is called candidate set. From that candidate set, the algorithm selects the best node with least cost from the source node. Our modifi ed algorithm goes through the same processes with Dijkstra’s algorithm but it will select a pair of nodes when it starts at the source node. After that, at each iteration, the algorithm selects only one best node based on cost (i.e., distortion). In order to estimate cost, (7) requires two paths. That why the algorithm picks up two nodes at first. After that, with each candidate node, the algorithm adds up previous selected node to form a pair of paths.
Information of video sequences
Our method is compared with a method which uses Dijkstra’s Shortest Path algorithm (DSP). That method mixes all kinds of traffic and performs single path routing. Our method combines routing algorithm (RA) and optimization methodologies (OM), so that it is named RAOM. The evaluating metrics are received data, end-to-end delay and PSNR. The results show below are collected at one of the clients.
In order to evaluate loss rate, we set up a scenario in which RAOM and DSP transmit
Container
sequence. For each method, we stream all 12 seconds of the sequence one time. Cumulative received data is collected at destination node. Our method sets constraint on end-to-end delay. However, in objective of distortion, packet loss is taken into consideration. This explains that our method yield less loss than DSP. In
Fig. 3
, we add the solid line to show play-back rate. According to
Fig. 3
, our method achieves higher data rate than DSP. DSP takes 3 seconds to reach play-back rate while RAOM does not. This means DSP will encounter initial delay longer than RAOM. On average, RAOM achieves 4.5 kbytes/s higher than DSP.
Received data of Container sequence.
In order to measure end-to-end delay, we run a scenario for
Foreman
sequence. Results is shown in
Fig. 4
. When the load of forwarders raises, the queuing delay will suffer. At first, RAOM produces relatively high delay. This can be explained that computing complexity requires processing time. In this way, after controller successfully solves the problem, delay gradually drops. Overall, our method gains lower delay than DSP.
End-to-end delay of Foreman sequence.
In order to compare PSNR, we run scenarios of
Foreman
sequence. We calculate PSNR based on YUV files. However, we only show PSNR of Y component because it is the most widely-used component for PSNR. Additionally, this is perframe PSNR, i.e., it is calculated for each frame.
Fig. 5
plots PSNR of 63 of total 400 frames in
Foreman
sequence. The graph shows that our method achieves higher PSNR than DSP. Moreover, RAOM appears to have highly dynamic routing mechanism when its PSNR fluctuates greatly in comparison with DSP.
PSNR of Foreman sequence.
Thuyen Minh Thi
received his B.S. Degree in Computer Science from Vietnam National University, Ho Chi Minh city, Vietnam, in 2011. He received his M.Eng. degree in Information and Communication from Inje University, Gimhae, Republic of Korea, in 2014. His research interests are OpenFlow and network optimization.
Thong Huynh
received his bachelor’s degree in Electronics and Telecommunication at Excellent Engineering Training Program, Ho Chi Minh University of Technology, Vietnam in 2010 and M.E. from Department of Infomation and Communications Engineering, Inje University, Korea. He is currently PhD candidate in the same department. His research interests are wireless scheduling and energy efficiency in wireless sensor networks.
In-Yeup Kong
received her B.S. degree, M.S. degree and Ph.D Degree from Pusan National University, Pusan, Republic of Korea, in 2000, 2002, and 2007. Since September 2008, she has been an associate professor at Kumoh National Institute of Technology, Gumi, Republic of Korea. Her research interests are in next-generation internet, and embedded systems.
Won-Joo Hwang
received his Ph.D Degree in Information Systems Engineering from Osaka University Japan in 2002. He received his B.S. and M.S. degree in Computer Engineering from Pusan National University, Pusan, Republic of Korea, in 1998 and 2000. Since September 2002, he has been an associate professor at Inje University, Gyeongnam, Republic of Korea. His research interests are in network optimization and cross layer design. Mr. Hwang is a member of the IEICE and IEEE.

Video Multicast
;
OpenFlow
;
Multiple Description Coded Video
;
Multipath Routing
;
Optimization of Routing

1. INTRODUCTION

With the development of demand for multimedia services, network load grows quickly. When congestion occurs, QoS of video multicast will drop because of high packet loss rate and delay. Packets become useless when they reach destination late. Therefore, both packet loss and delay lead to high level of video distortion. In order to deal with this problem, this paper proposes a solution that allows multicast video with low delay and low distortion. Current advanced architectures and technologies (e.g., IntServ, Diffserv, Multiple protocol label switching (MPLS)) attempt to solve such QoS problem. However, they are built on top of distributed hop-by-hop routing architecture. Without information of state and resource of the whole network, it is hard to gain efficiency of routing.
OpenFlow can define flows by various ways. This allows us to classify traffic type and define the flow that we want to support QoS enhancement. Our algorithm is run at OpenFlow controller. It keeps up-to-date information of the network state, so it is able to perform QoS routing efficiently.
In this paper, we propose a routing mechanism in order to multicast video in OpenFlow-based network with low packet loss rate and delay. However, due to the centralized architecture of OpenFlow, we aim to apply our method to a small-scale network to maintain low overhead and high stability. For a video source, there are many unicast flows; each of them is between the server and a client. For each flow, we consider a routing problem in order to find optimal transmitting paths. These paths aim at boosting reliability and reducing delay. In the network, flows of traffic are classified at OpenFlow-enabled forwarders. Video flows are transmitted among forwarders using MD coding. In MD, video stream is encoded into several independent descriptions (i.e., substreams). The controller monitors network states and applies routing mechanism to these descriptions. Our multipath routing algorithm is used for transmitting MD coded video to destination nodes. For each of these nodes, we provides different descriptions with different paths. In this way, we exploit multi-descriptions property of MD. Our routing objective is to find optimal paths in order to minimize video distortion at each destination node while delay is kept below play-back deadline.
Our model can be used in various applications. For instance, it can be applied to a small-scale network, e.g., a regional part of a network operator's backbone. It will enable video service providers to multicast data with low loss rate and delay.
The summary of our contributions in this paper is expressed as follows:
- • We propose a method to multicast video in OpenFlow-based network with low loss rate and delay. Our method performs multipath routing for each connections (Section III).
- • We formulate an optimization problem for routing MD coded video (Section IV). Additionally, we use optimization methodologies to solve the modelled multipath routing problem (Section V).

2. RELATED WORKS

Video transmission in general and video multicast in particular have found a number of applications. We describe here some previous works relating to them.
In
[1]
, the authors proposed a routing protocol for multicast. They used single path to transmit data from sender to each receiver. The single path was based on hop count. In this way, if the capacity of the shortest path did not meet the QoS requirement, the method could not provide a path with high QoS. In
[2]
, the authors dealt with building shared multicast tree. They used multipath routing and proposed spanning-joins protocol. When a new node wanted to join multicast tree, it broadcasted request messages to its neighborhood. Therefore, this process may face the problem of overhead.
In
[3]
, the authors dealt with video transmission problem. They used metric distortion but the objective function was Lagrangian cost function. It was not in close form as ours. Moreover, objective function did not consider packet loss due to missing play-back deadline. Similarly, Mao et al.
[4]
used distortion-rate function to estimate distortion based on data bit rate. Besides, they did not take play-back deadline into consideration. In
[5]
, the authors streamed MD video over overlay networks. Distortion was estimated by a function of source rate. They had this approximate function by experiment. In
[6]
, differential multicast routing was considered, however, it was for DWDM networks. Therefore, it is not suitable for our target networks.
In our method, centralized control mechanism of OpenFlow is employed so that we do not have problem of overhead. We derive distortion based on delay, traffic load, packet loss and play-back deadline. With distortion, we have a metric that is closer to user’s perception than metrics in
[7]
. We use this metric to estimate the performance of multicast paths. Besides propose a mechanism, we build a mathematical model as well as provide its formulation. Furthermore, we propose a multipath routing algorithm in order to benefit from multi-description property of MD coding.
3. SYSTEM MODEL

- 3.1 Network description

In our network (
Fig. 1
), data will travel from the server, through OpenFlow-based network, then arrive at the clients. For each forwarder, we consider two types of traffic: traffic of video flows and traffic of non-video flows. Each video flow is routed on two paths from the server to its client. Non-video flows are routed by default routing methods. This OpenFlow-based network is denoted as a directed graph.
PPT Slide

Lager Image

- 3.2 Problem

For each server-client pair of multicast transmission, we form a routing problem to find its two optimal paths. Path
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

4. PROBLEM FORMULATION

- 4.1 Derivation of packet loss rate pi,j

Two causes responsible for packet loss are bad link state and play-back deadline missing.
Without loss of generality, we denote two optimal paths with joint part and disjoint parts. We use Gilbert-Elliott model to formulate loss rate on joint part. Loss rate on disjoint parts is formulated by multiplication law of probability.
PPT Slide

Lager Image

PPT Slide

Lager Image

- • joint part is in good condition (with probabilitypup),
- •i-th packet passes thei-th disjoint part intact (pinti) and also arrives at its destination on-time (ponti).

- • joint part is in bad condition (pdown),
- • second packet passes second disjoint part intact (pint2) and also arrives at its destination on-time (pont2),
- or
- • joint part is in good condition (pup),
- • first packet is lost at first disjoint part (1 -pint1),
- • second packet passes second disjoint part intact (pint2) and also arrives at its destination on-time (pont2),
- or
- • joint part is in good condition (pup),
- • first packet passes first disjoint part intact (pint1) but not on-time (1 -pont1),
- • second packet passes second disjoint part intact (pint2) and also arrives at its destination on-time (pont2).

- 1. Probabilities relating to link state (pup,pdown,pinti)

- 2. Probabilities relating to missing play-back deadline (ponti)

PPT Slide

Lager Image

PPT Slide

Lager Image

- 4.2 Derivation of end-to-end delay

In above DTMC, the amount of time
PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

5. SOLUTION PROCEDURE

If we use binary indicator vectors of links to form routes, our problem is combinatorial optimization that belongs to discrete optimization. For each server-client pair, we applies subgradient method to the search for optimal solutions. This is an efficient method in discrete optimization. In each iteration of subgradient algorithm, we solve the problem's relaxed form. Our subgradient algorithm stops when value of subgradient equals to zero. This time, the solution of relaxed problem is globally optimal solution. This solution provides two optimal paths for transmitting video to a client. After finding out solution of a client, the algorithm continues with other clients in multicast group.
Lagrangian relaxation of original problem (1) has following form
PPT Slide

Lager Image

PPT Slide

Lager Image

6. SIMULATION

We build a simulated OpenFlow-based network in Opnet modeler. In the network, a server multicasts video data to clients. Our algorithm is implemented at a logically centralized node. This plays the role of controller in OpenFlow. Input data is CIF version of MD coded video. Information of video sequences is shown in
Table 1
.
Information of video sequences

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

PPT Slide

Lager Image

7. CONCLUSION

In this paper, we propose a routing method with QoS enhancement for video multicast. In order to have determining metric for routing, distortion of MD video is predicted. That estimation is done with regard to delay, traffic load, packet loss. Packet loss is estimated by link state model. Delay is estimated by queuing model. We solve routing problem of each server-client pair by combining routing algorithm (i.e., Dijkstra's algorithm) and optimization methodologies (i.e., relaxation, subgradient). Multipath routing is applied to MD to gain loss-resilient transmission. The routing problem is formulated as an optimization problem. It first is relaxed by Lagrangian method; then it is solved by subgradient method. Each subgradient iteration calls a modified Dijkstra’s algorithm to find locally optimal pair of paths. In simulation, we compare our method with a conventional method. Our approach gains better performance in terms of received data, delay and PSNR.
BIO

Ballardie T.
,
Francis P.
,
Crowcroft J.
1993
“An Architecture for Scalable Inter-domain Multicast Routing”
Proceedings of ACM SIGCOMM
85 -
95

Carlberg K.
,
Crowcroft J.
1997
"Building Shared Trees using a One-to-many Joining Mechanism"
ACM SIGCOMM Computer Communication Review
27
(1)
5 -
11
** DOI : 10.1145/251007.251008**

Heng B.A.
,
Apostolopoulos J.G.
,
Lim J.S.
2006
“End-to-end Rate-distortion Optimized MD Mode Selection for Multiple Description Video Coding”
EURASIP Journal on Applied Signal Processing
Article ID 32592
2006
1 -
12
** DOI : 10.1155/ASP/2006/32592**

Mao S.
,
Hou Y.T.
,
Cheng X.
,
Sherali H.D.
,
Midkiff S. F.
,
Zhang Y.Q.
2006
“On Routing for Multiple Description Video over Wireless Ad Hoc Networks”
IEEE Transactions on Multimedia
8
(5)
1063 -
1074
** DOI : 10.1109/TMM.2006.879845**

Begen A.
,
Altunbasak Y.
,
Ergun O.
,
Ammar M.
2005
“Multi-path Selection for Multiple Description Video Streaming over Overlay Networks”
Signal Processing: Image Communication
20
(1)
39 -
60
** DOI : 10.1016/j.image.2004.09.002**

Kim S.G.
,
Park S.Y.
2011
"A Study on Virtual Source-based Differentiated Multicast Routing and Wavelength Assignment Algorithms in the Next Generation Optical Internet based on DWDM Technology"
Journal of Korea Multimedia Society
14
(5)
658 -
668
** DOI : 10.9717/kmms.2011.14.5.658**

Egilmez H.E.
,
Civanlar S.
,
Tekalp A.M.
2013
“An Optimization Framework for Qos-enabled Adaptive Video Streaming over Openfl ow Networks”
IEEE Transactions on Multimedia
15
(3)
710 -
715
** DOI : 10.1109/TMM.2012.2232645**

Lu M.H.
,
Steenkiste P.
,
Chen T.
2005
“Video Streaming over 802.11 WLAN with Contentaware Adaptive Retry”
Proceeding of IEEE International Conference on Multimedia and Expo
723 -
726

Zhang R.
,
Regunathan S.L.
,
Rose K.
2000
“Video Coding with Optimal Inter/Intra-mode Switching for Packet Loss Resilience”
IEEE Transactions on Selected Areas in Communications
18
(6)
966 -
976
** DOI : 10.1109/49.848250**

Wang Y.
,
Vuran M.C.
,
Goddard S.
2012
“Cross-layer Analysis of the End-to-end Delay Distribution in Wireless Sensor Networks”
IEEE/ACM Transactions on Networking
20
(1)
305 -
318
** DOI : 10.1109/TNET.2011.2159845**

Citing 'Per formance Evaluation for Multicasting Video over OpenFlow-based Small-scale Network
'

@article{ MTMDCW_2014_v17n9_1084}
,title={Per formance Evaluation for Multicasting Video over OpenFlow-based Small-scale Network}
,volume={9}
, url={http://dx.doi.org/10.9717/kmms.2014.17.9.1084}, DOI={10.9717/kmms.2014.17.9.1084}
, number= {9}
, journal={Journal of Korea Multimedia Society}
, publisher={Korea Multimedia Society}
, author={Thi, Thuyen Minh
and
Huynh, Thong
and
Kong, In-Yeup
and
Hwang, Won-Joo}
, year={2014}
, month={Aug}