On the stability of local scheduling policies in networks of packet switches with input queues

A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on max...

Full description

Saved in:
Bibliographic Details
Published in:IEEE journal on selected areas in communications 2003-05, Vol.21 (4), p.642-655
Main Authors: Marsan, M.G.A., Giaccone, P., Leonardi, E., Neri, F.
Format: Article
Language:English
Subjects:
Computational complexity
Fabrics
Intelligent networks
Law
Networks
Optimization
Packet switching
Policies
Queues
Queuing theory
Scheduling
Scheduling algorithm
Stability
Studies
Switches
Switching theory
Telecommunication traffic
Throughput
Traffic control
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A significant research effort has been devoted to the design of simple and efficient scheduling policies for input queued (IQ) and combined input-output queued (CIOQ) packet switches. As a result, a number of switch control algorithms have been proposed. Among these, scheduling policies based on maximum weight matching (MWM) were identified as optimal, in the sense that they were proved to achieve 100% throughput under any admissible arrival process satisfying the strong law of large number. On the contrary, it has been shown that the usual MWM policies fail to guarantee 100% throughput in networks of interconnected IQ/CIOQ switches. Hence, new policies suited for networks of interconnected switches were proposed and proved to achieve 100% throughput. All of these new policies require coordination and cooperation among different switches. We identify scheduling policies that require no coordination among switches (and are, thus, said to be local), and that guarantee 100% throughput in a network of IQ/CIOQ switches. The only assumptions on the input traffic pattern are that it is stationary, satisfies the strong law of large numbers and does not oversubscribe any link in the network.
ISSN:0733-8716
1558-0008
DOI:10.1109/JSAC.2003.810522