Segment yönlendirme ile trafik mühendisliği

Trafik mühendisliğinde segment yönlendirme, ağ oluşturma alanında nispeten yeni bir tekniktir. Segment yönlendirme, bir paketin izleyeceği segmentlerin paketin başlığına yazıldığı daha basit bir kaynak yönlendirme şeklidir. Segmentler, SID'ler olarak bilinen Segment Kimlikleri kullanılarak tanımlanır. Düğüm SID'leri ve Bitişiklik SID'leri, farklı segment türlerini tanımlar: Birincisi, en kısa yol segmentlerini tanımlar ve ikincisi, iki düğüm arasındaki en kısa olmayan doğrudan bağlantıyı tanımlar. Giriş yönlendiricileri, Eşit Maliyetli Çoklu Yolları (ECMP'ler) kullanarak paketleri hedeflerine yönlendirir. Son zamanlarda, segment yönlendirme kullanan trafik mühendisliği için çeşitli çözümler önerilmiştir. Bu formülasyonlardaki amaç, ağdaki Maksimum Bağlantı Kullanımını (MLU) en aza indirmektir. Bu Karışık Tamsayılı Doğrusal Programlama (MILP) tabanlı formülasyonlar tüm olası yolları dikkate almaz ve düğüm ve segment sayısı arttıkça hesaplama süreleri makul bir değerin ötesine geçer. Bu eksiklikleri göz önünde bulundurarak, problem için yeni formülasyonlar ve algoritmalar sunuyoruz. Tüm segment çiftlerini formülasyona dahil etmek için yola dayalı bir model $K$-MMILP tanıtıldı. Ayrıca, akış tabanlı bir model olan $K$-MsMILP de önerilmiştir. Bu formülasyonlar, tüm Bitişik SID'leri, Düğüm SID'lerini ve ECMP'leri içerir. Ayrıca, akışın takip ettiği maksimum yol uzunluğunu kısıtlamanın MLU ve hesaplama süresi üzerindeki etkisi analiz edilmiştir. Önerilen akış tabanlı formülasyon, uçtan uca yol başına maksimum 3 segment kullanarak 20 örneğin her biri için düşünülen tüm topolojiler için optimum sonuçlar üretir. Ayrıca tüm topolojiler için hesaplama süresini önemli ölçüde azaltır. Örneğin, $16$ düğümlü Alman Ağı için, hesaplama süresi ortalama olarak $14,9$ kat oranında azaltılır. Ayrıca, $27$-düğümlü Avrupa ağı için, $3$-sMILP 24 saat içinde optimum sonuçlar üretemezken, $3$-MsMILP ortalama $2268$ saniyede sonuç üretti.