We investigate the performance of First-In, First-Out (FIFO) queues over wireless networks. We characterize the stability region of a general scenario where an arbitrary number of FIFO queues, which are served by a wireless medium, are shared by an arbitrary number of flows. In general, the stability region of this system is non-convex. Thus, we develop a convex inner-bound on the stability region, which is provably tight in certain cases. The convexity of the inner bound allows us to develop a resource allocation scheme; dFC. Based on the structure of dFC, we develop a stochastic flow control and scheduling algorithm; qFC. We show that qFC achieves optimal operating point in the convex inner bound. Simulation results show that our algorithms significantly improve the throughput of wireless networks with FIFO queues, as compared to the well-known queue-based flow control and max-weight scheduling.
In backpressure, each node constructs per-flow queues. There is some work in the literature to stretch this necessity. For example, @cite_12 , @cite_9 propose using real per-link and virtual per-flow queues. Such a method reduces the number of queues required in each node, and reduces the delay, but it still needs to construct per-link queues. Similarly, @cite_22 constructs per-link queues in the link layer, and schedule packets according to FIFO rule from these queues. Such a setup is different than ours as per-link queues do not introduce HOL blocking. The main differences in our work are: (i) we consider FIFO queues shared by multiple flows where HOL blocking occurs as each flow is transmitted over a possibly different wireless link, (ii) we characterize the stability region of a general scenario where an arbitrary number of FIFO queues, which are served by a wireless medium, are shared by an arbitrary number of flows, and (iii) we develop efficient resource allocation schemes to exploit achievable rate in such a setup.
@cite_9 @cite_22 @cite_12
2015207483 1988904411 2051945243
We consider the following queuing system which arises as a model of a wireless link shared by multiple users. There is a finite number N of input flows served by a server. The system operates in discrete time t = 0,1,2,…. Each input flow can be described as an irreducible countable Markov chain; waiting customers of each flow are placed in a queue. The sequence of server states m(t), t = 0,1,2,…, is a Markov chain with finite number of states M. When the server is in state m, it can serve mim customers of flow i (in one time slot).The scheduling discipline is a rule that in each time slot chooses the flow to serve based on the server state and the state of the queues. Our main result is that a simple online scheduling discipline, Modified Largest Weighted Delay First, along with its generalizations, is throughput optimal; namely, it ensures that the queues are stable as long as the vector of average arrival rates is within the system maximum stability region. Middleboxes are widely deployed in today's enterprise networks. They perform a wide range of important network functions, including WAN optimizations, intrusion detection systems, network and application level firewalls, etc. Depending on the processing requirement of traffic, packet processing for different traffic flows may consume vastly different amounts of hardware resources (e.g., CPU and link bandwidth). Multi-resource fair queueing allows each traffic flow to receive a fair share of multiple middlebox resources. Previous schemes for multi-resource fair queueing, however, are expensive to implement at high speeds. Specifically, the time complexity to schedule a packet is O(log n), where n is the number of backlogged flows. In this paper, we design a new multi-resource fair queueing scheme that schedules packets in a way similar to Elastic Round Robin. Our scheme requires only O(1) work to schedule a packet and is simple enough to implement in practice. We show, both analytically and experimentally, that our queueing scheme achieves nearly perfect Dominant Resource Fairness. Scheduling is a critical and challenging resource allocation mechanism for multihop wireless networks. It is well known that scheduling schemes that favor links with larger queue length can achieve high throughput performance. However, these queue-length-based schemes could potentially suffer from large (even infinite) packet delays due to the well-known last packet problem, whereby packets belonging to some flows may be excessively delayed due to lack of subsequent packet arrivals. Delay-based schemes have the potential to resolve this last packet problem by scheduling the link based on the delay the packet has encountered. However, characterizing throughput optimality of these delay-based schemes has largely been an open problem in multihop wireless networks (except in limited cases where the traffic is single-hop). In this paper, we investigate delay-based scheduling schemes for multihop traffic scenarios with fixed routes. We develop a scheduling scheme based on a new delay metric and show that the proposed scheme achieves optimal throughput performance. Furthermore, we conduct simulations to support our analytical results and show that the delay-based scheduler successfully removes excessive packet delays, while it achieves the same throughput region as the queue-length-based scheme. A model for wireless networks with slotted-Aloha-type random access and with multihop flow routes is considered. The goal is to devise distributed algorithms for utility-optimal end-to-end throughput allocation and queueing stability. A class of queue back-pressure random access algorithms (QBRAs), in which actual queue lengths of the flows in each node's close neighborhood are used to determine the nodes' channel access probabilities, is studied. This is in contrast to some previously proposed algorithms, which are based on deterministic optimization formulations and are oblivious to actual queues. QBRA is also substantially different from the well-studied ldquoMaxWeightrdquo type scheduling algorithms, even though both use the concept of back-pressure. For the model with infinite backlog at each flow source, it is shown that QBRA, combined with simple congestion control local to each source, leads to optimal end-to-end throughput allocation within the network saturation throughput region achievable by random access, without end-to-end message passing. This scheme is generalized to the case with minimum flow rate constraints. For the model with stochastic exogenous arrivals, it is shown that QBRA ensures stability of the queues as long as nominal loads of the nodes are within the saturation throughput region. Simulation comparison of QBRA and the queue oblivious random-access algorithms, shows that QBRA reduces end-to-end delays. Abstract— We consider wireless networks with interference constraints. The network consists of a set of links and a set of users who generate packets that traverse these links. Each user is associated with a route consisting of a sequence of links. The links are subject to the usual interference constraints: (i) if link l interferes with link k, then link k also interferes with link l, and (ii) two links that interfere with each other cannot transmit simultaneously. The interference set of a link is defined to be the set of links that interfere with the link, along with the link itself. A greedy scheduler is one which selects an arbitrary set of links to transmit subject only to the interference constraint. We use a traffic regulator at each link along the route of each flow which shapes the traffic of the flow. We prove that the network is queue-length stable under any maximal greedy scheduling policy provided that the total arrival rate in the interference set of each link is less than one. Current data collection protocols for wireless sensor networks are mostly based on quasi-static minimum-cost routing trees. We consider an alternative, highly-agile approach called backpressure routing, in which routing and forwarding decisions are made on a per-packet basis. Although there is a considerable theoretical literature on backpressure routing, it has not been implemented on practical systems to date due to concerns about packet looping, the effect of link losses, large packet delays, and scalability. Addressing these concerns, we present the Backpressure Collection Protocol (BCP) for sensor networks, the first ever implementation of dynamic backpressure routing in wireless networks. In particular, we demonstrate for the first time that replacing the traditional FIFO queue service in backpressure routing with LIFO queues reduces the average end-to-end packet delays for delivered packets drastically (75 under high load, 98 under low load). Further, we improve backpressure scalability by introducing a new concept of floating queues into the backpressure framework. Under static network settings, BCP shows a more than 60 improvement in max-min rate over the state of the art Collection Tree Protocol (CTP). We also empirically demonstrate the superior delivery performance of BCP in highly dynamic network settings, including conditions of extreme external interference and highly mobile sinks. We study a basic problem in Multi-Queue switches. A switch connects m input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacity B. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g., IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [4] for arbitrary B. Recently, a ( 17 9 1.89 )-competitive algorithm was presented for B>1 in [2]. Our main result in this paper shows that for B which is not too small our algorithm can do better than 1.89, and approach a competitive ratio of ( e e-1 1.58 ). We consider a discrete-time stochastic model of an ECN RED gateway where competing TCP sources share the link capacity. As the number of competing flows becomes large, the asymptotic queue behavior (normalized by the number of flows) at the gateway can be described by a simple recursion and the throughput behavior of individual TCP flows becomes asymptotically independent. A Central Limit Theorem complement is also presented, yielding a more accurate characterization of the asymptotic queue size. These results suggest a scalable yet accurate model of this complex large-scale stochastic feedback system, and crisply reveal the sources of queue fluctuations. In most network models for quality of service support, the communication links interconnecting the switches and gateways are assumed to have fixed bandwidth and zero error rate. This assumption of steadiness, especially in a heterogeneous internet-working environment, might be invalid owing to subnetwork multiple-access mechanism, link-level flow error control, and user mobility. Techniques are presented in this paper to characterize and analyze work-conserving communication nodes with varying output rate. In the deterministic approach, the notion of "fluctuation constraint," analogous to the "burstiness constraint" for traffic characterization, is introduced to characterize the node. In the statistical approach, the variable-rate output is modelled as an "exponentially bounded fluctuation" process in a way similar to the "exponentially bounded burstiness" method for traffic modelling. Based on these concepts, deterministic and statistical bounds on queue size and packet delay in isolated variable-rate communication server-nodes are derived, including cases of single-input and multiple-input under first-come-first-serve queueing. Queue size bounds are shown to be useful for buffer requirement and packet loss probability estimation at individual nodes. Our formulations also facilitate the computation of end-to-end performance bounds across a feedforward network of variable-rate server-nodes. Several numerical examples of interest are given in the discussion. A new coding and queue management algorithm is proposed for communication networks that employ linear network coding. The algorithm has the feature that the encoding process is truly online, as opposed to a block-by-block approach. The setup assumes a packet erasure broadcast channel with stochastic arrivals and full feedback, but the proposed scheme is potentially applicable to more general lossy networks with link-by-link feedback. The algorithm guarantees that the physical queue size at the sender tracks the backlog in degrees of freedom (also called the virtual queue size). The new notion of a node ldquoseeingrdquo a packet is introduced. In terms of this idea, our algorithm may be viewed as a natural extension of ARQ schemes to coded networks. Our approach, known as the drop-when-seen algorithm, is compared with a baseline queuing approach called drop-when-decoded. It is shown that the expected queue size for our approach is O[(1) (1-rho)] as opposed to Omega[(1) (1-rho)2] for the baseline approach, where rho is the load factor. It is well known that head-of-line blocking limits the throughput of an input-queued switch with first-in-first-out (FIFO) queues. Under certain conditions, the throughput can be shown to be limited to approximately 58.6 . It is also known that if non-FIFO queueing policies are used, the throughput can be increased. However, it has not been previously shown that if a suitable queueing policy and scheduling algorithm are used, then it is possible to achieve 100 throughput for all independent arrival processes. In this paper we prove this to be the case using a simple linear programming argument and quadratic Lyapunov function. In particular, we assume that each input maintains a separate FIFO queue for each output and that the switch is scheduled using a maximum weight bipartite matching algorithm. We introduce two maximum weight matching algorithms: longest queue first (LQF) and oldest cell first (OCF). Both algorithms achieve 100 throughput for all independent arrival processes. LQF favors queues with larger occupancy, ensuring that larger queues will eventually be served. However, we find that LQF can lead to the permanent starvation of short queues. OCF overcomes this limitation by favoring cells with large waiting times. We consider the question of obtaining tight delay guarantees for throughout-optimal link scheduling in arbitrary topology wireless ad-hoc networks. We consider two classes of scheduling policies: 1) a maximum queue-length weighted independent set scheduling policy, and 2) a randomized independent set scheduling policy where the independent set scheduling probabilities are selected optimally. Both policies stabilize all queues for any set of feasible packet arrival rates, and are therefore throughput-optimal. For these policies and i.i.d. packet arrivals, we show that the average packet delay is bounded by a constant that depends on the chromatic number of the interference graph, and the overall load on the network. We also prove that this upper bound is asymptotically tight in the sense that there exist classes of topologies where the expected delay attained by any scheduling policy is lower bounded by the same constant. Through simulations we examine the scaling of the average packet delay with respect to the overall load on the network, and the chromatic number of the link interference graph. Minimum cost routing is considered on multiclass multihop wireless networks influenced by stochastic arrivals, inter-channel interference, and time-varying topology. Endowing each air link with a cost factor, possibly time-varying and different for different classes, we define the Dirichlet routing cost as the square of the link packet transmissions weighted by the link cost-factors. Our recently-proposed Heat-Diffusion (HD) routing protocol [3] is extended to minimize this cost, while ensuring queue stability for all stabilizable traffic demands, and without requiring any information about network topology or packet arrivals. This is the first time in literature that such a multiclass routing penalty can be minimized at network layer subject to queue stability. Further, when all links are of unit cost factor, our protocol here reduces to the one in our recent paper [4], leading to minimum average network delay among all routing protocols that act based only on current queue congestion and current channel states. Our approach is based on mapping a communication network into an electrical network by showing that the fluid limit of wireless network under our routing protocol follows Ohm's law on a nonlinear resistive network. We present a capacity-achieving coding scheme for unicast or multicast over lossy packet networks. In the scheme, intermediate nodes perform additional coding yet do not decode nor even wait for a block of packets before sending out coded packets. Rather, whenever they have a transmission opportunity, they send out coded packets formed from random linear combinations of previously received packets. All coding and decoding operations have polynomial complexity. We show that the scheme is capacity-achieving as long as packets received on a link arrive according to a process that has an average rate. Thus, packet losses on a link may exhibit correlation in time or with losses on other links. In the special case of Poisson traffic with i.i.d. losses, we give error exponents that quantify the rate of decay of the probability of error with coding delay. Our analysis of the scheme shows that it is not only capacity-achieving, but that the propagation of packets carrying "innovative" information follows the propagation of jobs through a queueing network, and therefore fluid flow models yield good approximations. We consider networks with both lossy point-to-point and broadcast links, allowing us to model both wireline and wireless packet networks. We consider the setting of a network providing differentiated services. As is often the case in differentiated services, we assume that the packets are tagged as either being a high priority packet or a low priority packet. Outgoing links in the network are serviced by a single FIFO queue.Our model gives a benefit of α ≥ 1 to each high priority packet and a benefit of 1 to each low priority packet. A queue policy controls which of the arriving packets are dropped and which enter the queue. Once a packet enters the queue it is eventually sent. The aim of a queue policy is to maximize the sum of the benefits of all the packets it sends.We analyze and compare different queue policies for this problem using the competitive analysis approach, where the benefit of the online policy is compared to the benefit of an optimal offline policy. We derive both upper and lower bounds for the policies we consider. We believe that competitive analysis gives important insight to the performance of these queuing policies. This paper presents an analytic model for evaluating the MAC layer queueing delays at wireless nodes using the distributed coordination function of IEEE 802.11 MAC specifications. Our model is valid for finite loads and can account for arbitrary arrival patterns, packet size distributions and number of nodes. Each node is modeled as a discrete time G G 1 queue and we obtain closed form expressions for the delay and queue length characteristics at each node. We derive the service time distribution for the packets at each node while accounting for a number of factors including the channel access delay due to the shared medium, impact of packet collisions, the resulting backoffs as well as the packet size distribution. Our analytical results are verified through extensive simulations and are more accurate than existing models. This paper addresses the problem of fairness in wireless ad-hoc networks. Usually, the problem of fairness in wireless ad-hoc networks is addressed in a classic approach inherited from wired networks. The common assumption is that nodes flows have pre-assigned fair shares. The task becomes then to modify wired networks' fair queueing algorithms to address wireless network nature. Wired networks have efficient means of allocating fiar shares through admission control and additionally, the fair shares remain constant throughout the session duration due to the static nature of the nodes. In ad-hoc networks, it is meaningless to assume statically pre-assigned fair shares, since on one hand, not only the nodes move, but also the routers are mobile, and on the other hand, contention is location dependent, such that in terms of absolute guarantees, fairness would at most mean "avoiding starvation": thus applying rate proportional fiar queueing algorithms is beyond the original goal of such algorithm, viz. flow isolation protection and bandwidth guarantee. In this work we argue in favor of multi-level scheduling for wireless ad-hoc networks with max-min fair allocation of the fair shares at the lower-most layer (MAC layer). This paper, mainly lays down the theoretical framework by which one can calculate the fair shares that would achieve max-min fairness in an ad-hoc network. We design distributed algorithms that allow each node to determine its max-min per-link fair share in a global ad-hoc network without knowledge of the global topology of the network. The results are then used in conjunction with a novel practical scheduling algorithm for IEEE 802.11 to show how fairness is achieved We consider packet scheduling in a network providing differentiated services, where each packet is assigned a value. We study various queueing models for supporting QoS (Quality of Service). In the nonpreemptive model, packets accepted to the queue will be transmitted eventually and cannot be dropped. The FIFO preemptive model allows packets accepted to the queue to be preempted (dropped) prior to their departure, while ensuring that transmitted packets are sent in the order of arrival. In the bounded delay model, packets must be transmitted before a certain deadline, otherwise it is lost (while transmission ordering is allowed to be arbitrary). In all models the goal of the buffer policy is to maximize the total value of the accepted packets.Let α be the ratio between the maximal and minimal value. For the non-preemptive model we derive a Θ(log &alpha) competitive ratio, both exhibiting a buffer policy and a general lower bound. For the interesting case of two distinct values, we give an 2α--1 α competitive buffer policy, which exactly matches the lower bound. We also analyze a RED-like policy and derive its competitive ratio, which is approximately 2α--0.5 α for two values and Θ(log α) for multiple values. In addition we improve the previous known lower and upper bounds of the Fixed Partition and Flexible Partition policies.For the FIFO preemptive model, we improve the general lower bound and show a tight bound for the special case of queue size 2. We prove that the bounded delay model with uniform delay 2 is equivalent to a modified FIFO preemptive model with queue size 2. We then give improved upper and lower bounds on the 2-uniform bounded delay model. We also give lower bound for the 2-variable bounded delay model, which matches the previously known upper bound. BBR is a recently proposed congestion control. Instead of using packet loss as congestion signal, like many currently used congestion controls, it uses an estimate of the available bottleneck link bandwidth to determine its sending rate. BBR tries to provide high link utilization while avoiding to create queues in bottleneck buffers. The original publication of BBR shows that it can deliver superior performance compared to Cubic TCP in some environments. This paper provides an independent and extensive experimental evaluation of BBR at higher speeds. The experimental setup uses BBR's Linux kernel 4.9 implementation and typical data rates of 10Gbit s and 1 Gbit s at the bottleneck link. The experiments vary the flows' round-trip times, the number of flows, and buffer sizes at the bottleneck. The evaluation considers throughput, queuing delay, packet loss, and fairness. On the one hand, the intended behavior of BBR could be observed with our experiments. On the other hand, some severe inherent issues such as increased queuing delays, unfairness, and massive packet loss were also detected. The paper provides an in-depth discussion of BBR's behavior in different experiment setups. The back-pressure algorithm is a well-known throughput-optimal algorithm. However, its implementation requires that each node has to maintain a separate queue for each commodity in the network, and only one queue is served at a time. This fact may lead to a poor delay performance even when the traffic load is not close to network capacity. Also, since the number of commodities in the network is usually very large, the queueing data structure that has to be maintained at each node is respectively complex. In this paper, we present a solution to address both of these issues in the case of a fixed-routing network scenario where the route of each flow is chosen upon arrival. Our proposed architecture allows each node to maintain only per-neighbor queues and, moreover, improves the delay performance of the back-pressure algorithm.