Xem mẫu
- 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ù.
nguon tai.lieu . vn
