\documentclass{article}
\input{../6829-preamble}
\usepackage{url}

\begin{document}
\psetnum{1}
\date{2005/09/22}
\collab{Collaborators: $\set{\mathtt{amdragon}}$}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      The TDM scheme is not work-conserving: if one session is
      transmitting and the others are idle, the link will be idle
      during the time slots for the other connections even though
      packets are queued in the active session's queue.

      The statistical multiplexing scheme is work-conserving: the link
      is only idle when there are no packets in the single queue,
      which means no frames are waiting for service.
    \end{subproblem}

    \begin{subproblem}
      Consider first the statistical multiplexing case. Since packet
      arrivals are a Poisson process with parameter $N \lambda$ and
      service times are exponentially distributed with parameter
      $\mu$, and there is a single server, we have a \textsf{M/M/1}
      queuing process. Since $mu > N \lambda$, the system converges
      to a steady state, and a basic result from queuing theory tells
      us that the expected time in the system for each packet,
      including the time spent transmitting it over the link, is
      $\frac{1}{\mu - \lambda N}$.
    
      In statistical multiplexing, since the size of a slot is much
      smaller than the packet transmit time, we can treat the system as
      $N$ separate links, each of which transmits at an average rate of
      $\nicefrac \mu n$ frames/second. Each link has a separate queue,
v      where packet arrivals are a Poisson process with parameter
      $\lambda$. This is also a \textsf{M/M/1} queuing system, and so
      the average delay for a frame is $\frac{1}{\nicefrac{\mu}{N} -
        \lambda} = \frac{N}{\mu - \lambda}$.
      
      This tells us that the average delay for a frame in TDM is $N$
      times greater than the average delay for a frame in statistical
      multiplexing because the queues are being processed at a rate
      that is slower by a factor of $N$. As we'd expect, the delay
      increases as the packet arrival rate $\lambda N$ approaches the
      average service rate $\mu$ (and queue lengths fail to converge
      if it exceeds this rate).
    \end{subproblem}

    \begin{subproblem}
      In statistical multiplexing, the output link is always fully
      utilized because the aggregate input rate is the same as the
      output link capacity $\mu$, and the multiplexing scheme is
      work-conserving.

      In the TDM scheme, the link is only utilized during the
      time slots corresponding to the $A$ active sessions, and it is
      fully utilized during this time, since the aggregate input rate
      $\mu$ is greater than the effective output rate $\mu
      \frac{A}{N}$. So the link is utilized $\frac{A}{N}$ of the time.

      \vspace{2in}
    \end{subproblem}

    \begin{subproblem}
      TDM has less jitter because it maintains an individual queue for
      each session.  Regardless of utilization, each queue is always
      guaranteed to receive $\frac{1}{N}$ of the output link. Queue
      lengths for these individual queues are smaller, as is their
      variance, compared to having a single queue containing every
      packet.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    \begin{subproblem}
      All ACKs will be sent by the interval timer if the interval
      $\delta$ is shorter than the time required for the next packet
      to arrive. This time is $\nicefrac{s}{r}$. So normal delayed
      ACKs will never be sent if
      \[ \delta < \frac{s}{r} \]
    \end{subproblem}

    \begin{subproblem}
      The interval timer will trigger an ACK for every packet if
      \begin{align*}
        50 \text{ ms} &< \frac{512\text{ bytes}}{r} \\
        r &< \frac{512\text{ bytes}}{50 \text{ ms}} = 10
        \nicefrac{\text{ Kbyte}}{\text{s}}\\
      \end{align*}
      This is not likely to be a problem on today's Internet
      connections, except for slow connections such as dialup.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    The recipient should discard the packet and treat it as a dropped
    packet. Sending a duplicate ACK would indicate to the original
    sender that an out-of-order packet had been received,  causing it
    to (erroneously) assume that one of the other packets in its
    window has been received. It will then adjust its window size and
    transmit a new packet erroneously, which is incorrect.

    If the recipient ignores the packet completely, the next packet
    received will be out of order and trigger a duplicate ACK with the
    appropriate sequence number. This will cause the sender to
    retransmit the corrupted packet.

    It's also possible that the checksum error indicates that part of
    the packet header was corrupted. If this means that the source or
    destination host, port, or sequence number is incorrect, then
    sending a duplicate ACK is even more incorrect.
  \end{problem}

  \begin{problem}
    Submitted by email, or available from
    \url{http://www.ambulatoryclam.net/svn/classes/6.829/ps1/rmtp/}. 
  \end{problem}
\end{pset}
\end{document}