-------------------------------------------------
IP ROUTING
originally from Dr. Sidnie Feit
--------------------------------------------------
Contents
--------------------------------------------------
Part 1. IP Routing Protocols
Part 2. RIP & RIP ver 2
Part 3. IGRP & EIGRP
Part 4. OSPF
Part 5. OSI & BGP
--------------------------------------------------
ROUTING INFORMATION PROTOCOL
(Part 2 of 6)
The Interior Gateway Protocol in widest use today is RIP,
which is derived from Xerox Network Systems (XNS) routing
protocol. RIP's popularity os based on it's simplicity and
availability.
RIP was included in the Berkeley Software Distribution
TCP/IP implementation and still is distributed with UNIX
systems as program "routed".
In fact, RIP ROuting progam is a standard part of most
vendors' host and router TCP/IP packages. RIP routing is
included in free software from Cornell University caled
"gated". RIP was in widespread use for several years before
being standardized in RFC 1058. A second version was
proposed in 1993 and improved in 1994 (the original version
has been declared history which means obsolete).
RIP computes route using a simple distance vector routing
algorithm. Every hop in the network is assigned a cost
(usually 1). The total metric o for a path is the sum of the
hop costs. RIP chooses the next hop so that datagrams will
follow a least-cost path.
Figure below shos how distance estimates propagate across
the network. The router at upper left can tell the that the
datagrams is forwarded via Router A will reach network N in
fewer hops than datagrams forwarded via Router B.
Router C
+----------+
|which |
|route | +----------+ ====
|is better?|<-----|Router A | ||
+----------+ |I'm 2 hops|<---\ ||
^ | from N | +---------+ ||
| +----------+ |I'm | ||
| |connected|----||
| +-------+ |to N | ||
+----------+ |I'm | +---------+ ||
|Router B |<----|2 hops |<---/ ||
|I'm 3 hops| |from N | ||
+----------+ +-------+ ====
network N
RIP's strong points are its simplicity and availability.
Often there are no reason to use more functional and
complicated methods for a small network or a network with a
simple technology. However, for large, complex networks RIP
has some serious shortcomings. For Example :
- The max. metric of any kind of any path iis 15, 16 means
"I can't get there". Because it is easy to run out of hops
on a big network, RIP usually is configured with cost of
1 for each hop, weather that hop is a slow dialup or a
high speed fiber link.
- After disruption in the network, RIP ofteen is slow to
reestablish optimal routes. In fact, after a disruption,
datagram traffic may run around the circles for a while.
- RIP cannot respond to changes in delay orr load accross
links. It cannot split traffic to balance the load.
Initializing the RIP:
To get started, each router only needs to know the network
to which is connected. A RIP router broadcasts this
information to each of LAN neghbour routers. It also sends
this information at the other end of point-to-point or
virtual unit.
As shown above, the news spreads like gossip. Each router
passes the information to its own neighbours. For example,
Router C very quickly learns that it's two hops away from
network N.
Like all automated routing protocol, RIP has to send routing
updates, receive routing updates, and recompute routes. A
RIP router sends information to its neighbour routers every
30 seconds. Sending out routing information is called
"advertising" routes.
A host on a LAN could eavesdrop on RIP broadcast
advertisements and use them to update its ouwn routing table
-- or atleast assure itself that its routess are alive.
As shown in figure below, Router A has been sending traffic
to network 136.10.0.0 trough Router B. Router A receives an
update from neighbour D that announces a shorter route and
therefore changes its routing table. Note that the hop from
router A to D is added to D's metric to compute the distance
(2) from A to 136.10.0.0.
+--------------+ +---------------------------+
| Update from | | Router A Routing table |
| router D: | +---------------------------+
| I can get to |-->| Dest Next hop metric| Table
| 136.10.0.0 | |---------------------------+ before
| in 1 hop | | 136.10.0.0 B 5 | route
+--------------+ +---------------------------+ |
|
+---------------------------+ |
| Router A Routing table | V
+---------------------------+ Table
| Dest Next hop metric | after
+---------------------------+ update
| 136.10.0.0 B 3 |
+---------------------------+
RIP version 1 Mechanisms
Now let's walk trough the formal steps for RIP version 1
routing. We start our routing table off with distance that
we know about. Then, wheneever an update arrives from a
neighbour, we recheck our table and see if any entries can
be added or improved:
1. A cost is assigned to traversing each attached
subnetwork.
2. A router sends its current routing table to its neighbour
every 30 seconds.
3. When a router receives a neighbour's table, it checks
each incomming entry. A cost assigned to subnetwork on
which the update arrived is added to each metric.
4. If a destination is new, it added to the local routing
table.
5. If a destination already in the table, but the update
provides a shorter route, the entry is replaced.
It would be nice if routes alway got better and better, but
sometimes a link will go down. And our traffic will have to
take a longer path. We found out about bad news two ways:
1. Router A has been sending traffic to destination via
router X, and X sends an update that announces that the
number if hops of that destination has inreased (or
perhaps a desthination cannot be reached).
2. Router A has been senging traffic to a destination via
Router X but has not received any updates for 3 minutes.
Router A has to assume that Router X has crashed and mark
all routes trough X as unreachable (by giving them value
of 16).
RIP Version 1 Update Messages
As we mentioned earlier, update messages are sent between
RIP routers at regular intervals. In addition, request
messages may be sent to a neighbour to ask for routing
information. Typically, a system would sent out a request:
- During system initialization.
- When performing a network monitoring function.
|<--8 bit-->|<---8 bit--->|<-----16 bit---->|
+-----------+-------------+-----------------+
| command | version = 1 | zero |
+-----------+-------------+-----------------+
| Address Family Id = 2 | zero |
+-------------------------+-----------------+
| IP Address |
+-------------------------------------------+
| zero |
+-------------------------------------------+
| zero |
+-------------------------------------------+
| Metric |
+-------------------------------------------+
Format of a RIP version 1 message.
RIP version 1 Message details:
When the original RIP RFC was written, it was anticipated
that these routing messages would be used for other network
protocols beside IP, and so an address family identifier
field and space for up to 14 octets per address were
included.
The address family, IP address, and metric fields can be
repeated and a messages can contain up to 25 address
entries. The maximum message size is 512 bytes. If more than
25 entries need to be sent, multiple messages are used.
An update contains all destinations and metrics in the
sender's routing table. A request contains an entry for
which a metric is desired. A single entry with address 0 and
a metric of 16 asks for a compete routing table update.
Regular RIP updates are sent via the UDP from source port
520 to port 520 at destination router. However, request can
be from any port and response would be sent back to the
requesting port.
Fine-tuning RIP
The preceeding sections have described the basic RIP
protocol. However RIP implementations need some additional
features in order to solve problems:
- With a 30 second interval between updatess, it could take a
long time for changes to percolate trough a big network.
- After a change -- especially if some connnectifity has been
lost -- there is a tendency for traffic to run around in
circles.
Triggerred Upadates and Hold Down
Triggered updates speed up the process of discovering
changes. Whenever a router changes its metric for a route,
it sends updates announcing the change.
Note that one new update which trigger one router may
trigger others. However, this spurt of messages will prevent
a lot of user traffic from wandering along bad routes.
Since there will be a tendency for a lot of updates to be
sent at the same time, each system waits a random amounts of
time before sending. Also, the bandwidth used by triggered
updates can be reduced by sending only tose entries that
actually have changed, rather the entire routing table.
While adjustment are going on, a router which has
discovered may receive an obsolete update that indicate that
that a defunct route is available. If this update is
accepted, not only would affect on router, but the entire
network would replace good routing information with bad.
For this reason, some vendors implement a hold down rule
that sets a period of time during which updates are ignored
for destination that has been marked ureachable.
Split horizon and Poisoned Reverse
Why does RIP traffic sometimes round around in circles? The
reason is that after the change, it can take a while for all
the routers to get updated to accurate information. Fig
below shows a very simple example. Router D has two paths to
Network N. One is a direct 1 hop link, and the other is a
long 10-hop path. When the short link is disrupted, Router D
replaces the route with the alternate path which has a
metric of 10.
+----------+ +----------+ +----------+
| Router A | | Router B | | Router C |
+----------+ +----------+ +----------+
| | |
|| | | | ||
||============================================||
|| | ||
|
+----------+
|Router D |
+----------+
: \
: \ _____
: _\__ ^
: |____| :
: ____ : 10 hops
Broken link |____| :
: ____ : routers
: |____| :
: | __V__
_:____________|_
( )
( NETWORK N )
( )
(________________)
But the routing entries for Network N in the RIP messages
sent by Routers A,B and C would have the form:
Network N Metric=2
Thesse messages would not have any way to say that the route
is trough router D. What would happened if Router D got a
scheduled update from A before it has had a chance to tell
router A about its own change?
- D would update it's routing table to:
Destination Next Hop Metric
Network A 3
- D would start sending it's traffic to A ((who would send it
back)
- D also would send updates to A B and C annnouncing that it
can get to Network N in three hops.
- A would reply that it now can get to C inn four hops.
Routers B and D would be equally confused and, depending
on the timing of updates, might send traffic for N to A or
to D .
- RIP updates would bounce back and fourth..
The good news is that the metrics at A, B and C would be
increased by each update messages until they finally reach
eleven. And the correct route would be discovered. A couple
of simple mechanism can prevent the period of confusion from
occuring.
Split horizon means that the router should not report a
route to next-hop system for that route. For example in
figure above, this says that router A, B, C must not tell
Router D that they have a route to network N, because that
route actually passes trough D.
Poisoned reverse goes further, it prevents misunterstanding
by sending updates that says "Don't try to get there trough
me!" Specifically, update would include this entry:
Network N Metric 16
This cures the problem for the configuration shown above,
but for the networks containing big loops, traffic may still
run around in circles for a while, even if the destination
can't be reached at all. Fortunately, the metrics will
eventually increase to 16 and correct routing would be
restored. The process is called "counting to infinity".
Incidentally, don't count in finding triggered updates, hold
down, and poissoned reverse in every RIP router that you
encounter. There are dozen of version of RIP written for
every sort of box.
Deficiencies in version 1 of RIP: (that's why it's outdated)
1. No Subnet Mask
2. LAN Broadcast / not multicast.
3. Lack of Authentication
4. Can't distinguised fast from slow links.
5. Excessive traffic
RIP version 2.
Although RFC 1058 which defined version 1, was published in
1983, version 2 of RIP didn't appear until 1993. In that
time, a lot of work had been acomplished in designing
complex new protocols that solve all the problems.
But many orginzations like simplicity, ease of installation
and ease use of RIP.
Version 1 is declared 'historic' and useres should upgrade
to version two.
Version 2 offers simple solution for a few of RIP's
problems. However, to preserve internetworking with RIP
version 1 routers, the changes are modest. The maximum hop
counts remain at 15, and complete routing tablws are
exchanged every 30 seconds. But tables are multicast, raher
than broadcast.
Most version 2 changes are based on packing more information
into the update messages. Version 2 routing updates have the
format shown below.
|<--8 bit-->|<---8 bit--->|<-----16 bit---->|
+-----------+-------------+-----------------+
| command | version = 2 | zero |
+-----------+-------------+-----------------+
| Address Family Id = 2 | Route Tag |
+-------------------------+-----------------+
| IP Address |
+-------------------------------------------+
| subnet mask |
+-------------------------------------------+
| Next Hop |
+-------------------------------------------+
| Metric |
+-------------------------------------------+
Format of a RIP version 2 message.
Subnet Mask : Put into the message.
External Routers: The new Route Tag field includes
information learned by an external
protocol such A BGP. A popular use for
the tag is to state the Autonomous System
Number of an external Network
Next Hop : Used to report routes trough other
routers. Figure below a single router A
that supports RIP and IGRP and passes next
hop information between the two sets of
routers.
RIP Routers IGRP Proprietary Routers
\ / \ / \ / \ / \ /
___ ___ ___ ___ ___
| | | | | | | | | |
| X | | Y | | A | | B | | C |
|___| |___| |___| |___| |___|
| | | | |
| | | | |
||=================================||
<-----+---->
Translate A's B's Translate X's and Y's
and C's Routes to RIP to IGRP and multicast
and multicast to the to IGRP Routers.
RIP Routers
RIP version 2 Authentication
|<--8 bit-->|<---8 bit--->|<-----16 bit---->|
+-----------+-------------+-----------------+
| command | version = 2 | zero |
+-----------+-------------+-----------------+
|Addr Family Id = X'FFFF |authenticate type|
+-------------------------+-----------------+
| authentication info |
+-------------------|-----------------------+
| | |
+-------------------|-----------------------+
| V |
+
Version 2 message starting with an authenticator (
geocities.com/gandautama)