Introduction to Routing

Srinath Beldona
Senior Technical Specialist
srinath@apnic.net

APNIC Training and Development

Agenda
•  Pre-requisites
•  OSI & TCP/IP Layering architecture
•  IP Addressing
•  The need to route
•  Static Routing
•  Dynamic Routing
•  Distance Vector Routing Protocols and Limitations
•  Link State Routing Protocols (OSPF)
•  BGP as an Inter AS Routing Protocol
Pre-requisites
Pre-requisites

•  Good knowledge of computers

•  Binary System of numbers
•  Hexadecimal representation of numbers
•  Thorough understanding of OSI Layers
•  Good knowledge Data Link layer concepts and protocols
•  Good knowledge of TCP/IP
OSI Layers
Communication Architecture
•  Strategy for connecting host computers and other
communicating equipment.
•  Defines necessary elements for data communication
between devices.
•  A communication architecture, therefore, defines a
standard for the communicating hosts.
•  A programmer formats data in a manner defined by the
communication architecture and passes it on to the
communication software.
•  Separating communication functions adds flexibility, for
example, we do not need to modify the entire host software
to include more communication devices.
Layered Architecture
•  Layered architecture simplifies the network design.
•  It is easy to debug network applications in a layered
architecture network.
•  The network management is easier due to the layered
architecture.
•  Network layers follow a set of rules, called protocol.
•  The protocol defines the format of the data being
exchanged, and the control and timing for the handshake
between layers.
Who created OSI reference model ?
•  International standard organization (ISO) established a
committee in 1977 to develop an architecture for computer
communication.
•  Open Systems Interconnection (OSI) reference model is the
result of this effort.
•  In 1984, the Open Systems Interconnection (OSI) reference
model was approved as an international standard for
communications architecture.
•  Term “open” denotes the ability to connect any two
systems which conform to the reference model and
associated standards.
International Standards Organization

•  Established in 1947, the International Standards

Organization (ISO) is a multinational body
dedicated to worldwide agreement on international
standards. Almost three-fourths of countries in the
world are represented in the ISO. An ISO standard
that covers all aspects of network communications
is the Open Systems Interconnection (OSI) model.
It was first introduced in the late 1970s.
OSI Reference Model
•  The OSI model is now considered the primary Architectural
model for inter-computer communications.
•  The OSI model describes how information or data makes its
way from application programs (such as spreadsheets)
through a network medium (such as wire) to another
application program located on another network.
•  The OSI reference model divides the problem of moving
information between computers over a network medium into
SEVEN smaller and more manageable problems .
•  This separation into smaller more manageable functions is
known as layering.
Objectives of OSI Layering
•  To discuss the idea of multiple layering in data communication
and networking and the interrelationship between layers.
•  To discuss the OSI model and its layer architecture and to show
the interface between the layers.
•  To briefly discuss the functions of each layer in the OSI model.
•  To introduce the TCP/IP protocol suite and compare its layers
with the ones in the OSI model.
•  To show the functionality of each layer in the TCP/IP protocol with
some examples.
•  To discuss the addressing mechanism used in some layers of the
TCP/IP protocol suite for the delivery of a message from the
source to the destination.
OSI Layers
Functional Overview of OSI Layers
Communications in OSI Architecture
TCP/IP History

•  Department of Defense
(DoD) in the US created the Application Layer

TCP/IP reference model on

the objective creating a
resilient network. Transport Layer
•  Few of the layers in the
Internet Layer
TCP/IP model have the
same name as layers in the
OSI model. Network Access Layer
Application Layer functions & Examples

•  Application Layer Functions:

–  Handles high-level protocols, issues of representation,
encoding, and dialog control.
–  The TCP/IP protocol suite combines all application related
issues into one layer and ensures this data is properly
packaged before passing it on to the next layer.
•  Application Layer Examples:
–  Telnet – Provides the capability to remotely access
another computer
–  File Transfer Protocol – Download or upload files
–  Hypertext Transfer Protocol – Works with the World Wide
Web
 Transport Layer
Five basic services:
•  Segmenting upper-layer
Application
application data Layer
•  Establishing end-to-end
operations Transmission
•  Sending segments from Control Protocol
Transport Layer
one end host to another User Datagram
end host Protocol
Internet Layer
•  Ensuring data reliability
•  Providing flow control
Network Layer
Internet Layer = Network layer of OSI
•  The purpose of the Internet layer is to send
packets from a network node and have them arrive
at the destination node independent of the path
taken.
•  Internet layer protocols:
–  Internet Protocol (IP)
–  Internet Control Message Protocol (ICMP)
–  Address Resolution Protocol (ARP)
–  Reverse Address Resolution Protocol (RARP)
Internet Layer = Network layer of OSI
•  Internet layer protocols functions:
–  IP header encapsulation for data from upper layer
–  Internet Control Message Protocol (ICMP) troubleshooting
and supporting operations and maintenance
–  Address Resolution Protocol (ARP) is used to identify the
physical layer addresses
–  Reverse Address Resolution Protocol (RARP) is used
identify the IP address when a host/network element knows
its link layer address such as the mac address.
Internet Layer = Network layer of OSI
•  Implements routing of frames (packets) through the network.
•  Defines the most optimum path the packet should take from
the source to the destination
•  Defines logical addressing so that any endpoint can be
identified.
•  Handles congestion in the network.
•  Facilitates interconnection between heterogeneous networks
(Internetworking).
•  The network layer also defines how to fragment a packet into
smaller packets to accommodate different media.
 Network Access Layer
•  The network access layer
is concerned with all of
the issues that an IP Application
packet requires to Layer
actually make a physical
link to the network media.
•  It includes the LAN and Transport Layer
WAN technology details,
and all the details
Internet Layer Ethernet
contained in the OSI Fast Ethernet
physical and data link SLIP & PPP
FDDI
layers. Network Layer
ATM, Frame Relay & SMDS
ARP
Proxy ARP
RARP
Comparing the OSI & TCP/IP Model
Application Layer

Application
Layer Presentation Layer

Session Layer

Transport Layer Transport Layer

Internet Layer Network Layer

Data Link Layer

Network Access
Layer
Physical Layer

Originally as defined
Comparing the OSI & TCP/IP Model
Application Layer

Application
Layer Presentation Layer

Session Layer

Transport Layer Transport Layer

Network Layer Network Layer

Data Link Layer Data Link Layer

Physical Layer Physical Layer

Architecture used in this presentation

Similarities of the OSI & TCP/IP models

•  Both have layers.

•  Both have application layers, though they include
very different services.
•  Both have comparable transport and network
layers.
•  Packet-switched, not circuit-switched, technology is
assumed.
•  Networking professionals need to know both
models.
Differences of the OSI & TCP/IP models

•  TCP/IP combines the presentation and session layer into its

application layer.
•  TCP/IP combines the OSI data link and physical layers into
one layer.
•  TCP/IP appears simpler because it has fewer layers.
•  TCP/IP transport layer using UDP does not always
guarantee reliable delivery of packets as the transport layer
in the OSI model does.
Internet Architecture

•  Two computers, anywhere in the world, following

certain hardware, software, protocol specifications,
can communicate, reliably even when not directly
connected.
•  LANs are no longer scalable beyond a certain
number of stations or geographic separation.
Internet Architecture: Idea of Routing
Two Layer Hierarchy

Internet

Router 1 Router 2

Switch 1 Switch 2
Typical communication in a Network
Host B
Host A

Router 1 Router 2

S Switch 1 Switch 2 D

Host A Switch 1 Router 1 Router 2 Switch 2 Host B

Network or Internetwork Layer Functions
•  Design Goals
–  ‘Independent’ of layer 1 & 2 implementations
–  Hide layer 1 & 2 details from upper layers

•  Architecture
–  Connection oriented
–  Connectionless
–  (where should reliability be done?)

•  Services
–  Routing (Path selection)
–  Adaptation to different lower layers
Objectives for Routing Algorithms

•  Goals
–  Optimality
–  Fairness
–  Stability
–  Robustness
–  Correctness
–  Simplicity

•  Adaptive versus Static

•  Congestion Control
Adaptive Routing

•  Centralized

•  Isolated

•  Distributed
Distributed Routing
•  Metric - Vector Algorithms
–  sometimes called shortest path
–  Bellman-Ford most famous
–  Knowledge of immediate neighbors
–  Result is “first step” in path to ultimate destination
•  Link State Algorithms
–  OSPF {Open Shortest Path First}
–  Knowledge of network layer map (connectivity)
Summary of Network layer functions
IP Addressing and its role in
Routing
Why do we need IP addresses?
•  Impossible to engineer a universal network from a single
network technology because no single network suffices for
all uses
•  Some technologies such as Ethernet LANs are good for
high speed connection within a Local Area only.
•  Some technologies such as Serial Interfaces were very
good for use within in a Wide Area environment
•  Critical need for internetworking between various LAN and
WAN technologies
•  Different technological approaches create issues such as
Physical addresses used in one technology vs another.
Example Ethernet Mac address, Addressing Token ring,
FDDI Addressing etc.
Why do we need IP addresses?
•  Networks commonly built using disparate technologies
•  Internetworking using Logical Addressing helps connectivity of
disparate networks
•  This approach hides the details of the underlying L2 and L1
technologies completely
•  The primary goal is a system that hides the details of underlying
network hardware while providing universal communication
services.
•  Two fundamental observations about the design of
communication systems:
–  Network-Level Interconnection a No single network hardware technology
can satisfy all constraints.
–  Users desire universal interconnection
•  The need for all computers to communicate using a universal set
of machine identifiers. Unique IP Addresses become a key
requirement
IP Addresses in a Network
•  Every host in the Internet requires a unique IP address for communication.
This is a key architectural requirement
•  An IP address uniquely identifies a network interface on a host.
•  A host may have many interfaces
•  Each IP Address
consists of a network
portion and a host Internet
portion.
•  Combining network Router 1 Network A Network B Router 2
and host portion of
the IP address, all Switch 1 Switch 2
machines on the
internet can be
uniquely identified on
Host A.1 Host A.2 Host A.3
the internet. Host B.1 Host B.2 Host B.3
IP Address: 32-Bit Binary Number
History of IP Addressing
•  Classful IP Addressing
–  When IP was first standardized in September 1981, the specification
required that each system attached to an IP-based Internet be assigned
a unique, 32-bit Internet address value.
•  Systems that have interfaces to more than one network require a
unique IP address for each network interface.
•  The first part of an Internet address identifies the network on
which the host resides, while the second part identifies the
particular host on the given network.
Classful IP Addressing
•  To provide the flexibility required to support networks of
varying sizes, the Internet designers decided that the IP
address space should be divided into three address
classes-Class A, Class B, and Class C. This is often
referred to as Classful addressing.
Dotted-Decimal Notation

To make Internet addresses easier for people to read and

write, IP addresses are often expressed as four decimal
numbers, each separated by a dot. This format is called
“dotted-decimal notation.”
Limitations to Classful Addressing
•  IP Addresses were allocated to an organization based on its
request rather than its need.
•  The decision to standardize on a 32-bit address space
meant that there were only 232 (4,294,967,296) IPv4
addresses available.
•  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
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.
–  Internet routing tables were beginning to grow.
–  Local administrators had to request another network number from the
Internet addressing agency before a new network could be installed
at their site.

•  Resolved using a Subnet architecture

Subnetting & Routing Requirements

The router accepts all traffic from the Internet addressed to network 130.5.0.0,
and forwards traffic to the interior sub networks based on the third octet of the
Classful address.
Advantages of Subnetting
•  The size of the global Internet routing table does not grow
•  Net Administrator has the flexibility to deploy additional
subnets without obtaining a new network number from the
Internet agency
•  Route flapping (that is, the rapid changing of routes) within
the private network does not affect the Internet routing table
as they need not know about the reachability of each
subnet
Routing Protocols & Classful Addressing
•  Classful Routing Updates
–  Classful routing protocols (i.e. RIPv1, IGRP & BGP v3 )
do not send subnet masks in their routing updates.
–  The routing update could determine the subnet mask
simply by examining the value of the first octet in the
network address
Classless Inter-domain Routing
(CIDR – RFC 1519)
•  Advantages of CIDR
–  More efficient use of IPv4 address space
–  Route summarization
•  reduce routing table size
•  reduce routing update traffic
Classless Inter-domain Routing
(CIDR – RFC 1519)
•  Requires subnet mask to be included in routing
update because address class is meaningless
•  The network portion of the address is determined by
the network subnet mask, also known as the network
prefix, or prefix length (/8, /19, etc.).
•  The network address is no longer determined by the
class of the address
•  Blocks of IP addresses could be assigned to a
network based on the requirements of the customer,
ranging from a few hosts to hundreds or thousands
of hosts.
Classless IP Addressing
•  Classless IP Addressing
•  CIDR & Route Summarization
– Variable Length Subnet Masking (VLSM)
– Allows a subnet to be further sub-netted
•  according to individual needs
– Prefix Aggregation a.k.a. Route Summarization
– CIDR allows for routes to be summarized as a single route
Classless IP Addressing and Routing
•  For Route Summarization
•  Propagating VLSM and supernet routes requires a classless routing
protocol, because the subnet mask can no longer be determined by
the value of the first octet.
•  Classless routing protocols include the subnet mask with the network
address in the routing update.
•  RIPv2, EIGRP, IS-IS, OSPF and BGP
 VLSM
•  Classful routing
–  -only allows for one
subnet mask for all
networks
•  VLSM & classless routing
-This is the process of
subnetting a subnet
-More than one
subnet mask can be
used
-More efficient use of IP
addresses as compared
to classful IP
addressing
The need to route
Router as a Computer

•  Router Interface is a physical connector

•  Each interface connects to a separate network
•  Consist of socket or jack found on the outside of a router
•  Types of router interfaces:
– -Ethernet
– -Fast Ethernet
– -Serial
– -DSL
– -ISDN
– -Cable
The concept of Routing
172.16.1.0/24 172.16.2.0/24
Fa0/0 Router
172.16.1.2 172.16.2.2 Data
172.16.1.1
Switch 2
Switch 1
Data 172.16.1.2 172.16.2.2 Fa0/1
172.16.2.1

172.16.2.2 172.16.2.3 172,16,2.4

172.16.1.2 172.16.1.3 172.16.1.4

•  Every IP packet originated by the hosts contains a source ip address and a

destination IP address.
•  The router uses this information to forward packets based on the
destination IP address
•  For example: Packets arriving on Fa0/0 with Source IP Address 172.16.1.2
and destination IP Address of 172.16.2.2 will be forwarded out on Fa0/1
and Vice Versa
•  This technique helps to expand to multiple routers involved in routing to
scale connectivity between hosts on different networks.
 Scaling connectivity requires Routing
Fa0/0
172116.1.0/24 171.16.2.0/24
172.16.1.1
171.16.2.1
Switch 1 Switch 2
Fa0/1
Router Router

Internet

172.16.2.2 172.16.2.3 172,16,2.4

172.16.1.2 172.16.1.3 172.16.1.4

•  A router can build

routing tables •  Static routing more
dynamically or static Router 171.16.3.0/24 suitable for very small
171.16.3.1 Fa0/1
routes. networks and used
Switch 2
•  Routers participate in more for hub and
exchanging routing spoke environments
information or
reachability
information 171.16.3.2 171.16.3.3 171,16,3.4
Static Routing
 Static routing
•  A manually configured route on a router to reach a specific
destination network
Static routing
pointing to
Fa0/0 172.16.1.0/24
172116.1.0/24 on Router 2 171.16.2.0/24
172.16.1.1
171.16.2.1
Switch 1 Switch 2
Fa0/1
Router 1 Router 2
Static routing
pointing to
172.16.2.0/24
on Router 1
172.16.2.2 172.16.2.3 172,16,2.4
172.16.1.2 172.16.1.3 172.16.1.4

•  Useful for small networks

•  Mostly used in hub and spoke networks
•  Connecting to the Internet and single homed
 Static Routing Scenarios
Fa0/0
172116.1.0/24 171.16.2.0/24
172.16.1.1
171.16.2.1
Switch 1 Switch 2
Fa0/1
Router 1 Router 2

Internet

172.16.2.2 172.16.2.3 172,16,2.4

172.16.1.2 172.16.1.3 172.16.1.4

•  Connecting to the Internet and single

homed
•  A simple default route pointed to the Router 3 171.16.3.0/24
interface connecting to the router on 171.16.3.1 Fa0/1
Router 1, Router 2 and Router 3 helps
the hosts on these networks to Switch 2
connect to the internet
•  A static route is also required on the
ISP router to reach the respective
networks in the reverse direction 171.16.3.2 171.16.3.3 171,16,3.4
Static Route Configuration
 Static routing configuration Example
171.16.2.0/24
171.16.2.1
Fa0/0 E 1/0
172116.1.0/24 Switch 2
172.16.1.1 Fa0/1
E 1/0 Router 2
Switch 1
Router 1

Internet
172.16.2.2 172.16.2.3 172,16,2.4

E 1/0
172.16.1.2 172.16.1.3 172.16.1.4
Router 3 171.16.3.0/24
Default Route configuration to connect to the Internet 171.16.3.1 Fa0/1

Switch
R1# conf term 2
R1(config)# ip route 0.0.0.0 0.0.0.0 interface ethernet 1/0 11.250.250.1

R2# conf term

171.16.3.2 171.16.3.3 171,16,3.4
R2(config)# ip route 0.0.0.0 0.0.0.0 interface ethernet 1/0 12.250.250.1

R3# conf term

R3(config)# ip route 0.0.0.0 0.0.0.0 interface ethernet 1/0 13.250.250.1

 Static routing
•  A manually configured route on a router to reach a specific
destination network
Static routing
pointing to
Fa0/0 172.16.1.0/24
172116.1.0/24 E 1/0 on Router 2 171.16.2.0/24
172.16.1.1
172.16.3.1/30 171.16.2.1
Switch 1 Switch 2
E 1/0 Fa0/1
Router 1 172.16.3.2/30 Router 2
Static routing
pointing to
172.16.2.0/24
on Router 1
172.16.2.2 172.16.2.3 172,16,2.4
172.16.1.2 172.16.1.3 172.16.1.4

Router1# conf term

Router1(config)# ip route 172.16.2.0 255.255.255.0 ethernet 1/0 172.16.3.2

Router2# conf term

Router2(config)# ip route 172.16.1.0 255.255.255.0 ethernet 1/0 172.16.3.1
 Load sharing using static routing
Fa0/0
172116.1.0/24 E 1/0 E 1/0 171.16.2.0/24
172.16.1.1
172.16.3.1/30 172.16.3.2/30 171.16.2.1
Switch 1 Switch 2
Fa0/1

Router 1 E 1/1 E 1/1 Router 2

172.16.3.5/30 172.16.3.6/30

172.16.2.2 172.16.2.3 172,16,2.4

172.16.1.2 172.16.1.3 172.16.1.4

Router1# conf term

Router1(config)# ip route 172.16.2.0 255.255.255.0 ethernet 1/0 172.16.3.2
Router1(config)# ip route 172.16.2.0 255.255.255.0 ethernet 1/1 172.16.3.6

Router2# conf term

Router2(config)# ip route 172.16.1.0 255.255.255.0 ethernet 1/0 172.16.3.1
Router2(config)# ip route 172.16.1.0 255.255.255.0 ethernet 1/1 172.16.3.5
Pros and Cons of Static routing

•  Advantages of static routing

–  It can backup multiple interfaces/networks on a router
–  Easy to configure
–  No extra resources are needed

•  -More secure
•  Disadvantages of static routing
–  Network changes require manual reconfiguration
–  Does not scale well in large topologies
Dynamic Routing
Characteristics of Dynamic Routing

•  Dynamic routing protocols fulfill the following

functions
–  Dynamically share information between routers
–  Automatically update routing table when topology
changes
–  Determine best path to a destination
•  Routing protocols are grouped as either
–  Interior gateway protocols (IGP)Or
–  Exterior gateway protocols(EGP)
Terminology
•  Dynamic routing protocols fulfill the following functions
– -Dynamically share information between routers
– -Automatically update routing table when topology changes
– -Determine best path to a destination
•  Routing protocols are grouped as either
– -Interior gateway protocols (IGP)Or
– -Exterior gateway protocols(EGP)
•  Types of IGPs include
– -Classless routing protocols - these protocols include subnet mask
in routing updates
– -Classful routing protocols - these protocols do not include subnet
mask in routing update
Terminology

•  Metrics are used by dynamic routing protocols to calculate the

best path to a destination.
•  Administrative distance is the feature that routers use in order to
select the best path when there are two or more different routes to the
same destination from two different routing protocols. Administrative
distance defines the reliability of a routing protocol. Each routing
protocol is prioritized in order of most to least reliable (believable) with
the help of an administrative distance value.”
•  Components of a routing table include:
– -Route source
– -Administrative distance
– -Metric
Dynamic Routing Protocols

Function(s) of Dynamic Routing Protocols:

– -Dynamically share information between routers.
– -Automatically update routing table when topology changes.
– -Determine best path to a destination.
Dynamic Routing Protocols
The purpose of a dynamic routing protocol is to:
– -Discover remote networks
– -Maintaining up-to-date routing information
– -Choosing the best path to destination networks
– -Ability to find a new best path if the current path is no longer
available
Dynamic Routing Protocols

Components of a routing protocol

– Algorithm
•  In the case of a routing protocol algorithms are used for facilitating routing
information and best path determination
– Routing protocol messages
•  These are messages for discovering neighbors and exchange of routing
information
Classifying Routing Protocols

Types of routing protocols:

– -Interior Gateway Protocols (IGP)
– -Exterior Gateway Protocols (EGP)
– 
Classifying Routing Protocols

•  Interior Gateway Routing Protocols (IGP)

– -Used for routing inside an autonomous system & used to route
within the individual networks themselves.
– -Examples: RIP, EIGRP, OSPF

•  Exterior Routing Protocols (EGP)

– -Used for routing between autonomous systems
– -Example: BGPv4
 Classifying Routing Protocols

•  IGP: Comparison of Distance Vector & Link State

Routing Protocols
– Distance vector
–  routes are advertised as vectors
–  of distance & direction.
–  incomplete view of network
–  topology.
– Generally, periodic
–  updates.
– Link state
–  complete view of network
–  topology is created.
–  updates are not
–  periodic.
–  Faster Convergence
Classifying Routing Protocols

•  Convergence is defined as: when all routers’ routing

tables are at a state of consistency
Routing Protocols Metrics

•  Metric
– A value used by a routing protocol to determine which
routes are better than others.
Routing Protocols Metrics

•  Metrics used in IP routing protocols

– -Bandwidth
– -Cost
– -Delay
– -Hop count
– -Load
– -Reliability
Routing Protocols Metrics

•  The Metric Field in the Routing Table

•  Metric used for each routing protocol
– -RIP - hop count
– -IGRP & EIGRP - Bandwidth (used by default), Delay (used
by default), Load, Reliability
– -IS-IS & OSPF – Cost, Bandwidth (Cisco’s implementation)

– RIP-Routing Information Protocol I

– IGRP-Interior Gateway Routing Protocol
– EIGRP-Enhanced Interior Gateway Routing Protocol
– IS-IS - Intermediate System to Intermediate System
Routing Protocols Metrics

•  Load balancing
– This is the ability of a router to distribute packets among
multiple same cost paths
Administrative Distance of a Route

•  Purpose of a metric
– It’s a calculated value used to determine the best path to a
destination

•  Purpose of Administrative Distance

– It’s a numeric value that specifies the preference of a particular
route
Administrative Distance of a Route

Identifying the Administrative Distance (AD) in a routing

table
– It is the first number in the brackets in the routing table
Administrative Distance of a Route

Dynamic Routing Protocols

Administrative Distance of a Route

•  Directly connected routes

– Have a default AD of 0

•  Static Routes
– Administrative distance of a static route has a default value of 1
Administrative Distance of a Route

Directly connected routes

– -Immediately appear in the routing table as soon as the interface
is configured
Routing Basics
ISP Workshops

Last updated 21 July 2013

84
Routing Concepts
•  IPv6
•  IPv4
•  Routing
•  Forwarding
•  Some definitions
•  Policy options
•  Routing Protocols

85
IPv6
•  Internet is starting to use IPv6
–  Addresses are 128 bits long
–  Internet addresses range from 2000::/16 to 3FFF::/16
–  The remaining IPv6 range is reserved or has “special” uses

•  IPv6 address has a network portion and a host

portion

86
IPv4
•  Internet still uses IPv4
–  (legacy protocol)
–  Addresses are 32 bits long
–  Range from 1.0.0.0 to 223.255.255.255
–  0.0.0.0 to 0.255.255.255 and 224.0.0.0 to 255.255.255.255
have “special” uses

•  IPv4 address has a network portion and a host

portion

87
IP address format
•  Address and subnet mask
–  IPv4 written as
•  12.34.56.78 255.255.255.0 or
•  12.34.56.78/24
–  IPv6 written as
•  2001:db8::1/128
–  mask represents the number of network bits in the address
–  The remaining bits are the host bits

88
What does a router do?

89
A day in a life of a router

find path
forward packet, forward packet, forward packet,
forward packet...
find alternate path
forward packet, forward packet, forward packet,
forward packet…
repeat until powered off

90
Routing versus Forwarding
•  Routing = building
maps and giving
directions
•  Forwarding = moving
packets between
interfaces according to
the “directions”

91
IP Routing – finding the path
•  Path derived from information received from a
routing protocol
•  Several alternative paths may exist
–  best path stored in forwarding table

•  Decisions are updated periodically or as topology

changes (event driven)
•  Decisions are based on:
–  topology, policies and metrics (hop count, filtering, delay,
bandwidth, etc.)

92
IP route lookup
•  Based on destination IP address
•  “longest match” routing
–  More specific prefix preferred over less specific prefix
–  Example: packet with destination of 2001:db8::1/128 is
sent to the router announcing 2001:db8:1::/48 rather than
the router announcing 2001:db8::/32.

93
IP route lookup
•  Based on destination IP address

2001:db8::/32
Packet: Destination R3 announced from
IP address: 2001:db8::1 here

R1 R2

R4
2001:db8::/32 → R3
2001:db8:1::/16→ R4 2001:db8:1::/48
announced from
2001:db9::/32 → R5
here
2001:dba::/32 → R6
……
R2’s IP routing table
94
IP route lookup:
Longest match routing
•  Based on destination IP address

2001:db8::/32
Packet: Destination R3 announced from
IP address: 2001:db8::1 here

R1 R2

R4
2001:db8::/32 → R3 2001:db8::1 && ffff:ffff:: 2001:db8:1::/48
2001:db8:1::/48 → R4 vs. Match! announced from
2001:db9::/32 → R5 2001:db8:: && ffff:ffff:: here
2001:dba::/32 → R6
……

R2’s IP routing table

95
IP route lookup:
Longest match routing
•  Based on destination IP address

2001:db8::/32
Packet: Destination R3 announced from
IP address: 2001:db8::1 here

R1 R2

R4
2001:db8::/32 → R3 2001:db8::1 && ffff:ffff:ffff:: 2001:db8:1::/16
2001:db8:1::/48 → R4 vs. announced from
2001:db9::/32 → R5 2001:db8:1:: && ffff:ffff:ffff:: here
2001:dba::/32 → R6
…… Match as well!
R2’s IP routing table
96
IP route lookup:
Longest match routing
•  Based on destination IP address

2001:db8::/32
Packet: Destination R3 announced from
IP address: 2001:db8::1 here

R1 R2

R4
2001:db8::/32 → R3 2001:db8:1::/48
2001:db8:1::/48 → R4 2001:db8::1 && ffff:ffff::
vs. announced from
2001:db9::/32 → R5
2001:db9:: && ffff:ffff:: here
2001:dba::/32 → R6
……
Does not match!
R2’s IP routing table
97
IP route lookup:
Longest match routing
•  Based on destination IP address

2001:db8::/32
Packet: Destination R3 announced from
IP address: 2001:db8::1 here

R1 R2

R4
2001:db8::/32 → R3 2001:db8:1::/48
2001:db8:1::/48 → R4 announced from
2001:db9::/32 → R5 2001:db8::1 && ffff:ffff:: here
2001:dba::/32 → R6 vs. Does not match!
…… 2001:dba:: && ffff:ffff::
R2’s IP routing table
98
IP route lookup:
Longest match routing
•  Based on destination IP address

2001:db8::/32
Packet: Destination R3 announced from
IP address: 2001:db8::1 here

R1 R2

R4
2001:db8::/32 → R3 2001:db8:1::/48
2001:db8:1::/48 → R4 Longest match, 48 bit netmask announced from
2001:db9::/32 → R5
here
2001:dba::/32 → R6
……

R2’s IP routing table

99
IP Forwarding
•  Router decides which interface a packet is sent to
•  Forwarding table populated by routing process
•  Forwarding decisions:
–  destination address
–  class of service (fair queuing, precedence, others)
–  local requirements (packet filtering)
•  Forwarding is usually aided by special hardware

100
Routing Tables Feed the Forwarding
Table

Routing Information Base (RIB)

Forwarding Information Base (FIB)

BGP 4 Routing Table

OSPF – Link State Database

Connected Routes

Static Routes

101
RIBs and FIBs
•  FIB is the Forwarding Table
–  It contains destinations and the interfaces to get to those
destinations
–  Used by the router to figure out where to send the packet
–  Careful! Some people still call this a route!

•  RIB is the Routing Table

–  It contains a list of all the destinations and the various next
hops used to get to those destinations – and lots of other
information too!
–  One destination can have lots of possible next-hops – only
the best next-hop goes into the FIB

102
Explicit versus Default Routing
•  Default:
–  simple, cheap (cycles, memory, bandwidth)
–  low granularity (metric games)

•  Explicit (default free zone)

–  high overhead, complex, high cost, high granularity

•  Hybrid
–  minimise overhead
–  provide useful granularity
–  requires some filtering knowledge

103
Egress Traffic
•  How packets leave your network
•  Egress traffic depends on:
–  route availability (what others send you)
–  route acceptance (what you accept from others)
–  policy and tuning (what you do with routes from others)
–  Peering and transit agreements

104
Ingress Traffic
•  How packets get to your network and your
customers’ networks
•  Ingress traffic depends on:
–  what information you send and to whom
–  based on your addressing and AS’s
–  based on others’ policy (what they accept from you and
what they do with it)

105
Autonomous System (AS)

AS 100

•  Collection of networks with same routing policy

•  Single routing protocol
•  Usually under single ownership, trust and
administrative control

106
Definition of terms
•  Neighbours
–  AS’s which directly exchange routing information
–  Routers which exchange routing information
•  Announce
–  send routing information to a neighbour
•  Accept
–  receive and use routing information sent by a neighbour
•  Originate
–  insert routing information into external announcements
(usually as a result of the IGP)
•  Peers
–  routers in neighbouring AS’s or within one AS which
exchange routing and policy information
107
Routing flow and packet flow

packet flow
accept announce
AS 1 announce
routing flow
accept AS 2
packet flow

For networks in AS1 and AS2 to communicate:

AS1 must announce to AS2
AS2 must accept from AS1
AS2 must announce to AS1
AS1 must accept from AS2

108
Routing flow and Traffic flow
•  Traffic flow is always in the opposite direction of the
flow of Routing information
–  Filtering outgoing routing information inhibits traffic flow
inbound
–  Filtering inbound routing information inhibits traffic flow
outbound

109
Routing Flow/Packet Flow:
With multiple ASes

AS 1
AS 34
N1
AS16
AS 8
N16

•  For net N1 in AS1 to send traffic to net N16 in AS16:

–  AS16 must originate and announce N16 to AS8.
–  AS8 must accept N16 from AS16.
–  AS8 must announce N16 to AS1 or AS34.
–  AS1 must accept N16 from AS8 or AS34.
•  For two-way packet flow, similar policies must exist for
N1
110
Routing Flow/Packet Flow:
With multiple ASes

AS 1
AS 34
N1
AS16
AS 8
N16

•  As multiple paths between sites are implemented

it is easy to see how policies can become quite
complex.

111
Routing Policy
•  Used to control traffic flow in and out of an ISP
network
•  ISP makes decisions on what routing information to
accept and discard from its neighbours
–  Individual routes
–  Routes originated by specific ASes
–  Routes traversing specific ASes
–  Routes belonging to other groupings
•  Groupings which you define as you see fit

112
Routing Policy Limitations

red
red
Internet AS99

green green

packet flow
•  AS99 uses red link for traffic to the red AS and the
green link for remaining traffic
•  To implement this policy, AS99 has to:
–  Accept routes originating from the red AS on the red link
–  Accept all other routes on the green link

113
Routing Policy Limitations

red
red Internet
AS22 AS99

green green

packet flow
•  AS99 would like packets coming from the green AS to
use the green link.
•  But unless AS22 cooperates in pushing traffic from the
green AS down the green link, there is very little that
AS99 can do to achieve this aim

114
Routing Policy Issues

•  April 2013:
–  12900 IPv6 prefixes & 460000 IPv4 prefixes
•  Not realistic to set policy on all of them individually
–  44500 origin AS’s
•  Too many to try and create individual policies for

•  Routes tied to a specific AS or path may be

unstable regardless of connectivity
•  Solution: Groups of AS’s are a natural
abstraction for filtering purposes

115
Routing Protocols
We now know what routing means…
…but what do the routers get up to?
And why are we doing this anyway?

116
1: How Does Routing Work?
•  Internet is made up of the ISPs who connect to
each other’s networks
•  How does an ISP in Kenya tell an ISP in Japan what
customers they have?
•  And how does that ISP send data packets to the
customers of the ISP in Japan, and get responses
back
–  After all, as on a local ethernet, two way packet flow is
needed for communication between two devices

117
2: How Does Routing Work?
•  ISP in Kenya could buy a direct connection to the
ISP in Japan
–  But this doesn’t scale – thousands of ISPs, would need
thousands of connections, and cost would be astronomical

•  Instead, ISP in Kenya tells his neighbouring ISPs

what customers he has
–  And the neighbouring ISPs pass this information on to their
neighbours, and so on
–  This process repeats until the information reaches the ISP
in Japan

118
3: How Does Routing Work?
•  This process is called “Routing”
•  The mechanisms used are called “Routing Protocols”
•  Routing and Routing Protocols ensures that the
Internet can scale, that thousands of ISPs can
provide connectivity to each other, giving us the
Internet we see today

119
4: How Does Routing Work?
•  ISP in Kenya doesn’t actually tell his neighbouring
ISPs the names of the customers
–  (network equipment does not understand names)

•  Instead, he has received an IP address block as a

member of the Regional Internet Registry serving
Kenya
–  His customers have received address space from this
address block as part of their “Internet service”
–  And he announces this address block to his neighbouring
ISPs – this is called announcing a “route”

120
Routing Protocols
•  Routers use “routing protocols” to exchange routing
information with each other
–  IGP is used to refer to the process running on routers inside
an ISP’s network
–  EGP is used to refer to the process running between routers
bordering directly connected ISP networks

121
What Is an IGP?
•  Interior Gateway Protocol
•  Within an Autonomous System
•  Carries information about internal infrastructure
prefixes
•  Two widely used IGPs:
–  OSPF
–  ISIS

122
Why Do We Need an IGP?
•  ISP backbone scaling
–  Hierarchy
–  Limiting scope of failure
–  Only used for ISP’s infrastructure addresses, not customers
or anything else
–  Design goal is to minimise number of prefixes in IGP to aid
scalability and rapid convergence

123
What Is an EGP?
•  Exterior Gateway Protocol
•  Used to convey routing information between
Autonomous Systems
•  De-coupled from the IGP
•  Current EGP is BGP

124
Why Do We Need an EGP?
•  Scaling to large network
–  Hierarchy
–  Limit scope of failure

•  Define Administrative Boundary

•  Policy
–  Control reachability of prefixes
–  Merge separate organisations
–  Connect multiple IGPs

125
Interior versus Exterior
Routing Protocols
•  Interior •  Exterior
–  automatic neighbour –  specifically configured peers
discovery –  connecting with outside
–  generally trust your IGP networks
routers –  set administrative boundaries
–  prefixes go to all IGP routers –  binds AS’s together
–  binds routers in one AS
together

126
Interior versus Exterior
Routing Protocols
•  Interior •  Exterior
–  Carries ISP infrastructure –  Carries customer prefixes
addresses only –  Carries Internet prefixes
–  ISPs aim to keep the IGP –  EGPs are independent of ISP
small for efficiency and network topology
scalability

127
Hierarchy of Routing Protocols

Other ISPs
BGP4

BGP4
and OSPF/ISIS

BGP4 Static/BGP4

IXP Customers

128
FYI: Cisco IOS Default Administrative
Distances
Route Source Default Distance

Connected Interface 0
Static Route 1
Enhanced IGRP Summary Route 5
External BGP 20
Internal Enhanced IGRP 90
IGRP 100
OSPF 110
IS-IS 115
RIP 120
EGP 140
External Enhanced IGRP 170
Internal BGP 200
Unknown 255
129
Routing Basics
ISP Workshops

130
Distance Vector routing
protocols
Distance Vector Routing Protocols

Examples of Distance Vector routing protocols:

§  Routing Information Protocol (RIP)
§  Interior Gateway Routing Protocol (IGRP)
§  Enhanced Interior Gateway Routing Protocol
(EIGRP) -- hybrid
Distance Vector Routing Protocols

Distance Vector Technology

– The Meaning of Distance Vector:
•  A router using distance vector routing protocols
knows 2 things:
§ Distance to final destination
§ Vector, or direction, traffic should be
directed
Distance Vector Routing Protocols
Characteristics of Distance Vector routing protocols:
§  Periodic updates
§  Neighbors
§  Broadcast updates
§  Entire routing table is included with routing update
 Distance Vector Routing Protocols
Routing Protocol Algorithm:
-Defines a procedure for accomplishing a certain task
Distance Vector Routing Protocols

Routing Protocol Characteristics

– Criteria used to compare routing protocols includes
§  -Time to convergence
§  -Scalability
§  -Resource usage
§  -Implementation & maintenance
Distance Vector Routing Protocols
Link State routing protocols
OSPF

•  Open Shortest Path •  Designed for:

First –  TCP/IP environment
–  Fast convergence
•  Link state or SPF
–  Variable-length subnet
technology masks
•  Developed by OSPF –  Discontiguous subnets
–  Incremental updates
working group of IETF
–  Route authentication
(RFC 1247)
•  Runs on IP, Protocol 89
•  OSPFv2 standard
described in RFC2328

139
Link State

Z’s Link State

Q’s Link State
Z

A Q 2
B Z 13
Q Y
C X 13

Topology Information is kept

X in a Database separate from
the Routing Table
X’s Link State

140
Link State Routing
•  Neighbour discovery
•  Constructing a Link State Packet (LSP)
•  Distribute the LSP
–  (Link State Announcement – LSA)
•  Compute routes
•  On network failure
–  New LSPs flooded
–  All routers recompute routing table

141
Low Bandwidth Utilisation

LSA

X R1

LSA

•  Only changes propagated

•  Uses multicast on multi-access broadcast
networks
142
Fast Convergence
•  Detection Plus LSA/SPF
–  Known as the Dijkstra Algorithm

Alternate Path R2

N1
R1 X
Primary Path
R3
N2

143
Fast Convergence
•  Finding a new route
–  LSA flooded throughout
area
LSA
–  Acknowledgement based
–  Topology database
synchronised
–  Each router derives routing
N1
R1 X
table to destination
network

144
OSPF Areas

•  Area is a group of
contiguous hosts and
networks
–  Reduces routing traffic R1 R2

•  Per area topology Area 2 Area 3

Rc Rb
database Area 0
–  Invisible outside the Backbone Area
area Rd Ra

•  Backbone area MUST

be contiguous R5 R4
R8 R7
–  All other areas must be
Area 4 Area 1
connected to the
backbone R3
R6

145
Virtual Links between OSPF Areas

•  Virtual Link is used

when it is not possible
Rc Rb
to physically connect Area 0
the area to the Backbone Area

backbone Rd Ra

•  ISPs avoid designs Area 4

R5 R4
which require virtual R8 R7

links Area 1

–  Increases complexity R6
R3

–  Decreases reliability and

scalability

146
 Classification of Routers

R1 IR R2
IR

Area 2 Area 3
Rc Rb

ABR/BR
Area 0
Rd Ra
•  Internal Router (IR)
ASBR IR/BR
R5 R4
•  Area Border Router (ABR)
To other AS
•  Backbone Router (BR)
Area 1
R3 •  Autonomous System
Border Router (ASBR)

147
 OSPF Route Types

R1 IR R2
IR

Area 2 Area 3
Rc Rb

ABR/BR
Area 0 •  Intra-area Route
Rd Ra
–  all routes inside an area
ASBR
•  Inter-area Route
R5 R4
To other AS –  routes advertised from one
area to another by an Area
Area 1 Border Router
R3
•  External Route
–  routes imported into OSPF
from other protocol or static
routes 148
External Routes
•  Prefixes which are redistributed into OSPF from
other protocols
•  Flooded unaltered throughout the AS
–  Recommendation: Avoid redistribution!!

•  OSPF supports two types of external metrics

–  Type 1 external metrics
–  Type 2 external metrics (Cisco IOS default)

RIP
EIGRP
BGP
OSPF Static
R2
Connected
Redistribute etc.
149
External Routes
•  Type 1 external metric: metrics are added to the
summarised internal link cost

to N1
Cost = 10 External Cost = 1
R2

R1
to N1
Cost = 8 R3 External Cost = 2

Network Type 1 Next Hop

N1 11 R2
N1 10 R3 Selected Route
150
External Routes
•  Type 2 external metric: metrics are compared
without adding to the internal link cost

to N1
Cost = 10 External Cost = 1
R2

R1
to N1
Cost = 8 R3 External Cost = 2

Network Type 1 Next Hop

N1 1 R2 Selected Route
N1 2 R3
151
Topology/Link State Database

•  A router has a separate LS database for each

area to which it belongs
•  All routers belonging to the same area have
identical database
•  SPF calculation is performed separately for each
area
•  LSA flooding is bounded by area
•  Recommendation:
–  Limit the number of areas a router participates in!!
–  1 to 3 is fine (typical ISP design)
–  >3 can overload the CPU depending on the area topology
complexity

152
The Hello Protocol
•  Responsible for
establishing and
maintaining neighbour Hello
relationships
•  Elects designated router
Hello
on multi-access networks Hello

153
The Hello Packet
•  Contains:
–  Router priority
–  Hello interval Hello
–  Router dead interval
–  Network mask
–  List of neighbours
Hello
–  DR and BDR Hello
–  Options: E-bit, MC-bit,…
(see A.2 of RFC2328)

154
Designated Router
•  There is ONE designated router per multi-access
network
–  Generates network link advertisements
–  Assists in database synchronization

Backup
Designated Designated
Router Router

Designated Backup
Router Designated Router
155
Designated Router by Priority

•  Configured priority (per interface)

–  ISPs configure high priority on the routers they want as
DR/BDR
•  Else determined by highest router ID
–  Router ID is 32 bit integer
–  Derived from the loopback interface address, if
configured, otherwise the highest IP address

131.108.3.2 131.108.3.3

R1 DR R2

R1 Router ID = 144.254.3.5 R2 Router ID = 131.108.3.3

144.254.3.5
156
Neighbouring States
•  Full
–  Routers are fully adjacent
–  Databases synchronised
–  Relationship to DR and BDR

Full
DR BDR

157
Neighbouring States
•  2-way
–  Router sees itself in other Hello packets
–  DR selected from neighbours in state 2-way or greater

2-way

DR BDR

158
When to Become Adjacent
•  Underlying network is point to point
•  Underlying network type is virtual link
•  The router itself is the designated router or the
backup designated router
•  The neighbouring router is the designated router or
the backup designated router

159
LSAs Propagate Along Adjacencies

DR BDR

•  LSAs acknowledged along adjacencies

160
Broadcast Networks
•  IP Multicast used for Sending and Receiving Updates
–  All routers must accept packets sent to AllSPFRouters
(224.0.0.5)
–  All DR and BDR routers must accept packets sent to
AllDRouters (224.0.0.6)

•  Hello packets sent to AllSPFRouters (Unicast on

point-to-point and virtual links)

161
Routing Protocol Packets
•  Share a common protocol header
•  Routing protocol packets are sent with type of
service (TOS) of 0
•  Five types of OSPF routing protocol packets
–  Hello – packet type 1
–  Database description – packet type 2
–  Link-state request – packet type 3
–  Link-state update – packet type 4
–  Link-state acknowledgement – packet type 5

162
Different Types of LSAs
•  Six distinct type of LSAs
–  Type 1: Router LSA
–  Type 2: Network LSA
–  Type 3 & 4: Summary LSA
–  Type 5 & 7: External LSA (Type 7 is for NSSA)
–  Type 6: Group membership LSA
–  Type 9, 10 & 11: Opaque LSA (9: Link-Local, 10: Area)

163
Router LSA (Type 1)
•  Describes the state and cost of the router’s links to
the area
•  All of the router’s links in an area must be
described in a single LSA
•  Flooded throughout the particular area and no more
•  Router indicates whether it is an ASBR, ABR, or end
point of virtual link

164
Network LSA (Type 2)
•  Generated for every transit broadcast and NBMA
network
•  Describes all the routers attached to the network
•  Only the designated router originates this LSA
•  Flooded throughout the area and no more

165
Summary LSA (Type 3 and 4)
•  Describes the destination outside the area but still
in the AS
•  Flooded throughout a single area
•  Originated by an ABR
•  Only inter-area routes are advertised into the
backbone
•  Type 4 is the information about the ASBR

166
External LSA (Type 5 and 7)
•  Defines routes to destination external to the AS
•  Default route is also sent as external
•  Two types of external LSA:
–  E1: Consider the total cost up to the external destination
–  E2: Considers only the cost of the outgoing interface to the
external destination

•  (Type 7 LSAs used to describe external LSA for one

specific OSPF area type)

167
Inter-Area Route Summarisation
•  Prefix or all subnets
•  Prefix or all networks
•  ‘Area range’ command
R2
Backbone
Area 0

With Network Next Hop (ABR)

summarisation 1 R1
R1
Area 1
Without Network Next Hop
summarisation 1.A R1
1.A 1.B 1.C
1.B R1
1.C R1

168
No Summarisation
•  Specific Link LSA advertised out of each area
•  Link state changes propagated out of each area

1.A
1.B
1.C 3.A
1.D 3.B
Area 0 3.C
2.A 3.D
2.B
2.C
2.D

1.B 3.B
1.A 3.A

2.B
1.C 1.D 2.A 3.C 3.D

2.C 2.D

169
With Summarisation
•  Only summary LSA advertised out of each area
•  Link state changes do not propagate out of the area

1 3
Area 0
2

1.B 3.B
1.A 3.A

2.B
1.C 1.D 2.A 3.C 3.D

2.C 2.D

170
No Summarisation
•  Specific Link LSA advertised in to each area
•  Link state changes propagated in to each area

2.A 2.B
2.C 2.D
3.A 3.B 1.A 1.B
3.C 3.D 1.C 1.D
Area 0 2.A 2.B
1.A 1.B 2.C 2.D
1.C 1.D
3.A 3.B
3.C 3.D

1.B 3.B
1.A 3.A

2.B
1.C 1.D 2.A 3.C 3.D

2.C 2.D

171
With Summarisation
•  Only summary link LSA advertised in to each area
•  Link state changes do not propagate in to each area

2 1
3 2
Area 0
1
3

1.B 3.B
1.A 3.A

2.B
1.C 1.D 2.A 3.C 3.D

2.C 2.D

172
Types of Areas

•  Regular
•  Stub
•  Totally Stubby
•  Not-So-Stubby
•  Only “regular” areas are useful for ISPs
–  Other area types handle redistribution of other routing
protocols into OSPF – ISPs don’t redistribute anything
into OSPF

•  The next slides describing the different area

types are provided for information only

173
Regular Area (Not a Stub)
•  From Area 1’s point of view, summary networks from other
areas are injected, as are external networks such as X.1

ASBR
X.1 External
networks
X.1
2 1
3 2 X.1
Area 0
X.1
1
3

X.1 1.B 3.B

1.A X.1 3.A

2.B
1.D X.1 2.A 3.D
1.C 3.C

2.C 2.D

174
Normal Stub Area
•  Summary networks, default route injected
•  Command is area x stub
ASBR
X.1 External
networks
Default
2 1
3 2 Default
Area 0
Default
1
3

X.1 1.B 3.B

1.A X.1 3.A

X.1 2.B
1.C 1.D 2.A 3.C 3.D

2.C 2.D

175
Totally Stubby Area
•  Only a default route injected
–  Default path to closest area border router
•  Command is area x stub no-summary ASBR
X.1 External
networks
1
Totally Default 2 Default
Stubby Area Area 0
Default
1
3

X.1 1.B 3.B

1.A X.1 3.A

2.B
1.D X.1 2.A 3.D
1.C 3.C

2.C 2.D

176
Not-So-Stubby Area
•  Capable of importing routes in a limited fashion
•  Type-7 LSA’s carry external information within an NSSA
•  NSSA Border routers translate selected type-7 LSAs into type-5 external
network LSAs ASBR
X.1 External
networks
1
Not-So- Default 2 Default
Stubby Area Area 0 X.2
Default
X.2 1
3 X.2

X.2
X.1 1.B 3.B
1.A X.1 3.A

X.2 X.1
2.B
1.C 1.D 2.A 3.C 3.D
External
networks
2.C 2.D

177
ISP Use of Areas
•  ISP networks use:
–  Backbone area
–  Regular area

•  Backbone area
–  No partitioning

•  Regular area
–  Summarisation of point to point link addresses used within
areas
–  Loopback addresses allowed out of regular areas without
summarisation (otherwise iBGP won’t work)

178
Addressing for Areas

Area 0
network 192.168.1.0
range 255.255.255.192

Area 1 Area 2 Area 3

network 192.168.1.64 network 192.168.1.128 network 192.168.1.192
range 255.255.255.192 range 255.255.255.192 range 255.255.255.192

•  Assign contiguous ranges of subnets per area to

facilitate summarisation
179
Summary
•  Fundamentals of Scalable OSPF Network Design
–  Area hierarchy
–  DR/BDR selection
–  Contiguous intra-area addressing
–  Route summarisation
–  Infrastructure prefixes only

180
BGP as an Inter AS Routing
protocol
Border Gateway Protocol
•  A Routing Protocol used to exchange routing
information between different networks
–  Exterior gateway protocol

•  Described in RFC4271
–  RFC4276 gives an implementation report on BGP
–  RFC4277 describes operational experiences using BGP

•  The Autonomous System is the cornerstone of BGP

–  It is used to uniquely identify networks with a common
routing policy

182
BGP
•  Path Vector Protocol
•  Incremental Updates
•  Many options for policy enforcement
•  Classless Inter Domain Routing (CIDR)
•  Widely used for Internet backbone
•  Autonomous systems

183
Path Vector Protocol
•  BGP is classified as a path vector routing protocol
(see RFC 1322)
–  A path vector protocol defines a route as a pairing between
a destination and the attributes of the path to that
destination.

12.6.126.0/24 207.126.96.43 1021 0 6461 7018 6337 11268 i

AS Path

184
Path Vector Protocol

AS11268
AS6337

AS7018

AS500

AS6461

AS600

185
Definitions
•  Transit – carrying traffic across a network, usually
for a fee
•  Peering – exchanging routing information and traffic
•  Default – where to send traffic when there is no
explicit match in the routing table

186
Default Free Zone

The default free zone is made

up of Internet routers which
have explicit routing
information about the rest of
the Internet, and therefore do
not need to use a default route
NB: is not related to where an
ISP is in the hierarchy
187
Peering and Transit example
transit
provider A Backbone provider E
Provider C

peering IXP-West peering peering IXP-East

Backbone
provider B Provider D
provider F

transit

A and B peer for free, but need

transit arrangements with C and D
to get packets to/from E and F
188
Autonomous System (AS)

AS 100

•  Collection of networks with same routing policy

•  Single routing protocol
•  Usually under single ownership, trust and
administrative control
•  Identified by a unique 32-bit integer (ASN)
189
Autonomous System Number (ASN)
•  Two ranges
0-65535 (original 16-bit range)
65536-4294967295 (32-bit range – RFC6793)
•  Usage:
0 and 65535 (reserved)
1-64495 (public Internet)
64496-64511 (documentation – RFC5398)
64512-65534 (private use only)
23456 (represent 32-bit range in 16-bit world)
65536-65551 (documentation – RFC5398)
65552-4199999999 (public Internet)
4200000000-4294967295 (private use only)
•  32-bit range representation specified in RFC5396
–  Defines “asplain” (traditional format) as standard notation

190
Autonomous System Number (ASN)
•  ASNs are distributed by the Regional Internet
Registries
–  They are also available from upstream ISPs who are
members of one of the RIRs
•  Current 16-bit ASN assignments up to 63487 have
been made to the RIRs
–  Around 44500 are visible on the Internet
–  Around 1500 left unassigned
•  Each RIR has also received a block of 32-bit ASNs
–  Out of 4800 assignments, around 3700 are visible on the
Internet
•  See www.iana.org/assignments/as-numbers

191
Configuring BGP in Cisco IOS
•  This command enables BGP in Cisco IOS:
router bgp 100

•  For ASNs > 65535, the AS number can be entered

in either plain or dot notation:
router bgp 131076
or
router bgp 2.4

•  IOS will display ASNs in plain notation by default

–  Dot notation is optional:
router bgp 2.4
bgp asnotation dot

192
BGP Basics
Peering

A C

AS 100 AS 101

B D

E
•  Runs over TCP – port 179
•  Path vector protocol AS 102
•  Incremental updates
•  “Internal” & “External” BGP
193
Demarcation Zone (DMZ)

A C
DMZ
AS 100 Network AS 101
B D

AS 102

•  DMZ is the link or network shared between ASes

194
BGP General Operation
•  Learns multiple paths via internal and external BGP
speakers
•  Picks the best path and installs it in the routing
table (RIB)
•  Best path is sent to external BGP neighbours
•  Policies are applied by influencing the best path
selection

195
Constructing the Forwarding Table
•  BGP “in” process
–  receives path information from peers
–  results of BGP path selection placed in the BGP table
–  “best path” flagged

•  BGP “out” process

–  announces “best path” information to peers

•  Best path stored in Routing Table (RIB)

•  Best paths in the RIB are installed in forwarding
table (FIB) if:
–  prefix and prefix length are unique
–  lowest “protocol distance”

196
Constructing the Forwarding Table

discarded
BGP in
in
process accepted
everything

bgp BGP routing

peer table table

best paths
BGP out forwarding
out table
process

197
eBGP & iBGP
•  BGP used internally (iBGP) and externally (eBGP)
•  iBGP used to carry
–  Some/all Internet prefixes across ISP backbone
–  ISP’s customer prefixes

•  eBGP used to
–  Exchange prefixes with other ASes
–  Implement routing policy

198
BGP/IGP model used in ISP networks
•  Model representation

eBGP eBGP eBGP

iBGP iBGP iBGP iBGP

IGP IGP IGP IGP

AS1 AS2 AS3 AS4

199
External BGP Peering (eBGP)

AS 100 AS 101
C

•  Between BGP speakers in different AS

•  Should be directly connected
•  Never run an IGP between eBGP peers

200
Configuring External BGP

ip address on
ethernet interface
Router A in AS100

interface ethernet 5/0

ip address 102.102.10.2 255.255.255.240
! Local ASN
router bgp 100
network 100.100.8.0 mask 255.255.252.0
neighbor 102.102.10.1 remote-as 101 Remote ASN
neighbor 102.102.10.1 prefix-list RouterC in
neighbor 102.102.10.1 prefix-list RouterC out
!
ip address of Router Inbound and
C ethernet interface outbound filters
201
Configuring External BGP

ip address on
ethernet interface
Router C in AS101

interface ethernet 1/0/0

ip address 102.102.10.1 255.255.255.240
! Local ASN
router bgp 101
network 100.100.64.0 mask 255.255.248.0
neighbor 102.102.10.2 remote-as 100 Remote ASN
neighbor 102.102.10.2 prefix-list RouterA in
neighbor 102.102.10.2 prefix-list RouterA out
!
ip address of Router Inbound and
A ethernet interface outbound filters
202
Internal BGP (iBGP)
•  BGP peer within the same AS
•  Not required to be directly connected
–  IGP takes care of inter-BGP speaker connectivity

•  iBGP speakers must be fully meshed:

–  They originate connected networks
–  They pass on prefixes learned from outside the ASN
–  They do not pass on prefixes learned from other iBGP
speakers

203
Internal BGP Peering (iBGP)

AS 100
B
A
C

•  Topology independent
•  Each iBGP speaker must peer with every other
iBGP speaker in the AS
204
Peering between Loopback Interfaces

AS 100

C
A

•  Peer with loop-back interface

–  Loop-back interface does not go down – ever!
•  Do not want iBGP session to depend on state of a
single interface or the physical topology
205
Configuring Internal BGP

ip address on
loopback interface
Router A in AS100

interface loopback 0
ip address 105.3.7.1 255.255.255.255
!
router bgp 100 Local ASN
network 100.100.1.0
neighbor 105.3.7.2 remote-as 100 Local ASN
neighbor 105.3.7.2 update-source loopback0
neighbor 105.3.7.3 remote-as 100
neighbor 105.3.7.3 update-source loopback0
!
ip address of Router
B loopback interface
206
Configuring Internal BGP

ip address on
loopback interface
Router B in AS100

interface loopback 0
ip address 105.3.7.2 255.255.255.255
!
router bgp 100 Local ASN
network 100.100.1.0
neighbor 105.3.7.1 remote-as 100 Local ASN
neighbor 105.3.7.1 update-source loopback0
neighbor 105.3.7.3 remote-as 100
neighbor 105.3.7.3 update-source loopback0
!
ip address of Router
A loopback interface
207
Inserting prefixes into BGP
•  Two ways to insert prefixes into BGP
–  redistribute static
–  network command

208
Inserting prefixes into BGP –
redistribute static
•  Configuration Example:
router bgp 100
redistribute static
ip route 102.10.32.0 255.255.254.0 serial0

•  Static route must exist before redistribute

command will work
•  Forces origin to be “incomplete”
•  Care required!

209
Inserting prefixes into BGP –
redistribute static
•  Care required with redistribute!
–  redistribute <routing-protocol> means everything in
the <routing-protocol> will be transferred into the current
routing protocol
–  Will not scale if uncontrolled
–  Best avoided if at all possible
–  redistribute normally used with “route-maps” and under
tight administrative control

210
Inserting prefixes into BGP –
network command
•  Configuration Example
router bgp 100
network 102.10.32.0 mask 255.255.254.0
ip route 102.10.32.0 255.255.254.0 serial0

•  A matching route must exist in the routing table

before the network is announced
•  Forces origin to be “IGP”

211
Configuring Aggregation
•  Three ways to configure route aggregation
–  redistribute static
–  aggregate-address
–  network command

212
Configuring Aggregation
•  Configuration Example:
router bgp 100
redistribute static
ip route 102.10.0.0 255.255.0.0 null0 250

•  Static route to “null0” is called a pull up route

–  Packets only sent here if there is no more specific match in
the routing table
–  Distance of 250 ensures this is last resort static
–  Care required – see previously!

213
Configuring Aggregation –
Network Command
•  Configuration Example
router bgp 100
network 102.10.0.0 mask 255.255.0.0
ip route 102.10.0.0 255.255.0.0 null0 250

•  A matching route must exist in the routing table

before the network is announced
•  Easiest and best way of generating an aggregate

214
Configuring Aggregation –
aggregate-address command
•  Configuration Example:
router bgp 100
network 102.10.32.0 mask 255.255.252.0
aggregate-address 102.10.0.0 255.255.0.0 [summary-only]

•  Requires more specific prefix in BGP table before

aggregate is announced
•  summary-only keyword
–  Optional keyword which ensures that only the summary is
announced if a more specific prefix exists in the routing table
 Summary
BGP neighbour status
Router6>sh ip bgp sum!

BGP router identifier 10.0.15.246, local AS number 10!

BGP table version is 16, main routing table version 16!

7 network entries using 819 bytes of memory!

14 path entries using 728 bytes of memory!

2/1 BGP path/bestpath attribute entries using 248 bytes of memory!

0 BGP route-map cache entries using 0 bytes of memory!

0 BGP filter-list cache entries using 0 bytes of memory!

BGP using 1795 total bytes of memory!

BGP activity 7/0 prefixes, 14/0 paths, scan interval 60 secs!

Neighbor V AS MsgRcvd MsgSent TblVer InQ OutQ Up/Down State/PfxRcd!

10.0.15.241 4 10 9 8 16 0 0 00:04:47 2!

10.0.15.242 4 10 6 5 16 0 0 00:01:43 2!

10.0.15.243 4 10 9 8 16 0 0 00:04:49 2!

BGP Version Updates sent Updates waiting

...!

and received 216

 Summary
BGP Table
Router6>sh ip bgp!

BGP table version is 16, local router ID is 10.0.15.246!

Status codes: s suppressed, d damped, h history, * valid, > best, i - internal, !

r RIB-failure, S Stale, m multipath, b backup-path, f RT-Filter, !

x best-external, a additional-path, c RIB-compressed, !

Origin codes: i - IGP, e - EGP, ? - incomplete!

RPKI validation codes: V valid, I invalid, N Not found!

Network Next Hop Metric LocPrf Weight Path!

*>i 10.0.0.0/26 10.0.15.241 0 100 0 i!

*>i 10.0.0.64/26 10.0.15.242 0 100 0 i!

*>i 10.0.0.128/26 10.0.15.243 0 100 0 i!

*>i 10.0.0.192/26 10.0.15.244 0 100 0 i!

*>i 10.0.1.0/26 10.0.15.245 0 100 0 i!

*> 10.0.1.64/26 0.0.0.0 0 32768 i!

*>i 10.0.1.128/26 10.0.15.247 0 100 0 i!

*>i 10.0.1.192/26 10.0.15.248 0 100 0 i!

*>i 10.0.2.0/26 10.0.15.249 0 100 0 i!

*>i 10.0.2.64/26 10.0.15.250 0 100 0 i!

...!

217
Summary
•  BGP4 – path vector protocol
•  iBGP versus eBGP
•  stable iBGP – peer with loopbacks
•  announcing prefixes & aggregates

218
Thank you!
End of Session