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.