CS6456: Graduate

Operating Systems
Brad Campbell – [email protected]
https://www.cs.virginia.edu/~bjc8c/class/cs6456-f19/

1
Transport services and protocols
applicatio
n
 provide logical communication transport
network
between app processes data link
running on different hosts physical

lo
 transport protocols run in end

gi
ca
systems

enl
d-
• send side: breaks app

to
-e
messages into

nd
tra
segments, passes to

ns
network layer

po
rt
• rcv side: reassembles applicatio

segments into n
transport

messages, passes to network

data link
physical
app layer
 more than one transport
protocol available to apps
• Internet: TCP and UDP 3-2
Transport vs. network layer

 network layer: household analogy:

logical
communicatio 12 kids in Anicia’s
house sending
n between letters to 12 kids in
hosts Bill’s house:
 transport • hosts = houses
layer: logical • processes = kids
communicatio • app messages =
n between letters in envelopes
processes • transport protocol =
Anicia and Bill who
• relies on and demux to in-house
enhances siblings
network layer • network-layer
services protocol = postal
service 3-3
TCP: Overview RFCs: 793, 1122, 1323, 2018, 2581

• point-to-point:  full duplex data:

• bi-directional data flow
• one sender, one
in same connection
receiver • MSS: maximum
• reliable, in-order segment size
 connection-oriented:
byte steam:
• handshaking
• no “message (exchange of control
boundaries” msgs) inits sender,
receiver state before
• pipelined: data exchange
• TCP congestion  flow controlled:
and flow control • sender will not
set window size overwhelm receiver
3-4
 TCP segment structure
32 bits
URG: urgent data counting
(generally not used) source port # dest port #
by bytes
sequence number of data
ACK: ACK #
valid acknowledgement number (not segments!)
head not
PSH: push data now len used
UAP R S F receive window
(generally not used) # bytes
checksum Urg data pointer
rcvr willing
RST, SYN, FIN: to accept
options (variable length)
connection estab
(setup, teardown
commands)
application
Internet data
checksum (variable length)
(as in UDP)

3-5
TCP seq. numbers, ACKs
outgoing segment from sender
sequence numbers: source port # dest port #
sequence number
• byte stream “number” acknowledgement
of first byte in number rwnd
checksum urg pointer
segment’s data
window size
acknowledgements: N
• seq # of next byte
expected from other
sender sequence number space
side
• cumulative ACK sent sent, not- usable not
ACKed yet ACKed but not usable
Q: how receiver handles out- (“in- yet sent
of-order segments flight”)
incoming segment to sender
• A: TCP spec doesn’t source port # dest port #
say, - up to sequence number
acknowledgement
implementer number A rwnd
checksum urg pointer

3-6
TCP seq. numbers, ACKs
Host A Host B

User
types
‘C’ Seq=42, ACK=79, data = ‘C’
host ACKs
receipt of
‘C’, echoes
Seq=79, ACK=43, data = ‘C’ back ‘C’
host ACKs
receipt
of echoed
‘C’ Seq=43, ACK=80

simple telnet scenario

3-7
TCP: retransmission scenarios
Host A Host B Host A Host B

SendBase=92
Seq=92, 8 bytes of data Seq=92, 8 bytes of data
timeout

timeout
Seq=100, 20 bytes of data
ACK=100
X
ACK=100
ACK=120

Seq=92, 8 bytes of data Seq=92, 8

SendBase=100 bytes of data
SendBase=120
ACK=100
ACK=120

SendBase=120

lost ACK scenario premature timeout

3-8
TCP fast retransmit
Host A Host B

Seq=92, 8 bytes of data

Seq=100, 20 bytes of data
X

timeout ACK=100
ACK=100
ACK=100
ACK=100

Seq=100, 20 bytes of data

fast retransmit after sender

receipt of triple duplicate ACK 3-9
Principles of congestion control
congestion:
• informally: “too many sources
sending too much data too fast for
network to handle”
• different from flow control!
• manifestations:
• lost packets (buffer overflow at routers)
• long delays (queueing in router buffers)
• a top-10 problem!
3-10
TCP congestion control: additive increase
multiplicative decrease
 approach: sender increases transmission rate (window
size), probing for usable bandwidth, until loss occurs
• additive increase: increase cwnd by 1 MSS every
RTT until loss detected
• multiplicative decrease: cut cwnd in half after loss
additively increase window size …
congestion window size …. until loss occurs (then cut window in half)
cwnd: TCP sender

AIMD saw tooth

behavior: probing
for bandwidth

time
3-11
TCP Slow Start
Host A Host B
 when connection
begins, increase rate
exponentially until one segm
ent

RTT
first loss event:
• initially cwnd = 1 MSS two segm
ents
• double cwnd every RTT
• done by incrementing
four segm
cwnd for every ACK ents

received
 summary: initial rate
is slow but ramps up
time
exponentially fast

3-12
Why is TCP fair?
two competing sessions:
 additive increase gives slope of 1, as throughout increases
 multiplicative decrease decreases throughput proportionally

R
Connection 2 throughput equal bandwidth share

loss: decrease window by factor of 2

congestion avoidance: additive increase
loss: decrease window by factor of 2
congestion avoidance: additive increase

Connection 1 throughput R
3-13
Network layer: data plane, control plane

Data plane Control plane

 network-wide logic
 local, per-router  determines how datagram is
function routed among routers along
 determines how end-end path from source host
to destination host
datagram arriving
 two control-plane approaches:
on router input port
• traditional routing
is forwarded to algorithms: implemented in
router output port routers
forwarding
 values in arriving function • software-defined
packet header networking (SDN):
0111 1
implemented in (remote)
2
servers
3
4-
14
 The Internet network layer
host, router network layer functions:

transport layer: TCP, UDP

routing protocols IP protocol

• path selection • addressing conventions
• RIP, OSPF, BGP • datagram format
network • packet handling conventions
layer forwarding
table
ICMP protocol
• error reporting
• router “signaling”

link layer

physical layer

4-15
 IPv4 datagram format
IP protocol version 32 bits
number total datagram
header length type of length (bytes)
ver head. length
(bytes) len service for
“type” of data fragment fragmentation/
16-bit identifier flgs
offset reassembly
max number time to upper header
remaining hops live layer checksum
(decremented at
32 bit source IP address
each router)
32 bit destination IP address
upper layer protocol
to deliver payload to options (if any) e.g. timestamp,
record route
how much data taken, specify
overhead? (variable length, list of routers
 20 bytes of TCP typically a TCP to visit.
 20 bytes of IP or UDP segment)
 = 40 bytes + app
layer overhead
4-16
IPv4 addressing: introduction
223.1.1.1

• IP address: 32-bit 223.1.2.1

identifier for host,
router interface 223.1.1.2
223.1.1.4 223.1.2.9

• interface:
connection between 223.1.3.27
223.1.1.3
host/router and physical 223.1.2.2
link
• router’s typically have multiple
interfaces
223.1.3.1 223.1.3.2
• host typically has one or two
interfaces (e.g., wired Ethernet,
wireless 802.11)
• IP addresses 223.1.1.1 = 11011111 00000001 00000001 00000001
associated with each
interface 223 1 1 1

4-17
IPv4 addressing: CIDR

CIDR: Classless InterDomain

Routing
• subnet portion of address of
arbitrary length
• address format: a.b.c.d/x, where x is
host
# bits in subnet
subnet
part
portion of address
part
11001000 00010111 00010000 00000000
200.23.16.0/23

4-18
How many IPv4 addresses are left?

• https://ipv4.potaroo.net
Available /8 address blocks

4-19
NAT: network address translation

motivation: local network uses just

one IP address as far as outside
world is concerned:
 range of addresses not needed from ISP: just one IP
address for all devices
 can change addresses of devices in local network without
notifying outside world
 can change ISP without changing addresses of devices in
local network
 devices inside local net not explicitly addressable, visible
by outside world (a “security” plus)
4-20
NAT: network address translation

rest of local network

Internet (e.g., home network)
10.0.0/24 10.0.0.1

10.0.0.4
10.0.0.2
138.76.29.7

10.0.0.3

all datagrams leaving local datagrams with source or

network have same single destination in this network
source NAT IP address: have 10.0.0/24 address for
138.76.29.7 source, destination (as usual)
but, different source port
numbers 4-21
IPv6 datagram format
priority: identify priority among datagrams in flow
flow Label: identify datagrams in same “flow”.
(concept of “flow” not well defined).
next header: identify upper layer protocol for data
ver pri flow label
payload len next hdr hop limit
source address
(128 bits)
destination address
(128 bits)

data

32 bits
4-22
IPv6 Addresses
• Similar to IPv4 addresses, but 128 bits
• Example:
• 2601:5c2:300:c062:14a7:efa1:78b5:e8a
• CIDR still applies:
• 2601:5c2:300:c062:14a7:efa1:78b5:e8a/64
prefix
• Subnets are commonly 64 bits!
A local network can support 264 devices.
• No need for DHCP (although it still exists)
• Devices can choose their own address
(stateless autoconfiguration). Collisions are
unlikely with 264 addresses.
• Zero groups can be omitted:
• 2601:0000:0000:0000:0000:0000:0000:0008/16
• 2601::8/16
4-23
IPv6: adoption
• Google: 25% of clients access
services via IPv6 (Jan, 2019)
• NIST: 1/3 of all US government
domains are IPv6 capable
• Long (long!) time for deployment,
use
•20 years and counting!
•think of application-level changes in last 20
years: WWW, Facebook, streaming media, Skype,
…
4-24
IPv6: adoption (2019 update)

4-25
IPv6 for IoT?
• Reality: already 10s of billions of
devices
• IPv6 address space (2128) would enable
an IP address per device.
• IoT devices could directly interact with
the Internet, and use familiar protocols.
• However, power and software
complexity issues make it challenging
to run full IPv6 stacks on IoT devices.
• Security challenges?
• Networking challenges? 4-26
https://twitter.com/_inherlane/status/1034430721971118081 27
Socket programming with TCP
client must contact server • when contacted by client, server
• server process must first be TCP creates new socket for server
running process to communicate with that
particular client
• server must have created socket
• allows server to talk with
(door) that welcomes client’s
multiple clients
contact
• source port numbers used to
client contacts server by: distinguish clients (more in
• creating TCP socket, specifying Chap 3)
IP address, port number of
server process application viewpoint:
• when client creates socket: TCP provides reliable, in-order
client TCP establishes
byte-stream transfer (“pipe”)
connection to server TCP between client and server

2-28
Client/server socket interaction: TCP
server (running on hostid) client
create socket,
port=x, for incoming request:
serverSocket = socket()

wait for incoming create socket,

connection request
TCP connect to hostid, port=x
connectionSocket = connection setup clientSocket = socket()
serverSocket.accept()

send request using

read request from clientSocket
connectionSocket

write reply to
connectionSocket read reply from
clientSocket
close
connectionSocket close
clientSocket

2-29
 Example app: Python TCP client

from socket import *

serverName = 'servername'
serverPort = 12000
create TCP socket for
server, remote port 12000 clientSocket = socket(AF_INET, SOCK_STREAM)
clientSocket.connect((serverName, serverPort))
sentence = input('Input lowercase sentence:')
clientSocket.send(sentence)
No need to attach server
name, port
modifiedSentence = clientSocket.recv(1024)
print('From Server:
{}'.format(modifiedSentence))
clientSocket.close()

2-30
 Example app: Python TCP server

from socket import *

serverPort = 12000
create TCP welcoming
socket serverSocket = socket(AF_INET, SOCK_STREAM)
serverSocket.bind(('', serverPort))
server begins listening for
incoming TCP requests
serverSocket.listen(1)
print('The server is ready to receive')
loop forever
while 1:
server waits on accept()
for incoming requests, new
connSocket, addr = serverSocket.accept()
socket created on return
sentence = connSocket.recv(1024)
read bytes from socket
(but not address as in UDP) capitalizedSentence = sentence.upper()
connSocket.send(capitalizedSentence)
close connection to this connSocket.close()
client (but not welcoming
socket)

2-31
HTTP overview
HTTP: hypertext
transfer protocol HT
TP
• Web’s application layer req
ues
protocol PC running HT t
Firefox browser TP
• client/server model res
pon
se
• client: browser that
requests, receives, st
ue
(using HTTP re q
e server
TP ns running
protocol) and HT
res
po
“displays” Web HT TP Apache Web
server
objects
• server: Web server
iphone running
sends (using HTTP Safari browser
protocol) objects in
response to requests
2-32
HTTP overview (continued)

uses TCP: HTTP is “stateless”

• server maintains no
• client initiates TCP connection information about past
(creates socket) to server, port client requests
80
• server accepts TCP connection aside
from client protocols that maintain
“state” are complex!
• HTTP messages (application-  past history (state) must be
layer protocol messages) maintained
exchanged between browser  if server/client crashes, their
views of “state” may be
(HTTP client) and Web server inconsistent, must be
(HTTP server) reconciled
• TCP connection closed
2-33
Method types

HTTP/1.0: HTTP/1.1:
• GET • GET, POST, HEAD
• POST • PUT
• HEAD • uploads file in entity
• asks server to leave body to path
requested object out specified in URL
of response field
• DELETE
• deletes file specified
in the URL field
2-34
 HTTP request message
• two types of HTTP messages: request, response
• HTTP request message:
• ASCII (human-readable format)

carriage return character

line-feed character
request line
(GET, POST, GET /index.html HTTP/1.1\r\n
HEAD commands) Host: www.cs.virginia.edu\r\n
User-Agent: Firefox/3.6.10\r\n
Accept: text/html,application/xhtml+xml\r\n
headerAccept-Language: en-us,en;q=0.5\r\n
linesAccept-Encoding: gzip,deflate\r\n
Accept-Charset: ISO-8859-1,utf-8;q=0.7\r\n
carriage return, Keep-Alive: 115\r\n
line feed at start Connection: keep-alive\r\n
\r\n
of line indicates
end of header lines
2-35
 HTTP response message
status line
(protocol
status code HTTP/1.1 200 OK\r\n
status phrase) 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
header ETag: "17dc6-a5c-bf716880"\r\n
Accept-Ranges: bytes\r\n
lines 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
\r\n
data, e.g., data data data data data ...
requested
HTML file
2-36
HTTP response status codes
 status code appears in 1st line in server-to-
client response message.
 some sample codes:
200 OK
• request succeeded, requested object later in this msg
301 Moved Permanently
• requested object moved, new location specified later in this msg
(Location:)
400 Bad Request
• request msg not understood by server
404 Not Found
• requested document not found on this server
505 HTTP Version Not Supported
2-37
DNS: domain name system
people: many identifiers:
Domain Name System:
• SSN, name, passport #
• distributed database
Internet hosts, routers:
implemented in hierarchy of
• IP address (32/128 bit) many name servers
- used for addressing
• application-layer protocol:
hosts and routers
hosts, name servers
• “name”, e.g.,
communicate to resolve names
www.yahoo.com - used (address/name translation)
by humans • note: core Internet function,
Q: how to map between IP implemented as application-
address and name, and vice layer protocol
versa?

2-38
DNS: services, structure
DNS services why not centralize DNS?
• hostname to IP address • single point of failure
translation • traffic volume
• host aliasing • distant centralized database
• canonical, alias names • maintenance
• mail server aliasing A: doesn’t scale!
• load distribution
• replicated Web
servers: many IP
addresses correspond
to one name

2-39
DNS: a distributed, hierarchical database
Root DNS Servers

… …

com DNS servers org DNS servers edu DNS servers

pbs.org vatech.edu virginia.edu

yahoo.com amazon.com
DNS servers DNS servers DNS servers
DNS servers DNS servers

client wants IP for www.amazon.com; 1st approximation:

• client queries root server to find .com DNS server
• client queries .com DNS server to get amazon.com DNS server
• client queries amazon.com DNS server to get IP address for
www.amazon.com

2-40
DNS name root DNS server
resolution example
2
• host at cs.virginia.edu 3
TLD DNS server
wants IP address for 4
cs.berkeley.edu 5

local DNS server

iterated query: uvaarpa.virginia.edu
 contacted server 7 6
replies with name of 1 8
server to contact
 “I don’t know this authoritative DNS server
ns.cs.berkeley.edu
name, but ask this requesting host
server” cs.virginia.edu

cs.berkeley.edu
(23.253.180.102)
2-41
DNS records
DNS: distributed db storing resource records (RR)
RR format: (name, value, type, ttl)

type=A type=CNAME
 name is hostname  name is alias name for some
 value is IP address “canonical” (the real) name
 www.ibm.com is really
type=NS
• name is domain (e.g., servereast.backup2.ibm.c
foo.com) om
• value is hostname of  value is canonical name
authoritative name server for type=MX
this domain  value is name of mailserver
associated with name

2-42
DNS protocol, messages
• query and reply messages, both with same message format
2 bytes 2 bytes

msg header identification flags

 identification: 16 bit # for # questions # answer RRs
query, reply to query uses
same # # authority RRs # additional RRs
 flags:
questions (variable # of questions)
 query or reply
 recursion desired
 recursion available answers (variable # of RRs)
 reply is authoritative
authority (variable # of RRs)

additional info (variable # of RRs)

2-43
Puzzle: DNS True/False

1. A DNS name (e.g. microsoft.com) may be associated with multiple

IP addresses, but each IP address can only be associated with a
single DNS name.
• False
2. DNS caching reduces the time to resolve an IP address and reduces
DNS traffic on the internet.
• True
3. If all root servers fail, no DNS names can be resolved to IP
addresses.
• False
4. If a record for a DNS name is updated, no clients will receive the old
record after the change.
• False
2-44