TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN ĐIỆN TỬ VIỄN THÔNG
********** **********
BÀI TẬP LỚN
MÔN HỌC: TỔ CHỨC VÀ QUY HOẠCH MẠNG VIỄN THÔNG
Đề tài: “Các Thuật Toán Và Phương Thức Định Tuyến Trong Mạng ”
Giảng viên hướng dẫn: Nguyễn Văn Thắng
Nhóm sinh viên thực hiện:
Họ và tên SHSV Lớp

HÀ NỘI 4/2012
Mục Lục
2
I. Mở đầu
Một trong những hoạt động của mạng nói chung là việc truyền dữ liệu từ nguồn tới
đích. Định tuyến là một chức năng không thể tách rời của mạng khi truyền dữ liệuh từ nguồn
tới đích và có ý nghĩa đặc biệt quan trọng trong việc thiết kế và tối ưu mạng. Cấu trúc mạng,
giải pháp công nghệ và phương pháp định tuyến là 3 vấn đề liên quan mật thiết với nhau và
quyết định chất lượng hoạt động của mạng. Chính vì vậy, bài toán định tuyến cần được quan
tâm nghiên cứu để nhằm tối ưu hóa hiệu suất sử dụng tài nguyên mạng.
Trên thế giới đã có nhiều nghiên cứu về các phương pháp định tuyến, với mục đích
chủ yếu là tìm ra những phương pháp định tuyến thích hợp để áp dụng vào thực tế mạng
lưới. Trong thời gian gần đây, xu hướng định tuyến theo “giá” trên mạng đã trở thành một
chủ đề nghiên cứu quan trọng. Thông thường, lợi ích mang lại trên mạng được tối đa bằng
việc tối ưu hóa các hàm mục tiêu. Tùy thuộc vào cấu trúc và các đường truyền trên mạng
mà các hàm mục tiêu và ràng buộc đi theo sẽ khác nhau.
3
II. Nội dung
1. Giới thiệu về định tuyến:
Định tuyến là quá trình tìm đường đi để truyền tải thông tin trong liên mạng từ nguồn
đến đích. Nó là một chức năng được thực hiện ở tầng mạng. Chức năng này cho phép router

dưới đây này là các thuật ngữ đã được công nhận và được sử dụng thường xuyên chương này.
Một graph G, được định nghiã bởi tập hợp các đỉnh V và tập hợp các cạnh E. Các đỉnh
thường được gọi là các nút và chúng biểu diễn vị trí (ví dụ một điểm chứa lưu lượng hoặc một
khu vực chứa thiết bị truyền thông). Các cạnh được gọi là các liên kết và chúng biểu diễn
phương tiện truyền thông. Graph có thể được biểu diễn như sau:
G=(V, E)
5
Hình 2 là một ví dụ của một graph.
Hình 2: Một graph đơn giản
Mặc dù theo lý thuyết, V có thể là tập hợp rỗng hoặc không xác định, nhưng thông
thường V là tập hợp xác định khác rỗng, nghĩa là có thể biểu diễn
V={v
i
| i=1,2, N}
Trong đó N là số lượng nút. Tương tự E được biểu diễn:
E={e
i
| i=1,2, M}
Một liên kết, ej, tương ứng một kết nối giữa một cặp nút. Có thể biểu diễn một liên kết ej
giữa nút i và k bởi
e
j
=(v
i
,v
k
)
hoặc bởi
e
j

mạng lẫn quá trình hoạt động bên trong của các thuật toán, vì vậy sự khác nhau cần phải luôn
được phân biệt rõ ràng. Về mặt hình học các liên kết là các đường thẳng kết nối các cặp nút còn
các cung là các đường thẳng có mũi tên ở một đầu, biểu diễn chiều của cung.
Một graph có các liên kết gọi là graph vô hướng, tuy nhiên một graph có các cung gọi là
graph hữu hướng. Một graph hữu hướng có thể có cả các liên kết vô hướng. Thông thường ,
các graph được giả sử là vô hướng, hoặc sự phân biệt đó là không có ý nghĩa.
Có thể có khả năng xảy ra hiện tượng xuất hiện nhiều hơn một liên kết giữa cùng một cặp
nút (điều này tương ứng với việc có nhiều kênh thông tin giữa hai chuyển mạch). Những liên kết
như vậy được gọi là các liên kết song song. Một graph có liên kết song song gọi là một
multigraph.
Cũng có khả năng xuất hiện các liên kết giữa một nút nào đó và chính nút đó. Những
liên kết đó được gọi là các self loop. Chúng ít khi xuất hiện và thường xuất hiện do việc xem hai
nút như là một nút trong quá trình lập mô hình graph cho một mạng hoặc phát sinh trong quá
trình thực hiện một thuật toán có việc hợp nhất các nút. Hình 4.2 minh hoạ một graph có các liên
kết song song và các self loop. Một graph không có các liên kết song song hoặc các self loop gọi
là một graph đơn giản. Việc biểu diễn và vận dụng các graph đơn giản là tương đối dễ dàng, vì
vậy giả thiết rằng các graph được xem xét là các graph đơn giản. Nếu có sự khác biệt với giả
thiết này, chúng sẽ được chỉ ra.
7
3. Phân loại định tuyến :

Hình 3: Phân loại định tuyến
3.1. Định tuyến tĩnh:
Đối với định tuyến tĩnh các thông tin về đường đi phải do người quản trị mạng cập
nhật cho các router. Khi cấu trúc mạng có bất kỳ thay đổi nào thì chính người quản trị mạng
phải xóa hoặc thêm các thông tin về đường đi cho các router. Những loại này gọi là đường
đi cố định. Đối với hệ thống mạng nhỏ, ít có thay đổi thì công việc này đỡ mất công hơn.
Chính vì định tuyến đòi hỏi người quản trị mạng phải cấu hình mọi thông tin về đường đi
cho các router nên nó không có được tính linh hoạt như định tuyến động. Trong những hệ
thống mạng lớn, định tuyến tĩnh thường được sử dụng kết hợp với giao thức định tuyến

ứng dụng là không thực tế. Tuy vậy lan tràn gói có thể sử dụng trong những ứng dụng sau.
Trong ứng dụng quân sự, mạng sử dụng phương thức lan tràn gói để giữ cho mạng luôn
luôn hoạt động tốt khi đối mặt với quân địch.
Hình 5: Định tuyến lan tràn gói
Trong những ứng dụng cơ sở dữ liệu phân bố, đôi khi cần thiết phải cập nhật tất cả
cơ sở dữ liệu. Trong trường hợp đó sử dụng lan tràn gói là cần thiết. Ví dụ sự dụng lan tràn
gói để gửi cập nhật bản định tuyến bởi vì cập nhật không dựa trên độ chính xác của bảng
định tuyến. 40
Phương pháp lan tràn gói có thể được dùng như là đơn vị để so sánh phương thức
định tuyến khác. Lan tràn gói luôn luôn chọn đường ngắn nhất. Điều đó dẫn đến không có
giải thuật nào có thể tìm được độ trễ ngắn hơn. Một biến đổi của phương pháp lan tràn gói
là lan tràn gói có chọn lọc. Trong giải thuật này, router chỉ gửi gói đi ra trên các đường mà
đi theo hướng đích. Điều đó có nghĩa là không gửi gói đến những đường mà rõ ràng nằm
trên hướng sai
10
3.2.2. Định tuyến ngẫu nhiên (random walk):
Trong phương pháp định tuyến này, router sẽ chuyển gói đi đến trên một đường đầu
ra được chọn một cách ngẫu nhiên. Mục tiêu của phương pháp này là các gói lang thang
trong mạng cuối cùng cũng đến đích. Với phương pháp này giúp cho quá trình cân bằng tải
giữa các đường. Cũng giống như phương pháp định tuyến lan tràn gói, phương pháp này
luôn đảm bảo là gói cuối cùng sẽ đến đích. So với phương pháp trước thì sự nhân rộng gói
trong mạng sẽ ít hơn. Nhược điểm của phương pháp này là đường từ nguồn đến đích có thể
dài hơn đường ngắn nhất. Do đó trễ đường truyền sẽ dài hơn sẽ trễ ngắn nhất thực sự tồn tại
trong mạng.
- Gói tin được gửi đến mỗi đầu ra với một xác xuất nào đó
- So với flooding,số lượng gói truyền đi nhỏ hơn
- Đường đi ngắn nhất có thể không nằm trong số đường được chọn
Hình 6: Định tuyến ramdom walk
3.2.3. Định tuyến ngẫu nhiên (hot potato):
Định tuyến riêng biệt là loại định tuyến mà router quyết định định tuyến đi chỉ dựa

12
3.3.1. Định tuyến động (minimum spanning tree):
Có thể sử dụng quá trình trình duyệt để tìm một cây bắc cầu nếu có một cây bắc cầu
tồn tại. Cây tìm được thường là cây vô hướng. Việc tìm cây "tốt nhất" thường rất quan trọng
. Chính vì vậy, chúng ta có thể gắn một "độ dài" cho mỗi cạnh trong graph và đặt ra yêu cầu
tìm một cây có độ dài tối thiểu. Thực tế, "độ dài" có thể là khoảng cách, giá, hoặc là một đại
lượng đánh giá độ trễ hoặc độ tin cậy. Một cây có tổng giá là tối thiểu được gọi là cây bắc
cầu tối thiểu. Nói chung, nếu graph là một graph không liên thông, chúng ta có thể tìm được
một rừng bắc cầu tối thiểu. Một rừng bắc cầu tối thiểu là một tập hợp các cạnh nối đến
graph một cách tối đa có tổng độ dài là tối thiểu. Bài toán này có thể được xem như là việc
lựa chọn một graph con của graph gốc chứa tất cả các nút của graph gốc và các cạnh được
lựa chọn. Đầu tiên, tạo một graph có n nút, n thành phần và không có cạnh nào cả. Mỗi lần,
chúng ta chọn một cạnh để thêm vào graph này hai thành phần liên thông trước đó chưa
được kết nối được liên kết lại với nhau tạo ra một thành phần liên thông mới (chứ không
chọn các cạnh thêm vào một thành phần liên thông trước đó và tạo ra một vòng). Vì vậy, tại
bất kỳ giai đoạn nào của thuật toán, quan hệ: n=c+e .
luôn được duy trì, ở đây n là số lượng nút trong graph, e là số cạnh được lựa chọn
tính cho tới thời điểm xét và c là số lượng thành phần trong graph tính cho tới thời điểm xét.
Ở cuối thuật toán, e bằng n trừ đi số thành phần trong graph gốc; nếu graph gốc là liên
thông, chúng ta sẽ tìm được một cây có (n-1) cạnh. Quá trình duyệt cây sẽ tìm ra một rừng
bắc cầu. Tuy nhiên, chúng ta thường không tìm được cây bắc cầu có tổng độ dài tối thiểu.
Để tìm ra cây bắc cầu tối thiểu người ta sử dụng 2 thuật toán: prime và kruskal.
3.3.2. Định tuyến động (shortest path tree):
Bài toán tìm các đường đi ngắn nhất là một bài toán khá quan trọng trong quá trình thiết
kế và phân tích mạng. Hầu hết các bài toán định tuyến có thể giải quyết như giải quyết bài toán
tìm đường đi ngắn nhất khi một "độ dài " thích hợp được gắn vào mỗi cạnh (hoặc cung) trong
mạng. Trong khi các thuật toán thiết kế thì cố gắng tìm kiếm cách tạo ra các mạng thoả mãn tiêu
chuẩn độ dài đường đi.
13
Bài toán đơn giản nhất của loại toán này là tìm đường đi ngắn nhất giữa hai nút cho

14
Hình minh họa U Cạnh (u,v) V \ U Mô tả
{}
{A,B,C,
D,E,F,G}
Đây là đồ thị có trọng
số ban đầu. Các số là
các trọng số của các
cạnh.
{D}
(D,A) = 5 V
(D,B) = 9
(D,E) = 15
(D,F) = 6
{A,B,C,E
,F,G}
Chọn một cách tùy ý
đỉnh D là đỉnh bắt đầu.
Các
đỉnh A, B, Evà F đều
được nối trực tiếp
tớiD bằng cạnh của đồ
thị. A là đỉnh
gần D nhất nên ta
chọn A là đỉnh thứ hai
của cây và thêm
cạnh ADvào cây.
{A,D} (D,B) = 9
(D,E) = 15
(D,F) = 6 V

(B,C) = 8
(B,E) = 7 V
(D,B) = 9
chu trình
(D,E) = 15
(F,E) = 8
(F,G) = 11
{C,E,G}
Ở bước này ta chọn
giữa C, E, và G. C có
khoảng cách tớiB bằng
8, E có khoảng cách
tớiB bằng 7, và Gcó
khoảng cách tới F bằng
11. Elà đỉnh gần nhất,
nên chọn đỉnh Evà
cạnh BE.
{A,B,D,
E,F}
(B,C) = 8
(D,B) = 9
chu trình
(D,E) = 15
chu trình
(E,C) = 5 V
(E,G) = 9
(F,E) = 8
chu trình
(F,G) = 11
{C,G}

chu trình
(D,B) = 9
chu trình
(D,E) = 15
chu trình
(F,E) = 8
chu trình
(F,G) = 11
chu trình
{}
Hiện giờ tất cả các đỉnh
đã nằm trong cây và cây
bao trùm nhỏ nhất được
tô màu xanh lá cây.
Tổng trọng số của cây
là 39.
4.2. Thuật toán Kruskal:
- B1: khởi tạo T lúc đầu là một đồ thị rỗng.
- B2: nếu T đã gồm đúng n-1 cạnh của G thì t là cây bao trùm cần tìm. Kết thúc.
- B3: nếu T còn chưa đủ n-1 cạnh,thì vì G liên thông, nên G có không ít hơn n-1 cạnh, do đó còn
các cạnh của G chưa thuộc T. trong các cạnh của G chưa thuộc t có các cạnh không tạo ra chu
trình với các cạnh đã có trong T, chọn cạnh v có trọng số nhỏ nhất trong các cạnh ấy bổ sung
vào T. Loại bỏ những cạnh tạo thành chu trình.
17
- B4: quay lại B2.
VÍ DỤ:
Ảnh minh họa
18
4.3. Thuật toán Dijkstra:
Cho Graph liên thông G={V,E}, cần tìm khoảng cách ngắn nhất và đường đi từ nút s

o
• =0 với v =u
o
20
Tạo dàng đợi FIFO Q của các nút quét. Đưa s vào Q.
B2: lấy ra đỉnh đầu tiên trong hàng đợi h, kiểm tra giá của các nút lân cận U,nếu d(u )>
d(h)+ d(hu) thì đưa u vào hàng đợi và gán:
d(u)= d(h)+ d(hu)
π(u)= h
B3: lặp lại B2 cho đến khi Q={Ø}

5. Một số giao thức định tuyến động hiện nay:

Để quản trị mạng dễ dàng hơn, người ta đã cố gắng nghiên cứu định tuyến động theo các
hướng khác nhau như: tìm đường đi ngắn nhất và tìm đường đi tối ưu nhất. Điển hình cho hai
hướng nghiên cứu đó là hai giao thức định tuyến: RIP (tìm đường đi ngắn nhất) và OSPF (tìm
đường đi tối ưu nhất), ngoài ra người ta còn phát triển thêm giao thức EIGRP là giao thức định
tuyến lai giữa hai giao thức trên để lợi dụng ưu điểm của mỗi loại giao thức.
21
Hình 8: Phân loại các giao thức định tuyến
5.1. Giao thức định tuyến RIP (Routing Information Protocol):
Giao thức định tuyến RIP là giao thức định tuyến “distance vector” – định tuyến theo
khoảng cách từ nút cho tới mạng đích. Hiện nay giao thức này đã được nghiên cứu và phát triển
đến version 3, trong đó vesion 2 được sử dụng nhiều nhất. Chúng đều sử dụng “hop count” là
giá của đường đi tới mạng đích, trong đó mỗi “hop count” là một nút mạng có chức năng hoạt
động ở lớp 3 trong mô hình OSI. Và giá của đường đi có giá trị từ 0 đến 15. Cứ mỗi 30 giây thì
các nút mạng gửi thông tin bảng định tuyến cho nhau để cập nhật dữ liệu về đường đi tới các
mạng đích và duy trì kết nối. Giao thức này sử dụng thuật toán Bellman-Ford so sánh giá của các
liên kết để xây dựng nên bảng định tuyến và định tuyến gói tin.
Ví dụ trên nút mạng R1 ta sử dụng chương trình theo dõi bản tin cập nhật dữ liệu bảng

mạng chủ (BDR), nút mạng này chịu trách nhiệm cập nhật thông tin định tuyến cho các nút khác
dựa vào thông tin định tuyến từ các nút thay đổi tới nó. Do đó hạn chế được tình trạng tốn băng
thông do các nút mạng trao đổi thông tin định tuyến với nhau hoặc gây nghẽn mạng tại thiết bị
trung tâm.
Hình 10: Ưu điểm của BDR
Ưu điểm của giao thức này là mạng hội tụ nhanh do chỉ cập nhật khi mạng có sự thay đổi
và chỉ cập nhật những liên kết bị thay đổi. Đồng thời, do giá được tính toán theo băng thông của
các liên kết nên tăng được tốc độ lưu thông thông tin trên toàn mạng.
24
5.3. EIGRP (Enhanced Interior Gateway Routing Protocol):
Đây là giao thức định tuyến do Cisco IOS Software Release xây dựng từ năm 1992 và
chỉ hoạt động trên các thiết bị mạng do Cisco sản xuất. Giao thức này sử dụng thuật toán
Bellman-Ford hoặc Ford-Fulkerson, là hai thuật toán định tuyến theo khoảng cách. Nhưng quá
trình hoạt động cập nhật bảng định tuyến thì EIGRP lại hoạt động giống như OSPF, tức cập nhật
định tuyến theo trạng thái liên kết. Nhờ vậy, giống OSPF, giao thức EIGRP tăng dung lượng của
mạng hơn hẳn so với giao thức định tuyến RIP. Đồng thời, giá của mỗi liên kết được tính toán
dựa vào bốn thông số: băng thông, trễ, độ tin cậy và tải. Dựa vào bốn thông số này, mỗi thông
tin định tuyến trong đường đi được tính toán tối ưu, đảm bảo cho các gói tin trong mạng luôn
được truyền đi với độ tin cậy cao nhất. Ngoài ra, giao thức OSPF còn giúp người quản trị mạng
thực hiện quản trị mạng tối ưu hơn bằng cách phân vùng tự trị cho các vùng lân cận nhau. Mỗi
vùng tự trị là một AS:
Hình 11: Ưu điểm của phân vùng tự trị (AS)
Mỗi AS chạy một định tuyến EIGRP chung và chỉ định tuyến trong AS đó, muốn định
tuyến dữ liệu sang mạng khác thì các nút mạng phải định tuyến tĩnh tới nút mạng biên
(Gateway). Ở đây, ta lại thấy định tuyến tĩnh cũng có chức năng đặc biệt trong mạng.
Hai giao thức OSPF và EIGRP có hỗ trợ xác thực bản tin update nên có tính bảo mật rất
cao, cùng với update thông tin định tuyến mỗi khi có sự thay đổi của trạng thái liên kết nên có
ưu thế vượt trội so với giao thức định tuyến RIP. Nhưng bù lại mỗi nút mạng cần yêu cầu tốc độ
25