GENERALIZED GUARANTEED RATE SCHEDULING ALGORITHMS - A FRAMEWORK

In this paper, we define a class of generalized Guaranteed Rate (GR) s cheduling algorithms that includes algorithms which allocate variable rate to packets of a how, We define work-conserving generalized Virtua l Clock, Packet-by-Packet Generalized Processor Sharing, and Self-Cloc ked Fair Queuing scheduling algorithms that can allocate variable rate to the packets of a flow, We also define scheduling algorithms suitab le for servers where packet fragmentation may occur, We demonstrate th at if a class of rate controllers is employed for a how in conjunction with any scheduling algorithm in GR, then the resulting non-work-cons erving algorithm also belongs to GR, This leads to the definition of s everal non-work-conserving algorithms. We then present a method for de riving the delay guarantee of a network of servers when: 1) different rates are allocated to packets of a flaw at different servers along th e path and the bottleneck server for each packet may be different, and 2) packet fragmentation and/or reassembly may occur, This delay guara ntee enables a network to provide various service guarantees to flows conforming to any specification, We illustrate this by utilizing delay guarantee to derive delay bounds for flows conforming to Leaky Bucket , Exponentially Bounded Burstiness, and Flow Specification. Our method for determining these bounds is valid in internetworks and leads to t ighter results.