SE507118C2 - Förfarande för att optimera ett huvudsakligen optiskt ATM- nätvärk - Google Patents

Description

15 20 25 30 5Û71¶8 gränsas fördelarna med statistisk multiplexering (SM) som an- nars ATM tillhandahåller. den vinst som àstadkoms vid dynamisk multiplexering av flera SM kan kortfattat beskrivas såsom kanaler med skurtrafik till en kanal, varigenom de tomma tid- luckor, som kan förekomma i kanalerna på grund av trafikens skuraktiga karaktär, elimineras. Ju högre kapaciteten är, desto lägre blir den effektiva bandbredden, varvid resursan- vändningen blir effektivare.

Kombineringen av AON-teknik med ATM-teknik är förenad med en prestandaförlust på grund av en SM-förlust. Den totala ef- fekten är emellertid en förbättring på grund av den förbätt- rade prestandan, som kärrör från den förenklade VP-admini- streringen.

Användningen av denna kombinerade teknik ger både fördelar och nackdelar. Nackdelarna är att omkopplingen måste göras på tre olika nivåer (i stället för två), nämligen: 1. Endast op- VP-omkoppling (tvärkopplingar), (VPI ändras); 3. VC- Konstruktionsförfarandet är svårt att beräkna, tisk omkoppling för VPL; 2. där omkopplingen görs på basis av VPI omkoppling. eftersom komplexiteten uppgår till antalet tillgängliga våg- längder upphöjt till antalet noder i nätet. Huvudfördelen är emellertid att många opto-elektriska omvandlingar kan undvi- varigenom pres- kas, så att färre tvârkopplingar erfordras, tandan förbättras.

Där finns ett problem i hur man gör konstruktionen av den- na typ av system optimal, dvs. när exempelvis backbone net- works konstrueras måste man anta full logisk kopplingsmöjlig- het mellan nätets noder och försöka finna optimeringsalgorit- mer för att på bästa sätt använda det begränsade antalet våg- längder för att åstadkomma en hög total systemkapacitet på grund av den spatiella återanvändningen av våglängder.

Den konstruktion som används i IEEE-artikeln är en kombi- nation av välkända "singelhopp"- och "multihopp"-tillväga- 10 15 20 25 30 35 (fl c: sa ...å ...à oo gångssâtt, som används hos mánga andra WDM-nät/förslag. Arti- keln diskuterar optimering av knstnaden, effektiviteten och systemkapaciteten hos routingnoden genom teoretisk analys.

Optimeringen indelas här i två steg med målet att minimera meddelandefördröjning, orsakas av den genomsnittliga som överföring: 1. De söker och avbildar en virtuell topologi på en given fysisk; och 2. Tilldela våglängderna till länkar hos Detta att VP- konstruktionen redan har genomförts i steg 1, vilket innebär den virtuella topologin. förfarande gör att optimeringskriterier kan försämras och fördröjningar kan öka, eftersom där finns fler änd-till-änd-strömmar på en fy- sisk länk än det tillåtna antalet våglängder, varvid artikeln Följaktli- eftersom våg- föreslår en omdirigering av en av dessa strömmar. gen ökar den genomsnittliga fördröjningen, längdstilldelningen och bildandet av den virtuella topologin är delad.

SAMMANFATTNING (AON) år Här försöker Kombinering av ASM-nät med ett helt optiskt nät en ganska ny teknik med nackdelar och fördelar. vi konstruera den virtuella topologin för ett optimalt ATM- nât ovanpå ett AON. Optimeringskriteriet avser här att göra ATM-nätet "sà optiskt" vill ha så långa ljusvägar som möjligt i nätet utan att behö- som möjligt, vilket betyder att vi va byta 'vàglângd, dvs. det totala antalet nödvändiga våg- längdsbyten i nätet skall vara så få som möjligt, varigenom behovet för ljusvâgarna att passera korskopplingar (CC) mini- meras. Denna idé löser problemet med, och beskriver ett för- farande för, att söka en optimal routing av nämnda VPC, så att mängden VP-omkoppling kan reduceras så nwcket som nöj- Hos ATM-nät âr en änd-till-änd-förbindelse associerad En eller flera VCC är som är byggd på en el- ligt. med en VCC (virtuell kanalförbindelse).

(VPC) ler flera VP-länkar (VPL) utmed vägen för nämnda VCC. Nämnda VPL består av en eller flera länkade VP. nämnda VP en "bunt" med VCC utmed en fysisk länk. upprättade på en VP-förbindelse Följaktligen är 10 15 20 25 30 35 507118 Utmed en VPL är VPI/VCI inte förändrad. fordras ingen elektrisk bearbetning utmed nämnda VPL, Följaktligen er- vilket också är syftet med uppfinningen. Eftersom ingen elektrisk bearbetning behövs utmed en VPL kan samma våglängd tilldelas VP. I detta fall behöver in- te de VPC, som använder dessa VPL, träda in i korskopplingar- (CC). Ef- tersom begränsningen på ledningskapaciteten hos CC är beroen- till alla dess komponenter, dvs. na De kan omkopplas med passiva optiska switchar. de av den interna busshastigheten, möjliggör anbringandet av ett ATM-nät ovanpå ett AON användningen av ett mycket större nät. Målet är att bära cellerna med virtuell topologi så långt som möjligt i det optiska området. Paketvidarebeford- ring från ljusväg till ljusväg genomförs via elektrisk om- koppling, när så erfordras. måste full logisk vilket betyder att varje nod måste När' vi konstruerar en nätverksstomme, kopplingsbarhet antas, kunna kopplas till varje annan nod i nätet. I allmänhet är konstruktionen behäftad med tre problem som måste lösas opti- malt: 1. Dirigera nämnda flertal VPC; Indela dem i ett fler- tal VPL; 3. Dimensionera nämnda flertal VPL. Dessa problem är beroende av varandra.

När vår modell används, kan det tredje problemet försummas, i stället har vi en begränsning: VPL-kapacitet kapaciteten).

Ingen (kanal- Uppfinningen föreslår ett tvåfasförfarande för får överskrida partitionskapaciteten att åstadkomma optimering så ofta som möjligt, där den första fasen innebär att söka en (eller två för tillförlitlighetsän- damål) nod-och-vertex-åtskild väg och tilldela dem kapacitet i enlighet med deras trafik. Målet (vägar) för' varje nodpar är att vid dirigering av VPC minimera den totala nâtkostna- den. Detta erfordrar inparametrar såsom nodpositioner, skat- tat trafikbehov mellan noderna och kostnader att bygga fysis- eller skattat trafikbehov mellan noderna och den fysiska topologin med giv- ka länkar mellan dem, när vi konstruerar nätet; na kapaciteter, när vi omdirigerar nämnda flertal VPC. Den andra delen av förfarandet innefattar en uppdelning av vägar- na mellan nodparen i sekvenser och hopslagning av dessa se- 10 15 20 25 30 C H t: ~<| ...å s-Ä oo kvenser till VPL och tilldela dem en våglängd. Tonvikten läggs på den andra delen. Här är målet att minimera det tota- la antalet uppdelningar av en VPC eller med andra ord, mini- mera antalet VPL utmed en VPC. Det kan matematiskt uttryckas såsom ett begränsat diskret optimeringsproblem, som kan lösas genom stokastisk optimering [exempelvis ”Simulated Annealing” (uppnående av jämnvikt) eller generisk algoritm]. Nyheten hos uppfinningen ligger i tvåstegsmodellen såsom en helhet och i synnerhet det andra steget med optimeringsmålet och begräns- ningarna, dvs. formuleringen av problemet och hur stokastisk optimering skall tillämpas på detta problem, dvs. hur model- len skall matchas med optimeringsalgoritmen för att åstadkom- ma ett optimalt nät med ett minimum av elektrisk bearbetning.

Förfarandet ger den optimala virtuella topologin samtidigt med vàglängdstilldelningen! Vidare ökar det inte överförings- fördröjningarna i. nätet, eftersmn vi förenar strömmarna om tillräckligt med kapacitet är tillgänglig i stället för att omdirigera en av strömmarna, vilket är nödvändigt i enlighet med teknikens ståndpunkt, då antalet strömmar på en fysisk länk är fler än antalet tillgängliga våglängder.

FIGURBESKRIVNING Utföringsformer av uppfinningen kommer nu att beskrivas tillsammans med en ritning där: fig. 1 visar ett exempel av ett nät med sex noder med dess fysiska och virtuella topologi, optimerat i enlighet med upp- finningen.

DETALJERAD BESKRIVNING AV UTFÖRINGSFORMERNA För att förenkla beskrivningen av idén och den föredragna Rit- ningen visar det optimala sexnodiga 11-16 ATM-nätet över ett utföringsformen visas ett exempel av ett nät i fig. 1. optiskt nät 1, som använder våglängdsmultiplex, WDM, eller 10 15 20 25 30 35 507 H8 rumsmultiplex, rum DM. Antalet noder och det fysiska avstän- det är naturligtvis godtyckligt och ciet visade förfarandet begränsas inte till ett nät med den fysiska topologin som vi- 1 är sinsemellan förbundna I detta exempel förutsätts full logisk kopplingsbarhet och tre olika sas i ritningen. Noderna i fig. med sju fysiska länkar 2-8, såsom visas i figuren. våglängder a, b och c. Med den givna fysiska topologin får vi 15 VPC: sju med längden ett (22; 26; 29; 31; 35; 39; 43;), sex med längden två (21 och 25; 24 och 44; 27 och 28; 32 och 36; 30 och 34; 37 och 40;) och två med längden tre (23 och 45 och 41; 33 och 38 och 42). dvs. passerandet av en nod pà vägen från den ursprungliga no- till elektrisk (vàglängdsomfördelning' och. ommultiplexering) kan. behövas om Tillsammans har vi tio “hopp“, den destinationsnoden, där bearbetning inte optimeringsförfarandet i enlighet med uppfinningen hade reducerat antalet hopp, såsom visas nedan. Det föreslagna op- timeringsförfarandet har reducerat antalet hopp, som bearbe- tas av korskopplingar (CC), i detta exempel från 10 till 4. 60, 70, 80, vi behöver elektrisk bearbetning och lagring, visas i fig. 1.

Dessa punkter 50, där strömmarna blandas och där Givet nodernas läge, trafikmatrisen, de fysiska länkarna och deras kapacitet, börjar vi med det första steget av för- farandet som innebär en dirigering av ursprungs- destinationsnodparen eller VPC ovanpå det fysiska nätet base- rat på ett godtyckligt optimeringskriterium utan begränsning- ar relaterade till det fysiska skiktets optiska egenskaper, exempelvis den kortaste vägen(shortest path), vägen med lägst multi- belastning(least loaded path) eller genom den s.k. commodity flow routing algorithm. Detta steg innefattar ing- enting nytt, så det förklaras inte vidare förutom nämnandet att om inte de fysiska länkarna och deras kapaciteter anges initialt, kan vi välja ett godtyckligt känt optimeringskrite- Emellertid, är det viktigt tillsammans med det rium även för dessa parametrar. även om steg ett inte är viktigt för sig, andra steget, eftersom det säkerställer att optimeringen inte försämras när steget två används. Före en detaljerad beskriv- 10 15 20 25 30 35 CH CD \J na “A 00 ning av steg två är det viktigt att tydliggöra och definiera de många förkortningar som ATM-tekniken har gett upphov till.

Routerna är indelade i. grundbyggenheter, som vi i. denna tillämpning förkortar till bbus, var och en med samma längd som en fysisk länk, dvs. en fysisk länk består av en uppsätt- ning bbus. Följaktligen, i fig. 1, finns totalt 25 bbus num- rerade från 21 till 45. Förenandet av alla fysiska länkar 2-8 och noderna 11-16 utgör nätet 1. En deluppsättning av en fy- sisk länk är en VP (bbus av samma våglängd) exempelvis 34, 35 och 37. Följaktligen är en fysisk länk en förening av VP. VP Nämnda flertal Seriell gruppering innefattar disjunkta mängder VP täcker alla bbus av (en eller flera) (disjunct sets). i en fysisk länk. (förening) VP (med samma våglängd) utgör en VPL. Seriell gruppering av VPC. Ett exempel underlättar detta: 1 innefattar fem bbus 34-38, VPC med våglängden b mellan noderna 14 och 13, som består av tre VP 33, 38 och 42, och en annan VP på länken 8 är nämnda VP med vågläng- (en eller flera) VPL utgör en Den undre högra länken 8 i fig. men endast tre VP. Nämnda som passerar länken 8, består av en enda VPL, den c, som består av en parallellkoppling av tre bbus, 34, 35 och 37. Nämnda bbu 34 utgör en del av en VPC mellan en nod 12 och 16 och utgör en VPL uppbyggd av endast en VP. Eftersom denna VPC byter våglängd finns inget behov för elektrisk be- i nod 15.

För nodparet 15 och 16 förbundna av arbetning (korskoppling) Korskopplingen visas med referensbeteckningen 70. nämnda enskilda bbu 35 är nämnda VP med våglängden c både en VPL och en VPC. Nämnda flertal VPL är de viktigaste byggenhe- terna, eftersom de är parallella och seriella grupperingar av bbus, som inte behöver någon bearbetning. Nämnda flertal VPC beskriver endast en sekvens av VPL, som används av en punkt- till-punkt-ström.

Det andra steget baseras, i enlighet med ovan, på ett god- tyckligt första steg och delar in vägar mellan nodparen i se- kvenser och införlivar dessa sekvenserna till ett flertal VPL, och tilldelar dem en våglängd. Problemet växer snabbt 10 15 20 25 30 35 507118 med antalet noder och antalet tillgängliga våglängder. Redan i exemplet i fig. 1 med sex noder och tre tillgängliga våg- längder och 25 bbus består tillståndsrummet av' 3^2S olika tillstånd. Följaktligen är problemet extremt komplext för ett så litet exempel. I enlighet med idén reduceras problemet på- tagligt om tillståndsrummet effektiviseras genom att börja med att tilldela en och samma våglängd till alla logiska län- kar med längden 1 mellan angränsande noder. I fig. 1 illust- 26; 29; 31; 35; 39; tilldelats våglängden c. Denna tilldelning försämrar inte mo- reras detta av bbus 22; 43 som alla har dellens allmängiltighet även om den förenklar den. Den totala komplexiten blir 3^7 gånger lägre: 3^18. Problemet börjar nu ta form. För att fortsätta med steg två i modellen erfordras en matematisk formulering av det problem som skall lösas. På det sättet deterministisk global optimering, såsom exempelvis ”Simulated första nedan beskrivna används en icke- med dämpningsplan eller generisk algorotm eller (Tabu Search), som är att minimera det totala antalet VPL Annealing”, ”förbjuden sökning” för att åstadkomma den málfunktion, (minimera antalet hopp för varje VPC). Nedan visas i enlighet med uppfinningen hur problemet kan formuleras för att lösas med ”Simulated Annealing”. ett eller flera antalet våglängder som stöds av varje Nämnda indata är: Den fysiska topologin; optimalt valda vägar; fiber; skattat busy-hour trafikkrav för varje nodpar; fiberns transmissionskapacitet för varje våglängd. Algoritmen följande utdata: VP, dvs. parallell ihopslagning av bbus; flertal VPL, dvs. och den våglängd som är tilldelad varje enskild VPL. ger ett VPC Där An- talet våglängder/länkar får inte överskrida ett givet värde; den seriella kopplingen av VP utmed en finns ett flertal begränsningar som inte får överskridas: transmissionskapaciteten för varje våglängd får inte över- skridas; det maximala antalet hopp utmed en VPC kan begrän- sas. Algoritmen letar sig igenom till global optimering genom att göra “elementära rörelser", som i detta fall innebär att byta våglängden hos en godtycklig bbu i nätet. Där kan finnas 10 l5 20 25 30 35 UT C) \J ...x ...x CO flera globala optimeringar. En elementär rörelse definieras här som att byta våglängden hos en godtycklig bbu och kon- trollera huruvida nämnda flertal VP i angränsande länkar kan länkas ihop till en VPL eller inte. Om de har samma våglängd och om alla bbus med denna våglängd korsar båda länkarna sam- manlänkar vi sedan dessa VP till en VPL. Därefter utvärderas málfunktionen: vi räknar det totala antalet VPL och om ke- gränsningarna har överskridits adderar vi en straffterm. Vid försök att minimera málfunktionen accepteras de tillstånd där straff har adderats med lägre och lägre sannolikhet. Detta på hos ”Simulated Annealing”. Hos grund av "dämpningen" ”Simulated Annealing" gör vi slumpmässigt elementära rörel- ser. Om målfunktionen har bättre värde än det tidigare steget accepteras det med högre sannolikhet, om värdet är sämre med lägre sannolikhet. Att acceptera ett tillstånd innebär att vi i nästa algoritmsteg förflyttar oss till en av grannarna tillstånd i det flerdimensionella tillståndsrum- tillstànd. Under utförandet av dämpning accepte- (angränsande i detta ras i början slutet blir bättre rörelse accepteras, met) alla tillstånd med nästan samma sannolikhet; vid acceptanssannolikheten nästan deterministisk: sämre avvisas.

Vid användning av ”Simulated Annealing" (med dâmpnings- plan) har test visat att vi får ett resultat på omkring l0^4 steg. Detta resultat är ett globalt optimum med sannolikheten omkring 0,8. Om vi upprepar hela förfarandet tio gånger, blir att finna det optimumet 1 - sannolikheten för <1o^-7). globala Hos en annan utföringsform av uppfinningens första och andra steg fungerar optimeringsförfarandet lika bra om vi i stället för multipla fibrer våglängder använder multipla (dvs. rumsmultiplex i stället för WDM). Detta skulle medföra en användning av kablar som innefattar fler fibrer och en an- vändning av samma våglängd i hela nätet. 1 betyder detta att varje fysisk länk 2-8 skulle innefatta tre fibrer. Hela exemplet skulle vara exakt I det exempel som beskrivs i fig. 507118 10 lika med det som beskrevs ovan, med den skillnaden att de tre våglängderna a, b och c i stället skulle beteckna tre olika fibrer, där varje fiber använder samma våglängd. En VP skulle sedan definieras såsom en fiber i en fysisk länk. Mellan fib- rer hos olika fysiska länkar kan optisk omkoppling lätt åstadkommas. En naturlig orsak är sedan att om vi bildar en VPL från flera VP (fibrer), kan inget trafikflöde träda in eller lämna vid noder mellan dessa VP.

Claims (8)

10 15 20 25 30 (TI CD *J ...a ..._\ CD ll R_a_t_e_n_t_k_r_a_y

1. Förfarande för att bilda den virtuella topologin hos ett ATM-skikt, där ATM-skiktet bärs över ett optiskt våg- längdsmultiplex- (WDM) nåt (1), såscmx det fysiska skiktet, där initialt åtminstone är givet: nodernas (ll-16) läge; tra- fikmatrisen; och antalet våglängder (a, b, c) som bärs av varje fysisk länk (2-8), kännetecknat av att för det första dirigeras änd-till-änd-trafikströmmarna över det fysiska nä- tet med ett godtyckligt känt förfarande på ett optimalt sätt, dvs. den kortaste vägen, vägen med lägst belastning eller en- ligt Multicommodity Flow Model, och för det andra, (bbus) (21-45) nonx att använda en icke-deterministisk: algoritm, gruppera grundbyggenheterna seriellt och parallellt ge- exempelvis ”Simulated Annealing”, där málfunktionen är att minimera det totala antalet VPL, såsom indata. givet villkor som begränsar prestandan,

2. Förfarande enligt med krav 1, kännetecknat av att grup- (bbus) (21-45) b eller c) hos en godtycklig bbu; trollera huruvida VP i angränsande länkar kan sammanlänkas till en VPL eller inte; VPL om nämnda flertal VP har samma nämnda våglängd peringen av grundbyggenheter görs genom att byta våglängden (a, kon- sammanlänka nämnda flertal VP till en b el- och om alla bbus med denna våglängd tillhör trafik- (a, ler c) strömmar som korsar alla dessa VP hos nämnda VPL; utvärdera målfunktionen genom att räkna antalet VPL; addera en straff- term till málfunktionen i det tillståndet om åtminstone ett av villkoren har överskridits och sedan acceptera detta till- stånd med minskande sannolikhet.

3. Förfarande enligt krav 2, kännetecknat av att stegen i krav 2 upprepas ett förbestämt antal gånger eller tills ingen mer förbättring i enlighet med málfunktionen uppnås, varvid det uppnådda tillståndet väljs såsom den virtuella topologin för detta nät. 10 15 20 25 30 507118 12

4. Förfarande enligt något av kraven 1-3, kännetecknat av att tillståndsrummet minskas genom att tilldela alla funda- mentala byggenheter (bbus), som bär trafiken hos angränsande (22; 26; 29; 31; 35; 39; 43), icke-deterministiska algoritmen används. nodpar samma våglängd innan den

5. Förfarande för att bilda den virtuella topologin för ett ATM-skikt, där ATM-skiktet bärs över ett optiskt rumsmulti- (1). tone är givet: nodernas (11-16) talet olika fibrer b, fiber använder samma våglängd, plexnât såsom det fysiska skiktet, där initialt åtmins- läge; trafikmatrisen; och an- i varje fysisk länk, där varje kännetecknat av att för det (a, c) första dirigeras änd-till-änd-trafikströmmarna på optimalt sätt över det fysiska nätet genom ett godtyckligt känt förfa- rande, exempelvis kortaste vägen, vägen med lägst belastning eller enligt Multicommodity Flow Model, och för det andra, (bbus) (21-45) parallellt genom att använda en icke-deterministisk algoritm, gruppera de grundbyggenheterna seriellt och exempelvis ”Simulated..Annealing”, där' màlfunktionen är att minimera det totala antalet nödvändiga fiberbyten, givet villkor begränsande prestandan, såsom indata.

6. Förfarande enligt krav 5, kännetecknat av att gruppe- (bbus) (21-45) som är reserverad för en god- ringen av grundbyggenheterna görs genom att b eller C), tycklig bbu; kontrollera huruvida nämnda flertal VP i angrän- byta den fiber (a, sande länkar kan sammanlänkas till en VPL eller inte; samman- länka nämnda flertal VP till en VPL om alla bbus i nämnda fi- ber (VP) tillhör trafikströmmar som korsar alla nämnda fibrer (VP) antalet VPL; tillstånd om åtminstone en av begränsningarna har överskri- i nämnda VPL; utvärdera màlfunktionen genom att räkna addera en straffterm till màlfunktionen i detta dits; acceptera tillståndet med minskande sannolikhet.

7. Förfarande enligt krav 6, kännetecknat av att stegen i krav 6 upprepas ett förbestämt antal gånger eller tills inga fler förbättringar i enlighet med màlfunktionen uppnås, var- (TI co -1 ...Å -à oo 13 vid det uppnådda rumstillstándet väljs såsom nätets virtuella topologí.

8. Förfarande enligt något av kraven 5-7, kännetecknat av att tillstándsrummet effektiviseras genom att tilldela alla grundbyggenheter (bbus) som bär trafiken hos angränsande no- der en reserverad fiber (22; 26; 29; 31; 35; 39; 43) innan den icke-deterministiska algoritmen används.