Design Goals of routing protocols

The purpose of all routing protocols is to pick the best next hop device
on the way to a destination device. The thing that differs between routing
protocols is how they pick the BEST next hop.

Some of the design goals for routing protocols includes, Optimization,
simplicity and low overhead, robustness and stability, rapid convergence.

Routing metrics generally take into account, bandwidth, delay, load,
reliability, hop count, and cost.


Routing Protocols

Two major types of routing protocols exist, internal protocols that route
information within an organization and external protocols that route
information between networks.

IGP is the Interior Gateway Protocol used to exchange routing information
within an autonomous system. RIP and IGRP are examples of IGPs.

EGP is the Exterior Gateway Protocol used to exchange routing information
between autonomous systems. Border Gateway Protocol version 4 (BGP4) is an
example of an EGP.

An Autonomous System is a collection of networks under a common
administrative control, consisting of routers that present a consistent
view of routing to the external world. Autonomous system numbers are
allocated to the regional registries by the IANA.

IGPs route packets within an autonomous system. Examples of IGPs are RIP,
IGRP, EIGRP, and OSPF.

EGPs route packets between autonomous systems and BGP4 is the only
currently supported EGP.

Routing protocols are divided into three main categories. Distance Vector,
Link-State, and Hybrid.

Distance Vector Routing Protocols  determine the direction (vector) and
distance (hope count) to any network in the internetwork. Distance
vector-based routing algorithms (also known as Bellman-Ford) periodically
(such as every 30 seconds) send all or portions of their routing table to
their adjacent neighbors. While doing this, the algorithm also accumulates
distance vectors. Routers running IGP distance vector protocols send
periodic updates even if no changes in the network occur. By receiving a
neighbors routing table, a router can verify all the known routes and make
changes to the local routing table based upon updated information received
from the neighboring router.  RIP and IGRP are Distance Vector Protocols.

Link State Routing Protocols use a different algorithm to respond quickly
to network changes. They send triggered updates only when a network change
has occurred and send periodic updates (known as link-state refreshes) at
long time intervals, such as every 30 minutes.  Link state protocols build
routing tables based on a topology database.  This database is built from
link-state packets that are passed between all the routers to describe the
state of a network. The database is used by the shortest path first
algorithm to build the routing table. When a link changes state, the
device that detects the change creates a link-state advertisement (LSA)
concerning that link (Route) and that LSA is propogated to all OSPF
routers. Each OSPF router takes a copy of the LSA, updates its link-state
(topological) database, and forwards the LSA to all neighboring OSPF
routers. This flooding of the LSA is required to ensure that all OSPF
routers update their databases before creating an updated routing table
that reflects the new topology.

The link-state database calculates the best paths through the network by
applying the Dijkstra shortest path first (SPF) algorithm against the
link-state database to build the shortest-path first tree. The best
(shortest) paths are then selected from the shortest-path-first tree and
placed in the routing table. Whereas the distance vector algorithm has
nonspecific information about distant networks and no knowledge of distant
routers, a link-state routing algorithm maintains full knowledge of
distant routers and how they interconnect. 

Examples of link-state routing protocols are OSPF which stands for Open
Shortest Path First and IS-IS which is an OSI standard link-state routing
protocol for multiple layer 3 procotols like IP and DECnet Phase IV.

As networks become larger in scale, link-state routing protocols become
more attractive because of the following:

Link-state protocols send flash updates of a topology change within the
network
Periodic updates are more infrequence that those for distance vector
protocols
Networks running link-state routing protocols can be segmented into area
hierarchies, limiting the scope of route changes.
Networks running link-state routing protocols support classless addressing
Networks running link-state routing protocols support summarization.

Hybrid routing protocols combine aspects of both distance vector and
link-state protocols. They are also called balanced hybrids.

The balanced hybrid routing protocol uses distance vectors with more
accurate metrics to determine the best paths to destination networks.
However, it differs from most distance vector protocols by using topology
changes to trigger routing database updates as opposed to periodic
updates. 

The balanced hybrid routing type converges more rapidly, like the
link-state protocols. However it differs from these protocols by
emphasizing economy in the use of required resources such as bandwidth,
memory, and processor overhead.

An example of a hybrid algorithm is EIGRP. This protocol, developed by
Cisco is an advanced version of IGRP. It provides superior convergence
properties and operating efficiency and combines the advantages of
link-state protocols with those of distance vector protocols. You learn
more about this protocol later in the EIGRP section of this chapter.

RIPv1 and RIPv2

RIP stands for Routing Information Protocol and uses distance vector
algorithms to determine the direction and distance to any link in the
internetwork. 

If multiple paths to a destination exist, RIP selects the path with the
smallest number of hops. However, because hop count is the only routing
metric used by RIP, it does not necessarily select the fastest path to a
destination. 

RIP allows routers to update their routing tables at programmable
intervals; the default interval is every 30 seconds. Because RIP is
constantly sending routing updates to its neighboring routers, this
process can cause network traffic to build. 

To prevent a packet from a condition known as looping, RIP has a hop-count
limitation of 15 hops. If the destination network is more then 15 routers
away, it is considered unreachable and the packet is dropped. This
limitation creates a scalability issue when routing in large heterogeneous
networks.

RipV1 is a classful routing protocol, which means that all devices in the
same network must use the same subnet mask, because RIPv1 does not include
the subnet mask information with the routing update. RIPv2 provides what
is called prefix routing and does send subnet mask information with the
route updates. This supports the use of classless routing. With classless
routing protocols, different subnets within the same network can have
different subnet masks. The use of different subnet masks within the same
network is referred to as variable-length subnet masking (VLSM).

IGRP is a distance vector routing protocol developed by Cisco. While RIP
selects the path with the fewest hops, IGRP can select the fastest path,
based on delay, bandwidth, load, MTU, and reliability. Network
administrator can determine the importance given to any one of these
metrics or allow IGRP to automatically calculate the optimal path. By
default, IGRP uses bandwidth and delay metrics only. Like RIP, it supports
only classful routing. IGRP also has a much higher maximum hop count limit
than RIP to allow the network to scale.

IGRP sends routing updates at 90-second intervals or when a topology
change occurs. Advertising the network for a particular autonomous system.
The key design characteristics of IGRP are Versatility that enables it to
automatically handle indefinite complex topologies, Flexibility for
segments that have different bandwidth and delay characteristics, and
Scalability for functioning in very large networks.

EIGRP is an advanced version of IGRP and is a proprietary Cisco protocol.
It is supposed to offer superior operating efficiency such as faster
convergence and lower overhead bandwidth.

EIGRP combines the advantages of link-state protocols with those of
distance vector protocols, becoming a hybrid protocol.

EIGRP uses the same default and configurable metrics as IGRP, while using
five basic components to enhance its ability to route date. They are:
Neighbor discovery and recovery (this feature allows routers to learn
about neighboring routers dynamically), Reliable transport protocol (which
guarantees the ordered delivery of EIGRP packets to all neighbors), DUAL
finite-state machine (which stands for Diffusing update Algorithm and
tracks all routes advertised by all neighbors so that it can select a
loop-free path), Protocol-Specific modules (that are responsible for
network layer, protocol-specific requirements needed to make routing
decisions, EIGRP support multiple routed protocols), and VLSM support
(which adds subnet masks to the routing tables and update. EIGRP is
therefore capable of classless routing and the use of different subnet
masks within the network).

OSPF is a link state protocol that was written to address the needs of
large scalable internetworks beyond the capabilities of RIP. OSPF is an
IGP which means it distributes routing information to routers within the
same Autonomous system. The large network issues that it addresses include
the following, Speed of Convergence(in large network, RIP convergence can
take several minutes while OSPF floods the network with routing changes
and computes them in parallel), Support for VLSMs (OSPF supports classless
routing and sending subnet mask information along with routing updates
unlike RIP v1), Network Reachability (OSPF has virtually no reachability
limitations), Use of Bandwidth (Rip broadcasts full routing tables to all
neighbors every thirty seconds which can slow a WAN connection while OSPF
multicasts link-state updates and sends the updates only when a change in
the network occurs [it also sends updates every 30 minutes to ensure that
all routes are synchronized]), Method for path selection (rip has no
concept of network delays and link costs and bases routing decisions
solely on hop count. OSPF uses a cost value which is based on the
configured bandwidth of the interface).

BGP (BGPv4) is an EGP. It is the principle route advertising protocol used
by major companies and ISPs on the Internet. BGP exchanges routing
information between autonomous systems while guaranteeing loop-free path
selection. Version 4 of BGP is the first version of BGP that supports
classless interdomain routing (CIDR) and route aggregation. Unlike common
IGPs such as RI, OSPF, and EIGRP, BGP does not use metrics such as hop
count, bandwidth or delay. Instead BGP makes routing decisions based on
network policies using various BGP path attributes.

BGP updates are carried using TCP on port 179. In contrast RIP updates use
UDP port 520 while OSPF uses neither TCP nor UDP (it has its own network
layer protocol number of 89). Because BGP requires TCP, IP connectivity
must exist between BGP peers and TCP connections must be negotiated
between them before updates can be exchanged. Therefore, BGP inherits the
reliable, connection-oriented properties of TCP.

To guarantee loop-free path selection, BGP constructs a graph of
autonomous systems based on the information exchanged between BGP
neighbors. As far as BGP is concerned the whole internetwork is a graph or
tree of autonomous systems. The connection between any two autonomous
systems form a path, and the collection of path information is expressed
as a sequence of autonomous system numbers (called the autonomous system
path). This sequence forms a route to reach a specific destination.

BGP is used extensively in the Internet today to connect ISPs and to
connect enterprises to ISPs.  Routing protocols all provide the same basic
services to allow packets to be routed through an internetwork. 

Routing protocols have different characteristics and network
administrators must choose a protocol that is best suited for their own
environment.

from http://qcpages.qc.cuny.edu/~sbunin/datacomm/routing_protocols.html