[Solved]: Little's law and average time on a system with a switch

Problem Detail: 

We have a switch with $2$ lines of input and $2$ output. Each line is $10 Mbps$. The size of packets is fixed and is $1KB$. The $1^{st}$ line of input is active (transferring packets) $40\%$ of the time, while the $2{nd}$ line is active $70\%$ of the time. $\frac{1}{4}$ of packets of input $1$ (with arrival) directed to buffer of output line $1$, while the $\frac{3}{4}$ directed to buffer of output line $2$. Respectively $\frac{1}{2}$ of packets of input $2$ go to buffer 1 and $\frac{1}{2}$ to buffer $2$. Buffers $1$ and $2$ are monitored and we know that tha average number of packets in buffer $1$ is $3$ packets and in buffer $2$ is $4.5$ packets.There is also an external measurement system that measures the total time of packet input $1$ to the switch.Based on these measurements calculated the average time of packets of input $1$ in the system for those that are directed to output $1$ is $5mse$c and to output $2$ is $7msec$ . Find the average residence time of packets of input line $2$ that are directed to buffer $1$ and the average time in the system (for the same packets)

note: the residence time of one packet on switch, is the time spent on buffer plus the transmission time from the output line

Consider these cases: 1) consider packets sit in the buffer until they are done being transmitted 2) assume the transmitter works on one packet at a time and removes the packet from the buffer while it is working on it

Asked By : Adasel Pomik

Answered By : Wandering Logic

My best guess is that the intention of the problem is that packets sit in the buffer until they are done being transmitted. So when the problem says that $N_1 = 3$ this includes the packet being transmitted in addition to those waiting in the buffer.

Two applications of Little's Law should get you the answer without needing to figure out any details about the transmitter.

Spoiler! (Mouse over the region below to see my answer.)

The throughput on input line 1 is $.4 \times \frac{10\mathrm{Mb}}{s}\times \frac{1\mathrm{packet}}{\mathrm{KB}}\times\frac{1\mathrm{B}}{8\mathrm{b}} = .5\mathrm{Kpackets}/\mathrm{s}$. $\frac{1}{4}$th of that is directed to buffer 1, so $.125\mathrm{Kpackets/s}$. The throughput on input line 2 is $.875\mathrm{Kpacket}/\mathrm{s}$. Half of that is directed to buffer 1, so $.4375\mathrm{Kpacket/s}$. The problem says that $R_{11}$, the measured average time of a packet from input 1 to output 1 is 5ms. The throughput of those packets is 125p/sec, so by Little's Law the number of packets from input 1 inside buffer 1 averages 0.625. So 3-0.625=2.375 packets in buffer 1 must come from input 2. The throughput of input 2 packets in buffer 1 is 437.5p/s. By Little's Law the response time for input 2 packets in buffer 1 is 5.43ms.

If it really is supposed to be the case that packets leave the buffer while they are being transmitted, then you can apply Little's Law at any level of the hierarchy. You can apply it to the entire switch, to one of the outputs (the buffer + the transmitter), to just one of the buffers, or to one of the transmitters. When applied to the transmitter you would use the variety of Little's Law that is sometimes called the "utilization law" [Lazowska, Zahorjan, Graham and Sevcik; Quantitative System Performance, 1984].

Output 1 is providing $562.5\mathrm{packets/s}$, which is a utilization of $0.45$. So by the utilization law $0.45 = 562.5\mathrm{packets/s}\times S_{\mathrm{transmit}}$, so $S_{\mathrm{transmit}} = 0.8\mathrm{ms}$. Thus the time in the buffer for packets from input 1 is $4.2\mathrm{ms}$ rather than $5\mathrm{ms}$ and the rest of the calculation proceeds similarly to above. (Apply Little's Law twice.)

Another way to look at it, which provides the same answer, is that the utilization of the transmitter is the average number of packets in the transmitter. So the average number of packets in the output 1 buffer and transmitter combined is $3+0.45=3.45$. Then you apply Little's Law twice and you can confirm that you get exactly the same result as you get when assuming that each packet from input 1 takes $4.2\mathrm{ms}$ in the buffer and $0.8\mathrm{ms}$ in the transmitter.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13705