Control of Congestion and Flow in Integrated Service Networks
The paper focuses on implementing schemes to guarantee worst-case packet delay in high-speed networks, using Packet-by-Packet GPS combined with Leaky Bucket admission control to achieve the goal. It discusses the challenges and solutions in flow control mechanisms like GPS servers and work-conserving mechanisms.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Abhay.K.Parekh and Robert G.Gallager Laboratory for Information and Decision Systems Massachusetts Institute of Technology IEEE INFOCOM 1992
Introduction Major work of the paper GPS GPS Example PGPS Determine the difference of delay and traffic in 2 scheme
Bounds of buffer size Virtual System Implementation Leaky-Bucket Admission Control Result Conclusion
The Paper focus on a central problem in the control of congestion and flow in high speed integrated service networks. Goal is to find a implementable schemes for guaranteeing worst-case packet delay(Flow Control).
Major part of the paper is to provide a implementable scheme for guaranteeing worst-case packet delay. Show that PGPS ( Packet-by-Packet GPS ) combined with Leaky bucket admission control can achieve the goal.
GPS is a work-conserving flow control mechanism that ensure upper bounds of worst packet delay. But it can not be implemented because it assume that the packet size can be infinitely divided. Work Conserving server will not let bandwidth idle.
GPS Server checks to see if a new source can be accommodated and, if so, takes actions (such as reserving transmission links or switching capacity) to ensure the quality of service desired.
Once a source begins sending traffic, the network ensures that the agreed-upon values of traffic parameters are not violated.
GPS Serer is defined as Si( ,t) be the amount of session i traffic served in an time interval [ ,t]. Si( ,t) / Sj( ,t) i/ j, j = 1,2, ,N ,for any session i that is continuously backlogged in the time interval [ ,t].
By Summering all session j ( in order to find session i s rate ), we can derive : Si( ,t) j j (t- )r i,where r is the processing rate of server and is the weight of the session. gi = ir / j j .
GPS is a attractive multiplexing scheme for a number of reasons: If the average rate of a session i less than githe session can be guaranteed a throughput i,independent of the demand of the other session The delay of an arriving session i bit can be bounded as a function of the session I queue length , independent of the queues and arrivals of the other sessions
By varying i, we have flexibility to treat sessions in different way, as long as the total average rate of all sessions <= r. For example, a high-bandwidth delay- insensitive session can be assigned gi much less than its average rate, thus allowing for better treatment of the other sessios.
each backlogged flow is guaranteed a minimum service rate(fairness) the excess service rate is redistributed among the backlogged flows in proportion to their minimum service rates(flexible and efficient).
Standard techniques of approximating fluid GPS Select packet that finishes first in GPS assuming that there are no future arrivals Important properties of GPS Finishing order of packets currently in system independent of future arrivals Implementation based on virtual time Assign virtual finish time to each packet upon arrival Packets served in increasing order of virtual times
Tgps T pgps Lmax/ r ,where Lmaxis the maximum packet length Si(0, ) - i(0, ) LmaxS is the traffic served Q^i(0, ) - Qi(0, ) LmaxQ is the amount of backlog in session I.
GPS need buffer size Lmaxeach link PGPS needs Lmax+ max t 0(fi(t)-rit)
Virtual time , v(t), is used to to represent the progress of work in the reference system. When the departure or arrival of the events, the virtual time will update. Assign virtual finish time to each packet upon arrival Packets served in increasing order of virtual times
Two Sessions submit fixed size packet 1 unit length Rate of server is 1 Starting at time zero 1000 session 1 packets begins to arrive at a rate of 1 packet/sec At time 900 , 450 session 2 packets arrive at rate of 1 packet/sec
The virtual clock of session 1 will read 1800 and virtual clock of session 2 will read 900 at real time 900. ( if the server treat both session equally) And from that session 1 will read 1800,1802 while the other one is 900,902,904
= token generation rate. = max tokens in bucket. C = maximum rate at which traffic leaves the bucket. Ai( ,t) <= min{(t- ) Ci, , i + i(t- )} li(t) = tokens in the session i token bucket at time t. Ki(t) = total number of tokens accepted at the session i bucket in the interval (0, t]. Ai( ,t) <= li( ) + i(t- ) - li(t)
The use of Generalized processor Sharing (GPS), when combined with Leaky Bucket admission control, allows the network to make a wide range of worst-case performance guarantees on throughput and delay
