程序代写代做代考 case study android database DHCP file system dns Java FTP SQL javascript 4.P2P_CDN_Transport_n

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