SE508284C2 - Metod och anordning för flödesstyrning i paketförmedlande nät - Google Patents

Description

508 284 området.

I allmänhet kräver tillämpningar som utnyttjar data- kommunikationstjänster en stor bandvidd under ganska korta tidsperioder, vilket medför trafik med skurartade egenskaper.

Dessutom måste information, som sänds mellan typiska data- tillämpningar, vara felfri, men kan påverkas av viss över- föringsfördröjning utan försämrad prestanda. Applikationer inom telekommunikationsområdet kan sägas ha motsatta egenskaper dvs. bandbredden hålls konstant och de är inte för känsliga för bitfel, men känsliga för fördröjningar och fördröjnings- variation.

Datakommunikationstrafik måste följaktligen hanteras på ett annat sätt än telekommunikationstrafiken inom ATM-näten om kompromissen mellan nätutnyttjandet och tjänstkvaliteten (Quality of Service - QoS) skall kunna hållas vid en acceptabel balans.

Nyare satsningar inom standardiseringsområdet återspeglar behovet av en särskild ATM-tjänst för att ta hand om trafik med "rena" datakommunikationsegenskaper. En tjänst benämnd "Available Bit Rate" ABR-tjänst specificeras i ATM Forum Traffic Management Specification 4.0, ATMF 95-00l3R10, Feb. 1996. Denna tjänst kommer även att införas i ITU-T-rekommendationerna, jfr. t.ex. ITU-T Recommendation I.371, "Congestion Management for the B-ISDN", 1995.

ABR-tjänsten använder ett hastighetsbaserat stocknings- styrningskoncept. Nätet styr den hastighet med vilken användarna kan överföra data medelst återkopplingsinformation från källorna.

Sammanfattning.

Ett antal olika algoritmer för styrning av explicit hastighet har föreslagits inom ramen för utvecklingen av ABR- tjänsten. Komplexiteten hos dessa algoritmer beror i stor utsträckning på valet av buffertschemaläggningsprinciper i väljaren. För att begränsa komplexiteten har de flesta algo- ritmer hittills strävat mot väljare, som utnyttjar FIFO- schemaläggning. Vissa av dessa algoritmer utnyttjar emellertid vad som skulle kunna kallas en "per VC accounting" (VC - Virtual Connection) för att, t.ex., hålla reda på antalet aktiva för- bindelser i en väljare och/eller antalet lagrade celler per VC.

I de flesta av algoritmerna används en bufferttröskel på ett eller annat sätt för att bestämma om en väljare är utsatt för stockning eller inte. De åtgärder som vidtas under stockning skiljer sig ofta ganska drastiskt från de som vidtas under icke stockningsförhållanden för att minska stockningstillståndet. Vid 508 284 3 vissa något mera sofistikerade algoritmer jämförs den totala ingångshastigheten med en önskad hastighetsreferens, eller arbetslast, och en ändring i ingångshastigheten beordras i proportion till skillnaden, jfr. exempelvis A.W. Barnhart, Hughes Network Systems, ATM Forum Contribution 95-0195, February 1995, "Example Switch Algorithm for Section 5.4 of TM Spec.".

Simuleringar av den i detta dokument föreslagna algoritmen har visat att när små värden på en förstärkningsparameter används, har algoritmen svårigheter att finna korrekt hastighet (rättvis hastighet) tillräckligt snabbt för att effektivt kunna utnyttja oanvänd bandvidd. När förstärkningsparametern ges ett högt värde, tenderar hastigheten istället att oscillera och för- orsakar därmed en ostabil situation i nätverket. En annan liknande algoritm har föreslagits av Raj Jain et. Al., Ohio -State University, ATM Forum Contribution 95-0195, October 1995, "ERICA+: Extensions to the ERICA Switch Algorithm".

Ett syfte med föreliggande uppfinning är att åstadkomma en explicithastighetsmekanism som kombinerar både information cm buffertens besättningsgrad och den till en väljare erbjudna ingångshastigheten, och som kan användas i en väljare, som utnyttjar ett "vanligt" FIFO-system såväl som i en "rättvist- köande"- schemaläggare.

Detta syfte har uppnåtts genom att sättet och syster-' enligt de första och andra aspekterna har erhållit de i kra:-' 1-22 resp. 23-24 angivna kännetecknen.

Vid en betydelsefull utföringsform av den första asprr' erhålles värden på en uppsättning parametrar och variabler, vilka innefattar y(t): en konflikthastighet vid utgångsbufferten vid tidpunkten t, y““(t): en uppmätt erbjuden hastighet till utgångsbufferten vid tidpunkten t, C(t): tillgänglig hastighet vid bufferten för lågprioriterade celler vid tidpunkten t, Q(t): total kölängd vid bufferten vid tidpunkten t, p: del av en eftersträvad tillgänglig hastighet vid bufferten, M: en buffertkölängdreferens, q och bg proportionella konstanter för en förbindelse i, som passerar utgångsbufferten.

Baserat på dessa värden kalkyleras explicithastighets- värdet xflt) vid tidpunkten t för förbindelsen i som ' _ PQÅLL _ QÅLLLM Xít = YUZ) [J-“aih- ycot(t)} bigæotul) H Det sålunda kalkylerade explicithastighetsvärdet gt är 508 284 4 tilldelat till explicithastighetsfältet hos en tillbakaflödes- styrhanteringscell.

Vid en betydelsefull utföringsform av den andra aspekten erhålles värden på en uppsättning parametrar och variabler, som innefattar: xï(t): utgångshastighet vid tidpunkten (t) vid ingångsbufferten för förbindelse j, p(t): total last vid tidpunkten (t) vid utgången från ingångsbufferten kalkylerad som kvoten ABR-celler mottagna vid ingångsbufferten per tidsenhet/antalet tillfällen att sända en ABR-cell per tidsenhet, pref: önskad last på utgången från ingångsbufferten, %(t): kölängd vid tidpunkten (t) vid ingångsbufferten för förbindelse j, mf kölängdreferens vid ingångsbufferten för förbindelse j. a och b: proportionella konstanter för förbindelse j.

Baserat på dessa värden fastställs explicithastighets- värdet kflt) vid tidpunkten t för förbindelsen j som xjm = mami-jun [Lau _ -g-lfš ymååfirLj-QTTI) }1 där max (rflt)) är en operation utförd på de individuella förbindelsesutgångshastigheterna rflt) hos väljaren för att t;f-» .en gemensam utgångshastighet för förbindelserna som passerar d-- gemensamma utgångsbufferten och sålunda undvika en skillnad i o« individuella förbindelseshastigheterna. Explicithastighetsvärdet §(t) tilldelas till explicithastighetsfältet hos en tillbaka- riktad resurshanteringscell som passerar ingångsbufferten j.

Genom uppfinningen förkortas "avverkningstiden" på styrslingan genom att uppfånga information om väljaren på tillbakavägen mot källan. Detta tillstånd uppträder efter det sändning först har börjat med en fördröjning förorsakad av en hel slinga källa-väljare-destination.

Kort beskrivning av ritningarna.

Uppfinningen skall nu beskrivas närmare med hänvisning till ritningarna, på vilka fig. 1 är en schematisk vy av en ABR-förbindelse, som sträcker sig i båda riktningarna mellan ett källändsystem och ett destinationsändsystem via en väljare, fig. 2 är en vy, som i större detalj visar en del av förbindelsen enligt fig. 1, sträckande sig mellan en ingångsport och en utgångsport hos väljaren, varvid ingångsporten och utgångsporten innefattar en ingångsanordning resp. en utgångs- 508 284 anordning, fig. 3a-b och 4a-d är flödesdiagram, som åskådliggör arbetssteg, vilka utförs i ingångsanordningen och utgångs- anordningen, som visas i fig. 2, fig. 5 och 6 är blockscheman åskådliggörande i större detalj strukturen hos ingångsanordningen resp. utgångs- anordningen i fig. 2, fig. 7 och 8 visar flödesapproximationer av en algoritm, som används för beskrivning av ett system enligt uppfinningen av det slag som åskådliggjorts genom fig. 1-6, fig. 9 är ett kurvdiagram åskådliggörande uppförandet hos två konstanter, vilka används i algoritmen enligt uppfinningen, fig. 10a,b och 11a,b är kurvdiagram åskådliggörande det transienta uppförandet hos systemet enligt uppfinningen, fig. 12a,b är kurvdiagram åskådliggörande det transienta uppförandet hos ett system, som fungerar enligt en algoritm enligt teknikens ståndpunkt, fig. 13 är en vy liknande den i fig. 2 åskådliggörande en väljare vid en ytterligare utföringsform av uppfinningen, fig. 14 i större detalj åskådliggör en del av Väljaren enligt fig. 13.

Detaljerad beskrivning av utförinqsformer.

Fig. 1 är en schematisk vy av en som exempel angiven förbindelse, i vilken föreliggande uppfinning kan användas.

Närmare bestämt rör det sig om en ABR ände-till-ändeförbindelse (ABR: Available Bit Rate), som passerar genom ett antal nätelement, t.ex. ett antal väljare, av vilka en schematiskt indikeras vid 102, i ett ATM-nät. Väljaren 102 bildar flaskhals i förbindelsen och antas vara utgångsbuffrad eller logiskt ha en gemensam buffert per utgångsport. Enligt den tidigare Omnämnda ATM-Forumhänvisningen, är ABR en ATM-skikttjänstkategori, för vilken de begränsande ATM-skiktöverföringsegenskaperna, som tillhandahålls av ett nätverk, kan ändra sig efter upprättande av förbindelsen. Tjänsten innefattar en flödesstyrmekanism, som stödjer återkoppling för styrning av cellöverföringshastigheten hos källhastigheten som reaktion på föränderliga ATM-över- föringsegenskaper. Cellöverföringshastigheten på olika ställen utefter en förbindelse såsom den, som bildar exempel här, uttrycks vanligen som cell/ms eller Mbps och kommer att nedan hänvisas till såsom hastighet. Återkopplingen sker till källan genom särskilda styrceller benämnda resurshanteringsceller, eller RM-celler. Närmare bestämt uppträder i fig. 1 ABR- flödesstyrning mellan ett sändande källändsystem 104, nedan hänvisat till som källa, och ett mottagande destinations- 508 284 6 ändsystem 106, nedan hänvisat till som destination, represen- terande en respektive linjeterminering och förbundna med varandra via tvåriktade förbindelser. I och för sig är för en tvåriktad ABR-förbindelse varje förbindelsetermineringspunkt både en källa och en destination. För enkelhetens skull kommer emellertid endast informationsflödet från källan 104 till destinationen 106 med dess tillhörande RM-cellflöden att betraktas här. Med framriktning kommer därför här att menas riktningen från källan 104 till destinationen 106 och tillbaka- riktningen kommer att vara riktningen från destinationen 106 till källan 104.

I fig. 1 visas källändsystemet 104 såsom varande dubbelriktat anslutet till en väljarport, ej visad, hos väljaren 102. Den dubbelriktade förbindelsen representeras av länkar 108 och 110 för fram- resp. tillbakariktningen. Länkarna 108 och 110 är utsatta för fortplantningsfördröjning representerad av dl resp. d4 inom cirklar. Destinationsändsystemet 106 är dubbel- riktat anslutet till samma väljarport hos väljaren 102. Den dubbelriktade förbindelsen representeras av länkar 112 och 114 för fram- resp. tillbakariktningen. Länkarna 112 och 114 är utsatta för fortplantningsfördröjning representerad av d2 resp. d3 inom cirklar. Vid 116 och 118 antyds utgångsbuffertar, som slutar i länkar 112 resp. 110. Block betecknade med N represen- terar andra förbindelser som använder samma utgångsbuffert, dvs. utgångsbuffertarna 116 och 118 är utsatta för ett anhopat cell- flöde från alla aktiva förbindelser, som kan förorsaka upp- trädande av en stockningssituation mellan de ifrågavarande förbindelserna. Därav förorsakad transmissionsfördröjning från buffertarna 116 och 118 indikeras genom symboler 120 och 122.

Med stockning avses här detsamma som definieras i B-ISDN, nämligen ett tillstånd hos nätelement (t.ex. väljare, koncentratorer, tvärförbindelser och transmissionslänkar), i vilka ett nät ej är i stånd att uppfylla negotierade nätfunk- tionsmål för redan etablerade förbindelser och/eller för nya förbindelsekrav. Allmänt kan stockning förorsakas av oförut- sägbara statistiska fluktuationer av trafikflöden och feltill- stånd i nätet.

För det framriktade informationsflödet från källan 104 till destinationen 106 i fig. 1 finns det en styrslinga bestående av två RM-cellflöden, ett i framriktningen och ett i tillbakariktningen. Källan 104 genererar RM-celler i framrikt- ningen vilka returneras av destinationen 106 till källan som RM- celler i tillbakariktningen. Dessa RM-celler i tillbakarikt- ningen bär återkopplingsinformation, som tillhandahålls av 508 284 7 nätelementen och/eller destinationen tillbaka till källan. Såsom anges i ATM-Forumhänvisningen kan ett nätelement: - Direkt införa återkopplingsstyrinformation i RM- cellerna när de passerar i fram- eller tillbakariktningen.

- Indirekt informera källan om stockning genom att ställa en explicit framriktad stockningsindikeringsbit i datacell- huvudet hos cellerna i det framriktade informationsflödet. I detta fall kommer destinationen att uppdatera de tillbakariktade RM-cellerna baserat på denna stockningsinformation.

- Generera tillbakariktade RM-celler.

Ett block 124 i fig. 1 representerar olika ABR-relaterade funktioner såsom mätningar i buffertarna 116 och 118 av buffert- kölängd och/eller erbjuden hastighet, liksom RM-celläs- och skrivoperationer. Väljaren 102 kan även införa tillbakariktade RM-celler för att reducera återkopplingsfördröjningar. Återkopplingsinformation från väljaren 102 till källan 104 leds i de tillbakariktade RM-cellerna med en hastighet _ proportionell mot utmatningshastigheten. Om ett explicit- hastighetssystem används, anges flaskhalshastigheten för en förbindelse av minimum av explicithastigheter som kalkyleras i varje väljare eller i destinationsändsystemet 106. För explicit- hastigheten kommer här benämningen ER (Explicit Rate) att användas.

ER ges av ett ER-fält hos RM-cellen och används till att begränsa en maximalt tillåten cellhastighet vid källan, benämnd ACR, till ett specifikt värde. Ett fält i den framriktade RM- cellen, benämnt Current Cell Rate (CCR) är tilldelat till ACR vid källan vid sändning av en framriktad RM-cell. ER ställs inledningsvis av källan till en begärd hastighet och kan därpå reduceras av varje nätelement i överföringsvägen till ett värde, som elementet kan klara av.

Baserat på beskrivningen ovan med hänvisning till fig. 1, kommer uppfinningen nu att förklaras närmare med användning av en algoritm. Målsystemet för algoritmen kan vara ett nätelement, t.ex. i form av en fysiskt eller logiskt utgångsbuffrad väljare, såsom väljaren 102 i fig. 1, med dess utgångsbuffertar 116 och 118.

För att förkorta återkopplingsfördröjningen tilldelas RM- cellerna information i den andra riktningen genom väljaren, vilket innebär att förbindelser med samma fördröjning i en slinga innefattande endast källa och väljare, snarare än i en slinga innefattande även destinationen, kommer att ha samma styrslingfördröjning. Omfattningen av fördröjningsvärdena i en grupp bestäms av den krävda stabilitetstoleransen, å ena sidan, och begränsningar på grund av implementationsaspekter, å andra 508 284 8 sidan. Algoritmen utnyttjar två proportionella konstanter, benämnda airesp. bh för varje grupp, som i motsvarighet därtill benämns Gi, hos förbindelser som har samma utbredningsfördröjning d = d1+d4. Nogrannheten med avseende på hur förbindelser i prak- tiken uppdelas i grupper mildras och fördröjningar i en grupp antas identiska. Konstanterna q och bianvänds som proportio- nella konstanter för det uppmätta felet i hastighets- resp. kölängd. Regler för inställning av dessa konstanter kommer att diskuteras ytterligare nedan. Valfritt skulle alla förbindningar kunna anbringas i en och samma grupp av förbindelser, vilket undviker en sökning efter det lämpliga paret av konstanter när en tillbakariktad RM-cell skall ges ett ER-värde.

I den nedan visade algoritmen anges den explicita hastigheten vid tidpunkten t för gruppen Gisom xflt) och kalkyleras vid väljaren genom följande formel: (l) xit = y(t) [1-a1{1 yQC-(fltottw) - bi{ }] och tilldelas till ER-fältet hos RM-cellen, om inte ett lägre ER-värde tilldelats. Algoritmen använder följande variabler: - y(t): uppmätt individuell hastighet hos förbindelser i konflikt vid tidpunkten t, även i fortsättningen benämnd konflikthastighet, - yKn(t): uppmätt erbjuden hastighet vid tidpunkten t, - C(t): bandbreddkapacitet tillgänglig vid tidpunkten t, även i fortsättningen benämnd tillgänglig hastighet, - Q(t): buffertbeläggningen vid tidpunkten t, även i fortsättningen benämnd kölängd, - p: fraktion av den tillgängliga bandbredden som algoritmen försöker allokera, - M: en kölängdreferens.

Såsom diskuterats ovan är CCR-fältet i den framriktade RM-cellen tilldelat den maximalt tillåtna cellhastigheten ACR vid källan när en framriktad RM-cell sändes iväg. CCR används att kalkylera konflikthastigheten y(t) vid bufferten och hänvisas till nedan såsom den rättvisa fördelningshastigheten.

Kalkyleringarna sker medelst exponentiell medelvärdesbestämning av värdet i CCR-fälten, dvs. (2) y(t) = aCCRum + (1-a)y(t), där a är en exponentiell medelvärdeskonstant (i intervallet [0.l]), 508 284 9 CCRcon högre än ßy(t), där ß är en fraktion av den rättvisa fördel- ningshastigheten, som en CCR måste överskrida för att utgöra del av medelvärdet.

Detta villkor säkerställer att endast förbindningar som verkligen har sin flaskhals i den ifrågavarande väljarbufferten, eller åtminstone har en hastigheten nära den rättvisa fördel- ningshastigheten, tas med i beräkningen och därigenom undviker för liten genomströmning av bufferten. Den exponentiella medel- värdesbildningsfunktionen (2) används allmänt i andra FIFO- baserade ABR-algoritmer för explicit hastighet för att härleda ett mått på den rättvisa fördelningshastigheten och benämns då ofta MACR-kalkylering, jfr. A.W. Barnhart, Hughes Network Systems, ATM Forum Contribution 95-0195, February 1995, "Example Switch Algorithm for Section 5.4 of TM Spec.". I den här föreslagna algoritmen är medelvärdesbildningen något modifierad för att undvika utsvältning av uppdateringar om stora omedelbara ändringar i ingångshastigheten uppträder. En räknare räknar antalet mottagna, för lite genomströmmande CCR-värden och håller reda på räknevärdet. Om räknevärdet överskrider en gräns, kommer CCR-värdet att användas i alla fall. Varje mottagning av ett CCR-värde från en förbindelse i konflikt kommer att återställa räknaren.

Mätningarna av den erbjudna hastigheten yKn(t) och den anger de CCR som råkar på ett värde lika med eller tillgängliga hastigheten C(t) utförs genom tagande av för- hållanden mellan cellantal och tidsintervall, definierat av ett minimalt antal celler. C(t) erhålls genom att ta skillnaden mellan den totala länkhastigheten och den bandbredd, som allokeras av trafik med högre prioritet, dvs. den variabla bithastigheten VBR samt kontinuerliga bithastigheten CBR. I VBR- fallet skulle detta kunna ske inom en relativt kort tidsram, medan CBR-allokeringen endast ändras när förbindelser uppställs eller frigörs.

Såsom nämnts ovan arbetar algoritmen i en punkt i välja- ren där ABR-förbindelser är i konflikt med avseende på utgångs- länkkapaciteten, t.ex. vid en utgångsbuffert. Det kan emellertid av implementeringsskäl vara svårt att lokalisera tillräcklig bufferteringskapacitet vid utgångsporten. Istället är buffer- tarna belägna på ingångssidan och i ett sådant fall arbetar uppfinningen med en logisk utgångsbuffert och använder åtgärder erhållna från den fördelade bufferteringsstrukturen.

Längre fram kommer ett fall av lokalisering av algoritmen att beskrivas. Denna lokalisering kan betraktas som frivillig och alternativa lokaliseringar är helt möjliga vad avser algo- ritmen som sådan, men är emellertid begränsade av implemente- 5Û8 284 10 ringsskäl. Även om ändamålet med ABR är att använda outnyttjad bandbredd, kommer viss bandbredd att vara statiskt reserverad, t.ex. för enbart CBR-trafik, och behöver ej allokeras av ABR. I en pseudokod, som kommer att beskrivas längre fram, erhålls den statiskt allokerade bandbredden alltid från länkhastigheten.

En typisk väljarlösning med distribuerad buffertering har, såsom nämnts ovan, stora ingångsbuffertar vid ingångs- portarna och relativt små buffertar vid utgångsportarna. Cell- förluster i den lilla utgångsbufferten undviks medelst en intern flödesstyrmekanism, som ej bildar del av uppfinningen. För att undvika blockering i början bör vidare ingångsbuffertarna vara logiskt fördelade på separata buffertar för varje utgångsport.

Fördelningen av buffertering innebär att den i verkligheten erbjudna hastigheten och kön kommer att fördelas mellan ingångsbuffertarna, men algoritmen måste arbeta med den totala hastigheten och kölängden för anpassning till rättvisemålen. Ett sätt att uppnå detta, schematiskt visat i fig. 2, är att låta ett väljarinternt cellformat överföra räknevärden hos anlända celler och mätvärden på kölängder från varje logisk ingångs- buffert till en utgångsport, där den verkliga beräkningen av explicit hastighet och tilldelningen av tillbakariktade RM- celler sker.

Fig. 2 är en vy som i större detalj visar en del av förbindelsen enligt fig. 1, som sträcker sig mellan en ingångs- port och en utgångsport hos väljaren. I fig. 2 anger en pil 202 celler, som anländer från källan, vid en logisk ingångsbuffert 204 hos en ingångsanordníng 2069 Ingångsanordningen 206¿är en av ett antal ingångsanordningar 206LN som hör till väljaren, här antytt vid 212. Alla dessa ingångsanordningar innefattar logiska ingångsbuffertar, såsom bufferten 204. Vid varje ingångsanord- ning räknas det totala antalet anländande celler och antalet köande celler för att erhålla en anländande cellsumma Cyiresp. en köande cellsumma Q? Celler som lämnar bufferten 204 och anländer i en utgångsbuffert 214 i en ej visad utgångsport hos väljaren 212 antyds med en pil 216. Den bufferten 214 inne- fattande utgångsporten utgör en av N utgångsportar, som hör till väljaren 212. Pilar 218 och 220 antyder cellflöden från de logiska buffertarna hos andra av ingångsanordningarna 206LN, som också inträder i samma väljarutgångsbuffert 214. Celler som lämnar bufferten 214 och väljaren 212 sänds i framriktningen, antytt med pil 222, via en utgångsanordning 224 till en ej visad destination. Utgångsanordningen 224 är gemensam för de N utgångsportarna. Celler returnerade av destinationen i tillbaka- 508 284 H riktningen till väljaren 212 via utgångsanordningen 224 antyds med en pil 226.

Mätningarna av ingångscellräknevärde och kö, såsom Qioch Cyp från ingångsanordningen 20q, överförs från varje logisk ingångsbuffert till utgångsanordningen 224 i två fält av ett internt cellformat antytt vid 228. Vid utgångsanordningen 224 sker den verkliga explicithastighetsberäkningen och tilldel- ningen av tillbakariktade RM-celler, i en funktion som antyds med ett block 230, och en förteckning över alla räknevärden avseende anlända celler och kölängdvärden för var och en av ingångsanordningarna 206LN måste finnas där. En mot blocket 230 pekande pil 232 indikerar överföringen av Cyf och Qfvärdena liksom läsoperation på de framriktade RM-cellerna. Den fördröj- ning som förorsakas av utgångsbufferten 214 innan räknesummorna når utgångsanordningen 224 kommer att vara kort jämfört med den totala överföringsfördröjningen. Den totala erbjudna hastigheten kommer att beräknas i kontinuerliga intervaller och ögonblicks- värdet av den totala kölängden är helt enkelt summan av från ingångsportarna överförda kölängder. När en tillbakariktad RM- cell vidarebefordras används det totala kövärdet och det senaste hastighetsvärdet för att beräkna explicithastighetsvärdet. En dubbelpil 234 mellan pilen 226 och blocket 230 antyder läs- och skrivoperationer på en tillbakariktad RM-cell.

En liknande metod för att överföra cellräknevärden och kölängdmätningar såsom den som beskrivs med hänvisning till fig. 2, kan användas när stora buffertar är belägna i utgångsporten.

Ingen aggregering av mätningarna från olika ingångsportar är emellertid nödvändig i detta fall. Istället kan de överförda värdena användas direkt i ER-beräkningen.

De i fig. 2 utförda operationerna kommer nu att beskrivas nedan med hänvisning till fig. 3-6. Fig. 3 och 4 innehåller flödesdiagram, som åskådliggör funktionssteg utförda i ingångs- anordningen 206 resp. utgångsanordningen 224, och representeras i pseudokodblock som följer nedan. Ankomst av data eller RM- celler kommer att utgöra händelser, som klockar operationerna genom olika sekvenser. Beskrivningen med hänvisning till fig. 5 och 6, som visar delar av strukturen enligt fig. 2 i större detalj, kommer ytterligare att klargöra utförandet av opera- tionerna.

Följande variabler och parametrar kommer att användas i flödesdiagrammen och pseudokoden: NoRec: Totalt räknevärde för mottagna celler.

NoSentHP: Räknevärde för antalet celler med högre prioritet som sänds med variabel bithastighet (VBR). 508 284 12 Hplimitstep: Maximal intervallängd för beräkning av utgångslänkhastigheten.

InputRateLimitstep: Maximal intervallängd för beräkning av ingångshastigheten.

StaticAlloc: Värde på statiskt allokerad bandbredd för CBR-trafik. Det tillhandahålls av den signalerande applikationen eller driftstödshanteringssystemet för nätet.

InputRateIntLimit: Antal celler nödvändiga för kalkylering av erbjuden hastighet.

OutputRateIntLimit: Antal celler nödvändigt för kalkylering av utgångshastighet.

Q: Vektor för Q-värden för varje logisk ingångsbuffert.

Qtot: Summan av elementen i Q.

Rho: Laddningsfaktor som används för att möjliggöra styrning av systemet mot en last mellan 0 och 1 i stationärt tillstånd.

B: Fraktion av den rättvisa fördelning som en CCR måste överskrida för att bilda del av medeltal. a: Exponentiell medelvärdesbildande konstant (i intervallet [0,1]). a: Vektor för hastighetsproportionella faktorer för varje grupp av förbindelser med samma utbredningsfördröjning. b: Vektor för köproportionella faktorer för varje grupp av förbindelser med samma utbredningsfördröjning.

Flödesdiagrammet i fig. 3a och 3b visar funktionssteg utförda på ABR-celler i ingångsanordningen 206% Fig. 3a berör ABR-cellankomster till ingångsanordningen. Väntan på att ABR- celler skall anlända representeras av block 302 och pil 303 för fortsättväntatillstånd. Om en ABR-cell mottages, antytt med pil 304, följer cellräkne- och kölängdräknesteg 306 resp. 308. De respektive räknevärdena anges av Cyioch Qii fig. 3a. I det blockindikerande steget 308 och på motsvarande rad av pseudo- koden (cl) nedan, anger en asterisk * att detta steg ej används om en alternativ kölängdberäkning används, vilket kommer att beskrivas senare. Steg 308, eller alternativt steg 306, följs av retur till vänttillståndet enligt pil 310.

Kodblocket (cl) nedan innehåller det tillstånd och de operationer som visas i blocken 302, 306 och 308.

If Cell received (cl) çyi := Cyi +1 Qi I= Qi+1 Endïf Steg som förberedelse för transmission av ABR-celler till utgångsanordningen 224 visas i fig. 3b. Väntan på transmission 508 284 13 av ABR-celler till utgångsanordningen 224 representeras av block 312 och pil 313 för fortsättväntatillstånd. Om en ABR-cell skall överföras, antytt med pil 314, följer steg 316 och 318. I dessa steg införs de av operationerna enligt fig. 3a resulterande värdena i de respektive två fälten hos interncellformatet som indikeras vid 228 i fig. 2, följt av att Cyisätts till 0, steg 316, och av reducering av Qfräknevärdet med 1, steg 318. I det blockindikerande steget 318 och på motsvarande rader av pseudo- koden (2) anger en asterisk att detta steg ej används om alter- nativ kölängdberäkning används. Steg 318, eller alternativt steg 316, följs av återgång till vänttillståndet enligt pil 320.

Kodblock (c2) nedan innehåller tillstånd och operationer som visas i blocken 312, 316 och 318, varvid de ifrågavarande fälten hos interncellformatet benämns "Cell_Cy_field" och "Cell_Q_field": If Cell due for transmission to output port çell_Cy_field := Cyi (c2) Cell_Q_field := Qi Cyi = 0 Qi = Qi-1 EndIf Flödesdiagrammet enligt fig. 4a åskådliggör steg för beräkning av aggregerad erbjuden hastighet ynn och kölängd v.fl utgångsanordningen 224. Väntan på överföring av ABR-celler 1.. utgångslänken representeras av ett startsteg 402 och en retur- slinga 403 innehållande ett alternativt startsteg 404.

Om en ABR-cell skall överföras, följer steg 406 och 408, i vilka innehållen Cyioch Qiav de anlända cellvärdes- och kölängdfälten 228 av internformatet läses och adderas för att skapa ett totalankomsthastighetsräknevärde respektive ett total- kölängdräknevärde Qmv I blocket för steg 408 och i kodblocket (c3) nedan anger ett kölängdberäkningsuttryck följt av en asterisk * att denna beräkning ej används om den alternativa metoden för beräkning av totalkölängden används.

De räknevärden som erhålls via Cy-fältet i interncell- formatet anger antalet celler som anlänt till väljaringångs- porten innehållande ingångsbufferten 204 (denna ingångsport är logiskt ansluten till väljarens utgångsport via utgångsanord- ningen 224) sedan den sista cellavgången. Räknevärdet kan vara noll om det finns celler lagrade i bufferten 204 och inga celler anländer till den. Samma procedur utförs vid alla väljaringångs- portar så att till ingångsanordningen 224 anländande celler kommer att föra med sig antalet celler som anländer mellan två ankomster till den respektive logiska ingångsbufferten. Om dessa 508 284 14 räknevärden nu summeras kommer det totala antalet celler, som anländer till en viss utgångsport via ett antal ingångar att erhållas. Om detta värde divideras med den tid under vilken beräkningen utförs, kommer ett totalhastighetsmått att erhållas.

Om, å andra sidan, antalet ankomster summeras kontinuer- ligt och denna summa samtidigt minskas med 1 (Qmg för varje ABR- cell som passerar och avger ett Cy-värde, kommer ett netto av antalet celler i systemet för tillfället att erhållas, dvs. kölängden. Om de anländande Cy-värdena är noll kommer sålunda summan att kontinuerligt minska. I själva verket är detta exakt den operation som skulle ha gjorts för erhållande av kölängden om det endast funnits en stor utgångsbuffert, men i detta fall måste kövärdena överföras till utgången, vilket innebär en viss fördröjning mellan den sålunda erhållna kölängdberäkningen och innehållet i ingångsbuffertköerna vid en viss godtycklig tid- punkt. _ Det alternativa sättet att beräkna kölängden grundar sig på ovanstående överväganden. Om det alternativa sättet används behövs ingen köräknare vid ingången och register som används vid utgången för summering av de individuella kölängderna.

Enligt den alternativa metoden kan den totala kölängden beräknas vid utgångsanordningen enbart grundat på cellankomst- räkning. I utgångsanordningen 224 beräknas närmare bestämt en totalkölängd Qnn genom summering av ankomstcellräknevärdena Cyw räknade i ingångsanordningen 206 och ledda till utgångsanord- ningen 224 i interncellformatet 228 såsom beskrivits tidigare, samt subtrahering därifrån av 1 för varje cell, som hör till det styrda ABR-cellflödet, vilket sänds vidare på utgångslänken till destinationen. I blocket för steg 408 och i kodblocket (c3) nedan uttrycks denna alternativa beräkning som [QK“=max ((QKn+Cell_Cy)-0.1)], där nedstegningen -1 representerar den med cellankomsträknevärdet Cy anländande cellen, och 0 exkluderar negativa Q-värden. Hela det alternativa uttrycket är beläget inom parentes för att ange dess karaktär som alternativ.

Den alternativa metoden innebär att ingen separering mellan de från olika ingångsanordningar anländande värdena är nödvändig. Dessutom behöver bara ett värde överföras i intern- cellformatet. Den alternativa metoden skulle kunna införa vissa problem med synkronisering mellan det verkliga antalet lagrade celler och mätvärdet Q om celler förloras internt i väljaren.

Denna eventualitet bör emellertid vara extremt sällsynt om väljaren är korrekt konstruerad.

Steg 410 bestämmer när ett förutbestämt antal InputRateLimit av celler mottages. Om detta ej är fallet, sker 508 284 15 återgång till startsteget 402 enligt steg 412.

Steg 404 i returslingan 403 fastställer om celler ej mottagits under en bestämd tidsperiod InputTtimeLimit. Detta steg är för erhållande av ett nytt värde på yux om celler ej skulle anlända under en längre tidsperiod. Om något av de två villkoren enligt stegen 404 resp. 410 uppfylls, följer steg 414, i vilket en tidsram InputTdiff beräknas sedan det sista steget var i drift. Denna tidsram används i det följande steget 436, i vilket ykn beräknas som förhållandet mellan det totala räkne- värdet av mottagna celler och denna tidsram.

I det sista steget 418 fastställs startsteget för en ny tidsram som sluttiden för föregående tidsram, räknevärdet för mottagning av celler sätts till noll, och en ny tidstartpunkt för den bestämda tidsperioden InputTime1imit fastställs. Ãtergång till startsteget 402 sker därpå enligt pil 420.

Nedanstående kodblock (c3) definierar operationerna i flödesdiagrammet enligt fig. 4a.

Såsom angetts tidigare och följer av det ovanstående, mäts yKn(t) genom att ta förhållandet mellan cellräknevärdet och tidsintervallet, uttryckt som "NoRec/InputTdiff", där tids- intervallet "InputTdiff" bestäms av "Now-InputTlast".

If ABRCell due for transmission on link NoRec:= NoRec + Cell_Cy_field Q(i) := Cell_Q_field [Qtot=max((Qtot+Cell_Cy)-1,0)] If NoRec >= InputRateIntLimit InputTdiff := Now-InputTlast ytot := NoRec/InputTdiff InputTlast := Now (c3) InputTimeLimit := Now + InputRateLimitstep NoRec:=0 Endlf Elseïf (Now > InputTimeLimit) InputTdiff := Now-InputTlast ytot := NoRec/InputTdiff InputTlast := Now InputTimeLimit := Now + InputRateLimitstep NoRec:=0 Endif Flödesdiagrammet enligt fig. 4b anger operationer i samband med beräkning av bandbreddskapacitet som är tillgänglig för ABR-celler, dvs. den tillgängliga hastigheten C(t) i utgångsanordningen 224.

Väntan på uppträdande av huvud för högprioriterade HP- celler för utsändning representeras av ett startsteg 422 och en returslinga 424, som innehåller ett alternativt startsteg 428.

Om en HP-cell mottages i steg 422 följer ett HP-cellberäknings- 508 284 16 steg 426. Nästa steg 430 fastställer om mer än ett förutbestämt antal OutputRateIntLimit av HP-celler mottages. Om så ej är fallet följer retur till startsteget 422 enligt pil 432.

Steg 426 i returslingan 424 fastställer huruvida HP- celler ej mottagits under en förutbestämd tidsperiod Hptimelimit. Detta steg är för erhållande av ett nytt värde på C om HP-celler ej skulle anlända under en lång tidsperiod. Om endera av de två villkoren enligt de respektive stegen 426 och 430 uppfylls, följer steg 434, i vilket en tidsram OutputTdiff beräknas sedan senast detta steg var i drift. Denna tidsram används i det följande steget 436, i vilket beräkning sker av tillgänglig hastighet C(t).

Såsom angetts tidigare mäts den tillgängliga hastigheten C(t) genom att ta skillnaden mellan den totala länkhastigheten och bandbredd som är allokerad för trafik med högre prioritet.

Detta uttrycks i blocket 436 och i följande kodblock (c4) såsom "C:=LinkRate - StaticAlloc - NoSentHP/OutputTdiff". "LinkRate" är en konfigurationsparameter som tillhandahålls av driftstöd- systemet för nätet och anger typen av hastighet som tillhanda- hålls av skiktet under ATM. Betydelsen av "NoSentHP" och "StaticAlloc" har förklarats tidigare.

I det sista steget 438 sätts starttiden för en ny tidsram OutputTdiff som sluttiden för föregående tidsram, räknevärdet av mottagna celler i steg 428 sätts till noll, och en ny tidstart- punkt för den bestämda tidsperioden Hptimelimit sätts. Ãtergång till startsteget 422 följer därpå enligt block 440.

Kodblocket (c4) nedan innehåller tillstånden och operationerna som visas i fig. 4b.

If HPCell sent on output link NoSentHP:=NoSentHP +1 If NoSentHP >= OutputRateIntLimit (c4) OutputTdiff := Now-OutputTlast C :=LinkRate - StaticAlloc - NoSentHP/OutputTdiff OutputTlast := Now HPtimelimit:=Now+HPlimitstep NoSent := 0 Endïf Elself (Now > HPtimelimit) OutputTdiff = Now-OutputTlast C :=LinkRate - StaticAlloc - NoSentHP/OutputTdiff OutputTlast := Now HPtimelimit:=Now+HPlimitstep NoSent := O EndIf Flödesdiagrammet i fig. 4c anger operationer i samband 508 284 17 med kalkylering av rättvis fördelningshastighet y i utgångs- anordningen 224.

Väntan på att nästa RM-cell skall sändas representeras av block 442 och fortsättväntatillstånd-pil 444. Om en RM-cell är aktuell för utsändning, indikerat med pil 446, fastställer steg 448 om något av två villkor uppfylls. Det första av dessa villkor är att CCR har ett värde lika med eller högre än ßy(t), uttryckt som "RM(CCR) >= (Beta * y) OR (UF_Count >Uflimit)", och det andra villkoret är att ett räknevärde uttryckt som "UF_Count", av antalet mottagna underströmmande CCR-värden överskrider en gräns uttryckt som "UFlimit". Om något av de två villkoren fullföljs följer steg 450, annars steg 452.

I steg 450 utförs den genom formeln (2) ovan uttryckta operationen, vilket uttrycks i pseudokoden i fig. 4c och i nedanstående kodblock (c5) som "y := RM(CCR)*Alpha + y * (1- Alpha)". Detta följs av steg 454 där UF_Count sätts till noll, samt retur till väntsteget 442, 444 såsom antyds med pil 456.

I steg 452 utförs den operation, som uttrycks i pseudo- koden i kodblocket (c5) nedan som "UF_Count := UF_Count+1", följt av retur till vänttillståndet 442, 444 enligt pil 458.

Kodblocket (c5) nedan innehåller de i fig. 4c visade tillstånden och operationerna.

If Forward RM cell due for transmission on the output link If RM(CCR) >= (Beta * y) OR (UF_Count >UFlimit) y := RM(CCR)*Alpha + y * (1-Alpha) (c5) UF_Count:=0 Else UF_Count := UF_Count+1 EndIf EndIf Fig. 4d är ett flödesdiagram som åskådliggör stegen för beräkning av explicit hastighet. Avvaktan på anländande av RM- celler representeras av ett block 460 och pil 462 för fortsätt- väntatillstånd. Om en RM-cell mottages, antytt med pil 464, sker bestämning av identitet hos grupp Gii steg 466 för att möjlig- göra val av relevanta konstanter aioch br Därpå följer summe- ring av alla mottagna kövärden i steg 468 om den alternativa kölängdberäkningen ej skall användas, jfr. asterisk * i blocket för steg 468, och i pseudokoden (c6) nedan.

I steg 470 och 472 följer operationer för beräkning av explicit hastighet xflt) enligt formel (l) i utgångsanordningen 224. I steg 470 beräknas en ändringsfaktor för konflikthastig- heten y(t), och i steg 472 beräknas explicithastighetsvärdet genom multiplicering av ändringsfaktorn med aktuell konflikt- 508 284 18 hastighet y(t). 4 I steg 474 tilldelas det beräknade explicithastighets- värdet till ER-fältet hos en tillbakariktad RM-cell, som anländer till väljaren, om inte ett lägre ER-värde redan tilldelats till detta ER-fält. Detta uttrycks genom uttrycket Min(RM(ER),ExplicitRate), som ingår i blocket för steg 474. Steg 474 följs av retur till väntatillstånd 460, 462 enligt pil 476.

Pseudokoden (c6) nedan hänför sig till stegen i fig. 4d.

If Backward RM cell received i := Group id for connection (c6) Qtot := Sum(Q) ChangeFactor:=1-a(i)*(1-Rho*C/ytot) - b(i)*(Qtot -M)/ytot ExplicitRate := y * ChangeFactor RM (ER) := Min(RM(ER),Exp1icitRate) Endïf Fig. 5 visar ett mera detaljerat blockschema över ingångsanordníngen 206¿i fig. 2. Från den ej visade källan anländande celler inträder, enligt pil 202 (fig. 2), i en funktion 502, som utför operationer på ATM-cellhuvudet.

Funktionen 502 innehåller grundläggande ATM-funktioner såsom VPI/VCI (Virtual Path Identifier/Virtual Channel Identifier) -översättning, PTI (Payload Type Indicator) -operationer, som adderar väljarinterncellformat. Block 504 och 506 representerar en cellankomsträknare resp. kölängdräknare, som skall styras av funktionen 502 för ATM-cellhuvudoperationer, indikerat med pilar 508 resp. 510.

Med hänvisning till flödesdiagrammet i fig. 3a, tar funktionen 502 hand om vänttillståndet enligt stegen 302, 303, och räknarna 504 och 506 utför stegens 306 och 308 operationer.

Såsom angetts tidigare, används steget 308 inte om alternativ kölängdberäkning används och därför är räknaren 506 överflödig i detta fall.

Cellankomsträknaren 504 består av N separata räkne- register, ett för var och en av de N utgångsportarna hos väljaren 212. För varje anländ ABR-cell stegas ett motsvarande av dessa räkneregister enligt steg 306 och såsom uttrycks i rad 2 i kodblocket (cl) för att åstadkomma ankomstcellräknevärdet Cyp Vid transmission av ABR-cellen återställs registret till noll som del av steg 316 och såsom uttrycks av rad 3 hos kod- blocket (c2) ovan.

Kölängdräknaren 506 innefattar, om den används, N separata räkneregister, ett för var och en av de N utgångs- portarna hos väljaren 212. För varje anländ ABR-cell stegas ett motsvarande av dessa räkneregister upp enligt steg 308 och såsom 568 284 19 uttrycks på rad 3 i kodblocket (cl) för att åstadkomma köcell- räknevärdet Q? Vid transmission av ABR-cellen stegas registret ned som del av steg 318 och såsom uttrycks på rad 4 i kodblocket (c2).

Ett buffertminne 512 mottager, pil 514, cellerna från funktionen 502 och lagrar dessa celler logiskt per utgångsport för att undvika linjehuvudblockering (head of line blocking).

Högre prioritet ges åt celler från CBR- och VBR-förbindelser, t.ex. genom att implementera ett huvudlinjeprioritetsförfarande.

En cellschemaläggare 516 är ansluten till räknarna 504 och 506 för ömsesidig styrning, såsom indikeras av dubbla pilar 518 resp. 520. Cellschemaläggaren 516 hämtar, indikerat med pil 522, celler från buffertminnet 512 på sådant sätt att det alltid kommer att finnas en cell (CBR, VBR eller ABR) i varje till utgångsporten sänd celltidlucka, som härrör från en av de logiska ingångsbuffertarna. Det enda villkoret där detta ej är fallet uppträder om alla utgångsbuffertarna blockeras samtidigt, dvs. den interna flödesstyrningen stoppar flödet från alla ingångsanordningar. Om en cellucka är tillåten för transmission av en ABR-cell till utgångsporten i och om den alternativa kölängdberäkningen ej används, tilldelas de aktuella värdena Cyi och Qihos cellankomsträknarens 504 register i resp. kölängd- räknares 506 register i, till de respektive fälten hos intern- cellformatet enligt stegen 316 och 318 i fig. 3b. Efter tilldel- ningen återställer cellschemaläggaren 516 cellankomsträknarens 504 register i till noll och stegar ned kölängdräknarens 506 register i som del av dessa steg och som beskrivits ovan. Om den alternativa kölängdberäkningen används, finns det ingen kölängd- räknare och därför utelämnas de därmed förbundna stegen.

En väljarport 524 mottager, pil 526, celler från cell- schemaläggaren 516 och hanterar överföringen av varje cell (CBR, VBR, ABR) till väljarkärnan enligt pil 216 (fig. 2).

Fig. 6 är ett blockschema, som åskådliggör utgångsanord- ningen 224 och funktionen 230 i fig. 2 i större detalj. Cell- flödena 222 och 226, jfr. fig. 2, ingår i fig. 6. Inläsning av cellräknevärdet Cyioch kölängden Qh den senare ifall den alter- nativa metoden för kölängdberäkning ej används, i de anländande internformatfälten 228 (fig. 2) indikeras med ett block 602 och pilar 604 resp. 606. De lästa CW-värdena adderas enligt steg 406 i fig. 4a och till rad 2 i kodblocket (c3) i en adderings- funktion 608 för att bilda ett totalankomsthastighetsräknevärde.

De lästa värdena Qienligt rad 3 i kodblocket (c3) lagras i kö- längdregister 610LN.

I adderingsfunktionen 608 lagras ett sammanlagt räkne- 508 284 20 värde enligt steg 406 i fig. 4a hos alla ABR-cellankomster vid en utgångsport. När ett förutbestämt antal celler mottages, såsom bestäms av steg 410 och beräknas enligt rad 5 i kodblocket (c3), beräknas ett hastighetsmätvärde i form av ett förhållande av funktionen 608 enligt stegen 414 och 416, och raderna 6 och 7 i kodblocket (c3), dvs. yun beräknas. Alternativt triggar överskridande av ett maximumtidsvärde beräkningen såsom signa- leras enligt pil 611 från en cellräknare 612. Cellräknaren 612 räknar, indikerat med pil 613, de i flödet 222 synkront anländ- ande cellerna i form av CBR, VBR, ABR eller otilldelade celler, och används som en klockfunktion för att hålla reda på maximum- tiden för beräkning av varje ingångshastighet ymtav funktionen 608.

Den tillgängliga utgångshastigheten C för ABR-celler beräknas av en funktion 614. Funktionen 614 räknar, pil 615, antalet sända celler NoSentHP av högre prioritet genom identi- fiering av celler hörande till en VBR-förbindelse, och är anslu- ten till celllräknaren 612 för att hålla reda på tidsperioden Hptimelimit. Funktionen 614 har även tillgång till värdet på statiskt tilldelad bandbredd StaticAlloc för CBR-trafik.

Kölängdvärdena Qilagras i vardera ett av registren 610LN och ett totalt räknevärde summeras från deras innehåll, enligt den första raden i blocket för steg 408 samt rad 3 i kodblocket (c3).

Om den alternativa metoden för beräkning av kölängd används, kommer kölängdregistren 61OLN samt läsning och summering av kölängdvärden Qiatt ersättas med ett enda register

[610] anslutet, enligt den streckade pilen 6lO', till adderings- funktionen 608 för mottagning av det totala räknevärdet enligt steg 406. Det enda registret [610] kommer att uppdateras enligt andra raden i blocket för steg 408 och rad 4 i kodblocket (c3).

Innehållet i CCR-fältet hos varje RM-cell, som passerar igenom utgångsanordningen 224 i flödet 222, läses, indikerat genom block 616 och pil 617, av en medelvärdesbildningsfunktion 618. Bestämningen enligt steg 448 i fig. 4c utförs. Under förut- sättning av att något av villkoren i detta steg uppfylls utförs en exponentiell medelvärdesbildning av CCR-värdena i steg 450 följt av steg 454 i funktionen 618 enligt formeln (2) och såsom uttrycks i raderna 3 och 4 i kodblocket (c5). Denna medelvärdes- bildning används som en approximation av den rättvisa fördel- ningshastigheten hos väljaren 212 (fig. 2). Om villkoren i steg 448 ej uppfylls ersätter steg 452 stegen 450 och 454.

Om ett ER-värde skall beräknas, är räknevärdet och det erbjudna hastighetsvärdet hos funktionen 608, rättvisa hastig- 508 284 2] hetsvärdet hos medelvärdesbildningsfunktionen 618, den tillgäng- liga utgångshastigheten C hos funktionen 614, samt Qun tillgäng- liga, indikerat genom pilar 620, 622, 623 resp. 624, för en ER- beräkningsfunktion 626. Såsom framgår av ovanstående beräknas Qmt antingen som summan av innehåll hos alla register 610LN eller, om den alternativa metoden används, det uppdaterade inne-hållet hos ett enda register [610].

ER-beräkningen utförs för varje ankomst av en tillbaka- riktad RM-cell, bestämt av steg 460 i fig. 4d. Konsekutiv beräk- ning skulle emellertid kunna grunda sig på samma värde om RM- celler anländer tätt efter varandra. Beroende på grupp Giav förbindelser till vilka RM-cellen hör, såsom bestämt av steg 466, erhålls ett par proportionella konstanter a och b, dubbelpil 628, från ett register 630. Den tillgängliga hastig- heten C(t) beräknas enligt steg 436 föregånget av stegen 422-434 och avslutas av steg 438 i fig. 4b, jfr. även kodblocket (c4).

Beräkningen av den explicita hastigheten utförs enligt stegen 470 och 472 föregånget av steg 468 i fig. 4d.

Ett block 632 och en dubbelpil 634 till ER-beräknings- funktionen 626 indikerar läsning och skrivning av tillbaka- riktade RM-celler enligt stegen 460 resp. 474. Blocket 632 kan även innehålla en funktion som medger införing av nya tillbaka- riktade RM-celler om så erfordras, om tidsintervallet mellan från källan anländande RM-celler blir för långt.

Det transienta uppförandet hos ett system av det ovan med hänvisning till fig. 1-6 beskrivna slaget tillsammans med formlerna (1) och (2) kommer nu att diskuteras. För detta ändamål kommer flödesapproximationer av systemet enligt fig. 7 och 8 att användas. I fig. 7 visas systemet i blockschemaform vari ingångs- och utgångssignaler approximeras med kontinuerliga funktioner. Vissa av signalerna och funktionerna har beskrivits i föregående avsnitt.

Med avseende på ingångshastigheten, eller i själva verket kölängdhastigheten, är styralgoritmen enligt formel (1) en pro- portionell och integrerande (PI) algoritm där a är konstanten för den proportionella termen och b konstanten för den integre- rande termen. Följaktligen kommer kölängden att styras av en term med köderivatan motsvarande den proportionella termen, och en proportionell term (PD) motsvarande den integrerande termen med avseende på hastigheten. Beroende på vad som studeras arbe- tar styrningen sålunda antingen som en PI- eller PD-algoritm.

I fig. 7 representerar ett block 702 en funktion för beräkning av explicit hastighetsvärde och åstadkommande som utgång, flödespil 704, explicithastighetsvärdet x(t). Explicit- 508 284 22 hastighetsvärdet x(t) sänds tillbaka enligt flödespil 706 till källändsystemet. Närmare bestämt överlagras det explicita hastighetsvärdet x(t), påverkat av utbredningsfördröjningen dl, i en adderingsfunktion 708 på en signal ät, som mottages vid adderingsfunktionen 708 enligt flödespil 710. Resultatet, enligt flödespil 712, av överlagringen påverkas av utbredningsfördröj- ningen d4 för bildande av signalen nt, flödespil 714.

Signalens mt bakgrund är den följande. Varje styrslinga kommer att återföra hastighetsvärdet som källorna skall använda vid sändning för anpassning till stockning, dvs. x(t) av formeln (1). Det kan emellertid vara lämpligt att i modellen införa avvikelser från den ideala ingångssignalen källan kanske kan tillhandahålla genom att t.ex. sända med lägre hastighet eller inte alls. Denna avvikelse modelleras med hjälp av signalen i(t) i ändamål att införa generalitet i modellen. Vidare har under startfasen av förbindelsen ingen styrslinga upprättats eftersom inga RM-celler har returnerats ännu. I detta fall sänder källor- na med den s.k. inledningshastigheten ICR.

Signalen n(t) representerar ingångshastigheten från förbindelsen j och approximeras, i systemet, av en exponentiell medelvärdesbildning enligt formeln (2). I föregående beskrivning av algoritmen togs ingen hänsyn till ingångshastigheterna, var- för sålunda yflt) motsvarar y(t) i (l).

Signalen yF.bildar en ingång till funktionen 702 enligt pil 716 och till en adderingsfunktion 718 för att ta emot en signal N(t) bildande en annan ingång till adderingsfunktionen 718 enligt pil 720. Signalen N(t) modellerar trafiken från andra förbindelser. Om det finns Nvc aktiva förbindelser gäller NVC-l m N(t) = yjm j=l Utgångsflödet, indikerat med pil 724, från adderings- funktionen 718 är signalen ywdt) som bildar en annan ingång enligt pil 722 till funktionen 702, och en ingång enligt en pil 724 till en subtraheringsfunktion 726. Bandbreddskapaciteten eller tillgängliga hastigheten C(t) är en ytterligare ingång enligt pil 728 till subtraheringsfunktionen 726.

I en strömningsflödesmodell kan buffertbeläggningen eller kölängden Q(t) uttryckas som den positiva sidan av en integra- tion av den totala ingångshastigheten y“n(t) subtraherad med den tillgängliga hastigheten C(t). Subtraheringsfunktionen 726 åstadkommer skillnaden y“n(t)-C(t), som bildar en ingång enligt 508 284 23 pil 729 till en integrerande funktion 730, som utför integra- tionen av denna skillnad, dvs. (4) Q(t) = max {(YKn(t) ' C(t)dt,0} + Q(t0) Utgången Q(t) från funktionen 730 bildar en ingång enligt pil 732 till en subtraherande funktion 734 vilken som en ytter- ligare ingång mottager kölängdreferensen M enligt pil 736 och åstadkommer skillnaden Q(t)-M. Denna skillnad bildar enligt pil 738 en ytterligare ingång till funktionen 702.

För positiva kövärden av formeln (4) kommer derivatan av kölängden att vara (5) dQ(t)/dt = Y«n(t) _ Cít) I analysen av systemet antas antalet aktiva och kö- bildande förbindelser, Nvc, att vara konstant under transienter och alla förbindelser antas ha samma fördröjningar i slingan.

Vidare antas också ingångshastigheterna per förbindelse vara lika, vilket leder till följande approximation: (6) Ytoflt) z NVC * yj(t) Den explicita hastigheten x(t), jfr. formel (1) och köderivatan kan nu skrivas om som E§iEl} _ b ( Ql&l_:_M} (7) X(t) = Xflt)'a{Xflt)' NVC Nvc och d Qlšl (a) íl/É atom) = yJ-(c) - NVC Styrslingan kan nu slutas enligt fig. 7. För att ge ett explicit uttryck på kölängden har Laplace-transformer av de kontinuerliga funktionerna använts. Slututtrycket för kölängden ges i ekvationen Nvc * I(s)e (d_dl)s + {l+a(p-1)-e dS}C(s) + bm <9) Q = , S seub - (l - a) s + b Fig. 8 anger styrslingan i blockschemaform med användning av de Laplace-transformerade signalerna.

Nollpunkterna för nämnaren hos ekvation (9) kommer att vara avgörande för systemets uppförande och en stabilitetsanalys 508 284 24 har även utförts för att fastställa riktlinjer för inställning av parametrarna a och b. För ett givet värde a (bör vara i områ- det 0,1) kan det visas att följande gräns gäller för b-värdet för erhållande av ett stabilt system. 1-(1-3) l-(l-a) b<------ * atan d (l-a) (10) Det bör dock anmärkas att detta gäller för ett system med lika fördröjningar. Ett antal olika fördröjningar kommer att förorsaka olika uppförande och inställningen av ai- och bi- parametrarna i sådana fall bör ske med nödvändiga marginaler och stödjas av simuleringar.

Uttrycket ovan anger att b måste anpassas till fördröj- ningen i slingan.

Fig. 9 är ett diagram över de proportionella konstanterna a och b för olika källa-till-väljarsändningsfördröjningar d, varvid x-axeln och y-axeln visar a resp. b. En ökning av för- dröjningen d leder till en omvänd proportionell minskning av konstanten b. Notera att fig. 9 visar maximumvärden för b för varje värde av a som håller en upprättad styrslinga stabil. När d är av samma storleksordning som tidskillnaden mellan två an- komster av tillbakariktade RM-celler minskar emellertid nog- grannheten hos den linjära modellen, vilket resulterar i ett lägre b-värde. Simulering visar att för a satt till 0,8, värden på b bör vara mindre än 1 för att undvika svängningar.

Fig. lOa-b och lla-b visar kurvor erhållna som resultat av simuleringar av ett fall, i en struktur av ovan med hänvis- ning till fig. 2-6 beskrivet slag, där fyra källor börjar sända med en inledande cellhastighet(ICR) = 150 celler/ms (63,6 Mbps) vardera. Fig. l0a och lla visar på y-axeln den tillåtna cellhas- tigheten ACR i celler/ms. Fig. 10b och llb visar på x-axeln tiden T i ms. Vid båda simuleringarna var källa-till-väljar- sändningsfördröjningen d 5 ms och den hastighetsproportionella konstanten a var satt till 0,8. I fig. 10 är konstanten b satt till 0,1, vilken enligt fig. 9 är ett stabilt område för styr- slingan. Som väntat uppvisar transienten ej några svängningar.

Simuleringskurvorna i fig. 11 har b=0,3, vilket ger en ostabil styrslinga med odämpade svängningar.

En komparativ simulering av en algoritm beskriven i A.W.

Barnhart, Hughes Network Systems, ATM Forum Contribution 95- 0195, February 1995, “Example Switch Algorithm for Section 5.4 of TM Spec.", nämnd tidigare, visas i fig. l2a och b, som visar kurvor i koordinatsystem liknande de enligt fig. lOa, 11a resp. 508 284 25 10b, llb. Den algoritm, på vilken fig. 12 är baserad ger en långsammare konvergens mot den rättvisa fördelningshastigheten än algoritmen enligt formel (1), men förblir stationär vid den rättvisa fördelningen när den uppnås för det valda förstärk- ningsvärdet (G=0.006). Såsom indikerats tidigare, förorsakar högre förstärkningsvärden odämpad svängning runt den rättvisa fördelningshastigheten.

Beskrivningen hittills ovan förutsätter enbart FIFO- schemaläggning, men algoritmen kan modifieras till att arbeta i samband med rättvist köande.

I korthet strävar rättvist köande, benämnt FQ (Fair Queueing) nedan, efter att tillhandahålla lika delning av utgångsresurserna hos en väljaranordning, t.ex. utgångslänk- bandbredden. I motsats till ett FIFO-schemaläggningsförfarande, kan trafik som anländer till en FQ-väljare betjänas tidigare än trafik som anlände vid en tidigare tidpunkt. Ett rättframt sätt att implementera ett FQ-system är att ha individuella köer för varje förbindelse i väljaren och betjäna dessa cykliskt, genom att ge varje förbindelse (session) var sin betjäningstidlucka.

Närmare bestämt skulle för ett ATM-nät en sådan tidlucka kunna vara en cell, dvs. en cell från varje aktiv ATM-förbindelse sänds på ett cykliskt sätt, vilket även brukar benämnas "round robin scheduling". Denna typ av mekanism undviker tillstånd där en skurartad källa belägger hela utgångskapaciteten under långa tidsperioder, vilket väl kan hända i ett FIFO-fall. För närmare detaljer beträffande FQ, hänvisas till nedan angivna rapporter, i vilka olika alternativa metoder för att åstadkomma rättvist köande beskrivits och analyserats.

S. Golestani, "A Self-Clocked Fair Queueing Scheme for Broadband Applications", Infocom 1994.

K.Parekh, R. Gallager, "A generalized Processor Sharing Approach to Flow Control in Integrated Services Network: The Single Node Case", IEE/ACM Transactions on Networking, Vol. 1, No 3, June 1993.

Huvudskillnaden, jämfört med ett FIFO-schemaläggnings- förfarande, med användning av uppfinningen i en FQ-väljare är att det är möjligt att styra beläggningen i de individuella VC- köerna. Dessutom är det möjligt att härleda den verkliga rätt- visa fördelningshastigheten hos väljare genom att mäta utgångs- hastigheten hos en förbindelse. Detta gäller emellertid endast om det finns celler i köerna, dvs. väljarens last är 1. Det är därför betydelsefullt att explicithastighetsvärdet, som sänts tillbaka till källändsystemet står i relation till väljarens aktuella rättvisa fördelning. Annars kommer vissa förbindelser att erhålla större delar av bandbredd än andra, eftersom “round 508 284 26 robin scheduling" ej medför rättvis fördelning av länkkapacitet om det inte finns några celler i alla köer hela tiden.

Med last avses här och konventionellt verklig utgångs- hastighet från ett system i förhållande till systemets maximala utgångshastighet, dvs. om celler sänds in i systemet med en hastighet, som är lika med eller större än hos utgångslänken, kommer lasten att vara 1 (eller 100%). I rättvist köandefallet, som kommer att beskrivas närmare nedan, är det inte fråga om den totala ingångshastigheten (ym0 till systemet och att hänföra denna till länkhastigheten i “ändringsfaktorn" såsom i FIFO- fallet. Med användning av trafikteoretiska termer, avses uppträdande trafik (carried traffic) i rättvist köandefallet, och erbjuden trafik avses i FIFO-fallet (begreppet trafik mäts i Erlang och används väsentligen alltid i väljarsammanhang som ett kapacitetsmått).

Med några mindre ändringar kan samma modell för styr- slingan som för FIFO-fallet användas även i FQ-fallet. Signalen N(t) sätts till noll, eftersom inga andra förbindelser använder kön. Inverkan av de andra aktiva förbindelserna observeras istället i den tillgängliga hastigheten, som kommer att variera linjärt med antalet aktiva förbindelser. Den resulterande ut- gångskapaciteten för varje förbindelse kommer att påverkas av antalet andra aktiva ABR-förbindelser (FQ arbetar på varje för- bindelse) plus naturligtvis inverkan av VBR och CBR. Som nämnts används erbjuden trafik ej längre som del av ändringsfaktorn, utan nu används pågående trafik, eller med andra ord, lasten på systemet.

I den version av uppfinningen, som hänför sig till FQ- väljaren beräknas den explicita hastigheten enligt Qšêi }_b{Q-LLL_;_M; }] måx(r-(t ) (11) x(t) = max(rj(t))[1-a{1 - Û där ¶(t)är rättvisa fördelnings- eller utgångshastigheten för förbindelse j, och p(t) är den totala lasten på utgångslänken beräknad som kvoten: antalet sända ABR-celler per tidsenhet/an- talet tillfällen att sända en ABR-oell per tidsenhet. Lasten kommer sålunda att bli 1 om alla tillfällen av tillåtelse att sända en cell används. Istället för att mäta ingångshastigheten yun som i FQ-fallet, mäts lasten på bufferten, p(t), vilket motsvarar den pågående trafiken. I ovanstående formel står detta mått i relation till en föredragen referenslast, som utgör den önskade lasten på systemet. När lasten p(t) är lägre än refe- renslasten bidrar termen med ett positivt värde till att öka lasten. Kölängden mäts på en per förbindelsebasis, vilket är 508 284 27 möjligt i en FQ-omgivning. Maximal operation utförd på de indi- viduella förbindelseuthastigheterna rj(t) sker i ändamål att finna väljarens gemensamma rättvisa fördelningshastighet och sålunda undvika en divergens i de individuella förbindelse- hastigheterna. Skälet till att hänföra ändringsfaktorn till ett värde för alla förbindelser är att det finns risk för att för- bindelserna strävar mot olika hastigheter, dvs. att ändrings- faktorvärdet rör sig mot 1 men de tillhörande förbindelserna har uppnått olika hastigheter. Ehuru ekvationssystemet har flera olika lösningar för stationärt tillstånd, är med andra ord en önskvärd här, i vilken alla hastigheter är lika.

En utföringsform av ER-beräkning för ett FQ-system där alla operationer sker i ingångsporten kommer nu att beskrivas med hänvisning till fig. 13 och 14.

Fig. 13 är en schematisk vy, liknande fig. 2, av ingångs- porten visande del av en tvåvägsförbindelse, som sträcker sig igenom en väljare mellan en källa och destination. I fig. 13 indikerar en pil 1302 celler som anländer från en källa, ej visad, vid en logisk ingångsbuffert 1304 hos ingångsporten, betecknad 1306? Ingångsporten 130q är en av ett antal ingångs- portar 1306LN, som hör till väljaren, indikerad vid 1312. Alla dessa portar innehåller logiska ingångsbuffertar, såsom buffer- ten 1304. Vid varje ingångsport räknas antalet köande celler för att åstadkomma ett räknevärde Qiför köande celler. Celler som lämnar bufferten 1304 och inträder i en utgångsbuffert 1314 belägen i utgångsporten, som ej visas, hos väljaren 1312 indike- ras med en pil 1316. Den bufferten 1314 innefattande utgångs- porten är en av N utgångsportar hörande till väljaren 1312.

Pilar 1318 och 1320 indikerar cellflöden från de logiska buffer- tarna hos andra av ingångsportarna 1306LN, vilka även inträder i samma väljarutgångsbuffert 1314.

Celler som returneras av destinationen i tillbakarikt- ningen genom väljaren 1312 och ingångsporten 1306 indikeras med en pil 1322.

I ingångsporten 1306 sker beräkning av verklig explicit hastighet och tilldelning av tillbakariktad RM-cell i en funk- tion indikerad med ett block 1324. En pil 1326, som pekar mot blocket 1324, indikerar överföring av Qfräknevärdet. En dubbel- pil 1328 mellan pilen 1322 och blocket 1324 indikerar läs- och skrivoperationer på en tillbakariktad RM-cell.

Pig. 14 visar ett mera detaljerat blockschema över ingångsporten 130% i fig. 13. Celler som anländer från källan, ej visad, inträder enligt pil 1302 (fig. 13), i en funktion 1402, som utför ATM-cellhuvudoperationer. Funktionen 1402 inne- 508 284 28 håller grundläggande ATM-funktioner såsom VPI/VCI (Virtual Path Identifier/Virtual Channel Identifier)-översättning, PTI (Payload Type Indicator)-operationer, som adderar väljarintern- cellformat. Ett block 1406 representerar en kölängdräknare, som styrs av funktionen 1402 för utförande av ATM-cellhuvud- operationer, indikerat med pil 1410.

Kölängdräknaren 1406 stegas fram för varje anländ ABR- cell för att åstadkomma köande-cellräknevärdet Qp Vid sändning av ABR-cellen stegas registret ned.

Ett buffertminne 1412 mottager, pil 1414, cellerna från funktionen 1402 och lagrar dessa celler logiskt per utgångsport för att undvika "head of line"-blockering. Högre prioritet ges åt celler från CBR- och VBR-förbindelser, t.ex. genom att imple- mentera ett "head of line"-prioritetsschema.

En cellschemaläggare 1416 är ansluten till räknaren 1406 för ömsesidig styrning, såsom indikeras av dubbelpil 1420. Cell- schemaläggaren 1416 hämtar, indikerat med pil 1452, celler från _ buffertminnet 1412 på ett sådan sätt att det alltid kommer att finnas en cell (CBR, VBR eller ABR) i varje celltidlucka som sänds till väljarens utgångsport och härrör från den logiska ingångsbufferten 1304. Cellschemaläggaren 1416 är koordinerad med motsvarande cellschemaläggare hos alla ingångar, vilket innebär att den kan räkna tiden T för varje nytt "svep" över förbindelserna som FQ-algoritmen gör (en cell från varje förbin- delse sänds ut). 1/T ger därvid rättvisa fördelningshastigheten rfit) som systemet har för tillfället mot en viss utgång. Vidare beräknas lasten p(t) på utgångslänken 1316 som kvoten antalet sända ABR-celler per tidsenhet/antalet tillfällen att sända en ABR-cell per tidsenhet, såsom nämnts tidigare. Detta sker sepa- rat för varje ingångsbuffert 1304, men om FQ-algoritmen arbetar som den bör, ger detta ett mått på den totala lasten på utgången från utgångsbufferten 1314.

När ett ER-värde skall kalkyleras är räknevärdet i kö- längdräknaren tillgängligt, indikerat med pil 1428, för en ER- beräkningsfunktion 1430. Värdena på lasten p(t) och rättvisa fördelningshastigheten rflt) är tillgängliga, pil 1432, vid FQ- cellschemaläggaren 1416.

ER-beräkningen utförs för varje ankomst av en tillbaka- riktad RM-cell 1322. En väljarport 1434 mottager, pil 1436, cellerna från cellschemaläggaren 1416 och hanterar överföringen av varje cell (CBR, VBR, ABR) in i väljarkärnan enligt pilen 1316 (fig. 13).

Ett par proportionella konstanter a och b erhålls, dubbelpil 1438, från ett register 1440. Ett block 1442 och en 508 284 29 dubbelpil 1444 till ER-beräkningsfunktionen 1430 indikerar läs- ning och skrivning av tillbakariktade RM-celler. Blocket 1442 kan även innefatta en funktion som medger införing av nya till- bakariktade RM-celler om så erfordras, om tidsintervallet mellan RM-celler härrörande från källan blir för långt. Även i FQ-fallet kan algoritmen tillämpas på ett system som medger användning av stora utgångsbuffertar, vilket innebär att koordineringen av cellschemaläggare kan uteslutas. I detta fall måste räknarvärden överföras till utgången som i FIFO- fallet, vilket innebär en viss fördröjning mellan kölängd- beräkningen vid utgången och innehållet i ingångsbuffertköerna vid en viss godtycklig tidperiod.

Claims (34)

508 284 30 Patentkrav.

1. Sätt i ett ATM-system för styrning av flöden av dataceller och flödesstyrhanteringsceller från ett antal källor till en destination över förbindelser, som passerar ett nät- element, under återsändning av flödesstyrhanteringscellerna från destinationen via nätelementet till respektive källor, varvid nämnda nätelement är utsatt för stockning på grund av konflikt mellan förbindelserna, vilken konflikt nödvändiggör köande av förbindelserna, nämnda dataceller innehåller celler av lägre prioritet och celler av högre prioritet, samt nämnda flödesstyrhanteringsceller har ett explicit- hastighetsfält för ett explicithastighetsvärde, som används för att begränsa en vid källan maximalt tillåten cellhastighet till ett specifikt värde, samt ett fält för aktuell cellhastighet för mottagning av nämnda specifika värde, innefattande utförande av följande steg i nätelementet beräkning av ett förutbestämt antal celler av högre prioritet aktuella för sändning på en utgångslänk från nätele- mentet till destinationen under notering av tidsintervallet som krävs för att utföra beräkningen för att åstadkomma en cellhastighet för celler av högre prioritet i form av ett förhållande mellan de räknade cellerna av högre prioritet och tidsintervallet, beräkning av ett tillgängligt hastighetsvärde (C) för celler av lägre prioritet som en skillnad mellan ett totalt tillgängligt länkhastighetsvärde och cellhastigheten för celler av högre prioritet, upprättande av en kölängdreferens (M) bildande en önsk- värd kölängd, beräkning av avvikelser från det tillgängliga hastighets- värdet och kölängdreferensen på grund av mottagning av varieran- de mängder celler på förbindelser i konflikt, beräkning av ett modifierat explicithastighetsvärde som en funktion av dessa avvikelser, samt införing av det modifierade explicithastighetsvärdet i explicithastighetsfältet hos de tillbakariktade flödesstyr- hanteringscellerna.

2. Sätt enligt krav 1, innefattande utförande av följande ytterligare steg i nätelementet räkning av celler som anländer från respektive källor för att alstra källspecifika cellräknevärden (Cy), räkning av de källspecifika cellräknevärdena för att alstra ett bestämt totalt räknevärde avseende mottagna celler 508 284 31 under notering av tidsintervallet som krävs för att utföra räk- ningen för att alstra ett erbjudet hastighetsvärde (ytot) som ett förhållande mellan det bestämda totalräknevärdet och ett tidsintervall, beräkning av en total kölängd (Qtot) för alla anländande celler, beräkning av avvikelsen från det tillgängliga hastighets- värdet (C) som en skillnad mellan det tillgängliga hastighets- värdet och det erbjudna hastighetsvärdet (ytot), beräkning av avvikelsen från kölängdreferensen (M) som en skillnad mellan den totala kölängden (Qtot) och kölängd- referensen (M).

3. Sätt enligt krav 2, innefattande utförande av följande ytterligare steg i nätelementet notering av ett första tillstånd som innebär att mottagna CCR-fältvärden är lika med eller större än ett tröskelvärde och ett andra villkor innebärande att ett gränsantal av mottagna CCR-fältvärden mindre än tröskelvärdet har överskridits, beräkning, förutsatt att något av dessa villkor har uppfyllts, av en konflikthastighet (y) som en exponentiell medelvärdesbildning av CCR-fältvärdena, utförande av beräkningen av explicithastighetsvärdo: under användning av konflikthastigheten som en multiplikatii' faktor.

4. Sätt enligt krav 1 eller 2, innefattande att i nätelementet utförs det ytterligare steget att multiplicera avvikelser från det tillgängliga hastighetsvärdet (C) respektim kölängdvärdet (M) med vardera en proportionell konstant.

5. Sätt enligt krav 4, innefattande att i nätelementet utförs det ytterligare steget att bestämma värdena hos de respektive konstanterna för varje par av konstanter för varje förbindelse såsom beroende på utbredningsfördröjningen i en slinga, som sträcker sig över källan och nätelementet.

6. Sätt enligt något av krav 2-5, innefattande att i nätelementet utförs det ytterligare steget att minska det tillgängliga hastighetsvärdet (C) medelst en multiplikations- faktor.

7. Sätt enligt något av krav 2-6, innefattande att i nätelementet utförs de ytterligare stegen att räkna köande celler som anländer från respektive källor för att alstra källspecifika köande cellräknevärden (Qi), samt beräkna den totala kölängden (Qtot) genom att summera alla källspecifika köande cellräknevärden.

8. Sätt enligt något av krav 2-6, innefattande att i nätelementet utförs de ytterligare stegen att räkna celler som 508 284 32 anländer från respektive källor för att alstra källspecifika cellräknevärden (Cy), beräkna den totala kölängden (Qtot) genom att summera dessa räknevärden och därifrån subtrahera 1 för varje cell som sänds på utgångslänken.

9. Styrsystem i ett ATM-system för styrning av flöden av dataceller och flödesstyrhanteringsceller från ett antal källor till en destination över förbindelser, som passerar ett nät- element, under återsändning av flödesstyrhanteringscellerna från destinationen via nätelementet till respektive källor, varvid nämnda nätelement är utsatt för stockning på grund av konflikt mellan förbindelserna, vilken konflikt nödvändiggör köande av förbindelserna, nämnda dataceller innehåller celler av lägre prioritet och celler av högre prioritet, samt nämnda flödesstyrhanteringsceller har ett explicit- hastighetsfält för ett explicithastighetsvärde, som används för att begränsa en vid källan maximalt tillåten cellhastighet till ett specifikt värde, samt ett fält för aktuell cellhastighet för mottagning av nämnda specifika värde, innefattande medel (614) för beräkning av ett förutbestämt antal celler av högre prioritet aktuella för sändning på en utgångslänk från nät- elementet till destinationen under notering av tidsintervallet som krävs för att utföra beräkningen för att åstadkomma en cellhastighet för celler av högre prioritet i form av ett förhållande mellan de räknade cellerna av högre prioritet och tidsintervallet, medel (626) för beräkning av ett tillgängligt hastighetsvärde (C) för celler av lägre prioritet som en skillnad mellan ett totalt tillgängligt länkhastighetsvärde och cellhastigheten för celler av högre prioritet, upprättande av en kölängdreferens (M) bildande en önskvärd kölängd, beräkning av avvikelser från det tillgängliga hastighets- värdet och kölängdreferensen på grund av mottagning av varieran- de mängder celler på förbindelser i konflikt, beräkning av ett modifierat explicithastighetsvärde som en funktion av dessa avvikelser, samt införing av det modifierade explicithastighetsvärdet i explicithastighetsfältet hos de tillbakariktade flödesstyrhan- teringscellerna.

10. System enligt krav 9, innefattande medel (504) för räkning av celler som anländer från respektive källor för att alstra källspecifika cellräknevärden (Cy), 508 284 33 medel (608) för räkning av de källspecifika cellräkne- värdena för att alstra ett bestämt totalt räknevärde avseende mottagna celler under notering av tidsintervallet som krävs för att utföra räkningen för att alstra ett erbjudet hastighetsvärde (ytot) som ett förhållande mellan det bestämda totalräknevärdet och ett tidsintervall, samt medel (626) för beräkning av en total kölängd (Qtot) för alla anländande celler, beräkning av avvikelsen från det tillgängliga hastighets- värdet (C) som en skillnad mellan det tillgängliga hastighets- värdet och det erbjudna hastighetsvärdet (ytot), beräkning av avvikelsen från kölängdreferensen (M) som en skillnad mellan den totala kölängden (Qtot) och kölängd- referensen (M).

11. System enligt krav 10, innefattande medel (626) för notering av ett första tillstånd som innebär att mottagna CCR-fältvärden är lika med eller större än ett tröskelvärde och ett andra villkor innebärande att ett gränsantal av mottagna CCR-fältvärden mindre än tröskelvärdet har överskridits, beräkning, förutsatt att något av dessa villkor har uppfyllts, av en konflikthastighet (y) som en exponentiell medelvärdesbildning av CCR-fältvärdena, utförande av beräkningen av explicithastighetsvärdet under användning av konflikthastigheten som en multiplikations- faktor.

12. System enligt krav 9 eller 10, innefattande medel (626) för att multiplicera avvikelser från det tillgängliga hastighetsvärdet (C) respektive kölängdvärdet (M) med vardera en proportionell konstant.

13. System enligt krav 12, innefattande medel (626) för att bestämma värdena hos de respektive konstanterna för varje par av konstanter för varje förbindelse såsom beroende på utbredningsfördröjningen i en slinga, som sträcker sig över källan och nätelementet.

14. System enligt något av krav 10-13, innefattande medel (626) för att minska det tillgängliga hastighetsvärdet (C) medelst en multiplikationsfaktor.

15. System enligt något av krav 10-14, innefattande medel (610) för att räkna köande celler som anländer från respektive källor för att alstra källspecifika köandecellräkne- värden (Cy), samt beräkna den totala kölängden (Qtot) genom att summera alla källspecifika köandecellräknevärden.

16. System enligt något av krav 10-14, innefattande medel (608) för att räkna celler som anländer från respektive källor för att alstra källspecifika cellräknevärden (Cy), 508 284 34 beräkna den totala kölängden (Qtot) genom att summera dessa räknevärden och därifrån subtrahera 1 för varje cell som sänds på utgångslänken.

17. Sätt i ett ATM-system för styrning av flöden av dataceller och flödesstyrhanteringsceller från ett antal källor till en destination över förbindelser, som passerar en utgångs- buffert hos en väljare, under återsändning av flödesstyrhante- ringscellerna från destinationen via väljaren till respektive källor, varvid nämnda utgångsbuffert är utsatt för stockning på grund av konflikt mellan förbindelserna, vilken konflikt nödvändiggör köande av förbindelserna, nämnda dataceller innehåller celler av lägre prioritet och celler av högre prioritet, samt nämnda flödesstyrhanteringsceller har ett explicit- hastighetsfält för ett explicithastighetsvärde, som används för att begränsa en vid källan maximalt tillåten cellhastighet till ett specifikt värde, samt ett fält för aktuell cellhastighet för mottagning av nämnda specifika värde, innefattande utförande av följande steg i nätelementet fastställande av värden på en sats parametrar och variabler innefattande y(t): en konflikthastighet vid utgångsbufferten vid tid- punkten t, y“n(t): en uppmätt erbjuden hastighet till utgångs- bufferten vid tidpunkten t, C(t): tillgänglig hastighet vid bufferten för lågpriori- terade celler vid tidpunkten t, Q(t): total kölängd vid bufferten vid tidpunkten t, p: del av en eftersträvad tillgänglig hastighet vid bufferten, M: en buffertkölängd-referens, q och bg proportionella konstanter för en förbindelse i, som passerar utgångsbufferten, bestämning av explicithastighetsvärdet xgt) vid tid- punkten t för förbindelsen i som Xi: = y u-aiu _ gitïáíßgtfl _ bißgztiålt-Eq H tilldelning av explicithastighetsvärdet gt till explicithastighetsfältet hos en tillbakariktad flödesstyr- hanteringscell.

18. Sätt enligt krav 17, innefattande utförande av följande ytterligare steg i nätelementet 508 284 35 räkning av celler som anländer från respektive källor för att alstra källspecifika cellräknevärden (Cy), A räkning av de källspecifika cellräknevärdena för att alstra ett bestämt totalt räknevärde avseende mottagna celler under notering av tidsintervallet som krävs för att utföra räkningen för att alstra ett erbjudet hastighetsvärde (ytot) som ett förhållande mellan det bestämda totalräknevärdet och ett tidsintervall.

19. Sätt enligt krav 18, innefattande utförande av följande ytterligare steg i nätelementet notering av ett första tillstånd som innebär att mottagna CCR-fältvärden är lika med eller större än ett tröskelvärde och ett andra villkor innebärande att ett gränsantal av mottagna CCR-fältvärden mindre än tröskelvärdet har överskridits, beräkning, förutsatt att något av dessa villkor har uppfyllts, av konflikthastigheten (y) som en exponentiell medelvärdesbildning av CCR-fältvärdena.

20. Sätt enligt krav 19, innefattande bestämning av värdena hos de respektive konstanterna a och b såsom beroende på utbredningsfördröjningen i en slinga, som sträcker sig över väljaren och källan från vilken förbindelsen i börjar.

21. Sätt enligt något av krav 18-20, innefattande stegen att räkna köande celler som anländer från respektive källor för att alstra källspecifika köande cellräknevärden (Cy), samt beräkna den totala kölängden (Qtot) genom att summera alla käll- specifika köande cellräknevärden.

22. Sätt enligt något av krav 18-20, innefattande stegen att räkna celler som anländer från respektive källor för att alstra källspecifika cellräknevärden (Cy), beräkna den totala kölängden (Qtot) genom att summera dessa räknevärden och däri- från subtrahera 1 för varje cell som sänds på utgångslänken.

23. Sätt i ett ATM-system för styrning av flöden av dataceller och flödesstyrhanteringsceller från ett antal källor till en destination över förbindelser, som passerar en respek- tive ingångsbuffert och en gemensam utgångsbuffert hos en välja- re med rättvist köande, under återsändning av flödesstyrhante- ringscellerna från destinationen via väljaren till respektive källor, varvid nämnda väljare är utsatt för stockning på grund av konflikt mellan förbindelserna, vilken konflikt nödvändiggör köande av förbindelserna i ingångsbuffertarna och utgångs- bufferten, nämnda flödesstyrhanteringsceller har ett explicit hastighetsfält för ett explicit hastighetsvärde, som används för att begränsa en vid källan maximalt tillåten cellhastighet till 508 284 36 ett specifikt värde, samt ett aktuellt cellhastighetsfält för mottagning av nämnda specifika värde, ' innefattande utförande av följande steg i varje ingångs- port hos väljaren: upprättande av en önskad last (pref) på utgången från ingångsbufferten, upprättande av en kölängdreferens (M) bildande en önsk- värd kölängd, beräkning av avvikelser från den önskade lasten och kölängdreferensen på grund av mottagning av varierande mängder celler på förbindelser i konflikt, beräkning av ett modifierat explicit hastighetsvärde som en funktion av dessa avvikelser, samt införing av det modifierade explicithastighetsvärdet i det explicita hastighetsfältet hos de tillbakariktade flödes- styrhanteringscellerna.

24. Sätt enligt krav 23, innefattande utförande av följande ytterligare steg i ingångsporten: i beräkning av total last (p(t)) vid tidpunkten (t) på utgången från ingångsbufferten beräknat som kvoten antalet ABR- celler mottagna vid ingångsbufferten per tidsenhet/antalet tillfällen att sända en ABR-cell per minut, beräkning av en kölängd (QHt)) för anländande celler, beräkning av avvikelsen från den önskade lasten (pref) som en skillnad mellan den önskade lasten och den aktuella lasten, beräkning av avikelsen från kölängdreferensen (M) som en skillnad mellan den beräknade kölängden (Qflt)) och kölängd- referensen (M).

25. Sätt enligt krav 24, innefattande utförande av följande ytterligare steg i ingångsporten: beräkning av en utgångshastighet (rflt))vid ingångs- bufferten för förbindelsen, utförande av beräkning av explicithastighetsvärdet under användning av utgångshastigheten som en multiplikationsfaktor.

26. Sätt enligt krav 24 eller 25, innefattande att i ingångsporten utförs det ytterligare steget att multiplicera avvikelser från den önskade lasten (pref) respektive kölängd- värdet (M) med vardera en proportionell konstant.

27. Sätt enligt krav 26, innefattande att i väljaren utförs det ytterligare steget att bestämma värdena hos de respektive konstanterna för varje par av konstanter för varje förbindelse såsom beroende på utbredningsfördröjningen i en slinga, som sträcker sig över källan och väljaren. 508 284 37

28. System i ett ATM-system för styrning av flöden av dataceller och flödesstyrhanteringsceller från ett antal källor till en destination över förbindelser, som passerar en respek- tive ingångsbuffert och en gemensam utgångsbuffert hos en välja- re med rättvist köande, under återsändning av flödesstyrhante- ringscellerna från destinationen via väljaren till respektive källor, varvid nämnda väljare är utsatt för stockning på grund av konflikt mellan förbindelserna, vilken konflikt nödvändiggör köande av förbindelserna i ingångsbuffertarna och utgångs- bufferten, nämnda flödesstyrhanteringsceller har ett explicit hastighetsfält för ett explicit hastighetsvärde, som används för att begränsa en vid källan maximalt tillåten cellhastighet till ett specifikt värde, samt ett aktuellt cellhastighetsfält för mottagning av nämnda specifika värde, innefattande i varje ingångsport hos väljaren: medel för upprättande av en önskad last (pref) på ut- gången från ingångsbufferten, medel för upprättande av en kölängdreferens (M) bildande en önskvärd kölängd, medel för beräkning av avvikelser från den önskade lasten (pref) och kölängdreferensen på grund av mottagning av varieran- de mängder celler på förbindelser i konflikt, medel för beräkning av ett modifierat explicit hastig- hetsvärde som en funktion av dessa avvikelser, samt medel för införing av det modifierade explicithastighets- värdet i explicithastighetsfältet hos de tillbakariktade flödes- styrhanteringscellerna.

29. System enligt krav 28, innefattande i ingångsporten: medel för beräkning av total last (p(t)) vid tidpunkten (t) på utgången från ingångsbufferten beräknat som kvoten antalet ABR-celler mottagna vid ingångsbufferten per tidsenhet/antalet tillfällen att sända en ABR-cell per minut, medel för beräkning av en kölängd (Qflt)) för anländande celler, medel för beräkning av avvikelsen från den önskade lasten (pref) som en skillnad mellan den önskade lasten och den aktuella lasten, medel för beräkning av avvikelsen från kölängdreferensen (M) som en skillnad mellan den beräknade kölängden (Qflt)) och kölängdreferensen (M).

30. System enligt krav 29, innefattande i ingångsporten: medel för beräkning av en utgångshastighet (rflt)) vid 508 284 38 ingångsbufferten för förbindelsen, medel för utförande av beräkning av explicithastighets- värdet under användning av utgångshastigheten som en multi- plikationsfaktor. _

31. System enligt krav 29 eller 30, innefattande medel för att multiplicera avvikelser från den önskade lasten (pref) respektive kölängdvärdet (M) med vardera en proportionell konstant.

32. System enligt krav 31, innefattande medel för att bestämma värdena hos de respektive konstanterna för varje par av konstanter för varje förbindelse såsom beroende på utbrednings- fördröjningen i en slinga, som sträcker sig över källan och väljaren.

33. Sätt i ett ATM-system för styrning av flöden av dataceller och resurshanteringsceller från ett antal källor till en destination över förbindelser, som passerar en respektive ingångsbuffert och en gemensam utgångsbuffert hos en väljare för rättvist köande, under återsändning av resursrhanteringscellerna som bakåtriktade resurshanteringsceller från destinationen via väljaren till respektive källor, varvid nämnda utgångsbuffert är utsatt för stockning på grund av konflikt mellan förbindelserna, vilken konflikt nödvändiggör köande av förbindelserna i ingångsbuffertarna och utgångs- bufferten, nämnda resurshanteringsceller har ett explicithastighets- fält för ett explicithastighetsvärde, som används för att be- gränsa en vid källan maximalt tillåten cellhastighet till ett specifikt värde, samt ett fält för aktuell cellhastighet för mottagning av nämnda specifika värde, fastställande av värden på en sats parametrar och variabler innefattande ¶(t): utgångshastighet vid tidpunkten (t) vid ingångsbufferten för förbindelse j, p(t): total last vid tidpunkten (t) vid utgången från ingångsbufferten kalkylerad som kvoten ABR-celler mottagna vid ingångsbufferten per tidsenhet/antalet tillfällen att sända en ABR-cell per tidsenhet, pref: önskad last på utgången från ingångsbufferten, q(t): kölängd vid tidpunkten (t) vid ingångsbufferten för "förbindelse j, hf kölängdreferens vid ingångsbufferten för förbindelse a och b: proportionella konstanter för förbindelse j, bestämning av explicithastighetsvärdet kflt) vid 508 284 39 tidpunkten t för förbindelsen j som XJ-(c) = maxujunni-au - 1% Hflfigäš H där max (rflt)) är en operation utförd på de individuella förbindelseutgångshastigheterna ¶(t) hos väljaren för att finna en gemensam utgångshastighet för förbindelserna som passerar den gemensamma utgångsbufferten och sålunda undvika en skillnad i de individuella förbindelsehastigheterna, tilldelning av explicithastighetsvärdet kñt) till explicithastighetsfältet hos en tillbakariktad resurshanterings- cell som passerar ingångsbufferten j.

34. Sätt enligt krav 33, innefattande bestämning av värdena på konstanterna a och b såsom beroende av utbrednings- fördröjningen i en slinga som sträcker sig över källan och väljaren.