Kandahar University

Computer Science Faculty

Network department

Network Routing and Switching

Lecture 9 - Chapter 5
Network Layer
Routing Protocols

Lecturer: TA. Shams Rashidy

Google Classroom: ( )
 Chapter 5: outline
5.1 introduction 5.5 The SDN control plane
5.2 routing protocols 5.6 ICMP: The Internet Control
▪ link state Message Protocol
▪ distance vector 5.7 Network management and SNMP
5.3 intra-AS routing in the Internet:
OSPF
5.4 routing among the ISPs: BGP

Network Layer: Control Plane 5-2

Making routing scalable Hierarchical routing

our routing study thus far - idealized

▪ all routers identical
▪ network “flat”
… not true in practice

scale: with 600 billions of administrative autonomy

destinations: ▪ internet = network of
▪ can’t store all networks
destinations in routing ▪ each network admin may
tables! want to control routing in
▪ routing table exchange its own network
would swamp links!

Network Layer: Control Plane 5-3

Internet approach to scalable routing
aggregate routers into regions known as “autonomous
systems” (AS) (a.k.a. “domains”)

intra-AS routing inter-AS routing

▪ routing among hosts, routers ▪ routing among AS’es
in same AS (“network”) ▪ gateways perform inter-
▪ all routers in AS must run domain routing (as well
same intra-domain protocol as intra-domain routing)
▪ routers in different AS can run
different intra-domain routing
protocol
▪ gateway router: at “edge” of
its own AS, has link(s) to
router(s) in other AS’es
Network Layer: Control Plane 5-4
Interior and exterior
▪ AS – an internetwork under the control of single organization
▪ Interior Gateway Protocols – IGP (CCNA)
• Used within single AS
▪ Exterior Gateway Protocols – EGP (CCNP)
• Used to route b/w Ass
Interconnected ASes

3c
3a 2c
3b 2a
AS3 2b
1c AS2
1a 1b AS1
1d ▪ forwarding table
configured by both intra-
and inter-AS routing
Intra-AS Inter-AS algorithm
Routing
algorithm
Routing
algorithm • intra-AS routing
determine entries for
Forwarding
table
destinations within AS
• inter-AS & intra-AS
determine entries for
external destinations
Network Layer: Control Plane 5-7
 Inter-AS tasks
▪ suppose router in AS1 AS1 must:
receives datagram 1. learn which dests are
destined outside of AS1: reachable through AS2,
• router should forward which through AS3
packet to gateway 2. propagate this
router, but which one? reachability info to all
routers in AS1
job of inter-AS routing!

3c
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer: Control Plane 5-8

Example:

Network Layer 4-9

 Example: setting forwarding table in router 1d
▪ suppose AS1 learns (via inter-AS protocol) that subnet x
reachable via AS3 (gateway 1c), but not via AS2
• inter-AS protocol propagates reachability info to all internal
routers
▪ router 1d determines from intra-AS routing info that its
interface I is on the least cost path to 1c
• installs forwarding table entry (x,I)

3c
x
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d

Network Layer 4-10

Example: choosing among multiple ASes

▪ now suppose AS1 learns from inter-AS protocol that subnet

x is reachable from AS3 and from AS2.
▪ to configure forwarding table, router 1d must determine
which gateway it should forward packets towards for dest x
• this is also job of inter-AS routing protocol!

3c
x
3a
3b
AS3 2c other
1c 2a networks
other 1a 2b
networks 1b AS2
AS1 1d
?
Network Layer 4-11
 Example: choosing among multiple ASes
▪ now suppose AS1 learns from inter-AS protocol that subnet
x is reachable from AS3 and from AS2.
▪ to configure forwarding table, router 1d must determine
towards which gateway it should forward packets for dest x
• this is also job of inter-AS routing protocol!
▪ hot potato routing: send packet towards closest of two
routers.

use routing info determine from

learn from inter-AS hot potato routing: forwarding table the
from intra-AS
protocol that subnet choose the gateway interface I that leads
protocol to determine
x is reachable via that has the to least-cost gateway.
costs of least-cost
multiple gateways smallest least cost Enter (x,I) in
paths to each
of the gateways forwarding table

Network Layer 4-12

Intra-AS Routing
▪ also known as interior gateway protocols (IGP)
▪ most common intra-AS routing protocols:
• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First (IS-IS protocol essentially same
as OSPF)
• IGRP: Interior Gateway Routing Protocol (Cisco proprietary for
decades, until 2016)

Network Layer: Control Plane 5-13

Why routing protocols?

?
Static RP vs Dynamic RP
Type of IGPs
▪ Distance Vector
• Router know only distance (hope) and vector(next hope ) like RIP
▪ Link State
• Router know the state of all links (interface ) in the internetwork, and
select the best paths. OSPF
▪ Balanced Hybrid (Enhanced Distance Vector)
• Router uses known topology from neighboring routers (not all routers) and
select the best path. EIGRP
Classification of Routing Protocols

Network Layer: Control Plane 5-17

IGRP
▪ Stand for inertial gateway routing protocol
▪ IGRP is Cisco proprietary protocol
▪ IGRP works under DVRP routing protocol category IGRP exchange
routing table after 90 second
▪ IGRP is class full routing protocol and does not support VLSM
▪ IGRP calculate cost or metric by delay ,bandwidth ,load, MTU
,reliability
▪ IGRP default cost or metric is delay and bandwidth

Network Layer 4-18

continue
▪ IGRP can do load balancing on equal path
▪ IGRP default hope is 100 and maximum is 255
▪ IGRP work on same autonomous numbers
▪ IGRP can represent on routing table by I
▪ IGRP Administrative distance is 100
▪ IGRP works under IGP routing protocol
▪ Category

Network Layer 4-19

What is IGP
▪ IGP stand for inertial Gateway protocol
▪ Those routing protocol which works on same autonomous number
are called IGP
▪ Example :IGRP .EIGRP ,& OSPF
▪

Network Layer 4-20

What is EGP
▪ EGP stand for exterior gateway protocol
▪ Those routing protocol which works on different autonomous
numbers
▪ what is autonomous number
▪ Set of network under common administration
▪ We purchase form IANA
▪ All autonomous number is 65535
▪ Used 24000

Network Layer 4-21

What is bandwidth
▪ Bandwidth :maximum transmission of data a line is called
bandwidth
▪ Delay :time taken to traverse from path
▪ Load :amount of traffic in line
▪ Reliability :those line in which failure chances less

Network Layer 4-22

EIGRP
▪ Stand for enhance inertial gateway routing protocol
▪ Also called enhance IGRP
▪ Cisco open EIGRP September 2013 before it was proprietary of
Cisco
▪ EIGRP under Hybrid category
▪ Also called hybridized protocol
▪ EIGRP is classless routing protocol and support VLSM and
subnetting

Network Layer 4-23

Continue
▪ EIGRP works on same autonomous number
▪ EIGRP calculate cost or metric by bandwidth
▪ Delay ,load ,reliability MTU
▪ EIGRP default cost or metric delay and bandwidth
▪ EIGRP default hope is 100 and maximum is 255
▪ EIGRP make adjacency with neighbor router by hello packet

Network Layer 4-24

Continue
▪ Hello packet of EIGRP share by [Link]
▪ EIGRP sends periodic update
▪ Every router sends hello packet after 5 second for neighbor ship
▪ EIGRP is fastest routing protocol and advertize
▪ Change immediately to neighbors
▪ Administrative distance is 90 it show in routing by D
▪ EIGRP use DUAL algorithm

Network Layer 4-25

Network Layer 4-26
Tables of EIGRP
▪ [Link] table
▪ [Link] table
▪ [Link] table
▪ [Link] table :best path are store in routing table
▪ [Link] table :information about neighbor router
▪ [Link] table :all path are store in topology table

Network Layer 4-27

How to check neighbor table
▪ Router #show IP EIGRP neighbors
▪ 2. how to check routing table
▪ Router #show ip route
▪ [Link] to check topology table
▪ Router # show IP eigrp topology

Network Layer 4-28

Classful and Classless Routing Protocols
▪ Classful
• Don’t care about subnet mask information
• They automatically summarize route between major networks
• RIPv1 is Classful
▪ Classless
• They send and receive subnet mask information
• Allow manual summarization
• RIPv2, OSPF, EIGRP are Classless
Administrative Distance
Matric
▪ Each routing protocol has its own way to determine the best path
to a network.
• RIP: Hop Count
• OSPF: Sum of inverse of Bandwidth (Cost)
• EIGRP: Min. Bandwidth + Total Delay
▪ Each matric has certain advantages and disadvantages
Summary of routing protocols
 RIP ( Routing Information Protocol)
▪ included in BSD-UNIX distribution in 1982
▪ distance vector algorithm
• distance metric: # hops (max = 15 hops), each link has cost 1
• DVs exchanged with neighbors every 30 sec in response message (aka
advertisement)
• each advertisement: list of up to 25 destination subnets (in IP addressing
sense)

from router A to destination subnets:

u v subnet hops
w u 1
A B
v 2
w 2
x x 3
z C D y 3
y z 2
Network Layer 4-33
RIP: example

z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
z B 7
x -- 1
…. …. ....
Network Layer 4-34
RIP: example
A-to-D advertisement
dest next hops
w - 1
x - 1
z C 4
…. … ... z
w x y
A D B

C
routing table in router D
destination subnet next router # hops to dest
w A 2
y B 2
A 5
z B 7
x -- 1
…. …. ....
Network Layer 4-35
RIP: link failure, recovery
if no advertisement heard after 180 sec -->
neighbor/link declared dead
▪ routes via neighbor invalidated
▪ new advertisements sent to neighbors
▪ neighbors in turn send out new advertisements (if tables
changed)
▪ link failure info quickly (?) propagates to entire net
▪ poison reverse used to prevent ping-pong loops (infinite
distance = 16 hops)

Network Layer 4-36

RIP table processing
❖RIP routing tables managed by application-level process called route-
d (daemon)
❖advertisements sent in UDP packets, periodically repeated

routed routed

transport transprt
(UDP) (UDP)
network forwarding forwarding network
(IP) table table (IP)
link link
physical physical

Network Layer 4-37

OSPF (Open Shortest Path First)
▪ “open”: publicly available
▪ uses link-state algorithm
• link state packet dissemination
• topology map at each node
• route computation using Dijkstra’s algorithm
▪ router floods OSPF link-state advertisements to all
other routers in entire AS
• carried in OSPF messages directly over IP (rather than
TCP or UDP
• link state: for each attached link
▪ IS-IS routing protocol: nearly identical to OSPF

Network Layer: Control Plane 5-38

OSPF “advanced” features
▪ security: all OSPF messages authenticated (to prevent
malicious intrusion)
▪ multiple same-cost paths allowed (only one path in
RIP)
▪ for each link, multiple cost metrics for different TOS
(e.g., satellite link cost set low for best effort ToS;
high for real-time ToS)
▪ integrated uni- and multi-cast support:
• Multicast OSPF (MOSPF) uses same topology data
base as OSPF
▪ hierarchical OSPF in large domains.

Network Layer: Control Plane 5-39

Hierarchical OSPF
boundary router
backbone router

backbone
area
border
routers

area 3

internal
routers
area 1
area 2

Network Layer: Control Plane 5-40

Hierarchical OSPF
▪ two-level hierarchy: local area, backbone.
• link-state advertisements only in area
• each nodes has detailed area topology; only know
direction (shortest path) to nets in other areas.
▪ area border routers: “summarize” distances to nets in
own area, advertise to other Area Border routers.
▪ backbone routers: run OSPF routing limited to
backbone.
▪ boundary routers: connect to other AS’es.

Network Layer: Control Plane 5-41

 OSPF
▪ OSPF stand for open shortest path first
▪ OSPF is a global /open standard protocol
▪ OSPF is developed by IETF OSPF works under link state category
▪ OSPF is class less routing protocol and support VLSM OSPF make
adjacency with neighbor by hello packet OSPF hello packet share by
[Link] OSPF calculate cost or metric by bandwidth OSPF
advertise change immediately to neighbor routers OSPF hope is
unlimited

Network Layer 4-42

OSPF create three table
▪ 1: routing table
▪ 2: neighbor table
▪ 3: topology table
▪ [Link] table :best path store in routing table
▪ [Link] table :information about neighbor router
▪ [Link] table :information about all paths
▪ Information about topology path

Network Layer 4-43

continue
▪ OSPF works on wild card mask
▪ OSPF router are divided into different logical area
▪ Area 0 called backbone area
▪ All routers must be connected with area 0 (zero)
▪ OSPF can represent in routing table by o letter
▪ OSPF administrative distance is 110

Network Layer 4-44

What is area

▪ Collection of routers and network are called area

▪ What is wild card mask?
▪ Is opposite of subnet mask In subnet mask on bits represent
network bits in wild card mask off bits represent network bits

Network Layer 4-45

 Chapter 5: outline
5.1 introduction 5.5 The SDN control plane
5.2 routing protocols 5.6 ICMP: The Internet Control
▪ link state Message Protocol
▪ distance vector 5.7 Network management and SNMP
5.3 intra-AS routing in the Internet:
OSPF
5.4 routing among the ISPs: BGP

Network Layer: Control Plane 5-46

Internet inter-AS routing: BGP
▪ BGP (Border Gateway Protocol): the de facto
inter-domain routing protocol
• “glue that holds the Internet together”
▪ BGP provides each AS a means to:
• eBGP: obtain subnet reachability information from
neighboring ASes
• iBGP: propagate reachability information to all AS-
internal routers.
• determine “good” routes to other networks based on
reachability information and policy
▪ allows subnet to advertise its existence to rest of
Internet: “I am here”
Network Layer: Control Plane 5-47
eBGP, iBGP connections

2b

2a 2c
∂
1b 3b
2d
1a 1c ∂
3a 3c
AS 2
1d 3d

AS 1 eBGP connectivity AS 3
iBGP connectivity

1c gateway routers run both eBGP and iBGP protools

Network Layer: Control Plane 5-48

BGP basics
▪ BGP session: two BGP routers (“peers”) exchange BGP
messages over semi-permanent TCP connection:
• advertising paths to different destination network prefixes
(BGP is a “path vector” protocol)
▪ when AS3 gateway router 3a advertises path AS3,X to AS2
gateway router 2c:
• AS3 promises to AS2 it will forward datagrams towards X

AS 3 3b
AS 1 1b
3a 3c
1a 1c
AS 2 2b 3d X
1d
BGP advertisement:
2a 2c AS3, X

2d
Network Layer: Control Plane 5-49
Path attributes and BGP routes
▪ advertised prefix includes BGP attributes
• prefix + attributes = “route”
▪ two important attributes:
• AS-PATH: list of ASes through which prefix advertisement
has passed
• NEXT-HOP: indicates specific internal-AS router to next-
hop AS
▪ Policy-based routing:
• gateway receiving route advertisement uses import policy to
accept/decline path (e.g., never route through AS Y).
• AS policy also determines whether to advertise path to
other other neighboring ASes

Network Layer: Control Plane 5-50

 BGP path advertisement
AS3 3b
AS1 1b
3a 3c
1a 1c
AS2 2b 3d X
1d AS3,X
AS2,AS3,X
2a 2c

2d

▪ AS2 router 2c receives path advertisement AS3,X (via eBGP) from AS3
router 3a
▪ Based on AS2 policy, AS2 router 2c accepts path AS3,X, propagates
(via iBGP) to all AS2 routers
▪ Based on AS2 policy, AS2 router 2a advertises (via eBGP) path AS2,
AS3, X to AS1 router 1c
Network Layer: Control Plane 5-51
BGP path advertisement
AS3 3b
AS1 1b
3a 3c
1a 1c
AS2 2b 3d X
1d AS3,X
AS2,AS3,X
2a 2c

2d

gateway router may learn about multiple paths to destination:

▪ AS1 gateway router 1c learns path AS2,AS3,X from 2a
▪ AS1 gateway router 1c learns path AS3,X from 3a
▪ Based on policy, AS1 gateway router 1c chooses path AS3,X, and
advertises path within AS1 via iBGP
Network Layer: Control Plane 5-52
BGP route selection
❖router may learn about more than 1 route to
destination AS, selects route based on:
1. local preference value attribute: policy decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria

Network Layer 4-53

BGP messages
▪ BGP messages exchanged between peers over TCP
connection
▪ BGP messages:
• OPEN: opens TCP connection to remote BGP peer and
authenticates sending BGP peer
• UPDATE: advertises new path (or withdraws old)
• KEEPALIVE: keeps connection alive in absence of
UPDATES; also ACKs OPEN request
• NOTIFICATION: reports errors in previous msg; also
used to close connection

Network Layer: Control Plane 5-54

 BGP, OSPF, forwarding table entries
Q: how does router set forwarding table entry to distant prefix?

AS3 3b
AS1 1b
1
3a 3c
1a 2 1c
local link AS2 2b 3d X
interfaces 2 1d 1 AS3,X
at 1a, 1d AS2,AS3,X
2a 2c
physical link
2d

dest interface ▪ recall: 1a, 1b, 1c learn about dest X via iBGP
… … from 1c: “path to X goes through 1c”
X 1 ▪ 1d: OSPF intra-domain routing: to get to 1c,
… … forward over outgoing local interface 1

Network Layer: Control Plane 5-55

BGP, OSPF, forwarding table entries
Q: how does router set forwarding table entry to distant prefix?

AS3 3b
AS1 1b
1
3a 3c
1a 2 1c
AS2 2b 3d X
1d
2a 2c

2d

dest interface ▪ recall: 1a, 1b, 1c learn about dest X via iBGP
… … from 1c: “path to X goes through 1c”
X 2 ▪ 1d: OSPF intra-domain routing: to get to 1c,
… … forward over outgoing local interface 1
▪ 1a: OSPF intra-domain routing: to get to 1c,
forward over outgoing local interface 2
Network Layer: Control Plane 5-56
BGP route selection
▪ router may learn about more than one route to
destination AS, selects route based on:
1. local preference value attribute: policy decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria

Network Layer: Control Plane 5-57

Hot Potato Routing
AS3 3b
AS1 1b
3a 3c
1a 1c
AS2 2b 3d X
1d 112
AS3,X
152
AS1,AS3,X 2a 263 2c
201
OSPF link weights
2d

▪ 2d learns (via iBGP) it can route to X via 2a or 2c

▪ hot potato routing: choose local gateway that has least intra-
domain cost (e.g., 2d chooses 2a, even though more AS hops
to X): don’t worry about inter-domain cost!

Network Layer: Control Plane 5-58

BGP: achieving policy via advertisements
legend: provider
B network
X
W A
customer
C network:

Suppose an ISP only wants to route traffic to/from its customer

networks (does not want to carry transit traffic between other ISPs)
▪ A advertises path Aw to B and to C
▪ B chooses not to advertise BAw to C:
▪ B gets no “revenue” for routing CBAw, since none of C, A, w are B’s
customers
▪ C does not learn about CBAw path
▪ C will route CAw (not using B) to get to w
Network Layer: Control Plane 5-59
BGP: achieving policy via advertisements
legend: provider
B network
X
W A
customer
C network:

Suppose an ISP only wants to route traffic to/from its customer

networks (does not want to carry transit traffic between other ISPs)

▪ A,B,C are provider networks

▪ X,W,Y are customer (of provider networks)
▪ X is dual-homed: attached to two networks
▪ policy to enforce: X does not want to route from B to C via X
▪ .. so X will not advertise to B a route to C
Network Layer: Control Plane 5-60
Why different Intra-, Inter-AS routing ?
policy:
▪ inter-AS: admin wants control over how its traffic
routed, who routes through its net.
▪ intra-AS: single admin, so no policy decisions needed
scale:
▪ hierarchical routing saves table size, reduced update
traffic
performance:
▪ intra-AS: can focus on performance
▪ inter-AS: policy may dominate over performance

Network Layer: Control Plane 5-61

END
?
5-62