Optimal path selection for ethernet over SONET under inaccurate link-state information

Ethernet over SONET (EoS) is a popular approach for interconnecting geographically distant Ethernet segments using a SONET transport infrastructure. It typically uses virtual concatenation (VC) for dynamic bandwidth management. The aggregate SONET bandwidth that supports a given EoS system is obtained by "concatenating" a number of virtual channels (VCs), which together form a virtually concatenated group (VCG). This aggregate bandwidth can be increased on demand by adding one or more VCs to the existing VCG. The new VC (route) must be selected such that its end-to-end delay is within a certain range that reflects the delays of all existing VCs in the VCG and the available memory buffer of the EoS system. Algorithmically, the problem of selecting such a VC becomes that of flnding a path in a graph network that is bounded by an upper and lower bounds (the lower bound being a positive number). This problem, known as the two-sided constrained path (TSCP), was first formulated in [2] assuming exactly known link delays, and a heuristic solution known as the MLW-KSP algorithm was proposed for solving it. In this paper, we first prove that the TSCP problem is NPcomplete. We then propose a new solution for it based on the "backward-forward" search approach. We show that this solution is much more efficient than the previously proposed MLW-KSP algorithm. We then consider the TSCP problem under inaccurate link information, in which the delay and available bandwidth for each link are taken as random variables. The problem is now formulated as that of finding the most probable path that satisfies the upper and lower delay constraints. We consider two cases. In the first case, we assume that the link delays are random but the link bandwidths are exact. We then consider the more general case where both the link delays and bandwidths are random. Heuristic solutions are presented for both cases. Simulations are conducted to evaluate the performance of the proposed algorithms and to demonstrate the advantages of the probabilistic path selection approach over the classic triggerbased approach.