research-article

Belief-Propagation-Assisted Scheduling in Input-Queued Switches

Authors:

Shadi Atalla,

Davide Cuda,

Paolo Giaccone,

Marco PrettiAuthors Info & Claims

IEEE Transactions on Computers, Volume 62, Issue 10

Pages 2101 - 2107

https://doi.org/10.1109/TC.2012.198

Published: 01 October 2013 Publication History

Abstract

We consider the problem of scheduling the transmission of packets in an input-queued switch. In order to achieve maximum throughput, scheduling algorithms usually employ the queue length as a parameter for determining the priority to serve a given queue. In this work, we propose a novel scheme to optimize the performance of a preexisting scheduler. Our main idea is to assist the scheduling decision, considering "messagesâ rather than queue lengths. Such messages are obtained by running an iterative parallel algorithm, inspired by a rigorous belief-propagation approach. We demonstrate that belief-propagation-assisted scheduling is able to boost the performance of a given scheduler, reaching almost optimal throughput, even under critical traffic scenarios.

Cited By

View all

Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingACM SIGMETRICS Performance Evaluation Review10.1145/3143314.307850945:1(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3143314.3078509
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844401:1(1-33)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084440
Gong LTune PLiu LYang SXu JHajek BOh SChaintreau AGolubchik LZhang Z(2017)Queue-Proportional SamplingProceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems10.1145/3078505.3078509(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3078505.3078509
Show More Cited By

Belief-Propagation-Assisted Scheduling in Input-Queued Switches
1. General and reference
  1. Cross-computing tools and techniques
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Packet-mode policies for input-queued switches
SPAA '04: Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures

This paper considers the problem of packet-mode scheduling of input queued switches. Packets have variable lengths, and are divided into cells of unit length. Each packet arrives to the switch with a given deadline by which it must traverse the switch. ...
A logarithmic scheduling algorithm for high speed input-queued switches

Throughput of input queued switches using FIFOs is limited due to the Head of Line blocking (HoL) problem. Using VOQs at inputs and a proper scheduling algorithm, near 100% throughput can be achieved. Scaling in terms of number of ports and line rates ...
Belief-Propagation Assisted Scheduling in Input-Queued Switches
HOTI '10: Proceedings of the 2010 18th IEEE Symposium on High Performance Interconnects

We consider the problem of scheduling packets transmission across the switching fabric in an input-queued switch. In order to achieve maximum throughput, scheduling algorithms usually employ the queue length as a parameter for determining the priority ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Computers

IEEE Transactions on Computers Volume 62, Issue 10

October 2013

209 pages

ISSN:0018-9340

Issue’s Table of Contents

Publisher

IEEE Computer Society

United States

Publication History

Published: 01 October 2013

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingACM SIGMETRICS Performance Evaluation Review10.1145/3143314.307850945:1(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3143314.3078509
Gong LTune PLiu LYang SXu J(2017)Queue-Proportional SamplingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/30844401:1(1-33)Online publication date: 13-Jun-2017
https://dl.acm.org/doi/10.1145/3084440
Gong LTune PLiu LYang SXu JHajek BOh SChaintreau AGolubchik LZhang Z(2017)Queue-Proportional SamplingProceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems10.1145/3078505.3078509(4-4)Online publication date: 5-Jun-2017
https://dl.acm.org/doi/10.1145/3078505.3078509
Syrivelis DGiaccone PKoutsopoulos IPretti MTassiulas LBarros FPerumalla KEwald R(2014)On emulating hardware/software co-designed control algorithms for packet switchesProceedings of the 7th International ICST Conference on Simulation Tools and Techniques10.4108/icst.simutools.2014.254797(132-141)Online publication date: 17-Mar-2014
https://dl.acm.org/doi/10.4108/icst.simutools.2014.254797

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

Packet-mode policies for input-queued switches

A logarithmic scheduling algorithm for high speed input-queued switches