Announcement Project 2 due Fri. midnight Homework 3 out Due 3/1 Mon. Advertisement for my CS395/495 course next quarter:Computer Network Security: a Measurement-based ApproachDijkstra’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,EAEDCBF2213112535Some slides are in courtesy of J. Kurose and K. RossDistance Vector RoutingD ()ABCDA1764B148911D5542Ecost to destination viadestinationABCDA,1D,5D,4D,2Outgoing link to use, costdestinationDistance tableRouting tableDistance Vector: link cost changesLink cost changes: node detects local link cost change  updates distance table (line 15) if cost change in least cost path, notify neighbors (lines 23,24)XZ1450Y1algorithmterminates“goodnews travelsfast”Distance Vector: link cost changesLink cost changes: good news travels fast  bad news travels slow -“count to infinity” problem!XZ1450Y60algorithmcontinueson!Distance Vector: poisoned reverseIf Z routes through Y to get to X : Z tells Y its (Z’s) distance to X is infinite (so Y won’t route to X via Z) will this completely solve count to infinity problem? XZ1450Y60algorithmterminatesComparison 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 networkOverview 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 TranslationHierarchical Routingscale: with 200 million destinations: can’t store all dest’s in routing tables! routing table exchange would swamp links!administrative autonomy internet = network of networks each network admin may want to control routing in its own networkOur routing study thus far - idealization  all routers identical network “flat”… nottrue in practiceHierarchical Routing aggregate routers into regions, “autonomous systems” (AS) routers in same AS run same routing protocol “intra-AS” routingprotocol routers in different AS can run different intra-AS routing protocol special routers in AS run intra-AS routing protocol with all other routers in ASalsoresponsible for routing to destinations outside AS run inter-AS routingprotocol with other gateway routersgateway routersIntra-AS and Inter-AS routingGateways:•perform inter-AS routing amongst themselves•perform intra-AS routers with other routers in their ASinter-AS, intra-AS routing in gateway A.cnetwork layerlink layerphysical layerabbaaCABdA.aA.cC.bB.acbcIntra-AS and Inter-AS routingHost h2abbaaCABdcA.aA.cC.bB.acbHosth1Intra-AS routingwithin AS AInter-ASroutingbetween A and BIntra-AS routingwithin AS BWe’ll examine specific inter-AS and intra-AS Internet routing protocols shortlyOverview 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 TranslationThe 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)LANIP 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 Classful addressing:  inefficient use of address space, address space exhaustion e.g., class B net allocated enough addresses for 65K hosts, even if only 2K hosts in that network 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 address11001000 00010111 00010000 00000000networkparthostpart200.23.16.0/23IP addresses: how to get one?Q: How does hostget IP address? hard-coded by system admin in a file Wintel: control-panel->network->configuration->tcp/ip->properties UNIX: /etc/rc.config DHCP: Dynamic Host Configuration Protocol: dynamically get address from as server “plug-and-play”(more shortly)IP addresses: how to get one?Q: How does networkget network part of IP addr?A:gets allocated portion of its provider ISP’s address spaceISP'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