Traffic engineering with segment routing
Segment yönlendirme ile trafik mühendisliği
- Tez No: 757250
- Danışmanlar: PROF. DR. EZHAN KARAŞAN
- Tez Türü: Yüksek Lisans
- Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2022
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 94
Özet
Segment routing in traffic engineering is a relatively new technique in the field of networking. Segment routing is a simpler form of source routing where the segments that a packet will follow are written in the header of the packet. Segments are identified using Segment IDs known as SIDs. Node SIDs and Adjacency SIDs identify different types of segments: The first one identifies the shortest-path segments and the latter identifies the non-shortest direct links between two nodes. The ingress routers direct packets towards their destinations using Equal Cost Multiple Paths (ECMPs). Recently, several solutions have been proposed for traffic engineering using segment routing. The objective in these formulations is to minimize the Maximum Link Utilization (MLU) in the network. These Mixed Integer Linear Programming (MILP) based formulations do not consider all possible paths and the Running times increase beyond a reasonable value as the number of nodes and segments increase. Considering these short-comings, we introduce new formulations and algorithms for the problem. To incorporate all segment pairs into the formulation, a path-based model $K$-MMILP is introduced. Moreover, a flow-based model, $K$-MsMILP is proposed. These formulations incorporate all Adjacency SIDs, Node SIDs, and ECMPs. Furthermore, the effect of restricting the maximum path length followed by the flow on MLU and Running time is analyzed. The proposed flow-based formulation produces optimum results for all topologies considered for each of the 20 instances using a maximum of 3 segments per end-to-end path. It also significantly reduces the Running time for all topologies. For instance, for the $16$-node German Network, the Running time is reduced by a factor of $14.9$ times on the average. Moreover, for the $27$-node European network, the older formulation could not produce optimum results within 24 hours while $3$-MsMILP produced results in $2268$ seconds on average.
Özet (Çeviri)
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.
Benzer Tezler
- Performance comparison and traffic analysis in optical burst-switched networks
Optik çoğuşma anahtarlamalı ağlarda başarım karşılaştırması ve trafik analizi
BURAK KANTARCI
Yüksek Lisans
İngilizce
2005
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ.DR. SEMA OKTUĞ
- Asenkron transfer modu ve çerçeve aktarma
Asynchronous transfer mode and frame relay
HALİT DÖNMEZ
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNSEL DURUSOY
- ATM'de lan hizmetleri
ATM-lan services
İRFAN UĞUR
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. GÜNSEL DURUSOY
- VoIP over wireless networks
Kablosuz ağlarda internet protokolü üzerinden ses iletimi
GAMZE TEKİN
Yüksek Lisans
İngilizce
2013
Bilim ve TeknolojiDokuz Eylül ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ZAFER DİCLE
- Yüzey kurma probleminin transputer tabanlı sistemlerde paralel çözümü
Başlık çevirisi yok
ZİYA MERT GÜRAY
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. COŞKUN SÖNMEZ