ContactPerson: dahaixu@cse.buffalo.edu
### Begin Citation ### Do not delete this line ###
%R 2001-13
%U /home/csegrad/dahaixu/public_html/papers/494-1241764279.pdf
%A Qiao, Chunming 
%A  Xu, Dahai
%T Distributed Partial Information Management (DPIM) Schemes for Survivable Networks - Part I
%D July 10, 2001
%I Department of Computer Science and Engineering, SUNY Buffalo
%K distributed routing and signaling, bandwidth guarantee, sharing, allocation and deallocation,protection
%Y Algorithms
%X This paper describes a novel framework, 
called Distributed Partial Information 
Management (or DPIM). It addresses several major challenges 
in achieving efficient shared path protection under 
distributed control 
with only partial information, including 
(1) how much partial information about existing active and backup paths 
(or APs and BPs respectively) is maintained and exchanged; 
(2) how to obtain a good estimate of the bandwidth needed by a candidate BP, 
called BBW, and subsequently select a pair of AP and BP for a 
connection establishment request so as to minimize total bandwidth consumption 
and/or maximize revenues; 
(3) how to distributively allocate minimal BBW (and de-allocate maximal BBW) via distributed signaling; and 
(4) how to update and subsequently exchange the partial information.   
A DPIM-based scheme using Integer Linear Programming 
is described to illustrate our approach. 
In addition, an ultra-fast and efficient heuristic scheme 
is described. With about the same amount of partial information, 
such a heuristic-based DPIM scheme can achieve almost 
as a good performance as the ILP-based DPIM scheme, 
and a much better performance than another ILP-based scheme described in 
[1]. 
The paper also presents an elegant method to support 
dynamic requests for protected, unprotected, and pre-emptable 
connections in the unified DPIM framework.