Side_1_360

6.2.2 Routing Protocols

The original core routers in the ARPANET used

a protocol call the Gateway-to-Gateway Protocol

(GGP) to exchange routing information (every

router was then referred to as a gateway). A

router would exchange information with every

neighbour router (which was fixed). The routing

information consisted of a set of pairs (network,

distance). The distance gives the cost of reaching

that network. Here, cost was understood as the

number of hops, meaning that low bandwidth

paths with fewer hops would be preferred

to higher bandwidth paths with more hops.

A set of routers can be grouped into an autonom-

ous system(AS). An AS is handled by a single

administrative authority, e.g. a network operator.

A conceptual view on two ASs using Exterior

Gateway Protocols (EGPs) between them and

Interior Gateway Protocols (IGPs) internally is

given in Figure 18. As recognised, a gateway/

border router may use two different protocols,

one within the AS and another outside the AS.

One of the first IGPs is the Routing Information

Protocol (RIP), originally designed to provide

consistent routing and reachability information

among hosts in a local network at the University

of California at Berkeley. Using RIP, routing

data for each router is broadcast to all its neigh-

bours periodically. Each destination in the rout-

ing table is included in the route updates. For

a larger network, slow convergence may well

occur, for instance when a network portion sud-

denly becomes unavailable (slow count to infin-

ity). This could be alleviated by principles called

split horizon and hold down, see [Come88].

Other IGPs are OSPF and IS-IS.

Two routers that belong to different ASs are said

to be exterior neighbours. The protocol exterior

neighbour used to advertise reachability infor-

mation to other ASs is called the Exterior Gate-

way Protocol (EGP). An EGP has three main

features: i) support a mechanism allowing two

routers to agree to communicate reachability

information (acquisition); ii) a router tests

whether its EGP neighbour is responding; and

iii) EGP neighbours exchange reachability infor-

mation. The reachability information is com-

monly called routing information as it is used as

a basis for deciding upon routing of packets.

In order to fulfil its three features a number of

message types are devised, like ‘acquisition’,

‘cease’, ‘hello’, ‘poll’ and ‘routing update’.

When two routers agree to exchange reachability

information (acquisition), they also set initial

values for a time interval to be used for testing

whether the neighbour is alive (called a hello

interval) and a polling interval that controls the

maximum frequency of routing updates. These

intervals can be changed. Moreover, they may

be asymmetric, i.e. different values in the two

directions. Considering features ii) and iii)

above, one recognises that the reachability

exchange has been separated from the routing

information exchange. A motivation for this is

that reachability could change more frequently

without influencing the routing.

In a sense, EGP routing update messages can be

considered as a generalisation of GGP routing

updates as they include multiple routes (com-

pared to a single route in the GGP). Basically,

by using the routing information conveyed by

EGP, a tree structure can be composed for each

router where the router forms the root.

Between ASs, the Border Gateway Protocol

(BGP) is commonly used. As seen from a BGP

router, the network is made up of other intercon-

nected BGP routers. Two routers are connected

if they share a common network. Three cate-

gories of networks are used, see Figure 19: i)

stub network that has only one connection to the

BGP graph (no transit possible); ii) multicon-

nected network (could be used for transit, but

does not allow it); and iii) transit network, which

is used for transiting packets.

BGP can be said to be a distance vector protocol.

In addition to the cost to each destination, each

router does also keep information on the exact

path to be used. Information on these exact paths

is then exchanged. More information on BGP is

found in [RFC1771] and [RFC1268].

BGP version 4 includes mechanisms that allow

aggregation of routes and advertising of IP add-

ress prefixes. In one respect, one can say that

Figure 18 Use of exterior and
interior gateway protocols

interior gateway

protocol

interior gateway

protocol

exterior

gateway

protocol

autonomous system autonomous system

Figure 19 Network categories,
referring to BGP

a) stub b) multi-connected c) transit