Over the past several years, as the speed of computer and network increase dramatically, more and more networked multimedia applications proliferate rapidly. Many real-time applications such as multimedia streaming and video conferencing usually have more strict quality of service (QoS) requirements from the network, because they are more sensitive to available bandwidth, loss rate, delay and delay jitter than elastic traffic. Although some of these applications are becoming more flexible now and can adapt to the network fluctuations accordingly, there still exists a minimum QoS level that should be controlled during the session in order to keep the application working on an acceptable quality.
Current IP networks offer the so-called best effort (BE) services, which do not make any service quality commitment. To support QoS in the Internet, IETF has defined two architectures: the Integrated Services, and the Differentiated Services. The integrated services model provides per-flow QoS guarantee and RSVP (Resource ReserVation Protocol) was suggested for resource admission control and resource allocation. However, it is very complicated for backbone routers to maintain states of thousands of classes. On the other hand, differentiated services model gives a class-based solution to support relative QoS. In differentiated services, packets are divided into different QoS classes and forwarded as different priorities. Since it is highly scalable and relatively simple, differentiated services model may be promising to dominate the backbone of the next generation Internet in the near future. On the other side, there is still great possibility that integrated services will function within the access or corporate network.
Most previous work only considered how to differentiate media streams, i.e., different packets in the same IP session has the same communication characteristics. Information with different transmission requirements is transported by different IP sessions. For example, in layered coding and transmission, multiple independent communication channels are required for different layers. Two problems arise due to multiple channel approach: the synchronization between channels and the network state maintenance.
Delivering multimedia contents with high quality and low cost over the Internet is challenging due to the typical large sizes of media objects and the continuous streaming demand of clients. There are three representative solutions for media streaming in the Internet.
First, special content delivery networks have been built to replicate media servers across the Internet to move the contents close to the clients. This approach is performance-effective but is also very expensive.
The second approach is to utilize existing proxies to cache media data, which is cost-effective but not scalable due to limited storage and bandwidths of centralized servers.
The third approach is to build client-based P2P overlay networks for media content delivery, which is highly cost-effective but does not guarantee the quality of services because the capacities of peers can be heterogeneous and their availabilities can be transient.
Many researchers delve in the media delivery problem by looking into the proxy caching approach, which has been successfully used for delivering text-based content on the Internet. However, a full caching approach of media objects can quickly exhaust the limited proxy cache space. To handle the large sizes of media objects, researchers have developed a number of segment-based proxy caching strategies to cache partial segments of media objects instead of their entirety.
Although the segment-based proxy caching technique has shown its effectiveness for media streaming, the quality of service it can provide is still not satisfactory to clients for the following reasons. First, the limited storage capacity of a proxy will restrict the amount of media data it can cache for clients. Second, the delivery of streaming media normally requires a dedicated reservation of continuous bandwidths for the clients, thus, the highly demanded proxy bandwidths will limit the number of clients to be served simultaneously.
Furthermore, a proxy not only easily becomes a system bottleneck, but also forms a single point of failure, being vulnerable to attacks. On the other hand, the resources of bandwidth, storage, and CPU cycles are richly available and under-utilized among the clients. Thus, the P2P file sharing model is very attractive. However, directly borrowing this model for media streaming can not guarantee the quality of streaming service for the following three reasons.
First, the availability of demanded media data in each peer can be unpredictable because each peer caches and replaces media content independently without any coordination with other peers.
Second, the availability of services can also be dynamic due to the transient nature of peers even though the data is always available.
Third, the quality of services provided by multiple collaborative peers sometimes may not be sufficient for highly dynamic and Burstyn media streaming requests.
With the widespread penetration of broadband accesses, multimedia services are getting increasingly popular among users and have contributed to a significant amount of today's Internet traffic. Many multimedia applications, such as NetTV and news broadcast, involve live media streaming from a source to a large population of users. For these applications, IP Multicast is probably the most efficient vehicle; its deployment however remains confined due to many practical and political issues, such as the lack of incentives to install multicast capable routers and to carry multicast traffic. Researchers thus have resorted to application-level solutions, which build an overlay network out of unicast tunnels across cooperative participating users, called overlay nodes, and multicast is then achieved through data relaying among these nodes.
Initially as remedies to IP multicast, many overlay construction algorithms also advocate a tree structure for data delivering. While this works well with dedicated infrastructure routers as in IP multicast, it often mismatches an application-level overlay with dynamic nodes. As the autonomous overlay nodes can easily crash or leave at will, a tree is highly vulnerable, which is further aggravated with streaming applications that have high bandwidth and stringent continuity demands. Sophisticated structures like mesh and forest can partially solve the problem, but they are much more complex and often less scalable. On the other hand, migrating the multicast functionalities to application-layer also leads to greater flexibilities; in particular, all the nodes have strong buffering capabilities and can adaptively and intelligently determine the data forwarding directions.
Chapter 2:Literature Survey And Theory
Thus envision a data-centric design of a streaming overlay, where a node always forwards data to others that are expecting the data, with no prescribed roles like father/child, internal/external, and up-streaming /down-streaming, etc. In other words, it is the availability of data that guides the flow directions, while not a specific overlay structure that restricts the flow directions. This data-centric design is more suitable for overlay with high dynamic nodes, particularly considering that a semi-static structure, no matter how efficient, is constantly rendered to suboptimal due to node dynamics.
The Internet has witnessed a rapid growth in deployment of data-driven or swarming based peer-to-peer streaming systems (P2P streaming systems). Since the data-driven protocol is first proposed in academia. Such protocol achieves great success mainly due to the good scalability as well as the robustness to the high churn of the participating nodes. Recent exciting reports show that systems based on this type of protocol have the power to enable over 230,000 users simultaneously watching a hot live event with 300ยป500 Kbps by only one streaming server on the global Internet.
The basic idea of data-driven streaming protocol is very simple and similar to that of Bit-Torrent. The protocol contains two steps.
In the first step, each node independently selects its neighbors so as to form an unstructured overlay network, called the gossip-style overlay construction or membership management.
The second step is named block scheduling: the live media content is divided into blocks (or segments, packets) and every node announces what blocks it has to its neighbors. Then each node explicitly requests the blocks of interest from its neighbors according to their announcement. Obviously, the performance of data-driven protocol directly relies on the algorithms in these two steps.
To improve the performance of data-driven protocol, most of the recent papers focused on the construction problem of the first step. Researchers proposed different schemes to build unstructured overlays to improve its efficiency or robustness. However, the second step, i.e., the block scheduling has not been well discussed in the literature yet. The scheduling methods used in most of the pioneering works with respect to the data-driven/swarming based streaming are somewhat ad hoc. These conventional scheduling strategies mainly include pure random strategy, local rarest-first strategy and round robin strategy. Actually, how to do optimal block scheduling to maximize the throughput of data-driven streaming under a constructed overlay network is a challenge issue.
Video streaming
Video streaming architecture
A typical multicast streaming scheme is represented in Figure. A multicast source implements a streaming server which is responsible for retrieving, sending and adapting the video stream. Depending on the application, the video may be encoded on-line for a real-time transmission or preencoded and stored for an on demand transmission. Applications such as video conferencing, live broadcast or interactive group games require real-time encoding. However, applications such as video on-demand require pre-encoded video. Whence the multicast session is initialized, the streaming server retrieves the compressed video and begins the streaming with the adequate bit -stream rate.
Figure 1: Video Streaming Architecture
Streaming protocols and standards
Real-Time transmission control: RTP/RTCP
The Real-time Transport Protocol (RTP) and Realtime Control Protocol (RTCP) are IETF protocols designed to support streaming media. RTP is designed for data transfer and RTCP for control messages. Note that these protocols do not enable real-time services, only the underlying network can do this, however they provide functionalities that support real-time services. RTP does not guarantee QoS or reliable delivery, but provides support for applications with time constraints by providing a standardized framework for common functionalities such as time stamps, sequence numbering, and payload specification. RTP enables detection of lost packets.
RTCP provides feedback on quality of data delivery in terms of number of lost packets, inter-arrival jitter, delay, etc. RTCP specifies periodic feedback packets, where the feedback uses no more than 5 % of the total session bandwidth and where there is at least one feedback message every 5 seconds. The sender can use the feedback to adjust its operation, e.g. adapt its bit rate. The conventional approach for media streaming is to use RTP/UDP for the media data and RTCP/TCP or RTCP/UDP for the control.
Often, RTCP is supplemented by another feedback mechanism that is explicitly designed to provide the desired feedback information for the specific media streaming application. Other useful functionalities facilitated by RTCP include inter-stream synchronization and round-trip time measurement.
Session control: SIP/RTSP
The Session Initiation Protocol (SIP) and the Real-Time Streaming Protocol (RTSP) are used to control media streaming sessions. SIP is an application-layer control protocol that can establish, modify, and terminate multimedia sessions such as Internet telephony calls (VOIP). SIP can also invite participants to already existing sessions, such as multicast conferences. RTSP establishes and controls either a single or several time-synchronized streams of continuous media such as audio and video. It acts as a "network remote control" for multimedia servers. RTSP provides an extensible framework to enable controlled, on-demand delivery of real-time data, such as audio and video. Sources of data can include both live data feeds and stored clips. RTSP is intended to control multiple data delivery sessions, provide a means for choosing delivery channels such as UDP, multicast UDP and TCP, and provide a means for choosing delivery mechanisms bases upon RTP.
Session description: SDP
The Session Description Protocol (SDP) describes multimedia sessions, for example whether it is video or audio, the specific codec, bit rate, duration, etc, for the purpose of session announcement, session invitation and other forms of multimedia session monitoring. Session directories assist the advertisement of conference sessions and communicate the relevant conference setup information to prospective participants. SDP is designed to convey such information to recipients. SDP is purely a format for session description - it does not incorporate a transport protocol, and is intended to use different transport protocols as appropriate including the Session Announcement Protocol (SAP).
Session Announcement: SAP
Session Announcement Protocol (SAP) is an announcement protocol that is used to assist the advertisement of multicast multimedia conferences and other multicast sessions, and to communicate the relevant session setup information to prospective participants. A SAP announcer periodically multicasts an announcement packet to a well-known multicast addresses and port. A SAP listener learns of the multicast scopes it is within (for example, using the Multicast-Scope Zone Announcement Protocol) and listens on the well known SAP address and port for those scopes. In this manner, it will eventually learn of all the sessions being announced, allowing those sessions to be joined.
TIME-AWARE BLOCK SCHEDULING
We propose new formulation of block scheduling considering block deadline and the time of delivering. Our goal is to minimize the total time of scheduling all the streaming blocks that are delivered to each node in one request period under heterogeneous bandwidth constraints.
The idea of DON based streaming system is similar to Bit-Torrent protocol. But in Bit-Torrent protocol, node only concerns minimum time to complete downloading file with no block arriving ordering. The scheduling for media streaming requires successive order of block arrivals. In our protocol, the media streaming is divided into blocks with the same size, each of which has a unique sequence number. Every node has an exchanging window, the blocks in the exchanging window are the ones before the deadline, and only these blocks will be requested if they are not received. Every node periodically notifies all its neighbors a bit vector called "buffer map" representing the available blocs in its exchanging window to announce what blocks it has. Every node will periodically send requests to its neighbors for the absent blocks in its exchanging window, and the time between two requests is called a request period.
There are two types of bandwidth constraints, i.e. access bottlenecks (inbound and outbound bandwidth capacity) and non-access bottleneck bandwidth (end-to-end bandwidth). Due to the equal-size block concerned, measured the amount of inbound, outbound and end-to-end bandwidth in terms of the blocks that can be transmitted per second.
Data-driven overlay network is suitable for live- event streaming, because it can provide relatively- continuous streaming even in dynamic environment. In terms of improving streaming quality, prior work covered membership management, buffer map exchange, segment requesting schedule, etc. In this paper, we address the problem of segment-sending schedule on the segment-providing node, which may also affect the streaming quality. The schedule methods we discuss include FIFO schedule, lower-sequence favored schedule, and higher-sequence favored schedule.
A stream is divided into many segments. Each segment flows from the source node to all the nodes in the data-driven overlay network, by segment-requesting and segment- sending between partner nodes. The segment-requesting and segment-sending between partner nodes is composed of three steps: the segment-requesting node selects a "best" partner node to send the request for a certain segment; the segment request arrives at the requesting queue of the segment-providing node; and the segment-providing node replies the request in the requesting queue by sending the corresponding segment.
To improve the streaming quality, prior work has covered aspects including membership management, buffer map exchange, segment-requesting schedule, etc. But no work addressed how a segment-providing node schedules the segment- sending when replying the requests in the requesting queue. Different ways to schedule the segment-sending may result in different streaming qualities.
There are three methods: FIFO schedule, lower-sequence favored schedule, and higher- sequence favored schedule.
Streaming Quality
The streaming data transmitted in the data-driven overlay network can be divided into segments with uniform length. A buffer map can represent the information of available segments on a node. Each node periodically exchanges its buffer map with its partner nodes, and decides from which partner node to fetch a certain segment. If there are multiple partner nodes holding the same expected segment, various ways can be chosen to select the segment-providing node, for instance, the one with the highest bandwidth. This is called the segment-requesting schedule.
Each node maintains a buffer window, which is used to store a number of continuous segments of the stream. A node can only request for segments that are within the buffer window. After having played a segment, the segment could be discarded and the buffer window is moved upwards. Suppose the buffer window size of each node is B , which is usually much less than the total segment number of the stream. To make the streaming more continuous, each node usually doesn't begin to play the stream immediately after receiving the first segment. Instead, it waits for the arrival of the first several segments and then begins to play the stream. The number of segments each node waits for before playing the stream is called the playing waiting segment number, denoted by W. Obviously, there should be the relationship W<=B.
Segment-sending Schedule Methods
In data-driven overlay network, each node exchanges buffer map with partner nodes and decides from which partner node to request a certain segment. The request arrives at the requesting queue on the segment-providing node. At the time when the segment-providing node replies to the requests, if there are multiple requests in the requesting queue, it has to schedule the segment-sending.
There are two issues to consider: how to send the replying segments if the priority of each request is assigned, and how to assign the priority of each request in the requesting queue.
There are two ordinary methods to schedule the segment sending, both in favor of higher-priority requests. One method is to send one segment after another according to the priorities of the requests with the whole sending bandwidth, which is called the one-after-another method. The other method is to allocate the sending bandwidth proportional to the priorities of the requests and send the segments simultaneously, which is called the proportional-bandwidth method.
A segment s is available on node i only after the segment arrival time ( , ) Ar s i , either for playing or for forwarding. By queuing theory, the one-after-another method is better than the proportional-bandwidth method in that the requests with higher priorities will receive better services without sacrifice to requests with lower priorities. If there are new requests coming when the segment-providing node is sending a segment to some partner node, the new requests are inserted into the requesting queue, and the next-turn segment-sending schedule should be conducted only after the current sending is completed.
The key problem here is how to assign the priorities of the requests in the requesting queue. The simplest way is to assign the requests arriving earlier with higher priorities, which we call FIFO schedule. However, in data-driven overlay network which transmits live-event stream, the sequence number of the segment each node requests for should be considered. Higher-sequence favored or lower-sequence favored streaming may result in different streaming qualities. The method of assigning lower-sequence segments with higher priorities is called lower-sequence favored schedule, and the method of assigning higher-sequence segments with higher priorities is called higher-sequence favored schedule.
The procedure of segment-sending schedule on the segment-providing node can be shown in Figure 2. Requests arrive at the segment-providing node, and the providing node assigns the priorities of these requests by one of the three priority assignment methods we suggest. After that, the segment-providing node replies to the requests by sending the corresponding segments in a one-after-another way.
Proposed Project Module
BLOCK SCHEDULING: PROBLEM STATEMENT AND FORMULATION
The media streaming is divided into blocks with the equal size, each of which has a unique sequence number. Every node has a sliding window, which contains all the up-to-date blocks on the node and goes forward continuously at the speed of streaming rate. The blocks in the exchanging window are the ones before the playback deadline, and only these blocks is requested if they are not received. The unavailable blocks beyond playback deadline will be no more requested. The blocks that have been played are buffered in the sliding window, and they can be requested by other nodes.
Every node periodically pushes all its neighbors a bit vector called buffer map in which each bit represents the availability of a block in its sliding window to announce what blocks it holds. Due to the announcement of the neighbors, each node periodically sends requests to its neighbors for the desired blocks in its exchanging window. We call the time between two requests a request period, or period for short, typically 1-6 seconds. Then, each node decides from which neighbor to ask for which blocks at the beginning of each request period. When a block does not arrive after its request is issued for a while and is still in the exchanging window, it should be requested in the following period again
Objective
Our goal is to maximize the average priority sum of all streaming blocks that are delivered to each node in one request period under heterogeneous bandwidth constraints.
Block Scheduling Problem
Here introduce the block scheduling problem in data-driven P2P streaming. Figs. 2 and 3 give intuitive examples of block scheduling problem, BSP for short. The two numbers beside the pipe of each node represent the maximum blocks that can be downloaded and uploaded in each request period, respectively, denoting the inbound and outbound bandwidth constraints of each node. The blocks close to each node illustrate what blocks the node currently holds. We compare the LRF scheduling strategy used and optimal scheduling in these examples. In Fig. 2a, node 4 asks for blocks from node 1, 2, and 3. In the LRF scheduling strategy , a block that has the minimum number of holders among the neighbors is requested first. If multiple neighbors hold this block, it is assigned to the one with the maximum surplus bandwidth in turn. As illustrated in Fig. 2a, using LRF, block 3 has only one holder, so it is assigned to node 3. Then, the surplus upload bandwidth of node 3 is reduced to 1. After that, block 2 is assigned to node 2 since the surplus bandwidth of node 2 is larger than node 1 and the surplus bandwidth of node 2 becomes 1. Next, LRF strategy assigns block 4 to node 1 whose surplus bandwidth then descends to 0.
Finally, after node 2 gets block 5, no more blocks can be further assigned. Fig. 2a shows the scheduling result using LRF. Four blocks are delivered. On the other hand, one optimal scheduling solution is illustrated in Fig. 2b, and five blocks can be delivered with a gain of 25 percent compared to LRF. In fact, using LRF method usually cannot derive the maximum throughput. As shown in Fig. 2a, the upload bandwidth at node 3 and download bandwidth at node 4 are not fully utilized. Fig. 3a shows another scenario that node 3 and 4 may competitively request blocks from node 1, that is, their requests are congested at node 1. However, node 4 has more options. The optimal way is that node 4 requests blocks from node 2, while node 3 requests from node 1, as shown in Fig. 3b. In fact, compared to LRF, random strategies would be even worse. Moreover, the real situation is more complex because the bandwidth bottlenecks are not only at the last mile but also different blocks have different importance.
Figure 2 Illustration of the block scheduling problem (I). (a) LRF scheduling. (b) Optimal scheduling
Figure 3: Illustration of block scheduling problem (II). (a) LRF scheduling. (b) Optimal scheduling.
To maximize the throughput of the system, our approach is to maximize the number of blocks that are requested successfully under bandwidth constraints as much as possible within every period.
First, we define some notations that are used in the formulation. We let N denote the set of all receiver nodes in the overlay. Let Ii,Oi represent the inbound and outbound bandwidth of node i, and let Eki represent the maximal end-to-end available bandwidth from node i to k. Since it is assumed that all the blocks have equal length, we let Ii, Oi, and Eik be measured in blocks per second for convenience. Meanwhile, we use Di to denote the set of all the desired blocks of node i in its current exchanging window. Let h denote whether node i hold block j. We assume that the size of the exchanging window is WT measured in seconds.
We let Ci and di j denote the current clock on node i and theplayback time, i.e., the deadline of block j on node i, respectively. Any desired block j of node i should satisfy
Ci < di j < Ci +WT , that is, in exchanging window. Table 1 summarizes the notations in the rest of this paper. In data driven protocol, different blocks have different significance.
For instance, the blocks that have fewer suppliers should be requested preemptively so that they can be spread more quickly. Accordingly, defining different priority for blocks is important. Two properties have been considered in our priority definition: since the previous empirical study has shown that "rarest first" is a very efficient strategy in data dissemination, the rarity property is considered first. While as streaming application has real time constraint, the second one we considered is the emergency property. A block in danger of being delayed beyond the deadline should be more preemptive than the one just entering the exchanging window.
Consequently, we define the priority for the single rate scenario.
Our target is to maximize the average priority sum of each node, so we have the following optimization
Constraint (a), guarantees that each block should be fetched from at most one neighbor so that no duplicate blocks are requested.
Constraints (b) and (c) ensure the block scheduling satisfy the inbound and outbound bandwidth capacity limitations, respectively.
Constraint (d) ensures the maximal end-to-end available bandwidth limitation.
Last, constraint (e) indicates this optimization would be a 0-1 programming problem.
Min-Cost Flow Problem
Given a flow network with source and sink , where edge has capacity , flow and cost . The cost of sending this flow is . You are required to send an amount of flow from s to t.
The definition of the problem is to minimize the total cost of the flow:
with the constraints
Capacity constraints:
Skew symmetry:
Flow conservation:
for all
Required flow:
and
A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximums. This could be called aminimum cost maximum flow problem. This is useful for finding minimum cost maximum matchings.
With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, you can do a binary search on d.
A related and more general problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. You do this by setting the lower bound on all edges to zero, and then make an extra edge from the sink t to the source s, with capacity c(t,s) = d and lower bound l(t,s) = d, forcing the total flow from s to t to also be d.
The problem can be specialized into two other problems
if the capacity constraint is removed, the problem is reduced to the shortest path problem,
if the costs are all set equal to zero, the problem is reduced to the maximum flow problem.
The minimum cost flow problem can be solved by linear programming, since we optimize a linear function, and all constraints are simple.
Apart from that, many combinatorial algorithms exist, for a comprehensive survey, see [1]. Some of them are generalizations of maximum flow algorithms, others use entirely different approaches.
Well-known fundamental algorithms (they have many variations):
Cycle Canceling: a general primal method.
Minimum Mean Cycle Canceling: a simple strongly polynomial algorithm.
Successive Shortest Path and Capacity Scaling: dual methods, which can be viewed as the generalizations of the Ford-Fulkerson algorithm.
Cost Scaling: a primal-dual approach, which can be viewed as the generalization of the push-relabel algorithm.
Network Simplex: a specialized version of the linear programming simplex method.
Figure 4: Min Cost Example
Figure 5: Min Cost Flow - Network Simplex Algorithm
Figure 6: Min-Cost Flow problem model
Such min-cost flow problem can be solved in polynomial time, and by double scaling algorithm. In our model, we let b(i)=0, for all I belongs to V and L(i,j) =0 for all arcs. We can start the transformation with the rules in Table , where rules (a) - (e) and (f)- (k), respectively, give the vertex and arc meanings. Applying these rules, we can transform global BSP into a corresponding min-cost flow problem, and we have the following theorem.
The optimal flow amount f(nki,bkj) of the corresponding min-cost flow problem on arcs (nki,bkj) is also an optimal solution to the global BSP.
In data-driven streaming, we decompose a node into its three roles: a send, a receiver, and a neighbor. We model each sender k as a vertex sk, each receiver i as a vertex ri, and each neighbor k of node i as a vertex nik. Further, we model a desired block j for node i as a vertex bij. Besides, we add two virtual vertices: a source vertex s and a sink vertex t. The decision variables for this problem are whether to request block j from neighbor k of node i, which we represent by an arc from vertex nik to vertex bij if block j is a desired by node i. These arcs are capacitated by 1, and their per unit flow cost is 0. And, we insert arc from vertex nik to bij to indicate that neighbor k of node i holds block j. To avoid duplicate blocks, we add arc capacitated by 1 from bij to ri and set the per unit flow cost as the priority of block j for node i multiplied a constant -1/[N].
Heuristic Distributed Algorithm
Distributed algorithm, each node decides from which neighbor to fetch which blocks at the beginning of its request period. As the request period is relatively short, such as 3 seconds, our scheduling algorithm should make a decision as rapidly as possible. Therefore, in the distributed algorithm, we do a local optimal block scheduling on each node based on the current knowledge of the block availability among the neighbors. The local optimal block scheduling can also be modeled as a min-cost flow problem. The sub-min-cost flow problem in the each rectangle is just the local optimal block scheduling.
However, one problem to do local scheduling is that each node does not know the optimal flow amount on arcs. In other words, we should estimate the proper upper bound of the bandwidth from each neighbor. For simplicity, here, we use a purely heuristic way for each node to estimate the maximum rate at which each neighbor can send blocks. Our approach is to use the historical traffic from each neighbor to do this.
