Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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 > 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:
DateEvent
December 2018Published
5 March 2018Available
15 February 2018Accepted
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us