Recently, network function virtualization has been proposed to transform from network hardware appliances to software middleboxes. Normally, a demand needs to invoke several virtual network functions (VNFs) following the order determined by the service chain along a routing path. In this paper, we study the joint problem of the 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. Inspired by stress testing, we first propose a systematic way to elastically tune the link and server usage of each demand based on the network status and properties of demands. 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 that follows the guidance of this link and server usage. Via simulations, we show that our design effectively adapts resource allocation to network dynamics and, hence, serves more demands than other heuristics.
7 August 2020 in IEEE Transactions on Information Theory
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. This problem is first studied by He et al. [2], 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-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.
In this paper, we give a deterministic two-step Byzantine consensus protocol that achieves safety and liveness. A two-step Byzantine consensus protocol only needs two communication steps to commit in the absence of faults. Most two-step Byzantine consensus protocols exploit optimism and require a recovery protocol in the presence of faults. In this paper, we give a simple two-step Byzantine consensus protocol that does not need a recovery protocol.
We study the online minimum cost bipartite perfect matching with delays problem. In this problem, \(\varvec{m}\) servers and \(\varvec{m}\) requests arrive over time, and an online algorithm can delay the matching between servers and requests by paying the delay cost. The objective is to minimize the total distance and delay cost. When servers and requests lie in a known metric space, there is a randomized \(\varvec{O(\log n)}\)-competitive algorithm, where \(\varvec{n}\) is the size of the metric space. When the metric space is unknown a priori, Azar and Jacob-Fanani proposed a deterministic \(\varvec{O\left( \frac{1}{\epsilon }m^{\log \left( \frac{3+\epsilon }{2}\right) }\right) }\)-competitive algorithm for any fixed \(\varvec{\epsilon> 0}\). This competitive ratio is tight when \(\varvec{n = 1}\) and becomes \(\varvec{O(m^{0.59})}\) for sufficiently small \(\varvec{\epsilon }\). In this paper, we improve upon the result of Azar and Jacob-Fanani for the case where servers and requests are on the real line, providing a deterministic \(\varvec{\tilde{O}(m^{0.5})}\)-competitive algorithm. Our algorithm is based on the Robust Matching (RM) algorithm proposed by Raghvendra for the minimum cost bipartite perfect matching problem. In this problem, delay is not allowed, and all servers arrive in the beginning. When a request arrives, the RM algorithm immediately matches the request to a free server based on the request’s minimum \(\varvec{t}\)-net-cost augmenting path, where \(\varvec{t> 1}\) is a constant. In our algorithm, we delay the matching of a request until its waiting time exceeds its minimum \(\varvec{t}\)-net-cost divided by \(\varvec{t}\).