4.P2P_CDN_Transport_n
P2P + CDN + Transport Layer Part 1
Computer Networks and Applications
Week 4
COMP 3331/COMP 9331
Reading Guide: Chapter 2, 2.5, 2.6, 2.7 +
Chapter 3, Sections 3.1 – 3.4
2
Application Layer: outline
2.1 principles of network
applications
2.2 Web and HTTP
2.3 electronic mail
• SMTP, POP3, IMAP
2.4 DNS
2.5 P2P applications
2.6 video streaming and
content distribution
networks (CDNs)
2.7 socket programming
with UDP and TCP
Self study
Pure P2P architecture
v no always-on server
v arbitrary end systems
directly communicate
v peers are intermittently
connected and change IP
addresses
examples:
§ file distribution
(BitTorrent)
§ Streaming (KanKan)
§ VoIP (Skype)
3
File distribution: client-server vs P2P
Question: how much time to distribute file (size
F) from one server to N peers?
§ peer upload/download capacity is limited resource
us
uN
dN
server
network (with abundant
bandwidth)
file, size F
us: server upload
capacity
ui: peer i upload
capacity
di: peer i download
capacityu2 d2
u1 d1
di
ui
4
File distribution time: client-server
v server transmission: must
send (upload) N file copies:
§ time to send one copy: F/us
§ time to send N copies: NF/us
increases linearly in N
time to distribute F
to N clients using
client-server approach Dc-s > max{NF/us,,F/dmin}
v client: each client must
download file copy
§ dmin = min client download rate
§ client download time: F/dmin
us
network
di
ui
F
5
File distribution time: P2P
v server transmission: must
upload at least one copy
§ time to send one copy: F/us
time to distribute F
to N clients using
P2P approach
us
network
di
ui
F
DP2P > max{F/us,,F/dmin,,NF/(us + Sui)}
v client: each client must
download file copy
§ client download time: F/dmin
v clients: as aggregate must download NF bits
§ max upload rate (limiting max download rate) is us + Sui
… but so does this, as each peer brings service capacity
increases linearly in N …
6
N
i=1
0
0.5
1
1.5
2
2.5
3
3.5
0 5 10 15 20 25 30 35
N
M
in
im
um
D
is
tr
ib
ut
io
n
T
im
e P2P
Client-Server
Client-server vs. P2P: example
client upload rate = u, F/u = 1 hour, us = 10u
7
P2P file distribution: BitTorrent
tracker: tracks peers
participating in torrent
torrent: group of peers
exchanging chunks of a file
Alice arrives …
v file divided into 256KB chunks
v peers in torrent send/receive file chunks
… obtains list
of peers from tracker
… and begins exchanging
file chunks with peers in torrent
8
.torrent files
v Contains address of trackers for the file
§Where can I find other peers?
v Contain a list of file chunks and their
cryptographic hashes
§ This ensures that chunks are not modified
9
Title Trackers
House of Cards Season 4 Tracker1-url
Walking Dead Season 6 Tracker2-url
Game of Thrones Season 7 Tracker2-url,Tracker3-url
v peer joining torrent:
§ has no chunks, but will
accumulate them over time
from other peers
§ registers with tracker to get
list of peers, connects to
subset of peers
(“neighbours”)
P2P file distribution: BitTorrent
v while downloading, peer uploads chunks to other peers
v peer may change peers with whom it exchanges chunks
v churn: peers may come and go
v once peer has entire file, it may (selfishly) leave or
(altruistically) remain in torrent
10
BitTorrent: requesting, sending file chunks
requesting chunks:
v at any given time, different
peers have different subsets
of file chunks
v periodically, Alice asks each
peer for list of chunks that
they have
v Alice requests missing
chunks from peers, rarest
first
v Q: Why rarest first?
sending chunks: tit-for-tat
v Alice sends chunks to those
four peers currently sending her
chunks at highest rate
§ other peers are choked by Alice
(do not receive chunks from her)
§ re-evaluate top 4 every10 secs
v every 30 secs: randomly select
another peer, starts sending
chunks
§ “optimistically unchoke” this peer
§ newly chosen peer may join top 4
11
BitTorrent: tit-for-tat
(1) Alice “optimistically unchokes” Bob
(2) Alice becomes one of Bob’s top-four providers; Bob reciprocates
(3) Bob becomes one of Alice’s top-four providers
higher upload rate: find better
trading partners, get file faster !
Original Research Paper on BitTorrent linked to WebCMS 12
v Suppose Todd joins a BitTorrent torrent, but he
does not want to upload any data to any other
peers. Todd claims that he can receive a complete
copy of the file that is shared by the swarm. Is
Todd’s claim possible? Why or Why not?
13
Quiz: Free-riding
Getting rid of the server/tracker
v Distribute the tracker information using a
Distributed Hash Table (DHT)
v A DHT is a lookup structure
§Maps keys to an arbitrary value
§Works a lot like, well …. hash table
14
Content available in 6th Edition of the textbook Section 2.6.2
Hash table – review
v (key,value) pairs
v Centralised hash table – all (key,value) pairs on 1 node
v Distributed hash tables – each node has a “section” of (key,value)
pairs
15Figure src: http://en.wikipedia.org/wiki/Hash_table
Distributed Hash Table (DHT)
v DHT: a distributed P2P database
v database has (key, value) pairs; examples:
§ key: TFN number; value: human name
§ key: file name; value: BT tracker peer(s)
v Distribute the (key, value) pairs over the
(millions of peers)
v a peer queries DHT with key
§DHT returns values that match the key
v peers can also insert (key, value) pairs
16
Challenges
v How do we assign (key, value) pairs to
nodes?
v How do we find them again quickly?
v What happens if nodes join/leave?
17
Q: how to assign keys to peers?
v basic idea:
§ convert each key to an integer
§Assign integer to each peer
§ put (key,value) pair in the peer that is closest
to the key
18
DHT identifiers: Consistent Hashing
v assign integer identifier to each peer in range
[0,2n-1] for some n-bit hash function
§ E.g., node ID is hash of its IP address
v require each key to be an integer in same range
v to get integer key, hash original key
§ e.g., key = hash(“House of Cards Season 4”)
§ this is why its is referred to as a distributed “hash”
table
19
Assign keys to peers
v rule: assign key to the peer that has the
closest ID.
v common convention: closest is the
immediate successor of the key.
v e.g., n=4; all peers & key identifiers are in
the range [0-15], peers: 1,3,4,5,8,10,12,14;
§ key = 13, then successor peer = 14
§ key = 15, then successor peer = 1
20
1
3
4
5
8
10
12
15
Circular DHT (1)
v each peer only aware of immediate successor
and predecessor.
v “overlay network”
21
0001
0011
0100
0101
1000
1010
1100
1111
Who’s responsible
for key 1110 ?
I am
1110
1110
1110
1110
1110
1110
Define closest
as closest
successor
Circular DHT (2)
22
Worst case all peers probed, N messages, on average N/2
Mesh overlay (each peer tracks all other N-1 peers) only one message is
sent per query
Circular DHT with shortcuts
v each peer keeps track of IP addresses of predecessor,
successor, short cuts
v reduced from 6 to 2 messages.
v possible to design shortcuts so O(log N) neighbours, O(log N)
messages in query
1
3
4
5
8
10
12
15
Who’s responsible
for key 1110?
23
Peer churn
example: peer 5 abruptly leaves
vpeer 4 & 3 detect peer 5 departure; 4 makes 8 its
immediate successor; asks 8 who its immediate successor
is; makes 8’s immediate successor its second successor. 3
probes 4 for the new successor
1
3
4
5
8
10
12
15
handling peer churn:
vpeers may come and go (churn)
veach peer knows address of its two
successors (1 knows 3 &4 )
veach peer periodically pings its
two successors to check aliveness
vif immediate successor leaves,
choose next successor as new
immediate successor
24
More DHT info
v How do nodes join?
v How does cryptographic hashing work?
v How much state does each node store?
25
Research Papers (on WebCMS):
Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications
Dynamo: Amazon’s Highly Available Key-value Store
26
Application Layer: outline
2.1 principles of network
applications
2.2 Web and HTTP
2.3 electronic mail
• SMTP, POP3, IMAP
2.4 DNS
2.5 P2P applications
2.6 video streaming and
content distribution
networks (CDNs)
2.7 socket programming
with UDP and TCP
Self study
27
Video Streaming and CDNs: context
• Netflix, YouTube: 37%, 16% of downstream residential ISP
traffic
• ~1B YouTube users, ~75M Netflix users
§ challenge: scale – how to reach ~1B
users?
• single mega-video server won’t work (why?)
§ challenge: heterogeneity
§ different users have different capabilities (e.g., wired
versus mobile; bandwidth rich versus bandwidth poor)
§ solution: distributed, application-level
infrastructure
§ video traffic: major consumer of Internet bandwidth
v video: sequence of images
displayed at constant rate
§ e.g., 24 images/sec
v digital image: array of pixels
§ each pixel represented
by bits
v coding: use redundancy
within and between images
to decrease # bits used to
encode image
§ spatial (within image)
§ temporal (from one
image to next)
Multimedia: video
……………………..
spatial coding example: instead
of sending N values of same
color (all purple), send only two
values: color value (purple) and
number of repeated values (N)
……………….…….
frame i
frame i+1
temporal coding example:
instead of sending
complete frame at i+1,
send only differences from
frame i
28
Multimedia: video
§ CBR: (constant bit rate):
video encoding rate fixed
§ VBR: (variable bit rate):
video encoding rate changes
as amount of spatial,
temporal coding changes
§ examples:
• MPEG 1 (CD-ROM) 1.5
Mbps
• MPEG2 (DVD) 3-6 Mbps
• MPEG4 (often used in
Internet, < 1 Mbps)
……………………..
spatial coding example: instead
of sending N values of same
color (all purple), send only two
values: color value (purple) and
number of repeated values (N)
……………….…….
frame i
frame i+1
temporal coding example:
instead of sending
complete frame at i+1,
send only differences from
frame i
29
Streaming stored video:
simple scenario:
video server
(stored video)
client
Internet
30
Streaming multimedia: DASH
v DASH: Dynamic, Adaptive Streaming over HTTP
v server:
§ divides video file into multiple chunks
§ each chunk stored, encoded at different rates
§manifest file: provides URLs for different chunks
v client:
§ periodically measures server-to-client bandwidth
§ consulting manifest, requests one chunk at a time
• chooses maximum coding rate sustainable given current
bandwidth
• can choose different coding rates at different points in
time (depending on available bandwidth at time) 31
Streaming multimedia: DASH
v DASH: Dynamic, Adaptive Streaming over HTTP
v “intelligence” at client: client determines
§ when to request chunk (so that buffer starvation, or overflow does
not occur)
§ what encoding rate to request (higher quality when more bandwidth
available)
§ where to request chunk (can request from URL server that is
“close” to client or has high available bandwidth)
32
DASH implementations
v Android through ExoPlayer
v Samsung, LG, Sony, Philips Smart TVs
v Youtube
v Netflix
v JavaScript Implementaton for HTML5
v ….
33
v Caching and replication as a service (amortise cost of
infrastructure)
v Goal: bring content close to the user
v Large-scale distributed storage infrastructure (usually) administered by
one entity
§ e.g., Akamai has servers in 20,000+ locations
v Combination of (pull) caching and (push) replication
§ Pull: Direct result of clients’ requests
§ Push: Expectation of high access rate
34
Content distribution networks
Single server
CDN
An example
35
Many well-known sites
are hosted by CDNs. A
simple way to check
using dig is shown here.
Content distribution networks
§ challenge: how to stream content (selected
from millions of videos) to hundreds of
thousands of simultaneous users?
§ option 1: single, large “mega-server”
• single point of failure
• point of network congestion
• long path to distant clients
• multiple copies of video sent over outgoing link
….quite simply: this solution doesn’t scale
36
Content distribution networks
v challenge: how to stream content (selected from
millions of videos) to hundreds of thousands of
simultaneous users?
v option 2: store/serve multiple copies of videos at
multiple geographically distributed sites (CDN)
§ enter deep: push CDN servers deep into many access
networks
• close to users
• used by Akamai, thousands of locations
§ bring home: smaller number (10’s) of larger clusters in
POPs near (but not within) access networks
• used by Limelight 37
Content Distribution Networks (CDNs)
§ subscriber requests content from CDN
§ CDN: stores copies of content at CDN nodes
• e.g. Netflix stores copies of MadMen
where’s Madmen?
manifest file
• directed to nearby copy, retrieves content
• may choose different copy if network path congested
38
Content Distribution Networks (CDNs)
Internet host-host communication as a service
OTT challenges: coping with a congested Internet
§ from which CDN node to retrieve content?
§ viewer behavior in presence of congestion?
§ what content to place in which CDN node?
“over the top”
More later time permitting
CDN content access: a closer look
Bob (client) requests video http://netcinema.com/6Y7B23V
§ video stored in CDN at http://KingCDN.com/NetC6y&B23V
netcinema.com
KingCDN.com
1
1. Bob gets URL for video
http://netcinema.com/6Y7B23V
from netcinema.com web page
2
2. resolve http://netcinema.com/6Y7B23V
via Bob’s local DNS
netcinema’s
authoratative DNS
3
3. netcinema’s DNS returns URL
http://KingCDN.com/NetC6y&B23V 4
4&5. Resolve
http://KingCDN.com/NetC6y&B23
via KingCDN’s authoritative DNS,
which returns IP address of KingCDN
server with video
56. request video from
KINGCDN server,
streamed via HTTP
KingCDN
authoritative DNS
Bob’s
local DNS
server
40
Case study: Netflix
1
1. Bob manages
Netflix account
Netflix registration,
accounting servers
Amazon cloud
CDN
server
2
2. Bob browses
Netflix video
3
3. Manifest file
returned for
requested video
4. DASH
streaming
upload copies of
multiple versions of
video to CDN servers
CDN
server
CDN
server
41
Uses Push caching (during offpeak)
Preference to “deep inside” followed by “bring home”
NetFlix servers (snap shot from Jan 2018)
42
Researchers from Queen Mary University of London (QMUL) traced
server names that are sent to a user's computer every time they
play content on Netflix to find the location of the 8492 servers (4152 ISP,
4340 IXP).They have been found to be scattered across 578
locations around the world.
v The role of the CDN provider’s authoritative DNS name
server in a content distribution network, simply
described, is:
a) to provide an alias address for each browser access
to the “origin server” of a CDN website
b) to map the query for each CDN object to the CDN
server closest to the requestor (browser)
c) to provide a mechanism for CDN “origin servers” to
provide paths for clients (browsers)
d) none of the above, CDN networks do not use DNS
43
Quiz: CDN
44
Transport Layer
our goals:
v understand
principles behind
transport layer
services:
§ multiplexing,
demultiplexing
§ reliable data transfer
§ flow control
§ congestion control
v learn about Internet
transport layer protocols:
§ UDP: connectionless
transport
§ TCP: connection-oriented
reliable transport
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
45
Transport layer
v Moving “down” a layer
v Current perspective:
§ Application is the boss….
§ Usually executing within the OS Kernel
§ The network layer is ours to command !!
46
Network layer (context)
v What it does: finds paths through network
§ Routing from one end host to another
v What it doesn’t:
§ Reliable transfer: “best effort delivery”
§ Guarantee paths
§ Arbitrate transfer rates
v For now, think of the network layer as
giving us an “API” with one function:
sendtohost(data, host)
§ Promise: the data will go to that (usually!!)
47
Transport services and protocols
v provide logical communication
between app processes
running on different hosts
v transport protocols run in
end systems
§ send side: breaks app
messages into segments,
passes to network layer
§ rcv side: reassembles
segments into messages,
passes to app layer
§ Exports services to
application that network
layer does not provide
application
transport
network
data link
physical
application
transport
network
data link
physical
48
Why a transport layer?
Transport
Network
Datalink
Physical
Application
Host A Host B
Datalink
Physical
bro
w
ser
telnet
m
m
edia
ftp
bro
w
ser
IP
many application
processes
Drivers
+NIC
Operating
System
49
Why a transport layer?
Host A Host B
Datalink
Physical
bro
w
ser
telnet
m
m
edia
ftp
bro
w
ser
IP
many application
processes
Datalink
Physical
telnet
ftp
IP
H
T
T
P
server
Transport Transport
Communication
between hosts
(128.4.5.6 ßà162.99.7.56)
Communication
between processes
at hosts
50
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
51
Multiplexing/demultiplexing
process
socket
use header info to deliver
received segments to correct
socket
demultiplexing at receiver:handle data from multiple
sockets, add transport header
(later used for demultiplexing)
multiplexing at sender:
transport
application
physical
link
network
P2P1
transport
application
physical
link
network
P4
transport
application
physical
link
network
P3
52
Note: The network is a shared resource. It does not care about your applications, sockets, etc.
Connectionless demultiplexing
v recall: created socket has
host-local port #:
DatagramSocket mySocket1
= new DatagramSocket(12534);
v when host receives UDP
segment:
§ checks destination port #
in segment
§ directs UDP segment to
socket with that port #
v recall: when creating
datagram to send into
UDP socket, must specify
§ destination IP address
§ destination port #
IP datagrams with same
dest. port #, but different
source IP addresses
and/or source port
numbers will be directed
to same socket at dest
53
Connectionless demux: example
DatagramSocket
serverSocket = new
DatagramSocket
(6428);
transport
application
physical
link
network
P3
transport
application
physical
link
network
P1
transport
application
physical
link
network
P4
DatagramSocket
mySocket1 = new
DatagramSocket
(5775);
DatagramSocket
mySocket2 = new
DatagramSocket
(9157);
source port: 9157
dest port: 6428
source port: 6428
dest port: 9157
source port: ?
dest port: ?
source port: ?
dest port: ?
54
Connection-oriented demux
v TCP socket identified
by 4-tuple:
§ source IP address
§ source port number
§ dest IP address
§ dest port number
v demux: receiver uses
all four values to direct
segment to appropriate
socket
v server host may support
many simultaneous TCP
sockets:
§ each socket identified by
its own 4-tuple
v web servers have
different sockets for
each connecting client
§ non-persistent HTTP will
have different socket for
each request
55
Revisiting TCP Sockets
TCP handshake
Client
Socket
Welcoming, port X
Socket
Server ProcessClient Process
Connection, port X
Socket 1pipe
Client Process
Client
Socket
Connection, port X
Socket 2
56
Connection-oriented demux: example
transport
application
physical
link
network
P3
transport
application
physical
link
P4
transport
application
physical
link
network
P2
source IP,port: A,9157
dest IP, port: B,80
source IP,port: B,80
dest IP,port: A,9157
host: IP
address A
host: IP
address C
network
P6P5
P1
source IP,port: C,5775
dest IP,port: B,80
source IP,port: C,9157
dest IP,port: B,80
three segments, all destined to IP address: B,
dest port: 80 are demultiplexed to different sockets
server: IP
address B
57
v Suppose that a Web Server runs in Host C on port
80. Suppose this server uses persistent
connections, and is currently receiving requests
from two different Hosts, A and B.
§ Are all of the requests being sent through the same
socket at host C ?
§ If they are being passed through different sockets, do
both of the sockets have port 80?
58
Quiz: Sockets
May I scan your ports?
v Servers wait at open ports for client requests
v Hackers often perform port scans to determine open,
closed and unreachable ports on candidate victims
v Several ports are well-known
§ <1024 are reserved for well-known apps
§ Other apps also use known ports
• MS SQL server uses port 1434 (udp)
• Sun Network File System (NFS) 2049 (tcp/udp)
v Hackers can exploit known flaws with these known apps
§ Example: Slammer worm exploited buffer overflow flaw in the
SQL server
v How do you scan ports?
§ Nmap, Superscan, etc
http://netsecurity.about.com/cs/hackertools/a/aa121303.htm
http://www.auditmypc.com/
59
https://www.grc.com/shieldsup
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
60
UDP: User Datagram Protocol [RFC 768]
v “no frills,” “bare bones” Internet transport protocol
v “best effort” service, UDP segments may be:
§ lost
§ delivered out-of-order to app
v connectionless:
§ no handshaking between UDP sender, receiver
§ each UDP segment handled independently of
others
61
UDP: segment header
source port # dest port #
32 bits
application
data
(payload)
UDP segment format
length checksum
length, in bytes of
UDP segment,
including header
v no connection
establishment (which can
add delay)
v simple: no connection
state at sender, receiver
v small header size
v no congestion control:
UDP can blast away as
fast as desired
why is there a UDP?
62
2 bytes Optional
Checksum
UDP checksum
sender:
v treat segment contents,
including header fields, as
sequence of 16-bit integers
v checksum: addition (one’s
complement sum) of
segment contents
v sender puts checksum value
into UDP checksum field
receiver:
v Add all the received
together as 16-bit integers
v Add that to the checksum
v If the result is not 1111
1111 1111 1111, there are
errors !
• Goal: detect “errors” (e.g., flipped bits) in transmitted
segment
• Router memory errors
• Driver bugs
• Electromagnetic interference
63
64
UDP: Checksum
Ø Checksum is the16-bit one's complement of the one's
complement sum of a pseudo header of information from the
IP header, the UDP header, and the data, padded with zero
octets at the end (if necessary) to make a multiple of two
octets.
Ø Checksum header, data and pre-pended IP pseudo-header
Ø But the header contains the checksum itself?
Ø What’s IP pseudo-header?
UDP
IP pseduo-header
UDP payload
UDP header
Internet checksum: example
example: add two 16-bit integers
1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0
1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 0 0
1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1
wraparound
sum
checksum
Note: when adding numbers, a carryout from the most
significant bit needs to be added to the result
65
66UDP
4500 003C 1C46 4000 4006 B1E6 AC10 0A63 AC10 0A0C
4500 -> 0100010100000000
003C -> 0000000000111100
1C46 -> 0001110001000110
4000 -> 0100000000000000
4006 -> 0100000000000110
0000 -> 0000000000000000
AC10 -> 1010110000010000
0A63 -> 0000101001100011
AC10 -> 1010110000010000
0A0C -> 0000101000001100
4500 -> 0100010100000000
003c -> 0000000000111100
453C -> 0100010100111100
453C -> 0100010100111100
1c46 -> 0001110001000110
6182 -> 0110000110000010
6182 -> 0110000110000010
4000 -> 0100000000000000
A182 -> 1010000110000010
A182 -> 1010000110000010
4006 -> 0100000000000110
E188 -> 1110000110001000
E188 -> 1110000110001000
AC10 -> 1010110000010000
18D98 -> 11000110110011000
18D98 -> 11000110110011000
8D99 -> 1000110110011001
8D99 -> 1000110110011001
0A63 -> 0000101001100011
97FC -> 1001011111111100
97FC -> 1001011111111100
AC10 -> 1010110000010000
1440C -> 10100010000001100
1440C -> 10100010000001100
440D -> 0100010000001101
440D -> 0100010000001101
0A0C -> 0000101000001100
4E19 -> 0100111000011001
B1E6 ->1011000111100110
67
v Latency sensitive/time critical
v Quick request/response (DNS, DHCP)
v Network management (SNMP)
v Routing updates (RIP)
v Voice/video chat
v Gaming (especially FPS)
v Error correction unnecessary (periodic messages)
UDP Applications
Transport Layer Outline
3.1 transport-layer
services
3.2 multiplexing and
demultiplexing
3.3 connectionless
transport: UDP
3.4 principles of reliable
data transfer
3.5 connection-oriented
transport: TCP
§ segment structure
§ reliable data transfer
§ flow control
§ connection management
3.6 principles of congestion
control
3.7 TCP congestion control
68
Reliable Transport
l In a perfect world, reliable transport is easy
l All the bad things best-effort can do
l a packet is corrupted (bit errors)
l a packet is lost
l a packet is delayed (why?)
l packets are reordered (why?)
l a packet is duplicated (why?)
69
The Two Generals Problem
v Two army divisions (blue) surround enemy (red)
§ Each division led by a general
§ Both must agree when to simultaneously attack
§ If either side attacks alone, defeat
v Generals can only communicate via messengers
§ Messengers may get captured (unreliable channel)
70
The Two Generals Problem
• Two army divisions (blue) surround enemy (red)
– Each division led by a general
– Both must agree when to simultaneously attack
– If either side attacks alone, defeat
• Generals can only communicate via messengers
– Messengers may get captured (unreliable channel)
The Two Generals Problem
v How to coordinate?
§ Send messenger: “Attack at dawn”
§ What if messenger doesn’t make it?
71
The Two Generals Problem
• How to coordinate?
– Send messenger: “Attack at dawn”
– What if messenger doesn’t make it?
The Two Generals Problem
v How to be sure messenger made it?
§ Send acknowledgement: “We received message”
72
The Two Generals Problem
• How to be sure messenger made it?
– Send acknowledgment: “I delivered message”
Principles of reliable data transfer
v important in application, transport, link layers
§ top-10 list of important networking topics!
v characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
73
No bits are corrupted, lost or arrive
out-of-order at the receiver
v characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
Principles of reliable data transfer
v important in application, transport, link layers
§ top-10 list of important networking topics!
74
No bits are corrupted, lost or arrive
out-of-order at the receiver
v characteristics of unreliable channel will determine
complexity of reliable data transfer protocol (rdt)
v important in application, transport, link layers
§ top-10 list of important networking topics!
Principles of reliable data transfer
75
76
We’ll:
Ø Incrementally develop sender, receiver sides of
reliable data transfer protocol (rdt)
Ø Consider only unidirectional data transfer
§ but control info will flow on both directions!
Ø Channel will not re-order packets
Reliable data transfer: getting started
RDT
rdt1.0: reliable transfer over a reliable channel
Ø Underlying channel perfectly reliable
• no bit errors
• no loss of packets
Ø Transport layer does nothing !
v underlying channel may flip bits in packet
§ checksum to detect bit errors
v the question: how to recover from errors:
§ acknowledgements (ACKs): receiver explicitly tells sender
that pkt received OK
§ negative acknowledgements (NAKs): receiver explicitly tells
sender that pkt had errors
§ sender retransmits pkt on receipt of NAK
v new mechanisms in rdt2.0 (beyond rdt1.0):
§ error detection
§ receiver feedback: control msgs (ACK,NAK) rcvr-
>sender
rdt2.0: channel with bit errors
How do humans recover from “errors”
during conversation?
78
v underlying channel may flip bits in packet
§ checksum to detect bit errors
v the question: how to recover from errors:
§ acknowledgements (ACKs): receiver explicitly tells sender
that pkt received OK
§ negative acknowledgements (NAKs): receiver explicitly tells
sender that pkt had errors
§ sender retransmits pkt on receipt of NAK
v new mechanisms in rdt2.0 (beyond rdt1.0):
§ error detection
§ feedback: control msgs (ACK,NAK) from receiver to
sender
§ retransmission
rdt2.0: channel with bit errors
79
Global Picture of rdt2.0
sender receiver
Dotted line: erroneous transmission
Solid line: error-free transmission
80
Transport Part 1: Summary
v principles behind
transport layer services:
§multiplexing,
demultiplexing
§UDP
§ reliable data transfer
v Next Week:
§ rdt (continued)
§ Pipelined Protocols for
reliable data transfer
§ TCP
• TCP Flow Control
• TCP Connection
Management
81