% Copyright 2021 <NAME>

% Licensed under the Apache License, Version 2.0 (the "License");
% you may not use this file except in compliance with the License.
% You may obtain a copy of the License at

% 	http://www.apache.org/licenses/LICENSE-2.0

% Unless required by applicable law or agreed to in writing, software
% distributed under the License is distributed on an "AS IS" BASIS,
% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
% See the License for the specific language governing permissions and
% limitations under the License.

\documentclass{article}

\usepackage{amsmath, graphicx, hyperref}
\usepackage{fancyvrb, newverbs, xcolor}

\definecolor{cverbbg}{gray}{0.93}

\newenvironment{cverbatim}
 {\SaveVerbatim{cverb}}
 {\endSaveVerbatim
  \flushleft\fboxrule=0pt\fboxsep=.5em
  \colorbox{cverbbg}{\BUseVerbatim{cverb}}%
  \endflushleft
}

\newenvironment{lcverbatim}
 {\SaveVerbatim{cverb}}
 {\endSaveVerbatim
  \flushleft\fboxrule=0pt\fboxsep=.5em
  \colorbox{cverbbg}{%
    \makebox[\dimexpr\linewidth-2\fboxsep][l]{\BUseVerbatim{cverb}}%
  }
  \endflushleft
}

\newcommand{\ctexttt}[1]{\colorbox{cverbbg}{\texttt{#1}}}
\newverbcommand{\cverb}
  {\setbox\verbbox\hbox\bgroup}
  {\egroup\colorbox{cverbbg}{\box\verbbox}}

\begin{document}
\begin{titlepage}
    \begin{center}
        \vspace*{1cm}
        
        \Huge
        \textbf{Computer Networking Cheatsheet}
        
        \vspace{0.5cm}
        \LARGE
        
        \vspace{.5cm}
        
        <NAME>
   		  \vspace{1.5cm}
       
        \vfill
        
        \today
        
        \vspace{.8cm}
          \Large
          Computer Networking - SP. 2021 \\
        Computer Science\\
        Universit\`{a} della Svizzera Italiana, Lugano\\
        
    \end{center}
\end{titlepage}

\tableofcontents

\newpage

\section{Computer Networking and the Internet}
\subsection{Internet}
The Internet is both a computer network that connects together billions of computing devices around the world, and an infrastructure that provides services to applications. \\ \\
All of the devices connected to the Internet are called \textbf{hosts} or \textbf{end systems}. These hosts and end systems are connected together by a network of \textbf{communication links} and \textbf{packet switches}. The transmission rate of links is measured in bits/s. \\ \\
When two end systems need to exchange data, this is divided into \textbf{packets} and are sent through the network. When they arrive at destination, then they are reassembled. A \textbf{packet switch} takes a packet arriving on one of its incoming links and forwards them to one of its outgoing links. Packet switches can be of different types, such as \textbf{routers} and \textbf{link-layer switches}. \\ \\
End systems can access the Internet through \textbf{ISPs}. Each ISP in itself is a network of packet switches and communication links.

\subsection{Internet Services}
Applications on the Internet are said to be \textbf{distributed applications}, since they involve multiple end systems that exchange data with each other. In order for a program to instruct the Internet on how to deliver data to another program on another end system, \textbf{socket interfaces} are used. These interfaces are provided by hosts attached to the Internet.

\subsection{Protocols}
All activity in the Internet that involves two or more communicating remote entities is governed by a protocol. \\ \\
A protocol defines the format and the order of messages exchanged between two or more communicating entities, as well as actions taken on the transmission and/or receipt of a message or other event. Different protocols are used to accomplish different communication tasks. \\ \\
Internet standards are developed by the \textbf{IETF} (Internet Engineering Task Force) by means of \textbf{RFCs} (Requests For Comment). These RFCs define protocols such as TCP, IP, HTTP, SMTP... \\ \\
Other bodies also specify standards for network components, such as the \textbf{IEEE} (Institute of Electrical and Electronics Engineers).

\subsection{Network Edge}
A network edge is composed mainly of two parts:

\begin{itemize}
	\item \textbf{Network Edge}
	\vspace{.2cm} \\
	Is the part of the network which is composed of applications and end systems. These end systems are also referred to as \textbf{hosts}. That is because they run application programs.
	
	\item \textbf{Access Network}
	\vspace{.2cm} \\
	It is the network that physically connects an end system to the fist router, on a path from an end system all the way to any other distant end system.
\end{itemize}

\subsection{Physical Media}
\subsubsection{Guided Media}
In the case of guided media, the electromagnetic/optical waves are guided along a solid medium. Some examples of this kind of medium are:

\begin{itemize}
	\item \textbf{Twisted-Pair Copper Wire}
	\vspace{.2cm} \\
	Most used form is \textbf{UTP} (Unshielded Twisted Pair), and it is used for a computer network within a building.
	
	\item \textbf{Coaxial Cable}
	\vspace{.2cm} \\
	This medium is made out of copper (core) and has an internal concentric structure.
	
	\item \textbf{Fiber Optic Cable}
	\vspace{.2cm} \\
	This type of medium transfers bits as light pulses. It is immune to electromagnetic interference, have a very low signal attenuation up to 100 km and are very hard to tap.
\end{itemize}

\subsubsection{Unguided Media}
In the case of unguided media, electromagnetic waves are propagated in the atmosphere and/or in outer space.

\begin{itemize}
	\item \textbf{Terrestrial Radio Channel}
	\vspace{.2cm} \\
	No physical wire is needed to be installed, waves can penetrate walls and have a long range of action. Terrestrial radio channel can be divided into 3 categories: short range (Bluetooth), medium range (Wi-Fi) and long range (3G, LTE, 4G, 5G ...).
	
	\item \textbf{Satellite Radio Channel}
	\vspace{.2cm} \\
	Two types of satellites are used: \textbf{geostationary satellites} and \textbf{LEO satellites} (Low-Earth Orbiting).
\end{itemize}

\subsection{Packet Switching}
In order to send a message, the source breaks a long message into smaller chunks called \textbf{packets}. Between the source and the destination, each packet travels through \textbf{communication links} and \textbf{packet switches}. Packets are transmitted at a rate equal to the full transmission rate of the link. The formula is: \\

	\[ \Delta_{TX} = \frac{L}{R} \] \
	
\subsubsection{Store-and-Forward}
Most packets use the store-and-forward transmission. This means that the packet must be fully received before it can be forwarded to the next packet switch. The end-to-end delay over $N$ routers can be measured as follows: \\

	\[ d_{end-to-end} = N \cdot \frac{L}{R} \] \
	
\subsection{Forwarding Tables and Routing Algorithms}
Each router has a \textbf{forwarding table} that maps destination addresses to that router's outbound links. This is used by the router, in combination with the destination IP address in the packet's header, in order to find the next router the packet needs to be sent to. \\ \\
\textbf{Routing protocols} may, for example, determine the shortest path the packet needs to traverse in order to reach its destination.

\subsection{Circuit Switching}
In circuit switched networks, the resources needed along the path to provide for communication between the end systems are reserved for the whole duration of the connection. For this duration, also a constant transmission time is reserved and it is guaranteed to be constant. A circuit in a link is implemented using either:

\begin{itemize}
	\item \textbf{FDM (Frequency Division Multiplexing)}
	\vspace{.2cm} \\
	The frequency spectrum of the link is divided up among the established connections across the link. The link dedicates the frequency of the band for the entire duration of the connection. The bandwidth for telephone networks is 4 kHz, while FM radio stations share the 88-108 MHz frequency spectrum.
	
	\item \textbf{TDM (Time-Division Multiplexing)}
	\vspace{.2cm} \\
	In this case time is divided into frames of fixed duration, and each frame is divided into a fixed number of time slots. When the network establishes a connection, the network dedicates one time slot in every frame for this connection. 
\end{itemize}
Circuit switches can be wasteful because the dedicates circuits are idle during \textbf{silent periods}. These idle periods are instead used by packet switching networks and used for other connections.

\subsection{Structure of the Network}
In order to connect end users to each other, a network must be built. This network is hierarchical and is composed of multiple interconnected networks. These are the networks:

\begin{itemize}
	\item \textbf{Network Structure 1}
	\vspace{.2cm} \\
	This network structure interconnects all of the access ISPs with a \textbf{single global transit ISP}. This would be a network of routers and communication links that spans the globe.
	
	\item \textbf{Network Structure 2}
	\vspace{.2cm} \\
	This network consists of \textbf{many access ISPs} and a \textbf{few global transit ISPs}. Global transit ISPs themselves must be interconnected.
	
	\item \textbf{Network Structure 3}
	\vspace{.2cm} \\
	In any given region, there may be a \textbf{regional ISP} to which each \textbf{access ISP} connects. Each regional ISP then connects to \textbf{tier-1 ISPs}. These are the global transit ISPs.
	
	\item \textbf{Network Structure 4}
	\vspace{.2cm} \\
	\textbf{PoPs} (Points of Presence) are added in order to group one or more routers at the same location such that they can be connected to provider ISPs. Any ISP, could also decide to \textbf{multi-home}. That is, to connect two or more provider ISPs. \textbf{Peering} is when two ISPs that are both near and at the same hierarchy, connect their networks together. Finally, a third-party company can create an \textbf{IXP} (Internet eXchange Point), which is a meeting point where multiple ISPs can peer together.
	
	\item \textbf{Network Structure 5}
	\vspace{.2cm} \\
	\textbf{Content-Provider Networks} are added to the network -- such as Google. These networks peer with lower-level ISPs and connect to tier-1 ISPs.
\end{itemize}
This can be a schematic representation of the modern network of networks: \\ \\
\centerline{\includegraphics[width=9cm]{./assets/n_of_ns.png}}

\subsection{Packet Delay}
As a packet travels from one node to the subsequent node, the packet suffers from several types of delay at each node.

\subsubsection{Processing Delay}
The processing delay can be caused by the time required by routers and switches to examine the packet's header and finding out where it needs to go; it can also be caused by the time the router or switch takes in order to find bit-level errors in the packet, that may happen when the packet is transferred from a node to the other. \\ \\
This type of delay is in the order of $\mu s$.

\subsubsection{Queuing Delay}
The queuing delay is caused by the number of earlier-arriving packets that are waiting for transmission. If the traffic is heavy, then the time that the packets need to wait for them to be transmitted is longer. This kind of delay is calculated with the following formula: \\

	\[ d_{queue} = \frac{L \cdot a}{R} \cdot \frac{L}{R} \cdot \Big(1 - \frac{L \cdot a}{R}\Big) \] \\
	
\noindent For $\displaystyle \frac{L \cdot a}{R} < 1$. This type of delay is in the order of $\mu s$.

\subsubsection{Transmission Delay}
Assuming that we have a FIFO packet transmission, the packet can be transmitted only if all of the packets that are in front of it have been transmitted. The transmission delay can be calculated as follows: \\

	\[ d_{transmission} = \frac{L}{R} \] \\
	
\noindent This measures the time required to transmit all of the packet's bits onto the link. This type of delay is in the order of $\mu s / ms$.

\subsubsection{Propagation Delay}
The propagation delay depends on the physical medium of the link connecting the two nodes. The propagation speed can go from $2 \cdot 10^8 m/s$ to $3 \cdot 10^8 m/s$. The delay is calculated as follows: \\

	\[ d_{propagation} = \frac{d}{s} \] \\
	
\noindent This type of delay is in the order of $ms$.

\subsubsection{Nodal Delay}
The total nodal delay that happens at every node is: \\

	\[ d_{nodal} = d_{processing} + d_{queue} + d_{transmission} + d_{propagation} \] \
	
\subsection{Packet Loss}
Because the capacity of a router/switch queue is finite, if there are more packets than the buffer can hold, then those extra packets are dropped. Performance at a node must be thus measured also in terms of packet loss other than delay.

\subsection{End-to-End Delay}
The total delay from source to destination is calculated as: \\

	\[ d_{end-to-end} = N \cdot (d_{processing} + d_{transmission} + d_{propagation}) \] \\
This is true if all nodes have the same processing, transmission and propagation queues. If that were not the case, then all the single nodal delays must be added up together.

\subsection{End-to-End Throughput}
End-to-end throughput is the instantaneous rate at which a host can receive dat from another host. The formula is: \\

	\[ t_{end-to-end} = \frac{F}{T} \] \\
Throughput not only depends on the transmission rates of the links along the path, but also on the intervening traffic.
	
\subsection{Protocol Layers}
Each of the 5 layers that compose the \textbf{TCP/IP} protocol stack provides its service by performing certain actions within that layer and by using the services of the layer directly below it.

\subsubsection{Application Layer}
The application layer is where the network applications and their protocols reside. \\ \\
Some of the most important protocols of this layer are \textbf{HTTP}, \textbf{SMTP}, \textbf{FTP}, \textbf{DNS}... \\ \\
The packets at this layer are referred to as \textbf{messages}.

\subsubsection{Transport Layer}
The transport layer transports application-layer messages between application endpoints. \\ \\
The two layers of this protocol are \textbf{TCP} and \textbf{UDP}. TCP provides a connection-oriented service. It guarantees the delivery of messages to the destination and flow control. UDP, on the other hand provides no reliability, no flow control and no congestion control. \\ \\
The packets at this layer are referred to as \textbf{segments}.

\subsubsection{Network Layer}
The network layer moves packets from one host to the other. It also provides the service of delivering the segment to the transport layer in the destination host. \\ \\
The protocol provided at this level is the \textbf{IP protocol}, which defines how routers and end systems act on the packet's fields. All Internet components that have a network layer must run the IP protocol. \\ \\
The packets at this layer are referred to as \textbf{datagrams}.

\subsubsection{Link Layer}
The link layer moves a packet from one node to the next node in the route. \\ \\
The protocols used in this layer are for example \textbf{Ethernet}, \textbf{Wi-Fi} and \textbf{DOCSIS}. A datagram might be handled by a different protocol for each node it traverses. \\ \\
The packets at this layer are referred to as \textbf{frames}.

\subsubsection{Physical Layer}
The physical layer moves the individual bits within the frame from one node to the next. \\ \\
The protocols in this layer depend on the link and on the transmission medium.

\subsection{Encapsulation}
Routers and link switches do not incorporate all of the layers in the TCP/IP protocol stack. \\ \\
Each time the packet goes from a layer to another, a header or trailer is added to it. These headers and trailers contain information about the layer, such as the IP address and MAC address of the destination end system. \\ \\
From layers 1 to 3 (application, transport and network layers) headers are added at each layer. Instead in layer 4 (link layer), both a header and a trailer are added to the packet. The trailer is used to verify the integrity of the packet. \\ \\
In more complex cases, a large message may be divided into multiple transport-layer segments. These segments would have to be reconstructed by the destination host in order to get the full message.

\section{Application Layer}
\subsection{Architectures}
The application architecture is designed by the application developer and dictates how the application is structured over the various end systems.

\subsubsection{Client-Server Architecture}
In this architecture there is an always-on host which has a permanent IP address. This host (server) receives requests from other hosts (clients).

\subsubsection{Peer-to-Peer Architecture}
In this architecture there is no always-on host. Here the direct communication between peers is exploited. P2P architectures are self-scalable and cost effective. There are also problems with security, performance and reliability.

\subsection{Process Communication}
Processes that are executing in different hosts communicate by exchanging messages. These processes are called the \textbf{client process} (which initiates the communication) and the \textbf{server process} (which awaits to be connected).

\subsubsection{Sockets}
A socket is the interface between the application and the transport layer within a host (i.e. the API between the application and the network). The only control the application developer has on the transport-layer side is on:

\begin{itemize}
	\item Choice of the transport protocol
	\item Change the buffer size or maximum segment size
\end{itemize}

\subsubsection{Sever Process Identification}
In order to identify a server process, two pieces of information are needed:

\begin{itemize}
	\item \textbf{IP Address}
	\vspace{.2cm} \\
	It is a \textbf{32-bit} or \textbf{64-bit} (respectively IPv4 and IPv6) quantity that can uniquely identify a host.
	
	\item \textbf{Port Number}
	\vspace{.2cm} \\
	Since many different processes could run on a host, the IP is not sufficient to determine a specific process. To identify a process in a host, a port number is needed. Every port number is associated with a specific process.
\end{itemize}

\subsubsection{Services Needed by the Layer}
The following services are needed by the application layer:

\begin{itemize}
	\item \textbf{Reliable Data Transfer}
	\vspace{.2cm} \\
	The transport layer may need to provide a reliable data transfer rate. There exist applications that are \textbf{loss-tolerant} and application that require \textbf{100\% reliable} data transfer rates. In the first case, applications can tolerate some loss of packets.
	
	\item \textbf{Throughput}
	\vspace{.2cm} \\
	A transport service may need to provide guaranteed available throughput at some specified rate. There exist applications that are \textbf{bandwidth-sensitive}, and other that are \textbf{elastic}. In the first case, applications require a minimum amount of throughput to be effective. In the second case, applications make use of whatever throughput they get.
	
	\item \textbf{Timing}
	\vspace{.2cm} \\
	A transport service may need to provide timing guarantees available throughput at some specified rate. Low delays are preferred to high delays.
	
	\item \textbf{Security}
	\vspace{.2cm} \\
	A transport service may need to provide the application with one or more security services, such as encryption, data integrity or end-point authentication.
\end{itemize}

\subsection{Transport Services}
The two protocols offered when creating a network application are \textbf{UDP} and \textbf{TCP}.

\subsubsection{TCP}
It includes a connection-oriented service and a reliable data transfer service. Both services are received by the application when TCP is invoked.

\begin{itemize}
	\item \textbf{Connection-Oriented Service}
	\vspace{.2cm} \\
	The client and server exchange transport-layer control information with each other before the application-level messages begin to flow. This is known as \textbf{handshaking}. After a successful handshake, a connection is said to exist between the sockets of the two processes. Both processes can now send messages at the same time. \\ \\
	The connection is \textbf{full-duplex}, and the connection is teared down after the application has finished sending messages.
	
	\item \textbf{Reliable Data Transfer Service}
	\vspace{.2cm} \\
	The communication process can rely on TCP to deliver all of the data sent, without errors and in the proper order. It also has a congestion-control mechanism, which throttles a sending process when the network is congested between sender and receiver. It also attempts to limit each TCP connection to its fair share of network bandwidth.
\end{itemize}


\subsubsection{UDP}
It is a connectionless and lightweight protocol. It provides an unreliable data transfer service, no guarantee that the message will even reach the destination, the message might not arrive in order and there is no congestion-control mechanism.

\subsection{Application-Level Protocols}
An application-level protocol defines how an application's processes -- running on different end systems -- pass messages to each other. In particular they define the following:

\begin{itemize}
	\item The type of messages exchanged 
	\item The syntax of messages
	\item The semantics of the fields
	\item Rules of determining when and how a process sends and receives messages
\end{itemize}
There are two types of protocols:
\begin{itemize}
	\item \textbf{Open Protocols}
	\vspace{.2cm} \\
	HTTP, SMTP, FTP, Telnet...
	
	\item \textbf{Proprietary Protocols}
	\vspace{.2cm} \\
	Skype, BitTorrent...
\end{itemize}

\subsection{The Web and HTTP}
The \textbf{HTTP} (HyperText Transfer Protocol) protocol is at the heart of the Web. HTTP is implemented in two separate programs: a client program and a server program. These two programs communicate with each other by means of HTTP messages. HTTP defines how clients request Web pages from servers, and how servers transfer Web pages to clients. \\ \\
A \textbf{Web page} is a document stored inside of a Web server, and contains objects. An \textbf{object} is a file that is addressable by a single URL. \\ \\
When a user sends an \textbf{HTTP request}, the server receives it and responds with an \textbf{HTTP response} containing the requested objects.

\subsubsection{URL}
The \textbf{URL} (Uniform Resource Locator) of a web page is composed of the following parts: \\

\centerline{\includegraphics[width=7cm]{./assets/url.png}}

\subsubsection{HTTP Connection}
HTTP uses \textbf{TCP} as its underlying protocol. In order to obtain an HTTP connection, the following steps must be followed:

\begin{enumerate}
	\item The client initiates a TCP connection (by creating a socket) to the server on port 80;
	\item The server accept the TCP connection request made by the client;
	\item HTTP messages are now exchanged through the TCP link, from the client's to the server's socket;
	\item The TCP connection is then dismantled when it is not needed anymore. 
\end{enumerate}

\subsubsection{Persistent and Non-Persistent HTTP}
HTTP is a \textbf{stateless protocol}. This means that it does not maintain any information about past client requests. There are two types of stateless HTTP connections:

\begin{itemize}
	\item \textbf{Non-Persistent HTTP Connection}
	\vspace{.2cm} \\
	\textbf{At most one} object can be sent on this type of TCP connection. Once the response has been sent from the server to the client, the TCP connection is terminated. In total, the response time of an HTTP server is of 2 \textbf{RTTs} (Round Trip Times), plus the transmission time at the server of the HTML file. \\ \\
	In their default modes, browsers open 5 to 10 parallel TCP connections, and each of these connections handles one request-response transaction.
	
	\item \textbf{Persistent HTTP Connection}
	\vspace{.2cm} \\
	Multiple objects can be sent over a single TCP connection between client and server. As little as one RTT is used for all the referenced objects. \\ \\
	Persistent HTTP connections can also be pipelined, in which case two RTTs are needed to establish the connection, and one RTT is needed for \textbf{all} requested objects.
\end{itemize}

\subsection{Round-Trip Time}
The \textbf{RTT} (Round-Trip Time) is the time taken by a small packet to travel from a client to a server, and back. One RTT is used to initiate the TCP connection, and one RTT is used for the HTTP request and the first few bites of the HTTP response to arrive.

\subsection{HTTP Message Format}

The following is an example of HTTP request:

\begin{lcverbatim}
1  GET /doc/test.html HTTP/1.1 \r\n
   \_/ \____________/ \______/
    |         |          |
   Method    URL       Version
   
----------------------------------------------------------------

2  Host: my-server.com \r\n
.  ...
5  User-Agent: Mozilla/4.0 \r\n\r\n
   \_________/ \_________/
        |           |
       Name       Value
       
----------------------------------------------------------------

7  userName=Edoardo&userSurname=Riggio
\end{lcverbatim}
\textbf{Line 1}: Request Line; \\
\textbf{Lines 2-5}: Header Lines; \\
\textbf{Line 7}: Body.

\pagebreak

\noindent The following  is an example of HTTP response:

\begin{lcverbatim}
1  HTTP/1.1 200 OK \r\n
   \______/ \_/ \/
       |     |   Phrase
    Version Status
    
----------------------------------------------------------------

2  Date: Sat, 27 March 2021 15:51:20 GMT \r\n
.  ...
5  Content-Type: text/html \r\n\r\n
   \___________/ \_______/
         |           |
        Name       Value
        
----------------------------------------------------------------

7  <h1> <NAME> </h1>
\end{lcverbatim}
\textbf{Line 1}: Response Line; \\
\textbf{Lines 2-5}: Header Lines; \\
\textbf{Line 7}: Body. \\ \\
The HTTP status codes are:

\begin{itemize}
	\item \textbf{1xx} - Informational
	\item \textbf{2xx} - Success
	\item \textbf{3xx} - Redirection
	\item \textbf{4xx} - Client Error
	\item \textbf{5xx} - Server Error
\end{itemize}

\subsection{Cookies}
Since HTTP is a stateless protocol, in order to save info about the session we use cookies. In order to send and receive cookies, the following is done by the client and server:

\begin{enumerate}
	\item The client sends an HTTP request to the server;
	\item The server responds with a \cverb|Set-Cookie: xxxx| header;
	\item The client then does another HTTP request, this time including the \cverb|Cookie: xxxx| header;
	\item The server now responds with a normal HTTP response.
\end{enumerate}
By using cookies, a server knows exactly which pages the user visited, in which order, and at what time.

\subsection{Web Caching}
A \textbf{web cache} is a network entity that satisfies HTTP requests on behalf of an origin web server. The goal of this type of cache is to satisfy requests without involving the origin server, The cache acts as both client (for the main server) and server (for the clients). It is installed by the ISP. \\ \\
Web caching is used in order to reduce the response time for the client requests, reduce the traffic on an institution's access link, and substantially reduce Web traffic in the Internet as a whole -- improving the performances for all applications. \\ \\
Through the use of \textbf{CDNs} (Content Distribution Networks), Web caches are playing an important role in the Internet. The goal of CDNs is to localize traffic as much as possible.

\subsubsection{Conditional GET}
One problem that caches introduce are possible \textbf{stale objects}. HTTP can verify if it's actually stale with a \textbf{conditional GET}. This request includes the \cverb|If-Modified-Since: xxxx| header, so that the cache can always know if an object if stale or not.

\subsection{SMTP}
\textbf{SMTP} (Simple Mail Transfer Protocol) is a protocol that uses TCP to reliably transfer mail from client to server. Typically, a SMTP process is located on port 25 of a server. \\ \\
An email server is directly sent from one SMTP server to another, no in-between server are used. SMTP is mainly a push protocol, and multiple objects in SMTP are sent in multipart messages (MIME -- Multipurpose Internet Mail Extensions). \\

\centerline{\includegraphics[width=9cm]{./assets/smtp.png}}
\vspace{.6cm}
\noindent SMTP uses TCP as its underlying transport service. The following is an example of an SMTP exchange:

\begin{lcverbatim}
S: 220 server.com
C: HELO usi.ch
S: 250 Hello, pleased to meet you
C: MAIL FROM: <<EMAIL>>
S: 250 <EMAIL> ... Sender ok
C: RCPT TO: <<EMAIL>>
S: 250 <EMAIL> ... Recipient ok
C: DATA
S: 354 Enter mail, end with "." on a line by itself
C: Long time no see!
C: Would you like to hang out sometime?
C: .
S: 250 Message accepted for delivery
C: QUIT
S: 221 server.com closing connection
\end{lcverbatim}

\subsection{Mail Access Protocols}
Once the email has been delivered using SMTP, the user needs to access its mailbox in order to read emails. To do so, one of the following protocols is used:

\begin{itemize}
	\item \textbf{POP3}
	\vspace{.2cm} \\
	The \textbf{POP3} (Postal Office Protocol version 3) protocol allows a user to download emails from a server to its computer. It is a stateless protocol. There are two modes available in POP3:
	
	\begin{itemize}
		\item \textbf{Download-and-Delete Mode}
		\vspace{.2cm} \\
		The messages are downloaded to the computer and are later (when the user issues the \cverb|QUIT| command) deleted from the mailbox on the server.
		
		\item \textbf{Download-and-Keep Mode}
		\vspace{.2cm} \\
		The messages are kept in the mailbox even after the user has logged out.
	\end{itemize}
	
	\item \textbf{IMAP}
	\vspace{.2cm} \\
	The \textbf{IMAP} (Internet Mail Access Protocol) protocol allows a user to consult their emails from a remote server. By doing so, it can be accessed simultaneously by multiple clients.
	\item \textbf{HTTP}
	\vspace{.2cm} \\
	Mails are passed to the client using the \textbf{HTTP} protocol, rather than POP3 or IMAP. In this case emails are sent to the source server also using HTTP (transfer to destination service always happens through SMTP).
\end{itemize}

\subsection{DNS}
The \textbf{DNS} (Domain Name System) is a distributed database implemented in a hierarchy of DNS servers, and it is an application level protocol that allows hosts to query the distributed database. \\ \\
The DNS protocol runs over UDP and uses port 53. In addition to translating hostnames into IP addresses, DNS provides a few additional services, such as:

\begin{itemize}
	\item \textbf{Host Aliasing}
	\vspace{.2cm} \\
	A host with a complicated name could have one or more alias names. In that case, one of them is said to be the \textbf{canonical name}.
	\item \textbf{Mail Server Aliasing}
	\vspace{.2cm} \\
	DNS can be invoked by a mail application in order to obtain the canonical hostname for a supplied alias hostname as well as the IP address of the host. Moreover, the MX record of the DNS allows a company to use the same hostname for both their Web server and mail server.
	\item \textbf{Load Distribution}
	\vspace{.2cm} \\
	A set of IP addresses could be associated with the canonical hostname (for example when dealing with websites with lots of incoming traffic). The DNS in this case rotates the address every time a request is made.
\end{itemize}

\subsubsection{DNS Servers Hierarchy}
DNS uses a large number of servers organized in a hierarchical fashion. There are four classes of DNS servers:

\begin{itemize}
	\item \textbf{Root DNS Server}
	\vspace{.2cm} \\
	These servers provide the IP addresses of the TLD servers. There are over 400 root servers around the world.
	\item \textbf{TLD Server}
	\vspace{.2cm} \\
	A TLD (Top-Level Domain) sever manages a top-level domain (e.g. .it, .com, .net...). TLD servers provide the IP address for authoritative DNS servers.
	\item \textbf{Authoritative DNS Servers}
	\vspace{.2cm} \\
	Every organisation with publicly accessible hosts on the Internet must provide publicly accessible DNS records. These organisations can either create a personal authoritative DNS server, or use some service provider.
	\item \textbf{Local DNS Server}
	\vspace{.2cm} \\
	The local DNS server has a local cache of recent name-to-address translation pairs. This is the server where the user query first arrives.
\end{itemize}
DNS queries usually follow a recursive pattern from the requesting host to the local DNS, and an iterative pattern for the remaining steps.

\subsubsection{DNS Caching}
When a DNS server receives a DNS reply, this can be cached in the server's local memory. This is mainly done to improve the delay performance and to reduce the number of DNS messages. \\ \\
DNS servers will discard the cached information after a certain period of time (usually set to two days).

\subsubsection{DNS Records}
The DNS servers that together implement the DNS distributed database store \textbf{RRs} (Resource Records). An RR is a four-tuple. For example: \\

\centerline{\includegraphics[width=6cm]{./assets/dns.png}}
\vspace{.6cm}
There are four types of RRs:

\begin{itemize}
	\item \textbf{Type = A}
	\vspace{.2cm} \\
	\cverb|Name| is the hostname and \cverb|Value| is the hostname's IP address. This is a standard hostname-to-IP address mapping.
	\item \textbf{Type = NS}
	\vspace{.2cm} \\
	\cverb|Name| is the domain and \cverb|Value| is the domain's hostname of an authoritative DNS server that knows how to obtain the domain. This RR is used to route DNS queries further along in the query chain.
	\item \textbf{Type = CNAME}
	\vspace{.2cm} \\
	\cverb|Name| is the alias hostname and \cverb|Value| is the hostname's canonical hostname.
	\item \textbf{Type = MX}
	\vspace{.2cm} \\
	\cverb|Name| is the alias hostname and \cverb|Value| is the mail server hostname's canonical hostname.
\end{itemize}
If a DNS server is authoritative for a particular hostname, then the DNS server will contain \textbf{Type A} records for that hostname. \\ \\
If a DNS server is not authoritative for a particular hostname, then the server will contain a \textbf{Type NS} record for the domain that includes the hostname. Furthermore, it will also contain a \textbf{Type A} record that provides the IP address of the DNS server contained in the \cverb|Value| field of the NS record.

\subsubsection{DNS Messages}
The DNS query and reply messages are structured as follows:
\vspace{.5cm}

\centerline{\includegraphics[width=11cm]{./assets/dns_message.png}}
\vspace{.5cm}
\noindent The following are the fields of a DNS message:

\begin{itemize}
	\item \textbf{Identification}
	\vspace{.2cm} \\
	It is a 16-bit number that identifies the query. The same identifier is set to the corresponding answer.
	
	\item \textbf{Flags}
	\vspace{.2cm} \\
	There are a series of flags that identify the message. For example we have 1 bit describing if the message is a query or a response, 1 bit to identify if the server is an authoritative server...
	
	\item \textbf{Questions}
	\vspace{.2cm} \\
	Contains information about the query that is being made. This section includes: a \textbf{name field} containing the name that is being queried, and a \textbf{type field} which indicates the type of question being asked about the name.
	
	\item \textbf{Answers}
	\vspace{.2cm} \\
	Resource records for the name that was queried. It can contain multiple RRs.
	
	\item \textbf{Authority}
	\vspace{.2cm} \\
	It contains records of other authoritative servers.
	
	\item \textbf{Additional Information}
	\vspace{.2cm} \\
	It contains additional information, for example info about the canonical hostname of a server in response to an MX or CNAME query.
\end{itemize}

\subsection{Peer-to-Peer File Distribution}
In the P2P paradigm, \textbf{peers} are pairs of intermittently connected hosts. These peers communicate directly with each other, and are not owned by any service provider. The following are the two approaches for distributing a file.

\subsubsection{Client-Server Approach}
\begin{itemize}
	\item \textbf{Sending the File} \\
		\[ \displaystyle\frac{F}{u_s}~~~\text{(For 1 copy)} \] \\
		\[ \displaystyle N \cdot \frac{F}{u_s}~~~\text{(For N copies)} \] \
	
	\item \textbf{Downloading a file} \\
		\[ \displaystyle d_{min} = \min{\{d_1, d_2, ..., d_N\}}~~~\text{(min download rate)} \] \\
		\[ \displaystyle \frac{F}{d_{min}}~~~\text{(min download time)} \] \
	
	\item \textbf{Time to Distribute F to N Peers} \\
		\[ \displaystyle D_{CS} = \max{\ \Bigg\{\frac{NF}{u_s} , \frac{F}{d_{min}} \Bigg\}} \] \
\end{itemize}

\subsubsection{Peer-to-Peer Approach}
\begin{itemize}
	\item \textbf{Sending the File} \\
		\[ \displaystyle\frac{F}{u_s} \] \
	
	\item \textbf{Downloading a file} \\
		\[ \displaystyle u_s + \sum^{N}_{i = 1} u_i~~~\text{(min download rate)} \] \\
		\[ \displaystyle \frac{F}{d_{min}}~~~\text{(min download time)} \] \
	
	\item \textbf{Time to Distribute F to N Peers} \\
		\[ \displaystyle D_{P2P} = \max{\ \Bigg\{\frac{F}{u_s} , \frac{F}{d_{min}}, \frac{NF}{u_s + \sum^{N}_{i = 1} u_i} \Bigg\}} \] \
\end{itemize} \

\subsection{BitTorrent}
BitTorrent is a popular P2P protocol for file distribution. In BitTorrent, a collection of peers participating in the distribution of a particular file is called a \textbf{torrent}. Peers in a torrent download equal-sized chunks of size 256 kbytes. Once a peer has acquired the entire file, it can choose to either leave the torrent, or stay in the torrent. Once a torrent is left, it can later be rejoined. \\ \\
Each torrent has an infrastructure node called a \textbf{tracker}. This tracker will provide the user with a subset of peers from the participating peers on the list. The new peer now tries to establish a concurrent TCP connection with all of its peers. \\ \\
As time goes on, some peers might leave the torrent, and some others might join the torrent. The \textbf{rarest chunks} are requested first, this is done in order to equalize the numbers of copies of each chunk in a torrent. \\ \\
The peer gives priority to the neighbors that are supplying data at the highest rate. The peer reciprocates by sending data to the best four peers, any other peer is said to be \textbf{choked}, meaning that the user does not send chunks to them. \\ \\
Every 10 seconds, the peer recalculates the rates of its neighbors and possibly modifies its set of four peers -- which are said to be \textbf{unchoked}. Every 30 seconds, the user also picks up a new peer -- which is said to be \textbf{optimistically unchoked}, since it may become one of the user's top four uploaders.

\subsection{Video Streaming}
Videos are pre-recorded and saved onto a server. Users can request these videos on-demand from their end systems. These videos are compressed to a desired bit-rate. The higher the bit-rate, the better the image quality. There are two main methods to encode videos:

\begin{itemize}
	\item \textbf{Spacial Coding}
	\vspace{.2cm} \\
	This is when instead of sending $N$ values of the same color, only two values are sent: the color value and the times it is repeated.
	
	\item \textbf{Temporal Coding}
	\vspace{.2cm} \\
	This is when instead of sending a complete frame $i+1$ (where $i$ is the current frame), only the differences from frame $i$ are sent.
\end{itemize}
Here are some of the bitrates of different encodings:

\begin{itemize}
	\item \textbf{MPEG 1} - 1.5 Mbps
	\item \textbf{MPEG 2} - 3-6 Mbps
	\item \textbf{MPEG 3} - 64 Kbps-12 Mbps
\end{itemize}

\subsection{DASH}
\textbf{DASH} (Dynamic Adaptive Streaming over HTTP) is an HTTP-based streaming protocol. In DASH, the video is encoded into several different formats, everyone with different bit-rates. The servers keeps each version, and offers a \textbf{manifest file}. In this file there are all the bit-rates offered by the server and the location of the corresponding video. \\ \\
The client can choose the bit-rate which is suitable to its needs, namely the current bandwidth of the client.

\subsection{CDN}
A \textbf{CDN} (Content Distribution Network) manages servers located in multiple geographically distributed locations. CDNs replicates content across its clusters. Many CDNs may not want to push videos to their clusters, but instead use a simple pull strategy. If a client is requesting a video that is not on that cluster, then the cluster retrieves the video and stores a local copy. There are two main server placement strategies for CDNs:

\begin{itemize}
	\item \textbf{Enter Deep}
	\vspace{.2cm} \\
	Deploy server clusters in access ISPs all over the world. The goal is to get as close as possible to the user. In this approach, maintaining and managing the server clusters is challenging and expensive.
	
	\item \textbf{Bring Home}
	\vspace{.2cm} \\
	Build larger server clusters at a smaller number of sites. These CDNs are usually placed in IXPs. This approach has a lower maintenance overhead.
\end{itemize}
A CDN must intercept the video request made by a client and perform two operations: determine a suitable CDN server cluster for that client at that time, and redirect the client's request to a server in that cluster. To do so most CDNs take advantage of DNS to intercept and redirect requests. \\ \\
In order to select the best cluster for a user a particular time, two methods ca be used:
\begin{itemize}
	\item \textbf{Geographically Closest Cluster}
	\vspace{.2cm} \\
	Simply assign the cluster that is geographically closer to the client. This is not always a good idea, because the closest client might be the one with the greatest number of hops, thus the client might experience big delays.
	
	\item \textbf{Current Traffic Conditions}
	\vspace{.2cm} \\
	In this case the CDN periodically computes the current traffic conditions and, based on these calculations, decides which server cluster the client must be connected to.
\end{itemize}

\section{Transport Layer}
A transport-layer protocol provides for logical communication between the application processes running on different hosts. From an application's perspective, it is as if the two hosts were directly connected. \\ \\
There are two types of protocol actions in end systems:

\begin{itemize}
	\item \textbf{Sender}
	\vspace{.2cm} \\
	Breaks the application message into segments, which are then passed to the Network Layer.
	
	\item \textbf{Receiver}
	\vspace{.2cm} \\
	Reassembles the segments into messages, which are then passed to the Application Layer.
\end{itemize}

\subsection{Constraints from the Network Layer}
The \textbf{Network Layer} uses the \textbf{IP} (Internet Protocol) protocol. This protocol provides for the logical communication between hosts, where each host has a unique IP address. \\ \\
The IP protocol is what's known as a best-effort delivery service. This means that there is no guarantees of in-order delivery or even delivery per se.

\subsection{Transport Layer Protocol}
The transport layer has two protocols:

\begin{itemize}
	\item \textbf{TCP}
	\vspace{.2cm} \\
	TCP (Transmission Control Protocol) offers a reliable, in-order delivery. It also offers connection setup, flow control and congestion control.
	
	\item \textbf{UDP}
	\vspace{.2cm} \\
	UDP (User Datagram Protocol) offers an unreliable and unordered delivery.
\end{itemize}
Neither TCP nor UDP provide either delay or bandwidth guarantees. Instead, what they both provide is integrity checking and multiplexing-demultiplexing.

\subsection{Multiplexing and Demultiplexing}
Multiplexing and demultiplexing are used in order to extend the host-to-host delivery service provided by the network layer to a process-to-process delivery service for applications running on the hosts. The following are the ways multiplexing and demultiplexing are implemented:

\begin{itemize}
	\item \textbf{Multiplexing at Sender}
	\vspace{.2cm} \\
	It is the job of gathering data chunks at the source host from different sockets, encapsulating each chunk of data with header information in order to create segments, and passing the segments to the Network Layer.
	
	\item \textbf{Demultiplexing at Receiver}
	\vspace{.2cm} \\
	It is the job of delivering the data in a transport-layer segment to the correct socket.
\end{itemize}
Sockets have unique identifiers and each segment has a special field that indicates the socket to which the segment is to be delivered. These fields are the \textbf{source port number field} and the \textbf{destination port number field}. \\ \\
Port numbers ranging from 0-1023 are called \textbf{well-known ports}. These ports are restricted, and reserved to well-known application protocols (HTTP, FTP...).

\subsubsection{Connectionless Multiplexing and Demultiplexing}
When creating a segment to send into a UDP socket, the sender must specify the following:

\begin{itemize}
	\item \textbf{Destination IP Address}
	\item \textbf{Destination Port Number}
\end{itemize}
When the receiving host receives the UDP segment, it does two things:

\begin{itemize}
	\item Checks the destination port number in the segment
	\item Directs the UDP segment to the socket with that port number
\end{itemize}
All UDP datagrams with the same destination port number will be directed to the same socket at the receiving host.

\subsubsection{Connection-Oriented Multiplexing and Demultiplexing}
A TCP connection is defined by a 4-tuple:

\begin{itemize}
	\item \textbf{Source IP Address}
	\item \textbf{Source Port Number}
	\item \textbf{Destination IP Address}
	\item \textbf{Destination Port Number}
\end{itemize}
In the demultiplexing process, the receiver uses all four values of the tuple to direct the segment to the appropriate socket. \\ \\
Servers may also support may simultaneous TCP connections. Each connection is identified by its own 4-tuple, and to each of these connections is associated a different connecting client.

\subsection{UDP}
There are several peculiarities of UDP, such as:

\begin{itemize}
	\item Finer application-level control over what data is sent and when
	\item No connection is established
	\item There is no connection state neither at the sender nor at the receiver
	\item It has only 8 bytes of overhead
	\item No congestion control
\end{itemize}
The following is the structure of a UDP segment: \\ \\ \\
\centerline{\includegraphics[width=6cm]{./assets/udp.png}} \\ \\ \\
The fields are:

\begin{itemize}
	\item \textbf{Length}
	\vspace{.2cm} \\
	This field specifies the total number of bytes in the UDP header (header + data)
	\item \textbf{Checksum}
	\vspace{.2cm} \\
	It is used to verify the integrity of the UDP segment by revealing bit-flips.
\end{itemize}

\subsubsection{UDP Checksum}
The checksum is treated in different ways by both server and receiver.

\begin{itemize}
	\item \textbf{Server}
	\vspace{.2cm} \\
	It treats the UDP segment fields contents as sequences of 16-bit integers. These integers are all added up, and the final checksum is calculated as the one's complement of the actual sum. Finally the result is stored inside of the checksum field of the UDP segment.
	
	\item \textbf{Receiver}
	\vspace{.2cm} \\
	All of the segment's fields are summed up and it is added to the sender's checksum. If any bit with value of 0 is detected in the final sum, then there is an error in the packet. The packet is thus discarded by the receiver.
\end{itemize}
\begin{cverbatim}
- Sender
 
  Source Port:       0110011001100000 +
  Destination Port:  0101010101010101 +
  Length:            1000111100001100 =
                     ------------------
                     0100011011000001 
                             |
                             | 1's complement
                             V
                     1011100100111110
                      
- Receiver
 
  Source Port:       0110011001100000 +
  Destination Port:  0101010101010101 +
  Length:            1000111100001100 =
                     ------------------
                     0100011011000001 +
  Sender Checksum:   1011100100111110 =
                     ------------------
                     1111111111111111   <- The checksum is valid
\end{cverbatim}

\subsection{Reliable Data Transfer}
\textbf{Reliable data transfer} is when no transferred data bits are corrupted or lost, and all transferred data bits are delivered in the order they where sent in. \textbf{TCP} offers reliable data transfer.

\subsubsection{Rdt 2.0}
The underlying channel in charge of sending packets may flip bits while transmitting. Reliable data transfer protocols based on retransmission are known as \textbf{ARQ} (Automatic Repeat reQest). In order to see if there are bit-flips or not, we use:

\begin{itemize}
	\item \textbf{ACKs (Acknowledgments)}
	\vspace{.2cm} \\
	The receiver specifically tells the sender that the packet arrived correctly.
	
	\item \textbf{NAKs (Negative AcKnowledgments)}
	\vspace{.2cm} \\
	The receiver specifically tells the sender that the packet arrived with errors. The sender needs to retransmit the package.
\end{itemize}
This version of the protocol uses a \textbf{Stop \& Wait} technique, meaning that the sender sends the packet and waits for a response to arrive.

\subsubsection{Rdt 2.1}
In this version of the protocol a sequence number is added to the packet. By doing so, the infrastructure has to remember whether the expected packet should have a sequence number of 1 or 0. Furthermore, it needs to check is the packet that was sent is a duplicate or not.  \\ \\
This protocol still uses ACKs and NAKs in order to check if the packets are corrupted.

\subsubsection{Rdt 2.2}
This protocol has the same features that version 2.1 has. In this case, though, the protocol only uses ACKs. Thus the receiver sends back another ACK in the case that everything is OK, and the packet arrived correctly.

\subsubsection{Rdt 3.0}
By using this protocol we assume that the channel can also lose packets. In such cases retransmission is not enough. A \textbf{timeout} is introduced. \\ \\
The sender waits a predetermined amount of time (the timeout) in order for it to receive the ACK. If after this amount of time no ACK has been received, then the packet is retransmitted. \\ \\ 
The performance of this version is poor. This is because it spends more time waiting than working.

\subsubsection{Rdt 3.0 with Pipelining}
In pipelining operations, the senders allows for multiple yet-to-be-acknowledged packets to be sent. \\ \\
This operation can increase by a significant amount the usage and performance of the infrastructure. This is where the \textbf{Go-Back-N} protocols come to play.

\subsubsection{Go-Back-N}
The \textbf{Go-Back-N} protocol allows the sender to transmit multiple packets without waiting for an acknowledgment. \\ \\
The sender can have at most N unacknowledged packets in the pipeline. The sender holds a "window" of up to N consecutive transmitted but unACKed packets. \\ \\
The following function is to indicate that $n$ packets ($n$ included) have to be all ACKed.

\begin{cverbatim}
ACK(n)
\end{cverbatim}
The following function indicates that all packets with a higher sequence number than $n$ in the window have to be retransmitted.

\begin{cverbatim}
Timeout(n)
\end{cverbatim}
If a packet has been received out-of-order, it can either discard it or buffer it. The out-of-order packet is then reACKed based on which packet has the highest sequence number. \\ \\
The main problem with GBN is that a packet error would cause the retransmission of many other packets.

\subsubsection{Selective Repeat}
The receiver individually acknowledges all correctly received packets. Furthermore, the sender retransmits individually for unACKed packets -- the sender needs to maintain a timer for each packet.

\subsection{TCP}
\textbf{TCP} (Transmission Control Protocol) implements a reliable data transfer service. This includes services such as:

\begin{itemize}
	\item \textbf{Error Detection}
	\item \textbf{Retransmission}
	\item \textbf{Cumulative Acknowledgments}
	\item \textbf{Timeouts}
	\item \textbf{Header Fields for Sequence Numbers}
	\item \textbf{Header Fields for Acknowledgment Numbers}
\end{itemize}
TCP is a \textbf{connection-oriented} protocol. This connection is full-duplex and point-to-point.

\subsubsection{MSS and MTU}
The \textbf{MSS} (Maximum Segment Size) is the maximum amount of application-layer data in the segment. The \textbf{MTU} is the Maximum Transmission Unit.

\subsubsection{TCP Segment Structure}
The following is the structure of a TCP segment: \\ \\ \\
\centerline{\includegraphics[width=11cm]{./assets/tcp.png}} \\ \\
Some of the main sections are:

\begin{itemize}
	\item \textbf{Sequence Number}
	\vspace{.2cm} \\
	It is the byte-stream number of the first byte in the segment.
	
	\item \textbf{Acknowledgment Number}
	\vspace{.2cm} \\
	It is put by the host and is the sequence number of the next byte the host is expecting from the other host in the connection.
\end{itemize}
TCP only acknowledges bytes up to the first missing byte in the stream. For this reason, TCP is said to provide \textbf{cumulative acknowledgments}. \\ \\
TCP also uses timeouts in order to determine if a packet has to be retransmitted or not. The timeout value can be difficult to set. If it is too short, there is the risk of premature timeouts and unnecessary retransmissions. On the other hand, if the timeout is too long, there is a slow reaction to segment loss.

\subsubsection{Estimating the RTT}
In order to estimate the round trip time and find a suitable timeout value, we use the following formula: \\

\[ RTT_{Est.} = (1 - \alpha) \cdot RTT_{Est.} + \alpha \cdot RTT_{Sample} \] \\
This is also known as the \textbf{EWMA} (Exponential Weighted Moving Average). Typically we have $\alpha = 0.125$.

\subsubsection{Variability of RTT}
In order to set the proper timeout value, we have to need a "safety margin". Mathematically, this is defined as: \\

\[ Ti = RTT_{Est.} + 4 \cdot RTT_{Dev} \] \\
Where: \\

\[ RTT_{Dev} = (1 - \beta) \cdot RTT_{Dev} + \beta \cdot | RTT_{Sample} - RTT_{Est.} | \] \\
Here typically we have $\beta = 0.25$.

\subsection{TCP Flow Control}
The \textbf{receive window} field inside of the TCP segment controls the sender. This means that the sender will never overflow the receiver's buffer by transmitting too much, too quickly. The size of the window is computed as: \\ \\
\cverb|rwnd = RcvBuffer - [LastByteRcv - LastByteRead]|

\subsection{TCP Connection Management}
Before sending and receiving data, the sender and receiver handshake. This is done in order to agree to establish connection, and on the connection parameters. \\ \\
Two-way handshakes do not always work in networks. There are several reasons why. For example there can be variable delays, some messages could be re-transmitted or there could be message reordering. In such cases an half-opened connection could be established. This is why a three-way handshake is instead needed.

\subsection{Congestion Control}
A congestion happens when too many senders are sending too much data at once. This could cause long delays and packet loss. \\ \\
These are some congestion insights:

\begin{itemize}
	\item Throughput can never exceed capacity
	\item Delay increases as the maximum capacity is approached
	\item Packet loss and re-transmission decreases the effective throughout
	\item Unneeded duplicates further decreases the effective throughput
	\item Upstream transmission capacity and buffering are wasted for packets lost downstream
\end{itemize}

\subsubsection{End-to-End Congestion Delay}
In order to mitigate congestion, TCP provides an \textbf{end-to-end congestion control}. In this case there is no explicit feedback from the network, and the congestion is inferred from the amount of packets that are lost and from the delay.

\subsubsection{Network-Assisted Congestion Control}
In the case of \textbf{network-assisted congestion control}, the routers provide direct feedback to sending and receiving hosts with flows passing through the congested router. This could indicate the congestion level or explicitly set the sending rate.

\subsection{TCP Congestion Control}
TCP implement what is known as \textbf{AIMD} (Additive Increase/Multiplicative Decrease). In this approach senders can increase the sending rate until packet loss occurs. When this happens, the sender will decrease the sending rate on loss events. \\ \\
\textbf{Additive increase} will increase the sending rate by 1 maximum segment size every RTT until loss is detected. When loss is detected, we have a \textbf{multiplicative decrease}, where the sending rate is cut in half. \\ \\
Loss is detected by the arrival of a triple ACK, and the rate is cut in half. When loss detection by timeout is detected, instead, will make sure that the rate is cut to 1 MSS (Maximum Segment Size). \\ \\
A TCP connection is initially slow, with an initial cwnd of 1 MSS. For every RTT where there is no loss, the cwnd is doubled. This is done by incrementing the cwnd by one for every ACK the sender receives.

\section{Network Layer}
The network layer's goal is to transport the segment from the sending to the receiving host. The network layer is present in every Internet device. \\ \\
A \textbf{router}'s job is to examine the header files in all IP datagrams passing through it. After being examined, the datagrams are moved from input ports to output ports, in order to transfer them along their end-to-end path. \\ \\
There are two key functions of the network layer, these are:

\begin{itemize}
	\item \textbf{Forwarding}
	\vspace{.2cm} \\
	To move packets from a router input link to the appropriate output link.
	
	\item \textbf{Routing}
	\vspace{.2cm} \\
	To determine the route taken by packets from source to destination.
\end{itemize}
There are also two main elements in the network layer:

\begin{itemize}
	\item \textbf{Data Plane}
	\vspace{.2cm} \\
	It is a local, per-router function. It determines how datagrams arriving in the router are forwarded to router output ports.
	
	\item \textbf{Control Plane}
	\vspace{.2cm} \\
	It is a network-wide logic. This determines how datagrams are routed among end-to-end paths from source to destination. \\ \\
	There are two control plane approaches. The first involves \textbf{traditional routing algorithms}, and are directly implemented in routers. Another approach involves \textbf{SDN} (Software-Defined Networking), which is implemented in remote servers. Thus there are two kinds of control planes:
	
	\begin{itemize}
		\item \textbf{Per-Router Control Plane}
		\vspace{.2cm} \\
		The individual routing algorithm components in each router interact inside of the control plane.
		
		\item \textbf{SDN Control Plane}
		\vspace{.2cm} \\
		The remote servers compute and install the forwarding tables directly on the routers.
	\end{itemize}
\end{itemize}

\subsection{Network Service Model}
The Internet Network Layer does not guarantee the following:

\begin{itemize}
	\item Successful packet delivery to destination
	\item Timing or order of delivery
	\item Bandwidth available to end-to-end flow
\end{itemize}
It simply offers a best-effort service. The mechanism is fairly simple, sufficient provisioning of bandwidth allows performance of real-time applications to be "good enough". The replication of application-layer distributed services allow these services to be provided from multiple locations.

\subsection{Architecture of a Router}
The four core components of a router are:

\begin{itemize}
	\item \textbf{Input Ports}
	\vspace{.2cm} \\
		
	
	\item \textbf{Output Ports}
	\item \textbf{Switching Fabric}
	\item \textbf{Routing Processor}
\end{itemize}
While the first three components are part of the \textbf{Forwarding Data Plane}, the last component is part of the \textbf{Control Plane}.

\subsubsection{Input Ports}
Input ports are composed of three layers:

\begin{itemize}
	\item \textbf{Line Termination}
	\vspace{.2cm} \\
	It is the physical layer of the router.
	
	\item \textbf{Link Layer Protocol}
	\item \textbf{Lookup, Forwarding and Queuing}
	\vspace{.2cm} \\
	If the datagrams arrive faster than anticipated, then they will enter a queue. The header of the packet is used in order to lookup the output port -- which is the second function of this layer. \\ \\
	When looking in the forwarding table for a given destination address, the router uses the \textbf{longest prefix} that matches the destination address. \\ \\
	If a control packet is received, then the switch forwards it directly to the routing processor.
\end{itemize}

\subsubsection{Switching Fabric}
The goal of the switching fabric is to transfer the packet from the input port to the appropriate output port. \\ \\
The \textbf{switching rate} is the rate at which packets can be transferred from input to output ports. \\ \\
There are three main types of switching fabrics:

\begin{itemize}
	\item \textbf{Memory}
	\vspace{.2cm} \\ \\
	\centerline{\includegraphics[width=6cm]{./assets/memory.png}} \\ \\
	The packet is copied to the system's memory, and then transferred to the correct output port. The speed is limited by the memory bandwidth and by its physical space.
	
	\item \textbf{Bus}
	\vspace{.2cm} \\ \\
	\centerline{\includegraphics[width=6cm]{./assets/bus.png}} \\ \\
	The datagram is passed from the input port to the output port via a shared bus. The switching speed is limited by the bus' bandwidth.
	
	\item \textbf{Interconnection Network}
	\vspace{.2cm} \\ \\
	\centerline{\includegraphics[width=5cm]{./assets/interconnection.png}} \\ \\
	It is an interconnection network consisting of $2N$ buses that connect $N$ input ports to $N$ output ports. The crosspoints at which the buses intersect with each other can be opened or closed by the switching fabric.
\end{itemize}

\subsubsection{Input Port Queuing}
If a switch fabric is slower than the input and output port rate combined, queuing may occur at the input ports. \\ \\
We have \textbf{HOL} (Head-Of-the-Line) blocking when queued datagrams at the front of the queue prevent others in the queue from moving forward. There are two steps in which the queues are handled:

\begin{itemize}
	\item \textbf{Output Port Contention}
	\vspace{.2cm} \\
	Only the first in the queue is transferred, while the others are blocked.
	
	\item \textbf{One Packet Time Later}
	\vspace{.2cm} \\
	The next packet in the queue will suffer from HOL blocking.
\end{itemize}

\subsubsection{Output Port Queuing}
\textbf{Buffering} is required when datagrams arrive from the fabric faster than the link transmission rate. This could cause datagrams to be lost -- congestion or lack of buffers could be the causes. \\
The scheduling discipline chooses among queued datagrams those to be transmitted -- this is called \textbf{priority scheduling}. In order to calculate the buffering, we can use the following formula:
\[ Buf = RTT \cdot \frac{C}{N} \]
The router buffers drop packets whenever they are full. There are two ways packets can be dropped:

\begin{itemize}
	\item \textbf{Tail Drop}
	\vspace{.2cm} \\
	Drop the incoming packet.
	
	\item \textbf{Priority Drop}
	\vspace{.2cm} \\
	Drop or remove a packet on a priority basis.
\end{itemize}

\subsection{Packet Scheduling}
The scheduling algorithm decides which packet to send next on the link. There are several scheduling algorithms, such as:

\begin{itemize}
	\item \textbf{FCFS/FIFO}
	\vspace{.2cm} \\
	FCFS (First Come, First Served) is when packets are transmitted in order of arrival, to the output port.
	
	\item \textbf{Priority}
	\vspace{.2cm	} \\
	The arriving packets are classified by any header field of the packet. The packets with the highest priority are sent first.
	
	\item \textbf{Round Robin}
	\vspace{.2cm} \\
	The arriving packets are classified by any header field of the packet. The server now cyclically scans the queues, sending on complete packets from each input in turn.
	
	\item \textbf{WFQ}
	\vspace{.2cm} \\
	WFQ (Weighted Fair Queuing) is a generalized Round Robin algorithm. Each input has a weight. This weight is calculated using the following formula: \\
	\[ W_a = \frac{W_i}{\sum_i i} \]
\end{itemize}

\subsection{IPv4 Datagram Format}
The IPv4 datagram is composed by several field. The following is its visual representation: \\
\centerline{\includegraphics[width=11cm]{./assets/ipv4.png}} \\ \\ 
Some of the fields are:
\begin{itemize}
	\item \textbf{Version}
	\vspace{.2cm} \\
	Indicates the version of the IP protocol.
	
	\item \textbf{Type of Service}
	\vspace{.2cm} \\
	It indicates the Internet service quality selection (real-time or non-real-time)
	
	\item \textbf{Identifier}
	\vspace{.2cm} \\
	Uniquely identifies the fragments of a particular datagram.
	
	\item \textbf{Flags}
	\vspace{.2cm} \\
	It is composed of 3 bits. \textbf{Bit 1} must be 0, \textbf{Bit 2} indicates if the datagram may fragment (0 - Yes, 1 - No), and \textbf{Bit 3} indicates if this is the last fragment (0 - Yes, 1 - No).
	
	\item \textbf{Time To Live}
	\vspace{.2cm} \\
	It is decremented by one for every time that the datagram is processed by a router. If \cverb|TTL == 0|, the datagram is dropped.
	
	\item \textbf{Upper-Layer Protocol}
	\vspace{.2cm} \\
	Indicates the protocol to which to pass the datagram at the final destination (e.g. 6 $\rightarrow$ TCP, 17 $\rightarrow$ UDP...).
	
	\item \textbf{Header Checksum}
	\vspace{.2cm} \\
	The Internet checksum of the datagram is computed by treating each 2 bytes in the header as a number. This must be recomputed and stored again at each router.
	
	\item \textbf{Destination IP Address}
	\vspace{.2cm} \\
	It is inserted by the sender of the datagram, and determined by the DNS.
\end{itemize}

\subsection{IPv4 Addresses}
There are $2^{32}$ possible addresses in this format. To create such addresses, we use the dotted-decimal notation. The following is an example:

\begin{cverbatim}
11000001 | 00100000 | 11011000 | 00001001
\______/   \______/   \______/   \______/
   |          |          |          |
  193    .    32    .   216    .    9
\end{cverbatim}

\subsection{Network Interface}
The boundary between the host and the physical link is called an \textbf{interface}. An IP address is technically associated with an interface, rather than the host containing that interface. \\ \\
Each interface on every router and host must have an IP address that is globally unique.

\subsection{Subnet Mask}
A \textbf{subnet mask} is indicated by the leftmost $x$ bits (e.g. 172.16.58.3/24, it would indicate the 24 leftmost digits) of an IP address. \\ \\
In order to determine the subnets, detach each interface from its host/router, creating islands of isolated networks. Each of these isolated networks is called a \textbf{subnet}.

\subsection{IP Assignment}
IP can be assigned using classful addressing -- which is obsolete, or by \textbf{CIDR} (Classless InterDomain Routing). \\ \\
When a host sends a datagram with destination address 255.255.255.255, the message is delivered to all hosts on the same subnet. This address is also commonly referred to as the \textbf{broadcast address}.

\subsubsection{Internet Number Registry System}
The \textbf{ICANN} (Internet Corporation for Assigned Names and Numbers) distributes IP addresses. It also manages DNS root servers, assigns domains... \\ \\
While router addresses are manually configured by network administrators, host addresses are configured using \textbf{DHCP} (Dynamic Host Configuration Protocol). The goal of DHCP is to dynamically assign an IP address to the host, the moment it joins the network. The following are the steps of the DHCP:

\begin{enumerate}
	\item The host broadcasts a \textbf{DHCP discover message}.
	\item The DHCP server responds with a \textbf{DHCP offer message}.
	\item The host requests the IP address by means of a \textbf{DHCP request message}.
	\item The DHCP server sends back the address by means of a \textbf{DHCP ACK message}.
\end{enumerate}
A DHCP server can return much more than just the allocated IP address on the subnet. DHCP can also return:

\begin{itemize}
	\item The address of the first-hop router for the client.
	\item The name and IP address of the DNS.
	\item The network mask.
\end{itemize}

\subsubsection{Network Address Translation}
Thanks to the NAT, as far as the rest of the Internet is concerned, only one IPv4 address is used by a local network. \\ \\
All of the devices in the local network have a 32-bit address in a private IP space. Some of the possible masks are:

\begin{itemize}
	\item 10/8
	\item 172.16/12
	\item 192.168/16
\end{itemize}
The NAT has several jobs, such as:

\begin{itemize}
	\item \textbf{Replace Outgoing Datagrams}
	\vspace{.2cm} \\
	The source IP address of every outgoing datagram is repplaced by the NAT IP address. Same thing goes for port numbers.
	
	\item \textbf{Remember}
	\vspace{.2cm} \\
	It has to internally store a table containing every translation pair.
	
	\item \textbf{Replace Incoming Datagrams}
	\vspace{.2cm} \\
	The NAT IP address of every incoming datagram is replaced by the source IP address stored in the NAT. Same thing goes for port numbers.
\end{itemize}

\subsection{Internet Protocol Version 6}
IPv6 was created because of the exhaustion of 32-bit IPv4 addresses. It also introduces some new features, such as:

\begin{itemize}
	\item \textbf{Expanded Addressing Capabilities}
	\vspace{.2cm} \\
	The \textbf{anycast address} has been introduced with IPv6, and allows a datagram to be delivered to any one of a group of hosts (for example, an HTTP GET request can be sent to a number of mirror sites that contain a given document).
	
	\item \textbf{40-byte Header}
	\vspace{.2cm} \\
	This allows for a faster processing by routers.
	
	\item \textbf{Flow Labeling}
	\vspace{.2cm} \\
	A \textbf{flow} allows the labeling of packets belonging to particular flows for which the sender requests special handling (e.g. audio or video transmission, or traffic carried out by a high-priority user).
\end{itemize}
The following is a visual representation of an IPv6 datagram: \\ \\
\centerline{\includegraphics[width=11cm]{./assets/ipv6.png}} \\ \\ 
Some of the fields are:

\begin{itemize}
	\item \textbf{Version}
	\vspace{.2cm} \\
	Version of the IP protocol.
	
	\item \textbf{Traffic Class}
	\vspace{.2cm} \\
	It is used to give priority to certain datagrams.
	
	\item \textbf{Flow Label}
	\vspace{.2cm} \\
	It identifies a flow of datagrams.
	
	\item \textbf{Next Header}
	\vspace{.2cm} \\
	Indicates the protocol to which to pass the datagram at the final destination.
	
	\item \textbf{Hop Limit}
	\vspace{.2cm} \\
	Same as TTL in IPv4 datagrams. In this case, the counter decrements with each hop the datagram makes (i.e. with each intermediate router it goes through).
\end{itemize}

\subsection{Transition from IPv4 to IPv6}
The Internet can operate with mixed IPv4 and IPv6 router thanks to \textbf{tunneling}. Tunneling enables for IPv6 datagrams to be transmitted as the payload of IPv4 datagrams among IPv4 routers.

\subsection{Generalized Forwarding}
In order to forward packets, each router has a \textbf{forwarding table}. Routers also follow a \textbf{match plus  action} abstraction, meaning that they match the bits in the arriving packet, and then take action. \\ \\
There exist two main types of forwarding:

\begin{itemize}
	\item \textbf{Destination-Based Forwarding}
	\vspace{.2cm} \\
	The match and action is solely based on the destination IP address.
	
	\item \textbf{Generalized Forwarding}
	\vspace{.2cm} \\
	Many header fields can determine the action to be taken by the router. Many actions are possible, such as: drop, copy, modify, log the packet.
\end{itemize}

\subsection{OpenFlow}
OpenFlow is a communications protocol that gives access to the forwarding plane of a network switch or router over the network.

\subsubsection{Flow Tables}
The flow of the datagram is defined by the header field value of the datagram. \\ \\
The actions of flow tables determine the processing that needs to be applied to a packet that matches a flow table entry. Some of the most important actions are: forwarding, dropping and modify fields.

\subsection{Middleboxes}
A middlebox is any intermediary box performing functions apart from normal, standard functions of an IP router on the data path between a source host and a destination host. \\ \\
Examples of middleboxes are:

\begin{itemize}
	\item NAT
	\item Firewall and IDS (Intrusion Detection System)
	\item Load balancers
	\item Caches
\end{itemize}
The services provided by the middleboxes can also be divided into three main categories:

\begin{itemize}
	\item \textbf{NAT Translation}
	\item \textbf{Security Services}
	\item \textbf{Performance Enhancers}
\end{itemize}
Although middleboxes were initially proprietary, they have now moved towards \textbf{"whitebox" hardware} implementing an open API. \\ \\
\textbf{NFV}s (Network Functions Virtualization) are programmable services that operate over whitebox networking.

\section{Control Plane}
The main function of the control plane is \textbf{routing}. This means that it needs to determine the route that packets need to take to arrive to their destination.

\subsection{Routing Protocols}
Routing protocols are used to determine the best path, from sending to receiving host, through the network of routers. \\ \\
A \textbf{path} is a sequence of routers, packets need to traverse from a given initial source host to a final destination host. \\ \\ \\
\centerline{\includegraphics[width=9cm]{./assets/graph.png}} \\ \\ \\
There are four types of routing algorithms:
\begin{itemize}
	\item \textbf{Centralized}
	\vspace{.2cm} \\
	All routers have a complete topology and link cost information. These are the \textbf{link state} algorithms.
	
	\item \textbf{Decentralized}
	\vspace{.2cm} \\
	Iterative process of computation, where there is an exchanging of info with the neighbors. The routers initially only know the link cost to the attached neighbors. These are the \textbf{distance vector} algorithms.
	
	\item \textbf{Dynamic}
	\vspace{.2cm} \\
	Routes change more quickly. There are periodic updates in response to link cost changes.
	
	\item \textbf{Static}
	\vspace{.2cm} \\
	The routes change slowly over time.
	
	\item \textbf{Load-Sensitive}
	\vspace{.2cm} \\
	The link costs vary dynamically to reflect the current level of congestion of the underlying link.
	
	\item \textbf{Load-Insensitive}
	\vspace{.2cm} \\
	A link's cost does not explicitly reflect its level of congestion.
\end{itemize}

\subsubsection{Dijkstra's Link-State Routing Algorithm}
This is a \textbf{centralized} algorithm, which computes the least cost paths from one node to all other nodes in the network. This algorithm is iterative, and after the $k$th iteration of it the least-cost path are known up to $k$ destination nodes. \\ \\
For example, the following graph: \\ \\ \\
\centerline{\includegraphics[width=9cm]{./assets/dls_1.png}} \\ \\ \\
Would generate the following least-cost-path tree -- from the left-most router: \\ \\ \\
\centerline{\includegraphics[width=9cm]{./assets/dls_2.png}} \\

\subsubsection{Distance-Vector Algorithm}
This algorithm is based on the Bellman-Ford equation. The equation is the following: \\
\[ D_x(y) = \min_v\{ c_{x, v} + D_v(y) \} \] \\
The cost of the least-cost path from \textit{x} to \textit{y} is calculated as the minimum -- taken over all neighbors \textit{v} of \textit{x} -- of the sum the direct cost of the link from \textit{x} to \textit{v}, plus the least-cost path from \textit{v} to \textit{y}. \\ \\
This algorithm is \textbf{distributed}, as well as self-stopping, iterative and asynchronous. \\ \\
Whenever a link cost changes, the node detects the change and recalculates the local DV. In the case that the DV changes, then the neighbors are notified.

\subsection{Scalable Routing}
Both LS and DV assume all routers are identical and that the network is flat. This is unrealistic in the real world, thus the solution is to group routers into \textbf{Autonomous Systems}. \\ \\
An Autonomous System is a group of routers under the same administrative control. An algorithm running inside of an AS is called an \textbf{intra-autonomous system routing protocol}. \\ \\
There are two types of routing -- regarding scalable routing:
\begin{itemize}
	\item \textbf{Intra-AS}
	\vspace{.2cm} \\
	Routing within the same AS.
	
	\item \textbf{Inter-AS}
	\vspace{.2cm} \\
	Routing between ASs.
\end{itemize}

\subsubsection{Interconnected ASs}
Being ASs interconnected, the forwarding table of each router is configured accordingly. \textbf{Intra-AS routing} determines the entries for destinations within the AS, while \textbf{Intra- and Inter-AS} both determine the entries for external destinations.

\subsection{Intra-AS Routing Protocols}

\subsubsection{RIP (Routing Information Protocol)}
RIP is DV based, where DVs are exchanged between routers every 30 seconds. This protocol is no longer used.

\subsubsection{EIGRP (Enhanced Interior Gateway Routing Protocol)}
EIGRP is also DV based. This protocol was formerly CISCO-proprietary software.

\subsubsection{OSPF (Open Shortest Path First)}
OSPF is a link-state protocol that uses \textbf{flooding of link state information} and \textbf{Dijkstra's least-cost path algorithm}. Each router constructs an entire topological map of the entire AS. Each router locally runs the Dijkstra algorithm to determine the shortest-path tree to all subnets. \\ \\
OSPF does not mandate a policy for how link weights are set. Whenever there is a change in a link's state, a router broadcasts this new link-state to all other routers. \\ \\
Some of OSPF's advances are:

\begin{itemize}
	\item \textbf{Security}
	\vspace{.2cm} \\
	The exchanges between OSPF routers can be authenticated.
	
	\item \textbf{Multiple Same-Cost Paths}
	\vspace{.2cm} \\
	When multiple paths to a destination have the same cost, OSPF allow multiple paths to be used.
	
	\item \textbf{Integrated Support For Unicast and Multicast Routing}
	
	\item \textbf{Support for Hierarchy within a Single AS}
	\vspace{.2cm} \\
	One OSPF area in the AS is configured to be the backbone area. The primary role of the backbone area is to route traffic between the other areas on the AS. The backbone area contains all area border routers in the AS and may also contain non-border routers as well.
\end{itemize}

\subsection{Inter-Autonomous Routing Protocols}

\subsubsection{BGP}
BGP (Border Gateway Protocol) is arguably the most important of all the Internet protocols, as it is the protocol that glues the thousands of ISPs in the Internet together. This protocol is decentralized and asynchronous, and uses DVs. \\ \\
In BGP, packets are not routed to a specific destination address, but instead to CIDRized prefixes -- each prefix represents a subnet or a collection of subnets. \\ \\
BGP provides each router a means to:

\begin{itemize}
	\item \textbf{Obtain Prefix Reachability Information from Neighboring ASs}
	\vspace{.2cm} \\
	This protocol allows each subnet to advertise its existence to the rest of the Internet.
	
	\item \textbf{Define the Best Routes to the Prefixes}
	\vspace{.2cm} \\
	A router may learn about two or more different routes to a specific prefix. In order to determine the best route, the router will locally run a BGP route-selection procedure.
\end{itemize}
Pairs of routers exchange routing information over semi-permanent \textbf{TCP} connections using port 179. Each such connections is called \textbf{BGP connection}. There are two types of BGP connections:

\begin{itemize}
	\item \textbf{Internal BGP (iBGP)}
	\vspace{.2cm} \\
	These are BGP sessions between routers in the same AS.
	
	\item \textbf{External BGP (eBGP)}
	\vspace{.2cm} \\
	These are BGP sessions that span two ASs.
\end{itemize}
When a router advertises a prefix across a BGP connection, it includes with the prefix several \textbf{BGP attributes}. Two of the most important attributes are:

\begin{itemize}
	\item \textbf{AS-PATH}
	\vspace{.2cm} \\
	It contains a list of ASs through which the advertisement has passed.
	
	\item \textbf{NEXT-HOP}
	\vspace{.2cm} \\
	This is the IP address of the router interface that begins the AS-PATH.
\end{itemize}

\subsubsection{Hot Potato Routing}
This is a routing algorithm used by BGP. The hot potato routing algorithm will choose the gateway that has the least intra-domain cost. In this case there is no need to worry about the inter-domain cost.

\subsection{Routing Policy}
ISPs, in a real-world scenario, only want to route traffic to/from its customer networks. To do so, \textbf{routing policies} are enforced. These policies can trump all other considerations when selecting a route to destination.

\subsection{ICMP}
ICMP (Internet Control Message Protocol) is a protocol used by hosts and routers to communicate network-level information to each other. ICMP messages are sent as the payload of an IP address (as UDP and TCP). \\ \\
A visual representation of an ICMP message is the following: \\ \\ \\
\centerline{\includegraphics[width=11cm]{./assets/icmp.png}} \\ \\ \\
Some fields are:
\begin{itemize}
	\item \textbf{Code}
	\vspace{.2cm} \\
	The ICMP subtype
	
	\item \textbf{Content}
	\vspace{.2cm} \\
	Copy of the IP header and at least 8 bytes of IP data.
\end{itemize}

\subsubsection{Ping}
The ping program sends an ICMP type 8, code 0 message (echo request) to the specified host. The destination host, seeing the packet, sends back a type 0, code 0 message (echo reply) to the sender.

\subsubsection{Traceroute}
The traceroute program allows us to trace a route from a host, to any other host in the world. This program is implemented with the use of ICMP messages. These are the steps for a traceroute:

\begin{enumerate}
	\item Source sends a series of ordinary IP datagrams to the destination. Each of these datagrams is carrying a UDP message with an unlikely port number. each of these datagrams have a TTL of 1, 2, 3 ... $n$.
	\item The source starts timers for each of the datagrams.
	\item When the $n$th datagram reaches the $n$th router, that router will observe that the packet TTL is expired. The receiving router thus sends back to the source an ICMP type 11, code 0 message (TTL expired). This message includes the name and IP address of the router.
	\item Once the source obtains the ICMP message, it stops the timer on that datagram and returns the RTT, name and IP address of the $n$th router.
	\item The source stops sending packets when the destination host sends back an ICMP type 3, code 3 message (destination port unreachable) back to the source.
\end{enumerate}

\section{The Link Layer and LAN}
The basic service of the link layer is to move a datagram from one node to an adjacent node over a single communication link. Most of the link layer is implemented in hardware, while high-level functionalities may be implemented in software that runs on the host's CPU.

\subsection{Definitions}
A \textbf{communication network} is a system that allows two or more endpoints to be connected and to exchange data. \\ \\
An \textbf{endpoint} is any kind of equipment that is able to connect to the network. \\ \\
A \textbf{node} is any device that runs a link-layer protocol. \\ \\
A \textbf{link} is a communication channel that connects adjacent nodes along the communication path.

\subsection{Communication Media}
Both \textbf{wired} and \textbf{wireless} communication links exist. \textbf{Wired} links are:

\begin{itemize}
	\item \textbf{Fiber Optic Cable}
	\item \textbf{Coaxial Cable}
	\item \textbf{Twisted Pair Copper Cable}
\end{itemize}
\textbf{Wireless} links are:

\begin{itemize}
	\item \textbf{Radio Waves}
\end{itemize}

\subsection{Communication Links}
Some communication link types are:

\begin{itemize}
	\item \textbf{Point-to-Point}
	\vspace{.2cm} \\
	When there is a single sender at one end of the link and a single receiver at the end of the link.
	
	\item \textbf{Broadcast}
	\vspace{.2cm} \\
	When there are multiple sending and receiving nodes all connected to the same, single and shared broadcast channel.
	
	\item \textbf{Unidirectional}
	\vspace{.2cm} \\
	Also called simplex. It provides one-way communication.
	
	\item \textbf{Bidirectional}
	\vspace{.2cm} \\
	Can be either \textbf{full-duplex} (two one-way channels) or \textbf{half-duplex} (one two-way channel). For example Ethernet an Fiber Optics are full-duplex, while coaxial is half-duplex.
\end{itemize}

\subsection{Link Access}
The \textbf{MAC} (Medium Access Control) protocol specifies the rules by which a frame is transmitted onto the link. \\ \\
This is easy for point-to-point links, but gets complex for broadcast links. \\ \\
The types of multiple access protocol are:

\begin{itemize}
	\item \textbf{Channel Partitioning Protocols}
	\item \textbf{Taking-Turns Protocols}
	\item \textbf{Random Access Protocols}
\end{itemize}

The Link Layer guarantees reliable delivery. That is, network-layer datagrams are guaranteed to be relayed across the link. This is typically achieved by means of retransmissions and acknowledgments.

\subsection{Multiple Access Problem}
In order to solve the issue of multiple nodes sharing the same single broadcast link, there is the need of a MAC protocol in order to coordinate the frame transmission of the nodes.

\subsubsection{Channel Partitioning Protocols}
In \textbf{TDM} (Time Division Multiplexing), time is divided into rounds, and each round is divided into $N$ slots. Each node gets a fixed length slot in each round, and unused slots remain idle. \\ \\

\centerline{\includegraphics[width=9cm]{./assets/tdm.png}}
\vspace{.9cm}
\noindent The advantages are that there are no collisions and perfect fairness. \\ \\
The disadvantages are that the max rate is always $\frac{R}{N} bps$ -- even when only one node has frames to send, and that there is a fixed latency before a node can send data. \\ \\
In \textbf{FDM} (Frequency-Division Multiplexing), a channel is divided into $N$ different frequency bands -- each with a bandwidth of $\frac{R}{N}$. Each node is assigned to one of the $N$ fixed frequency bands, and the unused transmission time in frequency bands go idle. \\ \\

\centerline{\includegraphics[width=8cm]{./assets/fdm.png}}
\vspace{.9cm}
\noindent This method has the same advantages and disadvantages as TDM.

\subsubsection{Taking-Turns Protocols}
In \textbf{polling protocols}, the master node polls each node in a Round-Robin fashion. \\ \\
The advantages are that there are no collisions and fairness. \\ \\
The disadvantages are that the rate is less than $R~bps$ even if only one node is active, and the master node is a single point of failure. \\ \\
In \textbf{token-passing protocols}, there is no master node. Instead, a small frame, called \textbf{token}, is exchanged among the nodes. Only the node that has the token is allowed to transmit. \\ \\
The advantages are that this protocol is fully decentralized, and that it is efficient. \\ \\
The disadvantage is that the token could be lost.

\subsubsection{Random Access Protocol}
The transmitting nodes always sent at the full $R~bps$ rate. But if there is a collision, a back-off mechanism is used in order to decide when to retransmit the packet. Some examples of random access protocols are:

\begin{itemize}
	\item \textbf{ALOHA}
	\vspace{.2cm} \\
	This was used by Hawaiians to connect all of their islands with a central computer located on the university campus of the main island. \\ \\
	This setup was composed of one main host and many client machines, a downlink from the host to the clients with frequency $f_1$, and an uplink from the clients to the host with frequency $f_2$.
	
	\item \textbf{Slotted ALOHA}
	Time is divided into slots. The length of a slot is $\frac{L}{R}$ seconds -- where $L$ is the number of bits in the frame and $R$ is the channel rate). \\ \\
	All of the nodes are synchronized, meaning that each node knows when a slot begins. These nodes only transmit frames to the hub at the beginning of slots. \\ \\
	
	\centerline{\includegraphics[width=10cm]{./assets/slotted-aloha.png}}
	\vspace{.4cm}
	
	\item \textbf{CSMA/CD}
	\vspace{.2cm} \\
	\textbf{CSMA} (Carrier Sensing Multiple Access) is when a node listens to the channel before transmitting. If a frame from another node is being transmitted, the node trying to send the frame waits and tries again later. \\ \\
	\textbf{CD} (Collision Detection) is when a transmitting node listens to the channel while it is transmitting. If it detects that another node is transmitting an interfering frame, the node trying to send stops transmitting, it waits and tries again later. \\ \\
	\textbf{CSMA/CD} are mechanisms used in the Ethernet protocol.	
	
	\item \textbf{Ethernet}
\end{itemize}

\subsection{Link-Layer Address}
A link-layer address is the unique address of a network adapter. A \textbf{network adapter} is a piece of hardware that connects a computer to a network. Network adapters contain both the physical and link layers. \\ \\
Each adapter has its own MAC address. This address is permanent and usually burned into its ROM (Read-Only Memory).

\subsection{MAC Address}
\subsubsection{MAC Address Format}
There are several different MAC address formats. One example is \textbf{EUI-48} (Extended Unique Identifiers). This type of MAC address is used in both Ethernet and Wi-Fi. \\ \\
This MAC address is made up of 6 bytes -- $2^48$ addresses are possible. These 6 bytes are divided in two parts:

\begin{itemize}
	\item \textbf{OUI (Organizational Unique Identifier)}
	\vspace{.2cm} \\
	24 bits are used for the OUI. This is assigned by IEEE and is globally unique.
	
	\item  \textbf{NIC (Network Internet Controller)}
	\vspace{.2cm} \\
	24 bits are used for the NIC.
\end{itemize}

\subsubsection{MAC Address Spoofing}
This is a technique used in order to change the factory-assigned MAC address of a network interface on a network device. \\ \\
MAC address randomization can be used to prevent the tracking of devices in Wi-Fi rich environments.

\subsection{Frame Forwarding at the Link Layer}
The link-level frames contain the MAC address of the intended destination of the frame. The broadcast address of MAC addresses is FF-FF-FF-FF-FF-FF.

\subsection{Address Resolution Protocol}
Since there are two types of both network- and link-layer addresses -- IP and MAC addresses, there is the need to translate between them. \\ \\
The ARP (Address Resolution Protocol) protocol allows a host to find the MAC address of a node given the node's IP address. This is done by building an ARP table with all IP - MAC mappings.\\ \\
	
\centerline{\includegraphics[width=11cm]{./assets/arp.png}}
\vspace{.3cm}

\subsubsection{ARP Query}
An ARP query is sent when the ARP does not find an entry in the table for a given IP address. \\ \\
The ARP query packet is sent to the broadcast address of the subnet, thus being received by all hosts in the subnet.

\subsubsection{ARP Response}
If a host matches the \textbf{TPA} (Target Protocol Address), it replies to the query with an ARP response packet. \\ \\
If the destination node is in another subnet, then the frame must be passed to the router that interconnects the two subnets.

\subsubsection{ARP vs DNS}
\textbf{ARP} is used to resolve addresses for hosts that are in the same subnet. \\ \\
\textbf{DNS} is used to resolve host names for hosts that are anywhere in the Internet.

\subsection{Ethernet}
Ethernet is a family of computer networking technologies commonly used in LANs (Local Area Networks), MANs (Metropolitan Area Networks) and WANs (Wide Area Networks). The first Ethernet standard was the \textbf{10BASE-5} (10 Mbps rate, baseband signalling and max length of 500 m). \\ \\
\textbf{IEEE 802.3} is a collection of standards defining the physical layer an data-link layer's MAC of wired Ethernet.

\subsubsection{Ethernet Frame}
Here is a graphical representation of the Ethernet frame:\\ \\
	
\centerline{\includegraphics[width=12cm]{./assets/ethernet.png}}
\vspace{.6cm}
\noindent The following are its fields:

\begin{itemize}
	\item \textbf{Preamble}
	\vspace{.2cm} \\	
	7 bytes of alternating 0s and 1s.
	
	\item \textbf{SFD}
	\vspace{.2cm} \\
	The SFD (Start of Frame Delimiter) signals the end of the preamble and the start of the packet.
	
	\item \textbf{Destination a Source MAC Addresses}
	
	\item \textbf{EtherType}
	\vspace{.2cm} \\
	Identifies the high-level protocol to which this frame should be delivered.
	
	\item \textbf{Payload}
	
	\item \textbf{FCS}
	\vspace{.2cm} \\
	The FCS (Frame Check Sequence) is a checksum used to verify the integrity of the packet.
\end{itemize}

\subsection{Bus Topology with 10BASE-5 Ethernet}
All stations a connected to each other through a coaxial cable. The maximum length of the signal is of 500 meters. The stations connect to the cable by means of an AUI (Attachment User Interface). \\ \\
Multiple segments are joined by repeaters. A maximum of 4 repeaters can be but between any pair of hosts, thus making the maximum length of the signal 2500 meters.

\subsubsection{Collision Domain}
Any signal placed on an Ethernet segment by a host is broadcasted over the entire segment. \\ \\
All hosts that compete for access to the same link are said to be in the same collision domain.

\subsubsection{Receiver Algorithm}
An Ethernet 10BASE-5 adapter receives all frames sent by any host and accepts:

\begin{itemize}
	\item Frames to its own address
	\item Frames to the broadcast address (all 1s)
	\item Frames to the multicast address (starts with 1), if the adapter was instructed to do so
	\item All frames, if it has been set in promiscuous mode
\end{itemize}
There are three techniques used for transmitting frames:

\begin{itemize}
	\item \textbf{CSMA (Carrier Sensing Multiple Access)} 
	\vspace{.2cm} \\
	The station that wants to send some data measures the level of current of the wire. If the level is over a certain threshold, this means that the carrier is busy.
	
	\item \textbf{CD (Collision Detection)}
	\vspace{.2cm} \\
	The sending station continuously measures the signal of the wire. If the signal is higher or lower than the transmitted signal, then there is a collision.
	
	\item \textbf{Binary Exponential Back-off}
	\vspace{.2cm} \\
	It measures the time to wait for retransmission after a collision has been detected.
\end{itemize}

\subsection{Link-Layer Switches}
\subsubsection{Hub vs Switch}
A \textbf{hub} has the following characteristics:

\begin{itemize}
	\item Multiple inputs
	\item Multiple outputs
	\item \textbf{Repeats an incoming signal to all of its output ports}
	\item \textbf{Has no buffer}
\end{itemize}
A \textbf{switch} has the following characteristics:

\begin{itemize}
	\item Multiple inputs
	\item Multiple outputs
	\item \textbf{Forwards an incoming signal to a specific output port}
	\item \textbf{Has a buffer}
\end{itemize}
While \textbf{hub-based topologies} need collision-preventing algorithms (such as CSMA and CD), \textbf{switch-based topologies} have no collisions.

\subsubsection{Switch Ports}
Each device connected to a switch port can transfer data to any of the other ports at any time. \\ \\
Switches can also store incoming data and forward it to the target interface.

\subsubsection{Operations of a Switch}
Two of the main operations of a switch are:

\begin{itemize}
	\item \textbf{Filtering}
	\vspace{.2cm} \\
	Determine if an incoming frame needs to be dropped or not.
	
	\item \textbf{Forwarding}
	\vspace{.2cm} \\
	Determine the interface to which incoming frames should be directed to, and move those frames.
\end{itemize}
All of this is done by the \textbf{switch table}. There are also some rules that apply to switch tables, namely:

\begin{itemize}
	\item If there is no entry in the table for a particular frame, it will be forwarded to all interfaces.
	\item If there is an entry in the table associated to the same port the frame is coming from, the frame is dropped.
	\item If there is an entry in the table associated to a port, then the frame is forwarded to that interface
\end{itemize}

\subsubsection{Characteristics of a Switch}
Switches have many interesting characteristics, such as:

\begin{itemize}
	\item \textbf{Self Learning}
	\vspace{.2cm} \\
	Each incoming frame is stored in the switch table (which is initially empty). Entries that are in the table for more than the aging time are deleted.
	
	\item \textbf{Plug \& Play}
	
	\item \textbf{Full-Duplex}
	Any switch interface can send and receive at the same time.
	
	\item \textbf{No Collisions}
	
	\item \textbf{Heterogeneous Links}
	\vspace{.2cm}
	Each link can run at different speeds and over different media.
	
	\item \textbf{Easy Network Management}
\end{itemize}

\subsubsection{Switch vs Router}
A \textbf{switch} is a two-layered packet switch, where the upper layer is the link layer. \\ \\
A \textbf{router} is a three-layered packet switch, where the upper layer is the network layer.

\subsection{Transmission of Bits}
Electromagnetic waves transport energy through empty space, stored in the propagating electric and magnetic field. The magnetic field variation is perpendicular to the electric field. \\ \\
A single frequency electromagnetic wave exhibits a sinusoidal variation of electric and magnetic fields on space. \\ \\
Transmission of bits may happen in two different ways:

\begin{itemize}
	\item \textbf{Amplitude Modulation}
	\vspace{.4cm} \\
	\centerline{\includegraphics[width=7cm]{./assets/amplitude.png}}
	\vspace{.4cm}
	
	\item \textbf{Frequency Modulation}
	\vspace{.2cm} \\
	\centerline{\includegraphics[width=7cm]{./assets/frequency.png}}
\end{itemize}
Amplitude and frequency may change due to, for example, reflection and refractions during propagation.

\subsection{Bit Errors}
The \textbf{BER} (Bit Error Ratio) can be computed by the following formula:

\[ BER = \frac{N_{err}}{N_{tot}} \] \\
\noindent The typical value for the BER in Ethernet links is $10^{-7}$ to $10^{-13}$, while for wireless, the BER is $10^{-3}$ to $10^{-6}$.

\subsubsection{Bit Errors Detection and Correction}
There are two types of error correction:

\begin{itemize}
	\item \textbf{FEC (Forward Error Correction)}
	\vspace{.2cm} \\
	Correction is done from the sender to the receiver. Additional error correcting bits are added to the sender.
	
	\item \textbf{ARQ (Automatic Repeat reQuest)}
	\vspace{.2cm} \\
	Correction is done from the receiver to the sender. Acknowledgments are sent by the receiver to signal a successful/unsuccessful reception.
\end{itemize}

\subsubsection{FEC Techniques}
The following are the FEC techniques used:

\begin{itemize}
	\item \textbf{Parity check}
	\vspace{.2cm} \\
	The sender adds a 1 bit so that the number of bits equal to 1 in the sequence is even. \\ \\
	The receiver checks the number of 1s in the sequence + EDC (Error Detection and Correction) bits. If the number is odd, then there is an error. \\ \\
	Most of the times, if there is one bit flip, there can also be more than one. This is why there exist more advanced parity checks -- such as two-dimensional parity.
	
	\item \textbf{Checksums}
	\vspace{.2cm} \\
	The field frames are treated as integers used as input to a checksum function. \\ \\
	A checksum is needed at the UDP level, because there is no guarantee there is error checking at lower levels. It could also be that bit errors are introduced when a UDP segment is stored in the router's memory.
	
	\item \textbf{CRC (Cyclic Redundancy Check)}
	\vspace{.2cm} \\
	A CRC field $R$ of $r$ bits is added to a piece of data $D$.
	
	\[ R = \text{remainder of}~ \frac{D \cdot 2^r}{G} \] \\
	$G$ is called the \textbf{generator}, which is composed of $r+1$ bits, and is known to both sender and receiver. \\ \\
	The sender chooses $r$ bits such that $d+r$ is exactly divisible by $G$. If the remainder of the division is not 0, then there is an error.
\end{itemize}

\section{Wireless Networks}
\subsubsection{Wireless Propagation}
Propagation is error prone because of three main reasons:

\begin{itemize}
	\item \textbf{Interfaces}
	\vspace{.2cm} \\
	This occurs when two or more waves overlap. This could be caused by other radio devices or other electromagnetic noise. Waves can either be constructive or destructive. \\ \\
	The power of Wi-Fi devices is limited to 100 mW in Europe.
	
	\item \textbf{Path Loss}
	\vspace{.2cm} \\
	There is a difference between the transmitted power (P$_{tx}$) and received power (P$_{rx}$):
	
	\[ P_{rx}(d) \approx \beta \cdot P_{tx} \cdot \frac{1}{d^\alpha} \]
	
	\item \textbf{Multiplicative Propagation}
	\vspace{.2cm} \\
	Portions of the electromagnetic wave may reflect off objects and the ground, taking paths of different lengths between sender and receiver.	
\end{itemize}

\subsection{Wi-Fi}
The Wi-Fi alliance is a "global non-profit association with the goal of driving the best user experience with a new wireless networking technology".

\subsubsection{Wi-Fi Access Point}
A Wi-Fi access point is a Wi-Fi certified device that provide wireless connectivity. These access points act as a gateway to other networks -- which can either be wired or wireless. \\ \\
Most access points are static, but they could also be mobile. Wi-Fi devices are all those that are based on the \textbf{IEEE 802.11} standards.

\subsection{IEEE 802.11}
IEEE 802.11 is a MAC and physical layer specification. It is designed for use in a limited geographical area. \\ \\
This protocol extends the common wired Ethernet local network into the wireless domain.

\subsubsection{Channels}
Depending on the specific standard, IEEE 802.11 transmits in the 900 MHz, 2.4, 3.6, 5 and 60 GHz frequency bands. It operates in the \textbf{ISM} (Industrial, Scientific and Medical) radio bands.

\subsubsection{Logical Architecture}
The main components of a wireless network are:

\begin{itemize}
	\item \textbf{STA (STAtion)}
	\vspace{.2cm} \\
	It is a device that has the capabilities of using the 802.11 protocol.
	
	\item \textbf{AP (wireless Access Point)}
	\vspace{.2cm} \\
	A networking hardware device that allows STAs to connect to the wired Internet.
	
	\item \textbf{BSS (Basic Service Set)}
	\vspace{.2cm} \\
	Term used to describe the collection of STAs which may communicate together within an 802.11 network. An AP may or may not be part of the BSS.
	
	\item \textbf{DS (Distribution System)}
	\vspace{.2cm} \\
	It interconnects BSSs.
	
	\item \textbf{IBSS (Independent Basic Service Set)}
	\vspace{.2cm} \\
	It is comprised of one or more STAs which communicate directly with each other.
	
	\item \textbf{ESS (Extended Service Set)}
	\vspace{.2cm} \\
	Is one or more interconnected BSSs
\end{itemize}

\subsubsection{Operating Modes}
There are two possible modes of operations:

\begin{itemize}
	\item \textbf{Infrastructure Mode}
	\vspace{.2cm}
	Here STAs are connected wirelessly to an AP, forming a BSS.
	
	\item \textbf{Ad Hoc Mode}
	\vspace{.2cm} \\
	Here STAs are directly connected to each other, forming a IBSS.
\end{itemize}

\subsubsection{SSID (Service Set IDentifier)}
A SSID, identifies the wireless network. The SSID is a name configured on the wireless AP or an initial wireless client that identifies the wireless network. The SSID is periodically advertised by the wireless AP or the initial wireless client using a special 802.11 MAC management frame -- known as the \textbf{beacon frame}.

\subsection{RSSI (Received Signal Strength Indicator)}
The RSSI measures the strength of the signal that arrives at the receiver. It can be computed with the following formula:

\[ RSSI = 10~log_{10}\left(\frac{P_{rx}}{1~mW}\right) \] \\
The value of the RSSI may vary depending on several factors, such as:

\begin{itemize}
	\item \textbf{Transmission power}
	\item \textbf{Multipath effects}
	\item \textbf{Presence of obstacles}
	\item \textbf{Antennas not being isotropic}
	\vspace{.2cm} \\	
	Different values are measured in different directions)
\end{itemize}

\subsection{IEEE 802.11 MAC}
\subsubsection{Acknowledgments}
When the destination host receives a frame, it checks the CRC of that frame. \\ \\
If the CRC check \textbf{passes}, then the destination host waits a short time -- called SIFS (Short Inter-Frame Spacing), and finally sends a link-layer acknowledgment to the source. \\ \\
If the CRC check \textbf{does not pass}, then the destination discards the frame and does not send an acknowledgment. The source then re-sends the frame after a timeout.

\subsubsection{CSMA/CA}
Before sending a packet, the transmitter checks if the wireless channel is free or busy. \\ \\
If the channel is \textbf{free}, then the transmitter waits for a short time -- called DIFS (Distributed Inter-Frame Space), and finally sends the packet. \\ \\
If the channel is \textbf{busy}, then the transmitter uses binary exponential back-off to calculate when to resend the packet. \\ \\
There are two collision issues with wireless networks:

\begin{itemize}
	\item \textbf{Hidden Terminal Problem}
	\vspace{.2cm} \\
	This happens when two hosts cannot directly hear each other, but their signal might still be able to collide.
	
	\item \textbf{Exposed Terminal Problem}
	\vspace{.2cm} \\
	This happens when a host can overhear another host, but the overhearing host should not hamper the host to communicate.
\end{itemize}

\subsubsection{RTS/CTS Handshake}
An \textbf{RTS} (Request To Send) message is sent by a STA to an AP. It includes a field that indicates the length of the packet to transmit. \\ \\
To the RTS message, the AP sends back a \textbf{CTS} (Clear To Send) message. This message lets the STA know it can initialize the transfer, and any other STAs now know one STA is transmitting and for how long. \\ \\
All STAs must wait for an \textbf{ACK} message sent by the AP in order to try/re-try to transmit.

\subsubsection{RTS Collisions}
It might happen that an RTS packet sent from two or more STAs collide. \\ \\
An RTS may also hamper the reception of a CTS packet. A solution is to make the CTS packets longer than the RTS packets -- in this way, collisions are detected.

\subsubsection{MAC Frame Format}
The IEEE 802.11 MAC frame can be graphically represented as such: \\ \\

\noindent  \includegraphics[width=12.5 cm]{./assets/wifi-mac.png}
\vspace{.4cm}
Some fields are:

\begin{itemize}
	\item \textbf{Duration/ID}
	\vspace{.2cm} \\
	Used to indicate the remaining duration needed to receive the next frame transmission.
	
	\item \textbf{Address Fields}
	\vspace{.2cm} \\
	Depending upon the frame type, the four address fields will contain a combination of the following address types: \textbf{BSSID} (BSS IDentifier), \textbf{DA} (Destination Address), \textbf{SA} (Source Address), \textbf{RA} (Receiver Address) and \textbf{TA} (Transmitter Address)
	
	\item \textbf{Sequence Control}
	\vspace{.2cm} \\
	Indicates the sequence and fragment numbers of each frame.
	
	\item \textbf{Frame Body}
	\vspace{.2cm} \\
	It contains information from the higher levels.
	
	\item \textbf{FCS}
	\vspace{.2cm} \\
	It allows for integrity check of frames.
\end{itemize}

\subsection{Beaconing}
\textbf{Beacons} are broadcast messages that contain information about a Wi-Fi access point, such as:

\begin{itemize}
	\item \textbf{MAC Address}
	\item \textbf{SSID}
	\item \textbf{Operation Mode}
	\item \textbf{Active Channel}
	\item ...
\end{itemize}
An AP sends beacons at regular time intervals. Each AP transmits on a specific channel. The host maintains a list of all available access points and selects one to associate with.


% -----------
%  EXERCISES
% -----------

\newpage

\section{APPENDIX A - Formulae Glossary}

\begin{itemize}
	\item \textbf{$\alpha$}
	\vspace{.2cm} \\
	Path loss exponent. It depends on the medium in which the signal propagates.
	
	\item \textbf{$\beta$}
	\vspace{.2cm} \\
	Multiplicative attenuation factor.	
	
	\item \textbf{a}
	\vspace{.2cm} \\
	Average rate of packets per second.
	
	\item \textbf{C}
	\vspace{.2cm} \\
	Link capacity.
	
	\item \textbf{D$_x$(y)}
	\vspace{.2cm} \\
	The cost of the least-cost path from \textit{x} to \textit{y}
	
	\item \textbf{d}
	\vspace{.2cm} \\
	Distance between the nodes. \textbf{Unit:} meters
	
	\item \textbf{F}
	\vspace{.2cm} \\
	File size in bits. \textbf{Unit:} bits
	
	\item \textbf{G}
	\vspace{.2cm} \\
	Bit pattern of $r+1$ bits.
	
	\item \textbf{L}
	\vspace{.2cm} \\
	Length of a packet in bits. \textbf{Unit:} bits
	
	\item \textbf{N}
	\vspace{.2cm} \\
	Number of hops/peers/ports.
	
	\item \textbf{N$_{err}$}
	\vspace{.2cm} \\
	Number of bit errors.
	
	\item \textbf{N$_{tot}$}
	\vspace{.2cm} \\
	Total number of bits sent.
	
	\item \textbf{R}
	\vspace{.2cm} \\
	Transmission rate. \textbf{Unit:} bits/second
	
	\item \textbf{s}
	\vspace{.2cm} \\
	Propagation speed of the link. \textbf{Unit:} meters/second
	
	\item \textbf{T}
	\vspace{.2cm} \\
	Transfer rate. \textbf{Unit:} bits/second
	
	\item \textbf{u}
	\vspace{.2cm} \\
	Peer's upload rate. \textbf{Unit:} bits/second
	
	\item \textbf{u$_s$}
	\vspace{.2cm} \\
	Server's upload rate. \textbf{Unit:} bits/second
\end{itemize}

\newpage

\section{APPENDIX B - Standard Ports}
\begin{itemize}
	\item \textbf{22} - SSH
	\item \textbf{23} - Telnet
	\item \textbf{25} - SMTP
	\item \textbf{53} - DNS
	\item \textbf{80, 8080, 8008} - HTTP
	\item \textbf{110} - POP3
	\item \textbf{143} - IMAP
	\item \textbf{179} - BGP
    \item \textbf{465} - SMTP (secure)
    \item \textbf{853} - DNS (secure)
    \item \textbf{992} - Telnet (secure)
	\item \textbf{993} - IMAP (secure)
	\item \textbf{995} - POP3 (secure)
\end{itemize}

\newpage

\section{APPENDIX C - Exercises}

\subsection{Chapter 1}
\begin{itemize}
	\item \textbf{Consider a circuit-switched network with four routers, positioned at the corner of an imaginary square. Label the four switches A, B, C, and D, starting from the top left corner and going in the clockwise direction. Assume there are five connections between any two adjacent routers. What is the maximum number of simultaneous connections that can be in progress at any one time in this network?}
	\vspace{.2cm} \\
	Number of nodes times the number of connections for each node $\rightarrow$ 5 * 4 = 20
	
	\item \textbf{Suppose Host A wants to send a large file to Host B. The path from Host A to Host B has three links, of rates R1 = 500 kbps, R2 = 2 Mbps; R3 = 1 Mbps. Assuming no other traffic in the network, what is the throughput R$_t$ for the file transfer?}
	\vspace{.2cm} \\
	The lowest rate $\rightarrow$ 500 kbps
	
	\item \textbf{Calculate how long it would take to transfer 40 GB of data from A to B on a 1 Mbps link.}
	\vspace{.2cm} \\
	Convert from GB to mbit and divide by link rate. Then convert seconds to hours. $\rightarrow$ $\frac{320000}{1} = 320000~s \rightarrow 88.8~h$
	
	\item \textbf{Assume a packet of length 1000 bytes must be transmitted between router A and router B. The link between A and B is 2.5 km long, enables a propagation speed of 2.5 10$^8$ m/s, and a transmission rate of 2 Mbps. Assume the first bit of the packet leaves router A at time t$_0$ = 0 s. After which delay t$_1$ does the first bit of the packet reach router B?}
	\vspace{.2cm} \\
	Convert km in m, and divide it by the propagation speed (propagation delay) $\rightarrow$ $\frac{2500}{2.5 \cdot 10^8} = 0.00001~s \rightarrow 10~\mu s$
	
	\item \textbf{Suppose Host A wants to send a large file to Host B. The path from Host A to Host B has three links, of rates R1 = 500 kbps, R2 = 100 kbps, R3 = 1 Mbps. Suppose the file is 60 MB. Assuming all other delays are negligible with respect to the transmission delay, how long will it take to transfer the file to Host B? Please give your answer in minutes.}
	\vspace{.2cm} \\
	The throughput is the slowest link, thus is 100 kbps. Convert MB to kilobit and divide by throughput (transmission delay) $\rightarrow$ $\frac{480000}{100} = 4800~s = 80~min$
	
	\item \textbf{Assume a packet of length 1000 bytes must be transmitted between router A and router B. The link between A and B is 2.5 km. long, enables a propagation speed of 2.5 10$^8$ m/s, and a transmission rate of 2 Mbps. Assume the first bit of the packet leaves router A at time t$_0$ = 0 s. After which delay x = t$_0$ + t$_2$ does the last bit of the packet leave router A?}
	\vspace{.2cm} \\
	Convert bytes in Mbits, then divide by the transmission rate (transmission delay) $\rightarrow$ $\frac{0.008}{2} = 0.004~s = 4~\mu s$
\end{itemize}

\subsection{Chapter 2}
\begin{itemize}
	\item \textbf{Consider a link over which hosts can transmit at a rate of 2048 kbps in both directions. Suppose that packets containing data are 128 kbits long, and packets containing only control (e.g., ACK or handshaking) are 256 bits long. Now suppose that a client issues an HTTP/1.1 request to a server to retrieve an object. Suppose that the downloaded object fills a single data packet. Assuming that propagation, queuing and processing delays are negligible, how much time would it take a client to obtain the object from the server?}
	\vspace{.2cm} \\
	Convert bits in kbits, multiply by 3 (which is the number of packets containing control) and add it to the length of the data $\rightarrow$ $3*\left(\frac{0.256}{2048}\right)+\frac{128}{2048} = (3 * 0.000125) + 0.0625 = 0.000375 + 0.0625 = 0.062875 = 62.875 ms$
	
	\item \textbf{Consider a link over which a sender can transmit at a rate of 2 Mibps in both directions. Assuming an object of size 256 kibit must be transmitted, how much is the transmission delay?}
	\vspace{.2cm} \\
	Convert kibit to Mibit and divide it by the transmission rate (transmission delay) $\rightarrow$ $\frac{0.25}{2} = 0.125~s = 125~ms$
\end{itemize}

\subsection{Chapter 3}
\begin{itemize}
	\item \textbf{Suppose Host A sends a TCP segments to Host B over a TCP connection. The segment has sequence number X and carries Y bytes of payload. In the acknowledgment that Host B sends to Host A, what will be the acknowledgment number?}
	\vspace{.2cm} \\
	Y bytes of the payload are added to the X of the sequence number $\rightarrow$ $Y + X$
	
	\item \textbf{Suppose Host A sends a TCP segments to Host B over a TCP connection. The segment has sequence number X and carries Y bytes of payload. In the acknowledgment that Host B sends to Host A, what will be the sequence number?}
	\vspace{.2cm} \\
	It cannot be derived by the data
	
	\item \textbf{Assume that the current estimated round-trip-time (RTT) in a TCP connection is 250 ms. Assuming that the exponential weighted moving average with alpha = 0.1 is used to compute the estimate of RTT, what will be the new value of such estimate, after a new measurement of RTT equal to 200 ms is recorded?}
	\vspace{.2cm} \\
	Use the RTT estimation formula $\rightarrow$ $(1 - 0.1) \cdot 250 + 0.1 \cdot 200 = 0.9 \cdot 250 + 0.1 \cdot 200 = 225 + 20 = 245~ms$
	
	\item \textbf{Consider 8 TCP connections, each with a different end-to-end path, but all passing through a bottleneck link with transmission rate R = 64 MBps. If the congestion control mechanism used on these connections is fair, what will be the average transmission rate over each connection?}
	\vspace{.2cm} \\
	Since the TCP connection is fair, then we simply divide the transmission rate by the number of connections $\rightarrow$ $\frac{64}{8} = 8$ \textit{MBps}
	
	\item \textbf{Assume that the slow start threshold of a TCP connection is 32 MSS when a loss event is first detected. Immediately after another loss event is detected at the sender, what will be the value of the threshold?}
	\vspace{.2cm} \\
	For every loss detected, the MSS is divided by two. Since we have two losses detected, we divide two times by two $\rightarrow$ $\frac{32}{2} = 16$ \textit{MSS} and then $\frac{16}{2} = 8$ \textit{MSS}
\end{itemize}

\newpage

\section{APPENDIX C - Useful Links}
\begin{itemize}
	\item \textbf{Interactive Exercises}: \underline{\textit{\hyperlink{https://gaia.cs.umass.edu/kurose_ross/interactive/}{interactive end-of-chapter exercises}}}
	\item \textbf{Unit converter}: \underline{\textit{\hyperlink{https://www.google.com/search?q=unit+converter}{google unit converter}}}
\end{itemize}

\end{document}