Bài giảng Mạng máy tính - Chương 4: Tầng mạng

134 trang huongle 8160

Download

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

bai_giang_mang_may_tinh_chuong_4_tang_mang.pdf

Nội dung text: Bài giảng Mạng máy tính - Chương 4: Tầng mạng

Mạng máy tính Bộ môn Kỹ thuậtmáytínhvàMạng Khoa Công nghệ Thông tin ĐạihọcSư phạmHàNội 1-1
Chương 4: Tầng mạng Mục đích: Hiểu các nguyên tắc bên trong dịch vụ tầng mạng: Chọn đường Vấn đề quy mô Cách làm việccủaRouter Các chủđềnâng cao: IPv6, mobility Ví dụ và cài đặt trong Internet 1-2
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-3
Tầng mạng Chuyển segment từ host gửitới host nhận application transport network Bên gửi đóng gói data link network physical network data link network segment thành các data link physical data link physical physical datagram network data link physical network Bên nhậnchuyểncác data link segment tớitầng giao vận physical network network data link Các giao thứctầng mạng data link physical physical có trong mọi host, router network data link application physical transport Router kiểmtratrường network data link header trong mọiIP physical datagram chuyển qua nó 1-4
Chứcnăng chính củatầng mạng Chuyểntiếp: chuyển Liên hệ: các gói tin từđầuvào router sang đầura Dẫn đường: Quá trình thích hợpcủa router lậpkế hoạch chuyến đi từ nguồn đến đích Dẫn đường: xác định đường đicủa gói tin từ Chuyểntiếp: Quá trình nguồntới đích. xử lý qua một điểm đơn Các thuật toán dẫn đường 1-5
Ảnh hưởng giữachọn đường và chuyểntiếp Thuật toán dẫn đường Bảng chuyểntiếpcụcbộ Giá trị header Đường ra 0100 3 0101 2 0111 2 1001 1 Giá trị trong header của gói tin đến 0111 1 3 2 1-6
Thiếtlậpkếtnối Chứcnăng quan trọng thứ 3 trong mộtsố kiếntrúcmạng: ATM, frame relay, X.25 Trướcluồng datagram, hai host và các router ở giữathiếtlậpmộtkếtnối ảo Router tham gia Dịch vụ tầng mạng và tầng giao vận: Tầng mạng: giữa hai host Tầng giao vận: giữahaitiếntrình 1-7
Mô hình dịch vụ mạng Q: Mô hình dịch vụ nào cho kênh truyền các datagram từ bên gửitới bên nhận? Ví dụ các dịch vụ cho từng Ví dụ các dịch vụ cho một datagram: luồng datagram: Truyền đảmbảo Chuyển datagram đúng Truyền đảmbảo độ trễ thứ tự nhỏ hơn 40 msec Đảmbảotốc độ tối thiểucholuồng Hạnchế sự thay đổi khoảng cách giữacác gói tin 1-8
Các mô hình dịch vụ củatầng mạng Đảmbảo? Kiếntrúc Mô hình Phảnhồi mạng dịch vụ Bandwidth Mất gói Thứ tự Thờigiantắcnghẽn Internet best effort none Không Không Không Không (suy ra từ loss) ATM CBR tốc độ Có Có Có Không hằng số tắcnghẽn ATM VBR tốc độ Có Có Có Không đảmbảo tắcnghẽn ATM ABR đảmbảo Không Có Không Có mứctốithiểu ATM UBR none Không Có Không Không 1-9
Chương 4: Tầng mạng 4. 1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-10
Dịch vụ hướng kếtnối và không hướng kếtnốicủatầng mạng Mạng datagram cung cấpdịch vụ không hướng kếtnối ở tầng mạng Mạng VC cung cấpdịch vụ hướng kếtnối ở tầng mạng Tương tự vớicácdịch vụ củatầng giao vận, nhưng: Dịch vụ: host tớihost Không cho phép chọn: Mạng cung cấp datagram hoặcVC Cài đặt: trong phầnlõi 1-11
Virtual circuit “Đường đitừ nguồntới đích giống như mạng điệnthoại” Hiệunăng tốt Sự kiệnmạng theo đường đitừ nguồntới đích Thiếtlậpmỗicuộcgọitrướckhidữ liệucóthể truyền Mỗi gói tin mạng một định danh VC (không phải địachỉ host đích) Mọi router trên đường đitừ nguồntới đích duy trì trạng thái cho mỗikếtnối đi qua Tài nguyên router, đường truyền (bandwidth, vùng đệm) cấp phát cho VC 1-12
Cài đặtVC Một VC bao gồm: 1. Đường đitừ nguồntới đích 2. VC number, mộtsố cho mỗi đường truyềndọc đường đi 3. Điểm vào trong bảng chuyểntiếp trong router trên đường đi Gói tin thuộcvề VC mạng số VC. Số VC phảithayđổitrênmỗi đường truyền. Số VC mớitừ bảng chuyểntiếp 1-13
Bảng chuyểntiếp Số VC 12 22 32 1 3 2 Bảng chuyểntiếp Số giao diện của router phía trên bên trái: Giao diện đếnVC # đếnGiaodiện điVC # đi 1 12 2 22 2 63 1 18 3 7 2 17 1 97 3 87 Các Router duy trì thông tin trạng thái kếtnối! 1-14
Virtual circuit: Giao thức báo hiệu Sử dụng để thiếtlập, duy trì, chấmdứtVC Sử dụng trong ATM, frame-relay, X.25 Không sử dụng trong Internet hiệnnay application 6. Nhậndữ liệu application transport 5. Luồng dữ liệubắt đầu transport network 4. Cuộcgọi đượckếtnối 3. Chấpnhậncuộcgọi network data link 1. Khởi đầucuộcgọi 2. Cuộc gói đến data link physical physical 1-15
Mạng datagram Không thiếtlậpcuộcgọitạitầng mạng Router: không có trạng thái về các kếtnối end-to-end Không có khái niệmmứcmạng về kếtnối Các gói tin chuyểntiếpsử dụng địachỉ củahost đích Các gói tin cùng cặp địachỉ nguồn-đích có thểđi theo các đường khác nhau application application transport transport network network data link 1. Gửidữ liệu 2. Nhậndữ liệu data link physical physical 1-16
Bảng chuyểntiếp 4 tỷđiểmvào Dải địa chỉ đích Giao diện đường truyền 11001000 00010111 00010000 00000000 tới 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 tới 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 tới 2 11001000 00010111 00011111 11111111 trường hợp khác 3 1-17
Tương ứng tiềntố dài nhất Prefix Match Giao diện đường truyền 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 Trường hợp khác 3 Ví dụ DA: 11001000 00010111 00010110 10100001 Giao diện? DA: 11001000 00010111 00011000 10101010 Giao diện? 1-18
Mạng datagram hay mạng VC Internet ATM Dữ liệutraođổigiữa các máy tính Phát triểntừđiệnthoại Dịch vụ co giãn, không yêu Cuộc nói chuyệncủa con cầuthờigianchặtchẽ. người: Các hệ thống cuối “thông minh” Yêu cầuthời gian, độ tin (máy tính) cậychặtchẽ Có thể thích nghi, thựchiện Cần đảmbảodịch vụ điềukhiển, khôi phụclỗi Hệ thống cuối không cần “thông Bên trong mạng đơngiản, minh” phía rìa ngoài mạng phứctạp Điệnthoại Nhiềukiểu đường truyền Sự phứcnằm bên trong Đặc điểm khác nhau mạng Dịch vụ không thống nhất 1-19
Chương 4: Tầng mạng 4. 1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-20
Tổng quan về kiếntrúccủa Router Hai chứcnăng chính củarouter Chạy các giao thức/thuật toán chọn đường (RIP, OSPF, BGP) Chuyểntiếp các datagram từđường truyền vào sang đường truyền ra 1-21
Chứcnăng củacổng vào Tầng vậtlý: nhậnmứcbít Tầng liên kếtdữ liệu: Chuyểntiếp không tập chung: ví dụ: Ethernet Dựavàocủa datagram, tìm kiếmcổng ra sử dụng bảng chuyểntiếp trong bộ nhớ chi tiết trong chương 5 cổng vào Mục đích: xử lý cổng vào vớitốc độ của đường truyền Xếp hàng: Nếu các datagram đến nhah hơntốc độ chuyểntiếp vào trong switch fabric 1-22
Ba kiểu switch fabric 1-23
Chuyểnmạch qua bộ nhớ Router thế hệđầutiên: Các máy tính truyềnthống chuyểnmạch dướisự điềukhiểntrựctiếpcủaCPU Các gói tin được sao chép vào trong bộ nhớ củahệ thống Tốc độ bị hạnchế bởi bandwidth củabộ nhớ (2 lần truy nhậpbus đốivớimỗi datagram) Cổng vào Bộ nhớ Cổng ra Bus hệ thống 1-24
Chuyểnmạch qua bus Datagram từ bộ nhớ cổng vào chuyển sang bộ nhớ cổng ra thông qua bus dùng chung Cạnh tranh bus: tốc độ chuyểnmạch bị giới hạnbởi bandwidth củacủa bus Bus 1 Gbps, Cisco 1900: tốc độ đủ cho các router doanh nghiệp (khác router cho vùng, mạng backbone) 1-25
Chuyểnmạch qua mạng kếtnối Giảiquyếthạnchế vấn đề bandwidth củabus Mạng Banyan, mạng các kếtnối ban đầu được phát triển để kếtnối các processor trong multiprocessor Thiếtkế tiên tiến: phân mảnh các datagram thành các cell có độ dài cốđịnh, chuyểnmạch các cell qua fabric. Cisco 12000: chuyểnmạch Gbps qua mạng kếtnối 1-26
Cổng ra Đệm khi datagram đến fabric nhanh hơntốc độ truyền Nguyên tắclậplịch chọn các datagram đang xếp hàng để truyền 1-27
Xếphàngtạicổng ra Đệmkhitốc độ đến qua switch vượt quá tốc độ đường ra Xếp hàng (trễ) và mấtgóibởivìvùngđệmcủacổng ra bị tràn! 1-28
Xếp hàng ở cổng vào Fabric chậmhơncổng vào -> xếp hàng có thể xảyraở hàng đợi cổng vào Head-of-the-Line (HOL) blocking: các datagram xếp hàng tạitrước hàng đợingăn không cho datagram khác chuyểntiếp Độ trễ và mất gói khi xếp hàng bởi vì tràn vùng đệm vào! 1-29
Chương 4: Tầng mạng 4. 1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-30
Tầng mạng của Internet Chứcnăng tầng mạng của host, router: Tầng giao vận: TCP, UDP Giao thứcIP Giao thứcdẫn đường •Quy tắc đánh địachỉ •Chọn đường •Định dạng datagram •RIP, OSPF, BGP Tầng •Quy tắc điềukhiểngóitin mạng Bảng chuyểntiếp Giao thứcICMP •Thông báo lỗi •Báo hiệucủa router Tầng liên kếtdữ liệu Tầng vậtlý 1-31
Chương 4: Tầng mạng 4. 1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-32
Định dạng IP datagram Số phiên bản 32 bits củagiaothứcIP tổng chiềudài Chiều dài header type of của datagram ver head. (byte) len service length (byte) “kiểu” dữ liệu fragment 16-bit identifier flgs để phân offset mảnh/ Số hop tối đacònlại time to upper Internet ghép phân (giảmtạimỗi router) live layer checksum mảnh 32 bit địachỉ IP nguồn 32 bit địachỉ IP đích Giao thứccủatầng trên để chuyển payload Tùy chọn Ví dụ: timestamp, Overhead củaTCP? dữ liệu bảnghiđường 20 byte củaTCP (chiều dài thay đổi, đi thường là mộtTCP (danh sách 20 byte củaIP hoặc UDP segment) các router đi = 40 byte + qua) Overhead của tầng ứng dụng 1-33
Phân mảnh và ghép phân mảnh IP datagram Liên kếtmạng có MTU (kích thướctruyềntối đa) – frame mứcliênkếtdữ liệulớnnhấtcó thể. Phân mảnh: Các kiểu liên kết khác nhau, Vào: một datagram lớn MTU khác nhau Ra: 3 datagram nhỏ hơn Sự phân mảnh IP datagram: Một datagram thành nhiều datagram Ghép phân mảnh Chỉ ghép lạitại đích Sử dụng thông tin trong IP header để xác định, xếpthứ tự các phân mảnh 1-34
Sự phân mảnh và ghép phân mảnh IP datagram length ID fragflag offset Ví dụ =4000 =x =0 =0 Datagram: 4000 Một datagram lớn chia thành byte nhiều datagram nhỏ hơn MTU = 1500 byte length ID fragflag offset =1500 =x =1 =0 1480 bytes in data field length ID fragflag offset =1500 =x =1 =185 offset = 1480/8 length ID fragflag offset =1040 =x =0 =370 1-35
Chương 4: Tầng mạng 4. 1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-36
Địachỉ IP Địachỉ IP: 32-bit định 223.1.1.1 danh cho giao diệncủa 223.1.2.1 223.1.1.2 host, router 223.1.1.4 223.1.2.9 Giao diện: kếtnốigiữa 223.1.2.2 host/router và liên kết 223.1.1.3 223.1.3.27 vậtlý Thông thường, router có nhiềugiaodiện 223.1.3.1 223.1.3.2 host có thể có nhiều giao diện Địachỉ IP gán cho mỗi giao diện 223.1.1.1 = 11011111 00000001 00000001 00000001 223 111 1-37
Subnet Địachỉ IP: 223.1.1.1 Phần subnet (các bít 223.1.2.1 223.1.1.2 phần cao) 223.1.1.4 223.1.2.9 Phần host (các bít phần thấp) 223.1.2.2 223.1.1.3 223.1.3.27 Khái niệm subnet ? LAN Giao diệncủathiếtbị mà địachỉ IP có cùng 223.1.3.1 223.1.3.2 phần subnet Có thể kếtnốivới không không cần thông qua router Mạng chứa 3 subnet 1-38
223.1.1.0/24 Subnet 223.1.2.0/24 Công thức Để xác định các subnet, tách giao diệncủahost hoặcrouter, tạomạng cô lập. Mỗimạng cô lập gọilàmột subnet. 223.1.3.0/24 Subnet mask: /24 1-39
Subnet 223.1.1.2 Số subnet ? 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 1-40
Địachỉ IP: CIDR CIDR: Classless InterDomain Routing Phần địachỉ subnet có độ dài tùy ý Định dạng địachỉ: a.b.c.d/x, trong đóx làsố bít củaphần subnet trong địachỉ Phần Phần subnet host 11001000 00010111 00010000 00000000 200.23.16.0/23 1-41
Địachỉ IP: Cách gán địachỉ IP? Q: Cách để host có địachỉ IP? Khai báo bởingườiquảntrị Windows: Control Panel->Network->Configuration- >TCP/IP->Properties UNIX: /etc/rc.config DHCP: Dynamic Host Configuration Protocol: lấy địa chỉ IP động từ server 1-42
Địachỉ IP: Cách gán địachỉ IP? Q: Cách xác định subnet từđịachỉ IP? A: Tính dựa vào phầnkhônggianđịachỉđược cấp Khốicủ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 1-43
Địachỉ phân cấp: Gửikếttập Địachỉ phân cấp cho phép thông báo hiệuquả thông tin dẫn đường: Tổ chức0 200.23.16.0/23 Tổ chức1 “Gửi cho tôi gói tin có địachỉ bắt đầubằng 200.23.18.0/23 200.23.16.0/20” Tổ chức2 . 200.23.20.0/23 . Fly-By-Night-ISP . . . Internet Tổ chức7 . 200.23.30.0/23 “Gửi cho tôi gói tin có địachỉ bắt đầubằng ISPs-R-Us 199.31.0.0/16” 1-44
Địachỉ phân cấp ISPs-R-Us có hơnmột đường đitớitổ chức1 Tổ chức0 200.23.16.0/23 “Gửi cho tôi gói tin có địachỉ bắt đầubằng 200.23.16.0/20” Tổ chức2 . 200.23.20.0/23 . Fly-By-Night-ISP . . . Internet Tổ chức7 . 200.23.30.0/23 “Gửi cho tôi gói tin có địachỉ bắt đầubằng ISPs-R-Us 199.31.0.0/16 Tổ chức1 hoặc 200.23.18.0/23” 200.23.18.0/23 1-45
Địachỉ IP: Các thông tin khác Q: Cách ISP nhận địachỉ? A: ICANN: Internet Corporation for Assigned Names and Numbers Cấp phát địachỉ Quản lý DNS Gán tên miền, trả lờiyêucầuDNS 1-46
NAT: Network Address Translation Phầncònlạicủa Mạng cụcbộ Internet 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ấtcả các datagram rời mạng cụcbộ Các datagram với nguồnhoặc đích có cùng địachỉ NAT IP nguồnlà: trong mạng có địachỉ 10.0.0/24, 138.76.29.7, địachỉ nguồn/đích khác nhau về giá trị cổng nguồn có giá trị như bình thường 1-47
NAT: Network Address Translation Động cơ mạng cụcbộ sử dụng 1 địachỉ IP: Không cần đượccấpphátdải địachỉ từ ISP: một địachỉ IP cho tấtcả mọithiếtbị Có thể thay đổi địachỉ củathiếtbị trong mạng cụcbộ không cần thông báo vớithế giới bên ngoài Có thể thay đổi ISP không cầnthayđổi địachỉ củacác thiếtbị trong mạng cụcbộ Các thiếtbị trong mạng cụcbộ không có địachỉ rõ ràng đốivớithế giới bên ngoài (bảomậthơn) 1-48
NAT: Network Address Translation Thựchiện: NAT router phải: Các datagram ra ngoài: thay thế (địachỉ IP nguồn, port #) củamọi datagram ra ngoài thành (địachỉ NAT IP, port # mới) . . . Client/server ở xa sẽ trả lờisử dụng (địachỉ NAT IP, port # mới) là địachỉđích. Ghi nhớ (trong bảng phiên dịch NAT) mọicặp(địachỉ IP nguồn, port #) thành (địachỉ NAT IP, port # mới) Các datagram đi vào: thay thế (địachỉ NAT IP, port # mới) trong trường địachỉđích củamọi datagram đivào bằng (địachỉ IP nguồn, port #) tương ứng (chứa trong bảng phiên dịch NAT) 1-49
NAT: Network Address Translation Bảng phiên dịch NAT 1: host 10.0.0.1 2: NAT router Địachỉ phía WAN Địachỉ phía LAN thay đổi địachỉ nguồn gửi datagram tới 138.76.29.7, 5001 10.0.0.1, 3345 của datagram từ 128.119.40, 80 10.0.0.1, 3345 thành 138.76.29.7, 5001, S: 10.0.0.1, 3345 cậpnhậtbảng 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: Trả lời đến địachỉđích: thay đổi địachỉđích của datagram 138.76.29.7, 5001 từ 138.76.29.7, 5001 thành 10.0.0.1, 3345 1-50
NAT: Network Address Translation Trường giá trị cổng 16-bit: 60,000 kếtnối đồng thời qua một địachỉđơnphía LAN! Tranh luậnvề NAT: Các router chỉ nên xử lý tớitầng 3 Vi phạmthamsố end-to-end • NAT có thể phảichúý bởingườithiếtkếứng dụng, ví dụ: ứng dụng P2P Địachỉ ngắn nên được thay bằng IPv6 1-51
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-52
ICMP: Internet Control Message Protocol Sử dụng bởi host và router để Type Code Mô tả giao tiếp thông tin mứcmạng 0 0 echo reply (ping) Thông báo lỗi: không thấy 3 0 dest. network unreachable host, mạng, cổng, giao thức 3 1 dest host unreachable Echo request/reply (sử dụng 3 2 dest protocol unreachable trong lệnh ping) 3 3 dest port unreachable Tầng mạng trên IP: 3 6 dest network unknown Bản tin ICMP đượcchứa 3 7 dest host unknown trong IP datagram 4 0 source quench (congestion control - not used) Bản tin ICMP: type, code, 8 byte 8 0 echo request (ping) đầutiêncủa IP datagram gây ra 9 0 route advertisement lỗi 10 0 router discovery 11 0 TTL expired 12 0 bad IP header 1-53
Traceroute và ICMP Phía nguồngửimột Khi bản tin ICMP tới, chuỗi các UDP segment nguồn tính RTT đến đích Traceroute thựchiện3 Đầu tiên có TTL =1 lần Thứ hai có TTL=2, Điềukiệndừng Khi datagram thứ n tới UDP segment cuối router thứ n: cùng đếnhost đích Router loạibỏ datagram Đích trả về gói tin ICMP Và gửitới nguồnmộtbản tin ICMP (type 11, code “host unreachable” 0) (type 3, code 3) Bản tin bao gồmtêncủa Khi nguồnnhận gói tin router và địachỉ IP ICMP này -> dừng 1-54
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-55
IPv6 Mục đích ban đầu: Không gian địachỉ 32-bit sớmcấp phát hết Mục đích khác: Định dạng của header giúp tăng tốcxử lý và chuyển tiếp gói tin Thay đổi header để hỗ trợ QoS Định dạng của IPv6 datagram: Header có độ dài cốđịnh 40 byte Không cho phép phân mảnh 1-56
IPv6 Header Priority: Xác định mức ưutiêngiữa các datagram trong luồng Flow Label: xác định datagram trong cùng luồng Next header: xác định giao thứctầng trên 1-57
Các thay đổikhácso vớiIPv4 Checksum: loạibỏ hoàn toàn để giảmthời gian xử lý tạimỗi hop Options: cho phép, nhưng ngoài header, chỉ định bởitrường “Next Header” ICMPv6: phiên bảnmớicủaICMP Thêm các kiểubảntin mới, ví dụ “Packet Too Big” Chứcnăng quản lý nhóm multicast 1-58
Chuyểntừ IPv4 sang IPv6 Tấtcả các router không thể nâng cấp đồng thời Cách để mạng có thể hoạt động vớicả router IPv4 và IPv6? Tunneling: IPv6 là payload trong IPv4 datagram giữa các IPv4 router 1-59
Tunneling A B E F Góc nhìn lôgíc: tunnel IPv6 IPv6 IPv6 IPv6 A B C D E F Góc nhìn vậtlý: 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 dữ liệu Dest: F Dest: F dữ liệu dữ liệu dữ liệu A-to-B: E-to-F: B-to-C: B-to-C: IPv6 IPv6 IPv6 trong IPv6 trong IPv4 IPv4 1-60
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-61
Ảnh hưởng giữadẫn đường và chuyểntiếp Thuật toán dẫn đường Bảng chuyểntiếpcụcbộ Giá trị header Đường truyềnra 0100 3 0101 2 0111 2 1001 1 Giá trị trong header của gói tin đến 0111 1 3 2 1-62
Trừutượng hóa mạng bằng đồ thị 5 v 3 w 2 5 u 2 1 3 z 1 x y 2 Đồ thị: G = (N,E) 1 N = Tập các router = { u, v, w, x, y, z } E = Tập các liên kết ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Chú ý: Sự trừutượng hóa bằng đồ thị thích hợp trong nhiềungữ cảnh khác củamạng Ví dụ: P2P, N là tập các peer và E là tậpcáckếtnốiTCP 1-63
Trừutượng hóa mạng bằng đồ thị: chi phí 5 • c(x,x’) = chi phí của liên kết (x,x’) -vídụ: c(w,z) = 5 v 3 w 2 5 • cost có thể luôn là 1 u 2 1 z 3 hoặc liên quan tới bandwidth 1 hoặc liên quan tớitắc nghẽn x y 2 1 Chi phí của đường đi(x1, x2, x3, , xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) Câu hỏi: Đường đi có chi phí ít nhấtgiữau vàz? Thuậttoándẫn đường: thuật toán tìm đường đicóchi phíthấpnhất 1-64
Phân loạithuậttoándẫn đường Thông tin thống nhất hay không Tĩnh hay động? tập chung? Tĩnh (static): Thông tin thống nhất (Global): Các router thay đổichậm theo Tấtcả các router có topology, chi thờigian phí liên kết đầy đủ Động (dynamic): Các thuật toán “link state” Các router thay đổi nhanh hơn Thông tin không tập chung Cậpnhật định kỳ (decentralized): Phảnhồi khi chi phí liên kết Router biết các hàng xóm có kết thay đổi nốivậtlývới nó, chi phí liên kết tới hàng xóm Quá trình lặp tính toán, trao đổi thông tin với các hàng xóm Các thuật toán “distance vector” 1-65
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-66
Thuật toán dẫn đường Link-State Thuật toán Dijkstra Chú thích: Mọi nút đềubiết topology của c(x,y): chi phí liên kếttừ nút x mạng, chi phí của liên kết tới nút y; = ∞ nếu không là hàng Thựchiệnbằng “link state xóm trựctiếp broadcast” D(v): giá trị hiệntạicủa chi phí Mọi nút có thông tin giống đường đitừ nguồntới đích v nhau p(v): nút trướccủa v trong Tính toán đường đicóchi phí đường đitừ nguồntớiv thấpnhấttừ một nút (nguồn) tới N': tập các nút mà đường đicó tấtcả các nút khác. chi phí thấpnhất đãxácđịnh Cho kếtquả là bảng chuyển tiếp của nút đó Lặp: sau k vòng lặp, biết đường đi có chi phí thấpnhấttớik đích 1-67
Thuật toán Dijsktra 1 Khởitạo: 2 N' = {u} 3 for 4 if 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Lặp 9 Tìm w không trong N' thỏa mãn D(w) nhỏ nhất 10 Thêm w vào N' 11 CậpnhậtD(v) vớimọiv kề với w và không trong N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* Chi phí mớitới v là chi phí cũ tớiv hoặc là chi phí đường đi 14 ngắnnhấttớiw đãbiếtcộng với chi phí từ w tớiv */ 15 Tớikhimọi nút trong N' 1-68
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 3 z 1 x y 2 1 1-69
Thuật toán Dijkstra: thảoluận Độ phứctạpcủathuật toán: n nút Mỗi vòng lặp: cầnkiểmtramọi nút, w, không trong N n(n+1)/2 lần so sánh: O(n2) Cài đặtcóthể hiệuquả hơn: O(nlogn) Trường hợp không ổn định: Ví dụ: chi phí liên kết= lượng lưulượng đã mang 1 A A A A 1+e 2+e 0 0 2+e 2+e 0 D B 0 0 D 1+e 1 B D 0 0 B D 1+e 1 B 0 e 0 0 1 1+e 0 e C C C C 1 1 e tínhlại tínhlại tínhlại Khởi đầu đường đi 1-70
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-71
Thuật toán Distance Vector (1) Công thức Bellman-Ford (quy hoạch động) Định nghĩa dx(y) := chi phí của đường đi chi phí thấpnhấttừ x tớiy Thì dx(y) = min {c(x,v) + dv(y) } Trong đó, min được tính vớitấtcả các hàng xóm củax 1-72
Ví dụ Bellman-Ford (2) 5 Dễ thấy, dv(z) = 5, dx(z) = 3, dw(z) = 3 v 3 w 2 5 u 2 1 Công thứcB-F: 3 z 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 Nút đạt giá trị nhỏ nhất là next hop trong đường đi ngắn nhất ➜ bảng chuyển tiếp 1-73
Thuật toán Distance Vector (3) Dx(y) = chi phí thấpnhấttừ x tớiy Distance vector: Dx = [Dx(y): y є N ] Nút x biết chi phí tớimỗihàngxómv: c(x,v) Node x duy trì Dx = [Dx(y): y є N ] Node x cũng duy trì các distance vector của các hàng xóm củanó Đốivới hàng xóm v, x duy trì Dv = [Dv(y): y є N ] 1-74
Thuật toán Distance vector (4) Ý tưởng: Mỗinútđịnh kỳ gửi tính toán distance vector củanó tới các hàng xóm Khi nút x nhậntínhtoánDV mớitừ hàng xóm, nó cập nhậtDV củanósử dụng công thứcB-F: Dx(y) ← minv{c(x,v) + Dv(y)} với mỗi y ∊ N Ước lượng Dx(y) hội tụ tới chi phí thấp nhất thực tế của dx(y) 1-75
Thuật toán Distance Vector (5) Lặp, không đồng bộ: Mỗi Mỗinút: vòng lặp cục bộ thực hiện khi: Chi phí liên kết cục bộ thay đợi for (thay đổi chi phí liên đổi kết cục bộ, bản tin từ hàng Bản tin cập nhật DV từ hàng xóm) xóm Phân tán: tính lại Mỗi nút thông báo cho hàng xóm chỉ khi DV của nó thay đổi Nếu DV tới đích nào đó thay Sau đó, các hàng xóm đổi, thông báo cho hàng thông báo cho các hàng xóm xóm của nó nếu cần 1-76
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)} Bảng nút x = min{2+1 , 7+0} = 3 chi phí tới chi phí tới chi phí tới x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 y ∞∞ ∞ y 2 0 1 y ừ ừ t t 2 0 1 ừ z z t ∞∞ ∞ 7 1 0 z 3 1 0 Bảng nút y chi phí tới chi phí tới chi phí tới x y z x y z y x y z 2 1 x ∞ ∞∞ x 0 2 7 x 0 2 3 x z y 2 0 1 y 2 0 1 y 7 ừ t 2 0 1 ừ ừ t t z ∞∞ ∞ z 7 1 0 z 3 1 0 Bảng nút z chi phí tới chi phí tới chi phí tới x y z x y z x y z x ∞∞ ∞ x 0 2 7 x 0 2 3 y y 2 0 1 y 2 0 1 ừ ừ t ∞ ∞∞ t ừ t z z z 71 0 3 1 0 3 1 0 thờigian 1-77
Distance Vector: chi phí liên kết thay đổi Chi phí liên kết thay đổi: 1 Nútpháthiện chi phí liên kếtcụcbộ thay y đổi 4 1 Cậpnhật thông tin dẫn đường, tính lạiDV x z 50 Nếu DV thay đổi, thông báo cho các hàng xóm Tạithời điểm t0, y phát hiện chi phí liên kết thay đổi, cậpnhật DV của nó và thông báo cho hàng xóm của nó. “Tin mới Tạithời điểm t1, z nhậncậpnhậttừ y và cậpnhậtbảng của nó. đi nhanh” Nó tính chi phí thấpnhấtmớitới x và gửiDV củanótớicác hàng xóm của nó. Tạithời điểm t2, y nhậncậpnhậtcủa z và cậpnhậtbảng khoảng cách của nó. Chi phí thấpnhấtcủa y không thay đổivàvìvậyy không gửi bấtkỳ bản tin nào tớiz 1-78
Distance Vector: chi phí liên kết thay đổi Chi phí liên kết thay đổi: 60 Tin mới đi nhanh y 4 Tin xấu đichậm–vấn đề 1 x z “đếmvôhạn”! 50 Kỹ thuật “Poissoned reverse”: Nếu Z qua Y tớiX : Z nói với Y khoảng cách củaZ tới X là vô hạn(vì vậy, Y không dẫn đường tới X qua Z) Giải quyết bài toán “đếmvô hạn”? 1-79
So sánh thuậttoánLS vàDV Sự phứctạpbảntin Tính chịulỗi: Điềugìxảyra LS: n nút, E liên kết, O(nE) khi router bị lỗi? bảntin gửi đi LS: DV: chỉ trao đổigiữa các hàng Nút có thể thông báo chi xóm phí liên kết sai Thờigianhộitụ thay đổi Mỗi nút chỉ tính toán bảng Tốc độ hộitụ củanó LS: Thuật toán O(n2) đòi hỏi DV: O(nE) bảntin Nút có thể thông báo chi Có thể không ổn định phí đường đi sai DV: Thờigianhộitụ thay đổi Mỗibảng củanútsử dụng Có thể dẫn đường lặp bởi nút khác • Lan truyềnlỗi qua mạng Vấn đề “đếmvôhạn” 1-80
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-81
Hierarchical Routing Các nghiên cứudẫn đường trong điềukiệnlý tưởng Mọi router như nhau Mạng ổn định không đúng trong thựctế Co dãn: với 200 triệu đích Quyềntự trị Không thể chứatấtcả các internet = mạng củacácmạng đích trong bảng dẫn đường! Mỗiquảntrị mạng có thể Sự trao đổibảng dẫn đường muốn điềukhiểndẫn đường làm tràn ngập liên kết! trong mạng củahọ 1-82
Hierarchical Routing Kếttập các router thành Gateway router các cùng, “autonomous systems” (AS) Liên kếttrựctiếptới router trong AS khác Các router trong cùng AS chạy cùng giao thức dẫn đường Giao thứcdẫn đường “intra-AS” Các router trong các AS khác nhau có thể chạy các giao thứcdẫn đường intra-AS khác nhau 1-83
KếtnốigiữacácAS 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 Bảng chuyểntiếp được cấuhìnhcả thuậttoán dẫn đường intra-AS và Thuậttoán Thuậttoán inter-AS dẫn đường dẫn đường Intra-AS Inter-AS Intra-AS thiếtlậpcác điểm vào cho các đích Bảng phía trong chuyểntiếp Inter-AS và Intra-As thiết lậpcácđiểm vào cho các đích phía ngoài 1-84
Nhiệmvụ của Inter-AS Giả sử router trong AS1 AS1 cần: nhận datagram có đích 1. Học đích nào thì gửi ngoài AS1 qua AS2, đích nào thì Router nên chuyểntiếp gửi qua AS3 gói tin tới các gateway 2. Lan truyền thông tin router. Câu hỏi: chọn gateway router nào? trên tớimọirouter trong AS1 Công việcdẫn đường inter-AS! 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 1-85
Ví dụ: Thiếtlậpbảng chuyểntiếp trong router 1d Giả sử AS1 họctừ giao thức inter-AS biết rằng subnet x có thể tới đượctừ AS3 (gateway 1c) nhưng không tới đượctừ AS2. Giao thức Inter-AS lan truyền thông tin có thể tớitới các router bên trong Router 1d xác định từ thông tin dẫn đường intra-AS rằng giao diện I là trên đường đicó chi phí thấpnhấttới1c Thêm vào trong bảng chuyểntiếp điểmvào (x,I). 1-86
Ví dụ: ChọngiữacácAS Giả sử AS1 họctừ giao thức inter-AS biếtrằng subnet x có thể tới đượctự AS3 và từ AS2. Để cấuhìnhbảng chuyểntiếp, router 1d phảixácđịnh gateway nó nên chuyểntiếp gói tin gửi đến đích x. Đólàcôngviệccủagiaothứcdẫn đường inter-AS ! Gửi gói tin tới router chi phí thấpnhất Sử dụng thông tin Xác định từ bảng Họctừ giao thức dẫn đường từ giao chuyểntiếpgiaodiện inter-AS biếtrằng Chọn gateway có thức intra-ASU để I dẫntới gateway subnet x có thể chi phí thấpnhất xác định chi phí của chi phí thấpnhất. tới đượcqua đường đicóchi phí Cho (x,I) vào trong nhiều gateway thấpnhấttớimỗi bảng chuyểntiếp gateway 1-87
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-88
Dẫn đường Intra-AS Còn gọilàInterior Gateway Protocols (IGP) Các giao thứcdẫn đường Intra-AS phổ biến: RIP: Routing Information Protocol OSPF: Open Shortest Path First IGRP: Interior Gateway Routing Protocol (sở hữu của Cisco) 1-89
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-90
RIP ( Routing Information Protocol) Thuật toán Distance vector Trong BSD-UNIX Distribution, 1982 Độ đokhoảng cách: số hop (tối đa = 15 hop) đích hop u v u 1 A B w v 2 w 2 x 3 x y 3 z C D z 2 y 1-91
Thông báo củaRIP Distance vector: trao đổigiữa các hàng xom mỗi 30s qua Response Message (còn gọilà advertisement – thông báo) Mỗi thông báo: danh sách tới 25 mạng đích trong AS 1-92
RIP: Ví dụ z w xy A D B C Mạng đích Router tiếpSố hop để tới đích w A2 y B2 z B7 x 1 . . Bảng dẫn đường trong D 1-93
RIP: Ví dụ Đích TiếpHop Thông báo w x từ A tớiD z C 4 . z w xy A D B C Mạng đích Router tiếpSố hop tới đích w A2 y B2 z B A 7 5 x 1 . . Bảng dẫn đường trong D 1-94
RIP: Lỗi liên kết và khôi phục Nếu không nghe thấybản tin thông báo sau 180 giây -> hàng xóm/liên kết đã không hoạt động Đường qua hàng xóm mấthiệulực Không gửi thông báo đến các hàng xóm đó Các hàng xóm gửi thông báo mới(nếubảng thay thay đổi) Thông tin lỗiliênkết nhanh chóng lan truyền toàn mạng poison reverse sử dụng để ngănchặn vòng lặp ping- pong (khoảng cách không giớihạn = 16 hops) 1-95
RIP: Xử lý bảng Bảng dẫn đường củaRIP quảnlýbởitiếntrìnhmới ứng dụng gọi là route-d (daemon) Các thông báo đượcgửi trong các gói tin UDP, lặp lại định kỳ routed routed Transport Transprt (UDP) (UDP) network bảng bảng network (IP) chuyểntiếp chuyểntiếp (IP) link link physical physical 1-96
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1-97
OSPF (Open Shortest Path First) “open”: không thương mại Sử dụng thuật toán Link State Phổ biến gói tin LS Bản đồ Topology tạimỗi nút Tính toán đường đisử dụng thuật toán Dijkstra Các thông báo OSPF mang một điểmvàochomỗirouter hàng xóm Thông báo phổ biến trong toàn AS (bằng cách làm tràn) Mang bản tin OSPF trựctiếp qua IP (không phải qua TCP, UDP) 1-98
Các đặc điểmtiếnbộ của OSPF (không có trong RIP) An toàn bảomật: Tấtcả các bản tin OSPF đượcxác thực(ngănchặnviệccố tình xâm nhập) Cho phép nhiều đường đi cùng chi phí (trong RIP chỉ 1 đường đi) Đốivớimỗiliênkết, chi phí khác nhau cho TOS khác nhau (ví dụ: chi phí liên kếtvệ tinh thiếtlậpthấpchodịch vụ best effort, cao cho các dịch vụ thờigianthực) Hỗ trợ cả unicast và multicast: Multicast OSPF (MOSPF) sử dụng cùng dữ liệu topology như OSPF OSPF phân cấp trong các miềnlớn. 1-99
OSPF phân cấp 1- 100
OSPF phân cấp Phân cấp2 mức: vùng cụcbộ, backbone Thông báo Link-state chỉ trong vùng Mỗi nút có topology vùng chi tiết; chỉ biếthướng (đường đingắnnhất) tớicácmạng trong các vùng khác Area border router: tóm tắt các khoảng cách tớicác mạng trong vùng của nó, thông báo cho các Area Border router khác Backbone router: chạydẫn đường OSPF giớihạn trong backbone Boundary router: kếtnốitớicácAS khác 1- 101
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1- 102
Dẫn đường Internet inter-AS: BGP BGP (Border Gateway Protocol): chuẩnphố biến(nhưng không chính thức) BGP cung mỗimỗi AS cách thức để: 1. Có thông tin tới subnet từ các AS hàng xóm. 2. Lan truyền thông tin tới các subnet tớimọirouter trong AS 3. Xác định các đường đitốttới các subnet dựatrên thông tin tới các subnet Cho phép một subnet quảng cáo thông tin về sự tồntạicủanótớiphầncònlạicủa Internet: “I am here” 1- 103
Cơ bảnvề BGP Các cặp router (BGP peer) trao đổi thông tin dẫn đường qua các kếtnốiTCP báncốđịnh: Phiên BGP Chú ý: Các phiên BGP không tương ứng vớiliênkết vậtlý Khi AS2 quảng cáo prefix tới AS1, AS2 hy vọng nó sẽ chuyểntiếpbấtkỳ datagram dựđịnh tớiprefix AS2 có thể kếttập các prefix trong các thông báo củanó 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d Phiên eBGP Phiên iBGP 1- 104
Phân phối thông tin tới đích Với phiên eBGP giữa 3a và 1c, AS3 gửi thông tin tới đích prefix tớiAS1 Sau đó, 1c có thể sử dụng iBGP để phân phối thông tin tới đích prefix mớitớimọi router trong AS1 Sau đó, 1b có thể quảng báo lại thông tin mớitới AS2 qua phiên eBGP 1b-tới-2a Khi router họcvề prefix mới, nó tạomột điểmvàochoprefix trong bảng chuyểntiếpcủanó 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d Phiên eBGP Phiên iBGP 1- 105
Path attribute và BGP route Khi quảng cáo một prefix, quảng cáo bao gồmcác BGP attribute. prefix + attributes = “route” Hai attribute quan trọng: AS-PATH: chứa các AS qua đóquảng cáo cho prefix chuyển qua: AS 67 AS 17 NEXT-HOP: chỉđịnh internal-AS router cụ thể tới next-hop AS. (Có thể có nhiềuliênkếttừ AS hiệntạitới next-hop-AS) Khi gateway router nhậnquảng cáo đường đi, sử dụng import policy để chấpnhậnhoặctừ chối 1- 106
Chọn đường củaBGP Router có thể họcvề nhiềuhơn1 đường đi từ mộtsố prefix. Router phảichọn đường đi. Quy tắcloạitrừ: 1. Local preference value attribute: quyết định của chính sách 2. AS-PATH ngắnnhất 3. NEXT-HOP router gầnnhất: hot potato routing 4. Các tiêu chuẩnkhác 1- 107
Bảntin BGP Các bản tin BGP trao đổisử dụng TCP. Bản tin BGP: OPEN: mở kếtnốiTCP tới peer và xác thực bên gửi UPDATE: quảng cáo đường đimới(hoặcthuhồi đường đicũ) KEEPALIVE giữ kếtnối khi không có UPDATE, tương tự ACK tớiyêucầu OPEN NOTIFICATION: thông báo về các lỗitrongbảntin trước, cũng sử dụng để đóng kếtnối 1- 108
Chính sách dẫn đường củaBGP legend: provider B network X W A customer C network: Y Figure 4.5-BGPnew: a simple BGP scenario A,B,C là mạng của nhà cung cấp X,W,Y là khách hàng (củamạng nhà cung cấp) X là dual-homed: nốitới2 mạng X không muốndẫntừ B qua X tớiC vì vậy, X sẽ không quảng cáo tớiB đường đitớiC 1- 109
Chính sách dẫn đường củaBGP (2) legend: provider B network X W A customer C network: Y Figure 4.5-BGPnew: a simple BGP scenario A quảng cáo tớiB đường điAW B quảng cáo tớiX đường điBAW B quảng cáo tớiC đường điBAW? Không! B không nhận được“thunhập” cho việcdẫn đường CBAW vì W và C không là khách hàng củaB B muốnépC dẫn đường tới w qua A B muốndẫn đường chỉ tới/từ các khách hàng của nó! 1- 110
Tạisaodẫn đường Intra-AS và Inter-AS khác nhau ? Chính sách: Inter-AS: Ngườiquảntrị muốn điềukhiểnviệcdẫn đường lưulượng của nó, ai dẫn đường qua mạng của nó Intra-AS: mộtngườiquảntrị vì thế không cần policy decision Sự co giãn: Dẫn đường phân cấptiếtkiệmkíchthướcbảng, giảm lưulượng cậpnhật Hiệunăng: Intra-AS: có thể tập chung vào hiệunăng Inter-AS: policy có thểảnh hưởng lớntớihiệunăng 1- 111
Chương 4: Tầng mạng 4.1 Tổng quan 4.5 Thuật toán dẫn 4.2 Mạng Virtual circuit đường và datagram Link state Distance Vector 4.3 Bên trong Router Hierarchical routing 4.4 IP: Internet Protocol 4.6 Dẫn đường trong Định dạng Datagram Internet Địachỉ IPv4 RIP ICMP OSPF IPv6 BGP 4.7 Dẫn đường broadcast và multicast 1- 112
duplicate lặp R1 creation/transmission R1 lặp R2 R2 R3 R4 R3 R4 (a) (b) Source-duplication và in-network duplication. (a) source duplication, (b) in-network duplication 1- 113
A B c D F E G Reverse path forwarding 1- 114
A A B B c c D D F E F E G G (a) Broadcast khởitạotạiA (b) Broadcast khởitạotạiD Broadcast dọc theo spanning tree 1- 115
A A 3 B B c c 4 2 D D F E F E 1 5 G G (a) Bước xây dựng (b) Spanning tree đã xây dựng Xây dựng kiểu Center-based củamột spanning tree 1- 116
Dẫn đường Multicast: Bài toán Mục đích: Tìm một tree (hoặc các tree) kếtnối các router có local mcast group members tree: Không phảimọi đường giữa các router đượcsử dụng source-based: Cây khác nhau từ mỗibêngửitới bên nhận shared-tree: Cây giống nhau sử dụng bởitấtcả các group member Shared tree Source-based tree
Các cách tiếpcận để xây dựng mcast tree Cách tiếpcận: source-based tree: mộtcâychomỗi nguồn Cây đường đingắnnhất Reverse path forwarding group-shared tree: Group sử dụng mộtcây minimal spanning (Steiner) center-based tree Chúng ta xem xét các cách tiếpcậnmộtcáchcơ bản, sau đó xem xét các giao thứcsử dụng các cách tiếpcận đó
Cây đường đingắnnhất mcast forwarding tree: cây đường đingắn nhấtdẫn đường từ nguồntớimọi đích Thuật toán Dijkstra S: nguồn Ghi chú: R1 2 1 R4 router nốivới group member R2 5 router không nốivới 3 4 R5 group member R3 6 i Liên kếtsử dụng để chuyểntiếp, R6 R7 i chỉ thứ tự liên kết đượcthêm bởithuật toán
Reverse Path Forwarding Dựavàokiếnthứccủa router vềđường đi ngắnnhất unicast từ nó tới bên gửi Mỗi router có hành vi chuyểntiếp đơngiản: if (mcast datagram nhậntrênliênkết đếntrên đường ngắnnhấttrở lại trung tâm) then làm tràn datagram trên mọiliênkết đi else bỏ qua datagram
Reverse Path Forwarding: Ví dụ S: nguồn Chú thích R1 R4 router nốivới group member R2 router không nốivới R5 group member R3 datagram sẽđược R6 R7 chuyểntiếp datagram sẽ không được chuyểntiếp •Kếtquả là một source-specific reverse SPT –cóthể là sự lựachọntồivớicácliênkết không đối xứng
Reverse Path Forwarding: Tỉa forwarding tree chứa các cây con mà subtree con đó không có mcast group member Không cần chuyểntiếp các datagram xuống subtree “Tỉa” các bảntin gửilênbởi router mà không có downstream group members S: nguồn Chú ý R1 router nốivới R4 group member R2 router không nốivới P group member P R5 Tỉabảntin R3 P Liên kếtvới multicast R6 R7 forwarding
Shared-Tree: Steiner Tree Steiner Tree: minimum cost tree kếtnốitấtcả các router nốivới group member Bài toán là NP-complete Tồntạicáckỹ thuật heuristic Không sử dụng trong thựctế: Độ phứctạp tính toán Cần thông tin về toàn bộ mạng Chạylạikhimột router gia nhập hay rờikhỏi
Center-based tree Tấtcả dùng chung mộtcây Một router đượcxácđịnh là “trung tâm” của cây Gia nhập: edge router gửiunicastjoin-msg tới center router join-msg đượcxử lý bởi intermediate routers và chuyểntiếptớicenter join-msg hoặctới nhánh của cây có trung tâm này, hoặc đến trung tâm Đường đimàjoin-msg tham gia trở thành một nhánh mớicủa cây cho router này
Center-based tree: ví dụ Giả sử R6 đượcchọn làm trung tâm: Chú thích R1 router nốivới R4 3 group member R2 router không nốivới 2 group member 1 R5 Thứ tựđường đi trong đó cácjoin msgsinhra R3 1 R6 R7
Internet Multicasting Routing: DVMRP DVMRP: Giao thứcdẫn đường multicast kiểu distance vector, RFC1075 Làm tràn và tỉa: reverse path forwarding, source-based tree RPF tree dựatrênchínhbảng dẫn đường củanó DVMRP đượcxâydựng bởisự giao tiếpcủacác DVMRP router Không giả sử về unicast ở dưới Datagram ban đầutới mcast group đượclàmtràn mọinơi qua RPF Router không muốn trong group: gửi upstream prune msgs
DVMRP (tiếp) Trạng thái mềm: DVMRP router định kỳ (1 phút) “quên” branches bị tỉa: mcast data đưalại xuông các nhánh không đượctỉa downstream router: tỉalạihoặctiếptụcnhậndữ liệu router có thể nhanh chónh ghép lạivàocây Theo IGMP gia nhậptạilá odds và ends Thường cài đặt trong các router thương mại Dẫn đường Mbone sử dụng DVMRP
Tunneling Q: Làm thế nào để kếtnốitớicác“đảo” củacác multicast router trong “biển” các unicast router? topology vậtlý topology lôgíc mcast datagram được đóng gói trong datagram “thông thường” (không đánh địachỉ multicast) IP datagram thông thường gửi qua “tunnel” qua IP unicast router bình thường tới mcast router nhận mcast router nhậnsẽ bỏđóng gói để nhận mcast datagram
PIM: Protocol Independent Multicast Không phụ thuộcvàobấtkỳ thuậttoándẫn đường unicast cụ thể nào phía dưới(làmviệcvớitấtcả) Hai kịch bản phân phối multicast khác nhau: Đông đúc: Thưathớt: group member tồntại Số mạng với group member dày đặc, tồntạigần nhỏ nhau. group member phân tán rộng Bandwidth lớn bandwidth không lớn
So sánh kiểu đông đúc và thưathớt Đông đúc: Thưathớt: Thành viên nhóm tớikhi Không là thành viên tớikhi router chính thứctỉa router chính thứcgianhập Xây dựng data-driven Xây dựng receiver- driven dựa trên mcast tree (ví của mcast tree (ví dụ: dụ: RPF) center-based) bandwidth và non-group- bandwidth và non-group- router xử lý thoảimái router xử lý dè dặt
PIM- Chếđộđông đúc flood-and-prune RPF, tương tự DVMRP nhưng Giao thức unicast phía dưới cung cấp thông tin RPF cho datagram tới Downstream flood ít phứctạphơn (kém hiệuquả hơn) DVMRP giảmsự tin cậyvàothuậttoándẫn đường phía dưới Có cơ chế giao thức cho router phát hiệnnólà router nút lá
PIM – Chếđộthưathớt Cách tiếpcậncenter- based Router gửi join msg tới R1 R4 điểmhẹn(RP) gia nhập Các intermediate router R2 cậpnhậttrạng thái và gia nhập chuyểntiếp join R5 Sau khi gia nhậpqua gia nhập RP, router có thể R3 R7 chuyểntới source- R6 specific tree Mọidữ liệu multicast Điểmhẹn Tăng hiệunăng: giảmtập từđiểmhiẹn chung, đường đingắn hơn
PIM – Chếđộthưathớt Bên gửi (s): Dữ liệu unicast tớiRP, nó phân phốixuống R1 R4 RP-rooted tree gia nhập R2 RP có thể mở rộng gia nhập mcast tree upstream tới R5 nguồn gia nhập R3 R7 RP có thể gửi stop msg R6 nếu không có người Tấtcả dữ liệu điểmhẹn nhậnnốivào multicast “không ai đang nghe!” từđiểmhẹn
Tầng mạng: Tổng kết Các vấn đề đãxemxét: Các dịch vụ củatầng mạng Nguyên tắcdẫn đường: link state và distance vector Dẫn đường phân cấp IP Các giao thứcdẫn đường trong Internet: RIP, OSPF, BGP Tiếp: Bên trong router? Tầng liên kếtdữ liệu! IPv6 1- 134