Mạng máy tính - Chương 4: Giao thức tầng mạng (network layer)

Chương 4.Giao thức tầng mạng (network layer)Đoàn Thị Thu HàChương 4. Giao thức tầng mạng*1-6/2005Network addr, Broadcast và loopbackĐể ám chỉ một mạng, thay địa chỉ host bằng các bit 0, ví dụ: 192.168.10.0Broadcast:Địa chỉ host thay bằng các bit 1, vd: 192.168.10.255Các gói tin có ip đích dạng broadcast sẽ được gửi cho mọi host trong mạng.Loopback ip: 127.x.x.xcác gói tin được coi như được gửi tới từ nút khác.thường dùng 127.0.0.1Sự khủng hoảng của địa chỉ IPv4Một giải pháp cho địa chỉ IPv4Chương 4. Giao thức tầng mạng*1-6/2005SubnetĐôi khi cần chia nhỏ một mạng thành các mạng nhỏ hơn (subnet)Ví dụ:Chương 4. Giao thức tầng mạng*1-6/2005Subnet maskMột interface trong mạng cần có:IP addressMặt nạ mạng con (subnet mask):Là một số 32 bit bao gồm các bit cao = 1 và các bit thấp = 0. Các bit 1 quy định subnet, các bit 0 quy định địa chỉ host.từ subnet mask có thể xác định ranh giới giữa địa chỉ mạng và địa chỉ của interface (host).Ví dụ: Subnet gồm các host 192.168.10.x, một host có thể có thông số như sau:IP = 192.168.10.1SM = 255.255.255.0 (111111111.11111111.11111111.00000000)Kiểm tra xem hai IP có cùng một subnet không?(IP1 XOR IP2) AND SM = 0?Ranh giớiRanh giớiRanh giớiRanh giớiVD1VD2VD2VD2VD3VD3 VD3Các giải pháp ngắn hạnSự cải tiến địa chỉ IPv4Giải pháp dài hạn: IPv6Chương 4. Giao thức tầng mạng*1-6/2005IP addressing: CIDRClass-full addressing: sự phân lớp cứng nhắc, không còn thích hợp nữa.CIDR (Classless InterDomain Routing):Vị trí ngăn cách giữa net addr và host addr tuỳ ý.addr format: a.b.c.d/x, với x là số lượng bit dành cho net addr.11001000 00010111 00010000 00000000networkparthostpart200.23.16.0/23Dịch địa chỉ mạng: NATChương 4. Giao thức tầng mạng*1-6/2005NAT: Network Address TranslationChương 4. Giao thức tầng mạng*1-6/2005NAT: Network Address Translation10.0.0.110.0.0.210.0.0.310.0.0.4138.76.29.7local network(e.g., home network)10.0.0/24rest ofInternetDatagrams with source or destination in this networkhave 10.0.0/24 address for source, destination (as usual)All datagrams leaving localnetwork have same single source NAT IP address: 138.76.29.7,different source port numbersChương 4. Giao thức tầng mạng*1-6/2005NAT: Network Address TranslationChương 4. Giao thức tầng mạng*1-6/2005NAT: Network Address Translation (cont)Một LAN chỉ sử dụng một IP duy nhất khi giao tiếp với mạng ngoài.Từ đó:Không cần tìm dải IP từ ISP để cấp phát cho các thiết bị mạng trong (máy trạm) vì chỉ dùng 1 IP.Thay đổi IP của máy trạm nội bộ mà không ảnh hưởng tới mạng ngoài.Thay đổi ISP mà không cần thay đổi địa chỉ các thiết bị mạng trong.Các thiết bị mạng trong không “nhìn thấy” được từ mạng ngoài.Chương 4. Giao thức tầng mạng*1-6/2005NAT: Sự thi hànhChương 4. Giao thức tầng mạng*1-6/2005NAT example10.0.0.110.0.0.210.0.0.3S: 10.0.0.1, 3345D: 128.119.40.186, 80110.0.0.4138.76.29.71: host 10.0.0.1 sends datagram to 128.119.40, 80NAT translation tableWAN side addr LAN side addr138.76.29.7, 5001 10.0.0.1, 3345 S: 128.119.40.186, 80 D: 10.0.0.1, 33454S: 138.76.29.7, 5001D: 128.119.40.186, 8022: NAT routerchanges datagramsource addr from10.0.0.1, 3345 to138.76.29.7, 5001,updates tableS: 128.119.40.186, 80 D: 138.76.29.7, 500133: Reply arrives dest. address: 138.76.29.7, 50014: NAT routerchanges datagramdest addr from138.76.29.7, 5001 to 10.0.0.1, 3345 Chương 4. Giao thức tầng mạng*1-6/2005IP addresses: how to get one?Chương 4. Giao thức tầng mạng*1-6/2005IP addresses: how to get one?Chương 4. Giao thức tầng mạng*1-6/2005Đánh địa chỉ IP độngChương 4. Giao thức tầng mạng*1-6/2005IP addresses: how to get one?Chương 4. Giao thức tầng mạng*1-6/2005Phân cấp địa chỉ Internet - ISP“Send me anythingwith addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16”200.23.20.0/23Organization 2......ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23 ... .. . .Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 ICANN: Internet Corporation for Assigned Names and NumbersChương 4. Giao thức tầng mạng*1-6/2005ICMP (Internet Control Message Protocol)Chương 4. Giao thức tầng mạng*1-6/2005ICMP (Internet Control Message Protocol)Giao tiếp ở mức mạng giữa các hosts, routersThông báo lỗi (vd: không tìm được đường đi, không gửi tin được tới host, port).Echo request/reply.ICMP có thể coi là một thành phần của IPVề mặt kiến trúc, ICMP thuộc về tầng ứng dụng.Sử dụng UDP.ICMP msgĐược đóng gói trong IP datagrams/packet.Type + code + 8 bytes of IP datagram.Type Code description0 0 echo reply (ping)3 0 dest. network unreachable3 1 dest host unreachable3 2 dest protocol unreachable3 3 dest port unreachable3 6 dest network unknown3 7 dest host unknown4 0 source quench (congestion control - not used)8 0 echo request (ping)9 0 route advertisement10 0 router discovery11 0 TTL expired12 0 bad IP headerSự vận chuyển thông điệp ICMDSử dụng ICMDPing - A TCP/IP ApplicationChương 4. Giao thức tầng mạng*1-6/2005IPv6 - Giải pháp dài hạnIPv4: sử dụng 32-bit địa chỉ IP sẽ là không đủ???IPv6: Sử dụng 128-bit địa chỉ.Phần tiêu đề (header) cung cấp khả năng xử lý nhanh hơn, chất lượng hơn (QoS).40 bytes header.Không cho phép phân mảnh (fragmentation).ICPM v6.Chương 4. Giao thức tầng mạng*1-6/2005IPv6: datagram formatVer: phiên bản.Priority: thứ tự các gói tin trong cùng flow.Flow: nhãn của luồng mà gói tin thuộc vềCác ứng dụng đòi hỏi chất lượng cao  flow.Ứng dụng không đòi hỏi chất lượng  không được coi là flow.Next header: giao thức tầng trên.Chương 4. Giao thức tầng mạng*1-6/2005IPv6: chuyển đổi IPv4  IPv6Chuyển đổi tất cả các hosts, routers sang sử dụng IPv6: không thể!!!Chuyển đổi dần dần:tồn tại các nút mạng IPv4 và IPv6.IPv6 có khả năng xử lý gói tin IPv4.Tunneling: gói tin IPv6 được coi như phần data (payload) của IPv4 khi đi qua các nút mạng IPv4.Chương 4. Giao thức tầng mạng*1-6/2005TunnelingABEFIPv6IPv6IPv6IPv6tunnelLogical view:Physical view:ABEFIPv6IPv6IPv6IPv6CDIPv4IPv4Flow: XSrc: ADest: FdataFlow: XSrc: ADest: FdataFlow: XSrc: ADest: FdataSrc:BDest: EFlow: XSrc: ADest: FdataSrc:BDest: EA-to-B:IPv6E-to-F:IPv6B-to-C:IPv6 insideIPv4B-to-C:IPv6 insideIPv4Chương 4. Giao thức tầng mạng*1-6/2005Ch4. The Network Layer4.1 - Giới thiệu và chức năng của tầng mạng.4.2 - Network service model (VC and Datagram).4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).4.4 - Giao thức IP (Internet Protocol).4.5 - Giải thuật chọn đường (Routing Algorithms).4.6 - Chọn đường trong mạng Internet.Chương 4. Giao thức tầng mạng*1-6/2005Forwarding & routing1230111value in arrivingpacket’s headerrouting algorithmlocal forwarding tableheader valueoutput link01000101011110013221Chương 4. Giao thức tầng mạng*1-6/2005Network: graph abstractionNetwork = Graph = G(N,E).N = tập hợp các routers = { u, v, w, x, y, z }.E = tập các đường nối giữa các routers. = { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }Trọng số = chi phí (cost): độ trễ, độ nghẽn mạng, cước phíĐường đi tốt = đường đi có “chi phí” thấp nhất.uyxwvz2213112535Chương 4. Giao thức tầng mạng*1-6/2005Routing Algorithm classificationThông tin tập trung hay phân tán?Tập trung:mỗi router phải nắm giữ thông tin toàn bộ mạng (topology, link cost)“link state” algorithmsPhân tán: router nắm được chi phí truyền tin tới các router được nối trực tiếp với mình (hàng xóm) quá trình tính toán mang tính chất lặp đi lặp lại, trao đổi thông tin giữa các routers.“distance vector” algorithmsTĩnh hay động?Tĩnh: đường đi ít thay đổiĐộng: đường đi thay đổi thường xuyêncác thông tin dẫn đường được cập nhật định kỳ.link cost thay đổi.Chương 4. Giao thức tầng mạng*1-6/2005A Link-State Routing AlgorithmGiải thuật Dijkstra:Tất cả các nút mạng có thông tin như nhau về các liên kết của toàn bộ mạng.Cho phép tìm đường đi từ một nút tới tất cả các nút còn lại.Ký hiệu:c(i,j): chi phí phải trả để đi từ i tới j (trực tiếp)D(v): giá trị hiện tại của chi phí phải trả để đi từ đỉnh xuất phát tới đỉnh v.p(v): đỉnh trước đỉnh v trên đường đi ngắn nhấtN: tập hợp đỉnh mà đường đi ngắn nhất đã được xác định.Chương 4. Giao thức tầng mạng*1-6/2005Dijsktra’s Algorithm1 Initialization: 2 N = {A} 3 for all nodes v 4 if v kề với A 5 then D(v) = c(A,v) 6 else D(v) = ∞ 7 8 Loop 9 Tìm w không thuộc N sao cho D(w) nhỏ nhất10 N = N + w 11 for all v kề với w và không thuộc N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 until tất cả nút thuộc N Chương 4. Giao thức tầng mạng*1-6/2005Dijkstra’s algorithm: exampleStep012345 NAADADEADEBADEBCADEBCFD(B),p(B)2,A2,A2,AD(C),p(C)5,A4,D3,E3,ED(D),p(D)1,AD(E),p(E)∞2,DD(F),p(F)∞∞4,E4,E4,EAEDCBF2213112535Chương 4. Giao thức tầng mạng*1-6/2005Distance Vector Routing AlgorithmDistance Table data structure Mỗi nút mạng có một bảng khoảng cách.Hàng dành cho các đích có thể đến được.Cột dành cho các nút có thể đến trực tiếp (hàng xóm)Ví dụ: tại nút X, với đích Y đến qua nút Z:D (Y,Z)Xchi phí cho đường đi (XZY)Z là nút kế tiếp cần đi tớic(X,Z) + min {D (Y,w)}Zw==Chương 4. Giao thức tầng mạng*1-6/2005Distance Table: exampleAEDCB781212D ()ABCDA1764B148911D5542Ecost to destination viadestinationD (C,D)Ec(E,D) + min {D (C,w)}Dw==2+2 = 4D (A,D)Ec(E,D) + min {D (A,w)}Dw==2+3 = 5D (A,B)Ec(E,B) + min {D (A,w)}Bw==8+6 = 14loop!loop!Chương 4. Giao thức tầng mạng*1-6/2005Distance table  routing tableD ()ABCDA1764B148911D5542Ecost to destination viadestination ABCD A,1D,5D,4D,4Outgoing link to use, costdestinationDistance tableRouting tableTổng quan định tuyến Distance vectorChương 4. Giao thức tầng mạng*1-6/2005DV Algorithm: Initialization1 Initialization: 2 for all adjacent nodes v: 3 D (*,v) = infinity /* the * operator means "for all rows" */ 4 D (v,v) = c(X,v) 5 for all destinations, y 6 send min D (y,w) to each neighbor /* w over all X's neighbors */ XXXwAt all nodes, X:Chương 4. Giao thức tầng mạng*1-6/2005DV Algorithm: Loop8 loop 9 wait (until I see a link cost change to neighbor V 10 or until I receive update from neighbor V) 11 12 if (c(X,V) changes by d) 13 /* change cost to all dest's via neighbor v by d */ 14 /* note: d could be positive or negative */ 15 for all destinations y: D (y,V) = D (y,V) + d 16 17 else if (update received from V wrt destination Y) 18 /* shortest path from V to some Y has changed */ 19 /* V has sent a new value for its min DV(Y,w) */ 20 /* call this received new value is "newval" */ 21 for the single destination y: D (Y,V) = c(X,V) + newval 22 23 if we have a new min D (Y,w)for any destination Y 24 send new value of min D (Y,w) to all neighbors 26 forever wXXXXXwwChương 4. Giao thức tầng mạng*1-6/2005DV Algorithm: exampleXZ127YD (Y,Z)Xc(X,Z) + min {D (Y,w)}w==7+1 = 8ZD (Z,Y)Xc(X,Y) + min {D (Z,w)}w==2+1 = 3YChương 4. Giao thức tầng mạng*1-6/2005DV Algorithm: exampleXZ127YChương 4. Giao thức tầng mạng*1-6/2005Một vài so sánh (LS và DV)Link-StateCần nắm được thông tin toàn bộ mạngn nút, E links, nE msgs được gửi mỗi lầnO(n2), nE msgsMỗi nút chỉ tính toán bảng dẫn đường cho riêng mình.Distance VectorChỉ nắm giữ thông tin liên quan tới các nút “hàng xóm”msgs chỉ được gửi cho các nút “hàng xóm”.tốc độ hội tụ có thể khác nhau tuỳ từng tình huống, đôi khi rơi vào trạng thái lặp vô hạn.Thông tin dẫn đường của nút này được sử dụng bởi nút khác.Một nút gặp sự cố có thể gây ảnh hưởng tới các nút khác.Hierarchical Routing-Định tuyến phân cấpChương 4. Giao thức tầng mạng*1-6/2005Hierarchical Routing Dẫn đường theo từng mức mạng, do:Quy mô mạng Internet là rất lớn:Một nút không thể chứa tất cả các bản ghi cho mọi đích!Việc cập nhật bảng dẫn đường tốn kém!Nhu cầu mạng tự trịInternet = network of networksNgười quản trị mạng muốn điều khiển việc dẫn đường (routing) trong mạng họ quản lý.Hierarchical RoutingChương 4. Giao thức tầng mạng*1-6/2005Hierarchical Routing (cont)Phân vùng routers, tạo thành các “autonomous systems” (AS)Routers trong cùng AS sử dụng chung giao thức tìm đường, gọi là “intra-AS” routing protocol.Routers tại các AS khác nhau có thể sử dụng intra-AS routing protocol khác nhau.Gateway router:router đặc biệt trong ASsử dụng intra-AS routing protocol với các routers khác trong ASsử dụng inter-AS routing protocol với các gateway routers khác.Chương 4. Giao thức tầng mạng*1-6/2005Hierarchical Routing (cont)Gateways:perform inter-AS routing amongst themselvesperform intra-AS routers with other routers in their ASinter-AS, intra-AS routing in gateway A.cnetwork layerlink layerphysical layerabbaaCABdA.aA.cC.bB.acbcChương 4. Giao thức tầng mạng*1-6/2005Hierarchical Routing (cont)Host h2abbaaCABdcA.aA.cC.bB.acbHosth1Intra-AS routingwithin AS AInter-AS routingbetween A and BIntra-AS routingwithin AS BCác giao thức định tuyếnCác giao thức định tuyếnChương 4. Giao thức tầng mạng*1-6/2005Ch4. The Network Layer4.1 - Giới thiệu và chức năng của tầng mạng.4.2 - Network service model (VC and Datagram).4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).4.4 - Giao thức IP (Internet Protocol).4.5 - Giải thuật chọn đường (Routing Algorithms).4.6 - Chọn đường trong mạng Internet.Chương 4. Giao thức tầng mạng*1-6/2005Routing in the InternetInternet = nhiều Autonomous Systems (AS) :Stub AS: các công ty nhỏ chỉ bao gồm một kết nối với AS khác.Multihomed AS: công ty lớn: nhiều kết nối tới các AS khác.Transit AS: nhà cung cấp (móc nối các AS lại với nhau).Two-level routing: Intra-AS: người quản trị có quyền lựa chọn giao thức định tuyến bên trong mạngInter-AS: Giao thức định tuyến duy nhất cho inter-AS routing là BGPChương 4. Giao thức tầng mạng*1-6/2005Internet AS Hierarchy- hệ thống phân cấp bậc AS của InternetIntra-AS border (exterior gateway) routersInter-AS interior (gateway) routersChương 4. Giao thức tầng mạng*1-6/2005Intra-AS Routingm - định tuyến bên trong hệ thống tự trịTên gọi khác: Interior Gateway Protocols (IGP)Các giao thức bên trong hệ thống tự trị phổ biến:RIP: Routing Information ProtocolOSPF: Open Shortest Path FirstIGRP: Interior Gateway Routing Protocol (Cisco proprietary)Chương 4. Giao thức tầng mạng*1-6/2005RIP ( Routing Information Protocol)Giao thức định tuyến theo véc tơ khoảng cách: Distance vector algorithmĐược bao gồm trong bản phân phối BSD-UNIX vào năm 1982Thông số khoảng cách: số lượng chặng (hop, tối đa = 15 hops)Routing table được trao đổi 30 giây một lần thông qua RIP response msg (RIP advertisement - quảng cáo)Mỗi quảng cáo: danh sách lên đến 25 mạng đích bên trong hệ thống tự trịv1: RFC 1058; v2: RFC 1723 DCBAuvwxyzdestination hops u 1 v 2 w 2 x 3 y 3 z 2 Chương 4. Giao thức tầng mạng*1-6/2005RIP: ExampleDestination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x -- 1 . . ....wxyzACDBRouting table in DRIP: ExampleRIP – Liên kết hỏng và sự khôi phụcNếu không có liên kết nào được nghe sau 180s – Hàng xóm/ liên kết được xem là chếtCác tuyến đường qua hàng xóm này bị mất hiệu lựcCác quảng cáo mới được gửi đến các hàng xóm khácĐến lượt mình các hàng xóm gửi quảng cáo mới nếu bảng định tuyến bị thay đổiThông tin về liên kết hỏng được lan nhanh ra toàn mạngKỹ thuật poison reverse được sử dụng để ngăn chặn các ping – pong loop(infinite distance = 16 hops)Chương 4. Giao thức tầng mạng*1-6/2005RIP Table processing - tiến trình xây dựng bảng định tuyếnBảng định tuyến được quản lý bới một tiến trình thuộc tầng ứng dụng gọi là route-d (daemon)Các quảng cáo (advertisements) được gửi trong các gói UDP và được lặp lại theo chu kì.Chương 4. Giao thức tầng mạng*1-6/2005RIP Table example Ba mạng thuộc lớp C được kết nối vào (LANs) Router chỉ biết các tuyến đến các LANs được kết nối vào Default router được sử dụng để “go up” Route multicast address - địa chỉ quảng bá: 224.0.0.0 Loopback interface (for debugging – cho mục đích gỡ rối) Destination Gateway Flags Ref Use Interface -------------------- -------------------- ----- ----- ------ --------- 127.0.0.1 127.0.0.1 UH 0 26492 lo0 192.168.2. 192.168.2.5 U 2 13 fa0 193.55.114. 193.55.114.6 U 3 58503 le0 192.168.3. 192.168.3.5 U 2 25 qaa0 224.0.0.0 193.55.114.6 U 3 0 le0 default 193.55.114.129 UG 0 143454 Chương 4. Giao thức tầng mạng*1-6/2005RIP Table exampleChương 4. Giao thức tầng mạng*1-6/2005OSPF (Open Shortest Path First)“open”: publicly available; RFC 2178 Sử dụng giải thuật trạng thái đường liên kết Phổ biến các gói chứa thông tin về trạng thái đường liên kếtMỗi nút đều có bản đồ hình trạng mạng (Topology map)Tính toán tuyến đường sử dụng giải thuật Dijkstra’s algorithmOSPF advertisement carries one entry per neighbor routerCác quảng cáo được phổ biến ra toàn bộ hệ thống tự trị AS (qua địa chỉ multicast)Carried in OSPF messages directly over IP (rather than TCP or UDPChương 4. Giao thức tầng mạng*1-6/2005OSPF “advanced” features (not in RIP)Security: các OSPF msgs đều chứa thông tin chứng thực (authenticated).Multiple same-cost paths: Cho phép truyền tin theo nhiều đường có cùng chi phí với cùng một phiên truyền tin.Diff. cost metrics for diff. TOS: Cho phép nhiều đơn vị đo khác nhau cho từng loại dịch vụ (e.g., satellite link cost set “low” for best effort; high for real time)Integrated unicast and multicast support: Multicast OSPF (MOSPF) uses same topology database as OSPFHierarchical OSPF in large domains.Chương 4. Giao thức tầng mạng*1-6/2005Hierarchical OSPF – OSPF có thứ bậcTwo-level hierarchy: local area, backbone.Chỉ quảng cáo về trạng thái liên kết bên trong vùngMỗi nút có thông tin chi tiết về topology của vùng;Chỉ biết hướng (đường dẫn ngắn nhất) đi đến các mạng thuộc các vùng khác.Area border routers (router biên của vùng): “Tóm tắt” các khoảng cách đến các mạng bên trong vùng của nó, quảng cáo cho các ruoter biên của các vùng khác .Backbone routers: chạy định tuyến OSPF giới hạn trong các backbone.Boundary routers: Kết nối với các hệ thống tự trị khác AS’s.Chương 4. Giao thức tầng mạng*1-6/2005Internet inter-AS routing: BGPBGP (Border Gateway Protocol): RFC 1771; RFC 1772; RFC 1773 AS2 (OSPF intra-AS routing) AS1 (RIP intra-AS routing) BGP AS3 (OSPF intra-AS routing) BGP R1 R2 R3 R4 R5 BGP- Giao thức định tuyến trên InternetBGP- Giao thức định tuyến trên InternetBGP-Kiểm soát ai gởi lưu lượng đếnBGP-Kiểm soát ai gởi lưu lượng đếnHoạt động của BGPCác thông điệp BGPTại sao có sự khác nhau về định tuyến giữa Inter và Intra