Title :
Efficient, Fully Local Algorithms for CIOQ Switches
Author :
Firoozshahian, Amin ; Manshadi, Vahideh ; Goel, Ashish ; Prabhakar, Balaji
Author_Institution :
Stanford Univ., Stanford
Abstract :
A number of algorithms have been proposed in the literature for scheduling CIOQ switches. The algorithms which have been proven to provide strict performance guarantees on delay (via the emulation of an output-queued switch) have been too complicated to implement because they require the exchange of a large amount of information between inputs and outputs. With implementation as our primary focus, we consider scheduling algorithms that are "fully local." This means inputs and outputs must be able to make decisions regarding matchings using only local information (except requests, grants and accepts). This constraint, which is essentially necessary for high-speed implementations, appears too restrictive for designing algorithms which enable the emulation of an output-queued switch. Rather surprisingly, we find a very simple and fully local algorithm FLGS (for fully local Gale-Shapley) which, at a speedup of 2, emulates an output-queued switch implementing a number of different output link scheduling algorithms such as weighted round robin and strict priority. We explore the performance of the algorithm at speedups between 1 and 2 using simulations and find that it partitions the bandwidth nearly as well as an output-queued switch at speedups 1.2 or higher.
Keywords :
queueing theory; scheduling; telecommunication switching; CIOQ switch; fully local Gale-Shapley algorithm; output link scheduling algorithm; output-queued switch; weighted round robin; Algorithm design and analysis; Bandwidth; Communication switching; Delay; Emulation; Fabrics; Round robin; Scheduling algorithm; Switches; Throughput;
Conference_Titel :
INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE
Conference_Location :
Anchorage, AK
Print_ISBN :
1-4244-1047-9
DOI :
10.1109/INFCOM.2007.307