Question? Leave a message!




Computer Communication Networks (CCN) Network Layer

Computer Communication Networks (CCN) Network Layer
Computer Communication Networks (CCN) Network Layer 1Chapter Goals • understand principles behind network layer services: – Internetworking concepts – The network layer – IP – routing (path selection) – how a router works 2 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Overview • Internetworking • network layer services • IP • routing principle: path selection • hierarchical routing • Internet routing protocols reliable transfer – intradomain – interdomain • what‟s inside a router 3 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar The Internetworking Problem • Two nodes communicating across a “network of networks”… – How to transport packets through this heterogeneous mass A B Cloud Cloud Cloud 4 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar The Internetworking Problem • Problems: heterogeneity and scaling • Heterogeneity: – How to interconnect a large number of disparate networks (lower layers) – How to support a wide variety of applications (upper layers) • Scaling: – How to support a large number of end nodes and applications in this interconnected network 5 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Heterogeneity: Solutions • Translation (eg: bridges): specify a separate mapping between every pair of protocols (+) No software changes in networks required. () Need to specify N mappings when a new lower layer protocol is added to the list () When many networks, subset = 0 () Mapping may be asymmetric 6 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Heterogeneity: Solutions – Overlay model: Define a new protocol (IP) and map all networks to IP (+) Require only one mapping (IP new protocol) when a new protocol is added (+) Global address space can be created for universal addressibility and scaling () Requires changes in lower networks (eg: protocol type field for IP) 7 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Heterogeneity: Solutions () IP has to be necessarily simple else mapping will be hard. – Even in its current form mapping IP to ATM has proven to be really hard. – Basis for “besteffort” forwarding () Protocol mapping infrastructure needed: address hierarchy, address resolution, fragmentation 8 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar The Internet Network layer Host, router network layer functions: Transport layer: TCP, UDP IP protocol Routing protocols •addressing conventions •path selection •datagram format •RIP, OSPF, BGP Network •packet handling conventions layer routing ICMP protocol table •error reporting •router “signaling” Link layer physical layer 9 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Addressing: introduction • IP address: 32bit 223.1.1.1 identifier for host, 223.1.2.1 router interface 223.1.1.2 223.1.2.9 223.1.1.4 • interface: connection between host, router 223.1.2.2 223.1.3.27 223.1.1.3 and physical link – router‟s typically have multiple interfaces 223.1.3.2 223.1.3.1 – host may have multiple interfaces – IP addresses associated with 223.1.1.1 = 11011111 00000001 00000001 00000001 interface, not host, 223 1 1 1 router 10 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Addressing 1 • IP address: 223.1.1.1 – network part (high 223.1.2.1 order bits) 223.1.1.2 223.1.1.4 223.1.2.9 – host part (low order bits) 223.1.2.2 223.1.1.3 223.1.3.27 • What’s a network (from IP address LAN perspective) 223.1.3.2 223.1.3.1 – device interfaces with same network part of IP address network consisting of 3 IP networks – can physically reach (for IP addresses starting with 223, each other without first 24 bits are network address) intervening router 11 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Addressing 2 How to find the 223.1.1.2 networks 223.1.1.1 223.1.1.4 • Detach each 223.1.1.3 interface from 223.1.7.0 223.1.9.2 router, host • create “islands of 223.1.9.1 223.1.7.1 isolated 223.1.8.1 223.1.8.0 networks 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 Interconnected system consisting of six networks 12 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Addresses given notion of “network”, let‟s reexamine IP addresses: “classfull” addressing: class 1.0.0.0 to A network 0 host 127.255.255.255 128.0.0.0 to B network 10 host 191.255.255.255 192.0.0.0 to C network host 110 223.255.255.255 224.0.0.0 to multicast address D 1110 239.255.255.255 32 bits 13 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Some Special IP Addresses • All0s  This computer • All1s  All hosts on this net (limited broadcast: don’t forward out of this net) • All0 host suffix Network Address („0’ means „this’) • All1 host suffix All hosts on the destination net (directed broadcast). • 127...  Loopback through IP layer 14 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP addressing: CIDR 1 • 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 15 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP addressing: CIDR 2 • 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 host network part part 11001000 00010111 00010000 00000000 200.23.16.0/23 16 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Subnet Addressing – External routers need to store entries only for the “network ID” – Internal routers hosts use subnet mask to identify “subnet ID” and route packets between “subnets” within the “network”. – Eg: Mask: 255.255.255.0 = subnet ID = 8 bits with upto 62 hosts/subnet 17 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Subnet Addressing (Continued) – Route table lookup: • IF ((Maski Destination Addr) = = Destinationi) Forward to NextHopi – Subnet mask can end on any bit. – Mask must have contiguous 1s followed by contiguous zeros. Routers do not support other types of masks. 18 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Route Table Lookup: Example 30.0.0.7 40.0.0.8 128.1.0.9 40.0.0.0 30.0.0.0 128.1.0.0 192.4.0.0 40.0.0.7 128.1.0.8 192.4.10.9 Destination Mask Next Hop 30.0.0.0 255.0.0.0 40.0.0.7 40.0.0.0 255.0.0.0 Deliver direct 128.1.0.0 255.255.0.0 Deliver direct 192.4.10.0 255.255.255.0 128.1.0.9 19 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP addresses: how to get one Hosts (host portion): • hardcoded by system admin in a file • DHCP: Dynamic Host Configuration Protocol: dynamically get address: “plugand play” – host broadcasts “DHCP discover” msg – DHCP server responds with “DHCP offer” msg – host requests IP address: “DHCP request” msg – DHCP server sends address: “DHCP ack” msg 20 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP addresses: how to get one Network (network portion): • get allocated portion of ISP‟s address space: ISP'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 00000000 200.23.30.0/23 21 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Hierarchical addressing: route aggregation Hierarchical addressing allows efficient advertisement of routing information: Organization 0 200.23.16.0/23 Organization 1 “Send me anything 200.23.18.0/23 with addresses beginning Organization 2 200.23.16.0/20” . 200.23.20.0/23 FlyByNightISP . . . Internet . Organization 7 . 200.23.30.0/23 “Send me anything ISPsRUs with addresses beginning 199.31.0.0/16” 22 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Hierarchical addressing: more specific routes ISPsRUs has a more specific route to Organization 1 Organization 0 200.23.16.0/23 “Send me anything with addresses beginning Organization 2 200.23.16.0/20” . FlyByNightISP 200.23.20.0/23 . . . Internet . Organization 7 . 200.23.30.0/23 “Send me anything ISPsRUs with addresses beginning 199.31.0.0/16 Organization 1 or 200.23.18.0/23” 200.23.18.0/23 23 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP addressing: the last word... Q: How does an ISP get block of addresses A: ICANN: Internet Corporation for Assigned Names and Numbers – allocates addresses – manages DNS – assigns domain names, resolves disputes 24 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Getting a datagram from source to dest. 1 routing table in A Dest. Net. next router Nhops 223.1.1 1 223.1.2 223.1.1.4 2 IP datagram: 223.1.3 223.1.1.4 2 source misc dest data IP addr fields IP addr A 223.1.1.1 datagram remains 223.1.2.1 223.1.1.2 unchanged, as it travels 223.1.2.9 223.1.1.4 source to destination B addr fields of interest here 223.1.2.2 223.1.3.27 E 223.1.1.3 223.1.3.2 223.1.3.1 25 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Getting a datagram from source to dest. 2 misc Dest. Net. next router Nhops data 223.1.1.1 223.1.1.3 fields 223.1.1 1 223.1.2 223.1.1.4 2 Starting at A, given IP 223.1.3 223.1.1.4 2 datagram addressed to B: look up net. address of B A 223.1.1.1 find B is on same net. as A 223.1.2.1 link layer will send datagram 223.1.1.2 directly to B inside linklayer 223.1.2.9 223.1.1.4 frame B B and A are directly 223.1.2.2 E 223.1.3.27 223.1.1.3 connected 223.1.3.2 223.1.3.1 26 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Getting a datagram from source to dest. 3 misc Dest. Net. next router Nhops 223.1.1.1 223.1.2.2 data fields 223.1.1 1 223.1.2 223.1.1.4 2 Starting at A, dest. E: 223.1.3 223.1.1.4 2 look up network address of E E on different network A 223.1.1.1 A, E not directly 223.1.2.1 attached 223.1.1.2 routing table: next hop router to 223.1.2.9 223.1.1.4 E is 223.1.1.4 B link layer sends datagram to 223.1.2.2 E 223.1.3.27 223.1.1.3 router 223.1.1.4 inside linklayer frame 223.1.3.2 223.1.3.1 datagram arrives at 223.1.1.4 continued….. 27 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Getting a datagram from source to dest. – 4 Dest. next misc network router Nhops interface 223.1.1.1 223.1.2.2 data fields 223.1.1 1 223.1.1.4 223.1.2 1 223.1.2.9 Arriving at 223.1.4, 223.1.3 1 223.1.3.27 destined for 223.1.2.2 look up network address of E A 223.1.1.1 E on same network as router‟s 223.1.2.1 interface 223.1.2.9 223.1.1.2 router, E directly 223.1.2.9 223.1.1.4 B attached 223.1.2.2 link layer sends datagram to E 223.1.3.27 223.1.1.3 223.1.2.2 inside linklayer frame 223.1.3.2 223.1.3.1 via interface 223.1.2.9 datagram arrives at 223.1.2.2 (hooray) 28 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Features • Connectionless service • Addressing • Data forwarding • Fragmentation and reassembly • Supports variable size datagrams • Besteffort delivery • Provides only “Send” and “Delivery” services. Error and control messages generated by Internet Control Message Protocol (ICMP) 29 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar What IP does NOT provide • Endtoend data reliability flow control (done by TCP or application layer protocols) • Sequencing of packets (like TCP) • Error detection in payload (TCP, UDP or other transport layers) • Error reporting (ICMP) 30 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar What IP does NOT provide (Continued) • Setting up route tables (RIP, OSPF, BGP etc) • Connection setup (it is connectionless) • Address/Name resolution (ARP, RARP, DNS) • Configuration (BOOTP, DHCP) • Multicast (IGMP, MBONE) 31 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP datagram format IP protocol version 32 bits total datagram number length (bytes) header length type of head. ver length (bytes) len service for fragment “type” of data fragmentation/ 16bit identifier flgs offset reassembly max number upper time to Internet remaining hops live layer checksum (decremented at 32 bit source IP address each router) 32 bit destination IP address upper layer protocol to deliver payload to E.g. timestamp, Options (if any) record route data taken, pecify (variable length, list of routers typically a TCP to visit. or UDP segment) 32 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Fragmentation Reassembly 1 • network links have MTU (max.transfer size) largest possible linklevel frame. fragmentation: – different link types, in: one large datagram out: 3 smaller datagrams different MTUs • large IP datagram divided (“fragmented”) within net – one datagram becomes reassembly several datagrams – “reassembled” only at final destination – IP header bits used to identify, order related fragments 33 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar IP Fragmentation and Reassembly 2 length ID fragflag offset =4000 =x =0 =0 One large datagram becomes several smaller datagrams length ID fragflag offset =1500 =x =1 =0 length ID fragflag offset =1500 =x =1 =1480 length ID fragflag offset =1040 =x =0 =2960 34 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar Summary • Internet architectural principles • IP addressing and header • Fragmentation/Reassembly, Path MTU discovery 35 Rensselaer Polytechnic Institute © Shivkumar Kalvanaraman © Biplab Sikdar