NL9201668A

NL9201668A - Methode voor het converteren van een pollingfrequentietabel in een polling-volgordetabel.

Info

Publication number: NL9201668A
Application number: NL9201668A
Authority: NL
Original assignee: Nederland Ptt
Priority date: 1992-09-25
Filing date: 1992-09-25
Publication date: 1994-04-18
Also published as: EP0592027B1; JP2668817B2; DE69322583T2; EP0592027A1; JPH06268660A; DK0592027T3; ES2127242T3; US5623668A; DE69322583D1; ATE174740T1

Description

Methode voor het converteren van een pollingfrequentietabel in een polling-volgordetabei

A. ACHTERGROND VAN DE UITVINDING

De uitvinding heeft betrekking op een methode voor het pollen van queues met elk een in de tijd variërend en è priori onbekend aantal queue-elementen, waarbij uit queue-waarden, zoals de aantallen elementen in de verschillende queues of de toename van die aantallen queue-elementen, een ratiotabel wordt gevormd met ratiowaarden die die queuewaarden representeren, welke ratiotabel vervolgens wordt geconverteerd in een pollingvolgor-detabel met een zo regelmatig mogelijke pollingvolgorde. In het bijzonder wordt daarbij gedacht aan het pollen van ATM datacelien. Een dergelijke methode is o.m. bekend uit een publikatie van Boxma et al [1]. De daar gepresenteerde methode omvat een aantal stappen, te weten:

Stap 1: Aan de hand van queue-kenwaarden voor de verschillende queu es, zoals de queue-grootte of queue-groei wordt voor elke queue de 'occurrence ratio' (bijv. occurrence frequentie) berekend;

Stap 2: Aan de hand van de aldus berekende ratio's worden de grootte M

van de pollingtabel en per queue het absolute aantal occurrences berekend;

Stap 3: Aan de hand van de berekende tabelgrootte M en de berekende aantallen occurrences per queue wordt de polling-volgorde van de verschillende queues berekend.

In stap 3 wordt gebruik gemaakt van een 'random control policy' of van een 'golden ratio policy', beide ontleend aan studies van Hofri & Rosberg [2]. De prestaties van de 'random policy' zijn vrij beperkt. De prestaties van de 'golden ratio policy' zijn beter, echter daarvoor zijn vrij complexe mathematische bewerkingen nodig, die relatief veel tijd kosten, hetgeen voor het verwerken van ATM datacellen --die immers bedoeld zijn voor breedband toepassingen, zoals B-ISDN-- een tamelijk groot nadeel is.

B. SAMENVATTING VAN DE UITVINDING

De uitvinding beoogt een methode te verschaffen die gebaseerd is op het verwerken van gehele getallen in eenvoudige optel- en vergelijk-functies, hetgeen resulteert in een snel werkend pollingsysteem.

De uitvinding wordt gekenmerkt door de volgende stappen:

Stap 1: bereken aan de hand van de queuewaarden Q(n) de ratiowaarden R(n) in de ratiotabel;

Stap 2: bereken de som S van die ratiowaarden R(n);

Stap 3: ken aan elke queue x een correctiefactor C(x) toe die gelijk is aan die som S van de ratiowaarden, verminderd met de ratiowaarde R(x) van die queue x;

Stap 4 selecteer de queue i met de hoogste urgentiefactor U(i) of selecteer, indien meer queues die hoogste urgentiefactor U(i) hebben, één bepaalde queue i daaruit, bijvoorbeeld de eerste in de ratiotabel voorkomende queue met die hoogste urgentiefactor U(i);

Stap 5 verlaag de urgentiefactor U(i) van die geselecteerde queue i met de waarde van zijn correctiefactor C(i);

Stap 6 verhoog de urgentiefactor U(x) van de overige queues {Φ i) met hun ratiowaarde R(x);

Stap 7 herhaal vanaf stap 4 of herhaal vanaf stap 1 (zie hierna).

Men kan de pollingvolgordetabel eenmalig berekenen, rekening houdend met zich niet veranderende queuewaarden, zoals de lange termijn gemiddelde waarde voor de queue-grootte, dan wel die tabel periodiek herberekenen. E.e.a. is afhankelijk van het dynamische gedrag van de queuewaarden en van de gewenste nauwkeurigheid van het pollingsysteem. Het is dus enerzijds mogelijk de pollingtabel eenmalig te berekenen en anderzijds die tabel te herberekenen voorafgaand aan elke cyclus waarin de eerstvolgende te pollen queue wordt berekend. In het eerste geval kan van stap 7 worden 'teruggesprongen' naar stap 4, in het tweede geval moet worden teruggesprongen naar stap 1. Ook tussenvormen zijn mogelijk. Bijvoorbeeld is het mogelijk om eens per berekeningscyclus na te gaan of de queuewaarden zich gewijzigd hebben en de volgordetabel alleen te herberekenen na het detecteren van zo'n wijziging; ook kan dat om de n berekeningscycli gebeuren. Onderstaand is een voorbeeld uitgewerkt waarin om de drie berekeningscycli wordt nagegaan of de queuewaarden gewijzigd zijn en wordt alleen in dat geval een nieuwe ratiotabel, de som van de ratio's en nieuwe correctiefactoren berekend. Ook is een voorbeeld uitgewerkt waarin dit gebeurt bij elke berekeningscyclus, waardoor een maximale aanpassing van de pollingvolgordetabel aan het dynamisch gedrag van het variërende aanbod van de queue-elementen wordt bereikt.

C. REFERENTIES 1. Boxma, O.J. et al

Optimizing of polling systems Report BS-R8932

Centre for Mathematics and Computer Science, P.O.Box 4079, NL-1009AB Amsterdam 2. Hofri, M. et al

Packet delay under the golden ratio weighted TDM policy in a multiple-access channel IEEE Trans. Inform. Theory, Vol. IT-33, p. 341-349

D. UITVOERINGSVOORBEELDEN

Hierna zal de werking van de werkwijze volgens de uitvinding worden geïllustreerd. Gesteld dat er een drietal queues a, b en c is waarvan de 'arrival rate' (het aanbod van het aantal queue-elementen per tijdseenheid) op een bepaald moment is: Q(a) = 3, Q(b) = 6, Q(c) = 3. Hierna zullen de bovengenoemde stappen volgens de uitvinding worden gevolgd.

Stap 0 Ken aan elke queue x een initiële urgentiefactor U(x) toe, bijv.

U(a) = 0, U(b) = 0 en U(c) = 0.

Stap 1: De eenvoudigste ratiotabel is die waarbij de waarden voor Q(x) worden overgenomen, waardoor de ratiotabel is R(a) = 3, R(b) = 6 en R(c) = 3; Als de waarden van Q(x) bijvoorbeeld veel hoger liggen, bijvoorbeeld 3357, 5976 en 2840, kan er ook voor gekozen worden om hiervan eenvoudiger ratiogetallen af te leiden, bijvoorbeeld door de waarden van Q(x) door 1000 te delen en af te ronden naar de naastliggende gehele getallen, in dat geval weer 3, 6 en 3.

Stap 2: De som S = R(a) + R(b) + R(c) = 12;

Stap 3: De correctiefactoren C(x) worden: C(a) = 12-3 = 9, C(b) = 12 - 6 = 6 en C(c) = 12-3 = 9;

In de stappen 4, 5 en 6 wordt, gebruik makende van de in de vorige stappen berekende waarden, de eerstvolgende te pollen queue geselecteerd.

Stap 4 Alle urgentiefactoren U(x) zijn = 0 (initiële waarde); kies dan de eerste queue met die ('hoogste') waarde: queue a.

Stap 5 Verminder U(a) met de waarde van C(a): U(a) : = 0 - 9 = -9;

Stap 6 Vermeerder U(b) en U(c) met de waarde van R(b) resp. R(c): U(b) :=0 + 6= +6; U(c) :=0 + 3= +3

Stap 7 Herhaal stap 4, 5, en 6:

Stap 4 Kies queue b, die immers nu de hoogste waarde van U(x) heeft, namelijk U(b) = +6, terwijl U(a) = -9 en U(c) = +3;

Stap 5 Verminder U(b) met C(b): U(b) : = 6 - 6 = 0;

Stap 6 Vermeerder U(a) met R(a): U(a) :=-9 + 3 = -6 en U(c) met R(c): U(c) := +3 + 3 = +6;

Stap 7 Herhaal stap 4, 5 en 6:

Stap 4 Kies nu queue c, die nu de hoogste waarde van U(x) heeft, namelijk U(c) = +6, terwijl U(a) = -6 en U(b) = 0;

Stap 5 Verminder U(c) met C(c): U(c) := =6 - 9 = -3;

Stap 6 Vermeerder U(a) met R(a): U(a) :=-6 + 3 = -3 en U(b) met R(b): U(b) :=0 + 6= +6;

Stap 7 Herhaal stap 4, 5 en 6:

Enzovoort.......

Het bovenstaande kan in tabelvorm aldus worden getoond:

Queue names abc

Queue values Q(a)= 3 Q(b) = 6 Q(c)= 3

Ratio factor R= 1

Ratio values R(a)- 3 R(b)= 6 R(c)* 3

Sum ratio values S= 12

Correction values C(a)- 9 C(b)= 6 C(c)“ 9 P U(a) U(b) U(c) Selected queue (i) 1 O* O O a 2 -9 6* 3 b 3-606* c A -3 6* -3 b 5 O* O O a 6 -9 6* 3 b 7-606* c 8 -3 6* -3 b 9 O* O O a 10 -9 6* 3 b 11 -6 0 6* c 12 -3 6* -3 b 13 O* O O a IA -9 6* 3 b 15 -6 0 6* c

Bij een ratio-verdeling 3-6-3 is de berekende polling-volgorde dus a - b -c-b-a-b-c-b-a - enz. (de hoogste waarde van U(x) is met een * aangegeven). Het mag duidelijk zijn dat op het moment dat de aan de queues gemeten queuewaarden zich wijzigen, ook de pollingvolgorde zich kan wijzigen; in dat geval wijzigen zich dus ook de waarden van R(a), R(b) en R(c) en ook de waarden van C(a), C(b) en C(c). Een dergelijke wijziging kan direct voorafgaand aan elke berekeningscyclus P, waarin wordt berekend welke queue als volgende zal worden genomen) in die berekening worden betrokken, zodat de pollingvolgorde steeds optimaal is aangepast aan de toestroom van queue-elementen, zoals ATM datacellen. Ook kunnen wijzigingen eens per n berekeningscycli in de berekening worden betrokken. Aldus lijkt deze methode zeer geschikt voor toepassing in ATM systemen, hetwelk reeds door simulaties werd bevestigd.

Hierna zullen nog enige voorbeelden worden gegeven, waarbij gebruik is gemaakt van het onderstaande programma.

100 CLS

110 OPEN"pn.out" FOR APPEND AS#1 120 OPEN"pn.in" FOR INPUT AS#2 130 PRINT "Queue names abc" 140 PRINT#1,"Queue names abc"

150 INPUT#2,Q(1 ),Q{2),Q|3),R

160 IF (Q(1) = Q(1)) AND (0(2) = 0(2)) AND (Q{3) = Q(3ï) GOTO 420 170 Q{1) = Q{1 ):Q(2) =Q(2):Q(3) = Q(3) 180 PRINT "":PRINT#1,"" 190 PRINT USING "Queue values Q(a) = JW Q(b) = ### Q(c)=###";Q(1);Q{2);Q(3) 200 PRINT#1,USING "Queue values Q(a) = ### Q(b) = ### Q(c) = ###";Q{1);Q(2);-Q(3) 210 PRINT USING "Ratio factor R = ###";R 220 PRINT#1,USING "Ratio factor R = ###";R 230 S = 0 240 FOR X = 1 TO 3 250 R(X) = INT((Q(X)/R) + .5) 260 S = S + R(X) 270 NEXT X 280 FOR X = 1 TO 3 290 C(X) = S-R(X)

300 NEXT X

310 PRINT USING "Ratio values R(a) = ### R(b) = ### R(c) = ###";R(1),R{2),R(3) 320 PRINT#1,USING "Ratio values R(a) = ### R(b) = ### R(c) = ###";R(1),R(2),R(3)

330 PRINT USING "Sum ratio values S = ###";S 340 PRINT#1,USING "Sum ratio values S = M#";S

350 PRINT USING "Correction values £(*) = ### C(b)=### C(c) =###";C(1),C(2),C{3) 360 PRINT#1,USING "Correction values C(a)=### C(b) = ### C(c) = ###";C(1),C(2),-C(3) 370 PRINT"" 380 PRINT#1,"" 390 PRINT " P U(a) U(b) U(c) Selected queue (i) 400PRINT#1, " P U(a) U(b) U(c) Selected queue (i) 410 PRINT#1,"" 420 FOR P=1 TO 3 430 IF (U{ 1)> = U(2)) AND (U(1)> =U(3)) THEN Q$ = "a":M$(1) = "*":M$(2) = " ":M$(3) = " ":GOTO 460 440 IF (U{2)> =U(3)) AND (U(2)>=U(1)) THEN Q$ = "b":M$(1) = " ":M$(2) = "*":M$(3) = " ":GOTO 460 450 IF (U(3)> =U(1)) AND (U(3)> =U(1)) THEN Q$ = "c":M$(1) = " ":M$(2) = " ":M$(3) = "-*":G0T0 460 460 N = N + 1 470 PRINT USING "### ###& ###& ###& &";N,U(1),M$(1),U(2)fM$(2),- U(3),M$(3),Q$ 480 PRINT#1,USING "### ###& ###& ###& &";N,U(1),M${1),U(2),M$(- 2),U(3),M$(3),Q$ 490 IF Q$ = "a" THEN U(1)=U(1)-C(1):U(2)=U(2) + R(2):U(3)=U(3) + R(3) 500 IF Q$ = "b" THEN U(2) =U(2)-C(2):U(1) = U(1) + R(1 ):U(3) = U(3) + R(3) 510 IF Q$ = "c" THEN U(3)=U(3)-C(3):U(1)=U(1) + R(1):U(2)=U(2) + R(2)

520 NEXT P

530 IF EOF(2) GOTO 550 540 GOTO 150 550 CLOSE 560 SYSTEM

In het bovenstaande programma wordt na elke derde berekeningscyclus waarin een queue wordt aangewezen, nagegaan of zich in de queues een verandering heeft voorgedaan, bijvoorbeeld in het aantal zich in de queue bevindende elementen (of in bijvoorbeeld de netto toe- of afname). In het bovenstaande voorbeeld trad geen wijziging op; de queue-waarden waren dus in de beschouwde periode steeds constant (alleen indien zich wijzigingen voordoen, worden de nieuwe waarden gepresenteerd).

Onderstaand allereerst een situatie waarbij de queuewaarden een factor 100 groter zijn dan in het bovenstaande voorbeeld.

Queue names a b c

Queue values Q(a)=286 Q(b)=598 Q(c)=326

Ratio factor R=100

Ratio values R(a) = 3 R(b)= 6 R(c)= 3

Sum ratio values S= 12

Correction values C(a)= 9 C(b)= 6 C(c)= 9 P U(a) U(b) U(c) Selected queue (i) 1 0* 0 0 a 2 -9 6* 3 b 3-606* c 4 -3 6* -3 b 5 0* 0 0 a 6 -9 6* 3 b 7 -6 06* c 8 -3 6* -3 b 9 0* 0 0 a 10 -9 6* 3 b 11 -6 0 6* c 12 -3 6* -3 b 13 0* 0 0 a 14 -9 6* 3 b 15 -6 0 6* c

Door de queuewaarden door een ratiofactor van 100 te delen en de naastliggende gehele getallen als waarden voor de ratiotabel te gebruiken, ontstaat weer dezelfde situatie als in het eerste voorbeeld. Door de vrij grote ratiofactor wordt een lichte onnauwkeurigheid in de queueselectie geïntroduceerd, zoals uit het onderstaande voorbeeld kan worden gezien, waarin een kleinere ratiofactor is gebruikt waardoor de selectie nauwkeuriger is.

Queue names abc

Queue values Q(a)=286 Q(b)=598 Q(c)=326

Ratio factor R= 10

Ratio values R(a) = 29 R(b)= 60 R(c)= 33

Sum ratio values S=122

Correction values C(a)= 93 C(b) = 62 C(c) = 89 P U(a) U(b) U(c) Selected queue (i) 1 0* 0 0 a 2 -93 60* 33 b 3 -64 -2 66* c 4 -35 58* -23 b 5 -6 -4 10* c 6 23 56* -79 b 7 52* -6 -46 a 8 -41 54* -13 b 9 -12 -8 20* c 10 17 52* -69 b 11 46* -10 -36 a 12 -47 50* -3 b 13 -18 -12 30* c 14 11 48* -59 b 15 40* -14 -26 a

Onderstaand wordt een voorbeeld gegeven van een situatie waarbij de queuewaarden zich snel wijzigen. Om de drie berekeningscycli wordt rekening gehouden met de gewijzigde situatie (die steeds wordt aangegeven).

Queue names abc

Queue values Q(a)=286 Q(b)=598 Q(c)=326

Ratio factor R= 10

Ratio values R(a) = 29 R(b)= 60 R(c)- 33

Sum ratio values S=122

Correction values C(a)= 93 C(b) = 62 C(c)= 89 F U(a) U(b) U(c) Selected queue (1) 1 O* O O a 2 -93 60* 33 b 3 -64 -2 66* c

Queue values Q(a)=286 Q(b)=635 Q(c)=326

Ratio factor R= 10

Ratio values R(a) = 29 R(b)= 64 R(c)= 33

Sum ratio values S=126

Correction values C(a)= 97 C(b)= 62 C(c)“ 93 P U(a) U(b) U(c) Selected queue (i) 4 -35 58* -23 b 5 -6 -4 10* c 6 23 60* -83 b

Queue values Q(a)=234 Q(b)=635 Q(c)=326

Ratio factor R= 10

Ratio values R(a) = 23 R(b) = 64 R(c)= 33

Sum ratio values S=120

Correction values C(a)= 97 C(b)= 56 C(c) = 87 P U(a) U(b) U(c) Selected queue (i) 7 52* -2 -50 a 8 -45 62* -17 b 9 -22 6 16* c

Queue values Q(a)=234 Q(b)=635 Q(c)=376

Ratio factor R= 10

Ratio values R(a)= 23 R(b)= 64 R(c)= 38

Stam ratio values S-125

Correction values 0(8)=102 C(b) = 61 C(c) = 87 P U(a) U(b) U(c) Selected queue (i) 10 1 70* -71 b 11 24* 9 -33 a 12 -78 73* 5 b

Queue values Q(a)=198 Q(b)=635 Q(c)=376

Ratio factor R= 10

Ratio values R(a)“ 20 R(b) = 64 R(c) = 38

Sum ratio values S*122

Correction values C(a)**102 C(b) = 58 C(c)“ 84 P U(a) U(b) U(c) Selected queue (i) 13 -55 12 43* c 14 -35 76* -41 b 15 -15 18* -3 b

Het zal duidelijk zijn dat het evenzeer mogelijk is om niet per drie bereke-ningscycli, maar bij elke berekeningscyclus na te gaan of zich in de queues een wijziging in de queue-waarden heeft voorgedaan. In het onderstaande voorbeeld wordt daarvan uitgegaan, waarbij voorafgaand aan elke queue-selectie wordt gedetecteerd of de queuewaarden zijn gewijzigd ten opzichte van de vorige selectie; alleen in dat geval worden de gewijzigde queuewaarden gepresenteerd en de waarden voor R(x), S en C(x) herberekend. Het verloop van queuewaarden in de tijd is als volgt: 1 286 - 598 - 326 2 286 - 635 - 326 3 234 - 635 - 326 4 234 - 635 - 376 5 ,198 - 635 - 376 6 198 - 635 - 376 7 198 - 635 - 376 8 198 - 635 - 376 9 255 - 698 - 467 10 255 - 698 - 467 11 287 - 751 - 501 12 287 - 751 - 501 13 302 - 923 - 578 14 302 - 923 - 578 15 302 - 923 - 578

De berekening van de pollingvolgordetabel ziet er dan als volgt uit:

Queue names abc

Queue values Q(a)=286 Q(b)=598 Q(c)=326

Ratio factor R= 10

Ratio values R(a) = 29 R(b)= 60 R(c)“ 33

Sum ratio values S=122

Correction values C(a)= 93 C(b)= 62 C(c) = 89 P U(a) U(b) U(c) Selected queue (i) 1 0* 0 0 a

Queue values Q(a)~286 Q(b)*=635 Q(c)»326

Ratio factor R*= 10

Ratio values R(a)~ 29 R(b) = 64 R(c)“ 33

Sum ratio values S=126

Correction values C(a)= 97 C(b) = 62 C(c)= 93 P U(a) U(b) U(c) Selected queue (i) 2 -93 60* 33 b

Queue values Q(a)=234 Q(b)=635 Q(c)=326

Ratio factor R= 10

Ratio values R(a)= 23 R(b)= 64 R(c)= 33

Sum ratio values S=120

Correction values C(a)= 97 C(b)= 56 C(c)= 87 P U(a) U(b) 0(c) Selected queue (i) 3 -64 -2 66* c

Queue values Q(a)=234 Q(b)=635 Q(c)=376

Ratio factor R= 10

Ratio values R(a)= 23 R(b)= 64 R(c)= 38

Sum ratio values S=125

Correction values C(a)=102 C(b)= 61 C(c) = 87 P U(a) 0(b) U(c) Selected queue (i) 4 -41 62* -21 b

Queue values Q(a)=198 Q(b)=635 Q(c)=376

Ratio factor R= 10

Ratio values R(a)= 20 R(b)= 64 R(c)= 38

Stim ratio values S=122

Correction values C(a)=102 C(b)= 58 C(c)= 84 P U(a) U(b) U(c) Selected queue (i) 5 -18 1 17* c 6 2 65* -67 b 7 22* 7-29 a 8 -80 71* 9 b

Queue values Q(a)“255 Q(b)-698 Q(c)-467

Ratio factor R“ 10

Ratio values R(a)“= 26 R(b) = 70 R(c)* 47

Sum ratio values S=143

Correction values C(a)“117 C(b)= 73 C(c)« 96 P U(a) U(b) U(c) Selected queue (i) 9 -60 13 47* c 10 -34 83* -49 b

Queue values Q(a)=287 Q(b)=751 Q(c)=501

Ratio factor R= 10

Ratio values R(a)“ 29 R(b)*= 75 R(c)« 50

Sum ratio values S=154

Correction values C(a)=125 C(b)= 79 C(c)-104 P U(a) U(b) U(c) Selected queue (i) 11 -8 10* -2 b 12 21 -69 48* c

Queue values Q(a)=302 Q(b)=923 Q(c)=578

Ratio factor R= 10

Ratio values R(a)= 30 R(b)= 92 R(c)= 58

Stom ratio values S=180

Correction values C(a)“150 C(b)* 88 C(c)*=122 P U(a) U(b) U(c) Selected queue (i) 13 50* 6 -56 a 14 -100 98* 2 b 15 -70 10 60* c

Korter gepresenteerd:

Berekeningseyclus Queue-waarden Geselecteerde queue 1 286 - 598 - 326 a 2 286 - 635 - 326 b 3 234 - 635 - 326 c 4 234 - 635 - 376 b 5 198 - 635 - 376 c 6 198 - 635 - 376 b 7 198 - 635 - 376 a 8 198 - 635 - 376 b 9 255 - 698 - 467 c 10 255 - 698 - 467 b 11 287-751-501 b 12 287 - 751 - 501 c 13 302 - 923 - 578 a 14 302 - 923 - 578 b 15 302 - 923 - 578 c

In de bovenstaande voorbeelden is voor de eenvoud uitgegaan van drie queues. Het zal duidelijk zijn dat dat aantal op eenvoudige wijze vergroot kan worden.

Een belangrijke toepassing voor de werkwijze volgens de uitvinding is te vinden in systemen waarbij de servicetoewijzing snel aangepast moet kunnen worden aan een veranderende servicebehoefte. Een voorbeeld van een systeem waarbij sprake is van een snel veranderende servicebehoefte van de queues is het ATM Passieve Optische Netwerk, waarbij meerdere gebruikers aangesloten zijn op één lokale centrale, via een boomvormig vertakte glasvezel. Daarbij kunnen de gebruikers-queues met ATM datacellen onder gebruikmaking van de hierboven gepresenteerde werkwijze op doelmatige wijze worden uitgelezen.

Indien de pollingtabel steeds wordt aangepast aan de servicebehoefte is de keuze van de initiële waarden van U(a), U(b) en U(c) niet kritisch. Indien de pollingtabel echter semi-statisch gebruikt wordt, zijn die initiële waarden van meer betekenis. In de praktijk is gebleken dat een goede oplossing wordt gevonden indien als initiële waarden wordt genomen de som S van de ratiowaarden minus het geheeltallige deel van het quotiënt van die som S en de ratiowaarde R{a) resp. R(b) resp R(c). In het laatste voorbeeld gold:

Ratio values R(a)· 29 R(b) = 60 R(c)« 33

Sum ratio values S-122

Als de bovenstaande regel wordt gehanteerd, worden de initiële waarden van U(a,b,c):

Uj(a) = S - (S DIV R(a)) = 122 - (122 DIV 29) = 122 - 4 = 118

Uj(b) = S - (S DIV R(b)) = 122 - (122 DIV 60) = 122 - 2 = 120

Uj(c) = S - (S DIV R(c)) = 122 - (122 DIV 33) = 122 - 3 = 119

Het berekeningsresultaat van de pollingtabel wordt dan (uitgaande van dezelfde, bovenstaande queuewaarden):

Queue names a b c

Queue values Q(a)=286 Q(b)=598 Q(c)=326

Ratio factor R= 10

Ratio values R(a)= 29 R(b)= 60 R(c)= 33

Sum ratio values S=122

Correction values C(a)= 93 C(b)= 62 C(c)= 89 P U(a) U(b) U(c) Selected queue (i) 1 118 120* 119 b

Queue values Q(a)=286 Q(b)=635 Q(c)*326

Ratio factor R«= 10

Ratio values R(a)-= 29 R(b)« 64 R(c)« 33

Sum ratio values S=126

Correction values C(a)= 97 C(b)= 62 C(c)“ 93 P U(a) U(b) U(c) Selected queue (i) 2 147 58 152* c

Queue values Q(a)=234 Q(b)=635 Q(c)=326

Ratio factor R= 10

Ratio values R(a) = 23 R(b)= 64 R(c) = 33

Sum ratio values S*120

Correction values C(a)“ 97 C(b)= 56 C(c)· 87 P U(a) U(b) U(c) Selected queue (i) 3 176* 122 59 a

Queue values Q(a)=234 Q(b)=635 Q(c)“376

Ratio factor R= 10

Ratio values R(a) = 23 R(b)*= 64 R(c)- 38

Sum ratio values S=125

Correction values C(a)=102 C(b)= 61 C(c)“ 87 P U(a) U(b) U(c) Selected queue (i) 4 79 186* 92 b

Queue values Q(a)=198 Q(b)=635 Q(c)=376

Ratio factor R= 10

Ratio values R(a)= 20 R(b)= 64 R(c)= 38

Sum ratio values S=122

Correction values C(a)=102 C(b)= 58 C(c)= 84 P U(a) U(b) U(c) Selected queue (i) 5 102 125 130* c 6 122 189* 46 b 7 142* 131 84 a 8 40 195* 122 b

Queue values Q(a)=255 Q(b)=698 Q(c)=467

Ratio factor R= 10

Ratio values R(a)= 26 R(b)= 70 R(c)= 47

Sum ratio values S=143

Correction values C(a)=117 C(b)= 73 C(c)= 96 P U(a) U(b) U(c) Selected queue (i) 9 60 137 160* c 10 86 207* 64 b

Queue values Q(a)=287 Q(b)=751 Q(c)=501

Ratio factor R= 10

Ratio values R(a)= 29 R(b)= 75 R(c)= 50

Sum ratio values S-154

Correction values C(a)-125 C(b) = 79 C(c)-104 P U(a) U(b) U(c) Selected queue (i) 11 112 134* 111 b 12 141 55 161* c

Queue values Q(a)-302 Q(b)-923 Q(c)«578

Ratio factor R- 10

Ratio values R(a)« 30 R(b)= 92 R(c)« 58

Sum ratio values S=180

Correction values C(a)«150 C(b)= 88 C(c)~122 P U(a) U(b) U(c) Selected queue (i) 13 170* 130 57 a 14 20 222* 115 b 15 50 134 173* c

Zoals te zien is, heeft een wijziging van de initiële waarden slechts invloed op het resultaat van de eerste drie berekeningscycli (P = 1 ...3)

Een soortgelijke opmerking als ten aanzien van de keuze van de initiële waarden van de urgentiefactoren U(a,b,c) kan ook worden gemaakt met betrekking tot de keuze van de ratiofactor R. Een ratiofactor R = 1 geeft het meest nauwkeurige resultaat; de (gemeten) queuewaarden zijn dan tevens de voor de berekening te gebruiken ratiowaarden. Als echter de queuewaarden zeer groot zijn en met name indien de pollingtabel statisch van aard is en dus (gedurende een tijd) in bijvoorbeeld een RAM (met beperkte buffercapaciteit) moet worden opgeslagen, moet, door middel van een ratiofactor > 1, van de queuewaarden een gereduceerde afbeelding worden gemaakt, voorgesteld door de ratiowaarden. Een bijkomend probleem daarbij is dat de maximale transmissiesnelheid niet mag worden overschreden (als gebruik gemaakt wordt van queuewaarden die het aanbod van queue-elementen per tijdseenheid voorstellen). Een goede oplossing voor het berekenen van de ratiowaarden is de volgende. Gesteld de volgende queuewaarden (aanbod van queue-elementen per tijdseenheid in kbit/sec): 70000,19000,18500, 22333, en 8000. De totale daarvoor benodigde bandbreedte is 137833 kbit/sec. Gesteld dat de maximale transmissiebandbreedte 140000kbit/sec is. Een eerste oplossing is om de resterende bandbreedte van 140000 - 137833 = 2167 geheeltallig te delen door het aantal queues (5): 2167 DIV 5 = 433 en vervolgens de verschillende queue-groeiwaarden door dat quotiënt te delen: 70000 DIV 433 = 161; 19000 DIV 433 = 43; 18500 DIV 433 = 42; 22333 DIV 433 = 51 en 8000 DIV 433 = 18.

Bij voorkeur worden deze ratiowaarden nog elk vermeerderd met 1, waardoor gebruik wordt gemaakt van nagenoeg de gehele transmissiecapaciteit van 140000 kbit/sec; de ratiowaarden worden dan dus 162, 44, 43, 52 en 19. Opgemerkt wordt dat de ratiofactor voor verschillende queues een enigszins verschillende waarde heeft, namelijk in dit geval resp. 70000/162 = 432, 19000/44 = 431, 18500/43 = 430, 22333/52 = 429 en 8000/19 = 421.

Een andere oplossing voor het berekenen van de optimale gereduceerde afbeelding van de queuewaarden gaat als volgt. Stap 1: tel bij de oneven queuewaarden 1 op; die waarden worden dan 70000, 19000, 18500, 22333 + 1 = 22334 en 8000; de resterende bandbreedte wordt nu 2167 - 1 = 2166. Stap 2: deel de queuewaarden en de resterende bandbreedte door 2 en tel bij de oneven resulterende waarden 1 op; de nieuwe waarden worden dan 35000, 9500, 9250,11167 + 1 = 11168, 4000; het nieuwe restant is 1082 (2166/2 = 1083, waarvan 1 wordt afgetrokken om de waarde 11167 met 1 te verhogen). Stap 2 wordt herhaald totdat de resterende bandbreedte minimaal is, dat wil zeggen dat, indien stap 2 nogmaals zou worden herhaald, de resterende bandbreedte negatief zou worden. In dit geval resulteren uit het 8 maal herhalen van stap 2 de volgende ratiowaarden: 137, 38, 37, 44 en 16; de resterende bandbreedte is 1 (kbit/sec).

Met de voorgaande methoden voor het uit de queuewaarden berekenen van optimale ratiowaarden, die op hun beurt weer de input vormen voor het berekenen van de optimale pollingvolgorde, wordt bereikt dat de maximale (totaal)bandbreedte wordt gebruikt --waardoor de transmissiesnelheid van de queue-elementen maximaal is-- zonder dat die bandbreedte wordt overschreden. Aldus wordt door een en ander bereikt dat de queue-elementen in de verschillende queues in regelmatige volgorde en voldoende vaak (namelijk zo vaak dat de queue niet overloopt) worden uitgelezen (gepold) en dat de overdrachtsnelheid van die elementen, bijv. van abonnees afkomstige ATM-cellen in een passief optisch abonneenetwerk, maximaal is, zonder dat echter de toelaatbare transmissiesnelheid (bitrate) kan worden overschreden.

Claims

1. Methode voor het pollen van queues met elk een in de tijd variërend en è priori onbekend aantal queue-elementen, waarbij uit queue-waarden, zoals de aantallen elementen in de verschillende queues of de toename van die aantallen queue-elementen, een ratiotabel wordt gevormd met ratiowaarden die die queuewaarden representeren, welke ratiotabel vervolgens wordt geconverteerd in een pollingvolgordetabel met een zo regelmatig mogelijke pollingvolgorde, GEKENMERKT DOOR de volgende stappen: Stap 1: bereken aan de hand van de queuewaarden Q(n) de ratiowaarden R(n) in de ratiotabel; Stap 2: bereken de som S van die ratiowaarden R(n); Stap 3: ken aan elke queue x een correctiefactor C(x) toe die gelijk is aan die som S van de ratiowaarden, verminderd met de ratiowaarde R(x) van die queue x; Stap 4 selecteer de queue i met de hoogste urgentiefactor U(i) of selecteer, indien meer queues die hóógste urgentiefactor U(i) hebben, één bepaalde queue i daaruit, bijvoorbeeld de eerste in de ratiotabel voorkomende queue met die hoogste urgentiefactor U(i); Stap 5 verlaag de urgentiefactor U(i) van die geselecteerde queue i met de waarde van zijn correctiefactor C(i); Stap 6 verhoog de urgentiefactor U(x) van de overige queues (=iM) met hun ratiowaarde R(x); Stap 7 herhaal vanaf stap 4.

2. Methode voor het pollen van queues met elk een in de tijd variërend en d priori onbekend aantal queue-elementen, waarbij uit queue-waarden, zoals de aantallen elementen in de verschillende queues of de toename van die aantallen queue-elementen, een ratiotabel wordt gevormd met ratiowaarden die die queuewaarden representeren, welke ratiotabel vervolgens wordt geconverteerd in een pollingvolgordetabel met een zo regelmatig mogelijke pollingvolgorde, GEKENMERKT DOOR de volgende stappen: Stap 1: bereken aan de hand van de queuewaarden Q(n) de ratiowaarden R(n) in de ratiotabel; Stap 2: bereken de som S van die ratiowaarden R(n); Stap 3: ken aan elke queue x een correctiefactor C(x) toe die gelijk is aan die som S van de ratiowaarden, verminderd met de ratiowaarde R(x) van die queue x; Stap 4 selecteer de queue i met de hoogste urgentiefactor U(i) of selecteer, indien meer queues die hoogste urgentiefactor U(i) hebben, één bepaalde queue i daaruit, bijvoorbeeld de eerste in de ratiotabel voorkomende queue met die hoogste urgentiefactor U{i); Stap 5 verlaag de urgentiefactor U(i) van die geselecteerde queue i met de waarde van zijn correctiefactor C(i); Stap 6 verhoog de urgentiefactor U(x) van de overige queues (^ i) met hun ratiowaarde R(x); Stap 7 herhaal, tenminste in het geval dat de queuewaarden gewijzigd zijn, vanaf stap 1.