Congestion and packet classification based flow management for software-defined networks
Yazılım tanımlı ağlarda tıkanıklık ve paket sınıflandırmaodaklı akış yönetimi
- Tez No: 637468
- Danışmanlar: DOÇ. DR. BERK CANBERK
- 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: 2020
- 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ı: 65
Özet
Yazılım Tanımlı Ağlar, klasik ağlardan farklı olarak kontrol düzlemi ve veri düzlemi olarak iki katmana ayrılmıştır. Kontrol düzlemi ağa gelen akışlara hangi işlemlerin uygulanacağı, hangi yollardan gönderilmesi gerektiği kararlarını verip veri düzlemine iletmekle yükümlüdür. Veri düzlemi ise gelen akışların paketlerini, içerisinde var olan kurallar ile karşılaştırıp uygun kuralı bulduktan sonra pakete ilgili işlemi uygulamakla yükümlüdür. Kendi içerisinde uygun kuralı bulamaz ise ilgili akış için hangi kuralların uygulanması gerektiğini kontrol düzlemine sormaktadır. İki düzlem de kendi içerisinde ayrı ayrı ve birbirinin işleyişini etkileyen sorunlara sahiptir. Bu tezde hem kontrol düzlemindeki hem de veri düzlemindeki sorunlara odaklanılmıştır. Yazılım Tanımlı Ağ teknolojisinde, kontrol düzlemi, ağa gelen verilere uygulanacak işlemleri karar vermesinden dolayı, tüm ağdan sorumludur. Kontrol düzleminde gerekli kararları alan cihaz kontrolör olarak isimlendirilmekte, kontrol düzleminin yapması gereken işlemlerden dolayı tüm ağa hakim olacak merkezi bir konuma sahiptir. Ancak bu merkezi konum ve her şeyden sorumlu olmak, veri düzleminde trafik artışı olduğunda işleyişini etkilemektedir. Örneğin veri yoğunluğunun ani ve çok yoğun arttığı durumlarda, veri düzlemine gelecek olan yeni paketlerin sayısı da artmaktadır. Bu durum ise veri düzleminin gelen akışlara uygun kural bulamamasına ve hangi kuralın uygulanacağına karar vermesi için kontrolör ile iletişimi sıklaştırmasına neden olmaktadır. Böylece kontrolörün çalışma hızı, veri düzlemi ile arasındaki iletişimin artış hızına yetişememekte ve tıkanıklığa sebep olmaktadır. Kontrolör ile veri düzlemi arasında yaşanan tıkanıklık, kontrolörün gelen isteklere cevap verme süresini arttığı gibi kontrolöre gelen paketlerin düşürülme oranını da arttırmaktadır. Bunun yanında, artan cevap süresi, uçtan uca gecikmeyi (e2e latency) de arttırmaktır. Bu sorunları çözmek için, bu çalışmada kontrolöre uygulanmak üzere bir“Akış Yönetim Birimi”önerilmiştir. Önerilen bu birim kendi içerisinde Kabul ve Öncelik Yönetim Birimi olmak üzere iki alt birime sahiptir. Her iki alt birimde ise yeni nesil 5G ağlardaki farklı tiplerdeki akışların (URLLC, eMBB, mMTC) ihtiyaçları düşünülerek herbir akış için kuyruk önerilmiştir. Kabul Yönetim Birimi'nde Loss Ratio-Based Random Early Detection (LRED) algoritması çoklu kuyruk yapısına ve bir sonraki birim ile iletişime geçecek şekilde değiştirilip kullanılmıştır. Öncelik Yönetim Birimi'nde ise öncelik yönetimi için ağaç yapısı önerilmiştir. Önerilen bu ağaç yapısı ile hem farklı tipteki akışların farklı hız ihtiyaçlarına göre öncelik değerleri düşünülmüş hem de kuyrukların yakın gelecekteki doluluk oranları düşünülmüştür. Ancak, öncelik yönetimi için ağaç yapısının kurulması, uygun eyleme karar vermek için ağaç üzerinde gezileceğinden zaman kaybına neden olabilmektedir. Bu zaman kaybını önlemek için ağaç yapısındaki her düğüm için“Öncelik Değeri”tanımlanmış ve bu değerlere bakarak ağaç üzerinde gezme işleminin süresini kısaltmak için bir algoritma önerilmiştir. Öncelik Yönetim Birimi'nde kurulan ağaç yapısında, her bir katman, uygulanacak işlem sonucunda kuyrukların gelecekte oluşabilicek olası durumlarını tutmaktadır. Üç farklı akış tipi için oluşturulmuş üç farklı kuyruktan hangisine öncelik verileceği işlemi kuyruk sayısından ötürü üç farklı olasılığa sahiptir. Bu da, ağaç üzerinde her bir düğümün üç farklı çocuk düğümüne sahip olmasına neden olmaktadır. Her bir düğümün sahip olduğu öncelik değeri, hem akış tiplerinin öncelik değerleri hem de düğümün içerisinde kuyrukların boyları ele alınarak hesaplanmaktadır. Fakat ağaç üzerinde her bir düğüm için bu değeri hesaplama ve gezme işlemlerinin zaman almaması için geliştirilen algoritma, bir sonraki katman için hangi düğümün çocuk düğümleri için öncelik değeri hesabı yapılacağına karar vermekte ve bu yolla ağacı gezmektedir. Böylece uygun kararı vermek için hem tüm düğümler için öncelik değeri hesaplanmamış hem de tüm ağaç gezilmemiş olmaktadır. Bir sonraki katmandaki çocuk düğümlerinin öncelik değerlerini hesaplamak için ise, o anki katmanda hangi düğümün öncelik değeri en büyük ise o düğüm seçilmektedir. Bu da bize hangi kuyruktan paket alınıp işleme sokulacağını göstermiş olmaktadır. Kontrolöre uygulanan“Akış Yönetim Birimi”sayesinde, yapılan performans deneyleri ile kontrolör cevap süresinde %53'e kadar iyileşme, uçtan uca gecikmede %58'e kadar iyileşme ve paket düşme oranında ise %36'ya kadar bir iyileşme görülmüştür. Yazılım Tanımlı Ağ teknolojisi, yukarıda bahsedilen ve kontrol düzleminde yer alan yoğun ve ani trafik artışında oluşan sorundan başka veri düzleminde de soruna sahiptir. Paket sınıflandırma işlemi, klasik ağlarda da paketlere hangi işlemlerin uygulanacağına karar veren yönlendirici ve anahtarlarda uygulanmaktadır. Yazılım Tanımlı Ağ teknolojisinde her ne kadar paketlere hangi işlemlerin uygulanacağına karar verme işlemi kontrol düzlemindeki kontrolöre verilse de, veri düzlemindeki bu cihazlar hala paket sınıflandırma işlemini yapmaktadır. Çünkü, karar veremeselerde, belleklerinde kontrolörün gönderdiği kuralları tutmaktadırlar ve gelen paketlere hangi işlemin uygulanacağına karar vermek için bu kurallara bakmaktadırlar. Böylece paket sınıflandırma işlemi, yazılım tanımlı ağlar için de geçerliliğini korumaktadır. Fakat, yazılım tanımlı ağ teknolojisinin farklı trafik tiplerine hizmet veren servislerin ağ üzerinde yer alıp kolay işlem yapmasına olanak sağlaması, bu kuralların hem sayısının hem de paketlerle karşılaştırma işlemi sırasında bakılan alan sayısının artmasına neden olmaktadır. Artan bu karmaşıklık ise paket sınıflandırma işleminin, yazılım tanımlı ağlar için önemini arttırmakta ve veri düzleminde soruna neden olmaktadır. Paket sınıflandırma işlemi, klasik ağlardan beri var olan bir işlem olmasından dolayı, literatürde paket sınıflandırmanın hızlı yapılabilmesi çokça çalışma bulunmaktadır. Bu çalışmalar donanım bazlı ve yazılım bazlı olmak üzere iki ana gruba ayrılabilir. Donanım bazlı çalışmalarda Ternary Content Addressable Memory (TCAM) en çok kabul gören teknolojidir. Bu teknolojinin yanısıra CAM temelli olarak Binary CAM (BCAM), Field Programmable Gate Array (FPGA) ya da Graphics Processing Unit (GPU) teknolojileri kullanılarak yeni yöntemler geliştirilmektedir. Ancak donanım bazlı çözümlerin artan kural sayısı ve kural alan sayısı ile birlikte ölçekledirilebilir olmaması ve doğası gereği belirli bir donanımı gerektirmesi bu çözümleri her durumda uygulanabilir olmaktan çıkarmaktadır. Ayrıca en çok kabul gören teknoloji olan TCAM'in çok fazla enerji tüketmesi, enerjinin verimli kullanılması gereken durumlar için dezavantaj olarak görünmektedir. Donanım bazlı çalışmaların aksine, yazılım bazlı çalışmalar altta çalışan donanımdan bağımsız olarak uygulanabilmektedir. Yazılım tanımlı çalışmalar ise kendi içlerinde alan uzayı bazlı (tuple space based) ve karar ağacı bazlı (decision tree based) olmak üzere ikiye ayrılabilir. Karar ağacı bazlı çalışmalar, ağaç yapısını oluşturabilmek için kuralların alanlarının oluşturduğu uzayı bölmektedir. Uzayı bölme yöntemlerine göre kesme (cut) ve ayırma (split) olmak üzere ikiye ayrılabilir. Ancak, bu yöntemleri kullanan çalışmalar karar ağacını oluştururken; her bir alanda farklı kurallar olacak şekilde bölemedikleri için kural tekrarı sorunu oluşmaktadır. Bu sorunda, herhangi bir kural, ağacın birden fazla düğümünde yer alabilmektedir. Bu durum ise hızlı bir paket sınıflandırması sunan karar ağaçlarının kural güncelleme süresinde aynı başarıyı gösterememesine neden olmaktadır. Kural tekrarı sorununu ortadan kaldırmak için geliştirilen kural bölütleme çalışmaları ise çalışma süresi olarak kural alan sayısına bağlı oldukları için karar ağaçları kurulma süresini yavaşlatmakta, dolayısıyla da sürekli değişen trafiğe sahip olan ağlarda paket sınıflandırma işlemi ile kural güncellemesinin yavaşlamasına neden olmaktadır. Kural bölütleme sırasında alan sayısından bağımsız olan çalışmalar ise bazı kural alanlarının tamamını veya bir kısmını yok saydıklarından yanlış bir bölütlemeye, dolayısıyla da yanlış bir sınıflandırmaya neden olmaktadır. Alan uzayı bazlı çalışmalardan en eskisi ve OpenFlow vSwitch içerisinde uygulananı ise Tuple Space Search (TSS) yöntemidir. TSS'nin OpenFlow tarafından kabul görmesinin en büyük nedeni sağlamış olduğu hızlı kural güncellemesidir. Çünkü karar mekanizmasının kontrolörde olduğu yazılım tanımlı ağ teknolojisinde, anahtarlarda yer alan kuralların hızlı bir şekilde güncellenmesi büyük önem taşımaktadır. Ancak sağlamış olduğu hızlı güncellemenin aksine, TSS gerektiğinde kuralların tüm alanlarını karşılaştırmak durumunda kalmasından dolayı yeterince hızlı paket sınıflandırması yapamamaktadır. TSS dışındaki alan uzayı bazlı çalışmalar ise ya birden fazla hash tablosu oluşturma ya da ayrı tablolarda olması gereken kuralları aynı tablolalara koyma dezavantajlarına sahiptirler. Bu çalışmada ayrıca, hızlı bir paket sınıflandırması ve kural güncellemesi için karar ağacı temelli bir yöntem sunulmuştur. Ancak yukarıda bahsedildiği üzere hızlı bir paket sınıflandırmasının yanında hızlı bir kural güncellemesinin gerçekleştirilmesi için karar ağacı yöntemlerindeki kural tekrarı sorununun çözülmesi gerekmektedir. Fakat çözülmesi için önerilecek kural bölütleme yönteminin ise kural tekrarı sorununa yol açmayacak olmasının yanında çalışma süresini hızlandırması için kural alan sayısından bağımsız olması gerekmektedir. Bu bağımsızlığı sağlarken ise yanlış bir paket sınıflandırmasına yol açmaması için bölütleme sırasında kural alan sayısından bağımsız olmasına rağmen kural alanlarının karakteristiklerini yansıtması gerekmektedir. Bu bağlamda, bu tezde sunulan kural bölütleme yöntemi kural tekrarı sorununu ortadan kaldırırmakta ve çalışma süresi olarak kural alan sayısından bağımsızlık sağlarken kural alanlarının tümünün karakteristik özelliklerini göz önüne almaktadır. Karar ağaçları oluşturmak için kullanılan kural bölütleme yöntemleri, kuralları birbirlerinden ayırırken kuralların Kartezyen Koordinat düzleminde kaplamış oldukları alan karşılıklarını kullanmaktadır. Bu bağlamda, kural alanları, koordinat düzleminin eksenlerini temsil ederken kuralların bu uzayda kapladıkları alanlar ise aslında eşlebilecek olası tüm paketleri temsil etmektedir. Çünkü kurallar koordinat düzlemi gösteriminde bir alanı temsil etmekte iken gelen paketler ise bu uzaydaki noktaları temsil etmektedir. Bu durumda, paket sınıflandırması, paketlerin, kuralların koordinat düzlemindeki alanlarının içerisinde olup olmadığının cevabı olmaktadır. Kural tekrarı sorunu ise koordinat düzleminde alanları kesişen kuralların birbirlerinden alanları kesişmeyecek şekilde ayrılamamasından kaynaklanmaktadır. Tezde sunulan kural bölütme yöntemi de kuralların ve paket sınıflandırmasının yukarıda anlatılmış olan koordinat düzlemindeki karşılığından faydalanmaktadır. Paket sınıflandırmasının koordinat düzlemindeki karşılığının anlatımından da görüleceği üzere paketin herhangi bir kuralla eşleşmesi için paketin koordinat düzlemindeki her bir eksendeki değerinin, kuralların ilgili eksene karşılık gelen her bir bölgesinin koordinat düzlemindeki başlangıç ve bitiş değerlerinin arasında olması gerekmektedir. Tezde sunulan kural bölütme yönteminde ise bu özellikten faydalanılarak bahsi geçen eşitsizlikler her bir kural alanı veya eksen için alt alta yazıldıktan sonra toplanmıştır. Elde edilen yeni ve tek eşitsizlik ise bize paket sınıflandırmasının ve kuralların tüm alanlarını göz önüne alarak tek bir düzlemdeki karşılığını vermektedir. Tek bir düzlemde elde edilen bu karşılık ise kural bölütleme sorununu, kolayca alan bölütleme (interval partitioning) sorununa dönüşmüştür. Bu nedenle, kural bölütleme için alan bölütleme yönteminde kullanılan klasik Greedy algoritması sunulmuştur. Burada amaç ise kuralların tek boyuttaki karşılıklarından yararlanarak en az sayıda bölüt oluşacak şekilde kuralları birbirlerinden ayırmaktadır. Elden edilen kural bölütleri içerisindeki kurallar ise, alan bölütleme işleminin doğası gereği birbirleri ile kesişmemekte ve dolayısıyla da her bir bölüt için oluşturulan karar ağaçlarında kural tekrarı sorunu ortadan kaldırılmış olmaktadır. Bunun yanında ise, kuralların tek boyuttaki bu karşılıkları kullanırak yapılan bölütleme işlemi, tüm kural alanlarının karakteristik özelliklerini yansıtırken, çalışma süresi olarak da kural alan sayısından bağımsız halde getirilmiş olmaktadır. Kuralların ve paket sınıflandırma işleminin çok boyutlu koordinat düzlemindeki karşılığının tek boyuta indirilmesi ve bu tek boyut üzerinden kural bölütleme işleminin alan bölütleme işlemine dönüştürülmesi sayesinde elde edilen kazanımlar, bize karar ağaçların daha hızlı kurulması, paket sınıflandırmasının daha hızlı yapılması ve kural tekrar tekrarı sorunun ortadan kalkması nedeniyle de daha hızlı kural güncellemesinin yapılması olanağını sunmaktadır. Yapılan simülasyon neticeleri ile de bu kazanımlar doğrulanmış ve literatürde yer alan en hızlı iki yöntemden daha iyi sonuç edildiği görülmüştür. Yapılan simülasyon sonucunda, kural bölütleme süresi ve kural güncelleme süresi olarak PartitionSort yönteminden sırasıyla %88 ve yüzde %15'e kadar iyileşme elde edildiği; paket sınıflandırma süresi olarak da %50'ye kadar iyileşme elde edildiği görülmüştür.
Özet (Çeviri)
In this thesis, we focus on problems in the control plane and problems in the data plane of SDN separaterly. In the control plane, we specifically try to increase the response time of the SDN controller in ultra-dense scenarios. In the data plane, we aim to construct an efficient data structure to achieve both fast rule update and fast packet classification. In the SDN, the control plane is responsible for deciding route and operations for flows that coming to the data plane. To do so, the SDN controller in the control plane has a central view and controls all switches in the data plane. But, this can cause an increase in both e2e latencies of packets and drop rate in the controller if there is a high spiky demand of incoming heterogeneous flows. Because, switches in data plane have to ask what to do to the controller if there is a new incoming flow to them. When newly coming flows increase, communication traffic between the controller and data plane increase. As a result, this can cause congestion in the SDN controller, and e2e latency and drop rate in the controller increase because of this congestion. To solve these problems, we propose a management engine to implement in the SDN controller in ultra-dense SDN scenarios. In this engine, we propose two steps: admission and prioritization steps. We also create different queues for different types of 5G flows (URLLC, eMBB, mMTC) in each step. In the admission, we modify Loss Ratio-Based Random Early Detection (LRED) Algorithm. In prioritization, we propose a tree-based prioritization that considers the priority needs of different flow types and near future states of different queues. According to simulation results, our response time of the SDN controller, e2e latency of packets and dropped rate in the controller are better up to 53%, 58%, and 36%, respectively. Packet classification is a key factor for choosing proper action for incoming packet and has to be done fast, especially in OpenFlow. But OpenFlow vSwitch technology doesn't allow to use some fast hardware technology for packet classification like TCAM. Decision tree methods are preferred solutions for fast classification in OpenFlow vSwitch in the literature. But most of these methods can cause the rule replication problem. As a result, while the duration of packet classification decreases, rule update duration increases. There are also rule partitioning methods in the literature to solve this problem, but the running time of these methods mostly depends on the number of rule fields. Also, some of these solutions don't overcome the rule replication problem. At that point, the main question is that how can we make the rule partitioning fast by both preventing the rule replication and allowing fast packet classification and rule update in OpenFlow vSwitch? To solve the rule partitioning problem, we convert this problem to the interval partitioning and propose a classic Greedy Algorithm. As a result, the running time of the partitioning algorithm only depends on the rule number. After partitioning, we propose to use HyperCuts to construct decision trees for fast packet classification and rule update. According to performance evaluation results, we do the rule partitioning and rule updates faster than the PartitionSort method with the percentage of 88, 15, respectively. We also classify packets faster than the TupleMerge method with the percentage of 40 for online and 50 for offline scenarios.
Benzer Tezler
- Windows sistemler için ağ dosya sistemi müşteri programı
Network file systems client program for windows systems
İLTER İNANÇ
Yüksek Lisans
Türkçe
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. EMRE HARMANCI
- Okunabilir kopyalama algoritmalı DSM sisteminin gerçeklenmesi
Başlık çevirisi yok
ÖZGÜR KORAY ŞAHİNGÖZ
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. TAKUHİ NADİA ERDOĞAN
- 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
- Devre bağlaşmalı telefon şebekesi için yönlendirme yazılımı tasarımı
Software design of routing for circuit switched telephone network
TAHİR GÜN
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiYRD. DOÇ. DR. ÜMİT AYGÖLÜ
- Isı yalıtım malzemelerinin özelliklerinin uygulamaya etkileri
Effects of the insulation materials' properties to the application
SELEN ÜLKER
Yüksek Lisans
Türkçe
2009
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
DOÇ. DR. LEYLA TANAÇAN