1
|
Abstract
Mobile ad hoc networks (MANETs) use algorithms that schedule transmissions in a fair and efficient manner. A multihop scheduler schedules transmissions so that the channel utilization is maximized while guaranteeing the quality of service (QoS) for all nodes. QoS-based scheduling in MANETs must be obtained under time-critical conditions as these networks have several features that produce unique queuing dynamics. Schedulers in MANETs take into account various QoS parameters such as end-to-end packet delay, packet delivery ratio, flow priority, etc. Also, scheduling in MANETs takes many forms such as distributed priority, fair, opportunistic, etc. This article provides a survey of scheduling techniques for MANETs and discusses the advantages and disadvantages of each category.
Collapse
|
2
|
Zhang J, Qi H, Guo D, Li K, Li W, Jin Y. ATFQ: A Fair and Efficient Packet Scheduling Method in Multi-Resource Environments. IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2015. [DOI: 10.1109/tnsm.2015.2477517] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/07/2022]
|
3
|
Ghodsi A, Sekar V, Zaharia M, Stoica I. Multi-resource fair queueing for packet processing. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW 2012. [DOI: 10.1145/2377677.2377679] [Citation(s) in RCA: 17] [Impact Index Per Article: 1.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 10/27/2022]
Abstract
Middleboxes are ubiquitous in today's networks and perform a variety of important functions, including IDS, VPN, firewalling, and WAN optimization. These functions differ vastly in their requirements for hardware resources (
e.g.
, CPU cycles and memory bandwidth). Thus, depending on the functions they go through, different flows can consume different amounts of a middlebox's resources. While there is much literature on weighted fair sharing of link bandwidth to isolate flows, it is unclear how to schedule
multiple
resources in a middlebox to achieve similar guarantees. In this paper, we analyze several natural packet scheduling algorithms for multiple resources and show that they have undesirable properties. We propose a new algorithm, Dominant Resource Fair Queuing (DRFQ), that retains the attractive properties that fair sharing provides for one resource. In doing so, we generalize the concept of virtual time in classical fair queuing to multi-resource settings. The resulting algorithm is also applicable in other contexts where several resources need to be multiplexed in the time domain.
Collapse
Affiliation(s)
- Ali Ghodsi
- University of California, Berkeley, Berkeley, CA, USA
| | | | - Matei Zaharia
- University of California, Berkeley, Berkeley, CA, USA
| | - Ion Stoica
- University of California, Berkeley, Berkeley, CA, USA
| |
Collapse
|
4
|
Abstract
Leave-in-Time is a new rate-based service discipline for packet-switching nodes in a connection-oriented data network. Leave-in-Time provides sessions with upper bounds on end-to-end delay, delay jitter, buffer space requirements, and an upper bound on the probability distribution of end-to-end delays. A Leave-in-Time session's guarantees are completely determined by the dynamic traffic behavior of that session, without influence from other sessions. This results in the desirable property that these guarantees are expressed as functions derivable simply from a single fixed-rate server (with rate equal to the session's reserved rate) serving only that session. Leave-in-Time has a non-work-conserving mode of operation for sessions desiring low end-to-end delay jitter. Finally, Leave-in-Time supports the notion of
delay shifting
, whereby the delay bounds of some sessions may be decreased at the expense of increasing those of other sessions. We present a set of admission control algorithms which support the ability to do delay shifting in a systematic way.
Collapse
Affiliation(s)
- Norival R. Figueira
- Computer Systems Laboratory, Department of Computer Science and Engineering, University of California, San Diego, San Diego, CA
| | - Joseph Pasquale
- Computer Systems Laboratory, Department of Computer Science and Engineering, University of California, San Diego, San Diego, CA
| |
Collapse
|
5
|
Berstein GM. Reserved bandwidth and reservationless traffic in rate allocating servers. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW 1993. [DOI: 10.1145/174194.174197] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 10/26/2022]
Abstract
Bandwidth efficiency in communication networks can require supporting traffic with greatly differing quality of service requirements, particularly in terms of delay. The facilities needed to permit users to take advantage of excess bandwidth include (i) a method of conveying network state information to the source, and (ii) a method for guaranteeing quality of service requirements. Reservation oriented rate allocating servers (RASs) provide QOS guarantees while reservationless RASs provide fairness. This paper gives a technique for modifying a reservation oriented RAS to accommodate reservationless traffic and allow users with bandwidth reservations to take advantage of excess network bandwidth. In addition, this paper shows how to use the packet pair bandwidth probing technique with these new RASs to provide effective and efficient congestion control.
Collapse
|
6
|
Wilder R, Ramakrishnan KK, Mankin A. Dynamics of congestion control and avoidance of two-way traffic in an OSI testbed. ACM SIGCOMM COMPUTER COMMUNICATION REVIEW 1991. [DOI: 10.1145/122419.122422] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 10/26/2022]
Abstract
An extensive set of measurements were made in an OSI testbed to study the behavior of congestion control and avoidance. Testbed systems used the Connectionless Network Protocol (CLNP) and Transport Protocol Class 4 (TP4), which had been modified to perform the CE-bit [10] congestion avoidance and the "CUTE" [6] congestion recovery algorithms.We found that two-way traffic has dynamics which can significantly decrease fairness among competing connections using congestion avoidance. We present experiments that demonstrate this problem and our analysis of how two-way traffic results in reduced fairness. This analysis led us to develop an effective modification to the congestion avoidance algorithms to maintain fairness with two-way traffic.Our analysis of experimental results also points to undesirable interactions between two-way traffic dynamics and a sending strategy that times data transmissions, by the receipt of acknowledgements. These interactions reinforce burstiness of transmissions. therefore increasing buffering requirements and delay in routers. They may also decrease throughput.
Collapse
|