Path Computation Algorithms for Dynamic Service Provisioning in SDH Networks

Synchronous digital hierarchy (SDH) is a time division multiplexing technology widely used in transport networks to provide bandwidth services. Dynamic service provisioning refers to the arrival of service requests one-by-one randomly with no prior information on future requests. This requires the use of on-line algorithms which automatically compute the path to be taken to satisfy the given service request. This problem involves a tradeoff between minimizing the number of requests that are rejected and minimizing the total bandwidth that is utilized. Many earlier works have addressed path computation algorithms, but they treat each link as having some integer units of bandwidth. They do not take into account the multiplexing structure defined by SDH which imposes restrictions on the allocation of bandwidth and the fact that higher order trails (logical connections) have to be established to support any bandwidth requirement. In this work, these factors are considered in the path computation algorithms. The network is treated as a graph containing physical links and logical trails and weights are assigned to them before computing a path with the least cost. Weights are assigned such that the trails are given higher preference to physical links so that existing trails are used wherever possible. This avoids unnecessary creation of new trails. The performance is evaluated for different values of weights. An improvement in the form of dynamically adjusting the weights of links and trails is done and its performance is shown to be better than having constant weights.