Bài giảng Cơ sở truyền số liệu: Chương 3 - ĐH Bách Khoa Hà Nội
lượt xem 5
download
Bài giảng này cung cấp cho người học những kiến thức cơ bản về định tuyến động (dynamic routing). Những nội dung chính được trình bày trong chương này gồm có: Phân loại thuật toán, cây bắc cầu tối thiểu MST, thuật toán Kruskal, thuật toán Prim, nhận xét chung về MST.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cơ sở truyền số liệu: Chương 3 - ĐH Bách Khoa Hà Nội
- om .c ng co an Định tuyến động (dynamic routing) th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Cơ bản • Các nút mạng tự động tìm ra đường đi tối ưu. Việc tìm ra tuyến đi được thực hiện một cách phân tán tại các nút chứ om không do một nút trung tâm tính toán • Các nút chủ động trao đổi thông tin liên quan đến cấu hình .c mạng với nhau ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Cơ bản • Từ các thông tin thu thập được, mỗi nút tự tìm ra đường đi tối ưu đến các nút khác rồi lập ra bảng định tuyến om • Mỗi khi có gói tin đến, nút mạng tra bảng định tuyến đưa ra .c quyết định định tuyến ng • Bảng định tuyến thường xuyên được cập nhật mỗi khi có thay co đổi cấu hỉnh mạng, tắc nghẽn… an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Phân loại thuật toán • Cây bắc cầu tối thiểu (MST) • Prime om • Kruskal .c • Cây đường đi ngắn nhất (SPT) ng • Dijkstra co • Bellman Ford an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Cây bắc cầu tối thiểu MST • Giá của cây được định nghĩa là tổng các chi phí liên kết (link cost) của cây đó om • MST của một graph liên thông là cây bao gồm tất cả các nút của graph .c đó, có giá tối thiểu • Cho graph GV, E, phải tìm ra cây T G, T V,E' sao cho: ng co W (T) w( e) an th e E' min ng 1 3 o A du S C 5 u 2 cu 3 4 1 E F CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán Kruskal 1. Khởi tạo: T lúc đầu là một graph rỗng. 2. Nếu T đã gồm đúng n-1 cạnh của G thì T là cây bao trùm om cần tìm. Kết thúc. .c 3. Nếu T còn chưa đủ n-1 cạnh, thì vì G liên thông, nên G ng có không ít hơn n-1 cạnh; do đó còn các cạnh của G co chưa thuộc T. Trong các cạnh của G chưa thuộc T có các an cạnh không tạo ra chu trình với các cạnh đã có trong T, th chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ ng sung (cùng với các đỉnh chưa thuộc T của nó) vào T. Loại o bỏ những cạnh tạo thành chu trình. du 4. Quay lại 2. u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán Kruskal Graph ban đầu. om .c AD và CE đều có giá nhỏ nhất; AD được chọn một các ng co ngẫu nhiên an th Tiếp theo, CE là cạnh có giá nhỏ nhất không tạo thêm ng cycle nào, nó được chọn o du u cu DF được chọn. CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán Kruskal Chọn AB, DB bị loại bỏ (chắc chắn không được lựa chọn ở om các bước sau) .c ng co an th BE được chọn, các liên kết tiếp theo bị loại là BC, DE, và FE ng o du u cu Cuối cùng EG được chọn và ta có MST CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán Prim 1. Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có cạnh nào. om 2. Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm .c ng cần tìm. Kết thúc. co 3. Nếu G còn có các đỉnh không thuộc T, vì G liên thông an th nên có các cạnh nối một đỉnh trong T với một đỉnh ngoài o ng T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho du u cu vào T. 4. Quay lại 2. CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Thuật toán Prime Xét ví dụ: om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
- Nhận xét chung về MST • Có thể tìm được nhiều MST với cùng giá W(T) • Phạm vi áp dụng MST chủ yếu trong mạng LAN om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cơ sở truyền thông sợi quang: Chương 5 - HV Bưu chính viễn thông
15 p | 166 | 28
-
Bài giảng Cơ sở thiết kế máy phần 2: Chương 5 - Trần Thiên Phúc
9 p | 147 | 19
-
Bài giảng Cơ sở truyền số liệu: Chương 0 - ĐH Bách Khoa Hà Nội
9 p | 42 | 5
-
Bài giảng Cơ sở truyền số liệu: Chương 2 - ĐH Bách Khoa Hà Nội
12 p | 33 | 4
-
Bài giảng Cơ sở truyền số liệu: Chương 4 - ĐH Bách Khoa Hà Nội
10 p | 31 | 4
-
Bài giảng Cơ sở truyền số liệu: Chương 5 - ĐH Bách Khoa Hà Nội
14 p | 52 | 4
-
Bài giảng Cơ sở truyền số liệu: Chương 6 - ĐH Bách Khoa Hà Nội
6 p | 27 | 4
-
Bài giảng Cơ sở truyền số liệu: Chương 7 - ĐH Bách Khoa Hà Nội
16 p | 23 | 4
-
Bài giảng Cơ sở truyền số liệu: Chương 10 - ĐH Bách Khoa Hà Nội
11 p | 23 | 4
-
Bài giảng Cơ sở truyền số liệu: Chương 9 - ĐH Bách Khoa Hà Nội
5 p | 31 | 3
-
Bài giảng Cơ sở truyền số liệu: Chương 8 - ĐH Bách Khoa Hà Nội
13 p | 19 | 3
-
Bài giảng Cơ sở kỹ thuật thông tin vô tuyến: Chương 1 - Nguyễn Việt Hưng
18 p | 4 | 1
-
Bài giảng Cơ sở kỹ thuật mạng truyền thông: Chương 1 - PGS. TS. Nguyễn Tiến Ban
6 p | 13 | 1
-
Bài giảng Cơ sở kỹ thuật mạng truyền thông: Chương 2 - PGS. TS. Nguyễn Tiến Ban
7 p | 6 | 1
-
Bài giảng Cơ sở kỹ thuật mạng truyền thông: Chương 4 - PGS. TS. Nguyễn Tiến Ban
7 p | 7 | 1
-
Bài giảng Cơ sở kỹ thuật mạng truyền thông: Chương 5 - PGS. TS. Nguyễn Tiến Ban
5 p | 7 | 1
-
Bài giảng Cơ sở kỹ thuật thông tin vô tuyến: Chương 8 - Nguyễn Viết Đảm
13 p | 13 | 1
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn