Understanding Network Addresses and IP Addressing Schemes
Exploring the concept of network addresses, IP address allocation, prefixes, and packet forwarding in computer networks. Addressing requirements, the simplest solutions, IPv4 addressing, Ethernet frames, and hierarchical IP addressing schemes are covered in detail.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computer Networks Architecture and Protocols Network Addresses Departamento de Inform tica da FCT/UNL 1
Lecture Outline What is in a network address Implications of addressing schemes IP Address allocation IP address prefixes Longest-prefix matching IP address prefixes assignment and implications Growth in the number of prefixes over time Packet forwarding Forwarding tables Longest-prefix match forwarding 2
Network Addresses To send packets to an interface, we need a way of naming it The simplest way is to assign each interface a number, a different one We call these numbers network addresses 3
Addresses Requirements In a domain, make each address different Avoid management complications (e.g. manual assignment) Avoid generation complications to guarantee uniqueness (e. g. central authorities) Avoid to complicate the switching / forwarding process (e.g. matching addresses against entries in the switch / router tables) Avoid switching / forwarding table explosion 4
The Simplest Solution Generate addresses randomly with many bits Autonomous / decentralized management of addresses But requires a way of guaranteeing uniqueness (e.g. 128, 256, bits) Forwarding table size is O (# computers) Cannot be used in most situations (size of the address, table size, cost of table maintenance, ) 5
IP Address (IPv4) A unique 32-bit number Identifies an interface (on a host, on a router, ) Represented in dotted-quad notation 6
Ethernet frames and IP packets Origin IP address (4 bytes) Destination IP addresses (4 bytes) IP Payload Several fields of the IP header (12 bytes) Origin Ethernet address (6 bytes) Destination Ethernet address (6 bytes) crc (4 bytes) Ethernet Payload (from 46 to 1500 bytes) 7 Type (IEEE 802.3) or size (2 bytes) Preamble (8 bytes)
Hierarchical Addressing: IP Address Prefixes Divided into network & host portions (left and right) 193.136.126.0/24 is a 24-bit prefix with 28addresses 8
Address Allocation How to assign IP address prefixes to organizations ? In the old days, only IANA (Internet Addresses and Numbers Assignment Authority) assigned IP network numbers to organizations, building a flat space of prefixes Today, prefixes are assigned hierarchically through the RIR (Regional Internet Registries) 9
Examples FCCN has several /16 blocks aggregated FCCN has 193.136.0.0/15 193.136.0.0/16 and 193.137.0.0/16 FCT/UNL has a /21 prefix FCT/UNL has 193.136.120.0/21 193.136.0.0/24 to 193.136.0.7/24 10
Figuring Out Who Owns an Address Address registries Public record of address allocations Internet Service Providers (ISPs) should update when giving addresses to customers However, records are notoriously out-of-date Ways to query UNIX: whois h whois.ripe.net 193.136.122.0 http://www.ripe.net/whois/ http://www.geektools.com/whois.php 11
Scalability Through Hierarchy Hierarchical addressing Critical for scalable system Don t require everyone to know everyone else Reduces amount of updating when something changes Non-uniform hierarchy Useful for heterogeneous networks of different sizes 12
Scalability: Address Aggregation The rest of the Internet Send me any address matching: 193.136.0.0/15 193.136.0.0/15 FCCN Send me any address matching: 193.136.120.0/21 193.137.100.0/21 193.136.128.0/21 193.136.120.0/21 FCT/UNL Routers in the rest of the Internet just need to know how to reach 193.136.0.0/15. The provider can direct the IP packets to the appropriate customer. Question: what-if customer wants to change provider? 14
Aggregation is not Always Possible The rest of the Internet Send me any address matching: 193.136.0.0/15 or 193.136.120.0/21 (why ?) Send me any address matching: 100.100.0.0/16 or 193.136.120.0/21 100.100.0.0/16 193.136.0.0/15 FCCN Send me any address matching: 193.136.120.0/21 Send me any address matching: 193.136.120.0/21 193.137.100.0/21 193.136.128.0/21 193.136.120.0/21 FCT/UNL Multi-homed customer with 193.136.120.0/21 has two providers. Other parts of the Internet need to know how to reach these destinations through both providers. The customer doesn t control the path took by incoming (ingress) packets. 15
Longest-Prefix Matching Tabela de encaminhamento O endere o IP de destino do pacote est contido em todos estes prefixos . 193.136.126.34 193.136.118.0/16 193.136.119.0/16 193.136.0.0/15 193.136.120.0/21 193.136.126.0/24 193.136.128.0/15 193.136.136.0/15 193.136.144.0/14 193.136.160.0/15 100 120 60 10 110 150 50 10 10 interface 1 interface 4 interface 5 interface 1 interface 10 interface 3 interface 10 interface 2 interface 1 Endere o IP de destino do pacote Prefixo escolhido pela regra longest prefix is the best . 16
Load balancing with Backup The rest of the Internet Send me any address matching: 100.100.0.0/16 or 193.136.120.0/21 or 193.136.124.4/22 Send me any address matching: 193.136.0.0/15 or 193.136.120.0/22 100.100.0.0/16 193.136.0.0/15 FCCN Send me any address matching: 193.136.120.0/21 or 193.136.120.0/22 Send me any address matching: 193.136.120.0/21 or 193.136.124.4/22 193.137.100.0/21 193.136.128.0/21 193.136.120.0/21 FCT/UNL Multi-homed customer with 193.136.120.0/21 has two providers and load balances ingress packets across the two links. If any of them fails, the other is used as backup. 17
Hard Policy Questions How much address space per geographic region? Equal amount per country? Proportional to the population? What about addresses already allocated? Address space portability? Keep your address block when you change providers? Pro: avoid having to renumber your equipment Con: reduces the effectiveness of address aggregation Keeping the address registries up to date? What about mergers and acquisitions? Delegation of address blocks to customers? How to prevent DFZ (Default Free Zone) routing table explosion? More than 600.000 entries and counting 18
IP Routing Algorithm if ( ! packet.checksum_ok() || packet.getTTL() 1 == 0 ) { packet.process_error(); return // ignore packet , ... } if ( packet.header_length() > 5 ) { packet.process_options(); return } // packet has no options route = routing_table.getLongestPrefixMatch(packet.getDestAddress() if ( route == null ) packet.process_error() // don t know how to route else if ( route.getType() == local ) packet.deliver_locally() else if ( route.getType() == direct ) packet.deliver_directly() else if ( route.getType() == indirect ) { d = route.getIndirectRouter() route2 = routing_table.get_longest_prefix_match (d) if ( route2 != null ) packet.deliver_directly_via(d) else routing_table.error() } 19
Simplest Algorithm is Too Slow Scan the forwarding table one entry at a time See if the destination matches the entry If so, check the size of the mask for the prefix Keep track of the entry with longest-matching prefix Overhead is linear in size of the forwarding table Today, that means 600,000 entries! And, the router may have just a few nanoseconds before the next packet is arriving Need greater efficiency to keep up with line rate Better algorithms Hardware implementations 20
Patricia (Radix, Trie) Tree Store the prefixes as a tree One bit for each level of the tree Some nodes correspond to valid prefixes ... which have next-hop interfaces in a table When a packet arrives Traverse the tree based on the destination address Stop upon reaching the longest matching prefix 0 1 00 10 11 100 101 00* 11* 21
Where do Forwarding Tables Come From? Routers have forwarding tables Map prefix to outgoing link(s) Entries can be statically configured E.g., ip route 12.34.158.0/24 to Serial0/0.1 But, this doesn t adapt To failures To new equipment To the need to balance load That is where other technologies come in Routing protocols, DHCP and ARP 22
IP Prefixes and Routers Interfaces Each IP router interface is directly connected to a group of other interfaces Each of these groups of devices is addressed by a different IP prefix At this level, an IP prefix is associated with a set of interfaces that can communicate directly A point to point link has an IP prefix with only two interfaces A broadcast link has an IP prefix with many (> 2) different interfaces directly connected In a switched network, each VLAN is a complex subnetwork with lots of different interfaces directly connected that have an IP prefix of their own Each link has its own specific IP prefix 23
A Point-to-Point IP Prefix 80.80.1.0/24 80.80.2.0/24 80.80.4.0/24 80.80.1.1 80.80.1.254 80.80.2.254 80.80.2.1 80.80.4.254 80.80.4.253 80.80.1.2 80.80.1.3 80.80.3.254 80.80.2.2 80.80.3.2 80.80.3.1 80.80.3.0/24 24
Conclusion Addressing schemes are complex because they have lots of implications At the management level At the routing level With implications on scale and flexibility Mac addresses are flat and have been introduced to address a simple problem IP addresses have been introduced to address the needs of the Internet They are hierarchical and can scale However, address portability, network configuration, commercial issues, and routing optimization problems are also bringing scalability problems 25
