Bài giảng Mạng máy tính - Chương 5: Giao thức tầng liên kết dữ liệu (data link) - Trần Quang Diệu

Chương 5.Giao thức tầng liên kiết dữ liệu (data link)Quang Dieu Tran, PhDFaculty of Information TechnologyUniversity of Communication and Transport (Branch in Ho Chi Minh City)Email: dieutq@gmail.comWebsite: sites.google.com/sites/tranlecturesChương 5. Tầng liên kết dữ liệu2Ch5. Giao thức tầng liên kết dữ liệu5.1 - Introduction and services5.2 - Error detection and correction5.3 - Multiple access protocols & LAN5.4 - Link-layer addressing & ARP5.5 - Specific link layer technologies27/11/2020Chương 5. Tầng liên kết dữ liệu3Introduction & services27/11/2020Chương 5. Tầng liên kết dữ liệu4Data LinkData link: Liên kết dữ liệu; tầng 2.PDU: frame.packet  nhiều frameNhiệm vụ của tầng data link là truyền các các packet (datagram) từ nút này tới nút khác.“link”27/11/2020Chương 5. Tầng liên kết dữ liệu5Data Link & frameLink:router-router; host-host; router-hostframe: dữ liệu của tầng data linkapplicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys. linkdata linkprotocol27/11/2020Chương 5. Tầng liên kết dữ liệu6Các dịch vụ của tầng data linkĐóng frame và truy cập đường truyền (framing, link access)đóng gói tin vào các frametruy nhập đường truyền (đường truyền dùng chung cần có quy tắc truy nhập)địa chỉ vật lý (physical addr) được sử dụng.Truyền tin cậy (reliable delivery): rdt.đảm bảo các gói tin của tầng mạng không bị lỗi.tuỳ thuộc chất lượng đường truyền.27/11/2020Chương 5. Tầng liên kết dữ liệu7Các dịch vụ của tầng data link (cont)Flow control (điều khiển lưu lượng!!!)đảm bảo lưu lượng truyền hợp lý, nút nhận không bị quá tảiError detectionlỗi có thể phát sinh do nhiễu, tín hiệu yếunút nhận phát hiện lỗi, bỏ qua hoặc yêu cầu nút gửi gửi lại.Error correctionnút nhận xác định bit bị lỗi và sửa lỗi.Half-duplex and Full-duplexhalf-duplex: các nút không thể truyền nhận đồng thời.full-duplex: các nút có thể truyền nhận đồng thời.27/11/2020Chương 5. Tầng liên kết dữ liệu8ImplementationLink layer được thực thi tại network adapter (NIC – Network Interface Card):NIC = RAM + DSP chips + host bus interface + link interfaceapplicationtransportnetworklinkphysicalnetworklinkphysicalMMMMHtHtHnHtHnHlMHtHnHlframephys. linkdata linkprotocoladapter card27/11/2020Chương 5. Tầng liên kết dữ liệu9Ch5. Giao thức tầng liên kết dữ liệu5.1 - Introduction and services5.2 - Error detection and correction5.3 - Multiple access protocols & LAN5.4 - Link-layer addressing & ARP5.5 - Specific link layer technologies27/11/2020Chương 5. Tầng liên kết dữ liệu10Error detection and correctionD = DataEDC= Error Detection and Correction bitsBits thêm vào với mục đích kiểm soát lỗi.Số lượng bit càng cao thì khả năng kiểm soát lỗi càng tốt.Error detection: không phải lúc nào cũng phát hiện được lỗi!27/11/2020Chương 5. Tầng liên kết dữ liệu11ParityParity: cân bằng!!! (chẵn lẻ).Parity chẵn (even parity)tổng số các bit 1 (bao gồm cả bit parity) là chẵn.vd: parity của 101010101 là 1 (tổng số bit 1 = 5+1).parity bit = (số bit 1 của data là lẻ) ? 1 : 0Parity lẻ (odd parity):tổng số các bit 1 (bao gồm cả bit parity) là lẻ.vd: parity của 101010101 là 0 (tổng số bit 1 = 5).parity bit = (số bit 1 của data là chẵn)? 1:027/11/2020Chương 5. Tầng liên kết dữ liệu12Parity checkingSingle Bit Parity:Detect single bit errorsTwo Dimensional Bit Parity:Detect and correct single bit errors0027/11/2020Parity checking (cont.)Biết rằng đơn vị dữ liệu sau khi thêm bit kiểm tra là 7. Hãy tính ma trận kiểm tra chẵn lẻ hai chiều của chuỗi ký tự “SING”Giải: các ký tự trong chuỗi có mã 83-73-78-71 Chương 5. Tầng liên kết dữ liệu1327/11/20200101000110100110010110011101010001011000001010101Chương 5. Tầng liên kết dữ liệu14Internet ChecksumSender:Coi segment là một dãy các số nguyên 16 bitchecksum: tổng bù 1của các số 16-bit có segmentSender chèn giá trị tổng bù 1 trên vào trường checksum trong UDPReceiver:Tính checksum của segment nhận đượcSo sánh giá trị tính được với giá trị tại trường checksum:NO – Có lỗiYES – Không có lỗi. nhưng vẫn có thể có lỗi? .Goal: Phát hiện “errors” (vd: đảo bit) trong quá trình truyền/nhận các segment (lưu ý: chỉ dùng ở tầng transport)27/11/2020Chương 5. Tầng liên kết dữ liệu15CRC – Cyclic Redundancy CheckData = d bits dữ liệu (D).Sender chọn r+1 bit sinh (G - generator).Chọn r CRC bits (R) sao cho:DR chia hết cho G (modulo 2)DR = D*2r XOR R. (= (D D.2r = nG XOR R Do vậy:Nếu chia D.2r cho G, phần dư sẽ là RR = remainder[ ]D.2rG27/11/2020Chương 5. Tầng liên kết dữ liệu18Ch5. Giao thức tầng liên kết dữ liệu5.1 - Introduction and services5.2 - Error detection and correction5.3 - Multiple access protocols & LAN5.4 - Link-layer addressing & ARP5.5 - Specific link layer technologies27/11/2020Chương 5. Tầng liên kết dữ liệu19Multiple AccessHai loại “links”:point-to-pointPPP (dial-up access: kết nối Internet tại nhà qua modem)point-to-point link giữa Ethernet switch và hostbroadcast (chia sẻ: shared wire or medium)Radio; Bus LAN;802.11 wireless LAN27/11/2020Chương 5. Tầng liên kết dữ liệu20MAP: Multiple Access ProtocolsCác nút mạng dùng chung một đường truyền.Có lúc nhiều nút mạng cùng muốn truyền dữ liệu.xung đột (collision).chỉ có một nút truyền thành công!!!Multiple Access Protocol (MAP):các quy tắc quy định việc sử dụng đường truyền chung giữa các nút mạng.Human MAP examples:Class: đôi khi SV mất trật tự  xung đột (collision).Cocktail party: multiple languages27/11/2020Chương 5. Tầng liên kết dữ liệu21Ideal Mulitple Access ProtocolĐường truyền có tốc độ (rate) = RKhi một nút muốn truyền, tốc độ là R.Khi M nút muốn truyền, tốc độ TB là R/M.Điều khiển truy nhập phân tán:không cần một nút đặc biệt để điều khiển (các nút tự điều khiển).không cần các tín hiệu đồng bộĐơn giản.27/11/2020Chương 5. Tầng liên kết dữ liệu22MAP: taxonomy (phân loại)Channel partitioning (phân mảnh kênh truyền)kênh truyền được chia thành các “miếng” nhỏ (theo thời gian, tần số, code).mỗi “miếng” sẽ được một nút dùng riêng  không xung đột (collision).Random access (truy nhập ngẫu nhiên)nút nào muốn truyền, ngẫu nhiên truy cập kênh truyền  có khả năng xung đột; xử lý xung đột?Taking turns (truy nhập lần lượt)các nút phối hợp chặt chẽ trong việc sử dụng đường truyền  không xung đột. Goal: efficient, fair, simple, decentralized27/11/2020Chương 5. Tầng liên kết dữ liệu23Channel Partitioning MAP: TDMATDMA: time division multiple accessCác nút được lần lượt truy cập đường truyền trong khoảng thời gian xác định (time slot).Không phải nút nào cũng muốn truyền: unused slot (idle slot).Vd: 6 slots, 3 idle do nút 2,5,6 không có nhu cầu.27/11/2020Chương 5. Tầng liên kết dữ liệu24Channel Partitioning MAP: TDMAFDMA: frequency division multiple accessPhổ của kênh truyền được chia thành nhiều dải tần.Mỗi dải tần dành riêng cho một nút.Như vậy, nút không có nhu cầu truyền thì dải tần dành cho nó bị lãng phí (unused, idle).Vd: 2,5,6 idlefrequency bandstime27/11/2020Chương 5. Tầng liên kết dữ liệu25Channel Partitioning MAP: CDMACDMA (Code Division Multiple Access)Mỗi nút được xác định bởi mã duy nhất (code).Tất cả các nút sử dụng chung tần số nhưng lại có mã riêng (CQ - chipping sequence) để mã hoá và giải mã dữ liệu.encoded signal = (data) X (CQ)decoding: tích trong của encoded signal và CQ.Sử dụng chủ yếu trong mạng wireless (cellular, satellite).27/11/2020Chương 5. Tầng liên kết dữ liệu26CDMA example: encode/decode27/11/2020Chương 5. Tầng liên kết dữ liệu27CDMA example: two-sender interferencesender 1sender 227/11/2020Chương 5. Tầng liên kết dữ liệu28Random Access ProtocolsKhi nút muốn truyền:truy nhập đường truyền và truyền với tốc độ Rkhông có chế độ ưu tiên cho nút nào cả.Nếu nhiều nút cùng truyền  xung đột.cần có cơ chế phát hiện xung đột (collision detection).khôi phục khi có xung đột (recovery): chờ một lúc rồi truyền lạiMột số giao thức:slotted ALOHA, ALOHA.CSMA, CSMA/CD.27/11/2020Chương 5. Tầng liên kết dữ liệu29Slotted ALOHAChia thành các khoảng thời gian (time slot) = thời gian cần để truyền một frame.Nút luôn bắt đầu truyền từ thời điểm bắt đầu slot.Nếu xung đột, sẽ truyền lại frame tại thời điểm bắt đầu slot tiếp theo với xác suất p chọn trước.Success (S), Collision (C), Empty (E) slotsVDAt best: channeluse for useful transmissions 37%of time!27/11/2020Chương 5. Tầng liên kết dữ liệu30CSMA (Carrier Sense Multiple Access)Carrier Sense: lắng nghe trước khi truyền.Nếu kênh truyền rỗi thì truyền toàn bộ frame.Nếu kênh truyền bận, tuỳ cơ ứng biến:thử lại ngay lập tức với xác suất p cho tới khi kênh truyền rỗi.thử lại sau một khoảng thời gian ngẫu nhiên.27/11/2020Chương 5. Tầng liên kết dữ liệu31CSMA collisionsspace:khoảng cách giữa các nút.time: thời gian.Xung đột vẫn có thể xảy ra nếu trong khoảng thời gian t1-t0 tín hiệu chưa lan truyền được từ B tới D.Lãng phí!, cần cơ chế phát hiện xung đột.27/11/2020Chương 5. Tầng liên kết dữ liệu32CSMA/CD (Collision Detection)CSMA/CD:nghe trước khi truyền.dò xung đột trong một khoảng thời gian ngắn (đủ lớn).nếu phát hiện xung đột thì dừng truyền để tránh lãng phí.Phát hiện xung đột:wired LAN: đo hiệu điện thế.wireless: ???27/11/2020Chương 5. Tầng liên kết dữ liệu33CSMA/CD: example27/11/2020Chương 5. Tầng liên kết dữ liệu34“Taking Turns” MAPChannel partitioning MAP:hiệu quả khi nhiều nút cùng sử dụngngược lại, gây lãng phí khi chỉ có vài nút cần truyền tin.Random Access MAP:hiệu quả khi ít nút sử dụng: một nút có thể toàn quyền sử dụng đường truyền với tốc độ cao nhất.nhiều nút cùng sử dụng: xung đột.Taking turns:Tìm kiếm giải pháp tốt cho cả hai tình huống.27/11/2020Chương 5. Tầng liên kết dữ liệu35“Taking Turns” MAP: Polling & Token passingPollingCó một nút điều khiển (master) có nhiệm vụ:lần lượt “thông báo” cho các nút khác biết đến lượt truyền và được phép truyền tối đa một số lượng frame nào đó.khi một nút kết thúc truyền, master thông báo cho nút khác.Không xung đột.Vấn đề:mất thời gian thông báo: tốc độ trung bình TTL (Time To Live): thời gian tồn tại của bản ghi tới khi bị xoá.???: Làm thế nào để biết địa chỉ vật lý của B khi biết IP của B?1A-2F-BB-76-09-AD58-23-D7-FA-20-B00C-C4-11-6F-E3-9871-65-F7-2B-08-53 LAN237.196.7.23237.196.7.78237.196.7.14237.196.7.8827/11/2020Chương 5. Tầng liên kết dữ liệu43Trường hợp chưa biết MAC addr của nútNếu A muốn biết MAC addr của B (không có trong ARP table)A đã biết IP của B (ipb).A gửi ARP query packet tới tất cả các nút (broadcast), trong đó có chứa IP của B (ipb) hỏi xem nút nào có địa chỉ IP là ipb.Tất cả các nút đều nhận được và kiểm tra xem ipb có trùng với IP của mình không, nếu trùng thì trả lời (nút B).27/11/2020Chương 5. Tầng liên kết dữ liệu44Trường hợp hai nút ở hai mạng khác nhauA (111.111.111.111) muốn gửi tin tới B (222.222.222.222)A không biết MAC addr của B, nếu gửi ARP pkt hỏi LAN1  không có nút nào trả lời.ARB27/11/2020Chương 5. Tầng liên kết dữ liệu45A tạo IP packet với địa chỉ IP gửi = A, và địa chỉ IP nhận = B A dùng ARP để xác định MAC của R ứng với interface 111.111.111.110A tạo frame với dest. MAC = MAC của R, frame này chứa IP datagram từ A đến B.A’s data link layer sends frame R’s data link layer receives frame R lấy IP datagram khỏi frame, và coi đích đến là BR dùng ARP lấy địa chỉ MAC của BR tạo frame chứa IP datagram A-to-B IP rồi gửi đến BARB27/11/2020