`a`
Numerical Algebra, Control and Optimization (NACO)
 

On the optimality of packet-oriented scheduling in photonic switches with delay lines

Pages: 727 - 747, Volume 1, Issue 4, December 2011

doi:10.3934/naco.2011.1.727       Abstract        References        Full Text (429.4K)       Related Articles

Wouter Rogiest - SMACS Research Group, Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium (email)
Koen De Turck - SMACS Research Group, Department TELIN (IR07), Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium (email)
Koenraad Laevens - SMACS Research Group, Department TELIN (IR07), Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium (email)
Dieter Fiems - SMACS Research Group, Department TELIN (IR07), Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium (email)
Sabine Wittevrongel - SMACS Research Group, Department TELIN (IR07), Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium (email)
Herwig Bruneel - Department of Telecommunications and Information Processing, Ghent University, St-Pietersnieuwstraat 41, 9000 Gent, Belgium (email)

Abstract: Addressing the bandwidth inefficiency problem of current IP over DWDM backbone switching, Optical Packet/Burst Switching (OPS/OBS) provide viable solutions, capitalizing on statistical multiplexing gain, through packet-oriented scheduling. To resolve packet/burst contention, the involved photonic switches contain wavelength converters and fiber delay lines, controlled through a channel and delay selection (CDS) algorithm. Recently proposed CDS algorithms all rely on heuristics, of which the optimality is unexamined to date.
   This paper presents an in-depth analysis of the optimality of CDS algorithms. Methodologically, we rely on Markov chain analysis for performance evaluation, combined with a discrete Markov Decision Process formulation of the optimization problem, optimized for fast calculation, allowing to determine the exact optimum of a specific given setting of the switch, through numerical algebra solution techniques. Results point out that, for the basic switch setting assumed, of all known CDS algorithms, an algorithm called MING (MINimal Gap) is close to optimal, but never strictly optimal. Various graphs support this, showing that an algorithm optimal for any traffic load cannot (in general) be devised. Results for several other switch settings further confirm this, showing how known CDS algorithms might be modified, to attain improved control robustness.

Keywords:  Performance evaluation, Markov decision processes, optical networks, queueing theory, FDL buffers.
Mathematics Subject Classification:  Primary: 68M20, 90C40; Secondary: 60K25.

Received: June 2011;      Revised: August 2011;      Published: November 2011.

 References