The Library
Online packet scheduling for CIOQ and buffered crossbar switches
Tools
Tools
Tools
Al-Bawani, Kamal, Englert, Matthias and Westermann, Matthias (2018) Online packet scheduling for CIOQ and buffered crossbar switches. Algorithmica, 80 . pp. 3861-3888. doi:10.1007/s00453-018-0421-x
|
PDF
WRAP-online-packet-scheduling-crossbar-switches-Englert-2018.pdf - Accepted Version - Requires a PDF viewer. Download (679Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-018-0421-x
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×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 slot, 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 Rosén (J. Algorithms 60(1):60–83, 2006) 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: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 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., Packet switching (Data transmission), Computer algorithms., Computer network architectures. | ||||||||
| Journal or Publication Title: | Algorithmica | ||||||||
| Publisher: | Springer Verlag | ||||||||
| ISSN: | 0178-4617 | ||||||||
| Official Date: | December 2018 | ||||||||
| Dates: |
|
||||||||
| Volume: | 80 | ||||||||
| Page Range: | pp. 3861-3888 | ||||||||
| DOI: | 10.1007/s00453-018-0421-x | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
