Discrete Event Simulation of a Custom Multi-Server Queuing System

This project is divided into two main parts. The first involves developing a simulation program for a custom queuing system. The second part focuses on modifying the simulation to solve an optimisation problem.

System Specifications

• The system consists of a dispatcher and multiple servers, divided into two groups:
  • Group 0: Handles short jobs with a service time limit.
  • Group 1: Has no service time limit.
  • Each group has at least one server.
• Jobs are routed to the appropriate group based on user indication.
  • If a server is available in the group, the job is processed; otherwise, it joins the queue.
• Jobs exceeding the service time limit in Group 0 are terminated and sent to Group 1 for reprocessing.
• Jobs completed in Group 0 within the service time limit, as well as those completed in Group 1, leave the system permanently.
• Communication times between the dispatcher and servers are negligible, with system response time depending solely on queues and servers.

Discrete Events

The key events in the system are:

• Arrival of a new job at the dispatcher.
• Departure of a job from a server:
  • For Group 1, a departed job is one whose service is completed.
  • For Group 0, a departed job can be either a killed or completed job.

Note: The arrival of a recirculated job (killed in Group 0) is not treated as a separate event, as it coincides with the departure event from a Group 0 server. The simulation handles these events together.

The simulation assumes that an arrival event and a departure event will not occur simultaneously.

High-Level Workflow

Simulation Program

Trace Mode

In Trace Mode, the simulation reads inter-arrival times, service times, and server groups from configuration files.

Random Mode

Inter-Arrival Time Distribution

Inter-arrival times are generated as the product of two random numbers, 𝑎1𝑘 and 𝑎2𝑘:

𝑎𝑘 = 𝑎1𝑘 × 𝑎2𝑘

Where 𝑎1𝑘 is exponentially distributed with a mean arrival rate 𝜆 requests/second, and 𝑎2𝑘 is uniformly distributed in the interval [𝑎2ℓ, 𝑎2𝑢].

Job Class Probabilistic Distribution

The probability that a job is assigned to Group 0 is 𝑝0 ∈ (0, 1), independently generated for each job.

Service Time Distribution

Service times follow the Cumulative Density Function (CDF) as shown below.

Where 𝐺0(𝑡) represents the service time distribution for Group 0 jobs, and 𝐺1(𝑡) for Group 1 jobs.

Reproducibility

In Random Mode, the simulation saves the state of the random generator before each run. To reproduce results, the saved state is reloaded. The random.getstate() function is used to capture the random state, and it can be deactivated to reproduce specific results.

Getting Started

To run the simulation program, use:

python3 simulate.py configSetNumber

Where configSetNumber is the ID of a configuration set, which can be any integer between 0 and 6 based on the provided samples.

Optimiser Program

Parameters

Assume the system has the following parameters:

• Total number of servers: n = 10
• Service time limit (Tlimit) for Group 0 servers: 3.3
• Inter-arrival times: λ = 3.1, a2ℓ = 0.85, a2u = 1.21
• Probability (p0) that a job is directed to Group 0: 0.74
• Service times:
  • For Group 0: α0 = 0.5, β0 = 5.7, η0 = 1.9
  • For Group 1: α1 = 2.7, η1 = 2.5

The program determines the optimal number of Group 0 servers (n0) to minimise the weighted mean response time:

wrt = 0.83 x mrt0 + 0.059 x mrt1

With constraints that at least one server is present in each group (1 ≤ n0 ≤ n − 1).

Optimisation Process

The modified simulation program removes trace mode components and incorporates an exhaustive search loop to compare systems with different values of n0. Using the Common Random Numbers Method, the same set of random numbers is used across all configurations for fairness in comparison.

• Simulation length: 5000
• Number of independent replications: 30
• Simulations per replication: 9 (for each value of n0)
• Transient window size: 500

Results are analysed statistically using:

• Mean, standard deviation, and 95% confidence intervals.
• Approximate Visual Tests.
• Pairwise T-Tests.

For detailed implementation and analysis, refer to the report.

Getting Started

To run the optimiser program, use:

python3 optimiser.py

File Structure

|-- config/                     # system configuration
|   |-- mode_*.txt              # simulation mode
|   |-- para_*.txt              # system parameters
|   |-- interarrival_*.txt      # interarrival times
|   |-- service_*.txt           # service times
|-- output/                     # trace logs and outputs
|   |-- mrt_*.txt               # mean response time
|   |-- dep_*.txt               # departed jobs
|-- rand/                       # random state settings
|   |-- rand_state_sim.p        # random state for simulation
|   |-- rand_state_opt_*.p      # random state for optimiser
|-- simulate.py                 # simulation program
|-- optimiser.py                # optimiser progream
|-- plot.py                     # graph plotter
|-- transient.py                # transient window analyser

Configurations

• mode_*.txt specifies whether the simulation runs in random or trace mode.

Trace Mode

• para_*.txt contains three lines of parametric inputs:

  3 # Number of servers (n)
  1 # Number of Group 0 servers (n0)
  3 # Service time limit (Tlimit)

• interarrival_*.txt lists inter-arrival times:

  2.0000 # Inter-arrival time for job 1
  8.0000 # Inter-arrival time for job 2
  1.0000 # Inter-arrival time for job 3

• service_*.txt contains service time and server group for each job:

  5.0000 1 # Service time, server group
  4.0000 0 # Service time, server group
  9.0000 0 # Service time, server group

The number of lines in interarrival_*.txt must match service_*.txt.

Random Mode

• para_*.txt contains four lines of parametric inputs:

  5 # Number of servers (n)
  2 # Number of Group 0 servers (n0)
  3 # Service time limit (Tlimit)
  200 # Simulation end time (time_end)

• interarrival_*.txt contains inter-arrival time parameters:

  0.9 0.91 1.27 # lambda, a2ℓ, a2u

• service_*.txt contains three lines of service time parameters:

  0.7 # p0
  1.2 3.6 2.1 # α0, β0, η0 (Group 0)
  2.8 4.1 # α1, η1 (Group 1)

Trace Logs

• mrt_*.txt: Contains mean response times for completed Class 0 and Class 1 jobs.

  • In Random Mode, only jobs completed by time_end are included:

  5.5000 7.0000 # mrt0, mrt1

• dep_*.txt: Contains arrival time, departure time, and job classification for each job, ordered by completion time.

  • In Trace Mode, all jobs are processed; the number of lines equals the number of jobs.
  • In Random Mode, logs include all jobs completed by time_end:

  4.1000 7.2000 0 # Arrival time, departure time, class
  2.1000 7.3000 1 # Arrival time, departure time, class
  4.4000 16.1000 r0 # Arrival time, departure time, class