›
›

Mạng máy tính - Chương 4: Tầng mạng – network layer

pdf 80 trang vanle 3440
Download
Bạn đang xem 20 trang mẫu của tài liệu "Mạng máy tính - Chương 4: Tầng mạng – network layer", để 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:

  • pdfmang_may_tinh_chuong_4_tang_mang_network_layer.pdf

Nội dung text: Mạng máy tính - Chương 4: Tầng mạng – network layer

  1. Chương 4 Tầng Mạng – Network layer Nhập mơn mạng máy tính
  2. Chương 4: Nội dung trình bày  4. 1 Giới thiệu  4.5 các giải thuật Routing  4.2 Virtual circuit và  Link state datagram networks  Distance Vector  4.3 Bên trong một router?  4.4 IP: Internet Protocol  dạng thức Datagram  địa chỉ IPv4  ICMP  IPv6 2
  3. 4. 1 Giới thiệu 3 3
  4. lớp Network  chuyển các đoạn từ host ử ế ậ application g i đ n host nh n transport network data link  bên gửi sẽ đĩng gĩi các network physical network data link network đoạn vào trong các data link physical data link physical physical datagram network data link physical network  bên nhận sẽ chuyển các data link physical đoạn cho lớp transport network network data link  các giao thức lớp network data link physical physical trong mọi host, router network data link application physical transport  ẽ network Router s xem xét các data link trường header trong tất physical cả các IP datagram đã được chuyển cho nĩ 4
  5. 2 chức năng chính  Chuyển mạch (forwarding): di chuyển các gĩi từ đầu vào đến đầu ra thích hợp của router  Tìm đường (routing): xác định đường đi cho các gĩi từ nguồn đến đích  các giải thuật routing 5
  6. Tác động qua lại giữa routing & forwarding giải thuật routing bảng forwarding cục bộ giá trị header đường ra 0100 3 0101 2 0111 2 1001 1 giá trị đang đến trong header của gĩi 0111 1 3 2 6
  7. Thiết lập kết nối  chức năng quan trọng thứ 3 của một số kiến trúc mạng:  ATM, frame relay, X.25  trước khi các datagram chuyển đi, 2 host và các router trung gian thiết lập kết nối ảo  các router cũng liên quan  dịch vụ kết nối lớp network với lớp transport:  network: giữa 2 host (cĩ thể cũng chứa các router trung gian trong trường hợp kết nối ảo)  transport: giữa 2 tiến trình 7
  8. mơ hình dịch vụ tầng Network Hỏi: Mơ hình dịch vụ là gì (cho kênh truyền các datagram từ bên gửi đến bên nhận)? Ví dụ các dịch vụ cho các Ví dụ các dịch vụ cho 1 datagram riêng biệt: luồng các datagram:  giao nhận bảo đảm  giao nhận datagram theo ứ ự  giao nhận bảo đảm với độ th t trễ < 40 ms  bảo đảm băng thơng tối thiểu cho luồng  hạn chế các thay đổi trong khoảng trống giữa các gĩi 8
  9. mơ hình dịch vụ Network 9
  10. 4.2 Các mạng virtual circuit và datagram 10
  11. Kết nối lớp network và dịch vụ khơng kết nối  datagram network cung cấp dịch vụ khơng kết nối lớp network  kết nối ảo cung cấp dịch vụ kết nối lớp network  tương tự với các dịch vụ lớp transport, nhưng:  dịch vụ: host-to-host  khơng lựa chọn: network chỉ cung cấp 1 dịch vụ  hiện thực: bên trong phần lõi của network 11
  12. các mạch ảo “cách xử lý đường từ nguồn đến đích phải tương tự với mạch điện thoại”  hiệu quả  thiết lập cuộc gọi, chia nhỏ mỗi cuộc gọi trước khi dữ liệu cĩ thể truyền  mỗi gĩi mang nhận dạng kết nối ảo (khơng phải là địa chỉ đích)  mọi router trên đường từ nguồn đến đích giữ nguyên “trạng thái” qua mỗi kết nối  kết nối, các tài nguyên router (băng thơng, bộ đệm) cĩ thể được cấp phát cho kết nối ảo (các tài nguyên dành riêng = dịch vụ cĩ thể dự đốn trước) 12
  13. hiện thực kết nối ảo một kết nối ảo bao gồm: 1. đường từ nguồn đến đích 2. các số hiệu kết nối ảo, mỗi số dành cho mỗi kết nối dọc theo đường 3. các điểm đăng ký vào các bảng forwarding trong router dọc theo đường  gĩi thuộc về kết nối ảo mang số hiệu (khơng là địa chỉ đích)  số hiệu kết nối ảo cĩ thể thay đổi trên mỗi kết nối  số hiệu mới được cấp từ bảng forwarding 13
  14. ả B ng Forwarding số hiệu 12 22 32 1 3 2 bảng Forwarding trong số hiệu ế router gĩc tây-bắc: giao ti p giao tiếp vào số hiệu kết nối vào giao tiếp ra số hiệu kết nối ra 1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 Các Router giữ nguyên thơng tin trạng thái kết nối! 14
  15. các mạch ảo: các giao thức gửi tín hiệu  dùng để thiết lập, duy trì kết nối ảo  dùng trong ATM, frame-relay, X.25  khơng dùng trong Internet ngày nay application application transport 5. bắt đầu dịng dữ liệu 6. nhận dữ liệu transport network 4. cuộc gọi đã kết nối 3. chấp nhận cuộc gọi network data link 1. khởi tạo cuộc gọi 2. cuộc gọi đến data link physical physical 15
  16. các mạng Datagram (chuyển gĩi)  khơng thiết lập cuộc gọi tại lớp network  các router: khơng cĩ trạng thái về các kết nối end-to- end  khơng cĩ khái niệm mức network của “kết nối”  vận chuyển các gĩi dùng địa chỉ host đích  các gĩi giữa cùng cặp nguồn-đích cĩ thể cĩ các đường đi khác nhau application application transport transport network 1. gửi dữ liệu network data link 2. nhận dữ liệu data link physical physical 16
  17. bảng Forwarding 4 tỷ điểm đăng nhập cĩ thể Vùng địa chỉ đích Giao tiếp kết nối 11001000 00010111 00010000 00000000 đến 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 đến 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 đến 2 11001000 00010111 00011111 11111111 khác 3 17
  18. So trùng prefix dài nhất So trùng prefix Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 ngược lại 3 Các ví dụ: DA: 11001000 00010111 00010110 10100001 Chọn interface nào? DA: 11001000 00010111 00011000 10101010 Chọn interface nào? 18
  19. Datagram hoặc virtual network: tại sao? Internet (datagram) ATM (kết nối ảo)  dữ liệu trao đổi giữa các máy  phát triển từ hệ thống điện tính thoại  dịch vụ “mềm dẻo”, khơng  đàm thoại của con người: định thì chặt chẽ  định thì chặt chẽ, yêu cầu  các hệ thống đầu cuối “thơng độ tin cậy minh” (các máy tính)  cần thiết cho các dịch vụ  cĩ thể thích ứng, điều khiển bảo đảm và sửa lỗi  các hệ thống đầu cuối “ít  “bên trong” mạng đơn giản, thơng minh” “bên ngồi” phức tạp  điện thoại  nhiều kiểu kết nối  “bên trong” mạng phức tạp  các đặc tính khác nhau  đồng nhất dịch vụ khĩ khăn 19
  20. Cơng nghệ mạng riêng ảo  Virtual Private Network (VPN)  Sử dụng cơng nghệ mạch ảo để cung cấp thêm một số chức năng nâng cao 20
  21. 4.3 Router 21
  22. Tổng quan kiến trúc Router 2 chức năng chính:  chạy các giao thức/giải thuật routing (RIP, OSPF, BGP)  đẩy các datagram từ kết nối vào đến kết nối ra 22
  23. Các chức năng cổng vào lớp Physical: tiếp nhận mức bit lớp Data link: switch khơng tập trung: ví dụ: Ethernet  Với một địa chỉ đích, tìm kiếm trên bảng xem chương 5 định tuyến để xác định cổng ra phù hợp  mục tiêu: hồn tất xử lý cổng vào dựa trên “tốc độ dịng”  sắp hàng: nếu datagrams đến nhanh hơn tốc độ forwarding bên trong switch fabric 23
  24. 3 kiểu switching fabrics 24
  25. Switching thơng qua bộ nhớ Các router thế hệ thứ nhất: các máy tính cổ điển với switch dưới sự điều khiển trực tiếp của CPU gĩi được sao chép vào trong bộ nhớ hệ thống tốc độ giới hạn bởi băng thơng bộ nhớ cổng bộ nhớ cổng vào ra Bus hệ thống 25
  26. Switching thơng qua bộ nhớ 26
  27. Switch thơng qua 1 Bus  datagram từ bộ nhớ cổng vào đến bộ nhớ cổng ra thơng qua một bus chia sẻ  tranh chấp bus: tốc độ switch giới hạn bởi băng thơng của bus  1 Gbps bus, Cisco 1900: tốc độ đủ cho truy xuất các router 27
  28. Switch thơng qua 1 Bus  Datagram từ Bộ nhớ cổng vào tới Bộ nhớ cổng ra qua buss dùng chung  tăng tốc độ chuyển mạch so với việc sử dụng bộ nhớ 28
  29. Switch thơng qua 1 mạng liên hợp  vượt qua các giới hạn của băng thơng bus  các mạng kết nối nội bộ khác lúc đầu được dùng để kết nối các bộ xử lý trong thiết bị cĩ nhiều bộ xử lý  thiết kế nâng cao: phân mảnh datagram vào các ơ độ dài cố định, chuyển các ơ thơng qua fabric.  Cisco 12000: chuyển với tốc độ hàng Gbps thơng qua kết nối nội bộ 29
  30. Các cổng ra  Đệm được yêu cầu khi các datagram đến từ fabric nhanh hơn tốc độ truyền  Scheduling discipline chọn giữa những datagram đã sắp hàng để truyền 30
  31. Sắp hàng tại cổng ra  đệm khi tốc độ đến thơng qua switch vượt quá tốc độ dịng ra  sắp hàng (trễ) và mất mát bởi vì bộ đệm tại cổng ra bị tràn! 31
  32. Sắp hàng tại cổng vào  Fabric chậm hơn sự phối hợp tại các cổng vào -> sắp hàng xảy ra tại các hàng vào  Tắc nghẽn Head-of-the-Line (HOL): datagram đã sắp hàng phía trước của hàng ngăn cản các datagram khác di chuyển lên trước  sắp hàng (trễ) và mất mát bởi vì bộ đệm tại cổng vào bị tràn! 32
  33. 4.4 IP - Internet Protocol 33
  34. Lớp Internet Network Các chức năng: lớp Transport: TCP, UDP ứ các giao thức Routing giao th c IP ướ ị ị ỉ •chọn đường •các quy c đ nh đ a ch ạ ứ •RIP, OSPF, BGP •d ng th c datagram lớp •các quy ước quản lý gĩi Network forwarding giao thức ICMP table •thơng báo lỗi •router “signaling” lớp Link lớp physical 34
  35. dạng thức IP datagram số hiệu phiên bản 32 bits ổ ộ giao thức IP t ng đ dài độ dài header head. type of datagram (bytes) ver length (bytes) len service dành cho việc “kiểu” của dữ liệu fragment 16-bit identifier flgs phân mảnh/ offset tổng hợp số hop cịn lại time to upper header tối đa live layer checksum (giảm xuống tại mỗi router) 32 bit địa chỉ IP nguồn giao thức lớp trên 32 bit địa chỉ IP đích ụ ườ tùy chọn (nếu cĩ) ví d : tr ng timestamp bao nhiêu overhead dữ liệu ghi nhận đường đi, với TCP? (độ dài thay đổi, danh sách các 20 bytes của TCP tùy theo đoạn TCP router hoặc UDP) để đi đến 20 bytes của IP = 40 bytes + overhead lớp app 35
  36. Phân mảnh & tổng hợp IP  các kết nối mạng cĩ MTU (max.transfer size) - frame mức kết nối lớn nhất cĩ thể.  các kiểu liên kết khác nhau, phân mảnh: các MTU khác nhau vào: 1 datagram lớn  các datagram lớn được chia ra: 3 datagram nhỏ hơn (phân mảnh) bên trong mạng  1 datagram thành một vài datagram tổng hợp  “tổng hợp” tại đích cuối cùng  các bit của IP header xác định, thứ tự liên quan các mảnh 36
  37. Phân mảnh & tổng hợp IP length ID fragflag offset Ví dụ =4000 =x =0 =0 4000 byte datagram 1 datagram lớn thành một vài datagram nhỏ hơn MTU = 1500 bytes length ID fragflag offset =1500 =x =1 =0 1480 bytes trong trường dữ liệu length ID fragflag offset =1500 =x =1 =1480 length ID fragflag offset =1040 =x =0 =2960 37
  38. Định địa chỉ IP: giới thiệu  địa chỉ IP: 32-bit nhận 223.1.1.1 dạng cho host, router 223.1.2.1 223.1.1.2 interface 223.1.1.4 223.1.2.9  ế ố ữ interface: k t n i gi a 223.1.2.2 host/router và kết nối 223.1.1.3 223.1.3.27 vật lý  router thường cĩ nhiều interface 223.1.3.1 223.1.3.2  host thường cĩ 1 interface  mỗi địa chỉ IP liên kết với mỗi interface 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1 38
  39. Các Subnet (mạng con)  địa chỉ IP: 223.1.1.1  phần subnet (các bit cĩ 223.1.2.1 223.1.1.2 ọ ố tr ng s cao) 223.1.1.4 223.1.2.9  phần host (các bit cĩ trọng số thấp) 223.1.2.2 223.1.1.3 223.1.3.27  subnet là gì? subnet  các interface thiết bị cĩ ầ ủ ị ỉ ph n subnet c a đ a ch 223.1.3.1 223.1.3.2 IP giống nhau  cĩ thể tìm thấy nhau khơng cần sự can thiệp của router mạng gồm 3 subnets 39
  40. Subnets 223.1.1.0/24 223.1.2.0/24 phương pháp  Để xác định subnet, tách mỗi interface từ host hoặc router của nĩ, tạo vùng các mạng độc lập. Mỗi vùng mạng độc lập được gọi là một subnet. 223.1.3.0/24 Subnet mask: /24 40
  41. Subnets 223.1.1.2 Bao nhiêu? 223.1.1.1 223.1.1.4 223.1.1.3 223.1.9.2 223.1.7.0 223.1.9.1 223.1.7.1 223.1.8.1 223.1.8.0 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 41
  42. Định địa chỉ IP: CIDR CIDR: Classless InterDomain Routing  phần subnet của địa chỉ cĩ độ dài bất kỳ  dạng thức địa chỉ: a.b.c.d/x, trong đĩ x là số bit trong phần subnet của địa chỉ phần phần subnet host 11001000 00010111 00010000 00000000 200.23.16.0/23 42
  43. các địa chỉ IP: làm sao lấy một? Hỏi: Làm sao host lấy được địa chỉ IP?  Cấu hình bằng tay  Wintel: control-panel->network->configuration->tcp/ip- >properties  UNIX: /etc/rc.config  DHCP: Dynamic Host Configuration Protocol: tự động lấy địa chỉ từ server  “plug-and-play” 43
  44. các địa chỉ IP: làm sao lấy một? Hỏi: Làm sao mạng lấy được phần subnet của địa chỉ IP? Đáp: lấy phần đã cấp phát của khơng gian địa chỉ IP do ISP cung cấp khối của ISP 11001000 00010111 00010000 00000000 200.23.16.0/20 Tổ chức 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Tổ chức 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Tổ chức 2 11001000 00010111 00010100 00000000 200.23.20.0/23 . . Tổ chức 7 11001000 00010111 00011110 00000000 200.23.30.0/23 44
  45. Định địa chỉ phân cấp: route tích hợp Định tuyến phân cấp cho phép quảng cáo các thơng tin định tuyến một cách hiệu quả: Tổ chức 0 200.23.16.0/23 Tổ chức 1 “gửi cho tơi bất cứ thứ gì 200.23.18.0/23 với các địa chỉ bắt đầu Tổ chức 2 200.23.16.0/20” . Fly-By-Night-ISP 200.23.20.0/23 . . . . Internet Tổ chức 7 . 200.23.30.0/23 “gửi cho tơi bất cứ thứ gì ISPs-R-Us với các địa chỉ bắt đầu 199.31.0.0/16” 45
  46. Định địa chỉ phân cấp: nhiều cách route xác định ISPs-R-Us cĩ nhiều cách route đến Tổ chức 1 Tổ chức 0 200.23.16.0/23 “gửi cho tơi bất cứ thứ gì với các địa chỉ bắt đầu Tổ chức 2 200.23.16.0/20” . Fly-By-Night-ISP 200.23.20.0/23 . . . . Internet Tổ chức 7 . 200.23.30.0/23 “gửi cho tơi bất cứ thứ gì ISPs-R-Us với các địa chỉ bắt đầu Tổ chức 1 199.31.0.0/16 hoặc 200.23.18.0/23” 200.23.18.0/23 46
  47. Định địa chỉ IP: Hỏi: Làm sao một ISP lấy được dải địa chỉ? Đáp: ICANN: Internet Corporation for Assigned Names and Numbers  cấp phát các địa chỉ  quản lý DNS  gán các tên miền, giải quyết tranh chấp 47
  48. NAT: Network Address Translation phần cịn lại của mạng cục bộ Internet (vd: mạng gia đình) 10.0.0/24 10.0.0.1 10.0.0.4 10.0.0.2 138.76.29.7 10.0.0.3 Tất cả datagram đi ra khỏi mạng cục các Datagram với nguồn hoặc đích bộ cĩ cùng một địa chỉ IP NAT là: trong mạng này cĩ địa chỉ 10.0.0/24 138.76.29.7, với các số hiệu cổng nguồn khác nhau 48
  49. NAT: Network Address Translation  Mạng cục bộ chỉ dùng 1 địa chỉ IP đối với bên ngồi:  khơng cần thiết dùng 1 vùng địa chỉ từ ISP: chỉ cần 1 cho tất cả các thiết bị  cĩ thể thay đổi địa chỉ các thiết bị trong mạng cục bộ mà khơng cần thơng báo với bên ngồi  cĩ thể thay đổi ISP mà khơng cần thay đổi địa chỉ các thiết bị trong mạng cục bộ  các thiết bị trong mạng cục bộ khơng nhìn thấy, khơng định địa chỉ rõ ràng từ bên ngồi (tăng cường bảo mật) 49
  50. NAT: Network Address Translation Hiện thực: NAT router phải:  các datagram đi ra: thay thế (địa chỉ IP và số hiệu cổng nguồn) mọi datagram đi ra bên ngồi bằng (địa chỉ NAT IP và số hiệu cổng nguồn mới) . . . các clients/servers ở xa sẽ dùng (địa chỉ NAT IP và số hiệu cổng nguồn mới) đĩ như địa chỉ đích  ghi nhớ (trong bảng chuyển đổi NAT) mọi cặp chuyển đổi (địa chỉ IP và số hiệu cổng nguồn) sang (địa chỉ NAT IP và số hiệu cổng nguồn mới)  các datagram đi đến: thay thế (địa chỉ NAT IP và số hiệu cổng nguồn mới) trong các trường đích của mọi datagram đến với giá trị tương ứng (địa chỉ IP và số hiệu cổng nguồn) trong bảng NAT 50
  51. NAT: Network Address Translation bảng chuyển đổi NAT 1: host 10.0.0.1 2: NAT router ị ỉ ị ỉ đ a ch phía WAN đ a ch phía LAN ử ế thay đổi địa chỉ từ g i datagram đ n 138.76.29.7, 5001 10.0.0.1, 3345 10.0.0.1, 3345 -> 128.119.40.186, 80 138.76.29.7, 5001, ậ ậ ả c p nh t b ng S: 10.0.0.1, 3345 D: 128.119.40.186, 80 10.0.0.1 1 S: 138.76.29.7, 5001 2 D: 128.119.40.186, 80 10.0.0.4 10.0.0.2 138.76.29.7 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4 S: 128.119.40.186, 80 3 D: 138.76.29.7, 5001 4: NAT router 10.0.0.3 ả ồ ế ị ỉ 3: ph n h i đ n đ a ch : thay đổi địa chỉ datagram đích 138.76.29.7, 5001 đích từ 138.76.29.7, 5001 -> 10.0.0.1, 3345 51
  52. NAT: Network Address Translation  trường số hiệu cổng 16-bit:  60,000 kết nối đồng thời chỉ với một địa chỉ phía LAN  NAT cịn cĩ thể gây ra tranh luận:  các router chỉ xử lý đến lớp 3  vi phạm thỏa thuận end-to-end  những người thiết kế ứng dụng phải tính đến khả năng NAT, vd: ứng dụng P2P  sự thiếu thốn địa chỉ IP sẽ được giải quyết khi dùng IPv6 52
  53. ICMP: Internet Control Message Protocol  được các host & router dùng để truyền thơng thơng tin lớp kiểu mã mơ tả network 0 0 echo reply (ping) 3 0 dest. network unreachable  ỗ Thơng báo l i: host, 3 1 dest host unreachable ứ network, port, giao th c 3 2 dest protocol unreachable ự khơng cĩ th c 3 3 dest port unreachable  phản hồi request/reply 3 6 dest network unknown (dùng bởi lệnh ping) 3 7 dest host unknown  lớp network “trên” IP: 4 0 source quench (congestion  các thơng điệp ICMP chứa control - not used) trong các IP datagram 8 0 echo request (ping) 9 0 route advertisement  thơng điệp ICMP: kiểu, mã 10 0 router discovery thêm với 8 byte đầu tiên của 11 0 TTL expired IP datagram gây ra lỗi 12 0 bad IP header 53
  54. Traceroute & ICMP  nguồn gửi một chuỗi các đoạn  Khi thơng điệp ICMP đến, UDP đến đích nguồn tính tốn RTT  đầu tiên cĩ TTL =1  Traceroute thực hiện cơng  thứ hai cĩ TTL=2, tương tự. việc này 3 lần  khơng giống số port tiêu chuẩn dừng  khi datagram thứ n đến  đoạn UDP đến lần lượt tại router n: host đích  Router hủy datagram  đích trả về gĩi ICMP “host  và gửi đến nguồn một ICMP khơng cĩ thực” (kiểu 3, mã 3) message (kiểu 11, mã 0)  Khi nguồn cĩ ICMP này ->  ệ ứ ủ ị thơng đi p ch a tên c a đ a dừng. chỉ router& IP 54
  55. IPv6  động lực thúc đẩy ban đầu: khơng gian địa chỉ 32-bit sớm được cấp phát cạn kiệt.  động lực bổ sung:  dạng thức header giúp tăng tốc xử lý/forwarding  header thay đổi tạo điều kiện thuận lợi cho QoS dạng thức IPv6 datagram:  40 byte header, độ dài cố định  khơng cho phép phân mảnh 55
  56. IPv6 Header (tt) độ ưu tiên: xác định độ ưu tiên của các datagram trong luồng nhãn luồng: xác định các datagram trong cùng “luồng” (khái niệm “luồng” khơng được rõ ràng). header kế tiếp: xác định giao thức lớp trên cho dữ liệu 56
  57. Những thay đổi khác nữa so với IPv4  Checksum: bỏ hết, nhằm giảm thời gian xử lý tại hop  Options: cho phép, nhưng nằm ngồi header, chỉ thị bởi trường “Next Header”  ICMPv6: phiên bản mới của ICMP  các kiểu thơng điệp bổ sung, vd “Packet Too Big”  các chức năng quản lý nhĩm multicast 57
  58. Chuyển từ IPv4 sang IPv6  khơng phải tất cả router đều cĩ thể nâng cấp đồng thời  mạng cĩ các router dùng cả IPv4 và IPv6 hoạt động thế nào? 58
  59. Tunneling A B E F cách nhìn logic: tunnel IPv6 IPv6 IPv6 IPv6 A B E F cách nhìn thực: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 59
  60. Tunneling A B E F cách nhìn logic: tunnel IPv6 IPv6 IPv6 IPv6 A B C D E F cách nhìn thực: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Flow: X Src:B Src:B Flow: X Src: A Dest: E Dest: E Src: A Dest: F Dest: F Flow: X Flow: X Src: A Src: A data Dest: F Dest: F data data data A-to-B: E-to-F: B-to-C: B-to-C: IPv6 IPv6 IPv6 inside IPv6 inside IPv4 IPv4 60
  61. 4.5 Các giải thuật Routing Lớp Network 61 61
  62. Tác động lẫn nhau giữa routing, forwarding giải thuật routing bảng forwarding cục bộ giá trịheader l.kết ra 0100 3 0101 2 0111 2 1001 1 giá trị trong header của gĩi đến 0111 1 3 2 62
  63. Mơ hình đồ thị 5 v 3 w 2 5 u 2 1 z 3 1 x y 2 đồ thị: G = (N,E) 1 N = tập các routers = { u, v, w, x, y, z } E = tập các kết nối ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Ghi chú: Mơ hình đồ thị cũng dùng được trong những ngữ cảnh khác Ví dụ: P2P, trong đĩ N là tập các điểm và E là tập các kết nối TCP 63
  64. Mơ hình đồ thị: các chi phí 5 • c(x,x’) = chi phí kết nối (x,x’) v 3 w - ví dụ: c(w,z) = 5 2 5 u 2 1 z 3 •chi phí cĩ thể luơn luơn là 1, hoặc 1 ngược lại liên quan đến băng thơng, x y 2 1 hay liên quan đến tắc nghẽn chi phí của đường (x1, x2, x3, , xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) Hỏi: chi phí thấp nhất trên đường từ u đến z ? giải thuật Routing: giải thuật tìm đường cĩ chi phí thấp nhất 64
  65. phân lớp giải thuật Routing thơng tin tồn cục hoặc Tĩnh hay động? khơng tập trung tồn cục: Tĩnh:  tất cả router cĩ tồn bộ thơng  việc tìm đường đi thay tin về chi phí kết nối, cấu trúc đổi chậm chạp theo thời ạ m ng gian  Thuật tốn “link state” Phân tán: Động:  biết các kết nối vật lý đến các  việc tìm đường đi thay điểm lân cận và chi phí của nĩ đổi rất nhanh  lặp lại quá trình tính tốn,  ậ ậ trao đổi thơng tin với các điểm c p nh t theo chu kỳ lân cận  phản ứng với những thay  Thuật tốn “distance vector” đổi chi phí kết nối 65
  66. 1 giải thuật Routing “Link state” Sử dụng giải thuật Dijkstra Ký hiệu:  biết chi phí kết nối, cấu trúc  c(x,y): chi phí kết nối từ nút mạng của tất cả các nút x đến y; = ∞ nếu khơng kết  tất cả các nút cĩ thơng nối trực tiếp đến điểm lân cận tin giống nhau  D(v): giá trị chi phí hiện tại  tính tốn đường đi chi phí của đường từ nguồn đến đích thấp nhất từ 1 nút (nguồn) v đến tất cả các nút khác  p(v): nút trước nằm trên  cho trước bảng đường từ nguồn đến nút v forwarding của nút đĩ  sau k lần duyệt, biết được  N': tập các nút mà đường đi đường đi chi phí thấp nhất chi phí thấp nhất đã được xác của k đích định 66
  67. giải thuật Dijkstra 1 Khởi tạo: 2 N' = {u} 3 for tất cả các nút v 4 if v kề với u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Lặp 9 tìm w khơng cĩ trong N' nhưng D(w) tối tiểu 10 thêm w vào N' 11 cập nhật lại D(v) cho tất cả v kề với w và khơng cĩ trong N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* chi phí mới đến v là chính nĩ hoặc chi phí đường đi ngắn nhất 14 cộng với chi phí từ w đến v */ 15 cho đến khi tất cả các nút nằm trong N' 67
  68. giải thuật Dijkstra: ví dụ Bước N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 4,y 5 uxyvwz 5 v 3 w 2 5 u 2 1 z 3 1 x y 2 1 68
  69. giải thuật Dijkstra: ví dụ (2) Cây kết quả đường đi ngắn nhất từ u: v w u z x y Bảng forwarding kết quả trong u: đích kết nối v (u,v) x (u,x) y (u,x) w (u,x) z (u,x) 69
  70. giải thuật Dijkstra: thảo luận Độ phức tạp giải thuật: n nút  mỗi lần duyệt: cần kiểm tra tất cả các nút w khơng cĩ trong N  n(n+1)/2 phép so sánh: O(n2)  cĩ nhiều cách hiện thực đạt hiệu quả hơn: O(nlogn) Tình huống cĩ thể dao động:  vd: chi phí kết nối = lượng lưu thơng A A 1 A A 1+e 2+e 0 0 2+e 2+e 0 D B D B D B D B 0 0 1+e 1 0 0 1+e 1 0 e C 0 C 0 1 C 1+e 0 C e 1 1 e tính tốn lại tính tốn lại tính tốn lại khởi tạo routing 70
  71. giải thuật Vector khoảng cách (distance vector) cơng thức Bellman-Ford định nghĩa dx(y) := chi phí thấp nhất của đường đi từ x đến y thì d (y) = min {c(x,v) + d (y) } x v v trong đĩ min được tính trên tất cả lân cận v của x 71
  72. Bellman-Ford: ví dụ 5 rõ ràng, dv(z) = 5, dx(z) = 3, dw(z) = 3 v 3 w 2 5 u cơng thức B-F cho: 2 1 z 3 1 d (z) = min { c(u,v) + d (z), x y 2 u v 1 c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 72
  73. giải thuật Vector khoảng cách  Dx(y) = ước lượng chi phí thấp nhất từ x đến y  nút x biết chi phí đến mỗi lân cận v: c(x,v)  Nút X duy trì vectơ khoảng cách Dx = [Dx(y): y є N ]  Nút X cũng duy trì các vectơ khoảng cách đến các lân cận của nĩ  với mỗi lân cận v, x duy trì Dv = [Dv(y): y є N ] 73
  74. giải thuật Vector khoảng cách (4) Ý tưởng chính:  mỗi nút định kỳ gửi ước lượng vector khoảng cách của nĩ đến các lân cận  khi 1 nút x nhận ước lượng Dv mới từ lân cận, nĩ cập nhật DV của mình dùng cơng thức B-F: Dx(y) ← minv{c(x,v) + Dv(y)} với mỗi nút y ∊ N Dưới những điều kiện tự nhiên, ước lượng Dx(y) hội tụ tới chi phí dx bé nhất thực sự dx(y) 74
  75. giải thuật Vector khoảng cách (5) lặp, khơng đồng bộ: mỗi lặp mỗi nút: cục bộ được gây ra bởi:  chi phí kết nối cục bộ thay ờ ổ đổi ch cho (thay đ i trong chi phí kết nối cục bộ hoặc thơng  Thơng báo cập nhật từ lân báo từ lân cận) cận phân tán: tính tốn lại các ước lượng  mỗi nút thơng báo đến các lân cận chỉ khi DV của nĩ thay ế ế ấ đổi n u DV đ n b t kỳ đích nào cĩ ổ  các lân cận sau đĩ thơng báo thay đ i, thơng báo cho các đến các lân cận của nĩ nếu lân cận cần thiết 75
  76. D (z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} x = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 bảng nút x chi phí đến chi phí đến x y z x y z x 0 2 7 x 0 2 3 y y ừ ừ ∞ ∞ ∞ 2 0 1 t t z ∞ ∞ ∞ z 7 1 0 bảng nút y chi phí đến x y z y 2 1 x ∞ ∞ ∞ x z ừ y t 2 0 1 7 z ∞ ∞ ∞ bảng nút z chi phí đến x y z x ∞ ∞ ∞ ừ t y ∞ ∞ ∞ z 7 1 0 thời gian 76
  77. D (z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} x = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} bảng nút x = min{2+1 , 7+0} = 3 chi phí đến chi phí đến chi phí đến x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 y y ừ ừ ∞ ∞ ∞ 2 0 1 y ừ t t 2 0 1 z z t ∞ ∞ ∞ 7 1 0 z 3 1 0 bảng nút y chi phí đến chi phí đến chi phí đến x y z x y z x y z y 2 1 x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z y y 2 0 1 ừ 2 0 1 y 7 ừ ừ t 2 0 1 t t z ∞ ∞ ∞ z 7 1 0 z 3 1 0 bảng nút z chi phí đến chi phí đến chi phí đến x y z x y z x y z x ∞ ∞ ∞ x 0 2 7 x 0 2 3 y y 2 0 1 ừ y ừ 2 0 1 ừ t ∞ ∞ ∞ t t z z z 7 1 0 3 1 0 3 1 0 thời gian 77
  78. Vector khoảng cách: các thay đổi chi phí kết nối các thay đổi chi phí kết nối: 1 nút kiểm tra thay đổi chi phí kết nối y 4 1 cập nhật thơng tin dẫn đường, tính tốn x z lại vector khoảng cách 50 nếu DV thay đổi, thơng báo các lân cận Tại thời điểm t0, y kiểm tra thay đổi chi phí kết nối, cập nhật DV và thơng báo đến các lân cận của nĩ “duyệt Tại thời điểm t1, z nhận được cập nhật từ y và cập nhật bảng của nĩ. tin tức Nĩ tính tốn chi phí thấp nhất mới đến x và gửi DV của nĩ đến các tốt lân cận nhanh” Tại thời điểm t2, y nhận được cập nhật của z và cập nhật bảng khoảng cách của nĩ. Các chi phí thấp nhất của y khơng thay đổi và hơn nữa y khơng gửi bất kỳ thơng báo nào đến z. 78
  79. So sánh các giải thuật LS và DV thơng báo phức tạp sự linh hoạt: điều gì xảy ra nếu router hoạt động sai chức  ớ ế ố LS: v i n nút, E k t n i, O(nE) năng? các thơng báo được gửi LS:  DV: chỉ trao đổi giữa các lân  nút cĩ thể thơng báo chi phí ậ ố ệ ơ c n nên s thơng đi p bé h n kết nối khơng chính xác Tốc độ hội tụ  mỗi nút chỉ tính tốn bảng riêng của nĩ  LS: giải thuật O(n2) yêu cầu DV: O(nE) thơng báo  nút cĩ thể thơng báo chi phí  cĩ thể cĩ các dao động đường đi khơng chính xác  DV: thời gian hội tụ thay đổi  bảng của nút cĩ thể được nút  cĩ thể do các quá trình lặp khác dùng tìm đường  lỗi lan truyền thơng qua mạng  vấn đề đếm vơ hạn 79
  80. Hết Chương 4 80