As per Relevance of the word gateways, we have this rfc below:
Network Working Group D.
Request for Comments: 1102 M.I.T. Laboratory for Computer
May 1989
Policy Routing in Internet
1. Status of this
The purpose of this RFC is to focus discussion on particular
in the Internet and possible methods of solution. No
solutions in this document are intended as standards for
Internet. Distribution of this memo is unlimited
2.
An integral component of the Internet protocols is the
function, which determines the series of networks and gateways
packet will traverse in passing from the source to the destination
Although there have been a number of routing protocols used in
Internet, they share the idea that one route should be selected
of all available routes based on minimizing some measure of
route, such as delay. Recently, it has become important to
routes in order to restrict the use of network resources to
classes of customers. These considerations, which are
described as resource policies, are poorly enforced by the
technology in the Internet. This document proposes an approach
integrating policy controls into the Internet
I assume that the resources of the Internet: networks, links,
gateways, are partitioned into Administrative Regions or ARs.
AR is governed by a somewhat autonomous administration, with
goals as to the class of customers it intends to serve, the
of service it intends to deliver, and the means for recovering
cost. To construct a route across the Internet, a sequence of
must be selected that collectively supply a path from the source
the destination. This sequence of ARs will be called a Policy Route
or PR. Each AR through which a Policy Route passes will be
that the PR has been properly constructed. To this end, each AR
wish to insure that the user of the PR is authorized, the
quality of service is supported, and that the cost of the service
be recovered
In the abstract, a Policy Route is a series of ARs, which are
to be named with globally distinct identifiers. (The requirement
global names for ARs suggests that the name space of ARs is flat
That simplifying assumption is made in this RFC, but it should
possible to extend the scheme described here to permit nesting of
Clark [Page 1]
RFC 1102 Policy Routing in Internet Protocols May 1989
to reduce the amount of global information. The problem of
structure to the space of ARs is an exercise for later study.)
Before a PR can be used, however, it must be reduced to more
terms; a series of gateways which connect the sequence of ARs.
gateways will be called Policy Gateways
Presently, the closest mechanism to policy routing in the Internet
EGP, the Exterior Gateway Protocol. EGP was constructed to
regions of the Internet to communicate reachability information,
though they did not totally share trust. In this respect,
regions hooked together by EGP could each be viewed as
Regions. However, the mechanisms of EGP imposed a
restriction on the interconnection of the Administration Regions.
practice, this has proved unsatisfactory. Policy matters are
by human concerns, and these have not turned out to be amenable
topological constraints, or indeed to constraints of almost any sort
The proposals in this memo are designed to permit as wide a
as possible in the construction and enforcement of policies.
particular, no topological restrictions are assumed. In general,
approach taken in this memo is driven by the belief that
policies reflect human concerns, the system should primarily
concerned with enforcement of policy, rather than synthesis
policy. The proposal permits both end points and transit services
express and enforce local policy concerns
3. Policy
Almost all approaches to policy control share, to some degree,
idea of a Policy Route. The distinguishing component of a
approach is the procedure by which the Policy Route is synthesized
One approach to synthesizing routes is to associate with
distinct policy a subset of all the gateways in the system, and
run a routing algorithm across the subset of the gateways.
approach has several drawbacks. It requires a distinct
computation for every policy, which may be prohibitively expensive
It requires the global agreement on the nature and scope of
policy, which is at odds with the desire of Administrative Regions
establish their own independent policy assertions. Finally,
almost inevitably implies a topological restriction on
interconnection of regions
Another synthesis approach is to have each Policy Gateway
incoming packets and determine, based on local policy constraints
the most appropriate next AR. This approach might possibly work,
again has several drawbacks. First, it implies a substantial
of computation at each Policy Gateway. More importantly, it
the route selection from the location where it would most
Clark [Page 2]
RFC 1102 Policy Routing in Internet Protocols May 1989
be executed, the end-points of the connection
It is useful to think of the interconnected ARs as a marketplace,
which various services are offered and users select among
services to obtain packet transport. By this analogy, it
appropriate that the actual selection of the Policy Route should
made by the end ARs desiring to send the packets, rather than by
Policy Gateways. Looking to the phone system for comparison, it
the customer of the phone system who selects which of the
distance carriers to use, whether to purchase a fixed price
or pay incrementally for usage, and so on. In this proposal
therefore, Policy Routes are synthesized at the end point, where
packet originates, and are attached to packets in order to
them through the appropriate series of ARs. In other words,
Routes are a form of source routing. The role of synthesizing
Policy Route is shared between the source AR and the
source host
In this architecture, therefore, the function of the Policy
is not to synthesize the Policy Route, but to verify it. In
following sections, we will address the two questions of how a
Route is verified, and how a Policy Route is synthesized
In determining that Policy Routes should be synthesized at the
point, it is important to distinguish between those aspects
routing that reflect legitimate policy concerns, and those aspects
routing which, in reality, relate to the detailed operation of
ARs. For example, if one were to represent Policy Routes using
existing Internet source route mechanism, which allows the end
to specify a series of gateways through which the packet should pass
the result would be that too much function has been transferred
the internals of the Internet to the end points. The end point
have to have knowledge of exactly which gateways are up
operational at a particular moment, and this degree of
cannot be justified by policy concerns. Further, it would
necessary to run a systemwide gateway reachability protocol
This proposal attempts to strike a balance between end
specification of those concerns legitimately related to policy,
local determination in the Policy Gateways of the more
details necessary for reliable operation. This leads to a two-
routing model, in which the abstract Policy Route, a series
administrative regions, is specified by the end point as a form
source route, and each Policy Gateway selects the next actual
Gateway that is to be used to forward this packet. In other words
the abstract Policy Route is made concrete incrementally.
division of function does require that the source AR know if
are faults that have partitioned pairs of ARs that are
Clark [Page 3]
RFC 1102 Policy Routing in Internet Protocols May 1989
connected together. This implies a global reachability protocol
be run for the purpose of providing information to the source AR,
it need only concern itself at the level of ARs, not at the level
gateways. In a later section on cost-recovery, the topic of
selection will be discussed in more detail
An objection to a scheme such as source routing is that
potentially bulky source route must be in every packet, and must
evaluated for each packet. One solution to this performance
is to employ a limited form of route setup, in which the
Policy Route is carried only in the first packet of a sequence, and
short identifier or "handle" is included in subsequent packets of
sequence. Each Policy Gateway evaluates the PR on first encounter
and caches the result, which is then retrieved for later
using the handle in the packet. The idea of a handle and caching
and the need for a form of route setup, is discussed later
4. Verification of Policy
As a packet arrives at a Policy Gateway, attempting to enter an AR
the Policy Gateway must decide whether it is legitimate to
this packet, and if so, at what next Policy Gateway the packet
exit the AR (assuming that the final destination is not within
AR). The information available to the Policy Gateway to support
decision determines the range of policies that can be enforced
Determining what information is to be available is therefore
central feature of our proposal
4.1. Identifying the
Classic routing decisions, those minimizing some cost, are
driven only by the destination of the packet. At a minimum,
decisions must be based both on the source and the destination of
packet. In fact, source and destination addresses may not
sufficient to determine policy, for an AR may support different
with different rights, moreover a single user may wish to
different rights at different times. I suggest that to identify
user who is proposing to use this particular Policy Route, it
sufficient that the packets contain the source host and AR,
destination host and AR, and, optionally, a User Class Identifier,
UCI. In a later section, I discuss how to prevent misuse of the
class identifier
In fact, the source and destination host address may not be needed
support the practical range of policy decisions required
intermediate ARs. Only the source and destination AR information
be necessary. If individual host addresses are to be used,
implies that intermediate ARs will want to keep track of the
Clark [Page 4]
RFC 1102 Policy Routing in Internet Protocols May 1989
of individual hosts. It would be much simpler if the source AR
be trusted to permit only the proper hosts to use certain PRs.
will consider this further in a later section when I discuss the
of the Policy Controller
4.2. Verifying the
The packet contains an abstract Policy Route: a series of
identifiers. To validate this route, each Policy Gateway could
the complete selection of acceptable policy routes, and require
an incoming packet have a Policy Route that exactly matched one
the stored entries. This degree of constraint probably
the situation, and causes an information explosion. At the other
of the scale, Policy Gateways could simply be sensitive to the
AR and the destination AR. In some cases, particularly as regards
billing, this does not provide sufficient constraints. This
suggests that in deciding whether a given Policy Route is valid,
Policy Gateway should look at the source and destination ARs,
also the ARs immediately abutting the AR in question, called
entry and exit ARs
One can think of the verification information in the Policy
as a number of templates. Each template is associated with a
set of users, as described by the source and destination host
and the optional User Class, and contains the four ARs
above, Source, Destination, Exit, and Entry. An incoming
should be forwarded if, and only if, there is a template matching
information in the packet. These templates will be called
Terms
4.3.
The Policy Terms, as described so far, do not permit the
of a realistic range of policies. What is needed is the ability
attach to a Policy Term a number of conditions, which
circumstances under which the term is valid. These might
what type of service (TOS) is available, what times of day the
is valid, what accounting options are valid, and so on. A time-of
day condition, for example, would permit networks, like time-
systems, to offer their off-peak capacity to a wider community
In general, these conditions could be quite arbitrary. The
constraint on these conditions is that any condition imposed by
Policy Gateway must be understood by the end point, so that it
generate Policy Routes which will conform to the condition. If
is not so, and the Policy Gateway attaches capricious conditions
its policy terms, then the end points will construct Policy Routes
good faith which are rejected, leading to a failure to obtain
Clark [Page 5]
RFC 1102 Policy Routing in Internet Protocols May 1989
and serious dissatisfaction among users. For this reason, it
necessary that the nature of policy conditions be negotiated
advance
The most interesting and difficult conditions are those that
to the dynamic state of the network. An excellent example is
bilateral mutual aid agreement between two transit ARs in which
agrees to carry the load of the other if the other should go down
To capture this agreement, each might wish to put in Policy
with the condition that they are valid only if some other AR is non
functional. In the earlier discussion of Policy Route synthesis,
was necessary for the ARs to run a global up-down protocol
describe the connectivity of ARs. This protocol is sufficient
allow the Policy Gateway to know that some other AR is non
functional, but care is required in the dynamics of this system
ensure that the end point in the PR have a consistent view of
up-down status of the world. Otherwise, there would be
service outages, which again would lead to user dissatisfaction
In general, this proposal asserts that policies should not be
on highly dynamic phenomenon. Administrative Regions should
thought of as stable entities which do not change state rapidly
Highly dynamic characteristics like queue length should be dealt
by proper engineering internal to the AR. Precisely
conditions must be propagated globally, attempting to base
condition on a highly dynamic parameter is liable to lead to
instability
4.4. Ownership of Policy
In Section 1, all the resources of the network were described
being partitioned among the ARs. This statement does not extend
the Policy Gateways, which sit on the boundary between ARs.
the Policy Gateway must be composed of two physical halves,
by a wire, or there must be a joint agreement for the ownership
operation of the gateway. This is a matter for further study
5. Examples of Policy
This section presents examples of how policy terms would be used
express a range of practical policies. In order to give examples,
is necessary to define a notation for policy terms. The following
not necessarily the most compact form, but will be sufficient
some simple examples
Clark [Page 6]
RFC 1102 Policy Routing in Internet Protocols May 1989
A Policy Term will be expressed as follows
((Hs,ARs,ARent),(Hd,ARd,ARexit),UCI,Cg
where
Hs is the source host address
ARs is the source AR
ARent is the entry AR
and these three values comprise the first "element" of the term
describing the permitted access looking toward the source
Similarly, for the destination, there is an element describing
host address, the adjacent AR, and the ultimate AR
In addition to the two directional elements of the term, there
global information
UCI is the User Class Id,
Cg are any global conditions
In many cases, an element will not want to constrain one of
values, and we will use the "*" symbol to indicate a "wild-card
match
To construct some simple examples, here is a topology, where
elements are hosts, G elements are Policy Gateways, and
elements are ARs
H1 --- 1 --- G1 ----- 2 ------ G2 ----- 3 ----- H
| |
| |
| |
|---- G3 ----- 4 ------ G4 ------|------ G5 --- 5
| |
| |
| H
H
In this picture, there are four hosts, five gateways, and
Administrative Regions
First, consider AR two. It has no hosts attached, and models
transit service, such as the NSF network. It may have a very
policy: it will carry any traffic between universities,
further constraint. If we let AR1 and AR3 be the regions of
Clark [Page 7]
RFC 1102 Policy Routing in Internet Protocols May 1989
particular universities, then its policy term could be written as
AR2: ((*,1,*),(*,3,*),*,*).
This says that AR 2 agrees to carry traffic from AR 1 to AR 3,
without concern as to the entry and exit AR, and for any hosts
these ARs
This notation works, but is very bulky, as a new term is required
every pair of universities. There are several ways to compact
notation. First, we can use the * and a new symbol, "-", to
the terms a bit. For example
AR2: ((*,1,*),(*,*,-),*,*)
would assert that AR 1 can use AR 2 to talk to any directly
AR, where we use the "-" to mean that the exit AR must be
destination AR. In other words, the destination AR must be
attached to AR2. If AR 2 only attaches to universities, then
would provide the proper constraint
Another approach is to use the User Class ID
AR2:((*,*,*),(*,*,*),University,*)
says that any traffic of any sort that has the User Class
University is acceptable
Another, and perhaps most suitable notation, is to observe that
distinction between source and destination is actually artificial
While it helps in this memo to have names for the two ends,
end can be a source, depending on who sends the first packet. (
later section explores the bi-directional nature of PRs). A
general form of a PR is thus to permit any number of elements.
is, a Policy Term can have more than two elements, and the meaning
this is that a PR is valid if it uses any two of these
For example, if university 5 wanted to use the AR2 service, AR2
write a Policy term as follows
AR2:((*,1,*),(*,3,*),(*,5,*),*,*)
which would permit a policy route between hosts in any two of the
1, 3 and 5.
All the terms so far relate to the policies of AR2. If university 1
wanted to subscribe to this service, and use it to reach any
site, it would specify terms of its own. For example
Clark [Page 8]
RFC 1102 Policy Routing in Internet Protocols May 1989
AR1: ((*,1, -),(*,*,2),*,*).
This term says that any host in AR 1 can use AR 2 as a path to
host in any AR. Again we use the "-" notation to indicate that
entry AR is the same as the source AR, in this case the AR
the term
The ARs numbered 3 and 5 are more interesting. While 3 is
attached to 2, 5 is not. Instead, 5 has attached to 3. If 3
to use 2 for general transit service, it must provide a term
to the one provided by 1:
AR3: ((*,3,-),(*,*,2),*,*).
If 5 wants to use 2, more terms are required. Since 2 is
directly attached, it cannot be named as the exit AR in a
written by 5. The directly attached AR, 3, is all that can be named
AR5: ((*,5,-),(*,*,3),*,*).
Then AR3 must agree to carry the transit traffic for 5.
AR3: ((*,5,-),(*,*,2),*,*)
AR3 might not want to carry all forms of transit traffic for 5,
only of certain sorts or to certain locations. This could
expressed by restricting the previous term. For example
AR3: ((*,5,-),(*,2,-),*,*)
would permit traffic from 5 to cross 3 to reach 2, but only to
directly in those ARs
For some further examples, consider AR 4, which might represent
AR of a commercial user. It connects together the hosts of
user, for example, H3, and is connected to the other environment
permit cross-communication. Given the terms so far, no traffic
flow into this AR
If AR 1 wants to permit communication with AR 4, it could add
AR1: ((*,1,-),(*,4,-),*,*)
This would permit communication between hosts directly in each AR
but no transit traffic. In particular, H3 and H2 cannot talk.
are several different terms that would permit them to talk
Clark [Page 9]
RFC 1102 Policy Routing in Internet Protocols May 1989
The direct path would be the following
AR4: ((*,4,-),(H2,3,-),*,*)
AR3: ((*,3,-),(H3,4,-),*,*).
This would permit direct connection through G4. Note, for variety
that each term has been set up so that any host in the local AR
match, but only one host in the other AR. The combination happens
permit only H3 and H2 to communicate
If G4 were not there, another path would be via AR 2, which could
permitted by suitable terms in ARs 1,2,3 and 4.
Even if G3 and G4 exist, no transit traffic will flow across AR 4
from 1 to 3. Even if 1 and 3 want it to
AR1: ((*,1,-),(*,3,4),*,*)
AR3: ((*,3,-),(*,1,4),*,*),
the lack of a term for AR4 will prevent a valid PR via that path
Only if AR 4 added
AR4:((*,1,-),(*,3,-),*,*)
would AR 4 start serving AR a transit path from 1 to 3.
If AR4 added
AR4: ((*,4,-),(*,*,*),*,*), any host in AR 4 could talk to any
anywhere else, but AR 4 would still not become a transit service
These various examples demonstrate how individual ARs can
Policy Terms that can be combined to form a route. The
proposed here is probably not adequate to express the needed range
policies. For example, it may be desirable to have lists of ARs
part of a term, as well as single values and "*". Other
might be proposed to permit exclusion of a limited set of ARs.
may also be appropriate to write elements that are directional,
that connections can be "opened" in one direction but not in others
This idea is vague in a connectionless architecture, but seems
relate to some real policy requirements
In general, the problem of expressing policy terms in compact form
the same as the problem of constructing compact access control lists
There is still an ongoing argument whether access control
should be ordered, and should permit exclusion, and so on. It
seem that the exact same issues arise here. Some
attempting to express real policies may give guidance as to
Clark [Page 10]
RFC 1102 Policy Routing in Internet Protocols May 1989
expressive power needed
6. Cost
Almost all of the existing Internet has been paid for as a
purchase and provided to the users as a free good. There are
examples of cost recovery, but these are based on an
subscription fee rather than a charge related to the utilization
There is a growing body of opinion which says that accounting
usage, if not billing for it, is an important component of
resource management. For this reason, tools for accounting
billing must be a central part of any policy mechanism. However
precisely because the administrative regions are autonomous,
cannot impose a uniform form of billing policy on all of the regions
Some of them may continue to provide service freely, or on the
of an annual fee. Others may charge on the basis of
consumed, but even here there may be variations in detail, as
may charge by the packet and others may charge by the byte. Again
in the telephone analogy, we see a variety of billing policies,
both local and long distance carriers selling service either on
basis of a monthly fee or on a fee-per-minute of usage, with time
day conditions attached. The billing problem is thus a
complicated one, for the user would presumably desire to minimize
cost, in the context of the various outstanding conditions
If we are actually to pay for use of services, there is also
problem of collection. Using the current telephone system as
example, there are two strategies for collecting revenues. One
the pre-divestiture mode, in which the source AR (or the
AR in the case of a collect call) serves as a single collection
for all of the ARs involved in the call. After divestiture, we
another paradigm, in which the transit AR separately bills
customer
There are many reasons to support both collection formats.
primary reason for separate billing is that not all regions may
to charge the user in the same units of currency. Some regions
wish to charge actual dollars, while others may wish to charge
some form of private allocation units. On the other hand, having
single point of collection is very convenient, because it
a lot of duplicate effort in collection. It does, however, require
greater degree of trust and coordination among ARs
Single point collection also simplifies another sticky problem,
packets. For most types of service, the user would presumably
offended if asked to pay for a significant number of
undelivered because they have been lost before reaching
destination. If each region separately bills for its traffic,
Clark [Page 11]
RFC 1102 Policy Routing in Internet Protocols May 1989
to avoid billing for packets that are lost between that AR and
destination, it is necessary to have some form of lost
reporting, which travels backward through system decrementing
counters of all the intervening ARs. If single point collection
performed, then the usage meters can be put in the destination AR
and periodically propagated to the billing AR, if that is a
region
The discussion of lost packets makes clear an important
between billing and policy. If a Policy Route takes packets
a region of known unreliability, the regions preceding it on the
may be quite unwilling to forgive the charges for packets which
successfully crossed their region, only to be lost further down
route. A billing policy is a way of asserting that one region
to divorce itself from the reliability behavior of another region
The conditions in the policy terms, and corresponding policy routes
must therefore be able to capture two distinct conditions. The
is whether or not there exists a bilateral agreement between two
by which one agrees to be the collection agent for the other.
concatenation of a number of these agreements permits a
collection point to be used for the entire policy route. The
condition is whether or not the AR will accept packet and byte
from the next AR downstream as the basis of billing, or whether
AR insists that the billing be based on the counts at the exit
of this AR. This condition allows an AR to build a wall between
and a subsequent unreliable AR. One can imagine certain
agreeing to carry traffic into unreliable regions, but
grudgingly, knowing that the result is going to be user
which may be directed to all the ARs indiscriminately. The use of
specific policy condition can make clear to the end user which ARs
not view themselves as interworking harmoniously
To enforce these mechanisms, the abstract PR which is included in
packet must be augmented with a number of conditions. First,
each AR there is a 3-way flag which describes whether the
should be separately collected for the region, propagated back to
source (which corresponds to the normal telephone company paradigm),
or propagated towards the destination (which corresponds to a
call). Second, there is a flag which indicates whether the region
expected to accept from the next region downstream the packet
byte counts as the basis of billing. Third, there must be a
code, a unique number somewhat resembling a credit card number
which bills may be sent. The Policy Terms in the Gateways
similarly be augmented to permit verification. The management of
charge code, insuring its uniqueness and preventing its abuse,
discussed later
These conditions, which relate to agreements between two ARs,
Clark [Page 12]
RFC 1102 Policy Routing in Internet Protocols May 1989
somewhat different from the conditions previously discussed, such
time of day. Conditions relating to AR agreements will be
"bilateral conditions," while the others are called "
conditions." Note that even though bilateral conditions relate
the agreement between two ARs, they can have global effects
7. Gateway
In Section Two, this memo proposed that the end point should
an abstract Policy Route, as a series of ARs, and the Policy
at the entry to each AR should convert the next hop to a
route, selecting the Policy Gateway to exit from this region into
next. It turns out that this selection is not entirely devoid
policy concerns, and some additional conditions are required in
Policy Terms in order to make this operate properly
In order that each Policy Gateway be able to select the next
Gateway on the route, it is necessary to have a table which lists
of the potential Policy Gateways that connect together
regions. Presumably, this information is very slowly changing,
is not difficult to propagate. The more dynamic information that
needed is whether each of these gateways is up. It is
necessary that all of the Policy Gateways attached to a given AR
run a local up-down algorithm, one which hopefully can determine
only that each of the other gateways is up, but that its
are up and that it is properly forwarding traffic. It is
complicated to design such a test. However, we do not have to
a strategy for propagating this information globally, because it
only needed by the other Policy Gateways attached to each region
The policy matter related to concrete routes arises if there
several gateways connecting two administrative regions. As
so far, the exit Policy Gateway from any region (which is the
Policy Gateway for the next region) is selected by the entry
Gateway for that region. In other words, each region may select
exit gateway, but has no control over its entry gateway. There
certain circumstances where a particular region might insist on
able to control the entry gateway used. Imagine two parallel
regions, one which charges incrementally for service, the other
which provides its service as a free good. Obviously, from the
of view of the user, it is desirable to minimize the use of
charging AR, and maximize the use of the free AR. But this may
to gross overloads in the free AR, and apparent
against the charging AR. The owner of the free AR, therefore,
choose to impose a policy which says that it can be used only
reach certain points which are not directly connected to the AR
bills for its service, and the traffic must enter the free AR at
closest point to the destination. In other words, the free
Clark [Page 13]
RFC 1102 Policy Routing in Internet Protocols May 1989
requires that it be allowed to choose its entry gateway so that
minimizes its costs (which are not, in fact, being billed), with
intent of shifting as much as possible of the cost onto the
network
By adding more bilateral conditions to the Policy Terms and
Policy Route in the packet, it is possible to control the
options for Policy Gateway selection. At each boundary between ARs
there are only a limited number of ways to select the Policy Gateway
Either it is selected by the entry side, by the exit side, or by
collaborative algorithm specified through a bilateral agreement
(There might be several such algorithms, which requires
possibility of more complexity in the specification. In particular
if two adjacent ARs have agreed to use a common routing metric
some type of service, they may agree to make a common routing
on this metric.)
Allowing the policy gateway to be selected by the AR which is on
far side of the gateway represents an interesting
problem. It would be possible to send some message in advance of
packet, which requests the next AR to select its entry gateway.
do this, it would figure out what its exit gateway would be, and
figure backwards to minimize its costs (for example) to select
potential entry gateway back into the immediate region. This
complicated to describe, and would probably be complicated
implement. One way to focus the problem is to observe that
are bi-directional, because a packet flow is bi-directional, and
is very desirable that the packets from both directions follow
same route. Once a packet has come back along the reverse route,
gateway from which it emerges is precisely the gateway which
be used for future traffic in the other direction. But each gateway
in either the forward or reverse direction, must remember a
made by another AR
For this to work it is necessary that gateways not be stateless.
each Policy Gateway maintains a cache of recently computed
Routes, in particular remembering the result of computing the
for each abstract route, then by simply determining whether or
the forward direction or the reverse direction is allowed
constrain the gateway across this boundary, both policies can
enforced. But this requires building gateways with state, which
not been culturally acceptable in the Internet. I therefore
as a separate topic the virtues of state in Policy Gateways.
believe that fairly simple algorithms exist to set up the
bindings in the Policy Gateways, but that problem is a matter
later study
Clark [Page 14]
RFC 1102 Policy Routing in Internet Protocols May 1989
8. Flow
The previous section suggested that the gateway needed to
state in order to tie together the forward and reverse halves of
flow. This solved the particular problem of tying together
routing decision which had been made in each direction, so that
could be used in the other. There are, in fact, a number of
why the two halves of the flow should be tied together
- There is considerable overhead in accounting and collecting for
usage. It is clearly desirable to have both halves of the
metered jointly
- If the route is not bi-directional, then a failure in the
produces a uni-directional link. Uni-directional links are
to cause anomalous behavior in protocols
- As part of resource management, it may be desirable
intermediate nodes to pass flow control information back to
source of the flow. If identifiable reverse-direction
are passing through the gateway, then this information can
piggy-backed onto those packets
An additional advantage of maintaining state in the gateway is
it will greatly reduce the overhead of dealing with incoming packets
There are a number of decisions which the Policy Gateway must
which are a part of forwarding a packet: it must validate the
Route against its terms, it must create or modify an
record, and it must select the next Policy Gateway. It
unreasonable to imagine performing these tasks from scratch for
incoming packet. Once these decisions have been made, the
should be cached, so that they can be used for subsequent packets
The stateless gateway was proposed as part of the Internet design
order to insure a robust architecture. If the gateway has no state
then a crash of a gateway cannot endanger an on-going connection.
there is state in a gateway, and that state information is
because of a crash, then it is possible that a flow would
disrupted
In moving from a gateway with no state to a gateway which
information, it is necessary to ensure that the cached
can be lost and reconstructed. The idea of keeping in gateways
that state which can be easily reconstructed I call "soft state."
Clark [Page 15]
RFC 1102 Policy Routing in Internet Protocols May 1989
9. Synthesis and Selection of Policy
In this proposal, a packet contains a Policy Route, which is
by each Policy Gateway along the way. This section discusses how
Policy Route is created in the first place
PR creation cannot be done totally automatically by the system,
will in general require human judgment. Policies, after all,
matters of human concern. The approach to PR creation is thus
joint one, in which the system provides support to the
setting policy
Most commonly, the desired PR will be selected from among
available by first finding all valid PRs, and then picking one
meets the requirements of the user and has the lowest real cost
These two stages will be called synthesis and selection
To synthesize a PR across a sequence of ARs, one must find a
Term in each AR that would permit such a PR. The Policy Terms
each adjacent AR must be compatible in their billing conditions
other particulars. One can imagine finding a sequence of
Terms that match, rather like dominoes, and reach from the source
the destination
For a Policy Term at some AR to be acceptable as a part of a PR,
following must be true
- The Source and Destination Host address and UCI must match
term
- The Source and Destination AR must match the term
- The Entry and Exit AR must match the adjacent AR in the route
- The conditions in the term relating to the adjacent AR (e.g.,
billing) must match the conditions in the term from that region
These conditions, of course, are exactly what the Policy
would test in validating the PR when it is used
As the route is synthesized from matching terms, the
conditions of each term are noted, and the combination of
become the condition under which the PR is valid. As a
point of the synthesis the user may have indicated constraints on
acceptable conditions in order to limit the candidate terms in
synthesis
The result of PR synthesis, which is somewhat similar to
Clark [Page 16]
RFC 1102 Policy Routing in Internet Protocols May 1989
computation in a link-state routing algorithm where each Policy
represents an abstract link, is a potentially long list of
PRs to each destination AR, each with attached conditions.
selection process must identify one of these which is actually to
used. The selection can be based on the conditions, and on the
of each PR
To determine the cost, it must be possible to ask each AR to
the cost of using that Policy Term in the context of this
set of Entry and Exit ARs. Either there must be an
protocol for reporting these costs, or the task of cost
must be left to humans to perform outside the system. The
with architected cost reporting is that while some ARs may bill
real dollars, others may bill in terms of abstract
authorizations which have no meaning outside that AR. Even so,
believe that we should attempt to define a representation
reporting the billing basis associated with each AR. This is
matter for later study
While PR synthesis may be an automated process, selection probably
not. While cost minimization will help prune the list, and
routes may be rejected automatically on the basis of conditions,
of the selection will in general require human judgment.
observation, together with the observation that PR synthesis may
costly, suggests first that synthesis and selection cannot be
for each packet or indeed each time a transport connection
established, and second that it should not be done separately
each host in the AR
Instead, each AR should have one (or more) Policy Servers,
inside the AR which support the management of PRs. The Policy
would perform a number of functions
- It would store the Policy Terms for the AR, and make them
to the Policy Gateways and the Servers of other ARs as appropriate
- It would synthesize potential PRs to reach other ARs, and
which of these have been selected for use
- It will respond to requests from hosts in the AR for PRs,
return them so that they can be included in outgoing packets
- It will participate on behalf of the AR in AR up-down protocols
and other inter-AR routing algorithms
- It will remember the location of all Policy Gateways attached
this AR
Clark [Page 17]
RFC 1102 Policy Routing in Internet Protocols May 1989
- It will provide the management interface for those persons who
establish AR policy: setting of local Policy Terms, selection
Policy Routes, and so on
A host wishing to send packets outside the local AR must first
a PR to put into the packets. In the normal case, it would do so
directing a request to the local Policy Server, supplying the
destination and other negotiable conditions. (For example, the
is negotiable, the current time is not.) The Server, based on
input, must select the most appropriate PR and return it
At this point in the process, human intervention is not reasonable
as it would take much too long. By now, sufficient selection
have been done so that automated PR selection is possible. The
direct implementation is that the manual selection process
yield an ordered (or partially ordered) list of potential PRs,
the list is searched in order until a PR is found that matches
destination and conditions. That PR is then returned
10.
There are a number of aspects of this scheme which
opportunities for abuse. In essentially all cases, the
abuse is theft of network resources or improper charging. They
have a somewhat different nature than problems related to
or disclosure of data. Mechanism to insure proper use and
of resources often tolerate minor abuse in exchange for ease
operation. Also, control is often based on detection and
rather than prevention. Assumptions of this sort are
acceptable here as well. An isolated packet, which is not a part
any sequence of packets, may be too small an item to account for
control. But if a significant stream of packets goes unaccounted
this is less acceptable
There are three general options for abuse. One is to falsify
user identification information in the PR, the source and
host, the User Class Id and the charge code. Another is to take
valid PR and misuse it intact. And the third is to read out a
charge code from a PR and then make additional charges against it
To protect against putting false user identification information
a PR, the PRs should be sealed or signed, using a crypto
technique. Since Policy Servers are the source of PRs, the
can be done by the Server. This would require that the seal
digital signature of each Server be known, but avoids the need
have each host known. The Server would be trusted to seal only
PRs. It must only put User Class Ids and charge codes into PRs
a source permitted to use them, for example
Clark [Page 18]
RFC 1102 Policy Routing in Internet Protocols May 1989
Assuming a public key system, each Policy Server could have
separate key pair, the public half of which was advertised in
way. It is a matter for further study exactly what parts of the
need be sealed
If the Policy Server violates this trust, and uses a UCI or
code with an unauthorized host, there are two sub-cases: the
source host is in the same AS, or is outside it. If it is outside
this can be detected by inspection of the PR, since the
between AR and network number is (almost) static. One approach is
make an AR identifier part of the charge code, so that use of
code can be rejected unless that AR is the source AR for the packet
This works, but prevents using charge codes from a foreign location
Other more general techniques could probably be proposed
If the false source host is inside the AR, then further steps
required to prevent the problem. One general solution is to
that a PR is valid only if sealed by a Policy Server. Any
attempting to collect for usage should be required to keep a copy
the PR as proof that the route was used. If there seems to
unauthorized use of a charge code, the owner can ask to see the
which generated the charge, which will show the Policy Server
constructed the route. If this is an unauthorized use, action can
taken against the AR owning that Server, with the sealed PR
evidence. In other words, detection and redress may be more
than prevention
If we can assume that the Policy Server for a particular region is
trustworthy as that AR requires, there is still the problem of
Server of one region trying to steal from another AR. This could
done, for example, by taking a valid PR, and sending data
along it from the "middle" of the route, so that what appears to
coming from one source is actually coming from another in a
AR
This would require that packets coming back along the route
the original source be rerouted to the false source, which
require that the whole routing function within the AR be corrupted
It is unlikely that this would go long undetected, but if
control of this class of fraud is needed, it could be achieved
requiring any AR intending to charge against a particular PR
obtain from time to time a confirmation, sealed by the Server of
source AR, that its policy gateway has in fact forwarded some
of packets using this PR. This sort of function is probably overkill
but this class of fraud needs to be considered
Obviously, a more detailed study will be required of the problem
resource theft, but I believe that a mechanism can be made to
Clark [Page 19]
RFC 1102 Policy Routing in Internet Protocols May 1989
based on
- Local trust of the Policy Server within each AR
- Sealing of the PR by the Server
- Selective validation of the seal at the Policy Gateway
- Selective consistency checking of the PR at the Policy Gateway
- Use of seal on PR as evidence of the source of the PR
11. An Experimental Program -- Migration to Policy
The proposal above calls for several Internet components not
today: the Policy Route IP option, Policy Gateways, Policy Servers
and support protocols such as the global AS up-down protocol and
local (to the AS) Policy Gateway up-down protocol. Any plan
introduction of policy routing must provide a method to
with the concept without changing all the hosts and the gateways
in place
Since the Policy Server is a new component which can be added to
Internet without changing any existing components, it is easy to
that facility in place. This, then, becomes the central part of
experimental plan. Later, it is possible to imagine adding the
controls to some of the gateways. Most difficult will be
all the hosts to use the PR IP option. Based on our experience
adding minor features such as IP subnetworks, it will never
possible to get the PR option into all the hosts, and policy
must be made to work anyway
Taking into account these difficulties, here is a
experimental plan, in three phases
In Phase I, software for a Policy Server is created, and
available to all potential ARs. As a part of its function, it
two "temporary" feature, to mimic the function of the missing
and gateway support
To mimic the function of the policy gateway, two policy Servers
placed "near" a current function gateway which happens to connect
two ARs, one on each side of the current gateway, and
their respective ARs. These two Servers then proceed to fool
current gateway as follows
- The current gateway is given the two Servers as neighbors in
routing exchanges. In this way, the Servers can control
Clark [Page 20]
RFC 1102 Policy Routing in Internet Protocols May 1989
network numbers are advertised. This is similar to the way "gated
is used today to control routes
- A packet entering the AR is directed to the "near" Server
the AR, which performs the functions of the Policy Gateway
then resends the packet. This may require the use of a
source route in some cases, but can probably just be done
rewriting the destination IP address in the packet. (Note
the IP PR option proposed in the Appendix has fields for
original IP source and destination, so that these fields can
reused in forwarding the packet from gateway to gateway.)
To deal with the lack of host support for the PR option, we
make use of the Server. Since the Server is the recipient of
routing information coming into the AR (since it has been set up
the neighbor of the current gateway at the actual AR boundary)
alone knows the proper routes out. Internally, it advertises
as the default gateway to all networks outside the AR, so that
receives all the packets intending to leave the region. It,
than the host, adds the PR option and then sends the packet on
Policy Gateway (or the matching Server in the next AR playing
part) for relaying
By controlling how routes are propagated by the regular gateways,
is possible to prevent hosts from manually setting up routes
bypass the Servers. In any event, enforcement is not the
concern in Phase I of the experiment
In Phase II, certain of the current gateways are augmented with
Policy Gateway functions. This will make enforcement easier,
eliminate the extra hop which the packet had make in Phase I, as
passed from one Server to another through the current gateway.
the same time, some of the hosts are modified to insert the IP
option into the packet at the source. This will explore the
of PR selection
In Phase III, the PR design is proposed for general implementation
12. Policy Route
One objection to this scheme is the large size of the IP PR option
With all the information proposed in this memo, it is larger than
IP header itself. However, this problem can easily be avoided;
PR option seldom need be sent
Since the Policy Gateways are going to cache the result of
the PR, the cache holds the equivalent of the PR. All that
required is a very short option in the packet which is a handle
Clark [Page 21]
RFC 1102 Policy Routing in Internet Protocols May 1989
permits the gateway to find the correct cache entry. This
would be included in the original IP PR option, and then repeated
every packet. The Policy Server which generated the PR could
the handle, so it would be unique for each AR. Perhaps the AR id
a 16 bit UID would be sufficient
The full PR option needs to be in the packet only if the
Information in the gateway is lost. If a gateway crashes or
route changes, the end point must reconstruct the caches in
series of gateways that form the route. The end point
determine that this was necessary either when a gateway
explicitly that it does not have an entry corresponding to a handle
or when the host determines that it is not getting the
service
This sort of action can be thought of as an extension to the idea
retransmitting. In transport protocols such as TCP, the host
track of the behavior of the network, and if it believes
something is wrong (e.g., there is a lack of an acknowledgment),
takes action to restore the desired service. Other examples
switching to another gateway if the currently active adjacent
seems to be down. Sending the full PR option in the packet is
another example of allowing the end node to restore the state of
connection if it seems to be broken
Using this model, most packets would have only a short
(perhaps 12 bytes).
This idea of restoring the state in the gateway as needed
the idea of "soft state" mentioned earlier, and allows gateways
state to achieve the same robustness associated with
networks
Author's
David D.
Massachusetts Institute of
Laboratory for Computer
545 Main
Cambridge, MA 02139
Phone: (617) 253-6003
Email: ddc@LCS.MIT.
Clark [Page 22]
if you see any problems within the linking, don't worry be happy,
this is version 0.1 of the Relevance System and you gotta expect some crappy subroutines sometimes,
just be content we did not write this in Java, which would have made this "bigger and better" HAHAHHA.
RFC documents can be found at I.E.T.F.
Relevance System Copyright © 2002 Spectrum WorldResearch
other technical nosh by ServerMasters Corporation
collaboration of BobX
