Geçtiğimiz yıl, ağlarda en kısa yolları bulmaya yönelik yeni bir yöntem hakkında birçok kişi bana aynı makaleyi iletti. Bu araştırma, çoğu ağ ders kitabında öğretilen klasik Dijkstra yaklaşımını geliştirdiğini iddia ediyor. Başlangıçta biraz şüpheci yaklaştım; tıpkı Riemann Hipotezi'nin kanıtlandığını okusam duyacağım gibi. Dijkstra, bilgisayar bilimlerinde bir efsanedir ve 1959'da yayınladığı algoritması, paket anahtarlamadan birkaç yıl öncesine dayanır. Baskın link-state yönlendirme protokollerinden biri olan OSPF'nin (diğeri IS-IS'tir) spesifikasyonu, uygulayıcılara Dijkstra algoritmasını kullanmaları konusunda alışılmadık derecede ayrıntılı rehberlik sağlar ve çoğu uygulama on yıllardır bunu yapmıştır. Yıllar içinde uygulamayı hızlandırmak için birkaç küçük iyileştirme yapılsa da temellerde gerçek bir değişiklik olmamıştır.
Yeni algoritma, Dijkstra'ya yapılan küçük bir değişiklik değil, önemli ölçüde farklı bir yaklaşımdır. Temel iddiası, Dijkstra'nın bir sıralama işlemi gerektirmesi ve dolayısıyla en iyi sıralama algoritması kadar iyi performans gösterebilmesi durumunda, bu yeni yaklaşımın "sıralama bariyerini aştığı"dır. Yani, sıralama ihtiyacını ortadan kaldırıyor ve Dijkstra'dan daha iyi performans sınırları sunabiliyor. Makale, yeni algoritmayı tanımlayan çalışmanın üst düzey bir konferansta (ACM Symposium on the Theory of Computing) hakem değerlendirmesinden geçtiğini ve teorinin işlediğinden şüphe duymadığını belirtiyor. Ancak yazarın asıl sorusu, bu teorik gelişmenin gerçek dünyada ne kadar önemli olduğu.
Yazar, algoritmik performansdaki teorik bir gelişmenin etkilerini değerlendirirken iki ana konuyu akla getiriyor. Birincisi, gerçek bir yönlendirme sisteminde ele almamız gereken gerçek ölçeklendirme sınırları nelerdir? Örneğin, Dijkstra algoritmasının çalışma süresi n düğümlü (yönlendiriciler) ve m kenarlı (bağlantılar) bir ağ için (n log n + m) mertebesindedir. Yeni yaklaşım ise (m log^(2/3) n) mertebesini iddia ediyor ki bu, yeterince büyük n için açıkça daha az olacaktır. Ancak, herhangi bir şeyin ölçeklendirme özelliklerini değerlendirmenin zorluğu, fark yaratması için n'nin ne kadar büyümesi gerektiğini merak etmektir. İki yaklaşım arasında farklı sabit faktörler olabilir; küçük n değerlerinde, "daha az ölçeklenebilir" bir yaklaşım aslında daha iyi performans gösterebilir.
Bilgisayar bilimlerinin temel taşlarından biri olan Dijkstra algoritmasının performansını teorik olarak aşan yeni bir yaklaşımın, gerçek dünya ağ sistemlerindeki pratik etkileri ve ölçeklenebilirlik sınırları üzerine önemli bir tartışma başlatıyor.