Parallel algorithms for high performance switching in communication networks

The explosive growth of Internet is driving increased demand for faster transmission rate and faster switching technologies. On one hand, switching algorithms, including routing for establishing connections between inputs and outputs and scheduling for solving packet contentions, play a fundamental role on the performance of switching networks. On the other hand, low cost, high speed, and large capacity switching architectures are very attractive for high-performance switches and routers.;The main contributions of this dissertation can be categorized into three aspects:;Routing. Designing fast parallel routing algorithms for electronic or optical multi-stage interconnection networks using time, space, and wavelength approaches. (1) Time dilation. By modeling the permutation decomposition problem as the problem of edge colorings of bipartite graphs, we simplify the existing proof for the decomposability of a permutation and reduce the decomposition time to logarithmic. Using equitable coloring techniques, we further improve the routing time complexity for optical Benes networks. (2) Space dilation. We study the connection capacity of a class of multistage nonblocking switching networks constructed from Banyan networks by horizontal concatenation of extra stages and/or vertical stacking of multiple copies, and develop sublinear-time routing algorithms by modeling the routing problems for these networks as weak and strong edge colorings of bipartite graphs. (3) Wavelength dilation. We model the wavelength routing problem as the vertex coloring problem, show the maximum number of wavelengths needed, and develop polylogarithmic-time routing algorithms for WRSS Banyan networks and WRSR Benes networks.;Scheduling. Developing efficient parallel stable matching and acyclic stable matching algorithms for switch scheduling. (1) Stable matching. We propose a new approach, parallel iterative improvement, to solving the stable matching problem using randomization and greedy selection. Simulation shows that our algorithm has good average performance and converges in small number of iterations with high probability. (2) Acyclic stable matching. We model the acyclic stable matching problem as the dominating set problem for a rooted dependency graph. The scheduling algorithms based on our acyclic stable matching have low time complexity and are feasible for high-speed implementation.;Architecture. Rearrangeable nonblocking Benes group connectors and Clos group connectors for serving as the major switching matrix in the design of ingress edge routers of a burst-switched DWDM have been proposed. Based on our routing algorithms, the hardware of Benes group connectors can be reduced further.