gallery_lukumar_reentrant.m

function model = gallery_lukumar_reentrant(schedStrategy)
% GALLERY_LUKUMAR_REENTRANT Lu-Kumar unstable re-entrant line example
%
% This example implements the classic Lu-Kumar re-entrant line network,
% which demonstrates that queueing networks can be unstable even when
% the utilization at each station is strictly less than 1.
%
% Network structure:
%   - 2 stations (servers)
%   - 4 job classes forming a re-entrant line
%   - Station 1 serves classes 1 and 4
%   - Station 2 serves classes 2 and 3
%   - Job path: Source -> Class1 -> Class2 -> Class3 -> Class4 -> Sink
%
% Under FCFS scheduling: The network is stable when all station
% utilizations are < 1.
%
% Under certain priority policies (e.g., HOL with class 4 > class 1 at
% station 1, and class 2 > class 3 at station 2): The network can become
% unstable due to the "virtual bottleneck" phenomenon, even with
% utilization < 1 at each station.
%
% Reference:
%   Lu, S.H. and Kumar, P.R. (1991), "Distributed Scheduling Based on Due
%   Dates and Buffer Priorities", IEEE Transactions on Automatic Control,
%   Vol. 36, No. 12, pp. 1406-1416.
%
% Usage:
%   model = gallery_lukumar_reentrant();          % FCFS scheduling (stable)
%   model = gallery_lukumar_reentrant('FCFS');    % FCFS scheduling (stable)
%   model = gallery_lukumar_reentrant('HOL');     % HOL priority scheduling
%   model = gallery_lukumar_reentrant('PS');      % Processor sharing
%
% Copyright (c) 2012-2026, Imperial College London
% All rights reserved.
 
if nargin < 1
    schedStrategy = 'FCFS';
end
 
% Convert string to scheduling strategy
switch upper(schedStrategy)
    case 'FCFS'
        sched1 = SchedStrategy.FCFS;
        sched2 = SchedStrategy.FCFS;
    case 'HOL'
        sched1 = SchedStrategy.HOL;
        sched2 = SchedStrategy.HOL;
    case 'PS'
        sched1 = SchedStrategy.PS;
        sched2 = SchedStrategy.PS;
    otherwise
        sched1 = SchedStrategy.FCFS;
        sched2 = SchedStrategy.FCFS;
end
 
model = Network('Lu-Kumar-Reentrant');
 
%% Block 1: Nodes
source = Source(model, 'Source');
station1 = Queue(model, 'Station1', sched1);
station2 = Queue(model, 'Station2', sched2);
sink = Sink(model, 'Sink');
 
%% Block 2: Job Classes
% For HOL scheduling, priority is specified as the third parameter
% Higher value = higher priority
%
% "Bad" priority policy for instability demonstration:
%   Station 1: Class 4 (priority 1) > Class 1 (priority 0)
%   Station 2: Class 2 (priority 1) > Class 3 (priority 0)
%
% Under this policy, jobs in Class 4 are served before Class 1 at Station 1,
% and jobs in Class 2 are served before Class 3 at Station 2.
 
class1 = OpenClass(model, 'Class1', 0);  % Lower priority at Station 1
class2 = OpenClass(model, 'Class2', 1);  % Higher priority at Station 2
class3 = OpenClass(model, 'Class3', 0);  % Lower priority at Station 2
class4 = OpenClass(model, 'Class4', 1);  % Higher priority at Station 1
 
%% Block 3: Arrival Process
% External arrivals only to Class 1
arrivalRate = 0.45;  % arrival rate lambda
source.setArrival(class1, Exp(arrivalRate));
source.setArrival(class2, Disabled());
source.setArrival(class3, Disabled());
source.setArrival(class4, Disabled());
 
%% Block 4: Service Times
% Service rates chosen so that utilization at each station < 1
% Station 1 serves Class 1 and Class 4
% Station 2 serves Class 2 and Class 3
%
% Mean service times:
%   m1 = 1.0 (Class 1 at Station 1)
%   m2 = 1.0 (Class 2 at Station 2)
%   m3 = 1.0 (Class 3 at Station 2)
%   m4 = 1.0 (Class 4 at Station 1)
%
% Station utilizations:
%   rho1 = lambda * (m1 + m4) = 0.45 * (1 + 1) = 0.90 < 1
%   rho2 = lambda * (m2 + m3) = 0.45 * (1 + 1) = 0.90 < 1
 
m1 = 1.0;  % Mean service time for Class 1 at Station 1
m2 = 1.0;  % Mean service time for Class 2 at Station 2
m3 = 1.0;  % Mean service time for Class 3 at Station 2
m4 = 1.0;  % Mean service time for Class 4 at Station 1
 
% Station 1 services (Class 1 and Class 4)
station1.setService(class1, Exp(1/m1));
station1.setService(class2, Disabled());
station1.setService(class3, Disabled());
station1.setService(class4, Exp(1/m4));
 
% Station 2 services (Class 2 and Class 3)
station2.setService(class1, Disabled());
station2.setService(class2, Exp(1/m2));
station2.setService(class3, Exp(1/m3));
station2.setService(class4, Disabled());
 
%% Block 5: Routing (Re-entrant Line Topology)
% Job path: Source -> Class1@Station1 -> Class2@Station2 ->
%           Class3@Station2 -> Class4@Station1 -> Sink
%
% The re-entrant structure means jobs visit Station 1 twice (as Class 1
% first, then as Class 4) and Station 2 twice (as Class 2 first, then
% as Class 3).
 
P = model.initRoutingMatrix();
 
% Source -> Class1 at Station1
P{class1, class1}(source, station1) = 1;
 
% Class1 at Station1 -> Class2 at Station2 (class switch)
P{class1, class2}(station1, station2) = 1;
 
% Class2 at Station2 -> Class3 at Station2 (class switch, same station)
P{class2, class3}(station2, station2) = 1;
 
% Class3 at Station2 -> Class4 at Station1 (class switch)
P{class3, class4}(station2, station1) = 1;
 
% Class4 at Station1 -> Sink
P{class4, class4}(station1, sink) = 1;
 
model.link(P);
 
end