`Name:`

Queuing network modelling (QNM) `Domain:`

Algorithm`Functionality:`

Queuing network modelling (QNM) was developed to employ a small subset of queuing theory techniques for efficiently modelling two important queuing network systems, computer and communication (C&C) systems `Input:`

(1) Number of service stations $M = {M_{1}, M_{2}, \dots , M_{q}}$
(2) Number of servers $F_{k} = {F_{1}, F_{2}, \dots , F_{l_{k}}}$ be a set of servers for a service station $M_{k}$
(3) Class of customers Let n denote the number of customer classes in the model and $C_{i}$ denote a class of customers, the model will have a union of all classes of customers denoted as $c= \bigcup_{j=1}^{n} c_{j}$
(4) Workload intensity $\lambda = {\lambda_{1}, \lambda_{2}, \dots , \lambda_{n}}$, where $\lambda_{1}, \lambda_{2}, \dots , \lambda_{n}$ are the arrival rate of $C_{1}, C_{2}, \dots ,C_{n}$, respectively
(5) Number of visits, service time and service demands $D_{c,k}=V_{c,k} \cdot S_{c,k}$
The number of visits $V_{c,k}$ that a customer from class Cc makes to station $M_{k}$ is defined as the ratio of the number of service completions at that station to the number of service completions of the system
The service time $S_{c,k}$ is defined as the average time of service required at each visit to a station $M_{k}$ by a customer class $C_{c}$
`Output:`

(1) Utilization of a service station The utilization of a service station is interpreted as the proportion of time when station is busy, or, equivalently, as the average number of customers in service there For any station Mk and customer class $C_{c}$, the utilisation is denoted as $U_{c,k}$, where $U_{c,k}=\lambda_{c} \cdot D_{c,k}$
The aggregate utilization of a station $M_{k}$ is given by:$U_{k}=\sum_{c=1}^{n} U_{c,k}$
(2) Residence time and system response time The residence time refers to the time a customer waits in a queue and receives service, while the system response time is the time interval between the instant of a customer entry to a system and the instant of the service completion by the system
For a service station with single server, the residence time for class $C_{c}$ and station $M_{k}$ is denoted as $R_{c,k}$ and given by:$R_{c,k}=\frac{D_{c,k}}{1-U_{k}}$
For the service station with multiple servers, the residence time for class $C_{c}$ and station $M_{k}$ for the open queuing networks is given by:$R_{c,k}=D_{c,k}(1+\frac{C(U_{k},l_{k})}{U_{k}-l_{k}})$ where $C(U_{k},l_{k})$ is the Erlang C function
The system response time for a class $C_{c}$ customer, $R_{c}$, is the sum of its residence time at all stations:$R_{c}=\sum{k=1}^{q} R_{c,k}$
(3) Throughput Throughput for the customers in a class $C_{c}$ in a queuing network system is the rate at which the customers are served by the system. The system throughput can be expressed as follows:$X_{c}=\lambda_{c}$
The throughput of a customer in class $C_{c}$ at a station $M_{k}$ is obtained from $X_{c}$ as $X_{c,k}=V_{c,k} \cdot X_{c}$
(4) Queue length The queue length for the customers of a class $C_{c}$ at service station $M_{k}$ is the average number of customers at station $M_{k}$ waiting in queue and receiving service. We denote it as $Q_{c,k}$. By Little’s law, we have the queue length for open QNM as:$Q_{c,k}=\lambda_{c} \cdot R_{c,k}$
The queue length for the customers of a class $C_{c}$ in the system is given by:$Q_{c}=\lambda_{c} \cdot R_{c} \sum{k=1}^{q} Q_{c,k}$
Testing an Open Source Suite for Open Queuing Network Modelling using Metamorphic Testing Technique 10.1109/ICECCS.2009.28

`Description:`

`Property:`

$$If (\lambda_{c}<\lambda’_{c}) then (X_{c,k} \leq X’_{c,k}) \wedge (Q_{c,k}\leq Q’_{c,k}) \wedge (R_{c,k}\leq R’_{c,k}) \wedge (U_{c,k}<U’_{c,k}) \wedge (X_{c}<X’_{c}) \wedge (R_{c}\leq R’_{c}) \wedge (Q_{c}\leq Q’_{c})$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

$$If (S_{c,k}<S’_{c,k}) then (X_{c,k} = X’_{c,k}) \wedge (Q_{c,k}< Q’_{c,k}) \wedge (R_{c,k}< R’_{c,k}) \wedge (U_{c,k} \leq U’_{c,k}) \wedge (X_{c}=X’_{c}) \wedge (R_{c}<R’_{c}) \wedge (Q_{c}< Q’_{c})$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

$$If (q<q’) then (X_{c,k} \geq X’_{c,k}) \wedge (Q_{c,k}\geq Q’_{c,k}) \wedge (R_{c,k}\geq R’_{c,k}) \wedge (U_{c,k} \geq U’_{c,k}) \wedge (X_{c}=X’_{c}) \wedge (R_{c}\geq R’_{c}) \wedge (Q_{c}> Q’_{c})$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

$$If (\lambda’_{c}=n \cdot \lambda_{c}) then \frac{Q’_{c,k}}{Q_{c,k}}=n \cdot \frac{ R’_{c,k}}{ R_{c,k}}$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

$$If (\lambda’_{c}=n \cdot \lambda_{c}) then \frac{Q’_{c}}{Q_{c}}=n \cdot \frac{ R’_{c}}{ R_{c}}$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

$$If(\lambda’_{c}<\lambda_{c}) then \exists M_{k} \in M such that R_{c,k} \neq R’{c,k}$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`

`Description:`

`Property:`

$$If ((l_{k}=l’{k})\wedge (l_{k}\neq 1)\wedge (U_{k} \neq 1)\wedge (S’{c,k}=n \cdot S_{c,k}))then \frac{R’_{c,k} \cdot (1-U’{k})}{ R_{c,k} \cdot (1-U{k})} \neq n$$ `Source input:`

`Source output:`

`Follow-up input:`

`Follow-up output:`

`Input relation:`

`Output relation:`

`Pattern:`