Bài giảng Truyền số liệu và mạng - Chương 5: Mạng viễn thông

ï nhaän caùc goùi döõ töø nguoàn chuyeån ñeán traïm ñích
„ Khi caùc goùi döõ lieäu ñi vaøo nuùt chuyeån maïch, chuùng ñöôïc kieåm 
tra bôûi CPU cuûa nuùt (ñòa chæ ñích lôùp maïng cuûa goùi). Döïa vaøo 
ñoù goùi seõ ñöa ñeán haøng ñôïi cuûa ngoõ ra thích hôïp. Chöùc naêng 
naøy ñöôïc goïi laø ñònh tuyeán (routing) 
¾ Vieäc ñònh tuyeán taïi moãi nuùt seõ gaây ra 
thôøi gian treã 
‰ Treã do xeáp haøng trong CPU vaø
haøng ñôïi lieân keát ra
‰ Treã do thôøi gian xöû lyù cuûa CPU
‰ Treã do thôøi gian truyeàn goùi 
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-73
User Plane
Control Plane
Output 
Packets
Input 
Packets
Header payload 
Forwarding
Table
Packet
Classification
Next Hop + Port
Queuing and 
Schedule rules
Output
Queue
Routing
Packets
Ñònh tuyeán
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-74
Ñònh tuyeán
„ Ñònh tuyeán
„ Nhaän goùi döõ lieäu töø nguoàn vaø phaân phoái ñeán ñích
„ Nuùt chuyeån maïch
„ Thöïc hieän vieäc chuyeån maïch
„ Ñònh tuyeán
„ Ñònh tuyeán khoâng baûng:
„ Ngaãu nhieân
„ Nguoàn
„ Tính toaùn
„ Ñònh tuyeán theo baûng
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-75
Ñònh tuyeán
„ Ñònh tuyeán theo baûng
„ Xaùc ñònh con ñöôøng ñeán ñích toái öu
„ Khi tính toaùn toái öu, coù theå xem xeùt ñeán:
„ Toång thôøi gian truyeàn
„ Thôøi gian xöû lyù vaø xeáp haøng taïi moãi nuùt
„ Möùc ñoä öu tieân cuûa moãi goùi
„ Hoaïch ñònh cuûa admin
„ Thuû tuïc ñònh tuyeán
„ Tính chaát:
„ Tónh & ñoäng
„ Taäp trung & phaân boá
„ Thuû tuïc taäp trung: Shortest Forward Path Tree (SFPT), Shortest 
Backward Path Tree (SBPT)
„ Thuû tuïc phaân boá: Thuû tuïc trao ñoåi khoaûng caùch
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-76
Ñònh tuyeán
„ THUAÄT TOAÙN SFPT 
(SHORT FORWARD PATH FIRST)
„ Xaùc ñònh ñöôøng ñi ngaén nhaát töø 1 nguoàn tôùi taát caû caùc nuùt 
treân maïng 
„ Vò trí trung taâm caàn phaûi thöïc hieän vieäc tính toaùn naøy moät 
laàn cho moãi node ñeå xaùc ñònh con ñöôøng ngaén nhaát tôùi moãi 
node coøn laïi
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-77
Ñònh tuyeán
„ Moâ taû thuaät toaùn SFPT :
„ Trong caây SHORT FORWARD PATH FIRST (SFPT), Dijkstra ñaõ ñònh nghóa 
ra ba loaïi nhaùnh : I, II vaø III. Vaø trong router, seõ coù ba database ñaïi dieän cho 
taäp ba loaïi nhaùnh ñoù, goàm coù :
„ Tree database : ñaïi dieän cho nhaùnh loaïi I. Nhöõng link (nhaùnh) naøo ñöôïc theâm 
vaøo caây SFPT seõ ñöôïc theâm vaøo ñaây. Khi thuaät toaùn SFPT hoaøn taát, thì
database naøy chính laø toaøn boä caây SFPT.
„ Candidate database : database naøy ñaïi dieän cho nhaùnh loaïi II. Caùc link ñöôïc 
copy töø link state database sang database naøy theo moät traät töï nhaát ñònh. Caùc 
link trong database naøy seõ laàn löôït ñöôïc khaûo saùt ñeå theâm vaøo caây SFPT.
„ Link state database : chöùa taát caû caùc link. Ñaïi dieän cho loaïi nhaùnh III.
„ Ngoaøi ra Dijkstra cuõng ñònh nghóa ra hai loaïi node, A vaø B. Loaïi A, bao goàm 
taát caû caùc router noái vôùi caùc link trong caây SFPT. Loaïi B, goàm taát caû caùc 
router khaùc. Khi thuaät toaùn SFPT keát thuùc thì caùc router loaïi B seõ khoâng coøn.
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-78
Ñònh tuyeán
„ Thuaät toaùn SFPT cuûa Dijkstra nhö sau :
„ Böôùc 1 : Choïn moät router laøm goác.
„ Böôùc 2 : taát caû caùc link noái giöõa router goác vôùi neighbor cuûa noù seõ 
ñöôïc ñöa vaøo candidate database.
„ Böôùc 3 : cost cuûa moãi link trong candidate database seõ ñöôïc tính toaùn. 
Link naøo coù cost nhoû nhaát seõ ñöôïc theâm vaøo Tree database. Neáu nhö
coù hai link coù cost nhoû nhaát baèng nhau thì seõ choïn moät.
„ Böôùc 4 : router nighbor noái vôùi ñöôøng link ñoù seõ ñöôïc kieåm tra. Taát caû
caùc ñöôøng link noái vôùi router ñoù seõ ñöôïc ñöa vaøo candidate database, 
ngoaøi tröø ñöôøng link ñaõ coù trong Tree database.
„ Böôùc 5 : Neáu vaãn coøn giaù trò trong candidate database thì thuaät toaùn seõ 
quay laïi böôùc 3 thöïc hieän tieáp. Neáu khoâng coøn, thì döøng thuaät toaùn. 
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-79
Ñònh tuyeán
Giaûi thuaät :
N={s} (với s là nút nguồn )
For all node v#s
Begin 
εsv:=Csv
If εsv<∞ then Lsv:=(s,v)
End
Do while (N không chứa tất cả các node)
Find w#N for which εsw=minεsv
N=N∪{w} (N hợp với w, tức bổ sung thêm w vào N)
For all v∉N
Begin
Temp:=εsv
εsv:=min(εsv,εsw +εwv)
if εsv<temp then
L:=Lsw∪{v}
End
End
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-80
Ñònh tuyeán
„ Ví duï :Tìm ñöôøng ñi ngaén nhaát töø A ñeán taát caû caùc nuùt
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-81
Ñònh tuyeán
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-82
Ñònh tuyeán
AB
CD
E
3
2
1
7
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-83
Caùc thieát bò maïng vaø lieân maïng
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-84
Caùc thieát bò maïng vaø lieân maïng
¾Repeater (boä laëp laïi): Chæ hoaït ñoäng ôû lôùp 1
¾Bridge (caàu noái): hoaït ñoäng ôû lôùp 1 vaø 2
¾Router (boä ñònh tuyeán): hoaït ñoäng ôû lôùp 1, 2 vaø 3
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-85
Caùc thieát bò maïng vaø lieân maïng
„ Repeater
„ Repeater laø thieát bò maïng, hoaït ñoäng trong 1 maïng LAN 
„ Hoaït ñoäng trong phaïm vi lôùp vaät lyù cuûa moâ hình OSI
„ Keùo daøi chieàu daøi vaät lyù cuûa maïng baèng caùch khoâi phuïc laïi 
tín hieäu (ñaõ yeáu) treân ñöôøng truyeàn 
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-86
Caùc thieát bò maïng vaø lieân maïng
„ Bridge
„ Bridge laø thieát bò maïng, hoaït ñoäng trong 1 maïng LAN 
„ Brigde chia maïng lôùn thaønh nhieàu maïng nhoû hôn ñeå giaûm 
bôùt xung ñoät 
„ Hoaït ñoäng trong phaïm vi lôùp vaät lyù vaø lieân keát döõ lieäu cuûa 
moâ hình OSI
„ Bridge laøm nhieäm vuï taùi taïi tín hieäu vaø kieåm tra ñòa chæ ñeå
phaân phoái chuùng ñeán ñích döïa vaøo baûng ñòa chæ
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-87
Caùc thieát bò maïng vaø lieân maïng
D E F 
A truyeàn data ñeán C, D truyeàn data ñeán F ñoàng thôøi
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-88
Caùc thieát bò maïng vaø lieân maïng
„ Router
„ Router laø thieát bò lieân maïng, duøng ñeå keát noái caùc maïng 
LAN 
„ Hoaït ñoäng trong phaïm vi lôùp vaät lyù, lieân keát döõ lieäu vaø lôùp 
maïng cuûa moâ hình OSI
„ Chöùa phaàn meàm thöïc hieän vieäc ñònh tuyeán (xaùc ñònh 
ñöôøng ñi ngaén nhaát).
„ Vieäc ñònh tuyeán ñöôïc thöïc hieän döïa treân ñòa chæ cuûa lôùp 
maïng (ñòa chæ IP)
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-89
Caùc thieát bò maïng vaø lieân maïng
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-90
Caùc thieát bò maïng vaø lieân maïng
„ GATEWAY
„ Hoaït ñoäng ôû caû 7 lôùp trong moâ hình tham khaûo OSI 
„ Coù theå truyeàn döõ lieäu giöõa 2 maïng coù nghi thöùc khaùc nhau
„ Gateway (coång) thöôøng laø boä ñònh tuyeán coù caøi phaàn meàm 
ñeå hieåu nhöõng nghi thöùc cuûa moãi maïng coù keát noái ñeán boä
ñònh tuyeán 
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-91
Chöông 5_Baøi taäp :
Mạng Viễn thoâng
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-92
Baøi 1
„ Haõy tính vaø ñieàn caùc thoâng soá thích hôïp vaøo baûng sau
175.12.239.244
194.125.35.199
150.127.221.244
123.1.1.15
218.14.55.137
Broadcast AddressHost AddressNetwork Address
Address 
ClassHost IP Address
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-93
Baøi 2
„ Cho bieát trong caùc ñòa chæ IP sau ñaây. Ñòa chæ naøo khoâng coù
giaù trò. Taïi sao ?
„ 150.100.255.255
„ 175.100.255.18
„ 195.234.253.0
„ 100.0.0.23
„ 188.258.221.176
„ 127.34.25.189
„ 224.156.217.73
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-94
Baøi 3
„ Moät chi nhaùnh coâng ty A coù ñòa chæ maïng laø : 192.168.24.100/24 
„ Haõy cho bieát /24 mang yù nghóa gì vaø cho bieát ñòa chæ IP naøy thuoäc lôùp 
maïng naøo? Subnet mask laø bao nhieâu ?
„ Giaû söû chi nhaùnh muoán chia ra 4 maïng con (subnets), moãi subnet coù
khoaûng 30 hosts. Haõy tính vaø ñieàn thoâng soá vaøo baûng sau:
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-95
Baøi 4
„ Moät nhaø quaûn trò maïng caàn xaây döïng moät network bao goàm 5 
subnet nhö hình veõ sau:
•Vôùi caùc yeâu caàu:
Net1: goàm 10 thieát bò maïng
Net2: goàm 6 thieát bò maïng
Net3: goàm 18 thieát bò maïng
Net4: goàm 22 thieát bò maïng
Net5: goàm 17 thieát bò maïng
„ Haõy chia ñòa chæ IP cho caùc subnet vaø xaùc ñònh subnet-mask töông öùng 
vôùi ñòa chæ IP lôùp C 192.28.15.0 cho tröôùc.
„ Haõy tính soá löôïng ñòa chæ IP toång coäng coù theå söû duïng ñöôïc töø ñoù suy 
ra soá löôïng IP coøn laïi.
„ Neáu duøng taát caû caùc thieát bò maïng cuûa 5 subnet treân trong moät 
network duy nhaát söû duïng ñòa chæ netwwork laø 192.28.15.0. Haõy tính 
soá löôïng ñòa chæ IP coøn laïi trong network ñoù
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-96
Baøi 5
„ Moät coâng ty coù 4 chi nhaùnh ñöôïc caáp ñòa chæ IP lôùp C 
192.168.12.0. Chi nhaùnh 1 döï kieán coù toái ña 60 ngöôøi söû duïng 
vaø caùc chi nhaùnh coøn laïi toái ña 25 ngöôøi söû duïng. Tính toaùn 
phaân vuøng ñòa chæ IP ñöôïc caáp cho caùc chi nhaùnh cuûa coâng ty vaø
ghi chuù daõy ñòa chæ IP coù theå caáp cho ngöôøi söû duïng cuûa töøng
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-97
Baøi 6
„ Cho topo maïng nhö Hình veõ döôùi ñaây, vôùi nuùt goác laø A
„ Duøng giaûi thuaät ñònh tuyeán OSPF, laäp baûng ñònh tuyeán vaø tìm ñöôøng 
ñi ngaén nhaát töø nuùt goác laø A ñeán caùc nuùt coøn laïi treân maïng.
„ Khi moät link treân maïng bò hoûng thì laøm theá naøo caùc Router bieát ñeå caäp 
nhaät laïi baûng ñònh tuyeán.
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-98
Baøi 7
„ Cho topo maïng nhö Hình veõ döôùi ñaây, vôùi nuùt goác laø A
„ Duøng giaûi thuaät ñònh tuyeán OSPF, laäp baûng ñònh tuyeán vaø tìm ñöôøng 
ñi ngaén nhaát töø nuùt goác laø A ñeán caùc nuùt coøn laïi treân maïng.
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-99
Baøi 8
„ Cho maïng coù caáu truùc nhö hình veõ. Söû duïng thuaät toaùn 
Dijkstra ñeå tìm ñöôøng ñi töø node F ñeán caùc node coøn laïi
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-100
Baøi 9
„ Ñieàn caùc thoâng soá vaøo baûng sau
Khoa Điện – Điện tử - ĐHBK TP.HCM 5-101
Baøi 10
„ Haõy cho bieát phaûi duøng loaïi caùp naøo ñeå keát noái caùc thieát bò 
sau (coång LAN): Router-Router, PC-PC, Switch-Switch, 
Router-Switch, PC-Switch, PC-Router