Abstract:

In order to optimize network performance and reduce construction cost, the topology design and dimensioning problems in wide-area network planning were investigated based on delay constraint with the use of linear programming (LP) and heuristic greedy-drop algorithm.Firstly, demands’ weights were considered and LP was exploited with given paths to solve the capacity expansion problems of minimum delay and minimum delay with minimum cost.Secondly, greedy-drop algorithm was applied and candidate edges were removed from full mesh topology according to the global normalized delay increments.Thus, new added edges to satisfy the delay constraint were determined.Moreover, the combination of LP and greedy-drop algorithm was proposed to determine new added edges and capacity expansion of the delay-constraint scenario with minimum cost.The results turn out that the proposed algorithms are effective to solve the problems of topology design and capacity planning in wide-area network planning targeting delay optimization.

Key words: network planning, network dimensioning, greedy-drop, added edge, delay optimization