CSS 432: Subnetting, CIDR, and GlobalInternet
1
CSS432 Subnetting and CIDRTextbook Ch3.2.5Global InternetTextbook Ch4.1
Professor: Munehiro Fukuda
CSS 432: Subnetting, CIDR, and GlobalInternet
2
Internet Structure
Autonomous System (AS):
Administered independently of other AS
Have a different routing protocol and metrics
Do we really need to give an independent class A/B/C network number to everysingle AS?
NSFNET backbone
Stanford
BARRNET
regional
Berkeley
P
ARC
NCAR
UA
UNM
Westnet
regional
UNL
KU
ISU
MidNet
regional
…
CSS 432: Subnetting, CIDR, and GlobalInternet
3
Scaling Issues in Routing
Inefficient use of IP Address Space
Class C with 2 hosts (2/255 = 0.78% efficient)
Class B with 256 hosts (256/65535 = 0.39% efficient)
IP address space gets consumed too quickly
Too Many Networks
Routing tables do not scale
Route propagation protocols do not scale
Router gets slower to scan a big forwarding table
Hierarchy
CSS 432: Subnetting, CIDR, and GlobalInternet
4
Subnetting - Concept
Problem: Internet identifies only classes
Four networks must receive an independent class of network number, (whichexhausts IP addresses and floods network #s.)
Subnet: collects networks belonging to the same AS and give a single class ofnetwork number, which is then divided into subnet numbers internally.
Flat networks
A collection of subnets
40 nodes: Class C
200 nodes: Class C
256 nodes: Class B
Internet
IAS
128.96.36.1-200
BBUS
128.96.35.1-40
EDU
128.96.34.1 - 30
CSS
128.97.0.1 – 128.97.1.2
30 nodes: Class C
40 nodes
Subnet: 128.97.2.0
200 nodes
Subnet: 128.97.3.0
256 nodes
Subnet: 128.97.4.0
Internet
IAS
128.97.3.1-200
BBUS
128.97.2.1-30
EDU
128.97.1.1-30
CSS
128.97.4.1 – 128.97.5.2
30 nodes
Subnet: 128.97.1.0
Class B: 128.97.0.0
CSS 432: Subnetting, CIDR, and GlobalInternet
5
Subnetting – How to Address
Subnet masks define variable partition of host part
Subnets visible only within site
Network number
Host number
Class B address
Subnet mask (255.255.255.0)
Subnetted address
111111111111111111111111
00000000
Network number
Host ID
Subnet ID
127.97.0.1 – 127.97.255.254
127.97.8.254/24
Subnet ID
# of bits in subnet mask
CSS 432: Subnetting, CIDR, and GlobalInternet
6
Subnetting – How to Address
#bits
Subnetwork Mask
#subnets in Class B
#subnets in Class C
# of hosts
16
255.255.0.0
1
-
65534
17
255.255.128.0
-
-
32766
18
255.255.192.0
2
-
16382
19
255.255.224.0
6
-
8190
20
255.255.240.0
14
-
4094
21
255.255.248.0
30
-
2046
22
255.255.252.0
62
-
1022
23
255.255.254.0
126
-
510
24
255.255.255.0
254
1
254
25
255.255.255.128
510
0
126
26
255.255.255.192
1022
2
62
27
255.255.255.224
2046
6
30
28
255.255.255.240
4094
14
14
29
255.255.255.248
8190
30
6
30
255.255.255.252
16382
62
2
31
255.255.255.254
32766
126
-
32
255.255.255.255
65534
254
-
Note: subnet all 0’s and all 1’s are not recommended
CSS 432: Subnetting, CIDR, and GlobalInternet
7
Subnet Example
Forwarding table at router R1
Subnet Number Subnet Mask Next Hop
128.96.34.0 255.255.255.128 interface 0
128.96.34.128 255.255.255.128 interface 1
128.96.33.0 255.255.255.0 R2
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.0/25
128.96.34.15
128.96.34.1
H1
R1
128.96.34.130
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.128/25
128.96.34.129
128.96.34.139
R2
H2
128.96.33.1
128.96.33.14
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0/24
H3
IP address & subnet mast = subnet number
Example: 128.96.34.15 & 255.255.255.128
= 128.96.34.0
CSS 432: Subnetting, CIDR, and GlobalInternet
8
Forwarding Algorithm
D = destination IP address
for each entry (SubnetNum, SubnetMask, NextHop)
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to destination
else
deliver datagram to NextHop (a router)
Use a default router if nothing matches
Not necessary for all 1s in subnet mask to be contiguous
But should be avoided
Can put multiple subnets on one physical network
Ex. Two or more departments want to have their own subnet and toallocate IP addresses in it while sharing just one physical network
Subnets not visible from the rest of the Internet
CSS 432: Subnetting, CIDR, and GlobalInternet
9
Supernetting
Subnetting
Purpose: divide a large class of network number into subnetwork numbers → help assign address carefully.
Problem: an AS with more than 255 hosts still needs class B.
Supernetting
Solution: assign block of contiguous network numbers to aninstitution.
Ex. Assign two class C network numbers instead of one class Bnetwork.
Side effect: The information routers store and exchangeincreases dramatically
Ex. If an AS has 16 class C network numbers, every Internetrouter needs 16 entries for this AS.
CIDR: Classless Inter-Domain Routing
CSS 432: Subnetting, CIDR, and GlobalInternet
10
CIDR
Basic concept of supernetting using class C:
Represent blocks with a single pair
(first_class_C_network_address, count)
Example (192.5.48.0, 3)
Points to a group of blocks such as 192.5.48.0,192.5.49.0, and 192.5.50.0
In practice
No restriction to class C nor use of count
Restrict block sizes to powers of 2
Use a bit mask (CIDR mask) to identify block size
Ex. An AS assigned a block of 2048 contiguous addresses starting at128.211.168.0, (i.e., a collection of 8 class C networks)
Lowest128.211.168.010000000 11010011 10101000 00000000
Highest128.211.175.25510000000 11010011 10101111 11111111
CIDR mask (21bits)11111111 11111111 11111000 00000000
Address Notation:128.211.168.0/21
CSS 432: Subnetting, CIDR, and GlobalInternet
11
Classless Addressing Examples
CIDR allows to aggregate routes repeatedly
Then, what if there is a router capable of forwarding packets both to the regionalnetwork and to the cooperation Z?
PrefixNext Hop
192.4.0.0/18the regional network
192.4.48.0/20corporation Z
To which of those two should we forward a packet destined to 192.4.48.3?
Use Principle of Longest Match
Regional network
Corporation Y
11000000 00000100 0001
192.4.16.0/20
Corporation X
11000000 00000100 0000
192.4.0.0/20
Internet
backbone
Border gateway
11000000 00000100 00
192.4.0.0/18
Corporation Z
11000000 00000100 0011
192.4.48.0/20
CSS 432: Subnetting, CIDR, and GlobalInternet
12
Classless Lookup
Binary Tree for IP Routing
Patricia Tree for IP Routing
192.4.0.0/1811000000 00000100 00
192.4.48.0/2011000000 00000100 0011
128.4.0.0/1810000000 00000100 00
65.4.0.0/1401000001 000001
0
1
1
0
1
0
0
0
0
0
0
0
1
1
0
1
0
1
0
0
Skip 10
1
1
1
Skip 4
65.4.0.0/1401000001 000001
128.4.0.0/1810000000 00000100 00
192.4.0.0/1811000000 00000100 00
192.4.48.0/2011000000 00000100 0011
CSS 432: Subnetting, CIDR, and GlobalInternet
13
Route Propagation
Know a smarter router
Hosts know local (default) routers
Local routers know site routers
Site routers know core router
Core routers know everything
Site routers are called border routers.
Autonomous System (AS)
Corresponds to an administrative domain
Examples: University, company, backbone network
Two-level route propagation hierarchy
Interior gateway protocol (each AS selects its own)
Exterior gateway protocol (Internet-wide standard)
NSFNET backbone
Stanford
BARRNET
regional
Berkeley
P
ARC
NCAR
UA
UNM
Westnet
regional
UNL
KU
ISU
MidNet
regional
…
AS1
AS2
R1
R2
Exterior
Interior
CSS 432: Subnetting, CIDR, and GlobalInternet
14
Popular Interior Gateway Protocols
RIP: Route Information Protocol
Distributed with Unix
Distance-vector algorithm
Based on hop-count
OSPF: Open Shortest Path First
Recent Internet standard
Uses link-state algorithm
Supports load balancing
Supports authentication
CSS 432: Subnetting, CIDR, and GlobalInternet
15
Well-known Exterior Gateway Protocol
Border Gateway Protocol – 4th Version (BGP-4)
Assumption: Internet as an arbitrarily interconnected setof ASs
Goal: Reachability than optimality
Backbone service provider
Peering
point
Peering
point
Large corporation
Large corporation
Small
corporation
“
Consumer
”
ISP
“
Consumer
”
ISP
“
Consumer
”
ISP
Stub AS:
A single connecitoin to another AS
Only carries local traffic.
Multihomed AS:
Connections to multi ASs
Refuses to carry transit traffic
Transit AS:
Connections to multi-ASs
Carries both transit and local traffic.
CSS 432: Subnetting, CIDR, and GlobalInternet
16
BGP-4
Each AS has:
one or more border routers
one BGP speaker that advertises:
local networks
other reachable networks (transit AS only)
gives complete path information
Characteristics
Inter-BGP speaker communication based on P2P and TCP
Consistent maintenance on routing information among multiple BGPspeakers
Reachability-based information
Policy Support to distinguish between intra- and inter-AS reachabilityinformation
Incremental updates that sends only reachability change
Route aggregation to send multiple routes in one message
Authentication to allow a receiver to authenticate messages
CSS 432: Subnetting, CIDR, and GlobalInternet
17
BGP Example
Speaker for AS2 advertises reachability to P and Q
network 128.96, 192.4.153, 192.4.32, and 192.4.3, can bereached directly from AS2
Speaker for backbone advertises
networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can bereached along the path (AS1, AS2).
Speaker can cancel previously advertised paths
Backbone network
(AS 1)
Regional provider A
(AS 2)
Regional provider B
(AS 3)
Customer P
(AS 4)
Customer Q
(AS 5)
Customer R
(AS 6)
Customer S
(AS 7)
128.96
192.4.153
192.4.32
192.4.3
192.12.69
192.4.54
192.4.23
CSS 432: Subnetting, CIDR, and GlobalInternet
18
BGP Messages
BGP Speaker (sender)
BGP Speaker (receiver)
Timeline
OPEN( myAS#, timeRequiredToReceiveTheRestOfMessage, myIP, options)
KEEPALIVE( )
UPDATE( #Withdrawn, #MaskBits, IP, …., #NewPath, #MaskBits, IP, …., PathAttributes )
KEEPALIVE( )
Next UPDATE( ) or KEEPALIVE( )
Next UPDATE( ) or KEEPALIVE( )
NOTIFICATION(ErrorCode, ErroSubCode, Data)
Timer Interrupt
TCP connection
CSS 432: Subnetting, CIDR, and GlobalInternet
19
AS 102
AS 103
AS 101
(myself)
! Our AS number is 101, provide A’s is 102, provide B’s 103, and our firend’s is 777
router bgp 101
network 172.16.0.0
neighbor 172.16.1.1 remote-as 102 ! Provider A
neighbor 172.16.1.1 filter-list 81 weight 100 ! Traffic to our friend 777 uses provider A
neighbor 172.16.1.1 filter-list 82 out
neighbor 172.16.2.7 remote-as 103 ! Provider B
neighbor 172.16.2.7 filter-list 83 out
!
! Define an AS path access-list that selects our friend’s routes
ip as-path access-list 81 permit _777$ ! There is a path through A to our friend 777
!
! Define an AS path access-list that blocks provider B’s routes
ip as-path access-list 82 deny ^102_ ! Don’t let provider A use my network for transit
ip as-path access-list 82 permit .*
!
! Define an AS path access-list that blocks provider A’s routes
ip as-path access-list 83 deny ^103_ ! Don’t let provider B use my network for transit
Ip as-path access-list 83 permit .*
BGP Configuration for CiscoRouters
R_me
R_B
R_A
AS 777
(friend)
R_f
NO
at the end
at the beginning
CSS 432: Subnetting, CIDR, and GlobalInternet
20
Routing Areas
AS divided into areas
Area 0
Known as the backbonearea and connected to theback bone
Routers (R1, R2, R3) calledABR (Area Border Router)
OSPF link states
do not leave the area inwhich they originated if theyare not ABRs.
ABRs summarize routinginformation that they havelearned from one area andmake it available in theiradvertisements to otherareas.
R4
R5
R6
R2
R3
R1
R7
R8
R9
Area 0
Area 3
Area 2
Area 1
NO
Virtual Link
CSS 432: Subnetting, CIDR, and GlobalInternet
21
! Router 1 starts an OSPF process and place all interfaces in area 0
router ospf 1
network 0.0.0.0 255.255.255.255 area 0 ! Mask here means wild cards 0 or 1.
! Router 2 starts an OSPF process and place all interfaces in area 1
router ospf 1
network 0.0.0.0 255.255.255.255 area 0
! Router 3 starts an OSPF process and place in area1 the interface that is part
! of 172.168.48.0./22. Place all the other interfaces in area 0
router ospf 1
network 172.168.48.0 0.0.3.255 area 1 ! The last 10 bits may be 0 or 1
netwrok 0.0.0.0 255.255.255.255 area 0
OSPF Configuration for CiscoRouters
Router 1
Router 2
Router 3
Router 4
Router 5
172.168.48.0/24
172.168.50.0/24
172.168.0.0/24
172.168.49.0/24
CSS 432: Subnetting, CIDR, and GlobalInternet
22
IP Version 6
Features
128-bit addresses (classless)
multicast
real-time service
authentication and security
autoconfiguration
end-to-end fragmentation
protocol extensions
Header
40-byte “base” header
extension headers (fixed order, mostly fixed length)
fragmentation
source routing
authentication and security
other options
CSS 432: Subnetting, CIDR, and GlobalInternet
23
Reviews
Subnetting: How to address and forwarding algorithm
Supernetting: CIDR, principle of longest match, andclassless lookup
Exterior gateway protocol: BGP and routing areas
Exercises in Chapter 3
Ex. 55 (Subnetting)
Ex. 68 (CIDR)
Ex. 72 (CIDR)
Ex. 74 (CIDR)