Engellemesiz minimum kapsama anahtarı - Nonblocking minimal spanning switch
Bir tıkanmasızdır asgari karış anahtarı herhangi bir kombinasyon halinde, N çıkışlarına K giriş bağlanabilir bir cihazdır. Bu türden anahtarların en bilinen kullanımı telefon santralidir . "Engellemesiz" terimi, kusurlu değilse, her zaman bağlantı kurabileceği anlamına gelir. "Minimum" terimi, mümkün olan en az bileşene ve dolayısıyla minimum masrafa sahip olduğu anlamına gelir.
Tarihsel olarak, telefon anahtarlarında, arayanlar arasındaki bağlantılar büyük, pahalı elektromekanik röleler , Strowger anahtarları ile düzenleniyordu . Strowger anahtarlarının temel matematiksel özelliği, anahtara yapılan her giriş için tam olarak bir çıkış olmasıdır. Matematiksel anahtarlama devresi teorisinin çoğu, bir giriş kombinasyonunu bir çıkış kombinasyonuna bağlamak için gereken toplam anahtar sayısını azaltmak için bu özelliği kullanmaya çalışır.
1940'larda ve 1950'lerde, Bell Laboratories'deki mühendisler, bir telefon santrali uygulamak için gereken " anahtarlı yapının" boyutunu ve masrafını azaltmak için yöntemler üzerine geniş bir matematiksel araştırma serisine başladılar . Erken, başarılı matematiksel analiz, Charles Clos ile gerçekleştirilmiştir bir ( : Fransız kaydedin [ʃaʁl klo] daha küçük anahtarlarının inşa) ve bir anahtarlama kumaş denir Clos ağ .
Arka plan: topolojileri değiştirme
Çapraz çubuk anahtarı
Çapraz çubuk anahtarı bir N çıkışlarına K girişlerini bağlamak mümkün olma özelliğine sahip bir bire bir herhangi bir meşgul olmayan alıcı, teknik açıklaması "tıkanmasızdır" verilen bir özelliğe bir arayan bağlanabilir, böylece kombinasyon. Engelsiz olduğundan, her zaman bir aramayı tamamlayabilir (meşgul olmayan bir alıcıya), bu da hizmet kullanılabilirliğini en üst düzeye çıkarır.
Bununla birlikte, çapraz çubuk anahtarı bunu N 2 (N kare) basit SPST anahtarları kullanma pahasına yapar . Büyük N (ve bir telefon anahtarının pratik gereksinimleri büyük kabul edilir) için bu büyüme çok pahalıydı. Dahası, büyük çapraz çubuk anahtarlarının fiziksel sorunları vardı. Anahtar sadece çok fazla alana ihtiyaç duymakla kalmadı, anahtar kontaklarını içeren metal çubuklar o kadar uzar ki sarkacak ve güvenilmez hale gelecektir. Mühendisler ayrıca, herhangi bir zamanda, bir çapraz çubuk anahtarının her bir çubuğunun yalnızca tek bir bağlantı yaptığını fark ettiler. İki çubuktaki diğer kontaklar kullanılmamıştı. Bu, bir çapraz çubuk anahtarının anahtarlama yapısının çoğunun boşa gittiği anlamına geliyordu.
Bir çapraz çubuk anahtarı taklit etmenin açık yolu, onu daha küçük çapraz çubuk anahtarlarından inşa etmenin bir yolunu bulmaktı. Bir çapraz çubuk anahtarı, daha küçük çapraz çubuk anahtarlarının bazı düzenlemeleri ile taklit edilebiliyorsa, bu daha küçük çapraz çubuk anahtarları da daha küçük çapraz çubuk anahtarları tarafından taklit edilebilir. Anahtarlama yapısı çok verimli hale gelebilir ve muhtemelen standartlaştırılmış parçalardan bile oluşturulabilir. Buna Clos ağı denir .
Tamamen bağlı 3 katmanlı anahtarlar
Bir sonraki yaklaşım, çapraz çubuk anahtarını daha küçük çapraz çubuk anahtarlarının üç katmanına ayırmaktı. Bir "giriş katmanı", bir "orta katman" ve bir "çıktı katmanı" olacaktır. Daha küçük anahtarlar daha az büyüktür, daha güvenilirdir ve genellikle yapımı daha kolaydır ve bu nedenle daha ucuzdur.
Bir telefon sistemi yalnızca bire bir bağlantı kurmalıdır. Sezgisel olarak bu, her alt anahtarda girdi sayısının ve çıktı sayısının her zaman eşit olabileceği anlamına gelir, ancak sezgi bunun yapılabileceğini kanıtlamaz ve bize bunu nasıl yapacağımızı da söylemez. 16'ya 16 çapraz çubuk anahtarı sentezlemek istediğimizi varsayalım. Tasarım, toplam 16 giriş için giriş tarafında her biri 4 girişe sahip 4 alt anahtara sahip olabilir. Ayrıca, çıkış tarafında, toplam 16 çıkış için her biri 4 çıkışlı 4 çıkış alt anahtarımız da olabilir. Tasarımın mümkün olduğunca az kablo kullanması arzu edilir, çünkü kablolar gerçek paraya mal olur. İki alt anahtarı bağlayabilen mümkün olan en az kablo sayısı tek bir kablodur. Bu nedenle, her giriş alt anahtarının her bir orta alt anahtara tek bir kablosu olacaktır. Ayrıca, her bir orta alt anahtarın her bir çıkış alt anahtarına tek bir kablosu olacaktır.
Soru, kaç tane orta alt anahtara ihtiyaç duyulduğu ve bu nedenle, giriş katmanını orta katmana toplam kaç kablo bağlaması gerektiğidir. Telefon anahtarları simetrik olduğundan (arayanlar ve arananlar birbirinin yerine kullanılabilir), aynı mantık çıkış katmanına uygulanacak ve orta alt anahtarlar, çıkışlarla aynı sayıda girişe sahip "kare" olacaktır.
Ortadaki alt anahtarların sayısı, bunlara bağlantı tahsis etmek için kullanılan algoritmaya bağlıdır. Üç katmanlı bir anahtarı yönetmek için temel algoritma, gerekli giriş ve çıkış anahtarlarına giden kullanılmamış kablolara sahip bir orta alt anahtar için orta alt anahtarları aramaktır. Bağlanabilir bir orta alt anahtar bulunduğunda, giriş ve çıkış anahtarlarındaki doğru giriş ve çıkışlara bağlanmak önemsizdir.
Teorik olarak, örnekte, her biri her bir giriş anahtarına tam olarak bir bağlantı ve her bir çıkış anahtarına bir bağlantı içeren yalnızca dört merkezi anahtara ihtiyaç vardır. Buna "minimal yayılma anahtarı" denir ve onu yönetmek Bell Labs'ın araştırmalarının kutsal kasesiydi.
Bununla birlikte, bir kalem ve kağıtla yapılan biraz çalışma, tek bir orta anahtarın hem gerekli giriş anahtarına hem de gerekli çıkış anahtarına bağlantısının olmadığı koşullara bu kadar minimal bir geçiş yapmanın kolay olduğunu gösterecektir. Anahtarın kısmen bloke edilmesi yalnızca dört çağrı alır. Bir giriş anahtarı yarı doluysa, iki orta anahtarla bağlantıları vardır. Bir çıkış anahtarı diğer iki orta anahtardan gelen bağlantılarla birlikte yarı dolu ise, o zaman bu giriş ve çıkış arasında bir yol sağlayabilecek hiçbir orta anahtar kalmaz.
Bu nedenle, dört giriş alt anahtarlı ve dört çıkış anahtarlı 16x16 "basit bağlanmış bloksuz anahtar" anahtarının 7 orta anahtar gerektirdiği düşünüldü; en kötü durumda, neredeyse dolu bir giriş alt anahtarı üç orta anahtar kullanır, neredeyse tam çıkışlı bir alt anahtar üç farklı anahtar kullanır ve yedincinin son bağlantıyı yapmakta özgür olması garanti edilir. Bu nedenle, bazen bu anahtar düzenlemesine "2 n- 1 anahtarı" denir , burada n , giriş alt anahtarlarının giriş portlarının sayısıdır.
Örnek kasıtlı olarak küçüktür ve bu kadar küçük bir örnekte, yeniden düzenleme pek çok anahtarı kurtarmaz. 16 × 16 bir çapraz çubuğun 256 kontağı varken, 16 × 16 minimum kapsama anahtarının 4 × 4 × 4 × 3 = 192 kontağı vardır.
Sayılar büyüdükçe tasarruflar artar. Örneğin, 10.000 hat alışverişi, tam bir çapraz çubuk uygulamak için 100 milyon kişiye ihtiyaç duyacaktır. Ancak 100 100 × 100 alt anahtarın üç katmanı yalnızca 300 10.000 kontak alt anahtarı veya 3 milyon kontak kullanır.
Bu alt anahtarların her biri 3 × 10 10 × 10 çapraz çubuktan, toplam 3000 kontaktan, tüm değişim için 900.000 yapan; bu 100 milyondan çok daha küçük bir sayı.
Minimal bir kapsama anahtarını yönetme
Önemli keşif, yeni bir bağlantının tamamlanabilmesi için orta anahtarlardaki bağlantıları "ticaret kablolarına" yeniden düzenlemenin bir yoluydu.
İlk adım, giriş alt anahtarından bir orta katman alt anahtarına (A olarak adlandıracağız) kullanılmayan bir bağlantı ve istenen çıkış alt anahtarına (B olarak adlandıracağımız) orta katman alt anahtarından kullanılmayan bir bağlantı bulmaktır. Yeni bağlantının gelmesinden önce, giriş ve çıkış alt anahtarlarının her biri en az bir kullanılmamış bağlantıya sahip olduğundan, bu kullanılmayan bağlantıların her ikisi de mevcut olmalıdır.
A ve B aynı orta katman anahtarı olursa, bağlantı "2 n −1" anahtar durumunda olduğu gibi hemen yapılabilir . Bununla birlikte, A ve B farklı orta katman alt anahtarlarıysa, daha fazla çalışma gerekir. Algoritma, mevcut tüm bağlantıları içeren orta subswitches A ve B ile bağlantı yeni bir düzenleme bulur, ayrıca yeni bir bağlantı arzu.
A veya B'den geçen istenen tüm bağlantıların bir listesini yapın, yani, sürdürülecek tüm mevcut bağlantılar ve yeni bağlantı. Algoritma, yalnızca girişten çıkış anahtarına kadar olan dahili bağlantılarla ilgilenir, ancak pratik bir uygulama da doğru giriş ve çıkış anahtarı bağlantılarını takip etmelidir.
Bu listede, her giriş alt anahtarı en fazla iki bağlantıda görünebilir: biri alt anahtar A ve diğeri alt anahtar B'ye. Seçenekler sıfır, bir veya ikidir. Benzer şekilde, her çıkış alt anahtarı en fazla iki bağlantıda görünür.
Her bağlantı, bir bağlantı "zinciri" içinde bir bağlantı oluşturan, paylaşılan bir giriş veya çıkış alt anahtarı ile en fazla iki diğerine bağlanır.
Ardından yeni bağlantıyla başlayın. Buna, giriş alt anahtarından orta alt anahtar A üzerinden çıkış alt anahtarına giden yolu atayın. Bu ilk bağlantının çıkış alt anahtarının ikinci bir bağlantısı varsa, bu ikinci bağlantıya giriş alt anahtarından alt anahtar B'ye kadar bir yol atayın. Bu giriş alt anahtarının başka bir bağlantısı varsa, üçüncü bağlantıya alt anahtar A aracılığıyla bir yol atayın. Bu şekilde ileri geri devam edin. , orta alt anahtarlar A ve B arasında dönüşümlü olarak. Sonunda iki şeyden biri gerçekleşmelidir:
- zincir, yalnızca tek bir bağlantıya sahip bir alt anahtarla sonlanır veya
- zincir, başlangıçta seçilen bağlantıya geri döner.
İlk durumda, yeni bağlantının giriş alt anahtarına geri dönün ve aynı alternatif modeldeki orta alt anahtarlar B ve A aracılığıyla yollara bağlantılar atayarak zincirini geriye doğru izleyin.
Bu yapıldığında, zincirdeki her giriş veya çıkış alt anahtarının içinden geçen en fazla iki bağlantı vardır ve bunlar farklı orta anahtarlara atanır. Böylece, gerekli tüm bağlantılar mevcuttur.
Yeni bağlantı dahil zincirin parçası olmayan alt anahtarlar A ve B aracılığıyla ek bağlantılar olabilir; bu bağlantılar olduğu gibi bırakılabilir.
Yazılımda yeni bağlantı modeli tasarlandıktan sonra, anahtarın elektroniği aslında bağlantıları fiziksel olarak hareket ettirerek yeniden programlanabilir. Elektronik anahtarlar, yeni konfigürasyonun mevcut bağlantıyı bozmadan elektroniklere yazılabilmesi ve ardından tek bir mantık darbesi ile etkili olabilmesi için dahili olarak tasarlanmıştır. Sonuç, bağlantının konuşmada fark edilemeyecek bir kesinti ile anında hareket etmesidir. Daha eski elektromekanik anahtarlarda, bazen bir "anahtarlama gürültüsü" sesi duyulurdu.
Bu algoritma bir topolojik sıralama biçimidir ve minimum kapsama anahtarını kontrol eden algoritmanın kalbidir.
Anahtarların pratik uygulamaları
Algoritma keşfedilir keşfedilmez, Bell sistem mühendisleri ve yöneticileri bunu tartışmaya başladı. Birkaç yıl sonra Bell mühendisleri, kendisi tarafından kontrol edilebilen elektromekanik anahtarlar tasarlamaya başladı. O zamanlar bilgisayarlar tüp kullanıyordu ve bir telefon sistemini kontrol edecek kadar güvenilir değillerdi (telefon sistemi anahtarları güvenlik açısından kritiktir ve yaklaşık otuz yılda bir planlanmamış bir arızaya sahip olacak şekilde tasarlanmıştır). Aktarma tabanlı bilgisayarlar algoritmayı uygulamak için çok yavaştı. Bununla birlikte, tüm sistem, bilgisayarlar yeterince güvenilir olduğunda, mevcut anahtarlama sistemlerine uyarlanabilecek şekilde tasarlanabilir.
Kompozit anahtarları hataya dayanıklı yapmak zor değildir . Bir alt anahtar başarısız olduğunda, arayanlar tekrar ararlar. Bu nedenle, her yeni bağlantıda yazılım, en son piyasaya sürülen bağlantıyı yeniden kullanmak yerine her alt anahtarda bir sonraki ücretsiz bağlantıyı dener. Yeni bağlantının çalışma olasılığı daha yüksektir çünkü farklı devreler kullanır.
Bu nedenle, yoğun bir anahtarda, belirli bir PCB'nin herhangi bir bağlantısı olmadığında, test için mükemmel bir adaydır.
Belirli bir basılı devre kartını test etmek veya hizmetten çıkarmak için iyi bilinen bir algoritma vardır. Kartın alt anahtarından daha az bağlantı geçtikçe, yazılım alt anahtar aracılığıyla daha fazla test sinyalini bir ölçüm cihazına yönlendirir ve ardından ölçümü okur. Bu, çalışmaya devam eden eski aramaları kesintiye uğratmaz.
Bir test başarısız olursa yazılım, arızayı birkaç harici anahtardan okuyarak tam devre kartını izole eder. Ardından, arızalı devrelerdeki serbest devreleri meşgul olarak işaretler. Hatalı devreyi kullanan aramalar sona erdiğinde, bu devreler de meşgul olarak işaretlenir. Bir süre sonra, hatalı devreden arama geçmediğinde, bilgisayar devre kartında değiştirilmesi gereken bir ışık yakar ve bir teknisyen devre kartını değiştirebilir. Değiştirmeden kısa bir süre sonra, bir sonraki test başarılı olur, onarılan alt anahtara bağlantılar "meşgul değil" olarak işaretlenir ve anahtar tam çalışmaya döner.
Bell'in ilk elektronik anahtarlarındaki tanılama, aslında her iyi baskılı devre kartında yeşil bir ışık yakacak ve başarısız olan her bir baskılı devre kartına kırmızı bir ışık yakacaktı. Baskılı devreler, anahtarın tamamı kapatılmadan çıkarılabilecek ve değiştirilebilecek şekilde tasarlanmıştır.
Nihai sonuç Bell 1ESS idi . Bu Merkez Kontrolü (CC) adı verilen bir CPU, bir kontrol edildi kilit adım , Harvard mimarisi güvenilir kullanarak ikili bilgisayar diyot-transistör mantığı . 1ESS CPU'da, her adımı iki bilgisayar birbirini kontrol ederek gerçekleştirdi. Aynı fikirde olmadıklarında, kendi kendilerine teşhis koyarlar ve doğru şekilde çalışan bilgisayar değiştirme işlemini devralırken diğeri kendisini diskalifiye eder ve onarım talep ederdi. 1ESS anahtarı, 2012 itibariyle hala sınırlı kullanımdaydı ve her otuz yıllık çalışmasında, tasarımını doğrulayan, planlanmamış bir saatten daha az arıza olduğu doğrulanmış bir güvenilirliğe sahipti.
Başlangıçta, her telefon santralinin en yoğun kullanılan parçaları olan büyük şehirlerdeki uzun mesafeli ana hatlara kuruldu. Büyük şehirlerin onunla faaliyet gösterdiği ilk Anneler Günü'nde Bell sistemi, hem tamamlanan aramalarda hem de anahtar başına saniye başına toplam aramalarda toplam ağ kapasitesi için bir rekor kırdı. Bu, ana hat başına toplam gelir için bir rekorla sonuçlandı.
Dijital anahtarlar
Bir anahtarın pratik bir uygulaması , daha küçük alt anahtarların tek sayıda katmanından oluşturulabilir. Kavramsal olarak, üç aşamalı anahtarın çapraz çubuk anahtarlarının her biri daha küçük çapraz çubuk anahtarlarına ayrıştırılabilir. Her alt anahtarın sınırlı çoğullama kapasitesine sahip olmasına rağmen, birlikte çalışarak daha büyük bir N × N çapraz çubuk anahtarının etkisini sentezlerler .
Modern bir dijital telefon anahtarında, iki farklı çoklayıcı yaklaşımının alternatif katmanlarda uygulanması, anahtarlama yapısının maliyetini daha da azaltır:
- boşluk bölmeli çoklayıcılar , daha önce açıklanan çapraz çubuk anahtarları veya bazı geçiş anahtarları veya banyan anahtarları düzenlemesi gibi bir şeydir . Herhangi bir tek çıkış, herhangi bir girişten seçim yapabilir. Dijital anahtarlarda, bu genellikle VE kapılarının bir düzenlemesidir . Saniyede 8000 kez, bağlantı bir zaman aralığı süresince belirli kabloları bağlamak için yeniden programlanır . Tasarım avantajı: Uzay bölmeli sistemlerde, uzay bölmeli bağlantıların sayısı, zaman bölmeli çoğullama sistemindeki zaman dilimlerinin sayısına bölünür. Bu, anahtarlama yapısının boyutunu ve masrafını önemli ölçüde azaltır. Aynı zamanda güvenilirliği de artırır, çünkü başarısız olacak çok daha az fiziksel bağlantı vardır.
- zaman bölmeli çoklayıcıların her biri, sabit bir sırayla okunan ve programlanabilir bir sırayla (veya tersi ) yazılan bir belleğe sahiptir . Bu tür bir anahtar , bitişik katmanlarındaki uzay bölmeli çoklayıcılara giden zaman bölmeli çoklanmış bir sinyalde zaman dilimlerine izin verir . Tasarım avantajı: Zaman bölmeli anahtarlarda yalnızca bir giriş ve çıkış kablosu bulunur. Başarısız olacak çok daha az elektrik bağlantısına sahip olduklarından, boşluk bölmeli anahtarlardan çok daha güvenilirdirler ve bu nedenle modern telefon anahtarlarının dış (giriş ve çıkış) katmanları için tercih edilen anahtarlardır.
Pratik dijital telefon anahtarları, elektroniklerin boyutunu ve masrafını en aza indirir. İlk olarak, bir abone hattına hem giriş hem de çıkış bağlantılarının aynı kontrol mantığı ile idare edilmesi için anahtarı "katlamak" tipiktir. Daha sonra, dış katmanda bir zaman bölme anahtarı kullanılır. Dış katman, sokak tarafı yerel mevcudiyet kutularında abone hattı arayüz kartlarında (SLIC'ler) uygulanır. Merkezi anahtardan uzaktan kumanda altında, kartlar zaman çoklamalı bir hattaki zamanlama yuvalarına merkezi bir anahtara bağlanır. ABD'de çoğullamalı hat, bir T-1 hattının bir katıdır . Avrupa'da ve diğer birçok ülkede, bir E-1 hattının bir katıdır .
Bir telefon anahtarındaki kıt kaynaklar, alt anahtar katmanları arasındaki bağlantılardır. Bu bağlantılar, çoğullamanın türüne bağlı olarak zaman dilimleri veya teller olabilir. Kontrol mantığı , bu bağlantıları ayırmaya sahip ve temel yöntem daha önce ele algoritmasıdır. Alt anahtarlar, daha büyük alt anahtarları sentezleyecek şekilde mantıksal olarak düzenlenmiştir. Her alt anahtar ve sentezlenen alt anahtar, Clos'un matematiğinden türetilen mantıkla kontrol edilir ( özyinelemeli ). Bilgisayar kodu, daha büyük çoklayıcıları daha küçük çoklayıcılara ayırır.
Özyineleme limite alınırsa, çapraz çubuğu mümkün olan minimum sayıda anahtarlama elemanına bölerse, ortaya çıkan cihaz, topolojisine bağlı olarak bazen bir geçiş anahtarı veya banyan anahtarı olarak adlandırılır .
Anahtarlar, tipik olarak SONET gibi hızlı çoğullamalı veri hatları aracılığıyla diğer anahtarlar ve fiber optik ağlarla arayüz oluşturur .
Bir anahtarın her satırı, bilgisayar tarafından, test verileri üzerinden gönderilerek periyodik olarak test edilebilir. Bir anahtarın hattı başarısız olursa, bir anahtarın tüm hatları kullanımda olarak işaretlenir. Çoklayıcı hatları ilk giren ilk çıkış yolu ile tahsis edilir, böylece yeni bağlantılar yeni anahtar elemanlarını bulur. Arızalı bir anahtardan tüm bağlantılar kesildiğinde, arızalı anahtar önlenebilir ve daha sonra değiştirilebilir.
2018 itibariyle, bu tür anahtarlar artık yapılmamaktadır. Bunların yerini yüksek hızlı İnternet Protokolü yönlendiricileri alıyor.
