ContactPerson: dahaixu@cse.buffalo.edu ### Begin Citation ### Do not delete this line ### %R 2001-14 %U /home/csegrad/dahaixu/public_html/papers/804-3845774282.pdf %A Xu, Dahai %A Qiao, Chunming %T Distributed Partial Information Management (DPIM) Schemes for Survivable Networks - Part II %D July 10, 2001 %I Department of Computer Science and Engineering, SUNY Buffalo %K bandwidth sharing, distributed routing, on-line heuristic, potential cost %Y Algorithms %X A major challenge in shared path protection is to select a jointly optimized pair of active and backup paths. While Integer Linear Programming (ILP) based approaches are notoriously time consuming, existing heuristics such as active path first (APF) can only achieve sub-optimal results. In this paper, we propose a novel heuristic called APF with potential backup cost or APF-PBC under the distributed partial information management framework described in [1] for ultra-fast processing of on-line requests. We show that APF-PBC can outperform existing schemes based on Integer Linear Programming (ILP) with exactly the same input (either partial or complete information) and constraint. We also show how an intuitive function to compute the potential backup cost is derived mathematically based on the statistical analysis of experimental data.