Báo cáo tốt nghiệp: Nghiên cứu các giải thuật chọn đường trên mạng - ĐH Đông Đô

Báo cáo tốt nghiệp: Nghiên cứu các giải thuật chọn đường trên mạng trình bày các kỹ thuật chọn đường trong mạng như kỹ thuật chọn đường thích nghi và kỹ thuật chọn đường không thích nghi; cài đặt thử nghiệm thuật toán chọn đường và kết luận.

ngphutien

trường ®¹i häc ®«ng ®« khoa c«ng nghÖ th«ng tin

b¸o c¸o tèt nghiÖp nghiªn cøu c¸c gi¶i thuËt chän ®ƯỜng trªn m¹ng

Néi dung b¸o c¸o tèt nghiÖp

 C¸c kü thuËt chän ®ƯỜng trong m¹ng

 Kü thuËt chän ®ường thÝch nghi

 Chän ®ường theo vÐc-t¬ kho¶ng c¸ch

 Chän ®ường theo tr¹ng th¸i liªn kÕt

 Kü thuËt chän ®ường kh«ng thÝch nghi

 Chän ®ường tÜnh

 Chän ®ường tËp trung

 Cµi ®Æt thö nghiÖm thuËt to¸n chän ®ƯỜng

 ThuËt to¸n Dijkstra

 Cµi ®Æt thuËt to¸n Dijkstra

 kÕt luËn

C¸c kü thuËt chän đường trong m¹ng

Chän ®ường trong m¹ng lµ viÖc lùa chän ®ường ®i tèi u ®Ó truyÒn mét ®¬n vÞ d÷ liÖu tõ tr¹m nguån tíi tr¹m ®Ých

C¸c tiªu chuÈn thường ®îc chän ®Ó x¸c ®Þnh ®ường ®i tèi ưu :

 §é dµi ®ường dÉn (path length)  §é tin cËy cña viÖc truyÒn tin (reliability)  §é trÔ (delay)  Chi phÝ truyÒn tin (communication cost)

Chän ®ường theo vÐc-t¬ kho¶ng c¸ch

• Mçi

router chia xÎ b¶ng chän ®ường víi c¸c router l©n cËn

gåm :

C¸c b¶ng chän ®ường trong mét liªn m¹ng

• B¶ng chän ®ường (th«ng tin vÒ toµn bé ID m¹ng) m¹ng ®Ých, “chi phÝ”, ID router kÕ tiÕp

•

“Chi phÝ” lµ sè chÆng (hop) vµ lµ 1 ®¬n vÞ víi mäi liªn kÕt

CËp nhËt b¶ng chän ®ường cho router A

• Chu kú cËp nhËt b¶ng chän ®ường ng¾n (kho¶ng 30 gi©y/lÇn).

Chän ®ường theo tr¹ng th¸i liªn kÕt

• Mçi router chia xÎ b¶ng chän ®ường víi toµn bé c¸c router trong

m¹ng

• B¶ng chän ®ường (th«ng tin vÒ c¸c router l©n cËn) gåm : ID qu¶ng

•

c¸o, ID m¹ng l©n cËn, “chi phÝ”, ID router l©n cËn. “Chi phÝ” lµ 1 gi¸ trÞ ®îc tÝnh dùa trªn sù biÕn ®æi cña yÕu tè an toµn hay tr¹ng th¸i liªn kÕt

• Chu kú cËp nhËt b¶ng chän ®ường lín (kho¶ng 30 phót/lÇn).

Chän ®ường tÜnh

• Mçi nót m¹ng cã mét b¶ng chän ®ường gåm : nót m¹ng ®Ých mµ gãi tin cã thÓ ®îc chuyÓn ®Õn & c¸c ®ường ®i kh¸c nhau tíi ®Ých.

• B¶ng chän ®ường ®îc ngêi qu¶n trÞ m¹ng tÝnh to¸n tríc vµ cµi ®Æt trong m¹ng cè ®Þnh. • Tríc khi göi gãi tin, mét nót m¹ng t¹o ra mét sè ngÉu nhiªn vµ chän ra mét ®ường ®i thÝch hîp dùa trªn sè ngÉu nhiªn ®ã.

Chän ®ường tËp trung

• Trong m¹ng cã mét vµi trung t©m ®iÒu khiÓn chän ®ường RCC (Routing Control Center) ®Ó cÊt gi÷ th«ng tin tæng thÓ vÒ m¹ng. • C¸c nót m¹ng cã thÓ kh«ng göi th«ng tin nµo vÒ m¹ng tíi trung t©m

hoÆc (chän ®ường tÜnh) göi theo ®Þnh kú (chän ®ường ®éng).

• ¦u ®iÓm : th«ng tin trong RCC ®Çy ®ñ nªn ®a ra quyÕt ®Þnh chän ®ường nhanh vµ chÝnh x¸c. Gi¶i phãng c¸c nót m¹ng khái viÖc tÝnh to¸n chän ®- ường.

• Nhîc ®iÓm : dÔ x¶y ra t¾c nghÏn do sù tËp trung lu l- îng cao t¹i c¸c trung t©m ®iÒu khiÓn chän ®ường.

ThuËt to¸n Dijkstra

•

lij : kho¶ng c¸ch gi÷a 2 nót lij=vc nÕu ktt ®- m¹ng ij. ường.

• Nk : tËp hîp cña k+1 phÇn

Minh häa thuËt to¸n Dijkstra (1)

1. S¬ ®å m¹ng vÝ dô 2. A lµ ®Ønh nguån. Nh·n cña c¸c ®Ønh ®îc g¸n gi¸ trÞ v« cïng lín.

3. Nh·n cña c¸c ®Ønh l©n cËn A ®îc g¸n gi¸ trÞ b»ng kho¶ng c¸ch gi÷a chóng 4. D lµ ®Ønh cã "gi¸ trÞ" nhá nhÊt ®îc chän. Nh·n cña c¸c ®Ønh l©n cËn D ®îc g¸n gi¸ trÞ b»ng kho¶ng c¸ch gi÷a chóng víi gi¸ trÞ nh·n cña D