Genetik Algoritma ile İletişim Ağlarında Yönlendirme Optimizasyonu

1.GİRİŞ

1.1 Genetik Algoritma

Genetik Algoritma, evrimsel hesaplama yöntemi kullanan yapay zeka uygulamalarından biri olarak nitelendirilebilir. Adından da anlaşılacağı üzere Darwin’nin evrim teorisinden ilham alınarak modellenenmiş olup, doğal seleksiyon ve doğal genetik mekanizmaya dayanan araştırma metodu kullanır. En iyi çözümü elde edebilmek için, zayıf çözümleri evrimsel bir işleyişe göre eleme yoluna gider. En iyi çözüm, yapılan çevrimler (iteration/yineleme) sonucunda hala hayatta kalabilmeyi başaran çözümdür.

Evrimsel hesaplama metodu ilk olarak I. Rechenberg’in ‘Evrim Stratejileri’ eserinde tanıtılmıştır. Ardından Jonh Holland, evrim sürecini bilgisayar ortamında kullanarak genetik algoritmaları oluşturmuştur. Holland’ın ögrencisi olan D.E Golldberg 1989 yılında GA’nın çeşitli konularda kullanılabileceğini gösteren bir kitap yayınlamıştır. 1922 yılında ise John Koza genetik algoritmayı kullanarak genetik programlamayı geliştirmiştir.

GA’nın bir çok mühendislik probleminin çözümüne ilişkin uygulamaları mevcuttur. GA, geleneksel yöntemlerle çözümü zor veya imkansız olan bir çok problemler üzerinde uygulanabilir. Deneysel çalışmalardan, endüstiriyel uygulamalara kadar bir çok alanda GA çalışmaları yapılmaktadır. Mühendislikte, çözüm uzayı geniş olan problemlerin muhtemel çözümlerinin taranarak en iyinin bulunmasının çok zaman alıcı olduğu durumlarda, çoğu zaman kazandırıcı bir yöntem olarak karşımıza çıkar.

Genetik Algoritma, problemin ele alındığı ortamda (doğada) yer alan uygun ve güçlü çözümlerin (bireylerin) yaşatılarak, iyiler arasından daha da iyileştirilmiş çözümler üretmeyi amaç eden bir yöntemdir. Ancak her problem için en optimum sonucu bulduğunu garanti etmez.

GA’nın işleyişinde en temel unsur “uygunluğun” (fitness) ne olduğunun tarifinde yatar. Matamatiksel anlamda bu modellenmesi ve muhtemel her çözüm üzerinde uygulanması gereken bir fonksiyondur.

Çok temel bir örnek olarak iki şehir arasınında onlarca yol olduğunu ve bu yolların çoğunun Şekil 1.1’deki gibi birbiriyle kesiştiğini düşünelim. Yollar arasındaki bu kesişim noktaları bizim yeni güzargahlar elde etmemizi sağlayacaktır. Böylece elimizdeki alternatif güzergah sayısı artacaktır. Şimdi elimizdeki alternatifleri en uzundan en kısaya kadar sıraladığımızı ve uzun olanları elediğimizi düşünelim. Şayet mevcut yollardan yeni güzergahlar türetmeden en uzun yolları hemen eleseydik belki de daha kısa güzergahlar elde edemeyecektik. Zira uzun yollar diğer yollarla kesiştiğinde bize daha kısa yolların oluşmasına da neden olabilirler.

Şekil 1.1 İki nokta arasındaki olası güzergahlar

İlk bakışta bizim için en uygun yol en kısa yoldur. O zaman uygunluk fonksiyonumuz mesafe ile ters orantılı olmalıdır. Peki bu iki nokta arasındaki trafik çok yoğunsa durumu nasıl değerlendirmek gerekir? Elbetteki, uygunluk fonksiyonumuzun mesafe ve trafik yoğunluğu değişkenlerinin her ikisinide kapsayacak şekilde yeniden dizayn etmemiz gerkecektir. Bazı yollları paralı olduğunu ve fiyatlarınında değişik olduğunu düşünelim. Bu durumda ise en iyi yolu mesafe, yoğunluk ve maliyet değişkenleri dikkate alınarak dizayn edilmiş bir fonksiyonla bulabiliriz. Kısaca bizi amacımıza götüren bir çok çözüm olabilir ama hangi çözümümün en iyi olduğunu bulabilmek için kısıtlamalarımızın iyi tarif edilmesi ve bu tarife göre mevcut çözümler arasından en iyilerin seçilmesi gerekir.

1.2 İnternet ve Trafik Yönlendirme

Geride bıraktığımız son on senede, internetin tüm dünyada yayınlaşmasına tanık olduk. Bu gün yaşantımızın vazgeçilmez bir parçası haline dönüşen internet, son kullanıcılarına sevis sağlayıcılarının omurgaları üzerinden sunulmaktadır. Artan ihtiyaçları karşılayabilmek için bu omurgalar sürekli genişletilmekte ve yenilenmektedir. Bir çok servis sağlayıcı, omurgaları üzerinden kullanıcılarının web, e-mail gibi temel internet servislerinin yanı sıra telefon, video konferans, radyo, TV gibi tüm telekominikasyon ihtiyaçlarının vermek istemektedirler. Servis sağayıcılar, farklı karakteristiklere sahip tüm bu servisleri tek bir omurga üzerinden verebilmeleri için , ciddi bir trafik mühendisliğine gereksinim duymaktadırlar.

Trafik mühendisliği (TE), farklı önceliklere sahip ses, video ve data trafiğinin ortak bir taşıma platform üzerinden sağlıklı olarak nasıl transfer edileceğiyle ilgilenmektedir. İnternet omurgası bir çok servis sağlayıcının arabağlantılar (interconnection) ile birbirine bağlanmasıyla oluşur. Dolayısıyla böyle bir ağ tek bir otorite tarafından yönetilmediğinden anarşik bir yapıya sahiptir ve böyle bir yapının regulasyonunu yapmak pek de mümkün değildir. Ancak bir çok servis sağlayıcı kendi komşularıyla (peering yada upstream provider) kararlı bir ilişki kurmayı amaçlar. Böylece her servis sağlayıcı ihtiyaçlarını dikkate alarak kendi içinde ve doğrudan komşularıyla olan bağlantılarında trafik mühendisliği yapabilmektedir.

Servis sağlayıcılar kendi içindeki ve sınırlarındaki trafiği yönlendirmek için çoğu IETF (Internet Engineering Task Force) tarafından standartlaştırılmış yönlendirme protokolleri (routing protocol) kullanılırlar. Bu protokoller, operatörlerin girdiği verilere uygun olarak trafiğin akışını belirleyen algoritmalardır. Bu protokoller genel anlamda omurga içi ve dışı olmak üzere iki katagoriye ayrılır. Omurga içinde kullanılan protokoller IGP (Interior Gateway Protocol ) olarak adlandırılır ve bunlar arasında RIP (Routing Information Protocol) , IGRP (Interior Gateway Routing Protocol), EIGRP (Enhanced Interior Gateway Routing Protocol) ve OSPF (Open Shortest Routing First) ’dir. Omurgalar arası sınırda kullanılan ise EGP (Exterior Gateway Protocol) olarak adlandırılır ve bu gün BGP (Border Gateway Protocol ) neredeyse kullanılan yegane EGP protokolüdür.

Yönlendirme protokolleri, bir noktadan kaynaklanan trafiğin hedefine hangi yolla gideceğini belirlemekte kullanılır. Her protokolün kendine ait kriterleri vardır ve kendi kriterine en uygun yolu seçer. Genel olarak bu kirterler: atlanan nokta sayısı (hop count), linklerin bant genişliği, linklerdeki gecikme ve operatörlerin filtrelerle belirlediği kendine özel politikaları olarak sıralanabilir. Her protokol, aktaracağı trafik için en uygun yolu bulmaya çalışır. Başka bir ifadeyle alternatif yolları elindeki uygunluk fonksiyonuna göre eler ve kendince en iyi yolu hesaplar. Yönlendirme protokolerinin en uygun yolu nasıl hesapladıkları RFC’lerinde (Request for Comments) ayrıntılarıyla tanımlanmıştır.

Yönlendirme protokolleri, her trafik kaynaği için en uygun yolu arar. Şayet bir yol bir çok bir çok trafik kaynağı için uygun olarak seçilmişse ve yolun kapasitesi bu yolu kullananların trafik taleplerinin toplamından az olmaya başlarsa o yol artık çoğu için uygun bir yol olmaktan çıkar. Kaynakların trafik talebi önceden kesin olarak bilinmediğinden omurgadaki bazı linklerde aşırı yoğunluklar, ona alternatif olabilecek bazı yollarda ise düşük link kullanımları görülebilir. Son yıllarda bir çok araştırmacı yönlendirme protokoleri için link kullanımlarını dengelyeci optimizasyon yöntemleri üzerine çalışmalar yayınlamıştır. Bu çalışmaların arasında Genetik Algoritma yöntemine de oldukça sık başvurulduğunu görüyoruz.

Bu alanda en çok üretilen çalışmaların ise günümüz IP omurga ağlarında en sık kullanılan protokol olan OSPF ile standartlaşma çalışmaların henüz tamamlanmamış olan MPLS üzerinde yapıldığını görülmektedir.

2. GENETİK ALGORİTMANIN ÇALIŞMA PRENSİBİ

GA, belirli problemlerin muhtemel çözümlerini kromozom benzeri veri yapıları şeklinde kodlar. Böylece her çözüm belirli kriterlere göre kodlanmış diziler haline getirilir ve bu diziler kromozom olarak çağrılır.

Kromozomların kodlanması farklı şekillerde olabilir. Kodlamalar arasında en kullanışlı olanlar:

• İkili Kodlama (Binary Encoding) : GA’da ilk kullanılan ve en yaygın olan kodlama şeklidir. Her kromozom 1 ve 0’ lardan oluşan katarlar (string) halinde ifade edilir.
• Permutayon Kodlaması (Permutation Encoding) : Daha çok sıralama problemlerinde kullanılan kodlama yöntemidir. Görev yada güzergah sıralaması problemlerinde kullanılabilir.
• Değer Kodlaması (Value Encoding): Bünyesinde gerçek sayısal değerler barındıran problemlerde kullanılan kodlama şeklidir. Bu tür poblemleri ikili kodlama ile çözmeye çalışmak daha zor bir yol olabilir. Böyle durumlarda, kromozomlar gerçek değerlerle doğrudan kodlanır.

Başlanğıçta, elimizde var olan çözümler (kromozomlar) bizim başlanğıç neslimizi (initial population) ifade eder. Şayet en başta elimizde varolan bir başlanğıç nesli yoksa, kromozomlar rastgele üretilebilir. Daha sonra doğal seleksiyon sürecini başlatabilmek için çaprazlama ve mutasyon operatörleri kullanılarak yeni nesiller türetilir.
GA’nın akış şeması en genel haliyle Şekil 2.1’deki gibidir.

,

Şekil 2.1 GA’nın genel akış şeması

2.1 Çaprazlama

Mevcut neslin seçilmiş kromozomlarından yeni bireyler oluşturmak üzere çaprazlama işlevi yürütülür. Bu operatörün temel fonksiyonu, yeni nesillerin atalarının birebir kopyası olmalarını engellemektir. Evebeynlerin çaprazma oranı farklı olabilir.

Çaprazlama operatöründen kromozomların iyi özellikleri birleştirerek daha iyi kromozomlar oluşturması beklenir. Böylece arzu edilen en iyi bireye yani çözüme ulaşılır. Çaprazlama sonucunda iyi olmayan bireyler de türeyebilir ancak onlar uygunluk değerleri düşük olacağından seleksiyon gereği elenecektir.

Programlama sürecinde dört farklı çaprazlama operatörü kullanılabilir. Bu operatörlerden hangisinin seçileceği ise problemin çözümü öncesi yapılacak değerlendimelere bakılarak karar verilir.

Çaprazlama operatörleri:

• Tek Nokta Çaprazlama: Kullanılabilecek en basit çaprazlamadır. Kromozomlar üzerinde tek bir nokta seçilir ve o nokta referans alınarak evebeyn kromozomlar çaprazlanır. Şayet popülasyonda yeterince birey yoksa, en iyi çözüme ulaşmak güçleşir.
• İki Nokta Çaprazlama: Tek noktadan farkı iki referans nokta seçilmesidir.
• Çok Nokta Çaprazlama: İki noktanın gelişmiş halidir. Bir çok referans nokta seçilir ve bu referanslara göre evebeynlerin koromozomları çaprazlanır.
• Uniform Çaprazlama: Burada koromozom üzerinde referans noktalar kullanmak yerine, çaprazlama maskesi kullanılır. Çaprazlama maskesinin uzunlugu her bir kromozomun uzunluğu kadardır. Maskedeki 1 ve 0 ‘lar, türetilen kromozomun hangi geni hani ebeveynden alınacağını belirler.

	Tek Nokta	İki Nokta	Çok Nokta	Uniform
Kromozom-1	11010|0101	110|100|101	11|0|1001|01	110100101
Kromozom-2	01101|0011	011|010|011	01|1|0100|11	011010011
Kromozom Maskesi	..- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -			101010101
Yeni Kromozom	110100011	110010101	111100111	110000111

Çizelge 2.1 İki kromozomun farklı şekillerde çaprazlanması

2.2 Mutasyon

Kromozom üzerindeki bazı dizilerin (DNA dizilerinin) yerleri ile oynayarak değişiklikler yapılmasıdır. Özellikle, problemin çözüm uzayı dar ise mutasyon oldukça önem taşır. Zira dar toplulukarda oluşan bir mutasyonun sonraki nesiller üzerindeki ektisi de yüksek olacaktır. Nesiller arası çeşitliliğin azalması durumunda mutasyon iyi bir etki yaratabilir. GA içindeki temel işlevi, öngörüyü zorlaştırsa da nesiller arasındaki farklılaşmaya katkıda bulunarak sonuca daha hızlı ulaşmayı sağlamaktır. Kromozomlar üzerindeki mutasyon olasılığı genelde düşük bir değere sahiptir.

Mutasyonlar, kromozom üzerindeki 1 değerini 0; 0 değerini ise 1 yaparlar. Ele alınan problemin yapısına uygun olarak faklı mutasyon operatörleri tercih edilebilir.

Bunlar:

• Ters Çevirme
• Ekleme
• Yer Değiştirme
• Karşılıklı Değişim

2.3 Seleksiyon

GA’nın amaca hitap edebilmesi, seçim kriterinin yani dogal seleksiyonun yeterince iyi olmasına bağlıdır. En uygun kromozomlarının seçilebilmesi için “uygunluğun” ne olduğunu iyi tanımlanmalıdır. Diğer bir ifadeyle bizi en iyiye (optimal ) götürecek olan uygunluk fonksiyonun zayıf çözümleri eleyecek, kuvvetli çözümleri ise yaşatacak şekilde modellenmesi gerekmektedir.

Uygunluk fonksiyonunda, her problemin kendi doğal karakteristiğinde yer alan parametreleri kullanılır. Bu parametrelerin, güdülen amaca uygun olarak formule edilmesiyle de uygunluk fonksiyonu (fitness function) elde edilmiş olur.

GA’nın her çevriminde (iteration), elde edilen kromozomlar, uygunluk fonksiyonuna tabi tutulalarak uygunluk değerleri hesaplanır. Daha sonra yüksek uyuma sahip olanlar seçilir. Bu noktada bir çok seçim yöntemi kullanmak mümkündür. En çok kullanılan seçim yöntemleri aşağıda sırasıyla verilmiştir.

2.3.1 Rulet Çemberi (Roulette Wheel)

Bu seçim yöntemine orantılı seçim mekanizması da diyebiliriz. Bu seçim metoduna göre her bireyin seçimle şansı, uyumluluk değeriyle orantılıdır. Uyumluluk değeri yüksel olan bireyin seçilerek yeni popülasyona eklenme olasılığı yüksektir. Ancak uyumluluk değeri düşük olanlarında seçilme olası vardır. Örneğin elimizde 4 kadar kromozom olduğunu düşünelim. Bu kromozomların uyuyumluluk değerleri aşağıdaki gibi olsun.

Kromozom 1 : 45
Kromozom 2 : 30
Kromozom 3 : 15
Kromozom 4 : 10

Tüm Kromomozomların uyumlulukları toplamı, S=100’dür.
Bu durumda kromozomların seçilme olasılıkları:

Kromozom	Seçilme Olasılığı
Kromozom 1	0.45
Kromozom 2	0.3
Kromozom 3	0.15
Kromozom 4	0.1

Çizelge 2.2 Kromozomların seçilme olasılığı

Rulet çevirelim, yani program satırımıza 0 ile topam değerimiz olan 100 arasında bir sayı üretecek olan s=rand (0,S) satırımızı yazalım. Şayet ‘Random’ fonksiyonumuzdan elde edilen sayı:

0 ile 45 arasında ise Kromozom 1 seçilsin.
45 ile 75 arasında ise Kromozom 2 seçilsin.
75 ile 90 arasında ise Kromozom 3 seçilsin.
90 ile 100 arasında ise Kromozom 4 seçilsin.

Şekil 2.2 Rulet Çeberine göre seçilme

Şekil 2.2’de açıkca görüldüğü gibi uyumluluk değeri büyük olanın seçilme ihtimali yüksek. Küçük olanın seçilme ihtimali ise düşüktür.
Şayet kromozomların uyumluluk değeri arasında çok ciddi farklılıklar varsa, sonraki nesillerde çeşitliliği azaltacaktır. Bu durum Rulet Çemberinin dezavantajı olarak düşünülebilir.

2.3.2 Sıralı Seçim (Rank Selection)

Her kromozom uyumluluk fonksiyonuyla hesaplanmış uyum değerine göre sıralanır. Daha sonra kromozomlar en kötü uyum değerine sahip olandan en iyi değere sahip olana doğru sıralanır. En uyumsuz kromozomun değeri 0, en uyumlu kromozomun değeri is N (toplam kromozom sayısı) kadardır. Böylece kromozomların seçilme olasılığı, doğrusallaştırılmış artan fonksiyon haline getirilir. Bu çeşitlilik yaratmak açısından Rulet Çemberinden daha iyi sonuç veren bir seçim yöntemidir.

Uyumluluk değerinin büyüklüğüne göre kromozomların seçilme ihtimalinin Şekil 2.3 gibi olduğunu düşünelim.

Şekil 2.3 Kromozomların uyumluluk değerine göre ağırlıkları

Sıralama Seçim metoduna göre kromozomların seçilme ihtimali Şekil 2.4’deki gibi olacaktır.

Şekil 2.4 Kromozomların uyumluluk değerine göre sıralanması

2.3.3- Elitist Seçim

Bu yöntemin diğerlerinden farkı, en iyi bireyleri korumasıdır. En iyi uygunluk değerine sahip olan birey veya belirli bir yüzdeye giren en iyi bireyler korunarak yeni topluma doğrudan eklenir. Burada iyi bireylerin çaprazlama ve mutasyon sonucu kaybolmasını engellemek için böyle bir yol izlenmiştir.

2.4 Başlanğıç Populasyonu ve Kromozom Uzunluğu

Populasyon sayımızın çokluğu, çözüm uzayımızı daha iyi örneklediğinden en iyi çözümü elde etme olasılığımız artacaktır. Diğer taraftan da programin çözüm sürecinde (run-time) populasyonun büyüklüğüne ve çevrim sayısına doğrudan bağlıdır. Bu nedenle populasyon genişliğinin gereğinden büyük seçilmesi süreci geciktireceği gibi iyi çözüme ulaşmamıza katkıda da bulunmayabilir. Populasyonun büyüklüğünün, probleme bakılarak belirlenmesi en uygun yoldur.

Şayet populasyonun geniş olması gerekiyorsa, çözüm uzayımızı bir çok alana bölüp aramalarımızı lokalize etmek uygun bir yol olabilir. Zira bazı problemlerde, bizi çözüme ulaştıracak aralığa gelene kadar çok fazla zaman kaybedebiliriz.

Kromozom uzunluğu da oldukça önemli bir parametredir. Bazen kromozomdaki bazı bitlerin optimum değeri erken belirlenebilir. Bu durumda bu bitler bir sonraki çevrimlere dahil edilmeden hesap dışı bırakılabilir.

2.5 GA ile Basit Bir Uygulama

GA’nın daha çok analitik yollarla çözümü zor yada mümkün olmayan problemlerin çözümün araştırmak için kullanılır. Ancak GA’nın çalışma şeklini kolayca irdeleyebilmek için analitik olarak da kolayca çözülebilecek bir problemi konu edeceğiz.

Şimdi bir fonksiyonun maksimum değerinin GA ile araştıralım. Uyumluluk fonksiyonumuz f(x)=26x-x2-192 olsun. Araştırma yapacağımız aralık ise 0<x<32 olsun. Bu aralıkta bize maksimum değeri veren x değerini GA kullanarak arayalım. x değerini 0 ile 32 arasında seçtiğimize göre kromozomlarımızı 5 bitlik katarlar (string) halinde kodlayabiliriz.

Şimdi üç kromozomdan oluşacak olan başlangıç popülsayonumuzu rand(0,32) fonksiyonumuzla ragele üretelim ve elde ettiğimiz ondalık değerlerimizi ikili tabanda kodlayalım.

Kromozom1: (5)= (00101)₂ Uyumluk Değeri:297
Kromozom2: (15)= (01111)₂ Uyumluk Değeri:357
Kromozom3: (21)= (10101)₂ Uyumluk Değeri:62

Başlağıç populasyonumuzu uyum değerlerine göre sıraladığımızda, ikinci kromozomun en uyumlu olduğunu görüyoruz. Şimdi elimizdeki kromozomlardan yeni kromozomlar elde ederek, uyumluluk değeri daha yüksek olan kromozom olup olmadığını araştıralım.

Kromozom1: = 00|101	Kromozom2=01|111	Kromozom1 = 00|101
Kromozom2: = 01|111	Kromozom3=10|101	Kromozom2 =01|111

Yeni Kromozom 1=00111
Yeni Kromozom 2=01101
Yeni Kromozom 3=00111

Elde ettiğimiz yeni kromozomları uyumluluk değerine göre sıralarsak:

Yeni Kromozom 2= (01101)2=13 Uyumluk Değeri=361
Yeni Kromozom 1= (00111)2=7 Uyumluk Değeri=325
Yeni Kromozom 3= (00101)2=13 Uyumluk Değeri=297

İlk çevrim sonucunda elde ettiğimiz kromozomlar içerisinde uyumluluğu en yüksek olanın Yeni Kromozom 2 olduğununu görüyoruz. Uyumluluğu daha yüksek bir kromozom bulup bulamayacağımız ögrenebilmek için yeni bir çevrime daha ihtiyacımız var. Ancak biz bu kromozomları onlarca çevrime tabi de tutsak en yüksek uyumluluk değerinin 361 volacağını göreceğiz. Ele aldığımız problem matematikteki basit bir minimum-maksimum değer bulma problermidir. Şimdi problemimizi analitik yollarla çözerek, en yüksek değerin 361 olacağını gösterelim.

f(x)= 26x-x²+192; bu fonksiyonun türevi f ’(x)=26-2x olarak elde edilir.

26-2x=0 ‘dan x=13 elde edilir. 13 değeri f(x) fonksiyonunun maksimum değerini verir.

f(13)=26*13-13²+192=361

Maksimum değerini hesaplamaya çalıştığımız basit bir fonksiyon olduğundan ve araştırma yaptığımız aralık dar olduğundan, az sayıda kromozomla ve bir kaç çevrimle en iyi sonuca vardık. Ancak daha kompleks problemler için onlarca kromozomun, onlarca defa çaprazlanması ve bazı kromozomlar üzerinde mutasyon operatörünün çalıştırılması gerekirdi.

3. YÖNLENDİRME PROTOKOLLERİ

Yönlendirme protokolleri temel işlevlerini şöyle sıralayabiliriz:

1-Ağın durumunu ve linklerdeği değişimi izleyip anons etmek
2- Muhtemel her yön için ağ üzerindeki en kısa yolu hesaplamak
3-Paketlerin kaynaktan hedefe doğru yönlendirmek

Paketi gönderme işlemi tüm yönlendirme protokolleri için aynıdır. Bu protokolleri birbirinden ayıran ağdaki değişikliklerden (topolojinin değişikliklerinden) nasil haberdar olacakları ve her yön için en kısa yol hesabını nasıl yapacaklarıdır.

Bir ağda yönlendirmeden sorumlu olan elemanlara Yönlendirici (Router) adı verilir. Yönlendiriciler, ağ üzerindeki istemci, sunucu vb gibi terminallerden kaynaklanan IP trafiğinin hedeflerine iletilmesinden sorumludurlar.

Yönlendiriciler üzerinden bir yada birden fazla yönlendirme protokolü koşabilir. Örneğin omurganın sınırında olan bir yönlendirici, omurga içindeki yönlendiricilerle OSPF ile dışındakilerle ise BGP protokolü ile konuşabilir.

Yönlendirme protokollerini IGP ve EGP olmak üzere iki temel sınıfta değerlendirdiğimizi söylemiştik. IGP içinde kullanılan protokolleride hesaplama yöntemlerine göre sınıflandırmamız mümkündür.

Şekil 3.1 Yönlendirme Protokollerinin sınıflandırılması

3.1 RIP (Routing Information Protocol)

RIP protokolü, Bellman’ın en kısa yol bulma algoritmasına dayanan ve 1988’de IETF tarafından standarlaştırılan yönlendirme protokolüdür. Yönlendirme protokolleri arasından Distance-Vector ailesine aittir.

RIP, yol hesabını atlama sayısını kriter alarak (hop count) yapar. Kaynaktan hedefe giden yollar arasında en az kaç yönlendirici atlanacaksa o yol RIP için tercih edilen yoldur. Kaynak ile hedef arasındaki atlama sayısı, metric ya da cost olarak adlanırılır.

RIP protokolün en büyük dezavantajı alternatif yollar arasındaki bant genişliği, yoğunluk, gecikme gibi önemli parametreleri dikkate almamasıdır.

RIP, ağ içerisindeki değişiklikleri yönlendiricilerin birbirlerine periyordik olarak gönderdiği “yönlendirme durum paketlerinden” anlar. Ağda bir değişiklik olsun olmasın bu bilgiler belirlenmiş bir süre zarfında dağıtılır. Büyük ağlarda sürekili gönderilen durum bilgileri ciddi bant genişliği israfına neden olabilir.

3.2 IGRP (Interior Gateway Routing Protocol)

Yönlendirici marketinin açık ara öncüsü olan Cisco’nun geliştirdiği Distance-Vektör temelli yönlendirme protokolüdür. IGRP’de uygun yol hesabında bant genişliği , gecikme(delay), güvenilirlik(reliability) ve yük(load) değerleri göz önünde tutululur. Kaynak ile hedef arasındaki yolun metrik değeri aşağıdaki şekilde formulize edilir.

M (metric)= [K1* b+ (K2*b/(256-load) +K3*d]* (K5/(reliability+K4)]
b= 256*10⁷/min(bandwidth)
d=256*delay

Yolun yük ve güvenilirlik değerleri aktarım sırasında yönlendirici tarafından hesaplananır. Min(bandwidth) ifadesi ise bize yol boyunca bulunan linkler arasında bant genişliği en küçük olan linkin sahip olduğu bant genişliği değeridir. Başka bir ifadeyle zincirin en zayıf halkasını temsil eder.

Cisco’nun varsayılan (default) konfigurasyonunda K1=K3=1 ve K2=K4=K5=0 olarak olarak atanır. Bu durumda metrik ifadesi:

M_default=[10⁷/min(BW)+delay] *256 olarak kısattılır.

Bu formul bize ‘minimum bant genişliği en büyük ve gecikmesi en yüksek olan yolun’ metrik değerinin en küçük olacağını söyler. Kaynak ile hedef arasındaki alternatif güzergahlar arasında metrik değeri en küçük olan yol tercih edilen yoldur.

3.3 OSPF (Open Shortest Path First)

OSPF protokolü geniş omurgalar içindeki dinamik yönlendirme ihtiyacına çözüm olarak 1998 yılında IETF tarafından standarlaştırılan bir protokoldür. Yönlendirme protokolleri arasından Link-State ailesine aittir.

Aralarında OSPF konuşan tüm yönlendiriciler birbirlerine kendi linklerine ait durum bilgisi diğer tüm yönlendiricilere aktarırılar. Yönlendiricleri kendisine ait link-durum bilgisini komşuluk yaptığı diğer yönlendiricilere bildirir. Daha sonra bu komşular kendi komşularına bildirirerek kademe kademe tüm omurgaya bu bilgileri aktarmış olurlar. Bu metotla tüm yönlendiriciler omurga içindeki tüm linklerin durumunu öğrenmiş olur. Komşuluk ilişkisiyle, link bilgilerini tüm omurgaya yayma metoduna Link-Durum Algoritması (Link-State Algortithm ) adı verilir. Şayet topolojide bir değişiklik olursa, sadece değişiklik bilgisi bildirilir. Oluşan değişiklik tüm yönlendiricilerin yönlendirme veritabanına (routing database) yansır ve en kısa yol ağacında değişiklikler meydana gelir.

OSPF nispeten geniş omurgaların ihtiyacını karşılamak maksadıyla dizayn edilmsine rağmen çok büyük omurgalarda kaçınılmaz olarak hantallaşabilir. Zira omurga büyüdükçe o omurgaya mensup link sayısı, dolayısıyla da topolojiye ilişkin değişiklik olasılığı artacaktır. Her değişiklik sonrası tüm yönlendiricilerin yönlendirme veri tabanında değişiklikler olacak ve bu değişikliklere göre yeniden hesaplamalar yapılarak en kısa yol ağacı elde edilecektir. Dolayısıyla ağda sıklaşan değişiklikler, hem yönlendiricilerin sistem kaynaklarının (CPU, RAM gibi) hemde bant genişliklerinin israf olmasına neden olacaktır. Böyle bir durumu kontrol altına alabilmek için omurga içinde segmentasyon yapmak verimlilik katabilir. OSPF’nin diğer IGP protokollerinden farkı da bize omurga içinde farklı çalışma alanları yaratabilmesidir

Yönlendiricilerin ağdaki diğer yönlendirilerin link durumları hakında sahip oldukları bilgileri kullanarak yönlendirme veritabanlarını (routing database) oluştururlar. Her yönlendirici elindeki bu bilgileri kullanarak her yön için en kısa yol ağacını (Shortest Path Tree) oluşturur. SPT, Dijkstra algoritması kullanılarak hesaplanır.

SPT oluşturulurken:

1- Yönlendiricilerin sahip olduğu her linke cost yada metric olarakta adlandırılan bir ağırlık (weight) değeri atanır. Bu değer ağırlık Bu değer 1 ile 65535 (216-1) arasında değişen bir tamsayı olabilir. Bu değer omurganın topolojisine ve kaynakların oluşturacağı tahmini trafik talebine göre operatör tarafından her link için teker teker atanan bir değerdir. Şayet operatör ağırlık değerini manuel olarak girmez ise yönlendiriciler her linkin ağırlığını o linkin bant genişliğiyle ters orantılı olacak şekilde atayacaktır.
2- Her yönlendirici, en uygun yol hesabını yani STP’yi linklerin sahip olduğu ağırlık değerlerini kullanarak yapar.
STP, linklere atanan ağırlık değerleri ile oluşturulduğundan ağırlık değerlerin çok dikkatli seçilmesi gerekir. En uygun link ağırlıklarının seçiminde çeşitli yöntemler kullanılmaktadır. Bu yöntemler arasında Genetik Algoritma da oldukça önemli bir yere sahiptir. GA ile OSPF ağırlık seçimi üzerine (OSPFWS) bir çok makale yanınlanmış ve AT&T gibi dünya devi sayılan servis sağlayıcıların omurgasında dengeli trafik dağılımı için link ağırlık değeri seçiminde GA’dan faydalanılmıştır.

3.3.1 OSPF’de Link Ağırlığının GA ile Belirlenmesi

Kaynak ve hedef arasındaki yol boyunca tek bir link olabileceği gibi bir çok link de bulunabilir. Bu linklerden herhanği birinde darboğaz oluştuğu takdirde yol boyunca tüm trafik etkilenir. Darboğazlar, trafik talebinin link kapasitesi aşması durumunda meydana gelir. Bu durumlarda linklerin ağırlık değerleriyle oynanarak trafiğin kısmen yada tamamen başka güzergahlar üzerinden akması sağlanabilir.

Omurgadaki trafiğin sağlıklı bir şekilde taşınabilmesi için, linklerin ağırlık değerinin, maksimum link kullanım değerini minimize edecek şekilde seçilmesi gerekir. Link ağırlık değeri seçiminde kullanılan tekniklerden biri de MIP (Mixer Interger Programing) yöntemidir. Bu yöntem Fortz ve Throup tartafından, deneysel çalışmalar sonucunda türetilmiş olup, “lokal araştırma buluşsalı” (local search heuristic) tekniğini kullanır. Bu yöntem daha çok küçük ve orta büyüklükteki ağlarda yönlendirme optimizasyonu yapmak için kullanılır.

Bizim bu çalışma kapsamında Link ağırlık seçimi için GA kullanacağız. Eueung Mulyana ve Ulrich Killat [1], GA ile link ağırlığı seçiminde 50 kromozomlu bir başlangıç populasyonu kullanmış ve önceden belirletdikleri çevrim sayısı kadar seleksiyon mekanizmasını işleterek ey iyi sonuca ulaşmaya çalışmışlardır. Optimum sonuç bilinmediğinden (zaten aranan optimum sonuçtur), çevrimden çıkabilmek (program exit condition ) için önceden belirlenen bir iterasyon sayısı kullanmışlardır. Bu durumda ele alınan ağın durumuna göre en kaç defa çevrim yapılması gerektiği iyi tahmin edilmelidir. Şayet gerekenden az çevrim yapılırsa optimum sonuç elde edilmeden program sonlanacaktır. Çevrim sayısının gereğinden fazla olması durunuda da, programın çalışma süresi (run-time) uzayacaktır.

3.3.1.1 Kodlama

Genetik algoritmayı problemimize uygulayabilmemizin ilk şartı muhtemel çözümleri uygun bir biçimde kodlamaktır. Burada oluşturulacak olan kromozomlar link ağırlıkları kullanılarak kodlanacaktır.

Wk herhangi bir linkin ağırlık değeri olsun. Bu durumda kromozomumuz : (w1,w2,.....wk,.....wE) olur. E ,ağdaki linkleri temsil eder ve her link E’nin elemanıdır. Bu durumda, k= 1,........E ‘dir ve Wk є [1,MAX] ‘dir diyebiliriz.

OSPF’de bir link’in alacağı maksimum ağırlık değeri 65535 olduğuna göre Wk є [1, 65535] olur.

3.3.1.2 Seleksiyon

Linklerin ağırlık değerlerinden türetilen tüm kromozomlar uygunluk foksiyonuna göre seçilecek yada elenecektir. Uygunluk fonksiyonu, linklerin kapasite ve yoğunluk değerlerinden elde edilen bir toplama fonksiyonu olarak türetilmelidir. Ağdaki iki nokta arasındaki kapasitenin cij ve bu linkin kullanım yoğunluğunun lij olsun. Uygunluk fonksiyonumuz Σij(cij /lij ) terimini içerecek şekilde dizayn edilmelidir.

Eueung Mulyana ve Ulrich Killat [1] çalışmalarında Sıralı Seçim (Ranking Selection) mekanizması kullandılar. Sıralı Seçime göre her kromozomonun seçilme olasılığı, uyumluluk sırasına göre ardışık olarak sıralanır. Daha sonra, evebeyn kromozomlar yeni nesil kromozomlar türetilir ve bir önceki nesilin kötüleri ayıklanarak yeni nesilin uyumluluğu yüksek olan kromozomları popülasyona dahil edilir.

Şekil 3.2 GA populasyon dinamiği

3.2.1.3 Çoğalma (Reproduction) :

M. Ericsson, M.G.C Resende, P.M Pardolos [2] çalışmalarında aşağıda verilen çoğalma döngüsünü kullandılar. Sabitler (Const1, Const2 ) farklı olmak üzere, bu dönğü diğer OSPF optimizasyon çalışmalarında kullanılmıştır. Sabit değerler, ele alınan probleme göre değiştirilebilir. Bu değerlerin iyi seçilmesi uygunluk değeri yüksek olan kromozomlara yakınsamayı da (convergence) iyileştirir.

Şimdi, programda çaprazlama ve mutasyon işlemlerini yürüteceğimiz kodları yazalım:

for (0;E;k++) // E omurgadaki toplam link sayısı

  {

  r = rand[0,1];

  if (r< const1)

  {

  W[o1,k]= rand[0,MAX]; // o1 =offspring1, o1 =offspring2.

  W[o2,k]= rand[0,MAX];

  }

  elseif (r< const2)

  {

  W[o1,k]= W[p1,k] ; //p1=parent1, p2=parent2.

  W[o2,k]= W[p2,k] ;

  }

  else

  {

  W[o1,k]= W[p2,k] ;

  W[o2,k]= W[p1,k] ;

  }

}

Programın ilk ‘if’ satırında, ürettiğimiz sayı const1 değerinden küçükse, genin 1 ile 65535 sayıları arasından rasgele seçilmesini sağlıyoruz. Böylece program bazı genlerin değerini rasgele üreterek mutasyon etkisi yaratmaktadır. Ancak mutasyon etksini küçük tutmak için const1 <<1 olacak şekilde seçilmelidir.

const2 değeri ise, yavru kromozomların genlerinin ne kadarının hangi kromozomdan alacağını belirler. Örneğin birinci yavru genlerinin % (100*(const2 - const1) kadarını birinci kromozomdan, % (100- 100(const1+ const2)) kadarınıda ikinici kromozomdan alır. const1 değerini çok küçük olduğundan, birinci yavru genlerinin:

% 100*const2 kadarını birinci kromozomdan;
%100* (1-const2) kadarını ikinci kromozomdan alır.

3.2.2 Link Kullanımının GA ile Optimizasyonu :

Eueung Mulyana ve Ulrich Killat [1], 6 yönlendirici ve 14 linkten oluşan ve üzerlerindeki trafiği OSPF protokolüne göre yönlendiren bir ağ üzerinde link ağırlık değerlerini GA ile yeniden belirlemiş ve nasil bir optimizasyon sağladıklarını göstermişlerdir.

Cisco gibi yönlendirici üreticileri, linklerin ağırlık değerlerini varsayılan (default) olarak, link kapasitesiyle ters orantılı olacak şekilde seçerler. Yani herhanği bir yönlendiricide OSPF protokolü aktif edildiğinde, şayet operatör tarafından aksi belirtilmezse, linkin metrik (cost) değeri kapasiteyle ters orantılıdır. Bu, global bir yaklaşım olup optimum çözümü sunma iddiası taşımaz. Optimum çözümü bulabilmek için tüm ağı göz önünde bulundurmak ve linkleri çeşitli trafik senaryolarına göre sınamak gerekir.

Şekil 3.3’de metrik değerleri link kapasitesiteleriyle ters orantılı olacak şekilde seçilmiş bir ağ gösterilmektedir.

Şekil 3.3 Orjinal link ağırlıkları ve kullanım oranları

Burada ortalama link kullanım oranının %22.4, maksimum link kullanım oranının ise %42.9 olduğunu görüyoruz.

Şekil 3.4’de ise GA ile tüm linklerin metrik değerleri yeniden tespit edilmiş ve link doluluk oranları ölçülmüştür.

Şekil 3.4 Optimize edilmiş link ağırlık ve kullanım değerleri

Burada ise ortalama link kullanım oranı %22.7 olup, maksimum link kullanım oranı %35.7 değerine düşmüştür.

Bu örnek uygulamada maksimum link metrik değeri 30 olarak seçilmiştir. GA içerisinde 100 çevrim (iterasyon) kullanılmış ve program 100 defa çalıştırılmıştır. Program C++ ‘nın standart kütüphanesi kullanılarak yazılmış ve 800 Mhz’lik işlemcili, Linux iştetim sistemi üzerinde koşturulmuştur.

4. SONUÇ

Evrimsel hesaplama tekniği kullanan Genetik Algoritma, analitik yolllarla veya diğer optimisazyon yöntemleriyle çözümü zor yada imkansız olan problemlerin çözümünde kullanılan bir yöntemdir.

Geleneksel optimizasyon yöntemleri genel olarak belirli sınırlarda lokal aramalar yaparlar. GA kendi tanım aralığında global arama yaparken, tarama aralığığını uygunluk değerlerlerine göre belirli bölgelerde sıkıştırır. Her iterasyon sonucunda, uygunluk değerlerindeki değişime göre kendini adapte edebilir. Bu özelliği sayesinde çözüm uzayındaki lokal optimumlar arasından global optimumu daha kolay bulabilmektedir.

Yönlendirme protokoleri iki nokta arasında en uygun yolu bulmayı hedefler. IP omurga içinde kullanılan OSPF protokolu uygun yol hesabında her link için atanmış ağırlık değerlerini kullanır. Her linkin optimum ağırlık değerini hesaplayabilmek için omurgadaki tüm linkleri göz önünde bulunduran global bir yaklaşım getirmek gerekir. Yapılan araştırmalar incelendiğinde GA’nın bu tür çalışmalar için oldukça etkili sonuçlar verdiği görülmüştür.

KAYNAKLAR

[1] Eueung Mulyana, Ulrich Killat :An Alternative Genetic Algorithm to Optimize OSPF Weights
[2] M. Ericsson, M.G.C Resende, P.M Pardalos: Genetic Algorith For The Weight Setting Problem In OSPF Routing
[3] Anton Riedl; Optimized Routing Adaptation in IP Network Utilizing OSPF and MPLS
[4] Anton Riedl; Routing Optimization and Capacity Assignment in Multi-Service IP Networks
[5] Berna Bolat, K.Osman Erol, C.Erdem İmrak ; Mühendislik Uygulamalarında Genetik Algoritmalar ve Operatörlerin İşlevleri
[6] Anton Riedl; A Hybrid Genetic Algorith for Routing Optimization in IP Network Utilizing Bantwith and Delay Metric
[7] http://www.cisco.com/warp/public/104/1.html
[8] http://cs.felk.cvut.cz/~xobitko/ga/

Hazırlayan: Alper Özbilen