A Generalized Processor Sharing Approachto Flow Control .ppt

1、A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case Abhay K. Parekh, Member, IEEE, and Robert G. Gallager, Fellow, IEEE,IntServ Approach rate-based flow; the sources traffic is assigned values to the parameterized set of statistics (avg rate

2、, max rate, and burstiness) . We assume that rate admission control is done through leaky buckets User requests a certain QoS(throughput ,worst-case packet delay). The traffic entering the network has been “shaped” by the leaky bucket in a manner that can be succinctly characterized (we will do this

3、 in Section V), and so the network can upper bound the queuing delay through this characterization. network 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

4、 begins sending traffic, the network ensures that the agreed-upon values of traffic parameters are not violated.,Presentation Organization Generalized Processor Sharing (GPS) and the packet based scheme, PGPS, is defined and explained Results obtained in these section allow us to translate session d

5、elay and buffer requirement bounds derived for a GPS server system to a PGPS server system. a virtual time implementation of PGPS is proposed in the next section. The Leaky Bucket is described and proposed as a desirable strategy for admission control. We then proceed with an analysis, of a single G

6、PS server system in which the sessions are constrained by leaky buckets.,Why GPS Generalized Processor Sharing(GPS) is a flow-based multiplexing discipline that is efficient, flexible, fair and analyzable. characterized by two attractive properties: (i) each backlogged flow is guaranteed a minimum s

7、ervice rate(fairness), and (ii) the excess service rate is redistributed among the backlogged flows in proportion to their minimum service rates(flexible and efficient). analyzable so that performance guarantees can be made.,GPS server characteristics work conserving(server must be busy if there are

8、 packets waiting in the system) and operates at a fixed rate T. It is characterized by weights(positive real numbers) given to the flows Let Si(T,t) be the amount of session i traffic served in an interval (T,t. Then. a GPS server is defined as one for whichSi(T,t)/ Sj(T,t) = i/j, j=1,2,.Nsession i

9、is guaranteed a rate ofgi = ( i/j )r,GPS advantages Throughput guarantee Bounded delay Flexibilty Worst-case network queueing delay guarantees when the sources are constrained by leaky buckets. Session i is guaranteed a rate ofgi = ( i/j )r,A PACKET-BY-PACKET TRANSMISSION SCHEMEPGPS In PGPS the serv

10、er picks the first packet that would complete service in the GPS simulation if no additional packets were to arrive after time T.,Lemma 1: Let p and p be packets in a GPS system at time T, and suppose that packet p completes service before packet p if there are no arrivals after time T. Then, packet

11、 p will also complete service before packet p for any pattern of arrivals after time r.,Theorem 1: Fp = time at which packet p will depart under GPS. Fp = time at which packet p will depart under PGPS. Lmax = maximum packet length and r = rate of the server.Fp Fp = Lmax/r,Theorem 2: Si(T,t) = the am

12、ount of session i traffic (in bits, not packets) served under GPS in the interval T,t. i(T,t) = the amount of session i traffic served under PGPS. Lmax = maximum packet length and For all times t and sessions i, Si(0,t) - i(0,t) 0 such that Si(0,t) - i(0,t) = cLmaxholds for all sessions i over all p

13、atterns of arrivals.,Virtual time Virtual time , v(t), is used to to represent the progress of work in the reference system.,LEAKY BUCKET = 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 ses

14、sion 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),Lemma 2: For every session i, = (t- ) i / Nj=1 j,ConclusionThe 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.,