Real-Time Queueing Network Theory John P. Lehoczky Presented by Akramul Azim Department of Electrical and Computer Engineering University of Waterloo, Canada

1 Outline Fundamentals Queueing theory RT queueing theory Contributions

RT network queueing theory Analysis Simulation studies

Reducing lateness Critics and Reviews 2 Queueing Theory - Basics Queuing Theory deals with systems of the following type:

Input Process Output Process Queue

Example Bank Input Process Customers arrive at bank Output Process

Tellers serve the customers 3 Queueing Theory - Terminology and Notation State of the system Number of customers in the queueing system (includes customers

in service) Queue length Number of customers waiting for service = State of the system - number of customers being served M/M/1 Queue Single Server/Queue, arrivals follow poisson process, and job service times have an exponential distribution

4 Queueing Theory - Terminology and Notation N(t) = State of the system at time t, t 0 Pn(t) = Probability that exactly n customers are in the queueing system at time t n = Mean arrival rate (expected # arrivals per unit time) of new customers when n customers are in the system

s = Number of servers/queues (parallel service channels) n = Mean service rate for overall system (expected # customers completing service per unit time) when n customers are in the system 5 Real-Time Queueing Theory

Applications/tasks/jobs/packets have explicit timing requirements (deadlines) Stochastic task arrivals, execution time, and network routing Avoid over-provisioning of resources 6 Real-Time Queueing Network Theory

Real-time network queueing theory combines, 1) Hard real-time system scheduling theory 2) Heavy traffic queueing theory 3) Jackson network theory 7

Hard Real-time System Scheduling Theory Typical hard real-time system requirements Scheduling policies like EDF 8 Heavy Traffic Queueing Theory Heavy traffic is the case when traffic intensity nears 1

Timing behaviour of a RT queue becomes nearly deterministic in heavy traffic 9 Jackson Network A Jackson network is connects queue (e.g., M/M/1) at each node

Tasks may arrive any node in the network Tasks have end-to-end deadlines 10 RT Queueing Theory Terminologies Lead-time (l): The time remaining until the tasks deadline. Lateness: Negative lead-times

State variable: (N,l1,,lN), where N is the number of tasks Lead time vector: (l1(t),,lQ(t(t)), where Q(t) is the number in the system at time t 11 RT Queueing Network Terminologies P = (pij): K K routing matrix where pjk represents the probability

that a task leaving node j goes to node k = (1,, K), the arrival rates for independent Poisson external task arrival process to each node = (1 ,, k), initial deadline distribution = (1, , k) , the service rates = (1, , k), the total arrival rate to each node j = j/ j , the traffic intensity of total task arrivals

12 Facts Queueing Theory Lead-time vector depends on three factors: 1. The number of tasks in the queue 2. The tasks deadline distribution 3. The queue discipline (scheduling policy)

13 Facts Queueing Network Theory Lead-time vector of a node depends on four factors: 1. The total task arrival rate 2. The tasks deadline distribution of that node 3. The queue discipline (scheduling policy) 4. the occupancy of the node (queue length)

14 Experimental Analysis Simulation study performed Assume 2 stations in the network Nodes have a Queue, = .95, traffic intensity = 0.95 Task deadlines are at least 40

Two clocks are used: (1) Global (2) Local Global clock advances constantly Local clock advances only when queue lengths satisfy some precondition 15 Queue 1: Deadlines = 60 + 30 exp(1), Local Clk= 20

Note: 60 + 30 exp(1) = 141.54 16 Queue 1: Deadlines = 60 + 30 exp(1), , Local Clk= 40 17 Queue 1: Deadlines = 60 + 30 exp(1), , Local Clk= 60

18 Queue 2: Deadlines = 60 + 30 exp(1), , Local Clk= 20 19 Queue 2: Deadlines = 60 + 30 exp(1), , Local Clk= 40

20 Queue 2: Deadlines = 60 + 30 exp(1), , Local Clk= 60 21 Queue 1: Deadlines = 30 + 60 exp(1), , Local Clk= 20

Note: 30 + 30 exp(1) = 193.09 22 Queue 1: Deadlines = 30 + 60 exp(1), , Local Clk= 40 23

Queue 1: Deadlines = 30 + 60 exp(1), , Local Clk= 60 24 Queue 1: Deadlines = 30 + 60 exp(1), , Local Clk= 80 25

Queue 2: Deadlines = 30 + 60 exp(1), , Local Clk= 20 26 Queue 2: Deadlines = 30 + 60 exp(1), , Local Clk= 40 27

Queue 2: Deadlines = 30 + 60 exp(1), , Local Clk= 60 28 Queue 2: Deadlines = 30 + 60 exp(1), , Local Clk= 80 29

Simulation Findings Queueing theory can analyze complex network structures Task lead time profiles with reasonable accuracy at high, but not extreme 30

Facts - Lateness If task deadlines are 40, approximately 40% of the tasks will miss their deadlines If task deadlines are increased to 60, still 20% will be late. This holds even though the best scheduling policy used

31 Control Policies to Reduce Lateness Blocking policy: 1. Tasks are blocked if the total number of tasks reaches some level 2. Individual queue reaches some threshold Abort policy:

1. Tasks should be aborted as soon as they become late 32 Blocking Probabilities (Mean task deadlines = 40) Blocking strategy can reduce the task lateness from 40% to 4% 33

Critics Unable to provide guarantee of meeting deadlines of all tasks in the worst-case Simulation study performed with distributions but not any real data set or application Worst-case resource constraints not taken into account Analysis on bounding buffer requirements is absent

34 Conclusions and Future Work Can be used for modelling probabilistic real-time systems Can be used to assess queue control policies Can analyze large-scale soft-RT systems/networks Future work may include periodic arrival process and deriving bounds on queue length or buffer requirements.

35 Thank You. Any Questions? 36