›
›

Giáo trình Mạng máy tính - Chương 4: Kết nối mạng Internet - Nguyễn Hữu Thanh

pdf 60 trang huongle 240
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: Kết nối mạng Internet - Nguyễn Hữu Thanh", để 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_ket_noi_mang_internet_nguy.pdf

Nội dung text: Giáo trình Mạng máy tính - Chương 4: Kết nối mạng Internet - Nguyễn Hữu Thanh

  1. CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh Bộ môn Kỹ thuật thông tin Viện Điện tử - Viễn thông ĐHBK Hà Nội Email: thanhnh@mail.hut.edu.vn Nội dung Tại sao phải kết nối mạng lớp Internetworking? Khái niệm kết nối mạng và kiến trúc Internet Cấu trúc địa chỉ IP, liên hệ giữa địa chỉ IP, địa chỉ MAC IP và các giao thức có liên quan Định tuyến trong Internet 1
  2. Đặt vấn đề Nhu cầu: kết nối nhiều mạng con với nhau thành một mạng toàn cầu Khái niệm Kết nối nhiều mạng LAN ở lớp MAC Địa chỉ IP có khả thi? Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 3 Đặt vấn đề (tiếp )  Các khó khăn: Do địa chỉ MAC không có cấu trúc nên không thể sử dụng để định tuyến phải tạo ra một Khái niệm spanning tree ◊ Việc tạo ra spanning tree kết nối hàng chục ngàn nút không khả thi: Địa chỉ IP – Chọn nút gốc? – Kích thước bảng chuyển tiếp (forwarding table) quá lớn Internet – Các bản tin cấu hình quảng bá với số nút lớn làm Protocol mạng bị lụt với các bản tin điều khiển Các giao Việc kết nối các mạng vật lý: cấu trúc vật lý thức khác khác nhau và cách đánh địa chỉ khác nhau cực kỳ phức tạp (Ethernet, WiFi, ATM, .v.v.) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 4 2
  3. Đặt vấn đề (tiếp )  Kết luận: Cần phải có một phân lớp chung độc lập với các mạng vật lý kết nối mạng lớp Khái niệm Internetworking mạng Internet Application Application Địa chỉ IP TCP TCP Internet Protocol IP IP IP Các giao LLC/MAC (802.11) 802.11 802.3 LLC/MAC (802.3) thức khác Physical Physical Physical Định tuyến Sender Receiver CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 5 Yêu cầu thiết kế mạng Internet Phải tạo ra một “lớp kết nối liên mạng” (Internetworking) Khái niệm Địa chỉ mạng có cấu trúc: phụ thuộc vào vị trí mạng thích hợp cho định Địa chỉ IP tuyến Phân lớp chung không phụ thuộc vào cơ Internet Protocol sở hạ tầng và công nghệ mạng phần cứng Các giao thức khác “Giấu” cơ sở hạ tầng mạng phía dưới với các dịch vụ mạng lớp trên Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 6 3
  4. Yêu cầu thiết kế mạng Internet (tiếp ) Internet Khái niệm Địa chỉ IP Router Internet Protocol DSL ATM Ethernet Các giao 3G/4G thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 7 Lịch sử phát triển của Internet  1957: Mỹ thành lập cơ quan ARPA (Advanced Research Projects Agency) trực thuộc Bộ quốc phòng  1962: Mỹ tập trung nghiên cứu các phương thức gửi dữ liệu quân sự theo phương thức phân tán nguyên lý chuyển mạch gói  1968: ARPA thành lập dự án ARPANET kết nối UCLA, SRI (tại Stanford), UCSB (Santa Barbara), ĐH Utah. Băng Khái niệm thông 50kbps  1972: Email đầu tiên. ARPA đổi tên thành DARPA Địa chỉ IP (Defence Advanced Research Projects Agency). ARPANET sử dụng NCP (Network Control Protocol) cho phép truyền dữ liệu giữa 2 nút trên cùng mạng Internet  1973: Vinton Cerf và Bob Kahn (Stanford) bắt đầu phát Protocol triển TCP/IP, cho phép các máy tính liên mạng trao đổi dữ liệu Các giao thức khác  1974: thuật ngữ Internet được sử dụng lần đầu tiên  1976: Robert M. Metcalfe phát triển mạng Ethernet. Mạng truyền số liệu qua vệ tinh được phát triển. APARNET đã Định tuyến có hơn 23 nút CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 8 4
  5. Lịch sử phát triển của Internet (tiếp )  1981: NSF quyết định xây dựng mạng CSNET cho nghiên cứu độc lập với ARPANET. Liên kết giữa ARPANET và CSNET. Host: 213  1983: thành lập Internet Activities Board (IAB). TCP/IP thay thế hoàn toàn NCP. ĐH Wisconsin đưa ra DNS đầu tiên. Host: 562  1985: NSF thành lập mạng NSFNET, dung lượng: 1,55Mpbs. Host: Khái niệm 1962  1986: IETF (Internet Engineering Task Force) được thành lập. Host: 2308 Địa chỉ IP  1990: ngôn ngữ htlm ra đời. Host: 330000  1992: sự ra đời của World Wide Web. Băng thông mạng lõi: Internet 45Mbps. Host: 2.000.000 Protocol  1993: Mosaic ra đời: web browser đầu tiên với giao diện đồ họa  1996: host: 15.000.000 Các giao  1998: IPv6 được chuẩn hóa bởi IETF thức khác  1999: 802.11 ra đời Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 9 Đặc điểm của Internet  Mỗi gói được định tuyến (tìm đường) một cách độc lập router không lưu giữ trạng thái của các luồng dữ liệu  Cho phép truyền gói qua nhiều mạng vật lý khác nhau Khái niệm  Không có cơ chế đảm bảo trễ  Không có cơ chế đảm bảo thứ tự gói Địa chỉ IP  Không có cơ chế đảm bảo gói sẽ được truyền đến nơi nhận Internet Protocol Gói có thể bị mất do tràn hàng đợi ở nút trung gian  Các chức năng “thông minh” (truyền lại gói, sắp Các giao xếp thứ tự gói, điều khiển luồng, chống tắc thức khác nghẽn) được thực hiện bởi thiết bị đầu cuối Giao thức Internet (Internet Protocol – IP) được Định tuyến sử dụng! CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 10 5
  6. Chức năng chính của lớp Internetworking Định tuyến (routing): tìm đường đi cho một gói tin từ nguồn đến đích Khái niệm thuật toán vào giao thức định tuyến Địa chỉ IP Chuyển tiếp (forwarding): chuyển một gói tin từ một đầu vào router ra Internet Protocol đầu ra thích hợp bảng chuyển tiếp Các giao (forwarding/routing table) thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 11 Địa chỉ IP  Địa chỉ IP IPv4: 32 bit (chương này chỉ xét IPv4) IPv6: 128 bit Khái niệm  Yêu cầu: phải có cấu trúc, cho phép định tuyến địa chỉ IP: Địa chỉ IP Network ID. (địa chỉ mạng) Host ID. (địa chỉ máy trạm) Internet  Mỗi giao diện mạng có một địa chỉ IP – địa chỉ IP Protocol có tính duy nhất Các giao  Cấp phát địa chỉ IP: thức khác Tĩnh Động (TD qua DHCP) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 12 6
  7. Địa chỉ IP (tiếp ) Biểu diễn địa chỉ IP 4 byte được biểu diễn bởi 4 chữ số thập Khái niệm phân có chấm X X X X Địa chỉ IP . . . Internet 8 bit (0 - 255) Protocol Các giao TD: địa chỉ DNS của FPT: 210.245.0.10 thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 13 Địa chỉ IP (tiếp )  Không gian địa chỉ IP: Theo lý thuyết ◊Có thể là 0.0.0.0 ～ 255.255.255.255 Khái niệm ◊Một số địa chỉ đặc biệt (RFC1918) Địa chỉ IP Private address 10.0.0.0/8 Internet 172.16.0.0/12 Protocol (không có ý nghĩa toàn cục) 192.168.0.0/16 Các giao thức khác Loopback address 127.0.0.1 224.0.0.0 Multicast address Định tuyến ～239.255.255.255 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 14 7
  8. Địa chỉ IP (tiếp ) Số máy trạm tối đa trong một mạng: k=2n – 2 Khái niệm ◊Trong đó: n – số bit của Host ID. 2 địa chỉ còn lại: Địa chỉ IP ◊Địa chỉ toàn 0 – địa chỉ mạng – TD: Mạng 171.64.15.0 Internet Protocol ◊Địa chỉ toàn 1 – địa chỉ quảng bá trong phạm vi một mạng Các giao – TD: 171.64.15.255 địa chỉ quảng bá trong thức khác phạm vi mạng 171.64.15.0 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 15 Địa chỉ IP (tiếp )  Nguyên tắc đánh 223.1.1.1 223.1.1.2 223.1.1.4 địa chỉ: Mỗi mạng LAN có 223.1.1.3 địa chỉ mạng riêng Khái niệm biệt và được ngăn 223.1.9.2 223.1.7.2 cách bởi router Các máy trạm (kể Địa chỉ IP cả router) nằm trong một LAN có chung địa chỉ 223.1.9.1 223.1.7.1 Internet 223.1.8.1 223.1.8.2 Protocol mạng, còn địa chỉ máy trạm khác nhau 223.1.2.6 223.1.3.27 Các giao thức khác Có bao nhiêu mạng LAN trong hình bên? Định tuyến 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 16 8
  9. Địa chỉ IP (tiếp ) Câu hỏi: Làm sao phân biệt được địa chỉ mạng Khái niệm và địa chỉ máy trạm trong 32 bit địa chỉ IP? Địa chỉ IP Phân loại địa chỉ IP: Internet Có phân lớp (classful addressing) Protocol Không phân lớp (classless addressing): Các giao ◊Subnetting thức khác ◊Supernetting (CIDR) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 17 Địa chỉ IP (tiếp )  Địa chỉ IP có phân lớp: 5 lớp (A, B, C, D, E) 8bits 8bits 8bits 8bits Khái niệm Class A 0 7ｂｉｔ H H H Class B 1 0 6bit N H H Địa chỉ IP Class C 1 1 0 5ｂｉｔ N N H Internet Class D 1 1 1 0 Multicast Protocol Class E 1 1 1 1 Reserve for future use Các giao thức khác A B C D 0 232-1 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 18 9
  10. Địa chỉ IP (tiếp ) # of network # of hosts Class A 128 2^24 Class B 16384 65536 Khái niệm Class C 2^21 256 Địa chỉ IP  Địa chỉ IP có phân lớp: (tiếp ) Thí dụ: Internet ◊ 18.181.0.31 class A Protocol ◊ 171.64.74.155 class B Các giao Nhận xét: địa chỉ có phân lớp gây lãng phí thức khác không gian địa chỉ Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 19 Địa chỉ IP (tiếp ) Thí dụ: 18.181.0.31 (www.mit.edu) ? Khái niệm 171.64.74.155 (stanford) ? Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 20 10
  11. Địa chỉ IP (tiếp ) Nhận xét: đánh địa chỉ có phân lớp có một số nhược điểm Khái niệm Cứng nhắc, lớp C quá nhỏ, lớp B quá lớn không tận dụng hiệu quả miền Địa chỉ IP địa chỉ Các router trong mạng nội bộ cần phải Internet Protocol có địa chỉ mạng (network ID.) riêng biệt cho từng giao diện Các giao thức khác Thí dụ: một cơ quan có tổng cộng 300 máy tính tìm cơ chế đánh địa chỉ? Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 21 Địa chỉ IP (tiếp )  Subnetting: chia nhỏ một mạng thành nhiều mạng con với nhiều địa chỉ mạng con 16 CLASS “B” 2 14 Khái niệm 10 Net ID Host-ID e.g. Company Địa chỉ IP 2 14 16 2 14 16 10 Net ID 0000 Host-ID 10 Net ID 1111 Host-ID Subnet Internet Subnet ID (20) Subnet ID (20) Subnet Host ID (12) Host ID (12) Protocol Các giao 14 thức khác 14 16 16 10 Net ID 000000 Host-ID 10 Net ID 1111011011 Host-ID Subnet ID (22) Subnet Subnet ID (26) Subnet Host ID (6) Định tuyến Host ID (10) CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 22 11
  12. Địa chỉ IP (tiếp )  Subnetting (tiếp ): Subnetting thường được biểu diễn bằng địa chỉ IP kèm theo “mặt nạ mạng” (subnet mask) Khái niệm Thí dụ: ◊ IP address: 171.64.15.82 ◊ Subnet mask: 255.255.255.0 Địa chỉ IP Subnet mask: 24 bit đầu (3 byte đầu) là địa chỉ mạng, 8 bit cuối là địa chỉ máy trạm Internet Protocol Cách biểu diễn địa chỉ mạng: a.b.c.d/x, trong đó a.b.c.d là địa chỉ mạng, x là số bit của địa Các giao chỉ mạng thức khác ◊ 171.64.15.0/24 mạng có địa chỉ 171.64.15.0 với phần địa chỉ mạng dài 24 bit Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 23 Địa chỉ IP (tiếp )  Subnetting (tiếp ): • Địa chỉ máy trạm: 171.64.15.82 Địa chỉ mạng (24 bit) Địa chỉ máy (8 bit) 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 1 0 Khái niệm 171 64 15 82 • Mặt nạ mạng: 255.255.255.0 Địa chỉ IP Các bit phần địa chỉ mạng có giá trị 1 0 Internet Protocol 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 255 255 255 0 Các giao • Địa chỉ mạng: 171.64.15.0 thức khác Địa chỉ mạng (24 bit) Địa chỉ máy (8 bit) Định tuyến 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 24 12
  13. Địa chỉ IP (tiếp )  Subnetting (tiếp ): Thí dụ: subnetting tại Stanford ◊ Giải thích sơ đồ mạng bên dưới? Khái niệm To: cenic.net 171.64.1.131 171.64.74.0/24 hpr1-rtr 171.64.1.132/30 Địa chỉ IP 171.64.1.133 Stanford Class B 171.64.1.161 171.64.1.178 171.64.74.1 Internet Address Gates-rtr Protocol bbr2-rtr 171.64.74.58 171.64.0.0/16 171.64.1.160/27 AS 32 yuba Các giao 171.64.1.152 thức khác 171.64.1.144/28 To: cogentco.com border2-rtr 171.64.1.148 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 25 Địa chỉ IP (tiếp )  Supernetting: Classless Inter-Domain Routing (CIDR) addressing: ◊ Toàn bộ vùng địa chỉ IP được chia thành các segment được đặc trưng bởi một tiền tố (prefix) Khái niệm ◊ TD: 128.9.0.0/16 thể hiện một segment với vùng địa chỉ từ 128.9.0.0 – 128.9.255.255 (2^16 địa chỉ) Địa chỉ IP 128.9.0.0 Internet 142.12.0.0/19 Protocol 65.0.0.0/8 128.9.0.0/16 Các giao thức khác 0 232-1 216 Định tuyến 128.9.17.1 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 26 13
  14. Địa chỉ IP (tiếp )  Supernetting (tiếp ): Đường đi đến một địa chỉ IP xác định các router định tuyến dựa trên nguyên tắc “longest prefix match” TD: địa chỉ IP 128.9.17.1 thuộc về mạng nào trong các mạng sau: ◊ 128.9.16.0/20 Khái niệm ◊ 128.9.16.0/21 ◊ 128.9.24.0/21 128.9.16.0/21 Địa chỉ IP 128.9.24.0/21 Internet Protocol 128.9.16.0/20 128.9.176.0/20 Các giao 128.9.0.0/16 thức khác 0 232-1 Định tuyến 128.9.17.1 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 27 Địa chỉ IP (tiếp ) Supernetting (tiếp ): Cho phép nhóm nhiều segment con Khái niệm thành một segment lớn hơn Mục đích của supernetting: Địa chỉ IP ◊Tiết kiệm vùng địa chỉ Internet ◊Giảm số bản ghi trong bảng định tuyến Protocol Chú ý: supernetting chỉ được phép khi Các giao thức khác tất cả các segment con cùng nằm trên một hướng Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 28 14
  15. Địa chỉ IP (tiếp )  Supernetting (tiếp ): Thí dụ: tại bảng định tuyến của R1 /22 Khái niệm 128.9.16.0/22 = 10000000 00001001 00010000 00000000 128.9.20.0/22 = 10000000 00001001 00010100 00000000 Địa chỉ IP 128.9.24.0/22 = 10000000 00001001 00011000 00000000 128.9.28.0/22 = 10000000 00001001 00011100 00000000 Internet 128.9.16.0/20 Protocol R1 R2 /20 Các giao 128.9.16.0/22 4 thức khác 128.9.32.0/20 3 128.9.20.0/22 1 1 2 2 3 Định tuyến 128.9.48.0/20 128.9.28.0/22 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 29 Địa chỉ IP (tiếp )  Mối liên hệ giữa giao thức định tuyến và phương thức đánh địa chỉ: Khái niệm Các giao thức định tuyến chỉ hỗ trợ phương thức đánh địa chỉ có phân lớp (classful Địa chỉ IP addressing): RIP-1 (Routing Information Protocol) Internet Các giao thức định tuyến hỗ trợ đánh địa chỉ Protocol không phân lớp: RIP-2, OSPF (Open Shortest Các giao Path First), EIGRP (Enhanced Interior Gateway thức khác Routing Protocol), IS-IS Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 30 15
  16. Liên hệ giữa địa chỉ MAC và địa chỉ IP  Trong mạng vật lý, các trạm trao đổi dữ A 223.1.1.1 liệu thông qua các 223.1.2.1 khung lớp MAC IP 223.1.1.2 datagram được đóng 223.1.1.4 223.1.2.9 Khái niệm gói vào MAC frame B  A B: 223.1.2.2 A gửi 1 gói IP với địa 223.1.1.3 223.1.3.27 E Địa chỉ IP chỉ nguồn là IP addr. của A, đia chỉ đích là 223.1.3.1 223.1.3.2 đia chỉ IP của B Internet Protocol Gói IP được đóng vào một khung MAC với địa chỉ nguồn là Các giao A’s MAC addr, địa thức khác chỉ đích là B’s MAC addr Làm thế nào để A biết Thông thường A chỉ địa chỉ MAC của B? Định tuyến biết địa chỉ IP của B CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 31 Liên hệ giữa địa chỉ MAC và địa chỉ IP (tiếp ) MAC frame IP datagram B’s MAC A’s MAC B’s IP addr A’s IP addr IP payload Khái niệm addr addr frame frame IP IP Địa chỉ IP dest. addr src addr dest. addr src. addr  Giao thức ARP (Address Resolution Protocol): Để tìm địa Internet Protocol chỉ MAC tương ứng với một địa chỉ IP cho trước Mỗi nút mạng (máy trạm, router) đều chạy giao thức ARP Các giao Lưu giữ bảng ARP (ARP table): ánh xạ giữa địa chỉ IP và địa thức khác chỉ MAC {IP addr., MAC addr., TTL} TTL: thời gian sống của một bản ghi (thông thường 20 phút) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 32 16
  17. Liên hệ giữa địa chỉ MAC và địa chỉ IP (tiếp )  A B: IP: 223.1.1.1 1: A kiểm tra địa chỉ IP của B nhận ra B nằm trong cùng A MAC: 1A-23-F9-CD-06-9B một LAN với A 2: A tìm địa chỉ MAC của B IP: 223.1.1.4 trong bảng ARP (tương ứng với địa chỉ IP của B) MAC: 88-B2-F2-54-1A-0F 3: nếu tìm thấy: A đóng gói IP Khái niệm vào khung MAC với địa chỉ B MAC nguồn của A và địa chỉ MAC đích của B IP: 223.1.1.3 E 4: nếu không tìm thấy: A MAC: 5C-66-AB-90-75-B1 Địa chỉ IP quảng bá bản tin ARP request F 5 với địa chỉ MAC đích là địa chỉ - quảng bá (FF-FF-FF-FF-FF-FF) 3 A Internet kèm theo địa chỉ IP của máy - cần tìm B 60 Protocol - 5: Các máy trạm trong LAN EF nhận được bản tin ARP - B request. Chỉ B trả lời bằng bản 2 Các giao 6: A nhận được bản tin ARP reply từ - tin ARP reply tới A có chứa B cập nhật bảng ARP, gửi gói IP A thức khác địa chỉ MAC của B trong khung MAC 1 223.1.2.2 IP: IP: MAC: Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 33 Liên hệ giữa địa chỉ MAC và địa chỉ IP (tiếp )  A E: IP: 223.1.1.1 1: A kiểm tra địa chỉ IP của B MAC: 1A-23-F9-CD-06-9B nhận ra B nằm trên mạng A khác (LAN2) quyết định gửi gói tới default router (R1) IP: 223.1.1.4 2: A tìm địa chỉ MAC của R1 MAC: 88-B2-F2-54-1A-0F trong bảng ARP (tương ứng Khái niệm với địa chỉ IP của B) LAN2 3: nếu tìm thấy: A đóng gói IP B vào khung MAC với địa chỉ R1 MAC đích là R1 IP: 223.1.1.3 E Địa chỉ IP 4: nếu không tìm thấy: A MAC: 5C-66-AB-90-75-B1 quảng bá bản tin ARP request F 5 với địa chỉ MAC đích là địa chỉ LAN1 - 3 quảng bá (FF-FF-FF-FF-FF-FF) A LAN3 - Internet kèm theo địa chỉ IP của máy 60 Protocol cần tìm R1 - 5: Các máy trạm trong LAN EF - nhận được bản tin ARP B 2 Các giao request. Chỉ R1 trả lời bằng 7: R1 nhận được khung MAC từ - A thức khác bản tin ARP reply tới A có A lấy gói IP, tìm chặng tiếp theo 1 chứa địa chỉ MAC của R1 để gửi gói (LAN2) 223.1.2.2 6: A nhận được bản tin ARP 8: R1 lại thực hiện cơ chế ARP MAC: MAC: reply từ R1 cập nhật bảng trên LAN 2 như các bước 1 - 6 IP: Định tuyến ARP, gửi gói IP trong khung MAC CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 34 17
  18. Liên hệ giữa tên miền và địa chỉ IP  Tên miền – Domain Name System Là một hệ thống đặt tên cho máy trạm, dịch vụ, router, các loại tài nguyên khác nhau trêm mạng Mục đích: dễ nhớ và thuận tiện ◊ Địa chỉ mạng tên miền (domain name) Khái niệm ◊ Địa chỉ máy trạm tên máy (host name) – mail.hut.edu.vn 202.191.57.199 Đặc điểm của DNS: Địa chỉ IP ◊ Tên máy hoặc tên miền có cấu trúc phân lớp: một tên có thể thuộc về một tên miền cấp cao hơn – mail.hut.edu.vn thuộc về hut.edu.vn Internet Protocol ◊ Những tên miền hay sử dụng: – Theo lĩnh vực: .com, .edu, .net, .gov., .org – Theo địa lý: .us, .vn, .ru, .au, .de Các giao ◊ Tên miền cấp cao nhất được cấp phát bởi ICANN (Internet thức khác Corporation for Assigned Names and Numbers) ◊ Tên miền .vn được cấp phát bởi VNNIC ◊ Một tên miền sẽ tương ứng với một tổ chức duy nhất Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 35 Liên hệ giữa tên miền và địa chỉ IP (tiếp )  Mô hình truy vấn DNS: Client – server Cơ sở dữ liệu tên miền được lưu tại DNS server DNS server Khái niệm ◊ Phân tán ◊ Có cấu trúc phân tầng ◊ Mỗi miền đều có một server gốc Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 36 18
  19. Liên hệ giữa tên miền và địa chỉ IP (tiếp )  Mô hình truy vấn DNS (tiếp ): DNS query: ◊ Ứng dụng gửi một DNS query đến DNS server gần nhất (local DNS server) – TD: fpt.vn web browser gửi DNS server về địa chỉ IP của www.wikipedia.org ◊ DNS server kiểm tra, nếu không có thông DNS reply Khái niệm tin cần tìm thì sẽ chuyển tiếp DNS query (IP address) đến DNS server cấp cao hơn .v.v. ◊ Khi nhận được DNS reply, ứng dụng lưu giữ địa chỉ IP trong cache. Địa chỉ IP  Phương thức gửi bản tin DNS query: Linux/Unix: host [tên miền] Internet Windows: nslookup [tên miền] sales.fpt.vn test.fpt.vn rd.fpt.vn Protocol C/C++: gethostbyname() TD: host vnexpress.net DNS query (host1.rd.fpt.vn) Các giao  Chú ý: DNS có thể được sử dụng với thức khác nhiều mục đích – TD: cân bằng tải: cùng với một DNS query – DNS server có thể trả lời với các địa chỉ IP khác Định tuyến nhau CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 37 Network Address Translation  Khái niệm: NAT (Network Address Translation) là phương thức ánh xạ địa chỉ IP private thành địa chỉ IP public, cung cấp sự trao đổi số liệu trong suốt giữa các host.  Ví dụ: Khái niệm Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến 19
  20. NAT (tiếp ) Phân loại: Static NAT Khái niệm Dynamic NAT Địa chỉ IP NPAT: phổ biến nhất hiện nay, khắc phục được nhược điểm của Dynamic Internet NAT Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 39 NAT (tiếp )  Static NAT: là quá trình ánh xạ 1-1 từ địa chỉ IP private thành địa chỉ IP public. Sử dụng khi số lượng IP trong LAN bằng số lượng NAT-IP. Khái niệm Đơn giản. Địa chỉ IP 192.168.1.2 200.18.123.15 Internet 192.168.1.5 200.18.123.14 Protocol Các giao 192.168.1.6 200.18.123.12 thức khác Định tuyến Trong static NAT, địa chỉ 192.168.1.2 sẽ luôn luôn ánh xạ sang địa chỉ 200.18.123.15 20
  21. NAT (tiếp )  Dynamic NAT: là quá trình ánh xạ một địa chỉ IP private thành một địa chỉ IP public từ một dải các địa chỉ IP đã được đăng kí. Mỗi kết nối từ bên trong muốn ra ngoài sẽ được cung cấp một địa chỉ trong dải. Nếu dải địa chỉ này đã được cấp phát hết thì các kết nối sẽ không thể ra ngoài nữa. Khái niệm 200.18.123.12 (192.168.1.6) 200.18.123.13 (192.168.1.10) Địa chỉ IP 200.18.123.14 (192.168.1.5) 200.18.123.15 (192.168.1.2) 192.168.1.2 200.18.123.15 Internet Protocol 192.168.1.5 200.18.123.14 Các giao thức khác 192.168.1.6 200.18.123.12 Định tuyến Máy tính với địa chỉ IP 192.168.1.2 sẽ chuyển đổi sang địa chỉ đầu tiên chưa được sử dụng trong dải địa chỉ public 200.18.123.10 đến 200.18.123.20 NPAT (tiếp )  NPAT (Network Port Address Translation) các địa chỉ IP trong mạng LAN được dấu dưới một địa chỉ NAT-IP. Mỗi gói tin được gửi ra ngoài bằng địa chỉ NAT-IP và port nguồn được thay thế bằng một cổng nào đó chưa được dùng ở NAT (thường lớn hơn 1204). Khái niệm Khi nhận được gói tin, router sẽ kiểm tra địa chỉ IP và port trong bảng NAT và chuyển nó đến host. Địa chỉ IP tiết kiệm địa chỉ IP thực 192.168.1.2 200.18.123.10:1211 Internet Protocol 192.168.1.5 200.18.123.10:1212 Các giao thức khác 192.168.1.6 200.18.123.10:1213 Định tuyến Các địa chỉ private đều chuyển thành địa chỉ 200.18.123.10 nhưng với các port khác nhau 21
  22. NAT (tiếp ) Công dụng: Các máy bên trong LAN có thể chia sẻ Khái niệm kết nối internet với 1 địa chỉ IP duy nhất của WAN. Địa chỉ IP Dấu tất cả các IP bên trong LAN, tránh Internet sự dòm ngó của các attacker. Protocol Tránh được sự chồng chéo địa chỉ IP. Các giao thức khác Linh hoạt và sự dễ dàng trong quản lý. Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 43 Internet Protocol  IP: Version 4 – hiện tại đang được sử dụng rộng rãi Version 6 – là giao thức của tương lai Khái niệm Phiên bản IP được thể hiện trong trường “version” của IP header Địa chỉ IP Protocol Stack Internet Protocol App TCP Host-to-Host TCP / UDP Data Hdr Các giao Segment thức khác Internetwork IP Data Hdr IP Datagram Định tuyến Network Access CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 44 22
  23. Internet Protocol (tiếp )  Tiếp đầu IP (IP header) IP protocol version 32 bits total datagram length (bytes) header length head. DSCP length ver len (bytes) for “type” of data fragment Khái niệm 16-bit identifier flgs offset fragmentation/ max number time to upper Internet reassembly remaining hops live layer checksum Địa chỉ IP (decremented at 32 bit source IP address each router) 32 bit destination IP address Internet upper layer protocol Protocol to deliver payload to Options (if any) E.g. timestamp, record route data taken, pecify Các giao (variable length, thức khác list of routers typically a TCP to visit. or UDP segment) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 45 Phân mảnh gói tin  Vấn đề: truyền IP datagram qua nhiều mạng với kích thước gói cho phép lớn nhất khác nhau (TD: Ethernet: 1500byte)  Phân mảnh (Fragmentation) Source Destination Khái niệm A B Ethernet MTU=1500 bytes MTU=1500 bytes Địa chỉ IP MTU 0 More Frag=1 thức khác More Frag=0 Data HDR (ID=x) Data HDR (ID=x) Data HDR (ID=x) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 46 23
  24. Phân mảnh gói tin (tiếp )  Việc ghép mảnh (assemble) chỉ được thực hiện ở thiết bị đầu cuối  Nên tránh phân mảnh trong mạng thiết bị đầu Khái niệm cuối có thể ước lượng chiều dài gói nhỏ nhất (Maximum Transmission Unit - MTU) cho phép Địa chỉ IP trên đường đi Bên phát có thể gửi các gói có kích thước khác Internet nhau, không phân mảnh để tìm path MTU Protocol traceroute –F www.hut.edu.vn 1500 Các giao traceroute –F www.hut.edu.vn 1501 thức khác (DF=1 trong IP header; router gửi bản tin “ICMP lỗi”) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 47 Phân mảnh gói tin (tiếp )  Phân mảnh sử dụng các trường: identification, flags, fragment offset Identification: 16 bit - các offset của cùng 1 gói lớn có cùng một ID. Khái niệm Flags: 3 bit ◊ #1 bit: không sử dụng ◊ #2 bit – Don’t fragment (DF) bit: Địa chỉ IP – DF=1: Không được phép phân mảnh – DF=0: Được phép phân mảnh Internet ◊ #3 bit – More fragment (MF) bit: nếu DF=0 Protocol – MF=1: hãy còn phân mảnh tiếp theo – MF=0: phân mảnh cuối cùng Các giao Offset: 13 bit thức khác ◊ Vị trí của gói tin phân mảnh trong gói tin ban đầu ◊ Theo đơn vị 8 bytes Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 48 24
  25. Phân mảnh gói tin (tiếp )  Thí dụ: Khái niệm ID=2356 0 1399 ID=2356 Flag=0.0.0 Flag=0.0.1 Địa chỉ IP Offset=0 Offset = 0/8 = 0 0 1400 2800 3999 1400 2799 ID=2356 Flag=0.0.1 Internet Offset = 1400/8 = 175 Protocol 2800 3999 ID=2356 Các giao Flag=0.0.0 thức khác Offset = 2800/8 = 350 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 49 Các trường khác  Version: 4 bit 4: IPv4 6: IPv6  IHL (Internet Header Length): 4 bit – thể hiện chiều dài của header theo đơn 1 dword (32bit) Khái niệm  DSCP (Differentiated Service Code Point): 8 bit Tên cũ: type of service (TOS) Hiện tại được sử dụng trong quản lý chất lượng dịch vụ Địa chỉ IP (Quality-of-Service: QoS) (TD: các dịch vụ thời gian thực .v.v.) DiffServ (RFC2474) Internet Protocol  ECN (Explicit Congestion Notification): 2 bit – báo hiệu mạng bị tắc nghẽn, chỉ dùng khi thiết bị đầu cuối hộ trợ cơ chế này Các giao thức khác  Total length: 16 bit - Độ dài toàn bộ, tính cả phần đầu Tính theo bytes Max: 65536 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 50 25
  26. Các trường khác (tiếp )  TTL (Time-To-Live): 8 bit – “thời gian sống” Độ dài đường đi gói tin có thể đi qua Max: 255 Khái niệm Router giảm TTL đi 1 đơn vị khi nhận và chuyển tiếp gói tin Gói tin bị hủy nếu TTL bằng 0 Địa chỉ IP  Protocol: 8 bit – cho biết các giao thức được đóng Internet gói vào IP datagram: Protocol Giao thức tầng host-to-host: TCP (6), EGP (8), IGP (9), UDP (17), OSPF (89), SCTP (132) Các giao Giao thức tầng internetworking: ICMP (1), IGMP (2), IP thức khác (IP in IP) (4) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 51 Các trường khác (tiếp ) Header Checksum: 16 bit – Kiểm tra lỗi cho header Khái niệm Options: Địa chỉ IP Độ dài thay đổi, có thể lên đến 40 byte Được sử dụng để thêm các chức năng Internet Protocol mới Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 52 26
  27. ICMP  ICMP – Internet Control Message Protocol  RFC 792  ICMP được sử dụng ở tầng mạng để trao đổi thông tin Báo lỗi: báo gói tin không đến được một máy trạm, số chặng vượt quá giới hạn cho phép (TTL=0), kích thước Khái niệm gói tin quá dài .v.v. Thông tin phản hồi  Định dạng bản tin ICMP: Type, Code, cùng với 8 bytes đầu Địa chỉ IP tiên của gói tin IP bị lỗi Internet Type Code Checksum Protocol Rest of the header Các giao thức khác Data Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 53 ICMP (tiếp )  Một số dạng bản tin ICMP: Type Code description 0 0 echo reply (ping) 3 0 dest. network unreachable Khái niệm 3 1 dest host unreachable 3 2 dest protocol unreachable 3 3 dest port unreachable Địa chỉ IP 3 6 dest network unknown 3 7 dest host unknown Internet 4 0 source quench (congestion Protocol control - not used) 8 0 echo request (ping) Các giao 9 0 route advertisement thức khác 10 0 router discovery 11 0 TTL expired Định tuyến 12 0 bad IP header CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 54 27
  28. ICMP (tiếp )  Ping: Sử dụng để kiểm tra kết nối Khái niệm Gửi gói tin “ICMP echo request” Bên nhận trả về “ICMP echo reply” Địa chỉ IP Mỗi gói tin có một số hiệu gói tin Trường dữ liệu chứa thời gian gửi gói tin Internet Protocol ◊ Tính được thời gian đi và về - RTT (round-trip time) Cú pháp: ping [địa chỉ IP/tên host] Các giao thức khác ◊ ping www.google.com Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 55 ICMP (tiếp )  Traceroute Tìm đường đi (các router trung gian) từ nguồn tới đích Cú pháp: ◊ Linux: traceroute [địa chỉ IP/tên host] ◊ Windows: tracert [địa chỉ IP/tên host] Khái niệm C:\Documents and Settings\tnh>tracert www.jaist.ac.jp Tracing route to www.jaist.ac.jp [150.65.5.208] over a maximum of 30 hops: Địa chỉ IP 1 1 ms <1 ms <1 ms 192.168.1.1 2 15 ms 14 ms 13 ms 210.245.0.42 3 13 ms 13 ms 13 ms 210.245.0.97 4 14 ms 13 ms 14 ms 210.245.1.1 Internet 5 207 ms 230 ms 94 ms pos8-2.br01.hkg04.pccwbtn.net [63.218.115.45] 6 * 403 ms 393 ms 0.so-0-1-0.XT1.SCL2.ALTER.NET [152.63.57.50] Protocol 7 338 ms 393 ms 370 ms 0.so-7-0-0.XL1.SJC1.ALTER.NET [152.63.55.106] 8 402 ms 404 ms 329 ms POS1-0.XR1.SJC1.ALTER.NET [152.63.55.113] 9 272 ms 288 ms 310 ms 193.ATM7-0.GW3.SJC1.ALTER.NET [152.63.49.29] Các giao 10 205 ms 206 ms 204 ms wide-mae-gw.customer.alter.net [157.130.206.42] 11 427 ms 403 ms 370 ms ve-13.foundry2.otemachi.wide.ad.jp [192.50.36.62] thức khác 12 395 ms 399 ms 417 ms ve-4.foundry3.nezu.wide.ad.jp [203.178.138.244] 13 355 ms 356 ms 378 ms ve-3705.cisco2.komatsu.wide.ad.jp [203.178.136.193] 14 388 ms 398 ms 414 ms c76.jaist.ac.jp [203.178.138.174] 15 438 ms 377 ms 435 ms www.jaist.ac.jp [150.65.5.208] Định tuyến Trace complete. CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 56 28
  29. ICMP (tiếp )  Traceroute (tiếp ): Bên gửi truyền gói tin cho bên nhận ◊ Gói thứ nhất có TTL =1 ◊ Gói thứ 2 có TTL=2, Khi gói tin thứ n đến router thứ n: Khái niệm ◊ Router hủy gói tin ◊ gửi một gói tin ICMP (type 11, code 0) Địa chỉ IP ◊ có chứa tên và địa chỉ IP của router khi nhận được gói tin trả lời, bên gửi sẽ tính ra RTT Internet Khi nguồn nhận được gói tin ICMP này sẽ dừng lại Protocol Mỗi gói tin lặp lại 3 lần Các giao thức khác 3 probes 3 probes Định tuyến 3 probes CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 57 Tổng quan về định tuyến  “Bản đồ Internet” 1999: Khái niệm Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến Nguồn: CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 58 29
  30. Tổng quan về định tuyến (tiếp )  “Bản đồ Internet” 2006: Khái niệm Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến Nguồn: CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 59 Tổng quan về định tuyến (tiếp )  Số bản ghi trong bảng định tuyến tại mạng lõi Internet Nguồn: Khái niệm Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 60 30
  31. Tổng quan về định tuyến (tiếp )  Phân bố các bản ghi 100000 80000 Khái niệm 60000 40000 Địa chỉ IP 20000 Internet Numberentries of Protocol 0 Các giao 8 12 16 20 24 thức khác Prefix length (bits) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 61 Tổng quan về định tuyến (tiếp )  Vấn đề: A B A B Khái niệm R2 Địa chỉ IP R3 Internet Protocol R1 Các giao thức khác R1 chọn chặng tiếp R4 theo đi đến B ntn? Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 62 31
  32. Tổng quan về định tuyến (tiếp )  Bảng định tuyến (routing table) : Bảng định tuyến nằm trong các router Khái niệm Cho phép với một địa chỉ mạng đích thì phải gửi gói tin ra giao diện mạng nào của router Địa chỉ IP Bảng định tuyến được tạo ra do các router trao đổi bản tin định tuyến thông qua các giao thức Internet định tuyến (routing protocols) Protocol Nguyên lý định tuyến của router: “longest Các giao thức khác prefix match” Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 63 Tổng quan về định tuyến (tiếp )  Bảng định tuyến (tiếp ) dest. net. mask next hop interface metrics Khái niệm network 10.0.0.0 255.255.255.0 A’ IP addr. 1 1 Địa chỉ IP 172.16.0.0 255.255.255.0 C’ IP addr. 2 1 Internet Protocol Router A Router B Router C 10.0.0.0/24 1 2 172.16.0.0/24 Các giao thức khác 3 10.0.0.0/24 192.168.0.0/24 172.16.0.0/24 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 64 32
  33. Tổng quan về định tuyến (tiếp )  Mục tiêu: Tìm đường đi ngắn nhất từ một nút gốc tới các nút còn lại xây dựng cây theo đường ngắn nhất (shortest path tree - SPT) Các thuật toán xây dựng cây SPT: Khái niệm ◊ Thuật toán Bellman-Ford distance vector routing (RIP, IGRP) ◊ Thuật toán Dijkstra link state routing (OSPF) Địa chỉ IP  Câu hỏi: Sự khác nhau giữa cây bắc cầu tối thiểu (Minimum Internet Spanning Tree) và cây theo đường ngắn nhất? Protocol Tại sao nguyên tắc định tuyến trong Internet lại tuân theo cây SPT? Các giao thức khác  Chú ý: Xem lại môn “Cơ sở truyền số liệu” để hiểu chi tiết về lý thuyết định tuyến Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 65 Tổng quan về định tuyến (tiếp ) Các giao thức định tuyến: Các giao thức định tuyến nội miền Khái niệm (Intra-AS routing): ◊OSPF, RIP-1, RIP-2 Địa chỉ IP ◊IS-IS, EIGRP, IGRP Internet Các giao thức định tuyến liên miền Protocol (Inter-AS routing): Các giao thức khác ◊BGP Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 66 33
  34. Tổng quan về định tuyến (tiếp )  Cho R8 là nút gốc, tìm đường đi ngắn nhất từ R8 đến các nút còn lại Khái niệm Địa chỉ IP R 1 1 4 1 R2 R4 R6 Internet 2 2 3 Protocol 2 R7 3 R5 2 Các giao R 4 thức khác 3 R8 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 67 Thuật toán Bellman-Ford phân tán  1: Gọi Xn=(C1,C2, ,C7) là các khoảng cách từ Ri R8 (i=1 - 7), n – số bước lặp  2: X0=(,  ) Khái niệm  3: Router i gửi Xk tới các nút hàng xóm của i theo chu kỳ T vector khoảng cách (distance vector) Địa chỉ IP  4: Nếu router i nhận được bản tin với khoảng cách Ci nhỏ hơn khoảng cách hiện tại Ri cập Internet nhật X . Protocol n  5: Lặp lại bước 3 cho đến khi Xn+1=Xn Các giao thức khác  6: Dừng Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 68 34
  35. Thuật toán Bellman-Ford phân tán (tiếp ) n=1    R 1 1 4  1 R2 R4 R6 2 3 2 2 3 Khái niệm R7 R5 2  R 4 3  R8 Địa chỉ IP  0   n=2 R1 Inf Internet 1 1  4 R1 2 Protocol R2 Inf R2 R4 R6 R 3 4, R8 2 3 2 2 Các giao R 4 Inf 3 thức khác R7 R5 2 3 R5 2, R8 R3 4 2 R R6 2, R8 8 Định tuyến 4 0 R7 3, R8 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 69 Thuật toán Bellman-Ford phân tán (tiếp ) 6 4 6 R1 6, R 1 1 3 R 4 2 1 R2 R4 R6 R2 4, R 5 2 3 R 2 3 4, R8 2 R 3 4 6, R7 R7 R5 2 3 R5 2, R Khái niệm 8 R 4 2 3 R8 R6 2, R 8 4 0 R7 3, R Địa chỉ IP 8 5 4 n=3 R1 5, R 2 5 Internet R 1 1 2 R 1 R R R Protocol 2 4, R5 2 4 6 R 3 4, R8 2 2 Các giao R4 5, R 2 3 thức khác R7 R5 2, R R 2 8 5 3 R R R 4 2 6 2, 8 3 R8 Định tuyến R 7 3, R8 4 0 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 70 35
  36. Thuật toán Bellman-Ford phân tán (tiếp )  Nhận xét: Các bản tin DS được gửi theo chu kỳ, không phụ thuộc vào trạng thái đường truyền Khái niệm  Các vấn đề: Địa chỉ IP Số bước lặp của thuật toán? (thuật toán sẽ chạy bao lâu) Internet Protocol Thuật toán có luôn hội tụ hay không (n< )? Điều gì sẽ xảy ra khi một nút/liên kết bị hỏng Các giao thức khác hoặc khi khoảng cách thay đổi? Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 71 Thuật toán Bellman-Ford phân tán (tiếp )  Tính khoảng cách đến R4: 1 1 1 R1 R2 R3 R4 Khái niệm Bước lặp Địa chỉ IP R1 R2 R3 0 3,R 2,R 1, R 2 3 4 R3 R4 hỏng Internet Protocol 1 3,R2 2,R3 3,R2 3,R 4,R 3,R Các giao 2 2 3 2 thức khác 3 5,R2 4,R3 5,R2 “Counting to infinity” Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 72 36
  37. Thuật toán Bellman-Ford phân tán (tiếp ) Khắc phục vấn đề phân kỳ của Bellman-Ford (counting to infinity Khái niệm problem): Đặt số bước tối đa, TD: C <16 Địa chỉ IP i “Split horizon”: Do R2 nhận được Internet Protocol khoảng cách nhỏ nhất từ R3, R2 không gửi giá của mình đến R3 nữa Các giao thức khác “Split horizon with poison reverse”: R2 gửi khoảng cách  tới R Định tuyến 3 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 73 Thuật toán Dijkstra Router gửi bản tin cập nhật khi liên kết nối với nó thay đổi trạng thái Khái niệm bản tin “Link State Advertisement” (LSA) Địa chỉ IP Dựa vào bản tin cập nhật, mỗi router Internet Protocol tự tính khoảng cách nhỏ nhất từ Các giao chính nó đến tất cả các router khác thức khác sử dụng thuật toán Dijkstra Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 74 37
  38. Thuật toán Dijkstra (tiếp )  Cơ chế quảng bá trong Dijkstra: Gói tin trạng thái liên kết (Link State Packet - LSP) bao gồm: ◊ ID của router Ri gửi bản tin LSP ◊ Danh sách các hàng xóm của Ri cùng với khoảng cách Khái niệm tương ứng từ Ri ◊ Số thứ tự ◊ TTL Địa chỉ IP Khi router Rj nhận được bản tin LSP: ◊ Nếu số thứ tự chỉ ra bản tin mới nhất gửi LSP trên tất các các giao diện còn lại (quảng bá) Internet Protocol ◊ Nếu không hủy gói tin Các router gửi bản tin “hello” đến các nút hàng xóm Các giao nhận biết được trạng thái kênh truyền thức khác  Xây dựng cây SPT: Dựa trên bản tin LSA các router tự xây dựng cây Định tuyến SPT dựa trên thuật toán Dijkstra CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 75 Thuật toán Dijkstra (tiếp ) Bước {S} P(R1), P(R2), P(R3), P(R4), P(R5), P(R6), P(R7), d(R1) d(R2) d(R3) d(R4) d(R5) d(R6) d(R7) 0 R8   4, R8  2,R8 2,R8 3,R8 1 R8,R5  4,R5 4,R8  - 2,R8 3,R8 Khái niệm 2 R8,R5,R6  4,R5 4,R8 6,R6 - - 3,R8 3 R8,R5,R6,R7 4,R5 4,R8 6,R6 - - - Địa chỉ IP  4 R8,R5,R6,R7,R2 5,R2 - 4,R8 5,R2 - - - Internet Protocol 5 R8,R5,R6,R7,R2,R3 5,R2 - - 5,R2 - - - Các giao 6 R8,R5,R6,R7,R2,R3,R1 - - - 5,R2 - - - thức khác 7 R8,R5,R6,R7,R2,R3,R1,R4 - - - - - - - Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 76 38
  39. Thuật toán Dijkstra (tiếp ) 2 n=0 R8 n=1 R5 0 R8 0 R Khái niệm 6 n=2 R6 2 n=3 2 2 Địa chỉ IP R5 2 R7 3 R8 R5 0 R8 Internet 0 Protocol 1 1 R1 Các giao R2 R4 R6 thức khác 2 n=7 2 2 R7 3 R5 R 4 Định tuyến 3 R8 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 77 So sánh Bản tin định tuyến: Kích thước Khái niệm Số lượng bản tin trao đổi Địa chỉ IP Lượng thông tin cần lưu tại router Internet Độ ổn định (khi các bản tin bị lỗi) Protocol Thời gian hội tụ Các giao thức khác Gợi ý: trong LS có hiện tượng “counting-to-infinity” không? Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 78 39
  40. So sánh (tiếp )  Bản tin định tuyến: Kích thước: ◊ DV: lớn (gửi toàn bộ thông tin về kết nối từ 1 router tới tất cả các router khác) Khái niệm ◊ LS: nhỏ (chỉ có thông tin từ 1 router tới các router hàng xóm của nó) Địa chỉ IP Số lượng bản tin trao đổi ◊ DV: ít (chỉ gửi đến các nút hàng xóm) Internet ◊ LS: nhiều (quảng bá tới toàn mạng) Protocol  Lượng thông tin cần lưu tại router: Các giao DV: chỉ lưu giữ trạng thái các router hàng thức khác xóm LS: lưu giữ đồ hình toàn mạng Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 79 So sánh (tiếp )  Độ ổn định: DV: 1 router có thể gửi các bản tin với khoảng cách không đúng tới các hàng xóm lan ra toàn mạng LS: 1 router có thể quảng bá các bản tin LSA không Khái niệm đúng/lỗi cho toàn mạng ◊ Tuy nhiên các router khác vẫn có thể xây dựng được đồ hình mạng dựa vào các bản tin LSA tới từ các router khác Địa chỉ IP  Thời gian hội tụ: DV: các bản tin DV được gửi có chu kỳ, không phụ Internet thuộc vào trạng thái đường truyền thời gian hội tụ Protocol lâu, ngoài ra có thể tạo vòng lặp (routing loop) (nhớ lại giải pháp split horizon!) Các giao LS: các bản tin LSA được gửi chỉ khi trạng thái đường thức khác truyền thay đổi thời gian hội tụ nhanh hơn Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 80 40
  41. Định tuyến trong mạng Internet  Internet thực hiện định tuyến có phân tầng (hierarchical routing): Khái niệm Internet được phân thành các hệ tự trị - AS (Autonomous System) Địa chỉ IP Mỗi AS do được quản trị riêng biệt bởi các quản trị mạng Internet Protocol Trong một AS: sử dụng một giao thức định tuyến nội miền (interior gateway protocol) Các giao thức khác Giữa các AS: sử dụng giao thức định tuyến liên miền (exterior gateway protocol) Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 81 Định tuyến trong mạng Internet (tiếp ) Exterior Gateway Protocol (BGP ) 3a Khái niệm 2a 1c Địa chỉ IP 1b 3c 3a 2c Internet 3b 2a Protocol AS3 2b 1c AS2 1a Các giao 1b AS1 thức khác 1d Định tuyến Interior Gateway Protocol (OSPF, RIP) CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 82 41
  42. EGP và IGP AS2 AS1 IGP EGP OSPF domain Khái niệm EGP Địa chỉ IP RIP domain EGP EGP Internet AS4 EGP IGP AS3 Protocol IGP RIP domain IGP Các giao OSPF domain thức khác RIP domain AS5 Định tuyến RIP domain CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 83 Hệ tự trị  Mỗi hệ tự trị có một số hiệu riêng – AS number (ASN - 16 bits hay 32 bits) Khái niệm 2914 NTT-COMMUNICATIONS-2914 - NTT America, Inc. Địa chỉ IP 3491 BTN-ASN - Beyond The Network America, Inc. 4134 CHINANET-BACKBONE No.31,Jin-rong Street Internet 6453 GLOBEINTERNET Teleglobe America Inc. Protocol 24087 VNGT-AS-AP Vietnam New Generation Telecom 24066 VNNIC-AS-VN Vietnam Internet Network Information Center Các giao thức khác 17981 CAMBOTECH-KH-AS ISP Cambodia . Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 84 42
  43. Hệ tự trị (tiếp )  ASN được cấp phát bởi IANA (Internet Assigned Numbers Authority) Khái niệm Source: Địa chỉ IP Internet Protocol Các giao thức khác 2008 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 85 Định tuyến nội vùng Intra-AS routing = Interior Gateway Routing (IGP) Khái niệm Các giao thức định tuyến nội vùng thông dụng: Địa chỉ IP RIP (Routing Information Protocol) Internet OSPF (Open Shortest Path First) Protocol IGRP (Interior Gateway Routing Các giao thức khác Protocol) – Chỉ sử dụng cho các router của Cisco Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 86 43
  44. RIP  Đặc điểm: RIP – Routing Information Protocol Là giao thức định tuyến theo vector khoảng Khái niệm cách – sử dụng thuật toán Bellman-Ford phân tán Địa chỉ IP Được phát triển lần đầu dưới hệ điều hành BSD Unix năm 1982 Internet Protocol Trước đây được sử dụng rộng rãi, hiện nay ít được sử dụng Các giao thức khác Khoảng cách là số chặng tới mạng đích Số chặng tối đa: 15 chặng Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 87 RIP (tiếp )  Trao đổi thông tin: Định kỳ ◊ Các vector khoảng cách được trao đổi định kỳ - 30s ◊ Mỗi thông điệp chứa tối đa 25 mục ◊ Trong thực tế, nhiều thông điệp được sử dụng Sự kiện Khái niệm ◊ Gửi thông điệp cho nút hàng xóm mỗi khi có thay đổi ◊ Nút hàng xóm sẽ cập nhật bảng chọn đường của nó  Các bộ đếm thời gian: Địa chỉ IP Update timer ◊ Dùng để trao đổi thông tin cứ 30s Invalid timer Internet ◊ Khởi tạo lại mỗi khi nhận được thông tin chọn đường Protocol ◊ Nếu sau 180s không nhận được thông tin -> trạng thái hold-down Hold down timer Các giao ◊ Giữ trạng thái hold-down trong 180s thức khác ◊ Chuyển sang trạng thái down Flush timer ◊ Khởi tạo lại mỗi khi nhận được thông tin chọn đường Định tuyến ◊ Sau 240s, xóa mục tương ứng trong bảng chọn đường CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 88 44
  45. RIP (tiếp ) no update update update ↓ ↓ ↓ When it is timeout, hold down timer starts Invalid timer Khái niệm When it is timeout, This info will be deleted from RIP database Địa chỉ IP When it receives update, Hold down timer Invalid timer restarts Internet Protocol Flush timer Các giao thức khác When it is timeout, Routing info will be deleted from routing table Định tuyến 0 30 60 90 120 150 180 210 240 270 300 330 360 390 420 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 89 RIP (tiếp )  RIP RIPv1: chỉ hỗ trợ định tuyến trong các mạng đánh địa chỉ IP có phân lớp (classful) Khái niệm ◊ Bản tin cập nhật: thông tin mạng đích, khoảng cách tới mạng đích Địa chỉ IP RIPv2: hỗ trợ định tuyến trong cả mạng đánh Internet địa chỉ không phân lớp (classless) Protocol ◊ Bản tin cập nhật: thông tin mạng đích, subnet mask của mạng đích, khoảng cách tới mạng đích Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 90 45
  46. OSPF  Đặc điểm: OSPF – Open Shortest Path First Thông tin về trạng thái liên kết - LSA (link Khái niệm state advertisement) được quảng bá trên toàn AS Địa chỉ IP Với các AS lớn: OSPF được phân cấp thành nhiều miền OSPF nhỏ Internet Protocol Các router sử dụng thuật toán Dijkstra để thiết lập bảng định tuyến Các giao thức khác Khoảng cách (giá): 100Mbps/dung lượng kênh Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 91 OSPF (tiếp ) Phân vùng trong OSPF: Trong việc chọn đường, tại sao phải Khái niệm chia mạng thành các vùng nhỏ hơn? Nếu có quá nhiều router Địa chỉ IP ◊Thông tin trạng thái liên kết được truyền nhiều lần hơn Internet Protocol ◊Phải liên tục tính toán lại ◊Cần nhiều bộ nhớ hơn, nhiều tài nguyên Các giao CPU hơn thức khác ◊Lượng thông tin phải trao đổi tăng lên Định tuyến ◊Bảng chọn đường lớn hơn CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 92 46
  47. OSPF (tiếp ) boundary router Gb Area border router backbone router Ga Khái niệm Backbone Gc Địa chỉ IP 3c 2c Internet 3a Protocol 3b 1c 2a AS3 2b AS2 Các giao 1a thức khác 1b 1d AS1 Định tuyến internal router CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 93 OSPF (tiếp )  ABR - Area border routers: Quản lý 1 vùng và kết nối đến các vùng khác Khái niệm  ASBR - Autonomous system boundary router: Nối đến các AS khác Địa chỉ IP  BR - backbone routers: thực hiện OSPF Internet routing trong vùng backbone Protocol  Internal Router – Thực hiện OSPF bên Các giao thức khác trong một vùng Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 94 47
  48. RIP và OSPF – So sánh RIP OSPF Đặc điểm • Router bình đẳng • Phân câp • Cấu hình dễ dàng • Cấu hình phức tạp • Mạng cỡ nhỏ • Mạng cỡ vừa và lớn Khái niệm Khả năng mở rộng Không Có Địa chỉ IP Độ phức tạp tính toán Nhỏ Lớn Hội tụ Chậm Nhanh Internet Bảng chọn đường Trạng thái liên kết Protocol Trao đổi thông tin Giải thuật Distant vector Link-state Các giao thức khác Cập nhật hàng xóm 30s 10s (Hello packet) Đơn vị chi phí Số nút mạng Băng thông Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 95 Định tuyến liên miền  BGP (Border Gateway Protocol): giao thức định tuyến liên miền thông dụng nhất hiện nay BGP-4 Khái niệm  Vấn đề nảy sinh trong định tuyến liên miền: Đồ hình: mạng Internet có đồ hình phức tạp, không cấu trúc Địa chỉ IP Tính tự trị của các AS: các AS định nghĩa khoảng cách hoặc giá khác nhau khó tìm được đường đi thực sự Internet Protocol tối ưu Độ tin cậy (trust): một số AS không muốn gửi lưu lượng Các giao của mình tới một số AS xác định thức khác Chính sách (policy): Mỗi AS có một chính sách định tuyến khác nhau Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 96 48
  49. Quan hệ khách hàng – nhà cung cấp  Khách hàng (customer) – Nhà cung cấp (provider)  Khách hàng trả tiền cho nhà cung cấp Internet để được truy nhập vào mạng Khái niệm Địa chỉ IP provider Internet Protocol provider customer IP traffic Các giao thức khác customer Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 97 Quan hệ khách hàng – nhà cung cấp (tiếp ) Khái niệm Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến provider customer IP traffic CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 98 49
  50. Quan hệ khách hàng – nhà cung cấp (tiếp ) Khái niệm Địa chỉ IP Internet Protocol peer peer -Lưu lượng thường được trao đổi giữa các AS theo quan hệ provider – provider customer Các giao customer thức khác - Các AS cùng cấp không mong muốn traffic traffic NOT trao đổi lưu lượng (khi không có hợp đồng trao đổi lưu lượng) Định tuyến allowed allowed CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 99 BGP  Đặc điểm: Không sử dụng phương thức vector khoảng cách và trạng thái kênh truyền sử dụng Khái niệm vector đường dẫn (path vector) ◊ Cho phép một AS biết được thông tin đi đến AS khác ◊ BGP trao đổi các bản tin path vector: AS_PATH Địa chỉ IP Gửi thông tin này vào bên trong AS đó Xác định đường đi tốt nhất dựa trên thông tin Internet Protocol đó và các chính sách chọn đường Cho phép thiết lập các chính sách Các giao ◊ Chọn đường ra thức khác ◊ Quảng bá các đường vào Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 100 50
  51. BGP (tiếp )  eBGP và iBGP: External BGP vs. Internal BGP Phân tán thông tin chọn đường Khái niệm 1. 3a gửi tới 1c bằng eBGP 2. 1c gửi thông tin nội bộ tới (1b, 1d, ) trong AS1 bằng iBGP 3. 2a nhận thông tin từ 1b bằng eBGP Địa chỉ IP eBGP session Internet 3c Protocol iBGP session 3a 2c 3b 2a Các giao AS3 2b 1c thức khác AS2 1a 1b 1d Định tuyến AS1 CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 101 BGP (tiếp ) Áp dụng chính sách định tuyến với BGP: Khái niệm Khi các router gửi và nhận thông tin chọn đường: Địa chỉ IP ◊BGP có thể đặt các chính sách Internet – Cho đường vào Protocol – Cho đường ra Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 102 51
  52. BGP (tiếp ) Các bản tin BGP: Open: Thiết lập một phiên BGP giữa 2 Khái niệm router. Địa chỉ IP Keep Alive: Bắt tay theo chu kỳ. Internet Notification: Hủy bỏ phiên BGP sau khi Protocol trao đổi thông tin. Các giao thức khác Update: cập nhật các tuyến mới hoặc Định tuyến hủy bỏ các tuyến cũ CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 103 BGP (tiếp )  Bản tin cập nhật: chứa các thuộc tính của tuyến  Thuộc tính của tuyến: được sử dụng để chọn đường tối ưu khi có nhiều tuyến cùng đi đến một Khái niệm đích ORIGIN Địa chỉ IP ◊ Nguồn của thông tin (IGP/EGP/incomplete) AS_PATH Internet NEXT_HOP Protocol MED (MULTI_EXIT_DISCRIMINATOR) LOCAL_PREF Các giao thức khác ATOMIC_AGGREGATE AGGREGATOR Định tuyến COMMUNITY CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 104 52
  53. BGP (tiếp )  Các mức ưu tiên khi chọn tuyến Enforce relationships Highest Local Preference E.g. prefer customer routes Khái niệm over peer routes Địa chỉ IP Shortest ASPATH Lowest MED Internet traffic engineering Protocol i-BGP < e-BGP Lowest IGP cost Các giao to BGP egress thức khác Lowest router ID Throw up hands and Định tuyến break ties CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 105 BGP (tiếp ) 135.207.0.0/16 AS 1129 AS Path = 1755 1239 7018 6341 Global Access AS 1755 135.207.0.0/16 135.207.0.0/16 AS Path = 1239 7018 6341 Ebone AS Path = 1129 1755 1239 7018 6341 Khái niệm AS 12654 AS 1239 RIPE NCC 135.207.0.0/16 Địa chỉ IP Pick shorter RIS project Sprint AS Path = 7018 6341 AS path Internet 135.207.0.0/16 AS 7018 AS Path = 3549 7018 6341 Protocol 135.207.0.0/16 AS Path = 6341 AT&T Các giao AS 6341 AS 3549 thức khác 135.207.0.0/16 AT&T Research AS Path = 7018 6341Global Crossing 135.207.0.0/16 Định tuyến Prefix Originated CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 106 53
  54. Các giao thức định tuyến  Các giao thức định tuyến được thực hiện ở lớp mấy? BGP và RIP được truyền tải qua TCP (lớp Khái niệm ứng dụng) ◊RIP: Địa chỉ IP – UDP port: 520 Internet ◊BGP: Protocol – TCP port: 179 OSPF được truyền tải trực tiếp trong gói tin Các giao thức khác IP ◊Protocol type: 89 Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 107 Các thuật toán tìm bản ghi trong bảng định tuyến Các vấn đề liên quan đến tìm bản ghi trong bảng định tuyến (table Khái niệm lookup): Trong đánh địa chỉ có phân lớp: Địa chỉ IP ◊“Exact prefix match”: hashing Internet Protocol Trong đánh địa chỉ không phân lớp: “longest prefix match”: Các giao thức khác ◊Binary trie ◊Patricia tree Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 108 54
  55. Các thuật toán tìm bản ghi trong bảng định tuyến (tiếp )  Đặt vấn đề: Số bản ghi trong bảng định tuyến trong mạng lõi Internet tăng theo hàm mũ Khái niệm Phân bố chiều dài của network prefix (CIDR) thay đổi bất kỳ Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến Số bản ghi trong router lõi Phân bố độ dài network prefix trong (Nguồn: router lõi CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 109 Các thuật toán tìm bản ghi trong bảng định tuyến (tiếp ) Đặt vấn đề (tiếp ): Router lõi tiếp nhận luồng bit có tốc độ Khái niệm Gbit/s, cần phải gửi khoảng 1 triệu gói/s/port tốc độ xử lý nhanh Địa chỉ IP Bảng định tuyến thay đổi liên tục: Internet ◊100 lần/s vài chục ms phải cập nhật Protocol bảng định tuyến 1 lần Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 110 55
  56. Các thuật toán tìm bản ghi trong bảng định tuyến (tiếp )  Yêu cầu: Các bản ghi trong bản định tuyến phải được sắp xếp sao cho: ◊ Cập nhật các bản ghi (table entry) nhanh và dễ dàng Khái niệm ◊ Tốc độ tìm kiếm nhanh (table lookup) ◊ Kích thước bộ nhớ chứa bảng định tuyến nhỏ Địa chỉ IP ◊ Thích hợp với cơ chế đánh địa chỉ không phân lớp (classless addressing - CIDR) “longest prefix match” Internet  Gọi: Protocol W: Độ dài của địa chỉ IP ◊ IPv4: W=32 Các giao N: Số bit địa chỉ mạng (prefix) thức khác ◊ Trong CIDR: N thay đổi Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 111 Các thuật toán tìm bản ghi trong bảng định tuyến (tiếp ) Các thuật toán lookup (longest prefix match) cho CIDR: Khái niệm ◊Binary trie ◊Patricia tree Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 112 56
  57. Thí dụ Xét bảng định tuyến: dest. network (bin.)/subnet mask next hop a: 0/1 b: 01000/5 Khái niệm c: 011/3 d: 1/1 e: 100/3 Địa chỉ IP f: 1100/4 g: 1101/4 Internet h: 1110/4 Protocol i: 1111/4 Các giao Địa chỉ mạng: thức khác  P1 = 010011110  P2 = 111000110 thuộc về prefix nào ở bảng trên? Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 113 Thí dụ (tiếp ) Giải đáp: P1 = 010011110 a Khái niệm P2 = 111000110 h Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 114 57
  58. Binary Trie a: 0 0 1 P1 = 010011110 b: 01000 (1) a (0) d c: 011 0 1 1 d: 1 0 0 e: 100 1 0 (100) f: 1100 1 e 0 1 Khái niệm 1 g: 1101 0 (1100) (1101) c (011) f g h: 1110 0 h h i: 1111 Địa chỉ IP (1110) (1111) 0 (01000) Internet b Protocol  Nút mức L thể hiện chiều dài L bit  Các prefix trong bảng định tuyến được đánh dấu bằng nút màu thẫm Các giao  Thuật toán tìm kiếm: thức khác Đi theo cây nhị phân theo nhánh phù hợp Ghi nhớ nút prefix vừa đi qua (a) Đi cho tới khi không gặp nút phù hợp nữa thì dừng prefix cuối cùng đi qua là bản Định tuyến ghi thích hợp CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 115 Binary Trie (tiếp ) Đánh giá hiệu năng của thuật toán Binary Trie: Khái niệm Địa chỉ IP Internet Protocol Các giao thức khác Định tuyến CHƯƠNG 4 – KẾT NỐI MẠNG INTERNET PGS. TS. Nguyễn Hữu Thanh 116 58
  59. Bài tập  Bài tập 1: Cho bảng định tuyến tại router R1 R1 sẽ gửi gói đến mạng nào khi nhận được các gói tin có địa chỉ đích như sau: ◊ 192.138.32.1 ◊ 192.138.32.100 dest. network/subnet mask next hop 192.138.32.0/26 10.1.1.1 192.138.32.0/24 10.1.1.2 192.138.32.0/19 10.1.1.3 Bài tập (tiếp )  Bài tập 2: Công ty A xây dựng một mạng LAN bao gồm 1000 host được nhóm theo kiểu supernet. Trước tiên quản trị mạng của công ty này phải yêu cầu ISP B cung cấp một dải địa chỉ IP thuộc lớp C.Công ty A có thể chọn một vài địa chỉ nằm trong dải sau: ◊ Lựa chọn 1 gồm 5 địa chỉ: dải 200.1.15.0, 200.1.16.0, 200.1.17.0, 200.1.18.0, 200.19.0. ◊ Lựa chọn 2 gồm 5 địa chỉ: 215.3.31.0, 215.3.32.0, 215.3.33.0, 215.3.34.0, 215.3.35.0 Hãy trình bày cách thực lựa chọn địa chỉ và tìm supernet mask tương ứng 59
  60. Bài tập (tiếp ) Bài tập 3: Cho một mạng cục bộ thuộc công ty A được phân địa chỉ 220.130.15.0. Mạng này được chia thành 7 mạng nhỏ: ◊Mạng thứ nhất và 2 có 62 host. ◊Mạng thứ 3 và 4 có 30 host ◊Mạng thứ 5, 6, 7 mỗi mạng có14 host Hãy thiết kế mạng này. Tài liệu tham khảo  Internetworking with TCP/IP, Vol 1, Douglas Comer, Prentice Hall Computer  Networking: a top-down approach featuring the Internet, James F. Kurose, Keith W. Ross, Addison Wesley, 4thed, 2006  Computer Networks, Andrew S. Tanenbaum, Prentice Hall, 4th Edition  Computer Networks, Nick McKeown, Stanford University  M. Sanchez, E. Biersack, and W. Dabbous, "Survey and Taxonomy of IP address lookup algorithms," IEEE Network, 15(2):8-23, 2001.  M. Waldvogel, G. Varghese, J. Turner, and B. Plattner, “Scalable High Speed IP Routing Lookups,” Proc. ACM SIGCOMM ’97, Sept. 1997, pp.25–36. 60