% Created 2021-07-12 Mon 16:58
% Intended LaTeX compiler: pdflatex
\documentclass[presentation]{beamer}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{minted}
\usepackage{pdfpages}
\usepackage{xcolor}
\usepackage{graphicx}
\usepackage{xspace}
\usepackage{libertine}
\usepackage{fontawesome}
\mode<beamer>{\usetheme{Boadilla}}
\setbeamertemplate{navigation symbols}{}
\hypersetup{colorlinks}
\setbeamerfont{alerted text}{series=\bfseries}
\usepackage{algorithmicx}
\usepackage{graphicx}
\usetheme{default}
\author{Brett Viren}
\date{\today}
\title{Heart beats and time outs}
\subtitle{How long to wait for new input}
\hypersetup{
 pdfauthor={Brett Viren},
 pdftitle={Heart beats and time outs},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 27.2 (Org mode 9.4.4)}, 
 pdflang={English}}
\begin{document}

\maketitle

\begin{frame}[label={sec:org12818e6}]{Window algorithm}
Group elements from an \alert{ordered stream} into an ordered stream of \emph{windows of time}.

\begin{itemize}
\item Object \(i\) has a \emph{data time} \(T_i\), arrives at \emph{real} (aka \emph{system)} \emph{time} \(t_i\)
\begin{itemize}
\item Objects are \alert{strictly ordered} by their \(T_i\) to form a \emph{stream}.
\item For simplicity take \emph{data} and \emph{system} clock \alert{rate} as identical, but\ldots{}
\item In general \(T_i \ne t_i\) due to production/transmission latency and jitter.
\end{itemize}

\item Window \(j\) spans holds \(T_i \in [T_j, T_j + \Delta T)\), half inclusive interval.

\begin{itemize}
\item May require \emph{synchronous window edges}: \(\mod(T_j, \Delta T) = 0\)
\end{itemize}

\item New \(T_i\) arrives:
\begin{itemize}
\item if before current window: drop \(T_i\) (tardy)
\item if in current window: add \(T_i\)
\item if after window, output the window, start new window at \(T_j + \Delta T\)
\end{itemize}
\end{itemize}

What to do while no new \(T_i\)?
\begin{itemize}
\item Wait until one arrives \(\to\) unbounded latency
\item Time out and output the window, start new window at \(T_j + \Delta T\)
\begin{itemize}
\item \(\to\) potential future tardy
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[label={sec:orge8dea00}]{Latency vs Loss minimax problem}
Reduce latency bound \(\to\) more likely next message deemed tardy.

\begin{itemize}
\item Pick window \(\Delta T = 3\) (in some time unit).
\item Assume \alert{mean} \emph{data} time period between messages is 1 unit of time.
\begin{itemize}
\item Pick latency bound: wait no more than 2 units of time with no message.
\end{itemize}
\item At \(t_i = 5\) after a gap of 2 units we get either \(T=3\) or \(T=4\)
\end{itemize}

\begin{center}
\(\leftarrow\) time

\begin{center}
\begin{tabular}{lrlllll}
\(t_i\): & 6 & 5 & 4 & 3 & 2 & 1\\
\hline
 &  & PL(\(T=3\)) & none & none & PL(\(T=2\)) & PL(\(T=1\))\\
\hline
 &  & PL(\(T=4\)) & none & none & PL(\(T=2\)) & PL(\(T=1\))\\
\end{tabular}
\end{center}
\end{center}

PL = payload message type
\end{frame}

\begin{frame}[label={sec:orge399b85}]{Latency vs Loss cont}
\begin{center}


\begin{center}
\begin{tabular}{lrlllll}
\(t_i\): & 6 & 5 & 4 & 3 & 2 & 1\\
\hline
 &  & PL,\(T=3\) & none & none & PL,\(T=2\) & PL,\(T=1\)\\
\hline
 &  & PL,\(T=4\) & none & none & PL,\(T=2\) & PL,\(T=1\)\\
\end{tabular}
\end{center}
\end{center}

\begin{itemize}
\item At \(t = 2\) we get \(T=2\),  our window is not complete and we start waiting for next.

\item At \(t = 3\) we have reached max latency time with no input and output
window with \(\{T=2, T=1\}\).

\item Scenario 1: \(T=3\) comes at \(t=5\).  It should have gone into window
but window is output.  \(T=3\) is dropped as \alert{tardy}.

\item Scenario 2: \(T=4\) comes at \(t=5\).  It should NOT have gone into
window and we had to wait full latency to learn that.
\end{itemize}
\end{frame}


\begin{frame}[label={sec:org74ddaba}]{Latency vs Loss + Heartbeats}
Heartbeat (HB) messages vs normal payload (PL) messages:
\begin{itemize}
\item sent \alert{in band}, HB and PL ordered together by \emph{data time} \(T\)
\item HB sent with fixed \emph{data time} period faster than mean of PL
\item still subject to latency variances
\item optional: do not send HB if PL with identical \(T\)
\end{itemize}

\begin{center}
\begin{center}
\begin{tabular}{lrlllll}
\(t_i\): & 6 & 5 & 4 & 3 & 2 & 1\\
\hline
 &  & \(T=3\) & none & none & \(T=2\) & \(T=1\)\\
\hline
 &  & \(T=4\) & none & none & \(T=2\) & \(T=1\)\\
\end{tabular}
\end{center}
\end{center}
\end{frame}
\end{document}
