The Library
Online packet scheduling for CIOQ and buffered crossbar switches
Tools
Al-Bawan, Kamal, Englert, Matthias and Westermann, Matthias (2016) Online packet scheduling for CIOQ and buffered crossbar switches. In: 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), California, USA, 11-13 Jul 2016. Published in: SPAA '16 Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures pp. 241-250. ISBN 9781450342100. doi:10.1145/2935764.2935792
|
PDF
WRAP-online-packet-buffered-crossbar-Englert-2016.pdf - Accepted Version - Requires a PDF viewer. Download (620Kb) | Preview |
Official URL: http://dx.doi.org/10.1145/2935764.2935792
Abstract
We consider the problem of online packet scheduling in Combined Input and Output Queued (CIOQ) and buffered crossbar switches. In the widely used CIOQ switches, packet buffers (queues) are placed at both input and output ports. An N x N CIOQ switch has N input ports and N output ports, where each input port is equipped with N queues, each of which corresponds to an output port, and each output port is equipped with only one queue. In each time step, arbitrarily many packets may arrive at each input port, and only one packet can be transmitted from each output port. Packets are transferred from the queues of input ports to the queues of output ports through the internal fabric. Buffered crossbar switches follow a similar design, but are equipped with additional buffers in their internal fabric. In either model, our goal is to maximize the number or, in case the packets have weights, the total weight of transmitted packets.
Our main objective is to devise online algorithms that are both competitive and efficient. We improve the previously known results for both switch models, both for unweighted and weighted packets.
For unweighted packets, Kesselman and Rosen (J. Algorithms '06) give an online algorithm that is 3-competitive for CIOQ switches. We give a faster, more practical algorithm achieving the same competitive ratio. In the buffered crossbar model we also show 3-competitiveness, improving the previously known ratio of 4.
For weighted packets, we give 5.83- and 14.83-competitive algorithms with an elegant analysis for CIOQ and buffered crossbar switches, respectively. This improves upon the previously known ratios of 6 and 16.24.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Online algorithms, Queuing theory | ||||||
Journal or Publication Title: | SPAA '16 Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures | ||||||
Publisher: | ACM | ||||||
ISBN: | 9781450342100 | ||||||
Official Date: | 11 July 2016 | ||||||
Dates: |
|
||||||
Page Range: | pp. 241-250 | ||||||
DOI: | 10.1145/2935764.2935792 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 26 April 2017 | ||||||
Date of first compliant Open Access: | 26 April 2017 | ||||||
Funder: | European Research Council (ERC) | ||||||
Grant number: | Grant Agreement No. 307696 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) | ||||||
Type of Event: | Other | ||||||
Location of Event: | California, USA | ||||||
Date(s) of Event: | 11-13 Jul 2016 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year