IP Routing

PRINCIPLES DISTANCE VECTOR RIPv2 EIGRP APPLICATIONS

Routing
Guide packets through the network from sender to recipient Which path to choose?
o o o o o o o The fastest path? The shortest path? The cheapest path? The most reliable path? The least congested path? Any path that doesnt go into China? This particular path?

Thats the problem!

Static vs Dynamic
Static routing Paths are hard-coded Unresponsive to changes Extremely reliable Simple Dynamic routing Paths are computed Responsive to changes Maintenance-free Complex

A key feature of a network with redundancy is the ability to A key feature of a network with redundancy is the ability to re-route packets around an outage. This requires rapid re-route packets around an outage. This requires rapid responses to changes in network topology. responses to changes in network topology.

Internal vs External
Internal routing Routing within an AS Based on technical merit Uses an IGP External routing Routing between AS-es (Partly) based on policy Uses an EGP

AS 1

AS 2

AS 1

AS 3

RIB and FIB

RIB/FIB/Cache
Routing Information Base Populated by routing protocols etc Used to compute FIB Routing protocol specific Forwarding Information Base Used to deliver packets One destination per prefix Protocol-independent

Route cache Recently resolved routes Fast hash lookup of destinations Not necessary if FIB is fast enough

RIB/FIB Model (Simplified)

Dynamic Routing Protocols Import Policies Static Connected

Route Information Base (RIB)

Export Policies Dynamic Routing Protocols

Route Selection

Forwarding Information Base (FIB)

RIB/FIB Model (Complexified)

OSPF RIPv2 Import Policies OSPF RIB RIPv2 RIB ISIS RIB Static RIB Connected RIB ISIS

Export Policies OSPF RIPv2 ISIS

Route Selection

Forwarding Information Base (FIB)

Example RIB/FIB interaction

1. 2. 3. 4. 5.

130.236.189.0/24 heard from 130.236.178.12 with RIPv2 Check import policies OK Install route in RIPv2 RIB Apply route selection OK Install route in FIB Check export policies Announce 130.236.189.0/24 via RIPv2

1.

2.

3.

6. 7.

4.

Packet arrives for 130.236.189.22 Look up destination in route cache not found Match destination prefixes against FIB found next hop 130.236.178.12 Send packet to 130.236.178.12 Add 130.236.189.22/32 via 130.236.189.17 to route cache

5.

Simplified FIB Structure

Destination prefix 130.236.178.0/24 130.236.189.16/28 130.236.189.32/28 130.236.189.1/32 127.0.0.0/8 0.0.0.0/0 Gateway 130.236.189.17 0.0.0.0 0.0.0.0 130.236.189.17 0.0.0.0 130.236.189.17 Interface hme0 hme0 le1 hme0 lo hme0

Longest prefix match: Find the longest prefix in the FIB that matches the destination of the packet being forwarded and use that forwarding rule

Longest Prefix Match

Prefixes in FIB
A. B. C. D. E. F. G.

Addresses
1. 2. 3. 4. 5. 6. 7. 8. 9.

130.236.189.0/24 130.236.189.16/28 130.236.189.3/32 130.236.0.0/16 130.236.224.0/12 130.236.176.0/20 0.0.0.0/0

130.236.189.1 130.236.189.12 130.236.189.19 130.236.189.3 130.236.178.12 130.236.188.23 130.236.240.6 130.220.12.8 64.23.12.1

Match addresses to nex-hop gateways in FIB using the longest prefix match principle. Example: 1-A

Routing Table Tricks

Default Route A catch-all route Only one rule in FIB Answer: 0.0.0.0/0 This is the only prefix that matches all addresses. Default route is just an application of longest prefix match!

by ed by lly us ually us ed a e us a onn c ion o ees arre us u e conneecttion tto routt s u Deeffaulltt ro only havee on e c teway.. D a u t only hav on ga teway ttha t cific hostts ha ough a speecific gaharrd-hos s r ugh a sp y ad n th ro u is usuall h tthee neett,, th t routtee is usuall y ed h aul t ro ibut ed Thee deeffaulit can bee disttrribut Th d b dis u ,, butt it can g prrottocol. codeed b routting p o ocol. cod d a rou in tthrrough a h o ugh

Unicast Reverse Path Filtering

Procedure
Check that FIB lookup of source address matches the incoming interface Drop packets that come in on the wrong interface
Example packets
From 10.0.2.4 on le0 From 10.0.2.6 on le0 From 64.2.6.8 on le1 From 14.120.5.1 on le0

Used for
Prevent address spoofing Block flows at the network edge What about asymmetric routing? Example FIB 10.0.2.0/24 10.0.2.6/32 0.0.0.0/0 le0 le1 le1

URPF Example
Routing table 10.1.2.0/24 gw 10.0.1.1 dev le0 10.0.1.0/31 dev le0 10.0.2.0/31 dev le2 0.0.0.0/24 dev le1 10.1.2.3/32 gw 10.0.2.1 dev le2 Packets from 10.1.2.3 on le0 no longer pass RPF test and are dropped

INTERNET

le1 le2

le0

le1

le0

le0

Routing table 10.1.2.0/24 dev le0 10.0.1.0/31 dev le1 0.0.0.0/24 gw 10.0.1.0 dev le1 10.1.2.3/32 gw 10.0.1.0 dev le1

10.1.2.3

Routing table 10.1.2.0/24 gw 10.0.2.0 dev le0 10.0.2.0/31 dev le0 0.0.0.0/24 gw 10.0.2.0 dev le0 10.1.2.3/32 dev null0 Inject route 10.1.2.3/32 dev null0

This computer gets infected with Slammer and starts merrily pinging away.

Anycast (IPv4)
Definition
Send traffic to the closest of a group of equivalent destinations Point to (any) point

yc An up ro tg as

Uses
Divert high-volume traffic early Redundancy (high availability) Load balancing

Real-life examples
192.175.48.0/24 192.5.4.0/23

Member 1

Anycast Example
Anycast group: 10.1.2.0/24 Each member is a separate physical network A, B and C announce reachability to 10.1.2.0/24
o o X reaches member 1 through A Y reaches member 2 through B

yc An

up ro tg as

Member 3

B
Link A to member 1 is lost A now reaches 10.1.2.0/24 through B or C and chooses C
o o X reaches member 3 through A X never notices the outage

Member 2

Real Anycast Example (2005)

traceroute 192.5.5.241
From IDA (Linkping, Sweden)
1 2 3 4 5 6 7 8 9 idagw-fastether20.ida.liu.se b-ida.ida.liu.se g-b.net.liu.se ybliu2-g-2.net.liu.se linkoping2-SRP2.sunet.se stockholm1-POS2.sunet.se kthnoc5-SRP4.sunet.se Stockholm-GE-SOL-IX.p80.net blackhole-1.iana.org

From Pacific Supernet (Hong Kong)

1 2 3 4 5 6 7 8 9 rsm-vl1.pacific.net.hk ciscol6.pacific.net.hk a8-0-0-6a.yckbr01.net.reach.com i-6-0.tmhstcbr01.net.reach.com i-3-1.sjc-core01.net.reach.com i-13-0.paix-core01.net.reach.com i-3-1.paix04.net.reach.com paix-gw3.isc.org blackhole-1.iana.org

From Casa Byers (Linkping, Sweden)

1 2 3 4 5 6 7 8 9 10 11 12 212.214.112.1 foo126-145.visit.se foo126-130.visit.se rif6-cr1-png-lnk.se.sn.net rif2.cr1.png.nrk.se.sn.net rif5.cr2.png.nrk.se.sn.net rif17-rs2-t4-sto.se.sn.net rif1-cr3-t4-sto.se.sn.net ge0-0.tg4-p1.sto.se.sn.net pos2-0.tg4-peer1.sto.se.sn.net ge-2-1-4470.byb-gw.sth.netnod.se blackhole-1.iana.org

From Olivant (Faroe Islands)

1 2 3 4 5 6 7 8 9 feth1-0-0.bone2.olivant.fo 212.55.32.98 ser1-0-1-2-3-3-1.kdnxd4.ip.tele.dk fe1-0-0.100M.kdnxt1.ip.tele.dk pos0-3.155M.kd4nxg2.ip.tele.dk so-0-1-0.2488M.kd4nxu1.ip.tele.dk so-1-0-0.2488M.arcnxu1.ip.tele.dk pos8-0.2488M.arcnxg1.ip.tele.dk blackhole-1.iana.org

Dynamic Routing

Major Algorithm Families

Link State Algorithms (LSA) Broadcast information on entire topology Examples: OSPF, IS-IS Path-Vector Algorithms (PVA) DVA variant Exchange information on complete path to destination Examples: BGP Link Vector Algorithms (LVA) Research topic

Path-Finding Algorithms (PFA) DVA variant Exchange information about predecessor and cost Examples: RIPv2, EIGRP

Distance Vector Examples

RIP/RIPv2 Open standard Based on Distributed BellmanFord (DBF) Not loop-free Rapid convergence (v2) Full CIDR support (v2) Multiprotocol support EIGRP Cisco-proprietary protocol Based on DUAL Loop-free by design Rapid convergence Full CIDR support Multiprotocol support

10

Nave Distance-Vector
Example
1.

2.

3.

Keep a table with an entry for each destination. The entry contains the destination, the first router on the path to the destination and the cost (metric) associated with the path Periodically send the table to all neighbords When an update arrives, add the cost of the incoming link, then adopt those routing entries that have a lower metric than the corresponding entries in the current routing table

Dest A B

Router X Y

Metric 10 10

Incoming table Dest Router A Q B Z New table Dest Router A X B Z

Metric 12 8

Metric 10 9

Nave Operation
B
B A C 1 gw Y 1 gw Z

C
C: 1 B: 2 C: 1 A: 2 B: 2 C A: 2
A B

B: 1 A: 2 A: 1

B: 1 A: 2

A: 1
A B C 1 gw X 1 gw Z

1 gw Y 1 gw X

11

Nave Problems
B A B;3 B;3 C;4 C;5 C;6 C;7 C;8 C;9 C;10 C;11 C;12
route via B, metric 3 route via B, metric 3 route via D, metric 2 route via D, metric 2 route via B, metric 3 route via B, metric 3 directly connected directly connected

C
10

D
1

B D;2 UNR C;4 C;5 C;6 C;7 C;8 C;9 C;10 C;11 C;12

C B;3 A;3 A;4 A;5 A;6 A;7 A;8 A;9 A;10 A;11 D;11

Target Network

A A B B C C D D

Although B withdraws the route to the target network, traces of the route exist in A and C

Preventing Loops
Split horizon Do not claim reachability to a network in updates to the router through which the network is reached Prevents some loops Poison reverse Include above routes, but with a metric of infinity Breaks loops faster

Network A

X
A, metric 3 A, metric 3 B, metric 16

A: Q;3 B: Y;3

B, metric 16 A metric 2 Y
B: W;2 A: X;4
W

B, metric 2

Network B

12

Network A

Preventing Loops
Hold-Downs After losing a route, dont listen to just any updates for it Allows routes others have through this router to time out Slows convergence Can prevent some loops A:A, metric 4 X;4 B:B, metric 4 X;4
Q

A: Q;3 B: Y;3 X A, metric 3 A, metric B, metric 3 3

B, metric 2 Y
W

B: W;2 A: X;4

Network B

Speeding Convergence
Route poisoning
Send negative updates to explicitly withdraw routes Speeds convergence

Network A

A: Q;3 B: Y;3 X A, metric 3 B, metric 16 A, metric 3 B, metric 3

Triggered updates
Send an update as soon as something changes Speeds convergence

A: X;4 A, metric 4 B: X;4 B, metric 4 Y

B, metric 16 B, metric 2 B: W;2 A: X;4

W

Network B

13

RIP
Command: request or response Version: RIP version number AFI: Address family Address: IP address for the entry Metric: Distance to destination (legal values are 1-15; 16 for unreachable) RIP header

Command
RIP 1 Entry

Version

AFI Address

Metric

RIPv2
RIP header
Command Version

RIP 2 Authentication (optional)

0xFFFF Authentication type Authentication data (16 octets)

RIP 2 Entry
AFI Address Subnet mask Next hop Metric Route tag

Authentication type: type of authentication used Authentication data: Authentication-type specific data AFI: Address family Route tag: For distinguishing sources of route information Address: Address for the entry Subnet mask: Netmask for the entry Next hop: Where packets to the destination should be forwarded Metric: Distance to destination (legal values are 1-15; 16 for unreachable)

14

RIP Operations
Metric
Number of hops to destination Infinity equals 16
RIP Hacks
Split horizon mandated Poison reverse recommended Triggered updates
o o o o o Mandated for deleted routes Permitted for new routes Rate-limited Not in standard Not in standard

Timers
Every 30 seconds send an update to all neighbors (multicast in RIPv2) Routes time out after 180 seconds without updates Withdrawn routes are deleted after another 120 seconds

Hold-downs Route poisoning

EIGRP
The Good Provably loop-free Distributed computation Rapid convergence Easily configured Support for link weights Multipath support Multiprotocol support The Bad Patented algorithm (Cisco)
o US Patent #5,088,032

Only available from Cisco The Ugly

15

EIGRP Terminology
Successor Successor graph Upstream/downstream Distance Reported Distance (RD) Feasible Distance (FD) Topology Table B
X is downstream of Y with respect to B

20

X
10 5

Successor of A with respect to B

EIGRP Principle
Loop-freeness
Never select a neighbor that might cause a loop
3 5 5

Observation
If the reported distance from a neighbor to the destination is smaller than the feasible distance from me to the destination, then selecting that neighbor cannot result in a loop

10 5

16

EIGRP Example (1)

Reported distances: RDAD = 10 RDCD = 5 RDBD = 20 FDD = 15 A, C

B
50 50

S
50 20 5

Feasible distance: Feasible successors: Cost CSA changes to 20

o o

RDAD < FDD and DSAD < DSCD A is retained as successor

5 5

Cost CSA changes to 50

o o RDCD < FDD and DSCD < DSAD S chooses C as successor

1. Cost CSA changes to 20 2. Cost CSA changes to 50

EIGRP Example (1)

Reported distances: RDAD = 55 RDCD = 5 RDBD = 20 FDAD = 15 A, C

B
50 50

S
50

Feasible distance: Feasible successors:

S changes successor from A to C

o o o Sends update RD = 55 to B B can change successor RDCD < FDBD so C is chosen

5 5

Convergence!

17

EIGRP Example (2)

A has no feasible successor
o o o o o Sets FD and RD to +INF Sends update and query to S Sends RD=20 to A and B FD is set to 25

B
15 15

S
5

S has C as feasible successor A now sets S as successor B changes successor

C is feasible (S is not)

Convergence!

C to A is lost
5

More EIGRP
Transport Mechanisms
Reliable Transport Protocol Unreliable multicast

Metric
256*((K1*Bw)+ (K2*Bw)/(256-Load) + (K3Delay)*K5/Reliability+K4))) Default K2=K4=K5=0, K1=K3=1 Gives: 256 * (Bw + Delay)

Neighbor discovery
Periodic multicast hello packets Unreliable multicast transport

Protocol-Dependent Modules Updates

Only when required Reliable unicast transport Encoding/decoding of packets Interfacing DUAL to the routing table Metric conversions Route aggregation

18

Grab Bag of Topics

Redistribution and filtering

What routes should A take from OSPF and distribute to B via EGP? What routes should B accept via EGP from A and distribute with RIP? What routes should B accept via EGP from C and distribute with RIP or EGP to A? Should B distribute routes from D via EGP to A? Should they also be distributed with RIP internally?

OSPF A D B

EGP

RIP

19

Redistribution and filtering

Source of routes
o o o o o o o o o Connected interfaces Static routes RIPv2 EIGRP OSPF BGP IPX RIP AppleTalk RIP

Input filtering
o o o What routes do we accept? What routes do we export? What routes do we take from one routing protocol and export with another How are those routes changed?

Output filtering Redistribution

Layer 3 Switching
Pushing routing functions further into hardware Less expensive equipment Less flexible equipment
o o Fewer protocols Fewer interface options

Faster

But really, layer 3 switching is just marketspeak for routing

20

Layer 4-7 Switching

Routing is usually at layer 3
o Decisions based on IP address only

What if decisions are based on layer 4 information, or even higher-level information?

Internet

Src Src 147.12.1.3 147.12.1.3 62.8.1.45 62.8.1.45

Sport Sport 45502 45502 34110 34110

Dst Dst 81.0.0.1 81.0.0.1 81.0.0.1 81.0.0.1

Dport Dport 80 80 80 80

Proto Proto TCP TCP TCP TCP

Next-hop Next-hop A A B B
147.12.1.3 62.8.1.45

The End
Topics covered Routing principles Distance-vector algorithms
o o o o o o Problems and solutions RIP and RIPv2 EIGRP Reverse path filtering IPv4 Anycast Default route

Topics not covered Routing and policy Practical configuration Future topics Label Switching Multicast routing BGP (Path-Vector) OSPF (Link-State)

Tricks of the trade

21