2011, 1(4): 727-747. doi: 10.3934/naco.2011.1.727

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

1. 

SMACS Research Group, Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent

2. 

SMACS Research Group, Department TELIN (IR07), Ghent University, St.-Pietersnieuwstraat 41, 9000 Gent, Belgium

3. 

Department of Telecommunications and Information Processing, Ghent University, St-Pietersnieuwstraat 41, 9000 Gent

Received  June 2011 Revised  August 2011 Published  November 2011

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.
Citation: Wouter Rogiest, Koen De Turck, Koenraad Laevens, Dieter Fiems, Sabine Wittevrongel, Herwig Bruneel. On the optimality of packet-oriented scheduling in photonic switches with delay lines. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 727-747. doi: 10.3934/naco.2011.1.727
References:
[1]

F. Callegati, Optical buffers for variable length packets,, IEEE Communications Letters, 4 (2004), 292. doi: 10.1109/4234.873490.

[2]

F. Callegati, Approximate modeling of optical buffers for variable length packets,, Photonic Network Communications, 3 (2001), 383. doi: 10.1023/A:1011964113336.

[3]

F. Callegati, W. Cerroni and G. Corazza, Optimization of wavelength allocation in WDM optical buffers,, Optical Networks Magazine, 2 (2001), 66.

[4]

F. Callegati, D. Careglio, W. Cerroni, G. Muretto, C. Raffaelli, J. Sol\'e-Pareta and P. Zaffoni, Keeping the packet sequence in optical packet-switched networks,, Optical Switching and Networking, 2 (2005), 137. doi: 10.1016/j.osn.2005.09.001.

[5]

F. Callegati, W. Cerroni and G. S. Pavani, Key parameters for contention resolution in multi-fiber optical burst/packet switching nodes,, Proceedings of the Fourth IEEE International Conference on Broadband Communications, (2007), 217.

[6]

F. Callegati, G. Muretto, C. Raffaelli, P. Zaffoni and W. Cerroni, A framework for performance evaluation of OPS congestion resolution,, Proceedings of the Ninth Conference on Optical Network Design and Modelling, (2005), 242.

[7]

Y. Chen, C. Qiao and X. Yu, Optical burst switching: A new area in optical networking research,, IEEE Network, 18 (2004), 16. doi: 10.1109/MNET.2004.1301018.

[8]

C. M. Gauger, Optimized combination of converter pools and FDL buffers for contention resolution in Optical Burst Switching,, Photonic Network Communications, 8 (2004), 139. doi: 10.1023/B:PNET.0000033974.73365.4f.

[9]

Z. Haas, The staggering switch: an electronically controlled optical packet switch,, IEEE/OSA Journal of Lightwave Technology, 11 (1993), 925. doi: 10.1109/50.233257.

[10]

K. Laevens and H. Bruneel, Analysis of a single-wavelength optical buffer,, Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, (2003), 1.

[11]

J. Lambert, B. Van Houdt and C. Blondia, Single-wavelength optical buffers: Non-equidistant structures and preventive drop mechanisms,, Proceedings of the 2005 Networking and Electronic Commerce Research Conference, (2005), 545.

[12]

G. Muretto and C. Raffaelli, Combining contention resolution schemes in WDM optical packet switches with multi-fiber interfaces,, OSA Journal of Optical Networking, 6 (2007), 74. doi: 10.1364/JON.6.000074.

[13]

F. Masetti, M. Sotom, D. De Bouard, D. Chiaroni, P. Parmentier, F. Callegati, G. Corazza, C. Rafaelli, S. L. Danielsen and K. E. Stubkjaer, Design and performance of a broadcast and select photonic packet switching architecture,, Proceedings of the 1996 European Conference of Optical Communication, (1996), 15.

[14]

T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of optical burst switched networks with limited-range wavelength conversion, retransmission and burst segmentation,, Journal of the Operations Research Society of Japan (JORSJ), 52 (2009), 58.

[15]

J. F. Pérez and B. Van Houdt, Wavelength allocation in an optical switch with a fiber delay line buffer and limited-range wavelength conversion,, Telecommunication Systems, 41 (2009), 37. doi: 10.1007/s11235-009-9149-x.

[16]

C. Qiao and M. Yoo, Optical burst switching-a new paradigm for an optical internet,, Journal on High-Speed Networks, 8 (1999), 69.

[17]

R. Van Caenegem, D. Colle, M. Pickavet, P. Demeester, K. Christodoulopoulos, K. Vlachos et al., The design of an all-optical packet switching network,, IEEE Communications Magazine, 45(11) (2007), 52. doi: 10.1109/MCOM.2007.4378321.

[18]

W. Rogiest, K. De Turck, D. Fiems, K. Laevens, S. Wittevrongel and H. Bruneel, Optimized channel and delay selection for contention resolution in optical networks,, Proceedings of the IEEE International Conference on Communications (ICC2011, (2011), 1.

[19]

W. Rogiest, K. De Turck, K. Laevens, S. Wittevrongel and H. Bruneel, Contention resolution for optical switching: tuning the channel and delay selection algorithm,, Proceedings of the Ninth IARIA International Conference on Networks (ICN, (2010), 1.

[20]

W. Rogiest, J. Lambert, D. Fiems, B. Van Houdt, H. Bruneel and C. Blondia, A unified model for synchronous and asynchronous {FDL buffers allowing closed-form solution},, Performance Evaluation, 66 (2009), 343. doi: 10.1016/j.peva.2009.01.002.

[21]

W. Rogiest, K. Laevens, D. Fiems and H. Bruneel, A performance model for an asynchronous optical buffer,, Performance Evaluation, 62 (2005), 313. doi: 10.1016/j.peva.2005.07.010.

[22]

W. Rogiest, K. Laevens, D. Fiems and H. Bruneel, Modeling the performance of FDL buffers with wavelength conversion,, IEEE Transactions on Communications, 57 (2009), 3703. doi: 10.1109/TCOMM.2009.12.080040.

[23]

H. C. Tijms, "Stochastic Modelling and Analysis: A Computational Approach,", J. Wiley and Sons, (1986).

[24]

L. Tancevski, S. Tamil and F. Callegati, Non-degenerate buffers: A paradigm for building large optical memories,, IEEE Photonic Technology Letters, 11 (1999), 1072. doi: 10.1109/68.775350.

[25]

J. Turner, Terabit burst switching,, Journal on High-Speed Networks, 8 (1999), 3.

[26]

L. Tancevski, S. Yegnanarayanan, G. Castanon, L. Tamil, F. Masetti and T. McDermott, Optical routing of asynchronous, variable length packets,, IEEE Journal on Selected Areas in Communications, 18 (2000), 2084. doi: 10.1109/49.887927.

[27]

Y. Xiong, M. Vandenhoute and H. Cankaya, Design and analysis of optical burst-switched networks,, Proceedings of SPIE (Boston, 3843 (1999), 112.

[28]

Y. Xiong, M. Vandenhoute and H. Cankaya, Control architecture in optical burst-switched WDM networks,, IEEE Journal on Selected Areas in Communications, 18 (2000), 1838. doi: 10.1109/49.887906.

[29]

S. Yao, B. Mukherjee and S. Dixit., Advances in photonic packet switching: An overview,, IEEE Communications Magazine, 38 (2000), 84. doi: 10.1109/35.819900.

[30]

S. Yao, B. Mukherjee, S. J. B. Yoo and S. Dixit., A unified study of contention-resolution schemes in optical packet-switched networks,, Journal of Lightwave Technology, 21 (2003), 672. doi: 10.1109/JLT.2003.809573.

show all references

References:
[1]

F. Callegati, Optical buffers for variable length packets,, IEEE Communications Letters, 4 (2004), 292. doi: 10.1109/4234.873490.

[2]

F. Callegati, Approximate modeling of optical buffers for variable length packets,, Photonic Network Communications, 3 (2001), 383. doi: 10.1023/A:1011964113336.

[3]

F. Callegati, W. Cerroni and G. Corazza, Optimization of wavelength allocation in WDM optical buffers,, Optical Networks Magazine, 2 (2001), 66.

[4]

F. Callegati, D. Careglio, W. Cerroni, G. Muretto, C. Raffaelli, J. Sol\'e-Pareta and P. Zaffoni, Keeping the packet sequence in optical packet-switched networks,, Optical Switching and Networking, 2 (2005), 137. doi: 10.1016/j.osn.2005.09.001.

[5]

F. Callegati, W. Cerroni and G. S. Pavani, Key parameters for contention resolution in multi-fiber optical burst/packet switching nodes,, Proceedings of the Fourth IEEE International Conference on Broadband Communications, (2007), 217.

[6]

F. Callegati, G. Muretto, C. Raffaelli, P. Zaffoni and W. Cerroni, A framework for performance evaluation of OPS congestion resolution,, Proceedings of the Ninth Conference on Optical Network Design and Modelling, (2005), 242.

[7]

Y. Chen, C. Qiao and X. Yu, Optical burst switching: A new area in optical networking research,, IEEE Network, 18 (2004), 16. doi: 10.1109/MNET.2004.1301018.

[8]

C. M. Gauger, Optimized combination of converter pools and FDL buffers for contention resolution in Optical Burst Switching,, Photonic Network Communications, 8 (2004), 139. doi: 10.1023/B:PNET.0000033974.73365.4f.

[9]

Z. Haas, The staggering switch: an electronically controlled optical packet switch,, IEEE/OSA Journal of Lightwave Technology, 11 (1993), 925. doi: 10.1109/50.233257.

[10]

K. Laevens and H. Bruneel, Analysis of a single-wavelength optical buffer,, Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, (2003), 1.

[11]

J. Lambert, B. Van Houdt and C. Blondia, Single-wavelength optical buffers: Non-equidistant structures and preventive drop mechanisms,, Proceedings of the 2005 Networking and Electronic Commerce Research Conference, (2005), 545.

[12]

G. Muretto and C. Raffaelli, Combining contention resolution schemes in WDM optical packet switches with multi-fiber interfaces,, OSA Journal of Optical Networking, 6 (2007), 74. doi: 10.1364/JON.6.000074.

[13]

F. Masetti, M. Sotom, D. De Bouard, D. Chiaroni, P. Parmentier, F. Callegati, G. Corazza, C. Rafaelli, S. L. Danielsen and K. E. Stubkjaer, Design and performance of a broadcast and select photonic packet switching architecture,, Proceedings of the 1996 European Conference of Optical Communication, (1996), 15.

[14]

T. Phung-Duc, H. Masuyama, S. Kasahara and Y. Takahashi, Performance analysis of optical burst switched networks with limited-range wavelength conversion, retransmission and burst segmentation,, Journal of the Operations Research Society of Japan (JORSJ), 52 (2009), 58.

[15]

J. F. Pérez and B. Van Houdt, Wavelength allocation in an optical switch with a fiber delay line buffer and limited-range wavelength conversion,, Telecommunication Systems, 41 (2009), 37. doi: 10.1007/s11235-009-9149-x.

[16]

C. Qiao and M. Yoo, Optical burst switching-a new paradigm for an optical internet,, Journal on High-Speed Networks, 8 (1999), 69.

[17]

R. Van Caenegem, D. Colle, M. Pickavet, P. Demeester, K. Christodoulopoulos, K. Vlachos et al., The design of an all-optical packet switching network,, IEEE Communications Magazine, 45(11) (2007), 52. doi: 10.1109/MCOM.2007.4378321.

[18]

W. Rogiest, K. De Turck, D. Fiems, K. Laevens, S. Wittevrongel and H. Bruneel, Optimized channel and delay selection for contention resolution in optical networks,, Proceedings of the IEEE International Conference on Communications (ICC2011, (2011), 1.

[19]

W. Rogiest, K. De Turck, K. Laevens, S. Wittevrongel and H. Bruneel, Contention resolution for optical switching: tuning the channel and delay selection algorithm,, Proceedings of the Ninth IARIA International Conference on Networks (ICN, (2010), 1.

[20]

W. Rogiest, J. Lambert, D. Fiems, B. Van Houdt, H. Bruneel and C. Blondia, A unified model for synchronous and asynchronous {FDL buffers allowing closed-form solution},, Performance Evaluation, 66 (2009), 343. doi: 10.1016/j.peva.2009.01.002.

[21]

W. Rogiest, K. Laevens, D. Fiems and H. Bruneel, A performance model for an asynchronous optical buffer,, Performance Evaluation, 62 (2005), 313. doi: 10.1016/j.peva.2005.07.010.

[22]

W. Rogiest, K. Laevens, D. Fiems and H. Bruneel, Modeling the performance of FDL buffers with wavelength conversion,, IEEE Transactions on Communications, 57 (2009), 3703. doi: 10.1109/TCOMM.2009.12.080040.

[23]

H. C. Tijms, "Stochastic Modelling and Analysis: A Computational Approach,", J. Wiley and Sons, (1986).

[24]

L. Tancevski, S. Tamil and F. Callegati, Non-degenerate buffers: A paradigm for building large optical memories,, IEEE Photonic Technology Letters, 11 (1999), 1072. doi: 10.1109/68.775350.

[25]

J. Turner, Terabit burst switching,, Journal on High-Speed Networks, 8 (1999), 3.

[26]

L. Tancevski, S. Yegnanarayanan, G. Castanon, L. Tamil, F. Masetti and T. McDermott, Optical routing of asynchronous, variable length packets,, IEEE Journal on Selected Areas in Communications, 18 (2000), 2084. doi: 10.1109/49.887927.

[27]

Y. Xiong, M. Vandenhoute and H. Cankaya, Design and analysis of optical burst-switched networks,, Proceedings of SPIE (Boston, 3843 (1999), 112.

[28]

Y. Xiong, M. Vandenhoute and H. Cankaya, Control architecture in optical burst-switched WDM networks,, IEEE Journal on Selected Areas in Communications, 18 (2000), 1838. doi: 10.1109/49.887906.

[29]

S. Yao, B. Mukherjee and S. Dixit., Advances in photonic packet switching: An overview,, IEEE Communications Magazine, 38 (2000), 84. doi: 10.1109/35.819900.

[30]

S. Yao, B. Mukherjee, S. J. B. Yoo and S. Dixit., A unified study of contention-resolution schemes in optical packet-switched networks,, Journal of Lightwave Technology, 21 (2003), 672. doi: 10.1109/JLT.2003.809573.

[1]

Mathias Staudigl. A limit theorem for Markov decision processes. Journal of Dynamics & Games, 2014, 1 (4) : 639-659. doi: 10.3934/jdg.2014.1.639

[2]

A. Mittal, N. Hemachandra. Learning algorithms for finite horizon constrained Markov decision processes. Journal of Industrial & Management Optimization, 2007, 3 (3) : 429-444. doi: 10.3934/jimo.2007.3.429

[3]

Zhanqiang Huo, Wuyi Yue, Naishuo Tian, Shunfu Jin. Performance evaluation for the sleep mode in the IEEE 802.16e based on a queueing model with close-down time and multiple vacations. Journal of Industrial & Management Optimization, 2009, 5 (3) : 511-524. doi: 10.3934/jimo.2009.5.511

[4]

Kazuhiko Kuraya, Hiroyuki Masuyama, Shoji Kasahara. Load distribution performance of super-node based peer-to-peer communication networks: A nonstationary Markov chain approach. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 593-610. doi: 10.3934/naco.2011.1.593

[5]

Bart Feyaerts, Stijn De Vuyst, Herwig Bruneel, Sabine Wittevrongel. Performance analysis of buffers with train arrivals and correlated output interruptions. Journal of Industrial & Management Optimization, 2015, 11 (3) : 829-848. doi: 10.3934/jimo.2015.11.829

[6]

Wael Bahsoun, Paweł Góra. SRB measures for certain Markov processes. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 17-37. doi: 10.3934/dcds.2011.30.17

[7]

Hamed Fazlollahtabar, Mohammad Saidi-Mehrabad. Optimizing multi-objective decision making having qualitative evaluation. Journal of Industrial & Management Optimization, 2015, 11 (3) : 747-762. doi: 10.3934/jimo.2015.11.747

[8]

Zhanyou Ma, Wuyi Yue, Xiaoli Su. Performance analysis of a Geom/Geom/1 queueing system with variable input probability. Journal of Industrial & Management Optimization, 2011, 7 (3) : 641-653. doi: 10.3934/jimo.2011.7.641

[9]

Keiji Tatsumi, Masashi Akao, Ryo Kawachi, Tetsuzo Tanino. Performance evaluation of multiobjective multiclass support vector machines maximizing geometric margins. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 151-169. doi: 10.3934/naco.2011.1.151

[10]

Tuan Phung-Duc, Wouter Rogiest, Sabine Wittevrongel. Single server retrial queues with speed scaling: analysis and performance evaluation. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1927-1943. doi: 10.3934/jimo.2017025

[11]

Shunfu Jin, Wuyi Yue, Zhanqiang Huo. Performance evaluation for connection oriented service in the next generation Internet. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 749-761. doi: 10.3934/naco.2011.1.749

[12]

Shunfu Jin, Wuyi Yue, Chao Meng, Zsolt Saffer. A novel active DRX mechanism in LTE technology and its performance evaluation. Journal of Industrial & Management Optimization, 2015, 11 (3) : 849-866. doi: 10.3934/jimo.2015.11.849

[13]

Tom Goldstein, Xavier Bresson, Stan Osher. Global minimization of Markov random fields with applications to optical flow. Inverse Problems & Imaging, 2012, 6 (4) : 623-644. doi: 10.3934/ipi.2012.6.623

[14]

Xian Chen, Zhi-Ming Ma. A transformation of Markov jump processes and applications in genetic study. Discrete & Continuous Dynamical Systems - A, 2014, 34 (12) : 5061-5084. doi: 10.3934/dcds.2014.34.5061

[15]

A. M. Vershik. Polymorphisms, Markov processes, quasi-similarity. Discrete & Continuous Dynamical Systems - A, 2005, 13 (5) : 1305-1324. doi: 10.3934/dcds.2005.13.1305

[16]

H.Thomas Banks, Shuhua Hu. Nonlinear stochastic Markov processes and modeling uncertainty in populations. Mathematical Biosciences & Engineering, 2012, 9 (1) : 1-25. doi: 10.3934/mbe.2012.9.1

[17]

Wouter Rogiest, Dieter Fiems, Koenraad Laevens, Herwig Bruneel. Exact performance analysis of a single-wavelength optical buffer with correlated inter-arrival times. Journal of Industrial & Management Optimization, 2010, 6 (3) : 569-585. doi: 10.3934/jimo.2010.6.569

[18]

Erik Kropat, Silja Meyer-Nieberg, Gerhard-Wilhelm Weber. Singularly perturbed diffusion-advection-reaction processes on extremely large three-dimensional curvilinear networks with a periodic microstructure -- efficient solution strategies based on homogenization theory. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 183-219. doi: 10.3934/naco.2016008

[19]

Shunfu Jin, Wuyi Yue, Xuena Yan. Performance evaluation of a power saving mechanism in IEEE 802.16 wireless MANs with bi-directional traffic. Journal of Industrial & Management Optimization, 2011, 7 (3) : 717-733. doi: 10.3934/jimo.2011.7.717

[20]

Shunfu Jin, Wuyi Yue. Performance analysis and evaluation for power saving class type III in IEEE 802.16e network. Journal of Industrial & Management Optimization, 2010, 6 (3) : 691-708. doi: 10.3934/jimo.2010.6.691

[Back to Top]