-------------------------------------------------
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
--------------------------------------------------
IGRP & EIGRP
(Part 3 of 6)
Although IGRP is a distance vector protocol, IGRP's metric
is computed using a formula that takes many factors into
account, according network's delay and bandwidth. In
addition, IGRP can be based on routes on the current load
level occupancy of each link, as well as the current
end-to-end error rate.
IGRP can split traffic across path that are equally (or
almost equally) good. When there are several paths to
destination, more of the traffic is sent along the paths
that have higer bandwidth.
A Service Provider's boundary IGRP router can gather
information from several external AS. Routes to external
networks that are reported to internal routers. Thus, IGRP
suports routing between AS.
EIGRP uses the same metrics and routing formulas as IGRP,
but it introduces some important improvements. EIGRP cuts
down greatly on routing traffic by sending updates only
after a change and sending only altered entries. EIGRP also
includes an algorithm that prevents loops from forming.
In the sections that follow, we'll first describe IGRP and
then discuss the EIGRP enhancements.
IGRP Routing
Like RIP, an IGRP router would broadcast its routing table
to its neighbours at periodic intervals. And like RIP, an
IGRP router starts up with routing table entries for its
directly connected subnetworks. Its table is enlarged by
updates sent by neighbouring routers. IGRP update messages
don't include subnet masks, In place of the simple hop
counts used in RIP IGRP routing updates carry several types
of metric information, namely:
Delay : The delay is the time (in units of 10 micro
seconds) that it takes a bit to reach a
destination when there is no load on the
network.
Bandwidth : The metric is 10 000 000 divided by the
smallest bandwidth on the path (measured in
kilobits per second). For example the
smallest bandwidth of 10 kilobits per second
yield a metric of 1000 000
load : the load is the proportion of the path's
bandwidth that currently is in use.
It is coded on a scale from 0 to 255.
255 means 100 percent loaded.
Reliability : This is the fraction of the datagrams that
are arriving undamaged. it is coded on scale
from 0 to 255; 255 means 100% arriving
undamaged.
Hop Count : the number of hops to the destination
Path MTU : The biggest Maximum Transmission Unit (MTU)
that can be carried across every link on the
path.
The delay, bandwidth and MTU are derived from router
configuration information. The load and reliability are
computed dynamically, from information exchanged by the
routers.
example:
-------------------------------------------------------------
ip Route |ip |ip |ip |ip |ip | ip | ip
Dest |Route |Route |Route |Route |Route |Route|Route
|metric|metric|metric|metric|metric| if |Ages
| 1 | 2 | 3 | 4 | 5 |Index|second
------------+------+------+------+------+------+-----+------
128.6.0.0 |12610 | 1536 |61000 | 2 | 255 | 3 | 11
Metric 1, Overall route metric
(calculated with parameters specified by admin)
Metric 2, Bandwidth Metric (10000000/1536) kbps
Metric 3, Sum of interface delays (10000000/61000)x10us
Metric 4, Route Hop count
Metric 5, Interface reliability (255 = 100%)
IGRP Delay and bandwith measurment.
========================================================
Medium | Default delay values | bandwidth metric
| (10 microsecond units)| 10 000 000/ bw in
| | kbps
============+=======================+===================
Satellite | 200 000 (2 sec) | 20
(500 mbps) | |
------------+-----------------------+-------------------
Ethernet | 100 (1 milisec) | 1000
(10 mbps) | |
------------+-----------------------+-------------------
1.544 mbps | 2000 (20 milisec) | 6480
------------+-----------------------+-------------------
64 kbps | 2000 | 156250
--------------------------------------------------------
Other Configured IGRP Values.
Configuring an IGRP Router is fairly straightforward. In
addition to the IP addresses, subnet masks, MTUs, bandwidths
and delays, you can specify:
- A variance factor V. If M is the smallesst path metric,
paths with metric less than MxV will be used.
- Wether hold downs are enabled or disableed.
Timers also are configurable, although the defaults
frequency are used. The default values are:
- Updates are broadcast ever 90 seconds.
- If no update is received from a next-hopp router within 270
seconds, its entries are timed out. If there is no
alternative route, the destination is marked unreachable.
- A hold down, during which no new path foor an unreachable
destination will be accepted, will last 280 seconds.
- If no update for a destination hass beenn received for 540
seconds (the flush time) it is removed from the routing
table.
IGRP Protocol Mechanisms
Like RIP, an IGRP router sends periodic updates to its
neighbours. The updates include the entire routing table,
with all metrics.
A hold down prevents defunct rout from being reinstalled by
a stale message. No new router to destination is accepted
during the hold down periode. IGRP also provides its own
route poisoning. If the metric for a route increases by more
than factor of 1.1, it's very likely that a loop is buiding,
and so the route is removed.
A triggered updates are sent a change -- such as a removal
of a route. A route is removed when:
- communcation to a neighbor times out. Rooutes via the
neighbour are removed.
- A next hop router sends a notification tthat a route is
unusable.
- the metric has increased sufficiently soo that route
poisoning is invoked.
Exterior Routing
One reason that IGRP is popular with Internet Sevice
Providers is that or handles routing information between
Autonomous System. IGRP updates can include multiple routes
to outside outside networks. A default route to the outside
world can be selected from several proposed external
routes.
Enhanced IGRP Features
Enhanced IGRP uses the same metrics and distance
calculations found in IGRP. However, it improves IGRP
significantly by supporting subnet masks and no periodic updates.
Only changes are sent, and EIGRP make sure that these
changes have been received by requiring them to be
acknowledged. Simple periodic hello messages are used to
discover neighbor and check if they re still active. Another
important enhancement is use of the Diffuse Update ALgorithm
(DUAL), which guarantees loop free routing.
IGRP DUAL
The basic idea behind DUAL is simple. It's based on the
observation:
"If a path consistently takes you closer to a destination,
then the path cannot be a loop."
Turning the statemnt around, if a path is a loop, it will
contain a router whose distance to the destination is bigger
than the previous router's distance.
DUAL is designed to find paths that have the property that
each router along the way is closer to the destination.
As shown below, router E will view with great suspicion
an update from its downstream neighbour Z a much bigger
metric than E's own current table.
+--------------------+
| B |
| metric to net N=9 |
+--------------------+
^ |
| |
| v
+--------------------+ +--------------------+
| A | | C |
| metric to net N=10 | | metric to Net N=7 |
+--------------------+ +--------------------+
^ |
| |
| v
+--------------------+ +--------------------+
| Z | | D |
| metric to net N=11 | | metric to Net N=6 |
+--------------------+ +--------------------+
^ |
: |
: v
+--------------------+
| E |
| metric to net N=5 |
+--------------------+
Illustration routing around a loop
DUAL Topology Table
To implement DUAL, EIGRP saves information that IGRP would
have trown away. EIGRP saves the route information that each
neighbour has sent in its updates. IGRP would have discarded
information about any routes that were not optimal. The
information is stored in a side table called Topology Table.
Topology table data includes:
+-------------+-------------+-------------+--------------+
| Destination | Neighbor | Neighbor's | My current |
| | | metric | best metric |
+-------------+-------------+-------------+--------------+
DUAL Feasible Successors
The intresting entries in the topology Table are the ones
that describr feasible successors. My feasible successor are
neighbors who are closer to the destination than I am
(currently).
As long as as there is at least one fasible successor, I
have a route to the destination, and I am in Passive state
for DUAL. However, when an update changes the picture so
that I have no feasible successor, I start to query my
neighbors to find out whether traffic has simply been
changed to a longer one or a loop is forming.
Let's walk to a process a little more formally:
1. Suppose that I have reached the point where I have only
one feasible route trough destination, via router Z.
2. An update arrives from Z that increases Z's metric.
Furthermore, a new distance from Z to the destination is
greater than my current distance.
This could indicate that a loop is forming.
3. I go into Active state and start a route recomputation.
4. But while the recomputation is in progress, I will
continue to route trough Z.
5. I send an update message which is called a "querry" to
all neighbors except Z. The messages announces my new
bigger metric discount for the destination.
6. If a neighbor has one or more feasible routes, it sends
a reply and announces its good routes to a destination.
7. A neighbor that does not have a feasible route, will
enter Active state (if it's not already in it) and sent
queries to its neghbors.
Optionally, it can report back imediatelly that it
already in active state, and it is recomputing.
8. Queries will "diffuse" trough the network until either a
feasible route is found or a router that knows that the
destination is unreachable is contacted.
9. When a router has found a feasible route or established
unreachability, it sends back replies to the queries
that it has received.
10. When all of its own queries have been answered, a router
returns to passive state.
EIGRP has proven that distance vector routing is far from
dead. The next sections, we will look at its competitor,
link state routing. (
geocities.com/gandautama)