9603853
COPACC: A Cooperative Proxy-Client Caching System for On-Demand Media Streaming
Proxy caching is a key technique to reduce transmission cost for on-demand multimedia streaming. However, its effectiveness is limited by the insufficient storage space and weak cooperations among proxies and their clients. In this paper, we propose COPACC, a novel cooperative proxy-and-client caching system that combines the advantages of both proxy caching and peer-to-peer (P2P) client communications. We propose a comprehensive suite of protocols to facilitate the interactions among different network entities in COPACC. We also develop an efficient cache allocation algorithm to minimize the aggregated transmission cost of the whole system. Simulation results demonstrate that COPACC achieves remarkably lower transmission cost. Moreover, it is much more robust than a pure P2P system in the presence of node failures.
18232832
Tree-assisted gossiping for overlay video distribution
Given its readily deployable nature and broad applications for digital entertainment, video streaming through overlay networks has received much attention recently. While a tree topology is often advocated due to its scalability, it suffers from discontinuous playback under highly dynamic network environments. For on-demand streaming, the asynchronicity among client requests further aggravates the problem. On the other hand, gossip protocols using random message dissemination, though robust, fail to meet the real-time constraints for streaming applications. In this paper, we propose TAG, a Tree-Assisted Gossip protocol that addresses the above issues. TAG adopts a tree structure with time indexing to accommodate asynchronous requests, and an efficient pull-based gossip algorithm to mitigate the impact of network dynamicity. It seamlessly integrates these two approaches and realizes their best features, namely, low delay with a regular tree topology, and robust delivery with smart switching among multiple paths, thus making effective use of the available bandwidth in the network. We evaluate the performance of TAG under various settings, and the results demonstrate that it is quite robust in the presence of local and global bandwidth fluctuations. As compared to pure tree-based overlay VOD system, it achieves much lower and stable segment missing rates, even under highly dynamic network conditions.
39795223
On the Use of Sender Adaptation to Improve Stability and Fairness for Layered Video Multicast
Layered multicast has been shown as a promising technique for distributing a video program to a potentially large number of heterogeneous receivers. While several layered multicast approaches have been proposed, prior work has almost exclusively focused on improving the perceived video quality in terms of PSNR value or/and the fairness among different receivers. In this paper, we first argue that stability is another major index for the video playback quality; in an extreme case even with the best possible achievable PSNR value, the frequent switching between different layers still can lead to significant quality degradation. We then introduce an end-to-end adaptation framework that improves the stability and fairness for receivers by employing a dynamic layer rate allocation scheme on the sender's side. Specifically, we propose a new metric, called Stability-aware Fairness Index (SFI), which can capture both the stability as well as fairness. We then formulate the optimal layer rate allocation problem with the objective of minimizing the expected SFI for all the receivers in a multicast session, and derive an efficient algorithm to solve the problem. Simulation results demonstrate that our scheme can significantly improve the degree of stability and fairness, thus leading to better video playback quality.
46541251
Trustworthy Distributed Algorithm Design to Defend Distance Cheating in Link-Weighted ALM
In link-weighted Application Layer Multicast (ALM), each selfish and strategic end-host receiver may cheat in distance measurement to obtain a better position in the ALM tree. Distance cheating of ALM receivers might lead the ALM tree to be sub-optimal and unstable. We proposed a VCG-based cheat-proof mechanism to defend this kind of cheating behavior in previous work. Based on the theoretical framework, a practical algorithm is designed in this paper, which runs distributedly on ALM receivers. The primary characteristic of the distributed algorithm lies in that it is trustworthy to enforce each selfish receiver to fulfill the algorithm truthfully, which is not considered in other similar studies. Simulations results further suggest that the algorithm is effective in defending distance cheating in link-weighted ALM.
973730
Adaptive Video Multicast over the Internet
The authors survey existing solutions to adaptive video multicast, providing a taxonomy of solutions according to several distinct features. They also review the principal techniques from both video coding and network transport perspectives. Finally, they discuss the evaluation methodologies and metrics for adaptive video multicast systems.
17502480
A QoS-Based Joint Scheduling and Caching Algorithm for Multimedia Objects
With the development of the broadband Internet, multimedia services have been widely deployed and contributed to a significant amount of today’s Internet traffic. Like normal web objects (e.g., HTML pages and images), media objects can benefit from proxy caching; yet their unique features such as huge size and high bandwidth demand imply that conventional proxy caching strategies have to be substantially revised. Moreover, in the current Internet, clients are highly heterogeneous; it is necessary to differentiate their Quality-of-Service (QoS) requirements in streaming. However, the presence of an intermediate proxy in a streaming system poses great challenges to designers. This paper proposes a novel QoS-based algorithm for media streaming with proxy caching. We employ layered coding and transmission, and jointly consider the problems of caching and scheduling to improve the QoS for the clients. We derive general and effective solutions to the problems and evaluate their performance under various configurations. The results demonstrate that the proposed algorithm can accommodate diverse QoS demands from the clients, and yet satisfy stringent resource limits.
16004119
A Graph-Based Method for Face Identification from a Single 2D Line Drawing
The faces in a 2D fine drawing of an object provide important information for the reconstruction of its 3D geometry. In this paper, a graph-based optimization method is proposed for identifying the faces is a line drawing. The face identification is formulated as a maximum weight clique problem. This formulation is proven to be equivalent to the formulation proposed by Shpitalni and Upson (1996). The advantage of our formulation is that it enables one to develop a much faster algorithm to find the faces in a drawing. The significant improvement in speed is derived from two algorithms provided: the depth-first graph search for quickly generating possible faces from a drawing; and the maximum weight clique finding for obtaining the optimal face configurations of the drawing. The experimental results shown that our algorithm generates the same results of face identification as Shpitalni and Lipson's method, but is much faster when dealing with objects of more than 20 faces.
9274730
Agent-based, energy efficient routing in sensor networks
Amorphous computing aims at discovering new approaches for programming and controlling vast number of computational entities. So far, most related studies are mainly on the problem of pattern formation. However, there still remains a great challenge: how to enable amorphous entities to handle computationally hard problems? In order to tackle this challenge, we propose to take the energy efficient routing problem in sensor networks as a special topic for study, due to the similar characteristics of sensor nodes and amorphous entities. In the paper, each data packet sent from a source node is carried by an autonomous mobile data agent, which can make its own routing decision based on its local information. Moreover, we propose a novel data routing idea on energy efficient route choosing. Simulation results demonstrate that our routing schemes based on the proposed idea can achieve a better performance of energy load balancing in the network, and a shorter time delay for data agents to travel from a source to a sink than other schemes discussed in the paper. Furthermore, by endowing the data agents with some intelligence, data aggregation can be performed locally and dynamically during their transmissions in sensor networks.
33842812
Anycast-Based Cooperative Proxy Caching
As one of the most popular applications currently running on the Internet, the World Wide Web is of an exponential growth in size, which results in the network congestion and server overloading. Web caching as an important technique aims at reducing network traffic, server load, and user-perceived retrieval delays by replicating popular contents on proxy caches. In our paper, we develop an anycast-based cooperative web proxy caching mechanism. It puts response time, hop counts, self-organized load balancing, adaption, and self-configuration as primary concerns. In our scheme, anycast is used to bring a server “nearest” to a client to improve overall performance, all proxies in a local network consists an anycast group. The object placement and replacement problems are formulated as an optimization problem and the solution is obtained by using an anycast-based cooperative proxy caching algorithm. Some simulation experiments have been conduced to evaluate the proposed scheme in terms of a wide range of performance metrics. Analytical and experimental results show that our algorithm outperforms some existing algorithms in response time, hop counts.
5220045
A study of the performance and parameter sensitivity of adaptive distributed caching
A self-organized approach to manage a distributed proxy system called Adaptive Distributed Caching (ADC) has been proposed previously [8]. We model each proxy as an autonomous agent that is equipped to decide how to deal with client requests using local information. Experimental results show that our ADC algorithm is able to compete with typical hashing-based approaches. This paper gives a full description of the self-organizing distributed algorithm, with a performance comparison based on hits and hops rate. Additional evaluation of the parameters caching-, multiple- and single-table size is also presented.
30478531
Hamiltonian decompositions of Cayley graphs on Abelian groups
Abstract Alspach has conjectured that any 2k-regular connected Cayley graph cay(A,S) on a finite abelian group A can be decomposed into k hamiltonian cycles. In this paper, the conjecture is shown to be true if S={s1,s2,s3} is a minimal generating set of A with |A| odd, or S={s1,s2,…,sk} is a generating set of A such that gcd(ord(si),ord(sj))= 1 for i≠j.