Transcript IP: Routing and Subnetting

IP: Routing and Subnetting
Network Protocols and Standards
Autumn 2004-2005
Oct 26, 2004
CS573: Network Protocols and Standards
1
Routing IP Datagram

Direct Delivery (i.e., not involving routers):




Transmission of an IP datagram between two machines on a
single physical network does not involve routers
The sender encapsulates the datagram in a physical frame,
binds the destination IP address to a physical hardware
address (using ARP), and sends the resulting frame directly
to the destination
The two machines are known to be on the same network
because they have the same network identifier
Router
Example:

Oct 26, 2004
A sends IP Datagram to B
A
CS573: Network Protocols and Standards
B
C
2
Routing IP Datagram

Indirect delivery (i.e. through intermediate
routers)




Oct 26, 2004
Host performs routing decisions based on routing
table indicating “next hop”
“Next hop” refers to next router IP address on this
network, via which the destination is reached
Routing decisions are made based on network
prefixes (not full IP address)
The sender encapsulates the datagram in a frame
with the router’s physical destination address
(which is found by means of ARP).
CS573: Network Protocols and Standards
3
Direct and Indirect Routing
B wants to send packets to A and C!
Host A
204.240.18.10
204.240.18.1
Direct Routing:
Packets sent directly using
MAC address of A
Host B
204.240.18.20
Router
Internet
Indirect Routing:
Packets sent to the MAC address
of the router. At the IP level, B is
the source and C is the destination
Host C
36.14.0.200
Oct 26, 2004
CS573: Network Protocols and Standards
4
IP Routing Decisions
10.0.0.5
Network
10.0.0.0
20.0.0.6
20.0.0.5
R1
40.0.0.7
30.0.0.6
R3
Network
20.0.0.0
Network
30.0.0.0
R2
30.0.0.7
Network
40.0.0.0
Routing Table of R2
Oct 26, 2004
To Reach Hosts on Network
Next Hop Address
20.0.0.0
Direct Delivery
30.0.0.0
Direct Delivery
10.0.0.0
20.0.0.5
40.0.0.0
30.0.0.7
CS573: Network Protocols and Standards
5
IP Routing Algorithm






Router receives an IP datagram with network portion N and
destination D
If N is directly connected
 Transmit on that network
Else If host specific entry for D exists
 Use next hop in that entry
Else If route entry for N exists
 Use next hop in that entry
Else If default route for next hop exists
 Use default route for next hop
Else
 Declare error
Oct 26, 2004
CS573: Network Protocols and Standards
6
Routing Within Same Network



Consider a small company with a single LAN
to which a class C network address has been
assigned
The company is interested in adding another
small physical network (connected to old
network through a router) with a few hosts
Question: Could this company assign these
hosts IP addresses from the same C class
network? i.e., could the two LANs share the
same class C network address?
Oct 26, 2004
CS573: Network Protocols and Standards
7
Proxy ARP
To Internet
Main Router
Main Network
A
B
C
Router R
D
E
Hidden Network



Used to allow two physical networks to share the same IP
network prefix
Router R’s table is configured manually to route between these
two networks
Router R answers ARP requests on each network for hosts on
the other network, giving its own hardware address as the
target address
Oct 26, 2004
CS573: Network Protocols and Standards
8
Proxy ARP

Advantage of Proxy ARP Router


Disadvantages:



Can be added without disturbing the routing table in other
hosts or routers on that network
Does not generalize to complex network topologies (does
not scale)
Does not support a reasonable form of routing. (relies on
network managers to maintain tables of machines and
addresses manually)
Issues:

Oct 26, 2004
Several IP addresses map to the same physical address.
How to distinguish between a legitimate Proxy ARP router
and spoofing?
CS573: Network Protocols and Standards
9
Issues in Addressing

A large corporate/campus environment

Large number of Local Area Networks



If each physical network is assigned a network
number:



Oct 26, 2004
Some with fewer than 256 hosts
Some with more than 256 hosts
Immense administrative overhead to manage a large
number of network addresses
Routing tables in routers become extremely large (one
entry for each physical network)
Insufficient number of class B prefixes to cover medium
sized networks (having more than 256 hosts)
CS573: Network Protocols and Standards
10
Subnetting

Solution: Provide the campus with a
single class B network



Oct 26, 2004
Give freedom to the campus network
admin to allocate host numbers to hosts
From outside, the whole campus is simply
known by the class B network ID
Inside, there may be a hierarchy that
remains transparent to the outside world
CS573: Network Protocols and Standards
11
Subnetting

Consider a class B network




Oct 26, 2004
How to allocate host numbers to hosts?
A single LAN is out of question
If host numbers are assigned randomly,
i.e., without any hierarchy, the routers
inside the network will have to deal with
large tables – one entry per host
Thus, a hierarchical structure is required
CS573: Network Protocols and Standards
12
Subnetting
H
H
H
H
R
R
R
Physical Network
(Subnet 2)
H
Physical Network
(Subnet 3)
R
Physical Network
(Subnet 1)
H
H
R
Physical Network
(Subnet 4)
H
H
Oct 26, 2004
H
H
H
CS573: Network Protocols and Standards
13
Subnetting
Network 138.10.1.0
H1
Internet
R
138.10.1.1
H2
138.10.1.2
Network 138.10.2.0
R is not a Proxy ARP router!
H3
138.10.2.1
Subnet 1
Subnet 2
H4
138.10.2.2
H1 wants to send an IP datagram to H3:
Old addressing dictates it is a “direct delivery”
With subnetting, it may become “indirect”
Oct 26, 2004
CS573: Network Protocols and Standards
14
Subnetting


We previously divided IP addresses in a network
portion and a host portion
More generally, think of a 32-bit IP address as having
an Internet part and a Local part


Internet part of the IP address identifies a site (possibly with
many physical networks)
The local portion identifies a physical network and host at
that site (note: physical network == extended LAN)
Internet Part
Internet Part
Oct 26, 2004
Local Part
Subnet
Host
CS573: Network Protocols and Standards
15
Subnetting
Examples: Class B IP address
Internet Part
16bits
Oct 26, 2004
Subnet
Host
8bits
8bits
Internet Part
Subnet
Host
16bits
3bits
13bits
CS573: Network Protocols and Standards
16
Subnet Implementation
Subnet Mask:
Specifies the bits of the IP address used to identify the subnet
Internet Part of Address
Subnet Mask
(32bits)
16bits
11111111
255.
11111111
255.
Internet Part of Address
11111111
255.
Oct 26, 2004
16bits
11111111
255.
Subnet
Host
8bits
11111111
8bits
00000000
255.
0
Subnet
3bits
111
00000
224.
Host
13bits
00000000
0
CS573: Network Protocols and Standards
17
Subnetting

It is recommended that sites use contiguous
subnet masks

Avoid masks such as
11111111 11111111 11000010 11000000

When choosing a subnet mask, balance:





Oct 26, 2004
Size of networks
Number of networks
Expected growth
Ease of maintenance
It is possible to use different masks in different
parts of the network
CS573: Network Protocols and Standards
18
Subnet Routing

Conventional routing table entry

(network address, next hop address)


Network address format is predetermined for a given
class (e.g., first 16 bits for class B addresses!)
With subnetting, routing table entry becomes


(subnet mask, network address, next hop
address)
Then compare with network address field of
entries to find next hop address

Oct 26, 2004
Subnet mask indicates the network address!
CS573: Network Protocols and Standards
19
Subnet Routing

The use of mask generalizes the subnet routing algorithm to
handle all the special cases of the standard algorithm






Routes to individual hosts
Default route
Routes to directly connected networks
Routes to conventional networks (that do not use subnet
addressing)
Merely combine the 32-bit mask field with the 32-bit IP address
Example: To install a route for:



Oct 26, 2004
Individual host (Mask of all 1’s, Host IP address)
Default Route (Mask of all 0’s, network address all 0’s)
Class B network address (Mask of two octets of 1’s and two of 0’s)
CS573: Network Protocols and Standards
20
Subnet Routing

Algorithm



Extract destination IP (D) from datagram
Compute IP address of destination network N
If N matches any directly connected network address


Else



Oct 26, 2004
Send datagram over that network (obviously encapsulated in a
frame)
For each entry in the routing table, do
N* = bitwise-AND of D and subnet mask
If N* equals the network address field of the entry, then route
the datagram to the specified next hop
CS573: Network Protocols and Standards
21
Supernet Addressing


Use of many IP network addresses for a
single organization
Example:



To conserve class B addresses, issue multiple class
C address to the same organization
Issue: increase in the number of entries in the
routing table
Solutions:

Oct 26, 2004
Collapse a block of contiguous class C address into the
pair: (network address, count) where network address is
the smallest number in the block
CS573: Network Protocols and Standards
22
Supernet Addressing


It requires each block to be a power of 2 and
uses bit mask to identify the size of the block
Example
Dotted decimal





32-bit binary equivalent
Lowest: 234.170.168.0
11101010 10101010 10101000 00000000
Highest: 234.170.175.255
11101010 10101010 10101111 11111111
A block of 2048 addresses
32-bit mask is 11111111 11111111 11111000 00000000
Do we really need address classes when we have
masks?

Oct 26, 2004
Answer: NO  CIDR (Classless Inter Domain Routing)
CS573: Network Protocols and Standards
23
Supernet Addressing

In the router, the entry consists of:



Oct 26, 2004
The lowest address and the 32-bit mask
A block of addresses can be subdivided,
and separate route can be entered for each
subdivision
When looking up a route, the routing
software uses a longest-match paradigm to
select a route
CS573: Network Protocols and Standards
24
IPv6

Motivation


Limited address space
Support for new applications



Oct 26, 2004
Multimedia streams, for example
Security
Extensibility
CS573: Network Protocols and Standards
25
Features of IPv6

Larger addresses


Flexible header format


Set of optional headers
Support for flow identification


128 bit addresses
Needed in resource allocation for
multimedia streams
Provision for protocol extension
Oct 26, 2004
CS573: Network Protocols and Standards
26