api.me

mexify_me

@brief MATLAB Coder script to generate MEX functions for me_ module.

This script generates MEX (MATLAB Executable) versions of Maximum Entropy (ME) queueing-network functions for improved performance.

See also CODER, CODER.CONFIG, CODER.TYPEOF, CODEGEN.

me_oqn_blk(M, lambda0, Ca0, mu, Cs, P, c, N, blockrule, options)

ME_OQN_BLK Maximum Entropy algorithm for single-class open queueing networks with finite buffers, loss and transfer blocking

Extends ME_OQN to open networks in which a station has a finite buffer. Two per-station policies are supported:

loss (blockrule = 0) - a job that finds the destination full is
discarded. Each station is then a censored GE/GE/c/0;N queue, and the network is the ME decomposition of Kouvatsos (1994), Section 4.

transfer blocking - a job that completes service at station i and (blockrule = 1) finds the destination j full is held in i’s

server, which cannot serve anyone else until j has room (blocking after service, BAS).

Transfer blocking is not work conserving, so a product-form approximation cannot be applied to the network as it stands. Following Tahilramani, Manjunath and Bose (1999) the network is first made work conserving by inserting a GE/GE/inf HOLDING NODE h_ij on every routing pair with p_ij > 0 and a finite-buffer destination j. The holding node absorbs the blocked job, so station i’s server is released; the delay it introduces is the residual life of the minimum of the c_j service times in progress at j, inflated geometrically because the released job may find j full again. Station i’s own service time is inflated by the same blocking probability so that the jobs queued behind the blocked one still see the server as busy. The expanded network is work conserving and is solved node by node with the censored ME queue of ME_GEGECN, iterating over the blocking probabilities and the first two moments of the flows until they converge.

INPUTS:
M - Number of stations lambda0 - External arrival rates [M x 1] Ca0 - External interarrival scv [M x 1] (>= 1 where lambda0 > 0) mu - Service rates [M x 1] Cs - Service scv [M x 1] (>= 1 at every finite-buffer station) P - Routing probabilities [M x M], P(i,j) = p_ij. Row sums

below one send the residual flow out of the network

c - Servers per station [M x 1]; Inf marks an infinite server N - Buffer capacity per station [M x 1] in jobs, in service

included; Inf marks an unbounded buffer

blockrule - Policy at each finite-buffer station [M x 1]: 0 = loss,
1 = transfer blocking (BAS)

options - (optional) struct with fields .tol (default 1e-6),
.maxiter (default 1000), .verbose (default false), .damping (default 0.5), applied to the blocking probabilities as in the relaxation scheme of the source

OUTPUTS:

Q - Mean number of jobs at each station [M x 1], including the
jobs held blocked in that station’s servers

W - Mean response time [M x 1], Q ./ T T - Throughput (carried flow) [M x 1] U - Utilization [M x 1], mean fraction of busy servers, the jobs

held blocked counted as occupying their server

Ca - Interarrival scv of the offered flow at each station [M x 1] Cd - Interdeparture scv at each station [M x 1] PBa - Probability that an arrival at each station finds it full,

averaged over the incoming streams [M x 1]

lambda - Offered arrival rate at each station [M x 1], attempts
included

iter - Number of iterations performed

References:
D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994, Section 4. H. Tahilramani, D. Manjunath, S.K. Bose, “Approximate analysis of open network of GE/GE/m/N queues with transfer blocking”, MASCOTS 1999, 164-171.

Copyright (c) 2012-2026, Imperial College London All rights reserved.

me_gegecn_pb(p, K, N, c, Cs, Ca)

ME_GEGECN_PB Blocking probability seen by one arrival stream of a censored GE/GE/c/K;N queue

Evaluates equation (4.3) of Kouvatsos (1994) on the ME queue length distribution P returned by ME_GEGECN. Because a GE arrival process is a batch (bulk) process, an arrival can be blocked while the queue holds fewer than N jobs: the term (1-tau)^(N-n) is the probability that the batch overflows the residual room, and the extra factor of the first sum accounts for the servers that are still idle. With a Poisson stream (Ca = 1, tau = 1) every term but n = N vanishes and PB reduces to the PASTA value p(N).

The stream scv CA is a per-stream quantity, so the same node solution P yields a different blocking probability for each of the flows merging into the queue: the external arrivals, the flow from each upstream station, and the flow released by each holding node. That is exactly how PBe_j, PB^i_j and PB^{h_ij}_j are obtained in the transfer-blocking algorithm of Tahilramani, Manjunath and Bose (1999).

INPUTS:
p - ME queue length distribution, p(idx) = Pr{n = K+idx-1} K - Minimum number of jobs in the queue N - Buffer capacity in jobs c - Number of servers Cs - Squared coefficient of variation of the service times Ca - Squared coefficient of variation of the interarrival times OF THE

STREAM whose blocking probability is requested

OUTPUT:
PB - Probability that an arrival of this stream finds the queue full

References:
D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994, equation (4.3). H. Tahilramani, D. Manjunath, S.K. Bose, “Approximate analysis of open network of GE/GE/m/N queues with transfer blocking”, MASCOTS 1999, 164-171, equations (12) and (14).

Copyright (c) 2012-2026, Imperial College London All rights reserved.

me_gegecn(lambda, Ca, mu, Cs, c, K, N)

ME_GEGECN Censored GE/GE/c/K;N queue by entropy maximisation

Maximum Entropy solution of the single-class censored FCFS GE/GE/c/K;N queue of Kouvatsos (1994), Section 4.1. The queue holds at most N jobs and never fewer than K; arrivals finding N jobs present are turned away and departures are not allowed from state K. For a queue embedded in an OPEN network K is always 0; positive K arises in closed networks, where it records the minimum occupancy forced by the remaining stations being full.

The ME state probabilities subject to normalisation, the marginal utilisations u(l), the mean queue length excluding J jobs and the full-buffer probability coincide with the global balance solution

p(n) = p(K) * G_n * x^h(n) * y^f(n), n = K+1,…,N (4.2)

with G_n = prod_{l=K+1}^{m(n)} g(l), J = max(c,K+1), h(n) = max(0,n-J), f(n) = max(0,n-N+1), m(n) = max{K+1,min(c,n)}, and the Lagrangian coefficients g(l), x, y given in closed form by raw system data. The coefficients are invariant to N and K, so letting K -> 0 and N -> Inf recovers the stable GE/GE/c solution used by ME_OQN.

INPUTS:

lambda - Arrival rate offered to the queue (attempts, including the: arrivals that are turned away)
Ca - Squared coefficient of variation of the interarrival times: (Ca >= 1: the GE distribution is defined for scv >= 1)

mu - Service rate of one server Cs - Squared coefficient of variation of the service times

(Cs >= 1)

c - Number of servers (c >= 1, finite) K - Minimum number of jobs in the queue (K >= 0) N - Buffer capacity in jobs, in service included (N > K, finite)

OUTPUTS:

p - Queue length distribution, p(idx) = Pr{n = K+idx-1}, idx = 1..N-K+1 L - Mean number of jobs in the queue, sum_n n*p(n) U - Utilization, E[min(n,c)]/c (mean fraction of busy servers) PB - Probability that an arrival of the queue’s own aggregate stream

finds the queue full, eq. (4.3)

Lq - Mean number of jobs waiting, L - E[min(n,c)]

Reference:

D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994, Section 4.1, equations (4.1)-(4.3).

me_gegec_mql(lambda, Ca, mu, Cs, c)

ME_GEGEC_MQL Mean queue length of a stable infinite-capacity GE/GE/c/FCFS queue

Exact ME solution of Kouvatsos (1994), equation (3.9). Shared by the infinite-capacity branch of ME_OQN_BLK; ME_OQN carries a numerically identical local copy because it is compiled to a MEX file by MEXIFY.

INPUTS:: lambda - Arrival rate Ca - Squared coefficient of variation of the interarrival times mu - Service rate of one server Cs - Squared coefficient of variation of the service times c - Number of servers (finite, c >= 1)
OUTPUT:: L - Mean number of jobs in the queue
Reference:: D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994, equation (3.9).

me_oqn(M, R, lambda0, Ca0, mu, Cs, P, c, insens, options)

ME_OQN Maximum Entropy algorithm for Open Queueing Networks

Implements the ME algorithm from Kouvatsos (1994) “Entropy Maximisation and Queueing Network Models”, Section 3.2, with the GE/GE/c building block of Section 3.4 (eq. 3.9) and the GE/GE/inf building block.

INPUTS:

M - Number of queues (stations) R - Number of job classes lambda0 - External arrival rates [M x R matrix], lambda0(i,r) = lambda_oi,r Ca0 - External arrival scv [M x R matrix], Ca0(i,r) = Caoi,r mu - Service rates [M x R matrix], mu(i,r) = mu_i,r Cs - Service scv [M x R matrix], Cs(i,r) = Cs_i,r P - Routing probability matrix [M x M x R], P(j,i,r) = p_ji,r

(probability class r goes from queue j to queue i)

c - (optional) Servers per queue [M x 1 vector]; Inf marks an: infinite-server (IS) queue (default: ones(M,1))
insens - (optional) Logical vector [M x 1]; true marks a station with: an insensitive scheduling discipline (PS, LCFS-PR), solved with the product-form mean queue length L_r = rho_r/(1-rho) instead of the FCFS GE formula (default: false(M,1))
options - (optional) struct with fields:: .tol - convergence tolerance (default: 1e-6) .maxiter - maximum iterations (default: 1000) .verbose - print iteration info (default: false)

OUTPUTS:

L - Mean queue lengths [M x R matrix] W - Mean response times [M x R matrix], W = L ./ lambda Ca - Arrival scv at each queue [M x R matrix] Cd - Departure scv at each queue [M x R matrix] lambda - Total arrival rates [M x R matrix], inclusive of self-loop

revisits (visit-based throughput)

rho - Utilizations [M x R matrix]: per-server utilization for finite: c, mean number of busy servers for IS queues

iter - Number of iterations until convergence

Reference:

D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994. Equations (3.3), (3.6), (3.7), (3.9) and the multiclass GE/GE/1/FCFS mql of Section 3.1.1.

me_mqn(M, R, openClasses, lambda0, Ca0, N, mu, Cs, P, c, refstat, insens, options)

ME_MQN Maximum Entropy algorithm for Mixed Queueing Networks

Extension of the Kouvatsos (1994) Maximum Entropy Method to mixed open/closed multiclass networks. The 1994 survey notes that the closed two-stage treatment carries over to mixed networks (Section 2.3) but gives no algorithm; this implementation composes the open (Section 3.2) and closed (Section 3.3) ME algorithms by product-form-style conditioning:

the open classes are solved by the open GE-type fixed point on the station set, ignoring the closed classes;

the closed classes are solved by the two-stage pseudo-open plus convolution algorithm on servers whose capacity is reduced by the open-class utilization, mu_c(i,r) = mu(i,r)*(1-rho_o(i));

the open mean queue lengths are inflated by the closed occupancy, L_o(i,r) <- L_o(i,r)*(1 + Lc(i)) at single-server stations.

Steps 2-3 are exact in the BCMP product-form limit (exponential services, where they reduce to the classical mixed MVA treatment) and GE-type approximations otherwise. Only single-server and infinite- server stations are supported.

INPUTS:

M - Number of queues (stations) R - Number of job classes openClasses - Logical vector [1 x R], true for open classes lambda0 - External arrival rates [M x R], zero columns for closed Ca0 - External arrival scv [M x R] N - Class populations [1 x R], Inf for open classes mu - Service rates [M x R matrix] Cs - Service scv [M x R matrix] P - Routing probability matrix [M x M x R], P(j,i,r) = p_ji,r c - (optional) Servers per queue [M x 1]; Inf marks an IS

queue; finite values must be 1 (default: ones(M,1))

refstat - (optional) Reference station per closed class [1 x R] options - (optional) struct with tol / maxiter / verbose fields

OUTPUTS:

L - Mean queue lengths [M x R matrix] W - Mean response times [M x R matrix], W = L ./ lambda Ca - Arrival scv at each queue [M x R matrix] Cd - Departure scv at each queue [M x R matrix] lambda - Throughputs at each queue [M x R matrix] rho - Utilizations [M x R matrix] X - Class throughputs [1 x R] (arrival rates for open classes,

reference-station throughputs for closed classes)

iter - Total number of fixed-point iterations

Reference:

D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994. Sections 3.2-3.3.

me_cqn(M, R, N, mu, Cs, P, c, refstat, insens, options)

ME_CQN Maximum Entropy algorithm for Closed Queueing Networks

Implements the two-stage ME algorithm from Kouvatsos (1994) “Entropy Maximisation and Queueing Network Models”, Section 3.3, for closed multiclass networks of G/G/1 and G/G/inf queues.

Stage 1 solves a pseudo-open network (no external arrivals) subject to job flow conservation and the population constraints sum_i L(i,r)=N(r), using the GE-type fixed point of the open algorithm (Section 3.2). Stage 2 builds the ME product-form solution (3.8) from the Lagrangian coefficients of Stage 1, computes the normalising constant Z(N) by a multiclass convolution, and iterates the flow (work rate) equations until the class throughputs implied by the closed ME solution agree with those used to parametrise the building blocks.

INPUTS:

M - Number of queues (stations) R - Number of job classes N - Class populations [1 x R] mu - Service rates [M x R matrix] Cs - Service scv [M x R matrix] P - Routing probability matrix [M x M x R], P(j,i,r) = p_ji,r c - (optional) Servers per queue [M x 1]; Inf marks an

infinite-server (IS) queue; finite values must be 1 (default: ones(M,1))

refstat - (optional) Reference station per class [1 x R] for visit: normalisation (default: first station visited by the class)
options - (optional) struct with fields:: .tol - convergence tolerance (default: 1e-6) .maxiter - maximum iterations (default: 1000) .verbose - print iteration info (default: false)

OUTPUTS:

L - Mean queue lengths [M x R matrix] (sum_i L(i,r) = N(r)) W - Mean response times [M x R matrix], W = L ./ lambda Ca - Arrival scv at each queue [M x R matrix] (pseudo-open) Cd - Departure scv at each queue [M x R matrix] (pseudo-open) lambda - Class throughputs at each queue [M x R], lambda(i,r)=X(r)*v(i,r) rho - Utilizations [M x R matrix] from the closed ME solution

(mean jobs in service for IS queues)

X - Class throughputs at the reference station [1 x R] iter - Total number of fixed-point iterations

Reference:

D.D. Kouvatsos, “Entropy Maximisation and Queueing Network Models”, Annals of Operations Research, 48:63-126, 1994. Section 3.3.