The Bitcoin blockchain is a secure, distributed ledger that enables trusted transactions across untrusted entities. However, many applications need much faster transaction confirmation than that of the current Bitcoin blockchain. In this paper, we present a high-throughput, low-latency, deterministic confirmation mechanism called ACCEL for accelerating Bitcoin's block confirmation mechanism. Our key idea for achieving faster confirmation is the quick identification of singular blocks that provably belong to the blockchain. While it is impossible to determine with certainty if a block belongs to a blockchain when network delays are unbounded, singular block detection exploits the fact that the end-to-end latency between Bitcoin miners is substantially lower than the inter-block spacing and can be assumed to be upper bounded. ACCEL is especially suitable for low-latency, permissioned blockchains, where the block spacing can be optimized to the blockchain's small latencies to greatly improve throughput. We evaluate ACCEL's performance with extensive simulations and with a real implementation built with minimal changes to and fully compatible with the Bitcoin blockchain. We show that with appropriate bounds on the end-to-end latency, it is possible to reduce transaction confirmation latencies to milliseconds with ACCEL, and so meet the performance needs of a wide range of applications.

Packet networks need to maintain the state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best, we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor 2. Finally, we provide the empirical results illustrating the effectiveness of the proposed algorithm.

Existing security mechanisms for managing the Internet infrastructural resources like IP addresses, AS numbers, BGP advertisements and DNS mappings rely on a Public Key Infrastructure (PKI) that can be potentially compromised by state actors and Advanced Persistent Threats (APTs). Ideally the Internet infrastructure needs a distributed and tamper-resistant resource management framework which cannot be subverted by any single entity. A secure, distributed ledger enables such a mechanism and the blockchain is the best known example of distributed ledgers.

The advent of virtualization, containerization and the Internet of Things (IoT) is leading to an explosive growth in the number of endpoints. Ideally with Software Defined Networking (SDN), one would like to customize packet handling for each of these endpoints or applications. However this typically leads to a large growth in forwarding state. This growth is avoided in current networks by using aggregation which trades off fine-grained control of micro-flows for reduced forwarding state. It is worthwhile to ask whether the benefits of micro-flow control can be retained without a large growth in forwarding state and without using aggregation. In this paper we describe an incrementally deployable SDN-friendly packet forwarding mechanism called Path Switching that achieves this by compactly encoding a packet's path through the network in the packet's existing address fields. Path Switching provides the same reduction in forwarding state as source routing while retaining the benefits and use of fixed size packet headers and existing protocols.

Packet networks need to maintain state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet's desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor 2. Finally, we provide empirical results illustrating the effectiveness of the proposed algorithm.

We propose multi-class signaling overload control algorithms, for telecommunication switches, that are robust against different input traffic patterns and system upgrades. In order to appropriately measure the system load when several classes of signaling traffic are present, we first introduce the concept of equivalent system load measure that converts the multiple system measures associated with different classes of traffic into a single measure with respect to a pre-defined base class. We use this measure to develop three multi-class overload detection and measurement algorithms. Next, we develop a new algorithm for partitioning the allowable equivalent system load across multiple traffic classes, using a strict priority scheme. Using simulations of call flows from mobile telecommunications standards, we compare different multi-class overload algorithms under a variety of overload conditions. Our simulation results indicate that our algorithm that measures system load using a combination of request acceptance rate and processor occupancy provides highly reactive and robust overload control. Last, for the purpose of making the overload control algorithms more robust, we propose a measurement-based simple regression technique to dynamically estimate key system parameters. We find that estimates derived in this manner converge rapidly to their true values.

Telecommunication switches implement overload controls to maintain call throughput and delay at acceptable levels during periods of high load. Existing work has mostly focused on controls under sustained overload-they do not meet the demands of modern telecommunication systems where the increased number of services and mobile subscribers often creates fast changing hot spots. We introduce new algorithms that are designed to be highly reactive to sudden bursts of load. One algorithm is a modified version of RED for signaling traffic that measures the queue size. The second algorithm uses two measures: call acceptance rate and processor occupancy. Using simulations of realistic system models, we compare these new algorithms with each other and an existing algorithm that uses processor occupancy only. Our simulation results and qualitative arguments show that the combination of acceptance rate and processor occupancy results in a highly reactive and robust signaling overload control.