Joint routing, scheduling, and resource allocation in multi-hop networks: from wireless ad-hoc networks to distributed computing networks

This thesis includes the five works that I did during my Ph.D. study by now. ❧ In the first work, algorithms are suggested and analyzed for routing in multi-hop wireless ad-hoc networks that exploit mutual information accumulation as the physical layer transmission scheme, and are capable of routing multiple packet streams (commodities) when only the average channel state information is present, and that only locally. The proposed algorithms are modifications of the Diversity Backpressure (DIVBAR) algorithm, under which the packet whose commodity has the largest ''backpressure metric'' is chosen to be transmitted and is forwarded through the link with the largest differential backlog (queue length). In contrast to traditional DIVBAR, each receiving node stores and accumulates the partially received packet in a separate ''partial packet queue'', thus increasing the probability of successful reception during a later possible retransmission. Two variants of the algorithm are presented: DIVBAR-RMIA, under which all the receiving nodes clear the received partial information of a packet once one or more receiving nodes firstly decode the packet; and DIVBAR-FMIA, under which all the receiving nodes retain the partial information of a packet until the packet has reached its destination. The network capacity region with the Renewal Mutual Information Accumulation (RMIA) transmission scheme is proposed and is proved to be (under certain mild conditions) strictly larger than the network capacity region with the Repetition (REP) transmission scheme that is used by the traditional DIVBAR. DIVBAR-RMIA is proved to be throughput-optimal among the polices with RMIA, i.e., it achieves the network capacity region with RMIA, which in turn demonstrates that DIVBAR-RMIA outperforms traditional DIVBAR on the achievable throughput. Moreover, DIVBAR-FMIA is proven to perform at least as well as DIVBAR-RMIA with respect to throughput. Simulations also confirm these results. ❧ In the second work, joint routing, scheduling, and resource allocation to maximize the throughput of OFDMA based wireless ad-hoc networks is considered subject to MAC layer and network layer constraints. Comparing with previous work that assumes each subchannel to be orthogonally accessed by all network links through time sharing, the orthogonal multiple access (e.g., CDMA) is scheduled among the outgoing links of each node to each subchannel, and the interferences caused by other nodes is treated as noise. An iterative heuristic approach to decompose the original problem into subproblems is proposed, each of which can be solved approximately through linearization. Simulations demonstrate that, particularly in large networks, the proposed cross-layer design significantly outperforms the previously proposed ""orthogonal-only""' access. ❧ Distributed cloud networking enables the deployment of a wide range of services in the form of interconnected software functions instantiated over general purpose hardware at multiple cloud locations distributed throughout the network. The third work investigates the problem of optimal service delivery over a distributed cloud network, in which nodes are equipped with both communication and computation resources. The design of distributed online solutions that drive flow processing and routing decisions is addressed, along with the associated allocation of cloud and network resources. For a given set of services, each described by a chain of service functions, the cloud network capacity region is characterized and a family of dynamic cloud network control (DCNC) algorithms are designed that stabilize the underlying queuing system, while achieving arbitrarily close to minimum cost with a tradeoff in network delay. The proposed DCNC algorithms make local decisions based on the online minimization of linear and quadratic metrics obtained from an upper bound on the Lyapunov drift-plus-penalty of the cloud network queuing system. Minimizing a quadratic vs. a linear metric is shown to improve the cost-delay tradeoff at the expense of increased computational complexity. Our algorithms are further enhanced with a shortest transmission-plus-processing distance bias that improves delay performance without compromising throughput or overall cloud network cost. The throughput and cost optimality guarantees, convergence time analysis, and extensive simulations in representative cloud network scenarios are provided. ❧ Augmented information (AgI) services allow users to consume information that results from the execution of a chain of service functions that process source information to create real-time augmented value. Applications include real-time analysis of remote sensing data, real-time computer vision, personalized video streaming, and augmented reality, among others. In the fourth work, the problem of optimal distribution of AgI services over a wireless computing network is further considered, where nodes are equipped with both wireless communication and computing resources. The wireless computing network capacity region is characterized and a joint flow scheduling and resource allocation algorithm is designed that stabilizes the underlying queuing system while achieving a network cost arbitrarily close to the minimum, with a tradeoff in network delay. The solution captures the unique chaining and flow scaling aspects of AgI services, while exploiting the use of the the broadcast approach coding scheme over the wireless channel. ❧ In the fifth work, the design of fast approximation algorithms for the network function virtualization (VNF) service distribution problem (NSDP) is addressed, whose goal is to determine, in the centralized way, the placement of VNFs, the routing of service flows, and the associated allocation of cloud and network resources that satisfy client demands with minimum cost. We show that in the case of load-proportional costs, the resulting fractional NSDP can be formulated as a multi-commodity-chain flow problem on a cloud-augmented graph, and design a virtual queue-length based algorithm, named QNSD, that provides an O(ε) approximation in time O(1/ε). We then address the case in which resource costs are a function of the integer number of allocated resources and design a variation of QNSD that effectively pushes for flow consolidation into a limited number of active resources to minimize overall cloud network cost.