P1: 211
Zarki WL040/Bidgolio-Vol I WL040-Sample.cls September 15, 2003 8:55 Char Count= 0
834 WIRELESSINTERNETDynamic Routing
In a circuit-switched connection as used in a public
switched telephone network (PSTN), the path of a call
is established at the beginning of a connection and is
maintained throughout the duration of the call. One of
its weaknesses is the vulnerability of the network when
central switching stations fail. A much worse problem for
data traffic has been the fact that such traffic tends to be
bursty and the reserved circuit is unused much of the time,
thus wasting much of its capacity. In order to increase the
efficiency and robustness, a packet-switched architecture
was envisioned for the Internet. Packets from many
sources and destinations may share a common transmis-
sion circuit but be switched independently, and where the
flow of data packets is constantly monitored and adjusted
through the network, possibly around any failed nodes.
This process of directing the switching and flow of pack-
ets is called “routing.”
Routing in the Internet is performed by a device called
a router, which has connections to multiple networks and
has the ability to relay data packets between these net-
works. The router decides to which network each packet
should be sent based on the information available in the
IP header of each packet. Currently, most routers look at
only the destination address to decide the fate of a packet,
even though other information is available (see the section
Real-Time Traffic Support). Instead of the entire IP ad-
dress, only a subset of the address is used by the router.
In classful routing, only the class portion of the address
is used, while in CIDR, only the prefix portion of the ad-
dress is used. Based on the destination address, the router
consults its routing table, which lists the port number as-
sociated with the precomputed “optimal” path for that
destination address. The routing table can be configured
manually or automatically. In either case, the optimal path
is determined based on the network topology and differ-
ent link metrics (e.g., bandwidth, delay, load, reliability,
and cost).
When the routing table is configured manually, static
routing is said to be used. It is the preferred mode of op-
eration in networks with few nodes or in stub networks,
which is a network with only one or two paths to the rest
of the network.. While simple to configure for small net-
works, a router using static routing cannot reroute pack-
ets automatically if the instantaneous traffic loads change
or if a router or a link in a preconfigured route goes down
for any reason. The destination may remain unreachable
until human intervention is made to update the routers,
based on new traffic loads or utilization of the failed link
or node. Dynamic routing addresses these deficiencies by
enabling dynamic and automatic update of the routing ta-
bles in routers. For example, if a router detects failure of
a link, it will notify other routers of the condition so that
appropriate adjustments to the routing table entries can
be made. The algorithm for calculating the optimal path
and the mechanisms for sharing information among dif-
ferent routers specify numerous routing protocols used in
the Internet.
Routing protocols are generally divided into two
groups. Interior gateway protocol (IGP) is used within
ASs, and exterior gateway protocol (EGP) is used betweenrouters of different ASs, i.e., across the Internet. The two
most widely used IGPs are routing information proto-
col (RIP) (Hendrick, 1988) and open shortest path first
(OSPF) (Moy, 1998b). Examples of EGP include some-
what confusingly termed exterior gateway protocol (EGP)
(Mills, 1984) and border gateway protocol (BGP) (Rekhter
& Li, 1994). For details about the protocols, interested
readers may consult the RFCs as well as numerous books
and articles (Doyle, 1998; Huitema, 2000; Moy, 1998a).
Below we present a brief overview of the most popular
routing algorithms currently in use in the Internet.Routing Information Protocol (RIP)
RIP is a distance vector protocol that uses the number
of “hops” (i.e., the link between two nodes) to determine
the optimal path to the destination. Every 30 s, the entire
routing table is broadcast, and the routing tables of the
listening routers are updated based on the reported hop
counts. This reliance on second-hand information results
in relatively low computation and storage requirements,
but it also results in slow convergence. RIP is suitable only
for relatively small networks (no wider than 15 hops) since
the maximum hop count is restricted to 15 (a hop count of
16 is considered infinity). In addition, the high bandwidth
overhead of broadcasting entire routing tables makes the
algorithm hard to scale.Open Shortest Path First (OSPF)
OSPF is a link state-based algorithm, in which the link
states of each node are flooded to all routers in the net-
work. The transmission takes place only when there is a
change in network topology. The link state may convey
information about various link states such as through-
put, delay, loss rate, or some cost function. Based on the
link states, each node in the network computes the com-
plete network topology. As all nodes have access to the
same link state information, all nodes should arrive at the
same network topology. Based on this map of the network,
the shortest path tree to each destination is computed us-
ing a shortest path first algorithm, and the result is used
to populate the routing table. Such computation places
much heavier burden on memory and processing power
than algorithms such as RIP, but it also results in faster
response to network events such as a link failure, quicker
route convergence, and requires less traffic overhead espe-
cially for larger ASs. OSPF also offers additional advanced
features that are described in detail in the literature. Such
advantages are driving the increasing use of OSPF over
RIP.Border Gateway Protocol (BGP)
BGP is an interautonomous system (inter-AS) routing
protocol. BGP version 4 has become the main inter-AS
routing protocol in the Internet. BGP is a path vector pro-
tocol, which defines a route as a pairing between a desti-
nation and the attributes of the path to that destination.
A BGP router learns of multiple paths via internal and
external BGP speakers and picks the best path, which is
then sent to external BGP neighbors. A network adminis-
trator has control over the policies applied during the best
path selection. In addition, unlike other routing protocols,