Transcript DNS,TCP/IP Fundamentals, IP Addressing

Weeks 5-7
DNS, IP Addressing, IP
Routing
1
DNS: Domain Name System
People: many identifiers:

SSN, name, passport #
Internet hosts, routers:


IP address (32 bit) used for addressing
datagrams
“name”, e.g.,
www.yahoo.com - used
by humans
Q: map between IP
addresses and name ?
Domain Name System:
 distributed database
implemented in hierarchy of
many name servers
 application-layer protocol
host, routers, name servers to
communicate to resolve names
(address/name translation)
 note: core Internet
function, implemented as
application-layer protocol
 complexity at network’s
“edge”
2
DNS
DNS services
 Hostname to IP
address translation
 Host aliasing

Canonical and alias
names
 Mail server aliasing
 Load distribution
 Replicated Web
servers: set of IP
addresses for one
canonical name
Why not centralize DNS?
 single point of failure
 traffic volume
 distant centralized
database
 maintenance
doesn’t scale!
3
Distributed, Hierarchical Database
Root DNS Servers
com DNS servers
yahoo.com
amazon.com
DNS servers DNS servers
org DNS servers
pbs.org
DNS servers
edu DNS servers
poly.edu
umass.edu
DNS serversDNS servers
Client wants IP for www.amazon.com; 1st approx:
 Client queries a root server to find com DNS
server
 Client queries com DNS server to get amazon.com
DNS server
 Client queries amazon.com DNS server to get IP
address for www.amazon.com
4
DNS: Root name servers
 contacted by local name server that can not resolve name
 root name server:



contacts authoritative name server if name mapping not known
gets mapping
returns mapping to local name server
a Verisign, Dulles, VA
c Cogent, Herndon, VA (also Los Angeles)
d U Maryland College Park, MD
k RIPE London (also Amsterdam,
g US DoD Vienna, VA
Frankfurt) Stockholm (plus 3
i Autonomica,
h ARL Aberdeen, MD
other locations)
j Verisign, ( 11 locations)
m WIDE Tokyo
e NASA Mt View, CA
f Internet Software C. Palo Alto,
CA (and 17 other locations)
13 root name
servers worldwide
b USC-ISI Marina del Rey, CA
l ICANN Los Angeles, CA
5
TLD and Authoritative Servers
 Top-level domain (TLD) servers: responsible
for com, org, net, edu, etc, and all top-level
country domains uk, fr, ca, jp.
Network solutions maintains servers for com TLD
 Educause for edu TLD

 Authoritative DNS servers: organization’s
DNS servers, providing authoritative
hostname to IP mappings for organization’s
servers (e.g., Web and mail).

Can be maintained by organization or service
provider
6
Local Name Server
 Does not strictly belong to hierarchy
 Each ISP (residential ISP, company,
university) has one.

Also called “default name server”
 When a host makes a DNS query, query is
sent to its local DNS server

Acts as a proxy, forwards query into hierarchy.
7
Example
root DNS server
2
 Host at cis.poly.edu
3
wants IP address for
gaia.cs.umass.edu
TLD DNS server
4
5
local DNS server
dns.poly.edu
1
8
requesting host
7
6
authoritative DNS server
dns.cs.umass.edu
cis.poly.edu
gaia.cs.umass.edu
8
Recursive queries
recursive query:
2
 puts burden of name
resolution on
contacted name
server
 heavy load?
iterated query:
 contacted server
replies with name of
server to contact
 “I don’t know this
name, but ask this
server”
root DNS server
3
7
6
TLD DNS serve
local DNS server
dns.poly.edu
1
5
4
8
requesting host
authoritative DNS server
dns.cs.umass.edu
cis.poly.edu
gaia.cs.umass.edu
9
DNS: caching and updating records
 once (any) name server learns mapping, it caches
mapping
 cache entries timeout (disappear) after some
time
 TLD servers typically cached in local name
servers
• Thus root name servers not often visited
 update/notify mechanisms under design by IETF
 RFC 2136

http://www.ietf.org/html.charters/dnsind-charter.html
10
DNS records
DNS: distributed db storing resource records (RR)
RR format: (name,
 Type=A
 name is hostname
 value is IP address
value, type, ttl)
 Type=CNAME
 name is alias name for some
“cannonical” (the real) name
www.ibm.com is really
 Type=NS
servereast.backup2.ibm.com
 name is domain (e.g.
 value is cannonical name
foo.com)
 value is IP address of
 Type=MX
authoritative name
 value is name of mailserver
server for this domain
associated with name
11
DNS protocol, messages
DNS protocol : query and reply messages, both with
same message format
msg header
 identification: 16 bit #
for query, reply to query
uses same #
 flags:
 query or reply
 recursion desired
 recursion available
 reply is authoritative
12
DNS protocol, messages
Name, type fields
for a query
RRs in reponse
to query
records for
authoritative servers
additional “helpful”
info that may be used
13
Inserting records into DNS
 Example: just created startup “Network Utopia”
 Register name networkuptopia.com at a registrar
(e.g., Network Solutions)


Need to provide registrar with names and IP addresses of
your authoritative name server (primary and secondary)
Registrar inserts two RRs into the com TLD server:
(networkutopia.com, dns1.networkutopia.com, NS)
(dns1.networkutopia.com, 212.212.212.1, A)
 Put in authoritative server Type A record for
www.networkuptopia.com and Type MX record for
networkutopia.com
 How do people get the IP address of your Web site?
14
Network Layer
Goals:
 understand principles behind network layer
services:
routing (path selection)
 dealing with scale
 how a router works
 advanced topics: IPv6, mobility

 instantiation and implementation in the
Internet
15
Network Layer
 Introduction
 Virtual circuit and
datagram networks
 What’s inside a router
 IP: Internet Protocol




Datagram format
IPv4 addressing
ICMP
IPv6
 Routing algorithms
 Link state
 Distance Vector
 Hierarchical routing
 Routing in the
Internet



RIP
OSPF
BGP
 Broadcast and
multicast routing
16
Network layer
 transport segment from




sending to receiving host
on sending side
encapsulates segments
into datagrams
on rcving side, delivers
segments to transport
layer
network layer protocols
in every host, router
Router examines header
fields in all IP datagrams
passing through it
application
transport
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
network
data link
physical
application
transport
network
data link
physical
17
Key Network-Layer Functions
 forwarding: move
packets from router’s
input to appropriate
router output
 routing: determine
route taken by
packets from source
to dest.

analogy:
 routing: process of
planning trip from
source to dest
 forwarding: process
of getting through
single interchange
Routing algorithms
18
Interplay between routing and forwarding
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
0111
1
3 2
19
Connection setup
 3rd important function in some network
architectures:

ATM, frame relay, X.25
 Before datagrams flow, two hosts and
intervening routers establish virtual
connection

Routers get involved
 Network and transport layer cnctn service:
 Network: between two hosts
 Transport: between two processes
20
Network service model
Q: What service model for “channel” transporting
datagrams from sender to rcvr?
Example services for
individual datagrams:
 guaranteed delivery
 Guaranteed delivery
with less than 40 msec
delay
Example services for a
flow of datagrams:
 In-order datagram
delivery
 Guaranteed minimum
bandwidth to flow
 Restrictions on
changes in interpacket spacing
21
Network layer service models:
Network
Architecture
Internet
Service
Model
Guarantees ?
Congestion
Bandwidth Loss Order Timing feedback
best effort none
ATM
CBR
ATM
VBR
ATM
ABR
ATM
UBR
constant
rate
guaranteed
rate
guaranteed
minimum
none
no
no
no
yes
yes
yes
yes
yes
yes
no
yes
no
no (inferred
via loss)
no
congestion
no
congestion
yes
no
yes
no
no
22
Network layer connection and
connection-less service
 Datagram network provides network-layer
connectionless service
 VC network provides network-layer
connection service
 Analogous to the transport-layer services,
but:
Service: host-to-host
 No choice: network provides one or the other
 Implementation: in the core

23
Virtual circuits
“source-to-dest path behaves much like telephone
circuit”


performance-wise
network actions along source-to-dest path
 call setup, teardown for each call before data can flow
 each packet carries VC identifier (not destination host
address)
 every router on source-dest path maintains “state” for
each passing connection
 link, router resources (bandwidth, buffers) may be
allocated to VC
24
VC implementation
A VC consists of:
1.
2.
3.
Path from source to destination
VC numbers, one number for each link along
path
Entries in forwarding tables in routers along
path
 Packet belonging to VC carries a VC
number.
 VC number must be changed on each link.

New VC number comes from forwarding table
25
Forwarding table
VC number
22
12
1
Forwarding table in
northwest router:
Incoming interface
1
2
3
1
…
2
32
3
interface
number
Incoming VC #
12
63
7
97
…
Outgoing interface
2
1
2
3
…
Outgoing VC #
22
18
17
87
…
Routers maintain connection state information!
26
Virtual circuits: signaling protocols
 used to setup, maintain teardown VC
 used in ATM, frame-relay, X.25
 not used in today’s Internet
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
6. Receive data application
3. Accept call transport
2. incoming call network
data link
physical
27
Datagram networks
 no call setup at network layer
 routers: no state about end-to-end connections
 no network-level concept of “connection”
 packets forwarded using destination host address
 packets between same source-dest pair may take
different paths
application
transport
network
data link 1. Send data
physical
application
transport
2. Receive data network
data link
physical
28
Forwarding table
Destination Address Range
4 billion
possible entries
Link Interface
11001000 00010111 00010000 00000000
through
11001000 00010111 00010111 11111111
0
11001000 00010111 00011000 00000000
through
11001000 00010111 00011000 11111111
1
11001000 00010111 00011001 00000000
through
11001000 00010111 00011111 11111111
2
otherwise
3
29
Longest prefix matching
Prefix Match
11001000 00010111 00010
11001000 00010111 00011000
11001000 00010111 00011
otherwise
Link Interface
0
1
2
3
Examples
DA: 11001000 00010111 00010110 10100001
Which interface?
DA: 11001000 00010111 00011000 10101010
Which interface?
30
Datagram or VC network: why?
Internet
 data exchange among
ATM
 evolved from telephony
computers
 human conversation:
 “elastic” service, no strict
 strict timing, reliability
timing req.
requirements
 “smart” end systems
 need for guaranteed
(computers)
service
 can adapt, perform
 “dumb” end systems
control, error recovery
 telephones
 simple inside network,
 complexity inside
complexity at “edge”
network
 many link types
 different characteristics
 uniform service difficult
31
Router Architecture Overview
Two key router functions:
 run routing algorithms/protocol (RIP, OSPF, BGP)
 forwarding datagrams from incoming to outgoing link
32
Input Port Functions
Physical layer:
bit-level reception
Data link layer:
e.g., Ethernet
see chapter 5
Decentralized switching:
 given datagram dest., lookup output port
using forwarding table in input port
memory
 goal: complete input port processing at
‘line speed’
 queuing: if datagrams arrive faster than
forwarding rate into switch fabric
33
Three types of switching fabrics
34
Switching Via Memory
First generation routers:
 traditional computers with switching under direct
control of CPU
packet copied to system’s memory
 speed limited by memory bandwidth (2 bus
crossings per datagram)
Input
Port
Memory
Output
Port
System Bus
35
Switching Via a Bus
 datagram from input port memory
to output port memory via a shared
bus
 bus contention: switching speed
limited by bus bandwidth
 1 Gbps bus, Cisco 1900: sufficient
speed for access and enterprise
routers (not regional or backbone)
36
Switching Via An Interconnection
Network
 overcome bus bandwidth limitations
 Banyan networks, other interconnection nets
initially developed to connect processors in
multiprocessor
 Advanced design: fragmenting datagram into fixed
length cells, switch cells through the fabric.
 Cisco 12000: switches Gbps through the
interconnection network
37
Output Ports
 Buffering required when datagrams arrive from
fabric faster than the transmission rate
 Scheduling discipline chooses among queued
datagrams for transmission
38
Output port queueing
 buffering when arrival rate via switch exceeds
output line speed
 queueing (delay) and loss due to output port
buffer overflow!
39
Input Port Queuing
 Fabric slower than input ports combined -> queueing
may occur at input queues
 Head-of-the-Line (HOL) blocking: queued datagram
at front of queue prevents others in queue from
moving forward
 queueing delay and loss due to input buffer overflow!
40
The Internet Network layer
Host, router network layer functions:
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
forwarding
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
41
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
how much overhead
with TCP?
 20 bytes of TCP
 20 bytes of IP
 = 40 bytes + app
layer overhead
32 bits
type of
ver head.
len service
length
fragment
16-bit identifier flgs
offset
upper
time to
Internet
layer
live
checksum
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
42
IP Fragmentation & Reassembly
 network links have MTU
(max.transfer size) - largest
possible link-level frame.
 different link types,
different MTUs
 large IP datagram divided
(“fragmented”) within net
 one datagram becomes
several datagrams
 “reassembled” only at final
destination
 IP header bits used to
identify, order related
fragments
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
43
IP Fragmentation and Reassembly
Example
 4000 byte
datagram
 MTU = 1500 bytes
1480 bytes in
data field
offset =
1480/8
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
=185
length ID fragflag offset
=1040 =x
=0
=370
44
IP Addressing: introduction
 IP address: 32-bit
identifier for host,
router interface
 interface: connection
between host/router
and physical link



router’s typically have
multiple interfaces
host may have multiple
interfaces
IP addresses
associated with each
interface
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.2.9
223.1.3.27
223.1.2.2
223.1.3.2
223.1.3.1
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
1
45
IP Addressing
 Internet Scaling Problems
 In the early nineties, the Internet has experienced two
major scaling issues as it has struggled to provide continuous
and uninterrupted growth:
• The eventual exhaustion of the IPv4 address space
• The ability to route traffic between the ever increasing number
of networks that comprise the Internet
 The first problem is concerned with the eventual
depletion of the IP address space. The current
version of IP, IP version 4 (IPv4), defines a 32-bit
address which means that there are only 2 32
(4,294,967,296) IPv4 addresses available. This might
seem like a large number of addresses, but as new
markets open and a significant portion of the world's
population becomes candidates for IP addresses, the
finite number of IP addresses will eventually be
exhausted.
46
IP Addressing
 The address shortage problem is aggravated by
the fact that portions of the IP address space
have not been efficiently allocated. Also, the
traditional model of classful addressing does not
allow the address space to be used to its maximum
potential.
 The Address Lifetime Expectancy (ALE) Working
Group of the IETF has expressed concerns that if
the current address allocation policies are not
modified, the Internet will experience a near to
medium term exhaustion of its unallocated
address pool. If the Internet's address supply
problem is not solved, new users may be unable to
connect to the global Internet!
47
Trends
48
Classful IP Addressing
One of the fundamental
features of classful IP
addressing is that each
address contains a selfencoding key that
identifies the dividing
point between the network
prefix and the hostnumber.
49
Class A Networks
 Each Class A network address has an 8-bit
network-prefix with the highest order bit
set to 0 and a seven-bit network number,
followed by a 24-bit host-number.
 Today, it is no longer considered 'modern'
to refer to a Class A network. Class A
networks are now referred to as "/8s"
(pronounced "slash eight" or just "eights")
since they have an 8-bit network-prefix.
50
Class A Networks
 A maximum of 126 (2^7 -2) /8 networks can be
defined. The calculation requires that the 2 is
subtracted because the /8 network 0.0.0.0 is
reserved for use as the default route and the /8
network 127.0.0.0 (also written 127/8 or
127.0.0.0/8) has been reserved for the "loopback"
function.
 Each /8 supports a maximum of 16,777,214 (2^24
-2) hosts per network. The host calculation
requires that 2 is subtracted because the all-0s
("this network") and all-1s ("broadcast") hostnumbers may not be assigned to individual hosts.
 The /8 address space is 50% of the total IPv4
unicast address space.
51
Classful Addressing Continued
 Class B Networks
Each Class B network address has a 16-bit
network-prefix with the two highest order bits
set to 1-0 and a 14-bit network number,
followed by a 16-bit host-number.
 Class B networks are now referred to as"/16s"
since they have a 16-bit network-prefix.A
maximum of 16,384 (2^14 ) /16 networks can be
defined with up to 65,534 (2^16 -2) hosts per
network, it represents 25% of the total IPv4
unicast address space.

52
Classful Addressing Continued
 Class C Networks



Each Class C network address has a 24-bit network-prefix
with the three highest order bits set to 1-1-0 and a 21-bit
network number, followed by an 8-bit host-number.
Class C networks are now referred to as "/24s" since they
have a 24-bit network-prefix.
A maximum of 2,097,152 (2^21 ) /24 networks can be
defined with up to 254 (2^8 -2) hosts per network. It
represents 12.5% (or 1/8th) of the total IPv4 unicast
address space.
 Other Classes

Class D addresses have their leading four-bits set to 1-1-10 and are used to support IP Multicasting. Class E
addresses have their leading four-bits set to 1-1-1-1 and
are reserved for experimental use.
53
Dotted Decimal Notation
Dotted-decimal notation divides the 32-bit Internet address into
four 8-bit (byte) fields and specifies the value of each field
independently as decimal number with the fields separated by dots.
54
Limitations to Classful Addressing
 During the early days of the Internet, the
seemingly unlimited address space allowed IP
addresses to be allocated to an organization based
on its request rather than its actual need. As a
result, addresses were freely assigned to those
who asked for them without concerns about the
eventual depletion of the IP address space.
 The decision to standardize on a 32-bit address
space meant that there were only 2^32
(4,294,967,296) IPv4 addresses available. A
decision to support a slightly larger address space
would have exponentially increased the number of
addresses thus eliminating the current address
shortage problem.
55
Limitations to Classful Addressing
 The classful A, B, and C octet boundaries were
easy to understand and implement, but they did
not foster the efficient allocation of a finite
address space. Problems resulted from the lack of
a network class that was designed to support
medium-sized organizations.


A /24, which supports 254 hosts, is too small while a /16,
which supports 65,534 hosts, is too large.
In the past, the Internet has assigned sites with several
hundred hosts a single /16 address instead of a couple of
/24s addresses. Unfortunately, this has resulted in a
premature depletion of the /16 network address space.
The only readily available addresses for medium-size
organizations are /24s which have the potentially
negative impact of increasing the size of the global
Internet's routing table.
56
Subnetting
 In 1985, RFC 950 defined a standard procedure to
support the subnetting, or division, of a single Class A,
B, or C network number into smaller pieces.
 Subnetting was introduced to overcome some of the
problems that parts of the Internet were beginning to
experience with the classful two-level addressing
hierarchy:


Internet routing tables were beginning to grow.
Local administrators had to request another network number
from the Internet before a new network could be installed at
their site.
 Three-level
hierarchy is used
57
Subnetting
58
What did subnetting bring?
 Subnetting attacked the expanding routing table
problem by ensuring that the subnet structure of
a network is never visible outside of the
organization's private network.
 The route from the Internet to any subnet of a
given IP address is the same, no matter which
subnet the destination host is on. This is because
all subnets of a given network number use the
same network-prefix but different subnet
numbers.
 The routers within the private organization need
to differentiate between the individual subnets,
but as far as the Internet routers are concerned,
all of the subnets in the organization are collected
into a single routing table entry.
59
Subnetting contd
 This allows the local administrator to introduce
arbitrary complexity into the private network
without affecting the size of the Internet's
routing tables.
 Subnetting overcame the registered number issue
by assigning each organization one (or at most a
few) network number(s) from the IPv4 address
space. The organization was then free to assign a
distinct subnetwork number for each of its
internal networks.

This allows the organization to deploy additional subnets
without needing to obtain a new network number from
the Internet.
60
Example
• The size of the global Internet routing table does not grow
because the site administrator does not need to obtain additional
address space and the routing advertisements for all of the subnets
are combined into a single routing table entry.
• The local administrator has the flexibility to deploy additional
subnets without obtaining a new network number from the Internet.
• Route flapping (i.e., the rapid changing of routes) within the
private network does not affect the Internet routing table
61
Extended Network Prefix
Internet routers use only the network-prefix of the destination
address to route traffic to a subnetted environment. Routers within
the subnetted environment use the extended-network-prefix to
route traffic between the individual subnets. The extendednetwork-prefix is composed of the classful network-prefix and the
subnet-number.
130.5.5.25/24 notation is used to describe the IP address
62
Subnet Design Considerations
1) How many total subnets does the organization
need today?
2) How many total subnets will the organization need
in the future?
3) How many hosts are there on the organization's
largest subnet today?
4) How many hosts will there be on the
organization's largest subnet in the future?
63
Subnet Design Considerations
 The first step in the planning process is to take the
maximum number of subnets required and round up to the
nearest power of two. For example, if a organization needs 9
subnets, 2^3 (or 8) will not provide enough subnet
addressing space, so the network administrator will need to
round up to 2^4 (or 16). Also leave room for growth.
 The second step is to make sure that there are enough host
addresses for the organization's largest subnet. If the
largest subnet needs to support 50 host addresses today,
2^5 (or 32) will not provide enough host address space so
the network administrator will need to round up to 2^6 (or
64).
 The final step is to make sure that the organization's
address allocation provides enough bits to deploy the
required subnet addressing plan.
64
Subnet Example
 An organization has been assigned the network
number 193.1.1.0/24 and it needs to define six
subnets. The largest subnet is required to support
25 hosts.
65
Subnet example contd
 A 27-bit extended-network-prefix leaves 5
bits to define host addresses on each
subnet.
 This means that each subnetwork with a
27-bit prefix represents a contiguous
block of 2^5 (32) individual IP addresses.
However, since the all-0s and all-1s host
addresses cannot be allocated, there are
30 (2^5 -2) assignable host addresses on
each subnet.
66
Example Continued
Base Net:
Subnet #0:
Subnet #1:
Subnet #2:
Subnet #3:
Subnet #4:
Subnet #5:
Subnet #6:
Subnet #7:
11000001.00000001.00000001
11000001.00000001.00000001.
11000001.00000001.00000001.
11000001.00000001.00000001.
11000001.00000001.00000001.
11000001.00000001.00000001.
11000001.00000001.00000001.
11000001.00000001.00000001.
11000001.00000001.00000001.
.00000000 = 193.1.1.0/24
000 00000 = 193.1.1.0/27
001 00000 = 193.1.1.32/27
010 00000 = 193.1.1.64/27
011 00000 = 193.1.1.96/27
100 00000 = 193.1.1.128/27
101 00000 = 193.1.1.160/27
110 00000 = 193.1.1.192/27
111 00000 = 193.1.1.224/27
Subnets
Subnet #6: 11000001.00000001.00000001.110 00000 = 193.1.1.192/27
Host #1: 11000001.00000001.00000001.110 00001 = 193.1.1.193/27
Host #2: 11000001.00000001.00000001.110 00010 = 193.1.1.194/27
Host #3: 11000001.00000001.00000001.110 00011 = 193.1.1.195/27
.
.
Host #28: 11000001.00000001.00000001.110 11100 = 193.1.1.220/27
Host #29: 11000001.00000001.00000001.110 11101 = 193.1.1.221/27
Host #30: 11000001.00000001.00000001.110 11110 = 193.1.1.222/27
Hosts belonging to Subnet 6
67
Variable Length Subnet Masks
 In 1987, RFC 1009 specified how a subnetted network could use more
than one subnet mask. When an IP network is assigned more than one
subnet mask, it is considered a network with "variable length subnet
masks" (VLSM) since the extended-network-prefixes have different
lengths.
 There are several advantages to be gained if more than one subnet
mask can be assigned to a given IP network number:


Multiple subnet masks permit more efficient use of an organization's
assigned IP address space.
Multiple subnet masks permit route aggregation which can significantly
reduce the amount of routing information at the "backbone" level within an
organization's routing domain.
 Example. A /16 network with a /22 extended-network prefix permits
64 subnets each of which supports a maximum of 1,022 hosts.
 This is fine if the organization wants to deploy a number of large
subnets, but what about the occasional small subnet containing only
20 or 30 hosts? Since a subnetted network could have only a single
mask, the network administrator was still required to assign the 20
or 30 hosts to a subnet with a 22-bit prefix. This assignment would
waste approximately 1,000 IP host addresses for each small subnet
deployed!
68
Example Continued
 One solution to this problem was to allow a
subnetted network to be assigned more than one
subnet mask.
 Assume that in the previous example, the network
administrator is also allowed to configure the
130.5.0.0/16 network with a /26 extendednetwork-prefix.
 A /26 extended-network prefix permits 1024
subnets (2^10 ), each of which supports a
maximum of 62 hosts (2^6 -2).
 The /26 prefix would be ideal for small subnets
with less than 60 hosts, while the /22 prefix is
well suited for larger subnets containing up to
1000 hosts.
69
Recursive Definition of an
Organization’s Address Space
sub-subnet
sub2-subnet
subnet
The 11.0.0.0/8 network is first configured with a /16 extended-network-prefix.
The 11.1.0.0/16 subnet is then configured with a /24 extended-network-prefix
11.253.0.0/16 subnet is configured with a /19 extended-network-prefix. Note
that the recursive process does not require that the same extended-networkprefix be assigned at each level of the recursion. Also, the recursive sub-division of
the organization's address space can be carried out as far as the network
administrator needs to take it.
70
Route Aggregation
71
Requirements for VLSM Design
 The successful deployment of VLSM has three
prerequisites:

The routing protocols must carry extended-networkprefix information with each route advertisement.
• The bottom line is that if you want to deploy VLSM in a
complex topology, you must select OSPF or IS-IS as the
Interior Gateway Protocol (IGP) rather than RIP-1!
• It should be mentioned that RIP-2, defined in RFC 1388,
improves the RIP protocol by allowing it to carry extendednetwork-prefix information. Therefore, RIP-2 supports the
deployment of VLSM.

All routers must implement a consistent forwarding
algorithm based on the "longest match.“. A route with a
longer extended-network-prefix is said to be "more
specific" while a route with a shorter extended-networkprefix is said to be "less specific.“
72
Classless Inter Domain Routing
(CIDR)
 By 1992, the exponential growth of the Internet
was beginning to raise serious concerns among
members of the IETF about the ability of the
Internet's routing system to scale and support
future growth. These problems were related to:



The near-term exhaustion of the Class B network
address space
The rapid growth in the size of the global Internet's
routing tables
The eventual exhaustion of the 32-bit IPv4 address
space
73
CIDR
 CIDR was officially documented in September 1993 in RFC
1517, 1518, 1519, and 1520. CIDR supports two important
features that benefit the global Internet routing system:


CIDR eliminates the traditional concept of Class A, Class B, and
Class C network addresses. This enables the efficient allocation
of the IPv4 address space which will allow the continued growth
of the Internet until IPv6 is deployed.
CIDR supports route aggregation where a single routing table
entry can represent the address space of perhaps thousands of
traditional classful routes. This allows a single routing table
entry to specify how to route traffic to many individual
network addresses. Route aggregation helps control the amount
of routing information in the Internet's backbone routers,
reduces route flapping (rapid changes in route availability), and
eases the local administrative burden of updating external
routing information.
 Without the rapid deployment of CIDR in 1994 and 1995,
the Internet routing tables would have in excess of 70,000
routes (instead of the current 30,000+) and the Internet
would probably not be functioning today!
74
CIDR
 CIDR eliminates the traditional concept of Class A, Class B,
and Class C network addresses and replaces them with the
generalized concept of a "network-prefix."
 Routers use the network-prefix, rather than the first 3 bits
of the IP address, to determine the dividing point between
the network number and the host number. As a result, CIDR
supports the deployment of arbitrarily sized networks
rather than the standard 8-bit, 16-bit, or 24-bit network
numbers associated with classful addressing.
 In the CIDR model, each piece of routing information is
advertised with a bit mask (or prefix-length). The prefixlength is a way of specifying the number of leftmost
contiguous bits in the network-portion of each routing table
entry.
 Example. All prefixes with a /20 prefix represent the same
amount of address space (2^12 or 4,096 host addresses).
Furthermore, a /20 prefix can be assigned to a traditional
Class A, Class B, or Class C network number.
75
CIDR Address Blocks
76
Efficient Address Allocation
 Assume that an ISP has been assigned the address block
206.0.64.0/18. This block represents 16,384 (2^14 ) IP
addresses which can be interpreted as 64 /24s.
 If a client requires 800 host addresses, rather than
assigning a Class B (and wasting ~64,700 addresses) or four
individual Class Cs (and introducing 4 new routes into the
global Internet routing tables), the ISP could assign the
client the address block 206.0.68.0/22, a block of 1,024
(2^10 ) IP addresses (4 contiguous /24s).
77
CIDR Address Allocation
Example
 For this example, assume that an ISP owns the address
block 200.25.0.0/16. This block represents 65, 536 (2^16 )
IP addresses (or 256 /24s).
 From the 200.25.0.0/16 block it wants to allocate the
200.25.16.0/20 address block. This smaller block represents
4,096 (2^12 ) IP addresses (or 16 /24s).
 If you look at the ISP's /20 address block as a pie, in a
classful environment it can only be cut into 16 equal-size
pieces.
78
CIDR Address Allocation
 However, in a classless environment, the ISP is free to cut up
the pie any way it wants.
 It could slice up the original pie into 2 pieces (each 1/2 of the
address space) and assign one portion to Organization A, then
cut the other half into 2 pieces (each 1/4 of the address
space) and assign one piece to Organization B, and finally slice
the remaining fourth into 2 pieces (each 1/8 of the address
space) and assign it to Organization C and Organization D.
 Each of the individual organizations is free to allocate the
address space within its "Intranetwork" as it sees fit.
79
CIDR vs VLSM
 CIDR has the same familiar look and feel of VLSM
 CIDR and VLSM are essentially the same thing since they
both allow a portion of the IP address space to be
recursively divided into subsequently smaller pieces.
 The difference is that with VLSM, the recursion is
performed on the address space previously assigned to an
organization and is invisible to the global Internet. CIDR, on
the other hand, permits the recursive allocation of an
address block by an Internet Registry to a high-level ISP, to
a mid-level ISP, to a low-level ISP, and finally to a private
organization's network.
 Just like VLSM, the successful deployment of CIDR has
three prerequisites:



The routing protocols must carry network-prefix information
with each route advertisement.
All routers must implement a consistent forwarding algorithm
based on the "longest match.“
For route aggregation to occur, addresses must be assigned so
that they are topologically significant.
80
Controlling the Growth of
Internet's Routing Tables
• Within a domain, detailed information is
available about all of the networks that reside
in the domain.
• Outside of an addressing domain, only the
common network prefix is advertised. This
allows a single routing table entry to specify81a
route to many individual network addresses.
Routing In a Classless Envir.
Organization A using ISP1 and its addresses
Organization A using ISP2 and ISP1’s addresses
82
Example Continued
• The "best" thing for the size of the Internet's routing tables would
be to have Organization A obtain a block of ISP #2's address space
and renumber.
• This would allow the eight networks assigned to Organization A to
be hidden behind the aggregate routing advertisement of ISP #2.
• Unfortunately, renumbering is a labor-intensive task which could be
very difficult, if not impossible, for Organization A.
•
•
Let the ISP2 inject a specific route 200.25.16.0/21 to the Internet
Longest prefix match algorithms will make sure that Org A traffic
will go through ISP2 at the expense of specific routes in the routing
83
table
Address Allocation in the
Private Internet
 RFC 1918 requests that organizations make use of the private
Internet address space for hosts that require IP connectivity
within their enterprise network, but do not require external
connections to the global Internet.
 For this purpose, the IANA has reserved the following three
address blocks for private internets:



10.0.0.0 - 10.255.255.255 (10/8 prefix)
172.16.0.0 - 172.31.255.255 (172.16/12 prefix)
192.168.0.0 - 192.168.255.255 (192.168/16 prefix)
 Any organization that elects to use addresses from these
reserved blocks can do so without contacting the IANA or an
Internet registry.
 Since these addresses are never injected into the global
Internet routing system, the address space can simultaneously
be used by many different organizations.
 The disadvantage to this addressing scheme is that it requires
an organization to use a Network Address Translator (NAT).
84
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.4
10.0.0.1
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
85
NAT: Network Address Translation
 Motivation: local network uses just one IP address as
far as outside word is concerned:
 no need to be allocated range of addresses from ISP:
- just one IP address is used for all devices
 can change addresses of devices in local network
without notifying outside world
 can change ISP without changing addresses of
devices in local network
 devices inside local net not explicitly addressable,
visible by outside world (a security plus).
86
NAT: Network Address Translation
Implementation: NAT router must:



outgoing datagrams: replace (source IP address, port
#) of every outgoing datagram to (NAT IP address,
new port #)
. . . remote clients/servers will respond using (NAT
IP address, new port #) as destination addr.
remember (in NAT translation table) every (source
IP address, port #) to (NAT IP address, new port #)
translation pair
incoming datagrams: replace (NAT IP address, new
port #) in dest fields of every incoming datagram
with corresponding (source IP address, port #)
stored in NAT table
87
NAT: Network Address Translation
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
2
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3: Reply arrives
dest. address:
138.76.29.7, 5001
3
1
10.0.0.4
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
10.0.0.1
10.0.0.2
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
88
NAT: Network Address Translation
 16-bit port-number field:

60,000 simultaneous connections with a single
LAN-side address!
 NAT is controversial:
 routers
should only process up to layer 3
 violates end-to-end argument
• NAT possibility must be taken into account by app
designers, eg, P2P applications
 address
IPv6
shortage should instead be solved by
89
ICMP: Internet Control Message Protocol
 used by hosts & routers to
communicate network-level
information
 error reporting:
unreachable host, network,
port, protocol
 echo request/reply (used
by ping)
 network-layer “above” IP:
 ICMP msgs carried in IP
datagrams
 ICMP message: type, code plus
first 8 bytes of IP datagram
causing error
Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
description
echo reply (ping)
dest. network unreachable
dest host unreachable
dest protocol unreachable
dest port unreachable
dest network unknown
dest host unknown
source quench (congestion
control - not used)
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
90