We consider the problem of designing a fair scheduling algorithm for discrete-time constrained queuing networks. Each queue has dedicated exogenous packet arrivals. There are constraints on which queues can be served simultaneously. This model effectively describes important special instances like network switches, interference in wireless networks, bandwidth sharing for congestion control and traffic scheduling in road roundabouts. Fair scheduling is required because it provides isolation to different traffic flows; isolation makes the system more robust and enables providing quality of service. Existing work on fairness for constrained networks concentrates on flow based fairness. As a main result, we describe a notion of packet based fairness by establishing an analogy with the ranked election problem: packets are voters, schedules are candidates, and each packet ranks the schedules based on its priorities. We then obtain a scheduling algorithm that achieves the described notion of fairness by drawing upon the seminal work of Goodman and Markowitz (1952). This yields the familiar Maximum Weight (MW) style algorithm. As another important result, we prove that the algorithm obtained is throughput optimal. There is no reason a priori why this should be true, and the proof requires nontraditional methods.
To address the issue of fairness in a network, Kelly, Maullo and Tan (1998) @cite_3 proposed a flow-level model for the Internet. Under this model, the resource allocation that maximizes the global network utility provides a notion of fair rate allocation. We refer an interested reader to survey-style papers by Low (2003) @cite_16 and Chuang et.al. (2006) @cite_9 and the book by Srikant (2004) @cite_28 for further details. We take a note of desirable throughput property of the dynamic flow-level resource allocation model (see for example, Bonald and Massoulie (2001) @cite_13 , and de Veciana, Konstantopoulos and Lee (2001) @cite_11 ). This approach, though valid for a general network with arbitrary topology, does not take scheduling constraints into account.
@cite_28 @cite_9 @cite_3 @cite_16 @cite_13 @cite_11
2032824989 2161809383 2041718516 2084765981
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 discuss the relevance of fairness as a design objective for congestion control mechanisms in the Internet. Specifically, we consider a backbone network shared by a dynamic number of short-lived flows, and study the impact of bandwidth sharing on network performance. In particular, we prove that for a broad class of fair bandwidth allocations, the total number of flows in progress remains finite if the load of every link is less than one. We also show that provided the bandwidth allocation is "sufficiently" fair, performance is optimal in the sense that the throughput of the flows is mainly determined by their access rate. Neither property is guaranteed with unfair bandwidth allocations, when priority is given to one class of flow with respect to another. This suggests current proposals for a differentiated services Internet may lead to suboptimal utilization of network resources. The fair allocation of resources among different nodes is one of the critical problems in wireless mesh networks. Existing solutions mainly focus on rate-limitation policies or distributed fair MAC schemes at the potential expense of total network utilization. This paper investigates a special starvation problem among TCP flows that are different hops away from the BS, as well as its recently proposed solution, the ‘Minimum Content Window’ policy based on IEEE 802.11e. It is found that the aggregate throughput degrades sharply because the effect of this policy on the TCP congestion mechanism has been overlooked. This paper proposes a priority-based congestion control by using ‘Cross-Layer Explicit Congestion Notification’. Analysis and simulation results demonstrate that our scheme can improve the fairness of TCP flows while the aggregate throughput is at least 20 higher than the ‘Minimum Content Window’ policy. Copyright © 2011 John Wiley & Sons, Ltd. We compare the performance of three usual allocations, namely max-min fairness, proportional fairness and balanced fairness, in a communication network whose resources are shared by a random number of data flows. The model consists of a network of processor-sharing queues. The vector of service rates, which is constrained by some compact, convex capacity set representing the network resources, is a function of the number of customers in each queue. This function determines the way network resources are allocated. We show that this model is representative of a rich class of wired and wireless networks. We give in this general framework the stability condition of max-min fairness, proportional fairness and balanced fairness and compare their performance on a number of toy networks.