\documentclass{article}
\title{Prolog Notes}
\author{Ashwin Ahuja}
\usepackage{float}
\usepackage{graphicx}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{tabto}
\usepackage{amssymb}
\usepackage[T1]{fontenc}
\newenvironment{definition}{\par\color{blue}}{\par}
\newenvironment{pros}{\par\color[rgb]{0.066, 0.4, 0.129}}{\par}
\newenvironment{cons}{\par\color{red}}{\par}
\newenvironment{example}{\par\color{brown}}{\par}
\usepackage{fancyhdr}
%% Margins
\usepackage{geometry}
\geometry{a4paper, hmargin={2cm,2cm},vmargin={2cm,2cm}}

%% Header/Footer
\pagestyle{fancy} 
\lhead{Ashwin Ahuja}
\chead{Computer Networking}
\rhead{Part IB, Paper 5}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{1.0pt}
\renewcommand{\footrulewidth}{1.0pt}

\usepackage[export]{adjustbox}
\usepackage{caption}
\captionsetup{justification   = raggedright,
	singlelinecheck = false}

\lstset{
	basicstyle=\ttfamily,
	columns=fullflexible,
	breaklines=true,
	postbreak=\raisebox{0ex}[0ex][0ex]{\color{red}$\hookrightarrow$\space}
}
\usepackage{listings}
\lstset{
	escapeinside={(*}{*)}
}



\begin{document}
\begin{titlepage}
\begin{center}
			\vspace*{1cm}
			
			\Huge
			\textbf{Computer Networking}
			
			\vspace{0.5cm}
			\LARGE
			University of Cambridge
			
			\vspace{1.5cm}
			
			\textbf{Ashwin Ahuja}
			
			\vfill
			
			Computer Science Tripos Part IB\\
			Paper 5
			
			\vspace{5cm}
			
			March 2019
			
\end{center}
\end{titlepage}

\tableofcontents
\pagebreak

\section{Introduction}


\begin{definition}
\textbf{Network}: System of links that interconnect nodes in order to move information between nodes.
\end{definition}
\bigskip
\noindent
\textbf{Defining Characteristics of the Internet}
\begin{enumerate}
	\item \textbf{Federated System:} Internet ties together different networks (> 18,000 ISP networks) - tied together by the Internet Protocol - single common interface between users and the network and between networks. 
	
	This single interface is great for interoperability (this is the Internet's most important goal) but is difficult for business. However, there are practical realities of incentives, economics and real-world trust drive topology, route selection and service evolution.
	
	\item \textbf{Tremendous Scale:} 
	\begin{enumerate}
		\item 4.15 billion Users
		\item 1.3+ trillion unique URLs (1.8 billion web servers)
		\item 2.5 billion smartphones
		\item 850 billion tweets a day
		\item 5 billion YouTube videos watcher per day
		\item 300+ tb/s moved by switches
		\item 67.5 tb/s carried by network links
	\end{enumerate}
	
	\item \textbf{Enormous Diversity and Dynamic Range:} 
	\begin{enumerate}
		\item Communication Latency: microseconds to seconds (10$^{6}$)
		\item Bandwidth: 1Kbits/s to 400 Gbits/s (10$^{7}$)
		\item Packet Loss: 0 - 90$\%$
		\item Technology: optical, wireless, satellite, copper
		\item Endpoint devices: from sensors and cell phones to datacenters and supercomputer
		\item Applications: social networking, file transfer, ...
		\item Users: Governments, elderly, young, \textit{malicious}
	\end{enumerate}

	\item \textbf{Constant Evolution:} Things keep evolving, eg. 1970s to today: gone from 56kb/s to 400+gb/s backbone links, < 100 computers (mostly in the US) to 40B+ devices all over the globe.
	
	\item \textbf{Asynchronous Operation:} Always require dated communication feedback - has a fundamental constraint of the speed of light.
	
	\item \textbf{Prone to Failure:} Failure is rather likely - to send a message all components (lots of components) along a path must function correctly.
	
	Also, takes a long time to hear any bad news due to asynchrony $\$$ due to federation, it is hard to identify faults or assign blame.
	
	\item \textbf{Engineered System:} Constraint is what technology is practical in terms of bandwidths, port counts, error rates and \textbf{cost}
	
	\item Too complex for theoretical models
	\item Working code doesn't necessarily mean much
	\item Performance benchmarks are very narrow
	
\end{enumerate}

\subsection{Physical Channels}
\begin{enumerate}
	\item \textbf{Twisted Pair:} Two insulated copper wires (can be shielded (STP) or unshielded (UTP))
	
	Either Category 3 (traditional phone wires, 10 Mbps Ethernet) or Category 6 (1 Gbps Ethernet)
	
	\item \textbf{Coaxial Cable:} Two concentric, bidirectional copper conductors. Comes in:
	
	Baseband - single channel on cable (legacy Ethernet)
	
	Broadband - multiple channels on cable (Hybrid Fiber Coax)
	
	\item \textbf{Fiber Optic Cable:} High-speed (10s to 100 Gps) operation with point-to-point transmission and a low error rate. \textcolor{red}{However, immune to electromagnetic noise.}

\end{enumerate}

\subsubsection{Radio}
Bidirectional and multiple access, the propagation environment is effected by: (1) Reflection, (2) Obstruction by objects and (3) Interference

\bigskip
\noindent
\textbf{Link Types}
\begin{enumerate}
	\item Terrestrial Microwave: 45 Mbps channels
	\item LAN: 11 Mbps, 54 Mbps, 200 Mbps
	\item Wide-area: 4G cellular $\approx$ 4 Mbps
	\item Satellite (Geosynchronous or Low Earth): Kbps to 45 Mbps channel (or multiple smaller channels) with 270ms end-end delay
\end{enumerate}

\subsection{Nodes and Links}
\begin{definition}
\begin{itemize}
	\item \textbf{Bandwidth (capacity)}: number of bits sent (or received) per unit time (bps) (10Mbps in city over slow link, 10Gbps cross-country over fast link)
	\item \textbf{Latency (delay)}: propagation time for data to travel along the link (seconds) (0.1ms, 10ms)
	\item \textbf{Bandwidth-Delay Product (BDP)}: amount of data can be in flight at any time = propagation delay x bits/time = total bits in link (125KB, 12.5MB)
	\item \textbf{Packet Delay} = (Packet Size $\div$ Link Bandwidth) + Link Latency
\end{itemize}

\end{definition}

\subsection{Switched Networks:} 
Method of sharing network link resources (nodes share these resources)

\subsubsection{Circuit Switching} 
The source reserves the network capacity along a path.

Works as follows:
\begin{enumerate}
	\item Node A sends a reservation request
	\item Interior switches establish a connection (circuit)
	\item A starts sending data
	\item A sends tear-down circuit message
\end{enumerate}

\begin{definition}
\textbf{Frequency Division Multiplexing:} 
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/2.png} \end{figure}
	
\textbf{Time Division Multiplexing:} The time is divided into frames and the frames are divided into slots. The relative slot position inside the frame determines to which conversation the data belongs. The slots are reserved during circuit setup. However, if a conversation does not use its circuit then capacity is lost.
	
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/3.png} \end{figure}
\end{definition}

\bigskip
\textbf{Timing}
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/4.png} \end{figure}

\bigskip
\begin{itemize}
	\begin{pros}
	\item Guaranteed performance
	\item Fast transfer (once circuit is established)
	\end{pros}

	\begin{cons}
	\item Wastes bandwidth if traffic is bursty
	\item Overhead of connection setup time
	\item Recovery from failure is slow
	\end{cons}
\end{itemize}

\subsubsection{Packet Switching}
Data is sent as chunks (packets) of formatted bits - consists of a \begin{definition}
header: holds instructions to the network on how to handle the packet
\end{definition} and \begin{definition}
payload: data being carried
\end{definition}

\bigskip
In the header, contains a number of things including (1) internet address, (2) TTL, (3) Checksums. Each packet travels independently with no notion of packets belonging to a circuit - therefore no link resources are reserved in advance. 


The switches forward packets based on their headers - \textit{generally can assume time to process a packet at the switch is negligible}

\begin{enumerate}
	\item \textbf{Cut Through Switch}: Switch starts transmitting as soon as it has processed the header.
	\item \textbf{Store and Forward Switch}: Switch processes and forwards a packet only after it has received it entirely.
\end{enumerate}

Packet switches uses \textbf{statistical multiplexing}: Relies on the assumption that not all flows burst at the same time - that by sharing things, we get a higher efficiency. 

However, therefore under overload, things can get particularly bad. In order to deal with an overload, switches need to have a buffer which stores the overflow from the queue of packets to be dealt with - helps absorb transient overload. However, if receiving rate > processing rate, will always have a problem.


$\therefore$ packet delay = transmission delay + propagation delay + queuing delay (this is caused by packet interference which is made worse at high loads as there is less idle time to absorb bursts)

\bigskip
\textbf{Queuing Delay}
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/5.png} \end{figure}

\bigskip
\begin{itemize}
	\begin{pros}
		\item Efficient use of bandwidth
		\item Allows more users to use the network
		\item No overhead due to connection setup
		\item Resilient - can route around trouble
	\end{pros}
	
	\begin{cons}
		\item No guaranteed performance
		\item Header overhead per packet
		\item Queues and queuing delays
	\end{cons}
\end{itemize}


\subsection{Internet Federation}
Internet is composed of lots of different networks (> 18,000 ISPs):

\bigskip
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/6.png} \end{figure}
\begin{itemize}
	\item Tier-3 ISPs and local ISPs: customers of higher tier ISPs connecting them to the rest of the internet - this is the last hop for people
	\item Tier-2 ISPs (smaller ISPs): Pay tier-1 ISP for connectivity to the rest of the internet - they also peer privately with one another. 
	\item Tier-1 ISPs (are at the centre of hierarchy): National and international coverage - provides interconnect privately
\end{itemize}

\section{Architecture and Internet}

\subsection{Abstraction}
Abstraction is a concept for breaking down a problem - what not how. We therefore partition the system into modules and abstractions.
\begin{pros}
	This hides the implementation and allows it to be freely changed and can extend the functionality of the system by adding more modules.
\end{pros}

\begin{cons}
	However, this can impair the performance of the system - ie becomes question of ease of implementation vs worse performance.
\end{cons}


\bigskip
\textbf{Network System Modularity: } Implementation is distributed across many machines (routers and hosts). Must decide:

\begin{enumerate}
	\item \textbf{Layering: } How to break system into modules
	\item \textbf{End-to-End Principle: } Where modules are implemented
	\item \textbf{Fate-sharing: } Where state is stored
\end{enumerate}

\subsection{Layering}
This a restricted for of abstraction - the system functions are divided into layers with one build upon another. There is interaction only between adjacent layers. 

$\therefore$ The bottom layer is physical media and the top layer is application


\bigskip
\begin{definition}
	\textbf{Entity}: a thing - independent existence. They interact with the layers above and below, and communicate with. Usually do something useful. 
	
	\textbf{Peer Entities: } Same layer but different place. Communication between peers is supported by entities at lower layers.
	
	\textbf{Embedding: } Form of layering where higher-layer information embedded within lower-layer information. This higher layer information is generated by stripping off headers and trailers of the current layer. 
\end{definition}

\begin{cons}
\begin{itemize}
	\item Higher layers can duplicate lower layer functionality
	\item Information hiding hurts performance
	\item Headers get large
	\item Layer violations when gains too great to resist
	\item Layer violations when network doesn't trust ends
	\item Some application requirements can only be correctly implemented end-to-end in order to get things like reliability and security - \textbf{End-to-End Principle}
\end{itemize}
\end{cons}


\subsection{ISO Reference Model}
\begin{enumerate}
	\item Presentation: allow applications to interpret meaning of data - eg encryption, compression
	\item Session: Synchronisation, checkpointing, recovery of data exchange.
	\subitem The internet stack is missing these layers - these services must be implemented in applications
	\item Transport
	\item Network
	\item Link
	\item Physical
\end{enumerate}

\subsection{Protocols and Protocol Standardisation}
\begin{definition}
\textbf{Protocols define format, order of messages sent and received among network entities and actions taken on message transmission, receipt.}
\end{definition}

\bigskip
\textbf{Protocol Standardization: }All hosts must follow the same protocol - very small modifications can make a large difference or stop it working. Hence IETF (Internet Engineering Task Force) standards are created by working groups. We have gateways to allow networks which are using different protocols to communicate.


\bigskip
\textbf{Internet Design Goals (Clark '88)}:
\begin{enumerate}
	\item Connect existing networks
	\item Robust in face of failures
	\item Support multiple types of delivery services
	\item Accommodate a variety of networks
	\item Allow distributed management
	\item Easy host attachment
	\item Cost effective
	\item Allow resource accountability
\end{enumerate}


\subsection{Context of Internet}
\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/7.png} \end{figure}

Each layer (1) depends on layer below, (2) supports the layer above and is (3) independent of others. There are multiple versions of protocols in each layer and the interfaces differ so the components pick which lower-level protocol to use.

Network layer having only one protocol, IP allows for interoperability.

\begin{pros}
Layering is important to the internet's success as:
\begin{itemize}
	\item Reuse
	\item Hides underlying detail
	\item Innovation at each level can proceed in parallel
\end{itemize}
\end{pros}

\subsection{Adding functionality}
\begin{definition}
	\textbf{End-to-End Principle:} implementing functionality in the network (1) doesn't reduce host implementation complexity, (2) Does increase network complexity and (3) Increases delay and overhead on all applications even if it doesn't need the functionality.
\end{definition}

\bigskip
\textbf{When to implement - End-to-End principle interpretations}
\begin{enumerate}
	\item \textbf{Only-if-sufficient: }Don't implement a function at lower levels unless it can be completely implemented at this level
	\item \textbf{Only-if-necessary: }Don't implement anything in the network that can't be implemented correctly by the hosts.
	
	Therefore, make the network layer minimal - increased flexibility since lower layers stay simple - this trumps performance issues.
	
	\item \textbf{Only-if-useful: }If hosts can implement functionality correctly, implement it in a lower layer only as a performance enhancement iff it does not impose a burden on applications that do not require functionality.
\end{enumerate}

\subsection{Distributing Layers across the Network}
\begin{itemize}
	\item \textbf{Host: All layers} exist at the host - bits arrive on the wire, must make it up to the application
	\item \textbf{Router: Network, Physical, Link}: (1) Bits arrive on the wire so need physical, (2) Packets must be delivered to next-hop, link layer necessary and (3) Routers participate in global delivery so need network layer
	\item \textbf{Switches: Physical and Link}: Same as router, but don't do global delivery so don't need network layer
\end{itemize}

\bigskip
\textbf{Intermediate Layers: }Solves the issue of having to reimplement every application for every technology. We do this by introducing intermediate layers that provide a set of abstractions for various network functionality and technology. Therefore, a new app / media is implemented only once.

\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/8.png} \end{figure}



\section{Physical and Data-Link Layer}
\begin{definition}
	\textbf{Nodes}: Hosts and routers
	
	\noindent	
	\textbf{Links}: Communications channels that connect adjacent nodes along communication path are links (can be wired or wireless)
	
	\noindent
	\textbf{Frame}: Encapsulates datagram - layer-2 packet is an example of a frame
	
	\noindent
	\textbf{(Data-)Link Layer:} Has responsibility of transferring datagram from one node to adjacent node over a link
\end{definition}

\bigskip
\noindent
Link Layer provides the following main services:
\begin{enumerate}
	\item \textbf{Framing, physical addressing} \begin{itemize}
	\item Encapsulate datagram into frame - \textbf{adding header and trailer}. Frame headers use MAC addresses to identify the source and destination machines
	\item Channel access if working over a shared medium
	\end{itemize}
	\item \textbf{Reliable delivery between adjacent nodes}
	\item \textbf{Flow Control:} pacing between adjacent sending and receiving nodes
	\item \textbf{Error Control:} One of (1) error detection - these errors are caused by signal attenuation and noise and can request retransmission or (2) error correction
	\item \textbf{Access Control:} (1) Half-duplex: nodes at both ends of the link can transmit, but not at the same time $\&$ (2) Full-duplex: nodes at both ends can transmit at the same time 
	
\end{enumerate}

\bigskip
Link Layer is implemented in every host inside the \textbf{adaptors} or NIC (Network Interface Card) - implemented in a combination of hardware, software and firmware.


\bigskip
\textbf{Communications of Adaptors}
\begin{itemize}
	\item Sending: (1) encapsulates datagram in frame, (2) encodes the data for the physical layer and (3) adds error checking bits, provides reliability, flow control, etc.
	\item Receiving: (1) decodes data from physical layer, (2) looks for errors, provide reliability, flow control and (3) extracts the datagram, passing to upper layer at receiving side
\end{itemize}

\subsection{Coding}
Changing representation of the data, examples of coding representation changes are: (1) Encryption, (2) Error Detection, (3) Compression and (4) DAC and ADC

\bigskip
\textbf{Line Coding Examples}
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/9.png} \end{figure}

\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/10.png} \end{figure}

\bigskip
\textbf{Block Coding:} Transfers data with a fixed overhead: 20 $\%$ information per Baud in the case of 4B/5B. These are used to provide space for error-correcting codes to find, detect and fix issues in data.

\bigskip
\textbf{Line Coding Scrambling: }
\begin{enumerate}
	\item Create a scrambling sequence
	\item Duplicate the sequence
	\item Clients sending the message $\oplus$ scrambling sequence (decoding by doing inner product of signal and scrambling sequence)
	\item Never reuse scrambling sequence - if you use the same scrambling sequence for multiple messages then lose the secrecy
\end{enumerate}

\bigskip
\textbf{Self-Synchronising Scrambling}
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/11.png} \end{figure}

\subsection{Error Detection and Correction}
Basic Idea is: (1) Add additional information to a message in order to (2) detect and error and re-send a message or fix an error in the received message.

It is a method of using coding to deal with errors in data communication.

\bigskip
\begin{definition}
	\textbf{Forward Error Correction: }Replace erroneous data by its closest error-free data
\end{definition}

\bigskip
\textbf{Methods}
\begin{enumerate}
	\begin{definition}
		\item Parity: add one bit such that the number of all 1s is even	
	\end{definition}
	\begin{pros}
		Very easy to do - and only takes up one bit
	\end{pros}
	
	\begin{cons}
		Does not detect two-bit errors, no correction
	\end{cons}
	\begin{definition}
		\item \textbf{Cyclic Redundancy Check:} Sequence of redundant bits is appended to the end of data so that the resulting data becomes exactly divisible by a second predetermined binary number.
	\end{definition}
	
	CRC := rem(data $\div$ predetermined divisor)
	
	\begin{pros}
		Can detect various kinds of errors including 2-bit errors
	\end{pros}
	
	\begin{cons}
		More complicated, still offers no error correction
	\end{cons}
\end{enumerate}

\bigskip
\textbf{Error Detection vs Correction:}
\begin{itemize}
	\item Correction: A lot of noise. Expensive to re-send
	\item Detection: Less noise. Easy to re-send.
\end{itemize}

\subsection{Multiple Access Mechanisms}
In FDMA and TDMA each dimension is orthogonal - can be trivially combined, therefore this is very helpful.

\subsubsection{Code Division Multiple Access (CDMA)}
\begin{definition}
CDMA is used in several wireless broadcast channels standards (cellular, satellite, etc) where all user (unique code assigned to each user) share the same frequency but each user has their own chipping sequence to encode data. This allows multiple users to coexist and transmit simultaneously with minimal interference as long as the codes are orthogonal.
\end{definition}

\bigskip
\textbf{Encode / Decode}
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/12.png} \end{figure}
Therefore, when two senders send messages each with their unique code, each one has their unique code removed separately preventing the interference of multiple senders.


\subsubsection{Links}
Two types of links:
\begin{enumerate}
	\item Point-to-point: point-to-point link between Ethernet switch and host
	\item Broadcast (shared wire or medium): Ethernet, Hybrid Fiber-Coax, Home plug networking, wireless LAN
\end{enumerate}

\subsubsection{Protocols}
Distributed algorithm that determines how nodes on a single shared broadcast channel share channel, ie determining when the nodes can transmit. Therefore need to deal with interference and collisions. Also, need to do the communications about channel sharing on the channel itself.

\bigskip
\noindent
\textbf{Ideal Multiple Access Protocol on Broadcast channel of rate R bps}
\begin{enumerate}
	\item When one node wants to transmit, it can send at rate R
	\item When M nodes want to transmit, each sends at average rate R/M
	\item System is fully decentralised - has no special node to synchronise transmissions $\&$ no synchronisation of clocks
\end{enumerate}

\bigskip
\noindent
\textbf{MAC Protocols}
\begin{enumerate}
	\item \textbf{Channel Partitioning: } divide channel into smaller pieces and allocate piece to node for exclusive use
	
	\begin{pros}
		Channel is shared efficiently and fairly at high load
	\end{pros}

	\begin{cons}
		It is inefficient at low load: large delay in channel access and 1/N bandwidth is allocated even if only 1 active node
	\end{cons}
	
	\begin{enumerate}
		\item \textbf{TDMA (Time Division Multiple Access):} Access to the channel happens in rounds where each station gets a fixed length slot = pkt transfer time.
		
		\begin{cons}
			The unused slots go idle.
		\end{cons}
	
		\item \textbf{FDMA (Frequency Division Multiple Access):} Channel spectrum is divided into frequency bands and each station is assigned a fixed frequency band.
		
		\begin{cons}
			Unused transmission time in frequency bands go idle
		\end{cons}
	\end{enumerate}
	\item \textbf{Random Access: }channel is not divided - when a node has a packet to send, it transfers at a full channel data rate. Therefore, allow collisions, when there are two or more transmitting nodes, and recover from collisions
	
	\begin{pros}
		Efficient at low load, single node can fully utilize channel
	\end{pros}

	\begin{cons}
		At high load, there will be a collision overhead.
	\end{cons}

	\item \textbf{Taking Turns: }nodes take turns, but nodes with more to send can take longer turns - looking for the best in both worlds between channel partitioning and random access.
	
	\begin{enumerate}
		\item \textbf{Polling: }Master node invites slave nodes to transmit in turn - used with dumb slave devices
		
		\begin{cons}
			(1) Polling overhead, (2) Latency, (3) Single point of failure (master)
		\end{cons}
	
		\item \textbf{Token Passing: }Control token passed from one node to next sequentially
		
		\begin{cons}
			(1) Token overhead, (2) Latency, (3) Single point of failure (token)
		\end{cons}
	
	A number of the concerns can be fixed in part by a slotted ring (there are many simultaneous tokens)
	
	\end{enumerate}

\end{enumerate}

\bigskip
\textbf{Asynchronous Transfer Mode (ATM): }Asynchronous form of TDM, effectively it is Asynchronous Time Division Multiplexing. Sender transmits labelled cells wherever necessary.

\bigskip
\noindent
\begin{definition}
\textbf{Random Access}:
\begin{itemize}
	\item Carrier Sense: Check if someone else is already sending data and wait until the other node is done.
	\item Collision Detection: Detect when two nodes are transmitting at once by detecting that the data on the wire is garbled
	\item Randomness: Wait for a random time before trying again
\end{itemize}
\end{definition}

\subsubsection{Carrier Sense Multiple Access (CSMA)}
Listen before transmit. If the channel sensed idle then transmit the entire frame and if the channel sensed busy, defer the transmission.

\begin{cons}
	However, this doesn't eliminate all collisions because of non-zero propagation delay - when two nodes may not hear each other's before sending
\end{cons}

\subsubsection{CSMA/CD (Collision Detection)}
Carrier sending and deferral as in CSMA. The collisions are detected within a short time and colliding transmissions are aborted, reducing wastage. 

\begin{pros}
	Collision detection is easy in wired LANs, when you compare transmitted and received signals.
\end{pros}

\bigskip
\begin{cons}
	However, difficult in wireless LANs because: (1) Reception is shut off while transmitting, (2) Not perfect broadcast (limited range) so collisions local.

	There are limits on CSMA/CD Network Length as latency depends on physical length of link:
	\begin{itemize}
		\item Say A sends packet at time t
		\item B sees an idle line at time just before t+d so starts transmitting a packet
		\item B detects a collision and sends jamming signal
		\item But A can't see collision until t+2d
	\end{itemize} 
\end{cons}

\bigskip
\textbf{Performance}
\begin{itemize}
	\item Time wasted in collisions $\propto$ is proportional to distance d
	\item Time spent transmitting a packet = packet length (p) $\div$ bandwidth b
	\item Efficiency $\propto$ $\frac{\frac{p}{b}}{\frac{p}{b}+Kd}$ where K is a constant
	
	For large packets and small distances, the efficiency is close to 1, as the bandwidth increases the efficiency decreases. This explains why high-speed LANs are all switched.
\end{itemize}

\subsection{Ethernet}
\begin{pros}
	\begin{itemize}
		\item Easy to administer and maintain
		\item Inexpensive
		\item Increasingly higher speed
		\item Evolvable
	\end{itemize}
\end{pros}

\bigskip
\textbf{Evolution of Ethernet}: Everything changed except the frame format ((1) from single coax to hub-based star, (2) From shared media to switches, (3) From electrical signalling to optical)

\bigskip
\textbf{Ethernet CSMA/CD}: 
\begin{enumerate}
	\item Carrier Sense: wait for link to be idle
	\item Collision detection: listen while transmitting (if no collision, transmission is complete), if there's a collision, abort transmission and send jam signal. 
	\item Random Access: binary exponential back-off. After collision, wait a random time before trying again. After mth collision, choose K randomly from {0, ..., 2$^{m} - 1$} and wait for K*512 bit times before trying again using min packet size as slot. If transmission occurring when ready to send, wait until end of transmission (CSMA).
\end{enumerate}

\subsection{Wireless Spectrum}
\textbf{Metrics for Evaluation}
\begin{enumerate}
	\item Bitrate or Bandwidth
	\item Range
	\item Two-way / One-way
	\item Multi-Access / Point-to-Point
	\item Digital / Analog
	\item Applications and industries
	\item Frequency - affects most physical properties
\end{enumerate}

\bigskip
\textbf{Standards}
\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/13.png} \end{figure}

Wireless is harder - signals sent by sender don't always end up at the receiver intact - this leads to a number of issues.

\bigskip
\textbf{802.11 Architecture}: Access points are set to a specific channel and broadcast beacon messages with SSID and MAC Address periodically. Hosts scan all the channels to discover the APs (Access Points) and the hosts associates with the AP.

\subsubsection{Wireless Multiple Access Technique}
Carrier Sense takes a lot of time - sender has to listen before sending but collision detection is harder to do for wireless connections.

\bigskip
\textbf{Hidden Terminals}
\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/14.png} \end{figure}
A and C can both send to B but can't hear each other. A is a hidden terminal for C and vice versa. In this case, Carrier Sense is ineffective.

\bigskip
\textbf{Exposed Terminals}
\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/15.png} \end{figure}
There is an exposed node - (1) B sends a packet to A; C hears this and decides not to send a packet to D (despite the fact that this will not cause interference). Carrier sense would prevent a successful transmission.

\bigskip
\textbf{Important Points}
\begin{enumerate}
	\item No concept of global collision: (1) Different receivers hear different signals, (2) Different senders reach different receivers
	\item Collisions are at receiver, not sender: We only care if the receiver can hear the sender clearly, doesn't matter if sender can hear someone else - as long as signal does not interfere with receiver.
\end{enumerate}

Therefore protocol for wireless multiple access must detect if the receiver can hear the sender and tell senders who might interfere with the receiver to shut up. 

\bigskip
Also, since we can't detect collisions, we try to avoid them using Carrier Sense: \textit{When medium busy, choose random interval as the number of idle timeslots to wait for before sending}

When a collision is inferred, retransmit with binary exponential backoff (see above) - ACK from receiver to infer no collision

\bigskip
\textbf{CSMA/CA - MA with Collision Avoidance}
Before every data transmission:
\begin{enumerate}
	\item Senders sends RTS frame containing the length of the transmission
	\item Receiver responds with a CTS frame
	\item Sender sends data
	\item Receiver sends an ACK, now another sender can send data
	\item When sender doesn't get CTS, then it assumes a collision
	\item If other nodes hear an RTS, but not a CTS, then send data (RTS) as we presume the destination for first sender is out of the nodes' range - leads to problems in cases of lost CTS
	\item When you hear a CTS, keep quiet until scheduled transmission is over (hear an ACK)
\end{enumerate}

\bigskip
Can also prevent collisions by \textbf{partitioning Frequency Spectrum} - nodes within interference range can use separate channels. However, most cards have only 1 transceiver meaning things are not full duplex - you can't send and receive at the same time.

\bigskip
\textbf{RTS / CTS}
\begin{itemize}
	\begin{pros}
		\item RTS/CTS helps with hidden terminal
		\item Good for high-traffic Access points
		\item Turned on/off dynamically
	\end{pros}

	\begin{cons}
		\item Adds overhead
		\item Leads to wasted bandwidth
	
	\end{cons}
\end{itemize}

\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/16.png} \end{figure}

\subsection{Addresses}
\begin{definition}
\textbf{MAC Address: }Most LANs have a 48 bit MAC address - it is burned in the NIC ROM. It serves the function of getting a frame from one interface to another physically-connected interface (in the same network). MAC addresses are portable.

\noindent
\textbf{LAN Address: }The address allocation is administered by the IEEE - the manufacturer buys a portion of the MAC address space to ensure uniqueness. 
\end{definition}
\subsection{Hubs and Switches}
\begin{definition}
	\textbf{Hubs} are physical-layer repeaters: bits coming in one link go out all other links at the same rate and all nodes connected to the hub can collide with one another. There is no frame buffering and no CSMA/CD at hub, the host NICs detect collisions.
	
	\bigskip
	\noindent
	\textbf{Switches} are more complicated hubs, taking a more active role, doing a number of more things - see below.
\end{definition}

\subsubsection{Switches}
\begin{enumerate}
	\item \textbf{Link layer devices, taking an active role}: They store and forward Ethernet frames and examine the frame's MAC address. They selectively forward the frame to one or more outgoing links when the frame is to be forwarded on the segment and uses CSMA/CD to access the segment. 
	
	\item \textbf{Transparent}: hosts are unaware of the presence of switches.
	
	\item \textbf{Plug-and-play}
\end{enumerate}

They also allow \textbf{multiple simultaneous transmissions}:
\begin{itemize}
	\item hosts have direct connection to switch
	\item switches buffer packets
	\item Ethernet protocol used on each incoming link, but no collisions; therefore means full duplex
\end{itemize}

\bigskip
\textbf{Switch Table}: Switches have a switch table where each entry is \textit{MAC address of host, interface to reach host, time stamp}. The switch learns which hosts can be reached through which interfaces through the following means:
\begin{itemize}
	\item When a frame is received, the switch learns the location of the sender, doing the following:
	\begin{enumerate}
		\item Record link associated with sending host
		\item Index switch table using MAC destination address
		\item \begin{lstlisting}
		if(entry(destination)){
			if dest on segment from which frame arrived {
				drop frame;
			}
			else
			{
				forward the frame on interface indicated 
			}
		}
		else flood (forward on all but the interface on which the frame arrived)
		\end{lstlisting}
	\end{enumerate}
	\item Records sender / location pair in switch table
\end{itemize}

\bigskip
\textbf{Interconnecting Switches}: Using the old method with flooding can lead to forwarding loops, therefore create spanning trees (sub-graph that covers all vertices but contains no cycles). Links not in the spanning tree do not forward frames.

\bigskip
Attempt to find a tree that includes all nodes with a minimum number of edges and using the shortest paths and only keep the links on the shortest path.

\bigskip
Switches elect a root - switch with smallest identifier and each switch determines if each interface is on the shortest path from the root - excludes from tree if not. Format of message is Messages(Y, d, X): From node X, proposing Y as root and distance is d.

\bigskip
\textbf{Steps}
\begin{enumerate}
	\item Initially, each switch proposes itself as root: (1) Switch sends message out on every interface proposing itself as root with distance 0
	\item Switches update their view of the root: If new id is smaller, start viewing that switch as the root
	\item Switches compute distance from the root: (1) Add 1 to the distance received from neighbour and (2) identify interfaces not on shortest path to the root and exclude them from the spanning tree.
	\item If the root or shortest distance is changed, flood the updated message (Y, d+1, X)
	\item Root switch continues sending messages (periodically reannounce itself as the root) and other switches continue forwarding messages
	\item \textbf{Failures}
	\begin{enumerate}
		\item Detecting failure through time-out (Soft State): If no word from root, times out and claims to be root
		\item Failure of root node: Need to elect new root with next lowest identifier
		\item Failure of other switches and links: need to recompute the spanning tree
	\end{enumerate}
\end{enumerate}

\section{Network Layer}
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/21.png} \end{figure}

\textbf{Types of networks}:
\begin{enumerate}
	\item ISPs: backbone, edge and border (to other ISPs)
	\item Enterprises: Core, edge and border (to outside)
	\item Datacenters: Top-of-rack, Aggregation and Core, border (to outside)
\end{enumerate}

\bigskip
\textbf{Forwarding Decisions}
\begin{enumerate}
	\item When packet arrives: (1) Must decide which outgoing port, (2) in single transmission time, (3) decisions must be simple
	\item Routing state dictates where to forward packets - assume decisions are deterministic
	\item Global routing state means collection of routing state in each of the routers
\end{enumerate}

\bigskip
\begin{definition}
	\textbf{Forwarding (data plane): }Directing a data packet to an outgoing link, with the individual router using the routing state.
	
	\textbf{Routing (control plane): }Computing paths the packets will follow where the routers talk amongst themselves and jointly creating the routing state.
	
	N = number of external router ports
	
	R = speed of a port
	
	Router capacity = N x R
\end{definition}

\subsection{Router}
\textbf{Switches vs Routers}
\begin{itemize}
	\item \textbf{Routers:} maintain routing tables, implement routing algorithms
	\item \textbf{Switches:} maintain switch tables, implement filtering and learning algorithms
\end{itemize}
	
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/17.png} \end{figure}

The Route and Control Processor:
\begin{enumerate}
	\item Implements IGP and BGP protocols and computes the routing tables
	\item Pushes forwarding tables to the line cards
	\item It constitutes the control plane - making decisions over the long time horizons
\end{enumerate}

\begin{definition}
	\noindent
	The linecards and interconnect fabric makes a decision for each packet constituting the data plane.
\end{definition}

\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/18.png} \end{figure}

\begin{definition}
\begin{itemize}
	\item End hosts (clients, users, end points) are the final machines
	
	\item Border routers are the orange boxes, interior routers are blue boxes
	
	\item Autonomous Systems or Domains are the regions of the network under a single administrative entity - the clouds
	
\end{itemize}
\end{definition}

\bigskip
\noindent
\textbf{IP Router Architecture}
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/19.png} \end{figure}

\noindent
\textbf{Key Feature: }If control-plane fails, the data-path is not affected - keeps going using last table update

\bigskip
\noindent
\textbf{Per-packet processing}
\begin{enumerate}
	\item Accept packet arriving on incoming link
	\item Lookup packet destination address in forwarding table
	\item Manipulate packet header: (1) decrement TTL, (2) update header checksum
	\item Send packet to the outgoing port
	\item Buffer packet in the queue
	\item Transmit packet onto outgoing link
\end{enumerate}

\begin{figure}[H] \includegraphics[width=.65\textwidth, left] {./images/20.png} \end{figure}



\subsection{Routing Protocols}
\textbf{Internet Routing Protocols }are responsible for constructing and updating the forwarding tables at the router. They establish the paths between nodes where the network is modelled as a graph (routers are graph vertices, links are edges where they have an associated cost). The goal is to compute the shortest path from the source to the destination.

\bigskip
Internet Routing works at two levels:
\begin{enumerate}
	\item Intra-domain routing protocol is established by each AS that establishes routes within its domain
	
	Creates Link State - Open Shortest Path First (OSPF)
	
	Distance Vector - Routing Information Protocol (RIP)
	\item ASes participate in an inter-domain routing protocol that establishes routes between domains.
	
	Creates path vector using Border Gateway Protocol (BGP)
\end{enumerate}

\bigskip
\noindent
\textbf{Goals for routing solution}
\begin{enumerate}
	\item Least cost paths
	\item Fast convergence after change
	\item Scalable in terms of number of messages, table size and processing complexity
	\item Secure
	\item Policy
	\item Rich metrics
	\begin{itemize}
		\item Propagation delay
		\item Congestion
		\item Load balance
		\item Bandwidth (available, capacity, maximal, bbw)
		\item Price
		\item Reliability
		\item Loss rate
		\item Combinations of the above
	\end{itemize}
\end{enumerate}

\subsubsection{Link State Routing}
\begin{definition}
	\textbf{Link State:} List of its directly attached links and their costs
\end{definition}

\begin{enumerate}
	\item Each node maintains its local link state
	\item Each node floods its local link state: on receiving a new link state message, a router forwards the message to all its neighbours other than the one it received the message from.
	\item Thus, each node learns the entire network topology using \textbf{Djikstra's} to compute the shortest path between nodes.
	\begin{enumerate}
		\item INPUT: Network topology with link costs
		\item OUTPUT: Least cost paths from one node to all other nodes.
		\item After k iterations, a node knows the least cost path to its k closest neighbours
	\end{enumerate}
\end{enumerate}

\bigskip
\noindent
\textbf{Forwarding Table: }Gives us which is the next hop in order to get to any destination.

The naive approach is to have one entry per address, but that has approximately 4 billion entries, so is terribly inefficient. The improved approach is to group entries to reduce the table size. Groups and matches destinations using a \textbf{Longest Prefix Match} - picks the most specific correct entry that exists.

\begin{itemize}
\begin{cons}
	\item \textbf{Scalability: } O(NE) messages needed in order to flood link state messages and O(N log(N)) complexity. Also, O(E) entries in the link state topology database and O(N) entries in the forwarding table.
	\item \textbf{Transient Disruptions: }Inconsistent link-state database where some routers know about failure before others and the shortest paths are not consistent. This causes transient forwarding loops.
\end{cons}
\end{itemize}

\subsubsection{Distance Vector Routing}
Each router sends its knowledge about the whole network to its neighbours with information sharing happening at regular intervals.

\begin{enumerate}
	\item Each router knows the links to its neighbours
	\item Each router has provisional shortest path to each other router
	\item Routers exchange this distance vector information with their neighbouring routers - vectors because there is one entry per destination
	\item Routers look over the set of options offered by their neighbours and select the best one
	\item Iterative process converges to set of shortest paths
\end{enumerate}

However, (1) need to be careful about the metric we pick instead of cost, as it needs to be additive. Also, (2) need to ensure that all the nodes choose their paths according to the same criteria - otherwise could lead to a loop occurring. Finally, sometimes (3) routers can lie.

\begin{itemize}
\begin{pros}
	\item DV has lower messaging overhead than LS
	\item DV has a lower processing complexity than LS
\end{pros}
\begin{cons}
	\item More vulnerable to looping than LS
\end{cons}

	\item Message complexity
	\begin{itemize}
		\item LS: O(NE) messages
		\item DV: O(n(iterations) x E) where n(iterations) is O(network diameter)
	\end{itemize}

	\item Processing complexity
	\begin{itemize}
		\item LS: O(N$^{2}$)
		\item DV: O(n(iterations) x N)
	\end{itemize}

	\item Robustness: what happens if router malfunctions
	\begin{itemize}
		\item LS: (1) Node can advertise incorrect link cost, (2) each node computes only its own table
		\item DV: (1) Node can advertise incorrect path cost, (2) each node's table used by others, error propagates through the network
	\end{itemize}
\end{itemize}

\subsection{Delivery Models}
\begin{definition}
	\textbf{Broadcast: }send to all
	
	\noindent
	\textbf{Multicast: }send to all members of a group
	
	\noindent
	\textbf{Anycast: }send to any member of a group
\end{definition}


\subsection{Buffers}
How to pick the size of the buffer, it affects:
\begin{enumerate}
	\item End-to-end delay: transmission, propagation and queueing delay
	\item Router architecture: board space, power consumption and cost. \textbf{On chip buffers} have a higher density but lower cost for example and can also have \textbf{all-optical routers}.
\end{enumerate}

Rule-of-thumb: Window size is the number of packets is outstanding. If an ACK is received W <- W+1/W, if a packet is lost W <- W/2

\subsubsection{Small Buffers}
The aggregate window has the same dynamics, therefore the buffer occupancy has the same dynamics. The aggregate becomes Gaussian by the Central limit theorem with the variance in buffer size decreasing as N increases.

\subsection{IP Packet Structure}
20 Bytes of Standard Header, then Options
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/22.png} \end{figure}

\subsubsection{Reading Packet}
\textbf{Version Number (4 bits)}: indicates version of the IP protocol, either 4 or 6.

\noindent
\textbf{Header Length (4 bits)}: number of 32-bit words in header, generally 5 for 20-byte IPv4 header
	
\noindent
\textbf{Total Length (16 bits)}: number of bytes in the packet, maximum size is 2$^{16}$-1 but underlying links may impose smaller limits

\subsubsection{Getting Packet to Destination and Back}
\textbf{Source Address (32 bits)}: Unique ID for the sending host which allows the recipient to decide whether to accept the packet and allows recipient to respond to source

\noindent
\textbf{Destination Address (32 bits)}: Unique ID for the receiving host which allows each node to make forwarding decisions


\subsubsection{Telling host how to handle packet}
\textbf{Protocol (8 bits)}: identifies the higher-level protocol and is important for demultiplexing at the receiving host, eg 6 for TCP, 17 for UDP

\subsubsection{Special Handling}
\textbf{Type-of-Service (8 bits)}: allows packets to be treated differently based on needs - ie low delay for audio, high bandwidth for bulk transfer. It has been redefined several times over the years.

\subsubsection{Options}
\begin{enumerate}
	\item End of Options List
	\item No Operation (padding between options)
	\item Record Route
	\item Strict Source Route
	\item Loose Source Route
	\item Timestamp
	\item Traceroute
	\item Router Alert
\end{enumerate}

\subsubsection{Potential Problems}
\begin{enumerate}
	\item \textbf{Header Corruption}: Fixed by having a \textbf{checksum (16 bits)} over the packet header - if the checksum isn't correct, discard packet. 
	
	\item \textbf{Preventing Loops}: Forwarding loops cause the packets to cycle forever, eventually consuming all the capacity. Therefore, have a \textbf{TTL (Time-To-Live) field (8 bits)} which is decremented at each hop and the packet is discarded if the TTL reaches 0 and a time exceeded message is sent to the source (using an ICMP control message - this is the basis for trace-route)
	
	\item \textbf{Fragmentation}: When forwarding a packet, internet router can split it into multiple fragments if it is too big for the next hop link - since network links have a maximum transfer size. 
	
	\begin{itemize}
		\item \textbf{Fragmentation information (32 bits): identifier, flags and fragment offset} - allows us to reassemble the original packet. 
		
		\item \textbf{Identifier (16 bits)} are used to tell which fragments belong together, 
		
		\item \textbf{Flags (3 bits)} are the following: (1) Reserved (RF) is an unused bit, (2) Don't Fragment (DF) instructs routers to not fragment the packet even if it won't fit - instead will drop the packet and sends back a 'too large' ICMP control message and (3) More - says this fragment won't be last
		
		\item \textbf{Offset (13 Bits)}: What part of the datagram this fragment covers in 8-byte units 
	\end{itemize}
\end{enumerate}

\subsection{IP Addressing}
\begin{definition}
	\textbf{IP Address}: 32-bit identifier for host, router interface. Composed of a subnet part (high order bits) and a host part (low order bits)
	
	\bigskip
	\noindent
	\textbf{Interface}: Connection between host/router and physical link - hosts have one interface vs routers have multiple interfaces. There are IP addresses associated with each interface.
	
	\bigskip
	\noindent
	\textbf{Subnet}: Devices interface with the same subnet part of IP address and can physically reach each other without an intervening router.
	\begin{itemize}
		\item \textbf{Classless InterDomain Routing (CIDR)}
		\item Address format is a.b.c.d/x where x is the number of bits in the subnet portion of the address.
	\end{itemize}
\end{definition}

\bigskip
\textbf{Getting IP Addresses}
\begin{enumerate}
	\item Hard-coded by a system admin in file /etc/rc.config
	\item \textbf{Dynamic Host Configuration Protocol (DHCP)}: dynamically get address from a server - therefore highly portable.
\end{enumerate}

\subsubsection{DHCP Client-Server Scenario}
Allows a host to dynamically obtain its IP address from a network server when it joins the network. It can also renew the lease on address in use

\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/23.png} \end{figure}

The network gets allocated a portion of its provider ISP's address space. The addressing is done hierarchically to allow for efficient advertising of routing information. ISPs get a block of addresses after they are allocated by ICANN (Internet Corporation for Assigned Names and Numbers)

\subsubsection{Network Address Translation (NAT)}
(1) Solves the problem of running out of IP addresses, also (2) allows us to change addresses of devices in local network without notifying outside world. (3) Can also change ISP without changing addresses of devices in the local network. (4) Devices inside the local network are not explicitly addressable, visible by the outside world (is a security plus).

\bigskip
Means all datagrams leaving a local networks have the same single source NAT IP address with different source port numbers

\bigskip
\noindent
\textbf{Implementation}: NAT router:
\begin{enumerate}
	\item In outgoing datagrams, replace (source IP address, port number) to (NAT IP address, new port number). Remote servers will respond using (NAT IP address, new port number) as the destination address.
	
	\item Remember (in a NAT translation table) every (source IP address, port number) to (NAT IP address, new port number)
	
	\item In incoming datagrams, replace (NAT IP address, new port number) in destination fields of every incoming datagram with corresponding (source IP address, port number) stored in NAT table.
\end{enumerate}

\bigskip
\noindent
\textbf{Reasons NAT is Controversial}
\begin{cons}
	\begin{itemize}
		\item Violates end-to-end argument - NAT must be taken into account by app designers
		\item Routers should only process up to layer 3
		\item The address shortage should be instead solved with IPv6
	\end{itemize}
\end{cons}

\subsubsection{Traceroute}
\begin{enumerate}
	\item Source sends series of UDP segments to destination with consecutively increasing TTLs. 
	\item When the nth datagram arrives at the nth router, the router discards the datagram and sends to source an ICMP message (type 11, code 0). The message includes the name of the router and the IP address.
	\item When the ICMP message arrives, the source calculates RTT - traceroute does this three times
	\item \textbf{Stopping Criterion}
	\begin{itemize}
		\item UDP segment eventually arrives at destination host
		\item Destination returns ICMP "host unreachable" packet (type 3, code 3)
		\item When the source gets this ICMP, it stops.
	\end{itemize}
\end{enumerate}

\subsubsection{Internet Control Message Protocol (ICMP)}
Used by hosts and routers to communicate network level information including error reporting and for echo requests. It is a network layer above IP where ICMP messages are carried in IP datagrams.

\bigskip
\noindent
\textbf{ICMP structure:} type, code plus first 8 bytes of IP datagram causing error.

\begin{figure}[H] \includegraphics[width=.3\textwidth, left] {./images/25.png} \end{figure}

\subsection{Address Resolution Protocol (ARP)}
\begin{itemize}
	\item Every node maintains an ARP table of (IP address, MAC address)
	\item Consult the table when sending a packet which maps destination IP address to destination MAC address
\end{itemize}

\bigskip
\noindent
\textbf{Example: A sending a packet to B through R}
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/26.png} \end{figure}
\begin{enumerate}
	\item Host A constructs an IP packet to send to B with source 111.111.111.111 and destination 222.222.222.222
	\item Host A has a gateway router R used to reach destinations outside 111.111.111.0/24
	\subitem The address for R (111.111.111.110) is learned via DHCP/config
	\subitem Host A learns the MAC address of R's interface using an ARP request: broadcast request for 111.111.111.110 and gets an ARP response: R responds with E6:E9:00:17:BB:4B
	\item Host A encapsulates the packet and sends it to R
	\item Router R's adaptor receives the packet
	\subitem R extracts the IP packet from the Ethernet frame and sees the IP packet is destined to 222.222.222.222
	\item Consults its forwarding table and that matches 222.222.222.0/24
	\item R learns the MAC address of host B
	\subitem ARP request: broadcast request for 222.222.222.222
	\subitem ARP response: B responds with 49:BD:D2:C7:56:2A
	\item R encapsulates the packet and sends it to B
\end{enumerate}

\subsubsection{Security Analysis}
\begin{cons}
\textbf{Impersonation}: Any node that hears request can answer and can say whatever they want. Even legit receivers never see problems, because even though later packets carry its IP address, its NIC doesn't capture them since not its MAC address.
\end{cons}

\subsubsection{Key Ideas of ARP}
\begin{enumerate}
	\item \textbf{Broadcasting}: Can use broadcast to make contact - is scalable because of the limited size.
	
	\item \textbf{Caching}: remember the past for some time and store the information you learn to reduce the overhead. Remember own address and other host's addresses.
	
	\item \textbf{Soft state}: eventually forget the past - associate a time-to-live field with the information and either refresh or discard the information. This is key for the robustness in the face of unpredictable change.
\end{enumerate}

\subsection{IPv6}
Motivated by address exhaustion but brought lots of other changes:
\begin{figure}[H] \includegraphics[width=.8\textwidth, left] {./images/27.png} \end{figure}

\bigskip
\textbf{Header Structure}
\begin{figure}[H] \includegraphics[width=.8\textwidth, left] {./images/28.png} \end{figure}

Optional state is carried in extension headers where they notionally replace IP options. Each extension header indicates the type of the following header so that they can be chained. The final 'next header' indicates there is no 'next', or escapes into an upper-layer header.

\subsubsection{IPv6 Address Structure}
\begin{itemize}
	\item Split into 64 bits for a 'Routing Prefix' and 64 bits for 'Interface Identifier' - addressable interface (equivalent to a single host, if it only has one interface). 
	\item There is longest-prefix matching as in IPv4. 
	\item It is generally represented as eight 16 bit blocks (4 hex characters) separated by colons.
	\item Can condense the representation by removing leading zeros in each block and then further by reducing consecutive blocks of zeros to a '::' (can only be done once to the last blocks of zeros)
\end{itemize}

\bigskip
\noindent
The address space is carved into certain categories:
\begin{itemize}
	\item \textbf{host-local}: localhost; ::1 is equivalent to 127.0.0.1
	\item \textbf{link-local}: used on a single link or a non-routed common access network such as Ethernet LAN. Don't need to be unique outside of that link. May appear as the source or destination of an IPv6 packet. Routers must not forward IPv6 packets if the source or destination contains a link-local address
	
	not routed: fe80::/10 is equivalent to 169.254.0.0/16
	\item \textbf{site-local}: not routed globally
	\item \textbf{global unicast}: a conventional, publicly routable address that can be used that is associated with a single node and can be used to identify the node.
	
	2000::/3 is basically any v4 address not reserved in some other way
	\item \textbf{multicast}: addresses used to identify multicast groups - used as destination addresses, never as source addresses
	
	ff00::/8 is equivalent to 224.0.0.0/4
\end{itemize}

\subsubsection{Neighbour Discovery}
Neighbour Discovery Protocol specifies a set of ICMPv6 message types that allow hosts to discover other hosts or routing hardware on the network. Host can solicit neighbour host state to determine the layer-2 address of a host or to check whether an address is in use or it can solicit router state to learn more about the network configuration.

\subsubsection{Dynamic Address Assignment and SLAAC}
The two halves of the IPv6 address are derived in different ways - Network (top half) is done through Router Advertisements and the bottom half (Identifier) is done using SLAAC (Stateless) or DHCPv6 (Stateful) methods.

\bigskip
\textbf{SLAAC} is intended to make network configuration easy without manual configuration or DHCP server. An algorithm for hosts to automatically configure their network interfaces (set up addresses, learn routes) without intervention.

When host goes live or interface comes up, the system wants to know more about its environment - can configure link-local addresses for its interfaces using the interface identifier (EUI-64 - various techniques to derive a 64-bit value but often derives from the 48-bit MAC address). Uses this to ask router advertisements sooner than the next periodic announcements therefore we ask the network for information.

\begin{enumerate}
	\item Generate potential link-local address
	\item Ask the network (multicast) if that address is in use
	\item Assuming no responses, assign to interface
\end{enumerate}

\bigskip
\textbf{Router Solicitation}: Once the host has a unique link-local address, can send packets to anything else sharing that link substrate but host doesn't yet know any routers or public routers. The host asks the network (using multicast) for router information - \textbf{router solicitation}. Responses from the router (which is listening to a well-known multicast address) are sent directly to the host that sent the router solicitation. The responses may indicate that the host should do more (for example using DHCP to get DNS information).

\bigskip
\textbf{Router Advertisement}: Generated intermittently by routing hardware there are (1) nodes that forward traffic periodically advertise themselves to the network. (2) The periodicity and expiry of the advertisement are configurable. Tells a host where to derive its network state with two flags: Managed Address Configuration (M) and Other info (O)
\begin{itemize}
	\item Managed Address Configuration (M): use DHCPv6 to find your host address (and ignore option O)
	\item O: Other information is available via DHCPv6 such as DNS configuration
\end{itemize}


\textbf{Issues arising from totally decentralised address configurations}:
\begin{enumerate}
	\begin{cons}
	\item \textbf{Privacy}: SLAAC interface identifiers don't change over time so a host can be identified across multiple networks
	\end{cons}

	In response to this, there were a number of \textbf{privacy extensions to SLAAC}:
	\begin{enumerate}
		\item Temporary addresses for initiating outgoing sessions
		\item Generate one temporary address per prefix
		\item When they expire, they are not used for new sessions but can continue to be used for existing sessions
		\item Addresses should appear random, st they are difficult to predict
	\end{enumerate}

	\bigskip
	\textbf{Algorithm}
	\begin{enumerate}
		\item Assume that you have a stored 64-bit value from previous iterations or a pseudo-randomly generated value
		\item Take that input value and append it to EUI-64
		\item Compute the MD5 message digest of that value
		\item Set bit 6 to zero
		\item Compare leftmost 64-bits against list of reserved interface identifiers and those already assigned to an address on the local device. If the value is unacceptable, re-run using the rightmost 64 bits of the result instead of the historic input value from (2)
		\item Uses the leftmost 64-bits as the randomised interface identifier
		\item Store rightmost 64-bits as the history value to be used in the next iteration of algorithm
	\end{enumerate}


	\begin{cons}
	\item \textbf{Security}: Embedding a MAC address into an IPv6 address will carry that vendor's ID, a possible threat vector
	\end{cons}
\end{enumerate}

\subsubsection{IPv6 Transition}
\begin{cons}
\textbf{Issues}
\begin{enumerate}
	\item Lack of compatibility between IPv4 and IPv6
	\begin{enumerate}
		\item Different packet formats
		\item Different addressing schemes
	\end{enumerate}

	\item IPv4 has momentum (led to Classless Inter-Domain Routing and encouraged NAT)
\end{enumerate}
\end{cons}

\bigskip
\noindent
\textbf{Transition Technology}
\begin{enumerate}
	\item Tunnelling
	\item \textbf{Dual-stacked services and happy eyeballs}
	\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/29.png} \end{figure}
	
	Aim is to reduce the pain by dual-stacking the edge hosts and carry state in HTTP headers indicating the user's IP address. Can dual-stack the back-end opportunistically over a longer period of time. Can use DNS to enable / disable the v6 side last (if there is no AAAA record in DNS, no real users will connect to the IPv6 infrastructure)
	
	\textbf{Happy Eyeballs}: Introduction of IPv6 carried with it an obligation that applications attempt to use IPv6 before falling back to IPv4. But presence of IPv6 modifies the behaviour of DNS responses and response behaviour. Therefore Happy Eyeballs is an algorithm more responsive to users by attempting to connect to both IPv4 and IPv6 at the same time preferring IPv6. Examples of the Happy Eyeballs stack are used in Chrome, Firefox, OS X, etc.
	
	
	\item \textbf{DNS64 and NAT64}: 
	\begin{definition}
		\textbf{NAT64} is a mechanism that allows IPv6 hosts to communicate with IPv4 servers. The NAT64 server is the endpoint for at least one IPv4 address and an IPv6 network segment of 64 bits. The IPv6 client embeds the IPv4 address with which it wishes to communicate using these bits and sends its packets to the resulting address. The NAT64 server then creates a NAT mapping between the IPv6 and IPv4 address allowing them to communicate.
		
		\textbf{DNS64} describes DNS server which when asked for AAAA records (IPv6), but only finds A (IPv4) records, synthesises the AAAA records from the A records. The first path points to an IPv6/IPv4 translator and the second part embeds the IPv4 address from the A record.
	\end{definition}
	

	\item \textbf{464XLAT}: Allows clients on IPv6-only networks to access IPv4-only services, such as Skype. Effectively, it is DNS64 + NAT64 + a shim layer on the host itself to offer IPv4 addresses to applications.
	
	\item DNS behaviour
	
\end{enumerate}
	
\subsubsection{Improving on IPv4 and IPv6}
\begin{enumerate}
	\item No accountability and anonymity on source address
	\item Packet header used at edge is the same as at the core
	\begin{definition}
		\textbf{Edge}: host tells network what service it wants
		
		\textbf{Core}: packet tells switch how to handle it
	\end{definition}
	\item No idea of who is responsible for packet delivery
\end{enumerate}

\section{Transport Layer}
The layer is at the end-hosts between the application and network layer.

\bigskip
\noindent
\textbf{Role of Transport Layer}
\begin{enumerate}
	\item Need a way to decide which packets go to which applications - used for communications between application processes at the host (implemented using ports) - multiplexing between application processes
	\item IP provides a weak service model (best-effort) where the packets can be corrupted, delayed, dropped, reordered and duplicated. There is no guidance on how much traffic to send and when and dealing with this would be tedious for application developers.
	\item Provide common end-to-end services for the application layer with (1) reliable, in-order data delivery and (2) paced data delivery with flow and congestion control
	\item TCP and UDP are the most common transport protocols: UDP is minimalist transport protocol, TCP is the more complex one ((1) offers reliable, in-order, byte-stream abstraction, (2) congestion control, (3) but no performance guarantees)
\end{enumerate}

\bigskip
\begin{definition}
	\textbf{Socket:} software abstraction by which an application process exchanges network messages with the transport layer in the operating system - can get both UDP and TCP sockets.
	
	\textbf{Port:} Transport layer (16 bit) identifier. The OS stores a mapping between sockets and ports (packet carries a source and destination port number in transport layer heading). For UDP ports, OS stores (local port, local IP address), for TCP ports, OS stores (local port, local IP, remote port, remote IP)
	\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/30.png} \end{figure}
	
	There is a separate 16-bit port address space for UDP and TCP. There are also \textbf{well-known ports (0-1023)} where everyone agrees which services run on the ports (ssh=22, http=80). Also, \textbf{Ephemeral ports (most from 1024-65535)} are dynamically selected as the source port for a client process.
\end{definition}

\subsection{User Datagram Protocol (UDP)}
UDP offers lightweight communications between processes and	avoids the overhead and delays of the ordered, reliable delivery. Has the following:
\begin{enumerate}
	\item Source port
	\item Destination port
	\item Checksum (value of 0 means don't verify checksum)
	\item length
	\item DATA
\end{enumerate}

\subsection{Principles of Reliable Data Transfer}
Internet default it best effort for transport - not perfectly reliable: packets can be corrupted, lost, delayed, reordered, duplicated.

\bigskip
\textbf{Provided functions}
\begin{enumerate}
	\item rdt-send: called from application. Pass data to deliver to receiver in upper layer
	\item rdt-rec: called by rdt to deliver data to upper
	\item udt-send: called by udt to transfer packet over unreliable channel to receiver
	\item udt-rcv: called when packet arrives on rcv side of channel
\end{enumerate}
\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/31.png} \end{figure}

\textbf{Process}: Incrementally develop sender, receiver sides of reliable data transfer protocol (rdt) - consider only unidirectional data transfer but control information will flow in both direction. Can use FSMs to specify sender and receiver.

\subsubsection{rdt1.0}
The underlying channel is perfectly reliable with (1) no bit errors and (2) no loss of packets. \textbf{Stop and Wait} - sender sends a message and waits for an acknowledge
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/32.png} \end{figure}

\subsubsection{rdt2}
\textbf{rdt2.0}:
The underlying channel may flip bits in the packet. Features are:
\begin{enumerate}
	\item Checksum to detect the bit errors
	\item Acknowledgements (ACKs): receiver explicitly tells sender that the packet received is ok
	\item Negative acknowledgements (NAKs): receiver explicitly tells sender that the packet had errors - the sender retransmits the packet on receipt of the NAK
\end{enumerate} 
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/33.png} \end{figure}

\begin{cons}
\textbf{Flaws}: If ACK / NAK corrupted - sender doesn't know what happened at receiver. Can't just retransmit as it could be a possible duplicate.
\end{cons}

\begin{pros}
\bigskip
\textbf{Handling duplicates:}
\begin{enumerate}
	\item Sender retransmits current packet if ACK/NAK is garbled
	\item Sender adds sequence number to each packet
	\item Receiver discards (doesn't deliver) duplicate packets
	\item Also, the sender sends one packet, then waits for the receiver response
\end{enumerate}
\end{pros}

\bigskip	
\noindent
\textbf{rdt2.1}:
Handles garbled ACKs/NAKs

\bigskip
\noindent
\textbf{Sender}
\begin{enumerate}
	\item Sequence number is added to the packet - two sequence numbers is enough since must wait before sending next packet
	\item Must check if received ACK/NAK is corrupted
	\item Twice as many states as the state must remember whether the current packet has a 0 or 1 as a sequence number
\end{enumerate}
\begin{figure}[H] \includegraphics[width=.55\textwidth, left] {./images/34.png} \end{figure}

\bigskip
\noindent
\textbf{Receiver:}
Must check if received packet is duplicate - state indicates whether 0 or 1 is the expected packet sequence number
\begin{figure}[H] \includegraphics[width=.7\textwidth, left] {./images/35.png} \end{figure}

\bigskip	
\noindent
\textbf{rdt2.2}:
Same functionality as rdt2.1, using ACKs only. Instead of NAK, the receiver sends an ACK for the last packet received okay. Therefore, the receiver must explicitly include the sequence number of the packet being acknowledged. A duplicate ACK at the sender results in the same action as a NAK (retransmit the current packet).

\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/36.png} \end{figure}

\subsubsection{rdt3.0}
Underlying channel can also lose packets. The new approach is that the sender waits a reasonable amount of time for an ACK and retransmits if no ACK is received in this time. If the packet (or ACK) is just delayed the retransmission will be duplicate which the sequence number will handle. The receiver must therefore specify the sequence number of the packet being acknowledged. Therefore, \textbf{require a countdown timer}.

\bigskip
\noindent
\textbf{Sender}: Deal with loss using \textbf{timer-driven loss detection} - we set a timer when the packet is sent and retransmit the packet on timeout
\begin{figure}[H] \includegraphics[width=.65\textwidth, left] {./images/37.png} \end{figure}

\begin{cons}
\noindent
\textbf{Performance}: is very bad (especially if t << RTT) - with 1Gbps link, 15ms propagation delay and an 8kb packet:

\begin{equation}\label{key}
d_{trans} = \frac{L}{R} = \frac{8kb}{10^9 bps} = 8ms
\end{equation}

\begin{equation}\label{key}
Utilisation_{sender} = \frac{\frac{L}{R}}{RTT + \frac{L}{R}} = \frac{0.008}{30.008} = 0.00027
\end{equation}

\noindent
The network protocol limits the use of physical resources.
\end{cons}

\subsection{Packet-Window (Pipelined) Protocols}
\begin{definition}
	\textbf{Pipelining}: sender allows multiple in-flight, yet to be acknowledged packets. This means that the range of sequence numbers must be increased with buffering at the sender and/or receiver.
	
	\bigskip
	\noindent
	\textbf{Window}: set of adjacent sequence numbers. The size of the set is the \textbf{window size} - n. The general idea is that:
	\begin{enumerate}
		\item Sender can send packets in its window
		\item Receiver can accept packets in its window
		\item Window of acceptable packets slides on successful reception / acknowledgements
	\end{enumerate}
\end{definition}

\bigskip
\noindent
\textbf{Sliding window} means the sender sends lots of packets and the window moves over until the last acknowledged packet that it had sent. Options for the acknowledgements:
\begin{enumerate}
	\item \textbf{Cumulative ACKs:} ACK carries next in-order sequence number that the receiver expects, therefore can acknowledge a number of packets at the same time. 
	\begin{itemize}
		\item Therefore, if a packet isn't received, it sends an ACK for the missing packet and since the sender knows it has sent it a certain period ago (sets a timer), it retransmits. 
		\item \textbf{Go-Back-N}: Sender transmits up to n unacknowledged packets, receiver only accepts packets in order and discards out-of-order packets.
		\item Sender sets a timer for the first outstanding acknowledge, if there is a time-out then retransmit A+1, ..., A+n
		
		\bigskip
		\noindent
		\textbf{Sender}
		\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/39.png} \end{figure}
		
		\bigskip
		\noindent
		\textbf{Receiver}: always send an ACK for correctly-received packet with the highest in-order sequence number and discard any out-of-order packets
		\begin{figure}[H] \includegraphics[width=.7\textwidth, left] {./images/40.png} \end{figure}	
	\end{itemize}

	\item \textbf{Selective ACKs:} ACK individually acknowledges correctly received packets - offers more precise information but requires more complicated book-keeping.
	\begin{itemize}
		\item \textbf{Selective Repeat:} transmit up to n unacknowledged packets - sender ACKs each packet it receives. Then, the sender retransmits each packet that times out - need a timer per packet. 
	\end{itemize}
\end{enumerate}

\bigskip
\noindent
With sliding windows, it is possible to fully utilise a link, provided the window size is large enough

\begin{equation}\label{key}
throughput \approx \frac{n}{RTT}
\end{equation}

\subsection{TCP}
\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/41.png} \end{figure}	

\begin{itemize}
	\item \textit{HdrLen is the number of 4-byte words in the TCP header; 5 = no options}
	\item \textit{Urgent pointer is used with the \textbf{URG} flag to indicate if there is urgent data}
	\item \textit{Flags}: \textit{SYN}, \textit{ACK}, \textit{FIN}, \textit{RST}, \textit{PSH}, \textit{URG}
\end{itemize}

\begin{enumerate}
	\item Segmentation
	\begin{itemize}
		\item TCP Segment is an IP packet (with IP data: TCP Data segment, TCP header and the IP header) which is no bigger than the Maximum Transmission Unit. The TCP Data segment is no more than the Maximum Segment Size ie:
		\begin{equation}\label{key}
		MSS = MTU - (IP \; Header) - (TCP \; Header)
		\end{equation}
	\end{itemize}

	\item Sequence numbers are starting byte offsets in this segment = initial sequence number + k (offset)

	\item Sender and receiver maintain sliding window
	\item Receiver sends cumulative acknowledgements
	
	\begin{enumerate}
		\item When receiver receives packet, if all data prior to this received goto (2), else goto (3)
		\item \begin{equation}\label{key}
		ACK \;  acknowledged \; number = next \; expected \; byte = seqno + length(dataOfLastPacket)
		\end{equation}
		\item Otherwise acknowledge 1 + highest in-order byte, even if this has been acknowledged before
	\end{enumerate}

	\item Sender maintains a single timer
	\item Receivers don't drop out-of-sequence packets - these are buffered instead
	\item Introduces \textbf{fast retransmit} - uses duplicate ACKs to trigger early retransmission. These duplicated ACKs are a sign of an isolated loss therefore trigger a resend upon receiving a constant number of duplicate ACKs, TCP uses 3.
	\item Introduces time-out estimation algorithms - if sender hasn't received an ACK by time-out, retransmit the first packet in the window. If this time-out is too long, it is inefficient, however, if it is too short then there are duplicate packets which get sent. We therefore make the time-out proportional to the RTT.
	
	\bigskip
	\noindent
	\textbf{Estimating RTT:} 
	\begin{equation}\label{key}
	Sample RTT = ACKReceivedTime - SendPacketTime
	\end{equation} 
	\begin{equation}\label{key}
	Estimated RTT = \alpha \times (Estimated RTT) + (1 - \alpha) \times (Sample RTT) \; where \; 0 < \alpha \leq 1
	\end{equation}
	\item Has a checksum

\end{enumerate}

\bigskip
\noindent
\begin{cons}
\textbf{Ambiguous Measurements}: How to differentiate between the real ACK and the ACK of the retransmitted packet?
\end{cons}

\begin{pros}
\bigskip
(1) Fix using the \textbf{Karn/Partridge Algorithm}:
\begin{enumerate}
	\item Measure SampleRTT only for original transmissions, once a segment has been retransmitted, don't use it for any further measurements - compute EstimatedRTT using $\alpha$ = 0.875
	\item Time-out value (RTO) = 2 $\times$ EstimatedRTT - uses \textbf{exponential backoff} (up to maximum $\geq$ 60 seconds). Every time new measurement comes in (successful original transmissions), collapse RTO to 2 $\times$ EstimatedRTT
	
\end{enumerate}


\bigskip
(2) Fix using the \textbf{Jacobson/Karels Algorithm}: Need to better capture the variability in the RTT by directly measuring the deviation
\begin{equation}\label{key}
Deviation = | SampleRTT - EstimatedRTT |
\end{equation}
\begin{equation}\label{key}
EstimatedDeviation: \; exponential \; average \; of \; Deviation
\end{equation}
\begin{equation}\label{key}
RTO = EstimatedRTT + 4 \times EstimatedDeviation
\end{equation}

\end{pros}

\subsubsection{Connection Establishment}
\textbf{Initial Sequence Number:} Cannot use ISN = 0 as the IP addresses and port numbers uniquely identify a connection however the port numbers do get used again when the old packet is still in flight. Therefore, TCP needs to change the ISN with the hosts exchanging the ISNs when they establish a connection.

\begin{enumerate}
	\item Host A sends a \textbf{SYN: synchronize sequence numbers} to host B
	\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/42.png} \end{figure}	
	
	\item Host B returns a SYN acknowledgement (SYN ACK)
	\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/43.png} \end{figure}	
	
	\item Host A sends an ACK to acknowledge the SYN ACK 
	\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/44.png} \end{figure}	
	
	\begin{figure}[H] \includegraphics[width=.4\textwidth, left] {./images/45.png} \end{figure}	
\end{enumerate}

\bigskip
\begin{cons}
If SYN packet gets lost: 
\begin{enumerate}
	\item Packet is lost inside the network or server discards the packet
	\item Eventually, no SYN-ACK arrives - retransmits the SYN if needed
	\item But, TCP sender has no idea how to set the timer - no idea how far away the receiver is. Instead, have to guess a reasonable length of time - default is 3 seconds or 6 seconds.
\end{enumerate}
\end{cons}

\subsubsection{Tearing Down the Connection}
Host A sends FIN to B and B acknowledges to half-close, and then Host B must send FIN to A followed by an acknowledge from B. Instead B can set FIN with their ack of A's FIN in order to close on both sides.

\bigskip
\textbf{Abrupt Termination: }A sends a RESET (RST) to B, for example when an application process on A crashes. That is it, therefore B does not need to acknowledge the RST (if it is not delivered reliably, and B sends more data back, then A will send another RST).
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/46.png} \end{figure}	
\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/47.png} \end{figure}	


\subsubsection{Windows}
\begin{definition}
	\textbf{Congestion Window}: How many bytes can be sent without overflowing routers - computed by the sender.
	
	\noindent
	\textbf{Flow Control Window}: How many bytes can be sent without overflowing receiver's buffers - determined by the receiver and reported to sender
\end{definition}

\bigskip
\textbf{Sender Side Window} = minimum(Congestion Window, Advertised Window)

\bigskip
\noindent
Can generally assume that the Advertised Window >> Congestion Window

\subsubsection{Flow Control (Advertised Window)}
Receiver uses an Advertised Window (W) to prevent the sender from overflowing the window. Receiver indicates the value of W in ACKs, while the sender limits the number of bytes in flight $\leq$ W where:
\begin{equation}\label{key}
W = Buffer \; Size - (Last \; Byte \; Received - Last \; Byte \; Read)
\end{equation}

\bigskip
\textbf{Sliding Window with Flow Control}
\begin{definition}
	\textbf{Flow Control}: Adjusting sending rate to keep from overwhelming a slow receiver
\end{definition}
\begin{itemize}
	\item \textbf{Sender:} (1) Window advances when new data is acknowledged and (2) the Sender can send no faster than $\frac{W}{RTT}$ bytes/sec. 
	\item \textbf{Receiver:} (1) Window advances as receiving process consumes data and (2) advertises to the sender where the receiver window currently ends - sender agrees not to exceed this amount.
\end{itemize}


\subsubsection{Congestion Control}
\begin{definition}
\textbf{Congestion Control}: adjusting the sending rate to keep from overloading the network - global resource allocation involving many flows, many links and complex global dynamics.
\end{definition}

\bigskip
Statistical multiplexing (if two packets arrive at the same time) leads to congestion - if many packets arrive in a short period of time, then the router cannot keep up with the arriving traffic, delays traffic and the buffer may eventually overflow. This is very realistic as the internet traffic is bursty.

The general issue is balancing utilisation versus delay and loss. TCP's approach is to have the \textbf{end hosts adjusting the sending rate based on implicit feedback from the network}


\bigskip
\noindent
\textbf{Issues}
\begin{enumerate}
	\item \textbf{Discovering available bandwidth} - detecting congestion
	\item Adjusting to variations in bandwidth
	\item Sharing bandwidth between flows
	\begin{enumerate}
		\item Adjust total sending rate to match bandwidth
		\item Allocation of bandwidth between flows
	\end{enumerate}
\end{enumerate}

\bigskip
\textbf{History: TCP in 1980s} - sending rate is only limited by flow control and packet drops lead to senders retransmitting a full window's worth of packets. This led to a congestion collapse in October 1986

\bigskip
\textbf{Jacobson's Approach}: Extend TCP's existing window-based protocol, but vary the window size in response to congestion
\begin{pros}
	only requires a few lines of code added to TCP implementations and no upgrades to routers or applications. It is a pragmatic solution and has been extensively improved on since then - is making a comeback in datacenter environments
\end{pros}

\bigskip
\textbf{Single Flow View}
\begin{figure}[H] \includegraphics[width=.35\textwidth, left] {./images/48.png} \end{figure}	
\begin{definition}
	\textbf{Knee}: The point after which the (1) throughput increases slowly and (2) delay increases fast
	
	\textbf{Cliff}: The point after which (1) throughput starts to drop to zero (congestion collapse) and (2) delay approaches infinity
\end{definition}

\bigskip
\noindent
\textbf{General Approaches}
\begin{enumerate}
	\item \textbf{Send without care} - leads to many packet drops
	\item \textbf{Reservations}: Pre-arrange bandwidth allocations
	
	\begin{pros}
		Requires negotiation before sending packets
	\end{pros}
	
	\begin{cons}
		Low utilisation
	\end{cons}
	
	\item \textbf{Pricing}: don't drop packets for the high-bidders and let them be dropped for low-bidders, however it requires some kind of payment model.
	
	\item \textbf{Dynamic Adjustment}: Hosts (1) probe the network, (2) infer the level congestion and (3) adjust
	\begin{itemize}
		\item The network (1) reports congestion level to the hosts and (2) the hosts adjust
		\begin{pros}
			\item This is a combination of the above, simple to implement
		\end{pros}
		
		\begin{cons}
			\item Suboptimal, messy dynamics
		\end{cons}
	\end{itemize}
	
	\item 2-4 all are usable - generality of dynamic adjustment has proven powerful - doesn't presume business model, traffic characteristics, application requirements, but does assume good citizenship
\end{enumerate}

\bigskip
\noindent
\textbf{Detecting Congestion}
\begin{enumerate}
	\item Routers tell end hosts they're congested 
	\item Detect packet loss - TCP already has to detect this however, there could also be non-congestive loss (for example through checksum errors)
	
	\subitem Multiple duplicate ACKs - this is an isolated loss
	\subitem No ACK after certain time interval (time-out) - more serious - must have suffered several losses
	\subitem Therefore, adjust the rate differently for each case
\end{enumerate} 

\bigskip
\noindent
\textbf{Rate Adjustment}:
Idea is that if receive ACK, increase the rate. Upon detection of a loss, you have to decrease the rate. How we increase / decrease the rate depends on what phase of congestion control we are in
\begin{enumerate}
	\item Discovering available bottleneck bandwidth - \textbf{Slow Start}
	\begin{enumerate}
		\item \textbf{Goal:} start slow \textit{(for safety)} but ramp up quickly \textit{(for efficiency)}
		\item Start with small congestion window = 1, therefore initial sending rate is $\frac{Maximum Segment Size}{RTT}$
		\item Double the congestion window for each RTT with no loss
	\end{enumerate}
	\item Adjusting to bandwidth variations
	\begin{enumerate}
		\item \textbf{Goal:} Track variations in this available bandwidth, oscillating around its current value \textbf{through repeated probing} (rate increase) and \textbf{backoff} (rate decrease)
		\item TCP uses Additive Increase Multiplicative Decrease (AIMD)
		\begin{enumerate}
			\item \textbf{Additive Increase:} window grows by one MSS for every RTT with no loss, therefore for each ACK, 
			\begin{equation}\label{key}
			Congestion Window = Congestion Window + \frac{1}{Congestion Window}
			\end{equation}
			
			\item \textbf{Multiplicative Decrease:} On loss of a packet, divide the congestion window in half
			\begin{equation}\label{key}
			Congestion Window = \frac{Congestion Window}{2}
			\end{equation}
		\end{enumerate}
	\end{enumerate}

	\item Moving from Slow Start to AIMD (add slow start threshold - \textbf{ssthresh}): It is initialised to a large value and on a time-out, ssthresh is set to $\frac{Congestion Window (CWND)}{2}$
	
	\item \textbf{Fast Recovery:} Deals with problem of congestion avoidance being too slow in recovering from an isolated loss by granting the sender temporary credit for each duplicate ACK so as to keep the packets in flight.
	\begin{itemize}
		\item If dupACKcount = x: ssthresh = $\frac{cwnd}{2}$, cwnd = ssthresh + x. 
		\item While in fast recovery, cwnd++ for each additional duplicate ACK
		\item Exit fast recovery after receiving a new ACK - we then set cwnd = ssthresh
	\end{itemize}

\end{enumerate}

\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/49.png} \end{figure}	

\subsubsection{TCP Flavours}
\begin{enumerate}
	\item \textbf{TCP-Tahoe}: cwnd = 1 on triple duplicate acknowledge
	\item \textbf{TCP-Reno}: cwnd = 1 on time-out $\&$ cwnd = $\frac{cwnd}{2}$
	\item \textbf{TCP-newReno}: TCP-Reno and improved fast recovery - this is the default
	\item \textbf{TCP-SACK}: incorporates selective acknowledgements
\end{enumerate}

\begin{cons}
	\noindent
	Need to be able to deal with people working with different algorithms.
\end{cons}

\begin{figure}[H] \includegraphics[width=.55\textwidth, left] {./images/50.png} \end{figure}
\begin{equation}\label{key}
Packet \; drop \; rate \; p = \frac{1}{A} \; where \; A = \frac{3}{8}W_{max}^{2}
\end{equation}
\begin{equation}\label{key}
Throughput, \; B = \frac{A}{(\frac{W_{max}}{2})RTT} = \sqrt{\frac{3}{2}} \frac{1}{RTT\sqrt{p}}
\end{equation}

\bigskip
\textbf{Implications}
\begin{itemize}
	\item Flows throughput ~ $\frac{1}{RTT}$
	\begin{cons}
	\item TCP is unfair in the face of heterogeneous RTTs
	\item Packet drop rate is not practical for high speed TCP connections
	\item \textbf{Rate-based Congestion Control}: TCP throughput is choppy - swings between W/2 and W - some apps would prefer sending at a steady rate instead. 
	\end{cons}
	\begin{pros}
	\subitem \textbf{Solution is Equation-Based Congestion Control} involves ditch TCP rules and just follow equation - (1) measure the drop percentage p and (2) set the rate accordingly
	\end{pros}
\end{itemize}

\subsubsection{Adapting TCP to High Speed}
\begin{enumerate}
	\item Floyd '03: Once speed is past some threshold, change the equation to p$^{-0.8}$ rather than p$^{-0.5}$ (/ increase the congestion window faster once past threshold)
	\item Let additive constant in AIMD depend on the congestion window
	\item Multiple simultaneous connections
	\item Router-assisted approaches
\end{enumerate}

\subsubsection{TCP Problems and Solutions}
\begin{enumerate}
\begin{pros}
	\item Routers tell endpoints if they are congested
	\begin{enumerate}
		\begin{cons}
		\item Misled by non-congestion losses
		\item Fills up queues leading to high delays
		\end{cons}
	\end{enumerate}
	\item Routers tell endpoints what rate to send at
	\begin{enumerate}
		\begin{cons}
			\item Short flows complete before discovering available capacity
			\item AIMD is impractical for high speed links
			\item Sawtooth discovery is too choppy for some applications
			\item Unfair under heterogeneous RTTs
			\item Tight coupling with reliability mechanisms
		\end{cons}
	\end{enumerate}
	\item Routers enforce fair sharing
	\begin{enumerate}
		\begin{cons}
			\item End-hosts can cheat
		\end{cons}
	\end{enumerate}
\end{pros}
\end{enumerate}


\subsubsection{Router-Assisted Congestion Control}
\textbf{Fair Queueing}: doesn't eliminate congestion - just manages it.
For each packet, (1) compute the time at which the last bit of a packet would have left the router if flows are served bit-by-bit and then (2) serve packets in the increasing order of their deadlines.

\bigskip
\textbf{Weighted Fair Queuing}: assign different flows different shares - effectively an implementation of round-robin generalized to the case where not all packets are equally sized.

\bigskip
\textbf{Comparison with a FIFO}
\begin{itemize}
\begin{pros}
	\item \textbf{Isolation}: cheating flows do not benefit
	\item Bandwidth share do not depend on RTT
	\item Flows can pick any rate adjustment scheme they want
\end{pros}
\begin{cons}
	\item More complex: (1) per flow state (a queue) and (2) additional per-packet book-keeping
\end{cons}
\end{itemize}

\textbf{Explicit Congestion Control}: method of congested routers setting a single bit in a packet header to indicate congestion. If the data packet has the bit set, then the ACK also has the ECN bit set. There are a lot of options for what happens when routers set the bit - \textit{trade-off between link utilization and packet delay}. In general though, the end-host reacts as if it saw a drop - therefore halve the congestion window.

\begin{enumerate}
\begin{pros}
	\item Doesn't confuse corruption with congestion
	\item Can serve as an early indicator of congestion to avoid delays
	\item Easier to incrementally deploy - defined as an extension to TCP/IP in RFC 3168 (uses diffserv bits in the IP header)
\end{pros}
\end{enumerate}

\section{Network Applications}
\subsection{Client-Server Paradigm}
There exists a server which is:
\begin{enumerate}
\item Always on
\item Permanent IP address
\item Server farms for scaling
\end{enumerate}

\noindent
and \textbf{multiple} clients which:
\begin{enumerate}
    \item Communicate with the server intermittently
    \item Have dynamic IP addresses
    \item Do not communicate directly with one another
\end{enumerate}

\subsection{Infrastructure Services}
\textbf{Idea}: 
\begin{enumerate}
    \item Addresses of websites can change
    \item A single name can map to multiple IP addresses for (1) load balancing and (2) reducing latency through localisation
    \item A single address can be mapped to by multiple names (aliases), for example the mnemonic stable name and the dynamic canonical name (actual name of the host)
\end{enumerate}

This was originally done using a single per-host file (\textit{/etc/hosts)} but this had to be downloaded regularly and clearly just doesn't work. Led to the creation of a single distributed hierarchical system: \textbf{two intertwined hierarchies: (1) Infrastructure - DNS servers, (2) Naming structure}

\subsubsection{Domain Name System}
\textbf{Hierarchy}
\begin{enumerate}
    \item Root - location is hardwired into the other servers
    
    The main issue with the root is making it scale effectively - this is done by having 13 main root servers located across the globe which are replicated using \textbf{any-casting}
    \begin{definition}
    \subitem Localized routing for addresses
    \end{definition}
        
    \item Top-level Domain Servers (.com, .uk) - these are managed professionally
    \item Authoritative DNS servers - can be maintained locally or by a service provider
    \item Arpanet services can also be provided externally to this hierarchy
\end{enumerate}
\begin{figure}[H] \includegraphics[width=.55\textwidth, left] {./images/51.png} \end{figure}

\bigskip
\subsubsection{Using DNS}
Components:
\begin{enumerate}
    \item Local DNS servers - near the end-hosts that use it. Local host configured with a local server (\textit{/etc/resolv.conf)} or learn the server with DHCP
    \item Resolver software on hosts
    \begin{enumerate}
        \item Extract the server name (from the URL)
        \item Do a gethostname() to trigger the resolver code
    \end{enumerate}
\end{enumerate}

\bigskip
\noindent
\textbf{Resolution}: 
\begin{enumerate}
    \item \textbf{Iterated Query}: Host query travels up the hierarchy of DNS servers with each layer responding with the address of who to ask next - next layer up the hierarchy.
    \item \textbf{Recursive}: Puts the burden of name resolution on the contacted name server - has a possibility of dealing with heavy load a little bit worse
    \item \textbf{Hybrid Case}: Do recursive query up one level of the hierarchy and then iterative query from then on through the hierarchy.
\end{enumerate}

\subsubsection{DNS Caching}
Since top-level servers very rarely change therefore local DNS server often caches the information. Works by the DNS server caching the responses to queries with the response including a \textbf{TTL} which gets deleted after TTL expires

\bigskip
\noindent
\textbf{Negative Caching}: Remember things that don't work - for example in misspellings, these can otherwise take a long time. This is optional and is not widely implemented however.

\subsubsection{DNS Reliability}
\begin{enumerate}
\begin{pros}
    \item DNS servers replicated - queries can be load-balanced between replicas
\end{pros}
\begin{cons}
    \item UDP used for queries - spec supports TCP but this is not always implemented
    \begin{itemize}
        \item Exponential backoff when retrying the same server
        \item Use the same identifier for all queries - don't care which server responds
    \end{itemize}
\end{cons}
\end{enumerate}

\subsubsection{DNS Security}
\begin{enumerate}
    \item No way to verify the answers
    \item Very liable to spoofing or a man in the middle attack - eg on a public WiFi, the controller of the WiFi network controls the DNS
    \item Can also have a cache poisoning attack with additional records on the caches of DNS servers
    \item Also server vulnerabilities
\end{enumerate}

\bigskip
\noindent
\textbf{DNSSEC}
\begin{definition}
\noindent
Provides message authentication and integrity verification through cryptographic signatures:
\end{definition}

\begin{enumerate}
    \item People know who provided the signature
    \item No modifications between signing and validations
\end{enumerate}

\bigskip
\begin{cons}
\noindent
\textbf{But}
\begin{enumerate}
    \item No authorization
    \item No confidentiality
    \item No protection against DDOS
\end{enumerate}
\end{cons}

\bigskip
\noindent
There is an issue in scaling the key signing and key distribution which is solved by using the DNS to distribute the keys.
\begin{itemize}
    \item Use one trusted key to establish authenticity of other keys
    \item Builds the chain of trust from the root down - parents need to sign the keys of their children
    \item In practise, only the root key is really needed as the parents can always delegate security to the child
\end{itemize}

\subsection{Traditional Applications}
\subsubsection{Web}
Web applications (YouTube, Twitter, Instagram, etc) are very successful because of the ability to self-publish which is easy, independent and free. People aren't necessarily interested in technical perfection and instead want to find something neat.

\bigskip
\noindent
\textbf{Components}
\begin{itemize}
    \item \textbf{Infrastructure}:
    \begin{itemize}
        \item Clients
        \item Servers
        \item Proxies
    \end{itemize}
    \item \textbf{Content}:
    \begin{itemize}
        \item Individual objects (files, etc)
        \item Web sites (collection of objects)
    \end{itemize}
    \item \textbf{Implementation}:
    \begin{itemize}
        \item HyperText Markup Language (HTML): web page is made up of a base HTML file and referenced objects (images, etc). It serves a number of functions: (1) Formatting text, (2) Referencing images, (3) Embedding hyperlinks
        \bigskip
        \item \textbf{URL}: naming content -  \textbf{Syntax} is protocol://hostname[:port]/directorypath/resource
        \begin{itemize}
            \item \textbf{Protocol}: http, ftp, https, etc.
            \item \textbf{Hostname}: DNS name, IP address
            \item \textbf{Port}: Defaults to the protocol's standard port
            \item \textbf{Directory Path}: Reflects the file system
            \item \textbf{Resource}: Identifies the desired resource - can also extend to program executions, passing relevant data
        \end{itemize}
        \bigskip
        \item \textbf{HTTP}: request-response protocol

    \end{itemize}
\end{itemize}

\subsubsection{HTTP}
\begin{itemize}
            \item There is a reliance on a global namespace
            \item Resource meta-data
            \item Stateless - each request-response is treated independently and servers are not required to retain state
            \begin{itemize}
                \begin{pros}
                    \item Failure handling is easier
                    \item Can handle higher rate of requests
                    \item Order of requests doesn't matter - makes a lot of things easier
                \end{pros}
                \begin{cons}
                    \item Some applications need persistent state - for example needing to uniquely identify the user or store temporary information - fixed using \textbf{cookies}
                \end{cons}
            \end{itemize}
            
            \bigskip
            \noindent
            \textbf{Cookies}: client-side state maintenance where (1) the client stores small state on behalf of the server and (2) sends the sate in future requests to the server. This can be used to provide authentication. 
        \end{itemize}
        
        \bigskip
        \textbf{Request}: composed of (1) Request line (GET, POST, etc), (2) Header lines and (3) Carriage return which indicates end of message
        
        \textbf{Response}: composed of (1) Status line (protocol, status code, status phrase), (2) Header lines, (3) Requested data of multiple types
        \begin{enumerate}
            \item Files
            \item Generate the response dynamically if the URL triggers a program on the server and the server runs a program and sends the output to the client
            \item Return meta-data with no body - with the 'response' in the header
            \begin{definition}
            \subitem Information about a resource, stored as a separate entity, for example:
            \begin{itemize}
                \item Size of resource, last modification time, type of content
            \end{itemize}
            \end{definition}
        \end{enumerate}
        
        \bigskip
        \noindent
        \textbf{Steps}
        \begin{enumerate}
            \item HTTP Client initiates TCP connection to server
            \item Client sends HTTP request to server
            \item HTTP Server responds to request
            \item Client receives response and terminates connection
            \item TCP connection termination exchange
        \end{enumerate}
        \begin{cons}
        This takes a long time for a single request - at least 6 RTTs
        \end{cons}
        
        \bigskip
        \noindent
        \textbf{Performance}: Often slow as to retrieve multiple objects that are often required for a single web page, you have to request them one at a time. These can be fixed in a few ways:
        \begin{enumerate}
            \item \textbf{Concurrent Requests and Responses}: Use multiple connections in parallel but this does not necessarily maintain the order of responses - this is hard for the network to do.
            \item \textbf{Pipelined Requests and Responses}: Batch requests and responses, this reduces the connection overhead (a single TCP connection) and maintains the order of responses. 
            
            \begin{figure}[H] \includegraphics[width=.35\textwidth, center] {./images/52.png}\end{figure}
            
            \item \textbf{Persistent Connections}: Enables multiple transfers per connection where the same TCP connection exists across multiple requests including transfers subsequent to the current page. Then, the client or server can tear down the connection.
            
            \begin{pros}
            \begin{itemize}
                \item Avoid overhead of connection set-up and tear-down
                \item Allow TCP to learn more accurate RTT estimate
                \item Allow TCP congestion window to increase
            \end{itemize}
            \end{pros}
            
            \item \textbf{Caching}: Reduces the latency for clients transferring the same information - exploits the \textit{locality of reference}. 
            \begin{itemize}
                \item It works using a modifier to the GET requests adding 'If-modified-since' which returns '304 not modified' if the resource has not been modified since the specified time or a '200 ok' with latest version otherwise
                \item The response header contains: (1) Expires - how long it is safe to cache the resource, (2) No-cache - ignore all caches, therefore always get resource directly from the server
            \end{itemize}
            
            \textbf{Reverse Proxies}: Cache the documents close to the server decreasing the server load - typically done by the content providers. However, this only works for static content.
            
            \bigskip
            \textbf{Forward Proxies}: Cache documents close to the clients - reduce the network traffic and lowest latency. Done by ISPs and corporate LANs.
            
            \begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/53.png}\end{figure}
            
            \textbf{Content Distribution Networks}: Integrate forward and reverse caching with a single overlay network administered by one entity. 
            \begin{enumerate}
                \item Provide document caching: \textbf{Pull} and \textbf{Push}
                \item Do some processing: (1) Handle dynamic web pages, (2) Transcoding and (3) Security functions
            \end{enumerate}
            \begin{figure}[H] \includegraphics[width=.65\textwidth, left] {./images/54.png}\end{figure}
            
            \begin{example}
            \textbf{Akamai}: Creates new domain names for each client content provider. The DNS servers are authoritative for the new domains. The client content provider modifies its content to that embedded URLs reference the new domains and the requests are now sent to CDN's infrastructure.
            
            \begin{enumerate}
                \item CDN using DNS - DNS has information on loading / distribution / location
                \item CDN using anycast - same address from DNS name but local routes
                \item CDN based on rewriting HTML URLs
            \end{enumerate}
            \end{example}
            
        \end{enumerate}
        
        \bigskip
        \noindent
        \textbf{Evolution}
        \begin{itemize}
            \item \textbf{1.0}: One object per TCP therefore simple but slow
            \item \textbf{Parallel connections}: multiple TCP, one object each - it wastes bandwidth, may be server limited and out of order
            \item \textbf{1.1 pipelining}: aggregate retrieval time: ordered, multiple objects sharing single TCP
            \item \textbf{1.1 persistent}: lower overhead in time but increases overhead the ends - tough to know when to close the connection
        \end{itemize}
        
        \begin{example}
        \bigskip
        \noindent
        \textbf{Getting n small objects - where the time is dominated by the latency}
        \begin{itemize}
            \item One-at-a-time: $\approx$ 2n RTT
            \item Persistent: $\approx$ (n+1) RTT
            \item M concurrent: $\approx$ 2($\frac{n}{m}$) RTT
            \item Pipelined: $\approx$ 2 RTT
            \item Pipelined / Persistent: $\approx$ 2 RTT first time, RTT later
        \end{itemize}
        \end{example}
        
        \begin{example}
        \bigskip
        \noindent
        \textbf{Getting n large objects - where the time is dominated by bandwidth}
        \begin{itemize}
            \item One-at-a-time: $\approx$ nF/B
            \item M concurrent: $\approx$ $\frac{n}{m}$ $\frac{F}{B}$
            \item Pipelined and / or persistent: $\approx$ n$\frac{F}{B}$ - therefore the only thing that helps is getting more bandwidth
        \end{itemize}
        \end{example}

\subsubsection{Hosting}
\textbf{Multiple Sites Per Machine}: Problem is knowing which website you're trying to reach
\begin{pros}
\begin{enumerate}
    \item Multiple server processes on the same machine - separate port on each server
    \item Include site name in HTTP request - 'Host' header - this is a required header with HTTP/1.1
\end{enumerate}
\end{pros}

\bigskip
\noindent
\textbf{Replication}: How to direct client to particular replica of a popular website in order to (1) balance loads across server replicas and (2) pair clients with nearby servers.
\begin{enumerate}
    \item Single Location - single IP address, multiple machines: effectively just have a load balancer running on the IP address forwarding packets to multiple machines. \textit{Must ensure that all packets from a single TCP connection go to the same replica machine.}
    \item Several Locations: Configure DNS server to return closest address
\end{enumerate}

\subsubsection{After HTTP/1.1}
\textbf{SPDY and HTTP/2}
\begin{enumerate}
    \item \textbf{Binary protocol} which is (1) more efficient to parse, (2) more efficient on the wire, (3) much less error prone than textual protocols
    \item \textbf{Multiplexing} is interleaved, therefore requests and responses are batched
    \item \textbf{Server Push} proactively pushes critical information to the clients that it will need, for example style sheets
    \item One single TCP connection instead of multiple
    \item Header compression
    \begin{cons}
    \item Head of line blocking - line of packets is blocked on the packet which is first in the queue
    \end{cons}
\end{enumerate}

\bigskip
\noindent
\textbf{Quick UDP Internet Connections (QUIC)}

\noindent
\textbf{Aim:} Combine speed of UDP protocol with TCP's reliability - hard to make changes to TCP and therefore it is faster to implement new protocols on top of UDP. Shaves a second off Google Search page load time for slowest 1$\%$ of connections - and 30$\%$ fewer rebuffers when watching videos over QUIC

\bigskip
\noindent
\textbf{Features}
\begin{enumerate}
    \item Reliable transport over UDP (normally offers a fire and forget service which is quick but offers no reliability, this has to be built on top of UDP)
    \item Uses Forward Error Correction (FEC)
    \item Cryptography by default
    \begin{enumerate}
        \item Has a three-way handshaking process using TLS (Transport Layer Security), which provides authentication of the end-points as well as negotiation of cryptographic 
        \item Packets are individually encrypted - this also makes the system faster
    \end{enumerate}
    \item Restartable connections
    \item \textbf{Better support for multiplexing}: Different HTTP streams can in turn be mapped to different QUIC transport stream, but, while they still share the same QUIC connection so no additional handshakes are required and congestion state is shared, the QUIC streams are delivered independently so packet loss affecting one stream doesn't affect others
    \begin{cons}
    \item No guarantee of ordering of packets
    \end{cons}
\end{enumerate}


\subsection{Multimedia Applications - Session Interface Protocol (SIP)}
SIP is used for VoIP, bringing telephony to the internet including: (1) User location, (2) User availability, (3) User capabilities, (4) Session setup, (5) Session management

\bigskip
\noindent
\textbf{H.323}: Another similar standard written International Telecommunication Union - protocol is known for its complexity - SIP is not much better...

\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/55.png}\end{figure}

\noindent
\textbf{Resource Allocation for Multimedia Applications}: Need to know how to allocate resources specifically for multimedia applications for example giving the packet more priority. We do admission control using session control protocol. However, a standard for resource allocation for multimedia applications has never been specifically defined. However, it does happen sometimes inside single institutions. 

\begin{figure}[H] \includegraphics[width=.6\textwidth, left] {./images/56.png}\end{figure}

In aDSL and CABLE, the phone company controls the multiplexing on the line and throughout their network.

\subsection{Peer to Peer Networks}
\begin{definition}
No always-on server, instead there are arbitrary end systems that directly communicate. The peers are intermittently connected and change IP addresses frequently.
\end{definition}

\subsubsection{File Distribution}
\begin{figure}[H] \includegraphics[width=.5\textwidth, left] {./images/57.png}\end{figure}

\textbf{Time to distribute F to N clients using client/server approach}:
\begin{itemize}
    \item Server sequentially sends N copies = $\frac{NF}{u_{s}}$
    \item Client i takes $\frac{F}{d_{i}}$ time to download

    \begin{equation}\label{key}
    d_{cs} = max(\frac{NF}{u_{s}}, \frac{F}{min(d_{i})_{i}})
	\end{equation}
	
	\item This increases linearly in N for large N
\end{itemize}

\noindent
\textbf{File distribution time using P2P}:
\begin{itemize}
    \item Server sends one copy = $\frac{F}{u_{s}}$
    \item Client i takes $\frac{F}{d_{i}}$ to download
    \item NF bits must be downloaded - fastest possible upload rate = $u_{s}$ + $\sum$ $u_{i}$

    \begin{equation}\label{key}
	d_{P2P} = max(\frac{F}{u_{s}}, \frac{F}{min(d_{i})}, \frac{NF_{i}}{u_{s}} + \sum u_{i})
	\end{equation}
\end{itemize}

While they start off being similarly fast, as N increases, the distribution time for P2P increases less quickly than the linear relationship of the Client-Server model.

\subsubsection{Distributed Hash Table}
Effectively is a distributed Peer-to-Peer database, containing (key, value) store which can have items inserted and values returned based on the key

\bigskip
\noindent
\textbf{Process}:
\begin{enumerate}
    \item Each peer given integer identifier in range [0, 2$^{n}$-1] st each identifier can be represented by n bits
    \item Each key integer in the same range - hashing the key to get this to be true in all circumstances
    \item \textbf{Assigning (key, value) pairs to peers}: Assign key to the peer that has the closest ID where closest is the immediate successor of the key - rolling over to the front if necessary
    \item Each peer (in a circular manner) is only aware of the immediate \textbf{successor and predecessor} - therefore requires O(n) to resolve a query
    \item Introduce \textbf{shortcuts} st each peer keeps track of that peer so they keep track of the IP addresses of predecessor, successor, short cuts. Can design shortcuts st O(log n) neighbours and O(log n) messages in average query.
    \item \textbf{Peer Churn}: to handle peer churn, you actually need to know IP address of its two successors - where each peer periodically pings two successors to see if they are both alive.
    \begin{enumerate}
        \item If a peer leaves, the predecessor detects, makes second successor its immediate successor 
        \item Asks them who their immediate successor and sets them as second successor
        \item Informs predecessor of their new second successor
    \end{enumerate}
    
\end{enumerate}


\end{document}