Groupe d’études et de recherche en analyse des décisions

G-2004-87

A Heuristic for the Design Optimization of a Next Generation Internet Network

et

This paper proposes an efficient heuristic to solve the topological design of a next generation optical network that provides fully meshed connectivity between electronic edge nodes. Such an architecture, nicknamed "PetaWeb", is simple to manage and offers a total capacity of several petabits per second. From the topology standpoint, the PetaWeb presents a very unusual structure as the backbone nodes are totally disconnected. The network design problem leads to a very hard combinatorial problem that is very difficult to solve for large-sized instances. The heuristic we have developed is based on repeated matchings. Computational results will be presented and discussed.

, 31 pages