1


LỚP MẠNG
Lớp mạng có nhiệm vụ đưa các gói tin từ nguồn qua các đường đến đích. Để đến được
đích, gói tin phải đi từng bước qua nhiều bộ định tuyến trung gian. Điều này trái ngược với
tầng liên kết dữ liệu vốn chỉ chịu trách nhiệm truyền tải các khung từ đầu này đến đầu kia của
kênh truyền vật lý.
Để đạt được mục tiêu này, tầng mạng phải biết được tình trạng của mạng (cách thiết lập của tất
cả các bộ định tuyến và các liên kết) từ đó chọn đường dẫn thích hợp để gói tin đi qua, đối với
mạng lưới lớn cũng vậy. Nó cũng phải chú ý khi lựa chọn đường sao cho tránh được tình trạng
quá tải trên một số đường truyền và bộ định tuyến trong khi các đường khác thì đang rảnh rỗi.
Cuối cùng, vấn đề xảy ra khi các nguồn và đích ở trên hai mạng khác kiểu nhau. Trong chương
này, chúng ta sẽ nghiên cứu tất cả những vẫn đề này và minh họa cho chúng, chủ yếu sử dụng
Internet và giao thức lớp mạng, IP.

5.1 VẤN ĐỀ THIẾT KẾ LỚP MẠNG
Trong các phần sau, chúng ta sẽ giới thiệu về một số vấn đề các nhà thiết kế lớp mạng
phải nắm được. Những vấn đề này bao gồm các dịch vụ cung cấp cho lớp vận chuyển và thiết
kế nội bộ của mạng.
5.1.1 Lưu và chuyển tiếp mạch gói
Trước khi bắt đầu để giải thích các chi tiết của lớp mạng, ta xét một liên mạng dưới
đây. Liên mạng này được biểu diễn trong hình 5-1:
• . Các thành phần chính của mạng là thiết bị của nhà cung cấp đường truyền (ISP’s
equipment) nằm trong hình bầu dục (trong đó các bộ định tuyến được nối lại với nhau
bằng đường truyền), và các thiết bị của khách hàng nằm bên ngoài hình bầu dục.
• Host H1 được nối trực tiếp vào bộ định tuyến A của nhà cung cấp đường truyền bằng
một đường kết nối giống như máy tính cá nhân nối với một modem DSL.
•
Ngược lại, Host H2 nối vào một mạng LAN, mà đó có thể là một mạng Ethernet, rồi
nối với bộ định tuyến F thuộc sở hữu khách hàng. Bộ định tuyến này có xuất xứ từ ISP

(nhà cung cấp đường truyền). Bộ định tuyến F được biểu diễn ngoài hình bầu dục bởi
vì nó không thuộc về ISP.Tuy nhiên với mục đích của chương này, bộ định tuyến vẫn
được coi là một phần của mạng ISP vì chúng chạy các thuật toán tương tự như bộ định
tuyến của ISP(và một quan tâm chính của chúng tôi ở đây là thuật toàn)

2|Page


Hình 5-1. Môi trường của các giao thức trên lớp mạng.
Thiết bị này được sử dụng như sau. Một host với một gói tin cần truyền đi sẽ gửi gói
tin đến bộ định tuyến gần nhất, có thể là bộ định tuyến trên mạng LAN hoặc bộ định tuyến
của nhà cung cấp đường truyền (ISP). Gói tin được lưu trữ ở lại đó cho tới khi nó đã được gửi
hoàn toàn và liên kết đã được hoàn thành sẽ xử lý bằng cách kiểm tra. Sau đó gói tin sẽ được
chuyển tiếp tới bộ định tuyến tiếp dọc theo đường đi, cho đến khi nó đến host đích. Cơ chế
này chính là kỹ thuật lưu và chuyển mạch gói, như đã trình bày trong chương trước.
5.1.2 Các dịch vụ cung cấp cho tầng vận chuyển
Lớp mạng cung cấp dịch vụ cho lớp vận chuyển qua giao diện lớp mạng/lớp vận
chuyển. Một câu hỏi quan trọng là chính xác thì những loại dịch vụ lớp mạng nào cung cấp
cho lớp vận chuyển. Các dịch vụ cần phải thiết kế cẩn thận với các mục tiêu sau:
1. Các dịch vụ này phải được thiết kế một cách độc lập với các kỹ thuật của bộ định
tuyến.
2. Lớp vận chuyển cần được bảo vệ từ số lượng, chủng loại cho đến trình trạng cũng
như mô hình của các bộ định tuyến hiện hành.
3. Địa chỉ mạng phổ biến cung cấp cho lớp vận chuyển phải có sơ đồ đánh số nhất
quán cho dù là LAN hay WAN.
Với các mục tiêu này, các nhà thiết kế lớp mạng để lộ ra rất nhiều khe hở trong việc
thiết kế chi tiết các thông số kỹ thuật của các dịch vụ được cung cấp cho lớp giao vận. Các
khe hở này thoái hóa đi nhanh chóng khi xảy ra xung đột. Lớp mạng cung cấp hai dịch vụ
chính là Dịch vụ định hướng kế nối (Connection – Oriented Service) và Dịch vụ định hướng
không kết nối (Connectionless Service).

Một cộng đồng đại diện cộng đồng Internet lập luận rằng công việc của các bộ định
tuyến chỉ là di chuyển gói tin. Theo quan điểm này (dựa trên 40 năm kinh nghiệm với một
mạng máy tính thực sự), mạng vốn không đáng tin cậy, không quan trọng nó đã được thiết kế
3|Page


như thế nào. Vì vậy, các host phải chấp nhận yếu tố này đó là phải kiểm soát lỗi (phát hiện lỗi
và sửa chữa) và tự điểu khiển lưu lượng.
Quan điểm này dẫn đến việc cho rằng mạng nên cung cấp một Dịch vụ không kết nối
(Connectionless Sirvice), với GỬI GÓI TIN và NHẬN GÓI TIN gốc và một số khác. Đặc
biệt, không nên yêu cầu gói tin hay điều khiểu lưu lượng bởi vì các host sẽ thực hiện nó bằng
mọi cách và thường bằng cách lặp lại nó hai lần. Suy luận này là một ví dụ của nguyên lý
điểm tới điểm, một nguyên tắc thiết kế có rất nhiều ảnh hưởng trong việc định hình Internet
(Saltzer et al., 1984). Hơn nữa, mỗi gói tin phải thực hiện đầy đủ các địa chỉ đích, bởi vì mỗi
gói tin được thực hiện độc lập với gói tin trước đó của nó nếu có.
Một cộng đồng khác, đại diện bởi các công ty điện thoại lại cho rằng mạng nên cung
cấp một dịch vụ đáng tin cậy, Dịch vụ định hướng kết nối (Connection- Oriented Service).
Họ cho tằng với 100 năm kinh nghiệm thành công với hệ thống điện thoại trên toàn thế giới là
một hướng dẫn đáng tin cậy. Nhìn theo cách này, chất lượng dịch vụ là các yếu tố chi phối mà
không phải kết nối trong mạng, chất lượng dịch vụ rất khó để đạt được, đặc biệt là đối với
truyền tin thời gian thực với âm thanh thoại và video.
Ngay cả sau nhiều thập kỷ, ngày nay cuộc tranh luận giữa hai bên vẫn còn rất sôi nổi.
Gần đây, từ X25 trong thập niên 1970 và tiếp đó chuyển vào những năm 1980, dữ liện trên
mạng được sử dụng nhiều, Dịch vụ định hướng nối kết phát triển rộng rãi. Tuy nhiên, kể từ
ngày mạng ARPANET và INTERNET, dịch vụ không nối kết (Connectioness) của tầng mạng
đã phát triển rất phổ biến. Giao thức IP bây giờ phát triển rất thành công và còn đang tiếp tục.
Nó không bị thay thế bởi dịch vụ định hướng kết nối theo công nghệ được gọi là ATM mà đã
được phát triển mạnh vào những năm 1980. Thay vào đó, hiện nay ATM được sử dụng thích
hợp và IP cũng được dùng trên mạng điện thoại. Tuy nhiên Internet phát triển theo định
hướng kết nối các tính năng cũng như cải thiện chất lượng dịch vụ trở nên quan trọng. Hai ví

dụ về công nghệ theo định hướng Dịch vụ kết nối MPLS(MultiProtocol Label Swithching –
Chuyển mạch nhãn đa giao thức), chúng ta sẽ phân tích về nó trong chương nay và VLAN
chúng ta đã nói tới trong chương 4. Cả hai công nghệ đều được sử dụng rất rộng rãi.
5.1.3 Cài đặt dịch vụ không nối kết (Implementation of Connectionless Service)
Ta xem xét hai lớp của dịch vụ mạng có thể cung cấp cho người sử dụng, tìm hiểu xem
cơ chế hoạt động của các lớp này thế nào. Hai tổ chức khác nhau cùng khả quan, tùy thuộc
vào loại dịch vụ được cung cấp. Đối với dịch vụ không kết nối, gói tin được đưa vào mạng cá
nhân và chuyển một cách riêng rẽ với nhau. Không cần phải thiết lập nối kết trước khi truyền
tin. Trong trường hợp này, các gói tin được gọi là thư tín (Datagram) và mạng được gọi là
Datagram Network. Ngược lại trong dịch vụ định hướng kết nối, một đường kết nối giữa bên
gửi và bên nhận phải được thiết lập trước khi các gói tin được gửi đi. Kết nối này được gọi là
4|Page


mạch ảo (Virtual Circuit) tương tự như mạch vật lý được kết nối trong hệ thống điện thoại và
mạng trong trường hợp này được gọi là virtual-circuit network. Trong phần này, ta sẽ nghiên
cứu mạng thư tín (Datagram Network), và tiếp đó sẽ nghiên cứu về các mạng mạch
ảo( Virtual-circuit networks).
Bây giờ chúng ta sẽ trình bày về cách mạng Datagram hoạt động. Giả sử rằng trong
hình 5-2 ,process P1 có một message cần gửi tới process P2. Khi đó P1 sẽ gửi các message
này cho tầng vận chuyển và yêu cầu tầng vận chuyển truyền sang quá trình P2 trên host H2.
Tầng vận chuyển được chạy trên H1, cùng với hệ điều hành của nó. Tầng vận chuyển sẽ gắn
thêm header của nó vào message và chuyển các message xuống tầng mạng

Hình 5-2. Định tuyến trong mạng Datagram.
Ví dụ rằng thông điệp gửi đi lớp gấp 4 lần kích cỡ tối đa của một gói tin, vì thế tầng
mạng phải chia thành 4 gói tin 1,2,3 và 4, và lần lượt gửi từng gói một đến bộ định tuyến A
bằng một giao thức điểm nối điểm (point-to-point) như PPP chẳng hạn. Khi đó nhà cung cấp
đường chuyền (ISP) vượt quá cho phép. Mỗi bộ định tuyến có một bảng thông tin cục bộ chỉ
ra nơi nào có thể gửi các gói tin để có thể đến được những đích đến khác nhau trên mạng. Mỗi

mục của bảng chứa 2 thông tin quan trọng đó là Đích đến và ngõ ra kế tiếp cấn phải chuyển
gói tin để có thể đến được đích đến này. Chỉ có những kết nối trực tiếp mới có thể được sử
dụng. Ví dụ như trong hình 5-2, bộ định tuyến A chỉ có hai đường đi tới B và tới C, do đó mỗi
gói tin đến phải được gửi đến một trong hai bộ bộ định tuyến này, ngay ả khi điểm đích cuối
cùng là một bộ định tuyến khác. Bảng chọn đường của bộ định tuyến A lúc đầu như hình trên
“A’s table initially”.
5|Page


Tại bộ định tuyến A, khi các gói tin 1,2 và 3 đến bộ định tuyến A, nó được lưu trữ tạm
thời để kiểm tra lỗi. Sau đó chúng được chuyển tiếp sang bộ định tuyến C theo thông tin trong
bảng chọn đường của A. Gói tin 1 sau đó tiếp tục được chuyển đến E và sau đó đến F. Sau đó
nó được gói lại trong một khung của tầng liên kết dữ liệu và được chuyển đến host H2 bởi
mạng LAN. Các gói tin 2 và 3 có cùng đường đi tương tự. Tuy nhiên,với gói tin 4 thì khác
một chút. Khi nó đến bộ định tuyến A, nó sẽ chuyển gói tin này sang B mặc dù nó cũng có
đích là F. Vì một số lý do, bộ định tuyến A quyết định gửi gói tin 4 qua một con đường khác
với các gói dữ liệu đầu tiên. Có lẽ nó đã biết được một sự tắc nghẽn ở một nơi nào đó dọc
theo đường ACE và đã cập nhật bảng chọn đường của mình như ở hình với bảng chon đường
của bộ định tuyến A lúc sau “A’s table later”. Các giải thuật chiu trách nhiệm quản lý thông
tin trong bảng trọn đường cũng như thực hiện các quyết định về chọn đường được gọi là giải
thuật chon đường (Routing alogorithms). Giải thuật chọn đường là một trong những chủ đề
chính, chúng tôi sẽ nghiên cứu trong chương này. Chúng ta sẽ thấy nó có một số loại khác
nhau. IP (Internet Protocol), là cơ sở cho toàn bộ mạng Internet, là ví dụ điển hình về dịch vụ
mạng không nối kết. Mỗi gói tin có một đích đến mang đia chỉ IP mà bộ định tuyến sử dụng
để cá nhân chuyển tiếp mỗi gói tin. Các địa chỉ có 32 bit đối với IPv4 và 128 bit đối với IPv6.
Chúng tôi sẽ mô tả chi tiết hơn về IP trong phần sau của chương này.
5.1.4 Cài đặt dịch vụ định hướng kết nối (Connection – Oriented Service)
Đối với dịch vụ kết nối định hướng chúng ta cần một mạng lưới mạch ảo. Chúng ta hãy
cùng nhau giải quyết vấn đề đó. Mục đích của việc sử dụng mạng lưới mạch ảo là để tránh
việc phải chọn lại đường đi mới cho mỗi gói tin gửi đi, như hình 5-2. Thay vào đó, khi một

kết nối được thiếp lập, một tuyến đường từ nguồn gửi đến nguồn nhận được chọn như một
phần của giai đoạn thiết lập kết nối(Connection setup) và được lưu trong bảng chọn đường
của các bộ định tuyến nằm trên đường đi. Tuyến đường đó được sử dụng cho tất cả các gói tin
lưu thông qua kết nối, chính xác theo cách mà hệ thống điện thoại hoạt động. Khi kết nối kết
thúc, các mạch ảo bị xóa. Với dịch vụ định huowgns nối kết, mỗi gói tin mang một số định
dạng để xác định mạch ảo mà nó thuộc về.
Ví dụ như trong hình 5-3. Ở đây host H1 thực hiện một kết nối với host H2 qua kết
nối số 1.Kết nối này được ghi nhận trong mục từ đầu tiên trong bảng chọn đường của các bộ
định tuyến. Dòng đầu tiên trong bảng chọn đường của bộ định tuyến A cho biết những gói tin
mang số nhận dạng nối kết là 1 đến từ máy H1 phải được gửi sang bộ định tuyến C với số
nhận dạng nối kết là 1. Tương tự cho các mục đầu tiên của bộ định tuyến C và E, cũng có số
nhận dạng nối kết là 1.

6|Page


Hình 5-3. Định tuyến trong mạng mạch ảo.
Bây giờ chúng ta hãy cùng xem xét điều gì xảy ra nếu host H3 cũng muốn kết nối với
host H2. Nó chọn số nhận dạng kết nối là 1, vì đây là kết nối đầu tiên đối với H3 và yêu cầu
thiết lập mạch ảo. Điều này dẫn đến các bộ định tuyến phải thêm vào mục từ số 2 trong bảng
chọn đường. Lưu ý rằng chúng ta có một xung đột ở đây bởi vì mặc dù A thì có thể dễ dàng
phân biệt khi số nhận dạng nối kết với H1 là 1 và số nhận dạng kết nối từ H3 cũng là 1, nhưng
C thì không thể. Vì thế, A phải gán một số nhận dạng nối kết khác cho kết nối thứ 2 này để
tránh xung đột. Đó là lý do vì sao các bộ định tuyến cần có khả năng thay thế số nhận dạng
kết nối với các gói tin gửi đi.
Trong một số trường hợp, quá trình này được gọi là đánh dấu chuyển đổi (label
switching). Một ví dụ về mạng dịch vụ định hướng nối kết là MPLS( Multi Protocol Label
Switching). Nó được sử dụng trong mạng ISP trên Internet, với ISP gói tin được gói trong một
thanh MPLS với 20 bit số nhận dạng kết nối hay dấu chuyển đổi. MPLS thường có ít khách
hàng , với thiết lập ISP các kết nối lâu dài với chi phí và lưu lượng truy cập lớn, nhưng nó

đang ngày càng được sử dụng không chỉ vì khi chất lượng của dịch vụ đang được chú trọng
mà còn để cho nhiệm vụ khác là quản lý lưu lượng truy cập ISP. Chúng tôi sẽ nói nhiều hơn
về MPLS trong phần sau của chương này.
5.1.5 So sánh giữa các mạng mạch ảo (Virtual-Circuit) và mạng thư tín (Datagram )

7|Page


Cả mạng lưới mạch ảo (Virtual circuit) mà mạng thư tín (Datagram Network) đều có
những điểm mạnh và điểm yếu. Chúng ta sẽ tóm tắt các ưu nhược điểm của cả hai. Những
điểm chính đượng liệt kê trong bảng hình 5-4.
Vấn đề
Datagram Network
Virtual-Circuit
Thiết lập kết nối
Không cần
Cần thiết
Đánh địa chỉ
Mỗi gói tin chứa đầy đủ Mỗi gói tin chứa số mạch ảo
địa chỉ gửi và nhận.
nhỏ.
Thông tin trạng thái
Bộ định tuyến không
Mỗi mạch ảo phải được lưu lại
cần phải lưu giữ thông
trong bảng trọn đường của bộ
tin trạng thái của các
định tuyến.
nối kết
Chọn đường

Mỗi gói tin có đường đi
Đường đi được chọn khi mạch
khác nhau
ảo được thiết lập, sau đó tất cả
các gói tin đầu đi trên đường
này.
Ảnh hưởng khi bộ định
Không bị ảnh hưởng,
Tất cả các mạch ảo đi qua bộ
tuyến bị hỏng
ngoại trừ gói tin đang
định tuyến bị hỏng đều kết thúc
trên đường truyền bị
hỏng
Chất lượng dịch vụ
Khó đảm bảo
Dễ dàng để thực hiện nếu có đủ
tài nguyên gán trước cho từng
mạnh ảo.
Điều khiển tắc nghẽn
Khó
Dễ dàng nếu có đủ tài nguyên
gán trước cho từng gói mạch ảo
Hình 5-4. So sánh giữa Virtual-Circuit và Datagram Networks
Bên trong một mạng, một số lựa chọn tồn tại giữa các Virtual Circuit và Datagram.
Một chọn lựa (trade-off) là thiết lập thời gian so với địa chỉ phân tích thời gian. Bằng cách sử
dụng mạch ảo yêu cầu một quá trình thiết lập, việc này mất thời gian và thiêu thụ tài nguyên.
Tuy nhiên, khi vấn đề này được giải quyết, hình dạng của những gì để làm với một gói tin
trong một vi mạch ảo trở nên dễ dàng. Bộ định tuyến chỉ sực dụng số mạch để đánh dấu vào
một bảng nhằm mục đích tìm hiểu nơi gói tin sẽ đi. Trong một mạng lưới datagram, thiết lập

là không cần nhưng một thủ tục tra cứu phức tạp hơn là cần thiết để xác định vị trí các mục
cho các điểm đến.
Một vấn đề có liênquan là các địa chỉ đích được sử dụng trong mạng lưới
datagram là nó dài hơn số mạch được sử dụng trong các mạng mạch ảo (virtual-circuit) bởi
vì chúng có một ý nghĩa toàn cầu. Nếu các gói tin có xu hướng khá ngắn, trong đó một địa
chỉ đích đầy đủ trong mỗi gói có thể đại diện cho rất nhiều kể trên, và vì thế dẫn đến một sự
lãng phí băng thông.
8|Page


Tuy nhiên, một vấn đề nữa là số lượng bảng trống cần thiết trong bộ nhớ bộ định
tuyến. Một mạng lưới datagram cần phải có một đầu vào cho mỗi điểm đích, trong khi một
mạng lưới mạch ảo chỉ cần một đầu vào cho mỗi mạch ảo. Tuy nhiên, lợi thế này là không
khách quan khi kết nối cài đặt các gói tin phải được chuyển qua bộ định tuyến, và chúng sử
dụng địa chỉ đích, giống như datagrams làm.
Mạch ảo có một lợi thế trong đảm bảo chất lượng dịch vụ và tránh tắc nghẽn trong mạng nhờ
có tài nguyên ( ví dụ như bộ đếm, băng thông và CPU) có thể được lưu trữ trước khi kết nói
được thiết lập. Một khi các gói tin bắt đầu đến, các băng thông cần thiết và khả năng định
tuyến sẽ sẵn sàng. Với một mạng lưới datagram thì tránh tắc nghẽn là khó khăn hơn. Với hệ
thống xử lý giao dịch (ví dụ: mua sắm gọi lên để xác minh thẻ tín dụng mua hàng), chi phí cần
thiết để thiết lập và xóa một mạch ảo có thể ít hơn việc sử dụng của các mạch. Nếu phần
lớn lưu lượng truy cập dự kiến đều theo loại này, sử dụng ảo mạch bên trong mạng là một
việc khôn ngoan. Mặt khác, với cách dung long-running chẳng hạn như lưu lượng truy cập
VPN giữa hai văn phòng công ty, mạch ảo cố định (mà được thiết lập bằng tay vào cuối tháng
hay năm) có thể mang lại lợi ích.
Mạch ảo cũng có một vấn đề dễ bị hư hỏng. Nếu một bộ định tuyến gặp sự cố và
mất bộ nhớ của nó, ngay cả khi nó khôi phục lại ngay sau đó, tất cả các mạch ảo
đi qua nó sẽ bị hủy bỏ. Ngược lại, nếu một bộ định tuyến datagram gặp sự cố, chỉ là những
người sử dụng có gói dữ liệu được xếp hàng đợi trong bộ định tuyến lúc đó bị hỏng (và có
lẽ không thậm chí đó từ người gửi có khả năng để gửi lại chúng chúng

sau đó). Sự mất mát của một luồng liên lạng là điểm yếu của việc sử dụng mạch ảo, nhưng có
thể dễ dàng khắc phục cho nếu sử dụng datagrams. Datagram cũng cho phép các bộ định
tuyến cân bằng lưu lượng truy cập trên toàn mạng, khi đó các bộ định tuyến có thể bị thay đổi
phần nào một qua một chuỗi dài các gói tin truyền đi.

5.2 ROUTING ALGORITHMS ( THUẬT TOÁN ĐỊNH TUYẾN)
Các chức năng chính của lớp mạng là định tuyến các gói tin từ máy tính nguồn đến
máy tính đích. Trong hầu hết các mạng, các gói sẽ yêu cầu nhiều bước nhảy(hops) để tạo
thành hành trình. Chỉ một số trường hợp ngoại lệ là dành cho mạng phát rộng(broadcast
networks), nhưng trong trường hợp này định tuyến là một issue nếu nguồn và đích không nằm
trên cùng thành phần mạng. Các thuật toán lựa chọn các tuyến đường và cấu trúc dữ liệu mà
chúng sử dụng là một phần quan trọng trong thiết kế lớp mạng.
Các thuật toán định tuyến là một phần của các lớp phần mềm mạng chịu trách nhiệm
về quyết định đâu là đầu ra của một gói tin đến nên được truyền vào. Nếu mạng sử dụng các
gói dữ liệu nội bộ, quyết định này phải được thực hiện một lần nữa cho mỗi gói dữ liệu đến từ
các tuyến đường tốt nhất có thể đã thay đổi kể từ lần cuối cùng. Nếu mạng sử dụng mạch ảo
9|Page


nội bộ, các quyết định định tuyến được thực hiện khi một mạch ảo mới đang được thiết lập.
Sau đó, các gói dữ liệu chỉ cần làm theo các tuyến đường đã được thành lập. Các trường hợp
sau đó đôi khi được gọi là phiên định tuyến vì một tuyến đường vẫn còn hiệu lực cho toàn bộ
một phiên (ví dụ, khi đăng nhập trên một VPN).
Việc đó đôi khi hữu ích để thực hiện một sự phân biệt giữa các định tuyến, làm cho các
quyết định định tuyến được sử dụng, và chuyển tiếp, đó là những gì sẽ xảy ra khi một gói tin
đến. Người ta có thể nghĩ về một bộ định tuyến có hai quá trình bên trong nó. Một trong số
chúng xử lý mỗi gói tin khi nó đến, nhìn lên những đường đi để sử dụng nó trong các bảng
định tuyến. Quá trình này được chuyển tiếp. Các quá trình khác có trách nhiệm điền vào và
cập nhật các bảng định tuyến.
Bất kể các tuyến đường được chọn độc lập cho mỗi gói tin được gửi hay chỉ khi kết nối

mới được thành lập, thì tính chất nhất định được mong muốn trong một thuật toán định tuyến:
chính xác, đơn giản, linh hoạt, ổn định, công bằng và hiệu quả. Tính chính xác và đơn giản
hầu như không yêu cầu bàn luận, nhưng tính linh hoạt có thể ít thấy rõ ràng lúc đầu. Khi một
mạng lớn đặt ngoài không gian, nó có thể được dự kiến sẽ chạy liên tục trong nhiều năm mà
hệ thống sẽ không hỏng . Trong thời gian đó có thể sẽ có phần cứng và phần mềm hỏng của
tất cả các loại. Các máy tính(hots), bộ định tuyếnvà các tuyến sẽ bị lỗi nhiều lần, và các cấu
trúc liên kết sẽ thay đổi nhiều lần. Các thuật toán định tuyến sẽ có thể thay đổi tương ứng với
những thay đổi trong cấu trúc liên kết và truy cập mà không yêu cầu tất cả các công việc trong
tất cả các máy phải được hủy bỏ. Hãy tưởng tượng sự tàn phá nếu mạng cần được khởi động
lại mỗi khi một số bộ định tuyến bị lỗi!
Sự ổn định cũng là một mục tiêu quan trọng đối với các thuật toán định tuyến. Thực tế
có tồn tại các thuật toán định tuyến mà không bao giờ hội tụ về một tập cố định các đường
dẫn, bất kể nó chạy bao lâu. Một thuật toán ổn định đạt đến trạng thái cân bằng và ở duy trì ở
trạng thái đó. Thuật toán định tuyến nên được hội tụ nhanh, sự truyền dữ liệu trong mạng có
thể bị gián đoạn cho đến khi các thuật toán định tuyến đã đạt đến trạng thái cân bằng.
Trước khi chúng ta cố gắng tìm các ưu nhược điểm giữa tính công bằng và hiệu suất,
chúng ta phải quyết định những đặc điểm nào chúng ta tìm kiếm để tối ưu hóa. Giảm thiểu sự
chậm trễ gói tin trung bình để gửi lưu lượng truy cập thông qua mạng một cách hiệu quả là
một ưu điểm rõ ràng, nhưng như vậy là tối đa hóa tổng thông lượng mạng. hơn nữa, hai mục
đích này cũng có mâu thuẫn, kể từ thời điểm hệ thống tuần tự bất kỳ hoạt động gần hết công
suất tức là sẽ có sự trễ dài tuần tự., nhiều mạng cố gắng để giảm thiểu khoảng cách một gói tin
phải , gửi đi hoặc chỉ đơn giản là giảm số lượng các bước nhảy(hops) một gói phải thực hiện.
Hoặc là lựa chọn xu hướng cải thiện sự chậm trễ và cũng làm giảm số lượng băng thông tiêu
thụ cho mỗi gói tin, mà có xu hướng cải thiện thông lượng mạng tổng thể là tốt.
Thuật toán định tuyến được có thể được chia thành hai loại : nonadaptive và adaptive.
Thuật toán nonadaptive không dựa trên quyết định định tuyến của chúng trên bất kỳ phép
đo hoặc ước tính của các cấu trúc liên kết hiện tại và tuyến đường. Thay vào đó, sự lựa chọn
của các tuyến đường sử dụng để có được từ I đến J (cho tất cả các I và J) được tính toán trước,
offline, và tải về các bộ định tuyến khi mạng được khởi động. Thuật toán này đôi khi được
gọi là định tuyến tĩnh. Bởi vì nó không đáp ứng được trong trường hợp định tuyến thất bại,

định tuyến tĩnh được ứng dụng chủ yếu hữu ích cho các tình huống trong đó các lựa chọn định
10 | P a g e


tuyến là rõ rang. Ví dụ, bộ định tuyến F trong hình. 5-3 nên gửi các gói dữ liệu đầu vào mạng
với bộ định tuyến E không phụ thuộc vào điểm đến cuối cùng.

Các thuật toán Adaptive, ngược lại với thuật toán nonadaptive, thay đổi các quyết
định định tuyến của chúng để đáp ứng với những thay đổi trong cấu trúc liên kết, và đôi khi
cũng thay đổi trong tuyến đường. Các thuật toán định tuyến động khác nhau, trong đó chúng
có được thông tin của chúng (ví dụ như, tại địa phương, từ các bộ định tuyến lân cận, hoặc từ
tất cả các bộ định tuyến), khi chúng thay đổi các tuyến đường (ví dụ, khi thay đổi cấu trúc liên
kết, hoặc mỗi giây ΔT như những thay đổi tải), và những số liệu được sử dụng để tối ưu hóa
(ví dụ, khoảng cách, số hop, hoặc ước tính thời gian vận chuyển).
Trong các phần sau, chúng ta sẽ thảo luận về một loạt các thuật toán định tuyến. Các
thuật toán bao gồm mô hình cung cấp ngoài việc gửi một gói tin từ một nguồn tới một đích.
Đôi khi mục đích là để gửi các gói tin đến nhiều, tất cả, hoặc một trong một tập các điểm đến.
Tất cả các thuật toán định tuyến, chúng ta mô tả ở đây đưa ra quyết định dựa trên các cấu trúc
liên kết; chúng ta trì hoãn khả năng ra quyết định dựa trên mức độ giao thông để Sec 5.3.
5.2.1 Nguyên tắc Tối ưu (The Optimality Principle)
Trước khi chúng ta nhận được các thuật toán cụ thể, nó có thể hữu ích để lưu ý rằng
người ta có thể đưa ra tuyến đường tối ưu mà không quan tâm đến cấu trúc liên kết mạng hoặc
lưu lượng truy cập. Phát biểu này được biết đến như là nguyên tắc tối ưu (Bellman,1957).
11 | P a g e


Phát biểu như sau nếu bộ định tuyến J là trên đường đi tối ưu từ bộ định tuyến I tới bộ định
tuyến K, thì đường đi tối ưu từ J tới K cũng thuộc trên cùng một tuyến đường. Để thấy được
điều này,ta gọi phần của tuyến đường từ I đến J là r1 và phần còn lại của tuyến đường là r 2.
Như một hệ quả trực tiếp của các nguyên tắc tối ưu, chúng ta có thể thấy rằng tập hợp

các tuyến đường tối ưu từ tất cả các nguồn tới đích đã tạo thành một cây có gốc là điểm đến.
Một cái cây như vậy được gọi là cây tối thiểu và được minh họa trong hình. 5-6 (b), ở đây
khoảng cách metric là số hop. Mục tiêu của tất cả các thuật toán định tuyến là phát hiện và sử
dụng các cây tối thiểu cho tất cả các bộ định tuyến. Lưu ý rằng không chỉ tồn tại duy nhất một
cây tối thiểu; mà còn có các cây khác có chiều dài đường đi ngắn nhất. Nếu chúng ta cho phép
tất cả các con đường có thể được lựa chọn, các cây trở thành một cấu trúc tổng quát hơn được
gọi là một DAG (Directed Acyclic Graph). DGAs không có vòng lặp. Chúng ta sẽ sử dụng
cây tối thiểu như một cách viết tắt thuận tiện cho cả hai trường hợp. cả hai trường hợp đều
phụ thuộc vào giả định kỹ thuật rằng các đường dẫn không ảnh hưởng lẫn nhau, ví dụ, khi
nghẽn mạng xảy ra trên một tuyến đường thì nó sẽ không thể chuyển hướng sang tuyến đường
khác.
Một cây tối thiểu được coi là một cây khi nó không chứa bất kì vòng lặp nào,do đó mỗi gói tin
sẽ được gửi một số hữu hạn lần và được giới hạn bởi các hop.

Trong thực tế, điều trên xảy ra không hề dễ dàng. Các lien kết và các bộ định tuyến có
thể đi xuống và trở lại trong quá trình hoạt động, vì vậy các bộ định tuyến có thể có các ý
tưởng khác nhau về cấu trúc lien kết hiện tại. ngoài ra, chúng tôi có đưa ra thủ thuật để mỗi bộ
định tuyến có thể có được các thông tin cá nhân để làm cơ sở tính toán cây tối thiểu hoặc có
thể thu tập các thông tin này bằng các thủ thuật khác. Chúng ta sẽ trở lại những vấn đề này
ngay sau đây. Tuy nhiên, nguyên tắc tối ưu và cây tối thiểu cung cấp một chuẩn mực để đánh
giá các thuật toán định tuyến khác.
5.2.2 Thuật toán tìm đường đi ngắn nhất (Shortest Path Algorithm)

12 | P a g e


Chúng ta hãy bắt đầu nghiên cứu về thuật toán định tuyến của chúng ta với một kỹ
thuật đơn giản để tính toán đường đi tối ưu cho một mạng hoàn chỉnh. Những tuyến đường
này là những gì mà chúng ta muốn một thuật toán định tuyến phân phối tìm được, mặc dù
không phải tất cả các bộ định tuyến đều có thể biết tất cả các chi tiết về mạng.

Ý tưởng là để xây dựng một đồ hình cho mạng, với mỗi nút của đồ hình tương ứng với
một bộ định tuyến và mỗi cạnh của đồ hình tương ứng với một thông tin lien lạc, hoặc liên
kết. để chọn một đường đi giữa một cặp các thiết bị định tuyến cho trước, thuật toán phải tìm
ra đường đi ngắn nhất giữa chúng trên đồ hình.
Cần một số giải thích cho khái niệm đường đi ngắn nhất. một cách để đánh giá chiều
dài đường đi là số hop. Sử dụng số liệu này(metric), hai đường ABC và ABE trong hình
Fig.5-7 có chiều dài bằng nhau. Metric khác là khoảng cách địa lý bằng km, trong trường hợp
đó ABC rõ ràng là dài hơn ABE (giả sử con số được rút ra theo tỉ lệ).
Tuy nhiên, nhiều metric khác ngoài các hop và khoảng cách vật lý cũng có thể. Ví dụ,
mỗi cạch có thể được ghi nhãn là trễ trung bình của một gói tin kiểm tra, được đo bằng giờ.
Với nhãn đồ hình này, đường đi ngắn nhất là đường đi nhanh nhất chứ không phải đường đi
với số cạnh hay số km ít nhất.
Trong trường hợp chung, các nhãn trên cạnh có thể được tính toán như một hàm của
khoảng cách, băng thông, lưu lượng trung bình, chi phí thông tin lien lạc, trễ đo, và các yếu tố
khác. Bằng cách thay đổi hàm phụ(weighting function), thuật toán sau đó sẽ tính toán đường
đi ngắn nhất tính theo .

13 | P a g e


Một số thuật toán để tính toán đường đi ngắn nhất giữa hai nút của một đồ hình đã biết.
Được gọi là thuật toán Dijkstra(1959) và tìm đường đi ngắn nhất giữa một nguồn tới tất cả các
đích trong một mạng. Mỗi nút được gắn nhãn(trong ngoặc đơn) với khoảng cách từ nó tới nút
nguồn là tốt nhất. Các khoảng cách phải không âm, vì nó được dựa trên các số liệu thực tế
như băng thông và độ trễ. Ban đầu, những đi không biết, vì vậy tất cả các nút được gán nhãn
là vô cùng. Thu được thuật toán và tìm được đường đi. Một nhãn có thể là tạm thời hoặc vĩnh
viễn. Ban đầu, tất cả nhãn là được dự đoán. Khi nó phát hiện được rằng một nhãn đại diện cho
đường đi ngắn nhất có thể từ nguồn tới nút đó, nó sẽ gán nhãn đó và không thay đổi nữa.
Để minh họa cho thuật toán làm việc gán nhãn, nhìn vào trọng số, đồ thị vô hướng của
hình Fig. 5-7(a), ở đây những trọng số đại diện ví dụ như khoảng cách. Chúng ta muốn tìm

đường đi ngắn nhất từ A tới D. Chúng ta bắt đầu đánh dấu nút A là nút gốc bằng một vòng
tròn. Sau đó chúng ta kiểm tra lần lượt mỗi nút liền kề với A(nút làm việc), gán nhãn lại với
mỗi nút làm việc tới A. Bất cứ khi nào mà một nút đã được gán nhãn, chúng ta cũng gán nó
với nút từ.Trong mạng nếu có nhiều hơn một đường đi ngắn nhất từ A tới D và chúng ta muốn
tìm tất cả chúng, chúng ta nên cần nhớ tất cả nút dò có thể tìm tới một nút với cùng một
khoảng cách.
14 | P a g e


Sau khi kiểm tra tất cả các nút liền kề với A, chúng ta kiểm tra tất cả các nút được gán
nhãn tạm thời trong toàn bộ đồ thị và cố định vĩnh viễn các nhãn có giá trọng số nhỏ nhất, như
hình Fig. 5-7(b). Cái nút được gán cố định ấy trở thành nút làm việc mới.
Bây giờ chúng ta bắt đầu với nút B và kiểm tra tất cả các nút liền kề với B. Nếu tổng
các nhãn trên B và khoảng cách từ B tới các nút nhỏ hơn các nhãn vào nút đó, chúng ta có
một đường đi ngắn nhất, vậy nút được gán nhãn lại.
Sau khi tất cả các nút làm việc đã được kiểm tra và các nhãn được thay đổi nếu có thể,
toàn bộ đồ hình được tìm kiếm với các nút được gán nhãn nhỏ nhất. Nút này được cập nhập
và trở thành nút làm việc cho các vòng tiếp theo. Hình 5-7 biểu diễn sáu bước đầu tiên của
thuật toán.
Để xem tại sao thuật toán làm việc được, nhìn hình Fig. 5-7(c). Tại thời điểm này
chúng ta vừa gán nhãn cố định cho điểm E. Giả sử rằng có một con đường ngắn hơn ABE,
như AXYZE(cho số X và Y). Có thể có hai khả năng: hoặc là nút Z được gán cố định hoặc
không. Nếu có có,thì E được xét, vì vậy đường AXYZ không thể là đường đi ngắn hơn ABE.
Bây giờ hãy xem xét trường hợp Z vẫn chưa được gán nhãn cố định. Nếu nhãn ở Z lớn
hơn hoặc bằng nhãn ở E, thì AXYZ không thể là đường đi ngắn hơn ABE. Nếu nhãn ở Z mà
nhỏ hơn nhãn ở E, thì Z và không phải E là điểm được xét đầu tiên, cho phép E được dò từ Z.
Thuật toán được đưa ra trong hình Fig. 5-8. Các biến toàn cục n và cục bộ miêu tả đồ
hình và được khởi tạo đường đi ngắn nhất được gọi. Sự khác nhau duy nhất giữa chương trình
và thuật toán được mô tả ở trên cho trong hình Fig. 5-8, chúng ta tính toán đường đi ngắn nhất
bắt đầu tại nút đầu cuối, t, chứ không phải nút nguồn, s.

Kể từ khi con đường ngắn nhất từ t tới s trong một đồ thị vô hướng giống như đường đi ngắn
nhất từ s tới t, chúng ta không quan trọng điểm bắt đầu và điểm kết thúc. Lý do tìm kiếm
ngược là mỗi nút được gán nhãn với nút trước nó chứ không phải nút kế sau nó. Khi đường đi
cuối cùng được copy ra biến đầu ra, đường dẫn, đường dẫn đảo ngược. Hai hiệu ứng đảo
ngược hủy bỏ, và kết quả được xuất ra đúng thứ tự.
5.2.3 Flooding(phương pháp làm tràn ngập)
Khi một thuật toán định tuyến được thực hiện, mỗi bộ định tuyến phải đưa ra quyết
định dựa trên kiến thức địa phương, không phải là toàn bộ mạng hoàn chỉnh. Một kỹ thuật địa
phương đơn giản là flooding, trong đó mỗi gói tin đến được gửi đi trên tất cả các đường ngoại
trừ đường có gói dữ liệu vào.
Flooding rõ ràng là sẽ tạo ra số lượng lớn các gói tin trùng lặp, trong thực tế, sẽ tạo ra
một số vô hạn các gói tin trùng lặp nếu không có biện pháp nhằm hãm quá trình này lại. Một
biện pháp là tạo ra một hop đếm chứa trong phần đầu(header) của mỗi gói tin, với gói tin bị
hủy bỏ khi đếm bằng không. Trường hợp lý tưởng, bộ đếm hop được khởi tạo với độ dài của
đường đi từ nguồn tới đích. Nếu bên phát không biết chiều dài đường đi nó có thể khởi tạo
đếm trong trường hợp xấu nhất là đường kính đầy đủ của mạng.
#define MAX NODES 1024 /* maximum number of nodes */
#define INFINITY 1000000000 /* a number larger than every maximum path */
int n, dist[MAX NODES][MAX NODES]; /* dist[i][j] is the distance from i to j */
15 | P a g e


void shortest path(int s, int t, int path[])
{ struct state { /* the path being worked on */
int predecessor; /* previous node */
int length; /* length from source to this node */
enum {permanent, tentative} label; /* label state */
} state[MAX NODES];
int i, k, min;
struct state *p;

for (p = &state[0]; p < &state[n]; p++) { /* initialize state */
p->predecessor = −1;
p->length = INFINITY;
p->label = tentative;
}
state[t].length = 0; state[t].label = permanent;
k = t; /* k is the initial working node */
do { /* Is there a better path from k? */
for (i = 0; i < n; i++) /* this graph has n nodes */
if (dist[k][i] != 0 && state[i].label == tentative) {
if (state[k].length + dist[k][i] < state[i].length) {
state[i].predecessor = k;
state[i].length = state[k].length + dist[k][i];
}
}
/* Find the tentatively labeled node with the smallest label. */
k = 0; min = INFINITY;
for (i = 0; i < n; i++)
if (state[i].label == tentative && state[i].length < min) {
min = state[i].length;
k = i;
}
state[k].label = permanent;
} while (k != s);
/* Copy the path into the output array. */
i = 0; k = s;
do {path[i++] = k; k = state[k].predecessor; } while (k >= 0);
}
Hình 5-8. Dijkstra’s algorithm to compute the shortest path through a graph.
Flooding với một số hop có thể tạo ra một số mũ của các gói tin trùng lặp là hop count

phát triển và định tuyến các gói tin trùng lặp chúng thấy trước đó. Một kỹ thuật tốt hơn cho
flloding là phải có thiết bị định tuyến theo dõi các gói tin đã bị flooding, để tránh việc gửi
chúng ra một lần thứ hai. Một cách để đạt được mục tiêu này là phải có bộ định tuyến nguồn
đặt một số thứ tự trong mỗi gói tin mà nó nhận được từ host của nó. Mỗi bộ định tuyến sau đó
16 | P a g e


cần một danh sách mỗi bộ định tuyến nguồn kể mà số thứ tự có xuất xứ tại nguồn đã nhận
được. Nếu một gói tin đến có trong danh sách, thì nó không bị flooding.
Để ngăn chặn danh sách đang phát triển mà không bị ràng buộc, mỗi danh sách cần
được bổ sung bằng một quầy, k, có nghĩa là tất cả các số thứ tự qua k đã được nhìn thấy. Khi
một gói tin đi vào, nó rất dễ dàng để kiểm tra xem các gói tin đã flooding (bằng cách so sánh
số thứ tự của nó để k;. Nếu như vậy, nó sẽ được hủy. Hơn nữa, toàn bộ danh sách dưới đây k
là không cần thiết, vì k có hiệu quả tóm tắt nó.
Trong thực tế flooding không được áp dụng khi gửi nhiều gói tin, nhưng nó cũng có
một số ứng dụng quan trọng.
Đầu tiên, nó đảm bảo rằng một gói tin được gửi đến tất cả các nút trong mạng. Điều
này có thể gây lãng phí nếu có một nút duy nhất cần nhận gói tin này, nhưng nó sẽ có ứng
dụng hiệu quả trong truyền thông. Trong các mạng không dây, tất cả các tin tức được truyền
đi bởi một trạm có thể được nhận bởi tất cả các trạm khác trong phạm vi phát của nó, trong
thực tế flooding và một số thuật toán sử dụng ưu điểm này.
Thứ hai, flooding ... ngay cả khi có một số lượng lớn các thiết bị định tuyến đề định
tuyến dòng bit đến(ví dụ trong một mạng nằm trong khu vực có chiến tranh), flooding sẽ tìm
được đường đi nếu có đường đi tồn tại, để đưa gói tin đến được đích. Flooding cũng yêu cầu
rất ít trong cách thiết lập. Các bộ định tuyến chỉ cần biết các nút liền kề của chúng. Điều này
có nghĩa là flooding có thể được sử dụng như một khối xây dựng sẵn cho các thuật toán định
tuyến khác có hiệu quả hơn nhưng cần cách xây dựng phức tạp hơn. Flooding cũng có thể
được sử dụng như một thước đo để so sánh với các thuật toán khác. Flooding luôn luôn lựa
chọn đường đi ngắn nhất bởi vì nó chọn mỗi đường đi có thể song song với nhau. Do đó,
không có thuật toán nào khác có thể tạo ra một trẽ ngắn hơn(nếu chúng bỏ qua các trễ phát

sinh do quá trình flooding chính nó).
5.2.4 Distance Vecter Routing(định tuyến vector khoảng cách)
Mạng máy tính thường sử dụng thuật toán định tuyến động có yêu cầu phức tạp hơn
flooding, nhưng hiệu quả hơn bởi vì nó tìm đường đi ngắn nhất cho cấu trúc liên kết hiện tại.
Hai thuật toán định tuyến động trong thực tế được sử dụng phổ biến nhất là định tuyến vecter
khoảng cách và định tuyến trạng thái liên kết. Trong phần này, chúng ta sẽ xem xét các thuật
toán trước. Trong phần sau chúng ta sẽ nghiên cứu các thuật toán sau.
Một thuật toán định tuyến vecter khoảng cách hoạt động bằng cách mỗi bộ định tuyến
tạo ra một bảng( ví dụ một vecter) cho một khoảng cách tốt nhất tới mỗi đích và đường dẫn
nào được sử dụng. Những bảng này sẽ được cập nhật bằng cách trao đổi các thông tin với các
nút liền kề. Cuối cùng mỗi bộ định tuyến sẽ biết được đường dẫn tốt nhất đến đích.
Thuật toán định tuyến vecter khoảng cách đôi khi còn được gọi bằng tên khác, phổ biến nhất
là thuật toán định tuyến Bellman-Ford, sau khi nghiên cứu họ đã phát triển nó(Bellman, 1957;
và Ford and Fulkerson, 1962). Đó là thuật toán định tuyến ARPANET và nó được sử dụng
trong mạng Internet với tên RIP.
Trong thuật toán định tuyến vecter khoảng cách, mỗi bộ định tuyến tạo ra một bảng chỉ
số định tuyến và có chứa một mục nhập cho mỗi bộ định tuyến trong mạng. Mục nhập này
gồm hai phần: phần đường đi sử dụng cho điểm đích và phần ước lượng khoảng cách tới đích
17 | P a g e


đó. Khoảng cách phải được đánh giá như số lượng của hop hoặc sử dụng đơn vị đo khác, như
chúng ta đã đề cập để tính toán được đường đi ngắn nhất.
Bộ định tuyến được giả định là đã biết khoảng cách từ nó đến các nút liền kề. Nếu đơn
vị là hop, thì khoảng cách là hop. Nếu đơn vị là trễ, bộ định tuyến có thể đo trực tiếp nó với
gói tin đặc biệt ECHO mới nhận được và gửi nó lại nhanh nhất có thể.
Ví dụ, giả thiết rằng trễ được sử dụng như một đơn vị đo và bộ định tuyến đã biết trễ từ
nó tới các nút liền kề. Mỗi T msec, mỗi bộ định tuyến gửi tới mỗi nút liền kề một danh sách
độ trễ ước tính tới mỗi đích. Nó cũng nhận được một danh sách tương tự từ các nút liền kề.
Tưởng tượng rằng một trong các bảng vừa đến từ nút liền kề X, với Xi là trễ đo từ X tới bộ

định tuyến i. Nếu bộ định tuyến biết trễ tới X là m msec, nó cũng biết có thể biết được bộ định
tuyến i qua X là Xi+m msec. Bằng cách thực hiện tính toán này cho mỗi nút liền kề, một bộ
định tuyến có thể tìm ra đánh giá tốt nhất và sử dụng đánh giá đó và liên kết tương ứng trong
bảng định tuyến mới. Chú ý rằng bảng định tuyến cũ không được sử dụng trong tính toán.
Quá trình cập nhật này được minh họa trong hình Fig. 5-9. Phần (a) biểu diễn một mạng. Bốn
cột đầu tiên của phần (b) biểu diễn vecter trễ nhận được từ các nút liền

kề của bộ định tuyến J. Trong hình cho thấy 12-msec trễ tới B, 25-msec trễ tới C, 40-msec trễ
tới D,vv...Giả sử J đã được đo hoặc đánh giá độ trễ từ nó tới các nút liền kề thì A,I,H, và K sẽ
có trễ tương ứng là 8,10,12, và 6 msec.
Hãy xem J tính đường đi mới tới G. Nó biết rằng nó có thể nhận từ A 8 msec, và hơn
nữa từ A đến G có thể tính được là 18 msec, vì vậy J biết nó có thể đếm một trễ đến G là 26
msec nếu nó chuyển tiếp gói tin cho G tới A. Tương tự, nó tính trễ từ G qua I, H, và K tương
ứng là 41(31+10), 18(6+12), và 37(31+6) msec. Giá trị tốt nhất là 18 msec và định tuyến sử
dụng qua H. Tính toán tương tự được thực hiện cho tất cả các điểm đích khác, với bảng định
tuyến mới biểu diễn trong cột cuối cùng của hình vẽ.
The Count-to-Infinity Problem
18 | P a g e


Việc định tuyến để tìm ra đường đi tốt nhất trong mạng được gọi là hội tụ
(convergence). Định tuyến vecter khoảng cách thường sử dụng một kỹ thuật đơn giản mà các
bộ định tuyến có thể tính toán đường đi chung ngắn nhất, nhưng trong thực tế nó có một
nhược điểm quan trọng: mặc dù nó hội tụ chính xác, nhưng nó có thể làm chậm tin. Đặc biệt,
nó truyền tin tốt thì nhanh, tin xấu thì chậm. Xét một bộ định tuyến mà định tuyến tới đích X
dài nhất. Nếu trong chuyển tiếp tiếp theo, nút liền kề A bất ngờ gửi một trễ ngắn tới X, bộ
định tuyến chỉ chuyển sang sử dụng các đường tới A để gửi lưu lượng truy cập tới X. Trong
vecter chuyển tiếp, tin tốt sẽ được xử lí.
Để xem cách chúng nhanh chóng lan truyền tin tốt, xét năm nút mạng của hình Fig. 510, ở đây đơn vị trễ là số hop. Giả sử A đi xuống và tất cả bộ định tuyến khác biết điều này.
Nói cách khác, chúng ghi tất cả các trễ tới A là vô cùng.


Khi A đi lên, các bộ định tuyến khác biết được nó qua tốc độ vecter thay đổi. Để đơn
giản hóa, chúng ta sẽ giả thiết rằng tại một điểm nào đó trên mạng mà bắt đầu thay đổi tất cả
các vecter ở tất cả các bộ định tuyến tại cùng một thời điểm. Tại thời điểm đầu tiên của sự
thay đổi, B biết rằng trễ từ nút liền kề bên trái của nó tới A bằng không. Lúc này B làm thay
đổi bảng định tuyến để A là một hop đi sang bên trái. Tất cả các bộ định tuyến khác vẫn được
biết là A đi xuống. Tại thời điểm này, bảng định tuyến của A được biểu diễn ở dòng thứ hai
của hình Fig. 5-10(a). Trong sự thay đổi tiếp theo, C biết rằng B có một đường đi có chiều dài
từ 1 đến A, vì vậy mà nó cập nhật bảng định tuyến của nó để chỉ ra một đường đi chiều dài 2,
nhưng sau này D và E mới nhận được tin tức tốt. Rõ rang, những tin tốt đang lan rộng theo tỉ
lệ hop thay đổi. Trong một mạng đường đi dài nhất có chiều dài N hop, với N thay đổi mỗi
thay đổi sẽ tương ứng với đường dẫn và bộ định tuyến được cập nhật lại.
Bây giờ chúng ta hãy xét hình Fig. 5-10(b), trong đó tất cả các đường dẫn và bộ định
tuyến đều được khởi tạo ở trạng thái ban đầu. Bộ định tuyến B, C, D, và E có khoảng cách
tương ứng tới A là 1, 2, 3 và 4 hop. Đột nhiên, hoặc là A đi xuống hoặc liên kết giữa A và B
bị đứt.
Khi gói tin đầu tiên thay đổi, B không nhận được bất cứ thông tin gì về A. May mắn
thay là C nói “đừng lo lắng; tôi có một đường tới A có chiều dài 2.” B không một chút nghi
ngờ đường đi của C chạy qua nó chính là B, C phải có mười đường dẫn với tất cả đường dẫn

19 | P a g e


tới A có chiều dài 2. Kết quả là B nghĩ nó có thể đến được A qua C với chiều dài đường đi 3.
D và E không cập nhật trạng thái của chúng khi A thay đổi lần đầu tiên.
Trong lần thay đổi thứ hai, C thông báo rằng mỗi nút liền kề của nó phải có một đường
đi tới A có chiều dài 3. Nó chọn một trong số các nút một cách ngẫu nhiên và làm cho nó có
một khoảng cách mới tới A là 4, như biểu diễn ở hàng thứ ba của hình Fig. 5-10(b). thay đổi
tiếp theo xuất hiện trong phần còn lại của hình Fig. 5-10(b).
Từ hình này, nó giải thích lý do rõ rang tại sao tin xấu lại đến chậm: không bao giờ

định tuyến có giá trị lớn hơn giới hạn tối thiểu của các nút liền kề. Dần dần, tất cả các bộ định
tuyến làm việc theo cách của nó đến vô cùng, nhưng số lần thay đổi cần thiết phụ thuộc các
giá trị số được sử dụng đến vô cùng. Vì lý do này, nó thiết lập đến vô cùng cộng 1.
Không hoàn toàn ngạc nhiên, vấn đề này được biết đến như là vấn đề đếm tới vô
cùng(count-to-ìninity). Đã có nhiều cách để giải quyết vấn đề này,ví dụ ngăn chặn các bộ định
tuyến quảng cáo đường đi tốt nhất trở lại nút liền kề được trình bày trong RFC 1058. Tuy
nhiên, không có công nghệ nào trong thực tế giải quyết tốt được vấn đề này. Cốt lõi của vấn
đề là khi X nói với Y rằng nó có một đường đi nào đó, Y có cách nào biết được mặc dù bản
thân Y nằm trên đường đi đó.
5.2.5 Định tuyến Trạng thái Liên kết(Link State Routing)
Định tuyến vector khoảng cách đã được sử dụng trong ARPANET cho đến năm 1979,
thì nó được thay thế bằng định tuyến trạng thái liên kết. Vấn đề chính khiến thuật toán định
tuyến vector khoảng cách không được sử dụng nữa là thuật toán này thường mất rất nhiều thời
gian để hội tụ sau khi cấu trúc hạ tầng(topology) thay đổi(do vấn đề đếm tới vô cùng). Do đó,
có đã được thay thế bằng một thuật toán hoàn toàn mới, được gọi là thuật toán định tuyến
trạng thái lien kết. Các phiên bản của định tuyến trạng thái lien kết được gọi là IS-IS và OSPF
là các thuật toán định tuyến được sử dụng rộng rãi nhất trong các mạng lớn và mạng Internet
ngày nay.
Ý tưởng đằng sau định tuyến trạng thái lien kết khá đơn giản và có thể được đưa ra làm
5 phần. Mỗi bộ định tuyến phải làm những việc sau:
1. Tìm ra các nút liền kề và tìm các địa chỉ mạng của chúng.
2. Thiết lập khoảng cách cho mỗi nút liền kề của nó.
3. Cấu trúc một gói tin với tất cả thông tin vừa có được.
4. Gửi gói tin này tới và nhận các gói tin từ tất cả các bộ định tuyến khác.
5. Tính đường đi ngắn nhất cho mỗi bộ định tuyến.
Trong thực tế, cấu trúc lien kết hoàn chỉnh được phân phối cho mỗi bộ định tuyến. Sau đó
thuật toán Dijktra có thể chạy tại mỗi bộ định tuyến để tìm ra đường đi ngắn nhất cho mỗi bộ
định tuyến. Dưới đây chúng ta xét chi tiết từng bước trong năm bước trên.
Learning about the Neighbors - các nút liền kề
Khi một bộ định tuyến được khởi động, nhiệm vụ đầu tiên của nó là để tìm ra các nút

liền kề. Nó hoàn thành mục tiêu này bằng cách gửi một gói tin HELLO đặc biệt trên mỗi dòng
điểm tới điểm (point-to-point line). Bộ định tuyến ở điểm cuối sẽ được dự kiến sẽ gửi lại tên
20 | P a g e


của mình cho nó. Những tên này phải được chuẩn hóa bởi vì khi một bộ định tuyến ở xa được
báo rằng có tất cả ba bộ định tuyến cùng kết nối tới F, nó là yếu tố quan trọng để xác định
xem liệu cả ba có giống F không.
Khi hai hay nhiều bộ định tuyến được kết nối bằng liên kết broadcast (ví dụ swich,
ring, hay classic Ethernet), thì mạng sẽ phức tạp hơn một chút. Hình Fig. 5-11(a) cho thấy một
broadcast LAN mà ba bộ định tuyến A, C và F được kết nối trực tiếp. Mỗi bộ định tuyến này
được kết nối với một hoặc nhiều bộ định tuyến khác, như trong hình.
Broadcast LAN cung cấp kết nối giữa mỗi cặp bộ định tuyến đính kèm. Tuy nhiên, mô hình
mạng LAN như liên kết đa điểm-điểm (many point-to-point) làm tang kích thước của cấu trúc
lien kết(topology) và dẫn đến thừa thông tin. Một cách tốt hơn cho mô hình mạng LAN là xét
nó như một nút, biểu diễn trên hình Fig.5-11(b). Ở đây, chúng ta giả sử tạo ra nút N kết nối A,
C và F. Một bộ định tuyến được thiết kế trên mạng LAN được chọn để đóng vai trò của N
trong các giao thức định tuyến. Thực tế trên mạng LAN đường đi từ A tới C có thể được đại
diện bằng đường ANC.

Setting Link Costs –thiết lập chi phí liên kết
Thuật toán định tuyến trạng thái liên kết yêu cầu mỗi có một khoảng cách để tìm
đường đi ngắn nhất. Các chi phí để tìm các nút liền kề có thể được thiết lập tự động, hoặc cấu
hình bởi các nhà điều hành mạng. Một cách phổ biến là làm cho chi phí tỉ lệ nghích với băng
thông của liên kết. Ví dụ, 1-Gbps Ethernet có thể chi phí là 1 và 100-Gbps Ethernet có chi phí
là 10. Điều này làm cho việc lựa chọn đường đi tốt hơn có hiệu quả cao hơn.
Nếu mạng được mở rộng ra, trễ của đường dẫn có thể được tính đến vì vậy đường đi
mà ngắn hơn đường dẫn sẽ là sự lựa chọn tốt hơn. Cách trực tiếp nhất để xác định trễ này là
gửi qua một gói ECHO đặc biệt mà các nút khác yêu cầu gửi về ngay lập tức. Bằng cách đo
thời gian đi và chia cho hai, bộ định tuyến gửi có thể nhận được một ước tính tương đối về độ

trễ.
Building Link State Packets –xây dựng các gói tin trạng thái liên kết
21 | P a g e


Một thông tin cần thiết cho sự thay đổi đã được cập nhật, bước tiếp theo cho mỗi bộ
định tuyến là thiết lập một gói tin chứa tất cả dữ liệu. Gói tin bắt đầu với định danh của gói
gửi, theo sau là một dãy số và độ tuổi(sẽ được giải thích sau) và danh sách các nút liền kề. giá
cho mỗi nút liền kề cũng được cho sẵn. ví dụ mạng được trình bày trong hình Fig. 5-12(a) với
các giá được biểu diễn như các nhãn trên các dòng. Các gói dữ liệu trạng thái liên kết tương
ứng với sáu bộ định tuyến trên hình Fig 5-12(b).

Việc thiết lập các gói tin trạng thái liên kết rất dễ dàng. Phần cứng được xác định khi
thiết lập chúng. Một khả năng có thể là để thiết lập chúng theo định kỳ đều đặn. một khả năng
khác có thể là thiết lập chúng khi một số sự kiện quan trọng xảy ra, như một đường hoặc một
nút liền kề đang đi xuống hoặc bị quay trở lại hoặc thay đổi thuộc tính của nó.
Distributing the Link State Packets -phân phối các gói tin trạng thái liên kết
Phần khó khan nhất trong thuật toán là phân phối các gói tin trạng thái liên kết. Tất cả
các bộ định tuyến phải nhận được tất cả các gói tin trạng thái liên kết nhanh nhất và đáng tin
cậy. nếu các bộ định tuyến khác đang sử dụng các phiên bản khác của cấu trúc liên kết, thì các
bộ định tuyến mà chúng tính toán có thể có mâu thuẫn như xảy ra vòng lặp, máy không thể
truy cập, và các vấn đề khác.
Đầu tiên, chúng ta sẽ mô tả các thuật toán phân phối cơ bản. Sau đó chúng ta sẽ cung
cấp một số cải tiến. Ý tưởng cơ bản là sử dụng flooding để phân phối các gói tin trạng thái
liên kết đến tất cả các bộ định tuyến. Để kiểm tra flooding, mỗi gói chứa một dãy số mà được
tang lên sau mỗi lần gửi gói tin mới. Các bộ định tuyến theo dõi tất cả các cặp (bộ định tuyến
nguồn, trình tự) mà chúng gửi. khi một gói tin trạng thái liên kết mới đến nó sẽ được kiểm tra
bằng cách đối chiếu với danh sách các gói đã đến trước. nếu nó là gói mới thì nó sẽ được
chuyển tiếp trên tất cả các đường ngoại trừ đường vừa gửi đến. nếu nó là một bản sao thì nó sẽ
được bỏ đi. Nếu một gói với một dãy số nhỏ hơn gói tin có dãy số cao nhất thì nó sẽ bị từ

chối.
Thuật toán này có một số vấn đề nhưng chúng ta có thể kiểm soát chúng. Đầu tiên, nếu
dãy số tuần hoàn sẽ sinh ra vấn đề. Giải pháp là sử dụng một chuỗi 32 bit. Với một gói tin

22 | P a g e


trạng thái liên kết trong một giây, nó sẽ tuần hoàn 137 năm vì vậy khả năng này có thể được
bỏ qua.
Thứ hai, nếu một bộ định tuyến không bao giờ bị treo, nó sẽ mất số thứ tự của nó. Nếu
nó bắt đầu lại từ 0 thì gói tiếp theo nó gửi sẽ bị từ chối như một bản sao.
Thứ ba, nếu một dãy số bao giờ bị hỏng và 65, 540 nhận được thay vì 4(một bit lỗi), gói 5sẽ bị
từ chối, vì các số này bây giờ được thay bằng 65,540.
Các giải pháp cho tất cả các vấn đề này bao gồm tuổi của mỗi gói tin sau khi giảm số
thứ tự của nó mỗi lần một giây. Khi tuổi của nó giảm đến không, thông tin từ bộ định tuyến sẽ
được bỏ đi. Thông thường, một gói tin đến sau mỗi 10 giây thì các thông tin tìm ra cho việc
định tuyến chỉ khi bộ định tuyến đi xuống (hoặc là sau sự kiện có sáu gói tin liên tiếp bị mất).
Các vấn đề về tuổi cũng được giảm đi bởi mỗi bộ định tuyến trong quá trình flooding ban đầu,
để đảm bảo không có gói tin nào bị mất và hoạt động trong một trong một khoảng thời gian
nhất định (một gói tin mà có tuổi bằng không sẽ bị bỏ đi).
Một số cải tiến cho thuật toán này làm cho nó có hiệu quả hơn. Khi một gói tin trạng
thái liên kết đến một bộ định tuyến bằng flooding, nó không được xếp hàng. Thay vào đó, nó
được đặt trong một vùng chờ. Nếu một gói tin trạng thái liên kết khác cũng có nguồn đến
giống nó trước khi gói tin đầu tiên được chuyển đi thì số thứ tự của nó sẽ được so sánh. Nếu
chúng bằng nhau thì các sự sao chép sẽ được bỏ đi. Nếu chúng khác nhau gói cũ sẽ bị bỏ đi.
Để trách các lỗi trên các liên kết, tất cả các gói tin trạng thái liên kết đều được chấp nhận.
Cấu trúc dữ liệu được sử dụng ở bộ định tuyến B của mạng biểu diễn trong hình Fig. 512(a) được mô tả trong hình Fig. 5-13. Mỗi hàng tương ứng với một gói tin trạng thái liên kết
mới đến, nhưng vẫn chưa được xử lý xong. Các bảng mà chứa gói tin gốc gồm số thứ tự, tuổi,
và dữ liệu. Ngoài ra, có cờ để gửi cho ba liên kết của B (tới A, C, và F tương ứng). cờ gửi có
nghĩa là gói tin phải được gửi vào địa chỉ liên kết. những cờ chấp nhận có nghĩa là nó phải

được thừa nhận.
Trong hình Fig. 5-13, gói tin trạng thái liên kết đến trực tiếp từ A, vì vậy nó phải gửi
tới C và F và chấp nhận A như được chỉ ra bởi bit cờ. tương tự, gói tin từ F được chuyển tiếp
tới A và C và chấp nhận F.

Tuy nhiên, trạng thái với gói tin thứ ba từ E là khác nhau. Nó đến hai lần, một lần qua
EAB và một lần qua EFB. Do đó, nó chỉ gửi đến C nhưng nó phải chấp nhận cả A và F như là
bit cờ.
23 | P a g e


Nếu một bản copy đến khi bản gốc vẫn còn trong bộ đệm, các bit phải được thay đổi.
ví dụ, nếu một bản copy của C đến từ F trước khi kí tự thứ tư trong bảng được chuyển tiếp,
sáu bit sẽ được thay đổi thành 100011.
Computing the New Routes- tính toán đường đi
Khi một bộ định tuyến đã nhận được một bộ đầy đủ các gói dữ liệu trạng thái liên kết,
nó có thể xây dựng toàn bộ mạng bởi vì tất cả các liên kết đã được biểu diễn. Trên thực tế,
mỗi liên kết được biểu diễn hai lần, một lần cho mỗi hướng. Các hướng khác nhau có thể có
giá khác nhau. Có thể tính toán đường đi ngắn nhất sau khi tìm các đường đi khác từ bộ định
tuyến A tới B thay vì từ bộ định tuyến B đến A.
Bây giờ thuật toán Dijktra có thể được chạy để xây dựng các con đường ngắn nhất có
thể tới đích. Kết quả của thuật toán này cho các bộ định tuyến mà liên kết sử dụng để đến
được đích. Thông tin này được cài đặt trong bảng định tuyến, và hoạt động bình thường được
nối lại.
So với khoảng cách định tuyến vecto, định tuyến trạng thái liên kết đòi hỏi nhiều bộ nhớ và
tính toán. Cho một mạng với n bộ định tuyến, mỗi bộ định tuyến có k nút liền kề, bộ nhớ cần
thiết để lưu trữ dữ liệu đầu vào tỷ lệ thuận với kn. Ngoài ra một vấn đề với các mạng lớn là
thời gian tính toán nhanh hơn kn, ngay cả với các cấu trúc dữ liệu hiệu quả nhất. Tuy nhiên
trong nhiều tình huống thực tế, định tuyến trạng thái liên kết tốt hơn bởi vì nó không gặp phải
các vấn đề hội tụ chậm.

Định tuyến trạng thái liên kết được sử dụng rộng rãi trong các mạng thực tế. Nhiều ISP
sử dụng IS-IS(Intermediate System- Intermediate System) giao thức trạng thái liên kết (Oran
1990). Nó được thiết kế cho một mạng lướn đầu gọi là DECnet, sau đó thông qua ISO để sử
dụng với giao thức ISO và sau đó sử đổi để sử dụng với các giao thức khác nữa, đáng chú ý
nhất là IP. OSPF (Open Shortest Path First) chính là các giao thức trạng thái liên kết khác. Nó
được thiết kế bởi IETF vài năm sau khi IS-IS và thông qua nhiều đổi mới được thiết kế cho
IS-IS. Những đổi mới này gồm một phương pháp tự ổn định các cập nhật trạng thái liên kết
flooding, các bộ định tuyến được thiết kế trên mạng LAN, các phương pháp tính toán và phân
chia con đường hỗ trợ nhiều số liệu. Kết quả là có rất ít sự khác biệt giữa IS-IS và OSPF. Một
sự khác biệt quan trọng là IS-IS có thể mang thông tin về nhiều giao thức lớp mạng tại cùng
một thời điểm (ví dụ IP,IPX, và Apple Talk). OSPF không có tính năng này và đó là một
thuận lợi trong môi trường đa giao thức. Chúng ta sẽ bàn tới OSPF trong phần Sec. 5.6.6.
Một nhận xét chung về các thuật toán định tuyến cũng theo thứ tự. Trạng thái liên kết,
vecto khoảng cách, và các thuật toán khác dựa trên xử lý tất cả các bộ định tuyến để tính toán
đường đi. Vấn đề với phần cứng hoặc phần mềm ở một số bộ định tuyến có thể bị phá hủy
trên mạng. Nếu một bộ định tuyến không chuyển tiếp các gói tin tuyeend đường này sẽ không
làm việc đúng như mong đợi. Nếu nó chạy ra khỏi bộ nhớ hoặc tính toán sai tuyến đường thì
sẽ có sự cố xảy ra. Khi mạng phát triển lên đến phạm vi hàng chục, hàng tram, hoặc hàng
ngàn các nút thì xác xuất của một số bộ định tuyến giảm đi đáng kể. mục đích là để hạn chế
các thiệt hại xảy ra không thể tránh khỏi. Perlman (1988) trình bày chi tiết các vấn và giải
pháp.
24 | P a g e


5.2.6 Hierarchical Routing – định tuyến phân cấp
Khi các mạng phát triển về kích thước thì bảng định tuyến bộ định tuyến cũng phát
triển tương ứng. tại một thời điểm nhất định, mạng có thể lên đến điểm mà nó không còn khả
thi cho mỗi bộ định tuyến để có một mục nhập cho tất cả các bộ định tuyến khác, vì vậy việc
định tuyến sẽ phải được thực hiện theo thứ bậc, cũng như ở các mạng điện thoại.
Khi định tuyến phân cấp được sử dụng, các bộ định tuyến được chia thành những vùng. Mỗi

bộ định tuyến biết tất cả các chi tiết làm thế nào để định tuyến các gói tin tới các điểm đến
trong khu vực riêng của mình nhưng không biết gì về cấu trúc nội bộ của các khu vực khác.
Khi các mạng khác nhau liên kết với nhau, tự nhiên coi như là một khu vực riêng biệt để giải
phóng các bộ định tuyến trong một mạng khỏi phải biết cấu trúc của những khu vực khác.
Đối với các mạng lớn, một hệ thống phân cấp hai cấp có thể không đầy đủ; nó có thể là
cần thiết để nhóm các vùng thành các cụm, các cụm thành các vùng, các khu thành các nhóm,
và như vậy, cho đến khi chúng ta chạy ra khỏi tên. Ví dụ về một hệ thống phân cấp đa cấp,
xem xét làm thế nào một gói tin có thể được chuyển từ Berkeley, California, tới Malindi,
Kenya. Các bộ định tuyến Berkeley sẽ biết topo chi tiết trong tiểu bang California nhưng sẽ
gửi tất cả lưu lượng truy cập out-of-state đến bộ định tuyến Los Angeles. Các bộ định tuyến
Los Angeles sẽ có thể tuyến đường giao thông trực tiếp với các bộ định tuyến khác trong nước
nhưng sẽ gửi tất cả lưu lượng nước ngoài đến New York. Các bộ định tuyến New York sẽ
được lập trình để điều khiển tất cả các lưu lượng truy cập đến các bộ định tuyến trong nước
đến trách nhiệm xử lý lưu lượng nước ngoài, ở Nairobi. Cuối cùng, các gói tin sẽ làm việc
theo cách của mình xuống cây ở Kenya cho đến khi nó đã đến Malindi.
Hình 5-14 cho một ví dụ về số lượng của định tuyến trong một hệ thống phân cấp hai cấp với
năm khu vực. Các bảng định tuyến đầy đủ cho bộ định tuyến 1A có 17 mục, như thể hiện
trong hình Fig. 5-14 (b). Khi định tuyến được thực hiện theo thứ bậc, như trong hình Fig. 5-14
(c), có mục cho tất cả các bộ định tuyến địa phương, như trước đây, nhưng tất cả các khu vực
khác được hội tụ thành một bộ định tuyến duy nhất, vì vậy tất cả lưu lượng truy cập cho khu
vực 2 đi qua các đường 1B-2A, nhưng phần còn lại của điều khiển từ xa giao thông đi qua các
đường 1C-3B. Định tuyến phân cấp đã giảm bảng 17 mục thành 7 mục. Là tỷ số giữa số khu
vực về số lượng các thiết bị định tuyến cho mỗi khu vực phát triển, việc tiết kiệm không gian
bảng tăng.
Thật không may, những lợi ích trong không gian không được tự do. Có một vấn đề là
phải tăng chiều dài đường đi. Ví dụ, con đường tốt nhất từ 1A 5C là thông qua khu vực 2,
nhưng với định tuyến phân cấp tất cả các lưu lượng truy cập đến khu vực 5 đi qua khu vực 3,
bởi vì đó là tốt cho hầu hết các điểm đến trong khu vực 5.

25 | P a g e