Current blockchain systems suffer from a number of inherent drawbacks in its scalability, latency, and processing throughput. By enabling parallel confirmations of transactions, sharding has been proposed to mitigate these drawbacks, which usually requires frequent communication among miners through a separate consensus protocol.In this paper, we propose, analyze, and implement a new distributed and dynamic sharding system to substantially improve the throughput of blockchain systems based on smart contracts, while requiring minimum cross-shard communication. Our key observation is that transactions sent by users who only participate in a single smart contract can be validated and confirmed independently without causing double spending. Therefore, the natural formation of a shard is to surround one smart contract to start with. The complication lies in the different sizes of shards being formed, in which a small shard with few transactions tends to generate a large number of empty blocks resulting in a waste of mining power, while a large shard adversely affects parallel confirmations. To overcome this problem, we propose an inter-shard merging algorithm with incentives to encourage small shards to merge with one another and form a larger shard, an intra-shard transaction selection mechanism to encourage miners to select different subsets of transactions for validation, as well as a parameter unification method to further improve these two algorithms to reduce the communication cost and improve system reliability.We analyze our proposed algorithms using the game theoretic approach, and prove that they converge to a Nash Equilibrium. We also present a security analysis on our sharding design, and prove that it resists adversaries who occupy at most 33% of the computation power. We have implemented our designs on go-Ethereum 1.8.0 and evaluated their performance using both real-world blockchain transactions and large-scale simulations. Our results show that throughput has been improved by 7.2×, and the number of empty blocks has been reduced by 90%.

In memory computing and high-end distributed storage demand low latency, high throughput, and zero data loss simultaneously from datacenter networks. Existing reactive congestion control approaches cannot both minimize queuing latency and ensure zero data loss. A token-oriented proactive approach can achieve them together by controlling congestion even before sending data packets. However, state-of-the-art token-oriented approaches only strive to optimize network-level metrics: maximizing throughput while achieving flow-level fairness. This article answers the question of how to support objective-aware traffic scheduling in token-oriented approaches. The novelty of Token-Oriented in-network Prioritization (TOP) is that it prioritizes tokens instead of data packets. We make three contributions. Via simulations over a hypothetical TOP system, our first contribution is demonstrating the potential performance gain that can be brought by TOP. Second, we investigate the applicability of TOP. Although the overhead of enabling necessary TOP features in switches is trivial, we find that mainstream commodity datacenter switches do not support them. We hence propose a readily-deployable remedy to achieve in-network prioritization by pushing both switch and end-host hardware capacity to an extreme end. Lastly, we implement a running TOP system with Linux hosts and commodity switches, and evaluate TOP in testbeds and with large-scale simulations for various scenarios.

Link utilization has received extensive attention since data centers become the most pervasive platform for data-parallel applications. A specific job of such applications involves communication among multiple machines. The recently proposed coflow abstraction depicts such communication through a group of parallel flows, and captures application performance through corresponding communication requirements. Existing techniques to improve link utilization, however, either restrict themselves to achieving work conservation, or merely focus on flow-level metrics and ignore coflow-level performance. In this paper, we address the coflow-aware scheduling problem with the objective of maximizing link utilization. Through theoretic analyses, we formulate the coflow-aware scheduling problem as a NP-hard open shop scheduling problem with heterogeneous concurrency. We design Adia, a hierarchical scheduling framework to conduct both inter- and intra- link scheduling. The design of Adia leverages priority-based scheduling while guarantees work-conserving and starvation-free bandwidth allocation at the same time. We also prove Adia's algorithm is two-approximate in terms of link utilization. Extensive simulation results on ns3 further show that Adia outperforms both per-flow mechanisms coflow schemes in terms of link utilization, and achieves similar coflow performance in comparison with the state-of-art coflow scheduling schemes.

BBR is a congestion-based congestion control algorithm recently proposed by Google. It proactively measures the bottleneck bandwidth and round trip times (RTTs) of a connection pipe, based on which it governs its sending behaviors. Despite the significant throughput gains and latency reduction, some experimental studies reveal that BBR may result in a salient RTT-fairness problem, in that short-RTT flows can be starved of bandwidth allocation when comnetina with lons-R'I'T flows. In this paper, we study BBR's RTT-fairness problem from a theoretic perspective. We present a closed-form solution that characterizes the intrinsic dynamics of BBR flows and their interactions. Specifically, we model BBR's sending behaviors and bandwidth dynamics, based on which we establish an exponential relationship between the flows' bandwidth shares and their RTTs. We show that the degree of unfairness is dictated by the RTT ratio between two flows, irrespective of the other network parameters, such as the initial sending rates or link capacity. In particular, when the RTT ratio of the two flows is greater than 2, the short-RTT flow is starved of bandwidth allocation ( ≤ 0.1%), Our theoretical results are corroborated by simulations in a wide range of settings.

Link utilization has received extensive attention since datacenters become the most prevalent platform for data-parallel computing applications. A specific job of such applications involves communication among multiple machines. The coflow abstraction depicts such communication and captures application performance through corresponding network requirements. Existing techniques to improve link utilization, however, either restrict themselves to work conservation, or merely focus on flow-level metrics and ignore coflow-level performance. In this paper, we address the coflow-aware scheduling problem with the objective of maximizing link utilization. Through theoretic analyses, we formulate the coflow-aware scheduling problem as a NP-hard open shop scheduling problem with heterogeneous concurrency. Despite the hardness of this problem, we design Maluca, a hierarchical scheduling framework to conduct both inter- and intra-link scheduling. Maluca's algorithm is not only starvation-free and work-conserving, but also 2-approximate in terms of link utilization. Extensive simulation results demonstrate that Maluca outperforms both per-flow and coflow schemes in terms of link utilization, and achieves similar coflow performance in comparison with the state-of-art coflow scheduling schemes.

With the advent of big data processing frameworks, the performance of data-parallel applications is heavily affected by the time it takes to read input data, making it important to improve data locality. Existing methods in achieving data locality have primarily focused on selecting machines to place tasks of applications. Nevertheless, the set of machines that an application can choose from is determined by a cluster manager, which is oblivious to the location of data in existing resource sharing frameworks. In this paper, we design, implement and evaluate Custody, a new cluster management framework that helps to maximize data locality by allocating the executor processes with local access to data to those applications in need. Custody achieves this objective by dynamically collecting runtime information of an application's input data and by effectively allocating executors among and within applications through theoretic analyses of the data-aware resource sharing problem. With significantly better data locality, Custody avoids unnecessary network transfers and thus expedites job completion times. Our experimental results on a 100-node cluster demonstrate that Custody can improve the data locality for input tasks by 36.9% in comparison with Spark's default cluster manager. Meanwhile, it reduces the job completion times by 14.9% due to fewer network transfers.

Guaranteed performance for data-parallel applications is important for both service providers and cloud data centers that host such services. A job of data-parallel applications involves communication among multiple machines to transmit intermediate results. Such communication comprises a collection of parallel flows, which is abstracted as a coflow in recent proposals. In this paper, we study the problem of meeting deadlines for coflows in data center networks. Existing flow-level scheduling schemes are insufficient to guarantee the coflow-level performance, since a coflow can meet its deadline only when all its constituent flows finish on time. Due to the scarce bandwidth on the network bottleneck, it is vital to coordinate concurrent coflows to meet as many deadlines as possible. We present Chronos, a scheduling framework that captures the correlation of flows belonging to a coflow, and handles the resource allocation among multiple concurrent coflows. Chronos is work-conserving and starvation-free without integrating complicated admission control mechanisms. We show via extensive simulations on ns3 that Chronos can make 1.6× more coflows meet their deadlines compared to flow-level schemes.

Tasks in a data-parallel job communicate with each other through a number of concurrent flows, which is described as a coflow. These flows are correlated in the sense that the performance of a coflow is dictated by the flow that takes the longest time to complete. Minimizing coflow completion times, however, turns out to be a challenge, given the correlation across flows and how they are routed collectively through a datacenter network. In this paper, we propose Tailor, a simple yet effective mechanism with the objective of trimming the coflow completion times in a datacenter network. To achieve our objective, Tailor takes advantage of OpenFlow in a software-defined datacenter network. By monitoring and rerouting live flows to links with lighter loads, Tailor guarantees that the coflow completion time is minimized dynamically and converges to its lower bound. Our experimental results in both Mininet and large-scale simulations have shown that Tailor is much more effective than flow-level schemes when it comes to reducing coflow completion times. It also outperforms existing scheduling-only coflow mechanisms and achieves similar performance with the state-of-the-art hybrid mechanism, yet with much lower complexity.

Data-parallel applications, especially those associated with user-facing web services, have struggled to enhance their worst case performance. It is therefore important to improve the minimum amount of resources guaranteed for applications in a cluster. Existing cluster management frameworks, however, provide isolation for computation resources (such as CPU) only, and are oblivious to network isolation guarantees. In this paper, we design, implement and evaluate Libra, a new cluster management framework that helps to maximize the isolation guarantee for the bandwidth requirements from applications. We start with a theoretical analysis of the network sharing problem, which contains two key steps: container placement and bandwidth allocation. By collecting the status of access links and the bandwidth demand of applications, we coordinate the placement of containers to minimize the system bottleneck such that the bandwidth guarantee for applications can be optimized. We further embrace host-based rate limiting to ensure such maximized bandwidth guarantee can be reached without hurting network utilization. Both our testbed-based experiments and large-scale simulations demonstrate that Libra significantly improves the network isolation guarantee: in comparison with existing cluster managers and network schedulers, the performance gain is more than 105.59%. Meanwhile, it improves application performance by 57.71% and maintains high network utilization.

Even with the recent proliferation of in-memory computation in data-parallel frameworks (such as Spark), transfers over the network are still time-consuming. Similar to computation, network transfers serve as main roadblocks as we try to minimize job completion times. Existing schedulers were designed as isolated solutions that focused on computation or network performance only. Without any coordination, the utilization of computation and network resources may become unbalanced, leading to a reduced level of overall resource utilization. In this paper, we design, implement, and evaluate Symbiosis, a network-aware task scheduler designed to coordinate computation-bound and network-bound tasks in a large cluster, so that resources are utilized in a more balanced fashion. Symbiosis is an online scheduler that predicts resource imbalance before launching tasks, and correct such imbalance by co-locating computation-bound and network-bound tasks in the same executor process. As a guiding principle, it is engineered to be practically implemented within and to complement existing data-parallel frameworks. We have implemented Symbiosis within Spark, and carried out our experiments on a 100-node cluster. We show convincing evidence that Symbiosis reduces job completion times by 11.9% in comparison to Spark's current scheduler with little overhead.

In next-generation LTE-advanced cellular networks, device-to-device (D2D) communication has emerged as an effective way to offload cellular traffic and improve system performance. Conventionally, a device exclusively relies on cellular communication to retrieve the content it desires. With D2D communication, however, if the same piece of content is available in the vicinity of the device, the content can be directly retrieved from one of its neighbouring devices. Naturally, the key problem becomes how to maximize content sharing via D2D communication. Existing works on content sharing are mainly concerned with a multi-hop communication setting, while works on D2D communication have primarily focused on the communication aspects, including interference avoidance and energy efficiency. In this paper, we study the problem of maximizing cellular traffic offloading with D2D communication, by selectively caching popular content locally, and by exploring maximal matching for sender-receiver pairs. Specifically, we consider an interference-aware communication model and formulate selective caching as a Knapsack problem, and sender-receiver matching as a maximum weighted matching problem in a bipartite graph. We propose decentralized algorithms to solve both problems, and our simulation results demonstrate that our algorithms are effective in maximizing cellular traffic offloading.

Code offloading to remote infrastructures has been a common practice for mobile users who seek extra power or computing resources to perform computation-intensive tasks. Existing works, however, have so far mainly focused on code offloading from a single mobile device to remote cloud servers, which restricts the potential of code offloading only to devices with available Internet access. In this paper, we propose Circa, a new framework that demonstrates the feasibility of code offloading among multiple mobile devices in close proximity to one another, leveraging the presence of iBeacons. Our objective is to eliminate the costs incurred by running virtual machine instances in the cloud, and the need to connect remotely to the cloud as well. With the assistance of iBeacons, devices in the same vicinity can discover and support one another through collaborative code offloading with short-range communication, obviating the need for centralized servers. We have implemented Circa on the iOS platform and validated its feasibility using iOS devices. According to our experimental results, with more than two collaborators, Circa is capable of reducing the total execution time of an offloaded task substantially, while preserving satisfactory performance of the mobile application.

Even with modern physical-layer technologies in LTE networks, the capacity of cellular networks is still far from sufficient to satisfy the insatiable bandwidth demand of mobile applications. Owing to common interests among mobile users, Device-to-Device (D2D) communication has emerged as a viable alternative to offload cellular traffic, with the promise of substantially alleviating the need for cellular network bandwidth. In this paper, we first carry out an extensive theoretical analysis based on a game theoretic approach, and show that the objective of maximized cellular offloading is equivalent to maximizing the social welfare in a trading network, where the content to be shared is the commodity, and mobile users are buyers or sellers. We next design Rally, a set of distributed strategies that can converge to a sub game perfect Nash equilibrium in the content sharing game. Both our theoretical analyses and simulation results have shown the effectiveness of Rally, in that it can indeed maximize cellular traffic offloading through D2D communication.

Despite the growing deployment of 4G networks, the capacity of cellular networks is still insufficient to satisfy the ever-increasing bandwidth demand of mobile applications. Given the common interest of mobile users, Device-to-Device (D2D) communication has emerged as a promising solution to offload cellular traffic and enable proximity-based services. One of the main detriments for D2D communication is the lack of incentive for mobile users to share their content, since such sharing inevitably consumes limited resources and potentially jeopardizes user privacy. In this paper, we study the incentive problem in D2D communications. Specifically, we model the incentive in offloading scenario as an auction game. A trading network is constructed between an eNB and users, in which auctions are conducted to group offloading users and determine proper rewards. We further design a randomized auction mechanism to guarantee system efficiency and truthfulness. Extensive experiments verify the effectiveness of our mechanism in that it achieves a significant performance gain in comparison with baseline methods.