End to End Protocols

class: title, smokescreen, shelf, bottom, no-footer
background-image: url(images/Tcp_state_diagram.svg)

# 181U Spring 2020
## Introduction to the Internet

.smokescreen h1 {
    border-bottom: none;
}

.small {font-size: 80%}
  .smaller {font-size: 70%}
  .small-code.remark-slide-content.compact code {font-size:1.0rem}
  .very-small-code.remark-slide-content.compact code {font-size:0.9rem}

.line-numbers{
  /* Set "line-numbers-counter" to 0 */
  counter-reset: line-numbers-counter;
}

.line-numbers .remark-code-line::before {
  /* Increment "line-numbers-counter" by 1 */
    counter-increment: line-numbers-counter;
    content: counter(line-numbers-counter);
    text-align: right;
    width: 20px;
    border-right: 1px solid #aaa;
    display: inline-block;
    margin-right: 10px;
    padding: 0 5px;
}

</style>

---
layout: true
.footer[
- 181U
- See acknowledgements
]

---
class: compact
# Agenda

* Getting Processes to Communicate
* Simple Demultiplexor (UDP)
* Reliable Byte Stream (TCP)
 
---
class: compact
# Getting Processes to Communicate (review)
 
**processes** : program running on a single computer

* Within the a single computer, processes communicate using **inter-process** communication (through the Operating System)
* Processses on different computers communicate by exchanging **messages**

clients,servers
* **client process:** process that initiates communication
* **server process:** process that waits to be contacted.

---
class: compact
# Sockets

* Process sends/receives messages to/from its **socket**
* socket analagous to door
    - sending process shoves message out door
    - sending process relies upon transport infrastructure on the other side
of door to deliver to message to socket at receiving process

![](images/space.png# w-10pct)
![](images/sockets.png# w-80pct)

---
class: compact
# Getting Processes to Communicate -- issues

**The Underlying Network can**

* Drop messages
* Reorder messages
* Deliver duplicates of messages
* Limit the size of messages
* Deliver messages with an arbitrarily long delay

This level of service is called *best-effort*

**IP** is a best-effort protocol that provides host-to-host messages.

---
class: compact
# Getting Processes to Communicate -- issues

**Applications Expect**

* Guaranteed message delivery
* In-order delivery
* Delivery without duplication
* Arbitrarily large messages
* Support for multiple applications on each host
* Flow control (receiver can limit delivery rate)

---
class: compact
# Simple Demultiplexor (UDP)

![](images/udp-header-format.png# w-30pct fr)

* The simplest protocol extends host-to-host delivery into a process-to-process communication service.
* UDP extends IP by adding a simple header defining *ports* which are simply addresses that the communicating hosts use to multiplex and demultiplex messages to various applications.
* Notice
  * Port numbers are 16bits (64k unique ports)
  * Communicating processes must be mapped to (source, destination) pair 
* How do we find ports ?
  * Certain well-known services have "assigned" ports
  * 53: domain name server (DNS)
  * 25: mail server

---
class: compact
# Ports are an OS abstraction

![](images/udp-message-queue.png# w-30pct fr)

Typically, a port is implemented as a message queue
* Arriving messages are appended to a queue and read from the queue by an application process
* UDP does not implement flow control or reliable message delivery
* UDP checksum -- provides error detection for the header + contents

---
class: compact
# Socket programming with UDP

UDP: no "connection" between client & server

* no handshaking before sending data
* sender explicitly attaches IP destination address and port # to each packet
* receiver extracts sender IP address and port # from received packet

UDP: transmitted data may be lost or received out of order
---
class: small-code,compact,hljs-tomorrow-night-eighties,line-numbers
# Aside on Network Programming

The API for network applications is based upon sockets.  
* A  **socket** is the interface through which a application attaches to the network.  The C language interface is a bit confusing because it handles both internal and internet connections as well as datagram/stream connections.

```C
int socket(int domain, int type, int protocol)
```

A server **binds** a socket to an address, **listens** to the socket (and hence the address/port) and **accepts** connections from the internet.

```C
int bind(int socket, struct sockaddr *address, int addr_len);
int listen(int socket, int backlog);
int accept(int socket, struct sockaddr *address, int *addr_len);
```
This is all pretty ugly in C which works at the OS interface level

---
class: compact
# UDP Connection Example

![](images/space.png# w-20pct)
![](images/2019-12-03-14-09-34.png# w-60pct)

---
class: very-small-code,compact,hljs-tomorrow-night-eighties,line-numbers
# A UDP Server in go

```go

func handleUDPConnection(conn *net.UDPConn) {
        buffer := make([]byte, 1024)

n, addr, err := conn.ReadFromUDP(buffer)
        message := []byte("Hello UDP client!")
        _, err = conn.WriteToUDP(message, addr)
}

func main() {
        hostName := "localhost"
        portNum := "6000"
        service := hostName + ":" + portNum

udpAddr, err := net.ResolveUDPAddr("udp4", service)
        ln, err := net.ListenUDP("udp", udpAddr)

fmt.Println("UDP server up and listening on port 6000")

for {
                handleUDPConnection(ln) // loop forever
        }
}
```
---
class: small-code,compact,hljs-tomorrow-night-eighties,line-numbers
# UDP Client (in go)

```Go
func main() {
  hostName := "localhost"
  portNum := "6000"
  service := hostName + ":" + portNum
         // Use DNS to resolve remote address
  RemoteAddr, err := net.ResolveUDPAddr("udp", service)
         // Create a UDP connection
  conn, err := net.DialUDP("udp", nil, RemoteAddr)
         // The following could be in loop
         // write a message to server
  _, err = conn.Write([]byte("Hello UDP server!"))
         // receive message from server
  buffer := make([]byte, 1024)
  n, addr, err := conn.ReadFromUDP(buffer)
         // print out result
  fmt.Println("UDP Server : ", addr)
  fmt.Println("Received from UDP server : ", string(buffer[:n]))
 }
```

---
class: compact
# Reliable Byte Stream (TCP)

* UDP is connection-less -- 
  * server listens at a known port, 
  * client chooses a local port 
  * sends/receives to the server
  * ip:port provides a unique address on each side
* TCP is connection-oriented -- 
  * server listens at a known port, 
  * client chooses a local port 
  * client connects to server
  * sends/receives reliable byte streams to the server 
  
---
class: compact
# TCP Protocol Issues

* Reliable transfer -- based upon error detection + *sliding window* protocol
  - handles: message loss, duplication, reordering, delayed delivery
* Assumes a maximum packet lifetime
* Implements congestion control (TCP connection tries not to hog bandwidth)

---
class:compact
# Principles of Reliable Data Transfer
* IP layer is "unreliable" -- packets may be lost, duplicated, corrupted, and delivered out of order
* UDP is "unreliable"
* TCP is "reliable" -- data delivered in-order and only once.

![](images/space.png# w-2-12th)
![](images/reliablecommunication.png# w-70pct)

---
class: compact
# Reliable Data Transfer (Structure)

![](images/space.png# w-2-12th)
![](images/reliablecommunication2.png# w-70pct)

---
class: compact
# Direct Links

* In order to talk about TCP, we need to understand how "reliable" transmission can be implemented
* Issues to consider
  * Encoding -- how data are transmitted across a link
  * Framing -- how to send blocks of data across point-to-point link
  * Error detection -- how to determine if an error has occurred
  * Reliable transmission -- how to send data reliably across an error-prone link

---
class: compact
# Encoding

![](images/encoding.png# w-50pct fr)

* Signals travel between signalling components
* Bits flow between adaptors

![](images/space.png# w-30pct)
![](images/nrz-encoding.png# w-40pct)

---
class: compact
# Framing

![](images/framing.png# w-50pct fr)

We'll consider two different approaches:

1. Byte-oriented protocols (PPP)
    - framing is handled by inserting distinguished bytes in sequence to identify start/end of a frame
    - only suitable for encodings that are byte-oriented
2. Bit-oriented protocols (HDLC)
    - distinguished bit patterns inserted in data to identify start/end frame

Typically framing protocols also include basic error detection

---
class: compact
# Byte-Oriented Framing

There are two approaches:

1. Use special characters to mark the beginning and end of frame
2. Use a byte count at beginning of frame (this is more error prone)

IBM Binary Synchronous Communication (BISYNC)
* Mark beginning of frame with SYN character
* "Escape" SYN characters by preceding them with DLE character
* "Escape" DLE character with another DLS character.

---
class: compact
# Byte-Oriented Framing (PPP)

![](images/ppp.png# w-50pct fr)

* The start-of-text character (FLAG) is 01111110.  
* Protocol used for demultiplexing link (IP is distinguished)
* Checksum (really a CRC code) used to validate frame
* Payload is 1500 bytes by default.

---
class: compact
# Bit-oriented framing (HDLC)

![](images/hdlc.png# w-50pct fr)

* Not concerned with byte boundaries
* Distinguished sequence 01111110
* Uses "bit-stuffing" to break up sequences of  6 1's

---
class: compact
# Error Detection

There are many techniques.  Two common ones are
* Checksum
  * add up the words being transmitted and transmit the sum
  * relatively weak protection
* Cyclic redundancy code (CRC)
  * Uses a polynomial to generate error code
  * 32-bit CRC gives reasonably strong protection for common bit errors
  
---
class: compact
# Reliable Transmission

Assuming we can detect errors, we need a way to recover.

* The sender must get some form of acknowledgement from the receiver to determine if the frame arrived correctly
* The sender needs to decide when/if to retransmit a frame

---
class: compact
# Basic solution

* Receiver must acknowledge received good datagrams
* Sender must resend un-acknowledged datagrams after suitable "timeout" delay
* Datagrams have sequence numbers to ensure in-order, non-duplicated delivery

* Various protocols for managing this process
  * alternating-bit : two sequence numbers 0,1; only one datagram "in flight" at a time
  * window protocol : N sequence numbers, at most N-1 datagrams from consecutive sequence "in flight"
  * everything else is optimization (how acks/nacks are handled, etc.)
  * 
---
class: compact
# Stop and Wait

![](images/stop-wait.png# w-40pct fr)

Basic Protocol

* After sending a message/frame, sender waits for an acknowledgement before sending
the next frame.
* If no correct acknowledgement is received after a suitable "timeout" the sender retries.

Potential problems
* Sender retransmits too soon (d)
* Sender retransmits a message that was previously received correctly (c)

---
class: compact
# Alternating Bit Protocol

![](images/alternating-bit.png# w-30pct fr)

Stop and Wait can be made robust by adding a single bit sequence number

* Receiver can detect duplicate message
* Protocol cannot handle reordered messages !
* Protocol speed is limited by round-trip time !

---
class: compact
# "Pipelined" Protocols

**Pipelining** sender (through a sliding window) allows multiple datagrams in flight at once.
* Range of sequence numbers must be increased
* Buffering required at both sender and receiver

![](images/space.png# w-20pct)
![](images/windowprotocol.png# w-60pct)
---
class: compact
# Sliding Window Protocol

![](images/sliding-window1.png# w-30pct fr)

* By adding a range of sequence numbers, we can allow multiple
messages to be "in flight" simultaneously.  
* Receiver must buffer messages to ensure messages are received in order
* Sender must buffer messages until they are acknowledged

---
class: compact
# Sliding Window Algorithm (sender)

![](images/sender-window.png# w-40pct fr)
Sender variables
* LFS : last frame sent
* LAR : last frame acknowledged
* SWS : window size

```
LFS - LAR <= SWS
```

---
class: compact
# Sliding Window Algorithm (receiver)
![](images/receiver-window.png# w-40pct fr)

Sender variables
* LFR : last frame received
* LAF : last acknowledged frame
* SWS : window size

```
LAF - LFR <= SWS
```

---
class: compact
# Finite Sequence Numbers

In the absence of message reordering, the sequence number range need only be

```
SWS < (MaxSeqNum + 1)/2 
```

But, we need to ensure that reordered messages have a finite lifetime -- in the internet this is done with a variety of mechanisms.

---
class: compact
# Frame Order and Flow Control

Sliding window protocol serves three roles

1. Reliably deliver messages across an unreliable link
2. Preserve the order of message delivery
3. Flow control -- the acknowledgement messages provide a feedback mechanism; the receiver can delay sending acknowledgements.

---
class: compact
# TCP End-to-end Issues

* TCP using the sliding window protocol
  - This requires an explicit connection phase to setup the protocol
  - Because the round trip time (RTT) varies significantly (10ms-500ms or more), the window sie needs to adapt
  - Packets can be reordered and delayed, so there must be a maximum lifetime and the window can't wrap around too quickly

---
class: compact
# TCP Segments

![](images/transmit-segments.png# w-40pct fr)

* TCP is byte oriented, but the protocol sense contiguous sequences of bytes in "segments"
* The segments are reassembled into a byte sequence.

---
class: compact
# TCP Packet format

![](images/tcp-packet.png# w-30pct fr)

* SrcPort, DstPort -- ports for source, detination
* SequenceNum,Acknowledgement, AdvertisedWindow -- sliding window
  
  ![](images/space.png# w-30pct)
  ![](images/tcp-one-direction.png# w-40pct)

---
class: compact
# TCP Conversation

![](images/space.png# w-10pct)
![](images/tcp-conversation.png#w w-80pct)

---
class: compact
# TCP Connection Establishment

![](images/three-way-handshake.png# w-50pct fr)

* TCP uses a "three-way" handshake to establish the connection and initialize the windows.
* Sequence numbers for two directions of data are separate and chosen "randomly"

---
class: compact
# TCP Connection Protocol is Complicated

![](images/space.png# w-30pct)
![](images/tcp-connection-states.png# w-40pct)

---
class: compact
# Summary

* Getting Processes to Communicate
* Simple Demultiplexor (UDP)
* Reliable Byte Stream (TCP)
  * Framing
  * Error Detection
  * Reliable Data Delivery
* TCP Connections
* Acknowledgement 
  * Content and images from http://book.systemsapproach.org
  * Content and images from "Computer Networking: A Top Down Approach" 7th edition by Jim Kurose and Keith Ross.