An ultra-fast shared path protection scheme-distributed partial information management, part II

For pt.I see Chunming Qiao and Dahai Xu, INFOCOM'02, p.302-11, (2002). This paper describes a novel, ultra-fast heuristic algorithm to address an NP-hard optimization problem. One of its significances is that, for the first time, it is shown that a heuristic algorithm can also have better overall performance than its time-consuming, integer linear programming (ILP) based counterparts in the online case, which is non-intuitive. The proposed heuristic algorithm is useful for developing effective shared path (mesh) protection schemes that establish survivable connections in modern networks. The advantage of our heuristic algorithm over existing algorithms for finding a pair of link (or node) disjoint paths, active path (AP) and backup path (BP), comes from the following salient feature. It uses a so-called potential backup cost (PBC) function when selecting an AP in the first phase, in order to take into consideration the backup bandwidth needed by the corresponding BP yet to be chosen in the second phase. The PBC function is derived mathematically based on a rigorous statistical analysis of experimental data. While the use of PBC only requires partial aggregate information on existing connections and distributed control, it can also be applied even more effectively when complete information is available.