islip throuput fairness tradeoffs
Throughput/Fairness Trade offs for the iSLIP Scheduling
Algorithm
Petros Mol
Todor Ristov
Nikolaos Trogkanis
University of California, San
Diego
University of California, San
Diego
University of California, San
Diego
pmol@cs.ucsd.edu
tristov@cs.ucsd.edu
nikos@cs.ucsd.edu
ABSTRACT
High throughput and fairness consist two desirable properties when scheduling traffic in an Input-Queued crossbar switch. Unfortunately, these two goals are conflicting which makes the job of most scheduling algorithms that want to achieve both hard. Here, we investigate the trade offs between throughput and fairness for iSLIP, one of the most well-studied algorithms introduced in [4]. We study iSLIP’s behavior under several traffic patterns both for persistent and for Bernoulli arrivals and compare its throughput to the throughput achieved by a maximum matching algorithm which is less efficient and completely ignores fairness. We conclude that iSLIP’s superiority in fairness comes with only a minor degradation of throughput. Hence iSLIP seems to achieve a great balance between performance, throughput and fairness.
1.
INTRODUCTION
Input-Queued (IQ) switches are massively used in network design. The central problem in designing an input-queued switch is the scheduling algorithm that decides which packets should be transfered from input ports to output ports in a given time slot. Iterative algorithms consist a very important class of IQ switches’ scheduling algorithms because they can achieve very good performance due to pipelining.
The main properties desired by a good scheduling algorithm are high throughput, starvation-freeness, speed and simplicity. In this project we study one of the most celebrated iterative scheduling algorithms, iSLIP, and try to investigate how iSLIP balances these properties. Our goal is to analyze its performance in several different scenarios and get a deeper understanding of its characteristics.
The central
Algorithm
Petros Mol
Todor Ristov
Nikolaos Trogkanis
University of California, San
Diego
University of California, San
Diego
University of California, San
Diego
pmol@cs.ucsd.edu
tristov@cs.ucsd.edu
nikos@cs.ucsd.edu
ABSTRACT
High throughput and fairness consist two desirable properties when scheduling traffic in an Input-Queued crossbar switch. Unfortunately, these two goals are conflicting which makes the job of most scheduling algorithms that want to achieve both hard. Here, we investigate the trade offs between throughput and fairness for iSLIP, one of the most well-studied algorithms introduced in [4]. We study iSLIP’s behavior under several traffic patterns both for persistent and for Bernoulli arrivals and compare its throughput to the throughput achieved by a maximum matching algorithm which is less efficient and completely ignores fairness. We conclude that iSLIP’s superiority in fairness comes with only a minor degradation of throughput. Hence iSLIP seems to achieve a great balance between performance, throughput and fairness.
1.
INTRODUCTION
Input-Queued (IQ) switches are massively used in network design. The central problem in designing an input-queued switch is the scheduling algorithm that decides which packets should be transfered from input ports to output ports in a given time slot. Iterative algorithms consist a very important class of IQ switches’ scheduling algorithms because they can achieve very good performance due to pipelining.
The main properties desired by a good scheduling algorithm are high throughput, starvation-freeness, speed and simplicity. In this project we study one of the most celebrated iterative scheduling algorithms, iSLIP, and try to investigate how iSLIP balances these properties. Our goal is to analyze its performance in several different scenarios and get a deeper understanding of its characteristics.
The central
References: [1] D. Bertsekas and R. Gallager. Data Networks. Prentice Hall, 2nd edition, 1992. International Conference on Communications, 2002. ICC 2002, volume 2, 2002. Networking, 7(2):188–201, 1999. devices. Morgan Kaufmann, 2005.