Semidefinite optimization for transient analysis of queues

Abstract

We derive an upper bound on the tail distribution of the transient waiting time for the GI/GI/1 queue from a formulation of semidefinite programming (SDP). Our upper bounds are expressed in closed forms using the first two moments of the service time and the interarrival time. The upper bounds on the tail distributions are integrated to obtain the upper bounds on the corresponding expectations. We also extend the formulation of the SDP, using the higher moments of the service time and the interarrival time, and calculate upper bounds and lower bounds numerically.