<<

. 40
( 132 .)



>>

about the delivery of datagrams. If the underlying physical transmission channel does not
deliver a packet then IP will not compensate for this. Also IP does not guarantee the
order in which packets will be delivered: since datagrams between two hosts can take
different paths through the network, they can be delivered in variable order dependent on
the time of transmission through each path. These services, if required, are provided by
layers above the IP protocol.


5.3.1 Dynamic routing algorithms
Dynamic routers maintain and update the routing table dynamically. To keep an up-to-
date picture of the network, the routers periodically exchange information with each other.
Each of the routes will have cost 3 information associated with it. This is the metric by
which one route will be chosen over another. A metric is a standard measurement, such
as path length, to determine the optimal path to a destination. This metric can be very
simple such as ˜the best route is the one with the least number of routers to cross™. It
could, however, be more complex, taking into consideration a number of factors such as
bandwidth, latency and reliability. The two most common types of protocol using routing
algorithms to do this are:

• distance vector routing protocol
• link state routing protocol.


5.3.2 Distance vector routing protocol
Distance vector routers compile and send network route tables to other routers which
are attached to the same segment. Each router builds up its own table by broadcasting
its entire table and receiving broadcast tables from other neighbouring routers, to allow
it to maintain its own table. Broadcasts can occur as often as every 30 seconds, which
can cause congestion on the network. Cost information is relative to other routers. For
example, if router B tells router A that it can reach network 22 in 3 hops, then router A
will assume that it (i.e. router A) will be able to reach network 22 in 4 hops. An example
showing how the hop count is incremented is shown in Figure 5.12. The information
gathered by a router will be broadcast to neighbouring routers.
The process of updating all of the routing tables so that they all have the same infor-
mation is called convergence. The most common implementation of the distance vector
algorithm is RIP, which is described below.

5.3.2.1 Routing information protocol (RIP)
RIP has been a popular routing protocol for a number of years and it is used in IP
networks and also by Novell LANs. However, note that the implementations for the two
3
This is not a monetary cost, but an indication of the speed, bandwidth or latency, etc. of the link.
5.3 IP ROUTING 183



1 ho
p
WAN Router n




op
Router 4




1h
1 hop
Router 1 Router 3

op
1h




1h
op




Router 2



Figure 5.12 Example of distance vector routing

are different (Novell™s implementation also takes into consideration the time of a route
in ˜ticks™). The RIP protocol has a hop ¬eld limit of 15 hops, which means that there
can be a maximum of 15 hops (i.e. 15 routers) from source to destination. If a computer
cannot be reached within this limit then a message is usually sent back to the source,
saying ˜network unreachable™. RIP is de¬ned under the IETF™s RFCs 1508 and 1388. It
was introduced in 1988 and was the original routing protocol of the Internet.
The following factors are taken into account by a router when it is selecting the optimum
path for a packet through a network:

• The number of hops. A hop is a jump across a router, a metric count de¬nes the number
of hops for a given route.
• For Novell, the time in ˜ticks™ (approximately 1/18 second) each route takes.
• The cost of the path.

To understand how RIP works, refer to Figure 5.13 as an example. Suppose that routers
A, C and D have been exchanging routing information for some time. Router A™s routing
tables will appear as illustrated in Figure 5.14. The ˜next hop™ value of 0.0.0.0 indicates
the default network.
Router B is now switched on and broadcasts its availability. Router A will update its
routing table to include B as one hop away. Router A will then broadcast to routers C
and D that it can reach router B with one hop. Both routers C and D will update their
routing tables to include the new information that they can reach router B in two hops
(via router A). Eventually the routing tables will appear as in Figure 5.15.
Now consider that router C becomes faulty. Both routers A and D will notice that router
C has not broadcast its routing table. All routers should broadcast their routing tables to
their neighbours every 30 seconds. After waiting for a period of 6 times the broad-
cast interval (i.e. 6 — 30 = 180 seconds) the routers will delete router C™s information
from their routing tables. Router C and its associated network will now be regarded as
unreachable via routers A and D.
184 IP APPLICATIONS FOR GPRS/UMTS



1 hop
1

3 Router B
Router A
2




1
ho
1 hop




p
1
1

1 hop
2 2

Router D
Router C

Figure 5.13 Routing information protocol


Destination Next Hop Metric Interface
Router C 0.0.0.0 1 2
Router D 0.0.0.0 1 3

Figure 5.14 RIP router A routing table

Router A Router B
Destination Next Hop Metric Interface Destination Next Hop Metric Interface
Router C 0.0.0.0 1 2 Router A 0.0.0.0 1 1
Router D 0.0.0.0 1 3 Router D Router A 2 1
0.0.0.0 Router C Router A 2 1
Router B 1 1

Router C Router D
Destination Next Hop Metric Interface Destination Next Hop Metric Interface
Router A 0.0.0.0 1 1 Router A 0.0.0.0 1 1
0.0.0.0 1 2 Router C 0.0.0.0 1 2
Router D
Router B Router A 2 1 Router B Router A 2 1

Figure 5.15 RIP routing tables

In a second example, suppose that the link between C and D is faulty. Both C and D will
advertise the link loss and each router will update its tables with the latest information.
In this case C would advertise that it can reach D via A in two hops and vice versa.

Count to in¬nity
There is a problem with RIP known as count to in¬nity. This can be explained through the
¬rst example above, where router C is faulty. Routers A and D have updated their routing
tables; router A now tells router B that router C is unreachable. Router B will look at its
own routing table and see that it can reach router C in two hops. Router B broadcasts this
information to router A. Router A now believes that there is an alternative path to router
5.3 IP ROUTING 185


C via router B. Router A broadcasts this information to both routers B and D. They both
update their routing tables, adding 1 to the hop count for router C, believing that they can
reach router C through A. This continues with each router believing that it can reach router
C via another router. Eventually the maximum hop count of 15 is reached, where router
C is considered unreachable. However, this is only after a considerable period of time.
To overcome this problem of slow convergence, a solution called split horizon was
proposed. Split horizon prevents routers from sending routing information back along
paths where they ¬rst received that information. For example, in Figure 5.13, router B
learns of router C™s existence via router A. Using the split horizon technique, router B
will not be allowed to broadcast information on its path connected to router A about
router C. An example of this is illustrated in Figure 5.16. Router 2 has informed router 3
that it can reach router 1 in one hop. Router 3 informs the other routers that it can reach
router 1 in two hops but does not inform router 2 of this.
Another method to overcome the slow convergence problem is called poison reverse. In
this method routers send routing information back along paths where they ¬rst received
that information, but will always send a metric count (number of hops) of 16, which
means that the destination is unreachable. This essentially performs the same function,
but is simpler to implement.
An example of this is shown in Figure 5.17. Router 3 learns of router 1™s existence via
router 2. Using the poison reverse technique, router 3 will broadcast on its path to router
2 that it will take 16 hops to reach router 1, i.e. router 1 is unreachable via router 3.



Router 2 Router 4




Router 1 Router 3




Router 5

Figure 5.16 Example of split horizon



Router 2 Router 4



I can reach Router 1
in 16 hops
Router 1 Router 3




Router 5

Figure 5.17 Example of poison reverse
186 IP APPLICATIONS FOR GPRS/UMTS


There are several problems associated with RIP. One is that by allowing the routers to
talk to each other very frequently (i.e. to update tables) a lot of traf¬c is generated on the
network and this overhead can reduce performance. Another problem is slow convergence,
which is caused by routers not being kept up to date by distant routers because of delays
within these distant routers while they recalculate their own routing tables. For example,
using RIP in an IP environment where the update interval is 30 seconds, it will take around
7 minutes to con¬gure a large network (30 seconds — 15 hops). In a Novell environment
where the default update is 60 seconds it will take even longer. The 30-second interval,
or 60 in the case of Novell, can be reduced (or increased) by the network administrator
but more RIP traf¬c will be sent, causing more congestion on the network. Link state
protocols such as OSPF and NetWare Link State Protocol (NLSP) can overcome the
limitations of distance vector routing and are becoming more widely implemented.


5.3.2.2 Triggered updates
An extension to RIP is the triggered update. The triggered update only sends information
about the routing of a network when something substantial happens rather than broad-
casting every 30 seconds or so. This can be used to reduce convergence time on a LAN.
However, it is particularly suitable for public data networks, where the corporation may
have to pay for packets sent over the wide area network (WAN). Note also that as WAN
links are usually much slower than the LANs they are connecting, sending periodic RIP
updates can decrease the bandwidth available for data traf¬c. To ensure the link is still
up, RIP packets across the WAN are repeated until acknowledged, whereas on the LAN
interfaces, RIP is not acknowledged.


5.3.2.3 Routing information protocol version 2 (RIP2)
RIP version 2 (RIP2) is de¬ned in RFC 2453. It has been introduced to address some of the
shortcomings of RIP. RIP version 1 does not consider interior gateway protocol/exterior
gateway protocol (IGP/EGP) interaction and variable length subnetting. This is because
RIP predates the implementation of these protocols. This means that RIP cannot process
addresses other than based on the classful address, i.e. class A, B or C. This reduces its
effectiveness on modern networks containing subnets. RIP2 understands variable length
subnet masks and will work with CIDR networks. RIP is also limited to 15 hops and does

<<

. 40
( 132 .)



>>