CS计算机代考程序代写 flex DHCP algorithm Slide 1

Slide 1

1

CMPT 471
Networking II

Addressing
assigning networks and sub-networks
© Janice Regan, 2012-2018

© Janice Regan, 2012-2018
2
Internet addresses: IPv4
32 bit global internet (IP) address is used to uniquely identify a particular network interface connected to a particular host as a destination for communication
Globally applicable and globally unique
Expressed a series of 32 binary digits
10000000 00001011 00000011 00011111
Also expressed in dotted decimal notation
Binary digits are separated into four groups of eight digits
Each group of 8 digits are translated to a decimal number
The decimal number are separated by dots (periods)
Example address above becomes 128.11.3.31

© Janice Regan, 2012-2018
3
Structure of an IP address
Each IP address is split into two parts (netid, hostid) to identify the host and the network to which the host is connected
The netid (network address or prefix) identifies the network to which the host belongs.
The number of bits dedicated to the netid will determine the number of possible networks.
The hostid identifies the particular host (network interface for a multi homed host)
The number of bits dedicated to the hostid will determine the possible number of hosts on the network

© Janice Regan, 2012-2018
4
Allocating addresses to networks
Have considered some addresses reserved for particular purposes.
How are the remainder of the addresses in the IP address space allocated to networks?
Originally, the IPv4 protocol originally separated addresses into different classes, allowing for particular numbers of networks in each class. The addressing was know as classful addressing
Later, when the number of networks began to exceed the available network addresses an extended solution was needed. The solutions implemented were
Long term solution: new version of the IP protocol IPv6
Short term solution classless addressing or CIDR

© Janice Regan, 2012-2018
5
Classful addressing

© Janice Regan, 2012-2018
6
IP Addresses – Class A

First digit a 0
Small netid (7 bits) ⇨ 27-5 available networks
Large hostid (24 bits) ⇨ 224-2 hosts per network
Unicast address range, 0.0.0.0 to 127.255.255.255 does not include the following reserved addresses
0.0.0.0/8 ‘this’ network
10.0.0.0/8 private internets
14.0.0.0/8 Public data networks
24.0.0.0/8 IP over cable
127.0.0.0/8 loopback
Few networks each with many hosts.

© Janice Regan, 2012-2018
7
IP Addresses – Class B

First digits 10
medium netid (14 bits) ⇨ 214 available networks
medium hostid (16 bits) ⇨ 216-2 available hosts/network
Unicast address range 128.0.0.0 to 191.255.255.255 does not include the following reserved addresses
169.254.0.0/16 ‘local’ autoconfiguration
(for example when no DHCP server found)
172.16.0.0/12 reserved for private internets
moderate number of networks and hosts

© Janice Regan, 2012-2018
8
IP Addresses – Class C

First digits 110
large netid (21 bits) ⇨ 221 available networks
small hostid (8 bits) ⇨ 28-2 available hosts/network
Address range 192.0.0.0 to 223.255.255 does not include the following reserved addresses
192.168.0.0 – 192.168.255.0 reserved for private internets.
Large number of networks each with a small number of hosts (<256) © Janice Regan, 2012-2018 9 Classful Addressing: forwarding The original routing algorithms depended on each network having a network address that was either a Class A, B, C, D, or E address. Each network would have one entry in the routing table of each router. The entry would indicate the network address of the destination network and the interface on the present router through which the packet should be sent to reach that destination network. The network portion of the incoming packets destination address would be compared to all entries of the correct class in the routing table to determine the interface through which the packet should be forwarded © Janice Regan, 2012-2018 10 Problems with classful Large networks were difficult to administer and needed some internal structure to simplify their administration. (solution sub-netting) With the explosive growth of the Internet Class B networks were in short supply. Many organizations wanted more addresses than a class C address could supply but not as many as a class B address would give. Giving multiple class C addresses was one solution but it had its own problems, increasing the load on the network due to routing (one table entry for each class C network) Short term solution CIDR, long term solution IPv6 Subnetting To manage the addresses within a large network, the network manager will likely divide the network into smaller sub-networks For classful addressing this consisted of dividing a class B network into networks the size of a class C network (or an A into B’s and C’s). Then using internal routing between sub networks For CIDR, there is more flexibility in subnet size © Janice Regan, 2012-2018 11 © Janice Regan, 2012-2018 12 Classless InterDomain Routing CIDR (also called supernetting) Permits allocation of the remaining IP addresses in blocks more closely matched to user needs Makes routing algorithms more complex (cannot sort by class to simplify forwarding) Addresses are allocated based on a base address and a subnet mask or prefix, for 202.25.8.0/22 202.25.8.0 is the first allocated address or base address. The base address is the network address The netmask is 11111111 11111111 11111100 00000000, 22 1’s followed by 0’s to make up the rest of the 32 bits © Janice Regan, 2012-2018 13 CIDR: Using masks, prefixes Consider a 1024 address block, a 2048 address block, and a 4096 address block of addresses. These addresses are to be allocated in what would have been the class C portion of the address space. The allocated addresses are 202.35.8.0 to 202.35.11.255 (202.35.8.0/22) 1024 addresses with netmask 255.255.252.0 (22 1 bits) 202.35.24.0 to 202.35.31.255 (202.35.16.0/21) 2048 addresses with netmask 255.255.248.0 (21 1 bits) 202.35.32.0 to 202.35.47.255 (202.35.32.0/20) 4096 addresses with netmask 255.255.240.0 (20 1 bits) 13 © Janice Regan, 2012-2018 14 CIDR addressing 1024 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 2048 0 8 16 24 32 40 48 4096 0 16 32 48 Blue bars show all possible addresses, we will group consecutive addresses to make networks. The numbers on axes show particular addresses for reference: 16 means 202.35.16.0, 28 means 202.35.28.0 … The red portions show the networks listed on the previous slide. 202.35.8.0/22 is shown in red in the top illustration, contains 2(32-22) addresses starting with 202.35.8.0 and ending with 202.35.11.255 2 14 © Janice Regan, 2012-2018 15 CIDR: Assigning networks If K host addresses are desired and (2N-1)-2 < K < (2N)-2 the netmask will have 32-N bits The base address will fall on a 2N boundary, that is the binary form of the base address will be an even multiple of 2N. The base address will have all zero bits for the bits that are zero in the netmask. If an address within the allocated range is ANDed with the netmask the result will be the base address of the allocated range © Janice Regan, 2012-2018 16 CIDR: Routing A router will have a list of networks to which it connects A destination address will be ANDed with the netmask for each network, and the result will be compared with the base address of the network If the ANDed destination address gives the network base address the router knows it has found a candidate for the correct network to forward the package to. The candidate with the longest match is chosen In order to reduce the size of router tables aggregation is used. Networks in a given region/location are aggregated into a larger network for the purpose of forwarding. © Janice Regan, 2012-2018 17 A sample routing table Destination Gateway Genmask Metric Iface 196.74.0.0 * 255.255.240.0 0 Eth0 196.74.16.0 * 255.255.248.0 0 Eth1 196.74.24.0 * 255.255.248.0 0 Eth2 196.74.32.0 * 255.255.252.0 0 Eth3 196.74.36.0 * 255.255.252.0 0 Eth4 196.74.48.0 * 255.255.240.0 0 Eth5 © Janice Regan, 2012-2018 18 CIDR: Using net masks Given an address in one of these ranges, ANDing the address with the appropriate netmask should give the base address of that network For example test to see if 196.74.35.57 is in the fourth block or addresses 196.74.32.0/22 11000100 01001010 00100011 00111001 addresss 11111111 11111111 11111100 00000000 netmask 11000100 01001010 00100000 00000000 address AND netmask 196.74.32.0 the base address of the fourth block, therefore, the address is a member of the fourth block of addresses © Janice Regan, 2012-2018 19 Hierarchical addressing: 1 CIDR is a hierarchical addressing approach Groups of networks can be aggregated to appear as a single network to more distant routers Entries that appear to be a single network to a particular router may in fact be aggregations of many smaller networks © Janice Regan, 2012-2018 20 Hierarchical addressing: 2 CIDR (RFC 1518, 1519) Points out that CIDR replaces both sub and super netting, so long as addresses are assigned in blocks with size equal to an integer power of 2 network and host portions are readily separated with a mask IANA (the organization in charge of administering distribution of IP addresses) has three regional registries ARIN: North America RIPE: Europe APNIC: Asia LACNIC: South America Each of these registries was given a large block of addresses © Janice Regan, 2012-2018 21 Hierarchical addressing: 3 Each of the regional registries grants blocks of addresses to each country in its region Each country may grant addresses on a regional basis within the country Each country or region of a country will grant addresses to large IP providers and or companies for their networks These providers or companies apportion addresses to their users Hierarchical addressing: 3 Caveat CIDR was introduced after many addresses had already been allocated using the classful system. Some blocks of addresses are not within their “assigned” areas because they were assigned before CIDR was introduced. The CIDR routing algorithm will still get the packets to the right place, as explained in the following example © Janice Regan, 2012-2018 22 © Janice Regan, 2012-2018 23 CIDR example problem You are a administrator for ABC EngCo. Your company has been assigned the CIDR address block 196.74.0.0/17 Your predecessor has assigned three project groups to sub networks 196.74.16.0/21, 196.74.32.0/22, and 196.74.48.0/20 You have been asked to allocate networks for three additional groups with the following numbers of hosts needing addresses 2000, 512, and 3500 © Janice Regan, 2012-2018 24 Available addresses? Your block of addresses 196.74.0.0/17, has 2(32-17)=32768 addresses, 196.74.0.0 to 196.74.127.255 Networks already allocated 196.74.16.0 to 196.74.23.255 (196.74.16.0/21) 2048 addresses 196.74.32.0 to 196.74.35.255 (196.74.32.0/22) 1024 addresses 196.74.48.0 to 196.74.63.255 (196.74.48.0/20) 4096 addresses © Janice Regan, 2012-2018 25 Allocated / available space 1024 0 0 4 8 12 16 20 24 28 32 36 40 44 48 0 2048 4096 1024 00 0 52 56 60 64 4096 196.74.16.0/21 196.74.32.0/22 196.74. 48.0/20 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 52 56 60 64 Available space Remaining portions of your address allocation 196.74.0.0/20 (4096 addresses) 196.74.0.0/21 and 196.74.8.0.0/21 (2 x 2048) 196.74.0.0/22, 196.74.4.0/22, 196.24.8.0/22, 196.74.12.0.0/22 196.74.24.0/21 (2048 addresses) 196.74.36.0/22 (1024 addresses) 196.74.40.0/21 (2048 addresses) 196.74.64.0/18 (16384 addresses) © Janice Regan, 2012-2018 26 How big are our new networks? You have been asked to allocate networks with 2000, 512, and 3500 hosts If K host addresses are desired and (2N-1)-2 < K < (2N)-2 the netid will have 32-N bits So we need N=11 2048 addressed for the net with 2000 hosts N=10 1024 addresses for the net with 512 hosts (note N=9 only provides 510 addresses for hosts) N=12 4096 addresses for the net with 3500 hosts © Janice Regan, 2012-2018 27 © Janice Regan, 2012-2018 28 Allocating new networks Start with the largest as it will be the most difficult to find space for. There is a block starting at 196.74.0.0 (a 4096 boundary) that is large enough to hold this network. Also at 196.74.64.0, 196.74.80.0 … 196.74.112.0 (4 possible) Next consider the 2048 block, there are two possible locations starting on a 2048 boundary that have enough available space 196.74.24.0 and 196.74.40.0 Also at 196.74.64.0, 196.74.82.0, … 196.74.120.0 (8 possible) Finally consider the 1024 block. Place the block on a 1024 boundary (preferably one that is not also a 2048 or 4096 boundary) say 196.74.36.0. Also at 176.74.64.0, 196.74.78.0 … 196.74.124.0 (16 possible Why choose these networks These networks were chosen to leave the maximum possible flexibility to add further networks in the future. Decisions might be different if it were necessary to leave room for significant room for growth of these networks in the future. (For example you might want to leave room to double network size) © Janice Regan, 2012-2018 29 © Janice Regan, 2012-2018 30 Allocated / available space 0 indicates address 196.74.0.0 12 indicates address 196.74.12.0 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 0 00 0 52 56 60 64 4096 196.74.0.0/20 196.74.24.0/21 196.74.36.0/22 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 52 56 60 64 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 52 56 60 64 © Janice Regan, 2012-2018 31 Our example network To Internet To Internet Router0 196.74.0.0/20 196.74.16.0/21 196.74.24.0/21 196.74.32.0/22 196.74.36./22 196.74.48.0/20 196.74.0.0/18 196.72.0.111 © Janice Regan, 2012-2018 32 Aggregation for our example If the six networks in our example were all in the same distant city we would to refer to them with one router table entry with network address/mask 196.74.0.0/18 Alternately we could aggregate including the unused address space (64 to 128) using one router table entry for network address/mask 196.74.0.0/17. The networks shown above (or the whole address space assigned to ABC EngCo) can be aggregated into one entry for routing tables outside ABC EngCo 4096 4096 196.74.36.0/22 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 0 52 56 60 64 © Janice Regan, 2012-2018 33 A sample routing table: Router 0 Inside ABC EngCo Destination Gateway Genmask Metric Iface 196.74.0.0 * 255.255.240.0 0 Eth0 196.74.16.0 * 255.255.248.0 0 Eth1 196.74.24.0 * 255.255.248.0 0 Eth2 196.74.32.0 * 255.255.252.0 0 Eth3 196.74.36.0 * 255.255.252.0 0 Eth4 196.74.48.0 * 255.255.240.0 0 Eth5 IPv4 Router table for router at ABC ENGCO’s site © Janice Regan, 2012-2018 34 A sample routing table: Router 0 Routers at the Internet provider for ABC EngCo will see the networks there as a single network. To reach ABC EngCo these routers will have a single entry for Destination 196.74.0.0/17 with netmask 255.255.128.0 and gateway set to the address of the router that sits between ABC EngCo’s networks and the internet. (196.72.0.111) © Janice Regan, 2012-2018 35 Expanding our example: Regional The Internet provider in the city where ABC EngCo is located allocated the block of addresses you have been working with from its block of 196.72.0.0/14 For arguments sake assume this block is from a Canadian allocation (see if you can find where it really is) Routing tables: outside provider Users who are not using ABC EngCo’s internet provider use a single entry in their routing table for that internet provider (that entry includes ABC EngCo). The entry in other router tables outside ABC EngCo’s Internet provider would be for network 196.72.0.0/14. This entry includes ABC EngCo and all the other customers of that Internet provider © Janice Regan, 2012-2018 36 Routing Tables: outside Canada Continuing the generalization, the routing tables outside Canada could have a single entry for all of Canada That single entry might include the addresses administered by ABC EngCo’s internet provider © Janice Regan, 2012-2018 37 © Janice Regan, 2012-2018 38 Return to our example The aggregated address for ABC EngCo, 196.74.0.0/17, includes all ABC EngCo’s addresses Let us consider an additional complication What if the network196.74.44/22 belongs to ARTSCO? ARTSCO owned these addresses before ABC EngCo received their address block. How does this change the entries to the routing tables we just discussed? 196.74.44.0/22 4096 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 52 56 60 64 © Janice Regan, 2012-2018 39 Additions to routing tables What if the network196.74.44/22 belongs to ARTSCO? ARTSCO owned these addresses before ABC EngCo received their address block. Then an additional entry would be added to each the external routing tables discussed for 196.74.44.0/22. When the routing algorithm checked for matches for an address within 196.74.44.0/22 two matches would be found ABC EngCo (or aggregate) and 196.74.44.0/22, The longest match, has the most matching higher order bits. The length of the netid is the number of matching bits. For 196.74.44.0/22 there are 22 matching bits. For 196.72.0.0/14 there are 14 matching bits. The routing table entry with the most matching bits would be for ARTSCO so the packets would be delivered to the correct location 00 0 00 0 © Janice Regan, 2012-2018 40 A new European Sales office ABC EngCo is opening a new European sales office and wishes to use some of its remaining IP addresses 196.74.40.0/23 to service the European office Now the European routers will need an additional entry for 196.74.40.0/23 routing it to the correct European location © Janice Regan, 2012-2018 41 Return to our example The aggregated address for ABC EngCo, 196.74.0.0/17, includes all ABC EngCo’s addresses Let us consider an additional complication What if the network196.74.40/23 is for the European office? How does this change the entries to the routing tables we just discussed? 196.74.40.0/23 4096 00 0 0 4 8 12 16 20 24 28 32 36 40 44 48 00 0 52 56 60 64 © Janice Regan, 2012-2018 42 A new European Sales office Consider any routing table outside ABC EngCo What happens with two entries in the routing table both match the destination address 196.74.40.37 196.72.0.0/14 14 bit network address matches 196.74.0.0/17 17 bit network address matches 196.74.40.0/23 23 bit network address matches The longest match is selected, so the packet will go directly to the European office © Janice Regan, 2012-2018 43 Sending packets from Europe Consider sending a packet with address 196.74.18.23 In Europe the router may have a routing table entry for 196.0.0.0/8 routed through a gateway to North America That gateway may have a routing table entry for the regional provider 196.72.0.0/14 using the providers router as a gateway The providers router will have an entry for 196.74.0.0/17 to send the packet to ABC EngCo through ABC EngCo’s router /docProps/thumbnail.jpeg