Transcript Video Delivery Technologies for Large-Scale Deployment

Video Delivery Technologies
for Large-Scale Deployment of
Multimedia Applications
By Hua, Tavanapong, Tanatui et. al., Univ. of
Central Florida
Proceedings of IEEE, Sept. 2004
Presented by
Nimish Vartak
Dec 09, 2004
CSEE UMBC
Agenda
• Overview of Streaming
• Basics of IP Multicast
• IP Multicast for streaming
• Basics of ALM
• ALM Technologies for streaming
• Basics of Proxy Server
• Proxy Server Technologies
• Conclusion
Nimish Vartak
Streaming
• What is streaming
– Media is sent to end-user as in a download
– End-user can start playing data as soon as few packets are received.
• Issues with Large-Scale deployment
– Simplistic – Allocate server resources for each request
• Problems faced
– Expenses
– Variety of users
• T1, Cable
• Dial-up
– Scalability issues
Nimish Vartak
Video on Demand (VOD)
• Entities involved
•Video Server
•Client Machine
•Interaction flow
•Client requests video
•Server delivers requested
video to user in an
isochronous data stream.
•Simplest scheme
• One server channel to
serve each video request.
Nimish Vartak
Types of VOD
• No VoD
– User is passive
• Pay-per-view
– Sign-up for specific services at pre-determined times
• True VoD (TVOD)
– One channel for every user, Full VCR capability
• Near VoD (NVOD)
– Only one video stream for the same video requested
• Quasi VoD (QVOD)
– Threshold based NVOD
Nimish Vartak
Solution(s) ...
• Server transmission using IP multicast
– Reactive
– Pro-active
– Hybrid
• Streaming strategies using Application
Layer Multicast (ALM)
– Goes beyond the IP Multicasting, which is limited to LAN
• Proxy Caching
– Proxy for the cached portion
– Server for the un-cached portion
Nimish Vartak
Basics of IP Multicast
• Relies on the IP
Multicast support in
routers and switches.
• LAN-level Multicast –
Use of Group
Management protocol
like IGMP.
• Wide-area routing – can
use routing protocols
like PIM-SM, DVMRP
* Figure courtesy Kai Shen, Univ. of Rochester
Nimish Vartak
... using IP multicast
Nimish Vartak
... using IP multicast (Contd.)
Reactive Server Transmission
–Static Multicast
• One server channel serves a batch of requests for
–same video channel
– and arriving within short period of time
• e.g. FCFS, Maximum Queue Length First
–Dynamic Multicast
• Dynamically expands the multicast tree for late-arriving requests for
same video
• e.g. Chaining, Patching
Nimish Vartak
... using IP multicast (Contd.)
Examples of Static Multicast
• First Come First Serve (FCFS)
maintains fairness
• Maximum Queue Length First
(MQLF) is unfair to videos having
low request rates.
•Maximum-factored-queued-length
first (MFQLF)
• length li weighted by 1/√fi
• fi = access frequency
Thus ensures both
•High throughput
•Fairness
Nimish Vartak
... using IP multicast (Contd.)
Patching as an example of Dynamic Multicast
• It shows that users C1 and C2 are
served together with a single multicast
stream.
• At t time units later, user C3 requests
the same video.
• C3 joins the multicast tree and starts
buffering arriving video data
• At the same time C3 downloads the
missing portion via a patching stream.
•Requirement • Two streams - a regular
multicast and a patching and
• Enough buffer space to absorb
the time skew .
Nimish Vartak
... using IP multicast (Contd.)
Proactive Server Transmission (Periodic Broadcast)
Segments of video - Each segment is periodically broadcast on a dedicated channel.
Client tunes into one or more channel concurrently.
•Server Oriented
–Techniques in this scheme reduce service delay by increasing server bandwidth
– e.g. Staggered multicast, Skyscraper multicast
•Client Oriented
–Techniques in this scheme reduce the service delay by increasing the
requirement of client (and server) bandwidth
– e.g. Harmonic multicast, Pagoda multicast
Nimish Vartak
... using IP multicast (Contd.)
Hybrid Broadcast Schemes
• Beneficial for popular videos (only)
• Combining on-demand multicast and periodic broadcasts gives best performance
• e.g. Adaptive hybrid Approach
– Popularity – distribution of recent service requests
– Video broadcast
•Popular videos – using skyscraper broadcasting
•Lesser popular videos – batching
– Number of channels for broadcast depends on combination of video channels
currently in system while remaining channels allocated to batching.
Nimish Vartak
... using IP multicast (Contd.)
Issues with multicasting schemes:
• User heterogeneity
– Use of layered media formats
–Base + enhancement
• VCR-like interactions
– Use of an emergency channel for FF/REV.
– Use of Split and merge (SAM) for emergency channel
• Video Server Software
– Caching portions of broadcast videos in server memory improves the
number of concurrent videos that can be supported by a broadcasting
server
Nimish Vartak
Need for ALM
• Routers have an overhead of maintaining a
table of per-group states
• Prone to flooding attacks
• Difficult to provide congestion at a higher
layer.
• IP Multicast support is not implemented in all
routers and switches.
Nimish Vartak
Basics of ALM
• Multicasting occurs in the
higher layers - application
layer.
• Multicast support in the
network layer is not required.
• Unicast is used to for
communication between the
nodes.
• Network nodes in an overlay
network are end systems,
enabling sophisticated
functions.
• The overlay nodes topology
can be altered as desired.
• Also called end-to-end
multicast
* Figure courtesy Kai Shen, Univ. of Rochester
Nimish Vartak
Using ALM
Nimish Vartak
Using ALM (Contd.)
Infrastructure-based approach -e.g. Range Multicast
• Data is transmitted to the multicast tree of only Overlay nodes
• Overlay nodes are strategically placed in WAN
• A receiver joins the multicast group by connecting to nearest overlay node.
• Each node on the path caches video data into its fixed-size FIFO buffer as data flows
• Fundamental capability to accommodate more users over the time
• 'Range multicast' name implies that Data is available in at any point is a contiguous
segment of video, not a data point.
Nimish Vartak
Using ALM (Contd.)
P2P approach
Design Considerations
• Short access latency
• Quick and graceful recovery to handle peer failures
• Minimize overhead of information exchange between peers
Nimish Vartak
Using ALM (Contd.)
P2P with Pre-recorded Video Streaming
• A new client can receive a video stream from earlier arriving client’s buffer
• Chaining is first P2P approach
• Clients cache portions of the video data
• Hence clients have ability to forward the video to other downstream
clients.
• Client nodes form a “delivery chain”, and the server delivers the video
through that chain using a single data stream.
• Thus client gets data either from existing or new chain.
• This reduces the burden on the Video server.
Nimish Vartak
Using ALM (Contd.)
P2P with Live Streaming
Consideration for issues like:
– Access latency is more crucial
– Latency in forwarding data over many peers
– Hence the tree height needs to be minimum.
– Trade-off – small height  All peers get data from server
 Consumes more server bandwidth
– User joining a group is concerned about data only from the point of
joining
– Degradation of video content is crucial because the broadcast will not
repeat.
– e.g. CoopNet, ZigZag
Nimish Vartak
Using ALM (Contd.)
ZIGZAG as an example of P2P
• Peers organized into a logical hierarchy of clusters of peers.
• Each cluster requires the number of peers to be in a bounded range.
• One “leader” elected from the peers in the cluster.
• Shown are 32 peers including the server S.
• Level 0 contains all peers that are clustered in eight groups of four.
• A higher level cluster contains only the leaders of the lower level clusters.
Nimish Vartak
Using ALM (Contd.)
ZIGZAG as an example of P2P (Contd.)
• Multicast delivery tree:
– A peer, when is not in its highest level, does not have a connection to
or from any other peer
– A peer, when in its highest level, can only connect to other peers from a
different cluster in the immediate lower level
• Peers that are not leaders get data from a leader of a different cluster.
• Since the leader peer of each cluster does not forward the data to the peers in
its cluster, but forwards it to the peers in a different cluster, the technique is
called ‘ZIGZAG’.
• For ‘k’ minimum cluster size, and ‘N’ peers,
• ZIGZAG guarantees the height of the tree to be O(lognk) and a node degree
O(k2) .
• Keeping the height of the tree small improves the live-ness of the video.
• A bounded node degree minimizes the cost of reconnecting peers on failure.
Nimish Vartak
Basics of Video Proxy Tech.
• A proxy server is typically installed in the same local
network as the clients.
• The proxy delivers the cached portion of the requested
video to the client.
• The remote video server transmits only the uncached
portion of the video to the client.
• Thus, it is useful to
– Reduce service delays and network load, and video server
load
– Provide better playback quality
Nimish Vartak
Video Proxy Technologies
Nimish Vartak
Video Proxy Tech. (Contd.)
Stand-Alone Proxy Caching
Cache allocation policy with Reactive Transmission Schemes
• Prefix Caching
– Temporally divides video frames as:
• Retains the prefixes of videos in the proxy
• Playing of video continues while receiving suffix from the Remote
Server
• Video Staging
– Frames are spatially divided into two parts
• The upper part typically has more variability in the bandwidth
requirement and is stored at the proxy.
• The lower part has less variability in the bandwidth requirement and
is transmitted from the video server when needed.
Nimish Vartak
Video Proxy Tech. (Contd.)
Stand-Alone Proxy Caching
Cache allocation policy with Periodic Broadcast
• Caching the beginning frames (prefix) of very popular videos in a proxy
reduces the server–proxy bandwidth for broadcasting the rest of the
video.
• This is because a fewer broadcast channels are needed to broadcast a
shorter suffix.
• The important design issue is to ensure that the first segment of the
suffix is available to the client before the entire prefix is played out.
• Hence, the first segment of the suffix is made equal to the size of the
prefix.
• Optimal prefix sizes are those that result in the minimum server–proxy
bandwidth needed to broadcast the suffixes of the videos.
Nimish Vartak
Video Proxy Tech. (Contd.)
Stand-Alone Proxy Caching
Cache Replacement policy
• Applied when – the current cache space is not enough for new video
data
• Cache replacement policy determines
– which cache unit and
– how many of them to purge out to
• Aspects considered:
– The video sizes
– Popularity of the video
• Cache replacement policies for layer-encoded videos
– Selects a “victim” layer—the layer with the lowest hit ratio.
– Segments in the victim layer are purged from the end
Nimish Vartak
Video Proxy Tech. (Contd.)
Collaborative Proxy Caching
• Stores more videos close to requesting clients
• Uses
– aggregate network bandwidth and
– storage space of several proxies in the same Intranet
• The number of participating proxies and their resources are known a
priori
• Example Proxy server organization - Cache Hierarchy
– Proxies as the leaf nodes of the hierarchy keep the prefixes of
popular videos
– Client queries the Leaf proxy for a video
– If the prefix is not found, the parents and siblings proxies will be
queried
Nimish Vartak
Conclusion
• Variety of Methods are possible for Video streaming delivery
• Implementation challenges
• Buffer
• Connection speed
• Node Failure
• Multicast support
• Would new video standards alleviate the problem ?
• Scalability aspects ?
Nimish Vartak
References
•Video Delivery Technologies for Large-Scale Deployment of Multimedia Applications
Kien A. Hua, Mounir A. Tantaoui, and Wallapak Tavanapong
(PROCEEDINGS OF THE IEEE, VOL. 92, NO. 9, SEPTEMBER 2004)
•Multicast with Network Coding in Application-Layer Overlay Networks –
Ying Zhu, Baochun Li, Member, IEEE, and Jiang Guo
(IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, VOL. 22, NO. 1,
JANUARY 2004 1)
• Kia Shen, University of Rochestor [URCS-573]
Nimish Vartak
Thank You
Nimish Vartak