Chương 3. Giao thức tầng giao vận (transport layer)

Trần Quang Hải Bằng Faculty of Information Technology University of Communication and Transport (Unit 2) Office location: Administration building, Block D3, Room 6 Office phone: 38962018 Cell phone: N/A Email: tqhbang@utc2.edu.vn

2 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

3 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Transport Layer Services & Principles

(cid:1) Cung cấp phương tiện truyền

application transport network data link physical

l o

network data link physical

thông logic (logical communication) giữa các applications.

a

network g i data link c physical l

e

n

d

-

(cid:1) PDUs

e

network data link physical

n

d

t

r

network data link physical

a

n

s

p

o

r

t

network data link physical

application transport network data link physical

(cid:2) application: messages. (cid:2) transport: segments (đoạn). (cid:1) Các msg từ tầng application gửi xuống được chia nhỏ thành các đoạn (segments).

(cid:1) Transport protocol được thực thi tại các trạm cuối (end system).

4 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Transport & Network layers

(cid:1) Network layer:

(cid:2) Truyền thông logic giữa các trạm làm việc (host).

Household analogy: 12 kids sending letters to 12 kids (cid:1) processes = kids (cid:1) app messages = letters in

(cid:2) PDUs = packets (gói). (cid:2) IP (Internet Protocol) là

giao thức truyền không tin cậy.

envelopes (cid:1) hosts = houses (cid:1) transport protocol = Ann and

(cid:1) Transport layer:

Bill

(cid:1) network-layer protocol =

(cid:2) Tạo phương thức truyền thông logic giữa các ứng dụng (application/process).

postal service

(cid:2) Nhận các gói tin từ tầng

Network gửi lên.

5 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Transport Protocols

(cid:1) TCP (Transmission Control Protocol)

(cid:2) Connection-oriented (có liên kết). (cid:2) Flow control (điều khiển luồng). (cid:2) Congestion control (điều khiển chống nghẽn mạng). (cid:3) reliable transport protocol (tin cậy)

(cid:1) UDP (User Datagram Protocol)

(cid:2) Connectionless. (cid:2) Không có kiểm soát luồng và kiểm soát nghẽn mạng. (cid:3) unreliable transport protocol.

6 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

7 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Multiplexing/demultiplexing (mux/demux)

sender

receiver

sender

P3

P4

application-layer data

P2

M M

segment header

P1 M

application transport network

segment

M

application transport network

application transport network

(cid:1) Multiplexing (dồn kênh): Các msgs từ các apps (P1, P2) được chia nhỏ và đóng gói thành các segments (thêm header) (cid:3) dồn kênh diễn ra ở sending hosts

(cid:1) Demultiplexing (phân kênh): Các segments nhận được được gửi tới apps tương ứng (P3, P4) (cid:3) phân kênh diễn ra ở receiving hosts

M Ht Hn segment

8 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Dồn và chia kênh thế nào?

32 bits

(cid:1) source port number: ứng

source port # dest port #

dụng gửi dữ liệu.

other header fields

(cid:1) destination port number: ứng dụng nhận dữ liệu.

(cid:1) Port number:

(cid:2) 0-1023: well-known port

application data (message)

TCP/UDP segment format

number (đã được giữ cho các apps phổ biến). (cid:2) 1024 – 65535.

9 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Mux/demux: Ví dụ

source port: x dest. port: 23

server B

host A

Web client host C

source port:23 dest. port: x

Source IP: C Dest IP: B source port: y dest. port: 80

Source IP: C Dest IP: B source port: x dest. port: 80

port use: simple telnet app

Web server B

Source IP: A Dest IP: B source port: x dest. port: 80

Web client host A

port use: Web server

10 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

11 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Connectionless Transport (UDP).

(cid:1) User Datagram Protocol [RFC 768] (cid:1) “no frill”, “bare bones” Internet transport protocol.

(cid:2) chỉ cần những thủ tục cơ bản nhất. (cid:2) thông tin điều khiển cũng chỉ cần cơ bản nhất.

(cid:1) “best effort” service: dữ liệu có thể mất mát, sai sót nhưng

luôn “cố gắng hết sức” để giảm thiểu.

(cid:1) Connectionless:

(cid:2) Không có cơ chế bắt tay (handshaking): thiết lập (cid:3) truyền dữ

liệu (cid:3) kết thúc.

(cid:2) Không nắm giữ trạng thái. (cid:2) Các segments được xử lý độc lập với nhau.

12 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP: Segment structure

32 bits

source port # dest port #

checksum

length

Length, in bytes of UDP segment, including header

Application data (message)

(cid:1) source port. (cid:1) dest port. (cid:1) length. (cid:1) application data. (cid:1) checksum: mã kiểm tra lỗi (phục vụ cho cơ chế nhận biết lỗi – error detection)

UDP segment format

13 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP segment - example

Sender’s MAC address

Receiver’s MAC address

Type of upper layer’s protocol ( 0x0800 = IP )

14 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP segment – example (cnt.)

IP’s Header

15 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP segment – example (cnt.)

UDP’s header

16 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP segment – example (cnt.)

Data of applicaton layer

17 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP checksum

(cid:1) Mã kiểm tra phục vụ cho cơ chế nhận biết lỗi. (cid:1) Sender:

(cid:2) Coi segment như chuỗi các số nguyên 16-bit. (cid:2) checksum = số bù một (1’s complement) của tổng các

số nguyên đó.

(cid:1) Receiver:

(cid:2) Tính toán checksum của segment nhận được. (cid:2) So sánh với checksum chứa trong trường checksum của

segment nhận được (cid:3) nếu sai khác tức là có lỗi.

18 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

UDP checksum: example

(cid:1) Phép cộng các số 16-bit liên tiếp là phép cộng có nhớ. (cid:1) Kiểm tra checksum: Lấy tổng các số 16-bit (có nhớ) cộng với checksum: Kết quả là 1111 1111 1111 1111 thì không có lỗi, nếu khác là có lỗi.

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

wraparound

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

sum checksum (bù 1)

19 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

20 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Principles of Reliable Data Transfer (RDT)

(cid:1) Truyền dữ liệu tin cậy là vấn đề vô cùng quan trọng (top

10 list of important networking topics).

(cid:1) Cần thiết đối với app, transport, datalink layer.

21 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT

deliver_data(): called by rdt to deliver data to upper

rdt_send(): called from above, (e.g., by app.). Passed data to deliver to receiver upper layer

send side

receive side

rdt_rcv(): called when packet arrives on rcv-side of channel

udt_send(): called by rdt, to transfer packet over unreliable channel to receiver

22 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Finite State Machine (FSM)

event causing state transition actions taken on state transition

state 1

state 2

event actions

state: when in this “state” next state uniquely determined by next event

23 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT1.0: reliable data transfer over reliable channel

(cid:1) Tầng dưới:

(cid:2) Không có lỗi. (cid:2) Không mất mát dữ liệu (gói tin). (cid:1) Sender gửi dữ liệu xuống tầng dưới. (cid:1) Receiver nhận dữ liệu gửi từ tầng dưới lên.

rdt_send(data)

rdt_rcv(packet)

Wait for call from below

Wait for call from above

extract (packet,data) deliver_data(data)

packet = make_pkt(data) udt_send(packet)

sender

receiver

24 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.0: channel with bit errors

(cid:1) Tầng dưới có thể có lỗi bit (0  (cid:3) 1)

(cid:2) UDP checksum có khả năng phát hiện lỗi bit.

(cid:1) Khắc phục lỗi (error recover) thế nào?

(cid:2) acknowledgements (ACKs): receiver thông báo đã nhận gói dữ

liệu tốt (không có lỗi).

(cid:2) negative acknowledgements (NAKs): receiver thông báo gói dữ

liệu nhận được có lỗi.

(cid:2) Nếu nhận được NAK, sender cần gửi lại gói tin bị lỗi. (cid:2) human scenarios using ACKs, NAKs? (telephone talking!)

(cid:1) rdt2.0 so với rdt1.0:

(cid:2) error detection (cid:2) receiver feedback: control msgs (ACK,NAK) rcvr->sender.

25 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.0: FSM specification

receiver

rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && isNAK(rcvpkt)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

udt_send(sndpkt)

Wait for call from above

Wait for ACK or NAK

udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

Wait for call from below

sender

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK)

26 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.0: operation with no errors

rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && isNAK(rcvpkt)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

udt_send(sndpkt)

Wait for call from above

Wait for ACK or NAK

udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

Wait for call from below

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK)

27 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.0: error scenario

rdt_send(data) snkpkt = make_pkt(data, checksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && isNAK(rcvpkt)

rdt_rcv(rcvpkt) && corrupt(rcvpkt)

udt_send(sndpkt)

Wait for call from above

Wait for ACK or NAK

udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ

Wait for call from below

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) extract(rcvpkt,data) deliver_data(data) udt_send(ACK)

28 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.0: problems

(cid:1) Nếu ACK, NAK bị lỗi?

(cid:2) Sender không biết kết quả gửi gói tin thế nào. (cid:2) Cũng chẳng thể gửi lại gói tin vì có thể gây hiện tượng lặp gói

tin. (cid:1) Giải pháp:

(cid:2) Sender truyền lại nếu như ACK/NAK bị lỗi. (cid:2) Kiểm soát lặp gói tin (duplicate handling)

(cid:1) Thêm vào gói tin trường số thứ tự (sequence number).

(cid:2) Căn cứ vào số thứ tự gói tin, receiver bỏ qua những gói tin bị lặp. (cid:3) Sender sẽ không gửi gói tin tiếp theo nếu như chưa chắc chắn receiver nhận được gói trước đó (stop and wait protocol).

29 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.1: sender, handles garbled ACK/NAKs

rdt_send(data)

sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) ) udt_send(sndpkt)

Wait for ACK or NAK 0

Wait for call 0 from above

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt)

Λ

Λ

Wait for ACK or NAK 1

Wait for call 1 from above

rdt_send(data)

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) )

udt_send(sndpkt)

sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt)

30 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.1: receiver, handles garbled ACK/NAKs

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

&& has_seq0(rcvpkt)

extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt)

rdt_rcv(rcvpkt) && (corrupt(rcvpkt)

sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) &&

sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) &&

Wait for 0 from below

Wait for 1 from below

not corrupt(rcvpkt) && has_seq1(rcvpkt)

not corrupt(rcvpkt) && has_seq0(rcvpkt)

sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)

sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

&& has_seq1(rcvpkt)

extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt)

31 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT2.2: a NAK-free protocol

rdt_send(data) sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt)

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) ||

Wait for ACK 0

isACK(rcvpkt,1) ) udt_send(sndpkt)

Wait for call 0 from above

sender FSM fragment

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0)

Λ

rdt_rcv(rcvpkt) && (corrupt(rcvpkt) ||

has_seq1(rcvpkt))

udt_send(sndpkt)

receiver FSM fragment

Wait for 0 from below

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

&& has_seq1(rcvpkt)

extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK1, chksum) udt_send(sndpkt)

32 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT3.0: channels with errors and loss

(cid:1) Tầng dưới:

(cid:2) Có thể có lỗi. (cid:2) Có thể gây mất mát gói tin.

(cid:1) Giải pháp:

(cid:2) Sender truyền lại gói tin nếu như chờ ACK một thời

gian nhất định nào đó mà không thấy (cần countdown timer).

(cid:2) Nếu ACK hay gói tin chỉ bị chậm thôi? (cid:1) truyền lại sẽ gây ra hiện tượng lặp gói tin. (cid:1) cần sequence number.

33 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT3.0 sender

rdt_send(data)

sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) Λ

rdt_rcv(rcvpkt) Λ

Wait for ACK0

Wait for call 0from above

timeout udt_send(sndpkt) start_timer

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1)

stop_timer

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) stop_timer

Wait for ACK1

Wait for call 1 from above

timeout udt_send(sndpkt) start_timer

rdt_rcv(rcvpkt) Λ

rdt_send(data)

sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer

rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) ) Λ

34 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT3.0 in action

35 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT3.0 in action (cont)

36 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Hiệu suất của RDT3.0

(cid:1) Giả sử có đường truyền giữa 2 host với các thông số sau:

(cid:2) Bandwidth: 1 Gbps (109 bits per second) (cid:2) Propagation delay: 15 ms (cid:2) Size of packet: 1KB

=

= 8 microsec

T transmit =

L (packet length in bits) R (transmission rate, bps)

8kb/pkt 109 b/sec

.008

L / R

U

=

=

sender

30.008

= 0.00027 microsec

RTT + L / R

(cid:5) U sender: utilization – fraction of time sender busy sending (cid:5) 1KB trong 30msec -> 33KB/sec effective throught put over 1 Gbps link (cid:5) network protocol limits use of physical resources!

37 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

RDT3.0 stop-and-wait operation

sender

receiver

first packet bit transmitted, t = 0 last packet bit transmitted, t = L / R

RTT

first packet bit arrives last packet bit arrives, send ACK

ACK arrives, send next packet, t = RTT + L / R

.008

L / R

U

=

=

sender

30.008

= 0.00027 microsec

RTT + L / R

38 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Tăng hiệu suất đường truyền - Pipelined protocols

Pipelining: Gửi liên tục nhiều packets rồi đợi ACK

(cid:2) Số thứ tự gói tin (sequence numbers) tăng đều và duy nhất (cid:2) Sử dụng bộ nhớ đệm tại Sender và Receiver

(cid:1) Có 2 phương án xử lý khi gặp lỗi:

(cid:2) go-Back-N (cid:2) Selective repeat

39 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Tăng hiệu suất đường truyền - Pipelined protocols

sender

receiver

first packet bit transmitted, t = 0 last bit transmitted, t = L / R

RTT

first packet bit arrives last packet bit arrives, send ACK last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK

ACK arrives, send next packet, t = RTT + L / R

Increase utilization by a factor of 3!

.024

3 * L / R

U

=

= 0.0008

=

sender

30.008

microsecon

RTT + L / R

40 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Go-Back-N

Sender: (cid:1) Sử dụng k-bit ở header để lưu sequence number (cid:1) Cửa sổ trượt cho phép chứa N packets chưa được báo ACK.

(cid:6) Nếu nhận ACK(n): Mọi packet có số hiệu tới n-1 đã gửi thành công (cid:6) Cần giám sát thời gian timeout cho mỗi packet đang gửi đi (in-flight packet) (cid:6) timeout(n): Gửi lại packet n và các packet có seq # lớn hơn trong window

41 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

GBN in action

42 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

GBN: sender extended FSM

rdt_send(data)

if (nextseqnum < base+N) {

sndpkt[nextseqnum] = make_pkt(nextseqnum,data,chksum) udt_send(sndpkt[nextseqnum]) if (base == nextseqnum)

start_timer nextseqnum++ } else

Λ

refuse_data(data)

base=1 nextseqnum=1

Wait

rdt_rcv(rcvpkt)

&& corrupt(rcvpkt)

timeout start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) / udt_send(sndpkt[nextseqnum-1])

rdt_rcv(rcvpkt) &&

notcorrupt(rcvpkt)

base = getacknum(rcvpkt)+1 If (base == nextseqnum)

stop_timer

else start_timer

43 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

GBN: receiver extended FSM

default

udt_send(sndpkt)

rdt_rcv(rcvpkt)

&& notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum)

Λ

Wait

expectedseqnum=1 sndpkt =

make_pkt(expectedseqnum,ACK,chksum)

extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt) expectedseqnum++

ACK-only: always send ACK for correctly-received pkt with highest

in-order seq # (cid:2) may generate duplicate ACKs (cid:2) need only remember expectedseqnum

(cid:1) out-of-order pkt:

(cid:2) discard (don’t buffer) -> no receiver buffering! (cid:2) Re-ACK pkt with highest in-order seq #

44 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Selective Repeat (SR)

(cid:1) Receiver gửi ACK cho từng packet tới đích

(cid:2) Lưu trữ packets vào buffers (nếu cần thiết) để chuyển

lên layer phía trên

(cid:1) Sender gửi lại những packet không nhận được

ACK sau khoảng timeout (cid:2) Cần cơ chế định thời timeout cho từng packet (chưa

được ACK) (cid:1) Sender window

(cid:2) N consecutive seq #’s (cid:2) again limits seq #s of sent, unACKed pkts

45 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Selective repeat: sender, receiver windows

46 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Selective repeat

receiver

sender

data from above : (cid:7) if next available seq # in

window, send pkt

pkt n in [rcvbase, rcvbase+N-1] (cid:6) send ACK(n) (cid:6) out-of-order: buffer (cid:6) in-order: deliver (also deliver

buffered, in-order pkts), advance window to next not-yet-received pkt

timeout(n): (cid:7) resend pkt n, restart timer ACK(n) in

pkt n in [rcvbase-N,rcvbase-1] (cid:6) ACK(n) otherwise: (cid:6) ignore

[sendbase,sendbase+N]: (cid:7) mark pkt n as received (cid:7) if n smallest unACKed pkt, advance window base to next unACKed seq #

47 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Selective repeat in action

48 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Selective repeat: rắc rối khi window size quá lớn

Example: (cid:1) seq #’s: 0, 1, 2, 3 (cid:1) window size=3

(cid:1) receiver sees no difference in

two scenarios!

(cid:1) incorrectly passes duplicate

data as new in (a)

Q: what relationship between seq

# size and window size?

Yes, windows size= (total number /2) 0,1,2,3 => widwowsize=4/2=2

Transport Layer 3-49

49 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

50 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Overview

(cid:1) Transmission Control Protocol [RFCs: 793,1122,

1323, 2018, 2581]

application writes data

application reads data

(cid:1) Point-to-point: 1 sender, 1 receiver. (cid:1) Giao thức tin cậy (reliable). (cid:1) Kiểm soát luồng (flow control). (cid:1) Kiểm soát nghẽn mạng (congestion control). (cid:1) full duplex: Gửi & Nhận trên cùng một liên kết. (cid:1) send/receive buffers

socket door

socket door

TCP send buffer

TCP receive buffer

segment

51 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP segment structure

32 bits

URG: urgent data (generally not used)

source port # dest port #

sequence number

ACK: ACK # valid

counting by bytes of data (not segments!)

acknowledgement number

Header length (by 32-bit word)

FSRPAU

rcvr window size

head len

not used checksum

ptr urgent data

# bytes rcvr willing to accept

Options (variable length)

PSH: push data to app immediately (generally not used)

RST, SYN, FIN: connection estab (setup, teardown commands)

application data (variable length)

Internet checksum (as in UDP)

52 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP sequence number and ACKs

Seq. #’s:

Host B

Host A

(cid:2) byte stream “number”

of first byte in segment’s data

Seq=42, ACK=79, data = ‘C’

User types ‘C’

ACKs:

‘ C ’

(cid:2) seq # of next byte

d a t a =

host ACKs receipt of ‘C’, echoes back ‘C’

A C K = 4 3 ,

S e q = 7 9 ,

expected from other side

(cid:2) cumulative ACK Q: how receiver handles out-

Seq=43, ACK=80

host ACKs receipt of echoed ‘C’

of-order segments (cid:2) A: TCP spec doesn’t

time

say, - up to implementor

simple telnet scenario

53 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP segment – example (cnt.)

Sender’s MAC address

Receiver’s MAC address

Type of network layer’s protocol ( 0x0800 = IP )

54 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP segment – example (cnt.)

IP’s Header

55 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP segment – example (cnt.)

Dst’s port # (80)

ACK number

TCP’s Header

Sequence number

Src’s port # (2467)

Wnd’s size

Flags (00010000)

Header’s length (0xa0 = 40 bytes)

56 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP segment – example (cnt.)

TCP’s Header

Check sum

Pointer urgent data

57 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP segment – example (cnt.)

TCP’s Header

TCP’s Options (20 bytes)

58 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP: Reliable Data Transfer (retransmission)

Host A

Host B

Seq=92, 8 bytes data

A C K = 1 0 0

t u o e m i t

X loss

Seq=92, 8 bytes data

A C K = 1 0 0

time

lost ACK scenario

59 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP flow control

(cid:1) Các apps có thể xử lý dữ liệu chậm, các gói tin nhận về được đưa

vào bộ đệm (receiver buffer).

(cid:1) Flow control: kiểm soát không để cho receiver buffer bị tràn vì

sender gửi nhiều gói tin quá.

(cid:1) Receiver: Thông báo cho sender biết kích thước của RcvWidow

(free buffer): trường rcv window size trong TCP segment headers. (cid:1) Sender: Luôn nắm được kích thước tối đa của gói tin có thể truyền

tiếp.

60 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Connection management

Three way handshaking: (cid:1) Bước 1: client gửi TCP SYN control segment tới server.

(cid:1) TCP: Connection-oriented. (cid:1) Khởi tạo các giá trị: (cid:2) sequence number. (cid:2) buffers, flow control

information.

(cid:1) Client:Connection initiator (khởi tạo liên kết: socket). (cid:1) Server: Chấp nhận kết nối.

(cid:1) Bước 2: server nhận SYN segment rồi trả lời bằng SYNACK segment. (cid:1) Bước 3: client nhận

SYNACK segment và trả lời bằng ACK segment (có thể có dữ liệu đi kèm).

61 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

62 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Connection management: ngắt liên kết

(cid:1) Bước 1: client (phía muốn

client

server

ngắt liên kết) gửi TCP FIN segment.

closing

FIN

A C K

closing

(cid:1) Bước 2: server (phía còn lại) nhận được FIN, gửi ACK, ngắt liên kết, gửi tiếp FIN segment.

F I N

ACK

closed

t i a w d e m i t

(cid:1) Bước 3: client nhận FIN, trả lời bằng ACK. timed wait (chờ một lúc nữa cho tới khi liên kết đóng hẳn). (cid:1) Bước 4: server nhận ACK,

closed

đóng liên kết.

63 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Connection management (cont.)

TCP server lifecycle

TCP client lifecycle

64 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

65 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Congestion control

(cid:1) Nghẽn mạng là điều khó tránh khỏi!!! (cid:1) Khi mạng bị nghẽn, các gói tin có thể bị trễ hay bị mất. (cid:1) Hai hướng tiếp cận:

(cid:2) End-end congestion control: Thông tin về mức độ nghẽn mạng được suy ra từ lượng tin bị mất mát trong quá trình truyền.

(cid:2) Network-assited congestion control: Routers cung cấp các thông

tin phản hồi về tình trạng nghẽn mạng tới end systems.

(cid:1) Bit thông báo nghẽn mạng (cid:3) đừng gửi nữa hoăc xin chờ một lát. (cid:1) Tốc độ tối đa cho phép gửi (maximum rate allowed).

(cid:1) TCP sử dụng phương pháp end-end congestion control.

66 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Causes/costs of congestion: scenario 1

Host A

λ

out

λ

in : original data

(cid:1) 2 senders, 2 receivers

Host B

(cid:1) 01 router, buffers vô

unlimited shared output link buffers

hạn

(cid:1) no retransmission

(cid:1) large delays when

congested (cid:1) maximum achievable throughput

67 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Causes/costs of congestion: scenario 2

(cid:1) one router, buffers có hạn (cid:1) sender gửi lại các packet bị mất

λ

Host A

out

λ in : original data

λ'in : original data, plus retransmitted data

Host B

finite shared output link buffers

68 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Causes/costs of congestion: scenario 2

λ

λ

(cid:1) always: (goodput) = in

λ

λ

out (cid:1) “perfect” retransmission only when loss:

> in

out λ

(cid:1) retransmission of delayed (not lost) packet makes larger (than perfect

in

λ

case) for same

out

“costs” of congestion: (cid:6) more work (retrans) for given “goodput” (cid:6) unneeded retransmissions: link carries multiple copies of pkt

69 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Causes/costs of congestion: scenario 3

λ

λ

Q: what happens as in and increase ?

in

(cid:1) 4 senders (cid:1) multihop paths (cid:1) timeout/retransmit

λ

Host A

out

λ in : original data λ'in : original data, plus retransmitted data

finite shared output link buffers

Host B

70 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Causes/costs of congestion: scenario 3

λ

o u

t

H o s t A

H o s t B

Another “cost” of congestion: (cid:6) Khi thực hiện drop các packet trên đường truyền (cid:3) dung lượng đường truyền đã sử dụng để gửi tin tới điểm bị drop là vô ích.

71 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Congestion Control

(cid:1) end-end control (no network assistance) (cid:1) Sender điều khiển lượng dữ liệu gửi đi theo

quy tắc: LastByteSent-LastByteAcked

Làm thế nào sender đánh giá được tình trạng nghẽn? (cid:1) loss event = timeout or 3

≤≤≤≤ min {CongWin, ReceiverWnd}

duplicate ACKs

(cid:1) Công thức xấp xỉ:

rate =

Bytes/sec

CongWin RTT

(cid:1) TCP sender reduces rate (CongWin) after loss event

Cơ chế đánh giá nghẽn:

(cid:1) Giá trị CongWin luôn biến đổi và được tính toán theo khả năng truyền tải của mạng.

(cid:2) AIMD (cid:2) Slow start (cid:2) conservative after timeout

events

72 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP AIMD (additive-increase, multiplicative-decrease)

multiplicative decrease: cut CongWin in half after loss event

additive increase: increase CongWin by 1 MSS every RTT in the absence of loss events: probing

congestion window

24 Kbytes

16 Kbytes

8 Kbytes

time

Long-lived TCP connection

73 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Slow Start

(cid:1) When connection

(cid:6) When connection begins,

increase rate exponentially fast until first loss event

begins, CongWin = 1 MSS (cid:2) Example: MSS = 500

bytes & RTT = 200 msec

(cid:2) initial rate = 20 kbps (cid:1) Available bandwidth may be >> MSS/RTT (cid:2) desirable to quickly ramp up to respectable rate

74 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Slow Start (more)

(cid:1) When connection begins,

Host A

Host B

one segment

T T R

increase rate exponentially until first loss event: (cid:2) double CongWin every RTT (cid:2) done by incrementing

two segments

CongWin for every ACK received

four segments

(cid:1) Summary: initial rate is slow but ramps up exponentially fast

time

75 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Refinement

Philosophy:

(cid:1) After 3 dup ACKs:

(cid:2) CongWin is cut in half (cid:2) window then grows linearly

(cid:1) But after timeout event:

• 3 dup ACKs indicates network capable of delivering some segments • timeout before 3 dup ACKs is “more alarming”

(cid:2) CongWin instead set to 1

MSS;

(cid:2) window then grows

exponentially

(cid:2) to a threshold, then grows

linearly

76 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Refinement (more)

Q: When should the

exponential increase switch to linear?

A: When CongWin gets to 1/2 of its value before timeout.

Implementation: (cid:1) Variable Threshold (cid:1) At loss event, Threshold is set to 1/2 of CongWin just before loss

event

77 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Summary: TCP Congestion Control

(cid:1) When CongWin is below Threshold, sender in slow-

start phase, window grows exponentially.

(cid:1) When CongWin is above Threshold, sender is in congestion-avoidance phase, window grows linearly.

(cid:1) When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to Threshold.

(cid:1) When timeout occurs, Threshold set to CongWin/2

and CongWin is set to 1 MSS.

78 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP throughput (or transmission rate)

(cid:1) Gía trị throughout (số packet gửi đi / giây) của TCP

tính theo Window size và RTT là bao nhiêu? (cid:2) Không tính giai đoạn slowstart

(cid:1) Gọi W là giá trị window size khi xuất hiện mất gói.

(cid:2) Khi window size = W, throughput = W/RTT (cid:2) Ngay sau khi có nghẽn (lost), window size giảm xuống

= W/2 (cid:3) throughput = W/2RTT.

(cid:1) Throughout trung bình là: 0.75 W/RTT

Throughout TB = 3W/4RTT

79 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

TCP Futures

(cid:1) Hỏi: Giả sử MSS = 1500 byte, RTT = 100µs , Cần gửi đi với tốc độ là 10 Gbps (throughput=109 bps). Vậy giá trị Windowsize phải là bao nhiêu ?

(cid:1) Trả lời: window size W = 83,333 in-flight segments (cid:1) Throughput tính theo loss rate:

⋅22.1 RTT

MSS L

(cid:1) Trong đó L = loss rate

80 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Delay modeling

Notation, assumptions: (cid:1) Assume one link between client and server of rate R

Q: How long does it take to receive an object from a Web server after sending a request?

Ignoring congestion, delay

(cid:1) S: MSS (bits) (cid:1) O: object size (bits) (cid:1) no retransmissions (no loss, no corruption)

is influenced by:

Window size: (cid:1) First assume: fixed

congestion window, W segments

(cid:1) TCP connection establishment (cid:1) data transmission delay (cid:1) slow start

(cid:1) Then dynamic window, modeling slow start

81 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Fixed congestion window (1)

First case: WS/R > RTT + S/R: ACK for first segment in window returns before window’s worth of data sent

delay = 2RTT + O/R

82 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Fixed congestion window (2)

Second case: (cid:1) WS/R < RTT + S/R: wait for ACK after sending window’s worth of data sent

delay = 2RTT + O/R + (K-1)[S/R + RTT - WS/R]

Transport Layer 3-83

83 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Ch3. The Transport Layer

1. Transport Layer Services & Principles.

2. Multiplexing/Demultiplexing.

3. Connectionless Transport (UDP).

4. Principles of Reliable Data Transfer (RDT).

5. Connection-oriented Transport (TCP).

6. Congestion Control.

7. Sử dụng TCP hay UDP

84 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Một số so sánh TCP/UDP

(cid:1) Không liên kết, không lưu

trữ trạng thái.

(cid:1) Có liên kết, lưu trữ trạng thái liên kết (quản lý liên kết).

(cid:1) Điểm-điểm, quảng bá. (cid:1) Độ trễ thấp.

(cid:1) Điểm-điểm (cid:1) Có độ trễ (delay): thiết lập, quản lý liên kết, luồng, nghẽn…

(cid:1) Segment header nhỏ (8

(cid:1) Segment header lớn (20

bytes)

bytes)

(cid:1) Không giới hạn tốc độ

(cid:1) Bị giới hạn tốc độ truyền (congestion control)

truyền.

85 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012

Các app thực tế

Application

App protocol

Transport protocol

Electronic mail

SMTP

TCP

Remote terminal access

Telnet

TCP

Web

HTTP

TCP

File transfer

FTP

TCP

Remote file server

NFS

typically UDP

Streaming multimedia

proprietary

typically UDP

Internet telephony

proprietary

typically UDP

Network management

SNMP

typically UDP

Routing protocol

RIP

typically UDP

Name translation

DNS

typically UDP

86 Chương 3. Giao thức tầng giao vận (transport layer) 06/02- 24/03/2012