Modeling and fair slot assignment in elastic optical networks under dynamic traffic
Değişken trafikli esnek optik ağlarda modelleme ve adil slot atama
- Tez No: 581073
- Danışmanlar: DOÇ. DR. AYŞEGÜL YAYIMLI
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 89
Özet
Elastik optik ağlarda, optik spektrum çok sayıda dar bantlara bölünür ve WDM optik ağlar için ITU-grid tarafından tanımlanan daha geniş ve sabit slotlar yerine bir veya daha fazla ardışık slot birlikte kullanılabilir. Sadece gerekli sayıda ardışık slot kullanarak farklı bant genişliğinde bağlantıları oluşturma becerisine sahip olmak, ağ kaynaklarının daha verimli kullanılmasını sağlar. Esnek optik ağlarda çözülecek en temel sorun, yönlendirme ve spektrum atama problemleri olarak bilinen yeni gelen trafik talepleri için uygun bağlantılar kurmaktır. Dinamik trafik koşulları altında, farklı sayıda slot kullanma esnekliği, WDM ağlarda mevcut olmayan spektrum parçalanması olarak adlandırılan yeni bir soruna neden olur. Dinamik trafik koşullarında, bir süre sonra, gelen ve sonlanan bağlantılar nedeniyle, optik spektrum giderek farklı boyutlarda serbest ve ayrık slot gruplarına bölünür. Bu, spektrumda serbest alanlar olmasına rağmen bağlantı isteklerinin engellenmesine neden olabilir. Esnek optik ağlar (EON), daha ince spektrum ızgaraları aracılığıyla, spektral kaynakları verimli kullanmak için çok umut verici bir çözümdür. Çoklu bant genişliği servisleri aynı ağ kaynaklarını paylaştığında, uygun bant genişliği yönetimi gerekir. Ayrıca, yüksek bant genişliği isteklerinin düşük bant genişliği istekleriyle karşılaştırıldığında engellenmesi daha olasıdır ve bu da farklı istekler arasında adalet sorununa neden olur. Bu tezde temel amaç, dinamik trafik altındaki esnek optik ağlarda yönlendirme ve spektrum ataması problemini incelemektir ve problemi çözmek için yeni yöntemler geliştirmektir. Bu amaçla, spektrum kullanımı için elastik optik ağın dinamik davranışını modellemek için yeni bir grafik model geliştirilmiştir. Bu model, ağın mevcut durumunun grafiksel bir biçimde ve bellekteki uygun bir veri yapısının görselleştirilmesini basitleştirir. Modelin temel kavramları ilk önce tek bir bağlantı için gösteriliyor, daha sonra aynı fikir modeli tüm ağ topolojisini temsil etmek için genelleştirmek için kullanılıyor. Tek bir bağlantı için geliştirilen katmanlı model iki istek modelinde gösterildi, birinci tip [1, k] arasındaki herhangi bir sayıda slot bulunan tek biçimli bir model ve ikinci tip isteklerde ise, bağlantıların bant genişliği ihtiyacı ikinin katları halinde ifade edilebilir. Geliştirilen model hem statik hem de dinamik yönlendirme ve kanal atama durumlarında, ağdaki slotların belli bir andaki kullanım durumunu temsil etmek için kullanılabilir. Bir ağda gelen bağlantı istekleri belirli bir süre için önceden biliniyorsa, statik yönlendirme ve kanal atama yöntemleri kullanılabilir. Bu durumda ağda çok sayıda bağlantının kurulması için en uygun konfigürasyonu belirlemek için aynı anda tüm bağlantıları ele alabilen optimizasyon yöntemleri kullanılabilir. Ancak bu problem yapısı gereği NP-zor olduğu için tamsayı doğrusal programlama gibi yöntemler yerine sezgisel algoritmaların kullanılması tercih edilir. Bu tür sezgisel yöntemler ise bağlantıları belli bir kritere göre sıraya dizerek, teker teker kurulması prensibine dayanır. Bu durumda önerilen model ağ kaynaklarının kullanımını gösterebilmesi açısından yararlı olacaktır. Dinamik trafik durumunda ise, bağlantı isteklerinin ağa teker teker ve rastgele olarak geldiği varsayılır. Gelen bir bağlantı isteği için uygun yolun bulunması ve bu yol üzerindeki seçilen slot gruplarının rezerve edilmesi gerekmektedir. Bunu yaparken sadece ağın o anki durumuna bakılır. Bu nedenle ağ durumunu güncel tutan bir veri yapısı yönlendirme ve kanal atama algoritmalarını hızlandırabilir. Bu yeni modeli kullanarak, NP yönlendirme zorluğu olan genel yönlendirme ve spektrum ataması problemini çözmek için yeni etkili sezgisel algoritmalar tasarladık. Temel yaklaşım, farklı bant genişlikleri ile istenen adalet sağlamaya çalışarak genel engelleme olasılığını azaltmaktır. Adalet sorununu çözmek için iki yöntem önerdik: Birinci, Equal Opportunity Slot Assignment (EOSA) yönteminde, belirli slot numaralarından başlayan slot gruplarını tahsis etmeyi amaçlamaktadır. Bu sayede slot ataması mümkün olduğu kadar düzenli yapılır. Bir isteğin başlangıç slot numarası, kaç tane slot gerektirdiği dikkate alınarak belirlenir. Bu yöntemin asıl amacı, yüksek bant genişliği isteklerine, onları spektrumda düzgün bir şekilde yerleştirerek daha iyi atama olanakları sağlamaktır. Örneğin, biri 1 slotlı bant genişliğinde diğeri 7 slotlı iki bağlantı isteği, 16 slotlı bir blokta ilk 8 slotun parçası olarak yan yana yerleştirilebilir. Benzer şekilde, 2 ve 6 yarık, 3 ve 5 yarık, ... bağlantılar ayrıca 8 yarıkta toplanır. Daha yüksek bant genişliğine sahip bağlantı istekleri için 8 slot, böyle bir tamamlama gerekli değildir. Amaç, yüksek bant genişliği bağlantıları için engelleme olasılığını mümkün olduğunca azaltmaktır. İkinci yaklaşım olan, Nigh-Fairness Slot Ataması (NFSA), burada yine tüm spektrumu maksimum genişlikte slot gruplarına böldük. Temel fikir, her grubu iki eşit parçaya bölmektir; birinci kısım EOSA gibi davranır ve ikinci kısım seçilen herhangi bir algoritmayı izler. Simülasyonlarımızda First-Fit slot atamalarını kullanıyoruz. Bir istek geldiğinde, algoritma isteğin bant genişliğinin maksimum genişliğin yarısından daha küçük olup olmadığını kontrol eder ve bu durumda ilk uyan yöntemi kullanılır. Önerilen yöntemlerin her ikisi de, ağa gelen bağlantı taleplerinin slot numaralarının eşit şekilde dağıtıldığı varsayımına dayanmaktadır. Aslında, slot numaralarının dağılımı biliniyorsa, başlangıç slot numaralarına bağlı olarak farklı atamalar yapılabilir. Deneyler için farklı özelliklerde (Atamasında, ayrıt yoğunluğu) ağ topolojileri seçilmiştir. Bunlardan ikisi Kuzey Amerika topolojisi (NSFNet ve USNet), ikisi de Avrupa kıtası topolojisidir (COST239 ve COST266). Bu topolojiler, literatürde de benzeri çalışmalarda sıklıkla kullanılan fiziksel ağlardır. Deneylerde ağa gelen trafiğin, yani bağlantı isteklerinin Poisson dağılımına uygun olduğu varsayılarak, farklı yoğunluklarda bağlantı istekleri rastgele olarak üretilmiştir. Bağlantıların bant genişliği istekleri slot sayısı cinsinden 1 ile 16 arasında düzgün dağılmaktadır. Ağdaki tüm düğüm çiftleri arasında bağlantı isteği gelme olasılığı da eşittir. Bu seçilen trafik parametreleri, literatürdeki çalışmalar incelenerek ve en çok kullanılan parametreler gözönüne alınarak belirlenmiştir. Önerilen yöntemlerin performansını değerlendirmek için, EOSA ve NFSA'yı, farklı omurga topolojilerinde, karartma olasılığı durumunda en iyi performansa sahip First Fit slot atama yöntemiyle karşılaştırıyoruz. Farklı topolojiler için yapılan simülasyon sonuçları, ilk yöntemimizin, yüksek engelleme olasılığı olan kısmi adalet sorununu iyileştirdiğini, ancak ikinci yöntemimizin, engelleme olasılığını birinciden daha iyi geliştirdiğini göstermiştir. Genel olarak, yöntemlerimizin istenen adaleti sağladığını ve tüm ağın performansını engelleme olasılığı açısından dikkate değer bir şekilde iyileştirdiğini göstermektedir.
Özet (Çeviri)
In elastic optical networks, the optical spectrum is divided into very narrow bands (slots) and one or more consecutive slots can be used together, instead of thicker and fixed slots defined by the ITU-grid for WDM optical networks. Having the ability to create different bandwidth connections using only the required number of consecutive slots enables more efficient use of network resources. The most fundamental problem to be solved in elastic optical networks is to establish appropriate connections for new incoming traffic requests, known as routing and spectrum assignment problems. Under dynamic traffic conditions, the flexibility to use a different number of slots brings about a new problem called spectrum fragmentation that is not available in WDM networks. In dynamic traffic, over a period of time, the optical spectrum is divided into several free and separated slot groups of different sizes. This may result in blocking of connection requests even though there are free spaces in the spectrum. Another problem in elastic optical network is the fairness problem, which is due to high bandwidth requests are more likely to be blocked compared to low bandwidth requests. The main aim in thesis is to examine the problem of routing and spectrum assignment in the elastic optical networks under dynamic traffic and develop new methods for solving the problem. For this purpose, a new graphical model will be developed to model the dynamic behavior of the elastic optical network for spectrum utilization. This model simplifies the visualization of the current state of the network in a graphical form and an appropriate data structure in the memory. The basic concepts of the model are first shown for a single link, then the same idea is used to generalize the model to represent the entire network topology. The use of this model in the routing and spectrum assignment is explained by the update procedures in the structure after the addition or removal of a link. This new model can reduce the time complexity of routing and spectrum assignment methods by providing a data structure that captures the current spectrum of network links. Using this new model, we designed new effective heuristic algorithms to solve the problem of general routing and spectrum assignment, which proved to be NP-hard. The basic approach is to reduce the probability of general blocking by trying achieve desired fairness with different bandwidth. To solve the fairness problem, we proposed two methods: In Equal Opportunity Slot Assignment (EOSA), we set the slots that are determined by the number of slots needed, and the location of the slot will begin with respect to the predefined sections of whole grid. In the second approach, Nigh-Fairness Slot Assignment (NFSA), this idea has been developed using two different slot assignment methods. In general, the complexity of the problems prevents the optimal resolution of these except for very small samples. To evaluate the performance of the proposed methods, we compare EOSA and NFSA with First Fit slot assignment method, which has the best performance in case of blacking probability, on different backbone topologies. The result of comparison shows that our methods achieve desired fairness and improves the performance of the entire network in terms of blocking probability remarkably.
Benzer Tezler
- Milimetrik dalga ağlarda çoklu kullanıcılara iletimlerde adil hüzme tahsisi ve ölçeklenebilir video kodlamali video çoğa gönderimlerde deneyim kalitesi temelli hüzme planlaması
Fair beam allocation in millimeter-wave multiuser transmission and quality of experience based beam scheduling for svc video multicast to multiple groups in millimeter-wave networks
FIRAT KARABABA
Yüksek Lisans
Türkçe
2017
Elektrik ve Elektronik MühendisliğiTOBB Ekonomi ve Teknoloji ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. TOLGA GİRİCİ
- A demand assignment multiple access scheme with two level message base priorities
Başlık çevirisi yok
SELDA BEDESTENLİOĞLU
Yüksek Lisans
İngilizce
1990
Elektrik ve Elektronik MühendisliğiBoğaziçi ÜniversitesiPROF.DR. ERDAL PANAYIRCI
- An analysis of sexism in English coursebooks in tertiary education
Yükseköğretimde kullanılan İngilizce ders kitaplarındaki cinsiyetçilik üzerine bir analiz
IŞIL KOÇ
Yüksek Lisans
İngilizce
2021
Eğitim ve ÖğretimGazi Üniversitesiİngiliz Dili Eğitimi Ana Bilim Dalı
PROF. DR. KEMAL SİNAN ÖZMEN
- Kur'an-ı Kerim'e göre müslüman ve sorumlulukları
The Moslem and the responsibilitien of moslem according to the Koran
ERDAL ERTORUN
Yüksek Lisans
Türkçe
2004
DinAnkara ÜniversitesiTemel İslam Bilimleri Ana Bilim Dalı
PROF. DR. İDRİS ŞENGÜL
- Makine öğrenmesi ile BİLSEM'de öğrenci başarısını tahmin etme
Predicting student achievement in BİLSEM exam with machine learning
HAKAN ESEN
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇankırı Karatekin ÜniversitesiElektronik ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. SELİM BUYRUKOĞLU