University of California, San Diego
Department of Computer Science and Engineering

CSE 123A -- Computer Networks -- Winter 1996

1.

A graduate student wrote and subsequently ran a simulation program of a complex multiprocessor system. The simulation program produced the following results: (i) the average number of jobs in the system was equal to 12.3, (ii) the average arrival rate was equal to 15.6 jobs per second, and (iii) the average delay for a job was equal to 2.3 seconds. The student presents the results to the advisor who is skeptical; why? If you were the advisor, what question would you ask the student in order to confirm your suspicion of an error?

The advisor is skeptical due to Little's Law: , for any queuing system with a mean arrival rate of customers per unit time in equilibrium, where N is the mean number of customers in the system at any given time and T is the mean delay for any customer. A simple multiplication shows that this equation does not hold for the above numbers. This result is much more general than the M/M/1 systems that we have examined; it does not assume any specific distributions of either interarrival or service times. However, it assumes that the system is in equilibrium, or in steady-state. This would mean that the system has stabilized at some average rates that will not change over time; if the system is at a steady-state, our measurements will make the equality above hold. Thus, the only possible explanation for these measurements is that the system is not yet in steady state; else, the measurements are erroneous. A question that would determine which of these two cases holds, would be: Were these measurements taken while the system was in equilibrium? A positive answer indicates an error in the measurements, while a negative answer means that the measurements are useless; they cannot be used to predict the future behavior of the system. Note that a system may never reach equilibrium; a queue for example may grow indefinitely. In this case, average measurements have no meaning at all.

2.

Assume that in a packet radio network perfect capture allows receivers to correctly receive one of possibly many simultaneously transmitted packets. If we use a pure ALOHA protocol in such an environment, what should our target G be? Is it better to use linear, exponential, or no backoff? Why?

Since transmission of one frame per frame time is guaranteed, there is no need to backoff. It's always better to send packets as soon as possible for maximum throughput. (One problem with this is starvation. Stations farther out from the central cite may never get a chance to transmit.)

3.

If the bit string 0111101111101111111111110110111110 is subjected to bit stuffing, what is the output string?

Stuff a zero into the bit string after each five consecutive ones. Then the output string is
01111011111001111101111101101101111100.

4.

What is the CRC for the message 1110100001 when the generator polynomial is ?

Given , and the degree of r=5, we append r zero bits to the low order of the frame , which results in . Then the checksummed frame is obtained by

The output frame to be transmitted, is 111010000110010. Note that the subtraction using modulo 2 is the same as addition.

5.

Traffic for a certain destination arriving at a network node has two possible choices for an output line. The routing scheme is as follows: when a packet arrives, it goes onto the first choice queue if and only if that queue is empty and its output line is idle; otherwise it uses the second choice queue. Assume there is no other traffic passing through this node. The packet arrival process is assumed to be Poisson with rate (packets/sec) and the service times of packets through the first choice queue for this traffic stream are assumed to be exponentially distributed with parameter (packets/sec).

(a)

Come up with a model of the system that will allow you to determine what fraction of the packets get routed via the first choice queue. Describe (define) the states and state transitions in your model.

To begin, note that even though we could come up with a model that describes all possible states in the system, we are concerned only with events relating to the first choice queue. Looking at the description we can see that essentially the first choice queue behaves as if it has no space for queueing packets; it can only hold the packet that is transmitted at any time. The only events that change the state of this queue are packet arrivals when is empty, which make full, so all new arrivals will use the second choice queue , and packet departures from , which make it again ready to send one packet. It is important to note that we do not care what happens at ; it may grow without bound for all we know. It is enough to model the behavior of for our problem, so our state model will show only states (empty) and (full, a packet is being transmitted). This model is shown in Figure .

  
Figure 1: State model for Exercise 5

The events that relate to are arrivals when the queue is either empty or full, and departures from when it is full (note that we do not care about departures from at all; also, when is empty there can be no departures from it). The transition rates (shown near the arrows denoting the transitions) can be calculated by using the arrival rate for , which is just , the total arrival rate, since all new packets consider first, and the service rate for . Denoting the probability that the system is in as and in as , the transition rates are as shown in the figure: if a packet arrives when we are at ( empty), we move to ( full); when is full, if packets arrive we remain at , while if a packet leaves (the rate for this is ), we move back to . The transition rates are computed by multiplying the rates at which these events happen by the probability that the system is in a given state.

(b)

What fraction of the packets get routed via the first choice queue (in steady state)?

What we want is : the probability that the system is at at any given time, or, equivalently, that a packet arriving to the system will find empty and use it. Another way to see this is that the number of packets per unit of time making the transition from to (i.e., using the first queue) is , while the total number of packets per unit of time is and thus the ratio is .

The equations describing this system are:

The first is a balance equation for the system and the second one arises from the fact that the system must be in one of these two states. Note that we can assume that is in equilibrium since a queue cannot build up; all the overflowing packets are directed to , for which we do not care. Also, the loop on (a packet arrives when is full), shows up in both sides of the first equation, since it gets out of and back into . Solving the first one for and substituting into the second, we have that

which is what we are looking for.

 
Figure 2: Function plot for Exercise 5

(c)

Are there any constraints on the parameters of the first choice queue to be in steady state? If so what are they? If not, why not? Also, plot the fraction of the packets that get routed via the first choice queue as a function of the ratio .

We already saw that since the first choice queue does not build up, it is always in steady state, regardless of arrival and service rates. Thus, the usual constraint for M/M/1 models that does not need to hold here. The reason is that the traffic that cannot handle goes automatically to . In Section A.2 in the text, we had to assume that was less than one to guarantee that the mean number of customers in the system would not grow without bounds; here this problem cannot arise by definition. To plot the desired function, we just have to formulate the that we found before as a function of ; this is just the first form that we saw above

An approximation is shown in Figure 2, for values of from 0 to 2. Remember that can be larger than one in this problem.

6.

Consider a path in a store-and-forward network. The path goes through 10 nodes. At each node the packets are stored in a buffer before they are transmitted over the link to the next node. The packets contain 1000 bits and the transmission rates are equal to 10Mb/s. The total propagation time over the links along the path is 10ms. Assume that a packet is sent along that path and that it finds an average of 5 packets when it arrives at each buffer.

1. How long does it take for the packet to go through the path if the nodes transmit from each buffer on a First-Come-First-Served (FCFS) basis?

   Let k be the number of nodes along the path, C be the transmission rate, p be the packet size in bits, d be the propagation delay along the path.

   If each node transmits on a FCFS basis, then an incoming packet has to wait for an average of packet transmission times. Thus, the total for the packet to go through the path is

   

2. How long is the packet travel time if it is transmitted as expedited data?

   Since an expedited packet will skip to the head of the queue, the packet has to wait for an average of packet transmission time. Thus

   

7.

Consider the following (see Figure 3) open network of M/M/1 queues in equilibrium, find:

 
Figure 3: Queueing system for Exercise 7

(a)

The throughput for each queue, , . We can say that the throughput is the effective output rate of a queueing system. This is different from the service rate, which can be much larger than the throughput for systems that do not have many customers. The assumption that the system is in equilibrium, implies that each queue is in equilibrium, thus the throughput for each queue is equal to the arrival rate for that queue. Examining the figure we can see that the throughputs are given by the following system of equations:

The input rate for queue 1 is calculated by adding up all the smaller inputs: the output of queue 2 and the input to the system. Note that we must take the probabilities of a packet taking a specific route into account, by factoring them into the equations. By substituting the second equation in the first, we have:

For the last step to be permissible, the inequality must hold.

(b)

The necessary and sufficient condition for the system to be in equilibrium; give a geometric interpretation of it; in order to make things more specific for the purposes of illustration, assume , , and .

As we said before, the system is in equilibrium when all queues are in equilibrium. This means that the service rate for each queue must be strictly greater than its throughput, which we fund in part (a) above. The conditions for equilibrium are then:

Solving these inequalities for and and substituting the values , and , we have

The necessary and sufficient condition for the system to be in equilibrium is shown as a shaded area in Figure 4.

  
Figure 4: Condition for the system to be in equilibrium (Exercise 7)

Assuming , , and ,find:

(c)

The average number of customers waiting or being served for each queue, , . To find these, we can use Little's Law (remember that each queue is in equilibrium by implication). The effective arrival rate for each queue is just and , computed above, and the average time on each queueing system is given by the general formula . Substituting our values, we have:

Substituting the values , and , we have and .

(d)

The mean delay through the system, T. This is not the sum of the delays in each queue, because a packet may go through the queues for an unknown number of times. However, we can use Little's Law to find the total delay, by considering the whole system as one box. The input to the box from the outside world is and and the average number of customers is the sum of the customers in both queues; at any given time, the customers in the system are at either of the two queues. Substituting the values for and and that we found above, we have:

• About this document ...