BIG QUEUES

By X. CAVIR

CONTENTS THE SINGLE SERVER QUEUE THE SINGLE-SERVER QUEUEING MODEL ONE-DIMENSIONAL LARGE DEVIATIONS APPLICATION TO QUEUES WITH LARGE BU?ERS APPLICATION TO QUEUES WITH MANY SOURCES LARGE DEVIATIONS IN EUCLIDEAN SPACES SOME EXAMPLES PRINCIPLE OF THE LARGEST TERM LARGE DEVIATIONS PRINCIPLE CUMULANT GENERATING FUNCTIONS CONVEX DUALITY CRAM´ER’S THEOREM SANOV’S THEOREM FOR FINITE ALPHABETS A GENERALISATION OF CRAM´ER’S THEOREM MORE ON THE SINGLE SERVER QUEUE QUEUES WITH CORRELATED INPUTS QUEUES WITH MANY SOURCES AND POWER-LAW SCALINGS QUEUES WITH LARGE BU?ERS AND POWER-LAW SCALINGS INTRODUCTION TO ABSTRACT LARGE DEVIATIONS TOPOLOGY AND METRIC SPACES DE?NITION OF LDP THE CONTRACTION PRINCIPLE OTHER USEFUL LDP RESULTS CONTINUOUS QUEUEING MAPS INTRODUCTION AN EXAMPLE: QUEUES WITH LARGE BU?ERS THE CONTINUOUS MAPPING APPROACH CONTINUOUS FUNCTIONS SOME CONVENIENT NOTATION QUEUES WITH IN?NITE BU?ERS QUEUES WITH FINITE BU?ERS QUEUEING DELAY PRIORITY QUEUES 5 10 PROCESSOR SHARING 5 11 DEPARTURES FROM A QUEUE 5 12 CONCLUSION LARGE-BU?ER SCALINGS THE SPACE OF INPUT PROCESSES LARGE DEVIATIONS FOR PARTIAL SUMS PROCESSES LINEAR GEODESICS DEPARTURE PROCESS MEAN RATE OF DEPARTURES QUASI-REVERSIBILITY 6 10 SCALING PROPERTIES OF NETWORKS 6 11 STATISTICAL INFERENCE FOR THE TAIL-BEHAVIOUR OF QUEUES MANY-FLOWS SCALINGS TRA?C SCALING TOPOLOGY FOR SAMPLE PATHS THE SAMPLE PATH LDP EXAMPLE SAMPLE PATH LDPS APPLYING THE CONTRACTION PRINCIPLE OVER?OW AND UNDER?OW PATHS TO OVER?OW 7 10 PRIORITY QUEUES 7 11 DEPARTURES FROM A QUEUE LONG RANGE DEPENDENCE WHAT IS LONG RANGE DEPENDENCE? IMPLICATIONS FOR QUEUES SAMPLE PATH LDP FOR FRACTIONAL BROWNIAN MOTION SCALING PROPERTIES HOW DOES LONG RANGE DEPENDENCE ARISE? PHILOSOPHICAL DI?CULTIES WITH LRD MODELLING MODERATE DEVIATIONS SCALINGS MOTIVATION TRA?C PROCESSES QUEUE SCALINGS SHARED BU?ERS MIXED LIMITS 10 INTERPRETATIONS 10 1 E?ECTIVE BANDWIDTHS 10 2 NUMERICAL ESTIMATES 10 3 A GLOBAL APPROXIMATION 10 4 SCALING LAWS 10 5 TYPES OF TRA?C