-------------------------------------------------
IP ROUTING
source 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
--------------------------------------------------
IP Routing Protocols
(Part 1 of 6)
Routing is the most important funtion that IP does. In
large networks,IP routers exchange information that keeps
their routing tables up to date. How is this done?
"There is no single required protocol for updating IP
routing table information."
Instead, network administrators always have been free to
select any routing information protocol that meets their own
internal requirements. Over the last years, numerous
protocol have been designed --and improved-- by
standards groups and by vendors. By long tradition, these
protocols are called Interior Gateway Protocols, or IGPs.
Separating the way that routing tables get updated from the
rest of IP was a very good idea. Routing has become more and
more sophisticated and efficient, while the basic IP
protocol remain unchanged.
Today, there are several IGPs in common use. Currently, the
venerable Routing Information Protocol (RIP) is still
popular. RIP chooses routes based on simple hop counts
estimates.
Sites that have selecetd Cisco routers often opt for cisco's
proprietary Intenet Gateway Routing Protocol (IGRP) or
Enhanced Intenet Gateway Routing Protocol (E-IGRP). IGRP
uses sophisticated costs measurements that take many
factors --including current load and reliability-- into
consideration.
The more complex Open Shortest Path First (OSPF) is
implemented for some large networks. And there are
organization that use OSI's Intermediate system to
Intermediate System (IS-IS) protocol which can route both
OSI and IP traffic. Both OSPF and IS-IS build detailed maps
for at least part of a network and generate paths before
choosing a route.
Allowing free choice of protocols within an end-user
organization has worked quite well. However, a standard is
needed when routing accross the chains of Service Provider
networks that connect end user sites together.
In this chapter, we will take a look at how each of this
protocols work and will examine their distinguishing
features.
1. AUTONOMOUS SYSTEMS
How can many different choches of routing protocols be
allowed? The internet model partitioned the world into units
called Autonomous Systems (AS). Simply stated, an autonomous
systems was somebody's networks.
Formally, an Autonomous System was:
A connected segment of network topology that consits of a
collection of subnetworks (with hosts attached)
interconnected by a set of routers.
Most importantly, the subnetworks that make up an Autonomous
Systems were under a common administration.
A typical Autonomous System was a network owned by a company
or an internet service provider (ISP). Actually, nobody was
intrested in your autonomous system (AS), unless you wish to
communicattie with other AS. In this case, you need to
register to INTERNIC to get your own unique AS number.
Figure below shows companies, service providers, Autonomous
System, and their use of Interior Gateway Protocol(IGP) and
Border Gateway Protocol (BGP).
_________ __________ _________
( ABC inc ) ( HIJ, Inc ) ( XYZ Inc )
( 24531 ) ( 34202 ) ( 2056 )
( R I P ) ( IGRP ) ( EIGRP )
(_________) (__________) (_________)
| | |
____|_____ _____|____ ____|_____
/ Service \ / Service \ / Service \
| Provider | BGP | Provider |BGP | Provider |
| 501 |-----| 1011 |----| 27 |
| EIGRP | | EIGRP | | OSPF |
\__________/ \__________/ \__________/
\ /
BGP\ ___________ /BGP
/ Service \/
| provider |
| 1011 |
| EIGRP |
\___________/
An organization's network administrator make their own
decission about the types of router that they will use
inside their network and the routing protocol or protocols
that they will employ.
How were separated Autonomous systems tied together? The
internet has been finding ways to do this for many years. As
you may guess, the unique Autonomous numbers that we
mentioned earlier played a role. The Exterior Gateway
Protocols that make all it work are discussed later.
The definition of autonomous system and use of Autonomous
System numbers changed in 1996. Recall that many
Internet Service Providers have been delegated address
blocks, and their assign subblock for their costumers sites.
For routing purposes, a single AS numbeer is sufficient to
identify the intire cluster of networks made up of the
providers network and all of its costumer networks. As
stated in RFC 1920, the new definition is:
"An AS is a connected group of one single or more IP
prefixes or more network operators which has the SINGLE and
CLEARLY DEFINED routing policy."
Most networks that connected to the internet today have very
simple policy.
Most networks that connect to the Internet today have a very
simple routing policy, namely they have a single service
provider and they are willing to change data with any other
network connected t internet. Such a network does not need a
separate AS Number.
However, a bussiness might have multiple service providers -
or it might use the internets an inexpensive way to access
it's client and supplier and limit communications to these
sites. This bussiness would need it's own AS number. This
number would be used as an index of design and enforcing the
routing policy.
2. IP ROUTING
An IP Datagram folloes a path made up of sequence of hops. A
node is one hop away-- or adjacent-- if there is a direct
aLocal Area Network (LAN) or Wide area network (WAN)
connection to the node. Routers that are separated by one
hop are called neighbours.
A source route that mantains a preselected list of hops can
be ut into an IP header. Howeverm the use if source routes
is rare. A datagram is routed by choosing it's next hop
destination at each router along its path.
Next-hop routing is flexible and robust. A change in network
topology usually can be configuerd by updating one, or just
a few, routers. Routers can inform one another of both
temporary and permanent changes in the network and
dynamically can switch traffic onto alternative routes as
needed.
3. ROUTING METRICS
How do we decide one route is better than another? There has
to be some kind of metric (distance measurement) that can be
used to compare routes.
3.1 Distance Vector Protocols
Very simple routing protocols just use end-to-end hop counts
to compare routes. Some improvements is gained by using
weighted hop counts; for example, a hop accross high speed
LAN given weighted 1. While a hop accross a slow medium
(19.2 kbps) could be given weight 10. This assures that a
path accross fast link will be preffered to a path accross
slow links. RIP chosses based on hops counts
More sophisticated protocols combine elements such as
bandwidth, delay, reliability, current load, or dollar cost
into the callculation of a routing metrics. IGRP and EIGRP
use fine-tuned metrics.
Algorithms that base routing decission entirely on metric
values are called distance vector algorithms.
3.2 Link State Protocol
Recently, a lot of attention has been focussed on link state
routing algorithms. A link state router builds a map of the
network and discover a path from the router to any
destination.
A cost of metric is assigned to each link in the map. A
total cost is computed for each part starting at the router
by combining the link costs. Then the best path or paths for
carrying traffic is selected.
The routers sends updates to one another whenever the
topology changes. After a change, all paths are
recalculated. OSPF and IS-IS are link state protocols.
Link state algorithm are sometimes called Shortest Path
First (SPF). This refers to the same name of computer
science algorithm that is used to calculate the shortest
path from one node to all other nodes in a network.
4 ROUTING TABLES
Recall that a host or router consults its trouting table in
order to forward datagrams toward a remote destination. This
table matches each destination with the address of routers
to be used as the next hop.
" Destinations listed in a routing table can include
supernets, networks, subnets and individual system. "
A default destination entry also can be included. It is
represented as destination 0.0.0.0.
There is no standard format for routing tables, but a simple
table entry would contain item such as:
-> Address of destination network, subnetmm or system.
-> IP address of the next-hop router to bee used.
-> Network interface to be used to reach tthe next-hop
router.
-> Mask for this destination.
-> Distance to this destination
-> Number of seconds since the route was llast updated.
In order to keep routing table small, most or all of the
entries identify destination, supernets, networks and
subnets. The idea is that if you can get to a router on a
host's network and then the routers of host subnets, you
will be able to get to that hosts.
5. A RIP ROUTING TABLE
The routing entries in table below, come from a RIP router
owned by a university. The table lists destinations and
tells you the next hop router to which you should forward
datagrams heading for that destination. The table also
contain the metric (distance) informationthat helped the
router to choose the next hop.
The routing table includes entries for many different
subnets of network 128.36.0.0 along with routes to the three
networks 130.132.0.0, 192.31.2.0 and 192.31.235.0 (these
entries were retreived using HP Open View for Windows
Workgroup Node Manager). The table is split into two parts
because of the large number of columns.
------------------------------------------------------------
ip Route | ip Route | ip Route | ip Route |ip Route
Dest | mask | next hop | type | protocol
------------+-------------+-----------+-----------+---------
0.0.0.0 |0.0.0.0 |128.36.0.2 | indirect | rip
128.36.0.0 |255.255.255.0|128.36.0.62| direct | local
128.36.2.0 |255.255.255.0|128.36.0.7 | indirect | rip
128.36.11.0 |255.255.255.0|128.36.0.12| indirect | rip
128.36.12.0 |255.255.255.0|128.36.0.13| indirect | rip
128.36.13.0 |255.255.255.0|128.36.0.21| indirect | rip
130.132.0.0 |255.255.0.0 |128.36.0.41| indirect | rip
192.21.2.0 |255.255.255.0|128.36.0.10| indirect | rip
129.31.235.0|255.255.255.0|128.36.0.41| indirect | rip
(Continued)
-------------------------------------------------------------
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
------------+------+------+------+------+------+-----+------
0.0.0.0 | 2 | -1 | -1 | -1 | -1 | 1 |153836
128.36.0.0 | 0 | -1 | -1 | -1 | -1 | 1 | 0
128.36.2.0 | 1 | -1 | -1 | -1 | -1 | 1 | 10
128.36.11.0 | 1 | -1 | -1 | -1 | -1 | 1 | 13
128.36.12.0 | 14 | -1 | -1 | -1 | -1 | 1 | 15
128.36.13.0 | 1 | -1 | -1 | -1 | -1 | 1 | 16
130.132.0.0 | 2 | -1 | -1 | -1 | -1 | 1 | 25
192.21.2.0 | 3 | -1 | -1 | -1 | -1 | 1 | 10
129.31.235.0| 1 | -1 | -1 | -1 | -1 | 1 | 25
5.1 Using the Route Mask
To find a match for a destination address such as
128.36.2.25, you would compare 128.36.2.25 with each entry's
Route Destination. The entry route mask tells you how many
bits of 128.36.2.25 must match corresponding bits in the
oute corresponding bits in the Route Destination. For
example, the third entry in the table has route mask of
255.255.255.0 which means the 3 bytes 128.36.2, need to
match and they do.
Suppose if we got two match for two different entries. The
one with the longer mask is preffered.
5.2 Default Route
The first entry in table, is the default route. It announces
that if no match is found, traffic should be forwarded to
the neighbour router which address 128.36.0.2.
5.3 Using Subnet 0
By the way, the administrators of this network are doing
something that is frowned upon by the standards writes. They
have assigned subnet number 0 to the LAN that this router
lives on. Recall that you not supposed to use 0 as a subnet
number. However, some fascilities may use every number that
they can get their hands on. Router vendors understand this,
and the router standard
5.4 Direct and Indirect Destination.
Note that the second table entry says that LAN 128.36.0 is
of type direct, which means that this subnet is directly
connected to to this router. The protocol is local, which
indicates that this route was learned by looking at the
configuration of the router.
The remainder of these entries list remote subnets and
networks that are reached indirectly by forwarding traffic
to other routers. This routes were learned via RIP.
5.5 Routing Metrics
Looking at the second part of of the table, we see that it
has space for several metrics. RIP only use one metric, a
simple hop count reporting to the distance of a destination.
The unused column are set to -1. Note that a 0 metric is
assigned to subnet 128.36.0 which is directly connected to
the router. Many of the other destinations are one hop awat.
However subnet subnet 128.36.12.0 are 14 hops away.
5.6 Route Age
The Route Age column tracks the number of seconds since each
route was updated or validated. Entries have been earned via
RIP will age out and be invalidated if they are not
reconfirmed within 3 minutes.
6. IGRP/BGP ROUTING TABLES
The routing entries in Table 8.2 come from an Internet
router owned by an Internet Service Provider (ISP).
The table lists destinations an identifies the next hop
router to be used for datagrams heading for each
destinations. The tables also contains the information that
helps router to recalculate the next hop if the network
topology changes.
------------------------------------------------------------
ip Route | ip Route | ip Route |ip Route|ip Route
Dest | mask | next hop | type |protocol
------------+-------------+-------------+---------+---------
0.0.0.0 |0.0.0.0 |130.94.40.25 |indirect|ciscoIGRP
128.121.50.0|255.255.255.0|128.121.50.50|direct |local
128.121.52.0|255.255.255.0|128.121.50.55|direct |local
128.121.54.0|255.255.255.0|128.121.50.50|direct |local
128.6.0.0 |255.255.0.0 |130.94.0.49 |indirect|ciscoIGRP
128.96.0.0 |255.255.0.0 |130.94.0.250 |indirect|ciscoIGRP
130.33.0.0 |255.255.0.0 |130.94.0.2 |indirect|ciscoIGRP
130.44.0.0 |255.255.0.0 |130.94.0.49 |indirect|ciscoIGRP
130.68.0.0 |255.255.0.0 |130.94.0.49 |indirect|ciscoIGRP
44.0.0.0 |255.0.0.0 |130.94.15.201|indirect|bgp
128.3.0.0 |255.255.0.0 |130.94.40.201|indirect|bgp
129.210.0.0 |255.255.0.0 |130.94.40.201|indirect|bgp
13.0.0.0 |255.0.0.0 |130.94.15.201|indirect|bgp
(continued from the above)
-------------------------------------------------------------
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
------------+------+------+------+------+-------+-----+------
0.0.0.0 |10647 | 1170 |21000 | 0 | 255 | 6 | 12
128.121.50.0| 0 | -1 | -1 | -1 | -1 | 1 | 0
128.121.52.0| 0 | -1 | -1 | -1 | -1 | 1 | 35
128.121.54.0| 0 | -1 | -1 | -1 | -1 | 1 | 0
128.6.0.0 |12610 | 1536 |61000 | 2 | 255 | 3 | 11
128.96.0.0 |14647 | 1170 |61000 | 2 | 255 | 6 | 11
130.33.0.0 | 8710 | 1536 |22000 | 1 | 255 | 2 | 18
130.44.0.0 |16610 | 1536 |22000 | 1 | 255 | 3 | 37
130.68.0.0 |12710 | 1536 |62000 | 3 | 255 | 3 | 39
44.0.0.0 | 0 | -1 | -1 | -1 | -1 | 6 |51766
128.3.0.0 | 0 | -1 | -1 | -1 | -1 | 6 |42049
129.210.0.0 | 0 | -1 | -1 | -1 | -1 | 6 |586765
13.0.0.0 | 0 | -1 | -1 | -1 | -1 | 6 |224463
All the parameters are exactly the same as 5.1 to 5.6. The
route age in IGRP and RIP tracks the number of second since
the route was last updated. For BGP, the route Age is used
to track the stability of long distance routes.
6.1 Border Gateway Protocol entries.
The table ends with list of remote destination that were
learned via the Border Gateway Protocol which provide
information used to route between the Autonomous System
on the internet.
7. Protocols that mantain routing tables
How did these routers learn their table entries? How are
entries kept up to date? How is the best choiches for the
next hop router discovered? This chores are the job of
routing protocol. The simplest routing protocols does:
- Study diagrams of your network to find tthe best path.
- Enter data to your routing table manuallly.
- Updates your routing tables manually.
This is exactly what should be done for a simple branch
office router, for example, like the one in figure below:
192.101.64.0
_____ ====
| | ||
| |-----|| ______
|_____| || ( )
|| _____ _____ ( )
||___| |__| |__( )
_____ || |_____| |_____| ( )
| | || routers (______)
| |-----|| cloud
|_____| || (other network)
====
The small brach office routers 192.101.64.0 needs only
two entries, one for the local network, and a default entry
for the cloud.
Manual routing can be used troughout a very smal network.
But for a complex network, that is growing and changing, and
has a multiple potential routes to a destination, manual
routing will turn into a nightmare.
At some point, it becomes impossible for humans to analyze
and respond to a network conditions. A routing protocol is
then needed to automate:
1. Exchange of information between routers about the current
state of network conditions.
2. Recomputation of the next best-hop selection as changes
occur.
Over the years, there has been substantial research into
routing protocols. Many have been implemented and their
merits have been hotly debated.
What are the caracteristic of the winning protocol?
- When the network changes, it should resppond quickly.
- It should compute optimal routes.
- It should scale up well as your network grows
- It should be frugal in its use of computter resources.
- It should be frugal in its use of transmmission resources.
But computing optimal routes in a large network may require
considerable CPU and memory, and quick reponse may require
immediate transission of a mass of information. A good
protocol design has to balance at these requirements. We'll
start up off our study of routing protocols by looking at a
very simple one-RIP.
(to be continued)
Sorry Mr. Rifky, I kinda tired, I'll continue to type this
article to be published in few days, OK...?
Ganz. (
geocities.com/gandautama)