CS716
Advanced Computer Networks
By Dr. Amir Qayyum
1


Lecture No. 24


Supernetting/CIDR
• CIDR: Classless Inter­Domain Routing
• Compromise in address utilization vs 
scalability
• Eliminate class notion; generalize 
subnet notion
• All routers must understand CIDR 
addressing
– Longest match in the table


Supernetting/CIDR

• Assign block of contiguous network 
numbers to nearby networks
– Restrict block sizes to powers of 2
– Use bit mask(CIDR mask) to identify 
block size


CIDR
• Specify network with (network#, mask bits)

– Equivalent to (network#, # of hosts)

• Block of 8 class C networks may be treated as one
• Organizations can still use subnetting internally !
• Routing table entries look like:
subnet #
131.126.141.0
131.126.142.0
131.126.142.128 25
131.126.0.0
default

24
25
16
0

mask length
next hop
Interface 0
Interface 1
R1
R2
R3


CIDR Growth
• CIDR/supernetting allows hierarchical 
development
• Assign block of addresses to regional 

provider (e.g., 128.0.0.0/9 to BARRNET)
• Regional provider subdivides addresses
• Can hand out to subregional providers (e.g., 
128.32.0.0/16 to Berkeley)
• Who in turn hand out to smaller organization 
(e.g., 128.32.32.0/21 to Berkeley CS Dept)


Routing in
Large Scale Networks


Route Propagation

• Know a smarter router

– Hosts know local router
– Local routers know site routers
– Site routers know core router
– Core routers know everything

• Autonomous System (AS)

– Corresponds to an administrative domain
– Examples: university, company, backbone 
network
– Assign each AS a 16­bit number


Route Propagation

• Two­level route propagation hierarchy

– Interior gateway protocol (each AS 
selects its own)
– Exterior gateway protocol (Internet­wide 
standard)

• AS’s represent a third hierarchy

– Define routing domains
– Based on notion of autonomy of control


Notion of Autonomous Systems (AS)
• Intradomain routing (within an AS)

– Performed using domain­specific 
algorithm
– Selected by domain administrator 
(autonomously)
– Allows heterogeneous interior gateway 
protocols

• Interdomain routing (between AS’s)

– Performed using standard global 
algorithm
– Homogeneous exterior gateway protocol



Intra­domain (Interior GW) Protocols
• Routing Information Protocol (RIP)
– From the early Internet, developed for 
XNS
– Part of Berkeley Software Distribution 
(BSD) Unix
– Distance­vector algorithm
– Based on hop count (infinity set to 16 
hops)


Intra­domain (Interior GW) Protocols

• Open Shortest Path First (OSPF)
– Internet standard (RFC 2328), 
“open” means public
– Based on link­state algorithm
– Authenticates messages
– Load balances across links


Inter­domain (Exterior GW) Protocols

• Very complex and difficult
– Different metrics, security, large 
scale: 140K prefixes!

• Focuses on reachability rather than 
optimality
– Support for very flexible policies



Inter­domain (Exterior GW) Protocols

• Exterior Gateway Protocol (EGP)
– Defined on Internet with tree structure
– Embodied (and enforced) tree 
structure
– Had to be replaced eventually
– Used distance­vector updates
– Replaced by Border Gateway Protocol 
(BGP)


EGP Messages
• Neighbor acquisition
– One router requests that another be its peer
– Peers exchange reachability information

• Neighbor reachability
– One router periodically tests if the another is 
still reachable
– Exchange HELLO/ACK messages
– Uses a k­out­of­n rule

• Routing updates
– Peers periodically exchange their routing tables 
(distance­vector)



BGP­4: Border Gateway Protocol

• Internet is an arbitrarily 
interconnected set of AS’s
• Two types of traffic

– Local: begins or ends within an AS
– Transit: moves through an AS


BGP­4: Border Gateway Protocol

• Three types of AS’s

– Stub: one single connection to one 
other AS; carries local traffic only
– Multihomed: connections to multiple 
other AS’s, but refuses to carry transit 
traffic
– Transit: connections to multiple other 
AS’s and designed to carry both 
transit and local traffic


BGP­4: Borger Gateway Protocol

• Each AS has:

– One or more border gateways 
(routers) to handle inter­AS 

traffic
– One or more BGP speakers that 
participate in routing protocol: 
establish BGP sessions to 
exchange messages


BGP­4: Borger Gateway Protocol
• BGP speaker advertises:

– Names of networks within the AS
– Names of other reachable networks 
through the AS (transit AS only)
– Full path information (intra­domain 
protocols use heterogeneous metrics); 
path­vector routing
– Withdrawn routes/negative 
advertisements (cancel previously 
advertised route)


BGP Path­Vector Routing Example
• AS4 advertises 128.96 and 192.4.153 as local networks
• Speaker for AS2 advertises reachability to these networks
– Network 128.96 and 192.4.153 can be reached via AS4, and 
network 192.4.32 and 192.4.3 via AS5
Regional provider A
(AS 2)
Backbone network
(AS 1)

Regional provider B
(AS 3)

Customer P
(AS 4)

128.96
192.4.153

Customer Q
(AS 5)

192.4.32
192.4.3

Customer R
(AS 6)

192.12.69

Customer S
(AS 7)

192.4.54
192.4.23

• Speaker for backbone advertises
– Networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached 



BGP­4 ­ Details
• Full path in BGP messages to avoid 
loops
– Best route according to local policies is 
advertised
– No obligation to advertise route to known 
destinations

• 16 bit AS numbers are uniquely 
assigned
– Stub ASs do not need a unique AS number


BGP­4 ­ Details
• BGP­4 designed to support classless 
addresses
– Update messages contain prefix & its 
length (10.1/16)

• Update messages are reliably sent using 
TCP
– Occasional “keepalive” messages if 
nothing changes


Building Scalable Networks …
• Subdivided the routing problem into 
manageable parts
– New level of hierarchy is introduced


• Complexity of interdomain routing:
– Order of number of ASs

• Complexity of interdomain routing:
– Ooder of networks in an AS


Integrating Interdomain and 
Intradomain Routing

• How routers in a domain get routing 
information ?
• In a stub AS with single border 
router
– Inject a default route in intradomain 
routing protocol


Integrating Interdomain and 
Intradomain Routing
• In a domain with multiple border routers 
(any AS)
– Border routers inject specific routes learned 
from outside, with some cost

• In backbone networks, too costly to inject 
too many outside routes in intradomain 
protocol
– Use Interior BGP (IBGP) to redistribute outside 
routes