Mathematical Model - University of Waterloo

Mathematical Model - University of Waterloo

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

Recently Viewed Presentations

  • Psy631 Psychological Assessment - Francis Marion University

    Psy631 Psychological Assessment - Francis Marion University

    Psy631 Psychological Assessment William P. Wattles, Ph.D. * * * * * * * * * * * * * * * * * * * * * * Test Construction. Psychologists who develop and conduct research with tests and...
  • N N E I S T  A T

    N N E I S T A T

    Obtain a Transient Letter. This letter is obtained from the registrar at the students home school and serves both as a waiver of prerequisite courses and as a protection for students on the agreement of transfer or coursework back to...
  • AmeriCorps State Funding 2019-2020 A P P L

    AmeriCorps State Funding 2019-2020 A P P L

    The submitted reports describe evaluations that were conducted relatively recently, preferably within the last six years; The submitted reports show a meaningful and significant positive effect on program beneficiaries in at least one key outcome of interest.
  • Decimals Numbers and Number Sense By Kathy Russo

    Decimals Numbers and Number Sense By Kathy Russo

    four tenths is LESS THAN six tenths four tenths IS EQUAL TO forty hundredths Compare these decimals. 0.4 = 0.40 0.008 eight tenths is greater than eight hundredths eight hundredths is greater than eight thousandths 0.8 0.08 > > Compare...
  • Coleman, Guillory, Hernandez, Seale Teacher(s): Time: This Course:

    Coleman, Guillory, Hernandez, Seale Teacher(s): Time: This Course:

    Teacher(s): Time: The. Course Organizer. Student: Course Dates: Course Standards. This Course: Course Questions: is. about. U. S History Early. The story of American from exploration to reconstruction and how culture, economics, government, and geography have affected the shaping of...
  • testing - CS Department

    testing - CS Department

    Gathering unnecessary data. What do you expect from a WallPaper app? Are you agree a WallPaper app with gathering your phone number, subscriber identifier (e.g., IMSI), and the currently entered voice mail number on the phone?
  • ESnet Defined: Challenges and Overview Department of Energy ...

    ESnet Defined: Challenges and Overview Department of Energy ...

    ESnet Status Update ESCC July 18, 2007 William E. Johnston ESnet Department Head and Senior Scientist Energy Sciences Network Lawrence Berkeley National Laboratory
  • Heart Message - Ms. White's Science BLOG

    Heart Message - Ms. White's Science BLOG

    Which of the following best describes a living cell: a building block, a living organism, a complex factory, or all of the above? Explain your choice.