← Back to Tutorials Prev: Tutorial 05 Next: Tutorial 07

Tutorial 6: Queueing Network with Caching

This example shows how to include a cache with Least Recently Used (LRU) replacement policy in a queueing network. Requests choose the item to read according to a Zipf popularity distribution, and the cache switches the resulting hit or miss into different classes (HitClass or MissClass) to keep track of the read outcome.

Caching Network Diagram 
% Example 6: A queueing network with caching
model = Network('Model');

nItems = 1000;
cacheSize = 50;
% Block 1: nodes
clientDelay = Delay(model, 'Client');
cacheNode = Cache(model, 'Cache', nItems, cacheSize, ReplacementStrategy.LRU());
cacheDelay = Delay(model, 'CacheDelay');

% Block 2: classes
clientClass = ClosedClass(model, 'ClientClass', 1, clientDelay, 0);
hitClass = ClosedClass(model, 'HitClass', 0, clientDelay, 0);
missClass = ClosedClass(model, 'MissClass', 0, clientDelay, 0);

clientDelay.setService(clientClass, Immediate());
cacheDelay.setService(hitClass, Exp.fitMean(0.2));
cacheDelay.setService(missClass, Exp.fitMean(1));

cacheNode.setRead(clientClass, Zipf(1.4,nItems));
cacheNode.setHitClass(clientClass, hitClass);
cacheNode.setMissClass(clientClass, missClass);

% Block 3: topology
P = model.initRoutingMatrix;
P{clientClass, clientClass}(clientDelay, cacheNode)=1;
P{hitClass, hitClass}(cacheNode, cacheDelay)=1;
P{missClass, missClass}(cacheNode, cacheDelay)=1;
P{hitClass, clientClass}(cacheDelay, clientDelay)=1;
P{missClass, clientClass}(cacheDelay, clientDelay)=1;
model.link(P);

% Block 4: solution
ssaAvgTable = SSA(model,'samples',2e4,'seed',23000).avgNodeTable()
from line_solver import *

model = Network('Model')

nItems = 1000
cacheSize = 50
# Block 1: nodes
clientDelay = Delay(model, 'Client')
cacheNode = Cache(model, 'Cache', nItems, cacheSize, ReplacementStrategy.LRU)
cacheDelay = Delay(model, 'CacheDelay')

# Block 2: classes
clientClass = ClosedClass(model, 'ClientClass', 1, clientDelay, 0)
hitClass = ClosedClass(model, 'HitClass', 0, clientDelay, 0)
missClass = ClosedClass(model, 'MissClass', 0, clientDelay, 0)

clientDelay.set_service(clientClass, Immediate())
cacheDelay.set_service(hitClass, Exp.fit_mean(0.2))
cacheDelay.set_service(missClass, Exp.fit_mean(1.0))

cacheNode.set_read(clientClass, Zipf(1.4, nItems))
cacheNode.set_hit_class(clientClass, hitClass)
cacheNode.set_miss_class(clientClass, missClass)

# Block 3: topology
P = model.init_routing_matrix()
P.set(clientClass, clientClass, clientDelay, cacheNode, 1.0)
P.set(hitClass, hitClass, cacheNode, cacheDelay, 1.0)
P.set(missClass, missClass, cacheNode, cacheDelay, 1.0)
P.set(hitClass, clientClass, cacheDelay, clientDelay, 1.0)
P.set(missClass, clientClass, cacheDelay, clientDelay, 1.0)
model.link(P)

# Block 4: solution
ssaAvgTable = SSA(model, samples=20000, seed=23000).avg_table()
import jline.lang.ClosedClass;
import jline.lang.RoutingMatrix;
import jline.lang.constant.ReplacementStrategy;
import jline.lang.nodes.Cache;
import jline.lang.nodes.Delay;
import jline.lang.processes.Immediate;
import jline.lang.processes.Zipf;
import jline.solvers.ssa.SSA;

Network model = new Network("QNC");
Delay clientDelay = new Delay(model, "Client");
Cache cacheNode = new Cache(model, "Cache", 1000, 50, ReplacementStrategy.LRU);
Delay cacheDelay = new Delay(model, "CacheDelay");

ClosedClass clientClass = new ClosedClass(model, "ClientClass", 1, clientDelay, 0);
ClosedClass hitClass = new ClosedClass(model, "HitClass", 0, clientDelay, 0);
ClosedClass missClass = new ClosedClass(model, "MissClass", 0, clientDelay, 0);
clientDelay.setService(clientClass, new Immediate());
cacheDelay.setService(hitClass, Exp.fitMean(0.2));
cacheDelay.setService(missClass, Exp.fitMean(1.0));
cacheNode.setRead(clientClass, new Zipf(1.4, 1000));
cacheNode.setHitClass(clientClass, hitClass);
cacheNode.setMissClass(clientClass, missClass);

RoutingMatrix P = model.initRoutingMatrix();
P.set(clientClass, clientClass, clientDelay, cacheNode, 1.0);
P.set(hitClass, hitClass, cacheNode, cacheDelay, 1.0);
P.set(missClass, missClass, cacheNode, cacheDelay, 1.0);
P.set(hitClass, clientClass, cacheDelay, clientDelay, 1.0);
P.set(missClass, clientClass, cacheDelay, clientDelay, 1.0);
model.link(P);

new SSA(model, "samples", 20000, "seed", 1, "verbose", true)
        .avgTable().print();
#include "line/solvers/ssa/ssa_dispatch.h"

Network model("QNC");
Delay clientDelay(model, "Client");
qn::CacheParam<double> par;
par.nitems = 1000;
par.itemcap.assign(1, 50);
par.replacestrat = ReplacementStrategy::LRU;
std::vector<double> popularity(par.nitems);
double popularityNorm = 0.0;
for (std::size_t i = 0; i < par.nitems; ++i) {
    popularity[i] = 1.0 / std::pow(double(i + 1), 1.4);
    popularityNorm += popularity[i];
}
for (double& p : popularity) p /= popularityNorm;
par.pread = std::vector<std::vector<double>>{popularity, {}, {}};
par.hitclass = std::vector<std::size_t>{2, 0, 0};
par.missclass = std::vector<std::size_t>{3, 0, 0};
const std::size_t cacheNode = model.add_cache("Cache", par);
Delay cacheDelay(model, "CacheDelay");

ClosedClass clientClass(model, "ClientClass", 1, clientDelay, 0);
ClosedClass hitClass(model, "HitClass", 0, clientDelay, 0);
ClosedClass missClass(model, "MissClass", 0, clientDelay, 0);
clientDelay.set_service(clientClass, Immediate());
cacheDelay.set_service(hitClass, Exp(0.2));
cacheDelay.set_service(missClass, Exp(1.0));

Routing P;
P.set(clientClass, clientClass, clientDelay, cacheNode, 1.0);
P.set(hitClass, hitClass, cacheNode, cacheDelay, 1.0);
P.set(missClass, missClass, cacheNode, cacheDelay, 1.0);
P.set(hitClass, clientClass, cacheDelay, clientDelay, 1.0);
P.set(missClass, clientClass, cacheDelay, clientDelay, 1.0);
model.link(P);

ssa::SsaOptions opt;
opt.samples = 20000;
opt.seed = 1;
const ssa::SsaSolution res = ssa::solver_ssa(model.get_struct(), opt);
← Back to Tutorials Prev: Tutorial 05 Next: Tutorial 07