19.9 Survivable Light Trail Design

The major issue in the design of a survivable light trail network is to identify a set of light trails to carry the given traffic and to provide 100% protection against single-link failure. The survivable light trail network design problem is defined as follows. Given a graph G( V, E) , where V = N, and a traffic matrix D _{N N} , identify the minimum number of light trails to carry the given traffic in such a way that for each connection request, there is a primary connection established in one light trail and resources are reserved in another light trail for backup connection. Two light trails for each s-d pair are link-disjoint.

Recall that the maximum hop length of a light trail is denoted by Tl _max. The traffic matrix preprocessing algorithm proposed in Fig. 19.6 still applies here in which a long hop is recursively divided into multiple hops in order to satisfy the light trail hop-length constraint. It is necessary that for each recovering s-d pair there is more than one path available within Tl _max.

The next step is to develop an ILP formulation to optimize the capacity utilization in terms of the number of light trails, with the given network topology and refined traffic matrix obtained from traffic matrix preprocessing. The objective is to find the minimum number of light trails that are required for the system.