Bài giảng Data Link Layer - Đoàn Thị Thu Hà

Nội dung text: Bài giảng Data Link Layer - Đoàn Thị Thu Hà

1. Data Link Layer doanha86@gmail.com LOGO Đoàn Thị Thu Hà Khoa Công Nghệ Thông Tin Đại Học Nông Nghiệp Hà Nội
2. Contents www.thmemgallery.com 1. Introduction and services 2. Error detection and correction 3. Multiple access protocols & LAN 4. Link-layer addressing & ARP 5. Specific link layer technologies Company Logo
3. 1. Introduction and services www.thmemgallery.com Company Logo
4. Introduction www.thmemgallery.com Một số thuật ngữ ❑ Hosts và routers được gọi là các nút (notes) – các Bridges và switches cũng vậy ❑ Các kênh truyền thông kết nối các nút gần kề dọc theo đường dẫn truyền thông được gọi là các liên kết (links) ➢ Các liên kết hữu tuyến ➢ Các liên kết vô tuyến ➢ Các mạng cục bộ ❑ Đơn vị dữ liệu ở tầng 2 là frame, đóng gói/ bao bọc gam dữ liệu packet → nhiều frame Company Logo
5. Introduction www.thmemgallery.com Tầng liên kết dữ liệu có trách nhiệm truyền gam dữ liệu từ một nút gần kề qua một liên kết truyền thông Company Logo
6. Introduction www.thmemgallery.com 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 Company Logo
7. Introduction www.thmemgallery.com Ngữ cảnh ❑ Gam dữ liệu được chuyên chở Tương tự như sự vận chuyển Một chuyến đi từ Thái Bình ra bởi các giao thức khác nhau ở Côn Đảo tầng LKDL qua các liên kết -Ô tô: Đi từ TB đến HN -Máy bay: HN vào TP.HCM truyền thông khác nhau: -Tàu thuỷ: TP.HCM ra ➢ VD: Ethernet ở liên kết đầu tiên, Côn Đảo frame relay ở các liên kết trung ❑Khách du lịch = datagram ❑Đoạn vận chuyển gian, 802.11 ở liên kết cuối cùng = Liên kết truyền thông ❑ Mỗi giao thức ở tầng LKDL cung ❑Phương thức vận chuyển = giao thức tầng LKDL cấp các dịch vụ khác nhau ❑Đại lý du lịch ➢ VD: Có thể cung cấp các dịch vụ = giải thuật định tuyến chuyển dữ liệu tin cậy hoặc không qua liên kết truyền thông Company Logo
8. Services – Các dịch vụ www.thmemgallery.com ❑ Đóng frame và truy cập đường truyền (framing, link access) ▪ Đóng gói gam dữ liệu vào các frame, thêm thông tin điều kiển và kiểm soát lỗi (header, trailer) ▪ 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 để định danh nguồn và đích. ❑ Truyền dữ liệu 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. ➢ Hiếm khi được thực hiện ở các liên kết có tỷ lệ lỗi bít thấp( cáp quang, ) ➢ Được cung cấp ở các đường truyền vô tuyến vì tỷ lệ lỗi cao Company Logo
9. Services www.thmemgallery.com ❑ 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, điều chỉnh tốc độ giữa các nút gửi và nhận ❑ Error detection – Phát hiện lỗi ▪ Lỗi có thể phát sinh do nhiễu, sự suy giảm tín hiệ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 - Sửa lỗi ▪ Nút nhận xác định bit bị lỗi và sửa các bit lỗi mà không cần yêu cầu nút gửi phải gửi 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. Company Logo
10. 2. Error detection and correction www.thmemgallery.com Trong quá trình truyền dữ liệu có thể xảy ra lỗi ❑ Để phát hiện lỗi có thể xảy ra trong quá trình truyền: ➢ Bên gửi thêm vào các gói tin một số thông tin ➢ Bên nhận dựa vào các thông tin trên để kiểm tra ❑ 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 EDC càng lớn thì khả năng kiểm soát lỗi càng tốt. Company Logo
11. 2. Error detection and correction www.thmemgallery.com ❑Các kỹ thuật dò tìm lỗi phổ biến ➢Kiểm tra tính chẵn lẻ (Parity bit checking) ➢Kiểm tra tổng (Checksum) ➢Kiểm dư vòng (Cyclic Redundancy Check) ❑Error detection: không phải lúc nào cũng phát hiện được lỗi! Company Logo
12. Kiểm tra tính chẵn lẻ (Parity checking) www.thmemgallery.com ❑ Parity: cân bằng!!! (chẵn lẻ). ❑ Parity chẵn (even parity) ▪ Tổng số các bit 1 là chẵn. ▪ Vd: parity của 1011 1101 là 0 ❑ Parity lẻ (odd parity): ▪ Tổng số các bit 1 là lẻ. ▪ Vd: parity của 1101 0101 là 1. Company Logo
13. Parity checking www.thmemgallery.com Single Bit Parity: Two Dimensional Bit Parity: Detect single bit errors Detect and correct single bit errors 0 0 Company Logo
14. Kiểm tra tổng (Checksum) www.thmemgallery.com ❖Xem slide 21-22 Chapter 3 Company Logo
15. Cyclic Redundancy Check www.thmemgallery.com ❑Dùng các hàm toán học để xét dữ liệu ❑Tính toán phức tạp hơn rất nhiều ❑Có thể xử lý được nhiều lỗi hơn Company Logo
16. Cyclic Redundancy Check www.thmemgallery.com ❑ Dữ liệu được xem như một số nhị phân: D ❑ Chọn một chuỗi r + 1 bit, G (chuỗi sinh- Generator) ❑ Tìm một chuỗi R độ dài r bit, sao cho ghép của D và R thành một số nhị phân chia hết cho G( chia modunlo 2) Company Logo
17. Cyclic Redundancy Check www.thmemgallery.com ❖Cách tìm R Company Logo
18. 3. Multiple Access www.thmemgallery.com 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 Company Logo
19. MAP: Multiple Access Protocols www.thmemgallery.com ❑ 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. Company Logo
20. Giao thức đa truy cập lí tưởng www.thmemgallery.com Đườ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. Company Logo
21. MAP: taxonomy (phân loại) www.thmemgallery.com ❑ Channel partitioning – Chia kênh ▪ Kênh truyền được chia thành các “phần” nhỏ (theo Thời gian - TDMA, Tần số - FDMA, MÃ - CDMA). ▪ Chia từng phần đó cho các nút mạng → không xung đột (collision). ❑ Random access - truy nhập ngẫu nhiên ▪ Kênh không được chia, cho phép đồng thời truy nhập, chấp nhận là có xung đột ▪ Cần khả năng phát hiện, 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: Token Ring, Token Bus Company Logo
22. TDMA: time division multiple access www.thmemgallery.com ❑ 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. Company Logo
23. FDMA: frequency division multiple access www.thmemgallery.com ❑ 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). Company Logo
24. CDMA (Code Division Multiple Access) www.thmemgallery.com ❑ 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 ). Company Logo
25. CDMA example: www.thmemgallery.com Company Logo
26. CDMA example: two-sender interference www.thmemgallery.com sender 1 sender 2 Company Logo
27. Random Access Protocols www.thmemgallery.com ❑ 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. Company Logo
28. Slotted ALOHA www.thmemgallery.com ❑ 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 Company Logo
29. CSMA (Carrier Sense Multiple Access) www.thmemgallery.com ❑ 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. Company Logo
30. CSMA collisions www.thmemgallery.com ❑ 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. Company Logo
31. CSMA/CD (Collision Detection) www.thmemgallery.com ❖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ế. ▪ Company Logo
32. CSMA/CD: example www.thmemgallery.com Company Logo
33. So sách hai phương pháp www.thmemgallery.com ❖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. Company Logo
34. “Taking Turns” MAP: Polling www.thmemgallery.com Có 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 < R. ▪ khi master gặp sự cố thì cả mạng ngừng hoạt động! Company Logo
35. “Taking Turns” MAP: Token passing www.thmemgallery.com Company Logo
36. LAN www.thmemgallery.com ❖ 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. ▪ Company Logo
37. Link layer address www.thmemgallery.com 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) Company Logo
38. LAN Addresses and ARP www.thmemgallery.com 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 Company Logo
39. MAC address (cont) www.thmemgallery.com ❑ Đị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. Company Logo
40. When packet sent from A to B www.thmemgallery.com 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 223.1.1.2 với A 223.1.1.4 223.1.2.9 B ❖ link layer gửi packet tới B 223.1.2.2 223.1.1.3 223.1.3.27 E thông qua frame. 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 Company Logo
41. ARP: Address Resolution Protocol www.thmemgallery.com ❖ Mỗi nút mạng ???: Làm thế nào để (Host, Router) đều biết địa chỉ vật lý của B khi có ARP table biết IP của B? ❖ ARP Table: cho phép từ IP tra cứu 237.196.7.78 ra MAC addr 1A-2F-BB-76-09-AD Cấu tạo bản ghi: 237.196.7.23 237.196.7.14 LAN ▪ TTL (Time To Live): 71-65-F7-2B-08-53 58-23-D7-FA-20-B0 thời gian tồn tại của bản ghi tới khi bị xoá. 0C-C4-11-6F-E3-98 237.196.7.88 Company Logo
42. Trường hợp chưa biết MAC addr của nút www.thmemgallery.com ❖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). Company Logo
43. Trường hợp hai nút ở hai mạng khác nhau www.thmemgallery.com ❖ 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 Company Logo
44. ❖ A creates IP packet with source A, destination B ❖ A uses ARP to get R’s physical layer address for 111.111.111.110www.thmemgallery.com ❖ A creates frame with R's physical address as dest, frame contains A-to-B IP datagram ❖ A’s data link layer sends frame ❖ R’s data link layer receives frame ❖ R removes IP datagram from frame, sees its destined to B ❖ R uses ARP to get B’s physical layer address ❖ R creates frame containing A-to-B IP datagram sends to B A R B Company Logo
45. www.themegallery.com LOGO