Giáo trình Mạng máy tính - Chương 3: Tầng giao vận (Transport) - Trần Quang Hải Bằng

MẠNG MÁY TÍNH Chương 3: Tầng giao vận (Transport) bangtqh@utc2.edu.vn Nội dung 1. Các dịch vụ và nguyên lý tầngTransport 2. Dồn kênh và phân kênh 3. Vận tải phi kết nối (UDP). 4. Nguyên lý truyền dữ liệu tin cậy (Reliable Data Transfer - RDT). 5. Vận tải hướng kết nối - Connection Oriented(TCP). 6. Chống tắc nghẽn trong TCP bangtqh@utc2.edu.vn 7. Sử dụng TCP hay UDP Chương 3. Giao thức tầng giao vận (transport layer) 2 Transport Layer Services & Principles application transport network data link physical network data link
Cung cấp phương tiện truyền thông logic giữa các pplications.
Giao thức truyền tài chạy trên application network data link physical network data link physical network data link physical physicalnetwork data link physical các trạm đầu cuối – Bên gửi: Chia các messages thành các segmemt đẩy xuống tầng mạng. – Bên nhận: ghép các segment thành các message hoàn chỉnh bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 3 transport network data link physical đẩy lên tầng ứng dụng
Các giao thức truyền tải – TCP/UDP Transport Vs Network layers
Tầng mạng – Truyền thông logic giữa các trạm làm việc (host). – PDUs = packets (gói). Ví dụ tương đồng: 12 đứa trẻ gửi thư cho 12 đứa khác – IP (Internet Protocol) là giao thức truyền không tin cậy.
Tầng vận tải – Tạo phương thức truyền thông logic giữa các ứng dụng (application/process).  processes = đứa trẻ  app messages = thư được đóng gói trong bao thư  hosts = Nhà  transport protocol = Ann và bangtqh@utc2.edu.vn – Nhận các gói tin từ tầng Network gửi lên. Chương 3. Giao thức tầng giao vận (transport layer) 4 Bill  network-layer protocol = Dịch vụ bưu chính Các giao thức tầng truyền tải
giao gói tin tin cậy, có trật tự (TCP) – kiểm soát tắc nghẽn – kiểm soát lưu lượng application transport network data link physical network network data link – thiết lập kết nối
giao gói tin không tin cậy, không có trật tự (UDP) – một sự mở rộng của IP “nỗ lực hết sức”
Những dịch vụ chưa sẵn application transport data link physical network data link physical physical network data link physical network data link physical network data link physical bangtqh@utc2.edu.vn sàng: – đảm bảo độ trễ – đảm bảo băng thông Chương 3. Giao thức tầng giao vận (transport layer) 5 network data link physical network data link physical Nội dung 1. Các dịch vụ và nguyên lý tầngTransport 2. Dồn kênh và phân kênh 3. Vận tải phi kết nối (UDP). 4. Nguyên lý truyền dữ liệu tin cậy (Reliable Data Transfer - RDT). 5. Vận tải hướng kết nối - Connection Oriented(TCP). 6. Chống tắc nghẽn trong TCP bangtqh@utc2.edu.vn 7. Sử dụng TCP hay UDP Chương 3. Giao thức tầng giao vận (transport layer) 6 Multiplexing/demultiplexing Chuyển các phân đoạn nhận được Tách tại receiverthu thập dữ liệu từ nhiều socket, đóng bao dữ liệu với phần mào đầu (được sử dụng sau này để Dồn tại sender: process socket tới đúng các socket tách) transport application network P2P1 transport application P4 transport application P3 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 3-7 physical link physical link network physical link network Dồn và chia kênh thế nào?
Máy nhận gói tin: – mỗi gói tin có địa chỉ IP nguồn, địa chỉ IP đích – mỗi gói tin mang một đoạn dữ source port # dest port # 32 bits liệu tầng truyền tải – mỗi đoạn có địa chỉ và cổng của máy nhận (đích)
Các host dùng địa chỉ IP và số cổng để chuyển hướng đoạn dữ liệu sang socket thích hợpPort number: application data (message) other header fields bangtqh@utc2.edu.vn – 0-1023: Đã được giữ cho các apps phổ biến. – 1024 – 65535: các host sử dụng tự do Chương 3. Giao thức tầng giao vận (transport layer) 8 TCP/UDP segment format Mux/demux: Ví dụ application P3 transport application P4 application P2 P6P5 P3 transport physical link network physical link transport physical link network source IP,port: B,80 dest IP,port: A,9157 host: IP address A host: IP address C network source IP,port: C,5775 server: IP address B bangtqh@utc2.edu.vn Transport Layer 3-9 source IP,port: A,9157 dest IP, port: B,80 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 Nội dung 1. Các dịch vụ và nguyên lý tầngTransport 2. Dồn kênh và phân kênh 3. Vận tải phi kết nối (UDP). 4. Nguyên lý truyền dữ liệu tin cậy (Reliable Data Transfer - RDT). 5. Vận tải hướng kết nối - Connection Oriented(TCP). 6. Chống tắc nghẽn trong TCP bangtqh@utc2.edu.vn 7. Sử dụng TCP hay UDP Chương 3. Giao thức tầng giao vận (transport layer) 10 Connectionless Transport (UDP).
User Datagram Protocol - [RFC 768]
Giao thức truyền tải “không phức tạp”, “giản thiểu” – Chỉ cần những thủ tục cơ bản nhất. – thông tin điều khiển cũng chỉ cần cơ bản nhất.
Dịch vụ thực hiện theo cơ chế “cố gắng tối đa - best effort” : – Dữ liệu (UDP Segment) mất mát, – Giao không đúng thứ tự nhưng luôn “cố gắng” giảm thiểu.
Connectionless: – Không có cơ chế bắt tay (handshaking): thiết lập  truyền bangtqh@utc2.edu.vn dữ liệu  kết thúc. – Không nắm giữ trạng thái. – Các UDP segments được xử lý độc lập với nhau. Chương 3. Giao thức tầng giao vận (transport layer) 11 UDP (tt)
thường được dùng cho các ứng dụng đa phương tiện trực tuyến – khả năng chịu mất gói source port # dest port # 32 bits length checksum – dễ thay đổi tốc độ
những cách dùng UDP khác – DNS – SNMP
truyền tải tin cậy qua UDP: bổ application data (payload) bangtqh@utc2.edu.vn sung tính tin cậy ở tầng ứng dụng – cơ chế kiểm soát lỗi thuộc tầng ứng dụng! Chương 3. Giao thức tầng giao vận (transport layer) 12 UDP segment format UDP: Segment structure source port # dest port # 32 bits length, in bytes of UDP segment, including header
source port.
dest port.
length.
application data.
checksum: mã kiểm tra lỗi application data (payload) length checksum bangtqh@utc2.edu.vn (phục vụ cho cơ chế nhận biết lỗi – error detection) Chương 3. Giao thức tầng giao vận (transport layer) 13 UDP segment format UDP segment - example Receiver’s MAC address Sender’s MAC address Type of upper layer’s protocol ( 0x0800 = IP ) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 14 UDP segment – example (cnt.) IPv4’s Header bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 15 UDP segment – example (cnt.) UDP’s header bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 16 UDP segment – example (cnt.) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 17 Data of applicaton layer UDP Checksum
Mã kiểm tra phục vụ cho cơ chế nhận biết lỗi.
Bên gửi: – Coi segment như chuỗi các số nguyên 16-bit. – Checksum = số bù một (1’s complement) của tổng các số nguyên đó.
Bên nhận: – Tính toán checksum của segment nhận được. bangtqh@utc2.edu.vn – So sánh với checksum chứa trong trường checksum của segment nhận được  nếu sai khác tức là có lỗi. Chương 3. Giao thức tầng giao vận (transport layer) 18 UDP checksum: example
Phép cộng các số 16-bit liên tiếp là phép cộng có nhớ.
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 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 19 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 (ở dạng bù 1) Nội dung 1. Các dịch vụ và nguyên lý tầngTransport 2. Dồn kênh và phân kênh 3. Vận tải phi kết nối (UDP). 4. Nguyên lý truyền dữ liệu tin cậy (Reliable Data Transfer - RDT). 5. Vận tải hướng kết nối - Connection Oriented(TCP). 6. Chống tắc nghẽn trong TCP bangtqh@utc2.edu.vn 7. Sử dụng TCP hay UDP Chương 3. Giao thức tầng giao vận (transport layer) 20 Nguyên lý truyền thông tin cậy (RDT)
Truyền dữ liệu tin cậy là vấn đề vô cùng quan trọng (top 10 list of important networking topics).
Cần thiết đối với app, transport, datalink layer. bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 21 RDT rdt_send(): called from above, (e.g., by app.). Passed data to deliver to receiver upper layer deliver_data(): called by rdt to deliver data to upper send side receive side bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 22 udt_send(): called by rdt, to transfer packet over unreliable channel to receiver rdt_rcv(): called when packet arrives on rcv-side of channel Finite State Machine (FSM) Chúng ta sẽ
Xem xét vấn đề truyền tin cậy (RDT) giữa bên gửi và bên nhận theo cách “phức tạp dần”
Không quan tâm tới hướng truyền dữ liệu – thông tin điều kiển ở cả 2 phía!
Sửu dụng máy trạng thái đơn định – hữu hạn (FSM) để biểu diễn sender và receiver event causing state transition actions taken on state transition bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 23 state 1 state 2 state: when in this “state” next state uniquely determined by next event event actions RDT1.0: RDT over reliable channel
Tầng dưới: – Không có lỗi. – Không mất mát dữ liệu (gói tin).
Sender gửi dữ liệu xuống tầng dưới.
Receiver nhận dữ liệu gửi từ tầng dưới lên. Wait for rdt_send(data) Wait for rdt_rcv(packet) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 24 call from above packet = make_pkt(data) udt_send(packet) extract (packet,data) deliver_data(data) call from below sender receiver rdt2.0: channel with bit errors underlying channel may flip bits in packet  checksum to detect bit errors  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 new mechanisms in rdt2.0 (beyond rdt1.0):  error detection  receiver feedback: control msgs (ACK,NAK) rcvr- How do humans recover from “errors” during conversation? bangtqh@utc2.edu.vn >sender Transport Layer 3-25 RDT2.0: Channel with bit errors
Tầng dưới có thể có lỗi bit (0  1) – UDP checksum có khả năng phát hiện lỗi bit.
Khắc phục lỗi (error recover) thế nào? – acknowledgements (ACKs): receiver thông báo đã nhận gói dữ liệu tốt (không có lỗi). – negative acknowledgements (NAKs): receiver thông báo gói dữ liệu nhận được có lỗi. – Nếu nhận được NAK, sender cần gửi lại gói tin bị lỗi. – Giao thức người với ACKs, NAKs? (nói chuyên qua phone!) How do humans recover from “errors” during conversation? bangtqh@utc2.edu.vn
rdt2.0 so với rdt1.0: – Có phát hiện lỗi – Có báo nhận: control msgs (ACK,NAK) rcvr->sender. Chương 3. Giao thức tầng giao vận (transport layer) 26 RDT2.0: FSM specification snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) receiver rdt_send(data) Wait for call from above rdt_rcv(rcvpkt) && isACK(rcvpkt) udt_send(sndp kt) udt_send(NAK) rdt_rcv(rcvpkt) && corrupt(rcvpkt) Wait for ACK or NAK Wait for call from belowsender Λ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 27 extract(rcvpkt,data) deliver_data(data) udt_send(ACK) rdt_rcv(rcvpkt) && no corrupt(rcvpkt) RDT2.0: Trường hợp không có lỗi snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) rdt_send(data) Wait for call from above rdt_rcv(rcvpkt) && isACK(rcvpkt) udt_send(sndpkt) udt_send(NAK) rdt_rcv(rcvpkt) && corrupt(rcvpkt) Wait for ACK or NAK Wait for call from belowΛ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 28 extract(rcvpkt,data) deliver_data(data) udt_send(ACK) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) RDT2.0: error scenario snkpkt = make_pkt(data, checksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && isNAK(rcvpkt) rdt_send(data) Wait for call from above rdt_rcv(rcvpkt) && isACK(rcvpkt) udt_send(sndpkt) udt_send(NAK) rdt_rcv(rcvpkt) && corrupt(rcvpkt) Wait for ACK or NAK Wait for call from belowΛ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 29 extract(rcvpkt,data) deliver_data(data) udt_send(ACK) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) Vấn đề của RDT2.0
Nếu ACK, NAK bị lỗi? – Sender không biết kết quả gửi gói tin thế nào. – 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.
Giải pháp: – Sender truyền lại nếu như ACK/NAK bị lỗi. – Kiểm soát lặp gói tin (duplicate handling) • Thêm vào gói tin trường số thứ tự (sequence number). – Căn cứ vào số thứ tự gói tin, receiver bỏ qua những gói bangtqh@utc2.edu.vn tin bị lặp.  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). Chương 3. Giao thức tầng giao vận (transport layer) 30 RDT2.1: sender, handles garbled ACK/NAKs sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_send(data) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) Wait for call 0 from above Wait for ACK or NAK 0 udt_send(sndpkt) ) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt) Wait for call 1 from Wait for ACK or Λ Λ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 31 sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) rdt_send(data) udt_send(sndpkt) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isNAK(rcvpkt) ) aboveNAK 1 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) Wait for 0 from below sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq0(rcvpkt) Wait for 1 from below udt_send(sndpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) rdt_rcv(rcvpkt) && not corrupt(rcvpkt) && has_seq1(rcvpkt) rdt_rcv(rcvpkt) && (corrupt(rcvpkt) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) sndpkt = make_pkt(NAK, chksum) udt_send(sndpkt) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 32 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK, chksum) udt_send(sndpkt) RDT2.2: a NAK-free protocol Wait for call 0 from sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) rdt_send(data) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) )Wait for above udt_send(sndpkt) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) ACK0 sender FSM fragment Wait for 0 from below rdt_rcv(rcvpkt) && (corrupt(rcvpkt) || has_seq1(rcvpkt)) udt_send(sndpkt) receiver FSM fragment Λ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 33 rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && has_seq1(rcvpkt) extract(rcvpkt,data) deliver_data(data) sndpkt = make_pkt(ACK1, chksum) udt_send(sndpkt) RDT3.0: channels with errors and loss
Tầng dưới: – Có thể có lỗi. – Có thể gây mất mát gói tin.
Giải pháp: – 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). – Nếu ACK hay gói tin chỉ bị chậm thôi? bangtqh@utc2.edu.vn • truyền lại sẽ gây ra hiện tượng lặp gói tin. • cần sequence number. Chương 3. Giao thức tầng giao vận (transport layer) 34 RDT3.0 sender sndpkt = make_pkt(0, data, checksum) udt_send(sndpkt) start_timer rdt_send(data) Wait rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,1) ) rdt_rcv(rcvpkt) Wait for Λ Λ for ACK0 Wait for call 1 from above rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,0) rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) && isACK(rcvpkt,1) stop_timer stop_timer udt_send(sndpkt) start_timer timeout udt_send(sndpkt) timeout call 0from above Wait for ACK1 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 35 sndpkt = make_pkt(1, data, checksum) udt_send(sndpkt) start_timer rdt_send(data) rdt_rcv(rcvpkt) && ( corrupt(rcvpkt) || isACK(rcvpkt,0) ) start_timer Λ rdt_rcv(rcvpkt) Λ RDT3.0 in action bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 36 RDT3.0 in action (cont) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 37 Hiệu suất của RDT3.0
Giả sử có đường truyền giữa 2 host với các thông số sau: – Bandwidth: 1 Gbps (109 bits per second) – Propagation delay: 15 ms – Size of packet: 1KB transmit = 8kb/pkt 109 b/sec = 8 microsec U sender = .008 30.008 = 0.00027 microsec L / R RTT + L / R = L (packet length in bits) R (transmission rate, bps) =T bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 38 ❍ U sender: utilization – fraction of time sender busy sending ❍ 1KB trong 30msec -> 33KB/sec effective throught put over 1 Gbps link ❍ network protocol limits use of physical resources! RDT3.0 stop-and-wait operation first packet bit transmitted, t = 0 sender receive r last packet bit transmitted, t = L RTT first packet bit arrives ACK arrives, send next packet, t = RTT + L / R / R last packet bit arrives, send ACK bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 39 U sender = .008 30.008 = 0.00027 microsec L / R RTT + L / R = 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  Số thứ tự gói tin (sequence numbers) tăng đều và duy nhất  Sử dụng bộ nhớ đệm tại Sender và Receiver bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 40  Có 2 phương án xử lý khi gặp lỗi:  go-Back-N  Selective repeat Tăng hiệu suất đường truyền - Pipelined protocols first packet bit transmitted, t = 0 sender receiver last 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 last bit of 2nd packet arrives, send ACK last bit of 3rd packet arrives, send ACK Increase utilization bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 41 U sender = .024 30.008 = 0.0008 microsecon 3 * L / R RTT + L / R = by a factor of 3! Go-Back-N Sender:
Sử dụng k-bit ở header để lưu sequence number
Cửa sổ trượt cho phép chứa N packets chưa được báo ACK.  Nếu nhận ACK(n): Mọi packet có số hiệu tới n-1 đã gửi thành công bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 42  Cần giám sát thời gian timeout cho mỗi packet đang gửi đi (in-flight packet)  timeout(n): Gửi lại packet n và các packet có seq # lớn hơn trong window GBN in action bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 43 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 Wait start_timer udt_send(sndpkt[base]) udt_send(sndpkt[base+1]) Š timeout nextseqnum++ } else refuse_data(data) base=1 nextseqnum=1 rdt_rcv(rcvpkt) && corrupt(rcvpkt) Λ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 44 udt_send(sndpkt[nextseqnum-1]) base = getacknum(rcvpkt)+1 If (base == nextseqnum) stop_timer else start_timer rdt_rcv(rcvpkt) && notcorrupt(rcvpkt) GBN: receiver extended FSM Wait udt_send(sndpkt) default rdt_rcv(rcvpkt) && notcurrupt(rcvpkt) && hasseqnum(rcvpkt,expectedseqnum) extract(rcvpkt,data)expectedseqnum=1 Λ ACK-only: always send ACK for correctly-received pkt with highest in-order seq # – may generate duplicate ACKs deliver_data(data) sndpkt = make_pkt(expectedseqnum,ACK,chksum) udt_send(sndpkt) expectedseqnum++ sndpkt = make_pkt(expectedseqnum,ACK,chksum) bangtqh@utc2.edu.vn – need only remember expectedseqnum
out-of-order pkt: – discard (don’t buffer) -> no receiver buffering! – Re-ACK pkt with highest in-order seq # Chương 3. Giao thức tầng giao vận (transport layer) 45 Selective Repeat (SR)
Receiver gửi ACK cho từng packet tới đích – Lưu trữ packets vào buffers (nếu cần thiết) để chuyển lên layer phía trên
Sender gửi lại những packet không nhận được ACK sau khoảng timeout – Cần cơ chế định thời timeout cho từng packet (chưa được ACK)
Sender window bangtqh@utc2.edu.vn – N consecutive seq #’s – again limits seq #s of sent, unACKed pkts Chương 3. Giao thức tầng giao vận (transport layer) 46 Selective repeat: sender, receiver windows bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 47 data from above :
if next available seq # in window, send pkt timeout(n): sender pkt n in [rcvbase, rcvbase+N-1] ❒ send ACK(n) receiver Selective repeat
resend pkt n, restart timer ACK(n) in [sendbase,sendbase+N]:
mark pkt n as received
if n smallest unACKed pkt, advance window base to next unACKed seq # ❒ out-of-order: buffer ❒ in-order: deliver (also deliver buffered, in-order pkts), advance window to next not-yet-received pkt pkt n in [rcvbase-N,rcvbase-1] ❒ ACK(n) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 48 otherwise: ❒ ignore Selective repeat in action bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 49 Selective repeat: rắc rối khi window size quá lớn Example:
seq #’s: 0, 1, 2, 3
window size=3
receiver sees no difference in two scenarios!
incorrectly passes duplicate data as new in (a) Q: what relationship between seq # size and window size? bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 50Transport Layer 3-50 Yes, windows size= (total number /2) 0,1,2,3 => widwowsize=4/2=2 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 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 51 TCP Overview
Transmission Control Protocol [RFCs: 793,1122, 1323, 2018, 2581]
Point-to-point: 1 sender, 1 receiver.
Giao thức tin cậy (reliable).
Kiểm soát luồng (flow control).
Kiểm soát nghẽn mạng (congestion control).
full duplex: Gửi & Nhận trên cùng một liên kết.
send/receive buffers bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 52 socket door TCP send buffer TCP receive buffer socket door segment application writes data application reads data TCP segment structure source port # dest port # 32 bits sequence number acknowledgement number URG: urgent data (generally not used) ACK: ACK # valid counting by bytes of data (not segments!) application rcvr window size ptr urgent datachecksum FSRPAU head len not used Options (variable length) PSH: push data to app immediately (generally not used) RST, SYN, FIN: connection estab # bytes rcvr willing to accept Header length (by 32-bit word) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 53 data (variable length) (setup, teardown commands) Internet checksum (as in UDP) TCP sequence number and ACKs Seq. #’s: – byte stream “number” of first byte in segment’s data ACKs: – seq # of next byte expected from other side Host A Host B User types – cumulative ACK Q: how receiver handles out-of-order segments – A: TCP spec doesn’t say, - up to implementor ‘C’ host ACKs receipt host ACKs receipt of ‘C’, echoes back ‘C’ bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 54 of echoed ‘C’ time simple telnet scenario TCP segment – example (cnt.) Receiver’s MAC address Sender’s MAC address Type of network layer’s protocol ( 0x0800 = IP ) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 55 TCP segment – example (cnt.) IP’s Header bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 56 TCP segment – example (cnt.) TCP’s Header Src’s port # (2467) Dst’s port # (80) Sequence number ACK number Header’s lengthWnd’s bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 57 Flags (00010000)(0xa0 = 40 bytes) size TCP segment – example (cnt.) TCP’s Header Check bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 58 sum Pointer urgent data TCP segment – example (cnt.) TCP’s Header TCP’s Options bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 59 (20 bytes) TCP: Reliable Data Transfer (retransmission) Host A Host B loss ti m eo ut X bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 60 time lost ACK scenario TCP flow control
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).
Flow control: kiểm soát không để cho receiver buffer bị tràn vì sender gửi nhiều gói tin quá.
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.
Sender: Luôn nắm được kích thước tối đa của gói tin có thể truyền tiếp. bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 61 TCP Connection management
TCP: Connection-oriented.
Khởi tạo các giá trị: – sequence number. Three way handshaking:
Bước 1: client gửi – buffers, flow control information.
Client:Connection initiator (khởi tạo liên kết: socket).
Server: Chấp nhận kết nối. TCP SYN control segment tới server.
Bước 2: server nhận SYN segment rồi trả lời bằng SYNACK segment. bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 62
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). bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 63 TCP Connection management: ngắt liên kết
Bước 1: client (phía muốn ngắt liên kết) gửi TCP FIN segment.
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. client server closing
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).
Bước 4: server nhận ACK, đóng liên kết. closing ti m ed w ai t bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 64 closed ti m ed w ai t closed TCP client lifecycle TCP server lifecycle TCP Connection management (cont.) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 65 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 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 66 Congestion control
Nghẽn mạng là điều khó tránh khỏi!!!
Khi mạng bị nghẽn, các gói tin có thể bị trễ hay bị mất.
Hai hướng tiếp cận: – 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. – 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 bangtqh@utc2.edu.vn end systems. • Bit thông báo nghẽn mạng  đừng gửi nữa hoăc xin chờ một lát. • Tốc độ tối đa cho phép gửi (maximum rate allowed).
TCP sử dụng phương pháp end-end congestion control. Chương 3. Giao thức tầng giao vận (transport layer) 67 Causes/costs of congestion: scenario 1
2 senders, 2 receivers
01 router, buffers vô hạn
no retransmission unlimited shared Host A λin : original data Host B λout
large delays output link buffers bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 68 when congested
maximum achievable throughput Causes/costs of congestion: scenario 2
one router, buffers có hạn
sender gửi lại các packet bị mất finite shared output link buffers Host A λin : original data Host B λout λ'in : original data, plus retransmitted data bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 69
always: (goodput)
“perfect” retransmission only when loss:
retransmission of delayed (not lost) packet makes larger (than λ in λ out = λ in λ out > λ in λ Causes/costs of congestion: scenario 2 perfect case) for same out bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 70 “costs” of congestion: ❒ more work (retrans) for given “goodput” ❒ unneeded retransmissions: link carries multiple copies of pkt Causes/costs of congestion: scenario 3
4 senders
multihop paths
timeout/retransmit λ in Q: what happens as and increase ?λ in finite shared output link buffers Host A λin : original data λout λ'in : original data, plus retransmitted data bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 71 Host B Causes/costs of congestion: scenario 3 H o s t A λ o u t H o s t B bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 72 Another “cost” of congestion: ❒ Khi thực hiện drop các packet trên đường truyền  dung lượng đường truyền đã sử dụng để gửi tin tới điểm bị drop là vô ích. TCP Congestion Control
end-end control (no network assistance)
Sender điều khiển lượng dữ liệu gửi đi theo quy tắc: LastByteSent-LastByteAcked ≤ min {CongWin, ReceiverWnd} Làm thế nào sender đánh giá được tình trạng nghẽn?
Công thức xấp xỉ:
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.
loss event = timeout or 3 duplicate ACKs
TCP sender reduces rate (C ngWin) after loss event Cơ chế đánh giá nghẽn: rate = CongWin RTT Bytes/sec bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 73 – AIMD – Slow start – conservative after timeout events congestion window 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 TCP AIMD (additive-increase, multiplicative-decrease) 8 Kbytes 16 Kbytes 24 Kbytes bangtqh@utc2.edu.vn time Chương 3. Giao thức tầng giao vận (transport layer) 74 Long-lived TCP connection TCP Slow Start
When connection begins, CongWin = 1 MSS – Example: MSS = 500 bytes & RTT = 200 msec – initial rate = 20 kbps ❒ When connection begins, increase rate exponentially fast until first loss event
Available bandwidth may be >> MSS/RTT – desirable to quickly ramp up to respectable rate bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 75 TCP Slow Start (more)
When connection begins, increase rate exponentially until first loss event: – double CongWin every RTT Host A Host B – done by incrementing CongWin for every ACK received
Summary: initial rate is slow but ramps up exponentially fast R T T bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 76 time Refinement
After 3 dup ACKs: – CongWin is cut in half – window then grows linearly • 3 dup ACKs indicates network capable of delivering some segments Philosophy:
But after timeout event: – CongWin instead set to 1 MSS; – window then grows exponentially – to a threshold, then grows linearly • timeout before 3 dup ACKs is “more alarming” bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 77 Q: When should the exponential increase switch to linear? A: When CongWin gets to 1/2 of its value before timeout. Refinement (more) Implementation: bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 78
Variable Threshold
At loss event, Threshold is set to 1/2 of CongWin just before loss event
When CongWin is below Threshold, sender in slow-start phase, window grows exponentially.
When CongWin is above Threshold, sender is Summary: TCP Congestion Control in congestion-avoidance phase, window grows linearly.
When a triple duplicate ACK occurs, Threshold set to CongWin/2 and CongWin set to bangtqh@utc2.edu.vn Threshold.
When timeout occurs, Threshold set to CongWin/2 and CongWin is set to 1 MSS. Chương 3. Giao thức tầng giao vận (transport layer) 79 TCP throughput (or transmission rate)
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? – Không tính giai đoạn slowstart
Gọi W là giá trị window size khi xuất hiện mất gói. – Khi window size = W, throughput = W/RTT – Ngay sau khi có nghẽn (lost), window size giảm xuống = W/2  throughput = W/2RTT.
Throughout trung bình là: 0.75 W/RTT Throughout = 3W/4RTT bangtqh@utc2.edu.vn TB Chương 3. Giao thức tầng giao vận (transport layer) 80 TCP Futures
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 ?
Trả lời: window size W = 83,333 in-flight segments
Throughput tính theo loss rate: LRTT MSS⋅22.1 bangtqh@utc2.edu.vn
Trong đó L = loss rate Chương 3. Giao thức tầng giao vận (transport layer) 81 Delay modeling Q: How long does it take to receive an object from a Web server after sending a request? Ignoring congestion, delay is influenced by: Notation, as umptions:
Assume one link between client and
TCP connection establishment
data transmission delay
slow start server of rate R
S: MSS (bits)
O: object size (bits)
no retransmissions (no loss, no corruption) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 82 Window size:
First assume: fixed congestion window, W segments
Then dynamic window, modeling slow start 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 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 83 Fixed congestion window (2) Second case:
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] bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 84Transport Layer 3-84 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 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 85 Một số so sánh TCP/UDP
Có liên kết, lưu trữ trạng thái liên kết (quản lý liên kết).
Điểm-điểm
Có độ trễ (delay): thiết lập, quản lý liên kết, luồng,
Không liên kết, không lưu trữ trạng thái. nghẽnŠ
Segment header lớn (20 bytes)
Bị giới hạn tốc độ truyền (congestion control)
Điểm-điểm, quảng bá.
Độ trễ thấp.
Segment header nhỏ (8 bytes) bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 86
Không giới hạn tốc độ truyền. 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 bangtqh@utc2.edu.vn Network management SNMP typically UDP Routing protocol RIP typically UDP Name translation DNS typically UDP Chương 3. Giao thức tầng giao vận (transport layer) 87 bangtqh@utc2.edu.vn Chương 3. Giao thức tầng giao vận (transport layer) 88