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

128 trang huongle 3700

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: Lớp Network", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

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

giao_trinh_mang_may_tinh_chuong_4_lop_network.pdf

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

Chương 4 Lớp Network Computer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith Ross Addison-Wesley, July 2004. Slide này được biên dịch sang tiếng Việt theo sự cho phép của các tác giả All material copyright 1996-2006 J.F Kurose and K.W. Ross, All Rights Reserved Lớp Network 1
Chương 4: Lớp Network Mục tiêu: hiểu các nguyên lý nền tảng của các dịch vụ lớp network: các mô hình dịch vụ lớp network forwarding và routing một router làm việc như thế nào routing (chọn đường) xử lý với scale các đề tài nâng cao: IPv6, mobility hiện thực trong Internet Lớp Network 2
Chương 4: Nội dung trình bày 4. 1 Giới thiệu 4.5 các giải thuật 4.2 Virtual circuit và Routing datagram networks Link state 4.3 Bên trong một Distance Vector router? Hierarchical routing 4.6 Routing trong 4.4 IP: Internet Protocol Internet RIP dạng thức Datagram OSPF địa chỉ IPv4 BGP ICMP IPv6 4.7 Broadcast và multicast routing Lớp Network 3
4. 1 Giới thiệu Lớp Network 4
lớp Network chuyển các đoạn từ host gửi đến host nhận application transport network bên gửi sẽ đóng gói các data link network physical network data link network đoạn vào trong các data link physical data link physical physical datagram network data link physical network bên nhận sẽ chuyển các data link đoạn cho lớp transport physical network network data link các giao thức lớp data link physical physical network trong mọi host, network data link application physical transport router network data link Router sẽ xem xét các physical trường header trong tất cả các IP datagram đã được chuyển cho nó Lớp Network 5
2 chức năng chính forwarding: di chuyển tương tự: các gói từ đầu vào đến đầu ra thích hợp của routing: tiến trình lập router kế hoạch chuyến đi từ nguồn đến đích routing: xác định đường đi cho các gói forwarding: tiến trình từ nguồn đến đích vận chuyển qua 1 giao điểm các giải thuật routing Lớp Network 6
Tác động qua lại giữa routing & forwarding giải thuật routing bảng forwarding cục bộ giá trị header đường ra 0100 3 0101 2 0111 2 1001 1 giá trị đang đến trong header của gói 0111 1 3 2 Lớp Network 7
Thiết lập kết nối chức năng quan trọng thứ 3 của một số kiến trúc mạng: ATM, frame relay, X.25 trước khi các datagram chuyển đi, 2 host và các router trung gian thiết lập kết nối ảo các router cũng liên quan dịch vụ kết nối lớp network với lớp transport: network: giữa 2 host (có thể cũng chứa các router trung gian trong trường hợp kết nối ảo) transport: giữa 2 tiến trình Lớp Network 8
mô hình dịch vụ Network Hỏi: Mô hình dịch vụ là gì (cho kênh truyền các datagram từ bên gửi đến bên nhận)? Ví dụ các dịch vụ cho các Ví dụ các dịch vụ cho 1 datagram riêng biệt: luồng các datagram: giao nhận bảo đảm giao nhận datagram ứ ự giao nhận bảo đảm với theo th t độ trễ < 40 ms bảo đảm băng thông tối thiểu cho luồng hạn chế các thay đổi trong khoảng trống giữa các gói Lớp Network 9
mô hình dịch vụ Network Bảo đảm? kiến trúc Mô hình phản hồi Network dịch vụ Băngthông Mất Thứ Định tắc nghẽn mát tự thì Internet best effort không không không không không (phát hiện thông qua mất mát) ATM CBR tốc độ có có có không không đổi tắc nghẽn ATM VBR tốc độ có có có không có bảo đảm tắc nghẽn ATM ABR bảo đảm không có không có tối thiểu ATM UBR không không có không không Lớp Network 10
4.2 Các mạng virtual circuit và datagram Lớp Network 11
Kết nối lớp network và dịch vụ không kết nối datagram network cung cấp dịch vụ không kết nối lớp network kết nối ảo cung cấp dịch vụ kết nối lớp network tương tự với các dịch vụ lớp transport, nhưng: dịch vụ: host-to-host không lựa chọn: network chỉ cung cấp 1 dịch vụ hiện thực: bên trong phần lõi của network Lớp Network 12
các mạch ảo “cách xử lý đường từ nguồn đến đích phải tương tự với mạch điện thoại” hiệu quả thiết lập cuộc gọi, chia nhỏ mỗi cuộc gọi trước khi dữ liệu có thể truyền mỗi gói mang nhân dạng kết nối ảo (không phải là địa chỉ đích) mọi router trên đường từ nguồn đến đích giữ nguyên “trạng thái” qua mỗi kết nối kết nối, các tài nguyên router (băng thông, bộ đệm) có thể được cấp phát cho kết nối ảo (các tài nguyên dành riêng = dịch vụ có thể dự đoán trước) Lớp Network 13
hiện thực kết nối ảo một kết nối ảo bao gồm: 1. đường từ nguồn đến đích 2. các số hiệu kết nối ảo, mỗi số dành cho mỗi kết nối dọc theo đường 3. các điểm đăng ký vào các bảng forwarding trong router dọc theo đường gói thuộc về kết nối ảo mang số hiệu (không là địa chỉ đích) số hiệu kết nối ảo có thể thay đổi trên mỗi kết nối số hiệu mới được cấp từ bảng forwarding Lớp Network 14
Bảng Forwarding số hiệu 12 22 32 1 3 2 bảng Forwarding trong số hiệu ế router góc tây-bắc: giao ti p giao tiếp vào số hiệu kết nối vào giao tiếp ra số hiệu kết nối ra 1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 Các Router giữ nguyên thông tin trạng thái kết nối! Lớp Network 15
các mạch ảo: các giao thức gửi tín hiệu dùng để thiết lập, duy trì kết nối ảo dùng trong ATM, frame-relay, X.25 không dùng trong Internet ngày nay application 6. nhận dữ liệu application transport 5. bắt đầu dòng dữ liệu transport network 4. cuộc gọi đã kết nối 3. chấp nhận cuộc gọi network data link 1. khởi tạo cuộc gọi 2. cuộc gọi đến data link physical physical Lớp Network 16
các mạng Datagram không thiết lập cuộc gọi tại lớp network các router: không có trạng thái về các kết nối end- to-end không có khái niệm mức network của “kết nối” vận chuyển các gói dùng địa chỉ host đích các gói giữa cùng cặp nguồn-đích có thể có các đường đi khác nhau application application transport transport network 1. gửi dữ liệu 2. nhận dữ liệu network data link data link physical physical Lớp Network 17
4 tỷ điểm bảng Forwarding đăng nhập có thể Vùng địa chỉ đích Giao tiếp kết nối 11001000 00010111 00010000 00000000 đến 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 đến 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 đến 2 11001000 00010111 00011111 11111111 khác 3 Lớp Network 18
So trùng prefix dài nhất So trùng prefix Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 ngược lại3 Các ví dụ: DA: 11001000 00010111 00010110 10100001 Chọn interface nào? DA: 11001000 00010111 00011000 10101010 Chọn interface nào? Lớp Network 19
Datagram hoặc network: tại sao? Internet (datagram) ATM (kết nối ảo) dữ liệu trao đổi giữa các máy phát triển từ hệ thống điện tính thoại dịch vụ “mềm dẻo”, không đàm thoại của con người: định thì chặt chẽ định thì chặt chẽ, yêu các hệ thống đầu cuối “thông cầu độ tin cậy minh” (các máy tính) cần thiết cho các dịch vụ có thể thích ứng, điều bảo đảm khiển và sửa lỗi các hệ thống đầu cuối “ít “bên trong” mạng đơn giản, thông minh” “bên ngoài” phức tạp điện thoại nhiều kiểu kết nối “bên trong” mạng phức các đặc tính khác nhau tạp đồng nhất dịch vụ khó khăn Lớp Network 20
4.3 Router Lớp Network 21
Tổng quan kiến trúc Router 2 chức năng chính: chạy các giao thức/giải thuật routing (RIP, OSPF, BGP) đẩy các datagram từ kết nối vào đến kết nối ra Lớp Network 22
Các chức năng cổng vào lớp Physical: tiếp nhận mức bit lớp Data link: switch không tập trung: ví dụ: Ethernet với đích của datagram biết trước, tìm xem chương 5 cổng ra dùng bảng forwarding trong bộ nhớ cổng vào mục tiêu: hoàn tất xử lý cổng vào dựa trên “tốc độ dòng” sắp hàng: nếu datagrams đến nhanh hơn tốc độ forwarding bên trong switch fabric Lớp Network 23
3 kiểu switching fabrics Lớp Network 24
Switching thông qua bộ nhớ Các router thế hệ thứ nhất: các máy tính cổ điển với switch dưới sự điều khiển trực tiếp của CPU gói được sao chép vào trong bộ nhớ hệ thống tốc độ giới hạn bởi băng thông bộ nhớ cổng bộ nhớ cổng vào ra Bus hệ thống Lớp Network 25
Switch thông qua 1 Bus datagram từ bộ nhớ cổng vào đến bộ nhớ cổng ra thông qua một bus chia sẻ tranh chấp bus: tốc độ switch giới hạn bởi băng thông của bus 1 Gbps bus, Cisco 1900: tốc độ đủ cho truy xuất các router Lớp Network 26
Switch thông qua 1 mạng kết nối nội bộ vượt qua các giới hạn của băng thông bus các mạng kết nối nội bộ khác lúc đầu được dùng để kết nối các bộ xử lý trong thiết bị có nhiều bộ xử lý thiết kế nâng cao: phân mảnh datagram vào các ô độ dài cố định, chuyển các ô thông qua fabric. Cisco 12000: chuyển với tốc độ hàng Gbps thông qua kết nối nội bộ Lớp Network 27
Các cổng ra Đệm được yêu cầu khi các datagram đến từ fabric nhanh hơn tốc độ truyền Scheduling discipline chọn giữa những datagram đã sắp hàng để truyền Lớp Network 28
Sắp hàng tại cổng ra đệm khi tốc độ đến thông qua switch vượt quá tốc độ dòng ra sắp hàng (trễ) và mất mát bởi vì bộ đệm tại cổng ra bị tràn! Lớp Network 29
Sắp hàng tại cổng vào Fabric chậm hơn sự phối hợp tại các cổng vào -> sắp hàng xảy ra tại các hàng vào Tắc nghẽn Head-of-the-Line (HOL): datagram đã sắp hàng phía trước của hàng ngăn cản các datagram khác di chuyển lên trước sắp hàng (trễ) và mất mát bởi vì bộ đệm tại cổng vào bị tràn! Lớp Network 30
4.4 IP - Internet Protocol Lớp Network 31
Lớp Internet Network Các chức năng: lớp Transport: TCP, UDP ứ các giao thức Routing giao th c IP ướ ị ị ỉ •chọn đường •các quy c đ nh đ a ch ạ ứ •RIP, OSPF, BGP •d ng th c datagram lớp •các quy ước quản lý gói Network forwarding giao thức ICMP table •thông báo lỗi •router “signaling” lớp Link lớp physical Lớp Network 32
dạng thức IP datagram ố ệ ả s hi u phiên b n 32 bits giao thức IP tổng độ dài độ dài header head. type of datagram (bytes ver length (bytes) len service dành cho việc “kiểu” của dữ liệu fragment 16-bit identifier flgs phân mảnh/ offset tổng hợp số hop còn lại time to upper header tối đa live layer checksum (giảm xuống tại 32 bit địa chỉ IP nguồn mỗi router) 32 bit địa chỉ IP đích giao thức lớp trên tùy chọn (nếu có) ví dụ: trường timestamp bao nhiêu overhead dữ liệu ghi nhận đường đi, với TCP? (độ dài thay đổi, danh sách các 20 bytes của TCP tùy theo đoạn TCP router hoặc UDP) để đi đến 20 bytes của IP = 40 bytes + overhead lớp app Lớp Network 33
Phân mảnh & tổng hợp IP các kết nối mạng có MTU (max.transfer size) - frame mức kết nối lớn nhất có thể. các kiểu liên kết khác nhau, phân mảnh: các MTU khác nhau vào: 1 datagram lớn các datagram lớn được chia ra: 3 datagram nhỏ hơn (phân mảnh) bên trong mạng 1 datagram thành một vài datagram tổng hợp “tổng hợp” tại đích cuối cùng các bit của IP header xác định, thứ tự liên quan các mảnh Lớp Network 34
Phân mảnh & tổng hợp IP length ID fragflag offset Ví dụ =4000 =x =0 =0 4000 byte 1 datagram lớn thành một vài datagram nhỏ hơn datagram MTU = 1500 bytes length ID fragflag offset =1500 =x =1 =0 1480 bytes trong trường dữ liệu length ID fragflag offset =1500 =x =1 =185 offset = 1480/8 length ID fragflag offset =1040 =x =0 =370 Lớp Network 35
Định địa chỉ IP: giới thiệu địa chỉ IP: 32-bit nhận 223.1.1.1 dạng cho host, router 223.1.2.1 223.1.1.2 interface 223.1.1.4 223.1.2.9 ế ố ữ interface: k t n i gi a 223.1.2.2 host/router và kết nối 223.1.1.3 223.1.3.27 vật lý router thường có nhiều interface 223.1.3.1 223.1.3.2 host thường có 1 interface mỗi địa chỉ IP liên kết với mỗi interface 223.1.1.1 = 11011111 00000001 00000001 00000001 223 111 Lớp Network 36
Các Subnet (mạng con) địa chỉ IP: 223.1.1.1 phần subnet (các bit có 223.1.2.1 223.1.1.2 trọng số cao) 223.1.1.4 223.1.2.9 phần host (các bit có trọng số thấp) 223.1.2.2 223.1.1.3 223.1.3.27 subnet là gì? subnet các interface thiết bị có phần subnet của địa 223.1.3.1 223.1.3.2 chỉ IP giống nhau có thể tìm thấy nhau không cần sự can thiệp của router mạng gồm 3 subnets Lớp Network 37
223.1.1.0/24 Subnets 223.1.2.0/24 phương pháp Để xác định subnet, tách mỗi interface từ host hoặc router của nó, tạo vùng các mạng độc lập. Mỗi vùng mạng độc lập được gọi là một subnet. 223.1.3.0/24 Subnet mask: /24 Lớp Network 38
Subnets 223.1.1.2 Bao nhiêu? 223.1.1.1 223.1.1.4 223.1.1.3 223.1.9.2 223.1.7.0 223.1.9.1 223.1.7.1 223.1.8.1 223.1.8.0 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 Lớp Network 39
Định địa chỉ IP: CIDR CIDR: Classless InterDomain Routing phần subnet của địa chỉ có độ dài bất kỳ dạng thức địa chỉ: a.b.c.d/x, trong đóx làsố bit trong phần subnet của địa chỉ phần phần subnet host 11001000 00010111 00010000 00000000 200.23.16.0/23 Lớp Network 40
các địa chỉ IP: làm sao lấy một? Hỏi: Làm sao host lấy được địa chỉ IP? mã hóa cứng do người quản trị hệ thống trong 1 file Wintel: control-panel->network->configuration- >tcp/ip->properties UNIX: /etc/rc.config DHCP: Dynamic Host Configuration Protocol: tự động lấy địa chỉ từ server “plug-and-play” (xem chương kế tiếp để biết rõ hơn) Lớp Network 41
các địa chỉ IP: làm sao lấy một? Hỏi: Làm sao mạng lấy được phần subnet của địa chỉ IP? Đáp: lấy phần đã cấp phát của không gian địa chỉ IP do ISP cung cấp khối của ISP 11001000 00010111 00010000 00000000 200.23.16.0/20 Tổ chức 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Tổ chức 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Tổ chức 2 11001000 00010111 00010100 00000000 200.23.20.0/23 . . Tổ chức 7 11001000 00010111 00011110 00000000 200.23.30.0/23 Lớp Network 42
Định địa chỉ phân cấp: route tích hợp cho phép thông báo hiệu quả thông tin routing: Tổ chức 0 200.23.16.0/23 Tổ chức 1 “gửi cho tôi bất cứ thứ gì 200.23.18.0/23 với các địa chỉ bắt đầu Tổ chức 2 200.23.16.0/20” . Fly-By-Night-ISP 200.23.20.0/23 . . . . Internet Tổ chức 7 . 200.23.30.0/23 “gửi cho tôi bất cứ thứ gì ISPs-R-Us với các địa chỉ bắt đầu 199.31.0.0/16” Lớp Network 43
Định địa chỉ phân cấp: nhiều cách route xác định ISPs-R-Us có nhiều cách route đến Tổ chức 1 Tổ chức 0 200.23.16.0/23 “gửi cho tôi bất cứ thứ gì với các địa chỉ bắt đầu Tổ chức 2 200.23.16.0/20” . Fly-By-Night-ISP 200.23.20.0/23 . . . . Internet Tổ chức 7 . 200.23.30.0/23 “gửi cho tôi bất cứ thứ gì ISPs-R-Us với các địa chỉ bắt đầu Tổ chức 1 199.31.0.0/16 hoặc 200.23.18.0/23” 200.23.18.0/23 Lớp Network 44
Định địa chỉ IP: Hỏi: Làm sao một ISP lấy được khối địa chỉ? Đáp: ICANN: Internet Corporation for Assigned Names and Numbers cấp phát các địa chỉ quản lý DNS gán các tên miền, giải quyết tranh chấp Lớp Network 45
NAT: Network Address Translation phần còn lại của mạng cục bộ Internet (vd: mạng gia đình) 10.0.0/24 10.0.0.1 10.0.0.4 10.0.0.2 138.76.29.7 10.0.0.3 Tất cả datagram đi ra khỏi mạng cục các Datagram với nguồn hoặc đích bộ có cùng một địa chỉ IP NAT là: trong mạng này có địa chỉ 10.0.0/24 138.76.29.7, với các số hiệu cổng nguồn khác nhau Lớp Network 46
NAT: Network Address Translation Mạng cục bộ chỉ dùng 1 địa chỉ IP đối với bên ngoài: không cần thiết dùng 1 vùng địa chỉ từ ISP: chỉ cần 1 cho tất cả các thiết bị có thể thay đổi địa chỉ các thiết bị trong mạng cục bộ mà không cần thông báo với bên ngoài có thể thay đổi ISP mà không cần thay đổi địa chỉ các thiết bị trong mạng cục bộ các thiết bị trong mạng cục bộ không nhìn thấy, không định địa chỉ rõ ràng từ bên ngoài (tăng cường bảo mật) Lớp Network 47
NAT: Network Address Translation Hiện thực: NAT router phải: các datagram đi ra: thay thế (địa chỉ IP và số hiệu cổng nguồn) mọi datagram đi ra bên ngoài bằng (địa chỉ NAT IP và số hiệu cổng nguồn mới) . . . các clients/servers ở xa sẽ dùng (địa chỉ NAT IP và số hiệu cổng nguồn mới) đó như địa chỉ đích ghi nhớ (trong bảng chuyển đổi NAT) mọi cặp chuyển đổi (địa chỉ IP và số hiệu cổng nguồn) sang (địa chỉ NAT IP và số hiệu cổng nguồn mới) các datagram đi đến: thay thế (địa chỉ NAT IP và số hiệu cổng nguồn mới) trong các trường đích của mọi datagram đến với giá trị tương ứng (địa chỉ IP và số hiệu cổng nguồn) trong bảng NAT Lớp Network 48
NAT: Network Address Translation bảng chuyển đổi NAT 1: host 10.0.0.1 2: NAT router ị ỉ ị ỉ đ a ch phía WAN đ a ch phía LAN ử ế thay đổi địa chỉ từ g i datagram đ n 138.76.29.7, 5001 10.0.0.1, 3345 10.0.0.1, 3345 -> 128.119.40.186, 80 138.76.29.7, 5001, ậ ậ ả c p nh t b ng S: 10.0.0.1, 3345 D: 128.119.40.186, 80 10.0.0.1 1 S: 138.76.29.7, 5001 2 D: 128.119.40.186, 80 10.0.0.4 10.0.0.2 138.76.29.7 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4 S: 128.119.40.186, 80 3 D: 138.76.29.7, 5001 4: NAT router 10.0.0.3 ả ồ ế ị ỉ 3: ph n h i đ n đ a ch : thay đổi địa chỉ datagram đích 138.76.29.7, 5001 đích từ 138.76.29.7, 5001 -> 10.0.0.1, 3345 Lớp Network 49
NAT: Network Address Translation trường số hiệu cổng 16-bit: 60,000 kết nối đồng thời chỉ với một địa chỉ phía LAN NAT còn có thể gây ra tranh luận: các router chỉ xử lý đến lớp 3 vi phạm thỏa thuận end-to-end •những người thiết kếứng dụng phải tính đến khả năng NAT, vd: ứng dụng P2P sự thiếu thốn địa chỉ IP sẽ được giải quyết khi dùng IPv6 Lớp Network 50
ICMP: Internet Control Message Protocol được các host & router dùng để truyền thông thông kiểu mã mô tả tin lớp network 0 0 echo reply (ping) 3 0 dest. network unreachable Thông báo lỗi: host, 3 1 dest host unreachable network, port, giao thức 3 2 dest protocol unreachable không có thực 3 3 dest port unreachable phản hồi request/reply 3 6 dest network unknown (dùng bởi lệnh ping) 3 7 dest host unknown lớp network “trên” IP: 4 0 source quench (congestion các thông điệp ICMP control - not used) chứa trong các IP 8 0 echo request (ping) datagram 9 0 route advertisement 10 0 router discovery ệ ể thông đi p ICMP: ki u, mã 11 0 TTL expired ớ ầ thêm v i 8 byte đ u tiên 12 0 bad IP header của IP datagram gây ra lỗi Lớp Network 51
Traceroute & ICMP nguồn gửi một chuỗi các Khi thông điệp ICMP đến, đoạn UDP đến đích nguồn tính toán RTT đầu tiên có TTL =1 Traceroute thực hiện công thứ hai có TTL=2, tương việc này 3 lần tự. tiêu chuẩn dừng không giống số port đoạn UDP đến lần lượt tại khi datagram thứ n đến host đích router n: đích trả về gói ICMP “host Router hủy datagram không có thực” (kiểu 3, mã và gửi đến nguồn một ICMP 3) message (kiểu 11, mã 0) Khi nguồn có ICMP này -> thông điệp chứa tên của địa dừng. chỉ router& IP Lớp Network 52
IPv6 động lực thúc đẩy ban đầu: không gian địa chỉ 32-bit sớm được cấp phát cạn kiệt. động lực bổ sung: dạng thức header giúp tăng tốc xử lý/forwarding header thay đổi tạo điều kiện thuận lợi cho QoS dạng thức IPv6 datagram: 40 byte header, độ dài cố định không cho phép phân mảnh Lớp Network 53
IPv6 Header (tt) độ ưu tiên: xác định độ ưu tiên của các datagram trong luồng nhãn luồng: xác định các datagram trong cùng “luồng” (khái niệm “luồng” không được rõ ràng). header kế tiếp: xác định giao thức lớp trên cho dữ liệu Lớp Network 54
Những thay đổi khác nữa so với IPv4 Checksum: bỏ hết, nhằm giảm thời gian xử lý tại hop Options: cho phép, nhưng nằm ngoài header, chỉ thị bởi trường “Next Header” ICMPv6: phiên bản mới của ICMP các kiểu thông điệp bổ sung, vd “Packet Too Big” các chức năng quản lý nhóm multicast Lớp Network 55
Chuyển từ IPv4 sang IPv6 không phải tất cả router đều có thể nâng cấp đồng thời mạng có các router dùng cả IPv4 và IPv6 hoạt động thế nào? Lớp Network 56
Tunneling A B E F cách nhìn logic: tunnel IPv6 IPv6 IPv6 IPv6 A B E F cách nhìn thực: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Lớp Network 57
Tunneling A B E F cách nhìn logic: tunnel IPv6 IPv6 IPv6 IPv6 A B C D E F cách nhìn thực: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Flow: X Src:B Src:B Flow: X Src: A Dest: E Dest: E Src: A Dest: F Dest: F Flow: X Flow: X Src: A Src: A data Dest: F Dest: F data data data A-to-B: E-to-F: B-to-C: B-to-C: IPv6 IPv6 IPv6 inside IPv6 inside IPv4 IPv4 Lớp Network 58
4.5 Các giải thuật Routing Lớp Network 59
Tác động lẫn nhau giữa routing, forwarding giải thuật routing bảng forwarding cục bộ giá trịheader l.kết ra 0100 3 0101 2 0111 2 1001 1 giá trị trong header của gói đến 0111 1 3 2 Lớp Network 60
Mô hình đồ 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 routers = { u, v, w, x, y, z } E = tập các kết nối ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Ghi chú: Mô hình đồ thị cũng dùng được trong những ngữ cảnh khác Ví dụ: P2P, trong đóN làtập các điểm và E là tập các kết nối TCP Lớp Network 61
Mô hình đồ thị: các chi phí 5 • c(x,x’) = chi phí kết nối (x,x’) v 3 w 2 5 -vídụ: c(w,z) = 5 u 2 1 3 z •chi phí có thể luôn luôn là 1, hoặc 1 ngược lại liên quan đến băng thông, x y 2 1 hay liên quan đến tắc nghẽn chi phí của đường (x1, x2, x3, , xp) = c(x1,x2) + c(x2,x3) + + c(xp-1,xp) Hỏi: chi phí thấp nhất trên đường từ u đến z ? giải thuật Routing: giải thuật tìm đường có chi phí thấp nhất Lớp Network 62
phân lớp giải thuật Routing thông tin toàn cục hoặc không ộ tập trung Tĩnh hay đ ng? toàn cục: Tĩnh: tất cả router có toàn bộ thông ệ ườ tin về chi phí kết nối, cấu trúc vi c tìm đ ng đi thay mạng đổi chậm chạp theo các giải thuật “trạng thái kết thời gian nối” không tập trung: Động: biết các kết nối vật lý đến các việc tìm đường đi thay điểm lân cận và chi phí của nó lặp lại quá trình tính toán, trao đổi rất nhanh đổi thông tin với các điểm lân cập nhật theo chu kỳ cận phản ứng với những thay các giải thuật “vector khoảng cách” đổi chi phí kết nối Lớp Network 63
1 giải thuật Routing “trạng thái kết nối” giải thuật Dijkstra Ký hiệu: biết chi phí kết nối, cấu trúc c(x,y): chi phí kết nối từ mạng của tất cả các nút nút x đến y; = ∞ nếu không tất cả các nút có thông kết nối trực tiếp đến điểm tin giống nhau lân cận tính toán đường đi chi phí D(v): giá trị chi phí hiện tại thấp nhất từ 1 nút (nguồn) của đường từ nguồn đến đích đến tất cả các nút khác v cho trước bảng p(v): nút trước nằm trên forwarding của nút đó đường từ nguồn đến nút v sau k lần duyệt, biết được đường đi chi phí thấp nhất N': tập các nút mà đường đi của k đích chi phí thấp nhất đã được xác định Lớp Network 64
giải thuật Dijkstra 1 Khởi tạo: 2 N' = {u} 3 for tất cả các nút v 4 if v kề với u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Lặp 9 tìm w không có trong N' nhưng D(w) tối tiểu 10 thêm w vào N' 11 cập nhật lại D(v) cho tất cả v kề với w và không có trong N' : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* chi phí mới đến v là chính nó hoặc chi phí đường đi ngắn nhất 14 cộng với chi phí từ w đến v */ 15 cho đến khi tất cả các nút nằm trong N' Lớp Network 65
giải thuật Dijkstra: ví dụ Bước N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 4,y 5 uxyvwz 5 v 3 w 2 5 u 2 1 3 z 1 x y 2 1 Lớp Network 66
giải thuật Dijkstra: ví dụ (2) Cây kết quả đường đi ngắn nhất từ u: v w u z x y Bảng forwarding kết quả trong u: đích kết nối v (u,v) x (u,x) y (u,x) w (u,x) z (u,x) Lớp Network 67
giải thuật Dijkstra: thảo luận Độ phức tạp giải thuật: n nút mỗi lần duyệt: cần kiểm tra tất cả các nút w không có trong N n(n+1)/2 phép so sánh: O(n2) có nhiều cách hiện thực đạt hiệu quả hơn: O(nlogn) có thể dao động: vd: chi phí kết nối = số lượng lưu thông 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ính toán lại tính toán lại tính toán lại khởi tạo routing Lớp Network 68
giải thuật Vector khoảng cách công thức Bellman-Ford định nghĩa dx(y) := chi phí thấp nhất của đường đi từ x đến y thì d (y) = min {c(x,v) + d (y) } x v v trong đó min được tính trên tất cả lân cận v của x Lớp Network 69
Bellman-Ford: ví dụ 5 rõ ràng, dv(z) = 5, dx(z) = 3, dw(z) = 3 v 3 w 2 5 u 2 1 công thức B-F cho: 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 chú ý rằng tối tiểu đạt được là hop kế tiếp trong đường đi ngắn nhất Lớp Network 70
giải thuật Vector khoảng cách Dx(y) = ước lượng chi phí thấp nhất từ x đến y nút x biết chi phí đến mỗi lân cận v: c(x,v) Nút X duy trì vectơ khoảng cách Dx = [Dx(y): y є N ] Nút X cũng duy trì các vectơ khoảng cách đến các lân cận của nó với mỗi lân cận v, x duy trì Dv = [Dv(y): y є N ] Lớp Network 71
giải thuật Vector khoảng cách (4) Ý tưởng chính: mỗi nút định kỳ gửi ước lượng vector khoảng cách của nó đến các lân cận khi 1 nút x nhận ước lượng Dv mới từ lân cận, nó cập nhật DV của mình dùng công thức B-F: Dx(y) ← minv{c(x,v) + Dv(y)} với mỗi nút y ∊ N Dưới những điều kiện tự nhiên, ước lượng Dx(y) hội tụ tới chi phí dx bé nhất thực sự dx(y) Lớp Network 72
giải thuật Vector khoảng cách (5) lặp, không đồng bộ: mỗi lặp mỗi nút: cục bộ được gây ra bởi: chi phí kết nối cục bộ thay cho (thay đổi trong chi đổi chờ phí kết nối cục bộ hoặc thông ậ ậ ừ DV c p nh t thông báo t báo từ lân cận) lân cận phân bố: tính toán lại các ước lượng mỗi nút thông báo đến các lân cận chỉ khi DV của nó nếu DV đến bất kỳ đích nào thay đổi có thay đổi, cho các lân cận sau đóthông thông báo báo đến các lân cận của nó các lân cận nếu cần thiết Lớp Network 73
D (z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} x = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} bảng nút x = min{2+1 , 7+0} = 3 chi phí đến chi phí đến x y z x y z x 0 2 7 x 0 2 3 y y ừ ừ ∞∞ ∞ 2 0 1 t t z ∞∞ ∞ z 7 1 0 bảng nút y chi phí đến x y z y 2 1 x ∞ ∞∞ x z ừ t y 2 0 1 7 z ∞∞ ∞ bảng nút z chi phí đến x y z x ∞∞ ∞ ừ t y ∞∞ ∞ z 71 0 thời gian Lớp Network 74
D (z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} x = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} bảng nút x = min{2+1 , 7+0} = 3 chi phí đến chi phí đến chi phí đến x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 y y ừ ừ ∞∞ ∞ 2 0 1 y ừ t t 2 0 1 z z t ∞∞ ∞ 7 1 0 z 3 1 0 bảng nút y chi phí đến chi phí đến chi phí đến x y z x y z y x y z 2 1 x ∞ ∞∞ x 0 2 7 x 0 2 3 x z y y 7 2 0 1 ừ 2 0 1 y ừ ừ t 2 0 1 t t z ∞∞ ∞ z 7 1 0 z 3 1 0 bảng nút z chi phí đến chi phí đến chi phí đến x y z x y z x y z x ∞∞ ∞ x 0 2 7 x 0 2 3 y y 2 0 1 ừ y ừ 2 0 1 ừ t ∞∞ ∞ t t z z z 71 0 3 1 0 3 1 0 thời gian Lớp Network 75
Vector khoảng cách: các thay đổi chi phí kết nối các thay đổi chi phí kết nối: 1 nút kiểm tra thay đổi chi phí kết nối y 4 1 cập nhật thông tin dẫn đường, tính x z toán lại vector khoảng cách 50 nếu DV thay đổi, thông báo các lân cận Tại thời điểm t0, y kiểm tra thay đổi chi phí kết nối, cập nhật DV và thông báo đến các lân cận của nó “duyệt Tại thời điểm t1, z nhận được cập nhật từ y và cập nhật bảng của nó. tin tức Nó tính toán chi phí thấp nhất mới đến x và gửi DV của nó đến các tốt lân cận nhanh” Tại thời điểm t2, y nhận được cập nhật của z và cập nhật bảng khoảng cách của nó. Các chi phí thấp nhất của y không thay đổi và hơn nữa y không gửi bất kỳ thông báo nào đến z. Lớp Network 76
Vector khoảng cách: các thay đổi chi phí kết nối các thay đổi chi phí kết nối: 60 duyệt tin tức tốt nhanh y 4 1 duyệt tin tức xấu chậm - vấn đề x z “đếm đến vô tận”! 50 44 lần duyệt trước khi ổn định Poisoned reverse: Nếu Z dẫn đường từ Y thẳng tới X: Z nói với Y khoảng cách của nó đến X là ∞ (vì thế Y sẽ không dẫn đường đến X đi qua Z) sẽ giải quyết triệt để vấn đề đếm vô tận? Lớp Network 77
So sánh các giải thuật LS và DV thông báo phức tạp sự linh hoạt: điều gì xảy ra nếu router hoạt động sai chức ớ ế ố LS: v in nút, E kt n i, O(nE) năng? các thông báo được gửi LS: DV: chỉ trao đổi giữa các lân nút có thể thông báo chi phí ậ c n kết nối không chính xác Tốc độ hội tụ mỗi nút chỉ tính toán bảng riêng của nó LS: giải thuật O(n2) yêu cầu DV: O(nE) thông báo nút có thể thông báo chi phí ể ộ có th có các dao đ ng đường đi không chính xác DV: thời gian hội tụ thay đổi bảng của nút có thể được nút có thể do các quá trình lặp khác dùng tìm đường •lỗi lan truyền thông qua mạng vấn đề đếm vô hạn Lớp Network 78
Hierarchical Routing nghiên cứu trong môi trường lý tưởng hóa tất cả các router đồng nhất mạng “phẳng” không đúng trong thực tế quy mô: với 200 triệu quản trị đích internet = mạng của các ể ớ ấ ả không th ghi nh t t c ạ đích trong bảng routing! m ng bảng routing sẽ kiểm soát mỗi quản trị mạng muốn các kết nối! điều hành routing trong mạng của họ Lớp Network 79
Hierarchical Routing các router gom thành các Gateway router vùng, “các hệ thống tự trị- autonomous systems” (AS) trực tiếp kết nối đến các router trong cùng AS router trong AS khác chạy giao thức routing giống nhau giao thức “intra-AS” routing các router trong AS khác nhau có thể chạy giao thức intra-AS routing Lớp Network 80
Kết nối các AS 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 bảng Forwarding được cấu hình bởi cả giải thuật intra- và inter-AS routing g.thuật g.thuật Intra-AS thiết lập các Intra-AS Inter-AS điểm đăng nhập vào các Routing Routing đích nội mạng bảng Inter-AS & Intra-As thiết Forwarding lập các điểm đăng nhập vào các đích ngoại mạng Lớp Network 81
các tác vụ Inter-AS AS1 cần: giả sử router AS1 nhận 1. học các đích nào có datagram với đích nằm thể chạm đến thông ngoài nó qua AS2 và AS3 Router sẽ forward về 2. lan truyền thông tin một trong những này đến tất cả các gateway router kế tiếp, nhưng là cái nào? router trong AS1 công việc của inter-AS routing! 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 Lớp Network 82
Ví dụ: thiết lập bảng forwarding trong router 1d Giả sử AS1 học (thông qua giao thức inter-AS) mà subnet x có thể chạm đến qua AS3 (gateway 1c) nhưng không qua AS2. Giao thức Inter-AS lan truyền thông tin này đến tất cả các router nội mạng. Router 1d xác định từ thông tin intra-AS routing và I sẽ nằm trên đường đi chi phí thấp nhất đến 1c. Đưa giá trị (x,I) vào bảng forwarding 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 Lớp Network 83
Ví dụ: Chọn giữa nhiều AS Bây giờ giả sử AS1 học từ giao thức inter-AS là subnet x có thể chạm đến từ AS3 và từ AS2 Để cấu hình bảng forwarding, router 1d phải xác định gateway nào được dùng để chuyển các gói đến đích x. đấy cũng chính là công việc trên giao thức inter-AS routing! 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 Lớp Network 84
Ví dụ: Chọn giữa nhiều AS Hot potato routing: gởi các gói đến 2 router gần nhất dùng thông tin từ xác định từ bảng học từ giao thức Hot potato routing: giao thức intra-AS forwarding là I có thể inter-AS là subnet x chọn gateway để xác định các chi dẫn đến gateway chi có thể chạm đến thông nào có chi phí thấp phí của các đường phí thấp nhất. đưa qua nhiều gateways nhất đi có chi phí thấp giá trị (x,I) vào bảng nhất đến mỗi gateway Lớp Network 85
4.6 Routing trong Internet Lớp Network 86
Intra-AS Routing cũng gọi là Interior Gateway Protocols (IGP) các giao thức Intra-AS routing phổ biến: RIP: Routing Information Protocol OSPF: Open Shortest Path First IGRP: Interior Gateway Routing Protocol (Cisco độc quyền) Lớp Network 87
RIP ( Routing Information Protocol) giải thuật vector khoảng cách công bố năm 1982 trong BSD-UNIX Distribution không gian khoảng cách: số lượng hop (tối đa 15 hop) từ router A đến các subset: đích số hop u v u 1 A B w v 2 w 2 x 3 x y 3 z C D z 2 y Lớp Network 88
các thông báo của RIP Các vector khoảng cách: trao đổi giữa các lân cận mỗi 30s thông qua Response Message (cũng được gọi là thông báo). Mỗi thông báo: danh sách lên đến 25 mạng đích trong mỗi AS Lớp Network 89
RIP: ví dụ z w xy A D B C Network đích Router kế tiếpSố hop đến đích w A2 y B2 z B7 x 1 . . bảng Routing trong D Lớp Network 90
RIP: ví dụ Đích Kế tiếpSố hop w -1 thông báo x -1 từ A đến D z C 4 . z w xy A D B C Network đích Router kế tiếpSố hop đến đích w A2 y B2 z B A 7 5 x 1 . . bảng Routing trong D Lớp Network 91
RIP: kết nối sai & phục hồi Nếu không có thông báo nào sau 180s Æ lân cận/kết nối được xem như đã “chết” những đường đi qua lân cận không còn dùng được gửi thông báo mới cho các lân cận các lân cận tiếp tục gửi ra những thông báo mới đó (nếu các bảng thay đổi) thông tin kết nối lỗi nhanh chóng (?) lan truyền trên toàn mạng poison reverse dùng để ngăn chặn các vòng lặp ping- pong (khoảng cách vô hạn = 16 hop) Lớp Network 92
RIP: xử lý bảng các bảng RIP routing được quản lý bởi các tiến trình mức application gọi là route-d (daemon) các thông báo gửi trong các gói UDP, lặp lại theo chu kỳ routed routed Transprt Transprt (UDP) (UDP) network bảng bảng network (IP) forwarding forwarding (IP) link link physical physical Lớp Network 93
OSPF (Open Shortest Path First) “open”: sẵn sàng công khai dùng giải thuật Link State phân phối gói LS bản đồ cấu trúc mạng tại mỗi nút tính toán đường đi dùng giải thuật Dijkstra thông báo OSPF mang 1 entry vào mỗi router lân cận các thông báo phân tán đến toàn bộ AS (thông qua cơ chế flooding) thông điệp OSPF trực tiếp trên IP (chứ không phải là TCP hoặc UDP) Lớp Network 94
các đặc tính OSPF “cao cấp” (không có trong RIP) bảo mật: chứng thực tất cả các thông điệp OSPF (ngăn những kẻ có ý đồ xấu) cho phép nhiều đường đi có chi phí giống nhau (RIP chỉ cho 1) với mỗi kết nối, có nhiều không gian chi phí cho TOS khác nhau (vd: chi phí kết nối vệ tinh được thiết lập “thấp” để đạt hiệu quả tốt, “cao” cho thời gian thực) hỗ trợ uni- và multicast tích hợp: Multicast OSPF (MOSPF) dùng cùng cơ sở dữ liệu cấu trúc như OSPF OSPF phân cấp trong những miền lớn. Lớp Network 95
OSPF phân cấp Lớp Network 96
OSPF phân cấp phân cấp mức 2: vùng địa phương, backbone. các thông báo Link-state chỉ bên trong vùng mỗi nút có cấu trúc vùng chi tiết; chỉ biết hướng (đường đi ngắn nhất) đến các mạng trong các vùng khác các router ngoài biên vùng: “tổng hợp” khoảng cách đến các mạng trong vùng của nó, thông báo đến các router ngoài biên vùng các Backbone routers: chạy OSPF routing hạn chế đến backbone. các router ngoài biên: kết nối đến các AS khác. Lớp Network 97
Internet inter-AS routing: BGP BGP (Border Gateway Protocol): chuẩn thực tế BGP hỗ trợ cho mỗi AS: 1. Lấy thông tin khả năng chạm subnet đích từ các AS lân cận. 2. lan truyền thông tin đó đến tất cả các router bên trong AS. 3. Xác định đường đi “tốt” đến các subnet dựa trên thông tin khả năng chạm subnet đích và chính sách. cho phép subnet thông báo sự tồn tại của nó trên Internet Lớp Network 98
các cơ sở BGP Các cặp router (BGP peers) trao đổi thông tin routing trên các kết nối TCP bán bền vững: BGP sessions các phiên BGP không cần các kết nối vật lý tương xứng Khi AS2 thông báo 1 prefix đến AS1, AS2: AS2 có thể tích hợp các prefix trong thông báo của nó 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d eBGP session iBGP session Lớp Network 99
Phân phối thông tin khả chạm đích Với phiên eBGP giữa 3a và 1c, AS3 gửi thông tin khả chạm cho AS1. 1c sau đócóthể dùng iBGP phân phối thông tin khả chạm đến tất cả router trong AS1. 1b sau đócóthể thông báo lại thông tin khả chạm đến AS2 trên phiên eBGP từ 1b-đến-2a Khi router học xong prefix mới, tạo entry cho prefix trong bảng forwarding của nó. 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d eBGP session iBGP session Lớp Network 100
các thuộc tính đường đi & BGP khi thông báo 1 prefix, trong đócóchứa các thuộc tính BGP prefix + các thuộc tính = “dẫn đường” 2 thuộc tính quan trọng: AS-PATH: chứa các AS qua đó thông báo prefix truyền đi: AS 67 AS 17 NEXT-HOP: Chỉ định router bên trong AS là hop kế tiếp (có nhiều kết nối từ AS hiện tại đến AS hop kế tiếp) Khi gateway router nhận thông báo tìm đường, nó dùng import policy để chấp nhận/từ chối. Lớp Network 101
chọn BGP route Router có thể học nhiều hơn một nhưng chỉ được chọn một. Các quy tắc hạn chế: 1. Thuộc tính giá trị ưu tiên cục bộ: quyết định chính sách 2. AS-PATH ngắn nhất 3. NEXT-HOP router gần nhất: hot potato routing 4. Tiêu chuẩn bổ sung Lớp Network 102
các thông điệp BGP trao đổi các thông điệp BGP dùng TCP các thông điệp BGP: OPEN: mở kết nối TCP đến peer và chứng thực người gửi UPDATE: thông báo đường đi mới KEEPALIVE giữ kết nối sống (alive), cũng gọi là yêu cầu OPEN các ACK NOTIFICATION: thông báo các lỗi trong thông điệp trước đó, dùng để đóng kết nối Lớp Network 103
chính sách BGP routing legend: provider B network X W A customer C network: Y Figure 4.5-BGPnew: a simple BGP scenario A,B,C là những nhà cung cấp mạng X,W,Y là khách hàng (của những nhà cung cấp mạng) X là dual-homed: gắn vào 2 mạng X không muốn dẫn đường từ B qua X đến C vì thế X sẽ không thông báo với B về đường đến C Lớp Network 104
chính sách BGP routing (2) legend: provider B network X W A customer C network: Y Figure 4.5-BGPnew: a simple BGP scenario A thông báo với B về đường AW B thông báo với X về đường BAW B sẽ thông báo với C về đường BAW? Không có cách nào! B không có "lợi ích" về đường CBAW cũng như W không phải là những khách hàng của B, C B muốn buộc C phải tìm đường đến W thông qua AB B chỉ muốn tìm đường đến/từ khách hàng của nó! Lớp Network 105
Tại sao phải routing Intra- và Inter-AS khác nhau? chính sách: Inter-AS: người quản trị muốn điều hành hoạt động lưu thông routing, ai routing thông qua mạng của họ Intra-AS: 1 người quản trị, vì thế không cần các quyết định chính sách linh hoạt: routing phân cấp tiết giảm kích thước bảng, giảm lưu lượng cập nhật hiệu suất: Intra-AS: có thể tập trung vào hiệu suất Inter-AS: chính sách quan trọng hơn hiệu suất Lớp Network 106
4.7 Broadcast và multicast routing Lớp Network 107
Broadcast Routing Chuyển các gói từ nguồn đến tất cả các nút khác Nguồn trùng lặp thì không có hiệu quả tạo/truyền dẫn trùng lặp R1 trùng lặp R1 trùng lặp R2 R2 R3 R4 R3 R4 nguồn trùng lặp trùng lặp trong mạng Nguồn trùng lặp: làm sao xác định địa chỉ người nhận? Lớp Network 108
Trùng lặp trong mạng Ngập lụt: khi nút nhận gói broadcast và gửi đến tất cả các lân cận các vấn đề: bão broadcast & lặp lại Ngập lụt có điều khiển: nút chỉ gửi broadcast nếu nó không gửi gói nào giống như vậy trước đó nút phải theo dõi các gói đã broadcast hoặc reverse path forwarding (RPF): chỉ forward gói nếu nó đến trên đường ngắn nhất giữa nút và nguồn Cây mở rộng tại bất kỳ nút nào cũng đều không nhận thừa các gói Lớp Network 109
Cây mở rộng Đầu tiên xây dựng Cây mở rộng Các nút forward các bản sao chỉ trên Cây mở rộng A A B B c c D D F E F E G G (a) Broadcast khởi đầu tại A (b) Broadcast khởi đầu tại D Lớp Network 110
Cây mở rộng: tạo Nút trung tâm Mỗi nút gửi thông điệp gia nhập unicast đến nút trung tâm Thông điệp forward cho đến khi gặp một nút đã nằm trên cây mở rộng A A 3 B B c c 4 2 D D F E F E 1 5 G G (a) các bước xây dựng (b) cây mở rộng đã xây một cây mở rộng dựng xong Lớp Network 111
Multicast Routing: phát biểu vấn đề Mục tiêu: tìm một cây (trong các cây) kết nối các router có các thành viên nhóm Multicast cây: không phải tất cả các đường đi giữa các router được dùng cây dựa trên nguồn: cây khác nhau từ nơi gửi đến nơi nhận cây chia sẻ: cây giống nhau dùng bởi tất cả các thành viên nhóm cây chia sẻ cây dựa trên nguồn
Các cách tiếp cận xây dựng các cây multicast cây dựa trên nguồn: một cây mỗi nguồn các cây đường đi ngắn nhất cây đường đi ngược cây chia sẻ nhóm: nhóm dùng 1 cây mở rộng tối thiểu (Steiner) các cây trung tâm nghiên cứu các cách tiếp cận cơ bản
Cây đường đi ngắn nhất cây đường đi ngược multicast: cây đường đi ngắn nhất dẫn đường từ nguồn đến tất cả các điểm nhận giải thuật Dijkstra S: nguồn Ký hiệu R1 2 ớ ủ 1 R4 router v i các thành viên c a nhóm đã gắn vào R2 5 router không có các thành 3 4 R5 viên của nhóm gắn vào R3 6 i kết nối dùng cho forward, R6 R7 i chỉ thứ tự kết nối thêm vào bởi giải thuật
Cây đường đi ngược forward: phụ thuộc tri thức của router của đường đi ngắn nhất unicast từ nó đến nơi gửi mỗi router có cách xử lý forwarding đơn giản if (multicast datagram nhận được trên kết nối đến trên đường đi ngắn nhất kể từ trung tâm) then tràn ngập datagram lên tất cả các kết nối ra else lờ đi datagram
Cây đường đi ngược forward: ví dụ S: nguồn Ký hiệu R1 R4 router với các thành viên của nhóm đã gắn vào R2 router không có các thành R5 viên của nhóm gắn vào R3 datagram sẽ được R6 R7 forward datagram sẽ không được forward •kết quả là một cây SPT đảo ngược –cóthể là một lựa chọn tồi với các kết nối không đồng bộ
Cây đường đi ngược forward: cắt giảm cây forward chứa các cây con với các thành viên nhóm không multicast không cần forward các datagram xuống cây con “cắt giảm” các thông điệp gửi lên bởi router ệ S: nguồn Ký hi u R1 router với các thành viên R4 của nhóm đã gắn vào R2 router không có các thành P viên của nhóm gắn vào P R5 thông điệp cắt giảm R3 P các kết nối với multicast R6 R7 forward
Cây chia sẻ: cây Steiner cây Steiner: cây chi phí thấp nhất kết nối tất cả các router với các thành viên nhóm đã gắn vào vấn đề là NP-complete đã có các heuristic rất tốt không dùng trong thực tế: độ phức tạp tính toán cần thông tin về toàn bộ mạng monolithic: chạy lại bất cứ khi nào 1 router cần gia nhập/rời khỏi
Các cây trung tâm một cây truyền nhận chia sẻ cho tất cả 1 router được gọi là “trung tâm” của cây để gia nhập: bên ngoài gửi thông điệp gia nhập unicast cho router trung tâm thông điệp gia nhập “được xử lý” bởi các router trung gian và chuyển đến router trung tâm thông điệp gia nhập gặp nhánh của cây đã tồn tại hoặc đến được trung tâm đường đi thu được khi thông điệp gia nhập đến trở thành nhánh mới của cây cho router này
Các cây trung tâm: ví dụ giả sử R6 được chọn làm trung tâm: Ký hiệu R1 router với các thành viên R4 3 của nhóm đã gắn vào router không có các thành R2 2 viên của nhóm gắn vào 1 R5 thứ tự đường đi trong ấy các thông điệp gia nhập đã R3 sinh ra 1 R6 R7
Internet Multicasting Routing: DVMRP DVMRP: giao thức multicast routing dùng vector khoảng cách, RFC1075 flood & prune: forward đường đi ngược, cây dựa trên nguồn cây RPF dựa trên các bảng routing của DVMRP của riêng nó được xây dựng bởi truyền thông các router DVMRP không có các giả thiết về unicast bên dưới datagram ban đầu đến nhóm multicast làm tràn ngập mọi nơi thông qua RPF các router không phải nhóm: gửi các thông điệp cắt giảm
DVMRP: (tt) trạng thái “mềm”: router DVMRP chu kỳ (1 phút) “quên” các nhánh đã cắt giảm: dữ liệu mcast một lần nữa đổ xuống các nhánh không cắt giảm router dòng xuống: tái cắt giảm hoặc tiếp tục nhận dữ liệu các router có thể nhanh chóng tái cắt giảm gia nhập IGMP tại các nút lá còn lại đã hiện thực phổ biến trong các router thương mại hoàn thành routing dùng DVMRP
Tunneling Hỏi: Làm sao kết nối các “đảo” multicast router trong một “biển” các unicast router? cấu trúc vật lý cấu trúc logic multicast datagram được đóng gói trong datagram “thông thường” (không có multicast) datagram IP thông thường gửi thông qua “đường ống” và qua IP unicast đến router multicast nhận router multicast nhận mở gói để lấy multicast datagram
PIM: Protocol Independent Multicast không phụ thuộc vào bất kỳ giải thuật unicast routing bên dưới nào hai kịch bản phân phối multicast khác nhau Trù mật: Thưa thớt: các thành viên nhóm số lượng các mạng với các đóng gói trù mật thành viên nhóm ít băng thông dư thừa các thành viên nhóm “phân bố thưa thớt” băng thông không dư thừa
Hậu quả sự phân chia thưa thớt-trù mật Trù mật: Thưa thớt: nhóm các thành viên không có thành viên cho router là giả cho đến khi đến khi có các router gia các router cắt giảm thực nhập thực sự sự kiến trúc hướng người kiến trúc hướng dữ liệu nhận trên cây multicast trên cây multicast (vd: (vd: cây trung tâm) RPF) băng thông và router băng thông và router không thuộc nhóm xử lý không thuộc nhóm xử lý vừa phải phung phí
PIM- kiểu trù mật flood-and-prune RPF, tương tự DVMRP, nhưng: giao thức unicast bên dưới cung cấp thông tin RPF cho datagram đến ít phức tạp (ít hiệu quả) có cơ chế giao thức cho router để kiểm tra có phải router là nút lá
PIM – kiểu thưa thớt tiếp cận hướng trung tâm router gửi thông điệp R1 R4 gia nhập đến join rendezvous point (RP) R2 các router trung gian join cập nhật trạng thái và R5 forward thông điệp gia join nhập R3 R7 sau khi gia nhập bằng R6 RP, router có thể tất cả dữ liệu RP chuyển sang cây xác multicast định nguồn đến từ RP hiệu suất tăng: ít tập trung, các đường đi ngắn
PIM – kiểu thưa thớt bên gửi: dữ liệu unicast đến RP, RP phân phối xuống cây R1 R4 có nút gốc là RP join ể ở ộ RP có th m r ng cây R2 multicast dòng lên đến join nguồn R5 join RP có thể gửi thông R3 R7 điệp dừng nếu không có R6 bên nhận nào được gắn vào tất cả dữ liệu RP multicast “không có ai đang lắng đến từ RP nghe!”