CS2105 Notes

Packet-Switching Paradigm

• Packet Transmission Delay = time needed to transmit L-bit packet into link = $L/R$
  • Packets of length L bits
  • Transmission rate R (bits / second) aka link capacity, aka link bandwidth
• Routing: Determines source-destination route taken by packets (decided by routing algorithms)
• Forwarding: Move packets from router's input to appropriate output

Circuit-Switching Paradigm

• End-end resources allocated to, reserved for "call" between source and destination.
• No sharing of resources
  • Circuit-like performance
• Circuit segment idles if not used by call
• Used by traditional telephone networks

Internet Structure

Network of Networks.

• Access Nets
  • Access nets => regional net => ISP
  • Access nets => ISP
• ISP
  • ISP => IXP (Internet Exchange Point)
  • ISP <=> ISP (Peering Link)
• Content Delivery Network covers everything, bypassing tier-I and regional ISPs
• Router
  • For communication to OTHER local area networks
• Switch
  • For local area network
  • Local connections don't go through router
• Hub
  • Switch, but send same message to everyone (like a broadcast)

Packet Delay

• Nodal Processing $d_{proc}$
  • Check bit errors
  • Determine output link
  • Very fast
• Queueing Delay $d_{queue}$
  • Time waiting at output link for transmission
  • Depends on congestion level of router
• Transmission Delay $d_{trans}$
  • Time for a packet to be transferred onto the physical link
  • L: packet length (bits)
  • R: link bandwith (bps)
  • $d_{trans} = L/R$
• Propagation Delay $d_{prop}$
  • Time for a packet to travel along the physical link
  • d: length of physical link
  • s: propagation speed (~$2*10^8$ m/sec)
  • $d_{prop} = d/s$

Client-Server Architecture

• Server
  • Always-on host
  • Permanent IP
  • Data centers for scaling
• Client
  • Communicates with server
  • May be intermittently connected
  • May have dynamic IP addresses
  • Do not communicate directly with each other

P2P Architecture

• No always-on server
• Peers request and provide service to other peers
  • Self scalability! New peers bring service capacity & demand
• Peers are intermittently connected and change IP addresses, very complex management

• Process: program running within a host
  • Within same host, two processes communicate using inter-process communication (defined by OS)
  • Processes in different hosts communicate by exchanging messages
  • Client-Server
    • Client process initiates communication
    • Server process waits to be contacted
  • Process can have multiple ports for different purposes!
• Socket: process sends/receives messages from socket
  • destination IP address + source IP address + port numbers => identifies socket

TCP Service

• Reliable data transport (correct & ordered)
• Flow control: sender won't overwhelm receiver
• Congestion control: throttle sender when network is overloaded
• Does not provide timing, minimum throughput guarantee, security
• Connection-oriented: requires setup
• Reliable byte stream, connection-oriented

UDP Service

• Unreliable data transfer
• Does not provide: reliability, flow control, congestion control, timing, minimum throughput guarantee, security, connection setup
• Unreliable datagram, connectionless

HTTP

HTTP uses TCP connection. HTTP is stateless, requests are independent.

• Client initiates TCP connection.
• Server accepts TCP connection from client.
• HTTP messages exchanged between browser and Web Server.
• TCP connection is closed.

Note: need to fetch the HTML file itself first before the other objects / resources on the page.

GET /index.html HTTP/1.1\r\n
Host: www-net.cs.umass.edu\r\n
User-Agent: Firefox/3.6.10\r\n
Accept: text/html,application/xhtml+xml\r\n Accept-Language: en-us,en;q=0.5\r\n Accept-Encoding: gzip,deflate\r\n Accept-Charset: ISO-8859-1,utf-8;q=0.7\r\n Keep-Alive: 115\r\n
Connection: keep-alive\r\n
\r\n

method sp URL sp version cr lf
header-field-name value cr lf
...
header-field-name value cr lf
cr lf
BODY

HTTP/1.1 200 OK\r\n
Date: Sun, 26 Sep 2010 20:09:20 GMT\r\n Server: Apache/2.0.52 (CentOS)\r\n Last-Modified: Tue, 30 Oct 2007 17:00:02
    GMT\r\n
Content-Length: 2652\r\n
Keep-Alive: timeout=10, max=100\r\n Connection: Keep-Alive\r\n
Content-Type: text/html; charset=ISO-8859-
    1\r\n data
\r\n
data data data data data ...

Web Caches (Proxy Server)

Satisfy client request without involving origin server.

DNS: Domain Name System

Mapping between domain names (or canonical name) and IP address.

Distributed, hierarchical database

• Client wants to find www.amazon.com
  • Client queries root server to find .com server
  • Client queries .com server to get amazon.com server
  • Client queries amazon.com server to get www.amazon.com IP address

Root name servers are contacted by local name server that cannot resolve name. Provides IP address of TLD servers.

TLD servers are responsible for com, org, net, edu, country domains, etc...

Authoritative DNS servers provide authoritative hostname to IP mapping for organisation's named hosts. Can be maintained by organisation or service provider.

• Local DNS servers are not in global hierarchy of distributed database (because it can be private!!).

Port Number

• 16-bit integer (0 to 1023) are reserved for standard use.

Socket Programming with UDP

• No handshaking before sending data
• Sender explicitly attaches (IP destination address) and (port number) with each packet
• Receiver extracts (sender IP address) and (port number) from each packet
• May be lost or received out-of-order
• Unreliable datagrams

DNS (port number 53) resolving uses UDP.

from socket import *

server_name = "hostname"
server_port = 12000

client_socket = socket(AF_INET, SOCK_DGRAM) # for ipv4, for UDP
message = "blah"
client_socket.sendto(message.encode(), (server_name, server_port)) # encode to byte array
recv_message, server_address = client_socket.recvfrom(2048) # receive up to 2048 bytes
decoded_message = recv_message.decode()
client_socket.close()

from socket import *

server_port = 12000
server_socket = socket(AF_INET, SOCK_DGRAM)
server_socket.bind(("", server_port)) # empty IP address defaults to localhost
while True:
    message, client_address = server_socket.recvfrom(2048)
    modified_message = modify(message.decode())
    server_socket.sendto(modified_message.encode(), client_address)

Socket Programming with TCP

• Client must perform handshake
  • Server must be running and have a welcome socket
• TCP server creates new socket for each client
  • Source port numbers / connection are used to distinguish clients
    • No need to explicitly send (IP address) + (port number)

...
client_socket = socket(AF_INET, SOCK_STREAM) # for TCP
client_socket.connect((server_name, server_port))
client_socket.send(message.encode())
recv_message = client_socket.recv(1024)
client_socket.close()

server_socket = socket(AF_INET, SOCK_STREAM)
server_socket.bind(("", server_port))
server_socket.listen(1) # maximum number of connections
while True:
    connection_socket, addr = server_socket.accept() # waits for connection
    connection_socket.recv(1024)
    connection_socket.send(modified_message.encode())
    connection_socket.close() # close connection to THIS client

UDP: User Datagram Protocol

• On top of IP:
  • Adds connectionless multiplexing / de-multiplexing
  • Adds checksum
• Unreliable, but more performant
  • Often used by streaming multimedia apps (loss tolerant & rate sensitive)
• Application implements error detection and recovery mechanisms to achieve reliable transmission

Why UDP?

• No delay of establishing connection
• Simple: no connection state
• Small header size
• No congestion control

UDP Segment Header

<--       32 bits       -->
Source Port # | Dest Port #
Length        | Checksum

PAYLOAD...

• Length = payload length (in bytes), including header (header is always 8 bytes)

UDP / TCP Checksum

1. Treat UDP segment as sequence of 16-bit integers
   1. Includes Header + Payload + Pseudo-Header (source address / destination address)
2. Apply binary addition on every 16-bit integer
3. Carry (if any) from MSB will be added to result
4. Compute 1's complement (flip every bit) => UDP Checksum

Creating Reliable Data Transfer

Pipelined Protocols

TCP Header

<--        32 bits        -->
Source Port # | Dest Port #
       Sequence Number
    Acknowledgement Number
head    UAPRSF| rwnd
Checksum      | urgent_data_pointer
  options (variable length)

Application Data (variable length)

• Sequence number of first byte
  • Initial sequence number is randomly chosen
  • SYN consumes an extra sequence number
  • ACK does not consume sequence numbers
• Acknowledgement number: sequence number of next expected byte (from other side)
  • Cumulative ACK
• head length of header in 32-bit words (4 bits)
  • minimum size is 5 words, maximum size is 20 words, allows for up to 40 bytes of options
• reserved / unused space (4 bits)
• U urgent data (not generally used)
• A acknowledgement bit: 1 if valid acknowledgement field, 0 if should ignore (only for first packet of set-up)
• P push data now (not generally used)
• RST, SYN, FIN setup, teardown commands
• rwnd receive window: # bytes receiver is willing to accept
  • Used for congestion control
• Same checksum as UDP's checksum
• TCP spec doesn't mention how receiver handles out-of-order segments (can choose to buffer)

Connection-Oriented Demux

• Same destination IP address + port => demultiplexed to different sockets
• Identified by (source IP, source port, dest IP, dest port)
  • Handled by OS

TCP 3-way Handshake

• Client sends TCP with SYN bit, with SEQ = x
• Server sends TCP with SYN bit, with SEQ = y, A = 1, ACK = x+1 (SYN consumes a sequence number)
• Client sends TCP with A = 1, ACK = y+1 (might also send data)

TCP Closing Connection

• Client, Server each close their "sending side"
  • Sends TCP segment with FIN = 1
  • Responds to FIN with ACK, can combine with own FIN
  • After closing, can no longer send data (except ACK)
  • BUT, still receives data!
• After sending ACK for a FIN, must wait 2 * max segment lifetime in case this last ACK is lost!

TCP RDT

TCP Fast Retransmit

• If sender receives 4 ACKS for same data (aka triple duplicate ACKs)
  • Immediately resend unACK'd segment with smallest sequence number

IP Addressing

Interface: connection between host / router and physical link

• routers typically have multiple interfaces
• host typically has one or two interfaces (wired Ethernet, or wireless WiFi)
• an IP address is associated with each interface

DHCP

2 ways to get IP address:

• Host's IP address is hard-coded by system admin.
• OR DHCP (don't need any configuration, dynamically obtain)

Dynamic Host Configuration Protocol: allows host to dynamically obtain IP address from network server when joining a network

• goal:
  • can renew lease on address
  • allows reuse of addresses (only holds address when someone is actively using it)
  • support for mobile users
• overview - everything is broadcasted (only difference is 67 or 68)
  • host broadcasts DHCP discover message (optional)
    • uses source IP of 0.0.0.0 (because not assigned yet)
  • server responses with DHCP offer message - containing a few IP addresses (optional)
  • host requests IP address with DHCP request message
    • uses source IP of 0.0.0.0 (because not assigned yet)
  • server sends address with DHCP ack message
  • after which, done, the host is officially assigned to that IP address
  • also exists: DHCP renewal (request to re-use IP address) and DHCP release (give up IP address).
• DHCP can also return
  • address of first-hop router for client
  • name and IP address of DNS server
  • network mask
• DHCP runs over UDP
  • DHCP server port number: 67
  • DHCP client port number: 68

Note: there might be multiple DHCP servers (offering at the same time), which is why everything must be broadcasted, so everyone is aware.

Even if a subnet is not using DHCP, router will relay it to a subnet with a DHCP server

IPv4 Datagram Format

<--        32 bits        -->
ver           | IP datagram length
identifier    | flags | fragment offset
TTL | upper_layer | header_checksum
        source IP address
         dest IP address
Data

• ver (4 bits)
• IP datagram length (16 bits) - header + data
• identifier (16 bits) - for fragmentation / reassembly
• flags (3 bits)
  • 1bit for frag bit
• fragment offset (13 bits)
• TTL (8 bits) - number of remaining hops (decremented at each router), kills datagram when TTL = 0
• upper layer protocol (8 bits): TCP / UDP (violates upper-lower abstraction!)
• header_checksum (16 bits): only for IP header
• total: 20 bytes

NAT Table

Network Address Translation

• WAN (wide-area network) - the internet
  • all datagrams leaving LAN have same source NAT ip address (with unique port number)
  • Port numbers are from $[0, 2^{16}]$, but $[0, 2^{10} = 1024]$ are reserved.
• LAN (local-area network)
  • within LAN, hosts use private IP address to communicate
  • Port numbers are from $[0, 2^{16}]$, none are reserved. So, can use any in that range!

NAT routers must

• outgoing: replace (source IP address, port number) of every outgoing datagram to (NAT ip address, new port number)
• store: remember in NAT table the mapping of the above
• incoming: replace (NAT ip address, new port number) in destination fields of every incoming datagram with corresponding (source IP address, port number) stored in NAT table

Motivations & Benefits & Cons

• only require one public IP for the NAT router
• all hosts use private IP address, can change these without notifying outside world
• can change ISP without changing addresses of hosts in local network
• hosts inside local network are not explicitly addressable and visible by outside world (protected by NAT router, good for security!)
• bad for peer to peer connections

Intra-AS Routing

AS = Autonomous Systems, normally tied to an ISP (i.e. Singtel, Starhub...)

• finds a good path between two routers within an AS
• single admin, no policy decisions needed
• routing focuses on performance
• commonly used: RIP, OSPF

Inter-AS Routing

not covered in-depth in CS2105

• handles interface between ASs
• admin often wants control over how traffic is routed, who routes through net, etc
• security policy over performance
• de facto standard protocol: BGP

ICMP

Internet Control Message Protocol: used by hosts & routers to communicate netowrk-level information

• error reporting: unreachable host / network / port / protocol
• echo request / reply (used by ping)

ICMP messages are carried in IP datagrams, ICMP header starts after IP header. It is in the transport layer, but only used for network stuff. (still considered network layer)

ICMP Header = type + code (sub-type) + checksum + others

* some of the ICMP types and codes

• ping checks if remote host will respond (i.e. is there a connection?)
• traceroute sends small packets, with different TTL, to attempt to display routes to get to a remote host
  • might need to run a few times to get all possible routes

Error Detection

Network Links

1. point-to-point link
   • sender and receiver connected by dedicated link
   • Point-to-Point Protocol (PPP), Serial Line Internet protocol (SLIP), no need for multiple access control
2. broadcast link (shared medium)
   • multiple nodes connected to shared broadcast channel
   • when a node transmits a frame, the channel broadcasts the frame, and every other node receives a copy.
   • collision if a node receives two or more signals at the same time (cannot distinguish!)

MAC (Media Access Control) Address

Every adapter (NIC) has a MAC address (aka physical or LAN address).

NIC = Network Interface Card; ROM = Read-Only Memory

• used to send and receive link layer frames
• when an adapter receives a frame, checks if destination MAC address of the frame matches its own
  • if yes, adapter extracts the enclosed datagram and passes it to protocol stack
  • if no, discard
• MAC address is typically 48-bits, burned in NIC ROM (sometimes software settable, but most devices don't let you configure it)
  • typically in hexadecimal, i.e. 5C-F9-DD-E8-E3-D2
  • MAC address administered by IEEE (first 3 bytes identifies vendor of an adapter)
  • broadcast address: FF-FF-FF-FF-FF-FF (all 1s)
• duplicate MAC addresses in the same subnet is problematic and will be severely disrupted (doesn't matter if not in same subnet)

Ethernet

ARP - Address Resolution Protocol

Find 48-bit MAC address with 32-bit IP address.

Each IP node has an ARP Table, <IP address, MAC address, TTL>

Router, Host all require ARP table. Switch only requires Forwarding Table.

Only stores information for some neighbouring hosts in same subnet (LAN).

• Same Subnet
  1. If A knows B's MAC address from its ARP table
     1. Create a frame with B's MAC address and send it
     2. Only B will process this frame (others will ignore even if they receive it)
  2. A does not know B's MAC address
     1. A broadcasts an ARP query packet, containing B's IP address
        1. destination MAC address of FF-FF-FF-FF-FF-FF (broadcast address)
        2. All other nodes (in subnet) will receive it, but only B will reply
     2. B replies to A with its MAC address (unicast to A's MAC address)
     3. A caches B's IP-to-MAC address mapping in its ARP table (until TTL expires)
     4. Then, do as for case 1
• Different Subnet - Gateway Router R will handle connection between subnets
  1. A creates IP datagram with IP source A, destination B
  2. A creates link-layer frame with R's MAC address as destination address, frame contains A-to-B IP datagram
     1. If don't know R's MAC address, do ARP for it
  3. R receives frame and passes the datagram to IP
  4. R forwards datagram with IP source A, destination B
  5. R creates link-layer frame with B's MAC address as destination address, frame contains A-to-B IP datagram (only Ethernet frame changes, IP header and everything above doesn't change)

Cryptography

• Symmetric Key Cryptography = sender and receiver uses same key
  • need to agree on key
• Asymmetric Key Cryptography (aka Public Key Cryptography) = sender and receiver uses different key
  • do not share secret key, encrypt with public, decrypt with private (or vice versa)
  • slow compared to symmetric
  • in practice, one party creates a symmetry key, and uses RSA to transfer it, then uses that symmetric key as the session key

Message Integrity

Uses Cryptographic Hash Functions

• $H(.)$ takes large (unbounded size) input $m$ and produces fixed-size message digest / fingerprint
• computationally infeasible to find any two different messages $x$ and $y$ such that $H(x) = H(y)$.
  1. pre-image resistance
     1. given hash output, can't find original message
  2. second pre-image resistance
     1. given hash(m1) = h, very hard to find m2 such that hash(m2) = h as well
  3. collision resistance
     1. hard to find m1 and m2 such that hash(m1) = hash(m2), and m1 != m2
• small change in input should result in large change in hash output
• passwords are hashed using similar techniques, that's why you cannot recover the original password
• common ones
  • MD5 (cryptographically broken), still used for non-critical uses (e.g. websites share MD5 hash for file downloads)
  • SHA-1 (deprecated, cryptographically broken)
  • SHA-2, SHA-3

Certificate Authorities (CA)

CA maintains public database of everyone's public key.

CA signs its messages with its own private key. The public key of CAs are hardcoded into Operating System, as a list of Trusted Root Certificate Authorities.

• $E$ (person or router) registers its public key with CA
  • $E$ provides a proof of identity to CA
  • CA creates certificate binding $E$ to its public key, this contains $E$'s public key digitally signed by CA

Firewalls

Firewall isolates organisation's internal net from larger Internet, allowing some packets, while blocking others.

• prevents DoS (Denial of Service) attacks: SYN flooding with bogus TCP conenctions
• prevents illegal modification / access to internal data
• allow only authorised access to inside network
• internal network connected to Internet via router firewall (both IN and OUT)
• router filters packet-by-packet, decides to forward / drop packets based on (network & transport layer)
  • source & destination IP address
  • TCP / UDP source and destination port numbers
  • ICMP message type
  • TCP SYN & ACK bits
• examples
  • no outside web access: drop all outgoing packets to any IP address, port 80
  • prevent network from being used for a smurf DoS attack: drop all ICMP packets going to a "broadcast" address (e.g. 130.207.255.255)
  • prevent network from being tracerouted: drop all outgoing ICMP TTL expired traffic
• limitations
  • IP spoofing: router can't know if data really comes from claimed source
  • can become bottleneck (can use multiple firewalls instead, but costly)
  • tradeoff: degree of communication with outside world VS level of security (e.g. nuclear rocket computers not connected to Internet)
  • many highly protected sites still suffer from attacks (might provide a false sense of security)

Application Types

• streaming stored: can begin playout before downloading entire file
  • stored at server / CDNs, can transmit faster than audio / video will be rendered
  • pre-processing done to optimise this
• conversational (two-way live): interactive
  • delay more than 400ms is intolerable
• streaming live (don't have to be real-time, 10s delay is fine)
  • typically done with CDNs

Data is transmitted over-the-top (over the Internet, as compared to cable / broadcast / satellite)

* applicable for both video and audio

Video

Videos are sequences of images displayed at a some constant rate. Digital image: array of pixels, each pixel represented by bits. Videos have high bit rate. To reduce data usage, compress the video by using redundancy.

• reducing redundancy
  • Spatial coding (within image): aggregate pixels of the same colour
  • Temporal coding (between two frames): only send the delta of the frames
  • reduces the size of each frame, number of frames remain the same
• bit rate
  • Constant Bit Rate (CBR): fixed video encoding rate (might be wasteful)
    • not responsive to complexity of video
    • bitrate need to be high enough to handle the most complex segments of video
    • well-suited for real-time encoding because of consistency
  • Variable Bit Rate (VBR): encoding rate changes with spatial, temporal coding
    • well-suited for on-demand video because can pre-process data, and can buffer data

Audio

Sampled at constant rate, each sample is quantised (rounded) to a value represented by bits. (i.e. 256 quantised values require 8 bits, so with 8,000 samples / sec => 8,000 * 8 = 64,000 bps)

Streaming Stored Content

• constraints
  • Continuous Playout Constraint: once client playout begins, playback must match original timing, even with network delay being variable.
  • allow client interactivity: pause, fast-forward, rewind, jumping, etc...
  • video packets may be lost / retransmitted
• application playback buffer to buffer content, let fill rate = $x(t)$, average fill rate = $\bar x$, playout rate = $r$
  • if $\bar x < r$: buffer eventually empties (video freezes until buffer fills)
  • if $\bar x > r$: buffer will not be empty provided initial playout delay is large enough to absorb variability in $x(t)$
  • initial playout delay tradeoff:
    • buffer starvation less likely with larger delay
    • but larger delay until user can start watching
  • buffers data for smooth playback, client can play any part of this buffer (NOT the same as TCP buffer, TCP buffer is for storing out-of-order segments)

RTP vs RTCP

• RTP = Real-Time Transport Protocol
  • Delivers interactive data
    • Pure data only
  • Purpose: time-stamp, sequence and mixing (combining video with audio)
  • UDP because speed is most important, don't need to be reliable
• RTCP = RTP Control Protocol
  • Delivers statistics and control information (non-interactive)
    • How many bits, quality of bitstream
  • Delivered over next odd UDP port number that the RTP stream uses
• RTSP = Real-Time Streaming Protocol
  • Used to establish and control media sessions during endpoints.
    • Setup
    • Play / stop
    • Change quality
  • TCP because requires reliability, but not necessarily speed
    • Need to make sure the setup is correct

Voice Over IP (VoIP)

• higher delays are noticeable, impairs interactivity
  • < 150ms: good, > 400ms: bad
  • includes application level delays
    • network loss: IP datagram lost due to network congestion
    • delay loss: IP datagram arrives too late for playout (just discard)
      • typically use UDP
• data loss over 10% makes conversation unintelligible
  • modern networks rarely have data losses > 10%, so this isn't really an issue
• only sends chunks when during talk spurts (vs silent periods); 20ms chunks at 8Kbytes / second: 160 bytes of data
• application-layer header added to each chunk: chunk + header is then encapsulated into UDP or TCP segment
• packet lengths are ~20ms (fraction of a syllable!); low to minimise impact of packet loss, at a tradeoff for efficiency

HTTP Streaming

Video on Demand (VoD) video streaming increasingly uses HTTP streaming. Can just GET the whole video file, but wasteful because requires a large client buffer. Also, cannot have different encoding of videos to account for variation in device and network bandwidth.

Most VoD uses either DASH or Apple's HLS (HTTP Live Streaming).

Content Distribution Networks (CDNs)

1. single large mega-server (doesn't scale!)
   • single point of failure, and network congestion
   • potentially long path to distant clients
   • multiple copies of videos over outgoing link
2. store / serve multiple copies of videos at multiple geographically distributed sites (CDN)
   • enter deep: push CDN servers deep into many access networks (typically at ISPs, close to users)
   • bring home: smaller number (10's) of larger clusters in IXPs near, but not within access networks