our paper on routing by preference

[村山優子 <[e-mail]>]

The attached is the paper in the text form on routing by preference
for our presentation in video.

The postscript form has been placed for anonymous ftp in:

	host: sh.wide.ad.jp
	file: ~/pub/preference.ps.Z

Yuko Murayama
WIDE Project
----




             An Introduction to Routing by Preference



              Yuko Murayama          Kazunori Fujiwara
               WIDE Project          Waseda University

              Akihiro Shimizu             Motonori Nakamura
       Tokyo Institute of Technology        Kyoto University

             Hideyuki Aikawa              Shigeki Yoshida
         Fujitsu Laboratories, Ltd.      University of Tokyo

                          Hideyuki Matsuo
                         Hitachi Cable, Ltd.



                              Abstract

        This paper introduces a specific problem with network routing,
     namely how to enable the originator and the destination to choose
     their preferred route and paths. We explore the problem in the inter-
     administrative domains (AD) environment, and come to terms that
     each one of the end sites of a communication flow _ source and des-
     tination, has its own preference. Routing by preference is achieved by
     minimising costs in unfavourable ass.



1   Overview and Motivation


In Japan, internetworking with the Internet Protocol has been evolving [4].
The Routing Information Protocol (RIP) [3] has been used between routers
in the Japanese portion of the Internet, however, due to the gradual growth
of Japanese internet a new routing scheme is required. Since policy routing
has been researched and is being used in the U.S. Internet, we are considering
making use of it as well. The problem is, however, that our shift to a new
routing scheme is due to growth, and not because of the requirement for
access control.  The Japanese portion of the Internet has not reached the
stage of its U.S. counterpart yet in the sense that the requirements for access
control [1] have not been materialised yet. We started researching required
policies in the Japanese portion of the Internet last year, to find that it was
concerned more with connectivity.
   Under these circumstances, we have identified one specific requirement
for control over routing. This is a desire to enforce end-site's preference of
a route. We refer to the desire as the Motonori Problem in this paper, and
give some requirements for solution.
   In this paper, we define an administrative domain (AD) as a set of net-
works under a single administration. Several intra-AD routing schemes may
be used within an AD. The internet is composed of ADs interconnected to-
gether.  By the Internet, we mean the global internet operating with the
TCP/IP protocol suite [2]. Gateways which are engaged in inter-AD packet



                                  1




forwarding, are called border gateways. A pair of ADs are said to be neigh-
bours if there is at least one pair of border gateways, one in each AD, that
form an inter-AD connection.
   Our hypothesis of the internet environment is as follows.  The goal of
the internet is to provide its users with as near as global connectivity as
possible. Moreover, routing is performed hierarchically, first on an AD basis,
and second on a network basis as in most of the so-called policy routing
schemes.  We presume that an inter-AD route is expressed as a series of
ADs. A path is expressed as a series of border gateways.
   The organisation of the paper is as follows: Section 2 describes the prob-
lem of routing by preference. Section 3 discusses the requirements for solu-
tion. Section 4 gives some conclusions.



2   The Problem Description


2.1   Overview

In this section, we identify the problem of the enforcement of one's prefer-
ence in network routing. First, we describe the original problem defined by
Motonori Nakamura. Second, we present a similar problem in an organisa-
tion with overseas offices. Finally, the two problems are extended to fit in an
inter-AD environment and the problem of routing by preference is identified.
This problem is called "The Motonori Problem" in the rest of this paper.



2.2   The Original Motonori Problem:  the preference of the
      source

The original problem defined by Motonori Nakamura is as follows: suppose
that there are two networks, A and B, interconnected by two interfaces (see
Fig.1).  In Fig.1, A1 and A2 are the gateways in A, and B1 and B2 are
the gateways in B. The two networks differ with respect to delay, i.e. one
network is faster than the other, let A be faster than B. We assume that
site X in A is closer to A1 in terms of delay than to A2, and site Y is closer
to B2 than to B1. In this situation, the problem is how one can enforce two
policies as follows:


  1. when site X in A sends the traffic to site Y in B, the traffic shall stay
     in A for as long as possible, so that it will not have to travel in B for
     long before it gets to the destination.


  2. when a site in B, Y, sends the traffic to a site in A, the traffic will
     exit B as early as possible, so that it will travel most of the journey
     through A to reach its destination.


   [ Figure 1: The Original Motonori Problem ]


   In either case, the source of a communication flow wants the traffic to
take the shortest path in the slower network, but does not care how long
the traffic would stay in the faster network.



                                  2




2.3   An organisation with overseas offices:  the preference of
      the destination

An organisation A with overseas offices may well have intra-organisational
links to those sites. Suppose that the organisation has two interfaces, L1 and
L2 to the Internet, i.e. the local domain would be connected to one portion
of the Internet, B, and the overseas domain would be to another portion,
C. For instance, one interface is to the Japanese portion of the Internet and
the overseas interface is to the U.S. portion (see Fig.2).


   [ Figure 2: An organisation with overseas offices ]


   The organisation A wants the traffic destined for or generated from it,
to make as much use of its intra-organisational link as possible. This policy
can be enforced by the following strategies.


  1. when site X in A sends the traffic to site Y in portion C of the Internet,
     the traffic shall go through the internal link, L4, and to the destination
     through L2.


  2. when site Y in C sends the traffic to site X in A, the traffic will enter
     the organisation A's domain as soon as possible by taking L2.


  3. when a site in A2 sends the traffic to B, the traffic should go through
     L4 and L1.


  4. when a site in B sends the traffic to portion A2 of Organisation A, the
     traffic should come into A through L1, and get to the destination in
     A2 through L4.


   3 and 4 above are identical to 1 and 2 respectively and 1 and 2 are
identical with the original Motonori Problem introduced in the previous
subsection.  The problem of an organisation with overseas offices seems to
be reduced to the original Motonori Problem. However, in the latter what
matters is how to enforce the source's preference, while the former includes
the implications from the destination's preference.



2.4   The Motonori Problem: the preference of the source and
      the destination

We define the Motonori Problem by combining the previous two problems
and developing them further into an inter-AD environment.
   We detach the source and the destination sites from the ADs to be
traversed, so that the problem is concerned more with inter-AD transactions
(see Fig.3).
   The original Motonori problem could be extended as follows. We assume
that site X in C wants to send some traffic to site Y in D. The two transit
networks differ by some measurement of cost, i.e. one network, A, is better
than the other, B, from X's point of view. In this situation, the problem is
how one can enforce the following desire:


     when site X0 in X sends the traffic to site Y0 in Y the traffic
        shall stay in A as long as possible, so that it will travel the
        least amount of the path through B.



                                  3



   [ Figure 3: The Motonori Problem ]

   In general, the question is how a source can enforce its preference of m
ADs on a route which is composed of n ADs to a destination in the way that
the traffic would stay in an unfavourable AD as little as possible in terms
of a given cost parameter.  Indeed, routing by preference is achieved by
optimising costs of unfavourable AD paths. In other words, we do not care
too much about what it costs to get the traffic through the preferred ADs,
but do wish that traffic would travel the shortest paths via any unfavourable
ADs.
   The problem of an organisation with overseas offices could be extended
in the similar manner. A destination has m favourable ADs out of n ADs
on a route.  It wishes that the traffic destined to it would come into its
favourable ADs as soon as possible _ i.e.  to take the shortest paths in
the unfavourable ADs. One difference from the source preference problem
defined above is that it is the destination of a packet who wishes to enforce
its preference.
   In the inter-AD environment, we presume that an inter-AD route on an
AD basis is selected, and then the route is resolved into paths _ a series of
inter-AD routers. We have discussed the problems of enforcement of one's
preference in path selection so far, presuming that an inter-AD route has
been decided. A source or a destination could enforce its preference in inter-
AD route selection as well, so that the traffic would go through favourable
ADs as much as possible _ i.e. unfavourable ADs could be avoided as much
as possible.
   The Motonori Problem could be redefined as the enforcement of source's
and destination's preference in inter-AD route selection as well as in path
selection, so that the traffic would go through favourable ADs as much as
possible minimising costs in unfavourable AD paths.



3   The requirements for solution


3.1   Overview

In this section, we discuss the requirements for solution.
   Demands from a source and a destination would be expressed in terms of
two types of parameters; preference and cost. Preference parameters would
vary according to the AD level attributes and the network level attributes
including the qualities of service.  Some of those may include, but are not
limited, to the following:


   - AD level attributes, e.g. the membership of a certain inter-AD project,
     and AD categories such as academic, research, and so on.


   - network level attributes, such as the Maximum Transmission Unit
     (MTU) being bigger than for the others.


   - networks which offer a certain level of quality of services (QoS), e.g.
     short delay, high throughput, secure, inexpensive, etc.


   A cost parameter specified by a source or a destination would be put into
two categories; one related to distance, and the other not. It might be easier
to define the Motonori Problem with distance-related costs, however, there



                                  4




is no reason to refuse the problem with costs which is not related to distance.
A source would specify the parameter to minimise the performance, security,
or monetary costs in unfavourable ADs.
   Preference and cost parameters would be used for both route selection
and path selection.  Preference is used to select an AD route, so that un-
favourable ones could be avoided as much as possible. Cost parameters could
be used to select a minimum cost route out of possible preferred AD routes.
Paths for a selected route would be decided in the way that the minimum
cost paths would be taken in the unfavourable ADs.
   Source's preference may have to be known to other ADs only at the
forwarding time. Destination's preference may well be known to other ADs
by routing information exchange. It could be known to an individual source
AD at the start of forwarding such as at the path-set-up time in IDPR [5].
   Deciding a route and paths, one needs to know the followings:


  1. Source's and destination's demands;  favourable/unfavourable ADs,
     and the cost parameter to be minimised in the unfavoured AD paths.


  2. Costs of transit AD paths; costs of the links between border gateways.


   Source's demand and destination's demand may collide with each other.
Some kind of process may be needed to negotiate with both demands. Al-
ternatively, one can set up a policy on which demand should be taken into
account with high priority. Furder investigation is required in this aspect.
   Source's and destination's demands can be taken into account by route
calculation and forwarding.  Those demands have two aspects; inter-AD
routing and intra-AD routing.  The demands would be considered when
deciding an inter-AD route, so that unfavoured ADs could be avoided as
much as possible. Even if there were some unfavourable ADs on the selected
route, the effect of those AD paths would be minimised by selecting the
preferable one out of multiple inter-AD links according to the difference in
link costs obtained by the second requirement in the above.
   A transit AD could distribute the cost information on intra-AD and
inter-AD link between border gateways to other ADs. The cost might vary
according to the attributes of the communication flow _ i.e.  the type of
application, research traffic, source/destination, etc.  The costs could be
known to the border gateways of the neighbouring ADs in case of hop by
hop routing, and to all the possible source ADs in case of source routing.
Alternatively, it could be delivered on a request-reply basis.
   If the transit ADs would not like to advertise the intra-AD cost informa-
tion, the end sites' demand could be directed to unfavoured ADs to ask them
to minimise a given cost in intra-AD routing .  Since the use of resources
within an AD is decided autonomously by that AD, it is up to an unfavoured
AD to minimise a given cost to route the inter-AD traffic within the AD as
requested. Hence, the request would not be guaranteed. A solution would
only facilitate a way to express these demands to the transit ADs.



4   Conclusions


The work presented in this paper was motivated from the narrowly fo-
cussed viewpoint, i.e. a desire to allow a source and a destination to utilise



                                  5




favourable networks to reach a destination.
   In this paper we identify the problem of routing by preference as the
enforcement of source's and destination's desire to minimise a given cost
for unfavourable AD paths.  We need the way to express the source's and
destination's demands as well as the distribution of cost information of intra-
AD paths by the transit ADs. The source's demand could be implemented
in the forwarding phase.  The cost information of transit AD paths would
be distributed by a routing information exchange scheme.
   The destination's demand has never been considered in any policy rout-
ing protocol, but it could be implemented at the forwarding phase or at the
routing information exchange phase. We are planning to try and investigate
routing by preference in both the hop-by-hop and source routing paradigms.
   Further work is required on the negotiation between the source and the
destination if their demands collied each other.



References


[1]L. Breslau and D. Estrin. Design of inter-administrative domain routing
   protocols.  In Proc. ACM SIGCOMM'90 Symposium Philadelphia, PA,
   pp. 231-241, September 1990.


[2]V. G. Cerf and E. Cain. The dod internet architecture model. Computer
   Networks, pp. pp.307-318, July 1983. North-Holland.


[3]C.L. Hedrick. Routing information protocol. RFC 1058, June 1988.


[4]H. Ishida.  Academic internetworking in japan.  Proc. of INET'92, pp.
   103-112, June 1992. Kobe, Japan.


[5]M. Steenstrup. Inter-domain policy routing protocol specification: Ver-
   sion 1. Internet draft, May 1992.



                                  6