Routing Basics

ISP Workshops

Last updated 18th January 2016

Routing Concepts
p IPv4

& IPv6
p Routing
p Forwarding
p Some definitions
p Policy options
p Routing Protocols

IPv4
p Internet

still uses IPv4

(legacy protocol)
n Addresses are 32 bits long
n Addresses are written as decimal with each 8bit range separated by a .
n Range from 1.0.0.0 to 223.255.255.255
n 0.0.0.0 to 0.255.255.255 and 224.0.0.0 to
255.255.255.255 have special uses
n

p IPv4

address has a network portion and a

host portion
3

IPv6
p Internet

is starting to use IPv6

Addresses are 128 bits long

n Addresses are written as hexadecimal with
each 16-bit range separated by :
n Internet addresses range from 2000::/16 to
3FFF::/16
n The remaining IPv6 range is reserved or has
special uses
n

p IPv6

address has a network portion and a

host portion
4

IP address format
p Address
n

and subnet mask

IPv4 written as
12.34.56.78 255.255.255.0 or
p 12.34.56.78/24
p

IPv6 written as
p

mask represents the number of network bits in

the address
p

2001:DB8:A::1/64

Usually referred to as the subnet size

The remaining bits are the host bits

5

IP subnets
p IPv4
n

example 12.34.56.78/24

32 bits in an IPv4 address

24 bits for the network portion
p Leaves 8 bits for the host portion
p 8 bits means there are 28 possible hosts on this
subnet
p

p IPv6
n

example 2001:DB8:A::1/64

128 bits in an IPv6 address

64 bits for the network portion
p Leaves 64 bits for the host portion
p 64 bits means there are 264 possible hosts on this
subnet
p

What does a router do?

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
8

Routing versus Forwarding

p Routing

= building
maps and giving
directions

p Forwarding

=
moving packets
between interfaces
according to the
directions
9

IP Routing finding the path

p Path

derived from information received

from a routing protocol
p Several alternative paths may exist
n

Best path stored in forwarding table

p Decisions

are updated periodically or as

topology changes (event driven)
p Decisions are based on:
n

Topology, policies and metrics (hop count,

filtering, delay, bandwidth, etc.)
10

IP route lookup
p Based

on destination IP address
p longest match routing
More specific prefix preferred over less specific
prefix
n Example: packet with destination of
2001:DB8:1::1/128 is sent to the router
announcing 2001:DB8:1::/48 rather than the
router announcing 2001:DB8::/32.
n

11

IP route lookup
p Based

on destination IP address
Packet: Destination
IP address: 2001:db8:1::1
R1

2001:db8::/32
announced
from here

R3

R2

2001:db8::/32 R3
2001:db8:1::/48 R4
2001:db9::/32 R5
2001:dba::/32 R6

R2s IP routing table

R4

2001:db8:1::/48
announced from
here

12

IP route lookup:
Longest match routing
p Based

on destination IP address
Packet: Destination
IP address: 2001:db8:1::1
R1

2001:db8::/32 R3
2001:db8:1::/48 R4
2001:db9::/32 R5
2001:dba::/32 R6

2001:db8::/32
announced
from here

R3

R2
2001:db8:1::1 && ffff:ffff::
vs.
Match!
2001:db8:: && ffff:ffff::

R2s IP routing table

R4

2001:db8:1::/48
announced from
here

13

IP route lookup:
Longest match routing
p Based

on destination IP address
Packet: Destination
IP address: 2001:db8:1::1
R1

2001:db8::/32 R3
2001:db8:1::/48 R4
2001:db9::/32 R5
2001:dba::/32 R6

2001:db8::/32
announced
from here

R3

R2
2001:db8:1::1 && ffff:ffff:ffff::
vs.
2001:db8:1:: && ffff:ffff:ffff::

R2s IP routing table

R4

2001:db8:1::/48
announced from
here

Match as well!
14

IP route lookup:
Longest match routing
p Based

on destination IP address
Packet: Destination
IP address: 2001:db8:1::1
R1

2001:db8::/32 R3
2001:db8:1::/48 R4
2001:db9::/32 R5
2001:dba::/32 R6

2001:db8::/32
announced
from here

R3

R2
R4
2001:db8:1::1 && ffff:ffff::
vs.
2001:db9:: && ffff:ffff::

R2s IP routing table

2001:db8:1::/48
announced from
here

Does not match!

15

IP route lookup:
Longest match routing
p Based

on destination IP address
Packet: Destination
IP address: 2001:db8:1::1
R1

2001:db8::/32 R3
2001:db8:1::/48 R4
2001:db9::/32 R5
2001:dba::/32 R6

2001:db8::/32
announced
from here

R3

R2
R4

2001:db8:1::/48
announced from
2001:db8:1::1 && ffff:ffff::
here
vs.
Does not match!
2001:dba:: && ffff:ffff::

R2s IP routing table

16

IP route lookup:
Longest match routing
p Based

on destination IP address
Packet: Destination
IP address: 2001:db8:1::1
R1

2001:db8::/32 R3
2001:db8:1::/48 R4
2001:db9::/32 R5
2001:dba::/32 R6

2001:db8::/32
announced
from here

R3

R2
R4

2001:db8:1::/48
Longest match, 48 bit netmask announced from
here

R2s IP routing table

17

IP Forwarding
p
p
p

Router decides which interface a packet is sent to

Forwarding table populated by routing process
Forwarding decisions:
n
n
n

destination address
class of service (fair queuing, precedence, others)
local requirements (packet filtering)

Forwarding is usually aided by special hardware

18

Routing Information Base (RIB)

Forwarding Information Base (FIB)

Routing Tables Feed the Forwarding

Table
BGP 4 Routing Table
OSPF Link State Database
Connected Routes
Static Routes
19

RIBs and FIBs

p

FIB is the Forwarding Table

n
n
n
n

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!
Cisco IOS: show ip cef

RIB is the Routing Table

n

n
n

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
20
Cisco IOS: show ip route

Explicit versus Default Routing

p

Default:
n
n
n

Explicit: (default free zone)

n
n
n

Simple, cheap (CPU, memory, bandwidth)

No overhead
Low granularity (metric games)
Complex, expensive (CPU, memory, bandwidth)
High overhead
High granularity (every destination known)

Hybrid:
n
n
n

Minimise overhead
Provide useful granularity
Requires some filtering knowledge
21

Egress Traffic
p How

packets leave your network

p Egress traffic depends on:
Route availability (what others send you)
n Route acceptance (what you accept from
others)
n Policy and tuning (what you do with routes
from others)
n Peering and transit agreements
n

22

Ingress Traffic
p How

packets get to your network and your

customers networks
p Ingress traffic depends on:
What information you send and to whom
n Based on your addressing and ASs
n Based on others policy (what they accept from
you and what they do with it)
n

23

Autonomous System (AS)

AS 100

p
p
p

Collection of networks with same routing policy

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

Definition of terms
p

Neighbours
n
n

Announce
n

receive and use routing information sent by a neighbour

Originate
n

send routing information to a neighbour

Accept
n

ASs which directly exchange routing information

Routers which exchange routing information

insert routing information into external announcements

(usually as a result of the IGP)

Peers
n

routers in neighbouring ASs or within one AS which

exchange routing and policy information
25

Routing flow and packet flow

packet flow

AS 1

accept
announce

routing flow

announce
accept

AS 2

packet flow

For networks in AS1 and AS2 to communicate:

AS1
AS2
AS2
AS1

must
must
must
must

announce to AS2
accept from AS1
announce to AS1
accept from AS2
26

Routing flow and Traffic flow

p Traffic

flow is always in the opposite

direction of the flow of Routing
information
Filtering outgoing routing information inhibits
traffic flow inbound
n Filtering inbound routing information inhibits
traffic flow outbound
n

27

Routing Flow/Packet Flow:

With multiple ASes
AS 1

AS 34

N1

AS16
AS 8

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

n
n
n
n

N16

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

28

Routing Flow/Packet Flow:

With multiple ASes
AS 1

AS 34

N1

AS16
AS 8

N16

p As

more and more paths are implemented

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

Routing Policy
p Used

to control traffic flow in and out of an

ISP network
p ISP makes decisions on what routing
information to accept and discard from its
neighbours
Individual routes
n Routes originated by specific ASes
n Routes traversing specific ASes
n Routes belonging to other groupings
n

Groupings which you define as you see fit

30

Routing Policy Limitations

red

red

Internet
green

AS99
green
packet flow

p
p

AS99 uses red link for traffic to the red AS and

the green link for remaining traffic
To implement this policy, AS99 has to:
n
n

Accept routes originating from the red AS on the red link

Accept all other routes on the green link
31

Routing Policy Limitations

red

red

Internet

AS99

AS22
green

green
packet flow

p
p

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

32

Routing Policy Issues

p January
n

25800 IPv6 prefixes & 580000 IPv4 prefixes

p

2016:

Not realistic to set policy on all of them individually

52500 origin ASs

p

Too many to try and create individual policies for

p Routes

tied to a specific AS or path may

be unstable regardless of connectivity
p Solution: Groups of ASs are a natural
abstraction for filtering purposes
33

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

1: How Does Routing Work?

p Internet

is made up of the ISPs who

connect to each others networks
p How does an ISP in Kenya tell an ISP in
Japan what customers they have?
p And how does that ISP send data packets
to the customers of the ISP in Japan, and
get responses back
n

After all, as on a local ethernet, two way

packet flow is needed for communication
between two devices
35

2: How Does Routing Work?

p ISP

in Kenya could buy a direct connection

to the ISP in Japan
n

But this doesnt scale thousands of ISPs,

would need thousands of connections, and cost
would be astronomical

p 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
n This process repeats until the information
reaches the ISP in Japan
n

36

3: How Does Routing Work?

p This

process is called Routing

p The mechanisms used are called Routing
Protocols
p Routing and Routing Protocols ensures
that
The Internet can scale
n Thousands of ISPs can provide connectivity to
each other
n We have the Internet we see today
n

37

4: How Does Routing Work?

p

ISP in Kenya doesnt actually tell his

neighbouring ISPs the names of the customers
n

(network equipment does not understand names)

Instead, he has received an IP address block as a

member of the Regional Internet Registry serving
Kenya
n
n

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

38

Routing Protocols
p Routers

use routing protocols to

exchange routing information with each
other
IGP is used to refer to the process running on
routers inside an ISPs network
n EGP is used to refer to the process running
between routers bordering directly connected
ISP networks
n

39

What Is an IGP?
p Interior

Gateway Protocol
p Within an Autonomous System
p Carries information about internal
infrastructure prefixes
p Two widely used IGPs:
OSPF
n IS-IS
n

40

Why Do We Need an IGP?

p ISP

backbone scaling

Hierarchy
n Limiting scope of failure
n Only used for ISPs infrastructure addresses,
not customers or anything else
n Design goal is to minimise number of prefixes
in IGP to aid scalability and rapid convergence
n

41

What Is an EGP?
p Exterior

Gateway Protocol
p Used to convey routing information
between Autonomous Systems
p De-coupled from the IGP
p Current EGP is BGP

42

Why Do We Need an EGP?

p Scaling

to large network

Hierarchy
n Limit scope of failure
n

p Define

Administrative Boundary

p Policy

Control reachability of prefixes

n Merge separate organisations
n Connect multiple IGPs
n

43

Interior versus Exterior

Routing Protocols
p Interior

Automatic
neighbour discovery
n Generally trust your
IGP routers
n Prefixes go to all
IGP routers
n Binds routers in one
AS together
n

p Exterior

Specifically
configured peers
n Connecting with
outside networks
n Set administrative
boundaries
n Binds ASs together
n

44

Interior versus Exterior

Routing Protocols
p Interior

Carries ISP
infrastructure
addresses only
n ISPs aim to keep
the IGP small for
efficiency and
scalability
n

p Exterior

Carries customer
prefixes
n Carries Internet
prefixes
n EGPs are
independent of ISP
network topology
n

45

Hierarchy of Routing Protocols

Other ISPs
BGP4

BGP4
and OSPF/IS-IS

BGP4
IXP

Static/BGP4
Customers
46

FYI: Default Administrative

Distances
Route Source

Cisco

Juniper

Huawei

Brocade

Connected Interface

Static Route

60

EIGRP Summary Route

N/A

N/A

External BGP

20

170

255

20

Internal EIGRP Route

90

N/A

N/A

IGRP

100

N/A

N/A

OSPF

110

10

10

110

IS-IS

115

18

15

115

RIP

120

100

100

120

EGP

140

N/A

N/A

N/A

External EIGRP

170

N/A

N/A

Internal BGP

200

170

255

200

Unknown

255

255

255

47

Routing Basics
ISP Workshops

48