›

Bài giảng Computer Networking - Chương 5: Lớp Link và các mạng LAN

ppt 108 trang huongle 4130
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Computer Networking - Chương 5: Lớp Link và các mạng LAN", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_computer_networking_chuong_5_lop_link_va_cac_mang.ppt

Nội dung text: Bài giảng Computer Networking - Chương 5: Lớp Link và các mạng LAN

  1. Chương 5 Lớp Link & các mạng LAN Computer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith Ross Addison-Wesley, July 2004. Slide này được biên dịch sang tiếng Việt theo sự cho phép của các tác giả All material copyright 1996-2006 J.F Kurose and K.W. Ross, All Rights Reserved Lớp Link & các mạng LAN 1
  2. Chương 5: Lớp Data Link Mục tiêu: hiểu các nguyên lý của các dịch vụ lớp data link:  phát hiện và sửa lỗi  chia sẻ kênh broadcast : đa truy cập  định địa chỉ lớp link  truyền dữ liệu tin cậy, điều khiển luồng khởi tạo và hiện thực một số công nghệ lớp link Lớp Link & các mạng LAN 2
  3. Chương 5: Nội dung trình bày 5.1 Giới thiệu và các 5.6 Hubs & switches dịch vụ 5.7 PPP 5.2 Phát hiện và sửa lỗi 5.8 Link Virtualization: 5.3 Các giao thức đa ATM & MPLS truy cập 5.4 Định địa chỉ 5.5 Ethernet Lớp Link & các mạng LAN 3
  4. 5.1 Giới thiệu và các dịch vụ Lớp Link & các mạng LAN 4
  5. Giới thiệu “link” một số công nghệ: host và router gọi là các nút các kênh truyền thông nối liền các nút lân cận gọi là các kết nối (link)  các kết nối hữu tuyến (wired)  các kết nối vô tuyến (wireless)  các LAN gói dữ liệu trong lớp 2 gọi là frame, đóng gói datagram lớp data-link có trách nhiệm truyền datagram từ 1 nút đến nút lân cận trên đường liên kết Lớp Link & các mạng LAN 5
  6. Ngữ cảnh Datagram được truyền so sánh bởi các giao thức và trên hành trình từ Princeton → Lausanne các đường kết nối khác  limo: Princeton → JFK nhau:  máy bay: JFK → Geneva  Vd: Ethernet trên kết nối  ỏ → thứ 1, frame relay trên các tàu h a: Geneva kết nối trung gian, 802.11 Lausanne trên kết nối cuối cùng khách du lịch = datagram Mỗi giao thức kết nối đoạn đường đi = liên kết cung cấp các dịch vụ khác truyền thông nhau kiểu vận chuyển = giao  vd: có thể hoặc không thể thức lớp link cung cấp rdt trên kết nối đại lý du lịch = giải thuật routing Lớp Link & các mạng LAN 6
  7. Các dịch vụ truy cập liên kết, Framing:  đóng gói datagram vào frame, thêm header, trailer  truy cập kênh truyền nếu được chia sẻ  các địa chỉ “MAC” dùng trong các header của frame giúp xác định nguồn, đích • khác với địa chỉ IP! Truyền tin cậy giữa các nút lân cận  đã nghiên cứu làm thế nào để thực hiện được điều này trong chương 3  ít khi dùng trên các kết nối có tỷ lệ lỗi thấp (cáp quang, một số loại cáp xoắn)  các kết nối không dây: tỷ lệ lỗi cao Lớp Link & các mạng LAN 7
  8. Các dịch vụ (tt) Điều khiển luồng:  điều khiển tốc độ giữa các nút gửi và nhận Phát hiện lỗi:  các lỗi gây ra bởi sự suy giảm tín hiệu, nhiễu.  bên nhận phát hiện sự xuất hiện của các lỗi: • thông báo bên gửi truyền lại hoặc bỏ frame đó Sửa lỗi:  bên nhận xác định và sửa bit bị lỗi không cần phải truyền lại Half-duplex và full-duplex  với half duplex, các nút tại 2 điểm đầu cuối của kết nối có thể truyền, nhưng không đồng thời Lớp Link & các mạng LAN 8
  9. các Adaptor trong truyền thông datagram giao thức lớp link nút nhận nút gửi frame frame adapter adapter lớp link được hiện thực bên nhận trong “adaptor” (còn gọi  phát hiện lỗi, rdt, điều là NIC) khiển luồng  Ethernet card, PCMCI  trích ra datagram, chuyển card, 802.11 card cho nút nhận bên gửi: adapter là bán tự động  đóng gói datagram vào các lớp link & physical trong frame  thêm các bit kiểm tra lỗi, rdt, điều khiển luồng Lớp Link & các mạng LAN 9
  10. 5.2 Phát hiện và sửa lỗi Lớp Link & các mạng LAN 10
  11. Phát hiện lỗi EDC= Error Detection and Correction bits (các bit dùng để phát hiện và sửa lỗi, có thể dư thừa) D = Dữ liệu được bảo vệ bởi việc kiểm tra lỗi, có thể chứa các trường header Phát hiện lỗi không đảm bảo tin cậy 100%! •giao thức thỉnh thoảng có thể nhớ một số lỗi •trường EDC lớn hơn giúp việc phát hiện và sửa lỗi tốt hơn Lớp Link & các mạng LAN 11
  12. Kiểm tra Parity Bit Parity đơn: Bit Parity 2 chiều: phát hiện các lỗi bit phát hiện & sửa các lỗi bit 0 0 Lớp Link & các mạng LAN 12
  13. Internet checksum Mục tiêu: phát hiện “các lỗi” trong đoạn đã truyền (chú ý: chỉ dùng tại lớp transport) Bên gửi: Bên nhận: tính toán checksum của đoạn đã ử ộ ạ x lý các n i dung đo n nhận như một chuỗi các số kiểm tra checksum đó có bằng giá nguyên 16 bit trị trong trường checksum? checksum: thêm (tổng bù  KHÔNG – có lỗi ộ ạ 1) vào các n i dung đo n  CÓ – không lỗi. Nhưng có thể bên gửi đặt giá trị vẫn còn lỗi khác? Xem tiếp checksum vào trong các chương sau . trường UDP checksum Lớp Link & các mạng LAN 13
  14. Checksumming: kiểm tra dư thừa theo chu kỳ xem các bit dữ liệu, D, như số nhị phân chọn mẫu r+1 bit, G mục tiêu: chọn r bit CRC, R, như thế  chia cho G (theo cơ số 2)  bên nhận biết G, chia cho G. nếu phần dư khác 0: phát hiện lỗi!  có thể kiểm tra tất cả các lỗi nhỏ hơn r+1 bits sử dụng phổ biến trong thực tế (ATM, HDLC) Lớp Link & các mạng LAN 14
  15. CRC ví dụ Muốn: D.2r XOR R = nG tương đương: D.2r = nG XOR R tương đương: nếu chúng ta chia D.2r cho G, lấy phần còn lại R D.2r R = phần dư của[ ] G Lớp Link & các mạng LAN 15
  16. 5.3 Các giao thức đa truy cập Lớp Link & các mạng LAN 16
  17. Các giao thức và kết nối đa truy cập 2 kiểu “kết nối”: point-to-point (điểm-điểm)  PPP cho truy cập dial-up  kết nối point-to-point giữa Ethernet switch và host broadcast (chia sẻ đường truyền chung)  Ethernet mô hình cũ  upstream HFC  802.11 wireless LAN Lớp Link & các mạng LAN 17
  18. Các giao thức đa truy cập kênh broadcast đơn chia sẻ 2 hoặc nhiều sự truyền đồng thời bởi các nút: giao thoa  collision (đụng độ, tranh chấp) xảy ra nếu nút nhận được 2 hay nhiều tín hiệu cùng thời điểm giao thức đa truy cập giải thuật phân bố xác định cách các nút chia sẻ kênh truyền, nghĩa là xác định khi nào nút có thể truyền truyền thông về chia sẻ kênh phải dùng chính kênh đó!  không có kênh khác để phối hợp Lớp Link & các mạng LAN 18
  19. Các giao thức đa truy cập lý tưởng kênh Broadcast với tốc độ R bps 1. khi 1 nút muốn truyền, nó gửi dữ liệu với tốc độ R 2. khi M nút muốn truyền, nó gửi dữ liệu với tốc độ R/M 3. Hoàn toàn được phân quyền:  không có nút đặc biệt để các quá trình truyền phối hợp  không cần đồng bộ các đồng hồ, slot 4. Đơn giản Lớp Link & các mạng LAN 19
  20. Các giao thức MAC: 1 cách phân loại 3 lớp chính: Phân hoạch kênh  chia kênh thành các “mảnh” nhỏ hơn (các slot thời gian, tần số, mã)  cấp phát mảnh cho nút để sử dụng độc quyền Truy cập ngẫu nhiên  kênh không chia, cho phép các tranh chấp  “giải quyết” các tranh chấp “Xoay vòng”  Xoay vòng các nút, nhưng nút có nhiều quyền hơn được giữ thời gian truyền lâu hơn Lớp Link & các mạng LAN 20
  21. các giao thức phân hoạch kênh MAC: TDMA TDMA: time division multiple access truy cập đến kênh trong theo hình thức “xoay vòng” mỗi trạm có slot với độ dài cố định (độ dài = thời gian truyền gói) trong mỗi vòng các slot không dùng bị bỏ phí ví dụ: 6-trạm LAN, 1,3,4 có gửi gói, các slot 2,5,6 rảnh Lớp Link & các mạng LAN 21
  22. các giao thức phân hoạch kênh MAC: FDMA FDMA: frequency division multiple access phổ kênh truyền được chia thành các dải tần số mỗi trạm được gán một dải tần số cố định thời gian truyền không dùng trong các dải tần rảnh ví dụ: 6-trạm LAN, 1,3,4 có gói truyền, các dải tần 2,5,6 rảnh n ầ i t i ả các d các Lớp Link & các mạng LAN 22
  23. các giao thức truy cập ngẫu nhiên Khi 1 nút có nhu cầu truyền  truyền dữ liệu với trọn tốc độ của kênh  không có sự ưu tiên giữa các nút 2 hoặc nhiều nút truyền → “tranh chấp” giao thức truy cập ngẫu nhiên MAC xác định:  làm cách nào phát hiện tranh chấp  giải quyết tranh chấp (như truyền lại sau đó) Ví dụ:  chia slot ALOHA  ALOHA  CSMA, CSMA/CD, CSMA/CA Lớp Link & các mạng LAN 23
  24. chia slot ALOHA Những giả thiết Hoạt động tất cả frame có cùng kích khi nút lấy frame nó được thước phép truyền trong slot kế thời gian truyền được chia thành các slot kích thước tiếp như nhau (để truyền 1 frame) không tranh chấp, nút có các nút bắt đầu truyền các thể gửi frame mới trong frame chỉ ngay tại lúc bắt slot kế tiếp đầu slot nếu tranh chấp, nút truyền các nút được đồng bộ hóa lại frame trong mỗi slot kế nếu 2 nút hoặc nhiều hơn cùng truyền trong slot, tất cả tiếp với xác suất p cho đến đều phát hiện tranh chấp khi thành công Lớp Link & các mạng LAN 24
  25. chia slot ALOHA Ưu điểm Nhược điểm nút kích hoạt có thể các tranh chấp truyền liên tục với tốc lãng phí slot độ tối đa của kênh các nút có thể phát phân quyền cao: chỉ có hiện tranh chấp với ờ ơ ể các slot trong các nút th i gian ít h n đ truyền gói cần được đồng bộ đồng bộ hóa đơn giản Lớp Link & các mạng LAN 25
  26. hiệu suất trong cách chia slot Aloha hiệu suất là phần slot truyền để đạt hiệu suất cao thành công trong số nhiều nhất với N nút, tìm p* frame dự định truyền của nhiều làm cực đại hóa nút Np(1-p)N-1 với nhiều nút, tìm giới giả sử có N nút với hạn của Np*(1-p*)N-1 nhiều frame để truyền khi N → ∞, cho 1/e = trong slot với xác suất 0.37 là p xác suất để nút 1 Tốt nhất: kênh hữu truyền thành công dụng trong khoảng trong 1 slot = p(1-p)N-1 37% thời gian! xác suất để bất kỳ nút nào đó truyền thành Lớp Link & các mạng LAN 26 công = Np(1-p)N-1
  27. ALOHA thuần nhất (không chia slot) Aloha không chia slot: đơn giản hơn, không đồng bộ khi frame đến đầu tiên  truyền ngay khả năng tranh chấp tăng lên:  frame gửi tại thời điểm t0 tranh chấp với các frame khác gửi trong thời điểm [t0-1,t0+1] Lớp Link & các mạng LAN 27
  28. ALOHA thuần nhất: hiệu suất P(thành công với nút cho trước) = P(nút truyền) . . P(không có nút nào truyền trong [p0-1,p0] P(không có nút nào truyền trong [p0-1,p0] = p . (1-p)N-1 . (1-p)N-1 = p . (1-p)2(N-1) chọn p tối ưu và sau đó cho n -> ∞ = 1/(2e) = 0.18 Thậm chí xấu hơn! Lớp Link & các mạng LAN 28
  29. CSMA (Carrier Sense Multiple Access) CSMA: nghe ngóng trước khi truyền: Nếu kênh rảnh: truyền đi toàn bộ frame Nếu kênh bận, trì hoãn truyền So sánh với con người: đừng ngắt lời người khác đang nói! Lớp Link & các mạng LAN 29
  30. CSMA: các tranh chấp các tranh chấp vẫn xảy ra: trễ lan truyền nghĩa là 2 nút không nghe thấy quá trình truyền của nhau tranh chấp: truyền toàn bộ frame lãng phí thời gian chú ý: vai trò của khoảng cách & trễ lan truyền trong việc xác định xác suất tranh chấp Lớp Link & các mạng LAN 30
  31. CSMA/CD (Collision Detection) CSMA/CD: trì hoãn như trong CSMA  các tranh chấp được phát hiện trong khoảng thời gian ngắn  tranh chấp đường truyền được bỏ qua, giảm sự lãng phí kênh phát hiện tranh chấp:  dễ dàng trong các mạng LAN hữu tuyến: đo cường độ tín hiệu, so sánh với các tín hiệu đã truyền, đã nhận  khó khăn trong các mạng LAN vô tuyến: bên nhận bị tắt trong khi đang truyền so sánh với con người: đàm thoại lịch sự Lớp Link & các mạng LAN 31
  32. CSMA/CD phát hiện tranh chấp Lớp Link & các mạng LAN 32
  33. các giao thức “xoay vòng” MAC các giao thức phân hoạch kênh MAC:  chia sẻ hiệu suất kênh và công bằng khi tải lưu lượng lớn  không hiệu quả khi tải lưu lượng thấp: trễ khi truy cập kênh: băng thông cấp phát là 1/N thậm chí trong trường hợp chỉ có 1 nút hoạt động! các giao thức truy cập ngẫu nhiên MAC  hiệu quả khi tải lưu lượng thấp: 1 nút có thể dùng hết khả năng của kênh  tải lưu lượng lớn: tranh chấp các giao thức “xoay vòng” tìm kiếm giải pháp tốt nhất! Lớp Link & các mạng LAN 33
  34. các giao thức “xoay vòng” Kiểm tra tuần tự: chuyển Token: nút chủ “mời” các điều hành token chuyển tuần nút tớ đến truyền tự từ 1 nút đến nút kế tiếp theo lượt trên vòng thông điệp token liên quan: liên quan:  polling overhead  token overhead  latency  latency  1 vị trí chịu lỗi (chủ)  1 vị trí chịu lỗi (token) Lớp Link & các mạng LAN 34
  35. Tổng kết các giao thức MAC Bạn làm gì với một đường truyền chia sẻ?  Phân hoạch kênh theo thời gian, tần số hoặc mã • chia thời gian, chia tần số  Phân hoạch ngẫu nhiên (động), • ALOHA, S-ALOHA, CSMA, CSMA/CD • cảm nhận: dễ dàng với một số công nghệ (hữu tuyến), khó khăn với một số khác (vô tuyến) • CSMA/CD dùng trong Ethernet • CSMA/CA dùng trong 802.11  Xoay vòng • thăm dò từ vị trí trung tâm, chuyển token Lớp Link & các mạng LAN 35
  36. LAN lớp Data link:  các dịch vụ, phát hiện/sửa lỗi, đa truy cập tiếp: các công nghệ LAN  định địa chỉ  Ethernet  hub, switch  PPP Lớp Link & các mạng LAN 36
  37. 5.4 Định địa chỉ trong lớp Link Lớp Link & các mạng LAN 37
  38. Các địa chỉ MAC và ARP địa chỉ IP 32-bit:  address địa chỉ lớp network  dùng để lấy datagram từ IP subnet đích địa chỉ MAC (hoặc LAN/physical/ Ethernet):  dùng để lấy frame từ một interface với một interface vật lý khác (cùng mạng)  địa chỉ MAC 48 bit (cho hầu hết các loại LAN) được ghi sẵn trong adapter ROM Lớp Link & các mạng LAN 38
  39. Các địa chỉ MAC và ARP Mỗi adapter trên LAN có địa chỉ LAN duy nhất 1A-2F-BB-76-09-AD địa chỉ Broadcast = FF-FF-FF-FF-FF-FF LAN (wired / = adapter wireless) 71-6F7-2B-08-53 58-23-D7-FA-20-B0 0C-C4-11-6F-E3-98 Lớp Link & các mạng LAN 39
  40. Các địa chỉ MAC và ARP việc cấp phát địa chỉ MAC được quản lý bởi IEEE nhà sản xuất mua không gian địa chỉ MAC (duy nhất) So sánh: (a) địa chỉ MAC: giống số chứng minh nhân dân (b) địa chỉ IP: giống số điện thoại địa chỉ MAC phẳng & tính có thể thay đổi  có thể di chuyển card LAN giữa các mạng cục bộ địa chỉ phân cấp IP không thể thay đổi  phụ thuộc vào IP subnet mà nút đó gắn vào Lớp Link & các mạng LAN 40
  41. ARP: Address Resolution Protocol Hỏi: Làm sao xác định địa Mỗi nút IP (Host, chỉ MAC từ địa chỉ IP? Router) trên LAN có bảng ARP bảng ARP: ánh xạ địa 137.196.7.78 chỉ IP/MAC cho một 1A-2F-BB-76-09-AD số nút LAN 137.196.7.23 137.196.7.14 LAN  TTL (Time To Live): 71-6F7-2B-08-53 58-23-D7-FA-20-B0 thời gian sau đó ánh xạ địa chỉ sẽ bị hủy 0C-C4-11-6F-E3-98 (thường là 20 phút) 137.196.7.88 Lớp Link & các mạng LAN 41
  42. ARP: cùng LAN (network) A muốn gửi datagram đến B, địa chỉ MAC của B không có Một cặp địa chỉ IP-to-MAC trong bảng ARP của A được lưu trong bảng ARP của A broadcasts gói truy vấn nó cho đến khi thông tin đã cũ ARP chứa địa chỉ IP của B (times out)  trạng thái mềm: thông tin  địa chỉ MAC đích = FF- này sẽ times out (mất) trừ FF-FF-FF-FF-FF khi được làm tươi  tất cả máy trên LAN (refresh) lại nhận gói truy vấn ARP ARP là “plug-and-play”: đó  các nút tạo các bảng ARP B nhận gói truy vấn ARP và của nó không cần sự can trả lời cho A với địa chỉ thiệp của người quản trị MAC của mình  frame gửi đến địa chỉ MAC của A (unicast) Lớp Link & các mạng LAN 42
  43. DHCP: Dynamic Host Configuration Protocol Mục tiêu: cho phép host tự động lấy địa chỉ IP của nó từ server khi nó kết nối vào mạng Có thể làm mới lại từ địa chỉ đang dùng Cho phép dùng lại các địa chỉ (chỉ giữ địa chỉ trong khi kết nối đang hoạt động) Hỗ trợ cho các người dùng di động, muốn kết nối vào mạng DHCP tổng quan:  host broadcasts thông điệp “DHCP discover”  DHCP server đáp ứng với thông điệp “DHCP offer”  host yêu cầu địa chỉ IP: thông điệp “DHCP request”  DHCP server gửi địa chỉ: thông điệp “DHCP ack” Lớp Link & các mạng LAN 43
  44. kịch bản DHCP client-server 223.1.2.1 A 223.1.1.1 DHCP server 223.1.1.2 223.1.1.4 223.1.2.9 B 223.1.2.2 đến DHCP 223.1.1.3 223.1.3.27 E client cần địa chỉ trong mạng này 223.1.3.1 223.1.3.2 Lớp Link & các mạng LAN 44
  45. kịch bản DHCP client-server đến DHCP server: 223.1.2.5 DHCP discover client src : 0.0.0.0, 68 dest.: 255.255.255.255,67 yiaddr: 0.0.0.0 transaction ID: 654 DHCP offer src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 654 Lifetime: 3600 secs DHCP request src: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 thời Lifetime: 3600 secs gian DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs Lớp Link & các mạng LAN 45
  46. Routing đến LAN khác tình huống: gửi datagram từ A đến B qua R giả sử A biết địa chỉ IP của B A R B 2 bảng ARP trong router R, 1 cho mỗi IP mạng (LAN) Lớp Link & các mạng LAN 46
  47. A tạo datagram với nguồn A, đích B A dùng ARP để lấy địa chỉ MAC của R (dựa vào giá trị 111.111.111.110) A tạo frame lớp link với địa chỉ MAC của R như là địa chỉ đích, frame chứa IP datagram từ-A-đến-B adapter của A gửi frame adapter của A nhận frame R gỡ bỏ IP datagram từ Ethernet frame, thấy đích đến là B R dùng ARP để lấy địa chỉ MAC của B R tạo frame chứa IP datagram từ-A-đến-B gửi tới B A R B Lớp Link & các mạng LAN 47
  48. 5.5 Ethernet Lớp Link & các mạng LAN 48
  49. Ethernet công nghệ LAN hữu tuyến: rẻ hơn $20 cho tốc độ 100Mbs! công nghệ LAN được dùng phổ biến đầu tiên đơn giản hơn, rẻ hơn token LAN và ATM giữ tốc độ trung bình từ 10 Mbps – 10 Gbps Metcalfe’s Ethernet sketch Lớp Link & các mạng LAN 49
  50. cấu trúc hình sao-Star cấu trúc bus dùng phổ biến trong giữa thập niên 90 hiện nay cấu trúc star dùng nhiều hơn các lựa chọn kết nối: hub hoặc switch hub or switch Lớp Link & các mạng LAN 50
  51. Ethernet: cấu trúc Frame Gửi IP datagram đã đóng gói (hoặc gói giao thức lớp network khác) trong Ethernet frame phần đầu: 7 bytes với mẫu 10101010, theo sau là 1 byte với mẫu 10101011 dùng trong các tốc độ đồng hồ gửi, nhận đồng bộ Lớp Link & các mạng LAN 51
  52. Ethernet: cấu trúc Frame (tt) Địa chỉ: 6 bytes  nếu adapter nhận frame với địa chỉ đích đúng của nó hoặc địa chỉ broadcast (như gói ARP), nó chuyển dữ liệu trong frame cho giao thức lớp network  ngược lại, adapter hủy frame Kiểu: chỉ giao thức lớp cao hơn (thường là IP, nhưng cũng có thể là cái khác cũng được hỗ trợ như Novell IPX & AppleTalk) CRC: kiểm tra tại nơi nhận, nếu phát hiện lỗi, đơn giản hủy frame đó Lớp Link & các mạng LAN 52
  53. dịch vụ không kết nối, không tin cậy Connectionless (không kết nối): không bắt tay giữa adapter gửi và nhận. không tin cậy: nhận không gửi các tín hiệu ACK hoặc NACK cho bên gửi  dòng các datagram chuyển cho lớp network có thể có các khoảng trống  các khoảng trống đó sẽ được lấp đầy nếu ứng dụng dùng TCP  trái lại, ứng dụng sẽ thấy các khoảng trống Lớp Link & các mạng LAN 53
  54. Ethernet dùng CSMA/CD không có các slot trước khi thử truyền adapter không truyền nếu lại, adapter chờ một nó cảm nhận rằng có thời gian ngẫu nhiên, adapter nào đó đang nghĩa là random access truyền, nghĩa là carrier (truy cập ngẫu nhiên) sense (cảm nhận) adapter hủy bỏ việc truyền khi nó cảm nhận là có adapter khác đang truyền, nghĩa là collision detection (phát hiện tranh chấp) Lớp Link & các mạng LAN 54
  55. Ethernet CSMA/CD: giải thuật 1. Adaptor nhận datagram từ 4. Nếu adapter phát hiện có lớp network & tạo ra tiến trình truyền khác, nó frame hủy bỏ và gửi tín hiệu báo 2. Nếu adapter cảm nhận tắc nghẽn kênh rảnh, nó bắt đầu 5. Sau khi hủy bỏ, adapter truyền frame. Nếu cảm vào chế độ exponential nhận kênh bận, nó chờ đến backoff: sau tranh chấp khi kênh rảnh và sau đó thứ m, adapter chọn một truyền giá trị K ngẫu nhiên trong 3. Nếu adapter truyền toàn {0,1,2, ,2m-1}. Adapter bộ frame không phát hiện chờ K·512 lần thời gian các tiến trình truyền khác, truyền 1 bit và trở về bước công việc sẽ hoàn thành! 2 Lớp Link & các mạng LAN 55
  56. Ethernet CSMA/CD (tt) tín hiệu báo tắc nghẽn: chắc Exponential Backoff: chắn rằng tất cả các máy mục tiêu: tự điều chỉnh với phát khác đều cảm nhận các lần thử truyền lại nhằm được sự tranh chấp; 48 ước lượng tải hiện hành bits  tải nặng: thời gian chờ ngẫu thời gian truyền 1 bit: 0.1 nhiên sẽ dài hơn micro giây với 10 Mbps tranh chấp lần đầu: chọn K Ethernet ; thuộc {0,1}; độ trễ là K· 512 cho K=1023, thời gian chờ thời gian truyền 1 bit ả kho ng 50 mili giây sau khi tranh chấp lần 2: Nên xem Java chọn K thuộc {0,1,2,3} applet trên AWL Web site! sau khi tranh chấp lần 10, chọn K thuộc {0,1,2,3,4, ,1023} Lớp Link & các mạng LAN 56
  57. CSMA/CD hiệu suất Tprop = thời gian lan truyền tối đa giữa 2 nút trên LAN ttrans = thời gian lan truyền frame kích thước lớn nhất 1 efficiency = 1+ 5t prop / ttrans hiệu suất tiến đến 1 khi tprop tiến đến 0 tiến đến 1 khi ttrans tiến đến ∞ Tốt hơn ALOHA nhưng vẫn còn bị phân quyền, đơn giản, chi phí thấp Lớp Link & các mạng LAN 57
  58. 10BaseT và 100BaseT tốc độ 10/100 Mbps; còn gọi là “fast ethernet” T viết tắt của cụm từ Twisted Pair Các nút kết nối vào 1 hub: “cấu trúc hình sao”; khoảng cách tối đa giữa nút và hub là 100 m twisted pair hub Lớp Link & các mạng LAN 58
  59. các Hub Hub thực chất là repeater lớp physical:  các bit đến từ 1 đường và đi ra tất cả các đường còn lại  tốc độ như nhau  không có bộ đệm frame  không có CSMA/CD tại hub: adapter phát hiện tranh chấp  cung cấp các chức năng quản lý mạng twisted pair hub Lớp Link & các mạng LAN 59
  60. Mã Manchester dùng trong 10BaseT mỗi bit có 1 kiểu chuyển trạng thái cho phép các đồng hồ chạy trong các nút gửi và nhận để đồng bộ với nhau  dùng đồng hồ chung cho tất cả các nút! Lớp Link & các mạng LAN 60
  61. Gigabit Ethernet dùng dạng thức frame Ethernet chuẩn cho phép các kết nối điểm-điểm và các kênh broadcast chia sẻ trong chế độ chia sẻ, CSMA/CD được dùng, yêu cầu khoảng cách giữa các nút ngắn để đạt hiệu quả dùng các hub, gọi là “Buffered Distributors” Full-Duplex tại 1 Gbps cho các kết nối điểm-điểm hiện nay tốc độ đã đạt 10 Gbps! Lớp Link & các mạng LAN 61
  62. 5.6 Các Hub & switch Lớp Link & các mạng LAN 62
  63. Liên kết các hub Backbone hub liên kết các đoạn LAN Mở rộng khoảng cách tối đa giữa các nút nhưng các vùng tranh chấp riêng trong đoạn trở thành vùng tranh chấp lớn Không thể kết nối 10BaseT & 100BaseT hub hub hub hub Lớp Link & các mạng LAN 63
  64. Switch Thiết bị lớp Link  lưu và chuyển tiếp các frame Ethernet  xem xét header frame và chọn chuyển tiếp frame dựa trên địa chỉ MAC đích  khi frame được chuyển tiếp trên đoạn, dùng CSMA/CD để truy cập đoạn trong suốt  các host không cần chú ý đến sự hiện diện của các switch plug-and-play, tự học  switch không cần cấu hình Lớp Link & các mạng LAN 64
  65. Chuyển tiếp switch 1 2 3 hub hub hub •Làm sao xác định trên đoạn LAN nào sẽ chuyển tiếp frame? •Giống như vấn đề routing Lớp Link & các mạng LAN 65
  66. Tự học 1 switch có 1 bảng switch mỗi dòng trong bảng này có:  (địa chỉ MAC, Interface, Time Stamp) các dòng cũ trong bảng bị bỏ (TTL có thể đến 60 phút) switch học để biết những host nào có thể chạm đến thông qua những interfaces nào  khi nhận frame, switch “học” vị trí của bên gửi: đoạn LAN đi đến  ghi cặp bên gửi/vị trí vào trong bảng switch Lớp Link & các mạng LAN 66
  67. Lọc/Chuyển tiếp Khi switch nhận 1 frame: chỉ mục sắp xếp lại bảng switch dùng địa chỉ MAC đích if dòng tìm thấy cho đích then { if đích nằm trên đoạn từ đó frame đến then bỏ frame else chuyển tiếp frame trên interface chỉ định } else tràn ngập chuyển tiếp lên tất cả interface trừ nơi mà frame đến Lớp Link & các mạng LAN 67
  68. Switch: ví dụ Giả sử C gửi frame đến D switch địa chỉ interface 1 A 1 3 2 B 1 E 2 hub G 3 A hub hub I D F G B C E H Switch nhận frame từ C  ghi chú trong bảng bridge là C đến từ interface 1  D không có trong bảng, switch chuyển tiếp frame vào trong interface 2 và 3 ậ ở frame nh n b i D Lớp Link & các mạng LAN 68
  69. Switch: ví dụ Giả sử D trả lời phản hồi với frame cho C. địa chỉ interface switch A 1 B 1 E 2 hub G 3 A hub hub I C 1 D F G B C E H Switch nhận frame từ D  ghi chú trong bảng bridge là D đến từ interface 2  vì C có trong bảng, switch chỉ chuyển tiếp frame vào trong interface 1 ậ ở frame nh n b i C Lớp Link & các mạng LAN 69
  70. Switch: lưu thông độc lập switch chia subnet thành các đoạn mạng LAN switch lọc các gói:  các frame cùng đoạn LAN thường KHÔNG chuyển tiếp lên các đoạn LAN khác  các đoạn trở thành các vùng tranh chấp riêng biệt switch vùng tranh chấp hub hub hub vùng tranh chấp vùng tranh chấp Lớp Link & các mạng LAN 70
  71. Switch: truy cập độc quyền Switch với nhiều interfaces A các host có kết nối trực tiếp với switch C’ B không tranh chấp; full duplex switch Switching: A-đến-A’ và B-đến- C B’ đồng thời, không có các tranh chấp B’ A’ Lớp Link & các mạng LAN 71
  72. những vấn đề khác trên Switch cut-through switching: frame chuyển tiếp từ port vào đến port ra không cần tập hợp đủ toàn bộ frame đầu tiên kết hợp các interfaces chia sẻ/độc quyền, 10/100/1000 Mbps Lớp Link & các mạng LAN 72
  73. Mạng cơ quan mail server đi đến mạng bên ngoài router web server switch IP subnet hub hub hub Lớp Link & các mạng LAN 73
  74. Switches & Routers đều là các thiết bị store-and-forward (lưu giữ & chuyển tiếp)  các router: các thiết bị lớp network (xem xét các header lớp network)  các switch là các thiết bị lớp link các router duy trì bảng routing, hiện thực các giải thuật routing các switch duy trì các bảng switch, hiện thực các giải thuật lọc, tự học Lớp Link & các mạng LAN 74
  75. Tổng kết so sánh hubs routers switches traffic no yes yes isolation plug & play yes no yes optimal no yes no routing cut yes no yes through Lớp Link & các mạng LAN 75
  76. 5.7 PPP Lớp Link & các mạng LAN 76
  77. Những yêu cầu thiết kế PPP [RFC 1557] packet framing: đóng gói datagram lớp network vào frame lớp data link  mang dữ liệu lớp network của bất kỳ giao thức lớp network nào (không chỉ IP) tại cùng thời điểm  khả năng demultiplex (phân đa kênh) lên lớp trên bit trong suốt: phải mang bất kỳ mẫu bit nào trong trường data phát hiện lỗi (không sửa lỗi) kết nối động: phát hiện, thông báo kết nối lỗi đến lớp network sự đam̀ phań địa chỉ lớp network: mỗi điểm đầu cuối có thể tự học/cấu hình địa chỉ mạng của điểm khác Lớp Link & các mạng LAN 77
  78. PPP không yêu cầu không sửa/phục hồi lỗi không điều khiển luồng vận chuyển không cần theo thứ tự không cần hỗ trợ các kết nối đa điểm (như polling) Phục hồi lỗi, điều khiển luồng, sắp thứ tự dữ liệu được ủy nhiệm cho các lớp cao hơn! Lớp Link & các mạng LAN 78
  79. PPP Data Frame Flag: tách riêng (framing) Địa chỉ: không làm gì cả (chỉ có 1 tùy chọn) Điều khiển: không làm gì cả; tương lai có thể có nhiều trường điều khiển Giao thức: giao thức lớp trên nơi mà frame sẽ đến (ví dụ: PPP-LCP, IP, IPCP ) Lớp Link & các mạng LAN 79
  80. PPP Data Frame thông tin: dữ liệu lên lớp trên đang được mang đi kiểm tra: kiểm tra dư thừa theo chu kỳ để phát hiện lỗi Lớp Link & các mạng LAN 80
  81. Byte Stuffing (chèn thêm byte) yêu cầu “dữ liệu trong suốt”: trường dữ liệu phải được phép chứa mẫu flag Hỏi: nếu nhận thì đó là dữ liệu hay flag? Bên gửi: thêm (“stuffs”) byte sau mỗi byte dữ liệu Bên nhận: hai byte trên 1 hàng: hủy byte đầu, tiếp tục nhận dữ liệu chỉ 1 byte : flag byte Lớp Link & các mạng LAN 81
  82. Byte Stuffing mẫu flag byte trong dữ liệu gửi đi mẫu flag byte cộng với byte chèn thêm trong dữ liệu đã truyền Lớp Link & các mạng LAN 82
  83. PPP: giao thức điều khiển dữ liệu Trước khi trao đổi dữ liệu lớp network, các peer của data link phải cấu hình kết nối PPP (độ dài frame tối đa, cách chứng thực) thông tin tự học/cấu hình lớp network  với IP: mang các thông điệp IP Control Protocol (IPCP) (trường giao thức: 8021) để cấu hình/tự học địa chỉ IP Lớp Link & các mạng LAN 83
  84. 5.8 Link Virtualization: ATM & MPLS Lớp Link & các mạng LAN 84
  85. Các mạng ảo Sự ảo hóa các tài nguyên: một trừu tượng hóa mạnh mẽ trong kỹ thuật hệ thống ví dụ: bộ nhớ ảo, thiết bị ảo máy ảo: như Java hệ điều hành IBM VM xuất hiện từ những năm 1960/1970 sự phân lớp: không phải lo lắng về những chi tiết, chỉ xử lý trừu tượng hóa những lớp thấp hơn Lớp Link & các mạng LAN 85
  86. Internet: Các mạng ảo 1974: nhiều mạng không kết nối sự khác biệt: với nhau  các quy ước định địa chỉ  ARPAnet  các dạng thức gói tin  các mạng truyền dữ liệu trên cáp  phục hồi lỗi  mạng chuyển gói vệ tinh (Aloha)  routing  mạng chuyển gói radio ARPAnet mạng vệ tinh "A Protocol for Packet Network Intercommunication", V. Cerf, R. Kahn, IEEE Transactions on Communications, Lớp Link & các mạng LAN 86 May, 1974, pp. 637-648.
  87. Internet: Các mạng ảo (tt) lớp Internetwork (IP): Gateway: định địa chỉ: Internet xuất hiện “nhúng các gói Internet theo dạng như một thực thể đồng nhất bất thức gói cục bộ hoặc khai thác chấp sự hỗn tạp của mạng cục bộ chúng” bên dưới dẫn đường (mức Internet) đến mạng của các mạng gateway kế tiếp gateway ARPAnet mạng vệ tinh Lớp Link & các mạng LAN 87
  88. Kiến trúc Internet của Cerf & Kahn Sự ảo là gì? 2 lớp định địa chỉ: mạng Internet và mạng cục bộ lớp mới (IP) làm cho mọi thứ trở nên đồng nhất tại lớp internet công nghệ mạng cục bộ bên dưới  cáp  vệ tinh  modem điện thoại 56K  ngày nay: ATM, MPLS “không nhìn thấy” tại lớp internet. chỉ xem như công nghệ lớp data link Lớp Link & các mạng LAN 88
  89. ATM & MPLS ATM, MPLS chia các mạng theo quyền hạn của chúng  các mô hình dịch vụ, định địa chỉ, dẫn đường khác nhau từ Internet được Internet xem như các router IP kết nối logic  giống như kết nối dial-up là một phần thực tế của mạng riêng biệt (mạng điện thoại) Lớp Link & các mạng LAN 89
  90. Asynchronous Transfer Mode: ATM Chuẩn trong những năm 1990/2000 cho tốc độ cao (155Mbps đến 622 Mbps và có thể cao hơn), kiến trúc Broadband Integrated Service Digital Network Mục tiêu: tích hợp, chuyển vận giữa các thiết bị đầu cuối dữ liệu, giọng nói, video  các yêu cầu chất lượng dịch vụ/thời gian thực của tiếng nói, video (khác với Internet là mô hình hướng đến hiệu quả cao nhất)  “thế hệ kế tiếp” của điện thoại  chuyển gói (các gói có độ dài cố định, gọi là các “cell”) dùng các mạch ảo Lớp Link & các mạng LAN 90
  91. kiến trúc ATM lớp tiếp xúc: chỉ ở mức ngoài của mạng ATM  phân đoạn/tổng hợp dữ liệu  tương đối giống với lớp transport của Internet lớp ATM: lớp “network”  chuyển và dẫn đường cell lớp physical Lớp Link & các mạng LAN 91
  92. ATM: lớp network hay lớp link? Quan sát: vận chuyển giữa 2 thiết bị đầu cuối: “ATM từ desktop IP đến desktop” network ATM  ATM là một công network nghệ mạng Thực tế: dùng để kết nối các router IP backbone  “IP trên ATM”  ATM như lớp kết nối, liên kết các IP router Lớp Link & các mạng LAN 92
  93. ATM Adaptation Layer (AAL) ATM Adaptation Layer (AAL): “tiếp xúc” các lớp trên (IP hoặc các ứng dụng ATM thực tế) đến lớp ATM bên dưới AAL xuất hiện chỉ trong các hệ thống đầu cuối, không có trong các switch đoạn của lớp AAL (các trường header/trailer, dữ liệu) phân mảnh thành các cell ATM  tương tự: đoạn TCP trong nhiều gói IP Lớp Link & các mạng LAN 93
  94. ATM Adaptation Layer (AAL) [tt] Có nhiều phiên bản khác nhau của lớp AAL, phụ thuộc vào lớp dịch vụ ATM AAL1: cho các dịch vụ CBR (Constant Bit Rate) như giả lập mạch AAL2: cho VBR (Variable Bit Rate) như MPEG video AAL5: cho dữ liệu (như IP datagrams) Dữ liệu của user AAL PDU ATM cell Lớp Link & các mạng LAN 94
  95. Lớp ATM Dịch vụ: vận chuyển các cells xuyên qua mạng ATM network Bảo đảm? Kiến trúc Mô hình Phản hồi mạng dịch vụ Bandwidth M.mátThứtự Địnhthì tắc nghẽn Internet h.suất tốt không khôngkhông không không (➔ từ nhất mất mát) ATM CBR tốc độ có có có không không đổi tắc nghẽn ATM VBR tốc độ có có có không bảo đảm tắc nghẽn ATM ABR bảo đảm khôngcó không có tối thiểu ATM UBR không khôngcó không không Lớp Link & các mạng LAN 95
  96. Lớp ATM: các mạch ảo Vận chuyển trên mạch ảo: các cell lan truyền từ nguồn đến đích trên mạch ảo  thiết lập cuộc gọi, chia nhỏ trước khi dữ liệu có thể truyền  mỗi gói lan truyền trên mạch ảo xác định (không ID đích)  mọi switch trên đường đi từ nguồn đến đích duy trì “trạng thái” cho mỗi kết nối đã qua  các tài nguyên kết nối, switch (băng thông, các bộ đệm) có thể được cấp phát cho mạch ảo Permanent VCs (PVCs) – các mạch ảo bền vững  những kết nối bền vững thời gian dài  tiêu biểu: dẫn đường “bền vững” giữa các IP router Switched VCs (SVC) – các mạch ảo chuyển hướng  linh hoạt thiết lập dựa trên cơ sở mỗi cuộc gọi Lớp Link & các mạng LAN 96
  97. Lớp ATM: các mạch ảo Những thuận lợi của cách tiếp cận mạch ảo ATM:  hiệu suất, chất lượng dịch vụ được bảo đảm cho kết nối đã ánh xạ với mạch ảo (băng thông, độ trễ, sự biến động độ trễ) Những haṇ chế của cách tiếp cận mạch ảo ATM:  Không đủ sự hỗ trợ cần thiết cho lưu thông datagram  mỗi kết nối cần thiết giữa cặp nguồn/đích → không mở rộng được (cần đến N*2)  SVC đưa ra latency thiết lập cuộc gọi, xử lý các kết nối thời gian ngắn Lớp Link & các mạng LAN 97
  98. Lớp ATM: ATM cell byte ATM cell header 48-byte cần tải  Tại sao? tải nhỏ → độ trễ khi tạo cell ngắn (khi số hóa giọng nói)  nửa khoảng từ 32 đến 64 (thỏa thuận!) Cell header dạng thức Cell Lớp Link & các mạng LAN 98
  99. ATM cell header VCI: virtual channel ID  sẽ thay đổi từ kết nối đến kết nối thông qua mạng PT: kiểu tải (như cell RM với cell dữ liệu) CLP: Cell Loss Priority bit  CLP = 1 thể hiện cell có độ ưu tiên thấp, có thể hủy bỏ nếu tắc nghẽn HEC: Header Error Checksum  kiểm tra sự dư thừa theo chu kỳ Lớp Link & các mạng LAN 99
  100. ATM: lớp Physical (tt) 2 mảnh (lớp con) của lớp physical Transmission Convergence Sublayer (TCS): tiếp xúc giữa lớp ATM trên Physical Medium Dependent (PMD): phụ thuộc vào phương tiện vật lý sẽ dùng Các chức năng TCS:  sinh ra Header checksum: 8 bits CRC  mô tả sơ lược cell  với lớp con “không cấu trúc” PMD, chỉ truyền các cell rảnh rỗi khi không có cell dữ liệu nào phải truyền Lớp Link & các mạng LAN 100
  101. ATM: lớp Physical (tt) Physical Medium Dependent (PMD) SONET/SDH: truyền cấu trúc frame đồng bộ bit phân hoạch băng thông (TDM); tốc độ: OC3 = 155.52 Mbps; OC12 = 622.08 Mbps; OC48 = 2.45 Gbps, OC192 = 9.6 Gbps TI/T3: truyền cấu trúc frame (kiến trúc điện thoại cũ): 1.5 Mbps/ 45 Mbps không cấu trúc: chỉ các cell (bận/rảnh) Lớp Link & các mạng LAN 101
  102. IP-trên-ATM IP-trên-ATM thay Chỉ có IP cổ điển thế “mạng” (như các 3 “mạng” (như các đoạn LAN) với mạng đoạn LAN) ATM MAC (802.3) và các các địa chỉ ATM, địa địa chỉ IP chỉ IP ATM network Ethernet Ethernet LANs LANs Lớp Link & các mạng LAN 102
  103. IP-trên-ATM app app transport transport IP IP IP AAL AAL Eth Eth ATM ATM phy phy phy ATM phy phy ATM phy Lớp Link & các mạng LAN 103
  104. Đường đi của Datagram trong mạng IP-trên- ATM tại Host nguồn:  lớp IP ánh xạ giữa địa chỉ IP, ATM đích (dùng ARP)  chuyển datagram cho AAL5  AAL5 đóng gói các cell dữ liệu, đoạn → chuyển cho lớp ATM mạng ATM: di chuyển các cell dọc theo mạng ảo đến đích tại Host đích:  AAL5 tổng hợp các cell thành datagram nguyên thủy  nếu kiểm tra CRC là tốt thì datagram chuyển cho IP Lớp Link & các mạng LAN 104
  105. IP-trên-ATM các datagram IP đi ATM tiếp vào các ATM network AAL5 PDU từ các địa chỉ IP thành các địa chỉ ATM  giống các địa chỉ IP thành các địa Ethernet chỉ 802.3 MAC! LANs Lớp Link & các mạng LAN 105
  106. Multiprotocol label switching (MPLS) mục tiêu ban đầu: tăng tốc chuyển IP bằng cách dùng nhãn độ dài cố định (thay cho địa chỉ IP)  dựa trên các ý tưởng từ cách tiếp cận mạch ảo  nhưng datagram IP vẫn giữ địa chỉ IP PPP hoặc Ethernet MPLS header IP header phần còn lại của frame lớp Link header nhãn Exp S TTL 20 3 1 5 Lớp Link & các mạng LAN 106
  107. Các router có khả năng MPLS nghĩa là các router có khả năng chuyển nhãn chuyển tiếp các gói đến interface đi ra chỉ dựa trên giá trị nhãn (không xem xét địa chỉ IP)  bảng forwarding MPLS khác với bảng forwarding IP giao thức chuyển tín hiệu cần để thiết lập chuyển tiếp  RSVP-TE  chuyển tiếp có thể dọc theo những đường mà IP không được phép dùng riêng (như: dẫn đường có nguồn xác định)  dùng MPLS cho kỹ thuật lưu thông phải cùng tồn tại với các router chỉ dùng IP Lớp Link & các mạng LAN 107
  108. các bảng forwarding MPLS nhãn nhãn interface vào ra đích ra 10 A 0 nhãn nhãn interface 12 D 0 vào ra đích ra 8 A 1 10 6 A 1 12 9 D 0 R6 0 0 D 1 1 R4 R3 R5 0 0 A R2 nhãn nhãnR 1 interface vào ra đích ra nhãn nhãn interface vào ra đích ra 6 - A 0 8 6 A 0 Lớp Link & các mạng LAN 108