This paper presents a framework for Robust Infrastructure over Shared Computing resource (RISC), which can offer Organizations with Small-scale Computing infrastructures (OSCs) a way to share their unused resources in an ad-hoc manner for suitable monetary incentives. Such a framework provides dual benefits to an OSC: it enables sharing of unused resource during periods of low computing load while allowing execution of any long-term computation on public or anonym zed data at a very low cost during periods of high load. The ad-hoc and heterogeneous nature of the shared infrastructure make the resource management problem inRISC non-trivial -- a resource manager needs to: (i) maximize profit while determining incentives for resource owners and prices for resource users in an integrated manner, and (ii)emulate large-scale cloud-like robustness and capabilities out of unreliable, small-scale and intermittently available resources at a low cost. This leads to a constrained market situation where offered prices and incentives should lead to a desired level of SLA and reliability for the consumers. Existing approaches of incentive based scheduling for market-like grids assume an open market, based only on demand response, and thus are inapplicable for the constrained market situation in shared resources infrastructure. Specifically, RISC framework has two main components: (i) a first-of-a-kind Dynamic Pricing and Incentivization (DPI) strategy that computes the incentives and the prices while maximizing profit for RISC, using an epoch-by-epoch pricing feedback loop, and (ii) a DPI dependent Reliability, Cost and Seaware(RCS) scheduler that takes the resource reservation requests as input and assigns replicas of these requests tone or more shared resources for guaranteeing performanceSLAs and reliability, while minimizing the cost of resource reservations. Moreover, to handle the communication overhead of computing over geographically distributed resources, the scheduler strives to reduce the network cost of resource allocation. Results from extensive trace-driven experimentation show that our approach can indeed provide appropriate incentives for resource providers, and robust cost-efficient infrastructure solution for resource users.

We consider the problem of fair resource allocation for tasks where a resource can be assigned to at most one task, without any fractional allocation. The system is heterogeneous: capacity and cost may vary across resources, and different tasks may have different resource demand. Due to heterogeneity of resources, the cost of allocating a task in isolation, without any other competing task, may differ significantly from its allocation cost when the task is allocated along with other tasks. In this context, we consider the problem of allocating resource to tasks, while ensuring that the cost is distributed fairly across the tasks, namely, the ratio of allocation cost of a task to its isolation cost is minimized over all tasks. We show that this fair resource allocation problem is strongly NP-Hard even when the resources are of unit size by a reduction from 3-partition. Our central results are an LP rounding based algorithm with an approximation ratio of 2+ O(ϵ) for the problem when resources are of unit size, and a near-optimal greedy algorithm for a more restricted version. The above fair allocation problem arises for resource allocation in various context, such as, allocating computing resources for reservations requests from tenants in a data centre, allocating resources to computing tasks in grid computing, or allocating personnel for tasks in service delivery organizations.

Managing the Quality-of-Experience (QoE) of video streaming for wireless clients is becoming increasingly important due to the rapid growth of video traffic on wireless networks. The inherent variability of the wireless channel as well as the Variable Bit Rate (VBR) of the compressed video streams make QoE management a challenging problem. In this paper, we investigate scheduling algorithms to transmit multiple video streams from a base station to mobile clients. We present an epoch-by-epoch framework to fairly allocate wireless transmission slots to streaming videos. In each epoch, our scheme reduces the vulnerability to stalling by allocating slots to videos in a way that maximizes the minimum “playout lead” across all videos. We show that the problem of allocating slots fairly is NP-complete even for a constant number of videos. We then present a fast lead-aware greedy scheduling algorithm. Our greedy algorithm is optimal when the channel quality of a user remains unchanged within an epoch. Our experimental results, based on public MPEG-4 video traces and wireless channel traces that we collected from a WiMAX test-bed, show that the lead-aware greedy approach results in a fair distribution of stalls across the clients when compared to other algorithms, while still maintaining similar or fewer average number of stalls per client.

This paper presents C-CLOUD, a democratic cloud infrastructure for renting computing resources includingnon-cloud resources (i.e. computing equipment not part of any cloud infrastructure, such as, PCs, laptops, enterprise servers and clusters). C-CLOUD enables enormous amount of surplus computing resources, in the range of hundreds of millions, to be rented out to cloud users. Such a sharing of resources allows resource owners to earn from idle resources, and cloud users to have a cost-efficient alternative to large cloud providers. Compared to existing approaches to sharing surplus resources, C-CLOUD has two key challenges: ensuring Service Level Agreement (SLA) and reliability of reservations made over heterogeneous resources, and providing appropriate mechanism to encourage sharing of resources. In this context, C-CLOUD introduces novel incentive mechanism that determines resourcerents parametrically based on their reliability and capability.

In this paper, we study the problem of efficient video delivery over the cellular downlink. The key objective is to maximize the Quality of Experience (QoE) of the user, as measured by application level metrics such as the buffering ratio and low bit rate ratio. We present a two-tiered solution with a standard base-station scheduler that works on a per-packet basis and a Video Management System (VMS) that works at the granularity of thousands of video frames. The video management system uses knowledge of the video playout curves and future channel states to develop a scheduling policy that is feasibility optimal. The algorithms are simple and leverage recent results on real-time scheduling in wireless networks. We evaluate the performance of our algorithms using real video traces and a standard channel model. The VMS ensures that the per-user QoE guarantees are maintained, as compared with a standard PF scheduler that is oblivious to application level QoE requirements.

As businesses move their critical IT operations to multi-tenant cloud data centers, it is becoming increasingly important to provide network performance guarantees to individual tenants. Due to the impact of network congestion on the performance of many common cloud applications, recent work has focused on enabling network reservation for individual tenants. Current network reservation methods, however, do not gracefully degrade in the presence of network over subscriptions that may frequently occur in a cloud environment. In this context, for a shared data center network, we introduce Network Satisfaction Ratio (NSR) as a measure of the satisfaction derived by a tenant from a given network reservation. NSR is defined as the ratio of the actual reserved bandwidth to the desired bandwidth of the tenant. Based on NSR, we present a novel network reservation mechanism that can admit time-varying tenant requests and can fairly distribute any degradation in the NSR among the tenants in presence of network over subscription. We evaluate the proposed method using both synthetic network traffic trace and representative data center traffic trace generated by running a reduced data center job trace in a small test bed. The evaluation shows that our method adapts to changes in network reservations, and it provides significant and fair improvement in NSR when the data center network is oversubscribed.

Managing the Quality-of-Experience (QoE) of video streaming for wireless clients is becoming increasingly important due to the rapid growth of video traffic on wireless networks. The inherent variability of the wireless channel as well as the Variable Bit Rate (VBR) of the compressed video streams make QoE management a challenging problem. Prior work has studied this problem in the context of transmitting a single video stream. In this paper, we investigate multiplexing schemes to transmit multiple video streams from a base station to mobile clients that use number of playout stalls as a performance metric. In this context, we present an epoch-by-epoch framework to fairly allocate wireless transmission slots to streaming videos. In each epoch our scheme essentially reduces the vulnerability to stalling by allocating slots to videos in a way that maximizes the minimum `playout lead' across all videos. Next, we show that the problem of allocating slots fairly is NP-complete even for a constant number of videos. We then present a fast lead-aware greedy algorithm for the problem. Our choice of greedy algorithm is motivated by the fact that this algorithm is optimal when the channel quality of a user remains unchanged within an epoch (but different users may experience different channel quality). Moreover, our experimental results based on public MPEG-4 video traces and wireless channel traces that we collected from a WiMAX test-bed show that the lead-aware greedy approach performs a fair distribution of stalls across the clients when compared to other algorithms, while still maintaining similar or lower average number of stalls per client.

The Internet is witnessing a rapid increase in video traffic. Due to the scalability and the cost-savings offered by cloud-computing, Internet video service providers are increasingly delivering their content from multi-tenant cloud data centers. One of the major challenges faced by such a video service provider is the management of the Quality-of-Experience (QoE) of the end-users in the presence of Variable Bit Rate (VBR) video flows, time varying network conditions in the Internet, and the bounded egress bandwidth provided by the data center. To this end, we present InSite, a light-weight and easy-to-deploy solution for managing the QoE of a set of video flows of a service provider, which are served from a data center. InSite is deployed at the egress of a data center, between the video servers and the clients, and manages the video flows that are transmitted over TCP. The solution uses a novel generalized binary search technique to concurrently search for the appropriate flow rates for a set of flows, with the goal of maximizing the QoE-fairness across the flows, as opposed to TCP-fairness. The search takes into account the total egress bandwidth allocated for the set of video flows at the data center, the unknown and possibly time-varying capacities of any remote bottleneck links, and the playout buffer sizes of the video flows. The solution is also designed to operate with minimal modifications to the video servers and the clients. In our evaluations using extensive ns-3 simulations and a testbed implementation for serving videos over TCP, we observe that deploying InSite achieves several folds reduction in playout stalls over a system without InSite.

Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5).

We study efficient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as a number of servers implementing the data structure. We determine the exact conditions under which every read and write involves one round of communication with the servers. These conditions relate the number of readers to the tolerated number of faulty servers and the nature of these failures.

In this paper we present a new channel allocation scheme for IEEE 802.11 based mesh networks with point-to- point links, designed for rural areas. Our channel allocation scheme allows continuous full-duplex data transfer on every link in the network. Moreover, we do not require any synchronization across the links as the channel assignment prevents cross link interference. Our approach is simple. We consider any link in the network as made up of two directed edges. To each directed edge at a node, we assign a non-interfering IEEE 802.11 channel so that the set of channels assigned to the outgoing edges is disjoint from channels assigned to the incoming edges. Evaluation of this scheme in a testbed demonstrate throughput gains of between 50 - 100%, and significantly less end-to-end delays, over existing link scheduling/channel allocation protocols (such as 2P [11]) designed for point-to-point mesh networks. Formally speaking, this channel allocation scheme is equivalent to an edge-coloring problem, that we call the directed edge coloring (DEC) problem. We establish a relationship between this coloring problem and the classical vertex coloring problem, and thus, show that this problem is NP-hard. More precisely, we give an algorithm that, given k vertex coloring of a graph can directed edge color it using xi(k) colors, where xi(k) is the smallest integer n such that (lfloorn/2rfloor/n ) ges k.

IEEE 802.11 WiFi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antennas that can establish long-distance wireless point-to-point links. Some nodes in the network (called gateway nodes) are directly connected to the wired internet, and the remaining nodes connect to the gateway(s) using one or more hops. The dominant cost of constructing such a mesh network is the cost of constructing antenna towers at nodes. The cost of a tower depends on its height, which in turn depends on the length of its links and the physical obstructions along those links. We investigate the problem of selecting which links should be established such that all nodes are connected, while the cost of constructing the antenna towers required to establish the selected links is minimized. We show that this problem is NP-hard and that a better than O(log n) approximation cannot be expected, where n is the number of vertices in the graph. We then present the first algorithm in the literature, for this problem, with provable performance bounds. More precisely, we present a greedy algorithm that is an O(log n) approximation algorithm for this problem. Finally, through simulations, we compare our approximation algorithm with both the optimal solution, and a naive heuristic.

IEEE 802.11 Wi-Fi equipment based wireless mesh networks have recently been proposed as an inexpensive approach to connect far-flung rural areas. Such networks are built using high-gain directional antenna that can establish long-distance point-point links. In recent work, a new MAC protocol named 2P has been proposed that is suited for the interference pattern within such a network. However, the 2P protocol requires the underlying graph (for each 802.11 channel) to be bi-partite. Under the assumption that 2P is the MAC protocol used in the mesh network, we make the following contributions in this paper. GivenKnon-interfering 802.11 channels, we propose a simple cut-based algorithm to computeKbi-partite sub-graphs (on each of which the 2P protocol can be run separately). We establish the class of graphs that can thus be completely covered byKbipartite subgraphs. For the remaining set of graphs, we look into the "price" of routing all end-to-end demands overonlythe bipartite subgraphs. We analytically establish what fraction of the max flow of the original mesh-graph can be routed over the bipartite subgraphs. Finally we look into the problem of mismatch between the load on a link (as computed by max flow) and its effective capacity under a given channel allocation. We propose heuristics to cluster links with similar loads into the same bipartite graphs (channels) and through comprehensive numerical simulations show that our heuristics come very close to the best possible flow.

Agreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the number of communication rounds needed to achieve a global decision, i.e., for all nonfaulty (correct) processes to reach a decision. This paper studies the time-complexity of local decisions in agreement problems, which we define as the number of communication rounds needed for at least one correct process to decide. We explore bounds for early local decision that depend on the number f of actual failures (that occur in a given run of an algorithm), out of the maximum number t of failures tolerated (by the algorithm). We first consider the synchronous message-passing model where we give tight local decision bounds for three variants of agreement: consensus, uniform consensus, and (nonblocking) atomic commit. We use these results to (1) show that, for consensus, local decision bounds are not compatible with global decision bounds (roughly speaking, they cannot be reached by the same algorithm), and (2) draw the first sharp line between the time-complexity of uniform consensus and atomic commit. Then we consider the eventually synchronous model, where we give tight local decision bounds for synchronous runs of uniform consensus. (In this model, consensus and uniform consensus are similar, atomic commit is impossible, and one cannot bound the number of rounds to reach a decision in nonsynchronous runs of consensus algorithms.) We prove a counterintuitive result that the early local decision bound is the same as the early global decision bound. We also give a matching early deciding consensus algorithm that is significantly better than previous eventually synchronous consensus algorithms.

It is well known that the consensus problem can be solved in a distributed system if, after some time T/sub S/, no process fails and there is some upper bound /spl delta/ on how long it takes to deliver a message. We know of no existing algorithm that guarantees consensus among N processes before time T/sub S/+O(N/spl delta/). We show that consensus can be achieved by time T/sub S/+O(/spl delta/).

This paper addresses the problem of designing an efficient implementation of a basic atomic read-write data structure over an asynchronous message-passing system. In particular, we consider time-efficient implementations of this abstraction in the case of a single writer, multiple readers (also called a SWMR atomic register) and S servers: the writer, the readers, and t out of the S servers may fail by crashing. Previous implementations tolerate the failure of any minority of servers (i.e., t < S/2) and require one communication round-trip for every write, and two round-trips for every read.We investigate the possibility of fast implementations, namely, implementations that complete both reads and writes in one round-trip. We show that, interestingly, the existence of a fast implementation depends on the maximum number of readers considered. More precisely, we show that a fast implementation is possible if and only if the number of readers is less that S t-2. We also show that a fast implementation is impossible in a multiple writers setting when t ≥ 1.Our results draw sharp lines between the time-complexity of regular and atomic register implementations, as well as between single-writer and multi-writer implementations. The results lead also to revisit, in a message-passing context, the folklore theorem that "atomic reads must write".

This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault detectors.We show that any ⋄P-based t-resilient consensus algorithm requires at least t + 2 rounds for a global decision even in runs that are synchronous. We then prove the bound to be tight by exhibiting a new ⋄P-based t-resilient consensus algorithm that reaches a global decision at round t + 2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we knew of (which requires 2t + 2 rounds).We contrast our lower bound with the well-known t + 1 round tight lower bound on consensus for the synchronous model, pointing out the price of indulgence.

This paper describes a flexible and general purpose PKI platform. Providing an easily interoperable security infrastructure. Developed at AT&T Labs, the architecture is part of the UCAID/Internet2 efforts in PKI and scalable security. The architecture can host multiple certificate authorities (CAs) from different vendors in a uniform and scalable manner. This facilitates scalable operation with third-party CA systems. It acts as a CA distributor driven by uniform enrollment procedures based on vendor independent PKI policies. The design of seamless integration facilitates easy integration with third party CA services such as Verisign. The architecture adapts software components into a framework for secure, authenticated IP services over the open Internet or within internal intranets. Policy descriptions, written in XML, support explicit controls upon certificate sources and contents. These XML-encoded policies define issuance and acceptance of X.509v3 certificates from multiple CAs supporting the obligations and warrantees, even if the policy is neither recorded anywhere nor referenced in the certificate. The PKI component has been developed within a general middleware platform.

Discusses the Address Resolution Protocol (ARP) and the problem of ARP cache poisoning. ARP cache poisoning is the malicious act, by a host in a LAN, of introducing a spurious IP address to MAC (Ethernet) address mapping in another host's ARP cache. We discuss design constraints for a solution: the solution needs to be implemented in middleware, without any access or change to any operating system source code, it needs to be backward-compatible with the existing protocol and to be asynchronous. We present our solution and implementation aspects of it in a Streams-based networking subsystem. Our solution comprises two parts: a "bump in the stack" Streams module, and a separate Stream with a driver and user-level application. We also present the algorithm that is executed in the module and application to prevent ARP cache poisoning where possible, and to detect and raise alarms otherwise. We then discuss some limitations with our approach and present some preliminary performance figures for our implementation.