Hyperledger Fabric, a prominent permissioned blockchain platform, offers concurrent transaction processing via its Optimistic Concurrency Control (OCC) feature. However, conflicts arise when multiple transactions access the same data, severely impacting Fabric’s throughput. To reduce transaction conflicts, we draw inspiration from CSMA/CA, a wireless network medium access control protocol that uses Randomized Exponential Backoff (REB) to avoid packet collisions. Based on REB, we design Fabric/CA, a client-side transaction submission protocol designed to reduce transaction conflicts. By mitigating the computational waste caused by conflicts, Fabric/CA substantially improves Fabric’s performance. Our experiments show that under a high-contention workload, Fabric/CA achieves a reduction of over $98 \%$ in transaction conflicts, and boosts Fabric’s goodput by more than 10x.

Due to the increasing number of switching devices, failures regularly occur in modern computer networks. When a packet encounters a failed link, it is forwarded along a failover route. In fast rerouting, failover routes can be established quickly based on the pre-installed forwarding entries without the involvement of the control plane. Most prior research on fast rerouting sacrifices the quality of failover routes (e.g., the length of the failover route) for packet delivery guarantee. In this paper, we propose a fast rerouting framework that consists of two forwarding modes, the optimistic mode and the fallback mode. After a packet encounters the first failed link, it is forwarded in the optimistic mode, whose goal is solely to optimize the quality of failover routes. If the optimistic mode fails to find a high-quality failover route, the proposed framework then adopts the fallback mode, which can employ any fast rerouting algorithm that guarantees packet delivery. The simulation results show that the proposed framework can significantly shorten the failover routes and thus reduce the end-to-end delay. We believe that the proposed framework can also optimize other performance metrics related to failover routes.

We study fair multi-resource allocation in Network Function Virtualization (NFV) clusters, where the relative amounts of (multiple) resources allocated for a virtual network function (VNF) can be flexibly adjusted. In NFV clusters, the fairness across users can benefit from the flexibility of the multi-resource allocation for VNFs, but we also have to address a research challenge: What relative amounts of resources should be allocated to a VNF? Although many studies address fair multi-resource allocation in the literature, they all assume that the relative amounts of resources allocated for a VNF are pre-determined and fixed, which would lead to the poor fairness across users. In this paper, we make the first attempt to propose an algorithm to allocate resources to users under the circumstance of flexible multi-resource allocation for VNFs. Our algorithm is shown to achieve max-min fairness and satisfy two beneficial properties of fair multi-resource allocation: Pareto efficiency and envy-freeness. Simulations also show our algorithm can allocate resources in a fair and efficient way in NFV clusters.

We consider a transmission scheduling problem in which multiple agents receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall Age of Information (AoI). We call this problem the Min-AoI problem. Several special cases of the problem are known to be solvable in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r ≥ 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-AoI problem. Second, we give a randomized 2.619-approximation algorithm, a randomized 3-approximation algorithm, which outperforms the previous one in certain scenarios, and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-AoI problem is NP-hard.

We consider a transmission scheduling problem in which multiple systems receive update information through a shared Time Division Multiple Access (TDMA) channel. To provide timely delivery of update information, the problem asks for a schedule that minimizes the overall age of information. We call this problem the Min-Age problem. This problem is first studied by He et at. [IEEE Trans. Inform. Theory, 2018], who identified several special cases where the problem can be solved optimally in polynomial time. Our contribution is threefold. First, we introduce a new job scheduling problem called the Min-WCS problem, and we prove that, for any constant r ≥ 1, every r-approximation algorithm for the Min-WCS problem can be transformed into an r-approximation algorithm for the Min-Age problem. Second, we give a randomized 2.733-approximation algorithm and a dynamic-programming-based exact algorithm for the Min-WCS problem. Finally, we prove that the Min-Age problem is NP-hard.

In this paper, we focus on the design of consensus algorithms for permission-based blockchains, i.e., private blockchains. In most consensus algorithms, blocks are proposed by a specific role called “leader”. In this paper, we introduce a new role called “witness” to supervise the leader. The presence of the witness facilitates the design of the consensus algorithm. We propose a witness-based consensus algorithm that guarantees safety and liveness. We implemented this consensus algorithm on Go Ethereum. The experimental result shows that in a blockchain where four nodes participate in the consensus process, we can achieve a throughput of 1000 transactions per second (TPS). Even if these four nodes are located on different continents, and one of them is faulty, we can still achieve a throughput of 300 TPS. Finally, we find that during the experiment, a significant portion of time is spent on activities other than the consensus task. The result suggests that to further increase the throughput of a private blockchain, the consensus task and non-consensus activities should be considered jointly.

Recently, Network Function Virtualization (NFV) has been proposed to transform from network hardware appliances to software middleboxes. Normally, a demand needs to invoke several Virtual Network Functions (VNFs) in a particular order following the service chain along a routing path. In this paper, we study the joint problem of VNF placement and path selection to better utilize the network. We discover that the relation between the link and server usage plays a crucial role in the problem. We first propose a systematic way to elastically tune the proper link and server usage of each demand based on network conditions and demand properties. In particular, we compute a proper routing path length, and decide, for each VNF in the service chain, whether to use additional server resources or to reuse resources provided by existing servers. We then propose a chain deployment algorithm to follow the guidance of this link and server usage. Via simulations, we show that our design effectively adapts resource usage to network dynamics, and, hence, serves more demands than other heuristics.

In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist and consider the cases where the link quality is not perfect. We show that these problems are NP-complete and propose$O(1)$-approximation algorithms for each of them. Simulations show that the proposed algorithms have good performance in terms of energy cost.

Unlike conventional omnidirectional antennas, switched beam antennas exploit antenna arrays and signal processing techniques to focus energy in a specific beam-width and orientation. Recent research has shown that access points of a WLAN can exploit such switched beam antennas to increase the overall network capacity. The achievable sum rate of a WLAN with switch beam antennas is however mainly determined by how each AP selects its beam, including the orientation and width, and how each client associates with a proper AP. The goal of this paper is to solve the Joint Beam configuration and Client association (JBC) problem such that the sum rate of all clients in the network can be maximized. We formulate the JBC problem as a mixed integer linear programming model, and propose a 2-approximation algorithm to solve it. Our proposed algorithm has two distinctive properties: 1) it can be realized as a distributed protocol that allows the APs to configure their beams without the help of a central coordinator, and 2) it can be generally applied both in specific scenarios, where exact client locations are known, and in uncertain scenarios, where only geographic client distribution is given. Finally, we adjust the sum-rate maximization algorithm to the throughput maximization algorithm, which further takes medium sharing among clients into account. The simulation results show that the proposed algorithm outperforms both WLANs using omnidirectional antennas and other heuristics using switched beam antennas.

In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We find that many goals for network deployment, such as maximizing the number of covered users, the size of the coverage area, or the total throughput of the network, can be modeled with a submodular set function. Specifically, given a set of routers, the goal is to find a set of locations S, each of which is equipped with a router, such that S maximizes a predefined submodular set function. However, this deployment problem is more difficult than the traditional maximum submodular set function problem, e.g., the maximum coverage problem, because it requires all the deployed routers to form a connected network. In addition, deploying a router in different locations might consume different costs. To address these challenges, this paper introduces two approximation algorithms, one for homogeneous deployment cost scenarios and the other for heterogeneous deployment cost scenarios. Our simulations, using synthetic data and real traces of census in Taipei, Taiwan, show that the proposed algorithms achieve better performances than other heuristics.

In multiuser MIMO (MU-MIMO) LANs, the achievable throughput of a client depends on who is transmitting concurrently with it. Existing MU-MIMO MAC protocols, however, enable clients to use the traditional 802.11 contention to contend for concurrent transmission opportunities on the uplink. Such a contention-based protocol not only wastes lots of channel time on multiple rounds of contention but also fails to maximally deliver the gain of MU-MIMO because users randomly join concurrent transmissions without considering their channel characteristics. To address such inefficiency, this paper introduces MIMOMate, a leader-contention-based MU-MIMO MAC protocol that matches clients as concurrent transmitters according to their channel characteristics to maximally deliver the MU-MIMO gain while ensuring all users fairly share concurrent transmission opportunities. Furthermore, MIMOMate elects the leader of the matched users to contend for transmission opportunities using traditional 802.11 CSMA/CA. It hence requires only a single contention overhead for concurrent streams and can be compatible with legacy 802.11 devices. A prototype implementation in USRP N200 shows that MIMOMate achieves an average throughput gain of 1.42× and $1.52× over the traditional contention-based protocol for two- and three-antenna AP scenarios, respectively, and also provides fairness for clients.

In this paper, we investigate the wireless network deployment problem, which seeks the best deployment of a given limited number of wireless routers. We found that many goals for network deployment, such as maximizing the number of covered users or areas, or the total throughput of the network, can be modelled with the submodular set function. Specifically, given a set of routers, the goal is to find a set of locations S, each of which is equipped with a router, such that S maximizes a predefined submodular set function. However, this deployment problem is more difficult than the traditional maximum submodular set function problem, e.g., the maximum coverage problem, because it requires all the deployed routers to form a connected network. In addition, deploying a router in different locations might consume different costs. To address these challenges, this paper introduces two approximation algorithms, one for homogeneous deployment cost scenarios and the other for heterogeneous deployment cost scenarios. Our simulations, using synthetic data and real traces of census in Taipei, show that the proposed algorithms achieve a better performance than other heuristics.

In many applications, it is a basic operation for the sink to periodically collect reports from all sensors. Since the data gathering process usually proceeds for many rounds, it is important to collect these data efficiently, that is, to reduce the energy cost of data transmission. Under such applications, a tree is usually adopted as the routing structure to save the computation costs for maintaining the routing tables of sensors. In this paper, we work on the problem of constructing a data aggregation tree that minimizes the total energy cost of data transmission in a wireless sensor network. In addition, we also address such a problem in the wireless sensor network where relay nodes exist. We show these two problems are NP-complete, and propose O(1)-approximation algorithms for each of them. Simulations show that the proposed algorithms each have good performance in terms of the energy cost.