In contrast, the philosophy in link-state routing
is to distribute the topology of the network and
the cost of each link to all the routers. Each
router independently computes optimal paths to
every destination. If each router sees the same
cost for each link and uses the same algorithm to
compute the best path, the routes are guaranteed
to be loop free. Thus, the key elements in link-
state routing are a way to distribute knowledge
of network topology to every router in the net-
work, and a way to compute shortest paths given
the topology.
Topology Dissemination
Each router participating in the link-state algo-
rithm creates a set of link-state advertisements
(LSAs) that describe its links. An LSA contains
the router’s ID, the neighbour’s ID, and the cost
of the link to the neighbour. The next step is to
distribute a copy of every LSA to every router
using controlled flooding. The idea is that when
a router receives a new LSA, it stores a copy of
the LSA in a link state database, and forwards
the LSA to every interface other than the one on
which it arrived.
Computing Shortest Paths
A router typically uses Dijkstra’s shortest-path
first algorithm[DIJK59] to compute optimal
routes in the network. A good description of
the algorithm is given in [KESH97].
When the algorithm stops, we have, for each
router, the route on the shortest path used to
reach it.
Complexity
Generally, link-state algorithms are complex.
Much overhead is needed in order to prevent
corruption of the Link State Databases and keep
them coherent. It also requires that nodes inde-
pendently compute consistent routes. In large
networks, LSAs also require much memory in
the routers.
2.3.3 Link-state versus Vector-distance
Both link-state and vector-distance routing are
commonly used in the Internet today. Distance-
vector routing does not require that nodes inde-
pendently compute consistent routes. They also
require less memory for routing tables than do
link-state protocols, because they do not need
to maintain a link-state database.
Vector-distance routing was introduced first
with Routing Information Protocol(RIP), which
is a very simple protocol. It works well with
small networks. However, for large and complex
networks RIP is probably wholly inadequate:
- It does compute new routes after any change
in network topology, but in some cases it does
so slowly, by counting to infinity. - RIP cannot be used in networks in which
routes may use more than 15 hops, because a
metric of 16 indicates infinity.
On the other hand, conventional wisdom is
that link-state routing is more stable because
each router knows the entire network topol-
ogy. The advantages of link-state routing are,
among others:- Fast, loopless convergence;
- Support for precise metrics and, in the future,
multiple metrics; - Support of multiple paths to a destination.
The focus of research on routing in recent years
has been on link-state routing. Although the pro-
tocols are more complex, the extra functionali-
ties they offer can be very useful to support new
service requirements in modern IP-networks.2.4 Hierarchical Structures &
Domains
2.4.1 Autonomous Systems
Since the beginning of the Internet, the concept
of Autonomous System(AS) has been used to
define a set of routers and networks under the
same administration.In the early days of the Internet, the network
consisted of a small number of campus networks
that were interconnected via one single back-
bone network (which is also called the “core”).From a routing point of view, the definition of
an AS is quite simple: all parts of an AS must
remain connected [HUIT00]. Routers belonging
to the same AS must exchange routing informa-
tion in order to maintain connectivity. This is
normally achieved by selecting a single routing
protocol and running it between all the routers.
Therefore, a consistent internal routing policy is
employed within an AS.2.4.2 Interior Gateway Protocols
Routing protocols employed within ASs are
called Interior Gateway Protocols(IGPs). The
most used IGPs include RIP, OSPF, and IS-IS.Splitting the Internet into several ASs aims at
lowering the routing overhead and at easing the
network management. Computing routes, dis-
tributing new versions of software, or isolating