In 1985, Grassmann et al. (1985) published their celebrated paper, in which they introduced a numerically stable algorithm for computing the stationary probabilities of a finite-state Markov chain, one of the key performance quantities in both theory and applications. This algorithm later became the well-known GTH algorithm (or the state-reduction method) in the literature, becoming one of the standard algorithms in applied probability. In 1990, motivated by queueing applications, this algorithm was extended to deal with the stationary distributions of block-structured Markov chains with repeating rows by Grassmann and Heyman (1993). In this paper, we focus on the block-form GTH algorithm and organize it into two parts. In the first part, we connect the block-form GTH algorithm to censored Markov chains and the block-form R G -factorization. We show that the forward block-elimination and back block-form substitution of the block-form GTH algorithm are equivalent to solving a system formulated using the R G -factorization in two steps. We also show that this connection remains valid when the block-form GTH algorithm is extended to infinite-state Markov chains. It is well known that censoring an infinite-state Markov chain to a finite state space yields a stationary distribution that provides a best approximation to the stationary distribution of the original infinite-state Markov chain. In the second part, we first derive an explicit expression for the censored Markov chain from the infinite state space to a finite space for Markov chains of M / G / 1 type. Based on this expression, we propose a renormalized approximated censored transition matrix (RA-CM). The resulting stationary distribution is shown to be asymptotically optimal in terms of approximation error. We compare the approximation error of the RA-CM with the error arising from the last-block-column augmentation.

This paper tackles an online resource allocation problem with job transfers in communication networks. The system operates in discrete time, where at each time slot, the administrator reserves resources at servers for future job requests at a cost. The specificity here is that the jobs may be transferred between the servers to accommodate the demands best at an additional cost. Moreover, a violation cost is associated with each blocked job request. The goal is then to build an online policy that minimizes the overall cost. We propose a randomized online algorithm based on the exponentially weighted method that learns from the previous job request sequence. We prove that our algorithm enjoys a sub-linear in time regret, which indicates that the algorithm is adapting and learning from its experiences and is becoming more efficient in its decision-making as it accumulates more data. In addition, we test the performance of our algorithm on artificial data and compare it against a reinforcement learning method where we show that our proposed method outperforms the latter.

We propose a new approach for proportionally fair sharing of radio access resources (i.e., frequency carriers) in a 5G mobile environment. In particular, we formulate the multi-carrier scheduling problem as a game (played by different carriers) which results in proportionally fair user service rates at its equilibrium. We subsequently present a globally convergent algorithm to find the equilibrium point of the devised game, based on which we develop a frame-by-frame scheduling mechanism. We further discuss how to extend the proposed scheduling scheme to a multi-tenant setting in order to efficiently implement radio access network slicing in a 5G mobile system.

In this paper, we study cost-efficient and fair allocation of multiple types of resources in an environment of heterogeneous and self-organizing servers. To address this problem, we formulate an optimization problem which aims at minimizing the operational costs for all servers, while providing fairness across different users. We propose a fully distributed implementation to solve this problem. The proposed mechanism is shown to achieve envy-freeness among different users. Furthermore, we show how it captures the trade-off between cost-efficiency and fairness. We employ numerical experiments to show the effectiveness of our proposed mechanism in reducing operational costs for a geo-distributed data-center.

Efficient and fair allocation of multiple types of resources is a crucial objective in a cloud/distributed computing cluster. Users may have diverse resource needs. Furthermore, diversity in server properties/capabilities may mean that only a subset of servers may be usable by a given user. In platforms with such heterogeneity, we identify important limitations in existing multi-resource fair allocation mechanisms, notably Dominant Resource Fairness and its follow-up work. To overcome such limitations, we propose a new server-based approach; each server allocates resources by maximizing a per-server utility function. We propose a specific class of utility functions which, when appropriately parameterized, adjusts the trade-off between efficiency and fairness, and captures a variety of fairness measures (such as our recently proposed Per-Server Dominant Share Fairness ). We establish conditions for the proposed mechanism to satisfy certain properties that are generally deemed desirable, e.g., envy-freeness, sharing incentive, bottleneck fairness, and Pareto optimality. To implement our resource allocation mechanism, we develop an iterative algorithm which is shown to be globally convergent. Subsequently, we show how the proposed mechanism could be implemented in a distributed fashion. Finally, we carry out extensive trace-driven simulations to show the enhanced performance of our proposed mechanism over the existing ones.

Users of cloud computing platforms pose different types of demands for multiple resources on servers (physical or virtual machines). Besides differences in their resource capacities, servers may be additionally heterogeneous in their ability to service users - certain users' tasks may only be serviced by a subset of the servers. We identify important shortcomings in existing multi-resource fair allocation mechanisms - Dominant Resource Fairness (DRF) and its follow up work - when used in such environments. We develop a new fair allocation mechanism called Per-Server Dominant-Share Fairness (PS-DSF) which we show offers all desirable sharing properties that DRF is able to offer in the case of a single “resource pool” (i.e., if the resources of all servers were pooled together into one hypothetical server). We evaluate the performance of PS-DSF through simulations. Our evaluation shows the enhanced efficiency of PS-DSF compared to the existing allocation mechanisms. We argue how our proposed allocation mechanism is applicable in cloud computing networks and especially large scale data-centers.

We describe a scheduler for multiple servers shared among different packet-flows, where each packet-flow may be served by only a subset of available (preferred) servers. The scheduler allocates tokens to flows in a round-by-round manner, where token allocation to flows at the beginning of each round is weighted max-min fair. We present a packet scheduling scheme where when a server becomes free, it is allocated to serve the HOL packet of an eligible flow with the maximum remaining tokens. The scheduling algorithm is applicable even when the capacity of servers are not known a priori and may vary over duration of a round. Numerical examples are given to illustrate that the scheduler itself is weighted max-min fair.

Relay technology is one of the key technologies for long-term evolution advanced (LTE-A) project. The introduction of relay will not only bring a wider coverage and higher capacity to the system but also lower the cost of network building. Multihop wireless relay technology plays an important role in next-generation mobile and wireless communication systems. Nowadays, we are witnessing the formation of a new technological marvel: Internet of Things (IoT). This formation is able to combine in a particular operational entity, all the bits and pieces of the world around us. In this paper, we perform queuing modeling of a two-hop wireless relay network and carry out performance analysis of end-to-end packet delay. In the two-hop wireless relay network, two groups of wireless nodes (WNs) and a single relay node (RN) are considered. A Poisson packet arrival process and IEEE 802.11 distributed coordination function are assumed in the network for the network traffic model and for regulating the nodes' access to the shared channel, respectively. We model a node as a single-server queuing system, whose service time of a packet is unknown and dependent on the probabilistic parameters of IEEE 802.11 DCF medium access control (MAC). A system of equations is then obtained for numerically computing the probabilistic parameters of IEEE 802.11 DCF MAC through discretization of the continuous-time network operations, based on which we construct semi-Markov processes and derive an analytic result for the expectation of the end-to-end packet delay. As a key performance indicator in evaluation of wireless networks, the packet delay result helps measure the efficiency of IEEE 802.11 MAC in two-hop wireless relay networks.

Recently, the use of digital beamforming (DBF) antennas has been drawing lots of interest in airborne platforms for resolving the network partition problem in airborne mobile ad hoc networks (MANETs). In this paper, properties of the network capacity of an airborne MANET with DBF antennas are investigated. This paper considers an ad hoc network consisting of a number of uniformly distributed airborne platforms in a bounded area. These platforms are either directly or indirectly connected with each other through DBF antennas, and form an airborne MANET. We first formulate a digital beamforming antenna system model, referred to as the omni-direction plus sector (OPS) model, and then carry out an exact analysis for the network capacity. The OPS model characterizes the radiation pattern of a DBF antenna. Under the condition that a Hamiltonian path exists in the network, an explicit expression is derived for the network capacity. We show that, for fixed values of the OPS model, the network capacity increases as the network size increases until it reaches an optimal value. If the network size continues to increase, the network capacity will decrease until it reaches zero. Explicit expressions for the optimal network size and the maximum network capacity are also obtained. Finally, numerical results are presented. It is shown that both the optimal network size and the maximum network capacity increase as the antenna beamwidth decreases. They increase slowly when the beamwidth is large, but as the antenna beam becomes narrower, they increase faster.

In-order delivery of packets is a key issue in data communication networks. Re-sequencing delay and re-sequencing buffer size are two important measures in design, performance and optimization. In this paper, a large deviation result is proved for the re-sequencing buffer, which is fed bymparallelM/M/1 queues. The result provides a limit for the probability of a large buffer. This limit can be significantly simplified when themparallelM/M/1 queues are symmetric; that is, with the same arrival and service rates, respectively. The large deviation result obtained in this paper extends a recent result in the literature.

In multipath packet data networks, packets may reach the receiver out-of-sequence, i.e., packets arrive at the receiver in a sequence different from their egressing order at the transmitter. In practice, however, many applications require an in-sequence packet delivery, meaning that packets need to be delivered to an application on the receiver in their original order at the transmitter. The in-sequence packet delivery is usually implemented through the approach of packet resequencing. In this paper, a multipath data network with packet resequencing is modeled and the asymptotic properties of the steady-state probability distribution of the resequencing queue length are studied. The assumptions used are that the packets sent from the transmitter according to a Poisson process, and the transmission period of a packet along a route follows an exponential distribution. An asymptotic distribution function of the resequencing queue length is derived for a large queue length in the steady state of the network. Numerical and simulation examples are presented to validate the derived result. Through comparisons of large deviation and asymptotic values of the resequencing queue length distribution, we show that the asymptotic result provides a better approximation to the distribution function of the resequencing queue length than the large deviation result reported in the literature.

This paper proposes a new data compression algorithm to store the routing table in a tree structure using very little memory. This data structure is tailored to a hardware design reference model presented in this paper. By exploiting the low memory access latency and high bandwidth of on-chip memory, high-speed packet forwarding can be achieved using this data structure. With the addition of pipeline in the hardware, IP address lookup can only be limited by the memory access speed. The algorithm is also flexible for different implementation. Experimental analysis shows that, given the memory width of 144 bits, our algorithm needs only 400kb memory for storing a 20k entries IPv4 routing table and five memory accesses for a search. For a 1M entries IPv4 routing table, 9Mb memory and seven memory accesses are needed. With memory width of 1,068 bits, we estimate that we need 100Mb memory and six memory accesses for a routing table with 1M IPv6 prefixes.

In order to provide more value-added services, the Internet needs to classify packets into flows for different treatment. This function becomes a bottleneck in the router. High performance packet classification algorithms are therefore in high demand. This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is not sensitive to the size of the rule table or to the percentage of wildcards in the fields. It also scales well from two-dimensional classifiers to high-dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed. The update algorithm proposed is also very fast in general.

We present an efficient IP packet forwarding technique and its architecture. One forwarding table is decomposed into two balanced smaller sub-forwarding tables by a novel splitting rule. Therefore, an IP lookup can be converted into a pair of small sub-lookups. The output of an incoming packet can be determined by comparing the information, attached to the matching sub-prefixes of both sub-lookups. The sub-lookups and information comparison can perform in parallel. Our approach not only speeds up the Best Matching Prefix (BMP) search, but also reduces storage space at the same time.

This paper describes a new algorithm for packet classification using the concept of independent sets. The algorithm has very small memory requirements. The search speed is neither sensitive to the rule table nor to the percentage of wildcards in the fields. It also scales well from two dimensional classifiers to high dimensional ones. In particular, the algorithm is inherently parallel. Hardware tailored to this algorithm can achieve very fast search speed.