Bài giảng Mạng máy tính - Chương 4: Lớp Network - Nguyễn Cao Đạt

Nội dung text: Bài giảng Mạng máy tính - Chương 4: Lớp Network - Nguyễn Cao Đạt

1. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK CHÖÔNG IV Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 1 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Muïc tieâu thieát keá lôùp network : – Lieân maïng: z Autonomous domain (subnet). z Söû duïng caùch ñaùnh ñòa chæ maïng coù tính toaøn cuïc. z Ñònh tuyeán. z Söû duïng nhieàu kyõ thuaät lieân keát (LAN, WAN). – Ñònh tuyeán trong lieân maïng. – Giaûi quyeát taéc ngheõn. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 2
2. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Thieát bò söû duïng : – Chuyeân duïng vaø duøng vaøo muïc ñích ñaëc bieät. – Laøm vieäc ñöôïc vôùi caùc kyõ thuaät LAN hay WAN. – Ñöôïc bieát döôùi teân laø router hay ñoâi khi coøn goïi laø gateway. •router Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 3 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Toå chöùc beân trong cuûa lôùp network : – Virtual circuit z Caàu noái ñöôïc thieát laäp nhö laø ñöôøng ñi cuûa packet. z Taát caùc caùc döõ lieäu truyeàn qua caàu noái. z Caàu noái ñoùng thì virtual circuit seõ ñoùng. – Datagram z Packet ñöôïc tìm ñöôøng ñoäc laäp. z Töøng datagram chöùa ñöïng ñaày ñuû caùc ñòa chæ. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 4
3. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï veà IP (Internet Protocol) – RFC 791 – Giao thöùc lôùp 3 phoå bieán. – Giao thöùc neàn taûng taïo neân Internet. – Connectionless. z Ví duï veà ñòa chæ IP – Ñoäc laäp vôùi ñòa chæ phaàn cöùng (MAC). – Ñöôïc duøng cho nhöõng giao thöùc lôùp cao hôn vaø caùc öùng duïng maïng. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 5 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï veà ñòa chæ IPv4 – Ñöôïc duøng cho vaán ñeà truyeàn thoâng lieân maïng. – Ñöôïc gaùn treân moãi giao tieáp maïng. z Moät ñòa chæ IP töông öùng moät keát noái giöõa moät maùy tính vaø maïng. z Moät maùy tính coù nhieàu giao tieáp maïng töông öùng seõ coù moãi ñòa chæ IP treân moãi giao tieáp maïng. – Coù chieàu daøi 32 bit vaø chia thaønh hai phaàn: z prefix chæ ñònh maïng (do global authority gaùn) z suffix chæ ñònh maùy tính treân moãi giao tieáp (do Local administrator gaùn). Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 6
4. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK •Moâ hình ñaùnh ñòa chæ IP trong maïng Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 7 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï veà dònh daïng cuûa Packet (IP Datagram) Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 8
5. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï vaán ñeà veà truyeàn nhaän IP Datagram – Khoâng höôùng keát noái (connectionless), töùc coù thay ñoåi ñöôøng ñi. – Coù theå ñöôïc trì hoaõn vaø truyeàn khoâng theo thöù töï. – Coù theå bò maát trong khi truyeàn vì vaäy caàn taïo baûn sao. z Ví duï veà ñònh tuyeán treân IP – Ñöôïc dieãn taû taïi caùc router. – Chuyeån tieáp cô baûn döïa treân hop-by -hop. – Ñòa chæ ñích ñöôïc duøng cho vieäc xaùc ñònh ñöôøng ñi. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 9 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï veà vieäc ñònh tuyeán – Xaùc ñònh ñòa chæ ñích D. – Tìm ñöôøng ñi ñeán D trong baûng ñöôøng ñi. – Tìm ra ñòa chæ gôûi keá tieáp (Next hop address). – Gôûi Frame ñeán N. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 10
6. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK IP Routing 140.192.10.5 140.192.10.25 140.192.100.34 140.192.100.8 0060CA23BE45 0060CA34CD29 0060CA4AD2EE 0060CAAABBCC 140.192.10.1 140.192.100.1 00C0C1AA3411 00C0C1AA3412 Router 140.192.201.1 140.192.34.1 00C0C1AA3410 00C0C1AA3413 140.192.201.22 140.192.201.126 140.192.34.34 140.192.34.35 0060CA3499CC 0060CA3499DE 0060CA114499 0060CA7819AA Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 11 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Laøm theá naøo ñeå chuyeån döõ lieäu giöõa caùc maïng – Döïa vaøo baûng ñöôøng ñi taïi boä ñònh tuyeán. Layer 2 Layer 3 Table Routing Table ARP Table Network Interface Network.Host Layer 2 140.192.10.0 0 140.192.10.5 0060CA23BE45 140.192.100.0 1 140.192.10.25 0060CA34CD29 140.192.201.0 2 140.192.100.34 0060CA4AD2EE 140.192.34.0 3 140.192.100.8 0060CAAABBCC 140.192.201.22 0060CA3499CC 140.192.201.126 0060CA3499DE 140.192.34.34 0060CA114499 140.192.34.35 0060CA7819AA Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 12
7. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK From 140.192.34.34 to 140.192.10.5 140.192.34.34 knows that 140.192.10.5 isn't on the same net and sends it to router at 140.192.34.1 Note DA for layer 2 00C0C1AA3413 0060CA114499 IP 140.192.10.5 140.192.34.34 Data FCS Inside the router the Layer 2 headers and trailers are removed leaving only the layer 3 packet. The router looks up the packet's DA in the routing table and forwards to the appropriate interface. 140.192.10.5 140.192.34.34 Data At the interface, layer 2 headers and trailers are added back. DA is the address of the destination host. SA is the address of the router. FCS is recalculated. 0060CA23BE45 00C0C1AA3411 IP 140.192.10.5 140.192.34.34 Data FCS Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 13 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z ARP: – Address Resolution Protocol – Phaân giaûi ñòa chæ IP thaønh ñòa chæ MAC. – Moãi node gôûi broadcast tìm moät node khaùc: z 140.192.34.34 broadcasts tìm 140.192.34.1 – Node töông öùng traû lôøi vôùi ñòa chæ MAC cuûa noù z 140.192.34.1 traû lôøi vôùi 00C0C1AA3412 z Baûng ARP: – Bao goàm caùc tröôøng (IP, MAC) ñaõ ñöôïc hoïc töø caùc node laùng gieàng. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 14
8. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï veà baûng ñöôøng ñi Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 15 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Laøm theá naøo ñeå xaây döïng baûng ñöôøng ñi ? – Laøm baèng tay (Static Routing) z Baûng ñöôïc taïo baèng tay. z Thöôøng ñöôïc duøng trong caùc maïng nhoû. z Ñöôïc duøng neáu ñöôøng ñi khoâng bao giôø thay ñoåi. – Töï ñoäng (Dynamic Routing) z Phaàn meàm taïo vaø caäp nhaät thoâng tin trong baûng. z Caàn duøng trong caùc maïng lôùn. z Thay ñoåi ñöôøng ñi khi coù moät soá söï coá xaûy ra. z Ví duï: Distance Vector Routing, Link State Routing, Hierarchical Routing. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 16
9. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Laøm theá naøo ñeå tìm ra ñöôøng ñi toát nhaát ? – Bieåu dieãn maïng döôùi daïng ñoà thò: z Node : bieåu dieãn cho router z Arc :bieåu dieãn communication line (link) z Ñaïi löôïng söû duïng: – Khoaûng caùch. – Thôøi gian delay trung bình. – Dung löïông. – Söû duïng moät giaûi thuaät tìm ñöôøng z Dijkstra. z Flooding, z Flow-Based Routing. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 17 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK B7C B (2, A) C (¥, -) 3 2 2 3 E 2F E (¥, -) A D A 1 2 F (¥, -) D (¥, -) 6 4 2 G H G (6, A) H (¥, -) (a) (b) B (2, A) C (9, B) B (2, A) C (9, B) E (4, B) E (4, B) A F (¥, -) D (¥,-) A F (6, E) D (¥,1) G (6, A) H (¥, -) G (5, E) H (¥, -) (c) (d) B (2, A) C (9, B) B (2, A) C (9, B) E (4, B) E (4, B) A F (6, E) D (¥,-) A F (6,E) D (¥,-) G (5, E) H (9, G) G (5, E) H (8, F) (e) (f) •Moät ví duï tìm ñöôøng töø A->D duøng Dijkstra Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 18
10. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Giaûi thuaät Flooding : – Packet ñeán gôûi ra taát caû caùc link. – Taïo moät löôïng lôùn packet truøng laëp. – Caùc kyõ thuaät giaûi quyeát truøng laëp : z Duøng kyõ thuaät hop counter ñeå loaïi boû z Löu tröõ laïi packet ñaõ ñöôïc flood – Selective flooding : z Router gôûi packet ra caùc link höôùng tôùi ñích. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 19 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Giaûi thuaät Flow-Based Routing : – Thuaät giaûi söû duïng taûi & moâ hình maïng (topology) cho tính toaùn vaø choïn ñöôøng ñi toát nhaát (coù thôøi gian treå trung bình nhoû nhaát). z Tính toaùn thôøi gian treã trung bình döïa treân taûi & topology. z Tính nhieàu laàn treân nhieàu taäp ñöôøng ñi. z Choïn ra taäp ñöôøng ñi toát nhaát. z Caùc thoâng tin ñeå tính toaùn thôøi gian treå trung bình: z Moâ hình maïng. z Löu löôïng thoâng tin giöõa caùc node (router). z Dung löôïng ñöôøng truyeàn giöõa caùc node (router). z Taäp ñöôøng ñi ñang söû duïng. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 20
11. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Giaûi thuaät Flow-Based Routing : Destination ABCDEF 9 4 1 7 4 A AB ABC ABFD AE AEF 9 8 3 2 4 B BA BC BFD BFE BF BC20 4 8 3 3 2 20 10 C CBA CB CD CE CEF AD 20 20 1 3 3 3 4 20 10 Source D DFBA DFB DC DCE DF EF50 7 2 3 3 5 (a) A subnet with line E EA EFB EC ECD EF capacibilities shown in kbps 4 4 2 4 5 F FEA FB FEC FD FE (b) The traffic in packets/sec and the routing matrix Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 21 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Caùc coâng thöùc tính toaùn – Ti= 1/(µCi - λi) – Wi= λI / Σλi – Taver = Ti x Wi Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 22
12. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Ví duï: (giaû söû 1/µ = 800 bits/packet) Line λ (pkts/sec) C(kbps) µC(pkts/sec) T(msec) Weight AB 14 20 25 91 0.171 BC 12 20 25 77 0.146 CD 6 10 12.5 154 0.073 AE 11 20 25 71 0.134 EF 13 50 62.5 20 0.159 FD 8 10 12.5 222 0.098 BF 10 20 25 67 0.122 EC 8 20 25 59 0.098 Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 23 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z New esti mated Distance Vector Routing Router delay from J – Laø giaûi thuaät ñoäng (RIP, AB C D To A I H K 0 24 20 21 8 RIPv2, IGRP) 12 36 31 28 20 25 18 19 36 28 – Coøn goïi laø Bellman-Ford, FG E H 40 27 8 24 20 Ford-Fulkerson routing. 14 7 30 22 17 23 20 19 40 30 – Töøng router coù moät baûng cho 18 31 6 31 18 17 20 0 19 12 IJ K L bieát con ñöôøng toát nhaát tôùi 21 0 14 22 10 ñích. (a) Subnet 9 11 7 10 0 24 22 22 0 6 – Ñònh kyø trao ñoåi caùc baûng 29 33 9 9 15 JA JI JH JK ñöôøng ñi vôùi caùc router laùng delaydelay delay delay New is is is is routing gieàng. 810126 table for J – Tính toaùn laïi khi caùc lieân keát Vectors received from J's four neighbors coù loãi. (b) routing table Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 24
13. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Distance Vector Routing : (Tieáp theo) – Vaán ñeà Count-to-Infinity : ABCDE ABCDE ∞∞∞∞Initially 1234Initially 1 ∞∞∞After 1 exchange 3 234After 1 exchange 1 2 ∞∞After 2 exchanges 3 4 34After 2 exchange 1 2 3 ∞ After 3 exchanges 5 4 5 4 After 3 exchange 1 2 3 4 After 4 exchanges 5 6 5 6 After 4 exchange 7676 After 5 exchange (a) 7878 After 6 exchange . . ∞∞∞∞ (b) Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 25 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Distance Vector Routing : (Tieáp theo) – Giaûi quyeát vaán ñeà Count-to-Infinity : z Hold down : – Chôø moät thôøi gian tröôùc khi thay ñoåi ñöôøng ñi. Baùo giaù trò voâ cuøng cuûa moät router. Caên baûn döïa vaøo timer. z Report the entire path : – Baûo ñaûm khoâng bò laêp nhöng traû giaù khaù ñaét. z Split horizon : – Khoâng baùo caùc ñöôøng ñi ñeán caùc router laùng gieàng neáu höôùng ñi ñoù khoâng nhaän ñöôïc töø caùc router laùng gieàng khaùc. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 26
14. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Link State Routing : – OSPF – Caùc router trao ñoåi thoâng tin traïng thaùi lieân keát. – Caùch thöïc hieän : z Tìm caùc neighbors & hoïc ñòa chæ cuûa noù : – Duøng packet HELLO z Tính toaùn delay & chi phí cho töøng neighbors cuûa noù : – Duøng packet ECHO. z Xaây döïng packet duøng baùo taát caû ñaõ ñöôïc hoïc. z Gôûi packet naøy ñeán taát caû router : duøng flooding z Tính toaùn con ñöôøng ngaén nhaát tôùi moïi router khaùc. Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 27 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Link State Routing : (Tieáp theo) – Xaây döïng Link State packet : z Packet bao goàm : – Sender – Sequence number & age – Danh saùch caùc neighbors BC2 Link State Packets A B C D E F 4 3 Seq. Seq. Seq. Seq. Seq. Seq. ADAge Age Age Age Age Age 1 6 B 4 A 4 B 2 C 3 A 5 B 6 5 7 E5 C2 D3 F7 C1 D7 EF8 F6 E1 F8 E8 (a) A subnet (b) The link state packets for this subnet Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 28
15. Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Hierarchical Routing : – Heä thoáng maïng lôùn -> baûng routing lôùn : z Hao toán nhieàu taøi nguyeân khi xöû lyù z Hao toán nhieàu bandwitdth ñeå truyeàn nhaän caùc report – Router chia thaønh caùc vuøng (regions) – Router bieát roõ veà vuøng cuûa mình & khoâng bieát caáu truùc caùc vuøng khaùc Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 29 Tröôøng Ñaïi Hoïc Baùch Khoa Tp.HCM LÔÙP NETWORK z Hierarchical Routing : (Tieáp theo) Full table for 1A Hierarchical table for 1A Dest. Line Hops Dest. Line Hops Region 1 Region 2 1A ÐÐ 1A ÐÐ 1B 2A 2B 1B 1B 1 1B 1B 1 1C 1 1A 1C 1C 1 1C 2A 1B 2 2 1B 2 1C 2C 2D 2B 1B 3 3 1C 2 2C 1B 3 4 1C 3 2D 1B 4 5 1C 4 3A 4A 5B 5C 3A 1C 3 5A 3B 1C 2 4B 4C 3B 5D 4A 1C 3 5E 4B 1C 4 Region 3Region 4 Region 5 4C 1C 4 5A 1C 4 5B 1C 5 5C 1B 5 5D 1C 6 5E 1C 5 (a) (b) (c) Baûn quyeàn ®2004- Khoa Coâng Ngheä Thoâng Tin Trang 30