Transcoding Proxy With Communication Delay Ratio Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract- Diverse client devices differ in hardware, software and network connectivity.Each client requires specific content for efficient rendering of different versions of same data with high image resolution and high level of text summarization.Versatile Transcoding Proxy (VTP) architecture was proposed to transform the corresponding data or protocol according to the user's specification. Its effectiveness has been enhanced by adopting dynamic cache categories and by proposing the scheme Maximum Profit Replacement with Dynamic Cache Categories (DCC-MPR).From the weighted transcoding graph, caching candidate set is generated by the concept of dynamic programming and then cache replacement is performed. A version which helps in reducing the transcoding delay of other version is given the high priority. Based on the device capability and the user request, the corresponding transcoded version is sent either from cache or after transcoding them in case of absence of that version in the cache. Caching a version is done based on its popularity, size from which candidate set is generated. Cache replacement is done based on generalized profit.

Keywords- caching candidate set, weighted transcoding graph, generalized profit, Dynamic Cache Categories


The advancement in the field of mobile communication technology led the users of mobile communication to access the Internet at any place and at any time through any mobile device. These mobile devices are heterogeneous and so they differ in everything from components to the computing capability. Also the bandwidth of mobile communication is limited and hence the traditional content of a web object for desktop computers might not be suitable for a mobile device. Hence, there is a desire to transcode the content to a degraded format that is more appropriate to be presented on the mobile devices

Transcoding is the process of converting media file or object from one format to another. Transcoding is often used to convert video formats (i.e., Beta to VHS, VHS to QuickTime, and QuickTime to MPEG). But it is also used to fit HTML files and graphics files to the unique constraints of mobile devices and other Web-enabled products. These devices usually have smaller screen sizes, lower memory, and slower bandwidth rates. In this scenario, transcoding is performed by a transcoding proxy server or device, which receives the requested document or file and uses a specified annotation to adapt it to the client.

Transcoding systems can be divided into three classes according to the location where the Transcoding process takes places, i.e., the client-based, the server-based, and the proxy-based transcoding systems. In the client-based approaches, transcoding is left for mobile clients for considerations. The advantage of this approach is that it can preserve the original semantic of system architecture and transport protocols. It is noted that transcoding at client side is costly due to the limitation in both bandwidth and computing power. On the other hand, transcoding at server side is not flexible to satisfy the client's requirement and will require too much unnecessary storage. An intermediate proxy is able to on-the-fly transcode the requested object to a proper version according to the client's specification before it sends this object to the client. Thus, the transcoding system is often implemented at an intermediate proxy.

Conventional transcoding proxies can be further divided into two different classes according to the way how the transformation logic is applied. The first class is referred to as the fixed transcoding proxy, where the transcoding proxy merely transcode the input into the output without any context-aware processing. The second class is referred to as the heuristic transcoding proxy, which is able to read the capability profile from the client device and tries to transform the content according to the device capability.

However, since the proxy does not have any knowledge about which information is important, it is difficult to determine the transformation strategy of the content in case of heuristic approach. Although recent researchers have proposed various heuristics, these heuristics still suffer from the loss of important information or the loss of opportunities for better transcoding. Both the fixed Transcoding proxy and the heuristic transcoding proxy belong to monolithic transcoders, meaning that they can only provide Transcoding services to the content type or the protocol which can be recognized in advance. When there is a desire to deal with a new content type or a communication protocol, the upgrade of the whole architecture is inevitable. This consideration makes it rather difficult to maintain the transcoding proxy system.

The architecture of versatile transcoding proxy (denoted by VTP) for Internet content adaptation has been proposed .In this framework, the proxy can accept and execute the transcoding preference script provided by the client or the server to transform the corresponding data or protocol according to the user's specification so that the proxy server can avoid the uncertainty of the heuristic transcoding proxy. VTP architecture can also be used to transcode many types of client-server systems, with the registration of the standard CC/PP (Composite capabilities/preferences profile) device capability profile and built-in CC/PP parser the proposed versatile Transcoding proxy realizes context awareness. Therefore, it is adaptable to heterogeneous devices.

Existing media caching systems treat each client request equally and independently. Various different bit-rate versions of the same video clip may be cached at the proxy at the same time, which is a waste of storage. Moreover, to enhance the effectiveness of the VTP architecture, a transcoding scheme DCC-MPR is proposed to maintain the cached objects and perform cache replacement in the transcoding proxy. Two important components are contained in scheme Maximum Profit Replacement with Dynamic Cache Categories (DCC-MPR): mechanism DCC and algorithm MPR.

Scheme DCC offers fine granularity control in the number of cache categories by building a weighted transcoding graph which depicts the transcoding relationship among transcodable versions dynamically. From the transcoding relationship among categories, algorithm MPR performs cache replacement according to the content in the caching candidate set, which is generated by the concept of dynamic programming.

Algorithm MPR can be divided into two phases. The first phase performs when the proxy has sufficient space. In this phase, once the object is queried, it will be cached to increase the profit for future access. The second phase performs when the proxy has insufficient space. In this phase, the cache replacement is performed according to the priority of the requested object.

Cache replacement algorithm based on a generalized profit function has been included. It is to evaluate the profit from caching each version of an object. This generalized profit function explicitly considers several new emerging factors in the Transcoding proxy and the aggregate effect of caching multiple versions of the same object. It is noted that the aggregate effect is not simply the sum of the costs of caching individual versions of an object, but rather, depends on the transcoding relationship among these versions. The notion of a weighted transcoding graph is devised to evaluate the corresponding aggregate effect efficiently.

Utilizing the generalized profit function and the weighted transcoding graph, we propose, in this paper, an innovative cache replacement algorithm for transcoding proxies. In addition, an effective data structure is designed to facilitate the management of the multiple versions of different objects cached in the transcoding proxy. It is shown that the algorithm proposed consistently outperforms companion schemes in terms of the delay saving ratios and cache hit ratios. The feasibility of such a differentiated service scheme depends on the availability of a range of variations for the content so that the server can choose the correct variation given request conditions, while the content provider can manually provide a number of different variations for use by the system.

The rest of this paper is organized as follows. In Section II, we introduce some related previous works. In Section III, we present the details of designing the VTP architecture, and discuss the advantageous features and the usefulness in the server transcoding preference application. In Section IV, design of scheme DCC-MPR is described. Section V includes the experimental evaluation of the scheme. Finally, this paper concludes with Section VI.


Proxy Caching for Video-on-Demand Using Flexible Starting Point Selection [2] assumes that the connection between the clients and the proxy is characterized by high transmission rate and low latency. If the requested video content has already been accessed by one user and is cached on the proxy, the initial delay for the second and later users is significantly decreased compared to the case when content has to be loaded from the remote server.

New Stream Caching Schemas for Multimedia Systems [11] proposed a new multimedia caching strategy that includes several optimizations to the state of the art. This algorithm takes its roots from the interval caching algorithms but it evolves towards a more adaptive approaching that could obtain a better performance for variable bit-rate streams and serving media stored on multiple disks following different distributions.

QoS-Adaptive Proxy Caching for Multimedia Streaming over the Internet [15] proposed a media characteristic-weighted replacement policy is proposed to improve the cache hit ratio of mixed media including continuous and noncontinuous media. Secondly, a network-condition- and media-quality-adaptive resource-management mechanism is introduced to dynamically re-allocate cache resource for different types of media according to their request patterns.

A pre-fetching scheme is described based on the estimated network bandwidth, and a miss strategy to decide what to request from the server in case of cache miss based on real-time network conditions is presented in [15]. Request and send-back scheduling algorithms, integrating with unequal loss protection (ULP), are also proposed to dynamically allocate network resource among different types of media. The prefix of a multimedia stream is stored in the proxy in advance. Upon receiving a request for the stream, the proxy immediately initiates transmission to the client while simultaneously requesting the remaining portion from the server. In this way, the latency between server and proxy has been hidden.

A QoS-adaptive miss strategy and pre-fetching algorithm that fully consider the continuous- and non-contiguous-media characteristics are also described in [15]. A weighted request scheduling scheme that efficiently allocates the network resource between proxy and server among different type of requests together with a send-back scheduling scheme that efficiently utilizes the network resource between client and proxy based on media characteristics are proposed and analysed .

To maintain inter relationship among cache items and to perform cache replacement RESP (Replacement with Shortest Path) [7] framework has been framed. It contains two primary components, i.e., procedure MASP (standing for Minimum Aggregate Cost with Shortest Path) and algorithm EBR (standing for Exchange-Based Replacement). Procedure MASP maintains the interrelationship using a shortest path table, whereas algorithm EBR performs cache replacement according to an exchanging strategy. To maintain the transcoding graph, procedure MASP uses a table to record the shortest path information and determines the transcoding sources according to the table. To perform cache replacement, algorithm EBR uses a more profitable caching candidate to exchange less profitable elements in the cache so as to maximize the profit of cached elements. The experimental results show that the proposed RESP framework outperforms algorithm AE in cache hit ratio. Under many circumstances, the RESP framework can approximate the optimal solution very effectively. Moreover, the RESP framework costs much less computing complexity in processing user queries.

We compare the proposed DCC-MPR to the algorithm AE adopted in [14]. During the experiments, unlike the various metrics used in [14], we choose the tightest one, the exact hit ratio, to validate the performance of DCC-MPR. The exact hit ratio is defined as the fraction of requests which are satisfied by the exact versions of the objects cached. This metric is also motivated by the fact that we usually intend to provide an exact version to users (rather than an overqualified one) for effective bandwidth use. Since the comparison between AE and other schemes has been made in [14], we focus on comparing the performance between DCC-MPR and AE in this paper.

Cache Replacement for Transcoding Proxy Caching [10] addresses the problem of cache replacement for transcoding proxy caching. An efficient cache replacement algorithm is proposed. That algorithm considers both the aggregate effect of caching multiple versions of the same multimedia object and cache consistency. If the cache size is large enough, the problem becomes trivial since all objects can be stored in the cache such that the total access cost is minimized. As a result, cache replacement algorithms are used to determine a suitable subset of web objects to be removed from the cache to make room for a new web object.

Existing cache replacement algorithms cannot be simply applied to transcoding proxy caching because of the new emerging factors in the environment of transcoding proxies, such as the additional delay caused by transcoding, different sizes and different reference rates for different versions of a multimedia object, and the aggregate effect of the profits of caching multiple versions of the same multimedia object. An efficient cache replacement algorithm for transcoding proxies, AE in short, which selects objects to remove from the cache based on their generalized profit function one by one. When one object is removed from the cache, the generalized profits for the relevant objects will be revised. If the free space cannot accommodate the new object, another object with the least generalized profit is removed until enough room is made for the new object. However, this method is not optimal when there is more than one object to be removed.


Versatile Transcoding Proxy architecture consists of the three primary components: the service agent, the transcoding agent and the Transcoding Preference Script (TPS). TPS controls the behaviour of the VTP (Versatile Transcoding Proxy) server. TPS is used to determine the property of a device, and ask the associated software agents to provide the suitable parameters for transcoding. Transcoding agent is responsible for the transcoding actions that are taking place. Transcoding agent takes decisions based on the TPS. Service agent gets the TPS and decides on the object that is needed to be transcoded. Weighted transcoding graph depicts the transcoding relationship among the transcodable versions. Caching Candidate sets are selected by using the dynamic programming algorithm. MPR algorithm consists of two phases two phases. In Phase I, Proxy has sufficient space to cache the requested item. In Phase II, Proxy has insufficient space to cache the requested item.

The server contains database in which all the required details of a file are stored. The original object resides in server. The proxy selects files to be cached in an optimized way by using dynamic programming. Those files that are selected are referred as caching candidate set. Few of these files from this set are loaded into cache based on the cache size. This set contains files that have maximum profit. User request is handled by agents and the proxy uses dynamic cache replacement algorithm for maintaining the cache efficiently. The agents reads TPS and communicate with each other to make a decision .The requested file is delivered to user if cache hit occurs. In case of cache miss and if the file is indexed in candidate set, the space in cache is compared with requested file size. If sufficient space exists then the file is loaded into cache from server and hence the user request is satisfied. In case of insufficient space this algorithm chooses file from the cache which has lowest generalized profit and replaces it with requested file if the space in cache is sufficient to accommodate the requested file. If not, again the file with the lowest generalized profit is removed until the space in cache becomes sufficient to cache the requested file and then delivered to user. In this case if file is not indexed in cache request to server is sent and if it positive the same constraints as above is done. But the file that has been newly transcoded will not be stored in cache but in buffer and its details will be maintained by server for future storage. Thus the new object in buffer will have its details stored in server database and is then stored in cache if it reaches high profit and the cache is dynamically changed.

A. Server Maintenance:

Server possess database in which the file name, size, profit, weight to transcode are stored. The original file is stored in database. The weighted transcoding graph contains graph in which the object and its weight to transcoded is maintained. This graph is dynamic as it updates when a new object is added or removed to it. Candidate set is selected by traversing the graph and including profit of each file. The dynamic program provides an optimum solution for this.

B. Proxy:

The candidate set is maintained in cache which has index for the files that are having high profit to be cached then. Cache will store files of high priority. Service agents read user profile and directs transcoding agent to perform transcoding if needed. Service checks looks for cache hit and invokes MPR in case of cache miss. Transcoding agent will transcode if the requested object could not be found by service agent. Then service agent will serve the request then.

C. Client:

TPS script from the client is obtained to get profile based in which agents performs its functions. After processing client request client will view object through player created using JMF.


In this section, we describe the modified scheme DCC-MPR to maintain the cache categories of a transcoding proxy dynamically.

Fig. 1 Overall Architecture

Section IV-A, includes the mechanism of the weighted transcoding graph and the relevant procedures. Based on the profits of the versions of each object, the dynamic programming algorithm is proposed in Section IV-B.

In Section IV-C, the modified Maximum Profit Replacement Phase-I algorithm is proposed for a transcoding proxy to perform cache replacement. The database D is regarded as the collection which contains all possible objects and relevant versions. For each object i, the number of transcodable versions, i.e., the categories, is denoted by ni. The original version of object i is denoted as Oi,1, whereas the least detailed version which cannot be transcoded any more is denoted as oi,ni .

Weighted Transcoding Graph Generation

Weighted transcoding graph is used to represent the transcoding relationship among the various transcodable versions of an object. Transcoding cost of a version is the weight associated with that version. Transcoding relationship will be updated simultaneously as and when the versions are added. The weighted transcoding graph, Gi , is a directed graph with weight function wi . Gi depicts the transcoding relationship among transcodable versions of object. Each vertex v E V [Gi ] represents a transcodable version of object . In order to maintain dynamic cache categories, three procedures, i.e., AddCate(Gi) , RemoveCate(Gi ) , and

GetSubgraph(Gi,V') are defined.

­­­­ Caching Candidate Set Selection

Caching candidate set has the objects or the versions of the objects that are profitable to be cached. The caching candidate set is selected by using the dynamic programming algorithm. The caching Candidate set selection is done using the dynamic programming. The candidate set is chosen based on dynamic program to get an optimized solution set. The case is similar to a knapsack problem. A set of files having small size and high profit to be cached in a specified cache size must be selected. The algorithm picks every object and their versions and tries to fit with different cache sizes. The cache size is varied from minimum to maximum and the candidate set is obtained by tracing the objects that fits in the maximum cache size after their size and profit being compared. The singular profit for a version is taken if there are no other versions of the object are cached. The marginal profit is taken if any other version of the object is cached. The obtained candidate set is then ranked. The symbols used in this section are given in Table I.For a given weighted transcoding graph Gi, the profit functions including the singular profit, aggregate profit, marginal profit and generalized profit, are defined as follows:

Definition 1: PF(oi,j) is defined as the singular profit of caching while no other version of object is cached

where E×€Gi×€ represents the collection of all edges in graph Gi. It is noted that the reference rate ri,x reflects the popularity, whereas the term (di + ωi(1, x) − ωi(j, x)) is regarded as the delay saving.

Definition 2: PF(oi,j1, oi,j2,…, oi,jk)is defined as the aggregate profit of caching at the same time (oi,j1, oi,j2,…, oi,jk) at the same time

Where G'i is the subgraph derived from the procedure GetSubgraph (G'i,{oi,j1,oi,j2,…,oi,jk}).

Definition 3: PF(oi,j,oi,j1, oi,j2,…, oi,jk)) is defined as the marginal profit of caching oi,j , given that oi,j1, oi,j2,…, oi,jk are already cached where j≠j1,j2,..jk.

PF(oi,j|oi,j1,…,oi,jk) = PF(oi,j,oi,j1,oi,j2,…,oi,jk) - PF(oi,j1,oi,j2,…,oi,jk)

Definition 4: The generalized profit, gi,j , of the object oi,j is defined as gi,j = pi,j / si,j .In order to determine the items which should be cached in the transcoding proxy, we define the caching candidate set, denoted by DH. The caching candidate set DH, which is a subset of D contains the items with high priority to be cached.

Definition 5: The total profit of DH, denoted by PH, is defined as the summation of the profit of all data items, including the original and transcoded ones, in DH. The total size of DH, denoted by SH, is defined as the summation of the object size of all data items in DH.

Candidate set selection algorithm includes the cache size constraint, Zc and the database D as input. This procedure is based on the profit calculated for the various versions of the objects. The caching candidate set, DH is the output got as a result of this algorithm.

The dynamic programming algorithm used to select the caching candidate set is below:

Procedure DP

Input: Database D cache size constraint Zc

Note that |D| = m* n, where there are m kinds of objects and n= max{ni}

Output: caching candidate set DH

Create two dimensional (m*n+1)*(Zc+1) array c[][]

for i =1 to m

for j =1 to n

for z =1 to Zc

if si ≤ z

if pi,j + c[(i − 1) - n + j − 1][z - si] >

c[(i − 1) - n + j − 1][z]

c[(i − 1) - n + j][z] =

pi,j + c[(i − 1) - n + j − 1][z - si]


c[(i − 1) - n + j][z] = c[(i − 1) - n + j − 1][z]


c[(i − 1) - n + j][z] = c[(i − 1) - n + j − 1][z]



Modified MPR Algorithm Phase-I

The modified Maximum Profit Replacement algorithm has two phases: Phase I deal with the sufficient space in the cache whereas Phase II deals with the insufficient space in the cache. When a particular object is to be cached, the cache space is checked before it is cached.Flow of MPR Phase I is shown in Fig. 2.

Fig. 2 Flowchart of modified MPR algorithm PhaseI

MPR Phase I include the various decisions making based on the conditions that are met. The conditions include cache hit and cache miss. The cache hit occurs when the object requested by the client is present in the cache and the Cache miss occurs when the object requested by the client is not available in the cache. So an object has to be put into the cache for serving the client request. The cache space is compared with the size of the requested object. If the remaining available cache space is sufficient then the requested object is cache.

When cache miss occurs, a decision is made either to download the required version directly from the server or to download the original object to get the required version by means of transcoding. So a comparison is done between time to fetch the required version and time to download the original object, time to transcode it and a decision is made for the one having low value. After getting the required version, check if it belongs to the candidate set and check the cache space and cache it if sufficient space is found and the serve it to the client. If it does not belong to the candidate set and sufficient space is found, cache it and serve to the client and now it belongs to the non candidate set.

Modified MPR Algorithm Phase-II

If there is no sufficient space for caching the required version replacement is done. The non candidate set object having low GP is removed and it is cached and this replacement is continued until the required version finds sufficient space or the non candidate set goes empty. If the non candidate set empties and if there is no enough space for required version which does not belong to candidate set it is returned to the client without caching it. If the non candidate set empties and if there is no enough space for the required version which belongs to the candidate set, the GP of cached candidate set is compared with this. If the cached candidate object's GP is less than the required version replacement, that object is removed and the required version is cached. This is done until sufficient space is found for required version or required version's GP is higher than the cached candidate set's object to get sufficient space. The Flow of MPR Phase II is shown below in Fig.3.

Fig. 3 Flowchart of modified MPR algorithm PhaseII


The evaluation of the proposed scheme was done for the various video formats like AVI (Audio Video Interleave), MPEG (Moving Pictures Expert Group) and QuickTime format. The experiment involved about 100 video files of varying file extensions like .avi, .mpg and .mov and with varying sizes.

VI. Conclusions

In this paper, modified Maximum Profit Replacement with Dynamic Cache categories (DCC-MPR) is proposed. DCC MPR provides dynamic cache categories and also does the replacement of the objects in the cache. The modified DCC MPR performs cache replacement according to the content in the caching candidate set. The caching candidate set is generated using the dynamic programming concept, which is based on the weighted transcoding graph. Weighted transcoding graph is generated and updated dynamically upon addition and deletion of the versions. Modified DCC-MPR has better performances in many aspects compared to the DCC-MPR scheme in conventional transcoding proxy system.