ECE544: Communication Networks-II Spring 2009Today’s LectureIP BasicsIP InternetService ModelPacket FormatFragmentation and ReassemblyExampleGlobal AddressesDatagram ForwardingAddress TranslationARP DetailsATM ARPDynamic Host Control Protocol (DHCP)Slide 15Internet Control Message Protocol (ICMP)Routing BasicsRouting ProblemTwo main approachesDistance Vector ProtocolsDistance VectorDistributed Bellman-FordExample - initial distancesE receives D’s routesE updates cost to CA receives B’s routesA updates cost to CA receives E’s routesA updates cost to C and DFinal distancesFinal distances after link failureView from a nodeDistance Vector ExampleDV Example (cont.)Slide 35DV Example – after link R2-R3 breaksSlide 37Slide 38The bouncing effectC sends routes to BB updates distance to AB sends routes to CSlide 43How are these loops caused?Avoiding the Bouncing EffectDistance Vector in PracticeLink State RoutingLink State Routing: Building blocksLink state packets (LSPs)Reliable floodingSPT algorithm (Dijkstra)Link State AlgorithmImplementation of Dijkstra’s Algorithm (Method 1)Dijkstra/OSPF Method 1Slide 55Slide 56Dijkstra SPT Method 2Slide 58Slide 59Slide 60Slide 61Slide 62Link State in PracticeOSPF Link-State AdvertisementLink State CharacteristicsOSPF Sequencing and AgingProblem: Router FailureOne solution: LSP AgingLink MetricsRouting metric v.s. link utilizationDistance Vector vs. Link StateLayer 2 vs. Layer 3Today’s HomeworkECE544: Communication Networks-II Spring 2009H. LiuLecture 4Includes teaching materials from D. Raychaudhuri, L. PetersonToday’s Lecture•IP basics•Routing principles–distance vector (RIP)–link state (OSPF)IP Basics Best Effort Service ModelGlobal Addressing SchemeARP & DHCPIP Internet •A network of networks–Heterogeneity: inter-connect a collection of physical networks with various technologies (Ethernet, token-ring, …)–Scalability: Capable to grow to many nodes (size doubled every year)•Hierarchical addressing and routing•Protocol StackR2R1H4H5H3H2H1Network 2 (Ethernet)Network 1 (Ethernet)H6Network 3 (FDDI)Network 4(point-to-point)H7 R3 H8R1ETHFDDIIPIPETHTCPR2FDDIPPPIPR3PPPETHIPH1IPETHTCPH8Appl.Appl.Service Model•Connectionless (datagram-based)•Best-effort delivery (unreliable service)–packets are lost–packets are delivered out of order–duplicate copies of a packet are delivered–packets can be delayed for a long time•Keep router simplePacket Format•Packet formatVersion HLenTOS LengthIdent Flags OffsetTTL Protocol ChecksumSourceAddrDestinationAddrOptions (variable)Pad(variable)0 4 8 16 19 31Data•HLen: the length of header in 32-bit word•Length: the length of the datagram, including header in bytes•TOS: or Differentiated Services (DS) field, 2-bit Explicit Congestion Notification (ECN) + 6-bit Differentiated Services Code Point (DSCP)•Ident: identifier set by source, unique over some reasonable time period.•Checksum: only for headerFragmentation and Reassembly•Each network has some Maximum Transmission Unit (MTU)•Strategy–fragment when necessary (MTU < Datagram) by router–try to avoid fragmentation at source host–re-fragmentation is possible –fragments are self-contained datagrams–delay reassembly until destination host–do not recover from lost fragments •If one fragment is lost, the destination discards other fragments of this datagram–For ATM, frame is CS-PDUExample H1 R1 R2 R3 H8ETH IP (1400) FDDI IP (1400) PPP IP (512)PPP IP (376)PPP IP (512)ETH IP (512)ETH IP (376)ETH IP (512)Ident = x Offset = 0Start of header0Rest of header1400 data bytesIdent = x Offset = 0Start of header1Rest of header512 data bytesIdent = x Offset = 64Start of header1Rest of header512 data bytesIdent = x Offset = 128Start of header0Rest of header376 data bytes•Flags:–Reserved; must be zero. –Don't Fragment (DF): drop if datagram > MTU–More Fragments (MF): set to 1 if fragmented (except the last fragment) •Offset: measured in units of eight-byte blocks–fragmentation always happens on 8-byte boundaries–16-bit length (max 65,535)/8=>max possible offset value fit in 13 bit offset filedGlobal Addresses•Properties–globally unique–hierarchical: network + host•Private addresses–10.0.0.0 - 10.255.255.255–172.16.0.0 - 172.31.255.255–192.168.0.0 - 192.168.255.255 •Multicast addresses (class D): •224.0.0.0 to 239.255.255.255•Router:–Each interface has its own address•Assigned by The Internet Assigned Numbers Authority (IANA) Network Host7 240A:Network Host14 161 0B:Network Host21 81 1 0C:Datagram Forwarding •Strategy–every datagram contains destination’s address–if directly connected to destination network, then forward to node•Compare the network part of the dest. address–if not directly connected to destination network, then forward to some router–forwarding table maps network number into next hop–each host has a default router–each router maintains a forwarding table•Example (R2) Network Number Next Hop1 R32 R13 Interface 14 Interface 0Address Translation •Map IP addresses into physical hardware addresses (e.g. Ethernet MAC address)–destination host–next hop router•Techniques–encode physical address in host part of IP address–table-based•Address Resolution Protocol (ARP)–table of IP to MAC address bindings–broadcast ARP query if IP address not in table–target machine responds with its physical address–table entries are discarded if not refreshedARP Details •Format–HardwareType: type of physical network (e.g., Ethernet)–ProtocolType: type of higher layer protocol (e.g., IP)–HLEN & PLEN: length of physical and protocol addresses–Operation: request or response –Source/Target-Physical/Protocol addresses•Notes–table entries timeout in about 10 minutes–ARP request contains the source’s IP address and MAC address•Target updates its ARP table with source’s IP-MAC address mapping •Refresh the table entry for source’s IP-MAC address mapping if a node already has an entry for the source•Otherwise, do not refresh the table entriesTargetHardwareAddr (bytes 2 – 5)TargetProtocolAddr (bytes 0 – 3)SourceProtocolAddr (bytes 2 – 3)Hardware type = 1 ProtocolT ype = 0x0800SourceHardwareAddr (bytes 4 – 5)TargetHardwareAddr (bytes 0 – 1)SourceProtocolAddr (bytes 0 – 1)HLen = 48 PLen = 32 OperationSourceHardwareAddr (bytes 0 – 3)0 8 16 31ATM ARPH2RH1LIS 10LIS 12ATM