تسهیم جریان ویدیویی بهینه از طریق برنامه ریزی خطی

This paper presents a new optimal multiplexing scheme for compressed video streams based on their individual e-PCRTT transmission schedules. A linear programming algorithm is proffered, which takes into account the different constraints of each client. The algorithm simultaneously finds the optimum total multiplexed and individual stream schedules that minimize the peak transmission rate. Since the problem is formulated as a linear program it is bounded in polynomial time. It is shown that the algorithm succeeds in obtaining maximum bandwidth utilization with Quality of Service (QoS) guarantees. Simulation results using 10 real MPEG-1 video sequences are presented. The optimal multiplexing linear programming results are compared to the e-PCRTT and Join-the-Shortest-Queue (JSQ) procedures in terms of peak transmission bandwidth, P-loss performance and standard deviation. For several client buffer sizes, the rate obtained by our LP solution when compared to a previous e-PCRTT and JSQ methods resulted in reductions of 47% and 56%, respectively. This implies for a fixed rate problem that the proposed scheme can allow an increase in the number of simultaneously served video streams.

The main problem of transmitting compressed video over communication networks is its burst ness. Compressed movies exhibit peak rates that are often significantly larger than their long-term average rate. One of the suggested solutions for reducing burst ness is to use a playback buffer at the client side (PC, workstation, or set-top box). In such a system, the video streams are stored at a multimedia server and transmitted through the network to the client site. The client's video card then decodes the stream and forwards it to the video display. The server can significantly reduce the bandwidth requirements for transmitting stored video streams by prefetching frames into the client playback buffer. In order to compute an efficient server transmission plan, bandwidth-smoothing algorithms usually require a priori knowledge of the client buffer size, and the length of the transmitted video frames. Many kinds of video smoothing techniques [2], [21], [3], [5], [1] and [19] have been developed for reducing the bandwidth variability of video streams in order to improve network utilization. These techniques exploit client buffering and determine a smooth rate transmission schedule. The traffic management schemes for variable bite rate (VBR) videos fall into four main categories [17]: (1) deterministic without smoothing, (2) deterministic with smoothing, (3) probabilistic, and (4) probabilistic with collaborative prefetching schemes. In the first scheme [13] and [14], the original VBR traffic is sent into the network. Hence, for highly variable VBR traffic this scheme requires large initial delays to achieve moderate link utilization. The second scheme [4] and [6], sends a smoothed version of the original VBR traffic into the network. The video traffic is transmitted at different constant rates over different intervals according to a specific transmission schedule. The piece-wise constant-rate transmission schedule takes advantage of the fact that some of the prerecorded video can be prefetched into the client buffer. The challenge lies in computing those transmission schedules that have the smallest peak rate and rate variability while ensuring that the client buffer neither over- nor underflows. The probabilistic schemes send the original VBR encoded video into a non-buffered multiplexer [16] and [18]. This scheme introduces packets loss whenever the aggregate transmission rate exceeds the data link rate. The original traffic can be first smoothed before it is statistically multiplexed at a non-buffered link. The statistical multiplexing of the smoothed traffic increases link utilization at the expense of small packet loss probabilities. Reisslein and Ross [17] present a probabilistic transmission scheme with collaborative prefetching that determines the transmission schedule of an on-line connection as a function of the buffer contents at all the clients. It is shown that prefetching protocols with collaborative prefetching have less packet loss than the optimal smoothing algorithm [19] for the same link utilization. Using smoothing, one can represent a VBR stream as a series of fixed constant bit rates (CBRs), thus simplifying the allocation of network resources and increasing their utilization. This is the approach used by the piecewise constant rate transmission and transport (PCRTT) algorithm found in [17]. The difficulty of the PCRTT approach is that it treats each stream independently thus providing a sub optimal solution. An enhancement to PCRTT, called e-PCRTT, will be used in this paper. In this paper, we retain the CBR assumption, and propose a linear programming method, which treats all video streams collectively to obtain an optimal solution. In [22] the optimal smoothing algorithm is considered together with statistical multiplexing. Their investigation considers performance when small packet-losses are allowed. This scheme will provide not only statistical Quality of Service (QoS) guarantees, but provides increased system utilization. In parallel to smoothing algorithms there has been some work on developing schemes based on prefetching [16] and [18]. These protocols use VBR transmission, and can only provide statistical QoS guarantees. In [16], a protocol called Join-the-Shortest-Queue (JSQ) prefetching is presented which has many advantages compared to the other transmission schemes in the literature. JSQ achieves very high network utilization, facilitates user interactions, and has minimal start-up latency. Their experimental results showed that JSQ prefetching had a loss probability several orders of magnitude smaller than optimal smoothing [22] for the same buffer size and network utilization. Therefore, in this paper we compared our multiplexing results to the JSQ, which is considered to be the most advanced algorithm for video transmission multiplexing. Our purpose is to solve simultaneously the problem of individual smoothing and multiplexing of several video streams. Our method derives the transmission schedule for each individual stream by taking into account the interaction between streams, and optimizes the bandwidth allocation of the aggregated channel bandwidth. The main idea of the JSQ is to put a buffer in the client side, allowing prefetching of future frames when the transmission link is not fully utilized. The idea of video prefetching in JSQ is to keep the client's buffers as full as possible at all times, so that in intervals where the aggregate bit-rate exceeds the link capacity the user will not experience playback starvation. In our protocol the buffer is used to reduce the peak rate and the rate variability of the video sequence, and in some time intervals it will be almost empty. Another interesting work [18] also utilizes smoothing along with prefetching, but for the case where all video servers are distributed in a network environment. That work is actually an enhancement of JSQ for distributed environment, and not a centralized scenario where there is only one server as in our case. Our algorithm is planned to be implemented in a system where the program schedule is known in advance (prerecorded VBR sources), and not for real time situations such as Video on Demand (VoD). In our analysis we assume a network topology were all clients are physically separated but have the same buffer size. In our case, the optimization is done for a static situation, where it is known in advance all video programs that need to be transmitted in a common channel with maximum efficiency. So the complexity of the algorithm is not a critical issue here, because we can apply our algorithm off line. However, the system can be adapted to operate in a dynamic mode. One needs only to revise the transmission plan whenever a new demand is received. In addition, all our performance comparisons are done against “off-line” systems. The rest of the paper is organized as follows. In Section 2, the optimal multiplexing problem is defined. Section 3 presents the notation and the formal description of the problem. The conversion of the Multiplexed Problem to an upper bounded linear program (LP) is presented in Section 4. Section 5 deals with the influence of the total buffer size of all clients on the optimal solution, as well as a new LP formulation of the multiplexing optimal buffer allocation problem. Section 6 presents several small numerical examples using the proposed scheme. Section 7 provides LP solutions using ten real video streams. The LP, ePCRTT and JSQ solutions are compared using Ploss in Sections 8, respectively. The effect of the number of movies, and the linearizing approximation in the LP scheme is discussed in Section 9. Section 10 concludes the paper.

In this paper we proffer a linear programming formulation of the optimal multiplexing problem. Although there are several other approaches for solving this problem the advantage of the present approach are many. Linear programming is a well-known algorithm, easily understood, and readily available without the need for special coding. Our formulation accepts a linear approximation to the problem by partitioning the video streams into equal periods of length Δt. This approximation can be made more exact by decreasing Δt as desired. It will also accept an initial approximate solution to the program for further speedup. It is flexible, allowing the addition of constraints without the necessity of algorithm redesign. For example, if one wishes to add a bandwidth limit for each client, this can easily be done by placing an upper bound on the rate variables; rij. Sensitivity analysis is another advantage. For example, the shadow price of any individual buffer limit represents the marginal change of the optimal rate for an additional increment of buffer size. It also allows the investigation of varying selected parameters of the problem over their entire range through the use of parametric programming. This is demonstrated for the total buffer size parameter for both a small numerical example and for real video streams. It also, provides a framework for the future inclusion of multiple objectives, thus, tapping the power of multi-objective programming techniques. Finally, linear programming problems have been proven to belong to the class of polynomial bounded problems. The optimal LP multiplexing scheme has been applied to real MPEG-1 video sequences. These results are compared to the ePCRTT and JSQ procedure in terms of peak transmission bandwidth, ratio and Ploss performance measures. For several client buffer sizes, the rate obtained by ePCRTT was reduced by up to 60% by the LP solution, and compared to JSQ the LP procedure found peak rates by up to 68% lower. Future work includes consideration of the dynamic VoD environment, and a study of secondary measures and techniques for further smoothing of the rate function. In addition, we intend to investigate the effect of playback delay, and buffer size modifications to account for errors induced by the linear approximation and real-time usage of the LP method.