| |
 |
|
HOME > Course
Projects > Multimedia Network >
Video Streaming using Receiver-Driven Multiple Paths
Abstract
Introduction
Protocol Description
Protocol Implementation
Performance Analysis
Related Work
Pitfalls
Conclusion and Future Work
Acknowledgements
Download the codes from HERE
Abstract
In this paper, we propose an algorithm in which the receiver selects
several best routing paths to transfer video packets according to the
packet delay and packet loss characteristics of various paths. The receiver
dynamically selects the paths which map to the recent network traffic.
We will use NS to simulate this algorithm and try to find the best parameters
according to the network topology and traffic. In our protocol, we compare
the performance to the single path and normal multiple path algorithm.
The total packet loss will decrease significantly using our protocol.
Introduction
The media transfer protocol RTP/RTCP is over UDP. In traditional UPD
routing protocol, the network routing protocol selects the shortest path
for the packet transfer, and hence cannot guarantee the optimum path for
transferring the packets. The routing protocol does not select the best
path among all the shortest paths from the sender to the receiver. For
layered media, every packet may be assigned different priority. In this
case, the UDP routing protocol will regard them as same priority and will
do the same QoS for all the packets. In all these cases, the main factor
is that UDP cannot select the most optimum path for packet transfer. In
our algorithm, we will select several optimum paths to transfer the media
packets to resolve the above disadvantage.
Transferring all packets in one path will cause more delay and congestion
on this path and result into hotspots and bottlenecks in the network.
As a result of this, the quality of this path will decrease. In our protocol
we propose to perform traffic balancing, that is, we select several best
paths to transfer different packets according to the quality of the path.
In layered media, every packet should have different priority; the base
layer has the highest importance. So we could select several paths to
transfer this media; the base layer packets could be transferred along
the best paths, the upper layer media along lesser efficient paths, and
so on. This would enhance the QoS of the media transfer because we will
provide more important layers better paths.
Streaming applications need stringent timing requirements. The UDP protocol
does not guarantee real-time service and low delay for packets. Some protocols
like RSVP, diffServ apply to the streaming applications and support QoS
services. But all these services require UDP routers to implement the
appropriate protocol. If the inner router cannot support these services,
the streaming application would not get the required QoS services. So
the problem is to get the QoS services without the need to modify the
routers. This is another issue that we target to meet. In our algorithm,
the UDP router need not be modified.
In streaming applications, the media packets are sent from media server
(sender) to the client (receiver). In a sender-driven approach, the server
records information to determine the optimum paths to the client. For
normal medial server, there would be over hundred clients connected at
any particular time. These will increase the server overload and decrease
the server quality. Secondly, in some networks, the bandwidth of uploading
path is different from the downloading path (like DSL, the download speed
is much faster than uploading). So the receiver-driven approach may not
signify the accurate traffic characteristics from the server to the client.
So selection of an appropriate approach is one of the issues in our protocol.
In most protocols, if the servers or clients want to probe the network,
they must introduce additional control packets (for example using the
ping packet to detect the traffic). In our protocol, neither the client
nor the server needs to use additional packets for testing the traffic
of the network.
Protocol Description
The main idea in our protocol is to select several optimum paths instead
of one path to transfer the packets. There are several benefits of selecting
server optimum paths as mentioned above. We use receiver-driven approach
instead of sender-driven approach in the protocol in order to reduce the
overhead incurred at the server side. The traffic information of the path
is detected by the client from the media packets sent by the server. Because
the media packet includes send packet time and packet sequence number,
the client has the ability to know the packet delay and packet loss in
the path. The feedback information is sent from the client to server using
the some protocol (for example, if using RTP, RTCP can be used for traffic
information in path transfer from client to server).
The basic architecture of our scheme is shown in figure 1. We consider
a scenario with a single video server and several media clients in the
network. There are multiple paths between the server and the client and
these are characterized by varying parameters like delay, bandwidth and
packet loss.
In normal scenarios (as in OSPF), packets will be routed along the shortest
hop path. This shortest path may be highly congested leading to higher
delay. Therefore, different metrics must be used to find alternate better
paths. We propose to find these multiple paths by measuring end-to-end
delay of the path and also the packet loss experienced by the path.
Some of the issues in designing the protocol are: 1) Path selection: how
a client (receiver) would select several optimum paths. We propose that
the receiver records the previous packets and accordingly selects the
paths in an optimum manner. 2) Selection Policy (Metric): according to
the packet delay and packet loss along the path. Packet delay can be calculated
from the packet send time and receive time. Packet loss can be derived
from the packet sequence number. 3) Feedback mechanism: using RTCP to
report the new optimum paths information to the server. 4) Type of method
(static, dynamic, or adaptive): we use the dynamic method to let the client
report the paths information to server periodically.
Our protocol can thus provide the following advantages: 1) it can resolve
some of the limitations of UDP; 2) it uses multi path to balance the traffic
between the server and client; 3) supports different QoS services for
different layers in the layered media transfer; 4) uses receiver-driven
approach to reduce the server overload; 5) does not use any additional
packets for probing the network; 6) does not modify the internal routers.
Protocol Implementation
In this protocol, the client (receiver) will record the previous media
packages sent by the server. These packets are delivered using normal
streaming protocols like RTP, RTCP and RTSP. After the client receives
a certain number of packets which we have assumed to be 1000 for our simulations,
it maintains data structures to store the statistics. These statistics
include the number of packets received on a particular path, the average
delay and the number of packets lost on that path. Using this data, the
client finds optimum paths. These paths are then assigned weights and
this information about the paths and their corresponding weights is sent
back by the client to the server using feedback in RTCP packets. The weights
are assigned using the following function.
Weighti = f (Sj , Dj, PLi) for packets j = 1,2,…,n
on paths i = 1,2,…,m.
“f” is the function to calculate the path weight according
to the average delay (D) and the packet loss (PL).
The server can now distribute the packets along the paths depending upon
the feedback received. The remaining packets will be sent over the network
without specifying the path. (These packages are to use to detect the
other path traffic in the network). Thus over regular intervals, the receiver
would be able to update the weights of the specified paths and find new
better paths if any. This procedure is repeated at regular intervals in
order to dynamically adapt to changing network conditions. Thus, our approach
would adapt to network conditions and give a better performance by sending
a larger proportion of the traffic on the least congested and least delay
path. The sequence diagram is shown in following figure.
Performance Analysis
The performance for Weighted multipath routing was analyzed by performing
simulation. NS-2 (Network simulator) was chosen for the same. The version
we worked on was NS2.26. We had to create our topology that involved one
server and one client to start with. There were five routers and hence
five paths from the server to the client.
• Simulation on ns-2
– One Server and one cleint
– 5 Paths between server and client
– Packet size = 1k
– CBR at server = 1MBps
– Background Traffic to simulate other flows
• Constant
• Intermittent
The simulations were carried out for 15 seconds each. First few results
compare the performance under the video traffic only. As mentioned previously,
packets were sent by the source. In case of normal multiple path scheme,
packets would have been sent equally on all the paths. In the weighted
multiple path scheme, the packets would be sent according to the ratio
of the weights of the paths.
Following are the graphs describing the throughput as the simulation time
progresses.
As all the packets are sent on all the links in the same ratio, the links
with better bandwidth capacity and having less delay would prove to give
better performance. That is why there would be more packet loss on the
links with less bandwidth. Packets would be recorded as lost if they are
dropped at the queues in the intermediate schedulers or they are lost
in transit. In the actual NAM simulation the routers were seen to drop
these packets.
In graph 2, it is observed that the initial packet losses are high which
go over 100 packets. After that, the packet loss is considerably reduced.
It is consistent with the expected results that over the time, the path
constraints would be well expressed by the weights assigned to that path.
Thus our scheme sent more packets on the better paths. These paths are
better in terms of delay as well as packet loss. This was achieved because
we calculated the number of packets lost on each path and accordingly
calculated the weights.
In graph 1, the initial packet drops go up to 150 packets and remains
constant at the high value later on. Our scheme is giving packet drop
up to 115 initially and 70 later. It can be easily verified that our scheme
performs better with respect to throughput than the scheme of Normal multiple
paths.
It was not enough to test the performance only under the applied load.
Graphs 3 to 5 show the results when there was background traffic in the
system. Random background traffic was generated on few of the links.
It is obvious that the single path routing scheme would perform the worst
in case of highly loaded and congested network links. In graph 3, more
packets, up to 350 are dropped initially and 250 for the later period.
Multiple path routing would provide better quality as measured by the
throughput as the number of dropped packets. In graph 4, this value is
310 packets initially and much lower than the normal routing later.
Advantages with the Weighted Multiple Path algorithm can be observed
at the start of the experiments itself. The scheme provides stabilization
as the time progresses. After first five seconds, the number of packets
dropped was reduced almost to 50 packets on average.
Thus our scheme would give a better performance over time as it can be
concluded from these graphs. The argument can be valid that weighted multiple
path routing is not showing much improvement if the simulations are performed
for a short duration. But the observation is that the average lifetime
of video streaming applications like video conferencing or video on demand
are never too short.
Extensive simulations were carried out changing the values of the link
bandwidth as well as the packet sending rate. Also, background traffic
was changed at random. The nature of the background traffic was intermittent.
Next two graphs compare the two schemes of multiple routing very well.
The Weighted Multiple Path routing stabilizes quite fast. Only in the
initial time the packet losses are high. Later on, if the congestion on
any particular path increases (implemented as background traffic), the
weight of that link would be immediately reflect this. Thus the overall
packet losses at the receiver side are very low. The aim of distributing
the load across different links is achieved and the receiver side benefits
from higher throughput.
Related Work
There has been a lot of research in QoS based routing. In these cases
[1, 2, 6, 7], admission control is used along with routing. Routers are
responsible for finding paths that satisfy certain required QoS constraints.
These algorithms basically use two approaches – either maintain
global state information or flood the requests to find QoS-compliant paths.
However, the drawback of these approaches is that these routing algorithms
require changes in router functionality. Routers have the added responsibility
of finding QoS-compliant paths.
There has also been work in finding multiple paths between source and
destination. Multiple Description Coding [2], works on the same principle.
It routes descriptions over multiple paths in the hope that at least one
of them reaches the destination. If more descriptions reach the destination,
then better picture quality can be achieved. This adds robustness to the
system.
Recently, proportionate routing [7] has been suggested. This approach
selects multiple paths from source to destination. A path is added to
a list of candidate paths if adding it to the list increases the width
of the total paths. This is performed based upon localized information
about QoS metrics like delay etc. These candidate paths are assigned weights
on a hop-by-hop basis. The requirement of the algorithm is that the paths
have disjoint bottleneck links.
All of the above approaches suggest changes in the router functionality
and propose an enhancement to the routers. In our approach, we propose
to use an end-to-end approach. We select paths based on end-to-end metrics.
Weights are assigned to entire paths, instead of individual links. This
way, the routers are not required to be re-configured. The tradeoff with
our system would hence be that finer granularity over the control of paths
will not be achieved. Paths will be weighted on an end-to-end basis and
even though individual links on a bad path may be congestion-free, the
path would be considered to be unsuitable. However, we believe that this
would not prove to be a big disadvantage as the QoS metrics for entire
paths (like end-to-end delay) are more accurate measures in the selection
of paths.
Pitfalls
Our algorithm is based on the assumption that multiple paths between
source and destination are discovered. This assumption may require modifications
to the internal routers. Also, overhead incurred in assigning weights
may not be justifiable for small sessions in which cases short single
path sessions may prove to be a better solution. Clients need to store
the path information (packets loss, packet delay, etc) to perform statistical
analysis. In networks with lower traffic and packets loss, our protocol
does not get any performance improvement. It may result in worsening the
network quality as the client always sends feedback packets to the server
periodically.
Conclusion and Future Work
Thus, we have designed and simulated a receiver-driven weighted multipath
algorithm for video streaming. We use end-to-end metrics to designate
weights to the paths and hence does not require modifications internal
network routers. Our results show that a significant improvement in performance
can be obtained. The number of packet loss drops significantly and better
quality streaming can thus be achieved from the same.
In future, we can employ the adaptive method instead of the dynamic method
to test the performance in the low traffic network. In the adaptive method,
the client will maintain threshold; the client will send feedback only
if the received packet delay or packet loss reach the threshold. The threshold
can be adaptive to the network traffic. Finding the best function to calculate
the weight of the path is another future work we need to do. In this paper,
we have only tested the performance of a single server client. Next we
will focus on the multi server and multi client and test the performance
for our protocol.
Acknowledgements
[1] Ali C. Begen, Yucel Altunbasak, and Ozlem Ergun, “Fast heuristics
for multi-path selection for multiple description encoded video streaming,”
in IEEE Int. Conf. Multimedia and Expo, Baltimore, MD, July 2003.
[2] V. K. Goyal, “Multiple description coding: Compression meets
the network,” IEEE Signal Processing Mag.
[3] S. Lin, S. Mao, Y. Wang, and S. Panwar, “A reference picture
selection scheme for video transmission over ad-hoc networks using multiple
paths,” in IEEE ICME, 2001.
[4] Van Jacobson and Michael J. Karels, Congestion Control and Avoidance.
ACM SIGCOMM 88
[5] Vern Paxson, End-to-End Routing Behavior in the Internet. Proc. SIGCOMM
96
[6] Chen and Nahrstedt, " An Overview of Quality of Service Routing
for Next-Generation High Speed Networks: Problems and Solutions,"
IEEE Network, pp 64--79, Nov-Dec 1998.
[7] Srihari Nelakuditi, Zhi-Li Zhang, A Localized Adaptive Proportioning
Approach to QoS Routing.
[8] Documentation for ns from isi.edu.
|
