Advanced Markovian Queueing Models

3.1 Bulk Input (M[X]/M/1)

Concept: In the M[X]/M/1 model, arrivals occur in random-sized batches rather than one at a time. Each batch size is an integer-valued random variable $X$ with known probability distribution $P(X = k) = p_k$.

• Interarrival times: Exponential (rate $\lambda$)
• Batch sizes: Random, with finite mean $E[X] = \sum_k k p_k$
• Service: Exponential, single server, FCFS

Why It Matters: This model captures real-world phenomena where customers come in groups, which leads to “jumps” in system states.

Balance Equation (for state $n$): Let $\pi_n$ be the steady-state probability. The equations become more complex since transitions can increase by more than 1:

$$\lambda \sum_{k=1}^{n} p_k \pi_{n-k} + \mu \pi_{n+1} = (\lambda + \mu) \pi_n$$

Use Case:

• Airports: Passengers from a flight all arrive together at immigration
• Warehouses: Pallets or boxes with multiple items arrive for unpacking

---

3.2 Bulk Service (M/M[Y]/1)

Concept: In M/M[Y]/1, a single server serves a batch of up to Y customers at a time.

• Interarrival times: Exponential (rate $\lambda$)
• Service time: Exponential (rate $\mu$) for the whole batch
• Service batch size: Random variable $Y$ with max capacity $b$

Variants:

1. Threshold bulk service: Waits until $m$ customers are present before service starts.
2. Bounded batch size: Always serves up to $b$ customers if available.

System Modeling: This model modifies the birth-death framework to allow for multiple departures:

• Departure rate from $n$ customers depends on batch service size.
• The probability generating function (PGF) is often used for analysis.

Use Case:

• Elevators or cable cars: Wait to fill a minimum number before moving.
• Batch email systems: Emails are processed in groups periodically.

---

3.3 Erlangian Models (M/Ek/1 and Ek/M/1)

(a) M/Ek/1: Erlang Service Time

• Interarrival time: Exponential (rate $\lambda$)
• Service time: Erlang-k, i.e., sum of $k$ exponential phases
• More realistic than exponential since variability is lower

Why Erlang-k?

• Reduces service time variance:

$$\text{Var}(S) = \frac{1}{k \mu^2}$$

• For $k=1$, the model becomes M/M/1
• For $k \rightarrow \infty$, the service becomes deterministic

State Space: The system state includes:

• Number of customers
• Current phase of service

Modeling Method:

• Transform system into a continuous-time Markov chain with $k$ sub-states per service

(b) Ek/M/1: Erlang Interarrival Time

• Interarrival time: Erlang-k
• Service time: Exponential

This model is more predictable in terms of arrivals, useful in controlled environments.

Use Case:

• Assembly lines: Regular spacing of products
• Multi-step approvals: Applications that go through structured phases

---

3.4 Priority Queue Disciplines

Concept: Priority queues assign importance levels to different classes of customers.

Types of Priority:

1. Preemptive Resume:

   • Higher priority interrupts lower priority
   • Lower priority resumes later
   • Requires modeling with preemption state

2. Preemptive Repeat:

   • Lower priority restarts service after interruption
   • Used in real-time systems with deadline requirements

3. Non-Preemptive:

   • Higher priority waits until current customer finishes

Mathematical Framework:

• Separate arrival and service rates for each class $\lambda_i, \mu_i$
• Balance equations must consider class transitions and service preemption

Mean Waiting Time (for Non-Preemptive, 2 classes):

Let:

• Class 1 = High priority
• Class 2 = Low priority

Then:

$$W_{q,2} = \frac{\lambda_1}{\mu(\mu - \lambda_1)} + \frac{\rho}{\mu(1 - \rho)}$$

Use Case:

• Cloud services: Real-time video traffic (high priority) vs background updates
• Healthcare: Triage-based medical queueing

---

3.5 Retrial Queues

Concept: Retrial queues model frustrated customers who leave when they find the server busy and return later to retry.

• No physical waiting room
• Orbit customers retry after a delay (e.g., exponentially distributed)
• The retry mechanism behaves like a secondary Poisson process

State Representation:

• $n$: number in orbit
• $0/1$: whether the server is idle or busy

Balance Equations:

• Involve two-dimensional state space
• More complex than standard birth-death models

Key Performance Measures:

• Orbit size distribution
• Waiting time before successful service
• Blocking probability

Use Case:

• Telephony systems: Redial after busy signal
• Web traffic: Retry after a failed login/server timeout

---

Summary Table (Expanded)

Model	Core Idea	Mathematical Feature	Real-Life Example
M[X]/M/1	Bulk arrivals	General batch size distribution	Airport arrivals from flights
M/M[Y]/1	Bulk service	Max group size per service	Elevators, ride-share pooling
M/Ek/1 or Ek/M/1	Structured service or arrivals	Erlang distribution	Phased diagnostic, fixed-spaced production
Priority Queues	Class-based preferences	Preemption & service discipline	Hospitals, premium user access
Retrial Queues	Retry instead of wait	Orbit state + retry process	Phone redial systems, failed web login attempts