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

Chia sẻ: Nguyễn Phú Tiền | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

193
lượt xem 23
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Đô

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 more information and additional documents connect with me here: http://facebook.com/ngphutien/ Gi¸o viªn hướng dÉn : GS. TS. NguyÔn Thóc H¶i Sinh viªn thùc hiÖn : NguyÔn ViÕt Ngäc Líp : K96C2 Các file liên quan tới đồ án: Giai thuat chon duong tren mang.rar 302 KB https://mega.co.nz/#!Eg9ygITR!EE5cx1T1r4DbWgwyCMQ JaEdvQn5idN5jhY2hkg8joG4
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 • B¶ng chän ®ường (th«ng tin vÒ toµn bé m¹ng) gåm : ID m¹ng ®Ých, “chi phÝ”, ID router kÕ tiÕp C¸c b¶ng chän ®ường trong mét liªn m¹ng • “Chi phÝ” lµ sè chÆng (hop) vµ lµ 1 ®¬n vÞ víi mäi liªn kÕt • Chu kú cËp nhËt b¶ng chän ®ường ng¾n (kho¶ng 30 gi©y/lÇn). CËp nhËt b¶ng chän ®ường cho router A
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 m¹ng ij. lij=vc nÕu ktt ®- ườ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
Minh häa thuËt to¸n Dijkstra (2) 5. C lµ ®Ønh tiÕp theo cã nh·n nhá nhÊt ®îc chän. CËp nhËt l¹i c¸c nh·n l©n cËn C, ®¸nh dÊu l¹i ®ường ®i CF (do CF
Cµi ®Æt thuËt to¸n Dijkstra
KÕt luËn KÕt qu¶ nghiªn cøu :  T×m hiÓu, ph©n tÝch vµ ®¸nh gi¸ ®îc c¸c kü thuËt chän ®- ường tiªu biÓu nhÊt.  Cµi ®Æt thö nghiÖm ®îc thuËt to¸n Dijkstra vµ m« pháng qu¸ tr×nh chän ®ường trªn m¹ng. H¹n chÕ :  Cha t×m hiÓu thùc tÕ ®îc qu¸ tr×nh chän ®ường cña c¸c lo¹i m¹ng kh¸c nhau.  Cha cµi ®Æt ®îc thuËt to¸n chän ®ường trªn mét m¹ng thùc sù.