Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Lagrangean relaxation

Sortuj według:

Ogranicz wyniki do:

A Lagrangean Relaxation Algorithm for Flow Optimization in Survivable MPLS Networks

Walkowiak K.

Theoretical and Applied Informatics

2010

Vol. 22, No. 1

19-47

The problem that this paper investigates, namely, the working route assignment (WRA) problem, is one that arises naturally from problems of survivable network design that have recently received significant attention in data networking community. We consider an existing MPLS backbone transport network, which is in an operational phase and augmenting its resources is not possible. To address the issue of network survivability we apply restoration, i.e. after a network failure broken connections are dynamically restored. The main goal of our work is twofold. First, we want to develop an effective objective function for optimization of working routes in order to scale network flows and prepare the network for future failures and restoration. Second, we plan to find an efficient method to solve the WRA problem with this new objective function. Therefore, a function called RCL (Residual Capacity and Lost Flow in Link) facilitating the function LFL (Lost Flow in Link) developed previously by the author is formulated. Next, we present an approximation approach, called Lagrangean relaxation with heuristics (LRH) aimed to solve WRA with RCL as objective function. We further draw comparisons between LRH and an existing heuristic based on Flow Deviation algorithm. We also examine the performance of RCL against other functions in the context of network survivability. The results of simulation tests demonstrate that the new algorithm provides sub-optimal results, which are significantly better than other heuristic and the new function RCL can be effectively applied for assignment of working routes in survivable MPLS networks.