START-TIME FAIR QUEUING - A SCHEDULING ALGORITHM FOR INTEGRATED SERVICES PACKET-SWITCHING NETWORKS

We present a Start-time Fair Queueing (SFQ) algorithm that is computat ionally efficient and achieves fairness regardless of variation in a s erver capacity. We analyze its single server and end-to end deadline g uarantee for variable rate Fluctuation Constrained (FC) and Exponentia lly Bounded Fluctuation (EBF) servers. To support heterogeneous servic es and multiple protocol families in integrated services networks, we present a hierarchical SFQ scheduler and derive its performance bounds . Our analysis demonstrates that SFQ is suitable for integrated servic es networks since it: 1) achieves low average as well as maximum delay for low-throughput applications (e.g., interactive audio, telnet, etc .); 2) provides fairness which is desirable for VBR video; 3) provides fairness, regardless of variation in server capacity, for throughput- intensive, flow-controlled data applications; 4) enables hierarchical link sharing which is desirable for managing heterogeneity; and 5) is computationally efficient.