Method for fast cost-effective internet network topology design

摘要

A method of designing a network for an Internet Service Provider (ISP) is taught. The ISP provides routers that handle predetermined traffic demands and that are connected by links. An ordered sequence of (source-destination) pairs of routers is obtained. A particular (source-destination) pair and a minimum capacity on each potential link for the predicted traffic demands on the selected (source-destination) pair are selected. The differential cost of the link is then found, followed by a determination of the least-cost path for the selected (source-destination) pair. The current capacity and current cost of the network are then updated. The process repeats for all (source-destination) pairs in the ordered sequence. Least-cost paths can be determined using the Bellman-Ford method. The output of the basic method can be further refined by the Link Removal Heuristic (LRH) method, and/or a Flow Removal Heuristic (FRH) method.