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Ộ
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.ạ ụ ộ ẽ
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ộ ứ ượ ự ệ ở ầ ạ ứ
đá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 v Topology c a m ng. Các thông tin này có th do ng i qu n tr thi t l p. Quáề ủ ạ ể ườ ả ị ế ậ
trình đ nh tuy n c n th a mãn các yêu c u cho tr c bao g m: đ ng đi ng n nh t ho cị ế ầ ỏ ầ ướ ồ ườ ắ ấ ặ
có băng thông r ng nh t. Đ ng đi th ng ph i t i u theo m t trong hai tiêu chí.các góiộ ấ ườ ườ ả ố ư ộ
tin có th đ c g i đi theo đ ng này. Nh ng cũng có th chúng đ c g i đi đ ng th iể ượ ử ườ ư ể ượ ử ồ ờ
trên nhi u đ ng . Vi c đ nh tuy n đ c s d ng cho nhi u lo i m ng: m ng vi n thông,ề ườ ệ ị ế ượ ử ụ ề ạ ạ ạ ễ
liên m ng, internet, m ng giao thông.ạ ạ
Hình : Tìm đ ng đi ti p theoườ ế
Đ nh tuy n có th đ c chia ra làm 3 ph ng pháp đ nh tuy n: đ nh tuy n tĩnh, đ nhị ế ể ượ ươ ị ế ị ế ị
tuy n ng u nhiên và đ nh tuy n đ ng. Trong môi tr ng m ng th ng xuyên có s thayế ẫ ị ế ộ ườ ạ ườ ự
đ i ng u nhiên nên đ nh tuy n tĩnh ch có ý nghĩa các gateway và các m ng nh . ổ ẫ ị ế ỉ ở ạ ỏ
Trong đ nh tuy n đ ng, có hai ph ng th c đ nh tuy n: tìm đ ng theo đ ng đi ng nị ế ộ ươ ứ ị ế ườ ườ ắ
nh t và tìm đ ng đi t i u.ấ ườ ố ư
V n đ tìm đ ng đi ng n nh t đ c đ t ra: ta có th tìm đ ng đi ng n nh t t m t nútấ ề ườ ắ ấ ượ ặ ể ườ ắ ấ ừ ộ
đ n t t c các nút khác ho c tìm đ ng đi ng n nh t t m t nút đ n m t nút c th .ế ấ ả ặ ườ ắ ấ ừ ộ ế ộ ụ ể
Cách gi i quy t này đ c s d ng trong giao th c OSPF(Open Shortest Path First) v iả ế ượ ử ụ ứ ớ
vi c s d ng các thu t toán Dijikstra, Bellman-Ford.ệ ử ụ ậ
Ngoài ra ta có th đ các nút m ng t đ ng tìm ra đ ng đi t i u. Vi c tim ra tuy n điể ể ạ ự ộ ườ ố ư ệ ế
đ c th c hi n m t cách phân tán t i các nút ch 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 m ng v i nhau. 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 đ a ra quy t đ nh đ nh tuy n. B ng đ nh tuy n th ng xuyên đ c c p nh t m iế ư ế ị ị ế ả ị ế ườ ượ ậ ậ ỗ
khi có thay đ i c u hình m ng. Thu t toán đ c s d ng là Prime và Kruskal nh m t o raổ ấ ạ ậ ượ ử ụ ằ ạ
cây b c c u t i thi u.ắ ầ ố ể
2. Các khái ni m trong lý thuy t graph:ệ ế
Ph n này gi i thi u các thu t ng và các khái ni m c b n nh m mô t các m ng,ầ ớ ệ ậ ữ ệ ơ ả ằ ả ạ
graph, và các thu c tính c a nó. Lý thuy t graph là m t môn h c xu t hi n t lâu, nh ng lýộ ủ ế ộ ọ ấ ệ ừ ư
thuy t này có m t s thu t ng đ c ch p nh n khác nhau dùng cho các khái ni m c b n. Vìế ộ ố ậ ữ ượ ấ ậ ệ ơ ả
th có th s d ng m t s thu t ng khác nhau đ l p mô hình graph cho m ng. Các thu tế ể ử ụ ộ ố ậ ữ ể ậ ạ ậ
ng đ c trình bày 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)
Hình 2 là m t ví d c a m t graph.ộ ụ ủ ộ
Hình : 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={vi | i=1,2,......N}
Trong đó N là s l ng nút. T ng t ố ượ ươ ự E đ c bi u di n:ượ ể ễ
E={ei | 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ở
ej=(vi,vk)
ho c b iặ ở
ej=(i,k)
M t liên k t g i làộ ế ọ đi t i m t nútớ ộ n u nút đó là m t trong hai đi m cu i c a liên k t.ế ộ ể ố ủ ế
Nút i và k g i là ọk nhauề n u t n t i m t liên k t (ế ồ ạ ộ ế i, k) gi a chúng. Nh ng nút nh v y đ cữ ữ ư ậ ượ
xem là các nút láng gi ngề. B c c a nút là s l ng liên k t đi t i nút hay là s l ng nút lángậ ủ ố ượ ế ớ ố ượ
gi ng. Hai khái ni m trên là t ng đ ng nhau trong các graph thông th ng. Tuy nhiên v i cácề ệ ươ ươ ườ ớ
graph có nhi u h n m t liên k t gi a cùng m t c p nút, thì hai khái ni m trên là không t ngề ơ ộ ế ữ ộ ặ ệ ươ
đ ng. Trong tr ng h p đó, b c c a m t nút đ c đ nh nghĩa là s l ng liên k t đi t i nútươ ườ ợ ậ ủ ộ ượ ị ố ượ ế ớ
đó.
M t liên k t có th có hai h ng. Khi đó th t c a các nút là không có ý nghiă. Ng cộ ế ể ướ ứ ự ủ ượ
l i th t các nút có ý nghĩa. Trong tr ng h p th t các nút có ý nghĩa, m t liên k t có thạ ứ ự ườ ợ ứ ự ộ ế ể
đ c xem nh là m t ượ ư ộ cung và đ c đ nh nghĩa ượ ị