Slide bài giảng môn Kỹ thuật mạng truyền thông nội dung chương 3 phần 2: Định tuyến

lOMoARcPSD| 36067889
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG BÀI GIẢNG MÔN
Kĩ thuật mạng truyền thông
( Fundamentals of CommunicationsNetworks )
Giảng viên :
TS. Phạm Anh Thư
Điện thoại/E-mail:
0912528188, thupa80@yahoo.com, thupaptit@gmail.com Bộ môn:
Mạng viễn thông - KhoaViễn thông 1
Học kỳ/Năm biên soạn: II/ 2021-2022 lOMoARcPSD| 36067889
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ĐỊNH TUYẾN lOMoARcPSD| 36067889 
Định tuyến là sự lựa chọn một con ường ể truyền một ơn vị dữ
liệu từ trạm nguồn ến trạm ích trong một liên mạng. 
Chức năng ịnh tuyến, ược thực hiện ở tầng mạng, cho phép bộ
ịnh tuyến ánh giá các ường i sẵn có tới ích. 
Để ánh giá ường i, ịnh tuyến sử dụng các thông tin tôpô mạng.
Các thông tin này có thể do người quản trị thiết lập hoặc nhờ các giao thức ịnh tuyến. 
Đối với mạng hoạt ộng theo hướng phi kết nối, quyết ịnh ịnh
tuyến ược thực hiện cho mỗi gói tin. Đối với các mạng hướng kết
nối, quyết ịnh ịnh tuyến ược thực hiện một lần, tại thời iểm thiết lập kênh. 
Định tuyến (Routing) khác với chuyển tiếp (Forwarding)!: 
Forwarding: Select the output path using routing table lOMoARcPSD| 36067889 
Routing: Management and updating the routing tables lOMoARcPSD| 36067889
Bảng ịnh Tuyến (Routing table):chứa
thông tin ể Router có thể
chuyển tiếp gói tin hướng tới ích
Giao thức ịnh tuyến:
Định nghĩa một tập các quy
tắc mà router sử dụng khi
liên lạc với các router hàng xóm lOMoARcPSD| 36067889 Định tuyến trong (Interior Routing): RIP , IGRP , OSPF, EIGRP ...
Định tuyến ngoài (Exterior Routing): BGP. lOMoARcPSD| 36067889
Thông tin bảng ịnh tuyến display ip routing-table Routing Tables:
Destination/Mask proto pref Cost Nexthop Interface
0.0.0.0/0 STATIC 60 0 10.0.1.1 Ethernet1/0
1.0.0.0/8 RIP 100 1 10.0.1.1 Ethernet1/0
1.1.1.0/24 STATIC 60 0 10.0.1.1 Ethernet1/0
1.1.1.1/32 OSPF 10 2 10.0.1.1 Ethernet1/0
2.2.2.2/32 DIRECT 0 0 127.0.0.1 InLoopBack0
10.0.1.0/30 DIRECT 0 0 10.0.1.2 Ethernet1/0
10.0.1.2/32 DIRECT 0 0 127.0.0.1 InLoopBack0 lOMoARcPSD| 36067889  lOMoARcPSD| 36067889 lOMoARcPSD| 36067889 
Có hai kiểu ịnh tuyến: 
Định tuyến tĩnh (Static - Non-Adaptive):
thông tin trong các bảng ịnh tuyến ược người
quản trị mạng tạo lập trực tiếp
 routes never update or update slowly over time
 Examples: Dijkstra, Flooding algorithm
 Định tuyến ộng (Dynamic - Adaptive):
 routes update more quickly use dynamic information of
current topology such as load, delay, …
 Examples: Distance Vector, Link State Routing Định tuyến lOMoARcPSD| 36067889 tĩnh
Downloaded by D?a (nyeonggot7@gmail.com) Định tuyến lOMoARcPSD| 36067889  Định tuyến tĩnh:  Vì lý do an toàn  Trường hợp chỉ có một ường i duy nhất tới mạng, tránh ược lưu lượng cập nhật ịnh tuyến ộng Định tuyến lOMoARcPSD| 36067889 tĩnh
 Thông tin trong các bảng ịnh tuyến ược người
quản trị mạng tạo lập trực tiếp
 Ưu iểm: Không cần tốn băng thông cho quá trình trao ổi thông tin ịnh tuyến.
 Nhược iểm:Không thích ứng với sự thay ổi cấu trúc của mạng.
Các tuyến tĩnh ược người quản trị cập nhật và quản lý nhân
công. Trong trường hợp tô pô mạng thay ổi, người quản trị phải
cập nhật lại tuyến tĩnh một cách thủ công. Định tuyến lOMoARcPSD| 36067889
 Khắc phục nhược iểm của ịnh tuyến tĩnh Định tuyến ộ ng lOMoARcPSD| 36067889
 Sau khi người quản trị nhập các lệnh cấu hình ể
khởi tạo ịnh tuyến ộng, thông tin về tuyến sẽ
ược cập nhật tự ộng mỗi khi nhận ược một
thông tin mới từ liên mạng.
 Các thay ổi về tôpô mạng ược trao ổi giữa các router.
 Định tuyến ộng hoạt ộng linh hoạt hơn ịnh
tuyến tĩnh khi mạng có sự thay ổi trạng thái: Định tuyến ộ ng lOMoARcPSD| 36067889  „Có sự cố
 „Khôi phục sau sự cố
 Các giao thức ịnh tuyến ộng cũng có thể
chuyển lưu lượng từ cùng một phiên làm việc
qua nhiều ường i khác nhau trong mạng ể có
hiệu suất cao hơn. Tính chất này ược gọi là chia sẻ tải (load sharing)
 Sự thành công của ịnh tuyến ộng phụ thuộc vào hai
chức năng cơ bản của Router: Định tuyến ộ ng lOMoARcPSD| 36067889
 „Duy trì bảng ịnh tuyến
 „Chia sẻ tri thức cho các Router khác
dưới dạng các thông tin cập nhật ịnh tuyến
 Định tuyến ộng dựa vào các giao
thức ịnh tuyến ể chia sẻ tri thức giữa các router.
 Trong phương pháp ịnh tuyến ộng,
một trong các giao thức ịnh tuyến Định tuyến ộ ng lOMoARcPSD| 36067889
ược kích hoạt trong môi trường liên mạng.
 „Các bộ ịnh tuyến sẽ tự ộng trao ổi, cập nhật thông tin
ịnh tuyến một cách tự ộng.
 „Dựa trên các thông tin ịnh tuyến thu thập ược, các bộ
ịnh tuyến sẽ tự ộng xây dựng các thực thể trong bảng ịnh tuyến
 „Việc sử dụng ịnh tuyến ộng cho phép các bộ ịnh
tuyến thích ứng với việc thay ổi cấu trúc mạng. lOMoARcPSD| 36067889
So sánh ịnh tuyến tĩnh và ộng Định tuyến tĩnh Đị nh tuyến ộng Tính linh hoạt Hiệu quả sử dụng băng thông cho ịnh tuyến Tính bảo mật lOMoAR cPSD| 36067889 Q&A Cần sử dụng giao thức ịnh tuyến lOMoAR cPSD| 36067889 Q&A b4 300 km 200 km a5 200 km 400 km 150 km 100 km 150 km A 200 km a4 400 km b5 200 km 100 km 100 km 200 km 300 km b2 100 km 150 km 200 km a3 100 km 300 km
200 km a2 a1 200 km b1 : Nút mạng 200 km 100 km
Q: Tìm ường i từ A ến B với số
hopcount không vượt quá 5. B lOMoAR cPSD| 36067889 Q&A b3 lOMoAR cPSD| 36067889 Q&A b4 a5 3 2 b3 2 2 1 4 2 A a4 b5 2 4 2 7 1 1 b2 1 2 1 2 a3 1 3 2 a2 2 a1 b1 2 : Nút mạng 1
Q: Tìm ường i từ A ến B có giá (cost) thấp nhất. B lOMoAR cPSD| 36067889 Q&A b4 5 5 a5 2 10 10 b3 10 10 100 A a4 10 b5 3 10 10 5 10 b2 2 10 100 5 5 a3 2 a2 10 a1 b1 3 : Nút mạng 10
Q: Tìm ường i từ A ến B ể ảm bảo
băng thông ít nhất là Mb/ 3( 10(Mb/s). s), B lOMoARcPSD| 36067889 Giải thuật ịnh tuyến
 Khi một giao thức ịnh tuyến cập nhật bảng ịnh tuyến, mục ích
của nó là xác ịnh âu là thông tin tốt nhất ể lưu trong bảng ịnh
tuyến thông qua giải thuật ịnh tuyến.
 Mỗi giải thuật ịnh tuyến xác ịnh thông tin tốt nhất theo cách riêng của nó.
 „Giải thuật tạo ra một số, ược gọi là giá trị metric, cho mỗi
ường qua mạng. Thường thì giá trị metric càng nhỏ thì ường i càng tối ưu.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 
„Có thể tính toán các metric dựa trên một ặc tính ơn lẻ
của ường i; hoặc cũng có thể tính các metric phức tạp hơn
bằng cách kết hợp nhiều ặc tính. Giải thuật ịnh tuyến
 Các metric ược sử dụng phổ biến gồm:
 „Chiều dài ường i (số hopcount/trạmtrung gian)
 „Độ tin cậy/khả dụng
 „Độ trễ ịnh tuyến  „Băng thông
 „Chi phí truyền thông
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
 „Trong một giao thức ịnh tuyến cụ thể,
chỉ một hoặc một vài tham số ược lựa chọn ể tính quãng ường. Giải thuật ịnh tuyến
 Căn cứ vào cách thức trao ổi thông tin và
lựa chọn ường i ngắn nhất, có thể chia ịnh
tuyến ộng thành 2 loại
 „Véc tơ khoảng cách dựa trên giải thuật BellmanFord
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
 „Trạng thái liên kết dựa trên giải thuật Dijkstra
Nguyên lý tuyến tối ưu
Optimal path from I to K over J  distance K d 1 d 2  d 1 + d 2 is minimal J d I  3 Other path from J t
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 o K Set of all optimal routes d 3 > d 2 • from all sources as • to a given destination is d 1 + d 3 > d 1 + d 2 a tree: sink tree
Nguyên lý tuyến tối ưu
Cây bao trùm nhỏ nhất (sink tree) Destination
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com)
Định tuyến vector khoảng cách lOMoAR cPSD| 36067889 (Distance Vector Routing) 
Định tuyến vector khoảng cách là một phương pháp ịnh
tuyến ơn giản, hiệu quả và ược sử dụng trong nhiều giao
thức ịnh tuyến như RIP 
Vector khoảng cách ược thiết kế ể giảm tối a sự liên lạc giữa
các Router. Bản chất của ịnh tuyến vector khoảng cách là
một Router không cần biết tất cả các ường i ến các phân
oạn mạng, nó chỉ cần biết phải truyền một datagram ược
gán ịa chỉ ến một phân oạn mạng i theo hướng nào.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến vector khoảng cách  Mỗi router
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
 Duy trì một bảng (vector) cho biết khoảng cách tốt nhất tới ích
 Các bảng ược cập nhật bởi việc
trao ổi thông tin với các neighbors.
 Mỗi router biết khoảng cách (chi
phí) ến các node kế cận 
Router trao ổi một cách có
chu kỳ các bảng ịnh tuyến với
các node kế cận của nó. 
Dựa trên giải thuật Bellman- Ford Định tuyến vector khoảng cách  Thuật toán
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
 Tại mỗi bước trong một router:
 Nhận bảng ịnh tuyến từ các hàng xóm
 Tính toán khoảng cách tới các hàng xóm 
Tính toán cập nhật lại bảng ịnh tuyến  Các ặc tính:  Lặp  Không ồng bộ  Phân tán Giải thuật Bellman-Ford
 Thuật toán gồm các bước sau:
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
 Mỗi nút tính khoảng cách giữa nó và tất cả các
nút khác trong hệ thống và lưu trữ thông tin này trong một bảng.
 Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận.
 Khi một nút nhận ược các bảng thông tin từ các
nút lân cận, nó tính các tuyến ường ngắn nhất tới
tất cả các nút khác và cập nhật bảng thông tin của chính mình. Giải thuật Bellman-Ford
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
 Lặp: Tiếp diễn tới khi không có thông tin nào thay ổi
Phân bổ: Mỗi nút truyền thông chỉ với hàng xóm trực
tiếp Mỗi router duy trì: 
„Hàng cho mỗi ích khả thi 
„Cột cho mỗi hàng xóm trực tiếp tới nút 
„Mục trong hàng Y và cột Z của nút X: khoảng cách tốt nhất từ X tới Y qua hop tiếp theo là Z 
„Chú ý: Để ơn giản, ở ví dụ này chỉ cho thấy khoảng cách ngắn nhất tới ích. 
Mỗi nút thông báo các hàng xóm chỉ khi có ường i giá thành
thấp nhất tới bất kỳ ích nào ó có thay ổi 
Khi ó hàng xóm lại thông báo tới hàng xóm của nó nếu cần.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 36
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Bellman-Ford neighbor: j A B D A 1 14 5 B 7 8 5 C 6 9 4 D 4 11 2 E Distance table : D(i, j)
node E, for dest. A via neighbor B: D E ( A,B) E D (A,B)= B
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 = c(E,B) + min {D (A,w)}w = 8 + 6 = 14
Định tuyến vector khoảng cách  Ưu iểm:
 Đơn giản, dễ cấu hình Router ít tốn CPU và bộ nhớ  Nhược iểm:
 Hội tụ chậm, dẫn ến việc sai lệch trong bảng ịnh tuyến.
 Chiếm nhiều băng thông khi cập nhật do phải gửi toàn bộ bảng ịnh tuyến
 Tin tốt thì truyền nhanh, tin xấu thì truyền chậm
 Các thay ổi của tô-pô mạng không ược ghi nhận nhanh do các cập
nhật ược lan truyền theo từng nút một.
 Đếm dần ến vô cùng (nếu liên kết hỏng hoặc nút mạng hỏng làm
cho một nút bị tách khỏi một tập các nút khác, các nút này vẫn sẽ
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
tiếp tục ước tính khoảng cách tới nút ó và tăng dần giá trị tính
ược, trong khi ó còn có thể xảy ra việc ịnh tuyến thành vòng tròn)
Định tuyến vector khoảng cách
Example: Propagation of good news
 The count-to-infinity problem  A goes down after initially After this A goes down 2+1 3+1
B thinks that there is a path to A thru C but 4+1 4+1 C itself go to A via B!
Counting will continuous to infinity
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 
If the metric is “Number of Hop”, Infinite can define as longest path+1 
If the metric is “delay”, there is no well-defined upper bound
Định tuyến trạng thái liên kết (Link State)
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 
Mỗi Router xây dựng bên
trong nó một sơ ồ cấu trúc
mạng. Định kỳ, mỗi Router
cũng gửi ra mạng những thông iệp trạng thái.
 Các Router sử dụng bản tin trạng
thái nhận ược từ các Router khác ể
xây dựng sơ ồ mạng. Khi một
Router chuyển tiếp dữ liệu, nó sẽ
chọn ường i ến ích tốt nhất dựa
trên những iều kiện hiện tại.
Định tuyến theo trạng thái liên kết 40 
Trao ổi thông tin ịnh tuyến
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến trạng thái liên kết (Link State) Overview of algorithm:  Mỗi router phải: 
Khám phá ra các hàng xóm của nó và các ịa chỉ mạng của chúng 
Tính trễ hoặc chi phí (cost) tới mỗi hàng xóm của nó 
Tạo gói tin (packet) chứa khoảng cách này 
Gửi gói tin ó tới tất cả các router khác 
Tính toán ường i ngắn nhất (shortest path) tới mọi router khác
Định tuyến trạng thái liên kết
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Algorithm: Khám phá ra các hàng xóm: 
Gửi các gói tin HELLO tới các hàng xóm (chu kỳ 10s,
40s không có trao ổi coi như liên kết bị hỏng)
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến trạng thái liên kết (Link State) 
Tính toán chi phí của liên kết Algorithm: 
Có thể tính trễ quay vòng của gói tin HELLO 
Dựa trên các thông tin ược gửi trong gói tin trả lời
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến trạng thái liên o When to build? • periodically
• when significant events occur Algorithm:
Xây dựng các gói tin về trạng thái liên kết, gồm
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 các thông tin:  Địa chỉ gửi 
Số tuần tự và tuổi của gói tin 
Các hàng xóm và chi phí ến hàng xóm ó
Định tuyến trạng thái liên kết
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Algorithm:
Tính toán ường i ngắn nhất tới các ích 
Với ầy ủ các thông tin về liên kết, router có thể: 
Xây dựng lên topo hoàn chỉnh 
Sử dụng thuật toán Dijkstra ể tính toán ường i ngắn nhất tới tất cả các ích 
Đối với các mạng lớn  Bộ nhớ lưu trữ lớn  Thời gian tính toán lâu
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 
Thuật toán Dijkstra xây dựng cấu trúc dữ liệu dạng
cây, trong ó node hiện tại là gốc, và chứa mọi node khác trong mạng. 
Bắt ầu với một cây ban ầu chỉ chứa chính nó. Sau
ó lần lượt từ tập các node chưa ược thêm vào cây,
nó sẽ thêm node có chi phí thấp nhất ể ến một
node ã có trên cây. Tiếp tục quá trình ến khi mọi node ều ược thêm. 
Cây này sau ó phục vụ ể xây dựng bảng ịnh tuyến,
ưa ra bước truyền kế tiếp tốt ưu, … ể từ một node
ến bất kỳ node khác trên mạng. 47
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Dijkstra 
Các node có cấu hình mạng, chi phí liên kết cho
các liên kết trong cấu hình ó 
Chi phí liên kết (link cost) là một hàm của: 
Số chặng, khoảng cách, lưu lượng trung bình, trễ, … 
Tính toán ường i ngắn nhất (ít chi phí nhất) từ
một node (‘source”) tới tất cả các node khác 
Tạo ra bảng ịnh tuyến (routing table) cho node ó 
Lặp lại: sau k lần lặp lại, sẽ tính ược tuyến ngắn nhất tới k ích  Ký hiệu:
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Dijkstra  N: Tâp ̣ cac node trong ́ mang̣  c(i,j): chi phí liên kêt (link cost) ́ từ node i tới j. Nêu I ́ và j
không kêt ́ nôi ́ trực tiêp ́ với nhau thì c(i,j) nhân ̣ N: A, B, C, D, E, F giá trị vô C(A,C)=5; C(C,A)=5 cung̀ C(B,D)=2; C(D,B)=3 …
 p(v): cac node ́ doc theo ̣ tuyên ́ từ nguôn ̀ Source=A tới v p(F): A-D-E-F D(F)=4
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Dijkstra
 D(v): Giá trị hiên ̣ tai ̣ cua chi ̉ phí tuyên ́ từ nguôn ̀ tới đich V́
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Dijkstra
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 52
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 53
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 54
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 55
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 56
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Dijkstra
 Example: computes least cost paths from node A to all other nodes Step start N D(B),p(B)
D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
0 A 2,A-B 5,A-C 1,A-D infinity infinity
1 AD 2,A-B 4,A-D-C 1,A-D 2,A-D-E infinity 2 ADE 2,A-B 3,A-D-E-C 1,A-D 2,A-
D-E 4,A-D-E-F 3 ADEB 2,A-B 3,A-D-E-C 1,A-D 2,A-D-E 4,A-D-E-F 4 ADEBC
2,A-B 3,A-D-E-C 1,A-D 2,A-D-E 4,A-D-E-F 5 ADEBCF 2,A-B 3,A-D-E-C 1,A-D 2,A-D-E 4,A-D-E-F 5
D(v): Distance (cost) of A to v.P(v): nodes along path fromA to v. 2 3 C B
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 5 A 2 3 1 F 1 2 D 1 E
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Giải thuật Dijkstra  Thảo luận: 
Độ phức tạp thuật toán: 
Giả sử có nnodes, trừ node nguồn 
Vòng lặp ầu tiên: Tìm qua nnodes ể xác ịnh node có giá trị nhỏ nhất, w. 
Vòng lặp thứ hai: Kiểm tra n-1 nodes ể xác ịnh node có giá trị nhỏ nhấ.  
Vòng lặp thứ ba: n-2 nodes, ... 
Tổng số nodes ược tìm: n(n+1)/2 
Như vậy khi n lớn, thuật toán sẽ trở lên phức tạp
Ưu nhược iểm của ịnh tuyến LS
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 
Ưu iểm chính của ịnh tuyến bằng trạng thái kết nối là
phản ứng nhanh nhạy hơn, và trong một khoảng thời
gian có hạn, ối với sự thay ổi kết nối 
Gói ược gửi qua mạng trong ịnh tuyến bằng trạng thái liên
kết thì nhỏ hơn những gói dùng trong ịnh tuyến bằng
vector. Định tuyến bằng vector òi hỏi bảng ịnh tuyến ầy ủ
phải ược truyền i, trong khi ịnh tuyến bằng trạng thái kết
nối thì chỉ có thông tin về “hàng xóm” của node ược
truyền i. Vì vậy, các gói này dùng tài nguyên mạng ở mức không áng kể. 
Khuyết iểm chính của ịnh tuyến bằng trạng thái liên kết là
nó òi hỏi nhiều sự lưu trữ và tính toán ể chạy hơn ịnh tuyến bằng vector.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến phân cấp (1) 
Hai vấn ề cần xem xét khi mạng có số lượng lớn router: 
Phạm vi (scale): Khi số lượng các router lớn, khối lượng thông tin phải
tính toán, lưu trữ và trao ổi giữa các bảng chứa thông tin ịnh tuyến trên
mỗi router (ví dụ các cập nhật về ường i ngắn nhất) cũng trở nên cực lớn.
Các thông tin trao ổi cập nhật giữa các router sẽ “ngốn” toàn bộ băng
thông của ường truyền. Do ó nẩy sinh ra nhu cầu làm giảm ộ phức tạp
trong việc xác ịnh ường i trên một mạng lớn như Internet. 
Quản trị (Administrative automomy) : Mặc dù các nhà thiết kế thường
bỏ qua yêu cầu của các tô chức - chẳng hạn khả năng lựa chọn thuật toán
ịnh tuyến hay che dấu cấu trúc mạng bên trong của tổ chức với bên ngoài
- nhưng trên thực tế ây là những vấn ề quan trọng. Lý tưởng mà nói, một
tổ chức phải giữ khả năng quản trị và kiểm soát mạng máy tính của mình
nhưng vẫn có khả năng kết nối với các mạng bên ngoài.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến phân cấp (2) 
Cả hai vấn ề trên ều có thể giải quyết bằng cách nhóm các
router thành các vùng hay Miền tự trị (Autonomous System - AS). 
Các router trong cùng AS sử dụng cùng một thuật toán ịnh
tuyến (ví dụ như thuật toán LS hay DV) và biết ầy ủ về nhau .
Thuật toán ịnh tuyến chạy trong mỗi AS ược gọi là intra AS routing protocol. 
Như vậy cần phải kết nối các AS với nhau - và vì thế một số
router trong AS phải có thêm nhiệm vụ ịnh tuyến gói tin ra
phía ngoài AS. Các router ịnh tuyến gói tin ra phía ngoài như
vậy ược gọi là gateway router.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến phân cấp (3) 
Thuật toán ịnh tuyến ược sử dụng tại các gateway router là inter AS routing protocol.  Phân cấp ịnh tuyến: 
Chia mạng thành các vùng nhỏ hơn, router trong
vùng này chỉ biết cách ịnh tuyến tới các router khác trong cùng vùng với nó. 
Giảm khối lượng thông tin mà một router cần phải thực hiện ịnh tuyến 
Router không biết về cấu hình nội bộ của các vùng khác.
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến phân cấp (4) 
Gateway là router mà biết về các vùng khác  Ưu iểm: 
Có khả năng mở rộng. Mỗi router cần ít thông tin hơn 
In Ex. Distance table reduce from 17 entries to 7
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889
Định tuyến phân cấp (5)  Nhược iểm: 
Sub optimal routes. The average path length increases Optimal path for 1A to 5C is thru region 2 while in hierarchical is thru region 3
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 Bài tập
Downloaded by D?a (nyeonggot7@gmail.com) lOMoARcPSD| 36067889 65
Downloaded by D?a (nyeonggot7@gmail.com)