›

Giáo trình Mạng máy tính - Chương 4: Tầng Network

pdf 156 trang huongle 4510
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Mạng máy tính - Chương 4: Tầng Network", để 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:

  • pdfgiao_trinh_mang_may_tinh_chuong_4_tang_network.pdf

Nội dung text: Giáo trình Mạng máy tính - Chương 4: Tầng Network

  1. Chương 4 tầng Network A note on the use of these ppt slides: We’re making these slides freely available to all (faculty, students, readers). Computer They’re in PowerPoint form so you see the animations; and can add, modify, and delete slides (including this one) and slide content to suit your needs. Networking: A Top They obviously represent a lot of work on our part. In return for use, we only ask the following: Down Approach  If you use these slides (e.g., in a class) that you mention their source th (after all, we’d like people to use our book!) 6 edition  If you post any slides on a www site, that you note that they are adapted Jim Kurose, Keith Ross from (or perhaps identical to) our slides, and note our copyright of this Addison-Wesley material. March 2012 Thanks and enjoy! JFK/KWR All material copyright 1996-2012 J.F Kurose and K.W. Ross, All Rights Reserved Tầng Network 4-1
  2. Chương 4: tầng network Mục tiêu:  Hiểu các nguyên lý nền tảng của các dịnh vụ tầng network: . Các mô hình dịch vụ tầng network . forwarding so với routing . Cách mà router hoạt động . routing (chọn đường) . broadcast, multicast  Hiện thực trong Internet Tầng Network 4-2
  3. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network (Mạng mạch . distance vector ảo) và datagram . hierarchical routing network 4.6 routing trong Internet 4.3 Cấu trúc bên trong . RIP router . OSPF 4.4 IP: Internet Protocol . BGP . Định dạng datagram 4.7 broadcast và multicast . IPv4 addressing routing . ICMP . IPv6 Tầng Network 4-3
  4. Tầng Network application transport  Segment của tầng network data link transport từ host gửi đến physical network network data link data link network host nhận physical physical data link  physical network network Bên phía gửi sẽ đóng gói data link data link (encapsulate) các segment physical physical network network vào trong các datagram data link data link physical physical network  Bên phía nhận, chuyển các data link physical segment lên tầng transport application network transport data link network network  Các giao thức tầng network network physical data link data link data link physical physical trong mọi host, mọi router physical  router sẽ xem xét các trường của header trong tất cả các IP datagram đi qua nó Tầng Network 4-4
  5. 2 chức năng chính của tầng network  forwarding: di chuyển Tương tự: các packet từ đầu vào đến đầu ra thích hợp  routing: tiến trình lặp của router kế hoạch cho chuyến đi của packet từ  routing: xác định nguồn tới đích đường đi cho các gói từ nguồn đến đích.  forwarding: tiến trình vận chuyển qua 1 giao . Các thuật toán định điểm tuyến Tầng Network 4-5
  6. Tác động qua lại giữa routing và forwarding Thuật toán routing Thuật toán routing xác định đường đi của gói giữa 2 đầu cuối thông qua network local forwarding table header value output link Bảng forwarding xác định việc 0100 3 chuyển gói bên trong một router 0101 2 0111 2 1001 1 Giá trị trong header của packet đến 0111 1 3 2 Tầng Network 4-6
  7. Thiết lập kết nối  Chức năng qua trọng thứ 3 trong một số kiến trúc mạng: . ATM, frame relay, X.25  Trước khi các datagram di chuyển, 2 host đầu cuối và router trung gian (intervening routers) thiết lặp kết nối ảo . Các router cũng tham gia  Dịch vụ kết nối tầng transport so với tầng network : . network: giữa 2 hosts (cũng có thể bao gồm các router trung gian trong trường hợp kết nối ảo) . transport: giữa 2 tiến trình Tầng Network 4-7
  8. Mô hình dịch vụ Network Hỏi: mô hình dịch vụ nào cho cho 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 Ví dụ các dịch vụ cho các datagram riêng 1 luồn các biệt: datagram:  Giao nhận bảo đảm  Giao nhận datagram  Giao nhận bảo đảm với theo thứ tự độ trễ < 40ms  Băng thông được bảo đảm tối thiểu cho luồng  Hạn chế các thay đổi trong khoảng trống giữa các packet Tầng Network 4-8
  9. Các mô hình dịch vụ tầng Network: Bảo đảm? Kiến trúc Mô hình Phản hồi Network dịch vụ Băng thông Mất Thứ tự Định thì tắt nghẽn Internet best effort không không không không no (inferred via loss) ATM CBR Tốc độ có có có Không không đổi tắt nghẽn ATM VBR Tốc độ có có có Không bảo đảm tắt nghẽn ATM ABR Tốc độ no có không có bảo đảm ATM UBR không no có không không Tầng Network 4-9
  10. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network (Mạng mạch . distance vector ảo) và datagram . hierarchical routing network 4.6 routing trong Internet 4.3 Cấu trúc bên trong . RIP router . OSPF 4.4 IP: Internet Protocol . BGP . Định dạng datagram 4.7 broadcast và multicast . IPv4 addressing routing . ICMP . IPv6 Tầng Network 4-10
  11. Dịch vụ connection (hướng kết nối) và connection-less (phi kết nối)  Mạng datagram cung cấp dịch vụ connectionless tại tầng network  Mạng mạch ảo (virtual-circuit network) cung cấp dich vụ connection tại tầng network  Tương tự như các dịch vụ kết nối định hướng và không định hướng của tầng transport, nhưng: . Dịch vụ: từ host này đến host kiaost-to- host . Không lựa chọn: network chỉ cung cấp 1 dịch vụ . Thực hiện: trong mạng lõi Tầng Network 4-11
  12. Các mạch ảo (Virtual circuits) “đường đi từ nguồi tới đích tương tự như mạng điện thoại (telephone circuit)” . Hiệu quả . Các hoạt động của mạng dọc theo đường đi từ nguồn tới đích  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 packet mang định dạng của kết nối ảo (VC identifier) (không phải là địa chỉ của host đích)  Mỗi router trên đường đi từ nguồn tới đích duy trì trạng thái cho mỗi kết nối mà gói đi qua.  Đường link, các tài nguyên router (băng thông, bộ nhớ đẹ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ự đoán trước) Tầng Network 4-12
  13. Sự thực hiện kết nối ảo (VC) Một kết nối ảo bao gồm: 1. Đường đi (path) từ nguồn tới đích 2. Số hiệu kết nối ảo (VC numbers), một số cho một kết nối dọc theo đường đi 3. Các mục trong các bảng forwarding ở trong các router dọc theo đường đi  packet thuộc về kết nối ảo mang số hiệu (chứ không phải là điểm đến)  Số hiệu của kết nối bảo có thể được thay đổi trên mỗi kết nối. . Số hiệu mới của kết nối ảo được cấp phát từ bảng forwarding Tầng Network 4-13
  14. Bảng forwarding của kết nối ảo 12 22 32 1 3 2 VC number interface Bảng forwarding trong routernumber ở góc trái trên cùng: số hiệu của số hiệu của Cổng vào kết nối ảo vào Cổng ra kết nối ảo ra 1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 Các router kết nối ảo duy trì thông tin trạng thái kết nối! Tầng Network 4-14
  15. Các mạch ảo: các giao thức gửi tín hiệu  Được dùng để thiết lập, duy trì kết nối ảo  Được dùng trong ATM, frame-relay, X.25  Không được sử dụng trong Internet ngày nay application application 6. Nhận dữ liệu transport 5. Bắt đầu dòng dữ liệu transport network 4. Cuộc gọi được 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 Tầng Network 4-15
  16. Mạng Datagram  Không thiết lập cuộc gọi tại tầng network  Các router: không có trạng thái về các kết nối giữa 2 điểm cuối . Không có khái niệm về mức network của “kết nối”  Các packet được chuyển dùng địa chỉ của host đích application application transport transport network 1. Gởi các datagram 2. Nhận datagram network data link data link physical physical Tầng Network 4-16
  17. Bảng Datagram forwarding 4 tỉ địa chỉ IP, vì liệt Thuật toán routing kê ra 1 dãy các địa chỉ hơn là liệt kê ra từng ị ỉ ụ ổ local forwarding table đ a ch (các m c t ng dest address output link hợp) address-range 1 3 address-range 2 2 address-range 3 2 address-range 4 1 Địa chỉ IP đích trong header của packet đến 1 3 2 Tầng Network 4-17
  18. Bảng Datagram forwarding Dãy địa chỉ đích Link Interface 11001000 00010111 00010000 00000000 đến 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 1 đến 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 2 đến 11001000 00010111 00011111 11111111 3 khác Q: nhưng cái gì sẽ xảy ra nếu các dãy địa chỉ này không được chia hợp lý? Tầng Network 4-18
  19. So trùng prefix dài nhất So trùng prefix dài nhất Khi tìm kiếm 1 mục trong bảng forwarding table cho địa chỉ đích, dùng prefix dài nhất của địa chỉ cái mà trùng với địa chỉ đích. Dãy địa chỉ đích Link interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 2 11001000 00010111 00011 3 otherwise Ví dụ: DA: 11001000 00010111 00010110 10100001 Interface nào? DA: 11001000 00010111 00011000 10101010 Interface nào? Tầng Network 4-19
  20. Mạng datagram hoặc mạch ảo: tại sao? Internet (datagram) ATM (mạch ảo)  Dữ liệu trao đổi giữa các  Được phát triển từ hệ máy tính thống điện thoại . Dịch vụ “mềm dẻo, không  Đàm thoại của con định thì chặt chẽ. người: . Định thì chặt chẽ, yêu  Nhiều kiểu link cầu về độ tin cậy . Các đặc tính khác nhau . Cần cho các dịch vụ bảo . Khó đồng nhất dịch vụ đảm  ệ ố ầ ố  Các hệ thống đầu cuối Các h th ng đ u cu i “thông minh” (các máy “ít thông minh” . Điện thoại tính) . Bên trong mạng phức . Có thể thích ứng, điều tạp khiển và sửa lỗi . Mạng bên trong đơn giản, phức tạp tại “mạng bên ngoài” Tầng Network 4-20
  21. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network (mạng mạch . distance vector ảo) và datagram . hierarchical routing network 4.6 routing trong Internet 4.3 Cấu trúc bên trong . RIP router . OSPF 4.4 IP: Internet Protocol . BGP . Định dạng datagram 4.7 broadcast và multicast . IPv4 addressing routing . ICMP . IPv6 Tầng Network 4-21
  22. Tổng quan kiến trúc Router 2 chức năng chính của router:  Chạy các giao thức/thuật toán routing (RIP, OSPF, BGP)  Chuyển tiếp các datagram từ đường link vào tới đường link ra forwarding tables computed, routing pushed to input ports processor routing, management control plane (software) forwarding data plane (hardware) high-seed switching fabric router input ports router output ports Tầng Network 4-22
  23. Các chức năng của cổng Input lookup, link forwarding line layer switch termination protocol fabric (receive) queueing Tầng physical : Tiếp nhận mức bit decentralized switching: Tầng data link:  ớ ủ ế ướ Như là Ethernet V i đích c a datagram bi t tr c., tìm ổ ằ Xem chương 5 output port (c ng ra) b ng cách dùng bảng forwarding trong bộ nhớ của input port (cổng vào) (“match plus action”)  Mục tiêu: hoàn tất xử lý input port tại “tốc độ dòng” (‘line speed’)  Xếp hàng: nếu datagram đến nhanh hơn tốc độ chuyển tiếp bên trong switch Tầng Network 4-23
  24. Switching fabrics  Truyền packet từ bộ nhớ đềm đầu vào đến bộ nhớ đệm đầu ra thích hợp  Tốc độ switching: tốc độ mà các packet có thể được truyền từ đầu vào (inputs) đến đầu ra (outputs) . Thường được đo như nhiều tốc độ dòng của đầu vào/đầu ra . N inputs: switching rate N times line rate desirable  3 kiểu switching fabrics memory memory bus crossbar Tầng Network 4-24
  25. Switching thông qua bộ nhớ (memory) Các router thế hệ đầu tiên:  Các máy tính cổ điển với switching dưới sự điều khiển của CPU  packet được sao chép đến bộ nhớ của hệ thống  Tốc độ bị giới hạn bởi băng thông của bộ nhớ (2 bus qua mỗi datagram) input output port memory port (như (như Ethernet) Ethernet) Bus hệ thống Tầng Network 4-25
  26. Switching thông qua 1 bus  datagram từ bộ nhớ của port vào đến bộ nhớ của port ra thông qua một bus được chia sẽ  Sự tranh chấp bus: tốc độ switching bị giới hạ bởi băng thông của bus bus  32 Gbps bus, Cisco 5600: tốc độ đủ cho truy cập và các enterprise router Tầng Network 4-26
  27. Switching thông qua interconnection network  Vượt qua các giới hạn của băng thông bus  Đa mạng, crossbar, các mạng kết nối nội bộ khác lúc đầu được phát triển để kết nối các bộ vi xử lý trong bộ đa xử lý  ế ế ượ Thi t k đ c nâng cao: phân crossbar mảnh datagram vào các ô có độ dài cố định, chuyển các ô thông qua fabric.  Cisco 12000: chuyển 60 Gbps thông qua interconnection network Tầng Network 4-27
  28. Các cổng ra (Output) datagram switch buffer link fabric layer line protocol termination (send) queueing  Đệm (buffering) được yêu cầu khi các datagram đến từ fabric nhanh hơn tốc độ truyền  scheduling discipline chọn trong số các datagram xếp hàng để truyền Tầng Network 4-28
  29. Sắp hàng tại cổng ra switch switch fabric fabric at t, các packet nhiều hơn one packet time later từ đầu vào đến đầu ra  Đệm khi tốc độ đến qua switch vượt quá tốc độ dòng ra (output line)  Sắp hàng (trễ) và mất gói vì bộ nhớ đệm tại cổng ra bị tràn (overflow)! Tầng Network 4-29
  30. Bao nhiêu đệm?  RFC 3439 quy tắc ngón tay cái: đệm trung bình bằng với thời gian RTT “điển hình” (250 msec) nhân với dung lượng đường link C . Ví dụ C = 10 Gpbs link: 2.5 Gbit buffer  Khuyến nghị gần đây: với N luồng, đệm bằng với RTT . C N Tầng Network 4-30
  31. Sắp hàng tại cổng vào  fabric chậm hơn sự phối hợp của các cổng vào -> sắp hàng có thể xảy ra tại các hàng vào . Sắp hàng chậm trễ vào mất gói do tràn bộ đệm đầu vào!  Head-of-the-Line (HOL) blocking: datagram được sắp hàng tại phía trước hàng đợi ngăn cản các datagram khác trong hàng đợi di chuyển lên trước switch switch fabric fabric Sự cạnh tranh tại cổng ra: one packet time Chỉ có một datagram màu đỏ later: packet màu có thể được truyền. xanh lá trải qua packet màu đỏ thấp hơn bị HOL blocking chặn lại Tầng Network 4-31
  32. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-32
  33. Tầng Internet network Các chức năng tầng network của host và router: transport layer: TCP, UDP Các giao thức routing Giao thức IP • chọn đường đi • các quy ước định địa chỉ • RIP, OSPF, BGP • định dạng datagram Tầng • các quy ước quản lý gói network forwarding ứ table Giao th c ICMP •Thông báo lỗi • “tín hiệu” router Tầng link Tầng physical Tầng Network 4-33
  34. Định dạng IP datagram Số hiệu phiên bản giao thức IP 32 bits Tổng độ dài Độ dài header head. type of datagram(byte) ver length (bytes) len service Dành cho “kiểu” 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 (giảm xuống live layer checksum tại mỗi router) 32 bit source IP address Giao thức lớp trên 32 bit destination IP address để đưa payload đến Tùy chọn (nếu có) Ví dụ: trường timestamp ghi lại how much overhead? Dữ liệu đường đi, danh (độ dài thay đổi,  20 bytes of TCP các router đi đến thông thường là một  20 bytes of IP segment TCP  = 40 bytes + app layer overhead hoặc UDP) Tầng Network 4-34
  35. Phân mảnh và tổng hợp IP  Các đường link mạng có MTU (max.transfer size) – frame lớn nhất có thể ở mức kết nối . Các kiểu đường link khác Phân mảnh: nhau, các MTU khác nhau vào: 1 datagram lớn ra: 3 datagram nhỏ hơn  IP datagram lớn được chia (“fragmented”) bên trong mạng . 1 datagram thành 1 vài reassembly datagram . “tổng hợp” chỉ được thực hiện ở đích cuối cùng . Các bit của IP header được sử dụng để xác định, sắp đặt các fragment liên quan Tầng Network 4-35
  36. Phân mảnh và tổng hợp IP length ID fragflag offset Ví dụ: =4000 =x =0 =0  4000 byte datagram 1 datagram lớn thành vài datagram nhỏ hơn  MTU = 1500 bytes 1480 bytes length ID fragflag offset trong trường dữ liệu =1500 =x =1 =0 offset = length ID fragflag offset 1480/8 =1500 =x =1 =185 length ID fragflag offset =1040 =x =0 =370 Tầng Network 4-36
  37. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-37
  38. Định địa chỉ IP: giới thiệu 223.1.1.1  Địa chỉ IP: 32-bit nhận dạng cho host, 223.1.2.1 router interface 223.1.1.2 223.1.1.4 223.1.2.9  interface: kết nối giữa host/router và 223.1.3.27 223.1.1.3 đường link vật lý 223.1.2.2 . Router thường có nhiều interface . host thường có 1 hoặc 2 interface (ví dụ wired 223.1.3.1 223.1.3.2 Ethernet, wireless 802.11)  Mỗi địa chỉ IP được 223.1.1.1 = 11011111 00000001 00000001 00000001 liên kết với mỗi interface 223 1 1 1 Tầng Network 4-38
  39. Định địa chỉ IP: giới thiệu 223.1.1.1 Hỏi: các interface thật sự được kết nối 223.1.2.1 223.1.1.2 như thế nào? 223.1.1.4 223.1.2.9 đáp: sẽ tìm hiểu ươ 223.1.3.27 trong ch ng 5, 6. 223.1.1.3 223.1.2.2 Đáp: các interface Ethernet có dây được kết nối bởi các switch Ethernet 223.1.3.1 223.1.3.2 Bây giờ: không cần lo lắng về cách mà 1 interface được kết nối với một interface khác Đáp: interface WiFi không dây được (không có router trung gian)) kết nối thông qua WiFi base station Tầng Network 4-39
  40. Các Subnet (mạng con) Đại chỉ IP: 223.1.1.1 .Phần subnet – các bit có trọng số cao 223.1.1.2 223.1.2.1 .Phần host – các bit 223.1.1.4 223.1.2.9 có trọng số thấp 223.1.2.2 223.1.3.27 subnet là gì? 223.1.1.3 .Các interface của subnet thiết bị có phần subnet của địa chỉ IP 223.1.3.1 223.1.3.2 giống nhau .Có thể giao tiếp vật lý với nhau mà không Mạng gồm 3 subnet cần router trung gian can thiệp Tầng Network 4-40
  41. Các mạng con (subnet) 223.1.1.0/24 223.1.2.0/24 Phương pháp 223.1.1.1  Để xác định các 223.1.1.2 223.1.2.1 subnet, tách mỗi 223.1.1.4 223.1.2.9 interface từ host 223.1.2.2 hoặc router của nó, 223.1.1.3 223.1.3.27 tạo vùng các mạng subnet độc lập 223.1.3.2  Mỗi mạng độc lập 223.1.3.1 được gọi là một subnet 223.1.3.0/24 subnet mask: /24 Tầng Network 4-41
  42. Subnets 223.1.1.2 Có 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 Tầng Network 4-42
  43. Định địa chỉ IP: CIDR CIDR: Classless InterDomain Routing . Phần subnet của địa chỉ có độ dài bất kỳ . Định dạng địa chỉ: a.b.c.d/x, trong đó x là số các bits trong phần subnet của địa chỉ Phần Phần subnet host 11001000 00010111 00010000 00000000 200.23.16.0/23 Tầng Network 4-43
  44. Địa chỉ IP: làm sao để lấy một địa chỉ? Hỏi: làm thế nào một host lấy được địa chỉ IP?  Mã hóa cứng bởi người quản trị hệ thống trong 1 file . Windows: control-panel->network->configuration- >tcp/ip->properties . UNIX: /etc/rc.config  DHCP: Dynamic Host Configuration Protocol: tự động lấy địa chỉ IP từ server . “plug-and-play” Tầng Network 4-44
  45. 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 trong mạng khi host đó tham gia vào mạng . Có thể gia hạn địa chỉ IP mà host đó vừa được cấp . Cho phép tái sử dụng các địa chỉ IP (chỉ giữ địa chỉ trong khi được kết nối/”on”) . Hỗ trợ cho người dùng di động muốn tham gia vào mạng (trong thời gian ngắn) Tổng quan DHCP : . host quảng bá (broadcasts) thông điệp “DHCP discover” [tùy chọn] . DHCP server đáp ứng bằng thông điệp “DHCP offer” [tùy chọn] . host yêu cầu địa chỉ IP: “DHCP request” msg . DHCP server gởi địa chỉ: “DHCP ack” msg Tầng Network 4-45
  46. Ngữ cảnh DHCP client-server DHCP 223.1.1.0/24 server 223.1.1.1 223.1.2.1 223.1.1.2 Máy DHCP client 223.1.1.4 223.1.2.9 vừa tham gia vào mạng cần địa chỉ 223.1.2.2 trong mạng này 223.1.1.3 223.1.3.27 223.1.2.0/24 223.1.3.1 223.1.3.2 223.1.3.0/24 Tầng Network 4-46
  47. Ngữ cảnh DHCP client-server DHCP server: 223.1.2.5 DHCP discover arriving 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 lifetime: 3600 secs 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 Tầng Network 4-47
  48. DHCP: nhiều thông tin DHCP không chỉ trả về địa chỉ IP được chỉ định trên subnet, mà nó còn có thể trả về nhiều thông tin như sau: . Địa chỉ của router first-hop của client . Tên và địa chỉ IP của DNS sever . network mask (cho biết phần của mạng so với phần phần host của địa chỉ IP) Tầng Network 4-48
  49. DHCP: ví dụ  laptop tham gia vào DHCP DHCP mạng cần địa chỉ IP DHCP UDP ủ ị ỉ ủ DHCP IP c a nó, đ a ch c a DHCP Eth router first-hop, địa Phy chỉ của : dùng DHCP DHCP  DHCP request được đóng gói trong UDP, được đóng DHCP DHCP 168.1.1.1 gói trong IP, được đóng DHCP UDP gói trong 802.1 Ethernet DHCP IP  Ethernet frame broadcast DHCP Eth router với DHCP Phy server được tích hợp (dest: FFFFFFFFFFFF) trên vào trong router LAN, được nhận tại router đang chạy DHCP server  Ethernet demuxed to IP demuxed, UDP demuxed to DHCP Tầng Network 4-49
  50. DHCP: ví dụ  DHCP DHCP DHCP server lập địa chỉ DHCP UDP IP của client chứa DHCP DHCP IP ACK, địa chỉ IP của DHCP Eth router first-hop cho Phy client, tên và địa chỉ IP của DNS server  Đóng gói của DHCP DHCP DHCP DHCP UDP server, frame được DHCP IP chuyển cho client, tách DHCP Eth Router với DHCP DHCP tại client Phy DHCP server được tích hơp vào router  Bây giờ, client biết địa chỉ IP của nó, tên và địa chỉ IP của DSN server, địa chỉ IP của router first-hop của nó Tầng Network 4-50
  51. DHCP: Wireshark Message type: Boot Reply (2) Hardware type: Ethernet Trả lời Hardware address length: 6 output (home LAN) Hops: 0 Transaction ID: 0x6b3a11b7 Seconds elapsed: 0 Message type: Boot Request (1) Bootp flags: 0x0000 (Unicast) Hardware type: Ethernet Client IP address: 192.168.1.101 (192.168.1.101) Hardware address length: 6 Your (client) IP address: 0.0.0.0 (0.0.0.0) Hops: 0 Yêu cầu Next server IP address: 192.168.1.1 (192.168.1.1) Transaction ID: 0x6b3a11b7 Relay agent IP address: 0.0.0.0 (0.0.0.0) Seconds elapsed: 0 Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Bootp flags: 0x0000 (Unicast) Server host name not given Client IP address: 0.0.0.0 (0.0.0.0) Boot file name not given Your (client) IP address: 0.0.0.0 (0.0.0.0) Magic cookie: (OK) Next server IP address: 0.0.0.0 (0.0.0.0) Option: (t=53,l=1) DHCP Message Type = DHCP ACK Relay agent IP address: 0.0.0.0 (0.0.0.0) Option: (t=54,l=4) Server Identifier = 192.168.1.1 Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Option: (t=1,l=4) Subnet Mask = 255.255.255.0 Server host name not given Option: (t=3,l=4) Router = 192.168.1.1 Boot file name not given Option: (6) Domain Name Server Magic cookie: (OK) Length: 12; Value: 445747E2445749F244574092; Option: (t=53,l=1) DHCP Message Type = DHCP Request IP Address: 68.87.71.226; Option: (61) Client identifier IP Address: 68.87.73.242; Length: 7; Value: 010016D323688A; IP Address: 68.87.64.146 Hardware type: Ethernet Option: (t=15,l=20) Domain Name = "hsd1.ma.comcast.net." Client MAC address: Wistron_23:68:8a (00:16:d3:23:68:8a) Option: (t=50,l=4) Requested IP Address = 192.168.1.101 Option: (t=12,l=5) Host Name = "nomad" Option: (55) Parameter Request List Length: 11; Value: 010F03062C2E2F1F21F92B 1 = Subnet Mask; 15 = Domain Name 3 = Router; 6 = Domain Name Server 44 = NetBIOS over TCP/IP Name Server Tầng Network 4-51
  52. Địa chỉ IP: làm sao để lấy được 1 địa chỉ IP? Hỏi: làm sao mạng lấy được phần subnet của địa chỉ IP? Đáp: lấy phần đã được cấp phát của không gian địa chỉ IP do ISP cung cấp Dãy địa chỉ 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 Tầng Network 4-52
  53. Định địa chỉ phân cấp: route tích hợp Định địa chỉ phân cấp cho phép quảng cáo hiệu quả thông tin định tuyến Tổ chức 0 200.23.16.0/23 Tổ chức 1 “gởi cho tôi bất cứ thông tin gì 200.23.18.0/23 với các địa chỉ bắt đầu Tổ chức 2 200.23.16.0/20” . 200.23.20.0/23 . Fly-By-Night-ISP . . . Internet Tổ chức 7 . 200.23.30.0/23 “gởi cho tôi bất cứ thông ISPs-R-Us tin gì với các địa chỉ bắt đầu 199.31.0.0/16” Tầng Network 4-53
  54. Định địa chỉ phân cấp: các route cụ thể hơn ISPs-R-Us có 1 route cụ thể hơn tới tổ chức 1 Tổ chức 0 200.23.16.0/23 “gởi cho tôi bất cứ thông tin gì Với các địa chỉ bắt đầu Tổ chức 2 200.23.16.0/20” . 200.23.20.0/23 . Fly-By-Night-ISP . . . Internet Tổ chức 7 . 200.23.30.0/23 “gởi cho tôi bất cứ thông tin ISPs-R-Us gì với các địa chỉ bắt đầu Tổ chức 1 199.31.0.0/16 ặ ” 200.23.18.0/23 ho c 200.23.18.0/23 Tầng Network 4-54
  55. Định địa chỉ IP: the last word Q: làm cách nào mà một ISP lấy được khối địa chỉ? A: ICANN: Internet Corporation for Assigned Names and Numbers . Cấp phát địa chỉ . Quản lý DNS . Gán các tên miền, giải quyết tranh chấp Tầng Network 4-55
  56. NAT: network address translation Phần còn lại của Mạng cục bộ Internet (như là 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 Các datagram với nguồn hoặc đích khỏi mạng cục bộ có cùng trong mạng này có địa chỉ 10.0.0/24 một địa chỉ IP NAT là: cho nguồn, đích 138.76.29.7, (như thông thường) với các số hiệu cổng nguồn khác nhau Tầng Network 4-56
  57. NAT: network address translation Trình bày: mạng cục bộ chỉ dùng 1 địa chỉ IP đối với thế giới bên ngoài: . Không cần thiết dùng 1 vùng địa chỉ từ ISP: chỉ cần 1 địa chỉ IP cho tất cả các thiết bị . Có thể thay đổi các địa chỉ IP của các thiết bị trong mạng cục bộ mà không cần thông báo cho thế giới bên ngoài . Có thể thay đổi ISP mà không cần thay đổi địa chỉ IP của các thiết bị trong mạng nội bộ . Các thiết bị bên trong mạng cục bộ không nhìn thấy và không định địa chỉ rõ ràng từ bên ngoài (tăng cường bảo mật) Tầng Network 4-57
  58. NAT: network address translation thực hiện: NAT router phải: . Các datagram đi ra: thay thế (địa chỉ IP nguồn, số hiệu cổng nguồn) mọi datagram đi ra bên ngoài bằng (địa chỉ IP NAT, số hiệu port mới) . . . Các client/server ở xa sẽ dùng địa chỉ đó ( địa chỉ IP NAT, số hiệu port mối) như là địa chỉ đích . Ghi nhớ (trong bảng chuyển đổi NAT) mọi cặp chuyển đổi (địa chỉ IP nguồn, số hiệu port) sang (địa chỉ IP NAT, số hiệu port mới) . Datagram đi đến: thay thế(địa chỉ IP NAT, số hiệu port 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 Tầng Network 4-58
  59. NAT: network address translation Bảng chuyển đổi NAT 1: host 10.0.0.1 2: NAT router WAN side addr LAN side addr thay đổi địa chỉ nguồn gửi datagram tới từ 10.0.0.1, 3345 đến 138.76.29.7, 5001 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ỉ đích: thay đổi địa chỉ đích từ 138.76.29.7, 5001 138.76.29.7, 5001 tới 10.0.0.1, 3345 Tầng Network 4-59
  60. NAT: network address translation  Trường số hiệu port 16-bit: . 60,000 kết nối đồng thời với một địa chỉ phía LAN!  NAT gây ra tranh luận: . Các router chỉ nên xử lý đến tầng 3 . Vi phạm thỏa thuận end-to-end • Những nhà thiết kế ứng dụng phải tính đến khả năng của NAT, ví dụ ứng dụng P2P . Việc thiếu địa chỉ IP sẽ được giải quyết khi dùng IPv6 Tầng Network 4-60
  61. Vấn đề NAT traversal  Các client muốn kết nối tới server có địa chỉ 10.0.0.1 . ị ỉ ủ ở 10.0.0.1 Đ a ch 10.0.0.1 c a server là client trong mạng LAN (client không thể dùng nó như là địa chỉ IP ? đích) 10.0.0.4 . Chỉ có 1 địa chỉ có thể được nhìn thấy từ bên ngoài địa chỉ 138.76.29.7 NAT được NAT: 138.76.29.7 router  Giải pháp 1: cấu hình NAT tĩnh để chuyển các yêu cầu kết nối đến tại port được cho trước tới server . Ví dụ (123.76.29.7, port 2500) luôn luôn được chuyển tới 10.0.0.1 port 25000 Tầng Network 4-61
  62. Vấn đề NAT traversal  Giải pháp 2: Giao thức Universal Plug and Play (UPnP) Internet Gateway Device 10.0.0.1 ượ (IGD). Cho phép host đ c IGD NAT:  Học địa chỉ IP public (138.76.29.7)  ỡ ỏ NAT thêm/g b các port router mapping (thời gian thuê) Tầng Network 4-62
  63. Các vấn đề NAT traversal  Giải pháp 3: chuyển tiếp (relaying) (được sử dụng trong Skype) . Client được NAT thiết lập kết nối để chuyển tiếp . client bên ngoài kết nối để chuyển tiếp . Sự chuyển tiếp này bắc cầu các packet giữa các kết nối 2. Kết nối chuyển tiếp được 1. Kết nối 10.0.0.1 khởi tạo bởi chuyển tiếp được client khởi tạo tại host 3. Chuyển tiếp được NAT client được thiết lặp 138.76.29.7 NAT router Tầng Network 4-63
  64. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-64
  65. ICMP: internet control message protocol  Được sử dụng bởi các host và router để truyền Loại mã Mô tả thông thông tin tầng 0 0 echo reply (ping) network 3 0 dest. network unreachable . Thông báo: host, network, 3 1 dest host unreachable port, giao thức không có 3 2 dest protocol unreachable thực 3 3 dest port unreachable . Phản hồi request/reply 3 6 dest network unknown (được dùng bởi ping) 3 7 dest host unknown  Tầng network “trên” IP: 4 0 source quench (congestion control - not used) . Các thông điệp ICMP được mang trong các IP 8 0 echo request (ping) datagram 9 0 route advertisement 10 0 router discovery  Thông điệp ICMP: loại, mã 11 0 TTL expired cộng thêm 8 byte đầu 12 0 bad IP header tiên của IP datagram gây ra lỗi Tầng Network 4-65
  66. Traceroute và ICMP  Nguồn gửi một chuỗi các  Khi thông điệp ICMP segment UDP đến đích đến, nguồn ghi lại RTTs . Cái đầu tiên có TTL =1 . Cái thứ 2 có TTL=2, tương tự. . Không giống số port Tiêu chuẩn dừng:  Khi datagram thứ n đến  Segment UDP lần lượt router thứ n: đến tới host đích . router hủy datagram  Đích trả về thông điệp . Và gửi đến nguồn một thông ICMP “port không có điệp ICMP (loại 11, mã 0) thực”(loại 3, mã 3) . Thông điệp ICMP bao gồm  ồ ừ tên và địa chỉ IP của router Ngu n d ng 3 probes 3 probes 3 probes Tầng Network 4-66
  67. IPv6: Động lực  Độ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 khác: . Định dạng của header giúp tăng tốc xử lý/chuyển gói . header thay đổi để tạo điều kiện thuận lơi cho QoS Định dạng datagram IPv6 : . Header có độ dài cố định 40 byte . Không cho phép phân mảnh Tầng Network 4-67
  68. Định dạng datagram IPv6 Độ ưu tiên (priority): xác định độ ưu tiên của các datagram trong luồng Nhãn luồng (flow Label): xác định các datagram trong cùng “luồng”. (khái niệm “luồng” không được định nghĩa rõ ràng). Header kế tiếp (next header): xác định giao thức Tầng trên cho dữ liệu. ver pri flow label payload len next hdr hop limit source address (128 bits) destination address (128 bits) data 32 bits Tầng Network 4-68
  69. Những thay đổi khác so với IPv4  checksum: được bỏ toàn bộ để giảm thời gian xử lý tại mỗi hop  options: được cho phép, nhưng nằm ở ngoài header, được chỉ ra 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. Ví dụ “Packet Too Big” . Các chức năng quản lý nhóm multicast Tầng Network 4-69
  70. Chuyển từ IPv4 sang IPv6  Không phải tất cả router đều có thể được nâng cấp đồng thời . Không có “flag days” . Mạng sẽ hoạt động như thế nào với các router dùng cả IPv4 và IPv6?  tunneling: datagram IPv6 được mang như là payload trong datagram của IPv4 giữa các router IPv4 Các trường header IPv4 Các trường header IPv6 IPv4 payload Địa chỉ IPv4 nguồn và đích Địa chỉ IPv6 nguồn và đích UDP/TCP payload IPv6 datagram IPv4 datagram Tầng Network 4-70
  71. Tunneling A B IPv4 tunnel E F kết nối các router IPv6 Cách nhìn logic: IPv6 IPv6 IPv6 IPv6 A B C D E F Cách nhìn thực: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Tầng Network 4-71
  72. Tunneling A B IPv4 tunnel E F kết nối các router IPv6 Cách nhìn logic: 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-đến-B: E-đến-F: IPv6 B-đến-C: B-đến-C: IPv6 IPv6 bên trong IPv6 bên trong IPv4 IPv4 Tầng Network 4-72
  73. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-73
  74. Tác động lẫn nhau giữa routing và forwarding Thuật toán routing xác định đường đi qua Thuật toán routing mạng từ đầu cuối này đến đầu cuối khác Bảng forwarding xác định chuyển local forwarding table gói trong cục bộ của router này Địa chỉ đích output link address-range 1 3 address-range 2 2 address-range 3 2 address-range 4 1 Địa chỉ IP trong header của packet đến 1 3 2 Tầng Network 4-74
  75. 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 hợp các router = { u, v, w, x, y, z } E = tập hợ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 hữu ích trong các ngữ cảnh khác. Ví dụ, P2P, trong đó N is tập các peer và E là tập các kết nối TCP Tầng Network 4-75
  76. Mô hình đồ thị: Chi phí 5 c(x,x’) = chi phí kết nối (x,x’) e.g., c(w,z) = 5 v 3 w 2 5 u Chi phí có thể luôn luôn là 1, hoặc 2 1 z 3 ngược lại liên quan đến băng thông, 1 ặ ế ắ ẽ x y 2 ho c liên quan đ n t c ngh n 1 Chi phí đường đi (x1, x2, x3, , xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) Hỏi: Chi phí đường đi thấp nhất từ u tới z? Thuật toán routing: thuật toán tìm đường có chi phí thấp nhất Tầng Network 4-76
  77. Phân loại thuật toán Routing Q: thông tin toàn cục hay phân Q: tĩnh hay động? cấp (global or decentralized)? tĩnh: ụ Toàn c c:  Các route thay đổi  Tất cả các router có toàn bộ chậm theo thời gian thông tin về chi phí kết nối, Động: cấu trúc mạng  Các route thay đổi  Thuật toán “link state” nhanh Phân cấp: . Cập nhật theo chu  router biết các neighbor được kỳ kết nối vật lý với nó, và chi phí . Phản ứng với những kết nối đến neighbor đó thay đổi về chi phí  Lặp lại qua trình tính toán, kết nối trao đổi thông tin với các neighbor  Thuật toán “distance vector” Tầng Network 4-77
  78. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-78
  79. Thuật toán routing Link-State Thuật toán Dijkstra Ký hiệu:  Biết chi phí kết nối, cấu  c(x,y): chi phí kết nối trúc mạng của tất cả các từ node x đến y; = ∞ node nếu không kết nối trực . Được thực hiệu thông qua tiếp đến neighbor “link state broadcast”  D(v): giá trị chị phí . Tất cả các nodes có cùng hiện tại của đường đi từ thông tin với nhau nguồn tới đích v  Tính toán đường đi có chi  p(v): node trước nằm phí thấp nhất từ 1 node trên đường đi từ nguồn (‘nguồn’) đến tất cả các tới v node khác  N': tập các node mà . Cho trước bảng forwarding chi phí đường đi thấp của node đó nhất đã được xác định  Lặp lại: sau k lần lặp lại, biết được đường đi có chi phí thấp nhất của k đích Tầng Network 4-79
  80. Thuật toán Dijsktra 1 Khởi tạo: 2 N' = {u} 3 for tất cả các node v còn lại 4 if v kề với u (có cạnh nối với u) 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Lặp 9 Tìm w chưa có trong N' sao cho D(w) tối tiểu 10 Thêm w vào N' 11 Cập nhật D(v) với tất cả các node v kề với w và chưa 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 node nằm trong N' Tầng Network 4-80
  81. Thuật toán Dijkstra : ví dụ D(v) D(w) D(x) D(y) D(z) Bước N' p(v) p(w) p(x) p(y) p(z) 0 u 7,u 3,u 5,u ∞ ∞ 1 uw 6,w 5,u 11,w ∞ 2 uwx 6,w 11,w 14,x 3 uwxv 10,v 14,x 4 uwxvy 12,y 5 uwxvyz x 9 Ghi chú: 5 7  Xây dựng cây đường đi ngắn 4 nhất bằng cách lần theo các 8 predecessor node u 3 w y z  Các đường có chi phí bằng 2 nhau có thể tồn tại (có thể bị chia tùy tiện) 3 7 4 v Tầng Network 4-81
  82. Thuật toán 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 Tầng Network 4-82
  83. Thuật toán Dijkstra: ví dụ (2) Kết quả cây đường đi ngắn nhất từ u: v w u z x y Kết quả bảng forwarding trong u: Đích đến link v (u,v) x (u,x) y (u,x) w (u,x) z (u,x) Tầng Network 4-83
  84. Thuật toán Dijkstra, thảo luận Độ phức tạp của thuật toán: n nodes  Mỗi lần duyệt: cần kiểm tra tất cả các node, w, không có trong N  n(n+1)/2 phép so sánh: O(n2)  Có nhiều cách thực hiện hiệu quả hơn: O(nlogn) Có thể dao động:  Ví dụ: chi phí kết nối bằng với số lượng lưu thông được mang A 1 1+e A A A 2+e 0 0 2+e 2+e 0 D B D B D D 0 0 1+e 1 0 0 B 1+e 1 B 0 e 0 0 C C 0 1 C 1+e C 0 1 1 e Cho các chi phí, Cho các chi phí, Cho các chi phí, Khởi tạo Tìm định tuyến mới . Tìm định tuyết mới .Tìm định tuyết mới . Kết quả trong chi phí Kết quả trong chi Kết quả trong chi mới phí mới Tầng Networkphí mớ4i-84
  85. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-85
  86. Thuật toán Distance vector Công thức Bellman-Ford (dynamic programming) cho dx(y) := chi phí của đường đi có chi phí ít nhất từ x tới y thì d (y) = min {c(x,v) + d (y) } x v v Chi phí từ neighbor v tới đích y Chi phí tới neighbor v min được thực hiện trên tất cả các neighbor v của x Tầng Network 4-86
  87. 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 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 node đạt được tối thiểu là hop kế tiếp trong đường đi ngắn nhất, được sử dụng trong bảng forwarding Tầng Network 4-87
  88. Thuật toán Distance vector  Dx(y) = ước lượng chi phí thấp nhất từ x đến y . x duy trì distance vector Dx = [Dx(y): y є N ]  node x: . Biết chi phí đến mỗi neighbor v: c(x,v) . Duy trì distance vectors của các neighbor của nó . Cho mỗi duy trì neighbor v, x Dv = [Dv(y): y є N ] Tầng Network 4-88
  89. Thuật toán Distance vector Ý tưởng chính:  Mỗi node định kỳ gởi ước lượng distance vector của nó cho các neighbor  Khi x nhận ước lượng DV mới từ neighbor, nó cập nhật DV cũ của nó dùng công thức B-F: Dx(y) ← minv{c(x,v) + Dv(y)} với mỗi node y ∊ N  Dưới những điều khiện tự nhiên, ước lượng Dx(y) hội tụ tới chi phí dx thực sự nhỏ nhất dx(y) Tầng Network 4-89
  90. Thuật toán Distance vector Lặp, không đồng bộ: Mỗi node: mỗi lặp cục bộ được gây ra bởi: Chờ cho (thay đổi trong chi phí  Chi phí kết nối cục bộ thay đổi link cục bộ hoặc thông điệp từ neighbor)  Thông điệp cập nhật DV từ neighbor Phân bố: Tính toán lại các ước lượng  Mỗi node thông báo đến các neighbor chỉ khi DV của nó thay đổi Nếu DV đến đích bất kỳ vừa . Các neighbor sau đó thay đổi, thì thông báo neighbors thông báo đến các neighbor của nó nếu cần thiết Tầng Network 4-90
  91. Dx(z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 Bảng Chi phí đến Chi phí đến node x x y z x y z x 0 2 7 x 0 2 3 y y Từ 2 0 1 Từ ∞ ∞ ∞ z ∞ ∞ ∞ z 7 1 0 Bảng Chi phí đến node y x y z y 2 1 x ∞ ∞ ∞ x z y Từ 2 0 1 7 z ∞ ∞ ∞ Bảng Chi phí đến node z x y z x ∞ ∞ ∞ y Từ ∞ ∞ ∞ z 7 1 0 Thời gian Tầng Network 4-91
  92. Dx(z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 Bảng chi phí đến chi phí đến chi phí đến node x x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 y từ y từ ∞ ∞ ∞ 2 0 1 y từ 2 0 1 z z ∞ ∞ ∞ 7 1 0 z 3 1 0 Bảng chi phí đến chi phí đến chi phí đến node y 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 từ 2 0 1 từ 2 0 1 y 7 từ 2 0 1 z ∞ ∞ ∞ z 7 1 0 z 3 1 0 Bảng chi phí đến chi phí đến chi phí đến node z x y z x y z x y z x ∞ ∞ ∞ x 0 2 7 x 0 2 3 ừ t y y 2 0 1 từ từ y ∞ ∞ ∞ 2 0 1 z z z 7 1 0 3 1 0 3 1 0 Thời gian Tầng Network 4-92
  93. Distance vector: chi phí kết nối thay đổi Chi phí kết nối thay đổi:  node phát hiện sự thay đổi chi phí 1 kết nối cục bộ y 4 1  Cập nhật thông tin định tuyến, tính x z toán lại distance vector 50  Nếu DV thay đổi, thì thông báo cho neighbor “tin t0 : y phát hiện sự thay đổi chi phí kết nối, và cập nhật DV của tốt nó, thông báo đến các neighbor của nó. đi t1 : z nhận được cập nhật từ y, và cập nhật bảng của nó, tính chi nhanh” phí mới thấp nhất đến x, gởi DV của nó đến các neighborcủa nó. t2 : y nhận được cập nhật của z, và cập nhật bảng distance của nó. Các chi phí thấp nhất của y không thay đổi, vì vậy y không gởi thông điệp đến z. Tầng Network 4-93
  94. Distance vector: Chi phí kết nối thay đổi Chi phí kết nối thay đổi: 60  node phát hiện sự thay đổi chi y phí kết nối cục bộ 4 1 x z  Tin xấu đi chậm- “đếm đến vô 50 cùng” vấn đề!  44 lần duyệt trước khi thuật toán ổn định Tác động xấu ngược lại:  Nếu Z đi qua Y để tới X : . Z nói với Y khoảng cách của nó đến X là không xác định (vì vậy Y sẽ không đi tới X thông qua Z)  Điều này sẽ giải quyết được vấn đề đếm đến vô tận hay không? Tầng Network 4-94
  95. So sánh giữa thuật toán LS va DV Độ phức tạp của thông điệp Sự linh hoạt: điều gì xảy ra  LS: với n nodes, E kết nối, thì có nếu router gặp sự cố? O(nE) các thông điệp được gởi LS:  DV: chỉ trao đổi giữa các neighbor . node có thể quảng cáo sai . Thời gian hội tụ khác nhau chi phí kết nối . Mỗi node chỉ tính toán Tốc độ hội tụ bảng riêng của nó  LS: thuật toán O(n2) yêu cầu O(nE) DV: thông điệp . DV node có thể quảng cáo . Có thể có dao động sai về chi phí đường đi  DV: thời gian hội tụ khác nhau . Bảng của mỗi node được sử . Có thể là routing loop dụng bởi các node khác . Vấn đề đếm đến vô hạn (count- • Lỗi được lan truyền thông to-infinity) qua mạng Tầng Network 4-95
  96. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-96
  97. Định tuyến có cấu trúc (Hierarchical routing) Cho tới đây, tìm hiểu về routing của chúng ta thực hiện trong môi trường lý tưởng hóa  Tất cả các router là đồng nhất  Mạng “phẳng” không đúng trong thực tế Quy mô: với 600 triệu Quản trị đích đến:  internet = mạng của các  Không thể lưu trữ tất mạng cả các đích đến trong  Mỗi quản trị mạng có thể các bảng định tuyến muốn điều hành định  Việc trao đổi bảng định tuyến trong mạng của sẽ làm tràn ngập các riêng họ liên kết! Tầng Network 4-97
  98. Định tuyến có cấu trúc  Các router được gom vào gateway router: các vùng, “autonomous  Tại “biên” (“edge”) của systems” (AS) AS của nó  Các router trong cùng  Có liên kết đến router AS chạy cùng giao thức trong AS khác định tuyến với nhau . giao thức định tuyến “intra-AS” . Các router trong các AS khác nhau có thể chạy các giao thức định tuyến intra- AS khác nhau Tầng Network 4-98
  99. Kết nối các AS 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1  Bảng forwarding được cấu hình bởi cả thuật toán định tuyến intra- và Thuật toán Thuật toán inter-AS định tuyến định tuyến Intra-AS Inter-AS . intra-AS thiết lặp các mục cho các đích đến Bảng nội mạng Forwarding . inter-AS & intra-AS thiết lập các mục cho các đích đến ngoại Tầng Network 4-99
  100. Tác vụ Inter-AS  Giả sử router trong AS1 phải: AS1 nhận được 1. Học các đích đến nào datagram với đích đến có thể tới được thông nằm ngoài AS1: qua AS2 và AS3 . router nên chuyển 2. Lan truyền thông tin packet đến router này đến tất cả các gateway , nhưng là router trong AS1 cái nào? Công việc của định tuyến inter-AS! 3c 3a 3b AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d Tầng Network 4-100
  101. Ví dụ: thiết lập bảng forwarding trong router 1d  Giả sử AS1 học (thông qua giao thức inter-AS) mà subnet x có thể chạm tới thông qua AS3 (gateway 1c), nhưng không qua AS2 . Giao thức inter-AS lan truyền thông tin này đến tất cả các router nội mạng  router 1d xác định từ thông tin định tuyến intra-AS mà interface I của nó nằm trên đường đi có chi phí thấp nhất tới 1c . Đưa giá trị (x,I) vào bảng forwarding 3c x 3a 3b AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d Tầng Network 4-101
  102. Ví dụ: chọn giữa nhiều AS  Bây giờ, giả sử AS1 học từ giao thức inter-AS mà subnet x có thể chạm tới từ AS3 và từ AS2.  Để cấu hình bảng forwarding, router 1d phải xác định gateway nào mà nó nên dùng để chuyển các packet đến đích x . Đây cũng là công việc của giao thức định tuyến inter-AS! 3c x 3a 3b AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d ? Tầng Network 4-102
  103. Ví dụ: chọn giữa nhiều AS  Bây giờ, giả sử AS1 học từ giao thức inter-AS mà subnet x có thể chạm tới được từ AS3 và từ AS2.  Để cấu hình bảng forwarding, router 1d phải xác định gateway nào nó nên dùng để chuyển packet tới đích x . Đây cũng là công việc của giao thức định tuyến inter-AS!  hot potato routing: gửi packet tới 2 router gần nhất Xác định interface I Dùng thông tin định Học từ giao thức hot potato routing: từ bảng forwarding tuyến từ giao thức inter-AS mà subnet Chọn gateway nào cái mà dẫn đến intra-AS để xác định các x có thể chậm đến có chi phí thấp nhất gateway có chi chi phí của các đường thông qua nhiều phí thấp nhất. Đưa đi có chi phí thấp nhất gateway giá trị (x,I) vào bảng đến mỗi gateway forwarding Tầng Network 4-103
  104. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-104
  105. Định tuyến Intra-AS  Còn gọi là interior gateway protocols (IGP)  Các giao thức định tuyến intra-AS phổ biến: . RIP: Routing Information Protocol . OSPF: Open Shortest Path First . IGRP: Interior Gateway Routing Protocol (độc quyền của Cisco) Tầng Network 4-105
  106. RIP ( Routing Information Protocol)  Công bố vào năm 1982 trong BSD-UNIX  Thuật toán distance vector . Metric khoảng cách: số lượng hop (max = 15 hops), mỗi link có giá trị là 1 . Các DV được trao đổi giữa các neighbors mỗi 30 giây trong thông điệp phản hồi (còn gọi là advertisement) . Mỗi advertisement: danh sách lên đến 25 subnet đích Từ router A đến các subnet đích: u v subnet hops A B w u 1 v 2 w 2 x x 3 z C D y 3 y z 2 Tầng Network 4-106
  107. RIP: ví dụ z w x y A D B C Bảng định tuyến trong router D Subnet đích router kế tiếp số lượng hop đến đích w A 2 y B 2 z B 7 x 1 . . Tầng Network 4-107
  108. RIP: ví dụ Quảng cáo từ A-tới-D đích kế hops w - 1 x - 1 z C 4 . z w x y A D B C Bảng định tuyến trong router D Subnet đích router kế tiếp số lượng hop tới đích w A 2 y B 2 A 5 z B 7 x 1 . . Tầng Network 4-108
  109. RIP: lỗi đường kết nối và phục hồi Nếu không có quảng cáo nào sau 180 giây > neighbor/kết nối được xem như đã chết . Những đường đi qua neighbor bị vô hiệu . Các quảng cáo mới được gởi tới các neighbor . Các neighbor đó tiếp tục gởi ra những quảng cáo mới đó (nếu các bảng bị thay đổi) . Thông tin về lỗi đường kết nối nhanh chóng (?) lan truyền trên toàn mạng . poison reverse được dùng để ngăn chặn vòng lặp ping-pong (khoảng cách vô hạn = 16 hops) Tầng Network 4-109
  110. RIP: xử lý bảng  Các bảng định tuyến được quản lý bởi tiến trình ở mức application được gọi là route-d (daemon)  Các quảng cáo được gởi trong các packet UDP, được lặp lại theo chu kỳ routed routed transport transprt (UDP) (UDP) network forwarding forwarding network (IP) table table (IP) link link physical physical Tầng Network 4-110
  111. OSPF (Open Shortest Path First)  “open”: sẵn sàng công khai  Dùng thuật toán link state . Phổ biến packet LS . Bảng đồ cấu trúc mạng tại mỗi node . Tính toán đường đi dùng thuật toán Dijkstra  Quảng cáo OSPF mang 1 entry cho mỗi neighbor  Các quảng cáo được phát tán đến toàn bộ AS . Được mang trong thông điệp OSPF trực tiếp trên IP (chứ không phải là TCP hoặc UDP)  Giao thức định tuyến IS-IS : gần giống với OSPF Tầng Network 4-111
  112. Các đặc tính “tiến bộ” của OSPF (không có trong RIP)  Bảo mật: tất cả các thông điệp OSPF được chứng thực (để chống lại sự xâm nhập có hại)  Cho phép có nhiều đường đi có chi phí như nhau (RIP chỉ cho 1)  Với mỗi đường kết nối, nhiều số liệu chi phí (cost metrics) cho TOS khác nhau (ví dụ:chi phí đường kết nối vệ tinh được thiết lập “thấp” cho ToS nổ lực tốt nhất; cao cho ToS thời gian thực)  Hỗ trợ uni- và multicast tích hợp: . Multicast OSPF (MOSPF) dùng cùng cơ sở dữ liệu cấu trúc mạng như OSPF  OSPF phân cấp trong các miền lớn (large domains). Tầng Network 4-112
  113. OSPF phân cấp Router biên (boundary ) backbone router backbone area border routers area 3 internal routers area 1 area 2 Tầng Network 4-113
  114. OSPF phân cấp  Phân cấp mức 2: vùng cục bộ (local area), backbone. . Các quảng cáo link-state chỉ trong vùng . Mỗi node có chi tiết cấu trúc của vùng; chỉ biết hướng (đường ngắn nhất) đến các mạng trong các vùng khác.  Các router area border: “tóm tắt” các khoảng cách đến các mạng trong vùng của nó, quảng cáo đến các router Area Border của các vùng khác.  Các backbone router: chạy định tuyến OSPF được giới hạn đến backbone.  boundary routers: kết nối đến các AS khác. Tầng Network 4-114
  115. Định tuyến Internet inter-AS : BGP  BGP (Border Gateway Protocol): giao thức định tuyến liên miền (inter-domain ) trên thực tế . “gắn kết Internet lại với nhau”  BGP cũng cấp cho mỗi AS một phương tiện để: . eBGP: lấy thông tin có thể chạm tới subnet từ các AS neighbor. . iBGP: lan truyền thông tin đó đến tất cả các router bên trong AS. . Xác định các đường đi “tốt” đến các mạng khác dựa trên thông tin khả năng chạm tới và chính sách.  Cho phép subnet quảng cáo sự tồn tại của nó đến phần còn lại của Internet: “I am here” Tầng Network 4-115
  116. BGP cơ bản  BGP session: 2 router BGP (“cặp”) trao đổi các thông điệp BGP: . Quảng cáo các đường đi đến các tiền tố (prefixes) mạng đích khác nhau (Giao thức “path vector”) . Được trao đổi trên các kết nối semi-permanent TCP  Khi AS3 quảng cáo 1 prefix tới AS1: . AS3 hứa là nó sẽ chuyển các datagram tới prefix đó . AS3 có thể tổng hợp các prefixe trong quảng cáo của nó 3c 3a Thông điệp 3b BGP AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d Tầng Network 4-116
  117. BGP cơ bản: phân phối thông tin đường đi  Sử dụng phiên eBGP giữa 3a và 1c, AS3 gửi prefix về thông tin khả năng chạm (prefix reachability info) tới AS1. . 1c sau đó có thể dùng iBGP phân phối thông tin prefix mới tới tất cả các router trong AS1 . 1b sau đó có thể quảng cáo lại thông tin về khả năng chạm mới tới AS2 trên phiên eBGP từ 1b-tới-2a  Khi router học prefix mới, thì nó sẽ tạo mục cho prefix đó trong bảng forwarding của nó. Phiên eBGP 3a 3b Phiên iBGP AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d Tầng Network 4-117
  118. Các thuộc tính đường đi và các route BGP  prefix được quảng cáo bao gồm các thuộc tính BGP . prefix + attributes = “route”  2 thuộc tính quan trọng: . AS-PATH: chứa các AS mà thông qua đó quảng cáo prefix vừa đi qua: ví dụ: AS 67, AS 17 . NEXT-HOP: chỉ ra router bên trong AS cụ thể tới AS hop kế tiếp. (có thể có nhiều đường kết nối từ AS hiện tại tới AS hop kế tiếp)  router gateway mà nhận quảng cáo route sử dụng chính sách quan trọng (import policy) để chấp nhận/từ chối . Ví dụ: không bao giờ đi qua AS x . Định tuyến dựa trên chính (sách policy-based routing) Tầng Network 4-118
  119. Sự lựa chọn BGP route  router có thể học hơn 1 route tới AS đích, chọn route dựa trên: 1. Thuộc tính giá trị ưu tiên cục bộ: quyết định chính sách 2. AS-PATH ngắn nhất 3. NEXT-HOP router gần nhất: định tuyến hot potato 4. Tiêu chuẩn bổ sung Tầng Network 4-119
  120. Các thông điệp BGP  Các thông điệp BGP được trao đổi giữa các peer trên kết nối TCP  Các thông điệp BGP: . OPEN: mở kết nối TCP đến peer và chứng thực người gửi . UPDATE: quảng cáo đường đi mới(hoặc là lấy lại cái cũ) . KEEPALIVE: giữ kết nối sống khi các UPDATES không được cập nhật; còn gọi là yêu cầu OPEN các ACK . NOTIFICATION: thông báo các lỗi trong thông điệp trước đó; cũng được sử dụng để đóng kết nối Tầng Network 4-120
  121. Đặt các giao thức định tuyến lại với nhau: Làm thế nào một entry đưa vào trong bảng forwarding của 1 router?  Câu trả lời rất phức tạp!  Buộc các định tuyến phân cấp (mục 4.5.3) lại với nhau với BGP (4.6.3) và OSPF (4.6.2).  Cung cấp tổng quan về BGP!
  122. Làm thế nào để entry được đưa vào bảng forwarding? Thuật toán định tuyến Giả sử prefix Bảng local forwarding là trong AS khác. entry prefix output port 138.16.64/22 3 124.12/16 2 212/8 4 1 Dest IP 3 2
  123. Làm thế nào để entry được đưa vào bảng forwarding? 1. Router nhận thức được prefix 2. Router xác định port ra (output port) cho prefix 3. Router đưa cổng cho prefix đó vào trong bảng forwarding
  124. Router nhận thức được prefix 3c 3a Thông điệp 3b BGP AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d  Thông điệp BGP chứa “các route”  “route” là 1 prefix và các thuộc tính: AS-PATH, NEXT-HOP,  Ví dụ: route:  Prefix:138.16.64/22 ; AS-PATH: AS3 AS131 ; NEXT-HOP: 201.44.13.125
  125. Router có thể nhận được nhiều route 3c ệ 3a Thông đi p 3b BGP AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d  Router có thể nhận được nhiều route cho cùng prefix  Phải chọn 1 route
  126. Chọn route BGP tốt nhất tới prefix  Router chọn route dựa trên AS-PATH ngắn nhất  ụ Ví d : Chọn  AS2 AS17 to 138.16.64/22  AS3 AS131 AS201 to 138.16.64/22  Điều gì sẽ xảy ra nếu có mối ràng buộc? Chúng ta sẽ bàn sau!
  127. Tìm route nội bộ tốt nhất đến route BGP  Dùng thuộc tính NEXT-HOP của route được lựa chọn . Thuộc tính NEXT-HOP của Route là địa chỉ IP của interface của router đó, cái mà bắt đầu AS PATH đó.  Ví dụ:  AS-PATH: AS2 AS17 ; NEXT-HOP: 111.99.86.55  Router sử dụng OSPF để tìm ra đường đi ngắn nhất từ 1c tới 111.99.86.55 3c 111.99.86.55 3a 3b AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d
  128. Router xác định port cho route  Xác định port theo đường đi OSPF ngắn nhất  Thêm prefix-port entry vào bảng forwarding của nó: . (138.16.64/22 , port 4) 3c router 3a port 3b 1 2c AS3 1c 4 other 2 2a networks other 1a 3 2b networks 1b AS2 AS1 1d
  129. Định tuyến Hot Potato  Giả sử có 2 hoặc nhiều route liên tuyến tốt nhất (best inter-routes).  Sau đó chọn route với NEXT-HOP gần nhất . Dùng OSPF để xác định cổng nào là gần nhất . Hỏi: từ 1c, chọn AS3 AS131 hoặc AS2 AS17? . Đáp: route AS3 AS201 vì nó gần hơn 3c 3a 3b AS3 2c other 1c 2a networks other 1a 2b networks 1b AS2 AS1 1d
  130. Làm thế nào để entry được đưa vào bảng forwarding? Tóm tắt 1. Router có nhận thức về prefix . Thông qua các quảng cáo route BGP từ các router khác 2. Xác định port ra của router cho prefix đó . Dùng route BGP vừa chọn để tìm ra route liên AS (inter-AS ) tốt nhất . Dùng OSPF để tìm ra route tốt nhất trong nội bộ AS (intra-AS ) cái mà dẫn đến route liên AS tốt nhất (inter-AS route) . Router xác định port của router cho route tốt nhất đó 3. Đưa prefix-port entry vào trong bảng forwarding
  131. Chính sách BGP routing Ký hiệu: Mạng của B nhà cung cấp X W A Mạng của C khách hàng Y  A,B,C là các nhà cung cấp mạng  X,W,Y là khách hàng (của nhà cung cấp mạng)  X là dual-homed: được kết nối vào 2 mạng . X không muốn có tuyến đường từ B thông qua X tới C . Vì vậy X sẽ không quảng cáo cho B tuyến đường tới C Tầng Network 4-131
  132. Chính sách BGP routing (2) Ký hiệu: Mạng của B nhà cung cấp X W A Mạng của C khách hàng Y  A quảng cáo đường đi AW cho B  B quảng cáo đường đi BAW cho X  B có nên quảng cáo đường đi BAW cho C hay không? . Không nên! B không nhận được “thu nhập” cho việc định tuyến CBAW vì cả W và C không phải là khách hàng của B . B muốn bắt buộc C đi tới w thông A . B chỉ muốn dẫn đường đi/đến các khách hàng của nó! Tầng Network 4-132
  133. Tại sao phải định tuyến Intra-, Inter-AS khác nhau? Chính sách:  inter-AS: người quản trị muốn kiểm soát cách mà traffic của nó được định tuyến, ai mà định tuyến thông qua mạng của nó .  intra-AS: 1 người quản trị, vì vậy không cần các quyết định chính sách Linh hoạt:  Định tuyến phân cấp làm giảm kích thước bảng định tuyến, giảm lưu lượng cập nhật Hiệu suất:  intra-AS: có thể tập trung vào hiệu suất  inter-AS: chính sách quan trọng hơn hiệu suất Tầng Network 4-133
  134. Chương 4: Nội dung 4.1 Giới thiệu 4.5 các thuật toán routing 4.2 virtual circuit . link state network và datagram . distance vector network . hierarchical routing 4.3 Cấu trúc bên trong 4.6 routing trong Internet router . RIP 4.4 IP: Internet Protocol . OSPF . Định dạng datagram . BGP . IPv4 addressing 4.7 broadcast và multicast . ICMP routing . IPv6 Tầng Network 4-134
  135. Broadcast routing  Chuyển các packet từ nguồn tới tất cả các node khác  Nguồn trùng lặp thì không có hiệu quả: duplicate duplicate R1 creation/transmission R1 duplicate R2 R2 R3 R4 R3 R4 Nguồn Trùng lặp trùng lặp trong mạng  Nguồn trùng lặp: làm sao xác định được địa chỉ người nhận? Tầng Network 4-135
  136. Trùng lặp trong mạng  flooding: khi node nhận được packet broadcast, nó gởi bản sao đến tất cả các neighbor . Vấn đề: lặp lại & bão broadcast  Flooding có điều khiển: node chỉ broadcast packet nếu nó không gửi broadcast giống như vậy trước đó . node theo dõi các packet đã broadacst . Hoặc reverse path forwarding (RPF): chỉ chuyển các packet nếu nó đã đến trên đường đi ngắn nhất giữa node và nguồn  spanning tree: . Không có các packet dư thừa được nhận tại bất cứ node nào Tầng Network 4-136
  137. Spanning tree  Đầu tiên xây dựng một spanning tree  Sau đó các node chuyển tiếp/tạo các bản sao chỉ dọc theo spanning tree A A B B c c D D F E F E G G (a) broadcast được khởi tạo tại A (b) broadcast được khởi tạo tại D Tầng Network 4-137
  138. Spanning tree: tạo  Node trung tâm  Mỗi node gởi thông điệp gia nhập unicast (unicast join message) đến node trung tâm . Thông điệp này được chuyển tiếp cho đến khi nó đến tại một node đã nằm trên spanning tree A A 3 B B c c 4 2 D D F E F E 1 5 G G (a) Các bước xây dựng (b) spanning tree đã được spanning tree (center: E) xây dựng xong Tầng Network 4-138
  139. Multicast routing: phát biểu vấn đề Mục tiêu: tìm một cây (hoặc các cây) kết nối các router có các thành viên trong nhóm multicast  Cây (tree): không phải tất cả các đường đi giữa các router đều được sử dụng  Cây chia sẽ (shared-tree): cây giống nhau được sử dụng bởi các thành viên trong nhóm  Cây dựa trên nguồn(source-based): cây Ký hiệu khác nhau từ nơi gửi tới nơi nhận group member not group member router with a group member router without Cây chia sẽ Cây dựa trên nguồn group member Tầng Network 4-139
  140. Các cách tiếp cận để xậy dựng các cây multicast Các hướng tiếp cận:  Cây dựa trên nguồn (source-based tree): một cây cho mỗi nguồn . Các cây đường đi ngắn nhất . Cây đường đi ngược  Cây chia sẽ nhóm: nhóm dùng 1 cây . Mở rộng tối thiểu (Steiner) . Các cây dựa trên trung tâm (center-based trees) tìm hiểu các cách tiếp cận cơ bản, sau đó các giao thức cụ thể áp dụng cho các hướng tiếp cận này Tầng Network 4-140
  141. Cây đường đi ngắn nhất  Cây chuyển tiếp multicast (mcast forwarding tree): cây đường đi ngắn nhất dẫn đường từ nguồn tới tất cả các nơi nhận . Thuật toán Dijkstra s: nguồn Ký hiệu R1 2 router với các thành viên R4 1 của nhóm đã được gắn vào R2 5 router không có các thành viên 3 4 nào của nhóm được gắn vào R5 Đường kết nối được sử dụng 6 i R3 cho forwarding, R6 R7 i chỉ thứ tự đường link được thêm vào bởi thuật toán Tầng Network 4-141
  142. Reverse path forwarding  Dựa vào kiến thức của router của đường đi ngắn nhất unicast từ nó đến nơi gửi  Mỗi router có cách xử lý forwarding đơn giản: if (datagram multicast được nhận trên đường kết nối đến trên đường đi ngắn nhất kể từ trung tâm) then flood datagram lên tất cả các kết nối ra else bỏ qua datagram Tầng Network 4-142
  143. Reverse path forwarding: ví dụ s: nguồn Kí hiệu R1 R4 router với các thành viên của nhóm đã gắn vào R2 router không có các thành R5 viên của nhóm gắn vào R3 datagram sẽ được forward R6 R7 datagram sẽ không được forward  Kết quả là một cây SPT đảo ngược . Có thể là một lựa chọn không tốt với các kết nối không đồng bộ Tầng Network 4-143
  144. Reverse path forwarding: cắt giảm (pruning)  Cây forwarding chứa các cây con không có các thành viên trong nhóm multicast . Không cần forward các datagram xuống cây con . “cắt giảm” các thông điệp được gửi lên trên bởi router không có các thành viên nhóm downstream s: nguồn Ký hiệu R1 R4 router với các thành viên của nhóm đã gắn vào R2 P router không có các R5 thành viên của nhóm gắn vào P R3 P thông điệp cắt giảm R6 các kết nối với multicast R7 forward Tầng Network 4-144
  145. Cây chia sẽ (Shared-tree): cây steiner  Cây steiner : cây có chi phí thấp nhất kết nối đến tất cả các router với các thành viên nhóm đã được gắn vào  Vấn đề là NP-complete  Các heuristics rất tốt tồn tại  Không sử dụng trong thực tế: . Độ phức tạp tính toán . Cần thông tin về về toàn bộ mạng . monolithic: chạy lại mỗi khi router cần gia nhập/rời khỏi Tầng Network 4-145
  146. Cây dựa vào trung tâm (Center-based trees)  Một cây truyền nhận được chia sẽ cho tất cả  Một router được xác định như là “trung tâm” của cây  Để gia nhập: . router biên (edge ) gửi thông điệp gia nhập unicast đến router trung tâm . Thông điệp gia nhập (join-msg ) “được xử lý” bởi các router trung gian và chuyển đến các router trung tâm . Thông điệp gia nhập, hoặc đến nhánh cây của trung tâm này, hoặc đến ngay trung tâm . Đường đi được thực hiệu bởi thông điệp gia nhập trở thành nhánh cây mới của router này Tầng Network 4-146
  147. Cây dựa vào trung tâm: ví dụ Giả sử R6 được chọn là trung tâm: LEGEND R1 router với các thành viên R4 3 của nhóm đã gắn vào R2 router không có các 2 thành viên của nhóm gắn vào 1 R5 thứ tự đường đi trong ấy các thông điệp gia nhập đã R3 sinh ra 1 R6 R7 Tầng Network 4-147
  148. Internet Multicasting Routing: DVMRP  DVMRP: distance vector multicast routing protocol, RFC1075  flood và prune: forwarding đường đi ngược (reverse path forwarding), cây dựa vào nguồn (source-based tree) . Cây RPF dựa trên các bảng định tuyến của DVMRP của nó được xây dựng bởi truyền thông các router DVMRP . Không có các giả thuyết về unicast bên dưới . datagram ban đầu đến nhóm multicast được flood mọi nơi thông qua RPF . Các router không phải nhóm: gửi thông điệp cắt giảm lên trên Tầng Network 4-148
  149. DVMRP: tiếp tục  Trạng thái mềm: router DVMRP chu kỳ (1 phút) “quên” các nhánh cây bị cắt giảm: . Dữ liệu mcast một lần nữa đổ xuống các nhánh không được cắt giảm . Router phía dưới: cắt giảm lần nữa hoặc tiếp tục nhận dữ liệu  Các router có thể nhanh chóng tái cắt giảm . Gia nhập IGMP tại các lá  Còn lại . Thường được thực hiện trong router thương mại Tầng Network 4-149
  150. Tunneling Q: làm cách nào để kết nối “các đảo” của các router muticast trong một “biển” của các router unicast? Cấu trúc vật lý Cấu trúc logic  datagram multicast được đóng gói trong datagram “thông thường” (không có multicast)  datagram IP thông thường được gửi thông qua “đường hầm” (“tunnel”) và qua IP unicast đến router muticast nhận (xem lại IPv6 bên trong đường hầm IPv4)  router mcast nhận mở gói để lấy datagram multicast Tầng Network 4-150
  151. PIM: Protocol Independent Multicast  Không phụ thuộc vào bất kỳ thuật toán định tuyến unicast bên dưới nào (underlying unicast routing algorithm) (làm việc với tất cả)  2 ngữ cảnh phân phối multicast khác nhau: Dầy đặc: Thưa thớt:  Các thành viên nhóm  Số lượng các mạng với các đóng gói dày đặc, thành viên nhóm ít trong khoảng cách  Các thành viên nhóm “gần”. ”được phân bố thưa thớt”  Băng thông dư thừa  Băng thông không dư thừa Tầng Network 4-151
  152. Kết quả của sự phân chia thưa thớt-dày đặc: Dày đặc Thưa thớt:  Nhóm các thành viên bởi  Không có thành viên cho các router được giả định đến khi các router thực cho đến khi các router sự gia nhập cắt giảm thực sự  Kiến trúc receiver- driven  Kiến trúc data-driven của cây mcast (ví dụ cây trên cây mcast (ví dụ dựa vào trung tâm) RPF)  Băng thông và router  Băng thông và router không thuộc nhóm xử lý không thuộc nhóm xử lý vừa phải phung phí Tầng Network 4-152
  153. PIM- kiểu dày đặc flood-and-prune RPF: tương tự như DVMRP nhưng  Giao thức bên dưới cung cấp thông tin RPF cho datagram đến  flood xuống dưới (downstream) ít phức tạp (ít hiệu quả) hơn so với DVMRP giảm sự phụ thuộc vào thuật toán định tuyến cơ bản  Có cơ chế giao thức cho router để phát hiện có phải là router ở node lá (leaf-node) Tầng Network 4-153
  154. PIM – kiểu thưa thớt  Tiếp cận dựa vào trung tâm (center-based)  router gởi thông điệp gia R1 R4 nhập (join msg) đến join rendezvous point (RP) R2 . Các router trung gian join cập nhật trạng thái và R5 join forward thông điệp gia R3 nhập R6  ậ Sau khi gia nh p thông qua Tất cả dữ liệu R7 RP, router có thể chuyển rendezvous multicast đến từ point sang cây xác định nguồn rendezvous (source-specific tree) point . Hiệu xuất tăng: ít tập trung, các đường đi ngắn ơ h n Tầng Network 4-154
  155. PIM – kiểu thưa thớt (Các) Bên gửi: R1  Dữ liệu unicast đến RP, R4 RP phân phối xuống cây join R2 có nút gốc là RP join  RP có thể mở rộng cây R5 join multicast dòng lên đến R3 nguồn R6 R7  RP có thể gởi thông Tất cả dữ liệu rendezvous điệp dừng (stop msg) multicast đến từ point rendezvous nếu không có bên nhận point nào được ngắn vào . “không có ai đang lắng nghe!” Tầng Network 4-155
  156. Chapter 4: Hoàn thành! 4.1 Giới thiệu 4.2 Mạng mạch ảo và mạng 4.5 các thuật toán định tuyến datagram (virtual . link state, distance vector, circuit and datagram định tuyến phân cấp networks) 4.6 định tuyến trong Internet 4.3 bên trong router . RIP, OSPF, BGP 4.4 IP: Internet Protocol 4.7 broadcast and multicast . datagram định dạng, routing định địa chỉ IPv4, ICMP, IPv6  Hiểu về các nguyên tắt đằng sau các dịch vụ tầng network: . Các mô hình dịch vụ tầng network, so sánh cách mà router forwarding và routing dữ liệu, định tuyến(chọn đường đi), broadcast, multicast  Hiện thực trên Internet Tầng Network 4-156