Bài giảng Mạng máy tính - Chương 3: Lớp truyền tải

Chapter 3 LỚP TRUYỀN TẢI

Nguyễn Hồng Sơn

Chương 3-Lớp truyền tải

3-1

TỔNG QUAN

r Giao thức truyền tải UDP

r Các nguyên lý của

dịch vụ lớp truyền tải: m Ghép/tách kênh

(multiplexing/demulti plexing)

m Truyền số liệu tin cậy m Điều khiển luồng (flow

control)

m Kiểm soát nghẽn

(congestion control)

Chương 3-Lớp truyền tải

3-2

NỘI DUNG

r Các dịch vụ lớp truyền

tải

r Ghép/tách kênh (Multiplexing và demultiplexing)

r Giao thức truyền tải không kết nối UDP

r Các nguyên lý truyền số

liệu tin cậy

Chương 3-Lớp truyền tải

3-3

VAI TRO(cid:19) LỚP TRUYÊ(cid:19)N TA(cid:21)I

Hô(cid:27) trợ ca(cid:23)c ứng du(cid:22)ng truyê(cid:19)n thông

Application (HTTP, SMTP, FTP...)

Cung câ(cid:23)p cơ chê(cid:23) truyê(cid:19)n ta(cid:21)i data giữa ca(cid:23)c ứng du(cid:22)ng ma(cid:19) không phu(cid:22) thuô(cid:22)c ma(cid:22)ng

Transport (UDP, TCP...)

Ti(cid:19)m đường va(cid:19) chuyê(cid:21)n tiê(cid:23)p go(cid:23)i tin giữa ca(cid:23)c nu(cid:23)t ma(cid:22)ng

Network (IP, ICMP...)

Truyê(cid:19)n data qua mô(cid:22)t liên kê(cid:23)t giữa hai điê(cid:21)m nô(cid:23)i trực tiê(cid:23)p

Data Link (Ethernet, ADSL...)

Physical

Truyê(cid:19)n va(cid:19) nhâ(cid:22)n ca(cid:23)c ti(cid:23)n hiê(cid:22)u mang thông tin bit trên đường truyê(cid:19)n vâ(cid:22)t ly(cid:23)

Chương 3-Lớp truyền tải

3-4

Giao thức và dịch vụ truyền tải

application transport network data link physical

ề

r Thực hiện giao tiếp logic giữa các quá trình ứng dụng chạy trên các host khác nhau

n t

ả

r Các giao thức truyền tải chạy

ừ

ầ

u c

ố i

ế

ầ

u c

ố i

trên các đầu cuối m Bên truyền: chia data thành các phân đoạn (segment) và chuyển xuống lớp mạng.

m Bên nhận: tái lập các

application transport network data link physical

segment thành data và chuyển cho lớp ứng dụng r Có nhiều giao thức truyền tải m Internet: TCP và UDP

Chương 3-Lớp truyền tải

3-5

Các giao thức lớp truyền tải trên Internet

r Chuyển phát theo thứ

application transport network data link physical

ề

network data link physical

n t

ả

network data link physical

ừ

ầ

tự, tin cậy (TCP) m Kiểm soát nghẽn m Điều khiển luồng m Thiết lập kết nối

u c

ố

ế

network data link physical

ầ

u c

network data link physical

ố i

r Chuyển phát không theo thứ tự, không tin cậy (UDP)

network data link physical

r Các dịch vụ không được

network data link physical

application transport network data link physical

hỗ trợ: m Kiểm soát trễ m Đảm bảo băng thông

Chương 3-Lớp truyền tải

3-6

Ly(cid:23) do co(cid:23) hai chê(cid:23) đô(cid:22) truyê(cid:19)n ta(cid:21)i

r Ca(cid:23)c ứng du(cid:22)ng la(cid:19) đa da(cid:22)ng: co(cid:23) loa(cid:22)i câ(cid:19)n đô(cid:22)

chi(cid:23)nh xa(cid:23)c cao, co(cid:23) loa(cid:22)i câ(cid:19)n nhanh (thời gian thực)

r TCP: cho ca(cid:23)c ứng du(cid:22)ng nha(cid:22)y ca(cid:21)m với lô(cid:27)i (data services) vi(cid:23) du(cid:22) email, truyê(cid:19)n file

r UDP: cho ca(cid:23)c ứng du(cid:22)ng châ(cid:23)p nhâ(cid:22)n lô(cid:27)i nhưng nha(cid:22)y ca(cid:21)m với trê(cid:27) như VoIP, Video streaming

Chương 3-Lớp truyền tải

3-7

NỘI DUNG

r Các dịch vụ lớp truyền tải r Ghép/tách kênh (Multiplexing và

demultiplexing)

r Giao thức truyền tải không kết nối UDP r Các nguyên lý truyền số liệu tin cậy

Chương 3-Lớp truyền tải

3-8

Ghép/tách kênh

Tách tại host thu:

Ghép tại host tryền:

Chuyển các data nhận được đến đúng socket

Tập hợp data từ nhiều socket, đóng gói và gắn header

= socket = process

P4 application P2 P3 P1 P1 application application

transport transport transport

network network network

link link link

host 3

host 2

host 1

Chương 3-Lớp truyền tải

3-9

physical physical physical

Cách tách kênh r host nhận gói IP

32 bits

m Mỗi gói có một địa chỉ IP nguồn và địa chỉ IP đích

source port # dest port #

m Mỗi gói IP chứa một

segment lớp truyền tải

Các field khác

m Mỗi segment có chỉ số port

nguồn và đích

Data của ứng dụng

r host dùng địa chỉ IP và chỉ số port để chuyển segment đến đúng socket

Định dạng của TCP/UDP segment

Chương 3-Lớp truyền tải 3-10

Tách kênh không kết nối

r Khi host nhận UDP

r Tạo socket với các chỉ số

port :

DatagramSocket mySocket1 = new

DatagramSocket(12534);

segment: m Kiểm tra chỉ số port đích m Chuyển UDP segment đến socket ứng với port này

DatagramSocket mySocket2 = new

DatagramSocket(12535);

r Một UDP socket được nhận

dạng bởi hai thành tố: (địa chỉ IP đích, địa chỉ port đích)

Chương 3-Lớp truyền tải 3-11

Tách kênh không kết nối

DatagramSocket serverSocket = new DatagramSocket(6428);

P2 P1P1 P3

SP: 6428 SP: 6428

DP: 9157 DP: 5775

SP: 9157 SP: 5775

Client IP:B

client IP: A

server IP: C

Chương 3-Lớp truyền tải 3-12

DP: 6428 DP: 6428

Tách kênh hướng kết nối

r Server có thể có đồng thời nhiều TCP socket: m Mỗi socket được nhận dạng bởi một bộ gồm bốn yếu tố

r Web server có các

socket khác nhau cho mỗi kết nối với client m HTTP không liên tục sẽ có các socket khác nhau cho mỗi request

r Một TCP socket được nhận dạng bởi bốn yếu tố: m source IP address m source port number m dest IP address m dest port number r Host nhận gói dùng tất cả bốn yếu tố để chuyển segment đến đúng socket

Chương 3-Lớp truyền tải 3-13

Tách kênh hướng kết nối (2)

P1 P2 P6 P1 P4 P5 P3

SP: 5775

DP: 80

S-IP: B D-IP:C

SP: 9157 SP: 9157

DP: 80 DP: 80

Client IP:B

client IP: A

server IP: C

S-IP: A

Chương 3-Lớp truyền tải 3-14

S-IP: B D-IP:C D-IP:C

Tách kênh hướng kết nối Threaded Web Server

P1 P2 P1 P4 P3

SP: 5775

DP: 80

S-IP: B D-IP:C

SP: 9157 SP: 9157

DP: 80 DP: 80

Client IP:B

client IP: A

server IP: C

S-IP: A

Chương 3-Lớp truyền tải 3-15

S-IP: B D-IP:C D-IP:C

NỘI DUNG

r Các dịch vụ lớp truyền tải r Ghép/tách kênh (Multiplexing và

demultiplexing)

r Giao thức truyền tải không kết nối UDP r Các nguyên lý truyền số liệu tin cậy

Chương 3-Lớp truyền tải 3-16

UDP (User Datagram Protocol)

r Là giao thức truyền tải

Internet chỉ chứa tính năng thiết yếu.

Lý do đưa ra UDP? r Giảm trễ: không thiết lập

kết nối

r Được đặc tả trong RFC 768 r Thuộc dịch vụ “best effort” , các UDP segment có thể: m Bị mất m Chuyển phát không đúng thứ

r Đơn giản: không có trạng thái kết nối tại các host r Kích thước header nhỏ r Không phải kiểm soát nghẽn

tự

r Không kết nối (connectionless): m Không có "bắt tay" giữa UDP truyền và UDP nhận m Mỗi UDP segment được kiểm soát một cách độc lập với các segment khác

Chương 3-Lớp truyền tải 3-17

UDP

r Thường được dùng cho các

32 bits

source port # dest port #

checksum

length

Chiều dài của UDP segment, gồm header

ứng dụng streaming multimedia m Chịu thất thoát m rate sensitive r Các ứng dụng khác

Data

dùng UDP có m DNS m SNMP

r Chuyển phát tin cậy qua

Định dạng UDP segment

UDP thường phải bổ sung đặc tính tin cậy vào lớp ứng dụng m Sửa lỗi ứng dụng đặc

biệt

Chương 3-Lớp truyền tải 3-18

UDP checksum

Mục đích: phát hiện lỗi

Host nhận: r Tính checksum cho segment

nhận được

Host truyền: r Nội dung segment là tuần tự các số nguyên 16 bit r checksum: cộng tất cả các số trong phần nội dung và cộng 1 (bù 1) vào kết quả

r Đặt giá trị tổng

r Kiểm tra xem tổng tính được có bằng với tổng nhận được hay không: m Không --> có lỗi m Bằng --> không có lỗi

(checksum) vào trường checksum của UDP

Chương 3-Lớp truyền tải 3-19

Ví dụ tính Checksum r Lưu ý

m Khi cộng, số nhớ từ bit có ý nghĩa lớn nhất được

cộng vào kết quả

r Ví dụ: cộng hai số nguyên 16-bit

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

sum checksum

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

Chương 3-Lớp truyền tải 3-20

NỘI DUNG

r Các dịch vụ lớp truyền tải r Ghép/tách kênh (Multiplexing và

demultiplexing)

r Giao thức truyền tải không kết nối UDP r Các nguyên lý truyền số liệu tin cậy

Chương 3-Lớp truyền tải 3-21

Các nguyên lý truyền số liệu tin cậy

r Quan trọng trong các lớp ứng dụng, truyền tải và liên kết số

liệu

r Một trong 10 chủ đề liên mạng quan trọng nhất

Chương 3-Lớp truyền tải 3-22

Xây dựng dịch vụ Dịch vụ truyền/nhận data

Truyền số liệu tin cậy (2)

deliver_data(): được gọi bởi rdt để chuyển data lên lớp trên

rdt_send(): được gọi từ lớp trên. Số liệu được chuyển qua để chuyển đến máy thu

Host truyền

Host nhận

rdt_rcv(): được gọi khi gói đến

udt_send(): được gọi bởi rdt, để truyền gói qua kênh không tin cậy đến máy thu

Chương 3-Lớp truyền tải 3-23

rdt: reliable data transfer protocol udt: unreliable data transfer protocol

Truyền số liệu tin cậy (3)

r Tìm hiểu phía truyền và nhận của rdt r Chỉ xem xét truyền một hướng

m Thông tin điều khiển sẽ theo hai hướng

r Dùng sơ đồ trạng thái (finite state machine) để

đặc tả máy truyền và nhận

Sự kiện gây ra chuyển trạng thái Các hành động

state 1

state 2

Sự kiện Hành động

Trạng thái: khi đang ở trạng thái này, trạng thái kế tiếp được xác định bởi sự kiện kế tiếp

Chương 3-Lớp truyền tải 3-24

Rdt1.0: truyền tin cậy qua một kênh tin cậy

r Kênh truyền bên dưới hoàn toàn tin cậy

m Không có lỗi m Không mất gói

r Sơ đồ trạng thái tách biệt cho truyền và nhận:

m Máy truyền gửi data xuống kênh m Máy thu đọc data từ kênh bên dưới

rdt_send(data) rdt_rcv(packet)

Đợi gọi từ dưới Đợi gọi từ trên

Máy truyền

Máy thu

Chương 3-Lớp truyền tải 3-25

extract (packet,data) deliver_data(data) packet = make_pkt(data) rdt_send(packet)

Rdt2.0: kênh có lỗi

r Kênh bên dưới có xảy ra lỗi truyền bit

m Dùng checksum để phát hiện lỗi bit

r Cách thức sửa lỗi :

m acknowledgements (ACKs):máy thu thông báo cho máy

truyền rằng đã nhận tốt

m negative acknowledgements (NAKs):máy thu thông báo gói

đã bị lỗi

m Máy truyền gửi lại gói khi nhận NAK

r Các cơ chế mới trong rdt2.0 :

m Phát hiện lỗi m Phản hồi của máy thu, dùng ACK, NAK

Chương 3-Lớp truyền tải 3-26

rdt2.0: đặc tả sơ đồ trạng thái

Máy thu

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

rdt_rcv(rcvpkt) && isNAK(rcvpkt)

rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(sndpkt) Đợi gọi từ trên Đợi ACK hay NAK

udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Máy truyền

Đợi gọi từ dưới

Chương 3-Lớp truyền tải 3-27

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

rdt2.0: hoạt động không lỗi

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

rdt_rcv(rcvpkt) && isNAK(rcvpkt)

Đợi gọi từ trên Đợi ACK hay NAK rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(sndpkt)

udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ Đợi gọi từ dưới

Chương 3-Lớp truyền tải 3-28

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

rdt2.0: Hoạt động có lỗi

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

rdt_rcv(rcvpkt) && isNAK(rcvpkt)

Đợi gọi từ trên Đợi ACK hay NAK rdt_rcv(rcvpkt) && corrupt(rcvpkt) udt_send(sndpkt)

udt_send(NAK)

rdt_rcv(rcvpkt) && isACK(rcvpkt)

Λ Đợi gọi từ dưới

Chương 3-Lớp truyền tải 3-29

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

rdt2.0: tình huống đặc biệt

Điều gì xảy ra nếu

ACK/NAK bị mất?

Xử lý trùng: r Máy truyền gửi lại gói nếu chờ ACK/NAK quá lâu

r Máy truyền không biết điều

r Máy truyền thêm số tuần tự

vào mỗi gói

gì xảy ra tại máy thu! r Truyền lại có thể trùng

r Máy thu loại bỏ gói trùng, không chuyển lên trên

Idle RQ (stop and wait)

Máy truyền gửi gói và vào trạng thái đợi báo nhận ACK

Chương 3-Lớp truyền tải 3-30

rdt2.1: máy truyền, kiểm soát mất ACK/NAK

rdt_send(data)

Đợi ACK hay NAK 0

Đợi gọi 0 từ trên

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

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

Đợi ACK hay NAK 1

Đợi gọi 1 từ trên

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

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

Chương 3-Lớp truyền tải 3-31

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

rdt2.1: máy thu, kiểm soát mất ACK/NAK

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)

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

Đợi 0 từ dưới

Đợi 1 từ dưới

rdt_rcv(rcvpkt) &&

not corrupt(rcvpkt) && has_seq1(rcvpkt)

not corrupt(rcvpkt) && has_seq0(rcvpkt)

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)

Chương 3-Lớp truyền tải 3-32

rdt2.1: Nhận xét

Máy truyền: r seq # được thêm vào

gói

Máy thu: r Phải kiểm tra xem gói nhận có bị trùng không m Trạng thái chỉ ra số tuần

tự mong đợi

r Hai số tuần tự là đủ r Phải kiểm tra để phòng

ACK/NAK mất r Hai trạng thái

r Máy thu không thể biết tình trạng ACK/NAK tại máy truyền

m Phải nhớ gói hiện hành có số tuần tự là 0 hay 1

Chương 3-Lớp truyền tải 3-33

rdt2.2: NAK-free protocol

r Giống như rdt2.1, chỉ dùng ACK r Thay vì NAK, máy thu gửi ACK cho gói sau cùng nhận

tốt m Máy thu sẽ chỉ rõ số tuần tự gói nhận tốt trong ACK phản hồi r Trùng ACK tại máy truyền dẫn đến hành động tương tự

như NAK: truyền lại gói hiện hành

Chương 3-Lớp truyền tải 3-34

rdt2.2: sơ đồ trạng thái

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

Đợi ACK 0

Đợi gọi 0 từ trên

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

Máy truyền

isACK(rcvpkt,1) ) udt_send(sndpkt)

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

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

Máy thu

Đợi 0 từ dưới

has_seq1(rcvpkt))

udt_send(sndpkt)

rdt_rcv(rcvpkt) && notcorrupt(rcvpkt)

Chương 3-Lớp truyền tải 3-35

&& has_seq1(rcvpkt)

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

rdt3.0: các kênh lỗi và mất gói

Giải pháp: máy truyền đợi ACK một khoảng thời gian hợp lý

Giả sử: kênh bên dưới cũng có thể mất gói (data hay ACK) m checksum, seq. #, ACKs,

r Truyền lại nếu không thấy ACK

truyền lại là hữu ích nhưng không đủ

trong thời gian đợi r Nếu gói hay ACK bị trễ:

m Truyền lại sẽ bị trùng, nhưng có số tuần tự để kiểm soát

m Máy thu phải chỉ ra số tuần tự của gói đang báo nhận ACK

r Yêu cầu bộ định thời đếm lui

Chương 3-Lớp truyền tải 3-36

rdt3.0 máy truyền

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) Λ

Đợi ACK 0

Đợi gọi 0 từ trên

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

Đợi ACK1

Đợi gọi 1 từ trên

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) ) Λ

Chương 3-Lớp truyền tải 3-37

rdt3.0 Hoạt động

Không mất

Chương 3-Lớp truyền tải 3-38

Mất gói

rdt3.0 hoạt động (2)

Chương 3-Lớp truyền tải 3-39

Mất ACK Time out sớm

Hiệu năng của rdt3.0

r Ví dụ: 1 Gbps, Tp=15 ms , Kích thước gói =8000 bit :

microsecon

dtrans

L R

8000 9 10

bits bps

m U sender: utilization – tỉ lệ thời gian máy truyền thực sự làm công

việc truyền

.008

L / R

sender

30.008

= 0.00027 microsec

RTT + L / R

m 1KB pkt mỗi 30 msec -> thông lượng 33kB/sec qua liên kết

1Gbps

m Giao thức mạng đã giới hạn sử dụng tài nguyên vật lý!

Chương 3-Lớp truyền tải 3-40

rdt3.0: hoạt động ARQ không liên tục (Idle ARQ hay stop-and-wait)

sender receiver

Truyền bit đầu của gói, t = 0 Truyền bit sau cùng của gói,

t = L / R

RTT Bit đầu đến Bit sau cùng đến, gửi ACK

.008

L / R

sender

30.008

= 0.00027 microsec

RTT + L / R

Chương 3-Lớp truyền tải 3-41

ACK đến, gửi gói kế, t = RTT + L / R

Các giao thức dùng kỹ thuật ống dẫn

Pipelining: máy truyền cho phép nhiều gói được gửi

liên tiếp không cần có báo nhận ACK m Tăng chỉ số tuần tự m Đệm tại máy truyền và máy nhận

r ARQ liên tục: Selectiverepeat vàGo-back-N

Chương 3-Lớp truyền tải 3-42

Automatic Repeat reQuest

Kỹ thuật Pipelining

Nhằm gia tăng hiệu quả sử dụng đường truyền (utilization)

sender receiver

Truyền bit đầu của gói, t = 0 Truyền bit sau cùng của gói, t = L / R

RTT

Nhận bit đầu của gói Bit sau cùng của gói đến, gửi ACK Bit sau cùng của gói thứ hai đến, gửi ACK Bit sau cùng của gói thứ ba đến, gửi ACK

tăng utilization lên ba lần

.024

3 * L / R

= 0.0008

sender

30.008

microsecon

RTT + L / R

Chương 3-Lớp truyền tải 3-43

ACK đến, gửi gói kế tiếp, t = RTT + L / R

Các giao thức theo ARQ liên tục

Go-back-N r Máy truyền có thể có đến N gói chưa được báo nhận đã gửi qua trong ống

Selective Repeat r Máy truyền có thể có đến N gói chưa được báo nhận đã gửi qua trong ống

r Máy thu gửi ACK cho từng gói nhận tốt

r Máy thu chỉ gửi ACK cho gói mà từ nó về trước đều nhận tốt r Máy truyền có bộ định thời cho các gói chưa được báo nhận m Nếu định thời hết hạn,

r Máy truyền có bộ định thời cho từng gói chưa được báo nhận m Nếu định thời hết hạn, chỉ truyền lại gói tương ứng

truyền lại tất cả các gói đang chờ

Chương 3-Lớp truyền tải 3-44

Go-Back-N

Máy truyền: r Số tuần tự k-bit (seq #) trong header của gói r “cửa sổ”có kích thước N, số gói truyền liên tiếp chưa có báo nhận

Gói có số tuần tự kế tiếp

Gói chờ báo nhận

Đã báo nhận Còn trống chưa dùng

Chưa báo nhận Khe trống

r ACK(n): báo nhận cho tất cả các gói đến n

m Có thể nhận trùng ACK

r Bộ định thời cho các gói đang đợi r timeout(n):truyền lại tất cả các gói từ n trở đi

Chương 3-Lớp truyền tải 3-45

Cửa sồ truyền

Sơ đồ trạng thái của máy truyền Go- Back-N

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

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

Chương 3-Lớp truyền tải 3-46

Đợi

Sơ đồ trạng thái của máy nhận Go-Back-N

default

udt_send(sndpkt)

rdt_rcv(rcvpkt)

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

Chỉ tất cả các trường hợp ngoại trừ trường hợp nhận đúng gói có thứ tự mong muốn

expectedseqnum=1 sndpkt =

make_pkt(expectedseqnum,ACK,chksum)

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

Chương 3-Lớp truyền tải 3-47

Đợi

Hoạt động của Go-Back-N

Chương 3-Lớp truyền tải 3-48

Selective Repeat

r Máy thu báo nhận cho từng gói mà nó nhận tốt

m Đệm gói khi cần (chờ đúng thứ tự để giao cho giao thức

cao hơn)

r Máy truyền chỉ gửi lại gói không nhận được ACK m Bộ định thời cho mỗi gói truyền chưa có báo nhận

r Cửa sổ truyền

m Kích thước N, N chỉ số tuần tự liên tục được gán cho các

gói để truyền đi

m Giới hạn số gói được truyền liên tục

Chương 3-Lớp truyền tải 3-49

Selective repeat: cửa sổ truyền và thu

Gói chờ báo nhận Gói có số tuần tự kế tiếp Đã báo nhận Còn trống chưa dùng

Chưa báo nhận Khe trống

Cửa sồ truyền

(a) Tuần tự truyền với cửa sổ có kích thước N

Bộ đệm trống còn chứa thêm Ngoài trật tự nhưng đã báo nhận

Khe trống

Cần nhưng chưa thấy

Cửa sồ nhận

Chờ gói có tuần tự này

Chương 3-Lớp truyền tải 3-50

(a) Tuần tự nhận với cửa sổ có kích thước N

Selective repeat

Máy thu

Gói n trong khoảng của sổ

thu

Máy truyền data từ trên : r Nếu tuần tự kế sẵn sàng,

truyền gói (cửa sổ còn chỗ)

timeout(n): r Truyền lại gói n, khởi động

lại bộ định thời

r Gửi ACK(n) r Không đúng trật tự: đệm lại r Đúng trật tự: chuyển giao cho lớp trên, cửa sổ hướng đến chỉ số gói kế tiếp

ACK(n) trong khoảng tuần tự

trong cửa sổ:

Gói n chờ nhận đến r Gửi ACK(n)

r Loại chỉ số tuần tự n khỏi

danh sách đợi

r Tăng biên dưới của cửa sổ

lên 1

Chương 3-Lớp truyền tải 3-51

Hoạt động của Selective repeat

Chương 3-Lớp truyền tải 3-52

Ví dụ

r seq #’s: 0, 1, 2, 3 r window size=3 r Quan hệ giữa chỉ số

tuần tự và kích thước cửa sổ

Chương 3-Lớp truyền tải 3-53

HẾT CHƯƠNG 3

Chương 3-Lớp truyền tải 3-54

Bài giảng Mạng máy tính - Chương 3: Lớp truyền tải