Problem H$2\mathrm{.}2[15$ points$]$ Consider a packet processing facility that consists of two packet header processors

in series. The first performs a CRC computation on the packet header, while the second does an address lookup

on the destination address carried in the packet header.

A new packet arrives in each clock cycle with probability $p,$ and is queued if either of the two processors is

already busy processing a packet. In other words the "server" consisting of the two processors can only handle

one packet at the time. When both processors become idle, the first packet waiting at the head of the packet queue

$($note that this could be an arriving packet if the system was empty$)$ is sent first to the CRC processor, and next to

the address lookup processor, but only if the CRC is correct. If the CRC is incorrect, the packet is immediately

dropped, and the system moves on to processing the next packet, if any.

From observation, we know that the CRCs of incoming packets are correct with probability $q,$ independently

of each other. CRC computations take only one clock cycle, and the number of clock cycles $($memory access$)$

that an address lookup takes is geometrically distributed with an average of $L$ clock cycles.

$[4$ pts$]$ What is the distribution of a packet total processing time, i$.$e$.,$ the probability that the processing of

a packet takes altogehter $k1$ clock cycles? What is then the average packet processing time $E[S]?$

$[4$ pts$]$ Give a condition, function of $p,q,$ and $L$ for the system to be stable.

$[4$ pts$]$ Derive expressions, function of $p,q,$ and $L$ for the expected number of packets in the CRC processor

and in the address lookup processor, respectively. In other words, what is the fraction of the time that either

processor is busy processing a packet. $[3$ pts$]$ Formulate a Markov chain model that captures the system behavior. Identify explicitly what you

define as the system state as well as the transition probabilities between all states.

Hint: The state cannot be just the number of packets in the system since you also need to remember

whether a packet is in the CRC or in the address lookup processor. But this can be readily handled by

keeping track of both the number of packets in the queue, and which processor is currently handling the

packet in service.