Dıjkstra ve Bellman-Ford En Kısa Yol Algoritmalarının Karşılaştırılması

Year 2003, Volume: 7 Issue: 3, 55 - 62, 01.09.2003

Özmen Emre Demirkol Aşkın Demirkol

Abstract

 Bu çalışmada bilgisayar ağlarında kullanılan en temel iki algoritmanın, kullanım yöntemleri ve farkları araştırılmıştır. Bu iki algoritmanın, kullamldığı yerler ve çalışma prensipleri incelenmiştir. Matematiksel çözümler üzerinde örnek uygulamalar ve çözümleri anlatılmıştır. Çalışmamın temel amacı bilgisayar ağları üzerinde uzak noktalar arasındaki iletişimlerde en kısa yolun hesaplanması ve bu hesapların güvenilirliğini ölçmektir. Bu çerçevede tespit edilmiştir ki, Bellman~Ford algoritmasın, özellikle geniş ağlardaki performansının büyük ölçüde tahmine dayalı olması nedeniyle, Dij kstra algoritması daha iyi sonuç vermektedir.

Keywords

En Kısa Yolun Bulunması, Dijkstra Algoritması, Bellman-Ford Algoritması, RIP, OSPF

References

• [l]. G. Apostolopoulos, D. Williaıns, S. Kamat, , R. Guerin, A. Orda, and T. Przygienda. QOS Routing Mechanisms and OSPF Extensions. RFC 2676 - Experimental, August 1999
• [2]. C. Diot, B. N. Levine, B. Lyles, H. Kassem, and D. Balensiefen. Deployment issues for the IP multicast service and architecture. IEEE Network magazine special issue on Multicasting, 14(1):78--88, January/February 2000
• [3]. N. M. Malouch, Z. Liu, D. Rubenstein, and S. Sahu. A Graph Theoretic Approach to Bounding Delay in Proxy-Assi.sted, End-System Multicast. In 12th Intemational Workshop on N etwork aiıd Operating System Support for Digital Audio and Video (NOSSDAV'02), May 2002. 143
• [4]. G. Apostolopoulos, R. Guerin, and S. Kamat, "lmplementation and Performance Measurements of QoS Routing Extensions to OSP F, 11 in Proc. of IEEE Infocom, March 1999
• [5]. Y. Breitbart, M. Garofalakis, A. Kumar and R. Rastogi, " Optimal Conjiguration of OSPF Aggregates" , In Proc. ofIEEE INFOCOM2002
• [6]. Moy, J.; "The OSPF Specification," Draft RFC, Oct. 89
• [7]. Dirceu Cavendish and Mario Gerla. lnternet QoS Routing using the Bellman-Ford Algorithm. In IFIP Conference on High Performance Networking, 1998
• [8]. Xin Yuan, "On the extended bellman-ford algorithm to solve twoconstrained quality of service routing problems," in International Conference on Computer Communications and Networks(ICCN'99), Oct. 1999
• [9]. Q. Ma, P. Steenkiste, "Routing Traffic with QualityofService Guarantees in Integrated Services Networks", In 8th IEEE/ACM Intemational Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDA V'98), England, July 1998
• [10]. Chowdhury A., Luse P., Frieder O., Wan P., "Network Survivability Simulation of the Commercially Deployed Dynamic Routing System Protocol", IEEE Workshop on Fault-Tolerant Parallel and Distributed Systems, May 2000