2.

2 INTERNET ROUTING PROTOCOLS

 The IP addresses have a length of 4 bytes and are composed by two parts: a
part that identifies the network where the system is connected to, and another
part that identifies the physical connection between the system and the network.

 An extremity system or a router, which has several physical connections to one

or more networks, uses a distinct address for each connection.

 The routers are not involved when transmitting a packet between two systems
belonging to the same physical network (the same LAN data link protocol). The
source system encapsulates the packet in a data link frame and transmits it to the
physical address (in fact, the MAC – Medium Access Control address)
corresponding to the destination system. The physical address corresponding to
an IP address of a system from the same physical network is obtained using the
Address Resolution Protocol (ARP).
2.2 INTERNET ROUTING PROTOCOLS
(contin.)
 The routing consists of an algorithm that is used to determine the path between
a source and a destination hosts. When the source system S is not placed in the
same local network as the destination system D, several routing strategies can
be used. Let us consider that an intermediate node (router), on the path between
S and D, receives a packet for D containg the source address of S. Then, the
following routing strategies may be used:

 if the packet contains all routing information (for the whole route), the router
does not take any decision; instead, it sends the packet to the next router
specified in the packet. This method is named source routing and assumes
that the system S has complete knowledge about the path to D.

 the intermediate router may have complete prior knowledge about the route
to D; therefore, in this case the router does not have to take any decision. This
assumes that each intermediate router has a routing table containing the
correct routes to all possible destinations.
2.2 INTERNET ROUTING PROTOCOLS
(contin.)
 the router does not have prior information about the path to D and therefore,
will take an instant decision, based on the currently available routing
information. This information includes the paths to all neighboring nodes,
their load, etc. Each node needs to communicate to other nodes for updating
this routing information. The TCP/IP routing protocols use this distributed
mechanism, using a local database (routing table) in each node. This method
assumes that in each local network, there is at least one node (named
gateway) which keeps a routing table. All systems in the local network have
to know just the gateway address, which will start the routing of the packet to
the final destination. Multiple gateways can be defined for a LAN in order to
increase the redundancy (a priority mechanism is needed to select the
gateway). This distributed network routing was inspired by the ARPANET
introduced by DoD of USA.
2.2.1 Routing tables and routing decisions
 The packet routing is performed by routers, which keep an updated routing
table. The routing table contains pairs denoted as (N, R), where N is the IP
address of the destination network and R is the IP address of the first router
(next hop) on the route to the destination network N. Hence, the routing table
contains information only about four types of destinations:

 systems connected directly to one of the physical networks the router is

attached to (as gateway);

 systems or networks defined explicitely in the table;

 systems or networks for which the router received ICMP redirect messages,
and

 a default address used to specify all the other (unknown) destinations.

2.2.1 Routing tables and routing decisions
(contin.)
 An example of four networks connected by three routers and the complete
routing table (at convergence) for the router R2:
2.2.1 Routing tables and routing decisions
(contin.)
 The general algorithm for IP routing decisions:
2.2.2 Routing protocols
 The routing tables initialization and permanent updating to the network
functioning are made using special protocols for exchanging routing
information between routers. Routers operate per autonomous system basis.
2.2.2.1 Autonomous systems
 An autonomous system (AS) is defined as a logical portion of a larger IP network. An AS
normally consists of an internetwork within an organization. It is administered by a single
management authority. An AS can connect to other autonomous systems managed by the
same organization. Alternatively, it can connect to other public or private networks.
2.2.2.1 Autonomous systems (contin.)
 Some routing protocols are used to determine routing paths within an AS. Others
are used to interconnect a set of autonomous systems. The following routing
protocols are used in TCP/IP networks:
 Interior Gateway Protocols (IGPs): Interior Gateway Protocols allow routers to
exchange information within an AS. Examples of these protocols are Open Short Path
First (OSPF) and Routing Information Protocol (RIP);
 Exterior Gateway Protocols (EGPs): Exterior Gateway Protocols allow the exchange of
summary information between autonomous systems. An example of this type of routing
protocol is Border Gateway Protocol (BGP).

 Within an AS, multiple interior routing processes can be used. When this occurs,
the AS must appear to other autonomous systems as having a single coherent interior
routing plan. The AS must present a consistent view of the internal destinations.
2.2.2.2 Types of IP routing and IP routing
algorithms
 There are two primary methods used to build the routing table:
o Static routing: Static routing uses preprogrammed definitions representing paths through
the network;
o Dynamic routing: Dynamic routing algorithms allow routers to automatically discover
and maintain awareness of the paths through the network. This automatic discovery can
use a number of currently available dynamic routing protocols. The difference between
these protocols is the way they discover and calculate new routes to destination networks.
They can be classified into four broad categories:
 Distance vector protocols;
 Link state protocols;
 Path vector protocols;
 Hybrid protocols;
2.2.2.2.1 Static routing
 Static routing is manually performed by the network administrator. The
administrator is responsible for discovering and propagating routes through the
network. These definitions are manually programmed in every routing device in the
environment. After a device has been configured, it simply forwards packets out the
predetermined ports. There is no communication between routers regarding the
current topology of the network. In small networks with minimal redundancy, this
process is relatively simple to administer. However, there are several disadvantages
to this approach for maintaining IP routing tables:
 Static routes require a considerable amount of coordination and maintenance in non-
trivial network environments;
 Static routes cannot dynamically adapt to the current operational state of the network. If
a destination network becomes unreachable, the static routes pointing to that network
remain in the routing table. Traffic continues to be forwarded toward that destination.
Unless the network administrator updates the static routes to reflect the new topology,
traffic is unable to use any alternate paths that may exist.
2.2.2.2.1 Static routing (contin.)
 Normally, static routes are used only in simple network topologies. However, there
are additional circumstances when static routing can be attractive. For example,
static routes can be used:
 To manually define a default route. This route is used to forward traffic when the
routing table does not contain a more specific route to the destination;
 To define a route that is not automatically advertised within a network;
 When utilization or line tariffs make it undesirable to send routing advertisement traffic
through lower-capacity WAN connections;
 When complex routing policies are required. For example, static routes can be used to
guarantee that traffic destined for a specific host traverses a designated network path;
 To provide a more secure network environment. The administrator is aware of all
subnetworks defined in the environment. The administrator specifically authorizes all
communication permitted between these subnetworks;
 To provide more efficient resource utilization. This method of routing table management
requires no network bandwidth to advertise routes between neighboring devices. It also
uses less processor memory and CPU cycles to calculate network paths.
2.2.2.2.2 Distance vector routing
 These algorithms allow each device in the network to automatically build and
maintain a local IP routing table.

 The principle behind distance vector routing is simple. Each router in the
internetwork maintains the distance or cost from itself to every known destination.
This value represents the overall desirability of the path. Paths associated with a
smaller cost value are more attractive to use than paths associated with a larger
value. The path represented by the smallest cost becomes the preferred path to
reach the destination. This information is maintained in a distance vector table. The
table is periodically advertised to each neighboring router. Each router processes
these advertisements to determine the best paths through the network.

 The main advantage of distance vector algorithms is that they are typically easy to
implement and debug. They are very useful in small networks with limited
redundancy.
2.2.2.2.2 Distance vector routing (contin.)
 However, there are several disadvantages with this type of protocol:

 During an adverse condition, the length of time for every device in the network to produce
an accurate routing table is called the convergence time. In large, complex internetworks
using distance vector algorithms, this time can be excessive. While the routing tables are
converging, networks are susceptible to inconsistent routing behavior. This can cause
routing loops or other types of unstable packet forwarding;

 To reduce convergence time, a limit is often placed on the maximum number of hops
contained in a single route. Valid paths exceeding this limit are not usable in distance
vector networks;

 Distance vector routing tables are periodically transmitted to neighboring devices. They
are sent even if no changes have been made to the contents of the table. This can cause
noticeable periods of increased utilization in reduced capacity environments.
2.2.2.2.2 Distance vector routing (contin.)
 Enhancements to the basic distance vector algorithm have been developed to
reduce the convergence and instability exposures.

 Routing Information Protocol (RIP) is a popular example of a distance vector

routing protocol.
2.2.2.2.3 Link state routing
 The growth in the size and complexity of networks in recent years has necessitated
the development of more robust routing algorithms. These algorithms address the
shortcoming observed in distance vector protocols. These algorithms use the
principle of a link state to determine network topology.

 A link state is the description of an interface on a router (for example, IP address,

subnet mask, type of network) and its relationship to neighboring routers. The
collection of these link states forms a link state database.
2.2.2.2.3 Link state routing (contin.)
 The process used by link state algorithms to determine network topology is
straightforward :
1. Each router identifies all other routing devices on the directly connected
networks;
2. Each router advertises a list of all directly connected network links and the
associated cost of each link. This is performed through the exchange of link
state advertisements (LSAs) with other routers in the network;
3. Using these LSA advertisements, each router creates a database detailing the
current network topology. The topology database in each router is identical;
4. Each router uses the information in the topology database to compute the
most desirable routes to each destination network. This information is used to
update the IP routing table.
2.2.2.2.3 Link state routing (contin.)
 The SPF algorithm is used to process the information in the topology database. It
provides a tree-representation of the network. The device running the SPF
algorithm is the root of the tree. The output of the algorithm is the list of shortest-
paths to each destination network.

 For the particular topology presented in the figure, the individual costs values are
noted in the figure and in the lower side, the final tree is plotted, where only the
minimum cost paths are kept (a path cost is computed by adding all individual
costs).

 Because each router is processing the same set of LSAs, each router creates an
identical link state database. However, because each device occupies a different
place in the network topology, the application of the SPF algorithm produces a
different tree for each router.
Link-state routing - Dijkstra’s algorithm
• Dijkstra’s algorithm computes the least-cost path from one node (the
source, which we will refer to as u) to all other nodes in the network.
Dijkstra’s algorithm is iterative and has the property that after the kth
iteration of the algorithm, the least-cost paths are known to k destination
nodes, and among the least-cost paths to all destination nodes, these k
paths will have the k smallest costs.
• Let us define the following notation:
– D(v): cost of the least-cost path from the source node to destination v as of this
iteration of the algorithm.
– p(v): previous node (neighbor of v) along the current least-cost path from the source to
v.
– N : subset of nodes; v is in N if the least-cost path from the source to v is definitively
known.

• The global routing algorithm consists of an initialization step followed by

a loop. The number of times the loop is executed is equal to the number
of nodes in the network. Upon termination, the algorithm will have
calculated the shortest paths from the source node u to every other node
in the network.
Dijkstra’s algorithm - continued
Dijkstra’s algorithm - Example
2.2.2.2.3.1 Example for Shortest-Path First
Algorithm
 The SPF tree for router A:
2.2.2.2.4 Path vector routing
 The path vector routing algorithm is somewhat similar to the distance vector algorithm in
the sense that each border router advertises the destinations it can reach to its neighboring
router. However, instead of advertising networks in terms of a destination and the distance to
that destination, networks are advertised as destination addresses and path descriptions to
reach those destinations.

 A route is defined as a pairing between a destination and the attributes of the path to that
destination, thus the name, path vector routing, where the routers receive a vector that
contains paths to a set of destinations. The path, expressed in terms of the domains (or
confederations) traversed so far, is carried in a special path attribute that records the
sequence of routing domains through which the reachability information has passed. The
path represented by the smallest number of domains becomes the preferred path to reach the
destination.

 The main advantage of a path vector protocol is its flexibility.

 Border Gateway Protocol (BGP) is a popular example of a path vector routing protocol