667:
Generalized processor sharing assumes that the traffic is fluid, i.e., infinitely divisible so that whenever an application type has packets in the queue, it will receive exactly the fraction of the server given by the formula above. However, traffic is not fluid and consists of packets, possibly of
554:
This is a minimal rate. If some flow does not use its bandwidth during some period, this remaining capacity is shared by the active flows with regard to their respective weights. For example, consider a GPS server with
526:
323:
81:, which works fine if the sizes of the queues are small, but can result in problems if there are latency-sensitive packets being blocked by packets from bursty, higher bandwidth applications.
77:. When packets are queued up on one end of a congested link, the node usually has some freedom in deciding the order in which it should send the queued packets. One example ordering is simply
46:
In process scheduling, GPS is "an idealized scheduling algorithm that achieves perfect fairness. All practical schedulers approximate GPS and use it as a reference to measure fairness."
618:
368:
654:
420:
186:
134:
549:
443:
388:
230:
206:
154:
107:
668:
variable sizes. Therefore, GPS is mostly a theoretical idea, and several scheduling algorithms have been developed to approximate this GPS ideal: PGPS, aka
53:
packet sizes), and can be arbitrarily split. There are several service disciplines which track the performance of GPS quite closely such as
65:
In a network such as the internet, different application types require different levels of performance. For example, email is a genuinely
679:
GPS is considered as a fair ideal, and all its approximations "use it as a reference to measure fairness." Nevertheless, several
451:
672:, is the most known implementation of GPS, but it has some drawbacks, and several other implementations have been proposed, as
894:
766:
238:
759:"A generalized processor sharing approach to flow control in integrated services networks: The single-node case"
924:
664:
In GPS, and all protocols inspired by GPS, the choice of the weights is left to the network administrator.
558:
39:
which groups packets into classes and shares the service capacity between them. GPS shares this capacity
817:
725:
78:
331:
812:
656:, only the second and third flows are active, they will receive each one half of the capacity.
28:
798:"Efficient and scalable multiprocessor fair scheduling using distributed weighted round-robin"
710:
669:
54:
620:. The first flow will receive at least half of the capacity, whereas the other two only get
877:
Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing".
720:
627:
393:
159:
112:
24:
8:
715:
673:
758:
36:
900:
754:
534:
428:
373:
215:
191:
139:
92:
890:
705:
695:
70:
66:
32:
904:
882:
857:
822:
775:
730:
680:
886:
918:
841:
74:
50:
826:
797:
57:(WFQ), also known as packet-by-packet generalized processor sharing (PGPS).
700:
109:
flows (also called "classes", or "sessions") is configured with one weight
862:
845:
879:
Proceedings of IEEE INFOCOM '96. Conference on
Computer Communications
779:
686:
GPS is insensible to packet sizes, since it assumes a fluid model.
659:
136:
for each flow. Then, the GPS ensures that, considering one flow
49:
Generalized processor sharing assumes that traffic is fluid (
791:
789:
521:{\displaystyle R_{i}={\frac {w_{i}}{\sum _{j=1}^{N}w_{j}}}R}
786:
846:"Analysis and simulation of a fair queueing algorithm"
630:
561:
537:
454:
431:
396:
376:
334:
241:
218:
194:
162:
142:
115:
95:
212:
the queue is never empty), then, for any other flow
839:
318:{\displaystyle w_{j}O_{i}(s,t)\geq w_{i}O_{j}(s,t)}
648:
612:
543:
520:
437:
414:
382:
362:
317:
224:
200:
180:
148:
128:
101:
916:
876:
795:
752:
660:Implementations, parametrization and fairness
208:is continuously backlogged on this interval (
861:
850:ACM SIGCOMM Computer Communication Review
816:
796:Li, T.; Baumberger, D.; Hahn, S. (2009).
624:. Nevertheless, if on some time interval
748:
746:
370:denotes the amount of bits of the flow
917:
425:Then, it can be proved that each flow
833:
743:
613:{\displaystyle w_{1}=2,w_{2}=w_{3}=1}
870:
767:IEEE/ACM Transactions on Networking
13:
14:
936:
60:
232:, the following relation holds
41:according to some fixed weights
643:
631:
409:
397:
357:
345:
312:
300:
274:
262:
175:
163:
1:
736:
445:will receive at least a rate
89:In GPS, a scheduler handling
17:Generalized processor sharing
881:. Vol. 1. p. 120.
7:
689:
551:is the rate of the server.
10:
941:
887:10.1109/INFCOM.1996.497885
363:{\displaystyle O_{k}(s,t)}
84:
156:, and some time interval
69:kind of application, but
840:Demers, A.; Keshav, S.;
726:Statistical multiplexing
390:made output on interval
79:first-come, first-served
73:isn't since it requires
827:10.1145/1594835.1504188
35:. It is related to the
650:
614:
545:
522:
501:
439:
416:
384:
364:
319:
226:
202:
182:
150:
130:
103:
37:fair-queuing principle
925:Scheduling algorithms
711:Weighted fair queuing
670:Weighted fair queuing
651:
649:{\displaystyle (s,t]}
615:
546:
523:
481:
440:
417:
415:{\displaystyle (s,t]}
385:
365:
320:
227:
203:
183:
181:{\displaystyle (s,t]}
151:
131:
129:{\displaystyle w_{i}}
104:
55:weighted fair queuing
721:Weighted round robin
628:
559:
535:
452:
429:
394:
374:
332:
239:
216:
192:
160:
140:
113:
93:
25:scheduling algorithm
863:10.1145/75247.75248
805:ACM SIGPLAN Notices
716:Deficit round robin
674:Deficit round robin
188:such that the flow
646:
610:
541:
518:
435:
412:
380:
360:
315:
222:
198:
178:
146:
126:
99:
33:network schedulers
29:process schedulers
896:978-0-8186-7293-4
780:10.1109/90.234856
706:Processor sharing
696:Network scheduler
681:Fairness measures
544:{\displaystyle R}
513:
438:{\displaystyle i}
383:{\displaystyle k}
225:{\displaystyle j}
201:{\displaystyle i}
149:{\displaystyle i}
102:{\displaystyle N}
71:videoconferencing
67:store and forward
932:
909:
908:
874:
868:
867:
865:
837:
831:
830:
820:
802:
793:
784:
783:
763:
750:
731:Fairness measure
655:
653:
652:
647:
623:
619:
617:
616:
611:
603:
602:
590:
589:
571:
570:
550:
548:
547:
542:
527:
525:
524:
519:
514:
512:
511:
510:
500:
495:
479:
478:
469:
464:
463:
444:
442:
441:
436:
421:
419:
418:
413:
389:
387:
386:
381:
369:
367:
366:
361:
344:
343:
324:
322:
321:
316:
299:
298:
289:
288:
261:
260:
251:
250:
231:
229:
228:
223:
207:
205:
204:
199:
187:
185:
184:
179:
155:
153:
152:
147:
135:
133:
132:
127:
125:
124:
108:
106:
105:
100:
940:
939:
935:
934:
933:
931:
930:
929:
915:
914:
913:
912:
897:
875:
871:
838:
834:
818:10.1.1.567.2170
800:
794:
787:
761:
755:Gallager, R. G.
753:Parekh, A. K.;
751:
744:
739:
692:
662:
629:
626:
625:
621:
598:
594:
585:
581:
566:
562:
560:
557:
556:
536:
533:
532:
506:
502:
496:
485:
480:
474:
470:
468:
459:
455:
453:
450:
449:
430:
427:
426:
395:
392:
391:
375:
372:
371:
339:
335:
333:
330:
329:
294:
290:
284:
280:
256:
252:
246:
242:
240:
237:
236:
217:
214:
213:
193:
190:
189:
161:
158:
157:
141:
138:
137:
120:
116:
114:
111:
110:
94:
91:
90:
87:
63:
12:
11:
5:
938:
928:
927:
911:
910:
895:
869:
832:
785:
741:
740:
738:
735:
734:
733:
728:
723:
718:
713:
708:
703:
698:
691:
688:
661:
658:
645:
642:
639:
636:
633:
609:
606:
601:
597:
593:
588:
584:
580:
577:
574:
569:
565:
540:
529:
528:
517:
509:
505:
499:
494:
491:
488:
484:
477:
473:
467:
462:
458:
434:
411:
408:
405:
402:
399:
379:
359:
356:
353:
350:
347:
342:
338:
326:
325:
314:
311:
308:
305:
302:
297:
293:
287:
283:
279:
276:
273:
270:
267:
264:
259:
255:
249:
245:
221:
197:
177:
174:
171:
168:
165:
145:
123:
119:
98:
86:
83:
62:
59:
23:) is an ideal
9:
6:
4:
3:
2:
937:
926:
923:
922:
920:
906:
902:
898:
892:
888:
884:
880:
873:
864:
859:
855:
851:
847:
843:
836:
828:
824:
819:
814:
810:
806:
799:
792:
790:
781:
777:
773:
769:
768:
760:
756:
749:
747:
742:
732:
729:
727:
724:
722:
719:
717:
714:
712:
709:
707:
704:
702:
699:
697:
694:
693:
687:
684:
682:
677:
675:
671:
665:
657:
640:
637:
634:
607:
604:
599:
595:
591:
586:
582:
578:
575:
572:
567:
563:
552:
538:
515:
507:
503:
497:
492:
489:
486:
482:
475:
471:
465:
460:
456:
448:
447:
446:
432:
423:
406:
403:
400:
377:
354:
351:
348:
340:
336:
309:
306:
303:
295:
291:
285:
281:
277:
271:
268:
265:
257:
253:
247:
243:
235:
234:
233:
219:
211:
195:
172:
169:
166:
143:
121:
117:
96:
82:
80:
76:
72:
68:
61:Justification
58:
56:
52:
51:infinitesimal
47:
44:
42:
38:
34:
30:
26:
22:
18:
878:
872:
853:
849:
835:
808:
804:
771:
765:
701:Fair queuing
685:
678:
666:
663:
553:
530:
424:
327:
209:
88:
64:
48:
45:
40:
20:
16:
15:
842:Shenker, S.
75:low latency
774:(3): 344.
737:References
813:CiteSeerX
811:(4): 65.
676:or WF2Q.
483:∑
278:≥
919:Category
905:17558577
856:(4): 1.
844:(1989).
757:(1993).
690:See also
683:exist.
85:Details
903:
893:
815:
531:where
328:where
901:S2CID
801:(PDF)
762:(PDF)
891:ISBN
210:i.e.
31:and
27:for
883:doi
858:doi
823:doi
776:doi
622:1/4
21:GPS
921::
899:.
889:.
854:19
852:.
848:.
821:.
809:44
807:.
803:.
788:^
770:.
764:.
745:^
422:.
43:.
907:.
885::
866:.
860::
829:.
825::
782:.
778::
772:1
644:]
641:t
638:,
635:s
632:(
608:1
605:=
600:3
596:w
592:=
587:2
583:w
579:,
576:2
573:=
568:1
564:w
539:R
516:R
508:j
504:w
498:N
493:1
490:=
487:j
476:i
472:w
466:=
461:i
457:R
433:i
410:]
407:t
404:,
401:s
398:(
378:k
358:)
355:t
352:,
349:s
346:(
341:k
337:O
313:)
310:t
307:,
304:s
301:(
296:j
292:O
286:i
282:w
275:)
272:t
269:,
266:s
263:(
258:i
254:O
248:j
244:w
220:j
196:i
176:]
173:t
170:,
167:s
164:(
144:i
122:i
118:w
97:N
19:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.