bilgiz.org

Atm ağlarinda yönlendirme

  • 1.Giriş
  • 2. Homojen ve İstatistiksel Çoklama Yöntemi Kullanan ATM Kategorisi için Yönlendirme Algoritmaları
  • 2.1. U-LLR (“Unrestricted Least Loaded Routing”)
  • 2.2. R-LLR (“Restricted Least Loaded Routing”)
  • 2.3. P-LLR (“Partially Least Loaded Routing”)
  • 3. Heterojen ve İstatistiksel Çoklama Yöntemi Kullanmayan ATM Kategorisi için Yönlendirme Algoritması
  • 4. Sonuç
  • 5. Kaynakça



  • Tarih01.10.2017
    Büyüklüğü58.13 Kb.

    Indir 58.13 Kb.

    ATM BİLGİSAYAR AĞLARINDA YÖNLENDİRMENİN ETKİNLEŞTİRİLMESİNE YÖNELİK ALGORİTMA TASARIMLARI

    Ar. Gör. Muhammed CİNSDİKİCİ Doç. Levent TOKER



    cinsdikici@staff.ege.edu.tr toker@staff.ege.edu.tr

    Ege Üniversitesi, Bilgisayar Mühendisliği Bölümü, 35100, Bornova, İzmir

    Tel: +90-232-388 10 80 Fax: +90-232-339 94 05

    ÖZET


    ATM ağlarında veri paketlerinin, dinamik olarak değişen trafik koşulları göz önüne alınarak hedeflerine doğru yönlendirilmeleri gerekmektedir. Belirlenen hedeflere doğru giden paketlerin her bir oturum(“session”) için aynı rotayı takip etmeleri zorunlu değildir. Bu yüzden dinamik trafik ve servis kalitesi(QOS, “Quality of Service”) değerlerinin belirlediği ölçüler içerisinde, maliyeti en düşük ve uzaklık olarak daha yakın mesafelerin tercih edildiği yönlendirme stratejilerinin belirlenmesi gerekmektedir. Gereksinimlere uygun bir rota tayini için, ATM ağlarının kategorileri ve bu kategorilerin trafik karakteristiklerini analiz etmek gerekir. Bu çalışma, ATM ağı kategorilerini ve bu kategoriler için geliştirilen yönlendirme algoritmalarını irdelemektedir.

    1.Giriş


    A
    TM ağlarında iletişimin gerçekleştirilmesi 53 oktet uzunluklu hücrelerin iletimi ile sağlanır. Bilgi bu 53 oktetlik hücrenin 48 oktetlik(“payload”) olan kısmında taşınırken, hücrenin anahtarlar arasında yönlendirilmesi ise 5 oktetlik(“header”) parça ile sağlanır. ATM ağlarında fiziksel hat üzerinde VP(“Virtual Path”)’ler tanımlanır. VP’ler ise birçok VC(“Virtual Circuit”)’nin birleşmesinden meydana gelmiştir. ATM hücrelerinin yönlendirilmesinde 5 oktetlik başlık kısmında yer alan VPI(“Virtual Path Identifier”) ve VCI (“Virtual Circuit Identifier”) sahaları, her bir anahtar içinden geçerken yönlendirme için belirlenmiş en uygun VP ve VC numaralarını alırlar. ATM ağlarında yönlendirmenin gerçekleştirilmesi için temel yapıda yer alan VC ve VP’lerin kapasiteleri en önemli faktörleri oluşturmaktadır. Şekil 1.’de yer alan örnek bir ATM ağı yapısında VP’lerin kullanımı gösterilmektedir[1].

    Şekil 1. ATM Ağı Fiziksel Yapısı ve VP kurulumu


    Şekil 1.’de gösterildiği gibi iki anahtar arasındaki fiziksel hattın bant genişliği bir ya da daha fazla sayıda VP tarafından kullanılabilir. VP’lerin toplam kapasitesi fiziksel hattın bant genişliğine eşit olup, VP’ler ağ yapısının kuruluşu esnasında atanırlar. Bu atama ağ yapısında meydana gelecek bir değişime kadar sabit olarak tutulur. VP’ler tek bir fiziksel hat’a adanabileceği gibi birden fazla fiziksel hat üzerine de adanabilir. Bu tip kullanımda VP’nin bant genişliği, izlediği fiziksel hat/hatlar üzerinde sabit olarak korunur. Böylece ara anahtarlardan geçerken VP’nin yüküne hiçbir hücre eklenmesi ya da çıkartılması gerçekleştirilemez. Anahtarlardan geçişlerde kullanılan tampon bellekler ise sadece hücre çakışmalarıyla karşılaşılmaması için gerekli olup, VP’nin bant genişliğinde önemsiz bir etkiye sahiptir.[1][2]
    Yönlendirme algoritmaları VP’ler üzerinde kurulan VC’ler için yapılandırılırlar. Bunun nedeni VP’lerin belirlenmesi işleminin ağın kuruluşu esnasında tamamlanmasıdır. VC’ler kapsamında yönlendirmede önemli olan prensipler, o VC için tanımlanan trafik değerleri ve servis kalitesi parametrelerini içermektedir. Trafik değerleri olarak belirtilen değerler en yüksek oran (“peak-rate”), ortalama oran (“mean-rate”) ve yoğunluk (“burstness”) ölçütleridir. Servis kalitesini belirleyen unsurlar ise hücre kaybı oranı “cell-loss rate”, gecikme süresi “delay time”, bilgide kayıp miktarı “jitter” gibi değerlerdir[1].
    ATM ağlarında VC’lerin üzerindeki veri trafiğinin yönlendirilmeleri sırasında belirlenen rota, VC’nin üzerinde kurulan çağrı sonlanıncaya kadar değiştirilmez. Bununla ilintili olarak, ağ yapısında aktif olan VC’lere göre yönlendirme bilgilerinin oluşturulduğu ve yapılandırıldığı görülmektedir.
    ATM ağlarında kullanılan yönlendirme algoritmaları, ATM ağlarının hangi kategoride olduğu ile yakından ilişkilidir. ATM ağlarının hangi kategorilere ayrıldığı ise VP ve VC’ler üzerinde taşıdığı bilginin tipi ile ilgilidir. Bilinen bilgi tipleri ses, görüntü ve veri olarak sınıflandırılmakta olup, ATM’de bunların hepsinin iletimi sağlanmaktadır. ATM ağları taşıdığı bilginin türüne göre ikiye kategoriye ayrılmaktadır[3];

    1. Homojen

    2. Heterojen.

    Bu arada ATM ağları yapısında VC’ler VP’ler içinde kendilerine ayrılan bant genişliğini kullanmakta iki ayrı alternatif sergiliyorlarsa, ATM bu şekilde de iki kategoriye ayrılır;



    1. İstatistiksel çoklanmış (“statistical multiplexed”)

    2. İstatistiksel olmayan çoklama yöntemi kullanan(“non-statistical multiplexed”).

    Yukarıda belirtilen kategorilerin kombinasyonları düşünüldüğü zaman, ATM ağlarında dört ayrı kategori karşımıza çıkmaktadır. Yönlendirme algoritmaları için temel teşkil eden bu dört ayrı ATM ağı kategorisi şöyle özetlenebilir[3];



    • Homojen ve istatistiksel olmayan çoklama yöntemi kullanan ATM ağları: Bu tip ATM ağlarında, her VP belirlenmiş bir veri tipine adanmıştır. Kurulan her VC ise kendine ayrılan bant genişliğini aşamaz. Bu bağlamda, ATM ağları içinde deterministik bir alt yapıya sahip olan bu kategoride yönlendirmenin ele alınışı basite indirgenmiştir. Bu kategori sabit veri oranlı (“constant bit rate”) sınıf olarak da bilinir.

    • Homojen ve istatistiksel çoklama yöntemi kullanan ATM ağları: Her bir VP belirlenmiş bir veri tipine adanmış olup, VC’ler kendi kapasitelerinin üzerlerine çok kısa zaman dilimleri içinde çıkış yapabilirler. Bu tip ATM ağı kapsamlı bir yönlendirme algoritması ile yönetilmelidir. Genelde yönlendirme algoritmaları bu sınıfa yönelik olarak geliştirilmektedir.

    • Heterojen ve istatistiksel olmayan çoklama yöntemi kullanan ATM ağları: Bu tip ağlarda aynı VP üzerinde farklı veri tipleri taşınabilir. Bu farklı bant genişlikleri anlamına gelir. Ve her bir VC kendi bant genişliğini aşamaz. Yönlendirme algoritmaları bu tip olan ATM ağları için de geliştirilmektedir.

    • Heterojen ve istatistiksel çoklama yöntemi kullanan ATM ağları: Burada VP’ler hem farklı veri tipleri kullanırlar hem de VC’ler bant genişliklerini kısa zaman aralıklarında aşabilir. Böyle bir ATM ağı sınıfında yönlendirme oldukça karmaşık olup iyi bir analiz ve değerlendirme gerektirmektedir.

    Yukarıda verilen dört tip ATM ağı kategorisi içinde sadece iki ve üçüncü olarak verilen ATM ağı sınıfları için geliştirilen yönlendirme algoritmaları bu çalışmanın konusunu oluşturmaktadır. Birinci ve dördüncü kategoride yer alan ATM ağları bu çalışmanın kapsamına alınmamıştır. Birinci kategoride yer alan ATM ağı ’nın sabit veri oranlı (“single-rate circuit switched”) bir yapıda oluşu, bu kategorinin basit olarak tasarlanmış algoritmalar yardımıyla işlev görebilmesini sağlar. Bu yüzden, bu tip bir kategorinin yönlendirme stratejilerinden bahsetmek anlamlı değildir. Dördüncü tip kategori için ise, ağ kaynaklarının kullanımı düzensizlik göstermektedir. Böylelikle geliştirilmek istenen yönlendirme algoritmaları karmaşık bir yapı teşkil ederler. Bu sebeple, dördüncü kategorinin yönlendirme stratejisi de bu çalışmada ele alınmayacaktır.


    ATM ağlarında kullanılan yönlendirme algoritmalarını anlayabilmek için klasik telefon ağı üzerinde kullanılan şu üç temel algoritmayı bilmemiz gerekmektedir; DNHR(“Dynamic Non-Hierarchical Routing”), DAR (“Dynamic Alternative Routing”), LLR (“Least Loaded Routing”)[3].
    Telefon ağlarında kullanılan bu üç tip yönlendirme algoritması temelde “N” adet anahtardan oluşan ve tüm anahtarların birbirine bağlı (“fully connected”) olduğu bir ağ yapısını baz almaktadır. Ve buna göre N adet anahtar, j adet fiziksel hat (j= N*(N-1)/2), Cj kapasitesi (j.’nci hat üzerinde yer alan devre sayısı) ve rj (TR, “trunk reservation”) değerleri olduğu varsayılarak, yukarıda bahsi geçen üç temel algoritma yapılandırılmıştır.
    DNHR Algoritması: Eğer rota tayin edilirken iki anahtar arasındaki direkt olan hat dolu değilse ve o hat üzerindeki TR değeri bize kullanma izni veriyorsa direkt olan hattı kullan[4]. Eğer direkt hat doluysa o zaman tüm direkt olmayan alternatif rotalar içinden bir alt küme seç, bu kümeyi TR parametresine göre sırala. Eğer TR değeri uygun olan bir rota bu listeden seçilebiliyorsa (ilk uygun olan) yönlendirmeyi gerçekleştir. Eğer listede yer alan rotalardan hiçbiri alternatif TR değeri olarak olanaklı değilse, çağrı istemini bloke et.
    DAR Algoritması: Eğer direkt rotanın TR değeri uygun ve hat boş ise yönlendirmeyi direkt hat üzerinden gerçekleştir[4]. Değilse “alternatif rota” olarak tanımlanmış rotayı incele. Eğer onun TR değeri uygun değilse çağrıyı bloke et. Ardından gelecek yeni çağrılar için ise geriye kalan N-3 adet hat içinden (2’li kombinasyonlar düşünüldüğünde) doğrusal dağılıma uygun olacak biçimde rastgele bir “alternatif rota” seç.
    LLR Algoritması: Eğer direkt rota kullanılabiliyorsa, yönlendirmeyi gerçekleştir[4]. Değilse, tüm “alternatif rotalar” için “olabilirlik” değerlerini (TR değerleri hesaplaması ve karşılaştırılması yapılarak elde edilmektedir) çıkar ve tüm bu olasılıklar içinde en uygun “olabilirlik” değerine sahip olan rota üzerinden yönlendirmeyi gerçekleştir[3].
    Olabilirlik = min{ (Ci-TRi-i) ; (Cj-TRj-j) } (1)
    burada “” değeri o anki kullanılan devre sayısını belirtmektedir.
    Telefon ağları için geliştirilmiş bu 3 adet algoritmayı kendi aralarında karşılaştırmak gerekirse;

    • DAR algoritması DNHR algoritmasına göre daha az maliyete sahiptir. Bunun sebebi sıralı bir liste tutmamasından kaynaklanmaktadır.

    • DAR algoritması önceden tahminleme için sadece mantıksal hatların kapasitesine bakarak TR atamasını buna göre yapmaktadır.

    • DAR algoritmasında (N-2) adet “alternatif rota” varken DNHR algoritmasında sadece bir alt küme yer almaktadır. Bu ise daha az bir olasılık ile karşı karşıya kalınması demektir.

    • DAR’da kullanılan sinyalleme gereksinimi azdır. Sadece bir adet “alternatif rota” olduğu için “cranckback” sinyali kullanımına gerek duymaz. DNHR ise hangi rota daha uygun bunu tespit edebilmek için bu sinyallemeyi her bir sıralı denemede anahtarlar arası kullanmak zorundadır.

    • LLR algoritması tüm alternatif rotaların “olabilirlik” değerlerini hesapladığı için DAR ve DNHR algoritmalarına göre daha karmaşık ve maliyeti yüksektir.

    • LLR algoritması “olabilirlik” değerlerini göz önünede tutarak yönlendirme yaptığı için, performansı yüksek bir yönlendirme stratejisine sahiptir.

    Telefon ağları için belirtilen yönlendirme algoritmaları ATM ağları için temel teşkil etmektedir. Bu algoritmaların geliştirilmesi, ATM’in kategorileri, ATM’in getirdiği trafik değerleri ve servis kalitesi parametrelerinin bir bütün olarak değerlendirilmesine bağlıdır.[5]


    Bir sonraki bölümde iki ATM kategorisi için tasarlanan yönlendirme algoritmaları yer alacaktır.

    2. Homojen ve İstatistiksel Çoklama Yöntemi Kullanan ATM Kategorisi için Yönlendirme Algoritmaları

    Bu tip ATM kategorisinde, tüm kaynaklar aynı tip trafik karakteristiğine ve servis kalitesi(QOS,”Quality Of Service”) gereksinimlerine sahiptir ve VC’ler VP’lerin girişlerinde istatistiksel olarak çoklanırlar[6]. Bu çoklama hücre seviyesinde detaylandırılmıştır. Servis kalitesi gereksinimlerinin bu seviyede ele alınması, yönlendirme algoritması için önemlidir. Hücre seviyesinde, servis kalitesi gereksinimleri mutlaka “hücre kaybı”, “hücre gecikmesi” ve “hücre eksikliği (jitter)” ile ilgilenmelidir. Ancak bu parametreler içinde “hücre kaybı” öncelikli olarak ele alınması gerektiğinden diğer parametreler bu çalışmanın kapsamında olmayacaktır.


    Homojen olan ATM kategorisinde her VC için bir hücre kaybı limiti vardır. VC’lerin hiçbiri bu  limitini geçemez (, 10-6 ile 10-9 arası bir değerdir). Alternatif rota kullanılarak gerçekleştirilen iletimde hücre kaybı ancak iki aynı VP’nin girdi kuyruklamasında gerçekleşebilir. VP’ler içindeki veri akışı esnasında hücre kaybı yaşanmaz.
    Yönlendirme algoritmalarına geçmeden önce bazı tanımlar yapılması gerekmektedir. j.’nci rota olan VPj’nin içinde adet VC olduğu düşünülürse, Pj() bize, VPj’nin girişinde olacak hücre kaybı olasılığını belirtir. Eğer VC tek bir VPj üzerinden geçiş yapıyorsa VCj olarak tanımlar. Eğer i ve j VP’leri üzerinden geçiyorsa VCij olarak tanımlanır ve,[3]
    P(VCij üzerindeki hücre kaybı | i,j)  Pi(i) + Pj(j) (2)
    Bu formül, bize i adet ve j adet VCij’nin üzerinde meydana gelerek hücre kaybı oranının, en fazla i.’nci ve j.’nci VP’lerin girdi kuyruklarında meydana gelecek hücre kaybı oranına eşit olacağını teorik olarak ifade eder.
    Pi(i) + Pj(j)   (3)
    Yukarıdaki formülde de VP’ler de meydana gelen toplam hücre kaybının asla  değerini aşamayacağı belirtilmiş olup aşağıdaki gibi ifade edilebilir. Yani i.’nci ve j.’nci VP’ler de oluşacak toplam hücre kaybı o VP için tanımlanan  değerini geçemez[3],
    P(VCij üzerindeki hücre kaybı | i,j)   (4)
    Bu tanımlardan yola çıkarak yönlendirme de QOS ve TR değerleri ile ilgili olan durumların deterministik kurallarını betimlemek gerekir.

    Direkt Rota için (VPj) QOS-Permissible Koşulları
    İki anahtar arası kurulan direkt rotada yönlendirme için, servis koşullarından hücre kaybı referans olarak alınır[3].

    • madde 1:

    Pi(i+1)   (5)
    Bu madde, VPj içine fazladan bir VC eklense bile (formül 3.’te 1 ile ifade edilmiştir) yine de j.ci VP’nin hücre kaybının  değerini aşmayacağını belirtir.


    • madde 2:

    Her bir k.cı VP için (VPk) üzerinden VCjk’lar kurulu olduğu düşünülürse,
    Pi(i+1) + Pk(k)   (6)
    Bu madde iki anahtar arasında kurulan direkt rotalar ile bu noktalar arasından geçen alternatif rotaların sahip oldukları toplam hücre kaybı oranının yine  değerini geçemeyeceğini vurgular.

    Alternatif Rota için (VPij) QOS-Permissible Koşulları
    İki anahtar arası kurulan “alternatif rotalar” en az sayıda VP’den oluşmaktadır. Bu çalışma kapsamında alternatif rotalar, teorik alt yapının kolay açıklanabilmesi açısından 2’li VP’ler şeklinde ele alınmıştır[3].

    • madde 1:

    Pi(i+1) + Pj(j+1)   (7)
    Bu madde, iki ayrı VP için (1 adet fazla VC eklenmesi durumu da göz önünde tutularak) tanımlanan hücre kaybı oranlarının toplamının  değerini geçemeyeceğini belirtir.


    • madde 2:

    Her bir VPk üzerinden VCik geçtiği ve yine her bir VPk üzerinden VCjk geçtiği düşünülürse,
    Pi(i+1) + Pk(k)   ve Pj(j+1) + Pk(k)   (8)
    Bu madde ile yine  değeri limit olarak tutulmuştur. Alternatif rotada çakışmalar ve VC eklemeleri ile meydana gelebilecek durumlar da formülde kapsam altına alınmıştır.


    Alternatif Rota için (VPij) TR-Permissible Koşulları
    Yönlendirmede QOS değeri olarak uygun bir alternatif (en az ikili VP) rota bulunsa dahi direkt rota tercih sebebidir. Çünkü alternatif rota her zaman ağ kaynaklarının daha fazla kullanımı demektir. Bu sebeple alternatif rotaya doğru oluşacak bir yönlendirmeyi engelleyici olması açısından yeni bir hücre kaybı limiti tanımlanır; =/2. Bu bağlamda TR değeri açısından bir alternatif rotanın kullanılabilir olup olmadığı şu koşulla ifade edilir[3];
    Pi(i+1)   ve Pj(j+1)   (9)

    Yeni alternatif rota da her bir VPi ,VPj rotalarının hücre kaybı oranları  limitinin altında tutulmalıdır. Ancak böyle olursa alternatif rota tercih edilebilir.


    Tüm yukarıdaki tanımlar temel alınarak Homojen ve İstatistiksel çoklanmış ATM ağı kategorisi için üç adet yönlendirme algoritması geliştirilmiştir. Her üçünde de ortak paydalar olarak şunlar görülmektedir;

    • Eğer direkt rota “QOS-permissible” ise VC bu direkt rota üzerinde kurulur.

    • Eğer direkt rota uygun değilse hem “QOS-permissible” hem de “TR-permissible” olan bir alternatif rota kullanılır.

    Bu üç algoritma, alternatif rotayı; uygun olan bir rotalar kümesi içinden seçerken kullandığı seçim yaklaşımlarıyla birbirlerinden ayrılır.



    2.1. U-LLR (“Unrestricted Least Loaded Routing”)

    Öncelikle alternatif rotanın yükünü belirlemek gerekir. Bir VC kurulması sırasında üzerinden geçeceği i ve j VP’leri mutlaka TR-permissible değeri açısından uygun olmalıdır. Bu sadece 9 nolu formülün sağlanması ile mümkün olabilir. Öyleyse VPi ve VPj’den oluşan “R” rotası (R={i,j}) yükü doğal olarak şöyle tanımlanır[3];


    LoadTR(R)=max{ Pi(i+1) , Pj(j+1) } (10)

    U-LLR algoritması “QOS-permissible” olan bir set içinden en uygun “TR-permissible” ve LoadTR(R) değeri en küçük olan rotayı seçer. Bir başka ifadeyle, hücre kaybı oranı için tahminlenen en yüksek kayıp oranına sahip rotaların en düşük değerli olanı seçilir. Bu sayede ağ içinde veri akışı QOS açısından kontrollü olarak güvence altına alınır.


    U-LLR’nin algoritması ise[7];

    1. Öncelikle, direkt rota eğer “QOS-permissible” ise VC’yi bunun üzerinde kurmaya çalış. Eğer değilse, 2.ci adıma geç.

    2. Diyelimki, hem QOS hem de TR değerleri açısından uygun olan rotalar bir  kümesi teşkil etmiş olsun. Eğer  boş ise VC kurulması iptal edilir. Değilse VC,  içindeki en küçük LoadTR(R) değerine sahip olan rota üzerinden kurulur.

    2.2. R-LLR (“Restricted Least Loaded Routing”)

    Bu algoritma U-LLR’de göz ardı edilen kurulamayan VC’lerin sayısını, azaltmayı hedefler. Bir başka deyişle mümkün olduğunca VC kurulması sağlanır ve VC iptal edilme sayısı indirgenmeye çalışılır.


    Burada direkt rota (VPi) için belirlenen “QOS-permissible” değeri aşağıdaki 11 nolu formül ile değişime uğrar ve “sınırlandırılmış QOS-permissible” değeri haline dönüştürülür[3].
    Pj(j+1)  /2 (11)

    Böylece yönlendirme algoritması eğer direkt rotayı “sınırlandırılmış QOS-permissible” değeri açısından uygun bulursa, VC’yi kurar. Alternatif rota ise “TR-permissible” kuralına uygunluk varsa kurulur. Böylelikle VP üzerinde hücre kaybı oranı hiçbir zaman /2 limitini geçmemiş olur. Bu ise hücre kaybı oranının sürekli  limiti altında olması anlamını taşır ve QOS kalitesi garanti altına alınmış demektir.

    R-LLR’nin algoritması ise[7];


    1. Öncelikle, direkt rota eğer “sınırlandırılmış QOS-permissible” ise VC’yi bunun üzerinde kurmaya çalış. Eğer değilse, 2.ci adıma geç.

    2. Alternatif olan R rotasını, LoadTR(R) değeri en küçük olan rota olarak seç. Eğer R, “TR-permissible” ise VC’yi kur. Değilse VC’yi iptal et.



    2.3. P-LLR (“Partially Least Loaded Routing”)

    Bu algoritma R-LLR’a bir alternatif olarak düşünülmüştür. Temelinde şu prensip yatmaktadır; eğer VPj

    üzerinden geçen alternatif bir rota daha önceden tanımlanmışsa, o zaman VPj direkt rotası “kısmi QOS-permissible” olarak tanımlanır ve[3],
    Pj(j+1)  /2 (12)

    olarak ele alınır. Eğer önceden hiçbir alternatif rota VPj üzerinde tanımlı değilse o zaman direkt rotanın hücre kaybı oranı 13 nolu formüldeki gibi belirtilir.


    Pj(j+1)   (13)

    Eğer yönlendirme algoritması direkt rotalar için VC’leri “kısmi QOS-permissible” rotalar üzerinde ya da alternatif rotalar için VC’leri “TR-permissible” rotalar üzerinde /2 değerini geçmemiş olacaktır. Bu ise gereken QOS kalitesinin sağlanması anlamına gelir.


    P-LLR’nin algoritması ise[7];

    1. Öncelikle VC’yi direkt rota eğer “kısmi QOS-permissible” ise bunun üzerinde kurmaya çalış. Eğer değilse, 2.ci adıma geç.

    2. “TR-permissible” olan rotalardan  kümesini oluştur. Ve bu kümedeki her bir VP çifti için önceden kurulmuş olan en az bir alternatif rota elde et. VC’yi bunlar arasından en düşük LoadTR(R) değerine sahip olan rota üzerinde kur. Eğer  kümesi boş ise 3.cü adıma geç.

    3. R ile isimlendireceğin alternatif bir rota bul. Bu rotanın LoadTR(R) değeri küçük olmalı. Eğer R, “TR-permissible” ise VC’yi kur değilse VC’yi reddet.

    Bu algoritma kurulmak istenen VC’lerin başarıyla kurulma olasılığını yükseltmektedir. Böylece VC reddetme sayısı düşer.


    Bu üç algoritmayı kısaca karşılaştıracak olursak[3][5],

    • U-LLR algoritması daha basit ve diğerlerine göre uygulanabilirliği kolay olan bir algoritmadır.

    • R-LLR, U-LLR’de karşılaşılan hücre kaybı oranını  seviyesinden /2 seviyesine çekerek alternatif rotaların daha etkin kullanımını sağlamaktadır.

    • R-LLR’de U-LLR’e göre VC kurulumu ihtimali daha yüksektir.

    • P-LLR algoritması, R-LLR ve U-LLR’e göre daha karmaşık bir algoritmadır.

    • P-LLR algoritması VC kurulum ihtimalinin en yüksek olduğu algoritmadır.

    • VC’lerin kurulum performansı açısından bir kıyaslama yapılırsa,

    U_LLR < P_LLR < R_LLR

    • Algoritmaların karmaşıklık göstergeleri ise[8];

    OU_LLR (N2) , OR_LLR (N), OP_LLR (N)


    3. Heterojen ve İstatistiksel Çoklama Yöntemi Kullanmayan ATM Kategorisi için Yönlendirme Algoritması

    Bu kategori altında ele alınan ATM ağında yönlendirme için önem taşıyan prensipler şunlardır; VC’ler için belirlenen band genişliği “peak rate” olarak bilinen en yüksek değere göre yapılandırılır. Ancak her bir VC’nin en yüksek değeri bir diğer VC’den farklı olacağı da gözardı edilemez. Bu tip bir konfigürasyon için VC’ler için tanımlanmış bir sabit iletim oranları yoktur[6].


    VC’lerin band genişlikleri için farklı değerlerin kullanıldığı “multirate traffic” ortamında yönlendirme oldukça zordur. Bu yüzden yönlendirme tüm ağın geneline yayılmış bir durumdadır böylece yönlendirme için her bir düğüm çifti arasındaki band genişliği atamaları mevcuttur. Bunun yanısıra, dar band genişliğine sahip olan VC’leri belli rotalar için bir araya getirmek suretiyle (“packing”) yönlendirilme sağlanmaktadır[9]. Böylece beklenmeyen geniş band gereksinimli çağrı istekleri için hazırda tutulan bir kapasite ayrılmış olacaktır. Örneğin, “packing” şu tip durumlar için kaçınılmaz bir çözüm olabilir;

    1. Tüm VP’ler aynı band genişliğine sahipse.

    2. İki servis sınıfını destekliyorsa – bu servis sınıflarından ilkinde “peak rate” en yüksek değer VP’nin band genişliğine eşittir, diğer servis sınıfında ise “peak rate” en yüksek değer VP’nin band genişliğinin sadece bir kısmını oluşturmaktadır-.

    Bir diğer önemli kavram ise korumadır (“protect”). Koruma ile belirtilen bir servisin başka bir servis tarafından müdahale görmemesidir. Bir diğer deyişle, eğer bir servis, ağı tekil biçimde hakimiyetine almaya başlıyorsa, onun yönetimine kısıtlama koymak gerekmektedir.


    Burada bahsi geçen ATM kategorisi için sunulacak yönlendirme algoritması LLR algoritmasının çoklu band genişliğine(“multirate”) yönelik bir başka sürümü olarak görülebilir. Bu algoritma için bazı notasyonların tanımlanması gerekmektedir. Cj, VPj için iletim oranı olarak tanımlanmıştır. VC’lerin yönlendirilmesi için, her bir VPj üzerinde en yüksek değer(“peak rate”) belirlenmiş olup bu b olarak gösterilir ve şu kurala uygun olmak zorundadır; 0 < b  Cj . Bu yönlendirmede istatistiksel çoklama olmadığı için şunu kesin bir biçimde söylemek mümkündür; tüm VC’lerin “peak rate” değerlerini topladığımızda elde ettiğimiz Bj değeri herbir VPj için Bj  Cj şeklinde olmak zorundadır. Bu tanımlar ışığı altında herbir b ve VPj deperi için rj(b) “trunk reservation” değeri olarak belirtilir. Bunun yanısıra {j,k} rotalarını içeren bir yönlendirmede “olabilirlik” şu şekilde formüle edilebilir[3];
    Olabilirlik(j,k) = min{ (Cj-Bj-ri(b)) , (Ck-Bk-rk(b)) } (14)
    Multirate -LLR’nin algoritması ise[7];

    1. Öncelikle VC’yi direkt rota eğer Bi + b  Ci kuralına uygun ise bunun üzerinde kurmaya çalış. Eğer değilse, 2.ci adıma geç.

    2. Olabilirlik(j,k) değerini maksimize eden bir {j,k} rotası bul. Eğer bulduğun Olabilirlik(j,k) değeri b değerine eşit ya dalüçük ise VC’yi bu rota üzerine kur. Değilse VC isteğini iptal et.

    4. Sonuç

    ATM teknolojisi için belirtilen dört kategori için ele alınacak yönlendirme algoritmalarına dikkat edilecek olunursa, homojen ve istatistiksel çoklama kullanmayan ATM ağlarında normal telefon hatları için kullanılan yönlendirme algoritmaları geçerliliğini korumaktadır[3]. Ancak homojen olup istatistiksel çoklama kullanan ATM ağları için ise bu çalışmada sunulan üç algoritma (U_LLR, R_LLR, P_LLR) yönlendirme için alternatif çözümlerdir. Ve diğer ATM kategorileri içinde yine LLR taban algoritmasının değişik uyarlamaları söz konusudur.


    ATM ağlarında kullanılacak yönlendirme algoritmalarının herbiri maliyet, performans ve çağrı üzerine VC kurulumundaki başarı oranı ile birbirlerinden ayrılmaktadır. Tüm bu etmenlerin QOS adını verdiğimiz servis kalitesi için önemli kriterler oldukları gözardı edilmemelidir. Yukarıda bahsi geçen üç ana LLR algoritmasından en çekici olanı, R_LLR’dir. Çünkü çağrı istemi geldiğinde VC kurma ihtimali en yüksek olan algoritma olması önemli özelliğidir.
    ATM ağlarındaki yönlendirme algoritmalarının titizlikle ele alınmasıyla elde edilebilecek iyi bir yönlendirme stratejisi yardımıyla, ATM ağlarının performansından en iyi biçimde yararlanabilmek mümkün olacaktır. “Videoconferencing” ve “multimedia” uygulamaları için referans olarak gösterilen ATM ağları, yönlendirme algoritmaları yardımıyla da daha etkin çözümler sağlayacaktır[1][9].


    5. Kaynakça





    1. Dutton Harry J.R., Lenhard P., “Asynchronous Transfer Mode (ATM) Technical Overview”, Second Edition, Prentice Hall Inc., 1995, p:2-1;2-8

    2. Dodd Anabel Z., “The Essential Guide to Telecommunications”, Prentice Hall Inc., 1998, p.159-160, ISBN: 0-13-259011-5

    3. Steenstrup M., “Routing in Communications Networks”,Prentice Hall Inc., 1995, p.49-60,

    ISBN:0-13-010752-2

    1. Black U., “ATM Volume-II”, Prentice Hall Inc., 1998, p.113-130, ISBN: 0-13-571837-6

    2. Gelber S., “Data Communications Today”, Second Edition, Prentice Hall Inc., 1997, p.119-120,

    ISBN: 0-13-755950-X

    1. Hiramatsu A., “ATM Traffic Control Using Neural Networks”, Neural Networks in Telecommunications Magazine,Boston,Kluwer Academic,1994, p.63-89

    2. Farnk H., Chou W., “Routing in Computer Networks”, Networks, Vol.1,1971,p:99-122

    3. Torrieri D., “Algorithms for Finding an Optimal Set of Short Disjoint Paths in Communications Network”, IEEE Transaction on Communications, Vol.40, No:11, November 1992,p:1698-1702

    1. Neves J., Leito Mario J., Almeida L.B., “Neural Networks in B-ISDN Flow Control: ATM Traffic Prediction or Network Modeling?”, IEEE Communication Magazine, October 1995,p:50-56.









        Ana sayfa


    Atm ağlarinda yönlendirme

    Indir 58.13 Kb.