Request for Comments: 1479 BBN Systems and Technologies
July 1993
Inter-Domain Policy Routing Protocol Specification: Version 1
Status of this Memo
This RFCspecifies an IAB standards track protocol for the Internet
community, and requests discussion and suggestions for improvements.
Please refer to the current edition of the "IAB Official Protocol
Standards" for the standardization state and status of this protocol.
Distribution of this memo is unlimited.
Abstract
We present the set of protocols and procedures that constitute
Inter-Domain Policy Routing (IDPR). IDPR includes the virtual
gateway protocol, the flooding protocol, the route server query
protocol, the route generation procedure, the path control protocol,
and the data message forwarding procedure.
Contributors
The following people have contributed to the protocols and procedures
described in this document: Helen Bowns, Lee Breslau, Ken Carlberg,
Isidro Castineyra, Deborah Estrin, Tony Li, Mike Little, Katia
Obraczka, Sam Resheff, Martha Steenstrup, Gene Tsudik, and Robert
Woodburn.
Table of Contents
1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. Domain Elements . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. Policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . 6
1.4. Policy Semantics. . . . . . . . . . . . . . . . . . . . . . . 7
1.4.1. Source Policies . . . . . . . . . . . . . . . . . . . . . . 7
1.4.2. Transit Policies. . . . . . . . . . . . . . . . . . . . . . 8
1.5. IDPR Message Encapsulation. . . . . . . . . . . . . . . . . . 9
1.5.1. IDPR Data Message Format. . . . . . . . . . . . . . . . . .11
1.6. Security. . . . . . . . . . . . . . . . . . . . . . . . . . .12
1.7. Timestamps and Clock Synchronization. . . . . . . . . . . . .13
1.8. Network Management. . . . . . . . . . . . . . . . . . . . . .14
1.8.1. Policy Gateway Configuration. . . . . . . . . . . . . . . .17
1.8.2. Route Server Configuration. . . . . . . . . . . . . . . . .18
2. Control Message Transport Protocol. . . . . . . . . . . . . . .18
2.1. Message Transmission. . . . . . . . . . . . . . . . . . . . .20
2.2. Message Reception . . . . . . . . . . . . . . . . . . . . . .22
2.3. Message Validation. . . . . . . . . . . . . . . . . . . . . .23
2.4. CMTP Message Formats. . . . . . . . . . . . . . . . . . . . .24
3. Virtual Gateway Protocol. . . . . . . . . . . . . . . . . . . .27
3.1. Message Scope . . . . . . . . . . . . . . . . . . . . . . . .28
3.1.1. Pair-PG Messages. . . . . . . . . . . . . . . . . . . . . .28
3.1.2. Intra-VG Messages . . . . . . . . . . . . . . . . . . . . .29
3.1.3. Inter-VG Messages . . . . . . . . . . . . . . . . . . . . .29
3.1.4. VG Representatives. . . . . . . . . . . . . . . . . . . . .31
3.2. Up/Down Protocol. . . . . . . . . . . . . . . . . . . . . . .31
3.3. Implementation. . . . . . . . . . . . . . . . . . . . . . . .33
3.4. Policy Gateway Connectivity . . . . . . . . . . . . . . . . .35
3.4.1. Within a Virtual Gateway. . . . . . . . . . . . . . . . . .35
3.4.2. Between Virtual Gateways. . . . . . . . . . . . . . . . . .37
3.4.3. Communication Complexity. . . . . . . . . . . . . . . . . .40
3.5. VGP Message Formats . . . . . . . . . . . . . . . . . . . . .41
3.5.1. UP/DOWN . . . . . . . . . . . . . . . . . . . . . . . . . .41
3.5.2. PG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .42
3.5.3. PG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .43
3.5.4. VG CONNECT. . . . . . . . . . . . . . . . . . . . . . . . .44
3.5.5. VG POLICY . . . . . . . . . . . . . . . . . . . . . . . . .45
3.5.6. Negative Acknowledgements . . . . . . . . . . . . . . . . .46
4. Routing Information Distribution. . . . . . . . . . . . . . . .47
4.1. AD Representatives. . . . . . . . . . . . . . . . . . . . . .48
4.2. Flooding Protocol . . . . . . . . . . . . . . . . . . . . . .48
4.2.1. Message Generation. . . . . . . . . . . . . . . . . . . . .50
4.2.2. Sequence Numbers. . . . . . . . . . . . . . . . . . . . . .52
4.2.3. Message Acceptance. . . . . . . . . . . . . . . . . . . . .52
4.2.4. Message Incorporation . . . . . . . . . . . . . . . . . . .54
4.2.5. Routing Information Database. . . . . . . . . . . . . . . .56
4.3. Routing Information Message Formats . . . . . . . . . . . . .57
4.3.1. CONFIGURATION . . . . . . . . . . . . . . . . . . . . . . .57
4.3.2. DYNAMIC . . . . . . . . . . . . . . . . . . . . . . . . . .62
4.3.3. Negative Acknowledgements . . . . . . . . . . . . . . . . .63
5. Route Server Query Protocol . . . . . . . . . . . . . . . . . .64
5.1. Message Exchange. . . . . . . . . . . . . . . . . . . . . . .64
5.2. Remote Route Server Communication . . . . . . . . . . . . . .65
5.3. Routing Information . . . . . . . . . . . . . . . . . . . . .66
5.4. Routes. . . . . . . . . . . . . . . . . . . . . . . . . . . .67
5.5. Route Server Message Formats. . . . . . . . . . . . . . . . .67
5.5.1. ROUTING INFORMATION REQUEST . . . . . . . . . . . . . . . .67
5.5.2. ROUTE REQUEST . . . . . . . . . . . . . . . . . . . . . . .68
5.5.3. ROUTE RESPONSE. . . . . . . . . . . . . . . . . . . . . . .71
5.5.4. Negative Acknowledgements . . . . . . . . . . . . . . . . .72
6. Route Generation. . . . . . . . . . . . . . . . . . . . . . . .73
6.1. Searching . . . . . . . . . . . . . . . . . . . . . . . . . .74
6.1.1. Implementation. . . . . . . . . . . . . . . . . . . . . . .75
6.2. Route Directionality. . . . . . . . . . . . . . . . . . . . .78
6.3. Route Database. . . . . . . . . . . . . . . . . . . . . . . .79
6.3.1. Cache Maintenance . . . . . . . . . . . . . . . . . . . . .80
7. Path Control Protocol and Data Message Forwarding Procedure . .80
7.1. An Example of Path Setup. . . . . . . . . . . . . . . . . . .81
7.2. Path Identifiers. . . . . . . . . . . . . . . . . . . . . . .84
7.3. Path Control Messages . . . . . . . . . . . . . . . . . . . .85
7.4. Setting Up and Tearing Down a Path. . . . . . . . . . . . . .87
7.4.1. Validating Path Identifiers . . . . . . . . . . . . . . . .89
7.4.2. Path Consistency with Configured Transit Policies . . . . .89
7.4.3. Path Consistency with Virtual Gateway Reachability. . . . .91
7.4.4. Obtaining Resources . . . . . . . . . . . . . . . . . . . .92
7.4.5. Target Response . . . . . . . . . . . . . . . . . . . . . .93
7.4.6. Originator Response . . . . . . . . . . . . . . . . . . . .93
7.4.7. Path Life . . . . . . . . . . . . . . . . . . . . . . . . 94
7.5. Path Failure and Recovery . . . . . . . . . . . . . . . . . 95
7.5.1. Handling Implicit Path Failures . . . . . . . . . . . . . 96
7.5.2. Local Path Repair . . . . . . . . . . . . . . . . . . . . 97
7.5.3. Repairing a Path. . . . . . . . . . . . . . . . . . . . . 98
7.6. Path Control Message Formats. . . . . . . . . . . . . . . . 100
7.6.1. SETUP . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.6.2. ACCEPT. . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.6.3. REFUSE. . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.6.4. TEARDOWN. . . . . . . . . . . . . . . . . . . . . . . . . 104
7.6.5. ERROR . . . . . . . . . . . . . . . . . . . . . . . . . . 105
7.6.6. REPAIR. . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.6.7. Negative Acknowledgements . . . . . . . . . . . . . . . . 106
8. Security Considerations . . . . . . . . . . . . . . . . . . . 106
9. Authors's Address . . . . . . . . . . . . . . . . . . . . . . 107
References . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
1. Introduction
In this document, we specify the protocols and procedures that
compose Inter-Domain Policy Routing (IDPR). The objective of IDPR is
to construct and maintain routes between source and destination
administrative domains, that provide user traffic with the services
requested within the constraints stipulated for the domains
transited. IDPR supports link state routing information distribution
and route generation in conjunction with source specified message
forwarding. Refer to [5] for a detailed justification of our
approach to inter-domain policy routing.
1.1. Domain Elements
The IDPR architecture has been designed to accommodate an
internetwork with tens of thousands of administrative domains
collectively containing hundreds of thousands of local networks.
Inter-domain policy routes are constructed using information about
the services offered by, and the connectivity between, administrative
domains. The intra-domain details - gateways, networks, and links
traversed - of an inter-domain policy route are the responsibility of
intra-domain routing and are thus outside the scope of IDPR.
An "administrative domain" (AD) is a collection of contiguous hosts,
gateways, networks, and links managed by a single administrative
authority. The domain administrator defines service restrictions for
transit traffic and service requirements for locally-generated
traffic, and selects the addressing schemes and routing procedures
that apply within the domain. Within the Internet, each domain has a
unique numeric identifier assigned by the Internet Assigned Numbers
Authority (IANA).
"Virtual gateways" (VGs) are the only IDPR-recognized connecting
points between adjacent domains. Each virtual gateway is a
collection of directly-connected "policy gateways" (see below) in two
adjoining domains, whose existence has been sanctioned by the
administrators of both domains. The domain administrators may agree
to establish more than one virtual gateway between the two domains.
For each such virtual gateway, the two administrators together assign
a local numeric identifier, unique within the set of virtual gateways
connecting the two domains. To produce a virtual gateway identifier
unique within its domain, a domain administrator concatenates the
mutually assigned local virtual gateway identifier together with the
adjacent domain's identifier.
Policy gateways (PGs) are the physical gateways within a virtual
gateway. Each policy gateway enforces service restrictions on IDPR
transit traffic, as stipulated by the domain administrator, and
forwards the traffic accordingly. Within a domain, two policy
gateways are "neighbors" if they are in different virtual gateways.
A single policy gateway may belong to multiple virtual gateways.
Within a virtual gateway, two policy gateways are "peers" if they are
in the same domain and are "adjacent" if they are in different
domains. Adjacent policy gateways are "directly connected" if the
only Internet-addressable entities attached to the connecting medium
are policy gateways in the virtual gateways. Note that this
definition implies that not only point-to-point links but also
networks may serve as direct connections between adjacent policy
gateways. The domain administrator assigns to each of its policy
gateways a numeric identifier, unique within that domain.
A "domain component" is a subset of a domain's entities such that all
entities within the subset are mutually reachable via intra-domain
routes, but no entities outside the subset are reachable via intra-
domain routes from entities within the subset. Normally, a domain
consists of a single component, namely itself; however, when
partitioned, a domain consists of multiple components. Each domain
component has an identifier, unique within the Internet, composed of
the domain identifier together with the identifier of the lowest-
numbered operational policy gateway within the component. All
operational policy gateways within a domain component can discover
mutual reachability through intra-domain routing information. Hence,
all such policy gateways can consistently determine, without explicit
negotiation, which of them has the lowest number.
1.2. Policy
With IDPR, each domain administrator sets "transit policies" that
dictate how and by whom the resources in its domain should be used.
Transit policies are usually public, and they specify offered
services comprising:
- Access restrictions: e.g., applied to traffic to or from certain
domains or classes of users.
- Quality: e.g., delay, throughput, or error characteristics.
- Monetary cost: e.g., charge per byte, message, or unit time.
Each domain administrator also sets "source policies" for traffic
originating in its domain. Source policies are usually private, and
they specify requested services comprising:
- Access restrictions: e.g., domains to favor or avoid in routes.
- Quality: e.g., acceptable delay, throughput, and reliability.
- Monetary cost: e.g., acceptable session cost.
1.3. IDPR Functions
IDPR comprises the following functions:
- Collecting and distributing routing information including domain
transit policies and inter-domain connectivity.
- Generating and selecting policy routes based on the routing
information distributed and on the source policies configured or
requested.
- Setting up paths across the Internet using the policy routes
generated.
- Forwarding messages across and between domains along the
established paths.
- Maintaining databases of routing information, inter-domain policy
routes, forwarding information, and configuration information.
1.3.1. IDPR Entities
Several different entities are responsible for performing the IDPR
functions.
Policy gateways, the only IDPR-recognized connecting points between
adjacent domains, collect and distribute routing information,
participate in path setup, forward data messages along established
paths, and maintain forwarding information databases.
"Path agents", resident within policy gateways and within "route
servers" (see below), act on behalf of hosts to select policy routes,
to set up and manage paths, and to maintain forwarding information
databases. Any Internet host can reap the benefits of IDPR, as long
as there exists a path agent configured to act on its behalf and a
means by which the host's messages can reach the path agent.
Specifically, a path agent in one domain may be configured to act on
behalf of hosts in another domain. In this case, the path agent's
domain is an IDPR "proxy" for the hosts' domain.
Route servers maintain both the routing information database and the
route database, and they generate policy routes using the routing
information collected and the source policies requested by the path
agents. A route server may reside within a policy gateway, or it may
exist as an autonomous entity. Separating the route server functions
from the policy gateways frees the policy gateways from both the
memory intensive task of database (routing information and route)
maintenance and the computationally intensive task of route
generation. Route servers, like policy gateways, each have a unique
numeric identifier within their domain, assigned by the domain
administrator.
Given the size of the current Internet, each policy gateway can
perform the route server functions, in addition to its message
forwarding functions, with little or no degradation in message
forwarding performance. Aggregating the routing functions into
policy gateways simplifies implementation; one need only install IDPR
protocols in policy gateways. Moreover, it simplifies communication
between routing functions, as all functions reside within each policy
gateway. As the Internet grows, the memory and processing required
to perform the route server functions may become a burden for the
policy gateways. When this happens, each domain administrator should
separate the route server functions from the policy gateways in its
domain.
"Mapping servers" maintain the database of mappings that resolve
Internet names and addresses to domain identifiers. Each host is
contained within a domain and is associated with a proxy domain which
may be identical with the host's domain. The mapping server function
will be integrated into the existing DNS name service (see [6]) and
will provide mappings between a host and its local and proxy domains.
"Configuration servers" maintain the databases of configured
information that apply to IDPR entities within their domains.
Configuration information for a given domain includes transit
policies (i.e., service offerings and restrictions), source policies
(i.e., service requirements), and mappings between local IDPR
entities and their names and addresses. The configuration server
function will be integrated into a domain's existing network
management system (see [7]-[8]).
1.4. Policy Semantics
The source and transit policies supported by IDPR are intended to
accommodate a wide range of services available throughout the
Internet. We describe the semantics of these policies, concentrating
on the access restriction aspects. To express these policies in this
document, we have chosen to use a syntactic variant of Clark's policy
term notation [1]. However, we provide a more succinct syntax (see
[7]) for actually configuring source and transit policies.
1.4.1. Source Policies
Each source policy takes the form of a collection of sets as follows:
Applicable Sources and Destinations:
{((H(1,1),s(1,1)),...,(H(1,f1),s(1,f1))),...,((H(n,1),s(n,1)),...,
(H(n,fn),s(n,fn)))}: The set of groups of source/destination
traffic flows to which the source policy applies. Each traffic
flow group ((H(i,1),s(i,1)),...,(H(i,fi),s(i,fi))) contains a set
of source hosts and corresponding destination hosts. Here, H(i,j)
represents a host, and s(i,j), an element of {SOURCE,
DESTINATION}, represents an indicator of whether H(i,j) is to be
considered as a source or as a destination.
Domain Preferences: {(AD(1),x(1)),...,(AD(m),x(m))}: The set of
transit domains that the traffic flows should favor, avoid, or
exclude. Here, AD(i) represents a domain, and x(i), an element of
{FAVOR, AVOID, EXCLUDE}, represents an indicator of whether routes
including AD(i) are to be favored, avoided if possible, or
unconditionally excluded.
UCI: The source user class for the traffic flows listed.
RequestedServices: The set of requested services not related to
access restrictions, i.e., service quality and monetary cost.
When selecting a route for a traffic flow from a source host H(i,j)
to a destination host H(i,k), where 1 < or = i < or = n and 1 < or =
j, k < or = fi, the path agent (see section 1.3.1) must honor the
source policy such that:
- For each domain, AD(p), contained in the route, AD(p) is not equal
to any AD(k), such that 1 < or = k < or = m and x(k) = EXCLUDE.
- The route provides the services listed in the set Requested
Services.
1.4.2. Transit Policies
Each transit policy takes the form of a collection of sets as
follows:
Source/Destination Access Restrictions:
{((H(1,1),AD(1,1),s(1,1)),...,(H(1,f1),AD(1,f1),s(1,f1))),...,
((H(n,1),AD(n,1),s(n,1)),...,(H(n,fn),AD(n,fn),s(n,fn)))}: The set
of groups of source and destination hosts and domains to which the
transit policy applies. Each domain group
((H(i,1),AD(i,1),s(i,1)),...,(H(i,fi),AD(i,fi),s(i,fi))) contains
a set of source and destination hosts and domains such that this
transit domain will carry traffic from each source listed to each
destination listed. Here, H(i,j) represents a set of hosts,
AD(i,j) represents a domain containing H(i,j), and s(i,j), a
subset of {SOURCE, DESTINATION}, represents an indicator of
whether (H(i,j),AD(i,j)) is to be considered as a set of sources,
destinations, or both.
Temporal Access Restrictions: The set of time intervals during which
the transit policy applies.
User Class Access Restrictions: The set of user classes to which the
transit policy applies.
Offered Services: The set of offered services not related to access
restrictions, i.e., service quality and monetary cost.
Virtual Gateway Access Restrictions:
{((VG(1,1),e(1,1)),...,(VG(1,g1),e(1,g1))),...,((VG(m,1),e(m,1)),
gateways to which the transit policy applies. Each virtual
gateway group ((VG(i,1),e(i,1)),...,(VG(i,gi),e(i,gi))) contains a
set of domain entry and exit points such that each entry virtual
gateway can reach (barring an intra-domain routing failure) each
exit virtual gateway via an intra-domain route supporting the
transit policy. Here, VG(i,j) represents a virtual gateway, and
e(i,j), a subset of {ENTRY, EXIT}, represents an indicator of
whether VG(i,j) is to be considered as a domain entry point, exit
point, or both.
The domain advertising such a transit policy will carry traffic from
any host in the set H(i,j) in AD(i,j) to any host in the set H(i,k)
in AD(i,k), where 1 < or = i < or = n and 1 < or = j, k < or = fi,
provided that:
- SOURCE is an element of s(i,j).
- DESTINATION is an element of s(i,k).
- Traffic from H(i,j) enters the domain during one of the intervals
in the set Temporal Access Restrictions.
- Traffic from H(i,j) carries one of the user class identifiers in
the set User Class Access Restrictions.
- Traffic from H(i,j) enters via any VG(u,v) such that ENTRY is an
element of e(u,v), where 1 < or = u < or = m and 1 < or = v < or =
gu.
- Traffic to H(i,k) leaves via any VG(u,w) such that EXIT is an
element of e(u,w), where 1 < or = w < or = gu.
1.5. IDPR Message Encapsulation
There are two kinds of IDPR messages:
- "Data messages" containing user data generated by hosts.
- "Control messages" containing IDPR protocol-related control
information generated by policy gateways and route servers.
Within an internetwork, only policy gateways and route servers are
able to generate, recognize, and process IDPR messages. The
existence of IDPR is invisible to all other gateways and hosts,
including mapping servers and configuration servers. Mapping servers
and configuration servers perform necessary but ancillary functions
for IDPR, and thus they are not required to handle IDPR messages.
An IDPR entity places IDPR-specific information in each IDPR control
message it originates; this information is significant only to
recipient IDPR entities. Using "encapsulation" across each domain,
an IDPR message tunnels from source to destination across an
internetwork through domains that may employ disparate intra-domain
addressing schemes and routing procedures.
As an alternative to encapsulation, we had considered embedding IDPR
in IP, as a set of IP options. However, this approach has the
following disadvantages:
- Only domains that support IP would be able to participate in IDPR;
domains that do not support IP would be excluded.
- Each gateway, policy or other, in a participating domain would at
least have to recognize the IDPR option, even if it did not execute
the IDPR protocols. However, most commercial routers are not
optimized for IP options processing, and so IDPR message handling
might require significant processing at each gateway.
- For some IDPR protocols, in particular path control, the size
restrictions on IP options would preclude inclusion of all of the
necessary protocol-related information.
For these reasons, we decided against the IP option approach and in
favor of encapsulation.
An IDPR message travels from source to destination between
consecutive policy gateways. Each policy gateway encapsulates the
IDPR message with information, for example an IP header, that will
enable the message to reach the next policy gateway. Note that the
encapsulating header and the IDPR-specific information may increase
the message size beyond the MTU of the given domain. However,
message fragmentation and reassembly is the responsibility of the
protocol, for example IP, that encapsulates IDPR messages for
transport between successive policy gateways; it is not currently the
responsibility of IDPR itself.
A policy gateway, when forwarding an IDPR message to a peer or a
neighbor policy gateway, encapsulates the message in accordance with
the addressing scheme and routing procedure of the given domain and
indicates in the protocol field of the encapsulating header that the
message is indeed an IDPR message. Intermediate gateways between the
two policy gateways forward the IDPR message as they would any other
message, using the information in the encapsulating header. Only the
recipient policy gateway interprets the protocol field, strips off
the encapsulating header, and processes the IDPR message.
A policy gateway, when forwarding an IDPR message to a directly-
connected adjacent policy gateway, encapsulates the message in
accordance with the addressing scheme of the entities within the
virtual gateway and indicates in the protocol field of the
encapsulating header that the message is indeed an IDPR message. The
recipient policy gateway strips off the encapsulating header and
processes the IDPR message. We recommend that the recipient policy
gateway perform the following validation check of the encapsulating
header, prior to stripping it off. Specifically, the recipient
policy gateway should verify that the source address and the
destination address in the encapsulating header match the adjacent
policy gateway's address and its own address, respectively.
Moreover, the recipient policy gateway should verify that the message
arrived on the interface designated for the direct connection to the
adjacent policy gateway. These checks help to ensure that IDPR
traffic that crosses domain boundaries does so only over direct
connections between adjacent policy gateways.
Policy gateways forward IDPR data messages according to a forwarding
information database which maps "path identifiers", carried in the
data messages, into next policy gateways. Policy gateways forward
IDPR control messages according to next policy gateways selected by
the particular IDPR control protocols associated with the messages.
Distinguishing IDPR data messages and IDPR control messages at the
encapsulating protocol level, instead of at the IDPR protocol level,
eliminates an extra level of dispatching and hence makes IDPR message
forwarding more efficient. When encapsulated within IP messages,
IDPR data messages and IDPR control messages carry the IP protocol
numbers 35 and 38, respectively.
1.5.1. IDPR Data Message Format
The path agents at a source domain determine which data messages
generated by local hosts are to be handled by IDPR. To each data
message selected for IDPR handling, a source path agent prepends the
following header:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| VERSION | PROTO | LENGTH |
+---------------+---------------+-------------------------------+
| PATH ID |
| |
+---------------------------------------------------------------+
| TIMESTAMP |
+---------------------------------------------------------------+
| INT/AUTH |
| |
+---------------------------------------------------------------+
VERSION (8 bits) Version number for IDPR data messages, currently
equal to 1.
PROTO (8 bits) Numeric identifier for the protocol with which to
process the contents of the IDPR data message. Only the path agent
at the destination interprets and acts upon the contents of the PROTO
field.
LENGTH (16 bits) Length of the entire IDPR data message in bytes.
PATH ID (64 bits) Path identifier assigned by the source's path agent
and consisting of the numeric identifier for the path agent's domain
(16 bits), the numeric identifier for the path agent's policy gateway
(16 bits), and the path agent's local path identifier (32 bits) (see
section 7.2).
TIMESTAMP (32 bits) Number of seconds elapsed since 1 January 1970
0:00 GMT.
INT/AUTH (variable) Computed integrity/authentication value,
dependent on the type of integrity/authentication requested during
path setup.
We describe the IDPR control message header in section 2.4.
1.6. Security
IDPR contains mechanisms for verifying message integrity and source
authenticity and for protecting against certain types of denial of
service attacks. It is particularly important to keep IDPR control
messages intact, because they carry control information critical to
the construction and use of viable policy routes between domains.
All IDPR messages carry a single piece of information, referred to as
the "integrity/authentication value", which may be used not only to
detect message corruption but also to verify the authenticity of the
message source. In the Internet, the IANA will sanction the set of
valid algorithms which may be used to compute the
integrity/authentication values. This set may include algorithms
that perform only message integrity checks such as n-bit cyclic
redundancy checksums (CRCs), as well as algorithms that perform both
message integrity and source authentication checks such as signed
hash functions of message contents.
Each domain administrator is free to select any
integrity/authentication algorithm, from the set specified by the
IANA, for computing the integrity/authentication values contained in
its domain's messages. However, we recommend that IDPR entities in
each domain be capable of executing all of the valid algorithms so
that an IDPR control message originating at an entity in one domain
can be properly checked by an entity in another domain.
Each IDPR control message must carry a non-null
integrity/authentication value. We recommend that control message
integrity/authentication be based on a digital signature algorithm
applied to a one-way hash function, such as RSA applied to MD5 [17],
which simultaneously verifies message integrity and source
authenticity. The digital signature may be based on either public-
key or private-key cryptography. Our approach to digital signature
use in IDPR is based on the privacy-enhanced Internet electronic mail
service [13]-[15], already available in the Internet.
We do not require that IDPR data messages carry a non-null
integrity/authentication value. In fact, we recommend that a higher
layer (end-to-end) procedure, and not IDPR, assume responsibility for
checking the integrity and authenticity of data messages, because of
the amount of computation involved.
1.7. Timestamps and Clock Synchronization
Each IDPR message carries a timestamp (expressed in seconds elapsed
since 1 January 1970 0:00 GMT, following the UNIX precedent) supplied
by the source IDPR entity, which serves to indicate the age of the
message. IDPR entities use the absolute value of the timestamp to
confirm that a message is current and use the relative difference
between timestamps to determine which message contains the more
recent information.
All IDPR entities must possess internal clocks that are synchronized
to some degree, in order for the absolute value of a message
timestamp to be meaningful. The synchronization granularity required
by IDPR is on the order of minutes and can be achieved manually.
Thus, a clock synchronization protocol operating among all IDPR
entities in all domains, while useful, is not necessary.
An IDPR entity can determine whether to accept or reject a message
based on the discrepancy between the message's timestamp and the
entity's own internal clock time. Any IDPR message whose timestamp
lies outside of the acceptable range may contain stale or corrupted
information or may have been issued by a source whose internal clock
has lost synchronization with the message recipient's internal clock.
Timestamp checks are required for control messages because of the
consequences of propagating and acting upon incorrect control
information. However, timestamp checks are discretionary for data
messages but may be invoked during problem diagnosis, for example,
when checking for suspected message replays.
We note that none of the IDPR protocols contain explicit provisions
for dealing with an exhausted timestamp space. As timestamp space
exhaustion will not occur until well into the next century, we expect
timestamp space viability to outlast the IDPR protocols.
1.8. Network Management
In this document, we do not describe how to configure and manage
IDPR. However, in this section, we do provide a list of the types of
IDPR configuration information required. Also, in later sections
describing the IDPR protocols, we briefly note the types of
exceptional events that must be logged for network management.
Complete descriptions of IDPR entity configuration and IDPR managed
objects appear in [7] and [8] respectively.
To participate in inter-domain policy routing, policy gateways and
route servers within a domain each require configuration information.
Some of the configuration information is specifically defined within
the given domain, while some of the configuration information is
universally defined throughout an internetwork. A domain
administrator determines domain-specific information, and in the
Internet, the IANA determines globally significant information.
To produce valid domain configurations, the domain administrators
must receive the following global information from the IANA:
- For each integrity/authentication type, the numeric
identifier, syntax, and semantics. Available integrity and
authentication types include but are not limited to:
o public-key based signatures;
o private-key based signatures;
o cyclic redundancy checksums;
o no integrity/authentication.
- For each user class, the numeric identifier, syntax, and
semantics. Available user classes include but are not limited to:
o federal (and if necessary, agency-specific such as NSF, DOD,
DOE, etc.);
o research;
o commercial;
o support.
- For each offered service that may be advertised in transit
policies, the numeric identifier, syntax, and semantics. Available
offered services include but are not limited to:
o average message delay;
o message delay variation;
o average bandwidth available;
o available bandwidth variation;
o maximum transfer unit (MTU);
o charge per byte;
o charge per message;
o charge per unit time.
- For each access restriction that may be advertised in transit
policies, the numeric identifier, syntax, and semantics. Available
access restrictions include but are not limited to:
o Source and destination domains and host sets.
o User classes.
o Entry and exit virtual gateways.
o Time of day.
- For each requested service that may appear within a path setup
message, the numeric identifier, syntax, and semantics. Available
requested services include but are not limited to:
o maximum path life in minutes, messages, or bytes;
o integrity/authentication algorithms to be used on data
messages sent over the path;
o upper bound on path delay;
o minimum delay path;
o upper bound on path delay variation;
o minimum delay variation path;
o lower bound on path bandwidth;
o maximum bandwidth path;
o upper bound on monetary cost;
o minimum monetary cost path.
In an internetwork-wide implementation of IDPR, the set of global
configuration parameters and their syntax and semantics must be
consistent across all participating domains. The IANA, responsible
for establishing the full set of global configuration parameters in
the Internet, relies on the cooperation of the administrators of all
participating domains to ensure that the global parameters are
consistent with the desired transit policies and user service
requirements of each domain. Moreover, as the syntax and semantics
of the global parameters affects the syntax and semantics of the
corresponding IDPR software, the IANA must carefully define each
global parameter so that it is unlikely to require future
modification.
The IANA provides configured global information to configuration
servers in all domains participating in IDPR. Each domain
administrator uses the configured global information maintained by
its configuration servers to develop configurations for each IDPR
entity within its domain. Each configuration server retains a copy
of the configuration for each local IDPR entity and also distributes
the configuration to that entity using, for example, SNMP.
1.8.1. Policy Gateway Configuration
Each policy gateway must contain sufficient configuration information
to perform its IDPR functions, which subsume those of the path agent.
These include: validating IDPR control messages; generating and
distributing virtual gateway connectivity and routing information
messages to peer, neighbor, and adjacent policy gateways;
distributing routing information messages to route servers in its
domain; resolving destination addresses; requesting policy routes
from route servers; selecting policy routes and initiating path
setup; ensuring consistency of a path with its domain's transit
policies; establishing path forwarding information; and forwarding
IDPR data messages along existing paths. The necessary configuration
information includes the following:
- For each integrity/authentication type, the numeric identifier,
syntax, and semantics.
- For each policy gateway and route server in the given domain, the
numeric identifier and set of addresses or names.
- For each virtual gateway connected to the given domain, the numeric
identifier, the numeric identifiers for the constituent peer policy
gateways, and the numeric identifier for the adjacent domain.
- For each virtual gateway of which the given policy gateway is a
member, the numeric identifiers and set of addresses for the
constituent adjacent policy gateways.
- For each policy gateway directly-connected and adjacent to the
given policy gateway, the local connecting interface.
- For each local route server to which the given policy gateway
distributes routing information, the numeric identifier.
- For each source policy applicable to hosts within the given domain,
the syntax and semantics.
- For each transit policy applicable to the domain, the numeric
identifier, syntax, and semantics.
- For each requested service that may appear within a path setup
message, the numeric identifier, syntax, and semantics.
- For each source user class, the numeric identifier, syntax, and
semantics.
1.8.2. Route Server Configuration
Each route server must contain sufficient configuration information
to perform its IDPR functions, which subsume those of the path agent.
These include: validating IDPR control messages; deciphering and
storing the contents of routing information messages; exchanging
routing information with other route servers and policy gateways;
generating policy routes that respect transit policy restrictions and
source service requirements; distributing policy routes to path
agents in policy gateways; resolving destination addresses; selecting
policy routes and initiating path setup; establishing path forwarding
information; and forwarding IDPR data messages along existing paths.
The necessary configuration information includes the following:
- For each integrity/authentication type, the numeric identifier,
syntax, and semantics.
- For each policy gateway and route server in the given domain, the
numeric identifier and set of addresses or names.
- For each source policy applicable to hosts within the given domain,
the syntax and semantics.
- For access restriction that may be advertised in transit
policies, the numeric identifier, syntax, and semantics.
- For each offered service that may be advertised in transit policies,
the numeric identifier, syntax, and semantics.
- For each requested service that may appear within a path setup
message, the numeric identifier, syntax, and semantics.
- For each source user class, the numeric identifier, syntax, and
semantics.
2. Control Message Transport Protocol
IDPR control messages convey routing-related information that
directly affects the policy routes generated and the paths set up
across the Internet. Errors in IDPR control messages can have
widespread, deleterious effects on inter-domain policy routing, and
so the IDPR protocols have been designed to minimize loss and
corruption of control messages. For every control message it
transmits, each IDPR protocol expects to receive notification as to
whether the control message successfully reached the intended IDPR
recipient. Moreover, the IDPR recipient of a control message first
verifies that the message appears to be well-formed, before acting on
its contents.
All IDPR protocols use the Control Message Transport Protocol (CMTP),
a connectionless, transaction-based transport layer protocol, for
communication with intended recipients of control messages. CMTP
retransmits unacknowledged control messages and applies integrity and
authenticity checks to received control messages.
There are three types of CMTP messages:
DATAGRAM:
Contains IDPR control messages.
ACK: Positive acknowledgement in response to a DATAGRAM message.
NAK: Negative acknowledgement in response to a DATAGRAM message.
Each CMTP message contains several pieces of information supplied by
the sender that allow the recipient to test the integrity and
authenticity of the message. The set of integrity and authenticity
checks performed after CMTP message reception are collectively
referred to as "validation checks" and are described in section 2.3.
When we first designed the IDPR protocols, CMTP as a distinct
protocol did not exist. Instead, CMTP-equivalent functionality was
embedded in each IDPR protocol. To provide a cleaner implementation,
we later decided to provide a single transport protocol that could be
used by all IDPR protocols. We originally considered using an
existing transport protocol, but rejected this approach for the
following reasons:
- The existing reliable transport protocols do not provide all of the
validation checks, in particular the timestamp and authenticity
checks, required by the IDPR protocols. Hence, if we were to use
one of these protocols, we would still have to provide a separate
protocol on top of the transport protocol to force retransmission of
IDPR messages that failed to pass the required validation checks.
- Many of the existing reliable transport protocols are window-based
and hence can result in increased message delay and resource use
when, as is the case with IDPR, multiple independent messages use
the same transport connection. A single message experiencing
transmission problems and requiring retransmission can prevent the
window from advancing, forcing all subsequent messages to queue
behind it. Moreover, many of the window-based protocols do not
support selective retransmission of failed messages but instead
require retransmission of not only the failed message but also all
preceding messages within the window.
For these reasons, we decided against using an existing transport
protocol and in favor of developing CMTP.
2.1. Message Transmission
At the transmitting entity, when an IDPR protocol is ready to issue a
control message, it passes a copy of the message to CMTP; it also
passes a set of parameters to CMTP for inclusion in the CMTP header
and for proper CMTP message handling. In turn, CMTP converts the
control message and associated parameters into a DATAGRAM by
prepending the appropriate header to the control message. The CMTP
header contains several pieces of information to aid the message
recipient in detecting errors (see section 2.4). Each IDPR protocol
can specify all of the following CMTP parameters applicable to its
control message:
- IDPR protocol and message type.
- Destination.
- Integrity/authentication scheme.
- Timestamp.
- Maximum number of transmissions allotted.
- Retransmission interval in microseconds.
One of these parameters, the timestamp, can be specified directly by
CMTP as the internal clock time at which the message is transmitted.
However, two of the IDPR protocols, namely flooding and path control,
themselves require message generation timestamps for proper protocol
operation. Thus, instead of requiring CMTP to pass back a timestamp
to an IDPR protocol, we simplify the service interface between CMTP
and the IDPR protocols by allowing an IDPR protocol to specify the
timestamp in the first place.
Using the control message and accompanying parameters supplied by the
IDPR protocol, CMTP constructs a DATAGRAM, adding to the header
CMTP-specific parameters. In particular, CMTP assigns a "transaction
identifier" to each DATAGRAM generated, which it uses to associate
acknowledgements with DATAGRAM messages. Each DATAGRAM recipient
includes the received transaction identifier in its returned ACK or
NAK, and each DATAGRAM sender uses the transaction identifier to
match the received ACK or NAK with the original DATAGRAM.
A single DATAGRAM, for example a routing information message or a
path control message, may be handled by CMTP at many different policy
gateways. Within a pair of consecutive IDPR entities, the DATAGRAM
sender expects to receive an acknowledgement from the DATAGRAM
recipient. However, only the IDPR entity that actually generated the
original CMTP DATAGRAM has control over the transaction identifier,
because that entity may supply a digital signature that covers the
entire DATAGRAM. The intermediate policy gateways that transmit the
DATAGRAM do not change the transaction identifier. Nevertheless, at
each DATAGRAM recipient, the transaction identifier must uniquely
distinguish the DATAGRAM so that only one acknowledgement from the
next DATAGRAM recipient matches the original DATAGRAM. Therefore,
the transaction identifier must be globally unique.
The transaction identifier consists of the numeric identifiers for
the domain and IDPR entity (policy gateway or route server) issuing
the original DATAGRAM, together with a 32-bit local identifier
assigned by CMTP operating within that IDPR entity. We recommend
implementing the 32-bit local identifier either as a simple counter
incremented for each DATAGRAM generated or as a fine granularity
clock. The former always guarantees uniqueness of transaction
identifiers; the latter guarantees uniqueness of transaction
identifiers, provided the clock granularity is finer than the minimum
possible interval between DATAGRAM generations and the clock wrapping
period is longer than the maximum round-trip delay to and from any
internetwork destination.
Before transmitting a DATAGRAM, CMTP computes the length of the
entire message, taking into account the prescribed
integrity/authentication scheme, and then computes the
integrity/authentication value over the whole message. CMTP includes
both of these quantities, which are crucial for checking message
integrity and authenticity at the recipient, in the DATAGRAM header.
After sending a DATAGRAM, CMTP saves a copy and sets an associated
retransmission timer, as directed by the IDPR protocol parameters.
If the retransmission timer fires and CMTP has received neither an
ACK nor a NAK for the DATAGRAM, CMTP then retransmits the DATAGRAM,
provided this retransmission does not exceed the transmission
allotment. Whenever a DATAGRAM exhausts its transmission allotment,
CMTP discards the DATAGRAM, informs the IDPR protocol that the
control message transmission was not successful, and logs the event
for network management. In this case, the IDPR protocol may either
resubmit its control message to CMTP, specifying an alternate
destination, or discard the control message altogether.
2.2. Message Reception
At the receiving entity, when CMTP obtains a DATAGRAM, it takes one
of the following actions, depending upon the outcome of the message
validation checks:
- The DATAGRAM passes the CMTP validation checks. CMTP then delivers
the DATAGRAM with enclosed IDPR control message, to the appropriate