CS 6390 Advanced Computer NetworksInternet structure: network of networksInternet Protocol (IP)OutlineForwarding Alternatives for IPForwarding based on Global IP AddressesGranularity of forwarding table infoSlide 8Source routingVirtual Circuit/Tag switchingSlide 11IP AddressesIP AddressingSubnettingIP Address Assignment ProblemSolution 1 - CIDRHierarchical addressingHierarchical addressing: route aggregationHierarchical addressing: more specific routesSolution 2 - NAT (Network Address Translation)NATSlide 22Slide 23Slide 24IPv6IP Fragmentation & ReassemblyIP Fragmentation and ReassemblyICMP: Internet Control Message ProtocolEfficient use of available IP addresses DHCP: Dynamic Host Configuration ProtocolDHCP client-server scenarioSlide 35Slide 36Address prefix matchingPowerPoint PresentationLongest prefix match with TrieSlide 40CS 6390Advanced Computer NetworksAddressing & ForwardingInternet structure: network of networksTier 1 ISPTier 1 ISPTier 1 ISPNAPTier-2 ISPTier-2 ISPTier-2 ISPTier-2 ISPTier-2 ISPlocalISPlocalISPlocalISPlocalISPlocalISPTier 3ISPlocalISPlocalISPlocalISPLocal and tier- 3 ISPs are customers ofhigher tier ISPsconnecting them to rest of InternetDomain = Autonomous system (AS): each AS has an AS number, different from its network addressInternet Protocol (IP)Implements an IP virtual network on top of different types of hardwareHW is hidden by the network layer (except for link MTU)Service Model – (what IP promises to provide)An addressing scheme to uniquely identify each nodeConnectionless (datagram-based) serviceBest-effort delivery No reliability guaranteesPackets may be lost, delayed for long timePackets may be duplicated, delivered out of orderNo bandwidth or delay guaranteesOutlinePacket forwarding IP AddressingPrefix match algorithmsForwarding Alternatives for IPIP forwarding based on global IP addressesPackets carry destination IP addressRouters forward based on destination IP addressSource routingSource node includes the path into the packetVirtual circuit based IP forwarding (i.e. MPLS forwarding – this is below IP)Build virtual circuits to route packets over Can be pre-computed or in run timePackets will carry tags to be forwarded over the circuitsForwarding based on Global IP AddressesEach packet includes a full destination addressRemember that IP addresses are globally uniqueSwitches/routers include a “forwarding” table as destination -> next hopWhat is the granularity of the information in the “forwarding” tablesOne entry per host on the Internet?How many such entries are there globally?One entry per LAN?How big the resulting forwarding table would be?One entry per domain (i.e. organizational network)?How useful is this?Granularity of forwarding table info206.0.64.0/18204.188.0.0/15209.88.232.0/21Internet BackboneISP X owns:Company X : 206.0.68.0/22ISP y : 209.88.237.0/24Organization z1 : 209.88.237.192/26Organization z2 : 209.88.237.0/26Forwarding based on Global IP AddressesAdvantagesStateless Packet size efficiency – better than some others (i.e. source routing)DisadvantagesSwitches/routers need to know how to reach each destinationNeed to have a careful address assignment to avoid large tablesPackets are independently routedWhat would be the problem with that?Source routingSource host puts the entire (or partial) path in the packet headerStrict source routing: the entire path is defined and usedWhat is the main disadvantage of this?Loose source routing: include landmark routers to visit on the pathWhat would be the utility of this?Router processing (in strict source routing)No need for address lookup – why?The first entry in the address list is the next hop routerTake it off from the list and forward the packet to that routerAdvantagesForwarding is fast – no need for address lookupDisadvantagesVariable and long header sizeSource need to keep track of an accurate picture of the topologyVirtual Circuit/Tag switchingConnection setup/teardown for each call before/after data flowEach packet carries VC identifier (not destination host ID)Every router on source-dest path Maintains “state” for each passing connectionRouter processingLookup flow ID – simple table lookupFaster than IP lookup – why?Replace flow ID with outgoing flow IDForward to output portAdvantagesMore efficient lookupMore flexible – can have different paths for each flowCan do resource reservationEasier to implement in hardwareDisadvantagesStill need to route connection setup requestMore complex failure recovery – need to re-establishWill see more when we discuss MPLSOutlinePacket forwarding IP AddressingPrefix match algorithmsIP 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 bitsIP addresses are structured/hierarchical: (network, (subnet,) host) parts The initial addressing scheme: Classful addressing:IP AddressingIP addresses are hierarchical 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 addresscan physically reach each other without intervening router128.10.1.1128.10.1.2128.10.1.3128.10.1.4128.10.2.9128.10.2.2128.10.2.1128.10.3.22128.10.3.31128.10.3.1network consisting of 3 IP networks(For IP addresses starting with 128.10. In each, first 24 bits are network address)LAN or subnetSubnettingAdd another level to address/routing hierarchy: subnetSubnet masks define variable partition of host partSubnets visible only within the siteNetwork number Host numberClass B addressSubnet mask (255.255.255.0)Subnetted address111111111111111111111111 00000000Network number Host IDSubnet IDIP Address Assignment ProblemClassful addressing is bad!In class A & B, address blocks are not utilized wellRunning out of IP addresses (class A & B addresses)In class C, so few addresses (only 256) per networkNot enough for most organizationHaving multiple class C addresses increase the routing table sizesSolution 1 - CIDRAssign multiple class C addresses to a networkAssign them from a consecutive blocks as to enable aggregationNetwork portion of the
View Full Document