{'fraction_non_alphanumeric': 0.021060346933789397, 'fraction_numerical': 0.004397752259956022, 'mean_word_length': 4.794450736126841, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Client-Assisted Patching for Multicast Video-on-Demand Service in an Enterprise Network

Video-on-demand services allow users to select their desired video without watching the broadcast. Videos are stored in distributed servers. A single stream from the server can be utilized to satisfy a batch of common client requests. The key problem of this system is to minimize the server load to satisfy maximum number of clients. We propose a distributed client-side caching technique that reduces the server load significantly and increases the scalability of the system. We have implemented our system and compare our system with another state-of-the-art technique. Experimental results suggest that the newly proposed system outperforms the already proposed client assisted patching scheme.


Introduction
Video on demand (VoD) provides customers with informative and entertaining streams of multimedia and video information. A multicast VoD system (termed as Near VoD service) allows clients to share a server stream by batching their requests [1], and hence, improves channel utilization. The key idea is to avoid transmitting the same packet more than once on each link of the network by having branch routers duplicate and then send the packet over multiple downstream branches. Multicast can alleviates the workload of the VoD server and improves the system throughput by batching requests and reduces the required network bandwidth significantly, thereby decreasing the overall network load. It offers high scalability which, in turn, increases the system capacity to house large number of clients and provides considerable cost/performance benefits. However, it increases initial service latency that may cause some impatient customers to renege. Patching is a multicast technique that enables a server to transmit only the beginning of the entire video data to clients and ensures that clients download the rest data of the video from an ongoing stream [2]. By making multiple clients share an ongoing stream, Patching can reduce server network bandwidth requirements for True VoD (TvoD) services. Double Patching [3] ensures that a long patching stream delivers not only essential data for the current client but also extra data for future clients, so it significantly reduces the total amount of video data delivered by all streams. Patching eliminates the service latency imposed by the Batching scheme. The objective of Patching is to substantially improve the number of requests each channel can serve per time unit, thereby sufficiently reducing the per-customer system cost. In Patching scheme channels are often used to patch the missing portion of a service or deliver a patching stream, rather than multicasting the video in its entirety. In Patching, a client might have to download data from both regular multicast and patching channels simultaneously. However, Patching temporarily puts a heavy load on the servers as patching streams are dedicated to the patched clients. Client Assisted Patching (CAP) [4] uses client side cache to reduce the server load. In this approach, all patching channels are provided by the cooperative clients rather than the server itself. Thus, the system alleviates server load and the conserved bandwidth can be used to satisfy more multicast groups. It also increases the throughput and scalability of the system. The minimum buffer requirement in the intervals is same as the conventional patching scheme requires. Client Assisted Patching technique is illustrated in Figure 1. The patching stream is released when the missing portion is made up and the client will continue with the regular stream until the end of the session.
Client Assisted Patching reduces the server load by using the client side cache. However client cache is limited and only a small portion of the video can be stored in a single client to patch. In this paper, we have proposed Distributed Client-Assisted Patching (DCAP) where different clients will store different portion of the movie unlike the standard client-assisted system. Thus the system can provide a larger amount for patching instead of only the beginning portion.

Related Research Work
An adaptive logic designed to support multicast constraints at the client side is illustrated in [5]. A broadcast based network coded technique that allows the implementation of multicast VoD system utilizing a single serve channel is presented in [6]. Multicast VoD has good scalability and excellent cost/performance efficiency (See [7] for an excellent survey of multicast VoD services). However, it is difficult to support VCR-like interactivity with multicast VoD and, at the same time, improve service efficiency. There are several proposals [8]- [10] to solve this problem. One of the earlier periodic broadcast schemes was the Equally-spaced interval Broad casting [1]. Since it broadcasts a given video at equally-spaced intervals, the service latency can only be improved linearly with the increase of the server bandwidth. To significantly reduce the service latency, Pyramid Broadcasting (PB) was introduced in [11]. In PB, each video file is partitioned into the segments of geometrically-increasing sizes, and the server capacity is evenly divided into K logical channels. This ensures a smaller waiting time for every video. Some other works [12], [13] are also discussed in the literature to address different issues of periodic multicast VoD services. Cooperative client approach is recently proposed approach that relies on the cooperation of the video clients in forming an overlay network over which the video is propagated [14], [15]. To eliminate the service latency of batching, several dynamic multicast techniques have been proposed in [15]- [18]. Given that there is an existing multicast video, when to schedule another multicast for the same video is crucial.
The time limit, up to when a newly arrived client will be patched after a multicast session starts, is called

Journal of Computers
patching window [15], [19]. Some modifications of patching technique are discussed in [17], [20]. Two simple approaches of setting the patching window are discussed in [15]. The first one uses the length of the video as the patching window. That is, no multicast is initiated as long as there is an in-progress multicast session for the video. This approach is called the Greedy Patching because it tries to exploit an in-progress multicast as much as possible. However, over-greed can actually reduce data sharing [15]. The second approach, called the Grace Patching, uses a patching stream for the new client only if it has enough buffer space to absorb the skew. A multicast technique that completely prevents a server from transmitting unnecessary video data like double patching and uses four types of streams: regular stream (R-stream), patching stream (P-stream), short patching stream (S-stream) and linking stream (LK-stream). An R-stream, an S-stream, multicast window Wm and patching window Wp in the proposed XP4S [21]. Range Multicast is a new communication paradigm for VoD applications [18]. This scheme is a shift from a conventional thinking about multicast where every receiver must obtain the same data packet at all times. Client-to-client streaming scheme for VoD application [22] presents a technique to cooperatively stream the video using chaining technique with unicast communication among the clients. An enhanced client-centric approach for efficient video broadcast is described in [23]. P2Cast-an architecture that uses a peer-to-peer approach to cooperatively stream video using patching techniques, while only relying on unicast connections among peers. MegaDrop [24] is a fully decentralized VoD service via P2P techniques.
The MegaDrop system not only takes active peers into consideration but also provides mechanisms for discovering inactive peers that contain desired media objects. A Zero Delay Video-on-Demand Scheme is a technique proposed to solve the server delay of high-performance static streaming scheme [25]. It contains the outstanding thoughts from two efficient schemes: GEBB and patching scheme. P-chaining proposes a service scheme based on chaining [26], in which clients as well as the server provide streaming services. In the proposed scheme, services are provided by unicast and managed locally using node lists. Proxy-assisted scalable periodic broadcasting of videos for heterogeneous clients is proposed in [27]. This scheme is proposed to significantly reduce the waiting time of all heterogeneous clients, without the need for any additional backbone bandwidth.

Distributed Client-Assisted Patching
It has already been mentioned that Client Assisted Patching [4] reduces the server load by using the client side cache to store the initial portion of the movie. In this approach, all patching channels are provided by the cooperative clients. Thus, the system alleviates server load and the conserved bandwidth can be used to satisfy more multicast groups.
The patch window during the multicasting is defined by the duration when a particular client can join the multicast group. Generally to get the True VoD (TVoD) service a new multicast session is initiated at the end of patch window duration. The number of users in a multicast group depends on the size of window. If the window size is increased we can have less number of simultaneous multicast sessions for a particular video stream and the server load will be decreased. This decreased server load could be utilized for other streams (e.g., movies) to attract more users with increased revenue. But increased window size requires larger buffer in the clients and client buffer is limited. So storing the same portion to all clients can provide only a limited portion as patch to other clients. If the storage required for storing the initial portion of the movies can be distributed among a group of clients then it is possible to support a larger window size with the same amount of buffer in the clients. Thus it requires less buffer and a large multicast group can be supported with the same network bandwidth.
The Distributed Client Assisted Patching technique applies the idea of storing the initial portion of the session among the participating clients. Some observation about the new scheme can be described as

Journal of Computers
follows if the patching window is doubled (i.e., 2W instead of W) keeping the client buffer for patching W:  The clients are allowed to join an ongoing multicast session with in 2W time from the beginning of the session. Where W is the patch window in client assisted patching. Thus the effective patching window is doubled.
 Each client in a multicast session will store a portion of the video with length W depending on its arrival time. The distribution policy is described in the later section.
 If a client requests for a movie after starting of multicast session the ADC (Admission Controller, accessible through network) will select one or two patch parents for the client. Different parts of the patching stream may be supplied by different clients.
 In the new scheme the patch streams are distributed among the clients. It means that a client will not store the whole patch stream and the ADC must find multiple clients for patching. The main problem here is the reduced probability of finding a patch client. Thus in some cases waiting time will be increased and the percentage of served will be decreased. But as we are getting larger patch window we can effectively get more clients to be served with single movie stream.

Distribution Policy
In our proposed system each client in a multicast session will store a portion of the initial part of the movie with length W depending on its arrival time. The distribution policy of the part of the movie to be stored in patched clients is described in the following table.

Analysis for Server Bandwidth Requirement
In our analysis we will refer to the amount of data in terms of their play back duration. Let us assume both batching and patching be combined in this system. It is also assumed that batching and patching window window size is WB and WP respectively and all clients have enough buffers to store necessary patch stream.
During the patch window of a particular multicast session there will be only one regular multicast stream transmitted by the server. The rest will be patched by the client. During the batching no new clients will be served and they will get the stream in the next multicast session. So the total data delivered by the server during one multicast session for the ith movie Mi is where, i L is the length of the i-th movie i M . The patch streams for the late clients will be provided by the cooperative clients.
If k patching streams are initiated between t and t+Δt, then total data transmitted by k patch stream can be approximated as kt if Δt is negligible. If the probability of initiating k patch stream during Δt is P(k, Δt) then the total data delivered by the clients between t and Δt is  To determine the expression of the probability we assume that the multicast initiation process is Poisson with rate λ. The probability density function is , where x indicates the first time of the patch client arrival and fx indicates the probability that the first client arrives at time x. Now we can . Dc can be derived as follows: If we set Δt equals to 1 second then we get Since the client request rate is λ, the patch window is Wp and the batch window is WB the mean interval between two multicast group is τ = WB +Wp. Now consider N multicast session in a time interval T.
. Total data stream supplied by these N streams will be Dst = N L avg  Thus the server bandwidth requirements = Again the patching by the client will be continued within patch window Wp. So the link bandwidth required for patch streams which is provided by the clients to other clients can be measured as where b is the video play back rate and Lavg is the average movie length. If we represent the patch window of Client Assisted Patching as Wcap we can write From Equation (2.4) we can see that the server bandwidth requirement is inversely proportional to the patch window. So the larger the patch window the less will be the requirement of server bandwidth. Again distributed Client Assisted Patching supports a patch window that is double of the patch window supported by the Client Assisted Patching system. So we can say that our system saves about 35% bandwidth than that of Client Assisted Patching if WB=Wcap.

Complexity Analysis
The complexity of Admission-Control in Client Assisted Patching is O(sE log V + m 2 + ncE log V + n 2 c E) which is the sum of the complexity of two threads Batched-Requests-Processing and Online-Requests-Processing and the procedure Init-Admission-Controller. Here, s, m, V, E, nr, and nc indicates number of servers, movies, nodes, edges, clients seeking admission and clients already admitted respectively. Here admission controller invokes the procedure selectPatchingParent once to get a single

Journal of Computers
patch parent. Thus the highest order term in the time requirement to execute the procedure is nc 2 E. But in the Distributed Client Assisted Patching it requires two patch parents. The first parent will provide the first part of the required patch and the second parent will provide the rest. So the admission controller has to invoke the procedure selectPatchingParent twice to get two different patch parents. Thus the highest order term in the time requirement to execute the procedure will be 2nc 2 E. So the total time complexity of the proposed system can be described as: O(sE log V + m 2 + ncE log V + 2nc 2 E).

Performance Study
We study the behaviour of our approach and evaluate its performance based on the simulation results. We simulate Distributed Client Assisted Patching using Parsec, a C-based parallel discrete event simulation language. We also simulate Client Assisted Patching to make a comparison between our approach and Client Assisted Patching on various metrics. The same simulation settings has been used and the same assumptions were made as mentioned in [4].

Comparison with Client Assisted Patching
In Fig. 2 we observe that distributed scheme outperforms the Client Assisted Patching scheme as the distributed Client Assisted Patching scheme provides the scope of more patching streams. From the figure we observe that for the server with higher bandwidth and low request rate the percentage served is almost 100% for both the schemes. But when the server bandwidth is very low with high request rate both the system will perform worse as there will be contention for resources.  It is observed from Fig. 3 that percentage of patching degrades with the increase in request rate. For a system with low server bandwidth there will be less number of multicast movie streams and the large number of clients will be competing for patching. This will create contention in link bandwidth and the clients will be rejected for patching when there are not enough resources in links. We do not observe this degrading behaviour of the percentage of patched clients in Fig. 4 as there are sufficient resources. Here we observe that when both the systems have enough server bandwidth Distributed Client Assisted Patching performs 30% better (on the average) than the client assisted patching as this new system provides a larger patching window. When the available server bandwidth is lower as shown in the Fig. 3 the performance of the Client Assisted Patching further degrades where as our system shows almost the same performance as before. Fig. 5 shows that the average waiting time increases with the increase in request rate. An environment with higher request rate makes shortage of resources. So some clients may need to wait for the necessary

Journal of Computers
resources. Actually the lack of server bandwidth may not allow frequent batching for a multicast movie stream and clients need to wait for a long time to get available resources. This waiting time for batching plays a significant role in average waiting time. The Distributed Client Assisted Patching overcomes this problem by allowing the broader scope of patching and hence reduces the average waiting time which is observed in the figures.
From Fig. 6 we can see that our scheme needs about 25% less bandwidth than that of Client Assisted Patching on the average. This is less than the mathematical analysis presented earlier. The main reason behind this is the patch clients which were served directly from the server. We also see that Conventional Patching scheme requires huge bandwidth compared to other two schemes because in conventional patching all patch streams are provided from the server.
As per complexity analysis presented in Section 3.3 Distributed Client Assisted Patching needs more computation to find a patch parent than Client Assisted Patching. This is observed in our simulation results as shown in Fig. 7. The quadratic pattern of time requirement curve justifies the complexity analysis expression.

Conclusion
Since streaming of any multimedia object like high quality video consumes a significantly large amount of network resources, network bandwidth limitation is the major constraint in most of the multimedia systems. Multicast Video on-Demand (MVoD) systems with Patching are scalable and cheap-to-operate. To optimize system performance, over the past few years extensive research has been done on MVoD. Even though the significant progress has been made, it is still regarded as challenging research domain in VoD service. In our proposed Distributed Client Assisted Patching a client gets a larger amount of patch stream from two different patch parents. Thus our system provides larger patch window.
The mathematical analysis and simulation results reveal that the new scheme performs better in terms of number of served requests and bandwidth requirements for servers with expense of additional computation time to find one additional patch parent. It can be shown mathematically that increasing the patch window decreases the server bandwidth requirement. But increasing patch window (even if the clients have the higher capacity) makes it difficult to find the patch parents and there is a chance of overloading the network. Finding the optimal patch window size is a potential future in the area of Video on Demand.