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

Nội dung text: Bài giảng Mạng máy tính - Chương 5 (Phần 1): Giao thức tầng liên kiết dữ liệu (Data link)

1. Chương 5. Giao thức tầng liên kiết dữ liệu (data link) Quang Dieu Tran, PhD Faculty of Information Technology University of Communication and Transport (Branch in Ho Chi Minh City) Email: dieutq@gmail.com Website: sites.google.com/sites/tranlectures
2. Ch5. Giao thức tầng liên kết dữ liệu 5.1 - Introduction and services 5.2 - Error detection and correction 5.3 - Multiple access protocols & LAN 5.4 - Link-layer addressing & ARP 5.5 - Specific link layer technologies 18/05/2021 Chương 5. Tầng liên kết dữ liệu 2
3. Introduction & services 18/05/2021 Chương 5. Tầng liên kết dữ liệu 3
4. Data Link ◼ Data link: Liên kết dữ “link” liệu; tầng 2. ◼ PDU: frame. packet → nhiều frame ◼ Nhiệ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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 4
5. Data Link & frame M application Ht M transport Hn Ht M network data link network protocol Hl Hn Ht M link link Hl Hn Ht M physical physical phys. link frame ◼ Link:  router-router; host-host; router-host ◼ frame: dữ liệu của tầng data link 18/05/2021 Chương 5. Tầng liên kết dữ liệu 5
6. Cá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 frame truy 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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 6
7. Cá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ải ◼ Error detection  lỗi có thể phát sinh do nhiễu, tín hiệu yếu  nú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 correction  nút nhận xác định bit bị lỗi và sửa lỗi. ◼ Half-duplex and Full-duplex  half-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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 7
8. Implementation ◼ Link layer được thực thi tại network adapter (NIC – Network Interface Card): ◼ NIC = RAM + DSP chips + host bus interface + link interface M application Ht M transport Hn Ht M network data link network protocol Hl Hn Ht M link link Hl Hn Ht M physical physical phys. link frame adapter card 18/05/2021 Chương 5. Tầng liên kết dữ liệu 8
9. Ch5. Giao thức tầng liên kết dữ liệu 5.1 - Introduction and services 5.2 - Error detection and correction 5.3 - Multiple access protocols & LAN 5.4 - Link-layer addressing & ARP 5.5 - Specific link layer technologies 18/05/2021 Chương 5. Tầng liên kết dữ liệu 9
10. Error detection and correction ◼ D = Data ◼ EDC= Error Detection and Correction bits  Bits 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! 18/05/2021 Chương 5. Tầng liên kết dữ liệu 10
11. Parity ◼ Parity: 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 : 0 ◼ Parity 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:0 18/05/2021 Chương 5. Tầng liên kết dữ liệu 11
12. Parity checking Single Bit Parity: Two Dimensional Bit Parity: Detect single bit errors Detect and correct single bit errors 0 0 18/05/2021 Chương 5. Tầng liên kết dữ liệu 12
13. Parity 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 0 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 0 1 0 1 0 1 18/05/2021 Chương 5. Tầng liên kết dữ liệu 13
14. Internet Checksum 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) Sender: Receiver: ◼ Coi segment là một dãy các ◼ Tính checksum của segment số nguyên 16 bit nhận được ◼ checksum: tổng bù 1của các ◼ So sánh giá trị tính được với số 16-bit có segment giá trị tại trường checksum: ◼ Sender chèn giá trị tổng bù 1  NO – Có lỗi trên vào trường checksum  YES – Không có lỗi. trong UDP nhưng vẫn có thể có lỗi? . 18/05/2021 Chương 5. Tầng liên kết dữ liệu 14
15. CRC – Cyclic Redundancy Check ◼ Data = 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 << r ) XOR R)  receiver: nhận D’R’; biết trước G; chia D’R’ cho G, nếu phép chia có dư → có lỗi.  có thể phát hiện lỗi <= r bit. ◼ CRC được sử dụng rộng rãi trong thực tế. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 15
16. Phép tính modulo 2 ◼ Phép tính modulo N: K/quả modulo N = kết quả bình thường mod N. Vd: 5+9 (mod 4) = 14 mod 4 = 2. ◼ Phép tính modulo 2 với số nhị phân: Thực hiện với từng bit. 1+1 (mod 2) = 0; 1+0 (mod 2) = 1 (không nhớ!!!) 1-0 (mod 2) = 0 – 1 (mod 2) = 1 Với hai số nhị phân b1 và b2 (cộng không nhớ): ◼ b1 + b2 = b2 + b1 = b1 XOR b2 18/05/2021 Chương 5. Tầng liên kết dữ liệu 16
17. CRC Example Biết: D,G. Tìm R? DR chia hết cho G (mod 2) nghĩa là: D.2r XOR R = nG => D.2r = nG XOR R Do vậy:Nếu chia D.2r cho G, phần dư sẽ là R D.2r R = remainder[ ] G 18/05/2021 Chương 5. Tầng liên kết dữ liệu 17
18. Ch5. Giao thức tầng liên kết dữ liệu 5.1 - Introduction and services 5.2 - Error detection and correction 5.3 - Multiple access protocols & LAN 5.4 - Link-layer addressing & ARP 5.5 - Specific link layer technologies 18/05/2021 Chương 5. Tầng liên kết dữ liệu 18
19. Multiple Access Hai loại “links”: ◼ point-to-point  PPP (dial-up access: kết nối Internet tại nhà qua modem)  point-to-point link giữa Ethernet switch và host ◼ broadcast (chia sẻ: shared wire or medium)  Radio; Bus LAN;  802.11 wireless LAN 18/05/2021 Chương 5. Tầng liên kết dữ liệu 19
20. MAP: Multiple Access Protocols ◼ Cá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 languages 18/05/2021 Chương 5. Tầng liên kết dữ liệu 20
21. Ideal Mulitple Access Protocol Đường truyền có tốc độ (rate) = R ◼ Khi 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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 21
22. MAP: 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, decentralized 18/05/2021 Chương 5. Tầng liên kết dữ liệu 22
23. Channel Partitioning MAP: TDMA TDMA: time division multiple access ◼ Cá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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 23
24. Channel Partitioning MAP: TDMA FDMA: frequency division multiple access ◼ Phổ 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 idle frequency bands frequency 18/05/2021 Chương 5. Tầng liên kết dữ liệu 24
25. Channel Partitioning MAP: CDMA CDMA (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 ). 18/05/2021 Chương 5. Tầng liên kết dữ liệu 25
26. CDMA example: encode/decode 18/05/2021 Chương 5. Tầng liên kết dữ liệu 26
27. CDMA example: two-sender interference sender 1 sender 2 18/05/2021 Chương 5. Tầng liên kết dữ liệu 27
28. Random Access Protocols ◼ Khi nút muốn truyền: truy nhập đường truyền và truyền với tốc độ R khô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ại ◼ Một số giao thức: slotted ALOHA, ALOHA. CSMA, CSMA/CD. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 28
29. Slotted ALOHA ◼ Chia 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. At best: channel use for useful VD transmissions 37% of time! Success (S), Collision (C), Empty (E) slots 18/05/2021 Chương 5. Tầng liên kết dữ liệu 29
30. CSMA (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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 30
31. CSMA collisions ◼ space:  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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 31
32. CSMA/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: ??? 18/05/2021 Chương 5. Tầng liên kết dữ liệu 32
33. CSMA/CD: example 18/05/2021 Chương 5. Tầng liên kết dữ liệu 33
34. “Taking Turns” MAP ◼ Channel partitioning MAP: hiệu quả khi nhiều nút cùng sử dụng ngượ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. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 34
35. “Taking Turns” MAP: Polling & Token passing Polling Token passing ◼ Có một nút điều khiển (master) ◼ Thẻ bài (token) là một thông có nhiệm vụ: báo đặc biệt mà nút nào nắm  lần lượt “thông báo” cho các nút giữ nó sẽ được phép sử dụng khác biết đến lượt truyền và được đường truyền. phép truyền tối đa một số lượng frame nào đó. ◼ Thẻ bài được luân chuyển giữa  khi một nút kết thúc truyền, các nút. master thông báo cho nút khác. ◼ Vấn đề: ◼ Không xung đột.  Một nút gặp sự cố ảnh hưởng tới toàn mạng. ◼ Vấn đề:  nút nào đó sao nhãng việc chuyển  mất thời gian thông báo: tốc độ thẻ bài cho nút khác → cần một trung bình < R. vài thủ tục để khôi phục.  khi master gặp sự cố thì cả mạng ngừng hoạt động! 18/05/2021 Chương 5. Tầng liên kết dữ liệu 35
36. LAN ◼ MAP được sử dụng rộng rãi:  satellite, wireless  LAN (Local Area Network). ◼ LAN:  Mạng nội bộ, có phạm vi hẹp (toàn nhà, trường ĐH )  Vd: LAN kết nối Internet ◼ chia sẻ đường truyền. ◼ Các loại LAN:  Ethernet: phổ biến, sử dụng Random Access MAP.  FDDI (Fiber Distributed Data Interface): Token-passing.  18/05/2021 Chương 5. Tầng liên kết dữ liệu 36
37. Ch5. Giao thức tầng liên kết dữ liệu 5.1 - Introduction and services 5.2 - Error detection and correction 5.3 - Multiple access protocols & LAN 5.4 - Link-layer addressing & ARP 5.5 - Specific link layer technologies 18/05/2021 Chương 5. Tầng liên kết dữ liệu 37
38. Link layer address 32-bit IP address: ◼ network-layer address ◼ IP được đóng trong các gói tin (nguồn, đích). LAN (or MAC or physical) address: ◼ 48 bit (6 bytes) MAC address (đối với hầu hết LANs) ◼ được ghi trong adapter ROM *MAC: Media Access Control (Link layer = MAC + LLC (Logical Link Control) 18/05/2021 Chương 5. Tầng liên kết dữ liệu 38
39. LAN Addresses and ARP Mỗi adapter có một địa chỉ vật lý duy nhất, tương tự như số CMTND. 1A-2F-BB-76-09-AD Broadcast address = FF-FF-FF-FF-FF-FF LAN (wired or = adapter wireless) 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 18/05/2021 Chương 5. Tầng liên kết dữ liệu 39
40. MAC address (cont) ◼ Địa chỉ vật lý được phân bổ bởi IEEE. ◼ Nhà sản xuất phải đăng ký dải địa chỉ với IEEE. ◼ Khi di chuyển từ mạng này sang mạng khác: địa chỉ IP thay đổi nhưng địa chỉ vật lý không thay đổi. ◼ So sánh: địa chỉ vật lý: số CMTND. địa chỉ IP: địa chỉ hòm thư. ◼ Các frame muốn gửi tới đích thì cần chứa địa chỉ vật lý của nút đích. 18/05/2021 Chương 5. Tầng liên kết dữ liệu 40
41. When packet sent from A to B A gửi packet tới B, A sẽ: A 223.1.1.1 ◼ Tra cứu địa chỉ mạng của B, 223.1.2.1 phát hiện ra B cùng mạng với A 223.1.1.2 ◼ link layer gửi packet tới B thông 223.1.1.4 223.1.2.9 B qua frame. 223.1.2.2 223.1.1.3 223.1.3.27 E 223.1.3.1 223.1.3.2 frame source, packet source, dest address dest address B’s MAC A’s MAC A’s IP B’s IP IP payload addr addr addr addr datagram frame 18/05/2021 Chương 5. Tầng liên kết dữ liệu 41
42. ARP: Address Resolution Protocol ◼ Mỗi nút mạng (Host, ???: Làm thế nào để Router) đều có ARP biết địa chỉ vật lý của B khi table biết IP của B? ◼ ARP Table: cho phép từ 237.196.7.78 IP tra cứu ra MAC addr 1A-2F-BB-76-09-AD Cấu tạo bản ghi: 237.196.7.23 237.196.7.14  TTL (Time To Live): LAN thời gian tồn tại của bản 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 ghi tới khi bị xoá. 0C-C4-11-6F-E3-98 237.196.7.88 18/05/2021 Chương 5. Tầng liên kết dữ liệu 42
43. Trường hợp chưa biết MAC addr của nút ◼ Nế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). 18/05/2021 Chương 5. Tầng liên kết dữ liệu 43
44. Trường hợp hai nút ở hai mạng khác nhau ◼ A (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. A R B 18/05/2021 Chương 5. Tầng liên kết dữ liệu 44
45. ◼ A 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.110 ◼ A 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à B ◼ R dùng ARP lấy địa chỉ MAC của B ◼ R tạo frame chứa IP datagram A-to-B IP rồi gửi đến B A R B 18/05/2021 Chương 5. Tầng liên kết dữ liệu 45