Scale-out distributed storage systems can uphold balanced data growth in terms of capacity and performance on an on-demand basis. However, it is a challenge to store and manage large sets of contents being generated by the explosion of data. One of the promising solutions to mitigate big data issues is data deduplication, which removes redundant data across many nodes of the storage system. Nevertheless, it is non-trivial to apply a conventional deduplication design to the scale-out storage due to the following root causes. First, chunk-lookup for deduplication is not as scalable and extendable as the underlying storage system supports. Second, managing the metadata associated to deduplication requires a huge amount of design and implementation modifications of the existing distributed storage system. Lastly, the data processing and additional I/O traffic imposed by deduplication can significantly degrade performance of the scale-out storage. To address these challenges, we propose a new deduplication method, which is highly scalable and compatible with the existing scale-out storage. Specifically, our deduplication method employs a double hashing algorithm that leverages hashes used by the underlying scale-out storage, which addresses the limits of current fingerprint hashing. In addition, our design integrates the meta-information of file system and deduplication into a single object, and it controls the deduplication ratio at online by being aware of system demands based on post-processing. We implemented the proposed deduplication method on an open source scale-out storage. The experimental results show that our design can save more than 90% of the total amount of storage space, under the execution of diverse standard storage workloads, while offering the same or similar performance, compared to the conventional scale-out storage.

Flash-based NVMe storage devices dramatically improve I/O latency as well as I/O throughput. However, existing scale-out storage systems are designed for targeting hard disk drives and this design limitation causes significant performance degradation when they are used with NVMe devices. In this paper, we analyzed the performance of an existing scale-out storage system and identified lack of data locality and excessive lock contentions. To mitigate these problems, we present a new design based on locality aware lock contention avoidance (LALCA). LALCA proposes two techniques for scale-out storage system on high speed storage device: (1) locality-aware thread control to minimize processor context switching overhead and relevant performance degradation and (2) lock contention avoidance to remove locking problems in existing scale-out distributed storage system. With evaluation, LALCA shows not only up to 9 times performance improvement but also up to half CPU usage reduction when servicing small random I/Os.

We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices representing servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion. We show that solving a subproblem (\sf SingleMap) about mapping a single workload to the physical graph essentially suffices for solving the general problem. In particular, an $\alpha$-approximation algorithm for \sf SingleMap gives an $O(\alpha \log nD)$ competitive algorithm for the general problem, where $n$ is the number of nodes in the physical network and $D$ is the maximum to minimum workload duration ratio. We then consider the \sf SingleMap problem for two natural classes of workloads, namely depth-$d$ trees and complete-graph workloads. For depth-$d$ trees, we give an $n^{O(d)}$ time $O(d^2 \log (nd))$-approximation algorithm based on a strong LP relaxation inspired by the Sherali--Adams hierarchy. For complete graphs, we give a polylogarithmic approximation algorithm using Räcke decompositions.

As a state-of-the-art programming model for big data analytics, MapReduce is well suited for parallel processing of large data sets in opportunistic environments. Existing research on MapReduce in opportunistic environment has focused on improving single job performance, the issue of fairness that is critical in the more dominant scenario of multiple concurrent jobs remains unexplored. We address this problem by proposing an opportunistic fair scheduling algorithm, which extends the broadly adopted Fair Scheduler to an environment where nodes are intermittently available with possibly different availability patterns. The proposed scheduler maintains statistics specific to the opportunistic environment, e.g., node availability rates and pairwise availability correlations, and utilizes this information in scheduling decisions to improve fairness. Using a Hadoop-based implementation, we compare our scheduler with the current Hadoop Fair Scheduler on representative benchmarks. Our experiments verify that our scheduler can significantly reduce the variability in job completion times.

Rate adaptation is a MAC-layer mechanism in IEEE 802.11 networks that ensures efficient utilization of constantly varying wireless channel. For broadcast communication, however, the current practice is to send data at base rates (i.e., 1 or 2 Mbps in 802.11b/b+g and 6Mbps in 802.11a/g), leaving the channel capacity significantly underutilized. In this paper, we present a practical rate adaptation framework designed for broadcasting of streaming data to improve the channel utilization of 802.11 networks. The proposed framework jointly selects the data rate and the error protection level of FEC in a novel manner, and does not require changes to either existent applications or to the 802.11 standards - thus can be deployed in existing 802.11 networks. Using the performance measurement study in various live networking environments, we show that the proposed scheme provides substantial improvement in wireless channel utilization (more than 10x improvement compared to the current broadcast mode) and can adapt to different operational environments.

Content distribution in vehicular networks, such as multimedia file sharing and software updates, poses a great challenge due to network dynamics and high-speed mobility. In recent years, network coding has been shown to efficiently support distribution of content in such dynamic environments, thereby considerably enhancing the performance. However, the related work in the literature has mostly focused on theoretic or algorithmic aspects of network coding so far. In this paper, we provide an in-depth analysis on the implementation issues of network coding in wireless networks. In particular, we study the impact of resource constraints (namely CPU, disk, memory, and bandwidth) on the performance of network coding in the content distribution application. The contribution of this paper is twofold. First, we develop an abstract model of a general network coding process and evaluate the validity of the model via several experiments on real systems. This model enables us to find the key resource constraints that influence the network coding strategy and thus to efficiently configure network coding parameters in wireless networks. Second, we propose schemes that considerably improve the performance of network coding under resource constrained environments. We implement our overhead model in the QualNet network simulator and evaluate these schemes in a large-scale vehicular network. Our results show that the proposed schemes can significantly improve the network coding performance by reducing the coding overhead.

We consider the problem of opportunistically scheduling low-priority tasks onto underutilized computation resources in the cloud left by high-priority tasks. To avoid conflicts with high-priority tasks, the scheduler must suspend the low-priority tasks (causing waiting), or move them to other underutilized servers (causing migration), if the high-priority tasks resume. The goal of opportunistic scheduling is to schedule the low-priority tasks onto intermittently available server resources while minimizing the combined cost of waiting and migration. Moreover, we aim to support multiple parallel low-priority tasks with synchronization constraints. Under the assumption that servers' availability to low-priority tasks can be modeled as ON/OFF Markov chains, we have shown that the optimal solution requires solving a Markov Decision Process (MDP) that has exponential complexity, and efficient solutions are known only in the case of homogeneously behaving servers. In this paper, we propose an efficient heuristic scheduling policy by formulating the problem as restless Multi-Armed Bandits (MAB) under relaxed synchronization. We prove the index ability of the problem and provide closed-form formulas to compute the indices. Our evaluation using real data center traces shows that the performance result closely matches the prediction by the Markov chain model, and the proposed index policy achieves consistently good performance under various server dynamics compared with the existing policies.

Spot virtual-machine (VM) instances, such as Amazon EC2 Spot VMs, are a class of VMs that are purchased through a market mechanism of price-bids submitted by cloud users. Spot VMs can be obtained at substantially lower cost than other VM classes such as Reserved and On-demand instances, but they do not have guaranteed availability since it depends on the submitted price bids and the fluctuating spot VM price. Many applications with large computing requirements but no real-time availability constraints, such as scientific computing, financial modelling and large data analysis, can be carried out at a significantly lower cost using spot VMs. For such jobs, an important question that arises is what should the submitted price bids be so that the computation is completed within a fixed time interval while the cost is minimized. Towards this goal, we model a job as a fixed computation request with a deadline constraint and formulate the problem of designing a dynamic bidding policy that minimizes the average cost of job completion. We obtain analytical and closed-form results for the optimal strategy under a Markov spot price evolution, and then evaluate the performance of the algorithms on the actual spot price history of Amazon EC2 Spot VMs.

We consider the problem of scheduling low-priority tasks onto resources already assigned to high-priority tasks. Due to burstiness of the high-priority workloads, the resources can be temporarily underutilized and made available to the low-priority tasks. The increased level of utilization comes at a cost to the low-priority tasks due to intermittent resource availability. Focusing on two major costs, bandwidth cost associated with migrating tasks and latency cost associated with suspending tasks, we aim at developing online scheduling policies achieving the optimal bandwidth-latency tradeoff for parallel low-priority tasks with synchronization requirements. Under Markovian resource availability models, we formulate the problem as a Markov Decision Process (MDP) whose solution gives the optimal scheduling policy. Furthermore, we discover structures of the problem in the special case of homogeneous availability patterns that enable a simple threshold-based policy that is provably optimal. We validate the efficacy of the proposed policies by trace-driven simulations.

Amazon introduced Spot Instance Market to utilize the idle resources of Amazon Elastic Compute Cloud (EC2) more efficiently. The price of a spot instance changes dynamically according to the current supply and demand for cloud resources. Users can bid for a spot instance and the job request will be granted if the current spot price falls below the bid, whereas the job will be terminated if the spot price exceeds the bid. In this paper, we investigate the problem of designing a bidding strategy from a cloud service broker's perspective, where the cloud service broker accepts job requests from cloud users, and leverages the opportunistic yet less expensive spot instances for computation in order to maximize its own profit. In this context, we propose a profit aware dynamic bidding (PADB) algorithm, which observes the current spot price and selects the bid adaptively to maximize the time average profit of the cloud service broker. We show that our bidding strategy achieves a near-optimal solution, i.e., (1-∈) of the optimal solution to the profit maximization problem, where ∈ can be arbitrarily small. The proposed dynamic bidding algorithm is self-adaptive and requires no a priori statistical knowledge on the distribution of random job sizes from cloud users.

Interoperation in MANETs is an important issue in many operational situations, because of the growing number of heterogeneous MANETs with different standards, technologies and adminstrative management. To enable interoperation, gateways are often deployed for protocol translation, inter-MANET routing, and management policy enforcement among these heterogeneous MANETs. To optimize gateway deployment, we consider the gateway functionalities to be enabled or disabled dynamically in response to the changing network topology. In this paper, we offer mechanisms to select the minimal subset of enabled gateways among the deployed gateways to ensure the interoperation among the MANETs. To this aim, we formulate a novel graph optimization problem, called Minimal Gateway Assignment Problem, and prove that it is NP-hard. Nonetheless, we provide efficient algorithms to solve this problem with varying degrees of complexity and coordination. First, we provide a centralized polynomial-time algorithm that is 2-approximable, and a distributed algorithm. Second, by simulation, we show that our centralized and distributed algorithms can perform close to the optimal. We also report an interesting result that cooperation is the key factor to produce optimal outcomes - a simple algorithm with tight cooperation among MANETs gives much better outcomes than a smart algorithm with loose cooperation.

We study the challenging problem of strategic content placement in a dynamic MANET. Existing content placement techniques cannot cope with such network dynamics since they are designed for fixed networks. Opportunistic caching approaches are insufficient as they do not actively manage contents for certain goals. In this paper, we present a novel content management approach called LACMA, which leverages the location information available to mobile devices via GPS. The main idea of LACMA is to bind data to geographic location (as opposed to network nodes). This location-based strategy decouples the content placement problem from the changing network topology, and allows us to design an optimization framework even in a dynamic MANET environment. We present key components of LACMA used for strategic content placement and content-location binding (through proactive content push). We evaluate LACMA and compare its performance with existing caching schemes and show that LACMA considerably outperforms existing schemes over a wide range of scenarios.

The performance of many algorithms in dynamic networks depends on the properties of the underlying graph representing the network. Since such a graph is inherently time-varying, quantifying the change in its structure is important for understanding the behavior of higher-layer network algorithms. In this paper, we study change in the dynamic graph structure of mobile wireless networks that evolve over time due to node mobility. We define several graph evolution metrics and evaluate them through extensive numerical simulations under Levy Walk mobility, which has been shown previously to have similarities to human mobility patterns. Based on the mean and distribution of these metrics, we obtain important insights into the properties of the evolving graph generated by Levy Walk mobility, and then compare the results to the Random Waypoint mobility model. Finally, we discuss the effects of the rate of graph change on the performance of network applications such as data routing and flooding. Our results suggest that the proposed metrics are viable for quantitatively measuring the magnitude of change in a sequence of evolving graphs.

We consider a coalition network where multiple groups are interconnected via wireless links. Gateway nodes are designated by each domain to achieve a network-wide interoperability. Due to the inter-domain communication cost, the optimal gateway selection for one single domain depends on the gateway selections of other domains and vice versa. In this paper, we investigate the interactions of gateway selections by multiple domains from a potential game perspective. The equilibrium inefficiency in terms of price of stability is characterized under various conditions. In addition, we examine the well-established equilibrium selective learning algorithm B-logit and show that B-logit is a special case of a general family of algorithms, denoted by Γ collectively. A novel learning algorithm named MAX-logit is proposed, which retains the favorable equilibrium selection property with the provably fastest convergence speed than any other algorithms in Γ, and can be applied to many other applications of potential games. Simulation results show that MAX-logit can improve the convergence speed of B-logit by up to 33.85%.

We consider the problem of disseminating data from a base station to a sparse, partitioned mobile network by controllable data ferries with limited ferry-node and ferry-ferry communication ranges. Existing solutions to data ferry control mostly assume the nodes to be stationary, which reduces the problem to designing fixed ferry routes. In the more challenging scenario of mobile networks, existing solutions have focused on single-ferry control and left out an important issue of ferry cooperation in the presence of multiple ferries. In this paper, we jointly address the issues of ferry navigation and cooperation using the approach of stochastic control. Under the assumption that ferries can communicate within each partition, we propose a hierarchical control system called Dispatch-and-Search (DAS), consisting of a global controller that dispatches ferries to individual partitions and local controllers that coordinate the search for nodes within each partition. Formulating the global and the local control as Partially Observable Markov Decision Processes (POMDPs), we develop efficient control policies to optimize the (discounted) total throughput, which significantly improve the performance of their predetermined counterparts in cases of limited prior knowledge.

We study a basic resource allocation problem that arises in cloud computing environments. The physical network of the cloud is represented as a graph with vertices denoting servers and edges corresponding to communication links. A workload is a set of processes with processing requirements and mutual communication requirements. The workloads arrive and depart over time, and the resource allocator must map each workload upon arrival to the physical network. We consider the objective of minimizing the congestion.

The advancements of diverse radio technologies and emerging applications have spawned increasing heterogeneity in mobile ad hoc networks (MANETs). But the collaborative nature of communications and operations often requires that these heterogeneous MANETs to be interoperable. Nonetheless, the existing interconnection protocols designed for the Internet (namely inter-domain routing protocol such as BGP) are not adequate for handling the unique challenges in MANETs. In this paper, we present a novel Inter-MANET Routing protocol called InterMR that can handle the heterogeneity and dynamics of MANETs. Our first contribution is an Inter-MANET address scheme based on a variety of node attributes (e.g., symbolic name, property, etc.); this allows dynamic merging/split of network topologies without a separate Name Server. Our second contribution is to provide a seamless routing mechanism across heterogeneous MANETs without modifying the internal routing mechanisms in each MANET. The proposed scheme can transparently adapt to topological changes due to node mobility in MANETs by dynamically assigning the gateway functionalities. We show, by packet-level simulation, that the performance of InterMR can be improved by up to 112% by adaptive gateway assignment functionalities. We also show that InterMR is scalable with only modest overhead by analysis.

We seek to support communications in highly-partitioned mobile wireless networks via controllable data ferries. While existing ferry control techniques assume either stationary nodes or complete ferry observation of node locations, we address the more challenging scenario of highly mobile nodes and partial ferry observations. Using the tool of Partially Observable Markov Decision Processes (POMDP), we develop a comprehensive framework where we expand the solution space from predetermined trajectories to policies that can map ferry observations to navigation actions dynamically. Under this framework, we present an optimal and several efficient heuristic policies. We compare the proposed policies with predetermined control through analysis and simulations with respect to multiple node mobility parameters including speed, locality, activeness, and range of movement. The comparisons show a significant performance gain of up to twice the contact rate in cases of high uncertainty. In cases of low uncertainty, we give a sufficient condition under which predetermined control is optimal.

Due to technology or policy constraints, communications across network domains usually require the intervention of gateways, and their proper deployment is crucial to the overall performance. In this paper, we study the problem of placing static gateways in mobile DTNs consisting of multiple domains. Given a limited gateway budget, the problem is to select deployment locations to optimize certain performance. The challenge is that different domains may possess heterogeneous properties. To ensure general applicability of solution, we propose a unified framework based on utility optimization, and solve utility computation and placement optimization separately. To handle heterogeneity, we decompose utility computation into individual domains and derive closed-form solutions based on key domain characteristics with focus on the routing scheme. Moreover, we develop quadratic-complexity algorithms to solve the optimization efficiently, which has guaranteed performance under certain uniformity conditions. Although certain assumptions have been made in developing the solutions, evaluations based on synthetic data and real DTN traces both show that the proposed solutions can achieve near-optimal (within 5%) performance at much lower complexities, and the results are robust with respect to the routing schemes and the mobility patterns. Compared with utility-agnostic deployments, our solutions significantly improve the end-to-end performance (by up to 50%).

Controlled mobile helper nodes called data ferries have recently been proposed to bridge communications between disconnected nodes in a delay-tolerant manner. While existing work has explored various trajectory designs for the data ferry by assuming either static nodes or full observations at the data ferry, the problem remains open when the nodes are mobile and the ferry only has partial observations. In this paper, we investigate the problem of dynamic ferry mobility control under limited-range sensing. Assuming the data ferries are capable of sensing node presence within certain range and adjust their movements dynamically, we aim to design control policies that maximize the number of effective contacts. We provide a comprehensive model of the control framework using Partially Observable Markov Decision Process (POMDP), based on which we study the structure of the optimal policy and propose an efficient heuristic policy which shows significant improvement over the predetermined benchmark. To the best of our knowledge, this is the first data ferry control mechanism that can handle both stochastic node mobility and incomplete ferry observations.

The vitality and utility of a network are affected significantly by the network management system (NMS) that is used to administer and monitor the network. However, models that can characterize the quality of a NMS are generally missing in the literature. In this paper, we introduce the concept of quality of monitoring (QoM), provide a mathematical formulation based on stochastic processes that can be used to model a network monitoring system and define QoM metrics based on this formulation. A formal analysis of the proposed framework along various metrics is also provided, along with a case study of its application to network monitoring in a mobile ad hoc network.

Mobile wireless networks with intermittent connectivity, often called Delay/Disruption Tolerant Networks (DTNs), have recently received a lot of attention because of their applicability in various applications, including multicasting. To overcome intermittent connectivity, DTN routing protocols utilize mobility-assist routing by letting the nodes carry and forward the data. In this paper, we study the scalability of DTN multicast routing. As Gupta and Kumar showed that unicast routing is not scalable, recent reports on multicast routing also showed that the use of a multicast tree results in a poor scaling behavior. However, Grossglauser and Tse showed that in delay tolerant applications, the unicast routing overhead can be relaxed using the two-hop relay routing where a source forwards packets to relay nodes and the relay nodes in turn deliver packets to the destination via “mobility,” thus achieving a perfect scaling behavior of Θ(1). Inspired by this result, we seek to improve the throughput bound of wireless multicast in a delay tolerant setting using mobility-assist routing. To this end, we propose RelayCast, a routing scheme that extends the two-hop relay algorithm in the multicast scenario. Given that there are nssources each of which is associated with ndrandom destinations, our results show that RelayCast can achieve the throughput upper bound of Θ(min(1, n/nsnd)). We also analyze the impact of various network parameters and routing strategies (such as buffer size, multi-user diversity among multicast receivers, and delay constraints) on the throughput and delay scaling properties of RelayCast. Finally, we validate our analytical results with a simulation study.

Besides safe navigation (e.g., warning of approaching vehicles), car to car communications will enable a host of new applications, ranging from offlce-on-the-wheel support to entertainment. One of the most promising applications is content distribution among drivers such as multi-media files and software updates. Content distribution in vehicular networks is a challenge due to network dynamics and high mobility, yet network coding was shown to efficiently handle such dynamics and to considerably enhance performance. This paper provides an in-depth analysis of implementation issues of network coding in vehicular networks. To this end, we consider general resource constraints (e.g., CPU, disk, memory) besides bandwidth, that are likely to impact the encoding and storage management operations required by network coding. We develop an abstract model of the network coding procedures and implement it in the wireless network simulator to evaluate the impact of limited resources. We then propose schemes that considerably improve the use of such resources. Our model and extensive simulation results show that network coding parameters must be carefully configured by taking resource constraints into account.

In this paper, we present a novel deployment-time binding selection framework for Web services to improve the performance. Using the information about target environments, we determine the best binding based on the availability and the accessibility of a service, and the performance characteristics of the bindings in a target environment. We have implemented the proposed mechanism as part of Eclipse-based development tools. We present an extensive performance evaluation of our methodology using benchmarks that we have created following public Web service interfaces, and emulating several e-business applications including a large scale legacy transaction processing system that runs on a mainframe.

The objectives of this paper are twofold. First, we introduce a novel policy language, called CIM-SPL (simple policy language for CIM) that complies with the CIM (common information model) Policy Model and fully incorporates CIM constructs. Currently, the CIM standards from distributed management task force (DMTF) include a policy model, but there is no satisfactory way to render this policy model. CIM-SPL is a language that has been defined for this purpose. Second, we address design and implementation issues for policy languages in general, and for CIM-SPL in particular. The design of CIM-SPL was inspired by our previous experiences in designing various policy languages (e.g., PDL from Bell Laboratories, and ACPL from IBM) and lessons learned from studying other well-known policy languages (e.g., Ponder from Imperial College). We will discuss our design choices, evaluating the pros and cons of various alternatives. The ideas presented in this paper are meant to shed light on our design decisions, and provide guidance for those who want to build a CIM-based policy system or some other policy system in the future.

This paper introduces a novel deployment time optimization (DTO) technology for Internet services. Using the configuration information collected from the target operation environment, the proposed optimization technology attempts to deploy only necessary and most performant components for a service in the target environment. To facilitate DTO, we have developed a framework called blue pencil, which consists of the following modules: configuration discovery module, optimization rule repository, deployment optimization module, proxy generation module, and code transformation module. We present how these modules enable DTO and show the performance benefit of DTP in a client-server binding selection scenario.

In this paper, we develop two mechanisms to detect DoS attacks against CDN-hosted Web sites and CDN infrastructure servers. First, we propose a novel request routing algorithm which allows CDN servers to effectively distinguish attacks from legitimate requests. Our scheme, based on a keyed hash function, significantly improves the resilience of servers to DoS attacks. Second, we introduce several site allocation algorithms based on binary codes which insure that an attack on one hosted Web site has a limited impact on other hosted sites. Our scheme guarantees that a specified minimum number of servers remain available for non-victimized sites. Together, the proposed schemes significantly improve the resilience of CDN-hosted Web sites, and complement other work on countering distributed DoS attacks.

In this paper, we present a novel policy middleware architecture for managing IT systems and applications that span multiple networks and administrative domains. The proposed policy middleware provides a standard infrastructure for the creation, storage, distribution, and execution of policies, and helps in reducing the cost of making IT systems policy-aware. In particular, we focus on three aspects of the proposed policy middleware that help in making the middleware fully general: (1) a platform-neutral and extensible specification of policies; (2) the local ratification of policies, which lets system administrators accept, reject, or flag an incoming policy; and (3) the transformation of policies, which allows system administrators to transform incoming policies to match their local environment. We present our experience in building an application on the proposed middleware to audit the configuration of a storage area network. We also present performance results from a prototype and show that our policy middleware design can scale to handle a large number of policies.

Peer-to-peer (P2P) computing has become a popular distributed computing paradigm thanks to abundant computing power of modern desktop workstations and widely available network connectivity via the Internet. Although P2P file sharing provides a scalable alternative to conventional server-based approaches, providing efficient file search in a large scale dynamic P2P system remains a challenging problem. In this paper, we propose a set of mechanisms to provide a scalable keyword-based file search in distributed hash table (DHT)-based P2P systems. In particular, we address the problem induced by common keywords that are associated with a large number of files and thus require excessive storage consumptions from the hosting peers. Our proposed architecture, called keyword fusion, adaptively unburdens the peers overloaded with excessive storage consumptions due to common keywords and reduces network bandwidth consumption by transforming users' queries to contain more focused search terms. Through trace-driven simulations, we show that keyword fusion can reduces the storage consumption of the top 5% most loaded nodes by 50% and decrease the search traffic by up to 68% even in the modest scenarios of combining two keywords.

Peer-to-peer (P2P) computing has become a popular distributed computing paradigm thanks to the abundant computing power of modern desktop workstations and widely available network connectivity. Although P2P file sharing provides a scalable alternative to conventional server-based approaches, providing efficient file search in a large-scale dynamic P2P system remains a challenging problem. We propose a set of mechanisms to provide a scalable keyword-based file search in distributed hash table (DHT) based P2P systems. Our proposed architecture, called keyword fusion, balances unfair storage consumptions at peers and transforms users' queries to contain focused search terms. Through trace-driven simulations, we show that keyword fusion can reduce the storage consumption of the top 5% most loaded nodes by 50% and decrease the search traffic by up to 67%, even in a modest scenario of combining two keywords.

In this paper, we present a novel distributed algorithm that dynamically selects game servers for a group of game clients participating in large scale interactive online games. The goal of server selection is to minimize server resource usage while satisfying the real-time delay constraint. We develop a synchronization delay model for interactive games and formulate the server selection problem, and prove that the considered problem is NP-hard. The proposed algorithm, called zoom-in-zoom-out, is adaptive to session dynamics (e.g. clients join and leave) and lets the clients select appropriate servers in a distributed manner such that the number of servers used by the game session is minimized. Using simulation, we present the performance of the proposed algorithm and show that it is simple yet effective in achieving its design goal. In particular, we show that the performance of our algorithm is comparable to that of a greedy selection algorithm, which requires global information and excessive computation.

The exponential growth of mobile data users and services places a heavy burden on the limited wireless bandwidth of cellular data networks. The situation will be exacerbated with the advent of high bandwidth multimedia applications for mobile devices. We propose an architecture called the cellular-based ad hoc peer data sharing system (CAPS) to reduce the load on the cellular network while improving request response times. In CAPS, mobile hosts in a cellular network form an overlay multihop wireless network. This ad hoc network acts as a 'virtual cache' that enables data sharing among mobile hosts. Participating mobiles share the contents of their local caches with other mobiles. A subset of mobile hosts keep track of the location of objects with minimal overhead. Using CAPS, popular objects can be obtained over the ad hoc network without accessing the cellular infrastructure, thereby reducing the load on the cellular network and improving data access latency. We have extensively evaluated the performance of this architecture through simulations in ns-2 across a wide range of scenarios, and find that CAPS reduces the timeouts of the user requests by 70-90% and reduces the load at the base station by up to 60%.

Motivated by the need to enable easier data sharing and curb rising storage management costs, storage systems are becoming increasingly consolidated and thereby shared by a large number of users and applications. In such environments, service differentiation becomes increasingly important. Since caching is a fundamental and pervasive technique employed to improve the performance of storage systems, providing differentiated services from a storage cache is a crucial component of the entire end-to-end QoS solution. In this paper we discuss a QoS architecture for a shared storage proxy cache which can provide long-term hit rate assurances to competing classes. The proposed architecture consists of three components: (a) per-class feedback controllers that track the performance of each class, (b) a fairness controller that allocates excess resources fairly in the case when all goals are met, and (c) a contention resolver that decides cache allocation in the case when at least one class does not meet its target hit rate. We compare the performance of various feedback per-class controllers, and provide guidelines for designing QoS mechanisms for such a dynamic environment.

The focus of this paper is to compare two popular end-to-end congestion control algorithm in the literature, namely, AIMD (additive increase/multiplicative decrease) and AIPD (additive increase/loss proportional decrease). We clarify the definitions of AIMD and AIPD algorithms, and compare them in various aspects such as convergence, steady state throughput, fairness characteristics, and the corresponding utility functions. The comparison is based on a simple mathematical analysis and a set of simulation results using the ns-2 simulator.

In this work we present an end-to-end optimized video streaming system comprising of synergistic interaction between a source packetization strategy and an efficient and responsive, TCP-friendly congestion control protocol [Linear Increase Multiplicative Decrease with History (LIMD/H)]. The proposed source packetization scheme transforms a scalable/layered video bitstream so as to provide graceful resilience to network packet drops. The congestion control mechanism provides low variation in transmission rate in steady state and at the same time is reactive and provably TCP-friendly. While the two constituent algorithms identified above are novel in their own right, a key aspect of this work is the integration of these algorithms in a simple yet effective framework. This "application-transport" layer interaction approach is used to maximize the expected delivered video quality at the receiver. The integrated framework allows our system to gracefully tolerate and quickly react to sudden changes in the available connection capacity due to the onset of congestion, as verified in our simulations.

We describe a framework for video transmission over the Internet that features the coordinated operation of an application-layer video source coding algorithm and a transport-layer rate control mechanism. The proposed video coding scheme operates on a progressively encoded video stream and provides graceful resilience to network packet drops. The robustness is enabled through a generalized multiple description (MD) coding strategy, architectured as an adaptive array of packet-erasure correction codes. The video coding algorithm is matched to an efficient and reactive rate control mechanism that minimizes the fluctuation of rate and uses the profile of past losses to adjust the rate in a TCP-friendly manner. While the two constituent algorithms identified above are interesting in their own right, a key feature of this work is the integration of these algorithms in a simple framework that seeks to maximize the expected delivered video quality at the receiver through coordinated adaptation of the two components. We present simple simulation results to illustrate the utility of our approach.

Article Free Access Share on An application-level multicast architecture for multimedia communications (poster session) Authors: Kang-Won Lee Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile , Sungwon Ha Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile , Jia-Ru Li Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile , Vaduvur Bharghavan Coordinated Science Laboratory, University of Illinois at Urbana-Champaign Coordinated Science Laboratory, University of Illinois at Urbana-ChampaignView Profile Authors Info & Claims MULTIMEDIA '00: Proceedings of the eighth ACM international conference on MultimediaOctober 2000 Pages 398–400https://doi.org/10.1145/354384.354544Published:30 October 2000Publication History 3citation357DownloadsMetricsTotal Citations3Total Downloads357Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present our experience with the Illinois Reliable Multicast Architecture (IRMA) reliable multicast architecture. IRMA guarantees reliable, sequenced, and loosely synchronized delivery of multicast streams by supporting TCP as the multicast transport protocol at the end hosts without modifications to the standard TCP/IP stack. To support TCP as the multicast transport protocol, IRMA provides ACK aggregation, local recovery, and network level support for TCP flow/congestion control. We describe an implementation of IRMA, and evaluate its performance in a real network as well as in a simulation environment. The performance result of IRMA indicates that it may be a viable architecture for proving reliable multicast in the Internet.

Single-rate reliable multicast protocols are known to have scalability problems in the presence of a large number of receivers because the sender cannot distinguish independent packet losses at different receivers from multiple packet losses at the same receiver. In the presence of a large number of receivers, the sender may perceive a large aggregate packet loss even if no individual receiver is highly congested. Consequently, the multicast session progresses at a much slower rate than its desired sending rate. In order to solve this problem, we argue for decoupling of the mechanisms to achieve congestion control and reliability in reliable multicast protocols, and present a very simple "loss notification"-based multicast congestion control mechanism that can be used to augment both ACK-based and NAK-based reliable multicast protocols and solve the independent packet loss problem. We illustrate the efficacy of our approach via simulations using the ns2 simulator.

The Illinois Reliable Multicast Architecture (IRMA) is a reliable multicast architecture that guarantees reliable, sequenced, and loosely synchronized delivery of multicast streams. IRMA provides ACK-based reliability, hybrid local server-initiated and sender-initiated loss recovery, and support for end-to-end flow control and congestion control. Unlike most contemporary work, IRMA supports TCP as the reliable multicast transport protocol at the end host without modifications. IRMA has been instantiated in a laboratory testbed, and its performance has been measured in various scenarios. Preliminary performance results show that IRMA is efficient and adaptive to the dynamics of the network.

No abstract available.

We present an analysis of the relationship between the two link-level QoS (quality of service) parameters (delay and error rate) and the motion speed of a user in a wireless packet network environment. The analysis is based on: (1) a wireless channel simulation using a time-correlated Rayleigh fading model and (2) a physical layer model which complies with the wireless LAN draft standard, IEEE 802.11. The analysis on delay and error rate QoS parameters is targeted to two major types of network applications: (1) real-time applications which are sensitive to delay but can tolerate a small amount of data loss and (2) conventional data transfer applications which are sensitive to data loss but normally do not require specific delay bounds.

This paper studies the performance of a large class of scheduling algorithms, and investigates the interaction between the application and the network to improve performance under congestion. The following key ideas are presented in this paper: (a) we show the performance and scalability trade-offs between providing separation and multiplexing among flows; (b) we show that a bounded buffer FIFO scheduler performs approximately as well as a weighted round robin scheduler with per-flow queues in most practical situations, but requires significantly less overhead in terms of per-flow state; and (c) we show how link layer schedulers can use application-level hints in order to increase the perceived goodness of connections at higher layers.