Multicast traffic in input-queued switches: optimal scheduling and maximum throughput

The paper studies input-queued packet switches loaded with both unicast and multicast traffic. The packet switch architecture is assumed to comprise a switching fabric with multicast (and broadcast) capabilities, operating in a synchronous slotted fashion. Fixed-size data units, called cells, are tr...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2003-06, Vol.11 (3), p.465-477
Main Authors: Marsan, M.A., Bianco, A., Giaccone, P., Leonardi, E., Neri, F.
Format: Article
Language:English
Subjects:
Algorithms
Architecture
Bandwidth
Broadcasting
Fabrics
Multicast
Optimal scheduling
Optimization
Packet switching
Performance loss
Queues
Scheduling
Studies
Switches
Throughput
Traffic control
Traffic engineering
Traffic flow
Unicast
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:The paper studies input-queued packet switches loaded with both unicast and multicast traffic. The packet switch architecture is assumed to comprise a switching fabric with multicast (and broadcast) capabilities, operating in a synchronous slotted fashion. Fixed-size data units, called cells, are transferred from each switch input to any set of outputs in one time slot, according to the decisions of the switch scheduler, that identifies at each time slot a set of nonconflicting cells, i.e., cells neither coming from the same input, nor directed to the same output. First, multicast traffic admissibility conditions are discussed, and a simple counterexample is presented, showing intrinsic performance losses of input-queued with respect to output-queued switch architectures. Second, the optimal scheduling discipline to transfer multicast packets from inputs to outputs is defined. This discipline is rather complex, requires a queuing architecture that probably is not implementable, and does not guarantee in-sequence delivery of data. However, from the definition of the optimal multicast scheduling discipline, the formal characterization of the sustainable multicast traffic region naturally follows. Then, several theorems showing intrinsic performance losses of input-queued with respect to output-queued switch architectures are proved. In particular, we prove that, when using per multicast flow FIFO queueing architectures, the internal speedup that guarantees 100% throughput under admissible traffic grows with the number of switch ports.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2003.813048