failing elements is easier when the number of
links and routers is kept relatively small. How-
ever, connectivity must be maintained. The rout-
ing tables inside the AS should include entries
covering all possible Internet destinations. Since
IGP is only used within an AS, the choice of IGP
in one AS is independent of that of another AS.
The routing tables are maintained by the IGP,
but the IGP messages are only exchanged be-
tween routers that belong to the AS. These
routers can only discover information about the
internal networks to which they are directly con-
nected. They must get the information about the
exterior networks through a dialogue with exte-
rior gateways, which are entry points in adjacent
autonomous systems.
2.4.3 Exterior Gateway Protocols
The role of Exterior Gateway Protocol(or sim-
ply called Exterior Protocol) is precisely to
exchange this “reachability information” in
order to enable the ASs to exchange routing
information.
Although all the routers within an AS are mutu-
ally co-operative, routers interconnecting two
ASs may not necessarily trust each other. Exte-
rior protocols determine routing between entities
that can be owned by mutually suspicious
domains. An important part of exterior proto-
cols, therefore, is configuring border gateways
(that is, gateways that mediate between interior
and exterior routing) to recognise a set of valid
neighbours and valid paths.
The EGP-protocol was designed for this pur-
pose. Although EGP is still in use today, how-
ever, it is being replaced by Border Gateway
Protocol(BGP). The BGP version that has been
in use since 1995 is BGP-4 [RFC1771].
BGP-4 is a path-vector protocol, where distance
vectors are annotated not only with the entire
path used to compute each distance, but also
with certain policy attributes. It guarantees loop-
freeness at the expense of large routing tables.
BGP routers use TCP to communicate with each
other, instead of layering the routing messages
directly over IP, as is done in every other Inter-
net routing protocol. This simplifies the error
management in the routing protocol. However,
routing updates are subject to TCP flow control,
which can lead to fairly complicated and poorly
understood network dynamics. For example,
routing updates might be delayed waiting for
TCP to time out. Thus, the choice of TCP is
still controversial [KESH97].
If an AS has more than one BGP-speaking bor-
der gateway, path vectors arriving at a gateway
must somehow make their way to all the other
gateways in the AS (also called internal peer-
ing). BGP-4 is hard to maintain because of the
need to choose consistent path attributes from
all the border routers, and to maintain clique
connectivity among internal peers.2.4.4 Interconnecting Exterior and
Interior Routing Protocols
The key problem in interconnecting exterior and
interior protocols is that they may use different
routing techniques and different ways to decide
link costs. For example, the exterior protocol
may advertise a 5-hop count to another AS.
However, each of these hops may span a con-
tinent and cannot be compared with a 5-hop
path in the interior of an AS.A similar problem arises if the interior and ex-
terior routing protocols use different routing
schemes. For example, the exterior protocol may
use path-vector routing, and the interior may use
link-state routing. Thus, the border gateway
must convert from a link state database to a set
of distance vectors that summarise paths to its
interior. In the other direction, it must convert
from distance-vector advertisements to external
records for the interior routing protocol.The bottom line is that interconnecting a given
interior and exterior protocol requires a fair
amount of manual intervention, and frequent
monitoring to ensure that the network stays up.
This is a direct consequence of the heterogeneity
in the administration of the Internet, and of its
decentralised control.2.5 Supporting QoS Requirements
Routing deployed in today’s Internet typically
supports only one type of datagram service
called “best-effort”. No guarantee of QoS re-
quirements is offered, but routing is optimised
for a single arbitrary metric, administrative
weight or hop count. Alternative paths with
acceptable but non-optimal cost cannot be used
to route traffic.In order to support integrated-services class of
services, multiple paths between node pairs will
have to be calculated. Some of these new classes
of service will require the distribution of addi-
tional routing metrics, e.g. delay, and available
bandwidth. If any of these metrics change fre-
quently, routing updates can become more fre-
quent, thereby consuming network bandwidth
and router CPU cycles.A second problem is that today’s routing will
shift the traffic from one path to another as soon
as a “better” path is found. The traffic will be
shifted even if the existing path can meet the ser-
vice requirements of the exiting traffic. If rout-
ing calculation is tied to frequently changing