%=======================================================================
%  COMPUTER COMMUNICATION NETWORKS, LECTURE NOTES
%=======================================================================
\def\lectureNr{{9}}   %enter number!
\def\lecture{Peer to Peer Networking} %select and enter title
\def\scribe{Edward Kudlack}           %enter your name

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% --------------------------------------------------------------
% DON'T CHANGE ANYTHING UNTIL THE NEXT LINE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\def\solitude{1} %KEEP THIS WAY!!!


%
%\newcommand{\LectureDetails}[3]{
%\chapter{{#2}}
%% \chapter{Lecture {#1}: {#2}}
%\begin{flushright}
%{\large Notes taken by {#3}}
%\end{flushright}}
%
%\newcommand{\LectureDetailS}[6]{
%\chapter{{#2}}
%% \chapter{Lecture {#1}: {#2}}
%\begin{flushright}
%{{\large Notes taken by {#3} ({#4})} \\ {\large and {#5} ({#6})}}
%\end{flushright}}
%


\ifnum\solitude=1
  \documentclass[times, 10pt,letter]{article}
  \usepackage{times}
  \usepackage{fullpage,amsfonts,latexsym,graphics,amssymb}
  \usepackage{amsmath,amsthm,amstext,url}

  \title{Computer Communication Networks\thanks{\
         Lecture Notes for a course given by Stephen F. Bush
         at SUNY.} \\
         Lecture \lectureNr: \lecture}
  \author{Notes taken by \scribe}
  \date{November 2009}
%  \input{preamble}
\else
  %\LectureDetails{\lectureNr}{\lecture}{\scribe}
   \chapter{Lecture \lectureNr: \lecture}
   \begin{flushright}
   {\large Notes taken by \scribe}
   \end{flushright}
\fi



\ifnum\solitude=1

%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Theorems & Definitions


\newtheorem{theorem}{Theorem}


\newtheorem{claim}[theorem]{Claim}
\newtheorem{subclaim}{Claim}[theorem]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{observation}[theorem]{Observation}


\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{construction}[theorem]{Construction}
\newtheorem{example}[theorem]{Example}
\newtheorem{algorithm1}[theorem]{Algorithm}

\newenvironment{algorithm}{\begin{algorithm1}\ \\
    \vspace{-0.2cm}}{\end{algorithm1}}

%\newcommand{\qed}{\begin{flushright}
%\rule{.1in}{.1in} \end{flushright}  }


%\newenvironment{proofsk}{\nopagebreak
%\noindent{\bf Proof Sketch:}}{ \qed \par \medskip}

\newenvironment{proofsk}{\begin{proof}[Proof Sketch:]}
{\end{proof}}


\newenvironment{smallproof}{\nopagebreak \begin{quote} %
\begin{small} \noindent{\bf Proof:}}{ \qed \par %
\end{small} \end{quote} \medskip}

\newenvironment{note}{\nopagebreak \begin{quote} %
\noindent{\bf Note:}}{%
\end{quote} \medskip}

\newenvironment{notes}{\nopagebreak \begin{quote} %
\noindent{\bf Notes:} \par%
\begin{itemize}}{%
\end{itemize}\end{quote} \medskip}

\newenvironment{summary}{\begin{quote} {\bf Summary:}}{\end{quote}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% General Macros

\newcommand{\eqdef}{\stackrel{def}{=}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\inr}{\in_{\mbox{\tiny R}}}
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\st}{\mbox{ s.t. }}
\newcommand{\etal}{{\it et al }}
\newcommand{\into}{\rightarrow}

\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
%\newcommand{\vec}[1]{\overline{\mathbf{#1}}}
\newcommand{\e}{\epsilon}
\newcommand{\ee}{\varepsilon}
\newcommand{\ceil}[1]{{\lceil{#1}\rceil}}
\newcommand{\floor}[1]{{\lfloor{#1}\rfloor}}
\newcommand{\angles}[1]{\langle #1 \rangle}

\fi


%-------------------------------------------------------------
% YOU MAY ADD ADDITIONAL (PRIVATE) MACROS HERE,
% BUT DO START EACH WITH YOUR INITIALS.
% FOR EXAMPLE, IF YOUR NAMES ARE ARIK SHARON AND SHIMON
% PERES THEN START EACH MACRO WITH ASSP.
% EXAMPLE: \newcommand{\ASSPz2}{\Z_2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\ifnum\solitude=1
\begin{document}
\maketitle
\fi



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% BEGINNING OF DOCUMENT
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{summary}
This document contains the scribal version of the lecture delivered by Dr. Stephen Bush to the CSI416/516 class at the University of Albany, on November 3, 2009 containing information about Peer to Peer Networking, ARQ and Flow Control.
\end{summary}





\section{Peer to Peer}

Peer to peer communication as referred to in class is not just what happens in applications such as Bit torrent but is what happens when any two processes at the same layer in the communication stack interact. These processes are known as peer processes. Peer processes might be on adjacent nodes in the network, such as link layer processes, or may be on opposite sides of a connection, such as transport layer processes. Peer processes communicate using PDUs.

\section{ACK/NAK}

In order to provide reliable transmission, the peer processes on the receiving side can acknowledge (ACK) a correct transmission or negatively acknowledge (NAK) an incorrect transmission. There needs to be a timeout mechanism in case the ACK or NAK is not received (i.e. lost in transmission), in which case the data should be resent. ACK/NAK should be performed at each node in the link if the link is unreliable and should be performed at the ends of the link if the link is reliable. The end-to-end version is more common because of the overhead involved in the hop-by-hop version. With multicast, the only NAK should be sent to the sender to prevent a huge amount of transmission overhead.

\section{ARQ}

ARQ (Automatic Repeat Request) is a protocol for performing ACK/NAK and includes things related to this such as CRC. ARQ ensures reliable delivery of data. Transmitters send information frames (data) and receivers reply with control frames (ACK/NAK). Both contain CRC. Transmitters can also send enquiry control frames to request a status report from the receiver to find out where to restart transmission.

\section{Stop-and-Wait ARQ}

With Stop-and-Wait ARQ there is only one active frame at a time. The sender sends the frame, and will not send another until it has received an acknowledgement or negative acknowledgement from the receiver for that frame. Also, the sender will retransmit the message if its timer times out.  

\section{Go-Back-N ARQ}

Go-Back-N ARQ improves upon Stop-and-Wait ARQ when the time to put the frame into the transmission medium is smaller than the time the frame is in the transmission medium, or more simply, when there is unused space in the pipe. With Go-Back-N ARQ there can be N active frames at a time. An ACK is sent for each frame that is verified by the receiver and when a NAK is sent all frames after and including that negatively acknowledged frame are resent in sequential order. A timeout is treated the same as a NAK. The optimal window size, N, is equal to the delay bandwidth product.

\section{Full Duplex Systems}

If both ends are senders ACKs and NAKs do not have to be sent as separate frames but can be attached (or piggybacked) to information frames. This is done while both sides have information to send. If an acknowledgement is due but the side that is suppose to send it has no information, the acknowledgement will be sent separately after a length of time has passed. The timeout value should be large enough to account for both sides sending the largest possible frame.

\section{Problem with Go-Back-N ARQ}

A single lost frame can cause retransmission of a large number of frames. However, most frames are lost due to congestion and transmitting a large number of frames will multiply congestion, and thus lost frames in the network. A deadly cycle will ensue in which the network will become exponentially worse. A solution to this is Selective Repeat ARQ.

\section{Selective Repeat ARQ}

In Selective Repeat ARQ only the individual frame that received the NAK (or timed out) is retransmitted. Both sender and receiver maintain a window of packets that can be sent/received without an acknowledgement. Just like the other protocols, every correctly transmitted frame is matched by an acknowledgement.

\section{Flow Control}

With ARQ only a certain amount of data is sent before an acknowledgement is received, providing a form of flow control. However, since complications arise without a separate means of flow control, as can be read about in page 316 of the book, special control messages are usually used in addition to ARQ. Additionally, the overhead of ARQ can unnecessarily slow the rate of flow. To perform flow control the source can either request a rate to transfer data at or can monitor the network independently to see what rate is available to it for transmission. It may also do a mix of these things. 

\section{Second Generation Flow Control}

Responds to the receiver as well as to the state of the network. This can involve state measurement, sending at an optimal rate reported by the network or detected by measuring the network. This can also involve control, whether to use window (similar to ARQ) based flow control or rate (timer) based flow control. Additionally, this could also involve point of control, whether to use hop-by-hop or end-to-end flow control.

\section{TCP flow control}

TCP random early drop (RED) is when a random packet from the queue is dropped when the queue is overfilled. The packet is selected randomly to ensure equality, allowing equal access to the overfilled queue and not, for example, first come first serve access which would prevent subsequent packets from entering. 










%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% END OF DOCUMENT
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifnum\solitude=1
\end{document}

\fi