Routing Protocols

Routing Protocols

RIP - Routing Information Protocol

IGRP/EIGRP - [Extended] Interior Gateway Routing Protocol

OSPF - Open Shortest Path First

BGP - Border Gateway Protocol, details this afternoon

RIP

Routing Information Protocol

The original routing protocol, vintage 1982 or so

Distance-vector, interior gateway proto-col

Grew out of Xerox XNS (late 70s)

Used by routed on many workstations

Maximum metric of 15

Broadcast routing protocol

Routing updates every 30 seconds

"I’m a router to network xxx.xxx.xxx.xxx in yy hops"

RIP - cont.

Convenient solution for LANs. Spoken by:

Printers

Hubs

PCs

UNIX boxes

If misused, can cause extreme network congestion and chaos

UNIX boxes should always run routed –q to avoid advertising false information

If you must use RIP, use it only to ad-vertise a handful of networks and perhaps a default route

RIP Packet Format

1 8 16 32

|-------------|--------------|-----------------------------|

| command | version (=1) | must be zero |

| | | |

|----------------------------|-----------------------------|

| address family (=2) | must be zero |

| | |

|----------------------------------------------------------|

| IP address, 32 bits |

| |

|----------------------------------------------------------|

| must be zero |

| |

|----------------------------------------------------------|

| must be zero |

| |

|----------------------------------------------------------|

| metric (1-16) |

| |

|----------------------------------------------------------|

| |

| up to 24 more routes, with same format, ie: |

| address family, 0, ip address, 0, 0, metric |

| ... |

| |

|----------------------------------------------------------|

Advertises (to all routers on the local networks) that he can reach that IP ad-dress in metric hops.

Lots of wasted space in the packet

No netmasks so doesn’t work for CIDR addresses

RIP2 Packet Format

Fills in the "must be zero’s" with some-thing useful

1 8 16 32

|-------------|--------------|-----------------------------|

| command | version (=2) | routing domain |

| | | |

|----------------------------|-----------------------------|

| address family (=2) | route tag |

| | |

|----------------------------------------------------------|

| IP address, 32 bits |

| |

|----------------------------------------------------------|

| subnet mask, 32 bits |

| |

|----------------------------------------------------------|

| next-hop IP address |

| |

|----------------------------------------------------------|

| metric (1-16) |

| |

|----------------------------------------------------------|

| |

| up to 24 more routes, with same format, ie: |

| family, tag, ip addr, subnet, nexthop, metric |

| ... |

| |

|----------------------------------------------------------|

Inter-operates with RIP version 1

Routing domain identifies the routing daemon process

Route tag can be AS number for BGP

Debugging RIP

Use a packet sniffer, or...

Turn on routed -t on a UNIX box

% in.routed -t

RESPONSE from 199.45.198.253.520:

dst 0.0.0.0 metric 1

dst 199.45.197.0 metric 1

RESPONSE from 199.45.198.10.520:

dst 0.0.0.0 metric 1

dst 199.45.197.0 metric 1

RESPONSE from 199.45.198.34.520:

dst 0.0.0.0 metric 1

dst 199.45.197.0 metric 1

RESPONSE from 199.45.198.254.520:

dst 0.0.0.0 metric 1

dst 199.45.197.0 metric 1

What a mess

Four different gateways advertising the same routes all with the same met-ric

But not all have the same capability (Sun 2 vs. Sparc Ultra)

This site needs gated instead of routed to artificially weight metrics

RIP on a Cisco Router

To configure RIP on a Cisco router:

router rip

network 192.108.21.0

Says you will speak RIP and advertise the network 192.108.21.0

You can use "show ip route" to view the routing table

IGRP/EIGRP

(Enhanced) Interior Gateway Routing Protocol

Developed by Cisco in mid-1980’s to re-place RIP

Distance-vector, interior gateway proto-col

Uses ASs to identify routing groups

Handy for all-cisco networks, no so handy for heterogeneous networks

Works well in a WAN environment, can be easily distributed into RIP

IGRP/EIGRP cont.

Routing updates every 90 seconds for IGRP, asynchronous for EIGRP

Complex metric includes factors for de-lay, load, bandwidth, and reliability; varies from 1-255

Network manager gets to tune param-eters in formula

Better metric than RIP’s, makes IGRP more stable

Uses split horizon and triggered updates

IGRP/EIGRP cont.

Uses path holddown

No updates accepted after a failure

Waits a while (several update periods) before accepting updates again

Route Poisoning

Treats every update that appears to be counting to infinity as unusable

Keeps all paths, not just the best

Makes recovery faster when route goes down

Weaknesses of IGRP

Hard to balance load across multiple paths

No netmasks in routing info

EIGRP - Enhanced IGRP

Has netmasks

Can do CIDR aggregation

New diffusion algorithm

Controls transient loops during update propagation

E/IGRP, cont.

IGRP is commonly used when sharing information with other Cisco routers on your WAN, such as your ISP

You must enable IGRP routing, speci-fy an autonomous system number and the networks which will use IGRP

router igrp 101

network 129.19.0.0

network 192.108.21.0

IGRP then shares routing information with other routers also in the same au-tonomous system

Advertised/accepted routes can be controlled with access lists

OSPF

Open Shortest Path First

Interior gateway, link-state protocol

Also designed as a replacement for RIP

Can balance load across multiple links

Unlike RIP, can operate within a hierar-chy

OSPF, cont.

Largest entity within a hierarchy is an AS, uses internal AS numbers, unique within the organization

Each AS is divided into "areas"

Link State information is exchanged by all routers within an area; summarized at borders of areas

OSPF "backbone" (area 0) is responsi-ble for exchanging information between areas

SPF Algorithm

The Shortest Path First (SPF) [some-times called Dijkstra] algorithm is the ba-sis for operation of OSPF

Once interfaces are initialized, a router sends OSPF HELLO to its neighbors

Neighbor routers exchange link state in-formation; once they’re synchronized, they are said to be "adjacent"

Link state information is re-transmitted periodically

Every 90 minutes

Whenever a router’s state changes

OSPF’s Algorithm, cont.

Each router calculates a shortest path tree

Uses itself as the root of the tree

Builds the routing table with this SPF information

Designated router

Network segments with more than one router elect a "designated router"

DR is responsible for maintaining link state information for that segment

New router joining the club gets one answer from the DR, not multiples

One big feature of OSPF is support of variable-length subnet masks (RIP2 and EIGRP do too)

Currently, gated is the best way to sup-port OSPF on a UNIX box

OSPF on a Cisco

On a cisco router, your OSPF clause might look like:

router ospf 235

network 199.45.100.0 0.0.0.255 area 4

network 199.45.101.0 0.0.0.255 area 0

Local AS number chosen is 235

You are willing to speak OSPF on net-works 199.45.100.0 and 199.45.101.0

Output of "show ip ospf"

show ip ospf

Routing Process "ospf 235" with ID 199.45.141.67

Supports only single TOS(TOS0) routes

Number of areas in this router is 1

Area 1.1.1.1

Number of interfaces in this area is 1

Area has no authentication

SPF algorithm executed 29 times

Area ranges are

Link State Update Interval is 0:30:00 and due in 0:23:15

Link State Age Interval is 0:20:00 and due in 0:03:15

OSPF Details

Shortest path computation centralized, not distributed like distance vector proto-col

1 3

A ---------------- B --------------- C

| | ___/

| 3 4| 5 ___/

| | ___/

D ---------------- E ---/

6

A says:

from A, to B, link 1, distance 1

from A, to D, link 3, distance 1

B says:

from B, to A, link 1, distance 1

from B, to C, link 2, distance 1

from B, to E, link 4, distance 1

OSPF Details

Suppose backhoe cuts link 1 between A and B

A says to D

from A, to B, link 1, distance infinite

B says to C and E

from B, to A, link 1, distance infinite

Floods to the rest of the network, ie D says:

from A, to B, link 1, distance infinite

E hears it twice, messages are time stamped and have a message number

OSPF Details, cont.

Everybody updates their database and recomputes routes

Updates take message number into ac-count so old messages don’t pollute the database

Packets from A to B get re-routed thru D and E

Security of the database

Flooding includes hop-by-hop ac-knowledgments

Can authentic/encrypt

Have a checksum in the packets

Timeouts remove entries that are not refreshed periodically

Strengths of Link State Protocol

Fast, loopless convergence

Precise metrics, can do multiple metrics

Supports multiple paths to destination, can do load balancing

Done by having the SPF algorithm compute second best path too

BGP

Border Gateway Protocol

Distance vector protocol, used on the backbones

Covered in detail in this afternoons sessions

Routing algorithms used to want to route packets the fastest way

Metrics were related to speed

Routing algorithms on the backbone re-lated to policy

Metrics related to cost, hot potato routing

Get rid of packet as soon as you can

Provide as little transit as possible