 |
    |
An Optimization Solution for Packet Scheduling: A Pipeline-Based Genetic Algorithm Accelerator
Shiann-Tsong Sheu, Yue-Ru Chuang, Yu-Hung Chen, and Eugene Lai
Department of Electrical Engineering,
TamkangUniversity,
Tamsui, Taipei,
Taiwan 25137, R.O.C.
stsheu@ee.tku.edu.tw,
g8350021@tkgis.tku.edu.tw
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.
LNCS 2723, p. 681 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003