10 –ICMP, IPv6, Routing ProtocolsSlide 2ICMP: Internet Control Message Protocol (RFC 792)Traceroute and ICMPIPv6IPv6 Header (Cont)Other Changes from IPv4Transition From IPv4 To IPv6TunnelingInternet2Slide 11Interplay between routing and forwardingGraph abstractionGraph abstraction: costsA Link-State Routing AlgorithmDijsktra’s AlgorithmDijkstra’s algorithm: exampleDijkstra’s algorithm, discussionDistance Vector Algorithm (1)Bellman-Ford example (2)Distance Vector Algorithm (3)Distance vector algorithm (4)Distance Vector Algorithm (5)Example using DVsSlide 25Slide 26Slide 27Comparison of LS and DV algorithmsHierarchical RoutingSlide 30Interconnected ASesInter-AS tasksSlide 33Example: Choosing among multiple ASesIntra-AS RoutingRIP ( Routing Information Protocol)RIP advertisementsRIP: ExampleSlide 39RIP: Link Failure and RecoveryRIP Table processingOSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Hierarchical OSPFSlide 4510 –ICMP, IPv6, Routing ProtocolsNetwork Layer 4-1Network Layer 4-2Chapter 4Network LayerComputer Networking: A Top Down Approach Featuring the Internet, 3rd edition. Jim Kurose, Keith RossAddison-Wesley, July 2004. A note on the use of these ppt slides:We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we’d like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material.Thanks and enjoy! JFK/KWRAll material copyright 1996-2004J.F Kurose and K.W. Ross, All Rights ReservedNetwork Layer 4-3ICMP: Internet Control Message Protocol (RFC 792)used by hosts & routers to communicate network-level informationerror reporting: unreachable host, network, port, protocolecho request/reply (used by ping)network-layer “above” IP:ICMP msgs carried in IP datagramsICMP message: type, code plus first 8 bytes of IP datagram causing errorType 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 headerNetwork Layer 4-4Traceroute and ICMPSource sends series of UDP segments to destFirst has TTL =1Second has TTL=2, etc.Unlikely port numberWhen nth datagram arrives to nth router:Router discards datagramAnd sends to source an ICMP messageMessage includes name of router& IP addressWhen ICMP message arrives, source calculates RTTTraceroute does this 3 timesStopping criterionUDP segment eventually arrives at destination hostDestination returns ICMP “port unreachable” packetWhen source gets this ICMP, stops.Network Layer 4-5IPv6Initial motivation: 32-bit address space soon to be completely allocated. 128-bit addresses Additional motivation:header format helps speed processing/forwardingheader changes to facilitate QoS IPv6 datagram format: fixed-length 40 byte headerNetwork Layer 4-6IPv6 Header (Cont)Traffic class: identify priority among datagrams in flowFlow Label: identify datagrams in same “flow.” (concept of“flow” not well defined).Next header: identify upper layer protocol or if fragmentedNetwork Layer 4-7Other Changes from IPv4Fragmentation: using Next Hdr field, by source node, use Path MTU DiscoveryChecksum: removed entirely to reduce processing time at each hopOptions: allowed, but outside of header, indicated by “Next Header” fieldICMPv6: new version of ICMPadditional message types, e.g. “Packet Too Big”Also includes functionality of IGMP (used in multicasting)Network Layer 4-8Transition From IPv4 To IPv6Not all routers can be upgraded simultaneouslyno “flag days”How will the network operate with mixed IPv4 and IPv6 routers? Tunneling: IPv6 carried as payload in IPv4 datagram among IPv4 routersNetwork Layer 4-9TunnelingABEFIPv6IPv6IPv6IPv6tunnelLogical 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 insideIPv4Network Layer 4-10Internet2Currently assigning /48 addressesIPv6 backbone exists – The Abilene Network in the U.S.http://abilene.internet2.edu/peernetworks/international.html6Bone – IPv6 testbed http://www.thailandipv6.net/Network Layer 4-11Network Layer 4-121230111value in arrivingpacket’s headerrouting algorithmlocal forwarding tableheader valueoutput link01000101011110013221Interplay between routing and forwardingNetwork Layer 4-13uyxwvz2213112535Graph: G = (N,E)N = set of routers = { u, v, w, x, y, z }E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }Graph abstractionRemark: Graph abstraction is useful in other network contextsExample: P2P, where N is set of peers and E is set of TCP connectionsNetwork Layer 4-14Graph abstraction: costsuyxwvz2213112535• c(x,x’) = cost of link (x,x’) - e.g., c(w,z) = 5• cost could always be 1, or inversely related to bandwidth,or inversely related to congestionCost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) Question: What’s the least-cost path between u and z ?Routing algorithm: algorithm that finds least-cost pathNetwork Layer 4-15A Link-State Routing AlgorithmDijkstra’s algorithmnet topology, link costs known to all nodesaccomplished via “link state broadcast” all nodes have same infocomputes least cost paths from one node (‘source”) to all other nodesgives forwarding table for that nodeiterative: after k iterations, know least cost path to k dest.’sNotation:c(x,y): link cost