Bài giảng Tầng liên kết dữ liệu

Nút mạng:  PCs, Laptop, Routers, Server  Liên kết:  Kênh truyền thông giữacác nút kế tiếp  Hữu tuyến: Ethernet LAN, ADSL, fiber optic  Không dây: Wi-fi, Wi-Max, vệ tinh,  Tầng liên kết dữ liệu: Truyền dữ liệu giữa các thành phần kế tiếp

pdf54 trang | Chia sẻ: vietpd | Ngày: 30/08/2013 | Lượt xem: 1631 | Lượt tải: 1download
Bạn đang xem nội dung tài liệu Bài giảng Tầng liên kết dữ liệu, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
1Chương 8: Tầng liên kết dữ liệu Giảng viên: Ngô Hồng Sơn Khoa CNTT- ðHBK Hà Nội Bộ môn Truyền thông và Mạng máy tính 2Tổng quan  Tuần trước: Tầng ứng dụng  Mô hình: client-server vs. P2P  Case study: HTTP, Mail, FTP…  Tuần này: Tầng liên kết dữ liệu  Dịch vụ:  ðóng gói, ñịa chỉ hóa  Phát hiện và sửa lỗi  Kiểm soát luồng  Kiểm soát truy nhập ñường truyền  Công nghệ mạng LAN (Local Area Network)  Ethernet  Wireless LAN  Công nghệ mạng WAN (Wide Area Network)  Frame relay  ATM  …. 3Giới thiệu về Tầng liên kết dữ liệu 4Nút mạng và liên kết  Nút mạng:  PCs, Laptop, Routers, Server…  Liên kết:  Kênh truyền thông giữa các nút kế tiếp  Hữu tuyến: Ethernet LAN, ADSL, fiber optic…  Không dây: Wi-fi, Wi-Max, vệ tinh,…  Tầng liên kết dữ liệu: Truyền dữ liệu giữa các thành phần kế tiếp “link” 5Tầng liên kết dữ liệu và kiến trúc phân tầng LLC (Logical Link Control) MAC (Media Access Control) Application Transport Network Data-link Physical 802.2 LLC 802.3 Ethernet 802.4 Token Bus 802.5 Token Ring 802.11 Wi-Fi 802.16 Wi-Max ….. IEEE 802.x series Media independent sub-layer Media dependent sub-layer 6Tổng quan về các chức năng Framing Addressing Flow control Error control Media Access Control Datalink layer 7Các chức năng (1)  ðóng gói - Framing:  ðơn vị dữ liệu: Frame (khung tin)  Bên gửi: ñặt gói tin tầng mạng vào khung tin, thêm phần ñầu, phần ñuôi  Bên nhận: Bỏ phần ñầu, phần ñuôi và lấy gói tin truyền lên tầng mạng  ðịa chỉ hóa - Addressing:  ðịa chỉ vật lý ñặt trong phần ñầu gói tin ñể ñịnh danh nút nguồn, nút ñích 8Các chức năng (2)  ðiều khiển truy nhập ñường truyền  Nếu là mạng ña truy nhập, cần có các giao thức truy nhập ñường truyền cho nhiều máy trạm  Kiểm soát luồng:  Kiểm soát tốc ñộ truyền của bên gửi sao cho bên nhận hoạt ñộng tốt, không bị quá tải  Kiểm soát lỗi:  Phát hiện và sửa các lỗi bít  e.g. parity check, checksum, CRC check 9Kiểm soát lỗi Phát hiện lỗi Phát hiện và sửa lỗi 10 Nguyên lý phát hiện lỗi EDC= Error Detection Code (redundancy) Mã phát hiện lỗi Data Data EDC Data Data’ EDC’ All bit in Data’ OK? Y N Error Link with bit errors 11 Mã chẵn lẻ  Mã ñơn  Phát hiện lỗi bít ñơn  Mã hai chiều  Phát hiện và sửa lỗi bít ñơn  Khái niệm về checksum của Internet? 101011 111100 011101 001010 101011 101100 011101 001010 12 Internet checksum (nhắc lại)  Mã kiểm tra lỗi ñộ dài 16 bit  Tại bên gửi  ðặt 16 bit của checksum = 0  Tổng theo các số 16 bits  ðảo bit tất cả  Tại bên nhận  Tổng tất cả theo các số 16 bit  Phải thu ñược toàn các bit 1  Nếu không, gói tin bị lỗi 13 CRC: Cyclic Redundancy Check Mã vòng  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 chuỗi ghép của D và R là một số nhị phân chia hết cho G (chia modulo 2)  chia hết cho G D D R D D’ R’ mod G = 0 ? Y N Link with bit errors mod G = 0 14 CRC: Cách tìm R  có thể viết dưới dạng  D.2r XOR R  chia hết cho G  D.2r XOR R = n.G  D.2r = n.G XOR R  Có nghĩa là R là số dư khi chia D.2r cho G (phép chia modulo 2) R= D.2r mod G  Ví dụ 10101001000 1001 1001 1011110 1110 1001 1110 1001 1111 1001 1100 1001 1010 1001 110 R=110, chuỗi bít gửi ñi là 10101001110 D G R D R 15 CRC biểu diễn dưới dạng ña thức  1011 : x3 +x +1  Ví dụ một số mã CRC ñược sử dụng trong thực tế:  CRC-8 = x8 + x2 + x + 1  CRC-12 = x12+x11+x3+x2+x  CRC-16-CCITT = x16 + x12 + x5 + 1  CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1  G càng dài, mã CRC phát hiện lỗi càng hiệu quả  CRC ñược sử dụng rộng rãi trong thực tế  Wi-fi, ATM, Ethernet…  Phép toán XOR ñược cài ñặt bởi phần cứng  Phát hiện chuỗi bít bị lỗi có ñộ dài nhỏ hơn r+1 bit 16 Kiểm soát truy nhập ñường truyền 17 Các dạng liên kết  ðiểm-nối-ñiểm  ADSL  Telephone modem  Leased Line….  Quảng bá  Mạng LAN truyền thống với hình trạng bus hay mạng hình sao dùng hub (công nghệ lỗi thời)  Wireless LAN, radio network, mobile network  HFC:  …  Các mạng quảng bá cần giao thức ñiều khiển truy nhập ñể tránh xung ñột -> Giao thức ña truy nhập 18 Phân loại các giao thức ña truy nhập  Chia kênh:  Chia tài nguyên của ñường truyền thành nhiều phần nhỏ (Thời gian - TDMA, Tần số - FDMA, Mã - CDMA)  Chia từng phần nhỏ ñó cho các nút mạng  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 (collision)  Cần có cơ chế ñể phát hiện và tránh xung ñột  e.g. Pure Aloha, Slotted Aloha, CSMA/CD, CSMA/CA…  Lần lượt:  Theo hình thức quay vòng  Token Ring, Token Bus…. 19 Các phương pháp chia kênh  FDMA: frequency division multiple access  TDMA: time division multiple access  CDMA: code division multiple access 20 TDMA và FDMA FDMA frequency time TDMA: frequency time 4 kênh Ví dụ: 21 TDMA: Ví dụ  Mạng LAN có 6 máy, 1,3,4 hoạt ñộng. 2, 5, 6 nghỉ 1 3 4 1 3 4 6-slot frame 22 FDMA: Ví dụ f r e q u e n c y b a n d s time FDM cable 23 Các phương pháp truy cập ngẫu nhiên 24 Aloha  Packet-Switched Radio Network  Các nút truyền trên một tần số (f0)  Nút trung tâm nhận và truyền lại một tần số khác (f1) Nếu có hai nút cùng truyền: Xung ñột  Nếu có xung ñột, nút vừa truyền sẽ nhận ñược một gói tin bị lỗi, nó sẽ ñợi một thời gian ngẫu nhiên trước khi truyền lại Central Node Host 1 Host 3Host 2 f0 f1 25 Slotted ALOHA  Thời gian ñược chia làm các khe (slot) bằng nhau  Dữ liệu có cùng kích thước (1 slot)  Các nút phải ñồng bộ hóa thời gian 26 Pure ALOHA Hiu qu kém hn Slotted ALOHA! 27 CSMA/CD  Carrier Sense Multiple Access with Collision Detection (ða truy nhập, có phát hiện xung ñột)  Thế nào là CSMA/CD: trong một cuộc họp  Multiple Access:  Collision:  CSMA: “Listen before talk”  CD  “Listen while talking” b l a h blah b l a h b l a h 28 CSMA/CD  CSMA: Các máy nghe trước muốn truyền:  Nếu kênh rỗi, truyền toàn bộ dữ liệu  Nếu kênh bận, chờ (rút lui và quay lại)  Tại sao lại có xung ñột? ðộ trễ lan truyền 29 Xung ñột trong CSMA  Giả sử kênh truyền có 4 nút  Tín hiệu ñiện từ lan truyền từ nút này ñến nút kia mất một thời gian nhất ñịnh (trễ lan truyền)  Ví dụ: 30 CSMA/CD: Tóm tắt  Máy trạm nghe trước khi muốn truyền  Bận: Rút lui, sau ñó quay lại tiếp tục nghe  Rỗi: Bắt ñầu truyền, vừa truyền vừa “nghe ngóng” xem có xung ñột hay không  Nghe trong thời gian bao lâu?  Nếu phát hiện thấy xung ñột: Hủy bỏ quá trình truyền và quay lại trạng thái rút lui  Sau khi rút lui, khi nào thì quay lại  Exponential back-off 31 So sánh chia kênh và truy nhập ngẫu nhiên  Chia kênh  Hiệu quả, công bằng cho ñường truyền với lưu lượng lớn  Lãng phí nếu chúng ta cấp kênh con cho một nút chỉ cần lưu lượng nhỏ  Truy nhập ngẫu nhiên  Khi tải nhỏ: Hiệu quả vì mỗi nút có thể sử dụng toàn bộ kênh truyền  Tải lớn: Xung ñột tăng lên  Phương pháp quay vòng: Có thể dung hòa ưu ñiểm của hai phương pháp trên 32 Token Ring – Mạng vòng dùng thẻ bài  Một “thẻ bài” luân chuyển lần lượt qua từng nút mạng  Nút nào giữ thẻ bài sẽ ñược gửi dữ liệu  Gửi xong phải chuyển thẻ bài ñi  Một số vấn ñề  Tốn thời gian chuyền thẻ  Trễ  Mất thẻ bài…. T data (nothing to send) T 33 Tổng kết các phương pháp kiểm soát ña truy nhập  Chia kênh  Truy nhập ngẫu nhiên  Quay vòng  Phân tích ưu, nhược ñiểm 34 Thảo luận  Trong phương pháp CSMA/CD, khi lượng dữ liệu cần gửi tăng lên thì:  Xung ñột tăng lên?  Thông lượng tăng lên?  Trong phương pháp TDMA, xung ñột sẽ tăng lên khi lượng dữ liệu cần gửi tăng lên?  Khi lượng dữ liệu cần gửi là rất nhiều, phương pháp Token Ring là kém hơn so với CSMA/CD  Câu hỏi: Giải thích một cách ñịnh lượng hiệu quả của các phương pháp truy cập ñường truyền (Bài tập lớn) 35 LAN: Local Area Network 36 LAN topology Bus Ring WLAN hub, switch Star 37 Mạng Lan Ethernet  IEEE 802.3  Tốc ñộ ña dạng: 10 Mbps – 10 Gbps…  Ethernet: 10BaseT, 10Base2…  Fast Ethernet: 100BaseT  Giga Ethernet Metcalfe’s Ethernet sketch 38 Mạng hình sao  Mạng dạng bus từng phổ biến trước ñây  Các nút mạng cùng chia sẻ một ñường trục  Ngày nay: Chủ yếu là mạng hình sao  Một bộ chuyển mạch trung tâm với nhiều cổng Ethernet  Bộ chuyển mạch có thể tạo liên kết ñộc lập cho 2 nút mạng bất kỳ  Không xung ñột  Không giao thức ña truy nhập . switch bus: coaxial cable star 39 Cấu trúc ñơn vị dữ liệu của Ethernet  Preamble: Bắt ñầu một khung tin  Address: ðịa chỉ vật lý của trạm nguồn, trạm ñích  6 bytes  Type: Giao thức tầng trên (IP, Novell IPX, AppleTalk, …)  PAD: Phần thêm vào cho khung tin ñủ ñộ dài (nếu cần thiết)  CRC: Mã kiểm soát lỗi PAD 40 Chuẩn mạng cục bộ 802.3 Ethernet Standards  Link & Physical Layers  MAC: CSMA/CD  Có nhiều chuẩn Ethernet khác nhau  Cùng giao thức MAC và cấu trúc Frame  Tốc ñộ khác nhau: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps  Phương tiện truyền khác nhau: Cáp quang, cáp ñồng trục, cáp xoắn ñôi. application transport network link physical MAC protocol and frame format 100BASE-TX 100BASE-T4 100BASE-FX100BASE-T2 100BASE-SX 100BASE-BX fiber physical layercopper (twister pair) physical layer 41 Ethernet cổ ñiển Cáp ñồng trục ml 1500< 10Mb/s ( ) bitssMbsPacketsize sTRANSPPROPTRANSP sclPROP 120/1012 122 6105.2/1500/ 8max =×≥∴ >⇒> =×== µ µ µ Thực tế, Min packet size = 512 bits. • Thêm thời gian phát hiện xung ñột. • Cho phép “repeaters” ñủ thời gian khuếch ñại tín hiệu. Bộ lặp 500m 42 Chuẩn Ethernet 10Mb/s Ethernet MAC Protocol 10Base-5 10Base-2 10Base-T 10Base-F 10Base-5: Cáp ñồng trục béo, max = 500m. 10Base-2: Cáp ñồng trục gầy, max ~ 200m (180m). 10Base-T: Dùng cáp xoắn ñôi (twisted-pair) CAT 3 10Base-F: Dùng cáp sợi quang. 43 10Base-T  Sử dụng hub trung tâm, cáp TP CAT 3 (4 cặp dây xoắn).  Dễ lắp ñặt và quản trị  Làm Ethernet trở nên phổ biến hơn Hub 100m 44 “Fast Ethernet” 100Mb/s Ethernet MAC Protocol 100Base-T4 100Base-TX 100Base-FX Mạng hình sao, ðộ dài cáp 100m. 100Base-T4: Cáp TP CAT 3 . 100Base-TX: Cáp TP CAT 5. 100Base-FX: Cáp sợi quang. Hub, switch 100m 45 “Gigabit Ethernet” 1Gbps Ethernet MAC Protocol 1000Base-TX 1000Base-FX 1000Base-TX: 4 cặp dây xoắn, CAT 6. 1000Base-FX: Cáp sợi quang. 46 ðịa chỉ MAC và ARP  ðịa chỉ IP :  32-bit  Dùng trong tầng mạng IP  ðịa chỉ MAC :  Dùng trong tầng liên kết dữ liệu  48 bit 47 48 ARP và ñịa chỉ MAC Mỗi card mạng có một ñịa chỉ MAC Broadcast address = FF-FF-FF-FF-FF-FF = adapter 1A-2F-BB-76-09-AD 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 71-65-F7-2B-08-53 LAN (wired or wireless) 49 ARP: Address Resolution Protocol  Mỗi nút mạng (host, router) có một bảng ARP  ARP table: Ánh xạ ñịa chỉ IP/MAC của một số nút trong mạng < IP address; MAC address; TTL>  TTL (Time To Live): khoảng 20 min.) Vấn ñề: Xác ñịnh ñịa chỉ MAC từ ñịa chỉ IP 1A-2F-BB-76-09-AD 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 71-65-F7-2B-08-53 LAN 137.196.7.23 137.196.7.78 137.196.7.14 137.196.7.88 50 Giao thức ARP : Hoạt ñộng trên cùng một mạng  A muốn gửi dữ liệu tới B mà không biết ñ/c MAC của B  A quảng bá một gói tin ARP, trong ñó chỉ ra ñ/c IP của B  Quảng bá ntn?  Phạm vi gói tin ñược quảng bá?  B nhận ñược ñ/c này sẽ trả lời A ñ/c MAC của mình  Làm sao biết A gửi?  A lưu lại ñ/c MAC của B và gửi tin ñến B  ARP là một giao thức “plug-and-play”  Nếu muốn ARP mở rộng phạm vi hoạt ñộng sang một mạng khác?  ARP Proxy 51 Ví dụ: chuyển gói tin giữa hai máy R 1A-23-F9-CD-06-9B 222.222.222.220 111.111.111.110 E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D 111.111.111.112 111.111.111.111 A 74-29-9C-E8-FF-55 222.222.222.221 88-B2-2F-54-1A-0F B 222.222.222.222 49-BD-D2-C7-56-2A Giả sử A biết ñ/c IP của B 52  A tạo một gói tin IP, ñịa chỉ nguồn A, ñịa chỉ ñích B  A dùng ARP ñể lấy ñ/c MAC của router: 111.111.111.110  A tạo một frame, ñ/c ñích là router, ñặt gói tin vào  A chuyển frame tới R  R nhận frame  R ñọc ñịa chỉ IP của B từ trong khung tin  R dùng ARP ñể tìm ñ/c MAC của B  R tạo một frame, ñặt gói tin vào và chuyển ñến B R 1A-23-F9-CD-06-9B 222.222.222.220 111.111.111.110 E6-E9-00-17-BB-4B CC-49-DE-D0-AB-7D 111.111.111.112 111.111.111.111 A 74-29-9C-E8-FF-55 222.222.222.221 88-B2-2F-54-1A-0F B 222.222.222.222 49-BD-D2-C7-56-2A 53 Tuần tới  More about LAN:  Bridge and Switch  WLAN  Physical layer issues 54 Acknowledgment  Bài giảng có sử dụng các tư liệu và hình vẽ từ:  Tài liệu của trường ñại học Keio và Ritsumekan  Tài liệu “Computer Network, a top down approach” của J.F Kurose và K.W. Ross