Icke-blockerande minimal spännströmbrytare
En icke-blockerande minimalspänningsbrytare är en enhet som kan ansluta N ingångar till N utgångar i valfri kombination. Den mest välbekanta användningen av växlar av denna typ är i en telefonväxel . Termen "icke-blockerande" betyder att om den inte är defekt kan den alltid göra anslutningen. Termen "minimal" betyder att den har så få komponenter som möjligt, och därför den minimala kostnaden.
Historiskt sett, i telefonväxlar, arrangerades förbindelser mellan uppringare med stora, dyra banker av elektromekaniska reläer , Strowger-växlar . Den grundläggande matematiska egenskapen hos Strowger-switchar är att för varje ingång till switchen finns det exakt en utgång. Mycket av den matematiska omkopplingsteorin försöker använda denna egenskap för att minska det totala antalet omkopplare som behövs för att ansluta en kombination av ingångar till en kombination av utgångar.
[ʃaʁl klo] På 1940- och 1950-talen påbörjade ingenjörer i Bell Lab en utökad serie matematiska undersökningar av metoder för att minska storleken och kostnaden för det " omkopplade tyget " som behövs för att implementera en telefonväxel. En tidig, framgångsrik matematisk analys utfördes av Charles Clos ( franskt uttal: <a i=6>[ ), och ett switchat tyg konstruerat av mindre switchar kallas ett Clos-nätverk .
Bakgrund: byta topologi
Tvärstångsomkopplaren
Tvärstångsomkopplaren har egenskapen att kunna ansluta N ingångar till N utgångar i valfri en-till-en- kombination, så den kan koppla vilken som helst uppringare till vilken som helst icke-upptagen mottagare, en egenskap som ges den tekniska termen "icke-blockerande" . Eftersom den inte är blockerande kan den alltid slutföra ett samtal (till en icke-upptagen mottagare), vilket skulle maximera tjänstens tillgänglighet.
Men tvärstångsomkopplaren gör det på bekostnad av att använda N 2 (N i kvadrat) enkla SPST-omkopplare . För stort N (och de praktiska kraven på en telefonväxel anses vara stora) var denna tillväxt för dyr. Vidare hade stora tvärstagsomkopplare fysiska problem. Inte bara krävde strömbrytaren för mycket utrymme, utan metallstängerna som innehöll brytarkontakterna skulle bli så långa att de skulle hänga och bli opålitliga. Ingenjörer märkte också att varje stång i en tvärstångsomkopplare när som helst bara gjorde en enda anslutning. De andra kontakterna på de två stängerna var oanvända. Detta verkade antyda att det mesta av växlingstyget i en tvärstångsomkopplare var bortkastat.
Det uppenbara sättet att efterlikna en tvärbalksbrytare var att hitta något sätt att bygga den från mindre tvärbalksväxlar. Om en tvärbalksomkopplare kunde emuleras av något arrangemang av mindre tvärbalksomkopplare, så skulle dessa mindre tvärbalksomkopplare också i sin tur kunna emuleras av ännu mindre tvärbalksomkopplare. Växlingstyget skulle kunna bli mycket effektivt, och möjligen till och med skapas av standardiserade delar. Detta kallas ett Clos-nätverk .
Helt anslutna 3-lagers switchar
Nästa tillvägagångssätt var att bryta isär tvärbalksomkopplaren i tre lager med mindre tvärbalksomkopplare. Det skulle finnas ett "indatalager", ett "mellanlager" och ett "outputlager". De mindre switcharna är mindre massiva, mer tillförlitliga och i allmänhet lättare att bygga och därför billigare.
Ett telefonsystem behöver bara göra en en-till-en-anslutning. Intuitivt tycks detta betyda att antalet ingångar och antalet utgångar alltid kan vara lika i varje subswitch, men intuitionen bevisar inte att detta kan göras och den berättar inte heller för oss hur man gör det. Anta att vi vill syntetisera en 16 x 16 tvärstångsomkopplare. Designen kan ha 4 subswitchar på ingångssidan, var och en med 4 ingångar, för totalt 16 ingångar. Vidare, på utgångssidan, kan vi också ha 4 utgångssubswitchar, var och en med 4 utgångar, för totalt 16 utgångar. Det är önskvärt att designen använder så få ledningar som möjligt, eftersom ledningar kostar riktiga pengar. Minsta möjliga antal ledningar som kan ansluta två subswitchar är en enda tråd. Så varje ingångssubswitch kommer att ha en enda tråd till varje mittsubswitch. Dessutom kommer varje mittdelomkopplare att ha en enda tråd till varje utgångsdelomkopplare.
Frågan är hur många mittsubswitchar som behövs, och därför hur många totalt ledningar som ska ansluta ingångsskiktet till mellanskiktet. Eftersom telefonväxlar är symmetriska (uppringande och uppringda är utbytbara), kommer samma logik att gälla för utgångsskiktet, och de mittersta underkopplarna kommer att vara "fyrkantiga", med samma antal ingångar som utgångar.
Antalet mellanswitchar beror på algoritmen som används för att allokera anslutning till dem. Den grundläggande algoritmen för att hantera en treskiktsswitch är att söka mellan underswitcharna efter en mellanswitch som har oanvända ledningar till de nödvändiga in- och utgångsswitcharna. När en anslutningsbar mittdelbrytare har hittats är det trivialt att ansluta till rätt in- och utgångar i in- och utgångsomkopplarna.
Teoretiskt sett behövs i exemplet endast fyra centrala omkopplare, var och en med exakt en anslutning till varje ingångsomkopplare och en anslutning till varje utgångsomkopplare. Detta kallas en "minimal spaning switch" och att hantera den var den heliga graalen i Bell Labs undersökningar.
Men lite arbete med en penna och papper kommer att visa att det är lätt att få en så minimal brytare i förhållanden där ingen enskild mittomkopplare har en anslutning till både den nödvändiga ingångsomkopplaren och den nödvändiga utgångsomkopplaren. Det tar bara fyra samtal för att delvis blockera växeln. Om en ingångsomkopplare är halvfull har den anslutningar via två mittersta omkopplare. Om en utgångsomkopplare också är halvfull med anslutningar från de andra två mittomkopplarna, så finns det ingen kvarvarande mittomkopplare som kan ge en väg mellan den ingången och utgången.
Av denna anledning ansågs en "enkelt ansluten icke-blockerande omkopplare" 16x16 omkopplare med fyra ingångssubswitchar och fyra utgångsomkopplare kräva 7 mittenomkopplare; i värsta fall skulle en nästan full ingångssubswitch använda tre mittomkopplare, en nästan full utgångssubswitch skulle använda tre olika, och den sjunde skulle garanterat vara fri att göra den sista anslutningen. Av denna anledning kallas ibland detta omkopplararrangemang en "2 n -1 switch", där n är antalet ingångsportar för ingångssubswitchar.
Exemplet är avsiktligt litet, och i ett så litet exempel sparar inte omorganisationen många byten. En 16×16 tvärstång har 256 kontakter, medan en 16×16 minimal spännomkopplare har 4×4×4×3 = 192 kontakter.
När siffrorna blir större ökar besparingarna. Till exempel skulle en 10 000 linjers växel behöva 100 miljoner kontakter för att implementera en fullständig tvärstång. Men tre lager med 100 100×100 subswitchar skulle bara använda 300 10 000 kontaktsubswitchar, eller 3 miljoner kontakter.
Dessa subswitchar kan i sin tur vara gjorda av 3×10 10×10 tvärstänger, totalt 3000 kontakter, vilket gör 900 000 för hela växeln; det är ett mycket mindre antal än 100 miljoner.
Hantera en minimal spänningsbrytare
Den avgörande upptäckten var ett sätt att omorganisera anslutningar i mitten switchar till "handelsledningar" så att en ny anslutning kunde slutföras.
Det första steget är att hitta en oanvänd länk från ingångssubswitchen till en mellanskiktssubswitch (som vi ska kalla A), och en oanvänd länk från en mellanskiktssubswitch (som vi ska kalla B) till den önskade utgångssubswitchen. Eftersom, före ankomsten av den nya anslutningen, ingångs- och utgångssubswitchar vardera hade minst en oanvänd anslutning, måste båda dessa oanvända länkar existera.
Om A och B råkar vara samma mellanskiktsbrytare, kan anslutningen göras omedelbart precis som i växelfallet "2 n −1". Men om A och B är olika mellanskiktssubswitchar krävs mer arbete. Algoritmen hittar ett nytt arrangemang av anslutningarna genom de mittersta underomkopplarna A och B som inkluderar alla befintliga anslutningar, plus den önskade nya anslutningen.
Gör en lista över alla önskade anslutningar som går genom A eller B. Det vill säga alla befintliga anslutningar som ska underhållas och den nya anslutningen. Den riktiga algoritmen bryr sig bara om de interna anslutningarna från ingångs- till utgångsomkopplaren, även om en praktisk implementering också måste hålla reda på de korrekta in- och utgångskopplingarna.
I den här listan kan varje ingångssubswitch visas i högst två anslutningar: en till subswitch A och en till subswitch B. Alternativen är noll, en eller två. Likaså visas varje utgångssubswitch i högst två anslutningar.
Varje anslutning är länkad till högst två andra genom en delad in- eller utgångssubswitch, som bildar en länk i en "kedja" av anslutningar.
Börja sedan med den nya anslutningen. Tilldela den vägen från dess ingångssubswitch, genom mitten subswitch A, till dess utgångssubswitch. Om denna första anslutnings utgångssubswitch har en andra anslutning, tilldela den andra anslutningen en väg från dess ingångssubswitch genom subswitch B. Om den ingångssubswitchen har en annan anslutning, tilldela den tredje anslutningen en väg genom subswitch A. Fortsätt fram och tillbaka på detta sätt , alternerande mellan mittsubswitchar A och B. Så småningom måste en av två saker hända:
- kedjan avslutas i en subswitch med endast en anslutning, eller
- kedjan går tillbaka till den ursprungligen valda anslutningen.
I det första fallet, gå tillbaka till den nya anslutningens ingångssubswitch och följ dess kedja bakåt, tilldela anslutningar till vägar genom mittsubswitcharna B och A i samma alternerande mönster.
När detta är gjort har varje ingångs- eller utgångssubswitch i kedjan högst två anslutningar som passerar genom sig, och de är tilldelade olika mittomkopplare. Således är alla nödvändiga länkar tillgängliga.
Det kan finnas ytterligare anslutningar via subswitchar A och B som inte ingår i kedjan inklusive den nya anslutningen; dessa anslutningar kan lämnas som de är.
Efter att det nya anslutningsmönstret har utformats i programvaran, kan elektroniken i switchen faktiskt programmeras om, vilket fysiskt flyttar anslutningarna. De elektroniska switcharna är utformade internt så att den nya konfigurationen kan skrivas in i elektroniken utan att den befintliga anslutningen störs och sedan träda i kraft med en enda logisk puls. Resultatet är att anslutningen flyttas omedelbart, med ett omärkligt avbrott i konversationen. I äldre elektromekaniska omkopplare hörde man då och då ett klang av "växlingsljud".
Denna algoritm är en form av topologisk sortering och är hjärtat i algoritmen som styr en minimal spännomkopplare.
Praktiska implementeringar av switchar
Så snart algoritmen upptäcktes började Bells systemingenjörer och chefer diskutera den. Efter flera år började Bells ingenjörer designa elektromekaniska strömbrytare som kunde styras av den. På den tiden använde datorer rör och var inte tillräckligt tillförlitliga för att styra ett telefonsystem (telefonsystembrytare är säkerhetskritiska och de är designade för att ha ett oplanerat fel ungefär en gång per trettio år). Reläbaserade datorer var för långsamma för att implementera algoritmen. Hela systemet kunde dock utformas så att när datorer var tillräckligt tillförlitliga kunde de eftermonteras till befintliga kopplingssystem.
Det är inte svårt att göra kompositomkopplare feltoleranta . När en subswitch misslyckas ringer uppringarna helt enkelt igen. Så vid varje ny anslutning försöker programvaran nästa lediga anslutning i varje subswitch istället för att återanvända den senast släppta. Det är mer sannolikt att den nya anslutningen fungerar eftersom den använder olika kretsar.
Därför, i en upptagen switch, när en viss PCB saknar några anslutningar, är den en utmärkt kandidat för testning.
För att testa eller ta bort ett visst kretskort ur drift finns det en välkänd algoritm. När färre anslutningar passerar genom kortets subswitch dirigerar programvaran fler testsignaler genom subswitchen till en mätenhet och läser sedan av mätningen. Detta avbryter inte gamla samtal, som fortfarande fungerar.
Om ett test misslyckas, isolerar programvaran det exakta kretskortet genom att läsa felet från flera externa omkopplare. Den markerar sedan de fria kretsarna i den felaktiga kretsen som upptagen. När samtal som använder den felaktiga kretsen avslutas, markeras även dessa kretsar som upptagna. En tid senare, när inga samtal passerar genom den felaktiga kretsen, tänder datorn en lampa på kretskortet som behöver bytas ut, och en tekniker kan byta ut kretskortet. Kort efter bytet lyckas nästa test, anslutningarna till den reparerade subswitchen är märkta som "inte upptagen" och switchen återgår till full drift.
Diagnostiken på Bells tidiga elektroniska omkopplare skulle faktiskt tända ett grönt ljus på varje bra kretskort och tända ett rött ljus på varje misslyckat kretskort. De tryckta kretsarna var designade så att de kunde tas bort och bytas ut utan att stänga av hela strömbrytaren.
Det slutliga resultatet blev Bell 1ESS . Detta styrdes av en CPU som heter Central Control (CC), en dubbeldator med låssteg , Harvard-arkitektur som använder pålitlig diod-transistorlogik . I 1ESS CPU utförde två datorer varje steg och kontrollerade varandra. När de inte höll med, skulle de diagnostisera sig själva, och den korrekt fungerande datorn skulle ta upp switchfunktionen medan den andra diskvalificerade sig själv och begärde reparation. 1ESS-switchen var fortfarande i begränsad användning från och med 2012 och hade en verifierad tillförlitlighet på mindre än en oplanerad timmes fel under varje trettio års drift, vilket validerade dess design.
Ursprungligen installerades den på långväga trunkar i större städer, de mest använda delarna av varje telefonväxel. På den första morsdagen som större städer arbetade med det, satte Bell-systemet rekord för total nätverkskapacitet, både i slutförda samtal och totalt antal samtal per sekund per switch. Detta resulterade i rekord för totala intäkter per trunk.
Digitala omkopplare
En praktisk implementering av en switch kan skapas från ett udda antal lager av mindre subswitchar. Konceptuellt kan var och en av trestegsomkopplarnas tvärbalksomkopplare delas upp ytterligare till mindre tvärbalksomkopplare. Även om varje subswitch har begränsad multiplexeringsförmåga, syntetiserar de tillsammans effekten av en större N × N tvärbalksomkopplare.
I en modern digital telefonväxel reducerar tillämpningen av två olika multiplexermetoder i alternativa lager ytterligare kostnaden för växlingsstrukturen:
- rymddivisionsmultiplexrar är ungefär som de redan beskrivna tvärstångsomkopplarna , eller något arrangemang av delningsbrytare eller banyanomkopplare . Varje enskild utgång kan välja från vilken ingång som helst. I digitala omkopplare är detta vanligtvis ett arrangemang av OCH-grindar . 8000 gånger per sekund omprogrammeras anslutningen för att ansluta särskilda ledningar under en tidslucka . Designfördel: I rymddivisionssystem delas antalet rymddivisionsanslutningar med antalet tidluckor i tidsmultiplexeringssystemet. Detta minskar dramatiskt storleken och kostnaden för växlingstyget. Det ökar också tillförlitligheten, eftersom det finns mycket färre fysiska anslutningar att misslyckas med.
- tidsmultiplexorer har var och en ett minne som läses i en fast ordning och skrivs i en programmerbar ordning (eller vice versa ). Denna typ av omkopplare permuterar tidsluckor i en tidsmultiplexerad signal som går till rymdmultiplexorerna i dess intilliggande lager. Designfördel: Tidsindelningsomkopplare har bara en ingångs- och utgångsledning. Eftersom de har mycket färre elektriska anslutningar att misslyckas, är de mycket mer tillförlitliga än rumsuppdelade växlar, och är därför de föredragna växlarna för de yttre (ingång och utgång) skikten av moderna telefonväxlar.
Praktiska digitala telefonomkopplare minimerar storleken och kostnaden för elektroniken. För det första är det typiskt att "vika" omkopplaren, så att både ingångs- och utgångsanslutningarna till en abonnentlinje hanteras av samma styrlogik. Sedan används en tidsdelningsomkopplare i det yttre lagret. Det yttre lagret är implementerat i abonnentlinjegränssnittskort (SLICs) i lokal närvaro på gatusidan. Under fjärrkontroll från den centrala omkopplaren ansluts korten till tidsluckor i en tidsmultiplexerad linje till en central switch. I USA är den multiplexerade linjen en multipel av en T-1-linje . I Europa och många andra länder är det en multipel av en E-1-linje .
De knappa resurserna i en telefonväxel är kopplingarna mellan lager av subswitchar. Dessa anslutningar kan vara antingen tidsluckor eller trådar, beroende på typen av multiplexering. Styrlogiken måste allokera dessa anslutningar, och den grundläggande metoden är den redan diskuterade algoritmen . Subswitcharna är logiskt arrangerade så att de syntetiserar större subswitchar. Varje subswitch och syntetiserad subswitch styrs ( rekursivt ) av logik härledd från Clos matematik. Datorkoden bryter ner större multiplexorer till mindre multiplexorer.
Om rekursionen tas till gränsen och bryter ner tvärstången till minsta möjliga antal kopplingselement, kallas den resulterande enheten ibland en crossover-omkopplare eller en banyan-omkopplare beroende på dess topologi.
Switchar gränssnitt vanligtvis till andra switchar och fiberoptiska nätverk via snabba multiplexerade datalinjer som SONET .
Varje rad i en switch kan periodiskt testas av datorn genom att skicka testdata genom den. Om en växels linje misslyckas markeras alla linjer i en växel som i bruk. Multiplexerlinjer allokeras på ett först-in-först ut-sätt, så att nya anslutningar hittar nya switchelement. När alla anslutningar är borta från en defekt switch kan den defekta switchen undvikas och senare bytas ut.
Från och med 2018 görs inte längre sådana byten. De ersätts av höghastighetsroutrar för Internetprotokoll .
