Announcement Final 3/18 (Th) 12:00-1:30pm, Rm 381 Close Book One 8.5” by 11” sheet of paper permitted (single side) Cover network layer, data link layer and network security Extra office hour next Tu. 2-4pm, Rm 330Outline Network Layer Routing Principles•Link State Algorithm• Distance Vector Algorithm Hierarchical Routing The Internet (IP) Protocol• IPv4 addressing• Moving a datagram from source to destination• Datagram format• IP fragmentation• ICMP: Internet Control Message Protocol• NAT: Network Address TranslationRouting Algorithm classificationGlobal or decentralized information?Global: all routers have complete topology, link cost info “link state” algorithmsDecentralized: router knows physically-connected neighbors, link costs to neighbors iterative process of computation, exchange of info with neighbors “distance vector” algorithmsStatic or dynamic?Static: routes change slowly over timeDynamic: routes change more quickly periodic update in response to link cost changesLink-State: Dijsktra’sAlgorithm1 Initialization:2 N = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = infinity 7 8 Loop9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N: 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in NDijkstra’s algorithm: exampleStep012345start NAADADEADEBADEBCADEBCFD(B),p(B)2,A2,A2,AD(C),p(C)5,A4,D3,E3,ED(D),p(D)1,AD(E),p(E)infinity2,DD(F),p(F)infinityinfinity4,E4,E4,EAEDCBF2213112535Distance Vector Routing Algorithmiterative: continues until no nodes exchange info.self-terminating: no “signal” to stopasynchronous: nodes need notexchange info/iterate in lock step!distributed: each node communicates onlywith directly-attached neighborsDistance Table data structure each node has its own row for each possible destination column for each directly-attached neighbor to node example: in node X, for dest. Y via neighbor Z:D (Y,Z)Xdistance from X toY, via Z as next hopc(X,Z) + min {D (Y,w)}Zw==Distance 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!Distance table gives routing tableD ()ABCDA1764B148911D5542Ecost to destination viadestinationABCDA,1D,5D,4D,2Outgoing link to use, costdestinationDistance tableRouting tableDistance Vector Algorithm: exampleXZ127YDistance Vector 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 = 3YComparison of LS and DV algorithmsMessage complexity LS: with n nodes, E links, O(nE) msgs sent each  DV: exchange between neighbors only convergence time variesSpeed of Convergence LS: O(n2) algorithm requires O(nE) msgs may have oscillations DV: convergence time varies may be routing loops count-to-infinity problemRobustness: what happens if router malfunctions?LS: node can advertise incorrect linkcost each node computes only its owntableDV: DV node can advertise incorrect pathcost each node’s table used by others • error propagate thru networkThe Internet Network layerforwardingtableHost, router network layer functions:Routing protocols•path selection•RIP, OSPF, BGPIP protocol•addressing conventions•datagram format•packet handling conventionsICMP protocol•error reporting•router “signaling”Transport layer: TCP, UDPLink layerphysical layerNetworklayerIP Addressing: introduction IP address: 32-bit identifier for host, router interfaceinterface:connection between host/router and physical link router’s typically have multiple interfaces host may have multiple interfaces IP addresses associated with each interface223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1 = 11011111 00000001 00000001 00000001223111IP Addressing IP address: network part (high order bits) host part (low order bits) What’s a network ? (from IP address perspective) device interfaces with same network part of IP address can physically reach each other without intervening router223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27network consisting of 3 IP networks(for IP addresses starting with 223, first 24 bits are network address)LANGetting a datagram from source to dest.IP datagram:223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27ABEmiscfieldssourceIP addrdestIP addrdata datagram remains unchanged, as it travels source to destination addr fields of interest hereDest. Net. next router Nhops223.1.1 1223.1.2 223.1.1.4 2223.1.3 223.1.1.4 2forwarding table in AIP datagram formatverlength32 bitsdata (variable length,typically a TCP or UDP segment)16-bit identifierInternetchecksumtime tolive32 bit source IP addressIP protocol versionnumberheader length(bytes)max numberremaining hops(decremented at each router)forfragmentation/reassemblytotal datagramlength (bytes)upper layer protocolto deliver payload tohead.lentype ofservice“type” of data flgsfragmentoffsetupperlayer32 bit destination IP addressOptions (if any)E.g. timestamp,record routetaken, specifylist of routers to visit.how much overhead with TCP? 20 bytes of TCP 20 bytes of IP = 40 bytes + app layer overheadIP Addresses0networkhost10networkhost110network host1110multicast addressABCDclass1.0.0.0 to127.255.255.255128.0.0.0 to191.255.255.255192.0.0.0 to223.255.255.255224.0.0.0 to239.255.255.25532 bitsgiven notion of “network”, let’s re-examine IP addresses:“class-full” addressing:IP addressing: CIDR CIDR: Classless InterDomain Routing network portion of address of arbitrary length address format: a.b.c.d/x, where x is # bits in network portion of address “x” is often expressed as subnet mask11001000 00010111 00010000 00000000networkparthostpart200.23.16.0/23Subnet number Subnet mask200.23.16.0 255.255.254.0Overview Routing in the Internet Intra-AS routing: RIP and OSPF Inter-AS routing: BGP Multicast RoutingSome