O'Reilly logo

Linear Programming and Algorithms for Communication Networks by Eiji Oki

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required