Deep Reinforcement Learning (DRL) has become a powerful tool for developing control policies in queueing networks, but the common use of Multi-layer Perceptron (MLP) neural networks in these applications has significant drawbacks. MLP architectures, while versatile, often suffer from poor sample efficiency and a tendency to overfit training environments, leading to suboptimal performance on new, unseen networks. In response to these issues, we introduce a switch-type neural network (STN) architecture designed to improve the efficiency and generalization of DRL policies in queueing networks. The STN leverages structural patterns from traditional non-learning policies, ensuring consistent action choices across similar states. This design not only streamlines the learning process but also fosters better generalization by reducing the tendency to overfit. Our work presents three key contributions: first, the development of the STN as a more effective alternative to MLPs; second, empirical evidence showing that STNs achieve superior sample efficiency in various training scenarios; and third, experimental results demonstrating that STNs match MLP performance in familiar environments and significantly outperform them in new settings. By embedding domain-specific knowledge, the STN enhances the Proximal Policy Optimization (PPO) algorithm's effectiveness without compromising performance, suggesting its suitability for a wide range of queueing network control problems.

Deep Reinforcement Learning (DRL) offers a powerful approach to training neural network control policies for stochastic queuing networks (SQN). However, traditional DRL methods rely on offline simulations or static datasets, limiting their real-world application in SQN control. This work proposes Online Deep Reinforcement Learning-based Controls (ODRLC) as an alternative, where an intelligent agent interacts directly with a real environment and learns an optimal control policy from these online interactions. SQNs present a challenge for ODRLC due to the unbounded nature of the queues within the network resulting in an unbounded state-space. An unbounded state-space is particularly challenging for neural network policies as neural networks are notoriously poor at extrapolating to unseen states. To address this challenge, we propose an intervention-assisted framework that leverages strategic interventions from known stable policies to ensure the queue sizes remain bounded. This framework combines the learning power of neural networks with the guaranteed stability of classical control policies for SQNs. We introduce a method to design these intervention-assisted policies to ensure strong stability of the network. Furthermore, we extend foundational DRL theorems for intervention-assisted policies and develop two practical algorithms specifically for ODRLC of SQNs. Finally, we demonstrate through experiments that our proposed algorithms outperform both classical control approaches and prior ODRLC algorithms.

We consider a system consisting of a single transmitter/receiver pair and N channels over which they may communicate. Packets randomly arrive to the transmitter's queue and wait to be successfully sent to the receiver. The transmitter may attempt a frame transmission on one channel at a time, where each frame includes a packet if one is in the queue. For each channel, an attempted transmission is successful with an unknown probability. The transmitter's objective is to quickly identify the best channel to minimize the number of packets in the queue over T time slots. To analyze system performance, we introduce queue length regret, which is the expected difference between the total queue length of a learning policy and a controller that knows the rates, a priori. One approach to designing a transmission policy would be to apply algorithms from the literature that solve the closely-related stochastic multi-armed bandit problem. These policies would focus on maximizing the number of successful frame transmissions over time. However, we show that these methods have Ω(log T) queue length regret. On the other hand, we show that there exists a set of queue-length based policies that can obtain order optimal O(1) queue length regret. We use our theoretical analysis to devise heuristic methods that are shown to perform well in simulation.

Throughput-optimal transmission scheduling in wireless networks has been a well considered problem in the literature, and the method for achieving optimality, MaxWeight scheduling, has been known for several decades. This algorithm achieves optimality by adaptively scheduling transmissions relative to each user's stochastic traffic demands. To implement the method, users must report their queue backlogs to the network controller and must rapidly respond to the resulting resource allocations. However, many currently-deployed wireless systems are not able to perform these tasks and instead expect to occupy a fixed assignment of resources. To accommodate these limitations, adaptive scheduling algorithms need to interactively estimate these uncooperative users' queue backlogs and make scheduling decisions to account for their predicted behavior. In this work, we address the problem of scheduling with uncooperative legacy systems by developing algorithms to accomplish these tasks. We begin by formulating the problem of inferring the uncooperative systems' queue backlogs as a partially observable Markov decision process and proceed to show how our resulting learning algorithms can be successfully used in a queue-length-based scheduling policy. Our theoretical analysis characterizes the throughput-stability region of the network and is verified using simulation results.

We consider a system consisting of a single transmitter and N channels. Packets randomly arrive to the transmitter's queue, and at each time slot a controller can schedule one of the N channels for transmission. The channel's rates are time-varying with unknown statistics and must be learned through observation. Our objective is to minimize the number of packets in the system's queue over T time slots. We define the regret of the system to be the expected difference between the total queue length of a controller that must learn the channels' average rates and a controller that knows the rates, a priori. One approach to solving this problem would be to apply algorithms from the literature that were developed to solve the closely-related stochastic multi-armed bandit problem. However, we show that these methods have Ω(log(T)) queue length regret. On the other hand, we show that there exists a set of queue-length based policies that are able to obtain order optimal, O(1), regret.

We study the problem of learning channel statistics in order to efficiently schedule transmissions in wireless networks subject to interference constraints. In particular, we focus on the primary interference model which requires that at any time the set of activated links be a matching in the corresponding graph. We propose a distributable algorithm that forms greedy matchings in the graph in order to learn the channels' transmission rates, while simultaneously exploiting previous observations to obtain high throughput. Comparison to the offline solution shows our algorithm to have good performance that scales well with the number of links in the network. We then turn our attention to the stochastic setting where packets randomly arrive to the network and await transmission in queues at the nodes. We develop a queue-length-based scheduling policy that uses the channel learning algorithm as a component. We analyze our method in time varying environments and show that it achieves the same stability region as that of a greedy matching policy with full channel knowledge (i.e., half of the full stability region).

Legacy networks are often designed to operate with simple single-path routing, like the shortest path, which is known to be throughput suboptimal. On the other hand, previously proposed throughput optimal policies (i.e., backpressure) require every device in the network to make dynamic routing decisions. In this paper, we study an overlay architecture for dynamic routing, such that only a subset of devices (overlay nodes) need to make the dynamic routing decisions. We determine the essential collection of nodes that must bifurcate traffic for achieving the maximum multi-commodity network throughput. We apply our optimal node placement algorithm to several graphs and the results show that a small fraction of overlay nodes is sufficient for achieving maximum throughput. Finally, we propose a threshold-based policy (BP-T) and a heuristic policy (OBP), which dynamically control traffic bifurcations at overlay nodes. Policy BP-T is proved to maximize throughput for the case when underlay paths do no overlap. In all studied simulation scenarios, OBP not only achieves full throughput but also reduces delay in comparison to the throughput optimal backpressure routing.

We consider an opportunistic communication system in which a secondary transmitter communicates over the unused time slots of a primary user. In particular, we consider a system in which the primary user is uncooperative and transmits whenever its buffer is nonempty, and the secondary user relies on feedback from its receiver in order to decide when to transmit. The objective of the secondary user is to maximize its own throughput without degrading the throughput of the primary user. We analyze the maximum achievable throughput of the secondary user by formulating the problem as a partially observable Markov decision process. We derive bounds on the optimal solution and find a channel access policy for the secondary user that is near-optimal when the primary user's exogenous arrival rate is low. These results are then used to characterize the set of arrival rates to the primary and secondary users that may be stably supported by the system.

In order to steer antenna beams towards one another for communication, wireless nodes with highly-directional antennas must track the channel state of their neighbors. To keep this overhead manageable, each node must limit the number of neighbors that it tracks. The subset of neighbors that each node chooses to track constitutes a network topology over which traffic can be routed. We consider this topology design problem, taking into account channel modeling, transmission scheduling, and traffic demand. We formulate the optimal topology design problem, with the objective of maximizing the scaling of traffic demand, and propose a distributed method, where each node rapidly builds a segment of the topology around itself by forming connections with its nearest neighbors in discretized angular regions. The method has low complexity and message passing overhead. The resulting topologies are shown to have desirable structural properties and approach the optimal solution in high path loss environments.

This paper presents a transport layer protocol for multi-path networks with blockage. Using urban SATCOM as an example, we see from data taken from a 2006 measurement campaign that these blockages are generally on the order of 1 -- 5seconds in length and the links are blocked approximately 33%of the time. To compensate for this type of impairment, we have developed a multipath IP overlay routing algorithm, a random linear coding reliability scheme, and a maximum-queue-based (MQCC) congestion control algorithm. MQCC uses average buffer occupancy as a measure of the congestion in a network (as opposed to packet loss or round trip time (RTT)) and updates the transmission rate of each source to avoid network congestion. This allows us to design a congestion control algorithm that is independent of the channel conditions and can be made resilient to channel losses. The reliability scheme uses selective negative acknowledgments (Snacks) to guarantee packet delivery to the destination. We show through simulation that we can approach the optimal benchmark in realistic loss blockage channels.

Blockage of communication links due to environmental obstructions and the resulting on/off channel behavior present challenges for providing reliable communication in mobile wireless networks. Traditional reliability techniques such as forward error correction and automatic repeat request (ARQ) are not designed to operate at the timescales typically observed in blockage channels. This work presents an approach to overcoming blockage that consists of multipath routing coupled with end-to-end rateless coding. In order to provide compatibility with operational IP networks as well as the possibility of incremental deployment, these techniques can be implemented as a routing overlay. We present algorithms to compute the maximum throughput achievable through this routing overlay approach, as well as a specific scheme to implement a multipath routing overlay in an IP network. Finally, we provide results from testing this approach on a mobile wireless network with satellite communication links. In our test scenario, satellite links suffer blockage from buildings in an urban setting. Our results characterize multipath routing overlay performance, which depends on the responsiveness of the underlay routing scheme.

We consider the problem of transmitting a collection of packets from a source node to a destination node across a relay network. We analyze a simple random network coding scheme where each node transmits a random linear combination of packets each time it has an opportunity to transmit. The main result of this paper is an upper bound on the expected time to transmit a generation of packets across the network. We show that the expected time is bounded by the generation size divided by the capacity of the minimum cut separating the source from the destination, plus a term that grows as the square root of the generation size. We then use this bound to provide a queueing analysis of a strategy that dynamically creates generations as packets arrive in a queue at the network's source node. To facilitate our analysis, we model the relay network by a continuous-time Markov chain. Our primary analytical tool is a general method for computing upper bounds on hitting times associated with continuous-time Markov chains. We believe that this approach also provides a method for analyzing transmission times associated with more general network topologies.

This work addresses the challenge in providing reliable communication in mobile networks with intermittent, on/off links through the use of a routing overlay designed to deal with these channel impairments. Link blockage is a predominant feature of mobile networks operating at 10+ GHz frequencies, and current techniques are ill-suited to address this problem. We present an approach comprised of multiple-path routing with end-to-end coding, queue-length-based congestion control, and a negative acknowledgement (NACK) loss-recovery scheme; these are implemented in an IP-overlay. The demonstrated scenario consists of two clusters of mobile ground vehicles operating in an ``urban canyon'' environment. Blockage occurs on satellite links connecting the clusters. Through the use of interactive displays, demo participants gain an understanding of routing behavior.

Legacy networks are often designed to operate with simple single-path routing, like shortest-path, which is known to be throughput suboptimal. On the other hand, previously proposed throughput optimal policies (i.e., backpressure) require every device in the network to make dynamic routing decisions. In this work, we study an overlay architecture for dynamic routing such that only a subset of devices (overlay nodes) need to make dynamic routing decisions. We determine the essential collection of nodes that must bifurcate traffic for achieving the maximum multicommodity network throughput. We apply our optimal node placement algorithm to several graphs and the results show that a small fraction of overlay nodes is sufficient for achieving maximum throughput. Finally, we propose a heuristic policy (OBP), which dynamically controls traffic bifurcations at overlay nodes. In all studied simulation scenarios, OBP not only achieves full throughput, but also reduces delay in comparison to the throughput optimal backpressure routing.

We consider distributed strategies for joint routing, scheduling, and network coding to maximize throughput in wireless networks. Network coding allows for an increase in network throughput under certain routing conditions. We previously developed a centralized control policy to jointly optimize for routing and scheduling combined with a simple network coding strategy using max-weight scheduling (MWS) [9]. In this work we focus on pairwise network coding and develop a distributed carrier sense multiple access (CSMA) policy that supports all arrival rates allowed by the network subject to the pairwise coding constraint. We extend our scheme to optimize for packet overhearing to increase the number of beneficial coding opportunities. Simulation results show that the CSMA strategy yields the same throughput as the optimal centralized policy of [9], but at the cost of increased delay. Moreover, overhearing provides up to an additional 25% increase in throughput on random topologies.

We consider jointly optimal routing, scheduling, and network coding strategies to maximize throughput in wireless networks. While routing and scheduling techniques for wireless networks have been studied for decades, network coding is a relatively new technique that allows for an increase in throughput under certain topological and routing conditions. In this work we introduce k-tuple coding, a generalization of pairwise coding with next-hop decodability, and fully characterize the region of arrival rates for which the network queues can be stabilized under this coding strategy. We propose a dynamic control policy for routing, scheduling, and k-tuple coding, and prove that our policy is throughput optimal subject to the k-tuple coding constraint. We provide analytical bounds on the coding gain of our policy, and present numerical results to support our analytical findings. We show that most of the gains are achieved with pairwise coding, and that the coding gain is greater under 2-hop than 1-hop interference. Simulations show that under 2-hop interference our policy yields median throughput gains of 31% beyond optimal scheduling and routing on random topologies with 16 nodes.

We analyze the queueing delay performance when random linear coding is performed over packets randomly arriving at a source node for multicast transmission over packet erasure channels. We model random coding of packets as a bulk-service queueing system, where packets are served and depart the queue in groups. In this framework, we analyze two different block-based random linear coding schemes. The first scheme involves coding over a fixed blocksize, which leads to simpler analysis but also to a delay penalty for lightly-loaded systems. The second scheme adapts to the traffic load by allowing for a variable blocksize, thereby removing the delay penalty at low loads. We provide results on the maximum stable arrival rate of packets at the source and on the queueing delay as a function of the arrival rate.

We consider wireless multicasting over lossy links and explore the benefit of cooperative strategies in which multicast receivers exchange messages. A key feature of the problem considered here is that the source downlink channel has a higher loss rate than the channels between pairs of receivers; this feature implies that completion time may be reduced by offloading transmissions to receiver-receiver links and taking advantage of their higher reliability. Three strategies are analyzed and compared: a strategy in which all transmissions are carried out by the original source node; a strategy in which the original source transmits until it is able to designate a proxy-source among the receiver nodes to complete the multicast; and a strategy in which the original source transmits the minimal number of packets possible and cooperative transmissions among receivers are used to complete the multicast. These strategies are compared in terms of the number of packet transmissions needed to complete the multicast.

In this work we analyze the average queue backlog for transmission of a single multicast flow consisting of M destination nodes in a wireless network. In the model we consider, the channel between every pair of nodes is an independent identically distributed packet erasure channel. We first develop a lower bound on the average queue backlog achievable by any transmission strategy; for a single-hop multicast transmission, our bound indicates that the queue size must scale as at least Ω(ln(M)). Next, we generalize this result to a multihop network and obtain a lower bound on the queue backlog as it relates to the minimum-cut capacity of the network. We then analyze the queue backlog for a strategy in which random linear coding is performed over groups of packets in the queue at the source node of a single-hop multicast. We develop an upper bound on the average queue backlog for the packet-coding strategy to show that the queue size for this strategy scales as O(ln(M)). Our results demonstrate that in terms of the queue backlog for single-hop multicast, the packet coding strategy is order-optimal with respect to the number of receivers.

This paper presents techniques for achieving high throughput in delay-constrained, multihop wireless communication networks with time-varying link connectivity. We develop a rate-controlled, multipath strategy using network coding, and compare its performance with that of multipath flooding and with the performance of traditional single-path strategies. These performance comparisons include both theoretical benchmarks and simulation results from cooperative relay scenarios, which incorporate different sets of link connectivity statistics that are drawn from field tests of mobile satellite communication terminals. The results indicate that with appropriate rate-control, network coding can provide throughput performance comparable to multipath flooding of the network while utilizing bandwidth nearly as efficiently as single-path routing.

This paper compares scheduling and coding strategies for a multicast version of a classic downlink problem. We consider scheduling strategies where, in each time slot, a scheduler observes the lengths of all queues and the connectivities of all links and can transmit the head-of-the-line packet from a single queue. We juxtapose this to a coding strategy that is simply a form of classical random linear coding. We show that there are configurations for which the stable throughput region of the scheduling strategy is a strict subset of the corresponding throughput region of the coding strategy. This analysis is performed for both time-invariant and time-varying channels. The analysis is also performed both with and without accounting for the impact on throughput of including coding overhead symbols in each encoded packet. Additionally, we compare coding strategies that only code within individual queues against a coding strategy that codes across separate queues. The strategy that codes across queues simply sends packets from all queues to all receivers. As a result, this strategy sends many packets to unnecessary recipients. We show, surprisingly, that there are cases where the strategy that codes across queues can achieve the same throughput region achievable by coding within individual queues.

In this work, we find the capacity of a compound finite-state channel (FSC) with time-invariant deterministic feedback. We consider the use of fixed length block codes over the compound channel. Our achievability result includes a proof of the existence of a universal decoder for the family of FSCs with feedback. As a consequence of our capacity result, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel. Additionally, we show that for a stationary and uniformly ergodic Markovian channel, if the compound channel capacity is zero without feedback then it is zero with feedback. Finally, we use our result on the FSC to show that the feedback capacity of the memoryless compound channel is given by infthetasmaxQXI(X; Y |thetas).

We consider a problem of managing separate multicast sessions from a single transmitter. Each of K sessions has an associated packet stream, and a single transmitter must transmit these packet streams to a group of receivers. The multicast sessions are separate in the sense that each receiver only wants packets from one of the K streams. We will compare the maximum stable arrival rates that can be supported with and without using random linear coding across the K sessions. Intuitively, it seems that coding across sessions is not beneficial. Coding across sessions appears to introduce unnecessary additional delay since each receiver does not receive its next packet until it can decode the head-of-line packets from all K streams. However, we show that in many cases the maximum stable arrival rate that can be supported when coding across sessions is significantly greater than maximum stable arrival rate that can be supported when not coding across sessions. We provide a sufficient condition that indicates when coding across sessions is preferable. This condition is expressed in terms of the number of sessions, the number of receivers per session, and the reliability of the channels connecting the transmitter to the receivers.

This work addresses the feedback capacity of compound channels with memory. We provide an upper bound on the feedback capacity of a compound finite-state channel. As a consequence, we show that for a stationary channel with memory, if the compound channel capacity is zero without feedback then it is zero with feedback. Additionally, we show that feedback does not increase the capacity of the compound Gilbert-Elliot channel.

We assess the practicality of random network coding by illuminating the issue of overhead and considering it in conjunction with increasingly long packets sent over the erasure channel. We show that the transmission of increasingly long packets, consisting of either of an increasing number of symbols per packet or an increasing symbol alphabet size, results in a data rate approaching zero over the erasure channel. This result is due to an erasure probability that increases with packet length. Numerical results for a particular modulation scheme demonstrate a data rate of approximately zero for a large, but finite-length packet. Our results suggest a reduction in the performance gains offered by random network coding.

A wireless network in which packets are broadcast to a group of receivers through use of a random access protocol is considered in this work. The relation to previous work on networks of interacting queues is discussed and subsequently, the stability and throughput regions of the system are analyzed and presented. A simple network of two source nodes and two destination nodes is considered first. The broadcast service process is analyzed assuming a channel that allows for packet capture and multipacket reception. It is proved that the stability and throughput regions coincide in this small network. The same problem for a network with N sources and M destinations is considered next. The channel model is simplified in that packet capture and multipacket reception is no longer permitted. Bounds on the stability region are developed using the concept of stability rank and the throughput region of the system is compared to the bounds. Our results show that as the number of destination nodes increases, the stability and throughput regions diminish. Additionally, a previous conjecture that the stability and throughput regions coincide for a network of arbitrarily many sources is supported for a broadcast scenario by the results presented in this work.

The capacity region of an asynchronous system with two sources and two receivers is analyzed. The capacity region is first derived for a general discrete memoryless channel. The result is then applied to a random access system in which sources may either transmit information-bearing symbols or idle (empty) symbols in each time slot. The capacity region for this random access system is compared to the corresponding queueing stability region and it is demonstrated that the two regions do not coincide. This comparison is the primary contribution of our work; our result is a deviation from all previous results on the relation between information-theoretic capacity and queueing stability for random access systems

We introduce and study the problem of broadcast stability in a network where nodes utilize the ALOHA protocol to gain random access to the channel. We make use of the dominating systems argument used in previous works and also develop a novel method for finding the region of stable arrival rates of packets. The stability region is obtained by analyzing the broadcast service process for a channel with multipacket reception. Our results exhibit the effect of probabilistic reception and multipacket reception on the broadcast stability region. We also show that the broadcast stability region is contained within the stability region for unicast transmission. Our work is applicable to the broadcast transmission that underlies communication in many wireless networks, including multihop networks. In addition, our new method for finding the stability region may be applicable to previously unsolved problems, including the stability region for arbitrarily many sources and destinations