1 of 42

1

Internet Routing Protocols

2 of 42

Router Functions

  • Routing
    • Building maps
    • Providing directions
    • Routing Table
  • Switching
    • Moving packets between interfaces
    • Same as a switch

Rangsit University

2

3 of 42

Routing Table

Rangsit University

3

Destination Next Interface

192.1.1.0/24 -- f0/0

192.1.2.0/24 -- s2/0

192.1.3.0/24 192.1.2.2 s2/0

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

192.1.3.2

Longest Math

R2

R1

s2/0

s2/0

f0/0

192.1.3.3

Destination Next Interface

192.1.1.0/24 192.1.2.1 s2/0

192.1.2.0/24 -- s2/0

192.1.3.0/24 -- f0/0

Destination Next Interface

192.1.1.0/24 -- f0

Other 192.1.1.1 f0

Longest Math

4 of 42

Routing Table

Rangsit University

4

Destination Next Interface

192.1.1.0/24 -- f0/0

192.1.2.0/24 -- s2/0

192.1.3.0/24 192.1.2.2 s2/0

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

192.1.1.2

Longest Math

R2

R1

s2/0

s2/0

f0/0

192.1.3.3

Destination Next Interface

192.1.1.0/24 192.1.2.1 s2/0

192.1.2.0/24 -- s2/0

192.1.3.0/24 -- f0/0

Destination Next Interface

192.1.1.0/24 -- f0

Other 192.1.1.1 f0

Longest Math

5 of 42

Building the Routing Table

  • Hardware state
    • Directly Connect links

Routers must learn destinations that are not directly connected.

  • Static
    • Routes are defined manually
  • Dynamic
    • Routes are learned from Routing Protocols

Rangsit University

5

6 of 42

Routing Table

Rangsit University

6

Destination Next Interface

192.1.1.0/24 -- e0

192.1.2.0/24 -- s0

192.1.3.0/24 192.1.2.2 s0

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

e0

Directly Connect

R2

R1

s0

s1

e0

192.1.3.3

Destination Next Interface

192.1.1.0/24 192.1.2.1 s1

192.1.2.0/24 -- s1

192.1.3.0/24 -- e0

Destination Next Interface

192.1.1.0/24 -- e0

Other 192.1.1.1 e0

Directly Connect

7 of 42

Static Route

  • Routes configured manually
  • Useful when few or just one route exist
  • Frequently used for default route

Rangsit University

7

R1(config)#ip route 192.1.3.0 255.255.255.0 192.1.2.2

R2(config)#ip route 192.1.1.0 255.255.255.0 192.1.2.1

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

R2

R1

s2/0

s2/0

f0/0

192.1.3.3

8 of 42

Static Route

Rangsit University

8

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

R2

R1

s2/0

s2/0

f0/0

192.1.4.2

f1/0

192.1.4.1

R1(config)#ip route 192.1.3.0 255.255.255.0 192.1.2.2

R1(config)#ip route 192.1.4.0 255.255.255.0 192.1.2.2

R1(config)#ip route 0.0.0.0 0.0.0.0 192.1.2.2

R2

  • Routes configured manually
  • Useful when few or just one route exist
  • Frequently used for default route

9 of 42

No single default route

Rangsit University

9

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

R2

R1

s2/0

s2/0

f0/0

192.1.x.2

f2/0

192.1.4.1

R2

192.1.5.1

s3/0

R3

192.1.5.2

s2/0

…

192.1.4.2

R1(config)#ip route 192.1.3.0 255.255.255.0 192.1.2.2

R1(config)#ip route 192.1.4.0 255.255.255.0 192.1.5.2

…

…

10 of 42

Dynamic routes

Rangsit University

10

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

R2

R1

s2/0

s2/0

f0/0

f2/0

192.1.4.1

R2

192.1.5.1

s3/0

R3

192.1.5.2

s2/0

192.1.4.2

192.1.6.1

s3/0

192.1.6.2

s3/0

R1(config)#ip route 192.1.4.0 255.255.255.0 192.1.2.2

R1(config)#ip route 192.1.4.0 255.255.255.0 192.1.5.2

X

11 of 42

1

Internet Architecture and Routing Protocols

12 of 42

Building the Routing Table

Dynamic: Routing table is computed base on Information exchanged by Routing Protocol

Rangsit University

12

Rules define

  • How to exchange information
  • How to calculate the best routes

13 of 42

Internet Architecture

  • Routers (then called “Gateways”) had complete information about all possible destinations - They are referred to as core routers
  • Used the Gateway-to-Gateway Protocol (GGP), a distance vector Routing Protocol

Rangsit University

13

ARPANET

Gateway

Gateway

First there was the ARPANET

Gateway

Gateway

H

H

H

H

H

H

14 of 42

Internet Architecture

  • Then LANs 🡪 Campus Network 🡪 Enterprise Networks were connected to the ARPANET
  • Each Enterprise Networks becomes larger and contain many subnetworks

Rangsit University

14

Subnet

Subnet

Subnet

ARPANET

Core Router

Core Router

Core Router

H

H

H

H

H

Subnet

H

Subnet

H

15 of 42

Autonomous System (AS)

  • A set of hosts and routers under a single routing policy.
  • From a router point of view all parts of an AS must remain connected.
  • AS summarized the route inside and exchange information with core router
  • Core routers know only the route to an AS

Rangsit University

15

Subnet

Subnet

Subnet

ARPANET

Core Router

Core Router

Core Router

H

H

H

H

H

Subnet

H

Subnet

H

AS-1

AS-2

AS-3

16 of 42

Concepts of AS

  • Each AS is identified by a 16-bits “AS-number” assigned by the numbering authority.
  • Example of ASs
    • A corporate network linking several local networks through a corporate backbone
    • A set of client networks served by a single ISP

Rangsit University

16

AS

AS

AS

AS

Internet Backbone

Default Free Zone (DFZ)

Core Router

Core Router

Core Router

Core Router

Default route

17 of 42

Types of ASs

Rangsit University

17

AS 3

(transit)

AS 5

(stub)

AS 1

(transit)

AS 6

(Multihomed)

AS 2

(transit)

AS 4

(stub)

Transit

  • Multiple connections to other ASs
  • Refuses to carry non local (transit) traffic
  • E.g., a well-connected corporation

Stub

  • Single connection to another AS
  • All traffic is local (i.e., originates or terminates at the AS)
  • E.g., a typical corporation

Multihomed

  • Multiple connections to other ASs
  • Accepts local and nonlocal (transit) traffic
  • E.g., ISP or backbone operator

18 of 42

Internet Routing Protocols

Rangsit University

18

Exterior Gateway Protocol (EGP) is used to exchange routing information between ASs’ edge router to implement routing policy

Interior Gateway Protocol (IGP) is used within an AS to provide internal connectivity

Local

Subnet-3

Local

Subnet-2

Local

Subnet-1

Local

Subnet-3

Local

Subnet-2

Local

Subnet-1

AS-1

AS-2

Local

Subnet-3

Local

Subnet-2

Local

Subnet-1

AS-3

19 of 42

Internet Routing Protocols

  • Interior Routing Protocol
    • Distance-Vector Routing: e.g., RIP, IGRP
    • Link-State Routing: e.g., OSPF, IS-IS
  • Exterior Routing Protocol
    • Path Vector Routing: e.g., BGP

Rangsit University

19

20 of 42

Distance Vector Routing Protocols

  • Pass periodic copies of routing table to neighbor �routers and accumulate distance vectors

Rangsit University

20

C

D

B

A

C

B

A

D

Routing

Table

Routing

Table

Routing

Table

Routing

Table

Distance—How Far�Vector—In Which Direction

  • RIP
  • IGRP

21 of 42

Routing Information Protocol (RIP)

  • Designed by UC Berkeley, distributed with 4 BSD Unix
  • Widely available
  • Easy to implement
  • Usually free
  • Simple = limited
  • Hop count metric
  • Distance Vector
  • Periodic update
  • RIP message are transmitted using UDP port 520

Rangsit University

21

R1

R2

R3

T1

56k

T1

0 Hops

1 Hop

Path A

Path B

Hops Count Metric: limit to 15

22 of 42

Distance Vector— Operation

  • Routers discover the best path to �destinations from each neighbor.

Rangsit University

22

A

B

C

10.1.0.0

10.2.0.0

10.3.0.0

10.4.0.0

E0

S0

S0

S1

S0

E0

Routing Table

10.2.0.0

10.3.0.0

0

0

S0

S1

Routing Table

10.3.0.0

S0

0

10.4.0.0

E0

0

Routing Table

10.1.0.0

10.2.0.0

E0

S0

0

0

23 of 42

Distance Vector— Operation

Rangsit University

23

A

B

C

10.1.0.0

10.2.0.0

10.3.0.0

10.4.0.0

E0

S0

S0

S1

S0

E0

Routing Table

10.1.0.0

10.2.0.0

Routing Table

10.2.0.0

10.3.0.0

10.4.0.0

0

0

1

S0

S1

S1

Routing Table

10.3.0.0

S0

0

10.4.0.0

E0

0

10.2.0.0

S0

1

E0

S0

0

0

  • Routers discover the best path to �destinations from each neighbor.

24 of 42

Distance Vector— Operation

Rangsit University

24

A

B

C

10.1.0.0

10.2.0.0

10.3.0.0

10.4.0.0

E0

S0

S0

S1

S0

E0

Routing Table

10.1.0.0

10.2.0.0

10.3.0.0

10.4.0.0

Routing Table

10.2.0.0

10.3.0.0

10.4.0.0

10.1.0.0

0

0

1

1

S0

S1

S1

S0

Routing Table

10.3.0.0

S0

0

10.4.0.0

E0

0

10.2.0.0

S0

1

E0

S0

S0

1

2

0

0

  • Routers discover the best path to �destinations from each neighbor.

S0

25 of 42

Distance Vector— Operation

Rangsit University

25

A

B

C

10.1.0.0

10.2.0.0

10.3.0.0

10.4.0.0

E0

S0

S0

S1

S0

E0

Routing Table

10.1.0.0

10.2.0.0

10.3.0.0

10.4.0.0

Routing Table

10.2.0.0

10.3.0.0

10.4.0.0

10.1.0.0

0

0

1

1

S0

S1

S1

S0

Routing Table

10.3.0.0

S0

0

10.4.0.0

E0

0

10.2.0.0

S0

10.1.0.0

S0

1

2

E0

S0

S0

S0

1

2

0

0

  • Routers discover the best path to �destinations from each neighbor.

26 of 42

Configuring RIP

Rangsit University

26

R1(config)#router rip

R1(config-router)#network 192.1.1.0

R1(config-router)#network 192.1.2.0

192.1.3.1

192.1.1.1

192.1.2.1

192.1.3.2

192.1.1.2

192.1.2.2

f0/0

R2

R1

s2/0

s2/0

f0/0

192.1.3.3

R2(config)#router rip

R2(config-router)#network 192.1.2.0

R2(config-router)#network 192.1.3.0

27 of 42

When to Use RIP

  • Implementation in a few hours
  • Good for stable links
  • Good for small networks
  • Multivendor environment

Rangsit University

27

28 of 42

IGRP (Interior Gateway Routing Protocol)

  • Cisco developed
  • Distance vector
  • Compound metric
    • Delay
    • Bandwidth
    • Reliability
    • Load
    • Etc.

Rangsit University

28

R1

R2

R3

T1

56k

T1

29 of 42

How the IGRP Metrics Work

  • Bandwidth dominates short paths
  • Delay dominates long paths
  • Configure bandwidth on all interfaces

Rangsit University

29

Delay Metric�Based on

D1 + D2 + D3

Bandwidth�Metric Based�on 64kbps

D1

D2

D3

1.5 Mbps

64 kbps

1.5 Mbps

30 of 42

Configuring IGRP

Rangsit University

30

Router(config-router)#network network-number

  • Selects participating attached networks

Router(config)#router igrp autonomous-system

  • Defines IGRP as the IP routing protocol

31 of 42

IGRP Configuration Example

Rangsit University

31

router igrp 100

network 172.16.0.0

network 10.0.0.0

router igrp 100

network 10.0.0.0

router igrp 100

network 192.168.1.0

network 10.0.0.0

Autonomous System = 100

172.16.1.1

S2

E0

S3

192.168.1.1

10.1.1.1

10.2.2.2

10.1.1.2

S2

S3

10.2.2.3

172.16.1.0

A

B

C

192.168.1.0

E0

32 of 42

Open Shortest Path First protocol (OSPF)

  • Precise metric, Multiple metrics, Bandwidth based
  • Link State Routing Protocol (RFC 1583)
  • Centralized Dijkstra Algorithm

🡪 Fast Convergence

  • Hierarchical Structure may be achieved by partitioned AS into “areas”
  • …

Rangsit University

32

33 of 42

Precise metric, Bandwidth based

  • Precise metrics derived from bandwidth

100 / bandwidth (Mbps)

    • 56-kbps serial link = 1785 64-kbps serial link = 1562
    • T1 (1.544-Mbps) = 65 E1 (2.048-Mbps) = 48
    • 4-Mbps Token Ring = 25 16-Mbps Token Ring = 6
    • Ethernet = 10 Fast Ethernet / FDDI = 1

Rangsit University

33

R1

R2

R3

T1

56k

T1

1785

65+65=130

Path A

Path B

34 of 42

Link State Routing (RFC 1583)

    • Runs directly over IP (Protocol 89)
    • Neighbor discovery
      • Exchange Hellos with neighbor Routers
      • Multicast IP address: 224.0.0.5
    • Constructing a Topology Database
      • Each router broadcast LSA (Links State Advertisement) in the area
    • LSA (Link State Advertisement) are sent (using flooding)
      • triggered for update base on network failure or change
    • Based on Topology DB, Direct Graph is constructed
    • After receive new LSA
      • Each router constructs routes to each known destination in form of a shortest paths tree by running “Dijkstra’s algorithm” on the direct graph

Rangsit University

34

35 of 42

Adjacencies Database

Rangsit University

35

  • From hello response, each Router creates Adjacencies database

Z

X

Y

Net A

Net B

Net C

Net D

10 Mbps

10 Mbps

10 Mbps

100 Mbps

100 Mbps

100 Mbps

BR

Neighbors on Net D are Router Y, Z

Neighbors on Net D are Router X, Z

Neighbors on Net D are Router X,Y

36 of 42

Link State Advertisement

Rangsit University

36

Z

X

Y

Net A

Net B

Net C

Net D

10

10

10

1

1

1

BR

Y’s LSA

Net Metric

A 10

D 1

Z’s LSA

Net Metric

B 10

D 1

X’s LSA

Net Metric

C 10

D 1

  • Based Link Status, each router create LSA and broadcast LSA to other routers in the area.

37 of 42

Topology Database

Rangsit University

37

  • Based received LSA, each router create Topology database of the area.

Z

X

Y

Net A

Net B

Net C

Net D

10

10

10

1

1

1

BR

38 of 42

Routing Table

Rangsit University

38

Net A

Y

Z

X

Net D

Net C

Net B

10

10

10

1

BR

E1

E2

  • Based on to Topology database, Dijkstra’s algorithm is used to calculated routing table
  • In Dijkstra’s algorithm during each step, the next shortest path is added.
  • At k th step, shortest path to k nodes are determined.
  • Collection all shortest paths form Shortest Path Tree.

Destination

Net A

Net B

Net C

Net D

Metric

11

11

10

1

Next

Y

Z

local

local

Int

E1

E1

E2

E1

39 of 42

Hierarchical Structure and Areas

    • An AS may be partitioned into areas.
    • There must be single contiguous area called “Backbone”(Area #0).
    • All other areas must connect to other areas via backbone
    • Each area has it own Link State Database.
    • Results in marked reduction of routing traffic

Rangsit University

39

Backbone

Area #0

Area #3

Area #2

Area #1

40 of 42

Hierarchical Structure and Areas

  • ASBR summarize routes for ISP
  • An ABR summarize routes for its area
  • Internal Routers compute route within its areas
  • Backbone Routers compute route within backbone areas

Rangsit University

40

Backbone

Area #0

Area #3

Area #2

Area #1

ISP

Autonomous System�Boundary Router (ASBR)

Area Border Router (ABR)

Internal Router

Backbone Router

41 of 42

Distance Vector Vs Link-State Routing

Rangsit University

41

42 of 42

When to Use OSPF

  • Large hierarchical networks
  • Complex networks
  • Fast convergence
  • Multi-vendor

Rangsit University

42