End-to-End Protocols (Week 12)
Jaringan Komputer
Fakultas Ilmu Komputer Universitas Indonesia Semester Genap 2003/2004 Versi: 1
Understanding the Stack Recall the TCP/IP Internet Architecture
FTP
HTTP
NV
80
20,21
RTP
4444
UDP
TCP 6
17
IP
NET1
2
NET2
…
NETn
Versi 1
Basic Transport-layer Function Network layer: end-to-end logical communication between hosts Transport layer (rely on network layer): logical communication between application-level comm. end-points Multiple application-level end-points can reside in one host Application-level end-points can be a Web browser/server, a FTP client/server, etc
Transport layer: end-to-end implementation
3
Versi 1
End-to-end Communication
4
Versi 1
Transport-layer Service Model Transport layer: logical communication between application end-point point. multiplexing/demultiplexing
Additional services: reliable data transfer (guaranteed arrival, no error, inorder) flow control (keep sender from overrunning receiver): good for myself congestion control (keep sender from overrunning network): good for everybody
5
Versi 1
Internet Transport-layer Protocols UDP: connectionless multiplexing/demultiplexing error detection
TCP: connection oriented multiplexing/demultiplexing reliable data transfer flow control congestion control
services not available: delay guarantees bandwidth guarantees 6
Versi 1
How multiplexing/demultiplexing works?
using port numbers each IP datagram has source IP address, destination IP address each IP datagram carries a transport-layer segment each segment has source, destination port number port number??
dest. IP address for routing to the host; IP addresses and port numbers for going to appropriate socket in the dest. host.
7
Versi 1
Port Numbers Each port number is a 16-bit number, ranging from 0 to 65535. Port numbers ranging from 0 to 1023 are called wellknown port numbers and are restricted. Port number vs. socket socket (true destination attached to app. end-point) port number (a mechanism to identify socket)
Analogy PABX system vs Internet: Phone no ≈ Internet address Extension no ≈ Port no
8
Versi 1
Simple Demultiplexor (UDP) Unreliable and unordered datagram service Adds multiplexing 0 SrcPort No flow control Checksum Endpoints identified by ports servers have well-known ports see /etc/services on Unix
16
31 DstPort Length
Data
Header format Optional checksum pseudo header + UDP header + data
Pseudo header consists of:
Protocol no (6 for TCP, 17 for UDP) Source IP Destination IP Length field
9
Versi 1
UDP: User Datagram Protocol What is a connection? a group of segments between the same pair of comm. endpoints allow for shared resources, provide services more efficiently
UDP is connectionless: each UDP segment handled independently of others
UDP does multiplexing/demultiplexing simple error detection
UDP does not do reliable data transfer, flow control, congestion control …
10
Versi 1
What is good about UDP? TCP features may not be needed by some applications, such as? Less overhead: no connection establishment (which can add delay) small segment header no congestion control: UDP can blast away as fast as desired
Simple: no connection state at sender, receiver
11
Versi 1
UDP: more Often used for streaming multimedia apps loss tolerant rate sensitive
In general, UDP is also used when TCP features are not important What if you want a subset of features in TCP? implemented at applicationlevel flow control and error recovery in many multimedia apps 12
Versi 1
End-to-End Protocols Underlying best-effort network (IP service): drop messages re-orders messages delivers duplicate copies of a given message limits messages to some finite size delivers messages after an arbitrarily long delay
Common end-to-end services: guarantee message delivery deliver messages in the same order they are sent deliver at most one copy of each message support arbitrarily large messages support synchronization allow the receiver to flow control the sender support multiple application processes on each host
13
Versi 1
TCP Overview Full duplex Flow control: keep sender from overrunning receiver Congestion control: keep sender from overrunning network
Connection-oriented Byte-stream app writes Bytes TCP sends segments app reads Bytes
Application process
Application process
…
…
Write Bytes
TCP Send buffer
Segment
Read Bytes
TCP Receive buffer
Segment
…
Segment
Transmit segments
14
Versi 1
Reliable Data Transfer Our goal: end-to-end solution to achieve reliable data transfer What is reliable data transfer? guaranteed arrival no error in order delivery
Why is it difficult? end-to-end solution has no control of underlying communication channel, which can be error-prone and lossy
Where is it used in computer networks? reliable data link service on top of unreliable physical layer reliable transport service on top of unreliable IP 15
Versi 1
Simple Reliability: send/ACK Sender
Receiver
Sender
Timeout
Fram
ACK
Timeout
Timeout
Time
F ra m e
(a)
Timeout Timeout
F ra m e
Fram e ACK
duplication
Receiver Fram e ACK
Fram e ACK
ACK
(b)
16
ACK
Sender
Timeout
Receiver Fram e
e
(c)
Timeout
Sender
Receiver
(d)
duplication Versi 1
Stop-and-Wait Problem: Overhead ACK: min. 1 RTT, sender stop Example Mak. bit yang dapat dikirimkan: BW x latency. BW = Bandwidth 1.5Mbps link x 45ms latency = 67.5Kb ≈ 8KB 1KB Byte setiap 90ms => 1/16 utilisasi BW (link) Sender
Receiver
Length = latency bandwidth
Capacity = bandwidth X latency
17
Versi 1
Bandwidth & Latency (Review) Kinerja jaringan diukur dalam dua kategori: Bandwidth (throughput): jumlah bits yang dapat ditransfer dalam satu periode waktu • Misalkan: 1 Mbits/detik => 1 Mbps, berarti dapat mengirimkan data 1 juta bit setiap detik; • Bandwidth 1 Mbps, diperlukan waktu 1 mikro-detik untuk mengirimkan 1 bit.
Latency (delay): berapa lama waktu yang diperlukan untuk mengirimkan “message” dari satu ujung (end) ke ujung lainnya. • Ukuran latency adalah satuan waktu. • Misalkan: latency untuk jaringan JKT – SBY: 20 milidetik (oneway). • Pengukuran lain Round-Trip Time (RTT): latency message bolak balik (two way). 18
Versi 1
Example: Latency Network (Review) A
B
R2
Source
R1
Destination
R3 R4
Host A R1 R2
TRANSP1
“Store-and-Forward” at each Router
TRANSP2
PROP1
TRANSP3
PROP2
TRANSP4
R3
Host B
PROP3 PROP4
Minimum end to end latency = ∑ (TRANSPi + PROPi ) i
19
Versi 1
Example: Latency Network (Review) Kemungkinan output link sedang digunakan, maka paket harus antri (queued) di dalam buffer => delay antrian
Host A
TRANSP1 Q2 TRANSP2
R1 PROP1
R2 R3
Host B
TRANSP3 PROP2
TRANSP4 PROP3
PROP4
Actual end to end latency = ∑ (TRANSPi + PROPi + Qi ) i
20
Versi 1
E.g. : Exercise 1.5 (Page 61) - Review Hitung waktu transfer 1000 KB file, asumsi *RTT=100ms, ukuran paket 1KB data, dan diperlukan 2 RTT untuk handshaking awal. a) Badwidth 1.5 Mbps, dan paket data dikirim secara kontinyu (tidak terputus) -
21
Gunakan rumus latency dan perhitungkan semua faktor yang memberikan kontribusi terjadinya delay dari sender ke receiver. Latency = [handshaking] + waktu propagasi [paket 1, one way] + waktu transmisi Latency = [2 * RTT] + [RTT/2] + [BesarData/Bandwidth] Latency = [200ms] + [50 ms] + [1000KB/1.5Mbps] Latency = [200ms] + [50 ms] + [(1000*1024*8)/(1.5 * 106) s] Latency = 0.25 s + 5.46 s = 5.71 second
*Catatan: Di sini RTT = propagation delay Versi 1
E.g. : Exercise 1.5 (Page 61) - Review Hitung waktu transfer 1000 KB file, asumsi *RTT=100ms, ukuran paket 1KB data, dan diperlukan 2 RTT untuk handshaking awal. b) Badwidth 1.5 Mbps, dan paket data tidak dikirim secara kontinyu, tapi setiap satu paket dikirimkan sender harus menunggu 1 RTT, kemudian mengirim paket berikutnya. -
-
22
Dengan cara ini terdapat overhead 1 RTT pada paket kedua, ketiga, dst sampai paket ke-1000; paket pertama tidak perlu menunggu sehingga total delay dari 1000 paket tsb adalah 999 RTT. Latency = [handshaking] + waktu propagasi [paket 1, one way] + waktu transmisi + [total delay overhead menunggu] Latency = 5.71 s + [999 * RTT] Latency = 105.61 second.
*Catatan: Di sini RTT = propagation delay Versi 1
Sliding Window Allow multiple outstanding (un-ACKed) Bytes Upper bound on un-ACKed Bytes, called window
…
Receiver
…
Time
Sender
23
Versi 1
Segment Format 0
10
4
16
31
SrcPort
DstPort SequenceNum Acknowledgment
HdrLen
0
Flags
AdvertisedWindow UrgPtr
Checksum Options (variable) Data
24
Versi 1
Segment Format (cont) Each connection identified with 4-tuple: (SrcPort, SrcIPAddr, DsrPort, DstIPAddr)
Sliding window + flow control acknowledgment, SequenceNum, AdvertisedWinow Data(SequenceNum) Sender
Receiver Acknowledgment + AdvertisedWindow
Flags SYN, FIN, RESET, PUSH, URG, ACK
Checksum pseudo header + TCP header + data 25
Versi 1
Connection Establishment and Termination Three way handshake Active participant (client)
Passive participant (server)
S Y N,
SY
CK, A + N
A CK ,
26
Sequ
enceN
Se
Ackn
Ackno
um =
x
= y, m u c eN que n +1
nt = e m g owled
wledg
ment =y
x
+1
Versi 1
Flow Control – Credit Allocation [STAL00] Stalling W., Data and Computer Communications 6th ed, Prentice-Hall:2000, § 17.1 1 segment = 200 octets Initial W = 7 segments (1400 octets)
27
Versi 1
Sending and Receiving Perspectives
28
Versi 1
TCP Congestion Control Yang lebih berperan mengendalikan kemacetan adl lapisan transport (transport layer). Kemacetan dpt dikendalikan jika data rate dikurangi, dan hal tsb merupakan porsi tugas lapisan transport.
[TAN03] Tanenbaum, A.S., Computer Networks 4th ed. Prentice-Hall: 2003, § 6.5.9.
29
Versi 1
Receiver vs Network Capacity
(a) A fast network feeding a low-capacity receiver 30
(b) A slow network feeding a high capacity network Versi 1
Masalah & Penyelesaiannya Masalah: Apakah TCP congestion control cukup jika hanya mengandalkan ukuran jendela (window size) yg ditentukan oleh End System (ES) tujuan? Lihat slide 31. Bagaimana dgn internal congestion pd slide sebelum ini?
Penyelesaiannya: Selain receiver window, perlu juga congestion window. 31
Versi 1
Effective Window Size Ukuran jendela yg aman menurut ES asal. Min(receiver window size, congestion window size). Jika ES tujuan menyanggupi ukuran jendela 8KB, tetapi ES asal mengetahui kapasitas jaringan hanya 4KB -> ES asal memilih jendela berukuran 4KB. Jika ES tujuan menyanggupi ukuran jendela 8KB, dan ES asal mengetahui kapasitas jaringan 32 KB -> ES asal memilih jendela berukuran 8KB. 32
Versi 1
Slow Start & Threshold Mekanisme yg dilakukan ES asal utk memperkirakan kapasitas jaringan. Slow start (Jacobson 1988): Congestion window bertambah besar secara eksponensial, sampai terjadi timeout atau receiver window tercapai. Penambahan congestion window terjadi jika ES asal menerima ACK dr segmen yg telah dikirimkan sebelum timeout. Bagaimana jika congestion window mencapai receiver window? 33
Versi 1
Algoritma Slow Start & Threshold 1. 2.
3.
4.
34
Congestion window diberi nilai 1 segmen. Dilakukan slow start sampai congestion window mencapai threshold (pertambahan secara ekponesial). Kemudian congestion window bertambah secara linier, hingga mencapai receiver window atau terjadi timeout. Jika terjadi timeout, threshold diperkecil menjadi ½ dr congestion window terakhir. Kembali ke langkah 1.
Versi 1
Slow Start & Threshold Dalam suatu koneksi TCP, ES tujuan dpt mengubah ukuran receiver window. Lihat slide 31. ICMP Source quench akan dilaporkan ke TCP & dianggap sbg timeout. Timer management sangat penting & ditentukan secara statistik.
35
Versi 1
E.g. Slow Start & Threshold
36
Versi 1