CPE 619 Queueing NetworksOverviewOpen Queueing NetworksClosed Queueing NetworksMixed Queueing NetworksSeries NetworksSeries Networks (cont’d)Product-Form NetworkExample 32.1General Open Network of QueuesGeneral Open Network of Queues (cont’d)Closed Product-Form NetworksBCMP NetworksBCMP Networks (cont’d)Slide 15Non-Markovian Product Form NetworksNon-Markovian PFNs (cont’d)Slide 18Machine Repairman ModelCentral Server ModelTypes of Service CentersSummaryOperational LawsSlide 24Slide 25Operational QuantitiesUtilization LawExample 33.1Forced Flow LawForced Flow Law (cont’d)Slide 31Bottleneck DeviceExample 33.2Example 33.2 (cont’d)Slide 35Transition ProbabilitiesTransition Probabilities (cont’d)Slide 38Example 33.3Example 33.3 (cont’d)Little's LawExample 33.4Example 33.4 (cont’d)General Response Time LawGeneral Response Time Law (cont’d)Example 33.5Interactive Response Time LawExample 33.6Bottleneck AnalysisBottleneck Analysis (cont’d)Slide 51Bottleneck Analysis: ProofProof (cont’d)Slide 54Slide 55Typical Asymptotic BoundsTypical Asymptotic Bounds (cont’d)Example 33.7Example 33.7: Asymptotic BoundsExample 33.7 (cont’d)Example 33.8Slide 62CPE 619Queueing NetworksAleksandar MilenkovićThe LaCASA LaboratoryElectrical and Computer Engineering DepartmentThe University of Alabama in Huntsvillehttp://www.ece.uah.edu/~milenkahttp://www.ece.uah.edu/~lacasa2OverviewQueueing Network: model in which jobs departing from one queue arrive at another queue (or possibly the same queue)Open and Closed Queueing NetworksProduct Form NetworksQueueing Network Models of Computer Systems3Open Queueing NetworksOpen queueing network: external arrivals and departures Number of jobs in the system varies with timeThroughput = arrival rate Goal: To characterize the distribution of number of jobs in the system4Closed Queueing NetworksClosed queueing network: No external arrivals or departuresTotal number of jobs in the system is constant“OUT” is connected back to “IN” Throughput = flow of jobs in the OUT-to-IN linkNumber of jobs is given, determine the throughput5Mixed Queueing NetworksMixed queueing networks: Open for some workloads and closed for others  Two classes of jobs. Class = types of jobsAll jobs of a single class have the same service demands and transition probabilities. Within each class, the jobs are indistinguishable6Series Networksk M/M/1 queues in seriesEach individual queue can be analyzed independently of other queuesArrival rate= If i is the service rate for ith server:7Series Networks (cont’d)Joint probability of queue lengths: product form network8Product-Form NetworkAny queueing network in which:When fi(ni) is some function of the number of jobs at the ith facility, G(N) is a normalizing constant and is a function of the total number of jobs in the system9Example 32.1 Consider a closed system with two queues and N jobs circulating among the queuesBoth servers have an exponentially distributed service time. The mean service times are 2 and 3, respectively. The probability of having n1 jobs in the first queue and n2=N-n1 jobs in the second queue can be shown to be:In this case, the normalizing constant G(N) is 3N+1-2N+1. The state probabilities are products of functions of the number of jobs in the queues. Thus, this is a product form network.10General Open Network of QueuesProduct form networks are easier to analyzeJackson (1963) showed that any arbitrary open network of m-server queues with exponentially distributed service times has a product form11General Open Network of Queues (cont’d)If all queues are single-server queues, the queue length distribution is:Note: Queues are not independent M/M/1 queues with a Poisson arrival process In general, the internal flow in such networks is not Poisson. Particularly, if there is any feedback in the network, so that jobs can return to previously visited service centers, the internal flows are not Poisson12Closed Product-Form NetworksGordon and Newell (1967) showed that any arbitrary closed networks of m-server queues with exponentially distributed service times also have a product form solutionBaskett, Chandy, Muntz, and Palacios (1975) showed that product form solutions exist for an even broader class of networks13BCMP Networks1. Service Disciplines: First-come-first-served (FCFS)Processor sharing (PS)Infinite servers (IS or delay centers) and Last-come-first-served-preemptive-resume (LCFS-PR) 2. Job Classes: The jobs belong to a single class while awaiting or receiving service at a service center, but may change classes and service centers according to fixed probabilities at the completion of a service request14BCMP Networks (cont’d)3. Service Time Distributions: At FCFS service centers, the service time distributions must be identical and exponential for all classes of jobs At other service centers, where the service times should have probability distributions with rational Laplace transformsDifferent classes of jobs may have different distributions 4. State Dependent Service: The service time at a FCFS service center can depend only on the total queue length of the centerThe service time for a class at PS, LCFS-PR, and IS center can also depend on the queue length for that class, but not on the queue length of other classesMoreover, the overall service rate of a subnetwork can depend on the total number of jobs in the subnetwork15BCMP Networks (cont’d)5. Arrival Processes: In open networks, the time between successive arrivals of a class should be exponentially distributed No bulk arrivals are permitted The arrival rates may be state dependentA network may be open with respect to some classes of jobs and closed with respect to other classes of jobs16Non-Markovian Product Form NetworksBy Denning and Buzen (1978) 1. Job Flow Balance: For each class, the number of arrivals to a device must equal the number of departures from the device2. One Step Behavior: A state change can result only from single jobs either entering the system, or moving between pairs of devices in the system, or exiting from the system. This assumption asserts that simultaneous job-moves will not be observed.3. Device Homogeneity: A device's service rate for a particular class does not depend on the state of the system in any way except for the total