Abstract: We address the design of rearrangeable multihop lightwave networks having regular connectivity topology (such as Perfect Shuffle (PS), de Bruijn (dB) graph, GEneralized shuffle-exchange Multihop NETwork (GEMNET) and Manhattan Street NETwork (MSN)). A new formulation of the combined station assignment/flow routing problem with the congestion minimization objective is proposed. The formulation is applicable to any regular topology. We then develop a heuristic solution strategy based on tabu search. In terms of achieving small congestion (as obtained heuristically), the results suggest that with increased problem sizes, regular topologies become more attractive. Moreover, such design will implicitly offer benefits associated with management and operations of regular topologies.
Jadranka Skorin-Kapov is an Associate Professor in the Harriman School for Management and Policy, State University of New York at Stony Brook. She has received her B.Sc. and M.Sc. in Applied Mathematics from the Faculty of Natural and Mathematical Sciences, the University of Zagreb, Croatia, and her Ph.D. in Management Science from the University of British Columbia, Canada. Her research interests include combinatorial optimization and heuristic search. Her publication outlets include Mathematical Programming, Operations Research Letters, ORSA Journal on Computing, Computers and Operational Research, Discrete Applied Mathematics, Journal of Heuristics, Annals of Operations Research and European Journal of Operational Research.
Jean-Francois P. Labourdette was born in Blois, France, in 1963. He received the Diplome d'Ingenieur from Ecole Nationale Superieure des Telecommunications, Brest, France, in 1986, and the M.Sc. and Ph.D. degrees in electrical engineering from Columbia University, New York, in 1988 and 1991, respectively. From 1987 to 1991, he was a Graduate Research Assistant at the NSF Center for Telecommunications Research, Columbia University, workin on reconfigurable lightwave networks. He spent the summer of 1990 at Motorola Codex, Mansfield, MA, investigating the design of fast packet networks for integrated traffic. He joined AT&T Laboratories, Holmdel, NJ, in 1991. From 1991 to 1996, he conducted core network planning activities, working on circuit-switched network routing, dynamically reconfigurable T1/T3 network architectures and ATM networking. He was promoted to Principal Technical Staff Member in 1996. He is currently with the Frame Relay department, working on global Frame Relay services. His research interests include lightwave network architectures, network performances, traffic optimization and reconfiguration management of circuit-switched, packet, and optical networks. Dr. Labourdette was a recipient of a Lavoisier Scholarship from the French government in 1986-1987, and has been a Motorola Scholar in 1989-1990 and 1990-1991. He received the Eliahu I. Jury award for excellence in Systems, Communications or Signal Processing at Columbia University in 1992. He has served as a member of the Technical Program Committee for the IEEE INFOCOM conference since 1994 and for the IEEE ICC conference in 1994.