Computer Systems

Summary

Summary

Table of Contents

Networks

Layered Network Models

layer-service-protocol-model

osi-layers

tcp-vs-osi

layers-1

layers-2

Presentation layer

Session Layer

HTTP

URL - Uniform Resource Locator

scheme:[//[user[:password]@]host[:port][/path][?query][#fragment]

e.g. abc://username:password@example.com:123/path/data?key=value#fragid1

Persistent connection

Response Codes

MDN: Status Codes

Cookies

FTP - File Transfer Protocol

SMTP - Simple Mail Transfer Protocol

Comparison HTTP vs SMTP

DNS - Domain Name System

Database: Resource Records

Type Value
A IPv4 address for hostname Name
AAAA IPv6 address for hostname Name
NS Hostname of authoritative DNS server for domain Name
CNAME Canonical hostname for alias hostname Name
MX Mail exchange. Canonical name of a mail server. Allows company to have same aliased name for mail and Web

Sockets

Sockets in C

int listenfd = 0, connfd = 0    // listen, connection file descriptors
char sendBuff[1025];            // send buffer
struct sockaddr_in serv_addr;
//create socket
listenfd = socket(AF_INET, SOCK_STREAM, 0);
// initialise server address
memset(&serv_addr, '0', sizeof(serv_addr)); 
// initialise send buffer
memset(sendBuff, '0', sizeof(sendBuff));

// type of address: Internet IP
serv_addr.sin_family = AF_INET;
// listen on any IP address
serv_addr.sin_addr.s_addr = htonl(INADDR_ANY);
// listen on port 5000
serv_addr.sin_port = htons(5000);
// bind
bind(listenfd, (struct sockaddr*)&serv_addr, sizeof(serv_addr));
// listen: maximum number of client connections to queue
listen(listenfd, 10);
// accept
connfd = accept(listenfd, (struct sockaddr*)NULL, NULL);
// write
snprintf(sendBuff, sizeof(sendBuff), "Hello World!");
write(connfd, sendBuff, strlen(sendBuff));
// close
close(connfd);
// connect
connect(connfd, (struct sockaddr *)&serv_addr, sizeof(serv_addr));
// receive
while ((n = read(connfd, recvBuf, sizeof(recvBuff)-1) > 0) {
  // process buffer
}

socket-usage-system-calls

UDP User Datagram Protocol

udp-segment-structure-kr

TCP Transport Control Protocol

Network Layer

Connectionless

connectionless-network

Connection oriented

connection-oriented-network

Comparison: Virtual Circuit vs Datagram Networks

Issue Datagram Network Virtual-circuit network
Circuit setup Not needed Required
Addressing Each packet contains full source/dest address Each packet contains short VC number
State information Routers don’t hold state info about connections Each VC requires router table space per connection
Routing Packets routed independently Route chosen when VC set-up, all packets follow it
Effect of router failure None, except packets lost during crash All VCs through the failed route are terminated
QoS / Congestion control Difficult Easy if resources can be allocated in advance for each VC

Quality of Service

Internet protocol

Types of Address

IPv4 Address Classes and CIDR

IPv6

IPv6 Address

Consider 2001:0db8:0000:0000:0000:ff00:0042:8329 Removing leading zeros: 2001:db8:0:0:0:ff00:42:8329 Use double colon: 2001:db8::ff00:42:8329

IPv6 Header

ipv6-header

IPv4 header

ipv4-header

Subnets

Network Address Translation (NAT)

nat-operation

Private address ranges used:

NAT Criticisms

Fragmentation

ip-fragmentation

Downsides

Path MTU Discovery

path-mtu-discovery

IPv4 vs IPv6 fragmentation

Routing

Routing tables

e.g. 203.32.8.0 255.255.255.0 Eth0

Properties of a good routing algorithm

There are many goals, often in tension:

fairness-vs-efficiency-routing

Adaptive vs Non-adaptive

Flooding

Optimality Principle

sink-tree

Shortest Path

Steps

Steps each router performs: share information, then run centralised algorithm

  1. Discover neighbours and learn network addresses
  2. Set distance/cost metric to each neighbour, building graph
  3. Construct packet containing what it has learned
  4. Send packet to/receive packets from all other routers
  5. Compute shortest path to every other router (e.g. with Dijkstra’s)

Neighbour discovery

link-state-packet

Distance-Vector Routing

Border Gateway Protocol

valley-free-routes

IP Multicasting

Membership

Observations

Congestion Control

congestion-control-network

Congestion Control Solutions

Many approaches operating at different time scales

congestion-control-network-2

Explicit Congestion Control

explicit-congestion-control

Internet Control Protocols

ICMP Internet Control Message Protocol

DHCP Dynamic Host Configuration Protocol

MAC (Medium Access Control) Addresses

ARP Address Resolution Protocol

  1. Broadcasts Ethernet packet asking who owns target IP address on broadcast address FF:FF:FF:FF:FF:FF
  2. Broadcast arrives at every host on the network. The owner responds with its MAC address

Layer 2

Operating Systems

Operating Systems Fundamentals

Good overview of OS concepts: Linux kernel labs

Modes of operation

unix-system

Processes

Process state

  1. running: using CPU
  2. ready: runnable; temporarily stopped while another process is running
  3. blocked: unable to run while waiting for external event

process-fsm

Process Termination

Typical conditions for process termination:

Address space

process-segments

Multiprogramming

System call

user-kernel-mode

system-call-read

POSIX System calls

posix-system-calls

process-creation-exit

Standard C library handling of write system-call-write

Interrupt

Process table

Threads

Classical thread model

process-vs-thread

POSIX Threads pthreads

pthreads-calls

User-level threads vs kernel-level threads

threads-user-vs-kernel

Process Communication

Interprocess Communication

Race Conditions

critical-region

Requirements for solution to avoid race conditions

Avoiding race conditions

Methods for avoiding race conditions include:

Strict alternation with busy waiting

// process A
while (TRUE) {
  while (turn != 0) { }
  critical_region();
  turn = 1;
  noncritical_region();
}

// process B
while (TRUE) {
  while (turn != 1) { }
  critical_region();
  turn = 0;
  noncritical_region();
}

Test and Set Lock (TSL)

TSL RX, LOCK

Entering and leaving critical region using TSL instruction

enter_region:
  TSL REGISTER,LOCK     // copy lock to register, set lock to 1
  CMP REGISTER,#0       // was lock 0?
  JNE enter_region      // if not, lock was set, so loop
  RET                   // return to caller; critical region entered

leave_region:
  MOVE_LOCK,#0          // store 0 in lock
  RET                   // return to caller

Busy Waiting

Blocking

Deadlock

deadlock

Process Scheduling

Process Scheduler

Processes can be categorised as being CPU-bound or I/O-bound:

Scheduling decisions are made:

Scheduling Algorithms

Scheduling Algorithm Goals

All systems

Batch Systems

Interactive

Real-time

Scheduling Algorithms

First-come first served

Shortest Job First

Round-Robin Scheduling

Priority Scheduling

priority-scheduling

Others

Memory Management

Memory hierarchy

Ideally:

Reality:

memory-hierarchy

Memory allocation and management

No Memory Abstraction

relocation-problem

Memory Abstraction: Address spaces

Simple dynamic relocation approach that used to be common, hardware support with base and limit registers:

Swapping

swapping swapping-2

Managing free memory

Bitmaps

bitmap

Linked Lists

linked-list-mem-mgmt

Memory Allocation Algorithms

Virtual memory

Fragmentation

Memory management unit MMU

memory-management-unit

page-table

internals-mmu

Page Table Entry

page-table-entry

Translation lookaside buffer

tlb

Multilevel page tables

multi-level-page-table

Memory Replacement Algorithms

Summary

Algorithm Comment
Optimal Not implementable, useful benchmark
Not recently used Very crude approximation of LRU
FIFO May throw out heavily used pages
Second chance Big improvement over FIFO
Clock Realistic
LRU Excellent, difficult to implement
Not frequently used Crude approximation of LRU
Aging Efficient approximation of LRU
Working set Expensive to implement
WSClock Good efficient algorithm

Optimal Page Replacement

Not recently used

First in first out replacement

Second Chance algorithm

second-chance

Clock

clock-page-replacement

Least Recently Used

Working Set

Security

Goal

Symmetric cryptography

Encrypt(SecretKey, message) -> ciphertext
Decrypt(SecretKey, ciphertext) -> message

AES: Advanced Encryption Standard

ECB: Electronic Code Book mode

ecb-penguin

CBC: Cipher Block Chaining mode

cipher-block-chaining

Public Key Cryptography

  1. $D(E(P)) = P$ i.e. if we apply D to encrypted message we get plaintext
  2. Exceedingly difficult to deduce D from E
  3. E cannot be broken by chosen plaintext attack

RSA

Digital Signatures

Public key approach

digital-signatures

Message Digests

message-digests

SHA-1

sha-1

Management of Public Keys

subverting-public-key-encryption

Certificates

Alice asks issuer to sign info d = (PK_alice, Alice)
s = Sign(SK_issuer, d’)
Certificate: Issuer, signature s, d’ = (Issuer, PK_Alice, Alice, …) Verification: Verify(PK_issuer, d’, s)

X.509

Fields of X509 certificate:

x509-certificate

Public key infrastructure

public-key-infrastructure-hierarchy

Certificate issuance

domain-validation

Certificate Validation

PGP

Secure Communication

Goals

MAC Message Authentication Code

t = Mac(k, m)         # compute tag
b = Verify(k, m, t)   # bit is 0/1 indicating success of verification

mac-kurose

  1. Alice creates $m$, concatenates $s$ with $m$ giving $m+s$. Computes hash $H(m+s)$, called the message authentication code
  2. Alice appends the MAC to the message $m$: $(m, H(m+s))$ and sends this to Bob
  3. Bob receives $(m,h)$ and knowing $s$, calculates MAC $H(m+s)$. If $H(m+s) = h$ Bob is convinced of the integrity of the message.

e.g. CBC-MAC, HMAC

HMAC

t = Hash((k XOR opad) || Hash((k XOR ipad) || m))

Authenticated Encryption

// Encrypt
c = Enc(SK, m)
// Compute tag over ciphertext
t = MAC(k, c)
// Transmit (c, t) 
// Verify tag
b = Verify(k, t, c)
// if successful, decrypt
m = Dec(SK, c)

Diffie-Hellman Key Exchange

Wiki

diffie-hellman-paint

diffie-hellman-2

SSL/TLS history

TLS Basics

Handshake protocol

Record protocol

Local TLS Interception

Network level TLS Interception

tls-proxy

QUIC

quic

System Security

Goal

Trusted Computing Base

reference-monitor

Protection Domains

protection-domains

Access Control Lists

acl

Capabilities

capability-liest

Code Signing - Specialised hardware

code-signing

Encrypted hard drive

Trusted Platform Module TPM

Remote Attestation

Intel SGX

Covert Channels

covert-channel

Future Computer Systems

History of Multi-User Systems

Cloud Services

x-as-a-servce

x-as-a-service-2

SaaS

IaaS

PaaS

Serverless

System Administrator


Edit this page.