COMP211 (Networks)

With a wireless network the arriving mobile must:

• Associate with the access point.
• Authenticate to the network.

802.11 Authentication & Encryption

1. Discovery of Security Capabilities:
   1. AP advertises its presence, forms of authentication and encryption provided.
   2. Device requests specific forms of authentication and encryption desired.

   Although the device and AP are already exchanging messages the device is not yet authenticated and does not have encryption keys.

2. Mutual Authentication & Shared Symmetric Key Derivation:
   1. AS and the mobile already have a shared common secret (the password).
   2. AS and the mobile use the shared secret, nonces (to prevent replay attacks) and cryptographic hashing (to ensure message integrity) to authenticate each other.
   3. AS and the mobile derive a symmetric session key.

   AS is the authentication server (could be combined into the AP).

3. Shared Symmetric Session Key Distribution (for AES encryption):
   1. Same key derived at the mobile and AS.
   2. The AS informs the AP of the shared symmetric session.
4. Encrypted communication between the mobile and remote host via the AP.

This protocol is deployed above the transport layer and provides:

• Confidentiality - Via Symmetric encryption.
• Integrity - Via cryptography hashing.
• Authentication - Via public key cryptography.

TLS

TLS is implemented in the application layer alongside HTTP.

TLS 1.3 Cipher Suite

TLS 1.3 allows for the following choices:

• 4 ciphers based on AES.
• 1 CHACHA20 (stream cipher).

It requires Diffie-Hellman (DH) for key exchange as RSA is compromised.

Uses SHA (256 or 384) as a cryptographic hash function.

Server Authentication

Public keys for trusted CAs included in the browser/OS:

1. Browser requests the server certificate, issued by a trusted CA.
2. Browser checks the certificate and extracts the public key of the server.

Encrypted TLS Session

1. Browser generate symmetric session key, encrypts is with the server’s public key and send the encrypted key to the server.
2. Using its private key, the server decrypts the session key.
3. All data sent into the TCP socket (by the client and server) is encrypted with the session key.

Confidentiality

If Alice wants to send a confidential email to Bob she can do the following:

1. Generate a random symmetric private key $K_S$.
2. Encrypt the message with $K_S$ (for efficiency).
3. Also encrypt $K_S$ with Bob’s public key.
4. Send both $K_S(m)$ and $K^+_B(K_S)$ to Bob.

Bob will then:

1. Use his privaet key to decrypt and recover $K_S$.
2. Use $K_S$ to decrypt $K_S(m)$ to recover $m$.

Integrity & Authentication

If Alice want to send $m$ to Bob, with message integrity and authentication (no encryption) we can do the following:

1. Digitally sign the hash of her message with her private key, providing integrity and authentication.
2. Send the signature and the message in the clear.

Bob can then verify the message using the technique covered in the Integrity lecture.

Confidentiality, Integrity & Authentication

To do this:

1. Complete the integrity & authentication section.
2. Pass the signature and message to the confidentiality section.
3. Send the message.

This uses three keys:

• Alice’s private key: $K^-_A$.
• Bob’s public key: $K^+_B$.
• A session symmetric key: $K_S$.

PGP (Pretty Good Privacy)

This is pretty much the same as the last method. It provides:

• Secrecy
• Authentication
• Integrity

Digital Signatures

Digital signatures should be:

• Verification of a document creator.
• Verifiable and non-forgettable.
  • Must have only been created by the document creator.

We can complete a simple digital signature by encrypting the document with your private key $K^-_B$.

This is computationally expensive, especially as message length gets longer.

Message Digests

This is a fixed-length, easy to compute, hash of a document:

• Apply a hash function $H$ to $m$ to get a fixed size message digest $H(m)$.

graph LR
m --> H --> Hm["H(m)"]

Hash functions have the following properties:

• Many to One
• Produce fixed size message digests.

• Given a hash $x$ it should be computationally infeasible to find $m$ such that $x=H(m)$.

  It should be infeasible to find another message with the same hash.

Digital Signature with Message Digest

We can use message digests to compute the digital signature quicker for long files.

1. Bob sends a digitally signed message:

    graph
    m[Large message m] --> H[H - Hash function] --> Hm["H(m)"] --> ds["Digital Signature"]
    K-B --> ds --> dse[Encrypted Message Digest] --> +
    m --> + --> out
   

2. Alice verifies the signature and the integrity of the digitally signed message:

    graph
    in --> m[Large message m] & dse[Encrypted Message Digest]
    m --> H[H - Hash function] --> Hm["H(m)"] --> =
    dse --> ds["Digital Signature"] --> Hm2["H(m)"] --> =
    K+B --> ds
   

Public Key Certification Authorities (CA)

This method fixes the man in the middle attack issue from using plain public key authentication.

• A CA binds a public key to a particular entity $E$.
• The entity registers its public key with CE and provides proof of identity to the CA:
  • The CA creates a certificate binding the identity $E$ to $E$’s public key.
  • Certificate containing $E$’s public key digitally signed by the CA.

Creating Certificates

graph LR
bp[Bob's public key] --> ds[Digital Signature] & CA
bi[Bob's identifying information] --> CA
CA -->|CA's private key| ds
ds --> c[Certificate for Bob's public key, signed by CA]

Verifying Certificates

graph LR
cert["K-CA(KB+)"] --> ds[Digital Signature]
K+CA --> ds
ds --> K+B

In order for authentication to be secure you need to ensure that the protocol avoids replay attacks:

• This is where an attacker replays a recorded packet and is able to authenticate as you.

Nonce

To avoid this the server (Bob) can send a nonce (number used once) $R$ which Alice can manipulate and send back:

• This avoids the issue where an attacker can replay Alice’s messages as they will be different every time.

Symmetric Key Authentication

Provided that we have a shared key with the server we can complete the following actions:

sequenceDiagram
Alice ->> Bob: I am Alice.
Bob ->> Alice: R
Alice ->> Bob: K_{A-B}(R)

Public Key Authentication

To complete this with public key cryptography, we can do the following:

sequenceDiagram
Alice ->> Bob: I am Alice.
Bob ->> Alice: R
Alice ->> Bob: K-A(R)
Bob ->> Alice: Send me your public key.
Alice ->> Bob: K+A

Bob can the compute:

Therefore, the message must have been encrypted with Alice’s private key $K^-_A$.

Man in the Middle Attack

If a bad actor (Trudy) poses as Alice to Bob and as Bob to Alice. They can manipulate the messages between the two parties:

• Trudy can then encrypt the message back to the server with her own private key $K^-_T$.
• Trudy can then send her public key $K^+_T$ to the server.

This can be made completely transparent to Bob and Alice.

Public key cryptography is only secure if the public key of a person is correct.

This method has two keys:

• Public key:
  • Known to all.
  • Used for encryption.
• Private key:
  • Only known to the receiver.
  • Used for description.

graph LR
Alice -->|m| ea[Encryption Algorithm]
bp[Bob's Public Key] -->|KB+| ea
ea -->|"KB+(m)"| da[Decryption Algorithm]
bpr[Bob's Private Key] -->|KB-| da
da -->|"m"| Bob

The following notation is used:

• $K^+_B$ - Bob’s Public Key
• $K^-_B$ - Bob’s Private Key
• $K^+_B(m)$ - Ciphertext

The plaintext is decrypted by completing the following operation:

Requirements

For public key cryptography to work you need the following:

• $K^-_B(\cdot)$ and $K^+_B(\cdot)$ such that:

  \[m = K^-_B(K^+_B(m))\]

• Given a public key $K^+_B$, it should be computationally infeasible to determine the private key $K^-_B$.

Modular Arithmetic

$x\mod n=$ remainder of $x$ when we divide by $n$. This has the following properties:

Therefore:

RSA (Rivest, Shamir, Adelson Algorithm)

We consider that the message can be expressed as a bit pattern that can be converted to a decimal number.

Creating Public/Private Key Pair

1. Choose two large prime numbers $p,q$ (could be 1024 bits each).
2. Compute $n=pq,z=(p-1)(q-1)$.

3. Choose $e$ (with $e<n$) that has no common factors with $z$.

   $e,z$ are relatively prime.

   Prime factor decomposition can be useful so that you avoid those primes.

4. Choose $d$ such that $ed-1$ is exactly divisible by $z$.

   This is the same as $ed\bmod z=1$.

5. The public key is $(n,e)$ and the private key is $(n,d)$.

Encryption & Decryption

Given $(n,e)$ and $(n,d)$ as computed above:

1. To encrypt message $m$ ($<n$), compute:

   \[c = m^e\bmod n\]

2. To decrypt the received bit pattern, $c$, compute:

   \[m = c^d\mod n\]

Therefore:

RSA Proof

We must show that $c^d\bmod n=m$ and $c=m^e\bmod n$.

We can use the fact that for any $x$ and $y$:

where $n=pq$ and $z=(p-1)(q-1)$.

Therefore:

There is also an additional property of RSA that we can prove:

Using the public key and then the private key is the same as using the keys the other way around.

This can be proved like so:

Session Keys

DES is at least 100 times faster than RSA, therefore we:

1. Use public key cryptography to establish a secure connection.
2. Establish a second symmetric session key ($K_S$) for encrypting data.

In symmetric key cryptography both parties share the same key:

graph LR
Alice -->|plaintext| ea[Encryption Algorithm]
ka[Shared Encryption Key] -->|KS| ea
ea -->|"ciphertext (KS(m))"| da[Decryption Algorithm]
kb[Shared Decryption Key] -->|KS| da
da -->|plaintext| Bob

Symmetric Ciphers

The following are examples of symmetric ciphers:

• Caesar Cipher (ROT13)
  • All letters in the alphabet are rotated.
  • Only 26 keys.
• Monoalphabetic Cipher
  • Letters are substituted for other letters in any order.
  • 26! combinations.
  • Can be cracked using statistical/lexical analysis.
• Polyalphabetic Encryption
  • There is a set of $n$ substitution ciphers: $M_1,M_2,\ldots,M_n$.
  • They are used in a cycling pattern (like enigma).

  The encryption key for this encryption are the $n$ substitution ciphers and the cyclic pattern.

Block Ciphers

The message to be encrypted is processed in blocks of $k$ bits:

• A 1 to 1 mapping is used to map $k$-bit block of plaintext to $k$-bit block of ciphertext.
• For a mapping of $k=n$ there are $2^k!$ mappings.

The longer the block size the more secure the cipher is.

There are too many mappings to be held in memory for a 64 bit block length. As a result we:

1. Split the input into 8 bit blocks.
2. Encrypt the 8 bit blocks as above.
3. Shuffle the 8 bit blocks to produce the final 64 bit output.
4. Loop for $n$ rounds.
   • Changing a single bit in the input changes more in the output.

Cipher Block Chaining

When encrypting large messages, if two 64 bit blocks contain the same data they will produce the same output. This can allow for analytical description, which we don’t want.

Cipher block chaining XORs the $i^{\text{th}}$ input block, $m(i)$, with previous block of cipher text $c(i-1)$:

• The first block to be sent is the initialisation vector $c(0)$, which is just a random number in plaintext.

graph LR
mi["m(i)"] & ci1["c(i - 1)"] --> XOR --> bc[Block Cipher] --> ci["c(i)"]
ci -.-> ci1
ci -->|send| a[ ]

DES (Data Encryption Standard)

• 56 bit Symmetric Key
• 64 bit Plaintext Input
• Block cipher with block chaining.

This can be decrypted with brute force in less than a day.

• Can be made more secure with 3DES (encrypting 3 times).
  • Only increases brute force time linearly.

AES (Advances Encryption Standard

• Processes data in 128 bit blocks.
• 128, 192 or 256 bit keys.

Brute force attacks would take 149 trillion years, due to the large key-space.

Types of Attacks

There are two general classes of network attacks:

• Passive Attack

  Hard to detect.

  • Eavesdropping - Packet sniffing.
  • Impersonation - Spoofing source addresses.

• Active Attacks

  • Man-in-the-Middle Attacks - Actively changing messages on the connection.
  • Hijacking - Taking over an existing connection.
  • Denial of Service - Overloading resources.

Types of Network Security

• Confidentiality through encryption.
• Authentication
• Message Integrity
• Access & Availability

Cryptography Notation

graph LR
Alice -->|plaintext| ea[Encryption Algorithm]
ka[KA Alice's Encryption Key] -->|kA| ea
ea -->|"ciphertext (only publicly visible part)"| da[Decryption Algorithm]
kb[Bob's Decryption Key] -->|kB| da
da -->|plaintext| Bob

In this system we use the following notation:

• $m$ - Plaintext Message.

• $K_A(m)$ - Ciphertext, encrypted with $K_A$

  \[m=K_B(K_A(m))\]

Guided Transmission Media

In addition to the following you can also have transfer through physical media. This can give the best transfer rate (especially for large amounts of data).

• Twisted Pair
  • You can twist the cables more to give better cross talk.
• Coaxial Cable - A copper core surrounded by a mesh sheath.
• Fibre Optics - Light travels through a fibre via total internal reflection.

Unguided Transmission Media

We can use various bandwidths of the electromagnetic spectrum to transmit data. Different frequency bands have different properties:

• Radio Transmission
  • In VLF, LF and MF bands radio waves follow the curvature of the earth.
  • The HF band can bounce off the ionosphere.

Communication Satellites

Satellites in different height orbits have different communication properties:

Satellites operate on the following bands:

The channel capacity can be defined in two different ways:

• Data Rate:
  • In bits per second.
  • Rate at which data can be communicated.
• Bandwidth:
  • The frequency width of the transmitted signal.
  • In cycles per second or Hz.
  • Constrained by the transmitter and medium.

Nyquist Bandwidth

If the bandwidth is $B$, then the highest signal transmission (baud) rate is $2B$:

• For a binary signal the data rate supported by $B$ Hz is $2B$ bps.

This can be increased by using $M$ signal states:

• Each state encodes multiple bits.

• With no noise the maximum data rate is:

  \[2B\log_2(M)\]

  This is what QAM techniques use to transmit more bits per state.

  To find the number of bits from the number of states $M$ you can then calculate:

  \[\log_2(M)\]

  This is as we can encode the states in binary.

Shannon’s Capacity Formula

The amount of thermal noise present is measured by the ratio of signal power to noise power.

This is called the signal to noise ratio: $\frac SN$.

The ratio itself is not usually quoted but is represented is dB:

Therefore for $\frac SN=100$ then this 20 dB.

Typical analogue voice telephone usually gives 30dB of signal to nose.

Shannon’s Law

The maximum rate of a noisy channel with bandwidth $B$ and signal to noise ratio of $\frac SN$ is:

Shannon’s Law Example

For a channel bandwidth of 3.1 KHz and a signal to noise ratio of 30 dB ($\frac SN=1000$), the maximum bits per second is:

We can combine this with the Nyquist Bandwidth formula to find the maximum data rate of a noisy channel with multiple signal states.

Attenuation

The received signal must be sufficiently higher than noise to be received without error.

• Signal amplitude decreases with distance.
• Depends on the medium.
• Attenuation is an increasing function of frequency.

Delay Distortion

This occurs as the velocity of propagation of a signal through a guided medium varies with frequency:

• Only in guided media.
• Propagation velocity varies with frequency.
  • Different parts of the spectrum arrive at different times.

Noise

This is additional signals inserted between the transmitter and receiver. It could be due to:

• Thermal
  • Due to the thermal agitation of elections.
  • Uniformly distributed
  • White noise.
• Inter-modulation
  • Signals that are the sum and difference of the original frequencies sharing a medium.
• Cross-talk
  • A signal from one line is picked up on another.
• Impulse
  • Irregular pulses or spikes caused by external electromagnetic interference.
  • Short Duration
  • High Amplitude

Sine Waves

Sine waves can be made using the following function:

Where:

• $A$ - Amplitude
• $f$ - Frequency
• $t$ - Time
• $\phi$ - Phase
• $T$ - Period ($\frac1f$)

Any signal can be made of many sine components.

Frequency Domain Representation

• You can plot the frequencies of a periodic signal on a bar graph to represent the signal. (Discrete)
• Aperiodic signals have continuous frequency domain representations.

If a signal has a spectrum with a zero frequency component (direct current), this is used as a voltage offset.

Bandwidth

The bandwidth of a signal is the upper and lower limit of the frequencies that can be represented in the medium.

A higher bandwidth gives more definition to analogue signals.

Advantages of Digital

• Digital is lower cost.
• Data integrity is preserved over longer distances with digital data.
  • Repeaters can amplify the data without including line noise.
• High degree of multiplexing is easier with digital techniques.
  • Increases utilisation.
• Data is easier to encrypt.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

The link layer concerns the links that connect various nodes (hosts and routers) on a network. The link layer only needs to transfer a frame from a node to an adjacent node.

Services

The link layer provides the following services:

• Datagram encapsulated in frames with a header and trailer.
• Channel access for shared mediums.
• MAC addresses in frame headers identify source and destination.
• Reliable delivery between adjacent nodes:
  • Used on links with high error rates.
• Flow Control
• Error Detection
• Error Correction
  • The receiver corrects errors without re-transmission.

Hardware Implementation

The link layer is implemented in the network interface. This can be:

• NIC (Network Interface Card)
• Built-in network cards.

Network interfaces also implement the physical layer too as they physically connect to the network.

graph
subgraph computer
CPU --- Bus
Bus --- Memory
Bus --- Controller
Controller --- Physical
subgraph NIC
Controller
Physical
end
end
Physical --- Network

Error Detection

Error detection isn’t always 100% reliable:

• Larger check-sums yield better detection and correction

Parity Checking

Single bit parity can detect single bit errors:

Two dimensional bit parity can detect and correct single bit errors:

• The right most column and bottom row are the parity bits.
• The parity of a row or column is the single bit sum of that row or column.
• The bottom right parity digit can be used as singe bit parity for the parity bits.

Cyclic Redundancy Check (CRC)

This is a more powerful error-detection coding:

• $D$ - Data bits given as a binary number.

• $G$ - Bit pattern (generator), or $r+1$ bits.

  One bit longer than the number of CRC bits.

We need to choose $r$ CRC bits, $R$ such that $<D,R>$ exactly divisible by $G$ (mod 2):

• Receiver knows $G$, divides $<D,G>$ by $G$. If non-zero remainder then an error is detected.
• Can detect all burst errors less than $r+1$ bits.

This method is used in Ethernet and WiFi.

CRC Example

Before we divide by the generator $G$ we shift the data $D$ to the left by $r$ bits, or the length of the generator - 1:

To calculate this we do modulo 2 division on data using the generator completing an XOR in each step:

Multiple Access Protocols

Broadcast links are a shared link such as WiFi. If two or nodes transmit at the same time then there is interference:

• Collision - If a node receives two or more signals at the same time.

Ideally, multiple access protocols are distributed algorithms that have the following properties:

• Determine how nodes share the channel.
  • Determine when nodes can transmit.
• Communication about channel sharing must use the channel.
  • No out of band channel coordination is allowed.
• When one node wants to transmit, it can do so at the line speed.
• When multiple nodes transmit, they can do so at an equal divisor of the line speed.
• Fully decentralised:
  • No special nodes.
  • No synchronisation of clocks.

There are three broad classes of multiple access channel protocols:

• Channel Partitioning
  • Divide channel into smaller pieces (time, frequency, code).
  • Allocate piece to node for exclusive use.
• Random Access
  • Channel not divided, allowing collisions.
  • Recover from collisions.
• Taking Turns
  • Nodes take turns, but nodes with more to send can take longer turns.

Time Division Multiple Access (TDMA)

• Access to channel in rounds.
• Each station gets a fixed length slot (length = packet transmission time) in each round.
• Unused slots go idle.

Frequency Division Multiple Access (FDMA)

• Channel spectrum divided into frequency bands.
• Each station assigned fixed frequency bands.
• Unused transmission time in frequency bands go idle.

Random Access Protocols

Slotted ALOHA

Slotted ALOHA has the following assumptions:

• All frames are the same size.
• Time is divided into equal size slots (time to transmit 1 frame).
• Nodes start to transmit only slot beginning.
• Nodes are synchronised.
• If 2 or more nodes transmit in slot, all nodes detect collision.

It operates like so:

1. When node obtains fresh frame transmit in the next slot.
   • If no collision - Node can send new frame in next slot.

   • If collision - Node re-transmits frame in each subsequent slot with probability $p$ until success.

     Randomisation is included such that different nodes don’t re-transmit at the same time.

Carrier Sense Multiple Access (CSMA)

The simple implementation listens before transmit:

• If channel is sensed idle - Transmit entire frame.
• If channel sensed busy - Defer transmission.

Collision detection (CSMA/CD) is implemented like so:

• Collisions detected within short time.
• Colliding transmissions aborted, reducing channel wastage.
  • You can abort before the whole frame is transmitted.
• Collision detection is difficult in wireless when you can’t listen to the entire broadcast area or you transmit and receive on the same areal.

Propagation delay can cause collisions, as you can start transmitting before you have heard an existing transmission.

Ethernet CSMA/CD Algorithm

1. NIC receives datagram from network layer, creates frame.
2. If NIC senses channel:
   • If idle - Start frame transmission.
   • If busy - Wait until channel idle, then re-transmit.
3. If NIC transmits entire frame without collision, NIC is done with frame.
4. If NIC detects another transmission while sending - Abort send and send jam signal.
5. After aborting, NIC enters binary exponential backoff:
   • After $m^\text{th}$ collision, NIC chooses $K$ at random, from $\{0,1,2,\ldots,2^{m}-1\}$. NIC waits $K\times512$ bit times, returns to step 2.
   • More collisions result in higher backoff interval.

Taking Turns Protocols

Polling

• Master node invites other nodes to transmit in turn.
• Typically used with dumb devices.

This method can the following issues:

• Polling Overhead
• Latency
• Single point of failure.

Token Passing

• Control token passed from one node to the next sequentially.
• Node with token can transmit.

This method can the following issues:

• Token Overhead
• Latency
• Single point of failure (token)

LANs

MAC Addresses

MAC addresses are used to get a from from one interface to another physically connected interface. They are a 48-bits long and are generally burned into the NIC ROM:

• They are designed to be unique.
  • Each manufacturer buys a portion of the MAC address space from the IEEE.
• MAC addresses are portable (with the NIC) from one LAN to another.

Address Resolution Protocol (ARP)

Each IP node on a LAN has a table that tracks IP to MAC address mappings:

TTL (time to live) is typically set to 20 mins.

Suppose that $A$ wants to find $B$’s MAC address:

1. $A$ broadcasts ARP query, containing $B$’s IP address:
   • Destination MAC address is FF-FF-FF-FF-FF-FF.
   • All nodes on LAN receive ARP query.

    Source MAC: 71-65-F7-2B-08-53
    Source IP: 137.196.7.23
    Target IP address: 137.196.7.14
   

2. $B$ will send its MAC address back to $A$:

    Target IP address: 137.196.7.14
    Target MAC address: 58-23-D7-FA-20-B0
   

3. $A$ receives $B$’s reply and logs it in its local ARP table:

   IP Address	MAC Address	TTL
   137.196.7.14	58-23-D7-FA-20-B0	500

Ethernet

Ethernet can have the following topologies:

• Bus - All noes in the same collision domain.
• Switched:
  • Active link-layer 2 switch in the centre.
  • Each spoke runs a separate Ethernet protocol.

Ethernet Frames

The sending interface encapsulates the payload in an Ethernet frame:

graph
subgraph frame
preamble
destAddress
sourceAddress
type
data
CRC
end

• Preamble - used to synchronise the receiver and sender clock rates. 7 bytes of 10101010 followed by one byte of 10101011.
• Addresses - MAC addresses. If an adaptor receives a frame with it’s own address or a broadcast it is passed up to the network layer. Otherwise the frame is discarded.
• Type - Indicates higher layer protocol (IP, Novell, IPX, AppleTalk).
• CRC - If errors are detected the frame is dropped.

Ethernet Properties

• Connection-less - No handshaking between sending and receiving NICs.
• Unreliable - Receiving NIC doesn’t send ACKs to the sending NIC.
• Ethernet MAC Protocol - Un-slotted CSMA/CD with binary backoff.

There are many different 802.3 Ethernet standards. They define:

• Different speeds.
• Different physical layer media.

Switches

An Ethernet switch is a link-layer device that takes and active role:

• Store and forward Ethernet frames.
• Examine incoming frame’s MAC address and selectively forward frames to one-or-more outgoing links. When the frame is to be forwarded on segment it uses CSMA/CD to access the segment.

The host is unaware of switches as they are transparent.

The difference between switches and routers are that switches are layer 2 devices and routers are layer 3.

Multiple Simultaneous Transmissions

When there are multiple transmissions:

• Each device can operate at full link speed.
• Transmissions to all different interfaces can happen simultaneously.
• Transmissions to the same interface will get buffered.

Switch Tables

These record which hosts can be reached through each interface. They are not managed by a routing protocol.

• When a node sends a frame then the switch records the senders MAC address and interface.
• When the destination is unknown then it floods all other interfaces with the frame.
• If the destination address is in the switch table then the frame is sent on that interface.

Wireless Links & WLAN

Wireless links have the following characteristics compared to wired links:

• Decreased Signal Strength - Radio signal attenuates as it propagates through matter (path loss).
• Interference - Wireless network frequencies can be shared by many devices.
• Multi-path Propagation - Radio signals can reflect off objects and arrive at the destination at slightly different times.

IEEE 802.11 Wireless LAN

This standard includes WiFi and all use CSMA/CA for multiple access and have base station and ad-hoc variants.

Multiple Access (CSMA/CA)

IEEE 802.11 implements the following to facilitate multiple access:

• CSMA - Sense before transmitting to not collide with existing transmissions.
• No collisions detection. Instead collision avoidance (CSMA/CA) is implemented.
  • Collision detection is impossible in wireless settings as you can’t listen to the whole network from one device.

802.11 Sender

We must first reserve the channel using small reservation packets:

1. Sender transmits a small request to send (RTS) packet to the base-station using CSMA.
   • These may collide but they are short.
2. Base station broadcasts a clear to send (CTS) in response to the RTS.
3. CTS is heard by all nodes:
   • Sender continues to send data.
   • Other stations defer transmissions.

To send the data we complete the following:

1. If we sense the channel is idle for DIFS (a set amount of time to sense) then transmit the entire frame (no CD).
2. If we sense the channel is busy then start random backoff timer. Transmit when timer expires if the channel is idle.
3. If no ACK increase random backoff interval, repeat 2.

802.11 Receiver

1. If frame received OK, return ACK after SIFS (short time after receiving).

RTS-CTS Exchange

sequenceDiagram
par
A ->> AP:RTS(A)
and
note over AP: Reservation collision.
and
B ->> AP:RTS(B)
end
A ->> AP:RTS(A)
par
AP ->> A:CTS(A)
and
AP ->> B:CTS(A)
end
note over B:Defer until ACK(A)
A ->> AP:Data(A)
par
AP ->> A:ACK(A)
and
AP ->> B:ACK(A)
end

Blocks called par happen in parallel.

As this is a shared medium, $A$ and $B$ have the chance of seeing each other’s messages (albeit with some propagation delay). The only node that you are guaranteed to receive from is the AP.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Routing Algorithms

Routing algorithms choose a sequence of routers for a packet to traverse from source to destination.

We can define the cost of a hop by using link costs:

graph LR
subgraph G
u ---|2| v
v ---|2| x
u ---|1| x
v ---|3| w
x ---|3| w
w ---|1| y
x ---|1| y
w ---|5| z
y ---|2| z
end

This graph can be represented as:

Where $N$ is the set of routers:

and $E$ is the set of links:

Classifying Routing Algorithms

Algorithms can have some the following conflicting classifications:

• Global - All routers have complete topology and link cost info.
  • Link state algorithms.

  or

• Decentralised - Iterative process of computation using an exchange of info with neighbours.
  • Routers initially only know link costs to attached neighbours.
  • Distance vector algorithms.

• Static - Routes change slowly over time.

  or

• Dynamic - Routes change more quickly.

Intra-AS Routing (OSPF)

In this scenario you want a routing algorithm that has the best performance.

Autonomous systems (AS) are a single domain:

• All router in an AS must run the same intra-domain protocol.
• Routers in different AS may run any protocol
• Gateway routers link the edge of an AS to the gateways of other ASs.

Common intra-AS routing protocols are: RIP, EIDRIP, OSPF (essentially identical to IS-IS).

OSPF (Open Shortest Path First) Routing

This is a common and open intra-AS routing protocol.

This is a classic link-state protocol:

1. Each router floods OSPF link-state advertisements (directly over IP rather than using TCP/UDP) to all other routers in the entire AS.
2. Multiple link costs metrics possible:
   • Bandwidth
   • Delay
3. Each router has a full topology, uses Dijkstra’s algorithm to compute the forwarding table.

All OSPF messages are authenticated to prevent malicious intrusion.

Hierarchical OSPF

This allows for a two-level hierarchy with a:

• Backbone
  • Localised around boundary routers.
• Local Area
  • Include one router from the backbone and a section of the internal network.

nwdiag {
	group a {
		color = "pink" 
		b1
		a11
		a12
		a13
	}
	group b {
		color = "lightblue"
		b2
		a21
		a22
		a23
	}
	group c {
		color = "lightgreen"
		b3
		a31
		a32
		a33
	}
	internet -- boundary
	network backbone {
	boundary
		b1
		b2
		b3
	}
	network area1 {
		b1
		a11
		a12
		a13
	}
	network area2 {
		b2
		a21
		a22
		a23
	}
	network area3 {
		b3
		a31
		a32
		a33
	}
}

Link state advertisements are flooded only in an area or the backbone. This limits traffic on large networks:

• Each node has a detailed area topology. It only knows the direction to reach other destinations.

Inter-AS Routing (BGP)

In this scenario policy is more important than performance as the data is not internal.

Boarder gateway protocol (BGP) is the de-facto standard inter-domain routing protocol. BGP provides each AS a means to:

• eBGP - Obtain subnet reachability information from neighbouring ASes.
• iBGP - Propagate reachability information to all AS-internal routers.
• Determine good routes to other networks based on reachability information and policy.

nwdiag {
	group {
		1a
		1b
		1c
		1d
	}
	group {
		2a
		2b
		2c
		2d
	}
	group {
		3a
		3b
		3c
		3d
	}
	network peering1 {
		address = "eBGP"
		color = "pink"
		1c
		2a
	}
	network peering2{
		address = "eBGP"
		color = "pink"
		2c
		3a
	}
	network AS1 {
		address = "iBGP"
		color = "lightblue"
		1a
		1b
		1c
		1d
	}
	network AS2 {
		address = "iBGP"
		color = "lightblue"
		2a
		2b
		2c
		2d
	}
	network AS3 {
		address = "iBGP"
		color = "lightblue"
		3a
		3b
		3c
		3d
	}
}

Local routers run iBGP and gateway routers run both iBGP and eBGP.

BGP Paths

If an AS advertises a path to another AS then it promises that it can forward datagrams to that AS.

A BGP advertised routes contains two parts:

• Prefix - Destination being advertised.
• Attributes
  • AS-PATH - List of ASes through which prefix advertisement has passed.
  • NEXT-HOP - Indicates specific internal-AS router to next to next-hop AS.

You can also have policy-based routing:

• Gateway receiving route advertisement uses its own import policy to decide whether to accept or decline an incoming path.
  • Never route through AS$x$.
• AS policy also determines whether to advertise a path to other neighbouring ASes.

BGP Route Selection

A router may learn about more than one route to a destination AS. It will select a route based on:

1. Local preference value attribute (policy decision).
2. Shortest AS-PATH.
3. Closest NEXT-HOP router (hot potato routing).
4. Additional criteria.

SDN Control Plane

This aims to put less control with proprietary routers, concerning the routing tables, and instead put that load on centralised controllers. This can provide:

• Easier network management.
• Table based forwarding and programming routers with routing tables (OpenFlow).
• Open implementations of the control plane can be used.
• Traffic routing is easier.

Implementation

SDN uses the following hardware:

• Fast, simple switches that have support for communicating with a controller.
• SDN controller that has the following components:
  • Interface layer to network control apps (abstractions API).
  • Network-wide state management that holds the state of networks links, switches, services on a distributed database.
  • Communication between the SDN controller and the controlled switched.
  • Can be implemented as a distributed system for performance and stability.

The SDN applications can be unbundled, in that they are distinct from the routing vendor or SDN controller.

OpenFlow Protocol

• Operates between the controller and the switch.
• TCP is used to exchange messages with optional encryption.

There are three classes of OpenFlow messages:

• Controller to switch.
• Asynchronous messages from the switch to the controller.
  • A link has broken or a suspect packet is received.
• Symmetric messages from the switch to the controller.
  • To check liveness.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Network Layer

The network layer completes two functions:

• Forwarding - Moving packets from a router’s input link to the appropriate router output link.
• Routing - Determining the route taken by packets from source to destination.

Data Plane

This is a local, per-router, function. It determines how a datagram arriving on a routers input port is forwarded to the router output port.

Control Plane

This is a network wide logic. It determines how data is routed across the network.

Per-Router Control Plane

This in an individual routing algorithm that is implemented in each router to interact in the control plane:

• Each router has a table that is can use to forward packets towards its detonation.
• The tables are generated by a distributed algorithm, running on the routers.

Software-Defined Networking (SDN) Control Plane

A remote controller computes and installs forwarding tables in routers.

Routers

Routers generally have the following structure:

flowchart
rp --> lfq
subgraph rip[Router Input Ports]
lt[Line Termination] --> llp[Link Layer Protocol] --> lfq[Lookup, Forwarding & Queuing]
end
rip --> hssf[High-Speed Switching Fabric]
hssf --> rop
subgraph rop[Router Output Ports]
olfq[Datagram Buffer] --> ollp[Link Layer Protocol] --> olt[Line Termination] 
end
rp[Router Processing] <--> hssf
subgraph cp["Control Plane (milliseconds)"]
rp
end
subgraph dp["Data Plane (nanoseconds)"]
rip
hssf
rop
end

The ports are structured as follows:

• Line Termination - Physical layer.
• Link Layer - Ethernet.
• Lookup, Forwarding & Queuing - Decentralised switching using the header field values to lookup the output port using a forwarding table.
  • This should be completed at line speed.
  • Input port queuing can be used if datagrams arrive faster than forwarding rate into the switch fabric.
  • Head of the line (HOL) blocking - A datagram at the front of the queue prevents others in the queue from moving forward.
    • If too many packets are buffered then they can be dropped and lost.

Longest Prefix Matching

When looking for forwarding table entry for a given destination address, use the longest address prefix that matches the destination address.

• 10.24.0.2 would go on interface 1 as it matches more of 10.24.0.0/24 than 10.24.0.0/16.

The number after the slash is the number of bits that define the subnet.

Switching Fabrics

You can switch using the following topologies:

• Switching Via Memory - The packet is copied to the system memory and then the output port.
  • This crosses the system bus twice.
  • Limited by the memory bandwidth.
• Switching Via Bus - The input port memory is connected directly to the output port memory.
  • Switching speed limited by bus bandwidth.
  • One packet can be on the bus at a time.
• Switching Via Interconnection Network - A grid of switched interconnects are used that can be used to reduce contention between the input ports.
  • You can use multiple stages of switches to send multiple packets at once.

Internet Protocol (IP)

Datagram Format

The IPv4 datagram is laid out like so:

Fragmentation

The link layer can have a maximum transfer unit (MTU). As a result, the network layer, IP datagram must be fragmented into several that must be reassembled at the destination.

For example, with an MTU of 1500 bytes the following datagram:

Would be split into the following fragments:

Each fragment has it’s own 20 byte header, which means that the total data transferred in this example is 40 bytes more than using a single datagram.

The offset is the number of bytes offset divided by 8. This means the data can only be fragmented every 8 bytes.

Addressing

Each network interface has an assigned IP address.

• Subnets
  • Subnets are a group of devices that can access each-other without passing through a router.
  • Devices in the same subnet have the same high-order bits.
  • Subnet Mask - Defines the number of bits that make up the subnet part of the IP address: 192.168.0.1/24.

CIDR

Classless inter-domain routing is a method of defining the subnet and host part of an IP address:

DHCP

There are two ways of getting an IP address on a network:

• Setting a non-conflicting IP address manually.
• Dynamic host configuration protocol from a server on the network you are connecting to.
  • Allows for reuse of inactive addresses.
  • Can renew a lease on address in use.

sequenceDiagram
Client ->> Server:DHCP Discover
Server ->> Client:DHCP Offer (Send IP address.)
note left of Client: The above steps can be skipped if a previous IP has been assigned.
Client ->> Server:DHCP Request (Send IP address back.)
Server ->> Client:DHCP ACK

You can send broadcast traffic on a network by sending to 255.255.255.255. Port 67 is used for DHCP.

All of this is done as broadcast so multiple DHCP servers on the same network know what IP addresses are used.

DHCP can also offer the following:

• Address of first-hop router.
• Name and IP address of DNS server.
• Network mask.

Network Address Translation

All device in a local network share just one IPv4 address as far as the outside world is concerned.

nwdiag {
network ISP {
Modem [address = "138.76.29.7"];
}
network Local {
address = "10.0.0.0/24"
Modem [address = "10.0.0.1"];
Device1 [address = "10.0.0.2"];
Device2 [address = "10.0.0.3"];
Device3 [address = "10.0.0.4"];
}

• All datagrams leaving have the same source NAT IP (138.76.29.7) but different source port numbers.
• Datagrams with source or destination in the “Local” network have a 10.0.0.0/24 address for the source or destination (as usual).
• Devices in the local network can only have the following local prefixes:
  • 10/8
  • 172.16/12
  • 192.168/16

This works on the router in the following sequence:

1. Host 10.0.0.2 sends datagram to 128.119.40.186:80.
2. NAT router changes datagram source address from 10.0.0.2:3345 to 138.76.29.7:5001 and notes this in the table.
3. Reply arrives from the destination with address of 138.76.29.7:5001.
4. The port is looked up in the table and is forwarded to the correct client on the local network.

IPv6

IPv4 only used a 32-bit addresses. IPv6 allows for every device to have it’s own unique address on the internet using a 128-bit address. The datagram is laid out like so:

• No checksum (to speed processing as routers)
• No fragmentation or reassembly
• No options

Tunnelling & Encapsulation

To send an IPv6 datagram through a router that only supports IPv4 it must be encapsulated inside an IPv4 packet.

• Routers at the edge of the tunnel should be configured to pack and unpack the IPv6 datagrams.

This is slower through the legacy tunnel but is quicker through the rest of the network.

Generalised Forwarding & SDN

Each router contains a forwarding table (flow table). When a packet arrives we complete a match plus action:

• Match bits in arriving packet and take action.

Simple routers use destination based forwarding where packets are forwarded based on the destination IP address.

Generalised forwarding includes the following features:

• Many IP header fields can determine actions.
• Additional actions are possible including: drop, copy, modify, log.

Match & Action

The flow of packets is enabled by flow tables like so:

Generalised forwarding can use the following in it’s packet handling:

• Match - Pattern values in packet header fields.
• Actions _ For matched packet such as: drop, forward, modify, send to controller.
• Priority - Disambiguate overlapping patterns.
• Counters - Number of bytes and number of packets.

This can be useful for dropping or investigating malicious traffic.

OpenFlow

OpenFlow tables can complete generalised forwarding using headers in the:

• Link Layer (MAC, Ethernet, VLANs)
• Network Layer (IP)
• Transport Layer (TCP/UDP)

The tables are laid out like so:

Drop all traffic on port 22 (SSH).

You can then use these tables to complete the following actions:

• Router
  • Match - Longest destination IP prefix.
  • Action - Forward out a link.
• Firewall
  • Match - IP addresses and TCP/UDP port numbers.
  • Action - Permit or deny.
• Switch
  • Match - Destination MAC address
  • Action - Forward or flood (broadcast).
• NAT
  • Match - IP address and port.
  • Action - Rewrite address and port.

Orchestrated tables can create network-wide behaviour by connecting a set of routers to an OpenFlow server.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

You may want a protocol that is tailored to a specific scenario such as:

• Long fat pipes (many in flight packets).
• Wireless networks (noisy links with high bandwidth).
• Long delay links (long RTT).
• Data centre networks (latency sensitive).
• Low priority TCP traffic.

To facilitate this you can implement transport-layer functions in the application layer, on top of UDP.

QUIC - Quick UDP Internet Connections (HTTP/3)

This is an application layer protocol on top of UDP:

• Increases the performance of HTTP
• Uses a slimmed HTTP/2 protocol and QUIC instead of TLS.

This protocol has the following features:

• Error and Congestion Control - Similar to TCP
• Connection Establishment - Reliability, congestion control, authentication, encryption and state all in one RTT.
  • Normally there would be two handshakes, one for TCP and one for TLS.
• Multiple application-level streams can be multiplexed over a single QUIC connection.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Congestion

Congestion is where too many sources are sending too much data too fast for the network to handle. This can give:

• Long Delays
• Packet Loss

This is different from flow control where one sender is sending data too fast.

End to End Congestion Control

• No explicit feedback from the network.
• Congestion is inferred from observed loss and delay.
• Approach taken from TCP.

Network Assisted Congestion Control

• Routers provide direct feedback to sending and receiving hosts with flows passing through congested router.
• May indicate congestion level or explicitly set a sending rate.

This is used in the: TCP ECN, ATM and DECbit protocols.

TCP Congestion Control - AMID

AMID is a distributed, asynchronous algorithm that optimised congested flow rates network wide.

Sender can increase sending rate until packet loss (congestion) occurs, then decrease the sending rate on loss event.

We do this by using the following two methods:

• Additive Increase
  • Increase the sending rate by 1 maximum segment size every RTT until loss is detected.
• Multiplicative Decrease
  • Cut the sending rate in half at each loss event.

This results in a saw-tooth behaviour as the protocol probes from bandwidth.

Multiplicative Decrease

In addition to the definition before the sending rate is:

• Cut in half on loss detected by triple duplicate ACK. (TCP Reno)
• Cut to 1 maximum segment size (MSS) when loss is detected by timeout. (TCP Tahoe)

Congestion Window

The congestion window is the number of unACKed packets that can be in flight at any one time.

The behaviour roughly is:

1. Send cwnd bytes, wait for RTT for ACKS, then send more bytes.

   \[\text{TCP Rate} \approx\frac{\text{cwnd}}{\text{RTT}}\text{ (bytes/sec)}\]

2. TCP sender limite transmission:

   \[\text{LastByteSent} - \text{LastByteAcked}\leq \text{cwnd}\]

3. cwnd is dynamically adjusted in response to observed network congestion (implementing TCP congestion control).

TCP Slow Start

When connection begins, increase the rate exponentially until first loss event:

1. Initially cwnd = 1 MSS
2. Double cwnd every RTT.
3. Done by incrementing cwnd for every ACK received.

To avoid congestion we can switch to linear increases in the cwnd:

• When cwnd gets to $\frac12$ of its value before timeout.

We can do this with the following implementation:

• Have a variable called ssthresh.
• On loss event, ssthresh is set to $\frac12$ of cwnd just before loss event.

TCP Fairness

For a system to be fair, if $K$ TCP sessions share the same bottleneck link of bandwidth $R$, each should have an average rate of $\frac R K$.

TCP is fair as with two competing TCP sessions:

• Additive increase gives slope of 1, as throughput increases.
• Multiplicative decrease decreases throughput proportionally.

This results in equal bandwidth provided both clients have the same RTT.

You can open more TCP connections to the same server to make your connection “unfair”.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

TCP Flow Control

This is where the receiver sends messages to the sender to slow the rate of transfer. This is so that the incoming data doesn’t overflow the buffer by sending data quicker than it can be processed.

• Free space is advertised in the rwnd field of the TCP header.
• RcvBuffer is set by the socket options (typically 4096 bytes).
  • Many operating systems auto adjust RcvBuffer.

    flowchart
    subgraph RcvBuffer
    us[Used Space]
    rwnd["rwnd (Free Space)"]
    end
    p[TCP Segment Payloads] --> RcvBuffer
    RcvBuffer --> a[Application Process]
  

• Sender limits the amount of unACKed data to received rwnd.

  This guarantees the receive buffer will not overflow.

TCP Connection Management

Before exchanging data the sender and receiver need to handshake. This includes:

• Accepting the incoming connection.
• Agreeing on connection parameters.

Two-Way Handshake

A 2-way handshake is problematic as is gives issues when used over an unreliable medium. Ordinarily it would work like so over a port number $x$:

sequenceDiagram
Client ->> Server: req_conn(x)
note right of Server: ESTAB
Server ->> Client: acc_conn(x)
note left of Client:ESTAB

This can produce half-open connections and duplicate data if the handshake messages are lost and re-transmitted.

Three-Way Handshake

This is a more redundant handshake method than resolved the issue of a two way handshake:

sequenceDiagram
note left of Client: Choose init seq num x, send TCP SYN msg
Client ->> Server: SYNbit=1, Seq=x
note right of Client: SYN SENT
note right of Server: Choose init seq num y, send TCP SYNACK msg ACKing SYN
note left of Server: SYN RCVD
Server ->> Client: SYNbit=1, Seq=y, ACKbit=1, ACKnum=x+1
note right of Client: ESTAB
note left of Client: Received SYNACK(x) indicates server is live.<br>Send ACK for SYNACK, this segment may contain client-to-server data.
Client ->> Server: ACKbit=1, ACKnum=y+1
note left of Server: ESTAB
note right of Server: Received ACK(y) indicates client is live.

Closing a TCP Connection

1. Client and server each close their side of the connection:
   • Send TCP segment with FIN bit = 1
2. Respond to received FIN with ACK.
   • On receiving FIN, ACK can be combined with on FIN.

Simultaneous FIN exchanges can be handled.

sequenceDiagram
Client ->> Server: FINbit=1, seq=x
note left of Client: Can no longer send but can receive data.
note right of Server: Can still send data.
note right of Client: FIN_WAIT_1
note left of Server: CLOSE_WAIT
Server ->> Client: ACKbit=1, ACKnum=x+1
note left of Client: Wait for server to close.
note right of Client: FIN_WAIT_2
note left of Server: LAST_ACK
Server ->> Client: FINbit=1, seq=x
note right of Server: Can no longer send data.
note left of Client: Timed wait for 2*max segment lifetime.
note right of Client: TIMED_WAIT
Client ->> Server: ACKbit=1, ACKnum=y+1
note left of Server: CLOSED
note right of Client: CLOSED

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

TCP Features

TCP has the following features:

• Point-to-Point - one sender, one receiver
• Reliable, In-Order Byte Stream - no “message boundaries”
• Full Duplex Data:
  • Bi-directional data flow in same connection.
  • MSS - maximum segment size.
• Cumulative ACKs
• Pipelining - TCP congestion and flow control set window size.
• Connection-Oriented - Handshaking (exchange of control messages) initialises sender, receiver state before data exchange.
• Flow Controlled - Sender will not overwhelm receiver.

TCP Segment Structure

• Sequence Numbers - Count the bytes of data in the byte-stream (not the sequence of the segments).
• Acknowledgements:
  • Acknowledge the sequence number of the next byte expected from the other side.
  • Cumulative ACK.

TCP Sequence Numbers & ACKs

Here is an example of a simple telnet scenario:

sequenceDiagram
note left of A: User types 'C'
A -->> B:Seq=42, ACK=79, data='C'
note right of B: B ACKs receipt of 'C', echoes back 'C'
B -->> A:Seq=79, ACK=43, data='C'
note left of A: A ACKs receipt of echoed 'C'
A -->> B:Seq=43, ACK=80

TCP Round Trip Time & Timeout

The timeout should be longer than the round trip time (rtt) but the rtt varies:

• Too Short - Premature timeout, unnecessary re-transmission.
• Too Log - Slow reaction to segment loss.

To get a SampleRTT we can measure the time from segment transmission until ACK receipt (ignoring re-transmissions). We want to smooth this out so we sample several recent rtts.

To estimate the round trip time we use an exponential weighted moving average:

The influence of past samples decrease exponentially.

To calculate the timeout interval we include a safety margin that takes into account the variance of the SampleRTT:

DevRRT is the safety margin. It is calculated as an exponential weighted moving average of SampleRTT deviation from EstimatedRTT:

Typically $\beta=0.25$

TCP Sender (Simplified)

This is a simplified sender that ignores duplicate ACKS, flow control and congestion control.

Data received from application:

• Create segment with sequence number.
  • Sequence number is the byte-stream number of the first data byte in the segment.
• Start timer if not already running.
  • The timer is for the older unACKed segment.
  • Expiration interval is the TimeOutInterval.

Timeout:

• Re-transmit segments that caused the timeout.
• Restart the timer.

ACK Received:

• If ACK acknowledges previously unACKed segments:
  • Update what is known to be ACKed.
  • Start timer if there are still unACKed segments.

Receiver ACK Generation

This covers RFC 5681:

TCP Fast Re-transmit

If a sender receives three additional ACKs fro the same data (triple duplicate ACKs), resend unACKed segment with the smallest sequence number:

• It is likely that unACKed segment was lost:
  • We can resend the data and save waiting for the timeout.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Calculating Utilisation

Stop and wait protocols are inefficient as ideally they can only send one packet per round trip time.

To calculate the time to transmit a 1 MB packet into a 1 Gbps channel:

Where:

• $D$ - Time to transmit packet.
• $L$ - Length of the packet.
• $R$ - Rate of transfer.

To find the utilisation of the medium we can use the following:

With the previous packet, link speed, 30 ms rtt and a stop and wait protocol we can calculate the following:

This is only 0.027% utilisation.

Pipelining

This allows us to send multiple packets before the first one is acknowledged. There are two main families of protocols:

Go-Back-N Protocol

Sender

There is a window of up to $N$, consecutive transmitted but unACKed packets:

• Cumulative ACK - We must acknowledge all packets up to and including the sequence number included in the client’s ACK.
• On receiving ACK(n) - Move window forward to begin at $n+1$.
• Timer is used for the oldest in-flight packet.
  • When the timer runs out, re-transmit packet $n$ and all higher sequence number packets in the window.

Due the reuse of sequence numbers we use sequence numbers of $>2N$ (more than 2 times the window size).

Receiver

This is ACK only:

• Always send ACK for correctly-received packet so far, with highest in-order sequence number.
• May generate duplicate ACKs
• Need only remember the next expected sequence number.

On receipt of out-of-order packet:

• Can discard (don’t buffer) or buffer for later.

  This is an implementation decision.

• Re-ACK packet with highest in-order sequence number.

Selective Repeat Protocol

In this method the receiver individually acknowledges all correctly received packets.

• Buffers packets, as needed, for eventual in-order delivery to the upper layer.

The sender times-out/re-transmits individually for each unACKed packet:

• Sender maintains timer for each unACKed packet.

The sender window:

• Has a size of $N$ consecutive seq numbers.
• The timers keep track of unACKed packets.

Sender

Data from above:

• If next available sequence number in window, send packet.

Timeout(n):

• Resend packet $n$, restart timer.

ACK(n) in [sendbase,sendbase+N]:

• Mark packet $n$ as received.
• If $n$ smallest unACKed packet, advance window base to next unACKed sequence number.

Receiver

Packet $n$ in [rcvbase, rcvbase+N-1]:

• send ACK(n)
  • Out-of-order - buffer.
  • In-order - deliver (also deliver buffered, in-order packets), advance window to next not-yet-received packet.

Packet $n$ in [rcvbase-N,rcvbase-1] (already received):

• ACK(n)

Otherwise:

• Ignore

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Recovering From Errors

We can use acknowledgements and negative acknowledgements from the client to the sender:

• Acknowledgements (ACKs) - Tells the sender that the packet was received okay.

• Negative Acknowledgements (NACKs) - Tells the sender that the packet had errors.

  This can be removed as the sender can resend the packet if there is a timeout for an ACK.

Corrupted Acknowledgements

If an acknowledgement is lost then the sender will send a duplicate packet. We can add sequence numbers to keep track of if a packet is a duplicate:

• For stop and wait we can alternate between 0 and 1.
• If there is a duplicate the packet is dropped and another acknowledgement is sent.

Packet Loss

A timer can be put on each packet:

• If an ACK is not received in time the packet is re-transmitted.
  • If the re-transmission is a duplicate then the sequence numbers will handle this.

Twice the round trip time is a reasonable starting point for the timer.

Stop & Wait Sequence

Sender:

1. Sequence number is added to the packet.
   • 0 or 1 will do.
2. Send the packet and start timer.
3. Check if the ACK is corrupt or a NACK, if it is send the same packet.
4. Send the next packet if an ACK is received.
5. If packet times out, send it again.

Receiver:

1. Must check if received packet is duplicate.
2. State indicates whether 0 or 1 is expected packet sequence number.
3. If packet is duplicate send ACK.
4. If packet is in order then send ACK and pass to the application layer.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Connection-Less Transport

This means that there is:

• No handshaking between sender, receiver.
• Each UDP segment handled independently of others.

This saves time, is simpler and gives a small header size.

UDP Uses

UDP is used for the following:

• Streaming multimedia apps (loss tolerant, rate sensitive).
• DNS
• SNMP
• HTTP/3

If reliable transfer needed over UDP (HTTP/3):

• Add needed reliability at application layer.
• Add congestion control at application layer.

UDP Segment Header

A UDP segment is laid out like the following:

The segment is 32 bits wide.

Internet Checksum

Checksums are used to find flipped bits in transmission.

To calculate the internet checksum:

1. Treat the whole contents of the UDP segment as a sequence of 16-bit integers.

2. Complete a one’s complement sum of the integers.

   Wraparound the carry-out to the beginning of the addition.

3. Put the checksum value in the UDP checksum field.

This only adds weak protection against single bit flips.

These notes are low-effort, due to catching up in this module. See the videos and slides for more detail.

Demultiplexing

Each IP datagram carries the source and destination IP address and a transport-layer segment. This segment includes:

• Source Port
• Destination Port
• Other Header Fields
• Application Data

Connection-less Demultiplexing

This is used by UDP. To create a socket you can use the following Java code:

DatagramSocket socketName = new DatagramSocket(12345);

IP/UDP datagrams with same destination port #, but different source IP addresses and/or source port numbers will be directed to same socket at receiving host.

Connection-Oriented Demultiplexing

TCP socket is identified by a 4-tuple:

• Source IP Address
• Source Port Number
• Destination IP Address
• Destination Port Number

The receiver uses all four values (4-tuple) to direct the segment to the appropriate socket.

Server may support many simultaneous TCP sockets:

• Each socket is identified by its own 4-tuple.
• Each socket is associated with a different connecting client.

Differences

• UDP - Demultiplexing using destination port number (only).
• TCP - Demultiplexing using 4-tuple: source and destination IP addresses, and port numbers.

The transport layer provides logical communication between application processes running on different hosts.

• Sender - Breaks the application messages into segments and passes to the network layer.
• Receiver - Reassembles the segments into messages and passes them to the application layer.

There are two transport layer protocols available:

• TCP
• UDP

Network Layer vs. Transport Layer

The network layer is a logical communication between hosts.

This is similar to the postal service.

The transport layer extends this network service to provide a logical communication between processes:

• It relies on and enhances network layer services.

Transport Layer Actions

The sender:

1. Is passed an application-layer message.
2. Determines segment header fields values.
3. Creates a segment.
4. Passes the segment to IP.

The receiver:

1. Receives a segment from IP.
2. Checks header values.
3. Extracts the application-layer message.
4. Demultiplexes the message up to the application via a socket.

Two Principle Internet Transmission Protocols

TCP (Transmission Control Protocol):

• Reliable, in-order delivery.
• Congestion Control
• Flow Control
• Connection Setup

UDP (User Datagram Protocol)

• Unreliable, unordered delivery.
• No-frills extension of “best-effort” IP.

The following services are not available:

• Delay Guarantees
• Bandwidth Guarantees

Compared to UDP there are some differences:

The client must contact the server:

• The server process must first be running.
• The server must have created a socket that welcomes the client’s contact.

Clients contact the server by:

• Creating TCP socket, specifying IP address, port number of server process.
• When the cloent creates a socket the slcinet TCP establishes connection to server TCP.

When contacted by the client, the server TCP creates a new socket for the server process to communcate with that particular client:

• This allows the server to talk iwht multiple clients.
• Source port number are used to distinguish clients.

TCP provides a reliable, in-order byte-stream transfer (pipe).

Example Program

Like the UDP example the client sends a string the the server over TCP. The server then converts the string to upper-case and then sends it back.

Java TCP Client

import java.io.*;
import java.net.*;
class TCPClient {
	public static void main(String argv[]) throws Exception {
		String sentence;
		String modifiedSentence;
		
		// create input stream
		BufferedReader inFromUser = new BufferedReader(new InputStreamReader(System.in));
		
		// create client socket and connect to server
		Socket clientSocket = new Socket("hostname", 6789);
		
		// create output stream attached to socket
		DataOutputStream outToServer = new DataOutputStream(clientSocket.getOutputStream());
		
		// create input stream attached to socket
		Buffered Reader inFromServer = new BufferedReader(new InputStreamReader(clientSocket.getInputStream()));
		
		sentence inFromUser.readLine();
		
		// send line to server
		outToServer.writeBytes(sentence +'\n');
		
		// read line from server
		modifiedSentence = inFromServer.readLine();
		
		System.out.println("FROM SERVER: " + modifiedSentence);
		
		clientSocket.close();
	}
}

Java TCP Server

import java.io.*;
import java.net.*;

class TCPServer {
	public static void main(String argv[]) throws Exception{
		String clientSentence;
		String capitalisedSentence;
		
		// create welcoming socket at port 6789
		ServerSocket welcomeSocket = new ServerSocket(6789);
		
		while(true) {
			// wait on welcoming socket for contact by client
			Socket connectionSocket = welcomeSocket.accept();
			
			// create input stream attached to socket
			BufferedReader inFromClient = new BufferedReader(new InputStreamReader(connectionSocket.getInputStream()));
			
			// create output stream attached to socket
			DataOutputStream outToClient = new DataOutputStream(connectionSocket.getOutputStream());
			
			// read in line from socket
			clientSentence = inFromClient.readLine();
			
			capitalisedSentence = clientSentence.toUpperCase() +'\n';
			
			// write out line to socket
			outToClient.writeBytes(capitalisedSentence);
		}
	}
}

A recap of the content is in Java Socket Programming Recap & Assignment 1.

A socket is a door between the application process and the transport layer. There are two socket types, one for each transport layer (UDP/TCP).

UDP

There is no explicit connection between the client and the server:

• No handshake before data is sent.
• Sender explicitly attache the IP destination address and port to each packet.
• Receiver extracts the sender IP address and port from the received packet.

Transmitted data may be lost or received out of order.

UDP provides unreliable transfer of groups of bytes (data-grams) between client and server.

Example Program

The client in this example sends a string the the server over UDP. The server then converts the string to upper-case and then sends it back.

Java UDP Client

import java.io.*;
import java.net.*;

class UDPClient {
	public static void main(String args[]) throws Exception {
	
		// create input stream
		BufferedReader inFromUser = new BufferedReader(new InputStreamReader(System.in));
		
		// create client socket
		DatagramSocket clientSocket = new DatagramSocket();
		
		// translate host name to IP address using DNS
		InetAddress IPAddress = InetAddress.getByName("hostname");
		
		byte[] sendData = net byte[1024]; // message limited to 1024 characters
		byte[] receiveData = new byte[1024];
		
		// read message from terminal
		String sentence = inFromUser.readLine();
		
		// convert string to byte array
		sendData = sentence.getBytes();
		
		// create data-gram with data to send, length, IP address and port
		DatagramPacket sendPacket = new DatagramPacket(sendData, sendData.length, IPAddress, 9876);
		
		// send data-gram to server
		clientSocket.send(sendPacket);
		
		DatagramPacket receivePacket = new DatagramPacket(receiveData, receiveData.length);
		
		// read data-gram from server
		clientSocket.receive(receivePacket);
		
		// extract data from packet
		String modifiedSentence  = new String(receivePacket.getData());
		
		System.out.println("FROM SERVER:" + modifiedSentence);
		clientSocket.close();
	}
}

Java UDP Server

import java.io.*;
import java.net.*;

class UDPServer {
	public static void main(String args[]) throws Exception {
		
		// create data-gram socket at port 9876
		DatagramSocket serverSocket = new DatagramSocket(9876);
		
		byte[] receiveData = new byte[1024];
		byte[] sendData = new byte[1024];
		
		while(true) {
			
			// create space for received data-gram
			DatagramPacket receive Packet = new DatagramPacket(receiveData, receiveData.length);
			// receive data-gram
			serverSocket.receive(receivePacket);
			
			String sentence = new String(receivePacket.getData());
			
			// get IP address and port of sender
			InetAddress IPAddress = receivePacket.getAddress();
			int port = receivePacket.getPort();
			
			String capitalisedSentence = sentence.toUpperCase();
			
			sendData = capitalisedSentence.getBytes();
			
			// create data-gram to send to client
			DatagramPacket sendPacket = new DatagramPacket(sendData, sendData.length, IPAddress, port);
			
			// write out data-gram to socket
			serverSocket.send(sendPacket);
		}
	}
}

This lecture continues from The Application Layer - Network Applications.

File Distribution for Client-Server Model

To send a file to $N$ clients the server must upload $N$ file copies:

• Time to send one copy: $\frac F {u_s}$
• Time to send $N$ copies $\frac{NF}{u_s}$

Each client must download a file copy:

• $d_\min=$ minimum client download rate.
• Minimum client download time: $\frac F{d_\min}$

Therefore the time to distribute $F$ to $N$ clients using the client-server approach is:

File Distribution for P2P

Server transmission must upload at least one copy:

• Time to send one copy: $\frac F{u_s}$

Each client must download a file copy:

• Minimum cloent download time: $\frac F{d_\min}$

Additional Clients as aggregate must download $NF$ bits:

• Max upload rate (limiting max download rate) is: $u_s +\sum u_i$

Therefore the time to distribute $F$ to $N$ client using a P2P approach is:

As the service capacity increases linearly with $N$ the service is self-scaling.

BitTorrent

• File is divided into 256Kb chunks.
• Peers in the torrent send and receive file chinks.

There are two parties:

• Tracker - Tracks peers participating in the torrent.
• Torrent - The group of peers exchanging chunks of a file.

When a new peer arrives:

1. They obtain a list of peers from the tracker.
2. Begin exchanging file chunks with the peers in the torrent.

File Chunks

Requesting chunks:

• At any given time, different peers have different chunks.
• Periodically, you ask each peer for a list of chunks that they have.
• You request missing chunks from peers, rares first.

Sending chunks (tit-for-tat):

• You send chunks to those sending you chunks at the highest rate.
  • Other peers are choked.
  • Re-evalulate to peers every 10 seconds.
• Every 30 seconds, randomly seelct another peer to start sending chunks.
  • Optimistically un-choke this peer.
  • This new peer may gain rate.

Higher upload rate gets better trading partners, allowing you to get the file faster.

DNS allows host-names to be mapped to IP addresses:

• The DNS is implemented as a distributed database on a hierarchy of many name servers.
• It is implemented in the application-layer to put complexity at the network edge.

DNS allows for the following:

• Host-name to IP address translation.
• Host aliasing.
• Mail server aliasing.
• Load distribution:
  • Many IP addresses can correspond to one name.

Against Centralised DNS

There are many reasons why you don’t want DNS to be centralised:

• Single point of failure.
• Traffic volume.
• Can be physically distant from clients.
• Maintenance will take down the whole internet.

In order to scale the internet DNS is implemented as a distributed database.

Hierarchy

flowchart
r[Root DNS Servers] --> com[.com DNS Servers] & org[.org DNS Servers] & edu[.edu DNS Servers]
com --> yahoo[yahoo.com DNS Servers] & amazon[amazon.com DNS Servers]
org --> pbs[pbs.org DNS Servers]
edu --> nyu[nyu.edu DNS Servers] & umass[umass.edu DNS Servers]
subgraph Root
r
end
subgraph Top Level Domain
com
org
edu
end
subgraph Authorative
yahoo
amazon
pbs
nyu
umass
end

Root Name Servers

There are 13 logical root name servers with each server being redundant across the world. They are:

• Official last resort name servers.
• Managed by ICANN (Internet Corporation for Assigned Names and Numbers)
• Very important to the function of the internet.

Top Level Domains

TLD servers are responsive for all top level domains (.com, .org, .net, …) and all the country domains (.uk, .fr, .jp, …). There are companies responsible for all top level domains.

Authoritative Servers

There are organisations own DNS servers, providing authoritative host-name to IP mappings for an organisation named hosts.

These can be maintained by an organisation or the service provider.

Local DNS Name Servers

Each ISP has a default name server. When a host makes a DNS query it is sent to it’s local DNS server. This has:

• A cache of recent name-to-address translation pairs.
• Acts as a proxy, forwarding queries into the hierarchy.

Iterated Query

DNS also allows recursive queries.

In the worst case the following would happen when you search for a host-name via DNS:

1. Client requests local DNS server.
2. Local DNS server requests root DNS server for top level domain.
3. Local DNS server requests TLD for authoritative domain.
4. Authoritative responds with IP address.
5. Local DNS server responds to client with IP address.

Caching Records

Once any name server learns a mapping it is cached:

• Cache entries timeout after some time (TTL).
• TLD servers are typically cache in the local name servers.
  • This means taht the root name servers are not often visited.
• Cached entries may be out of date:
  • If name host changes IP address it may not be known until all TTLs expire.
• Update and notify mechanisms are proposed in IETF standard RFC 2136.

DNS Record Types

DNS is a distributed databse that stores resource records (RR). The RR schema is:

RR(name, value, type, ttl)

There are several types:

• type=A
  • name is the hostname
  • value is the IP address
• type=CNAME
  • name is an alias name for some canonical name.
  • value is the canonical name.
• type=NS
  • name is the domain.
  • value is the host-name of the authoritative name server for this domain.
• type=MX
  • value is the name of the mail-server associated with name.

Cookies

Cookies are used to maintain user state. Many websites use four components to achieve this:

1. Cookie header line of HTTP response message.
2. Cookie header line in next HTTP request message.
3. Cookie file kept on user’s host, managed by user’s browser.
4. Back-end database at website.

A cookie is just a unique ID number stored in a file.

sequenceDiagram
client ->> server: Usual HTTP request msg
server ->> database: Create ID entry
server ->> client: Usual HTTP response & "set-cookie:1678"
client ->> server: Usual HTTP request msg & "cookie:1678"
server -> database: Access
Note over server, database: Cookie specific action
server ->> client: Usual HTTP response msg
note left of client: One week later
client ->> server: Usual HTTP request msg & "cookie:1678"
server -> database: Access
Note over server, database: Cookie specific action
server ->> client: Usual HTTP response msg

HTTP Cookies

Cookies can be used for:

• Authorisation
• Shopping Carts
• Recommendations
• User Session State (Web E-Mail)

Cookies permit sites to learn a lot about you. Third party cookies allow a common identity to be tracked across multiple sites.

Web Caches (Proxy Servers)

Proxy servers allow a client request to be satisfied without involving the origin server.

• If the object is in the cache - The cache returns the object to the client.
• Else - The cache requests the object from the origin server, caches the object and sends the object to the client.

Web caching allows the following:

• Less response time for the client.
• Reducing traffic on an institutions access link.
• Enables poor content providers to operate more effectively.

Conditional GET

This allows servers to check if their cached object is up to date. This allows:

• No object transmission delay.
• Lower link utilisation.

You can specify the date of a cached copy in the request:

If-modified-since: <date>

If the copy is up to date the server will not return the object but the following response:

HTTP/1.0 304 Not Modified

Here is the sequence of interactions:

sequenceDiagram
client ->> server: Request & "If-modified-since:<date>"
alt Object not modified
	server ->> client: "HTTP/1.0 304 Not Modified"
else Object modified
	server ->> client: "HTTP/1.0 200 OK <data>"
end

A web page is a set of several referenced objects which are accessible by their URL:

HTTP

This is the application layer protocol for the web:

• It uses a client server model.
  • Clients request and receive, servers can return objects in response to a request.
• HTTP uses TCP over port 80.

• HTTP is stateless - No information about past client requests are held.

  Protocols that maintain state are complex. The past history must be maintained and if the client or server crashes their views of state may become inconsistent.

Types of Connections

There are two different types of HTTP connection:

Non-Persistent HTTP

1. TCP connection opened.
2. At most one object sent over the TCP connection.
3. TCP connection closed.

Persistent HTTP

1. TCP connection opened.
2. Multiple objects can be sent over a single TCP connection.
3. The connection is closed when finished.

Round Trip Time (RTT)

This is the time for a small packet to travel from client to server and back.

For HTTP 1.0 (non-persistent) the response time is:

from the following sequence diagram:

sequenceDiagram
Note left of client: Initiate TCP
client ->> server: Open TCP
activate server
server ->> client: TCP Open
Note left of client: Request File
client ->> server: Request File URL
server ->> client: Transmit File
deactivate server
Note left of client: File Received

This is an issue as there is additional overhead in order to open and close the single TCP connections.

In HTTP 1.1 (persistent) you can have as little as one RTT for all referenced objects as the connection is left open.

SMTP

After the header, and before the body, of the email there must be a blank line. This is required for the assignment.

DATA
SUBJECT: Hello

This is the body.
.

Java Sockets

To open a socket use the code:

import java.net.*;
Socket socket = new Socket("ip.address", <port>);

Reading Sockets

To read the socket you can use the following:

import java.io.*
InputStream is = socket.getInputStream();
InputStreamReader isr = new InputStremReader(is);
BufferedReader br = new BufferedReader(isr);

The BufferedReader allows you to read the stream a line at a time.

To read the buffer to a variable you can use the following:

String response = br.readLine();

Writing to Sockets

To send data you must first setup an output stream:

DataOutputStream os = new DataOutputStream(socket.getOutputStream());

To write a variable to the stream you use:

os.writeBytes(variable);

Assignment 1

The instructions for this assignment are available here.

In order to establish a TCP connection and send commands to a server you can use the following skeleton code:

import java.io.*;
import java.net.*;

public class EmailSender
{
	public static void main(String[] args) throws Exception
	{
		// Establish a TCP connection with the mail server.
		Socket socket = new Socket("35.246.112.180",1025);

		// Create a BufferedReader to read a line at a time.
		InputStream is = socket.getInputStream();
		InputStreamReader isr = new InputStreamReader(is);
		BufferedReader br = new BufferedReader(isr);

		// Read greeting from the server.
		String response = br.readLine();
		System.out.println(response);
		if (!response.startsWith("220")) {
		 throw new Exception("220 reply not received from server.");
		}

		// Get a reference to the socket's output stream.
		DataOutputStream os = new DataOutputStream(socket.getOutputStream());

		// Send HELO command and get server response.
		String command = "HELO alice\r\n";
		System.out.print(command);
		os.writeBytes(command);
		response = br.readLine();
		System.out.println(response);
		if (!response.startsWith("250")) {
		 throw new Exception("250 reply not received from server.");
		}
	}
}

Service Requirements

• Data Integrity
  • You may need 100% reliable data transfer for some types of data transfer.
  • Media streaming can often compensate for loss.
• Timing
  • Some apps require low latency for effective use of the application.
• Throughput
  • Media streaming often requires a minimum throughput to be effective.
• Security
  • Data encryption

Common Applications

Internet Transport Protocols

TCP

This method provides:

• Reliable Transport
• Flow Control
  • Sender won’t overwhelm the receiver.
• Congestion Control

It doesn’t provide:

• Timing
• Minimum throughput guarantee
• Security

This protocol is connection-oriented as a setup it required between teh client and server processes.

UDP

This method provides:

• Unreliable Data Transfer

It doesn’t provide:

• Reliable Transport
• Flow Control
• Congestion Control
• Timing
• Minimum throughput guarantee
• Security

This method has no guarantees. However, this enables the fastest connections and quickest setup times.

Security

TCP and UDP sockets provide no security methods, as a result there are additional protocols that allow this service.

Transport layer security (TLS) provides:

• TCP encrypted connections.
• Data integrity
• End-point authentication.

TLS is implemented in the application layer. This means that:

• Apps use TLS libraries that, in turn, use TCP.
• TLS socket API allows clear-text to be sent to the socket to traverse the network encrypted.

Network Applications

These are programs that:

• Run on different end systems.
• Communicate over the network.

As this is a layered system there is no need to write software for the network-core devices.

Client-Server Architecture

The server is:

• Always on host.
• Permanent IP address.
• Can use data centres for scaling.

The clients:

• Communicate with the server.
• May be intermittently connected.
• May have a dynamic IP address.
• Don’t communicate directly with each other.

Peer-to-Peer (P2P) Architecture

This architectures includes:

• No always on server.
• Arbitrary end system directly communicating.
• Peers request service from other peers and provide service to other peers.
  • Self scalability - New load also brings more service capacity.
• Peers are intermittently connected and change IP addresses.
  • Complex to manage.

Processes Communicating

A process is a program running within a host:

• Within the same host, two process communicate using inter-process communication (defined by the OS).
• Processes in different hosts communicate by exchanging messages.

Sockets

Processes send and receive messages to and from its socket:

• Sending a message from a socket relies on a transport infrastructure behind the port.
• There should be two sockets involved (one to send and one to receive).

Addressing Processes

In order to identify a process you need the system’s IP address and the port number associated with the process and the host.

Examples are:

• HTTP server: port 80
• SMTP server: port 25

Application-Layer Protocols

The protocol for the application layer must define the following things:

• Types of messages exchanged.
• Message syntax.
• Message semantics
• Rules for when and how processes send & respond to messages.

You can use open protocols:

• Defined in RFC’s
• Everyone has access to the protocol definition.
• Allows for interoperability.

Or proprietary protocols:

• Are made in-house and are not open to the public.

There are three major components to e-mail:

• User Agents
  • Such as outlook or geary.
• Mail servers
  • Mailbox - contains incoming messages for user.
  • Mesage Queue - of outgoing messages.
  • SMTP Protocol - Between mail server to send email messages.
• The protocol: simple mail transfer protocol (SMTP)

SMTP

The standard for this protocol is RFC 5321.

• Uses TCP on port 25.
• Direct transfer from the sending to receiving server.
• Three phases of transfer:
  • Handshaking
  • Transer of Messages
  • Closure
• Command/Response Interaction (like HTTP):
  • Commands: in ASCII.
  • Response: Status code and phrase.

Example SMTP Request

SMTP requests are sent as multiple objects, sent in a multi-part message. The message is split based on who is responding.

220 EventMachine SMTP Server

HELO alice

250 Ok EventMachine SMTP Server

MAIL FROM: <sender@example.com>

250 Ok

RCPT TO: <receiver@example.org>

250 Ok

DATA

354 Send it

SUBJECT: Hello

Hi Bob, How's the weather? Alice.
.

250 Message accepted

The message is ended with \r\n.\r\n. Where \r is a carriage return and \n is a newline.

Mail Message Format

SMTP is defined in RFC 531 (like HTTP). Additionally, RFC 822 defines the syntax for e-mail messages (like HTML).

An SMTP message can be split into two parts:

• Header Lines:
  • To:
  • From:
  • Subject:
• Body - Message with ASCII characters only.

Mail Access Protocols

SMTP can send mail but in order to retrieve it and read the contents you must use other protocols:

• SMTP - Delivery and storage of e-mail.
• IMAP (Internet mail access protocol RFC 3501) - Messages stored on server, provides retrieval, deletion & folders of stored messages.
• HTTP - Provides web-based interfaces on top of SMTP & IMAP.

HTTP

There are two types of HTTP messages:

• request
• response

HTTP messages are encoded in ASCII. Here is one now:

GET / HTTP/1.1
Host: comp211.gairing.com
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:92.0) Gecko/20100101 Firefox/92.0
Accept: text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8
Accept-Language: en-GB
Accept-Encoding: gzip, deflate
DNT: 1
Connection: keep-alive
Upgrade-Insecure-Requests: 1

Only the GET and Host: lines are required for a valid request.

• The top line is the request line. You can make requests such as GET, POST and HEAD.
• The rest of the lines are called the header lines. They specify certain parameters that the browser can set.

All lines end with a \r\n to indicate a carriage return and line feed. There is also an extra one at the end of the header lines.

HTTP Request Message Format

<method> <URL> <version>\r\n	# request line
<header field name> <value>\r\n	# header lines
...
\r\n
<entity body>	# the requested body

Other HTTP Request Messages

POST method:

• Web page often includes form input.
• User input sent from client to server in entity body of HTTP POST request message.

GET method (for sending data to server):

• Include user data in URL field of HTTP GET request message.

  This follows a ? in the URL.

HEAD method:

• Requests headers (only) that would be returned if specified URL were requested with an HTTP GET method.

PUT method:

• Uploads new file (object) to the server.

• Completely replaces file that exists at the specified URL with content in the entity body of POST HTTP request message.

  This method is often blocked on web servers.

HTTP Response

This is the response that the server sends back to a client:

HTTP/1.1 200 OK
Content-Type: text/html
Content-Length: 417
Connection: keep-alive
Keep-Alive: timeout=15
Date: Mon, 04 Oct 2021 11:40:11 GMT
Server: Apache
Last-Modified: Thu, 03 Oct 2019 20:28:35 GMT
ETag: "1a1-594076e0ed808"
Accept-Ranges: bytes


<HTML>
<HEAD>
<TITLE>This is just a simple HTML page</TITLE>
</HEAD>
<BODY BGCOLOR="FFFFFF">
<HR>
<H1>This is a Header</H1>
<H2>This is a Medium Header</H2>
Send me mail at <a href="mailto:support@yourcompany.com">
support@yourcompany.com</a>.
<P> This is a new paragraph!
<P> <B>This is a new paragraph!</B>
<BR> <B><I>This is a new sentence without a paragraph break, in bold
italics.</I></B>
<HR>
</BODY>
</HTML>

• The top line is the status line.
• Next are header lines.
• Then the data requested.

HTTP Response Status Codes

Defining protocol layers helps in dealing with complex systems:

• Explicit structure allows identification, relationship of complex system’s pieces.
  • Layered reference model for discussion.
• Modularisation eases maintenance, updating of system.
• Change in layer’s service implementation is transparent to rest of system.

Internet Protocol Stack¹

ISO/OSI Reference Model

The OSI reference model also includes:

• Presentation - Allows the applications to interpret the meaning of data.
  • Encryption, compression, machine specific conventions.
• Session - Synchronisation, check-pointing and recovery of data exchange.

The internet stack is missing these layers. If they are need they must be implemented in the application.

1961-1972 - Early Packet-switching Principles

• 1961 - Kleinrock - Queuing theory shows effectiveness of packet switching.
• 1964 - Baran - Packet-switching in military nets.
• 1967 - ARPAnet conceived by Advanced Research Projects Agency.
• 1969 - First ARPAnet node operational.
• 1972 - ARPAnet public demo.
  • NCP - Network control protocol is the first host-host protocol.
  • First e-mail program.
  • ARPAnet has 15 nodes.

1972-1980 - Internet Working, New & Proprietary Nets

• 1970 - ALOHAnet satellite network in Hawaii.
• 1974 - Cerf & Kahn - Architectures for interconnecting networks.
  • Minimalism, autonomy - no internal changes required to interconnect networks.
  • Best effort service model.
  • Stateless routing.
  • Decentralised control
• 1976 - Ethernet at Xerox PARC.
• Late 70s - Proprietary architectures: DECnet, SNA, XNA.
• 1979 - ARPAnet has 200 nodes.

1980-1990 - New Protocols, A Proliferation of Networks

• 1983 - Deployment of TCP/IP
• 1982 - SMTP e-mail protocol defines.
• 1983 - DNS defines for name-to-IP-address translation.
• 1985 - FTP protocol defined.
• 1988 - TCP congestion control.

The french government gives free network access devices to access the Minitel network.

1990-2000 - Commercialisation, The Web, New Applications

• Early 1990s - ARPAnet decommissioned.
• 1991 - NSF lifts restrictions on commercial use of NSFnet (decommissioned 1995).
• Early 1990s - The Web
  • Hypertext (Bush - 1945, Nelson - 1960s)
  • HTML, HTTP (Berners-Lee)
  • 1994 - Mosaic, later Netscape.
  • Late 1990s - Commercialisation of the web.
• Late 1990s-200s:
  • More killer apps - Instant messaging, P2P file sharing.
  • Network security to forefront.
  • 50 millions hosts, 100 million users.
  • Backbone links running at Gbps

2005-Present - More applications, greater proliferation.

• 18 billion connected device.
• Aggressive deployment of broadband.
• Online social networks.
• Service providers (Google, FB…) create their own networks.
• Enterprises run their services in the cloud.

The internet was not originally designed with security in mind. This means that current methods have been patched onto the existing layers of the internet.

Denial of Service

This method of network abuse uses several computers to send traffic to a server in order to overwhelm it.

Packet Sniffing

On broadcast media, like Ethernet and WiFi, you are able to record the transmitted packets for later analysis.

These packets include all transmitted data so sensitive information, like cookies and passwords, can be captured on encrypted sites.

IP Spoofing

Packets can be sent with a false source address. This can complete actions on behalf of an already authenticated machine.

Delay

There are several types of delay that a packet can experience:

• Nodal Processing ($d_\text{proc}$)
  • Checking for bit errors.
  • Determining the output link.
  • Generally < 1 ms
• Queuing Delay
  • Time waiting at output link for transmission.
  • Depends on the congestion level of the router.

• Transmission Delay

  \[d_\text{trans}=\frac L R\]
  • $L$ - Packet length in bits.
  • $R$ - Link transmission rate in bps.

• Propagation Delay

  \[d_\text{prop}=\frac d s\]
  • $d$ - The length of the physical link.
  • $s$ - The propagation speed on the physical media ($~2\times 10^8$ ms).

This comes together to give the total packet delay of:

Traffic Intensity

This is calculated using the following equation:

• $R$ - Link bandwidth in bps.
• $L$ - Packet length in bits.
• $a$ - Average packet arrival rate.

Queuing delay increases exponentially with the traffic intensity.

For small values then the delay is small but if the delay is >1 then packets are dropped.

traceroute

This is a program that can measure the delay to all the ‘hops’ on a packet’s journey.

Throughput

Throughput is the rate at which bits are being sent from sender to receiver. This can be measured as:

• Instantaneous - Rate at a given point in time.
• Average - Rate over a longer period of time.

The throughput is limited by the slowest link on a packet’s path.

The network core is a mesh of interconnected routers. They use packet-switching to break the application-layer messages into packets:

• Forward packets from one router to the next, across links on path from the source to the destination.
• Each packet is transmitted at full link capacity.

Store and Forward

The entire packet must arrive a a router before it can be transmitted on to the next link.

Including the transmission delay ($\frac L R$) the end-end delay is:

this assumes zero propagation delay.

Queuing Delay & Loss

If the arrival rate exceeds the transmission rate of a link then:

• Packets will queue, waiting to be transmitted on the output link.
• Packets can be dropped if the memory buffer in the router fills up.

Network Core Functions

These are the core functions from the perspective of a router.

Forwarding

This is a local action that moves the arriving packets from the router’s input link to the appropriate router output link.

Routing

This is a global action that determines the source-destination paths taken by packets.

Routing algorithms are used to do this.

Circuit Switching

This is an alternative to packet switching. End-end resources are allocated to be reserved for a call between the source and destination.

• Dedicated resources
  • There is no sharing and you are guaranteed performance.
• Circuit segment is idle if not used by a call.
• Commonly used in traditional telephone networks.

Packet switching is better suited to the internet as communication is generally is bursts with lots of idle time.

Frequency Division Multiplexing (FDM)

By using a modulation technique, you can split the bandwidth by frequency and transfer data on a circuit at many different frequencies.

Time Division Multiplexing (TDM)

This method splits the entire bandwidth into time slots that can be assigned to certain users.

Circuit Switching Evaluation

• Good for bursty data as we can take advantage of:
  • Resource sharing.
  • No call setup.
• Excessive congestion is possible:
  • Packet delay and loss due to buffer overflow.
  • Protocols need to reliable data transfer, congestion control.
• Bandwidth guarantees are still required for video and audio streaming.

Internet Structure

In order to connect all the international ISPs together we use global ISPs. These global ISPs are then joined by internet exchange points (IXPs). Additionally content provider networks may run their own networks to bring their content closer to edge nodes.

flowchart TD
t11[Tier 1 ISP 1]
t12[Tier 1 ISP 2]
cdn[Content Provider]
ixp1[IXP]
ixp2[IXP]
ixp3[IXP]
r1[Regional ISP]
r2[Regional ISP]
a1[Access ISP]
a2[Access ISP]
a3[Access ISP]
a4[Access ISP]
a5[Access ISP]
a6[Access ISP]
a7[Access ISP]
a8[Access ISP]
a9[Access ISP]
t11 --- t12
t11 --- ixp1 & r1
t12 --- cdn
t12 --- ixp2 & ixp3 & r2
cdn --- ixp1 & ixp2 & ixp3
ixp1 --- r1 & a1
ixp2 --- r1 & r2
ixp3 --- r2
r1 --- a1 & a2 & a3 & a4
r2 --- a5 & a6 & a7 & a8 & a9

• Tier 1 - Commercial ISPs
  • Have national and international coverage.
• Content Provider Networks - Private networks
  • Connects it data centres to the internet, often bypassing tier 1 and regional ISPs.
• IXPs - Internet Exchange Points
  • Connect ISPs to one-another.
• Access ISPs
  • The people you pay for internet service.

The network edge is made up of the following devices:

• Hosts - Clients and servers.
• Servers - Often in data centres.

The hosts are connected to the internet via access networks through physical media:

• Wired links
• Wireless links.

The hosts are then connected to the network core which are a set of interconnected routers.

Access Networks & Physical Media

To connect a host to an edge router you would use:

• Residential networks.
• Institutional/enterprise networks.
• Mobile networks.

These connections have the properties:

• Bandwidth/transmission rate.
• Shared or dedicated access.

Cable Internet

This is a single coaxial cable that uses frequency division multiplexing FDM to split the frequency bands for different purposes and users.

graph LR
Host --- cm[Cable Modem] --- Splitter --- od[Other Households] --- CMTS --- ISP
subgraph Cable Headend
CMTS
end
subgraph House
Host
cm
TV
Splitter
end
TV --- Splitter

• CMTS - Cable modem termination system.
• HFC - Hybrid fibre coax
  • An asymmetric connection with 40 Mbps - 1.2 Gbps downstream, 30 - 100 Mbps upstream.

Homes share network access to the cable hardened.

Digital Subscriber Line (DSL)

Uses the existing telephone line to central office DSLAM:

• Data over DSL phone line goes to the internet.
• Voice over DSL phone line goes to the telephone network.

graph LR
Host --- cm[DSL Modem] --- Splitter --- DSLAM --- ISP
subgraph Central Office
DSLAM --- tn[Telephone Network]
end
subgraph House
Host
cm
Phone
Splitter
end
Phone --- Splitter

• DSLAM - DSL access multiplexer.
• Voice and data are transmitted at different frequencies over a dedicated line.
• Often asymmetric connection with 24 - 52 Mbps downstream, 3.5 - 16 Mbps upstream.

Home Networks

Often have the following:

• Cable/DSL modem
• Router, firewall, NAT
• Wired Ethernet
• WiFi AP

Several of these functions are often combined into the modem from the provider.

Wireless Networks

A shared wireless access network that connects a host to a router.

• WLANS - Wireless local area networks:
  • Typically ~30m
  • Often use WiFi IEEE 802.11b/g/n
• Wide area cellular access networks:
  • Provide by mobile operators ~10s km
  • 10s Mbps
  • 3G/4G/5G

Enterprise Networks

Similar home networks but often with separate components and additional hosts.

Sending Packets

For a host to send data on a network it:

• Takes application message.
• Breaks it into smaller chunks, known as packets, of length $L$ bits.
• Transmits packet into access network at a transmission rate $R$.
  • $R$ is the link transmission rate or bandwidth.

Physical Media

Twisted Pair (TP)

Two twisted insulated copper wires. This is the basis of the cable used for Ethernet.

• Cat 5 - 100Mbps to 1Gbps
• Cat 6 - 1 to 10Gbps

Coaxial Cable

Two concentric copper conductors. Multiple frequency channels are put on a cable to gain additional bandwidth.

• 100s Mbps per channel

Fibre Optic cable

Glass fibre carrying light pulses, each pulse a bit.

• High speed operation ~10-100s Gbps
• Low error rate as it is immune to electromagnetic interference.

Unguided Media

The signal is carried in the electromagnetic spectrum. There is no physical wire. There are propagation effects from the environment:

• Reflection
• Obstruction
• Interference

There are several types of radio link types:

• Terrestrial microwave:
  • 45 Mbps channels.
• WiFi
  • Up to 100s Mbps.
• Wide-Area
  • 4G ~10 Mbps.
• Satellite
  • Up to 45 Mbps per channel.
  • 270 ms end to end delay.
  • Can gain lower latency by using low orbit vs geosynchronous satellites.

Overview of the internet

There are several different types of devices that make up the internet.

• Hosts - Devices/end systems that are at the edge of the network.
• Packet switches - Routers/switches that forward packets to other devices.
• Communication links - Fibre/copper/radio transmission links between devices.
• Networks - A collection of devices, routers and links managed by an organisation. These can be:
  • Mobile networks.
  • Home networks.
  • Enterprise networks.
  • Local ISPs
  • National ISPs
  • Content provider networks
  • Datacenter networks

The internet is a network of networks that are generally enabled by interconnected ISPs.

Protocols

Control the sending and receiving of messages. There are many different types for different purposes.

Internet Standards

There are certain organisations that maintain open protocols for the internet:

• RFC - Request for comments.
• IETF - Internet engineering task forces.

Services

Infrastructure provides services to applications. These services provide a programming interface to distributed applications:

• Hooks - Allow sending receiving app to use the internet as a transport service.
• APIs provide service options analogous to the postal service.

Protocol Overview

Define the format, order of messages sent and recieved among network entities, and action taken on message transmission, and receipt.

To find the time the following sequence of actions might happen:

sequenceDiagram
me->>you: Hi
you->>me: Hello
me->>you: Got the time?
you->>me: 2:00 pm