Side_1_360

the source to be aware of the entire network

topology. If a link or a router along the path

goes down, a source-routed packet will not

reach its destination. Moreover, if a path is

long, the packet header can be fairly large.

Thus, source routing trades off specificity

in routing for packet-header size and extra

overhead for control messages.

An intermediate solution is to use a loose

source route. With loose source routes, the

sender chooses a subset of routers that the

packet should pass through, and the path may

include routers not included in the source

route. Loose source routes are supported in

the IP version 4 and 6 headers.

• Stochastic vs. deterministic:With a determin-
  istic route, each router forwards packets
  toward a destination along exactly one path.
  In stochastic routing, each router maintains
  more than one next hop for each possible des-
  tination. It randomly picks one of these hops
  when forwarding a packet.The advantage of
  stochastic routing is that it spreads the load
  among many paths, so that the load oscilla-
  tions characteristic of deterministic routing are
  eliminated. On the other hand, a destination
  may receive packets along the same connec-
  tion out of order, and with varying delays.
  Consequently, modern networks usually use
  deterministic routing.


• Single vs. multiple path:In single-path rout-
  ing, a router maintains only one path to each
  destination. In multiple-path routing, a router
  maintains a primary path to a destination,
  along with alternative paths. If the primary
  path is unavailable for some reason, routers
  may send packets on the alternative path1).


• State-dependent (dynamic) vs. state-indepen-
  dent (static):With state-dependent or dynamic
  routing, the choice of a route depends on the
  current (measured) network state. For exam-
  ple, if some links are heavily loaded, routers
  may try to route packets around that link.
  With state-independent or static routing, the
  route ignores the network state. For example,
  a shortest-path route (where we measure the
  path length as the number of hops) is state-
  independent. State-dependent routing usually
  finds better routes than state-independent rout-
  ing, but can suffer from problems caused by
  network dynamics (such as the routing oscilla-
  tions). It also requires more overhead for mon-
  itoring the network load.
  
  
  • Link-state routing vs. distance-vector routing:
    In link-state routing each node knows the
    topology and the cost of each link. In dis-
    tance-vector routing the vector contains infor-
    mation of topology and cost from the originat-
    ing node to the destination.
  
  
  
  

Having broadly considered the choices in rout-

ing protocol design, we are going to study spe-

cific routing protocols that make a selection

from the choices described earlier. The literature

on routing is vast. In this paper we only study

routing in IP-networks (i.e. the Internet).

2.2 Status of Internet Routing

We refer to the previous discussion (section

2.1.3) of routing protocol choices. In summary,

in today’s Internet the following choices have

been made:

• Centralised routing is not used in the Internet
  due to the problems of dependability and scal-
  ability. The distributed routing approach is
  implemented.


• Separate protocols are used for intra-domain
  routing and inter-domain routing, respectively
  (more discussion in section 2.4).


• Hop-by-hop routing is the most common
  approach in Internet today. However, it is
  believed that source routing (or explicit rout-
  ing) might be better suited to select paths sat-
  isfying user’s QoS requests [SU00]. There-
  fore, research on source routing has got more
  focus in recent years.


• Deterministic routing is preferred due to its
  ability to offer more consistent quality of ser-
  vice.


• Currently, single-path routing is used on the
  Internet, because maintaining alternative paths
  requires more routing table space. However,
  multiple-path routing can reduce both the
  packet blocking probability and the restoration
  time in the presence of failure. Multiple-path
  routing can also give better support to the QoS
  requirements that are becoming more and
  more important for the future Internet.


• The Internet uses both state-dependent and
  state-independent routing.


• Both distance-vector and link-state routing are
  used, as discussed in the next section.

1)With stochastic routing, routers may send packets on alternative paths even if the primary path is

available.