Transcript IP (old) - Rudra Dutta

CSC/ECE 573
Internet Protocols
IP - Addressing and Forwarding
Design Principles
(Names and Addresses)
1. No hardcoded addresses
2. Single naming structure
3. Addresses must be unambiguous
4. Upper-layer protocols must be able to identify end-
points unambiguously
5. Standardize on compact, binary addresses that
make computations (e.g., selection of a route)
efficient
6. Name should be case-insensitive ASCII
Copyright Rudra Dutta, NCSU, Spring, 2005
2
Internet Addresses
32-bit addresses
Each Internet host has one globally unique IP addresses
that is used in all communication with that host. But…



the IP address may change (dial-in)
may have several addresses (routers  multi-homed hosts)
an IP address specifies an interface (network connection), not a
host!
Two-level hierarchy (initially)  three-level (later)

2-level addressing: (network, host)
Class A, B, or C (initially)  Classless interdomain routing
(CIDR) (later)

aggregation, routing based on prefix and mask
Copyright Rudra Dutta, NCSU, Spring, 2005
3
IP Address Classes
Copyright Rudra Dutta, NCSU, Spring, 2005
4
IP Address Classes (cont'd)
Class
First Byte
# Networks
Hosts per
Network
Comments
A
< 128
27 (128)
224 –2 (16M)
Mostly used
B
128…191
214 (16384)
216 – 2 (65534)
Mostly used
C
192…223
221 (2M)
228 – 2 (254)
D
224…239
228 (268M)
-
Dynamic,
multicast
E
240…255
227 (134M)
-
reserved
Copyright Rudra Dutta, NCSU, Spring, 2005
5
IP Address Space Allocation and Use
http://www.caida.org/outreach/resources/learn/ipv4space/
Copyright Rudra Dutta, NCSU, Spring, 2005
6
Dotted decimal notation
Host Name
myhost.csc.ncsu.edu
32-bit address
1001 1000 0000 0001 0011 0110 0011 0000
Dotted decimal
152.1.54.48
Copyright Rudra Dutta, NCSU, Spring, 2005
7
Special Case IP Addresses
Net ID
Host ID
Appear as
Source?
Appear as
Destination?
Description
0
0
OK
Never
This host on this net
0
hostID
OK
Never
Another host on this net
127
Anything
(usually 1)
OK
OK
Loopback address
All 1’s
All 1’s
Never
OK
Limited broadcast (local
net)
netID
All 1’s
Never
OK
Directed broadcast to
netID
Copyright Rudra Dutta, NCSU, Spring, 2005
8
Special Case IP Addresses (cont'd)
Loopback interface



used in testing TCP/IP and for inter-process communication
on the local machine
packet sent to a net 127 address should never appear on
any network
hosts/routers should never propagate routing/reachability
info for network 127
Using 0s for the network ID




only allowed at startup (during the bootstrap procedure)
allows a machine to communicate temporarily
once a machine learns its own IP address it must not use
network 0
Host id = 0: used to refer to the network
Copyright Rudra Dutta, NCSU, Spring, 2005
9
Problems with IP Addresses
If a host moves to a new network, its IP address
changes
Limited address space
Class thresholds, e.g., what if a class C net grows
beyond 254 hosts?
Routing structure is not hierarchical, but flat



requires one routing table entry per network
too many networks
Improvement: CIDR
“Multi-homed” hosts: path taken to a host depends on
the destination IP address used
Copyright Rudra Dutta, NCSU, Spring, 2005
10
ifconfig Command
Used to configure or query a network interface on a host

NOTRAILERS  trailer encapsulation is not used
myhost % ifconfig –a
le0: flags=63<UP,BROADCAST,NOTRAILERS,RUNNING>
inet 152.1.54.48 netmask ffffffc0 broadcast 152.1.54.63
lo0: flags=49<UP,LOOPBACK,RUNNING>
inet 127.0.0.1 netmask ff000000
Copyright Rudra Dutta, NCSU, Spring, 2005
11
netstat Command
myhost % netstat -in
Name Mtu
Net/Dest
Address
Ipkts Ierrs Opkts Oerrs Collis Queue
le0
1500 152.1.54.0 152.1.54.48 95945 173
45215 5477
109995 0
lo0
1536 127.0.0.0
2273
0
127.0.0.1
2273
0
0
0
Provides information about the interfaces on a system








“-i” means print interface information
“-n” means print IP addresses instead of host names
“IPKTS” = # of input packets
“Ierrs” = # of input errors
“Opkts” = # of output packets
“Oerrs” = # of output errors
“Collis” = # of collisions on the ethernet
“Queue” = current size (packets) of the output queue
Copyright Rudra Dutta, NCSU, Spring, 2005
12
Network Byte Order
“Little Endian” vs. “Big Endian”



Different machine architectures store the bytes of a multibyte word in different orders
most significant byte first = big endian
least significant byte first = little endian
Header info (addresses, packet length, etc.) must be
understood by both sender and receiver
Network standard byte order: send most significant
byte first ( Big-Endian style)
User data is exempt from the standard
Copyright Rudra Dutta, NCSU, Spring, 2005
13
Original IP Addressing
(net_id, host_id) pair, three classes, but




Class A (16M hosts) too large for most sites
Class C (254 hosts) too small
Class B (65,534 hosts) is OK
the “Goldilocks” problem
Organizations requested Class B addresses to avoid
outgrowing the 8-bit host field of Class C:


only 65,534 Class B addresses  not enough
more than half of all Class B networks have fewer than 50
hosts (!)

inefficient use
Copyright Rudra Dutta, NCSU, Spring, 2005
14
Hypothetical Solution 1
Class C networks use 10-bit host_id


1022 hosts
Most organizations would have settled for a Class C address
512K Class C networks leads to routing table explosion
Storage of 512K entries is not the problem



complexity of routing algorithms grows faster than linear
administrative overhead of managing network addresses
routers must exchange their tables



larger messages
more frequent updates, routing instabilities
higher probability of loss
Router software designed when number of nets ~= 1,000

design choices made then are far from optimal now
Copyright Rudra Dutta, NCSU, Spring, 2005
15
Hypothetical Solution 2
Deeper hierarchy

Country, state, city, network, host fields
Even more inefficient use of addresses (small
vs. large countries)
need more than 32 bits  IPv6
Copyright Rudra Dutta, NCSU, Spring, 2005
16
Problems with IP Addressing
Large number of networks  routing table
size

temporary fix: same IP prefix must be shared by
multiple physical networks
Exhaustion of Class B addresses

temporary fix: use multiple class C addresses
instead
Copyright Rudra Dutta, NCSU, Spring, 2005
17
Requirements for Address
Extensions
Any solution should not destroy the original
addressing scheme

“backwards compatibility”
Sites are free to modify addresses in any way,
provided that:


all hosts/routers at site agree to use the new addressing
scheme
other sites can treat addresses as in the “classic” scheme
Routing algorithms must be modified to handle
addressing extensions
Copyright Rudra Dutta, NCSU, Spring, 2005
18
Subnet Addressing
Standardized in RFCs 950, 1122

Hosts must support
Relates to class B addresses mostly, although it can
also be used with class A and C addresses
Large organizations may have multiple LANs, sharing
a single IP network address


System administrator may (a) decide to subnet, and (b) how
many bits to allocate to subnet ID and host IDs
Class B example:
0
10
Copyright Rudra Dutta, NCSU, Spring, 2005
16
Net ID
24
Subnet ID
31
Host ID
19
Subnet Addressing (cont'd)
Result: three-level hierarchical addressing



enables more hierarchical routing
hides internal network structure from outside world
reduces the size of routing tables
Copyright Rudra Dutta, NCSU, Spring, 2005
20
Non-subnetted Example
Copyright Rudra Dutta, NCSU, Spring, 2005
21
Subnetted Example
Copyright Rudra Dutta, NCSU, Spring, 2005
22
Subnet Masks
Masking: the process of extracting the address of the physical
network from an IP address
A mask is a 32-bit number. Bits are set to…


1, indicating the corresponding bit of the IP address is part of the
network address (net ID or subnet ID)
0, indicating the corresponding bit of the IP address is part of the
host ID
Based on first bits of the IP address, you can always figure out
how long (how many bits) the network ID is
With a subnet mask, you can also figure out what the subnet ID
is
Copyright Rudra Dutta, NCSU, Spring, 2005
23
Applying Bitwise-AND Operator
Copyright Rudra Dutta, NCSU, Spring, 2005
24
Subnet Masks
Apply bitwise-AND operation on IP address and
mask to find the net ID and subnet ID
How can you tell if a destination IP address is…


On the same subnet as you?
On the same network as you?
IP Address =
Network Mask =
Net ID =
141.14.2.21
255.255.0.0
141.14
IP Address =
Subnet Mask =
Net ID =
Subnet ID =
141.14.2.21
255.255.255.0
141.14
2
Copyright Rudra Dutta, NCSU, Spring, 2005
25
Special Addresses in Subnetting
Appear
Appear as
as
Destination?
Source?
Net
ID
Subnet
ID
Host
ID
netID
subnetID
All
1’s
Never
OK
Subnet-directed broadcast
to netID, subnetID
netID
All 1’s
All
1’s
Never
OK
All-subnets-directed
broadcast to netID
Copyright Rudra Dutta, NCSU, Spring, 2005
Description
26
Subnet Routing
In a site using subnet addressing all hosts and
routers must use a modified algorithm for routing
Guidelines:

the same mask must be used throughout an entire set of
physical nets sharing a single Class B IP address


a site must use contiguous subnet masks -- a string of 1s
must precede a string of 0s


Can we do it another way?
Can we do it another way?
all machines should participate in subnet routing
Copyright Rudra Dutta, NCSU, Spring, 2005
27
Variable-Length Subnetting
Site with a Class C address 192.15.34.0, needs five
subnets with 60, 60, 60, 30, and 30 hosts
Problems


Cannot use subnet mask 255.255.255.192, since it allows 4
subnets each with (28/ 4) - 2 = 62 hosts
Cannot use subnet mask 255.255.255.224, since it allows 8
subnets each with (28 / 8) - 2 = 30 hosts
Solution: use two masks of different lengths


Router requirements RFC 1993 requires support for this
However, not all routing protocols exchange the subnet
mask along with the destination network ID
Copyright Rudra Dutta, NCSU, Spring, 2005
28
Variable-Length Subnetting
Copyright Rudra Dutta, NCSU, Spring, 2005
29
In-class Work
Given the following IP address and associated mask, answer the
questions below:
IP Address :
Mask :
10101000 00110001 11001110 00111100
11111111 11111111 11110000 00000000
(a) Write down the dotted decimal form of the IP address.
(b) Do not consider CIDR. Is subnetting being used?
(c) Assume supernetting is not being used. What is the subnet
ID? Give both binary and decimal representations.
(d) Could you answer part (c) without the assumption? How or
why not?
(e) What is the host ID? Give both binary and decimal
representations.
Copyright Rudra Dutta, NCSU, Spring, 2005
30
In-class Work
A Class B site has 30 physical networks
120 hosts in each network
What are possible subnet masks to use?

There are several
Which one should we use? Why?
What happens if number of networks
increases to 40?
What if the 10 new networks have 200 hosts
each?
Copyright Rudra Dutta, NCSU, Spring, 2005
31
Supernet Addressing
Exhaustion of Class B addresses  use Class C
addresses instead
Organizations assigned blocks of 2n contiguous
Class C addresses:

if 2000 addresses (hosts) are needed, allocate a block of
2048 addresses (8 contiguous Class C networks)
ISPs can use this scheme effectively

“supernetting”
Problem = routing table size explosion

better: discard class boundaries altogether
Copyright Rudra Dutta, NCSU, Spring, 2005
32
Supernetting Example
Copyright Rudra Dutta, NCSU, Spring, 2005
33
Classless InterDomain Routing
(CIDR)
Basic idea: allocate multiple IP addresses in a way
that results in a smaller number of routing table
entries

IP addresses must share the same high-order bits
A block of contiguous addresses is collapsed, or
summarized, into a single routing table entry of the
form (network_address, count), such that


network_address: the smallest address in the block
count: total number of addresses in the block
Copyright Rudra Dutta, NCSU, Spring, 2005
34
Classless InterDomain Routing
(cont’d)
Not restricted to Class C addresses


old Class A, B, C networks no longer used with
CIDR
“classless”
In reality, “count” not used


size of each block is a power of two
32-bit mask indirectly specifies the size of the
block
Copyright Rudra Dutta, NCSU, Spring, 2005
35
Defining a Supernet
Copyright Rudra Dutta, NCSU, Spring, 2005
36
Supernet Mask vs. Subnet Mask
Copyright Rudra Dutta, NCSU, Spring, 2005
37
CIDR Example
Block of 131,072 Class C networks (32M total
addresses), starting at 194.0.0.0
Address
Dotted Decimal
Binary
Lowest
194.0.0.0
11000010 00000000 00000000 00000000
Highest
195.255.255.255
11000011 11111111 11111111 11111111
Mask
254.0.0.0
11111110 00000000 00000000 00000000
Copyright Rudra Dutta, NCSU, Spring, 2005
38
Allocation of Class C Address Space
Lowest
Highest
Allocation
194.0.0.0
195.255.255.255
Europe
198.0.0.0
199.255.255.255
North America
200.0.0.0
201.255.255.255
Central and South America
202.0.0.0
203.255.255.255
Asia and the Pacific
204.0.0.0
223.255.255.255
Reserved
All sites in Europe have a common prefix
CIDR summarizes 32M addresses into one entry

only a single entry needed in most U.S. routers
Once the packet gets to Europe, more detailed routing
tables are needed
Copyright Rudra Dutta, NCSU, Spring, 2005
39
CIDR Example
Three sites in Europe ask for 2048, 1024, and 4096
addresses, respectively
Site
Lowest
Highest
Mask
“Count”
1
194.24.0.0
194.24.7.255
255.255.248.0
2048 = 211
2
194.24.8.0
194.24.11.255
255.255.252.0
1024 = 210
3
194.24.16.0
194.24.31.255
255.255.240.0
4096 = 212
Copyright Rudra Dutta, NCSU, Spring, 2005
40
CIDR Example (cont'd)
Routers all over Europe are now updated with three
entries:
Network Address
Mask
Next
Hop
11000010 00011000 00000000 00000000
11111111 11111111 11111000 00000000
R1
11000010 00011000 00001000 00000000
11111111 11111111 11111100 00000000
R2
11000010 00011000 00010000 00000000
11111111 11111111 11110000 00000000
R3
Copyright Rudra Dutta, NCSU, Spring, 2005
41
CIDR Example (cont'd)
Packet comes in addressed to 194.24.17.4:
IP address of packet in binary =
11000010 00011000 00010001 00000100
Boolean ANDed with Site 1 mask =
11000010 00011000 00010000 00000000

does not match Site 1 base address
Boolean ANDed with Site 2 mask =
11000010 00011000 00010000 00000000

does not match Site 2 base address
Boolean ANDed with Site 3 mask =
11000010 00011000 00010000 00000000

matches Site 3 base address  sent to R3
Copyright Rudra Dutta, NCSU, Spring, 2005
42
CIDR Routing
Router entries not tried sequentially; indexing tricks used
Longest prefix match

if two entries match, the one whose mask has the most 1 bits wins
Studies claim that if:



CIDR were applied to all IP addresses, and
existing IP addresses were reallocated according to continental
boundaries/ISPs
Then routing table entries could be reduced to 200 (from more than
10,000 currently)
Short-term solution

long-term solution: IPv6
Copyright Rudra Dutta, NCSU, Spring, 2005
43
IP Forwarding
IP: Contextless One-hop Forwarding
Roughly layer 3 functionality
Router-to-router, or between router and
host
Contextless or connectionless paradigm


Each packet forwarded independently
Low overhead
Unreliable


Possible error, loss, reordering, duplication
Not necessarily bad
Copyright Rudra Dutta, NCSU, Spring, 2005
45
IP Header
Various fields have different uses

Version
(4)
Not all are used by core IP
Hdr Len
(4)
TOS (8)
Identification (16 bits)
Time to Live (8)
Total Length in bytes (16)
Flags (3)
Protocol (8)
Fragment Offset (13)
Header Checksum (16)
Source IP Address
Destination IP Address
Options (if any)
PAD
Data Field
Copyright Rudra Dutta, NCSU, Spring, 2005
46
One-hop delivery
It is assumed that physical net methods can be used

But physical net capabilities might differ
Maximum Transmission Unit (MTU)



Largest IP packet a network will accept
Arriving IP packet may be larger
Solution: break into several packets

That is, “fragment”
MTU
IP Packet
Copyright Rudra Dutta, NCSU, Spring, 2005
47
Multiple Fragmentations
Original packet may be fragmented
multiple times along its route
Source
Host
Internet
Process
Destination
Host
Internet
Process
Fragmentation
Copyright Rudra Dutta, NCSU, Spring, 2005
49
Defragmentation
Internet layer process on destination host
defragments, restoring the original packet
IP Defragmentation only occurs once
Source
Host
Internet
Process
Destination
Host
Internet
Process
Defragmentation
Copyright Rudra Dutta, NCSU, Spring, 2005
50
Fragment Offset Field
Fragment offset field (13 bits) is used to
reorder fragments with the same
Identification field
Contains the data field’s starting point
(in octets) from the start of the data field
in the original IP packet
Version
(4)
Hdr Len
(4)
TOS (8)
Identification (16 bits)
Copyright Rudra Dutta, NCSU, Spring, 2005
Total Length in bytes (16)
Flags (3)
Fragment Offset (13)
54
Multihop - IP Forwarding
Routers look at destination IP address
of packet to make decisions
What do I do with this packet, based
upon its IP destination address only
B
B?
D?
Router A
D
Packet
Copyright Rudra Dutta, NCSU, Spring, 2005
C?
C
56
IP Forwarding Revisited
If Destination Host is NOT On One of the
Router’s Subnets, the Router Sends the
Packet to a Next-Hop Router for Delivery

Routing decision – which one ?
Subnet
Subnet
Copyright Rudra Dutta, NCSU, Spring, 2005
57
Simple-minded Network
Routers deliver packet to another router, and
forget about it

Forwarding table provides a mapping
Forward the packet to somebody else

Make it somebody else’s problem
Hence, forwarding vs. routing
Forwarding

This mechanism (what IP does)
Routing

Setting the forwarding tables
Copyright Rudra Dutta, NCSU, Spring, 2005
58
Multiple Matches
Longest Match Principle



Must select one row to determine delivery
If two rows match, use longest match, that is
match to greatest number of bits
For 128.171.17.13, use local delivery (24-bit
match)
Net/Subnet
Mask
Destination
128.171.17.0 24
Local
128.171.0.0
Next-Hop
Router A
Copyright Rudra Dutta, NCSU, Spring, 2005
16
62
Nothing Matches
Syntactic solution
Always include 0.0.0.0 as net and mask
for (at least) one rule
 At least this rule will always match

Copyright Rudra Dutta, NCSU, Spring, 2005
64
Default routes – significance of 0.0.0.0 Rule
Strictly speaking, need next hop
information for every network in the
Internet

Order of 100,000 now
Instead, keep detailed routes only for
local neighborhood
For unknown destinations, use a default
router
 Reduces size of routing tables at the
expense of non-optimal paths
 Move towards hierarchy

Copyright Rudra Dutta, NCSU, Spring, 2005
65
Forwarding Table Selection Rules
Compare destination IP address of an arriving
packet against ALL rows within the router
forwarding table because there may be multiple
matches
Select a single row that matches
If multiple rows match, select the longest match
If multiple rows tie on the longest match, select the
row with the largest or smallest metric, depending
on the specific metric
(If there is no match, select the default row)
Copyright Rudra Dutta, NCSU, Spring, 2005
66
In class question
How will these rules need to be
modified for CIDR forwarding?

Only asking about forwarding
Copyright Rudra Dutta, NCSU, Spring, 2005
67
In-class Work
Line
Destination Address Netmask Metric (Cost)
Interface Next-Hop Router
1
2
3
4
5
6
7
8
9
10
11
12
152.19.0.0
152.15.33.0
152.1.0.0
152.40.0.0
152.229.0.0
152.40.6.0
152.19.17.0
152.229.0.0
152.40.8.0
152.15.12.0
152.15.122.0
0.0.0.0
2
1
2
2
1
3
4
3
1
2
3
3
16
24
16
16
16
24
24
16
24
24
24
0
47
0
12
33
34
47
55
20
23
9
3
5
B
Local
B
B
D
E
H
E
D
Local
Local
H
Default router?
152.1.1.211 – which router/rule?
152.15.12.99 ?
152.40.8.44 ?
125.1.2.3 ?
Copyright Rudra Dutta, NCSU, Spring, 2005
68
The Forwarding Engine
Copyright Rudra Dutta, NCSU, Spring, 2005
69