Abstract
The dense wavelength division multiplexing (DWDM) technique has been developed to provide a tremendous number of wavelengths/channels in an optical fiber. In the multi-channel networks, it has been a challenge to effectively schedule a given number of wavelengths and variable-length packets into different wavelengths in order to achieve a maximal network throughput. This optimization process has been considered as difficult as the job scheduling in multiprocessor scenario, which is well known as a NP-hard problem. In current research, a heuristic method, genetic algorithms (GAs), is often employed to obtain the near-optimal solution because of its convergent property. Unfortunately, the convergent speed of conventional GAs cannot meet the speed requirement in high-speed networks. In this paper, we propose a novel hyper-generation GAs (HG-GA) concept to approach the fast convergence. By the HG-GA, a pipelined mechanism can be adopted to speed up the chromosome generating process. Due to the fast convergent property of HG-GA, which becomes possible to provide an efficient scheduler for switching variable-length packets in high-speed and multi-channel optical networks.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Charles A. Brackett: Dense Wavelength Division Multiplexing Networks: Principles and Applications. IEEE J. Select. Areas Communication, Vol. 8, No. 6, pp. 948–964, August (1990).
Paul Green: Progress in Optical Networking. IEEE Communications magazine, Vol. 39, No. 1, pp. 54–61, January (2001).
F. Jia, B. Mukherjee, J. Iness: Scheduling Variable-length Messages in A Single-hop Multichannel Local Lightwave Network. IEEE/ACM Trans. Networking, Vol. 3, pp. 477–487, August (1995).
J. H. Lee, C. K. Un: Dynamic Scheduling Protocol for Variable-sized Messages in A WDM-based Local Network. J. Lightwave Technol., pp. 1595–1600, July (1996).
Babak Hamidzadeh, Ma Maode, Mounir Hamdi: Efficient Sequencing Techniques for Variable-Length Messages in WDM Network. J. Lightwave Tech., Vol. 17, pp. 1309–1319, August (1999).
Sengupta S., Ramamurthy R.: From Network Design to Dynamic Provisioning and Restoration in Optical Cross-connect Mesh Networks: an Architectural and Algorithmic Overview. IEEE Network, Vol. 15, Issue 4, pp. 46–54, July–Aug (2001).
Edwin S.H. Hou, Nirwan Ansari, Hong Ren: A Genetic Algorithm for Multiprocessor Scheduling. IEEE Transaction on Parallel and Distributed Systems, Vol. 5, No. 2, February (1994).
Mitsuo Gen, Runwei Cheng: Genetic Algorithms and Engineering Design. Wiley Interscience Publication, (1997).
J. S.R. Jang, C. T. Sun, E. Mizutani: Neuro-Fuzzy Soft Computing. Prentice-Hall International, Inc., Chapter 7.
D. E. Goldberg: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA, (1989).
Shiann-Tsong Sheu, Yue-Ru Chuang, Yu-Jie Cheng, Hsuen-Wen Tseng: A Novel Optical IP Router Architecture for WDM Networks. In Proceedings of IEEE ICOIN-15, pp. 335–340, (2001).
Shiann-Tsong Sheu, Yue-Ru Chuang: Fast Convergent Genetic Algorithm for Scheduling Variable-Length Packets in High-speed Multi-Channel Optical Networks. Submitted to IEEE Transaction on Evolutionary Computation, (2002).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sheu, ST., Chuang, YR., Chen, YH., Lai, E. (2003). An Optimization Solution for Packet Scheduling: A Pipeline-Based Genetic Algorithm Accelerator. In: Cantú-Paz, E., et al. Genetic and Evolutionary Computation — GECCO 2003. GECCO 2003. Lecture Notes in Computer Science, vol 2723. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45105-6_83
Download citation
DOI: https://doi.org/10.1007/3-540-45105-6_83
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40602-0
Online ISBN: 978-3-540-45105-1
eBook Packages: Springer Book Archive