Wyniki wyszukiwania - BazTech

1

Branch-and-cut algorithm for optimization of non-bifurcated multicommodity flows in survivable networks

Walkowiak K.

Systems Science

|

2006

|

Vol. 32, no 3

27-35

EN

This paper addresses the problem of non-bifurcated multicommodity flow optimization in survivable networks. As the objective we apply the Lost Flow in Link (LFL) function, which is an upper bound of the flow that can be lost due to a failure of a single link. Since the problem under consideration is NP-complete we propose an exact algorithm to find optimal results. To facilitate the high computation complexity caused by the NP-completeness, we propose three cut inequalities: mixed integer rounding, cover inequality and upper bound on the objective function. Cuts are combined with the branch-and-bound algorithm to construct the branch-an-cut algorithm. We evaluate the proposed cuts by making numerical experiments using five network topologies with various demand patterns. Results of simulation prove the robustness of our approach - combined application of all three cuts reduces the number of nodes and decision time by 80% compared to the branch-and-bound algorithm.

2

The Branch and Bound Algorithm for joint optimization of primary and Backup routes in Survivable Networks

Walkowiak K.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2003

|

T. 15, z. 4

273-296

EN

Survivability of computer networks is an important subject. Organizational and individual users of computer network expect reliable services with guarantees of data delivery. In high-speed network technologies like Asynchronous Transfer Mode (ATM) and Multiprotocol Label Switching (MPLS) a large amount of data can be lost due to a network failure and cause significant economics loses. In this work we focus on problems of network survivability. Several network restoration methods are presented and discussed. A new optimization problem of Joint Primary and Backup Routes Assignment is formulated. As the rerouting strategy the local-destination rerouting is applied. The function of lost flow due to a failure of any single link is used as an objective function. The problem of finding the optimal assignment of connections in NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover two heuristic algorithms are proposed. Numerical results are included.

PL

Przeżywalność sieci komputerowych jest ważnym zagadnieniem. Użytkownicy indywidualni i instytucjonalni oczekują niezawodnych usług gwarantujących dostarczenie przesyłanych danych. W szybkich sieciach komputerowych takich jak ATM ( Asynchronous Transfer Mode) oraz MPLS (Multiprotocol Label Switching) wiele ważnych i cennych informacji może być utraconych wskutek awarii. W tej pracy koncentrujemy się na zagadnieniach przeżywalności sieci komputerowych. Przedstawiono i porównano kilka metod zapewniania przeżywalności w sieciach. Nowy problem optymalizacyjny równoczesnego wyznaczania tras podstawowych i zapasowych został sformułowany. Jako metodę restoracji sieci po awarii wybrano restorację lokalno-globalną. Funkcja utraconego przepływu po awarii pojedynczego łącza została użyta jako funkcja kryterialna. Rozważany problem jest NP.-zupełny. Dlatego zaproponowano algorytm dokładny oparty na metodzie podziału i oszacowań. Dodatkowo przedstawiono dwa algorytmy przybliżone. Dołączono wyniki eksperymentów obliczeniowych.

3

The branch and bound algorithm for a backup virtual path assignment in survivable atm networks

Walkowiak K.

International Journal of Applied Mathematics and Computer Science

|

2002

|

Vol. 12, no 2

257-267

EN

Issues of network survivability are important, since users of computer networks should be provided with some guarantees of data delivery. A large amount of data may be lost in high-speed Asynchronous Transfer Mode (ATM) due to a network failure and cause significant economic loses. This paper addresses problems of network survivability. The characteristics of virtual paths and their influence on network restoration are examined. A new problem of Backup Virtual Path Routing is presented for the local-destination rerouting strategy. The function of the flow lost due to a failure of a single link is chosen as the performance index. The problem of finding the optimal virtual path assignment is NP-complete. Therefore we develop an exact algorithm based on the branch and bound approach. Moreover, two heuristic algorithms are proposed. Numerical results are presented.