\section{Virtual Clock}

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

   \begin{sitem}
      \item Different approach
      \begin{sitem}
         \item uses reservations rather than feedback
         \item rate-based rather than window-based
         \item router-centric rather than host-centric
      \end{sitem}

      \item Idea
      \begin{sitem}
         \item modeled after time-division multiplexing (TDM)
         \item statistical multiplexing to accommodate bursty traffic
         \item uses logical (rather than real) time
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Defining Rate}

   \begin{sitem}
      \item Explicit flow setup phase
      \begin{sitem}
         \item source indicates its needs
         \item network grants or denies request
      \end{sitem}
      \item Resource needs
      \begin{sitem}
         \item average rate ({\tt AR}) 
         \item average interval ({\tt AI})
         \item example: {\tt AR} = 10 packets per second and {\tt AI} = 100ms
         \item range: {\tt 1/AR $\le$ AI} $\le$ total flow duration
         \item datagram traffic gets it's own flow; granted some capacity
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Virtual Clock as a Queuing Discipline}

   \begin{sitem}
      \item Similar to weighted fair queuing
      \item Router variables
      \begin{sitem}
         \item {\tt VClock}$_i$ for each flow $i$
         \item clock tick ({\tt VTick}$_i$) for flow $i$
         \item {\tt VTick$_i$ = 1/AR$_i$} (assumes all packets on flow
               $i$ are the same size)
         \item example: flow $i$ has {\tt AR} = 200 packets per second, 
               then {\tt VTick}$_i$ = 5ms
      \end{sitem}
      \item Router algorithm
      \begin{sitem}
         \item first packet: {\tt VClock}$_i$ = {\tt RealTime}
         \item each packet thereafter: {\tt VClock$_i$ += VTick$_i$}
         \item timestamp each packet with {\tt VClock}$_i$
         \item packets queued and serviced in according to timestamps
         \item when buffer space is full, packet with largest timestamp is
               dropped
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Example of interleaved service proportional to {\tt AR}
      \begin{sitem}
         \item flow 1: {\tt AR} = 1000 packets per second
         \item flow 2: {\tt AR} = 500 packets per second
      \end{sitem}
      \pichere{vc1.eps,height=2in}

      \item Example of discarding a packet
      \pichere{vc2.eps,height=2in}

   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Virtual Clock as a Flow Meter}

   \begin{sitem}
      \item Note
      \begin{sitem}
         \item have not yet usee {\tt AI}
         \item possible for flow to ``save up'' credits and use for burst
      \end{sitem}
      \item Additional mechanism
      \begin{sitem}
         \item when setup flow $i$, compute {\tt AIR$_i$ = AR$_i$ $\times$ 
               AI$_i$}
         \item upon receiving {\tt AIR}$_i$ bytes on flow $i$...
         \begin{sitem}
            \item if {\tt VClock}$_i$ - {\tt RealTime} $>$ {\tt Threshold},
                  then send advisory to source
            \item if {\tt VClock}$_i$ $<$ {\tt RealTime}, then reset
                  {\tt VClock}$_i$ to {\tt RealTime}
         \end{sitem}
         \item source not allowed to accumulate ``unused time'' during one 
               {\tt AI} period and use it in another
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item Last detail
      \begin{sitem}
         \item source can still accumulate credit {\it within} an {\tt AI}
         \item problem: using one variable ({\tt VClock}) to control both
               queuing order and flow monitoring
         \item solution: introduce auxiliary copy of {\tt VClock}
         \item upon receiving each packet...
      \end{sitem}
\begin{tt}
AuxVClock$_i$ = MAX(RealTime, AuxVClock$_i$)\\
VClock$_i$ = VClock$_i$ + VTick$_i$\\
AuxVClock$_i$ = AuxVClock$_i$ + VTick$_i$\\
Stamp packet with current value of AuxVClock$_i$
\end{tt}
      \item Thus
      \begin{sitem}
         \item {\tt VClock}$_i$ resynchronized with real time once for 
               every {\tt AIR}$_i$ bytes of data on flow $i$
         \item {\tt AuxVClock}$_i$ resynchronized with real time once for
               every packet on flow $i$
      \end{sitem}
   \end{sitem}
\end{slide}
