Designing Internet transport networks with minimun cost.

摘要

Deploying a transport network which supports the large amount of Internet traffic is very costly. First, thousands of miles of fiber have to be laid down to interconnect the cities. Second, expensive switching equipment, both electronic routers and optical switches, have to be installed in each city to send, receive and switch traffic. In this dissertation, we look at how to design such a transport network with minimum cost in order to support the large amount of Internet traffic. We study this problem in both metro networks and backbone networks.; We first consider metro SONET rings. In contrast to prior work, we assume that each wavelength could be set to one of multiple line speeds. We propose Integer Linear Programming (ILP) formulations and several computation techniques to solve the minimization problem exactly. We also propose an efficient heuristic algorithm that can produce a near optimal result in a much shorter amount of time. We demonstrate that, using the tools we developed; employing multiple line speeds can reduce the cost by roughly 20% compared to the case where only a single line speed is used.; We then consider backbone WDM mesh networks. We decompose the problem into two subproblems. First, we consider the fiber topology design problem so as to minimize the switching cost under a fiber cost budget assuming that either only electronic switching or only optical switching is used. Then, we consider the problem of how to lower the switching cost further by employing both electronic and optical switching. By repeatedly solving the two subproblems for different fiber cost budget, we can find the design with the minimal total cost. We show that when decomposing the problem into two subproblems, we are not losing much in terms of optimality. In the process of solving the second subproblem (minimize switching cost), we characterize the tradeoff between electronic and optical switching for many different topologies and show that it follows a power-law.