Ağı kapat - Clos network

Nın alanında telekomünikasyon, bir Ağı kapat bir çeşit çok aşamalı devre anahtarlama pratik, çok aşamalı anahtarlama sistemlerinin teorik idealizasyonunu temsil eden ağ. Edson Erwin tarafından icat edildi^[1] 1938'de ve ilk olarak Charles Clos (Fransızca telaffuz:[ʃaʁl klo])^[2]1952'de.

Bir Clos ağı, aşamalar ekleyerek, büyük bir bölüm oluşturmak için gereken çapraz nokta sayısını çapraz çubuk anahtarı. Bir Clos ağ topolojisi (aşağıda diyagramı gösterilmiştir) üç tamsayı ile parametrelendirilir n, m, ve r: n her birini besleyen kaynakların sayısını temsil eder r giriş aşaması çapraz çubuk anahtarları; her giriş aşaması çapraz çubuk anahtarında m çıkışlar; ve var m orta kademe çapraz çubuk anahtarları.

Devre anahtarlama, bağlantı süresi boyunca uç noktalar arasındaki bir bağlantı için özel bir iletişim yolu düzenler. Bu, adanmış bağlantılar yetersiz kullanılırsa mevcut toplam bant genişliğinden ödün verir, ancak bağlantıyı ve bant genişliğini daha öngörülebilir hale getirir ve modernde olduğu gibi, her paket işlendiğinde değil, yalnızca bağlantılar başlatıldığında kontrol ek yükü getirir. paket anahtarlamalı ağlar.

Clos ağı ilk tasarlandığında, çapraz nokta sayısı, anahtarlama sisteminin toplam maliyetinin iyi bir tahminiydi. Bu, elektromekanik çapraz çubuklar için önemliyken, gelişiyle daha az alakalı hale geldi. VLSI burada ara bağlantılar ya doğrudan silikon içinde ya da nispeten küçük bir pano kümesi içinde uygulanabilir. Her biri fiber optik bağlantılara dayanan çok büyük ara bağlantı yapılarına sahip karmaşık veri merkezlerinin ortaya çıkmasıyla, Clos ağları yeniden önem kazandı.^[3] Clos ağının bir alt türü olan Beneš ağı da yakın zamanda makine öğrenme.^[4]

Topoloji

Yakın ağların üç aşaması vardır: giriş aşaması, orta aşama ve çıkış aşaması. Her aşama, genellikle sadece adı verilen bir dizi çapraz çubuk anahtarından (aşağıdaki şemaya bakın) oluşur. çapraz çubuklar. Ağ, aşamalar arasında r-yönlü mükemmel bir karıştırma uygular. Bir giriş çapraz çubuğu anahtarına giren her çağrı, mevcut orta kademe çapraz çubuk anahtarlarından herhangi biri aracılığıyla ilgili çıkış çapraz çubuğu anahtarına yönlendirilebilir. Hem giriş anahtarını orta kademe anahtarına bağlayan bağlantı hem de orta kademe anahtarını çıkış anahtarına bağlayan bağlantı boşsa, belirli bir yeni arama için bir orta kademe çapraz çubuğu mevcuttur.

Kapalı ağlar üç tam sayı ile tanımlanır n, m, ve r. n her birini besleyen kaynakların sayısını temsil eder r giriş aşaması çapraz çubuk anahtarları. Her giriş aşaması çapraz çubuk anahtarında m çıkışlar ve var m orta kademe çapraz çubuk anahtarları. Her giriş aşaması anahtarı ve her orta aşama anahtarı arasında tam olarak bir bağlantı vardır. Var r çıkış aşaması anahtarları, her biri m girişler ve n çıktılar. Her bir orta kademe anahtarı, her bir çıkış aşaması anahtarına tam olarak bir kez bağlanır. Böylece giriş aşamasında r her birinde bulunan anahtarlar n girişler ve m çıktılar. Orta aşamada m her birinde bulunan anahtarlar r girişler ve r çıktılar. Çıkış aşamasında r her birinde bulunan anahtarlar m girişler ve n çıktılar.

Engelleme özellikleri

Göreceli değerleri m ve n Clos ağının engelleme özelliklerini tanımlar.

Katı anlamda engellemesiz Kapalı ağlar (m ≥ 2n−1): orijinal 1953 Kapanış sonucu

Eğer m ≥ 2n−1, Clos ağ kesin anlamda engellemesizbir giriş anahtarındaki kullanılmayan bir girişin her zaman bir çıkış anahtarındaki kullanılmayan bir çıkışa bağlanabileceği anlamına gelir, mevcut çağrıları yeniden düzenlemek zorunda kalmadan. Clos'un klasik 1953 makalesinin temelini oluşturan sonuç budur. Bir giriş anahtarının girişinde boş bir terminal olduğunu ve bunun belirli bir çıkış anahtarındaki boş bir terminale bağlanması gerektiğini varsayalım. En kötü durumda, n− Söz konusu giriş anahtarında 1 başka çağrı etkin ve n− Söz konusu çıkış anahtarında 1 başka arama etkin. En kötü durumda, bu çağrıların her birinin farklı bir orta aşama anahtarından geçtiğini varsayalım. Dolayısıyla en kötü durumda, 2nOrta aşama anahtarlarının −2'si yeni çağrıyı taşıyamaz. Bu nedenle, tam anlamıyla engellemesiz çalışmayı sağlamak için, başka bir orta kademe anahtarı gerekir ve toplamda 2n−1.

Yeniden düzenlenebilir şekilde engellenmeyen Kapalı ağlar (m ≥ n)

Eğer m ≥ nClos ağı yeniden düzenlenebilir şekilde engellenemezBu, bir giriş anahtarındaki kullanılmayan bir girişin her zaman bir çıkış anahtarındaki kullanılmayan bir çıkışa bağlanabileceği anlamına gelir, ancak bunun gerçekleşmesi için, mevcut çağrıların Clos ağındaki farklı orta kademe anahtarlarına atanarak yeniden düzenlenmesi gerekebilir.^[5] Bunu kanıtlamak için dikkate almak yeterlidir m = nClos ağından tam olarak yararlanıldığında; yani, r×n devam eden aramalar. Kanıt, bunların herhangi bir permütasyonunun nasıl olduğunu gösterir r×n giriş terminalleri üzerine r×n çıkış terminalleri daha küçük permütasyonlara bölünebilir ve bunların her biri, bir Clos ağındaki bireysel çapraz çubuk anahtarları tarafından uygulanabilir. m = n.

Kanıt kullanır Hall'un evlilik teoremi^[6] Bu isim genellikle aşağıdaki şekilde açıklandığı için verilmiştir. Varsayalım ki r erkekler ve r kızlar. Teorem, her alt kümesinin k erkekler (her biri için k öyle ki 0 ≤ k ≤ r) aralarında biliyorum k veya daha fazla kız olursa, her erkek tanıdığı bir kızla eşleştirilebilir. Eşleşmenin gerçekleşmesi için bunun gerekli bir koşul olduğu açıktır; şaşırtıcı olan, yeterli olmasıdır.

Bir Clos ağı bağlamında, her erkek çocuk bir giriş anahtarını temsil eder ve her kız bir çıkış anahtarını temsil eder. İlgili giriş ve çıkış anahtarları aynı aramayı taşıyorsa, bir oğlanın bir kızı tanıdığı söylenir. Her bir set k erkekler en azından bilmeli k kızlar çünkü k giriş anahtarları taşıyor k×n aramalar ve bunlar en az k çıkış anahtarları. Bu nedenle, her bir giriş anahtarı, bire bir eşleştirme yoluyla aynı aramayı taşıyan bir çıkış anahtarı ile eşleştirilebilir. Bunlar r aramalar bir orta kademe anahtarı ile taşınabilir. Bu orta aşama anahtarı şimdi Clos ağından kaldırılırsa, m 1 azaldı ve daha küçük bir Clos ağımız kaldı. İşlem daha sonra kendini tekrar eder m = 1 ve her çağrı bir orta aşama anahtarına atanır.

Engelleme olasılıkları: Lee ve Jacobaeus yaklaşımları

Gerçek telefon anahtarlama sistemleri, maliyet nedenlerinden dolayı nadiren katı anlamda engelleme yapmazlar ve Lee tarafından değerlendirilebilecek küçük bir engelleme olasılığına sahiptirler. Jacobaeus yaklaşımlar,^[7] mevcut çağrıların yeniden düzenlenmediğini varsayarsak. Burada, her giriş veya çıkış anahtarındaki diğer etkin çağrıların potansiyel sayısı sen = n−1.

Lee yaklaşımında, aşamalar arasındaki her dahili bağlantının belirli bir olasılığa sahip bir çağrı tarafından zaten meşgul olduğu varsayılır. pve bunun farklı bağlantılar arasında tamamen bağımsız olduğunu. Bu, özellikle küçükler için engelleme olasılığını olduğundan fazla tahmin eder. r. Belirli bir dahili bağlantının meşgul olma olasılığı p = uq/m, nerede q bir giriş veya çıkış bağlantısının meşgul olma olasılığıdır. Tersine, bir bağlantının ücretsiz olma olasılığı 1−p. Bir giriş anahtarını belirli bir orta kademe anahtarı aracılığıyla bir çıkış anahtarına bağlayan yolun serbest olma olasılığı, her iki bağlantının da serbest olma olasılığıdır (1−p)². Dolayısıyla mevcut olmama olasılığı 1− (1−p)² = 2p−p². Engelleme olasılığı veya böyle bir yolun serbest olmaması olasılığı [1− (1−p)²]^m.

Jacobaeus yaklaşımı daha doğrudur ve nasıl türetildiğini görmek için, Clos ağına (giriş çağrıları) giren çağrıların bazı özel eşlemelerinin orta aşama anahtarlarında zaten mevcut olduğunu varsayalım. Bu, yalnızca akraba giriş anahtarı ve çıkış anahtarlarının konfigürasyonları önemlidir. Var ben Bağlanacak boş giriş terminali ile aynı giriş anahtarı üzerinden giren giriş çağrıları ve j Bağlanacak serbest çıkış terminali ile aynı çıkış anahtarı üzerinden Clos ağdan ayrılan çağrılar (çıkış çağrıları). Dolayısıyla 0 ≤ ben ≤ senve 0 ≤ j ≤ sen.

İzin Vermek Bir atama yöntemlerinin sayısı olabilir j çıkış çağrıları m orta kademe anahtarları. İzin Vermek B engellemeye neden olan bu atamaların sayısı olabilir. Bu, kalan davaların sayısıdır. m−j orta kademe anahtarları ile çakışır m−j of ben içeren alt kümelerin sayısı olan giriş çağrıları m−j bu aramalardan. O zaman engelleme olasılığı:

${displaystyle eta _ {ij} = {frac {B} {A}} = {frac {left ({egin {dizi} {c} i m-jend {dizi}} ight)} {sol ({egin {dizi } {c} m jend {dizi}} sağ)}} = {frac {i! j!} {(i + jm)! m!}}}$

Eğer f_ben olasılığı ben diğer çağrılar giriş anahtarında zaten etkindir ve g_j olasılık j diğer çağrılar çıkış anahtarında zaten etkindir, genel engelleme olasılığı:

${displaystyle P_ {B} = toplam _ {i = 0} ^ {u} toplam _ {j = 0} ^ {u} f_ {i} g_ {j} eta _ {ij}}$

Bu ile değerlendirilebilir f_ben ve g_j her biri bir ile gösterilir Binom dağılımı. Önemli bir cebirsel işlemden sonra, bu şu şekilde yazılabilir:

${displaystyle P_ {B} = {frac {(u!) ^ {2} (2-p) ^ {2u-m} p ^ {m}} {m! (2u-m)!}}}$

Üç aşamadan fazla ağları kapatın

Yakın ağlar, herhangi bir tek sayıda aşamaya da genelleştirilebilir. Her bir orta kademe çapraz çubuk anahtarının 3 aşamalı bir Clos ağ ile değiştirilmesiyle, beş aşamalı Clos ağlar oluşturulabilir. Aynı işlemi tekrar tekrar uygulayarak 7, 9, 11, ... aşamaları mümkündür.

Beneš ağı (m = n = 2)

Bu türden, yeniden düzenlenebilir şekilde engellemeyen bir ağ m = n = 2 genellikle a olarak adlandırılır Beneš ağı, daha önce başkaları tarafından tartışılmış ve analiz edilmiş olsa da Václav E. Beneš. Giriş ve çıkışların sayısı N = r×n = 2r. Bu tür ağların 2 günlüğü vardır₂N - Her biri içeren 1 aşama N/ 2 2 × 2 çapraz çubuk anahtarı ve toplam N günlük₂N − N/ 2 2 × 2 çapraz çubuk anahtarı. Örneğin, 8 × 8 Beneš ağı (ör. N = 8) aşağıda gösterilmiştir; 2 günlüğü var₂8 - 1 = 5 aşama, her biri N/ 2 = 4 2 × 2 çapraz çubuk anahtarı ve toplamda N günlük₂N − N/ 2 = 20 2 × 2 çapraz çubuk anahtarı. Merkezi üç aşama, iki küçük 4 × 4 Beneš ağından oluşurken, orta aşamada her 2 × 2 çapraz çubuk anahtarının kendisi 2 × 2 Beneš ağı olarak kabul edilebilir. Bu örnek, bu nedenle, bu tür bir ağın özyinelemeli inşasını vurgulamaktadır.

Ayrıca bakınız

• Çapraz çubuk anahtarı Bir Clos ağının anahtarlama elemanını açıklar.
• Engellemesiz minimum kapsama anahtarı Bir Clos ağın anahtarlama algoritmasını açıklar.
• Banyan anahtarı Ağları bağlamanın alternatif bir yolu.
• Şişman ağaç Ağları bağlamanın alternatif bir yolu.
• Omega ağı Ağları bağlamanın alternatif bir yolu.

Referanslar