Schedule-Based Approach for Flow-Control in Data Communication Networks

摘要

An approach for achieving user-session packet throughput guarantees and packet intranetwork delay limits is described. Both objectives are important for packetized voice calls. The approach permits flexible usage of link capacity by sessions, which is important for data sessions. Throughput is guaranteed to a session at links in its path by scheduling priority-slots in link-frames for transmission. An extension of end-to-end windowing limits the intra-network delay for a session to the sum of, first, the product of the frame-time and the session's window-size, and, second the session's priority-slot schedule-delay. An NP-completeness result is proven, showing, for general networks, that the scheduling of priority-slots to obtain minimum sum of schedule-delays is algorithmically hard. Minimum-delay scheduling algorithms for special network classes, and a scheduling heuristic for general networks, are presented. For Poisson packet generation at session rates less than throughput guarantees, limited simulations suggest that low mean values of packet end-to-end delays, relatively insensitive to choice of window-sizes, are obtained even at small but non-zero window-sizes.