The FCFS service discipline: Stable network topologies, bounds on traffic burstiness and delay, and control by regulators Academic Article uri icon

abstract

  • We consider the well-known First Come First Serve (FCFS) scheduling policy under bursty arrivals. This policy is commonly used in scheduling communication networks and manufacturing systems. Recently it has been shown that the FCFS policy can be unstable for some nonacyclic network topologies. We identify some network topologies under which FCFS is stable for all arrival and service rate vectors within the system's capacity. This is done by determining a sharp bound on the burstiness of traffic exiting from a tandem section of the system, in terms of the burstiness of the incoming traffic. This burstiness bound further allows us to provide a bound on the maximum number of parts in the system, and the maximum delay. It also enables us to analyze the performance of some systems controlled by the use of traffic smoothing regulators. The maximum delay can remain bounded even in the heavy traffic limit, when all stations are 100% utilized.

author list (cited authors)

  • Winograd, G. I., & Kumar, P. R

citation count

  • 10

complete list of authors

  • Winograd, GI||Kumar, PR

publication date

  • June 1996