Tiểu Luận: Các Thuật Toán Và Phương Thức Định Tuyến Trong Mạng

ƯỜ

Ạ Ọ

NG Đ I H C BÁCH KHOA HÀ N I Ộ VI N ĐI N T VI N THÔNG

Ệ Ử Ễ

Ệ

**********

Ễ

Ọ Các Thu t Toán Và Ph

ng Th c Đ nh Tuy n Trong

Ổ Ứ ậ

Ạ ị

ứ

ế

ề

Gi ng viên h

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: “ ươ ” M ng ạ ẫ

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

ở ầ

ngu n t

i đích.

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

Đ 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 ể

ờ ủ

ữ ệ

ứ

ế

ề

ạ

ộ

ị

ừ

ồ ớ 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, ấ

ạ

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 ế

ụ

ớ

ị

ủ

ng pháp đ nh tuy n thích h p đ áp d ng vào th c t

y u là tìm ra nh ng ph ế

ữ

ươ

ự ế ạ m ng

ụ

ế

ể

ợ

ị

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 đ

i đa

ủ ề

ứ

ọ

ườ

ợ

ạ

c t ượ ố

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 ộ

Gi

ớ

i thi u v đ nh tuy n: ề ị

ế

ệ

Đ nh tuy n là quá trình tìm đ

i thông tin trong liên m ng t

ế

ị

ườ

ng đi đ truy n t ể

ề ả

ạ

ừ

ế ngu n đ n ồ

c th c hi n

t ng m ng. Ch c năng này cho phép router

đích. Nó là m t ch c năng đ ộ

ứ

ượ

ệ ở ầ

ự

ứ

ạ

đánh giá các đ

i đích. Đ đánh giá đ

ườ

ng đi s n có t ẵ

ớ

ể

ườ

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 đ

c s d ng cho nhi u lo i m ng: m ng vi n thông,

ề

ườ

ng . Vi c đ nh tuy n đ ị

ệ

ế

ượ

ử ụ

ề

ễ

ạ

liên m ng, internet, m ng giao thông.

ạ

Hình : Tìm đ

ườ

ng đi ti p theo ế

c chia ra làm 3 ph

ng pháp đ nh tuy n: đ nh tuy n tĩnh, đ nh

Đ nh tuy n có th đ ế

ể ượ

ị

ươ

ế

ị

tuy n ng u nhiên và đ nh tuy n đ ng. Trong môi tr

ng xuyên có s thay

ế

ẫ

ộ

ị

ườ

ng m ng th ạ

ườ

ự

đ 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.

ấ

ườ

ố ư

c đ t ra: ta có th tìm đ

m t nút

V n đ tìm đ ề

ấ

ườ

ng đi ng n nh t đ ắ

ấ ượ

ể

ặ

ườ

ng đi ng n nh t 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.

ử ụ

ệ

ậ

đ ng tìm ra đ

ng đi t

i u. Vi c tim ra tuy n đi

Ngoài ra ta có th đ các nút m ng t ể ể

ạ

ự ộ

ườ

ố ư

ệ

ế

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 đ

tìm ra đ

ng đi t

i u đ n các nút khác r i l p ra b ng đ nh

ậ

ượ

c m i nút t ỗ

ự

ườ

ố ư

ồ ậ

ế

ả

ị

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. ể

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. ườ ươ

c đ nh nghiã b i t p h p các đ nh M t ộ graph G, đ ượ ị ở ậ ợ ỉ 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

t b truy n thông). Các c nh đ c g i là các m t khu v c ch a thi ự ứ ộ ế ị ề ạ ượ ọ ễ 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. ụ ủ ộ ộ

ộ

M c dù theo lý thuy t, ặ

Hình : M t graph đ n gi n ả ơ ế 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 c bi u di n: ố ượ ươ ự E đ ượ ễ ể

E={ei | i=1,2,......M}

M t liên k 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 ế ej, t ộ ươ ứ ộ ế ố ữ ể ể ộ ặ ễ ộ

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 m t nút ế ọ đi t ộ ớ ộ ế n u nút đó là m t trong hai đi m cu i c a liên k t. ố ủ ế ể ộ

n u t n t i m t liên k t ( Nút i và k g i là ọ k nhau ề ế ồ ạ ộ ế i, k) gi a chúng. Nh ng nút nh v y đ ư ậ ượ c ữ ữ

ng liên k t đi t i nút hay là s l ng nút láng xem là các nút láng gi ngề . B c c a nút là s l ậ ủ ố ượ ế ớ ố ượ

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 c đ nh nghĩa là s l ng liên k t đi t i nút đ ươ ườ ng h p đó, b c c a m t 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

các nút có ý nghĩa. Trong tr các nút có ý nghĩa, m t liên k t có th l i th t ạ ứ ự ườ ng h p th t ợ ứ ự ế ộ ể

c đ nh nghĩa đ ượ c xem nh là m t ư ộ cung và đ ượ ị

aj=[vi,vk]

ho c đ n gi n h n ả ơ ặ ơ

aj=[i,k]

k đ c g i là ng ra đ i v i i,k] t n t i và ng ra ượ ọ c n k h ậ ề ướ ố ớ i n u m t cung [ ế ộ ồ ạ b c h ậ ướ

ng vào và b c c n k h c a ủ i là s l ố ượ ng các cung nh v y. Khái ni m ư ậ ệ c n k h ậ ề ướ ậ ậ ề ướ ng

vào cũng đ c đ nh nghĩa t ng t ượ ị ươ . ự

M t graph g i là m t ộ m ngạ n u các liên k t và các nút có m t trong liên k t có các ế ế ế ặ ọ ộ

ng, lo i...). Các m ng đ c s d ng đ mô hình thu c tính (ch ng h n nh đ dài, dung l ạ ư ộ ẳ ộ ượ ạ ạ ượ ử ụ ể

các v n đ c n quan tâm trong truy n thông, các thu c tính riêng bi t c a nút và liên k t thì liên ấ ề ầ ề ộ ệ ủ ế

quan đ n các v n đ c th trong truy n thông. ấ ề ụ ể ế ề

S khác nhau gi a các liên k t và các cung là r t quan tr ng c v vi c l p mô hình cho ả ề ệ ậ ự ữ ế ấ ọ

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 ng có th có c các liên k t vô h ng. Thông th ng , ữ ướ . M t graph h u h ộ ữ ướ ể ế ả ướ ườ

các graph đ c gi s là vô h t đó là không có ý nghĩa. ượ ả ử ướ ng, ho c s phân bi ặ ự ệ

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 ế ữ ấ ệ ả ộ

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 liên k t đó đ ế ượ ọ ấ ệ ườ ấ ệ ệ

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 ế ế ặ ộ

ng đ i d 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 ậ ụ ơ ệ ể ễ ả ơ ươ ố ễ

dàng, vì v y gi t r ng các graph đ thi ậ ả ế ằ ượ c xem xét là các graph đ n gi n. N u có s khác bi ơ ự ế ả ệ t

thi t này, chúng s đ v i gi ớ ả ế ẽ ượ c ch ra. ỉ

: Phân lo i đ nh tuy n ạ ị ế

Hình : 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 ỏ

ố ớ ệ ố

ố ị

ệ

ạ

ổ

i qu n tr m ng ph i c u hình m i thông tin v

công h n. Chính vì đ nh tuy n đòi h i ng ị

ế

ỏ

ườ

ả ấ

ị ạ

ả

ọ

ề

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 cho m t s m c đích đ c bi

ộ ố ụ

ế

ặ

ộ

ị

ệ

Ho t đ ng c a đ nh tuy n tĩnh có th chia làm 3 b ế

ạ ộ

ủ

ể

ị

ướ

c nh sau: ư

Đ u tiên, ng

i qu n tr m ng c u hình các đ

ng c đ nh cho các router

ầ

ườ

ị ạ

ấ

ả

ườ

ố ị

Router cài đ t các đ

ặ

ườ

ng đi này vào b ng đ nh tuy n ả

ế

ị

Gói d li u đ

c đ nh tuy n theo các đ

ữ ệ

ượ

ế

ị

ườ

ng đi c đ nh này ố ị

Sau đây là demo c u hình c a m ng đ nh tuy n tĩnh

ủ

ế

ạ

ấ

ị

Hình : Demo c u hình m ng đ nh tuy n

ế

ấ

ạ

ị

3.2. Đ nh tuy n ng u nhiên (random routing):

ế

ẫ

ị

3.2.1. Đ nh tuy n ng u nhiên lan tràn gói (flooding):

ế

ẫ

ị

t đó là lan tràn gói. Trong ph M t d ng m nh h n c a đ nh tuy n riêng bi ơ ủ ị ộ ạ ế ạ ệ ươ ứ ng th c

này, m i gói đi đ n router s đ c g i đi trên t t c các đ ng ra tr đ ẽ ượ ử ế ỗ ấ ả ườ ừ ườ ế ng mà nó đi đ n.

Ph ng th c lan tràn gói này hi n nhiên là t o ra r t nhi u gói sao chép (duplicate). Trên ươ ứ ề ể ạ ấ

th c t ự ế ố , s gói này là không xác đ nh tr khi th c hi n m t s bi n pháp đ h n ch quá ự ộ ố ệ ể ạ ừ ế ệ ị

c nh y trong ph n tiêu đ trình này. M t trong nh ng bi n pháp đó là s d ng b đ m b ệ ử ụ ộ ế ữ ộ ướ ầ ả ề

i m i b c nh y. Gói s b lo i b khi b c a m i gói. Giá tr này s b gi m đi m t t ủ ẽ ị ả ộ ạ ỗ ị ỗ ướ ẽ ị ạ ỏ ả ộ

c nh y s có giá tr ban đ u t đ m đ t giá tr không. V m t lý t ế ề ặ ạ ị ưở ng, b đ m b ộ ế ướ ả ẽ ầ ươ ng ị

ngu n đ n đích. N u nh ng i g i không bi t đ dài c a đ ng đi, nó ứ ng v i đ dài t ớ ộ ừ ư ườ ử ế ế ồ ế ộ ủ ườ

có th đ t giá tr ban đ u c a b đ m cho tr ng h p x u nh t. Khi đó giá tr ban đ u đó ầ ủ ộ ế ể ặ ị ườ ợ ấ ầ ấ ị

c đ t b ng đ ng kính c a m ng con. M t k thu t khác đ ngăn s lan tràn gói là s đ ẽ ượ ặ ằ ườ ộ ỹ ự ủ ể ậ ạ

thêm s th t vào tiêu đ các gói. M i router s c n có m t danh sach theo nút ngu n đ ố ứ ự ẽ ầ ề ỗ ộ ồ ể

t ngu n đó đã đ c xem xét. Đ tránh danh sách phát tri n không ch ra nh ng s th t ữ ố ứ ự ừ ỉ ồ ượ ể ể

gi t c các s th t đ n ớ ạ i h n, m i danh sách s tăng lên b i s đ m ẽ ở ố ế k đ ch ra r ng t ể ỉ ằ ỗ ấ ả ố ứ ự ế k

đã đ c xem. Khi m t gói đi t i, r t d dàng có th ki m tra đ ượ ộ ớ ấ ễ ể ể ượ c gói là b n sao hay ả

không. N u đúng gói là b n sao thì gói này s b lo i b . T c là khi nh n đ ẽ ị ạ ỏ ứ ế ả ậ ượ c m i gói ỗ

tin,nút m ng s g i đi t .Lan tràn gói có ẽ ủ ạ ấ ả t c các nút k c n,tr nút đã g i gói cho nó ừ ề ậ ử

u đi m là lan tràn gói luôn luôn ch n đ c u đi m này là do v ư ể ọ ườ ng ng n nh ắ ất. Có đ ượ ư ể ề

ph ng di n lý thuy t nó ch n t t c các đ ng có th do đó nó s ch n đ ươ ệ ế ọ ấ ả ườ ẽ ọ ượ c ể

đ ng gói g i trong m ng quá ườ ng ng n nh t ắ ấ . Tuy nhiên nh ượ c đi m c a nó là s l ủ ố ượ ể ử ạ

nhi uề . S d ng lan tràn gói trong h u h t các 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 : Đ nh tuy n lan tràn gói

ế

ị

t ph i c p nh t t Trong nh ng ng d ng c s d li u phân b , đôi khi c n thi ơ ở ữ ệ ữ ứ ụ ầ ố ế ả ậ ậ ấ t

ng h p đó s d ng lan tràn gói là c n thi c c s d li u. Trong tr ả ơ ở ữ ệ ườ ử ụ ầ ợ ế 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 ể ử ậ ế ở ậ ả ự ậ ậ ộ ị

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

ng mà đi

ọ ọ

ả

i thu t này, router ch g i gói đi ra trên các đ ỉ ử

ậ

ườ

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

ướ

3.2.2. Đ nh tuy n ng u nhiên (random walk): ẫ

ế

ị

b ng đ nh tuy n. 40 ả ế ị

Trong ph ươ ng pháp đ nh tuy n này, router s chuy n gói đi đ n trên m t đ ẽ ộ ườ ng ế ể ế ị

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 đ u ra đ ầ ượ ụ ủ ẫ ọ ộ ươ

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 ế ạ ố ớ ươ

i gi a các đ b ng t ằ ả ữ ườ 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 : Đ nh tuy n ramdom walk ế

ị

3.2.3. Đ nh tuy n ng u nhiên (hot potato): ẫ ế ị

t là lo i đ nh tuy n mà router Đ nh tuy n riêng bi ế ị ệ ạ ị ế quy t đ nh đ nh tuy n đi ch ị ế ế ị ỉ

c. d a vào thông tin b n thân nó l m l t đ ả ượ ặ ượ ự

Đây là m t thu t toán t ng thích riêng bi ậ ộ ươ ệ ộ t (isolated adaptive algorithm). Khi m t

gói đ n m t nút, router s c g ng chuy n gói đó đi càng nhanh càng t t b ng cách cho nó ẽ ố ắ ế ể ộ ố ằ

vào hàng ch đ u ra ng n nh t. Nói cách khác, khi có gói đi đ n router s tính toán s gói ờ ầ ế ẽ ắ ấ ố

đ c n m ch đ truy n tren m i đ ng đ u ra. Sau đó nó s gán gói m i vào cu i hàng ượ ằ ờ ể ỗ ườ ề ẽ ầ ố ớ

ch ng n nh t mà không quan tâm đ n đ ng đó s đi đâu. Hình 7 bi u di n các hàng ch ế ườ ắ ấ ờ ẽ ễ ễ ờ

i m t th i đi m nào đó. Có ba hàng ch đ u ra t đ u ra bên trong m t router t ầ ộ ạ ờ ầ ể ộ ờ ươ ứ ng ng

ng ra. Các gói đang x p hàng trên m i đ ng đ ch đ . v i 03 đ ớ ườ ỗ ườ ế ể ờ ượ c truy n đi ề

Trong ví d đây, hàng ch đ n ụ ở ờ ế F là hàng ch ng n nh t ờ ắ ấ v i ch có m t gói n m trên ộ ằ ớ ỉ

i thu t khoai tây nóng do đó s đ t gói m i đ n vào hàng ch này. hàng ch này. Gi ờ ả ớ ế ẽ ặ ậ ờ

Hình : Đ nh tuy n ng u nhiên

ẫ

ị

Có th bi n đ i ý t ng này m t chút b ng cách k t h p đ nh tuy n tĩnh v i gi ể ế ổ ưở ế ợ ế ớ ộ ị ả i

ế ằ

thu t khoai tây nóng. Khi gói đi đ n, router s tính đ n c nh ng tr ng s tĩnh c a đ ế ả ữ ủ ườ ng ẽ ế ậ ố ọ

t nh t tr khi đ dài dây và đ dài hàng ch . M t kh năng là s d ng l a ch n tĩnh t ả ử ụ ự ộ ờ ộ ọ ố ấ ừ ộ

ng nào đó. M t kh năng khác là s d ng đ dài hàng ch hàng ch l n h n m t ng ờ ớ ơ ộ ưỡ ử ụ ả ộ ộ ờ

ng n nh t tr tr ng s tĩnh c a nó là quá th p. Còn m t cách khác là ấ ừ ọ ủ ấ ắ ố ộ s p x p các đ ắ ế ườ ng

theo tr ng s tĩnh c a nó và sau đó l i s p x p theo đ dài hàng ch c a nó. Sau đó ủ ố ọ ạ ắ ế ờ ủ ộ

ng có t ng v trí s p x p là nh nh t. s ch n đ ẽ ọ ườ ỏ ấ Dù gi ắ ế ổ ị ả i thu t nào đ ậ ượ c ch n đi ọ

chăng n a cũng có đ c tính là khi ít t i thì đ ữ ặ ả ườ ng có tr ng s cao nh t s đ ố ấ ẽ ượ ọ ọ c ch n,

nh ng s làm cho hàng ch cho đ ng này tăng lên. Sau đó m t s l u l ng s đ ư ẽ ờ ườ ộ ố ư ượ ẽ ượ c

3.3. Đ nh tuy n đ ng (dynamic routing):

chuy n sang đ ng ít t i h n. ể ườ ả ơ

ế ộ ị

Là quá trình mà trong đó giao th c đ nh tuy n tìm ra đ ng t t nh t trong m ng và ứ ị ế ườ ố ạ ấ

ư duy trì chúng. Có r t nhi u cách đ xây d ng lên b ng đ nh tuy n m t cách đ ng. Nh ng ự ế ề ể ả ấ ộ ộ ị

t c đ u th c hi n theo quy t c sau: nó s khám t t c các tuy n đ ng đ n đích có th t ấ ả ề ự ệ ẽ ắ ấ ả ế ườ ế ể

và th c hi n m t s quy t c đ c đ nh tr c đ xác đ nh ra đ ng t ộ ố ắ ượ ị ự ệ ướ ể ị ườ ố Ư t nh t đ n đích. u ấ ế

đi m c a dynamic routing là đ n gi n trong vi c c u hình và t ơ ệ ấ ủ ể ả ự ộ ế đ ng tìm ra nh ng tuy n ữ

đ ng thay th n u nh m ng thay đ i. Nh c đi m c a dynamic routing là yêu c u x ườ ư ạ ế ế ổ ượ ầ ử ủ ể

lý c a CPU c a router cao h n là static route. Tiêu t n m t ph n băng thông trên m ng đ ủ ủ ầ ạ ơ ố ộ ể

xây d ng lên b ng đ nh tuy n. ả ự ế ị

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 ắ ầ ế ể ộ ộ

i. Cây tìm đ c th ng là cây vô h ng. Vi c tìm cây "t c u t n 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à ỗ ạ ể ắ ậ ọ ộ ộ

i thi u. Th c t đ t ra yêu c u tìm m t cây có đ dài 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 ể ượ ệ ự ứ ấ ả ư ủ ọ ộ ố

c l a ch n. Đ u tiên, t o m t graph có n nút, n thành nút c a graph g c và các c 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 ộ ạ ỗ ầ ể ầ ạ ả ọ

c đó ch a đ c k t n i đ c liên k t l i v i nhau t o ra hai thành ph n liên thông tr ầ ướ ư ượ ế ố ượ ế ạ ớ ạ

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 i b t kỳ giai đo n nào c a thu t toán, quan ướ c đó và t o ra m t vòng). Vì v y, t ộ ậ ạ ấ ủ ạ ậ ạ

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. n tr đi s thành ph n trong graph g c; n u graph g c là liên Ở ố cu i thu t toán, ậ e b ng ằ ừ ế ầ ố ố ố

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 ẽ

ng không tìm đ c cây b c c u có t ng đ dài t b c c u. Tuy nhiên, chúng ta th ắ ầ ườ ượ ắ ầ ổ ộ ố i thi u. ể

Đ tìm ra cây b c c u t i ta s d ng 2 thu t toán: prime và kruskal. ắ ầ ố ể i thi u ng ể ườ ử ụ ậ

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

i quy t nh gi 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 bài ế

toán tìm đ c g n vào m i c nh (ho c cung) ườ ng đi ng n nh t khi m t "đ dài " thích h p đ ộ ợ ượ ắ ỗ ạ ặ ắ ấ ộ

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. ẩ ộ ườ

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 ấ ữ ắ

tr c. Lo i bài toán này có th là bài toán tìm đ m t nút t t c các nút i t ướ ể ạ ườ ng đi ng n nh t t ắ ấ ừ ộ ớ ấ ả

còn l ng đ ng bài toán tìm đ i, t ạ ươ ươ ườ ng đi ng n nh t t ắ t ấ ừ ấ ả t c các đi m đ n m t đi m. Đôi ế ộ ể ể

khi đòi h i ph i tìm đ ng đi ng n nh t gi a t ng đi đôi khi có ả ỏ ườ ấ ữ ấ ả t c các c p nút. Các đ ặ ắ ườ

i h n nh t đ nh (ch ng h n nh gi ng đi). nh ng gi ữ ớ ạ ấ ị i h n s l ư ớ ạ ố ượ ẳ ạ ng các c nh trong đ ạ ườ

Ti p theo, chúng ta xét các graph h u h ng và gi s r ng đã bi ữ ướ ế ả ử ằ ế ộ t đ dài c a m t cung ủ ộ

gi a m i c p nút ỗ ặ ữ ồ i và j là lij. Các đ dài này không c n ph i đ i x ng. Khi m t cung không t n ả ố ứ ầ ộ ộ

lij đ c gi t ạ i thì đ dài ộ ượ ả ử s là r t l n (ch ng h n l n g p ẳ ạ ớ ấ n l n đ dài cung l n nh t trong ầ ộ ấ ớ ấ ớ

m ng). Chú ý r ng có th áp d ng quá trình này cho các m ng vô h ụ ể ạ ạ ằ ướ ỗ ng b ng cách thay m i ằ

s r ng ng hoàn toàn; sau đó gi c nh b ng hai cung có cùng đ dài. Ban đ u gi ạ ầ ằ ộ ả ử ằ lij là d ươ ả

thi t này có th đ ế ể ượ c thay đ i. ổ

Lo i đ nh tuy n này đ c dùng thông d ng v i các thu t toán đ c dùng: dijkstra, ạ ị ế ượ ụ ậ ớ ượ

bellman ford.

Các thu t toán dùng đ đ nh tuy n: ể ị ế ậ

4.1. Thu t toán Prim: ậ

Thu t toán này có nh ng u đi m riêng bi ữ ư ể ậ ệ t là khi m ng dày đ c,trong vi c xem xét ặ ệ ạ

m t bài toán tìm ki m ế các cây b c c u t i thi u ắ ầ ố ể . H n n a các thu t toán ph c t p h n đ ậ ứ ạ ơ ượ c ơ ữ ộ

xây d ng d a vào các thu t toán cây b c c u t ắ ầ ố ự ự ậ i thi u,và m t s thu t toán này ho t đ ng t ậ ạ ộ ộ ố ể ố t

c s d ng cho thu t toán sau đây,thu t toán này đ c phát h n v i các c u trúc d li u đ ấ ơ ớ ữ ệ ượ ử ụ ậ ậ ượ

bi u b i Prim. Các thu t toán này phù h p v i các quad trình th c hi n song song b i vì các quá ợ ớ ể ở ự ệ ậ ở

trình đó đ c th c hi n b ng các toán t vector. Thu t toán đ c miêu t nh sau: ượ ệ ằ ự ử ậ ượ ả ư

B1: Ch n m t đ nh s b t kỳ c a G cho vào cây T. Khi đó cây T là m t cây ch có ộ ỉ ủ ấ ọ ộ ỉ

m t đ nh và ch a có c nh nào. ư ộ ỉ ạ

B2: N u T đã g m t t c các đ nh c a G thì T là cây bao trùm c n tìm. K t thúc. ồ ấ ả ủ ế ế ầ ỉ

ố B3: N u G còn có các đ nh không thu c T ,vì G liên thông nên có các c nh n i ộ ế ạ ỉ

m t đ nh trong T v i m t đ nh ngoài T, ch n m t c nh có tr ng s nh nh t trong s đó cho ố ỏ ấ ớ ộ ỉ ộ ạ ộ ỉ ố ọ ọ

vào T.

Ví d :ụ

B4: Quay l i B2. ạ

U

C nh (u,v)

V \ U

Hình minh h aọ

ạ

Mô tả

ọ Đây là đ th có tr ng ồ ị

{A,B,C,D

ố s ban đ u. Các s là ố

ầ

{}

,E,F,G}

các tr ng s c a các

ố ủ

ọ

c nh.ạ

Ch n m t cách tùy ý

ộ

ọ

đ nhỉ

ắ ầ D là đ nh b t đ u.

ỉ

Các

đ nhỉ

A, B, Evà F đ uề

(D,A) = 5 V

ượ

ế c n i tr c ti p

ố ự

(D,B) = 9

{A,B,C,E

{D}

iớ D b ng c nh c a đ ạ

ủ

ằ

ồ

(D,E) = 15

,F,G}

th .ị A là đ nhỉ

(D,F) = 6

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

{B,C,E,F,

Đ nh đ

ỉ

ượ

ế c ch n ti p ọ

(D,E) = 15

theo là đ nhỉ

(D,F) = 6 V

g nầ D ho cặ Anh t.ấ B c

(A,B) = 7

ó kho ng cách

ả

iớ D b ng 9 và ằ

E có

iớ A b ng 7, ằ

kho ng cách t

i cây

ả

ớ

hi n t

i b ng 15,

ệ ạ ằ

và F có kho ng cách

ả

b ng 6.

ằ

ầ F là đ nh g n ỉ

cây hi n t

ệ ạ

i nh t nên ấ

ch n đ nh

F và

ọ

ỉ

c nhạ DF.

(D,B) = 9

ế ụ Thu t toán ti p t c

ậ

(D,E) = 15

ng t

nh b

ươ

ự

ư ướ c

{B,C,E,G

{A,D,F}

(A,B) = 7 V

ướ

c. Ch n đ nh ọ

ỉ B có

}

(F,E) = 8

kho ng cách

ả

(F,G) = 11

iớ A b ng 7. ằ

b Ở ướ

ọ c này ta ch n

(B,C) = 8

gi aữ C, E, và G. C có

kho ng cách t

(B,E) = 7 V

ả

ớ B b ngằ

8, E có kho ng cách

(D,B) = 9

ả

{A,B,D,

chu trình

{C,E,G}

Gcó

iớ B b ng 7, và

ằ

kho ng cách

(D,E) = 15

ả

(F,E) = 8

iớ F b ng 11. ằ

Elà đ nhỉ

(F,G) = 11

ọ g n nh t, nên ch n

ầ

ấ

đ nhỉ

Evà c nhạ BE.

(B,C) = 8

(D,B) = 9

chu trình

b Ở ướ

ọ c này ta ch n

(D,E) = 15

gi aữ C vàG. C có

{A,B,D,

chu trình

kho ng cách

ả

{C,G}

E,F}

(E,C) = 5 V

G có

iớ E b ng 5, và ằ

kho ng cách t

(E,G) = 9

ả

ớ E b ngằ

(F,E) = 8

9. Ch nọ C và c nhạ EC.

chu trình

(F,G) = 11

(B,C) = 8

chu trình

Đ nhỉ

G là đ nh còn l ỉ

ạ i

(D,B) = 9

duy nh t. Nó có ấ

kho ng cách

chu trình

ả

{A,B,C,

(D,E) = 15

iớ F b ng 11, và

ằ

{G}

D,E,F}

chu trình

kho ng cách

ả

(E,G) = 9 V

iớ E b ng 9. ằ

ở ầ g n

(F,E) = 8

ọ h n nên ch n

chu trình

đ nhỉ

Gvà c nhạ EG.

(F,G) = 11

(B,C) = 8

chu trình

t c các

(D,B) = 9

Hi n gi ệ

ờ ấ ả

đ nh đã n m trong cây

chu trình

ằ

ỉ

{A,B,C,

(D,E) = 15

và cây bao trùm nhỏ

D,E,F,G

{}

c tô màu xanh

chu trình

nh tấ đ

ượ

}

(F,E) = 8

lá cây. T ng tr ng s ổ

ọ

ố

chu trình

c a cây là 39. ủ

(F,G) = 11

chu trình

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. ạ ỏ ữ ạ ấ ổ ạ ạ

B4: quay l i B2. ạ

VÍ D :Ụ

nh minh h a

Ả

ọ

Mô tả

AD và CE là các c nh nh nh t v i đ dài 5, và ta ỏ

ấ ớ ộ

ạ

ch nọ AD m t cách tùy ý (tô màu xanh).

ộ

CE là c nh nh nh t không t o thành chu trình v i đ dài 5, ạ

ớ ộ

ấ

ạ

ỏ

c ch n.

nên nó là c nh th hai đ ạ

ứ

ượ

ọ

C nh th ba

DF v i đ dài 6 cũng đ

c ch n t

ng t

ứ

ạ

ớ ộ

ượ

ọ ươ

ự

v y.ậ

Các c nh ti p theo theo th t

ứ ự ọ

ầ tr ng s tăng d n ố

ế

ạ

là AB và BE, v i đ dài 7. Ch n

ớ ộ

ọ AB m t cách tùy ý.

ộ

c ch n trong t

C nhạ BD không th đ

ể ượ

ọ

ươ

ỏ ng lai (tô màu đ )

vì đã có đ

ng n i

ườ

ố B và D nên n u ch n nó s t o thành

ẽ ạ

ế

ọ

chu trình ABD.

Ti p t c ch n c nh nh nh t ti p theo là

ế ụ

ấ ế

ạ

ọ

ỏ

BE v i đ dài 7. ớ ộ

Thêm m t s c nh đ

c tô màu đ :

ộ ố ạ

ượ

ỏ BC vì nó s t o chu

ẽ ạ

trình BCE, DE vì nó s t o chu trình

ẽ ạ

DEBA, và FE vì nó sẽ

FEBAD.

t o chu trình ạ

Cu i cùng, thu t toán ch n c nh ậ

ạ EG đ dài 9, và tìm ra cây

ọ

ộ

ố

bao trùm nh nh t.

ấ

ỏ

4.3. Thu t toán Dijkstra:

ậ

ng đi t nút s Cho Graph liên thông G={V,E}, c n tìm kho ng cách ng n nh t và đ ầ ấ ả ắ ườ ừ

t c các nút khác. đ n t ế ấ ả

o= s}, gán d(v) b ng:ằ

•

B1: thi t l p i=0, t p ch a các nút có giá c đ nh S={u ế ậ ố ị ứ ậ

•

∞ v i v≠u ớ o

0 v i v= u ớ o

N u | V|= 1 thì k t thúc. ế ế

i) cho v.

B2: v i m i v € V/S, thay th :d(v)= min{d(v),d(u ớ ỗ ế ị i)+ d(vui)}. N u d(v) thay đ i giá tr , ế ổ

i+1)

đ t nhãn (d(v), u ặ

i+1 có giá nh nh t. gán S=S(u ỏ ấ

B3: trong s các v v a đ ố ừ ượ ậ c c p nh t giá, tìm U ậ

B4: thay th b i i+1. N u i =|V|-1 k t thúc. N u không quay v B2. ế ở ế ế ề ế

4.4. Thu t toán Bellman Ford:

ậ

ng đi t Cho graph liên thông G={V,E},c n tìm kho ng cách ng n nh t và đ ầ ả ấ ắ ườ ừ ế nút s đ n

t c các nút khác. t ấ ả

•

B1: thi t l p hàm xác đ nh nút ti n b i c u s là π(s)= s và các giá d(v) b ng: ế ậ ề ố ả ằ ị

•

=∞ v i v≠u ớ o

=0 v i v =u ớ o

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={Ø} ặ ạ ế

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 ứ ể

i d ng u đi m c a m i lo i giao th c. đ nh tuy n lai gi a hai giao th c trên đ l ị ể ợ ụ ư ỗ ạ ứ ữ ủ ứ ể ế

Hình : 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 ả ậ

đ nh tuy n, sau m i th i gian nh t đ nh nút m ng g i yêu c u nút m ng khác g i thông tin đ nh ị ỗ ờ ấ ị ử ử ế ạ ầ ạ ị

tuy n v đ xây d ng b ng đ nh tuy n c a riêng mình. Trong b ng đ nh tuy n có ch a thông ế ề ể ế ủ ự ứ ế ả ả ị ị

tin v m ng đích, c ng đi t i m ng đích và giá c a đ ng t i m ng đích đó là bao nhiêu. ề ạ ổ ớ ạ ủ ườ ớ ạ

RIP

ế ở

c đi m c a giao th c đ nh tuy n này là d d n t Nh

Hình : Quá trình g i thông tin đ nh tuy n ị ễ ẫ ớ

ứ ị

ư ế

ủ ể ượ i gói tin trong m ng b l p vòng ạ ị ặ

(loop) do th i gian các nút m ng g i thông tin đ nh tuy n cho nhau là đ nh kì, và trong th i gian ị ử ế ạ ờ ờ ị

khá lâu trong khi môi tr ườ ng m ng luôn có s thay đ i ng u nhiên. Đ ng th i giao th c này ẫ ứ ự ạ ổ ồ ờ

không phân bi t lo i gói tin đ ệ ạ ượ ự c truy n đi trong m ng nên v i nh ng gói tin là th i gian th c ớ ữ ề ạ ờ

ng, t c là giao th c không h tr QoS (Quality of v n b x lí gi ng nh ng gói tin d li u th ữ ẫ ị ử ữ ệ ố ườ ỗ ợ ứ ứ

Service). Ngoài ra, vì giá đ c tính theo s “hop count” nên có th có tr ng h p giá c a liên ượ ể ố ườ ủ ợ

ớ ơ k t thì nh trong khi băng thông cũng nh thì s gây ngh n m ng, mà liên k t có giá l n h n ẽ ế ế ẽ ạ ỏ ỏ

nh ng băng thông l n thì l i không có d li u đ c truy n. Do đó giao th c này ch đ c s ư ớ ạ ữ ệ ượ ỉ ượ ử ứ ề

các m ng nh , và dung l d ng ụ ở ạ ỏ ượ ạ ng m ng không quá l n đ tránh tình tr ng ngh n m ng ớ ể ẽ ạ ạ

5.2. OSPF (Open Shortest Path First):

gây m t d li u do b l p vòng quá nhi u. ấ ữ ệ ị ặ ề

c phát tri n năm 1987 b i IETF (Internet Engineering Task Force). Giao th c OSPF đ ứ ượ ể ở

Đây là giao th c “link-state” – ho t đ ng d a trên thông tin v tr ng thái các liên k t trong ạ ộ ề ạ ứ ự ế

m ng. M i nút m ng nh n và g i các gói tin LSU (Link State Update) t ử ạ ạ ậ ỗ ớ i các nút m ng khác v ạ ề

tr ng thái liên k t c a nó t i các m ng khác nh th nào, t đó xây d ng nên cây SPF (Shortest ế ủ ạ ớ ư ế ạ ừ ự

Path First) b ng thu t toán Dijkstra. đây, giá đ c s d ng b ng cách tính toàn t băng thông ằ ậ Ở ượ ử ụ ằ ừ

i u v cách tính giá liên c a các liên k t, băng thông càng l n thì giá càng nh , cho th y s t ớ ủ ấ ự ố ư ề ế ỏ

c b t kì s thay đ i n o v tr ng thái liên t đ k t so v i giao th c RIP. Khi m i nút m ng bi ế ứ ạ ỗ ớ ế ượ ấ ổ ả ề ạ ự

i nút m ng khác. Do đó, bình k t t ế ớ ạ i m ng khác thì nó m i g i d li u đ nh tuy n c p nh t t ớ ử ữ ệ ị ế ậ ậ ớ ạ

th ng không có s thay đ i nào v m ng thì các nút m ng ch g i nh ng gói có kích th ườ ề ạ ỉ ử ự ữ ạ ổ ướ c

không đáng k đ duy trì liên k t, còn khi có thay đ i thì ch g i thông tin v s thay đ i đó, ể ể ề ự ỉ ử ế ổ ổ

ng băng thông cho toàn m ng. d n t i gi m l ẫ ớ ả ượ ạ

Trong m ng đa truy c p OSPF (các nút m ng s d ng giao th c OSPF trao đ i thông tin ử ụ ứ ạ ạ ậ ổ

t b l p 2 mô hình OSI – nh v i nhau cùng n i vào thi ớ ố ế ị ở ớ ư Hình 10) có c ch b u ch n nút ơ ế ầ ọ

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 : 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 ậ ỉ ậ ự ạ

c tính toán theo băng đ i và ch c p nh t nh ng liên k t b thay đ i. Đ ng th i, do giá đ ổ ế ị ỉ ậ ữ ậ ồ ổ ờ ượ

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. ủ ế ượ ố ộ ư ạ

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 ư ế ả ặ ậ ị

i ho t đ ng gi ng nh OSPF, t c c p nh t đ nh đ ng c p nh t b ng đ nh tuy n thì EIGRP l ị ộ ậ ả ế ậ ạ ứ ậ ạ ộ ậ ị ư ố

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

c tính toán 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 đ ế ơ ẳ ứ ị ế ượ ủ ạ ớ ờ ồ ỗ

i. D a vào b n thông s này, m i thông d a vào b n thông s : băng thông, tr , đ tin c y và t ự ễ ộ ậ ố ố ả ự ố ỗ ố

ng đi đ c tính toán t i u, đ m b o cho các gói tin trong m ng luôn tin đ nh tuy n trong đ ế ị ườ ượ ố ư ả ả ạ

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: ộ

Ư

ủ

ể

M i AS ch y m t đ nh tuy n EIGRP chung và ch đ nh tuy n trong AS đó, mu n đ nh ố ị ộ ị ế ế ạ ỗ

Hình : u đi m c a phân vùng t ỉ

tr (AS) ự ị ị

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 ạ ầ

đ x lí cao, do đó hai giao th c này ch y u đ ộ ử ủ ế ượ ử ụ ỏ ớ c s d ng trong m ng lõi. V i m ng nh v i ớ ạ ứ ạ

ng ng i dùng ít ng s l ố ượ ườ ườ i ta s d ng đ nh tuy n RIP đ chi phí thi ế ử ụ ể ị ế ị ẻ ơ ễ ấ t b r h n, và d c u

hình s d ng h n. ử ụ ơ

III. K t lu n ế

ậ

Đ nh tuy n l u l

ế ư ượ

ị

ớ ng trong m ng đã tr i qua nh ng giai đo n phát tri n quan tr ng. V i

ữ

ể

ạ

ả

ọ

ng pháp đ nh

s phát tri n nhanh chóng c a công ngh vi n thông và máy tính, các ph ự

ệ ễ

ủ

ể

ươ

ị

tuy n m ng ngày càng tr nên linh ho t g n li n v i hi u qu c a ho t đ ng m ng l

ạ ộ

ạ ắ

ả ủ

ế

ề

ệ

ạ

ở

ớ

ướ i,

c trong công tác thi

k ho ch đ nh tuy n tr thành m t thành ph n không th thi u đ ộ ế

ể

ế

ạ

ầ

ở

ị

ượ

ế t

k , xây d ng và v n hành, qu n lý m ng. ế

ự

ả

ạ

ậ

Qua quá trình tìm hi u v đ nh tuy n t

sách báo và internet, bài t p l n c a chúng em

ề ị

ế ừ

ể

ậ ớ

ủ

đ a ra các v n đ : ề

ấ

Đ nh tuy n.

ế

ị

ng pháp đ nh tuy n (các lo i đ nh tuy n).

ươ

ạ ị

ế

ị

Thu t toán đ nh tuy n và ví d . ụ

ế

ậ

ị

Giao th c đ nh tuy n ng d ng các thu t toán.

ế ứ

ứ

ụ

ậ

ị

Bài t p l n c a chúng em còn nhi u thi u sót, r t mong đ

c s ch b o c a th y giáo.

ậ ớ

ủ

ề

ế

ấ

ượ

ỉ ả

ự

ủ

ầ

Em xin chân thành c m n th y!

ả ơ

ầ

IV. Tài li u tham kh o ả

ệ

[1] Rick Graziani - Allan Johnson, Routing Protocols And Concepts. Cisco Press,

2008.

[2] Donald Gross, Carl M. Harris, Fundamentals of Queueing Theory, Wiley-

Interscience,1998

[3] Joseph L. Hammond, Peter J.P.O' Reilly, Performance Analysis of Local

Computer Networks, Addison-Wesley, 1988

C s m ng thông tin [4] Slide gi ng d y môn ả ạ ơ ở ạ ệ , TS. Nguy n Văn Ti n, Vi n Đi n ễ ế ệ

t ử ễ ộ . vi n thông, Đ i h c Bách Khoa Hà N i ạ ọ

M ng máy tính [5] Slide gi ng d y môn ả ạ ạ ệ , Gi ng viên Nguy n H u Thanh, Vi n ễ ữ ả

Đi n t ệ ử ễ vi n thông, Đ i h c Bách Khoa Hà N i. ộ ạ ọ