Linear Programming and Algorithms for Communication Networks

Chapter 5

Disjoint path routing

This chapter presents several problems on finding disjoint paths for reliable communications. First, the basic problem of finding a set of disjoint routes whose total cost is minimized, which is called a MIN-SUM problem, is considered. Several approaches, which include integer linear programming (ILP), a disjoint shortest pair algorithm, and the Suurballe algorithm, are introduced to solve the problem. Second, the MIN-SUM problem in a network with shared risk link groups (SRLGs) and its solutions are presented. Third, the MIN-SUM problem in a multiple-cost network and its solutions are introduced.

5.1 Basic disjoint path problem

5.1.1 Integer linear programming problem

With optical fiber bandwidth and node capacity ...