Transcript RIP2

RFC 2453
RIP 2
(Routing Information Protocol)
Daher Kaiss
Motivation

Introduction

Review the Basic Protocol

RIP Characteristics

Protocol Extensions & Compatibility
2
Introduction
Basic Internet Model
H1
N1
R1
R2
N2
R3
N3
H2
3
Why RIP?

Although OSPF has a lot of advantages,
we still need RIP :
– Very little “overhead” in small networks
• Mainly in terms of bandwidth, Configuration and
management time.
– Very easy to implement
4
RIP 1 Limitations - I

RIP 1 doesn’t consider :
– Autonomous Systems and IGP/EGP
interactions.
– Subnetting
– Authentication
5
The Basic Protocol
6
So, What is RIP ?




A routing protocol
Based on Bellman-Ford Algorithm
Uses a distance vector algorithm
Historically :
– Used since the early ARPANET
– Based on the program “routed”, which is
included in the Berkeley Unix.
– An updated version was used by XNS
(Xerox Network Systems)
7
RIP Basic Protocol (Cont..)

RIP is working as an IGP (Interior
Gatway Protocol) in moderate size AS’s
8
Limitations of the protocol - II



Only Networks with longest path
(Network diameter) of 15 hops
Identifying Loops requires a lot of time
and bandwidth
“Best route” doesn’t consider real-time
parameters (e.g. delay, reliability, dollar
cost, or load)
9
Distance Vectors Algorithms

Find a path from the sender to the
destination

Forwarding inside Network or Subnet is
the responsibility of Network technology

Network technology is Transparent to IP
10
Distance Vectors Algorithms (Cont..)

Each Router has it’s own data-base
about all the destinations

Each entry includes :
– Next router
– “Metric” (e.g. time delay, dollar cost)

Destinations are networks but could be
individual host
11
The router’s data base

For each destination keep the following:
– address (subnet): In IP implementation
– router : First router along the path
– interface : The physical network to be
used to reach the first router
– metric : indicating the distance
– timer :amount of time since the entry was
last updated
– other flags ...
12
The router’s rule

Periodically, Send to others update
messages about your data base content

Take care to keep your data base
updated
13
So, what is “good” path ?

Goodness is determined according to
the value of the “metric” (1..15)

In simple networks : “metric” simply
counts the number of routers a
message must go through

In more complex : May consider delay,
cost and others
14
Calculating the minimal metric

Based on Bellman-Ford Algorithm

Formally :
– D(i,i) = 0
all i
– D(i,j) = mink [d(i,k) + D(k,j)]
otherwise
* D(i,j) represents the metric of the best rout from I to j

Algorithm will converge in finite time

Assuming no topology change occurred
15
Calculating the minimal metric (Cont..)

Data is adaptively updated - No need to
keep the whole estimates

Only routers participate in the game No need for individual hosts information

Worse metric that comes from the next
router, should be considered
16
Calculating the minimal metric (Cont..)
Example :
R2
N1
R1
N3
N2
N3
R2
5
R3
17
So Far So Good !! J

But …

The discussion assumes fixed topology

In practice routers and lines often fail
Algorithm needs modifications L
18
Dealing with changes in topology

Main problem : If a router crashes, it
has no way to notify it’s neighbors

Solution : time-out paradigm

Details depend upon the protocol itself

In RIP : Send update messages to your
neighbors every 30 seconds
19
Dealing with changes in topology (Cont..)

If R1 doesn’t hear from R2 for 180
seconds,R2 is marked invalid

R1 notifies its neighbors the R2 is
unreachable

Unreachable metric = 16
20
Preventing Instability

Main problem : Mathematics proves that
the algorithm converges in finite time,
but it doesn’t tell how long does it take it
to converge !!!


“Count to infinity” method
Choose “infinity” value to be 16.
21
Preventing Instability (Cont..)
Example
Cost=1
A
B
Cost=1
Cost=1
C
Cost=1
Cost=10
D
N
Cost=1
22
Preventing Instability (Cont..)
Example
Cost=1
A
B
Cost=1
Cost=1
C
D: dir 1, dir 1 ….. dir 1
B: unreach, C 4, C5 … C12
Cost=10
C: B 3, A 4, A 5, . ..A 11, D 11
D
N
A: B 3, C 4, C 5, …,C 11, C 12
Cost=1
23
Preventing Instability (Cont..)

If network becomes inaccessible, we
want to stop counting as soon as
possible

“infinity” was chosen to be as small as
possible
24
Preventing Instability (Cont..)

“Simple Split Horizon Scheme”
– Omit routes learned from one neighbor in
updates sent to that neighbor

“Split Horizon With Poisoned Reverse”
– Include such routs in update but set their
metric to infinity
25
Protocol Characteristics
26
Message Format
RIP1 Packet Format
Command (1)
Version (1)
Must be Zero (2)
RIP Entry (20)
RIP1 Entry Format
Address Family identifier (2)
Must be Zero (2)
IPv4 address (4)
Must be Zero (4)
Must be Zero (4)
Metric (4)
27
Handling messages

Input processing
– Request Messages
– Response Messages
28
Protocol Extensions
29
Entry Format
Address Family identifier (2)
Rout Tag (2)
IP address (4)
Subnet Mask(4)
Next Hop (4)
Metric (4)
30
Authentication

Authentication scheme uses the space
of an entire RIP entry
Command (2)
0xFFFF
Version (2)
Unused (2)
Authentication type (2)
Authentication (16)
31
Compatibility


Implemented by compatibility switch
Necessary for two reasons :
– Some implementations still follow RIP1
– Use of Multicasting (*) would prevent RIP1
from receiving RIP2 updates
(*) Multicasting is used to reduce the unnecessary load
on hosts not listening to RIP2 messages
32