How to Solve Network Performance Assignments Involving Closed Queueing Networks

A Closed Queueing Network (CQN) is a system where a fixed number of requests circulate among different queues without external arrivals or departures. These networks are widely used in modeling computer systems, web servers, and cloud computing architectures.

In the context of web performance evaluation, CQNs help analyze the response time, utilization, and efficiency of different components of a web system. The AnyCo Web Server problem is an example where HTTP requests move through a network of processors, routers, and storage devices.

1. Identifying the Queues and Their Characteristics

In a Closed Queueing Network (CQN), different queues represent processing elements such as routers, servers, and storage units. Each queue has unique characteristics, such as processing times, queue types (M/M/1, delay type), and the number of requests it can handle simultaneously. Understanding these characteristics is crucial for correctly modeling the system and ensuring accurate performance analysis. Identifying queues helps in defining service demands, transition probabilities, and determining the overall system efficiency. Every CQN-based problem consists of the following:

• Queues (Servers or Processing Units): Components where requests wait for service.
• Routing Probabilities (Pij): Probability that a request moves from one queue to another.
• Service Demands (Di): Time taken to process a request at each queue.
• Visit Ratios (Vi): Expected number of times a request visits a particular queue.

For example, in the AnyCo Web Server system:

• Users think for a while before making a request (Queue 1 - Delay Type).
• Requests are routed to an ISP Router (Queue 2 - M/M/1 queue with exponential service time of 1 ms).
• The Web Server CPU (Queue 3) handles requests in four time slots.
• Requests can then go to either the Disk Server (Queue 4) or exit via the AnyCo Router (Queue 5).

2. Determining Transition Probabilities (Pij)

Transition probabilities define the likelihood of a request moving from one queue to another. These values are essential for constructing the probability matrix, which describes the flow of requests through the system. By analyzing system specifications and traffic behavior, students can determine these probabilities and use them to build the closed queueing model. Transition probabilities help in calculating visit ratios and ultimately in optimizing the network's efficiency. The transition probability matrix is constructed based on problem specifications. For the given assignment, key probabilities include:

• Requests from the CPU (Queue 3) go to the Disk (Queue 4) with 75% probability.
• The remaining 25% of the time, requests go to the AnyCo Router (Queue 5).

3. Computing Visit Ratios (Vi)

Visit ratios represent the expected number of times a request visits a specific queue before completing its journey through the network. These are computed using transition probabilities and system behavior patterns. Visit ratios help in identifying bottlenecks and assessing the workload distribution among different queues. Properly computing visit ratios allows for accurate service demand calculations and effective network performance tuning. Visit ratios define how often requests visit each queue. These are calculated using:

where Vj is the visit ratio of the previous queue and Pji is the transition probability from queue j to queue i.

Using the given routing probabilities, visit ratios can be derived by solving a system of equations based on the queue transitions.

4. Calculating Service Demands (Di)

Service demand represents the total processing time a request spends at a particular queue. It is calculated using the formula , Di=Si*Vi where Si is the average service time and is the visit ratio. Accurately determining service demands helps in performance evaluation, identifying system bottlenecks, and improving overall response time. This step is crucial for optimizing resources and ensuring balanced workload distribution across the network. The service demand for a queue is given by:

where Si is the average service time at queue i.

For example, if the Web Server CPU requires 0.08s per request and the visit ratio to the CPU is determined to be 2.5, then:

Similarly, service demands are computed for the ISP Router, Disk Server, and AnyCo Router.

5. Solving the CQN Using ClosedQN.xls

ClosedQN.xls is an analytical tool used to solve CQN models by inputting transition probabilities, visit ratios, and service demands. By entering these values into the spreadsheet and solving for different customer populations (K values), students can obtain key performance metrics like response time, queue utilization, and system throughput. The tool provides insights into network efficiency and helps in evaluating optimization strategies. After computing Pij, Vi, and Di, the next step is to input values into the ClosedQN.xls spreadsheet:

• Enter the number of customers (K) starting from 1.
• Click "Solve" to compute response times and utilizations.
• Generate graphs to visualize system performance.

6. Interpreting Results

Once the CQN model is solved, the results must be analyzed to assess network performance. Key metrics such as response time, queue utilization, and throughput provide insights into system efficiency. Identifying high utilization queues helps pinpoint bottlenecks, while response time analysis ensures that system performance meets required thresholds. This step is vital for making informed decisions about performance improvements.

• Response Time Analysis: The total response time includes the user think time and network processing time.
• Utilization Metrics: Higher utilization indicates a heavily loaded component, which may require optimization.
• Bottleneck Identification: The queue with the highest service demand and utilization is the bottleneck.

7. Evaluating System Improvements

System improvements involve modifying parameters such as network bandwidth, server capacities, and load distribution to enhance performance. For example, adding additional network links, upgrading storage systems, or implementing load balancing can significantly impact response times and efficiency. Evaluating these improvements using CQN models helps in designing optimized networks that meet user demands and improve overall performance. Many assignments ask for performance tuning recommendations. Common optimizations include:

• Increasing Network Bandwidth: For instance, changing a single T-1 link to two T-1 links reduces ISP Router delays.
• Upgrading Storage Performance: Reducing disk access time (e.g., from 50ms to 30ms) improves response time.
• Load Balancing: Distributing requests more evenly prevents overloading a single queue

Conclusion

Closed Queueing Networks are powerful tools for performance analysis in web server environments. By systematically computing transition probabilities, visit ratios, and service demands, and leveraging analytical tools like ClosedQN.xls, students can effectively model and optimize networked systems.

Mastering this approach not only helps in solving assignments but also provides valuable insights for real-world system design and network performance evaluation.