\section{Queuing Disciplines}

% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item First-In-First-Out (FIFO)
      \begin{sitem}
         \item does not discriminate between traffic sources
      \end{sitem}

      \item Fair Queuing (FQ)
      \begin{sitem}
         \item explicitly segregates traffic based on flows
         \item ensures no flow captures more than its share of capacity
         \item variation: weighted fair queuing (WFQ)
      \end{sitem}

      \pichere{fq.eps,height=2.5in}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Problem: packets not all the same length
      \begin{sitem}
         \item really want bit-by-bit round robin
         \item not feasible to interleave bits (schedule on packet basis)
         \item simulate by determining when packet would finish
      \end{sitem}

      \bigskip
      \item For a single flow
      \begin{sitem}
         \item suppose clock ticks each time a bit is transmitted
         \item let $P_i$ denote the length of packet $i$ 
         \item let $S_i$ denote the time when start to transmit packet $i$
         \item let $F_i$ denote the time when finish transmitting packet $i$
         \item $F_i = S_i + P_i$
         \item When does router start transmitting packet $i$?
         \begin{sitem}
            \item If before router finished packet $i-1$ from this flow, 
                  then immediately after last bit of $i-1$ ($F_{i-1}$)
            \item If no current packets for this flow, then start transmitting
                  when arrives (call this $A_i$)
         \end{sitem}
         \item Thus: $F_i = MAX(F_{i-1}, A_i) + P_i$
      \end{sitem}

      \bigskip
      \item For multiple flows
      \begin{sitem}
         \item calculate $F_i$ for each packet that arrives on each flow
         \item treat all $F_i$'s as timestamps
         \item next packet to transmit is one with lowest timestamp
      \end{sitem}

      \bigskip
      \item Not perfect: can't preempt the packet currently being transmitted

      \bigskip
      \item Example

      \pichere{fair_queuing.eps,height=4in}
   \end{sitem}
\end{slide}
