Parallel Scheduling Algorithm based on Complex Coloring for Input-Queued Switches
| Autor: | Wang, Lingkang, Ye, Tong, Lee, Tony T., Hu, Weisheng |
|---|---|
| Rok vydání: | 2016 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | This paper explores the application of a new algebraic method of edge coloring, called complex coloring, to the scheduling problems of input queued switches. The proposed distributed parallel scheduling algorithm possesses two important features: optimality and rearrangeability. Optimality ensures that the algorithm always returns a proper coloring with the minimum number of required colors, and rearrangeability allows partially re-coloring the existing connection patterns if the underlying graph only changes slightly. The running time of the proposed scheduling algorithm is on the order of $O(\log^2 N)$ per frame, and the amortized time complexity, the time to compute a matching per timeslot, is only $O(\log N)$. The scheduling algorithm is highly robust in the face of traffic fluctuations. Since the higher the variable density, the higher the efficiency of the variable elimination process, complex coloring provides a natural adaptive solution to non-uniform input traffic patterns. The proposed scheduling algorithm for packet switching can achieve nearly 100% throughput. Comment: 16 pages, 15 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|