RFC 1477

RFC 1477: IDPR as a Proposed Standard 💖

okay bestie, this is RFC 1477, written by M. Steenstrup of BBN Systems and Technologies for the Network Working Group, dated July 1993 🎀 the title says "Proposed Standard," but ngl the memo itself says it does not specify an Internet standard, so read the status section carefully 👀 the title block doesn't list anything it obsoletes or updates ✨

Status of this Memo 🎀

This memo provides information for the Internet community. It does not specify an Internet standard. Distribution of this memo is unlimited. 🌸

1. Introduction ✨

this doc is a deep dive into inter-domain policy routing (IDPR) 🦋 it covers an overview of functionality and a discussion of experiments. the objective of IDPR is to construct and maintain routes between source and destination administrative domains, so user traffic gets the services it requested, within the constraints stipulated for the domains it transits 💅

Four documents describe IDPR in detail:

• M. Steenstrup. An architecture for inter-domain policy routing. RFC 1478. July 1993.
• M. Steenstrup. Inter-domain policy routing protocol specification: version 1. RFC 1479. July 1993.
• H. Bowns and M. Steenstrup. Inter-domain policy routing configuration and usage. Work in Progress. July 1991.
• R. Woodburn. Definitions of managed objects for inter-domain policy routing (version 1). Work in Progress. March 1993.

this is a product of the Inter-Domain Policy Routing Working Group of the Internet Engineering Task Force (IETF) 💜

2. The Internet Environment 🌈

as data communications tech evolves and user populations grow, the demand for internetworking goes up. the Internet currently comprises over 7000 operational networks and over 10,000 registered networks 🤯 and for the last several years, the number of constituent networks has approximately doubled annually. we don't expect the Internet to keep that growth rate, but we must prep for the Internet of five to ten years in the future 🚀

Internet connectivity has grown right alongside the number of component networks. Internetworks proliferate through interconnection of autonomous, heterogeneous networks administered by separate authorities. we use the term "administrative domain" (AD) to refer to any collection of contiguous networks, gateways, links, and hosts governed by a single administrative authority that selects the intra-domain routing procedures and addressing schemes, specifies service restrictions for transit traffic, and defines service requirements for locally-generated traffic 📚

in the early 1980s, the Internet was purely hierarchical, with the ARPANET as the single backbone 🕰️ the current Internet has a semblance of a hierarchy in the collection of backbone, regional, metropolitan, and campus domains that compose it. however, technological, economical, and political incentives have prompted the introduction of inter-domain links outside of the strict hierarchy. so the Internet has the properties of both hierarchical and mesh connectivity 🕸️

we expect that, over the next five years, the Internet will grow to contain O(10) backbone domains, most providing connectivity between many source and destination domains and offering a wide range of qualities of service, for a fee. most domains will connect directly or indirectly to at least one Internet backbone domain, in order to communicate with other domains. in addition, some domains may install direct links to their most favored destinations 💕 domains at the lower levels of the hierarchy will provide some transit service, limited to traffic between selected sources and destinations. however, the majority of Internet domains will be "stubs," that is, domains that do not provide any transit service for any other domains but that connect directly to one or more transit domains 🧸

the bulk of Internet traffic will be generated by hosts in the stub domains, so the applications running in those hosts will determine the traffic service requirements 📱 we expect application diversity encompassing electronic mail, desktop videoconferencing, scientific visualization, and distributed simulation, for example. many of these applications have strict requirements on loss, delay, and throughput 😭

in such a large and heterogeneous Internet, the routing procedures must be capable of ensuring that traffic is forwarded along routes that offer the required services without violating domain usage restrictions. we believe that IDPR meets this goal, since it has been designed to accommodate an Internet comprising O(10,000) administrative domains with diverse service offerings and requirements 💅✨

3. An Overview of IDPR 🦋

IDPR generates, establishes, and maintains "policy routes" that satisfy the service requirements of the users and respect the service restrictions of the transit domains. policy routes are constructed using information about the services offered by, and the connectivity between, administrative domains, plus information about the services requested by the users 🧩

3.1 Policies

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 session 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: e.g., domains to favor or avoid in routes.
• Quality: e.g., acceptable delay, throughput, and reliability.
• Monetary cost: e.g., acceptable cost per byte, message, or session time.

3.2 Functions

the basic IDPR functions include:

• Collecting and distributing routing information, i.e., domain transit policy and connectivity information. IDPR uses link state routing information distribution, so that each source domain may obtain routing information about all other domains.
• Generating and selecting policy routes based on the routing information distributed and on source policy information. IDPR gives each source domain complete control over the routes it generates.
• Setting up paths across the Internet, using the policy routes generated.
• Forwarding messages across and between administrative domains along the established paths. IDPR uses source-specified message forwarding, giving each source domain complete control over the paths traversed by its hosts' inter-domain traffic.
• Maintaining databases of routing information, inter-domain policy routes, forwarding information, and configuration information.

3.3 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, maintain forwarding information databases, and forward data messages along established paths.
• "Path agents," resident within policy gateways, 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 willing to act on its behalf and a means by which the host's messages can reach that path agent.
• Special-purpose servers maintain all other IDPR databases as follows:
  • Each "route server" is responsible for both its database of routing information, including domain connectivity and transit policy information, and its database of policy routes. Also, each route server generates policy routes on behalf of its domain, using entries from its routing information database and using source policy information supplied through configuration or obtained directly from 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 routing information database and route database maintenance and the computationally intensive task of route generation.
  • Each "mapping server" is responsible for its database of mappings that resolve Internet names and addresses to administrative domains. The mapping server function can be easily integrated into an existing name service such as the DNS.
  • Each "configuration server" is responsible for its database of configured information that applies to policy gateways, path agents, and route servers in the given administrative domain. Configuration information for a given domain includes source and transit policies and mappings between local IDPR entities and their addresses. The configuration server function can be easily integrated into a domain's existing network management system.

3.4 Message Handling

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 the Internet, only policy gateways and route servers must be able to generate, recognize, and process IDPR messages. Mapping servers and configuration servers perform necessary but ancillary functions for IDPR, and they are not required to execute IDPR protocols. The existence of IDPR is invisible to all other gateways and hosts. Using encapsulation across each domain, an IDPR message tunnels from source to destination across the Internet through domains that may employ disparate intra-domain addressing schemes and routing procedures.

heads up 🙈 "must" and "not required" are lowercase in this memo, so they're plain English words here, not formal requirement keywords.

4. 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 🚨 this is the part to take seriously, bestie, so don't skip it 😤

---

part 1 of 3 is done, and more is coming, so stay tuned 🎀✨

4.1. Integrity and Authenticity 🔐

Okay so every IDPR message carries one special piece of info, which the IDPR docs call the "integrity/authentication value" 💖. It can catch message corruption, and it can also verify that the message really came from the source IDPR entity it claims ✨. The Internet Assigned Numbers Authority (IANA) decides which algorithms are valid for computing these values 🎀. That list may include algorithms that only do integrity checks, like n-bit cyclic redundancy checksums (CRCs), and algorithms that do both integrity and source authentication, like signed hash functions of message contents 🔥.

Every domain administrator gets to pick any integrity/authentication algorithm from the IANA list for the values in their domain's messages, periodt 💅. However, we recommend that IDPR entities in each domain be able to run all of the valid algorithms, so a message from one domain can be properly checked by an entity in another domain 🫶.

IDPR control messages 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, since that checks message integrity and source authenticity all at once 🔐. The digital signature MAY be based on either public key or private key cryptography 🔑. However, 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 take on the job of checking the integrity and authenticity of data messages, because of the amount of computation involved 💀.

4.2. Timestamps ⏰

Each IDPR message carries a timestamp (expressed in seconds elapsed since 1 January 1970 0:00 GMT) supplied by the source IDPR entity 🕰️. It shows how old the message is. IDPR entities look at the absolute value of a timestamp to confirm the message is current, and they compare timestamps to figure out which message has the freshest info 💅. All IDPR entities MUST possess internal clocks that are synchronized to some degree, so the absolute value of a message timestamp actually means something. The synchronization granularity IDPR needs is on the order of minutes, and it can be achieved manually 🙈.

Every IDPR recipient of an IDPR control message MUST check that the message's timestamp is in the acceptable range 🧐. If it's outside that range, the message may contain stale or corrupted information, or it may have come from a source whose clock lost synchronization with the recipient 😬. Those messages MUST therefore be discarded, to stop incorrect IDPR control information from spreading 🚫. For IDPR data messages, we don't require a timestamp acceptability test. We leave that choice to each individual domain administrator 🌸.

5. Size Considerations 📏

IDPR provides policy routing among administrative domains, and it has been designed to accommodate an Internet containing tens of thousands of domains, supporting diverse source and transit policies 🌍.

To construct policy routes, route servers require routing information at the domain level only 🧠. No intra-domain details need to be included in IDPR routing information. So the size of the routing information database a route server maintains depends on the number of domains and transit policies, and not on the number of hosts, gateways, or networks in the Internet.

We expect that, within a domain, a pair of IDPR entities will normally be connected so that when the primary intra-domain route fails, the intra-domain routing procedure can use an alternate route ✨. In that case, a temporary intra-domain failure is invisible at the inter-domain level. So we expect that most intra-domain routing changes will be unlikely to force inter-domain routing changes 😌.

Policy gateways distribute routing information when detectable inter-domain changes occur, but they MAY also elect to distribute routing information periodically as a backup 🛟. So policy gateways don't often need to generate and distribute routing information messages, and how often these messages go out depends only weakly on intra-domain routing changes.

IDPR entities rely on intra-domain routing procedures to transport inter-domain messages across domains 🚚. That means IDPR messages MUST appear well-formed according to the intra-domain routing procedures and addressing schemes in each domain traversed. This requires appropriate header encapsulation of IDPR messages at domain boundaries 📦. Only policy gateways and route servers MUST be capable of handling IDPR-specific messages. Other gateways and hosts simply treat the encapsulated IDPR messages like any other. So for the Internet to support IDPR, only a small proportion of Internet entities need special IDPR software 👑.

With domain-level routes, many different traffic flows may use not only the same policy route but also the same path, as long as their source domains, destination domains, and requested services are identical 🦋. So the size of the forwarding information database a policy gateway maintains depends on the number of domains and source policies, and not on the number of hosts in the Internet. Plus, memory tied to failed, expired, or disused paths can be reclaimed for new paths, so forwarding information for many paths can fit 🧚.

6. Interactions with Other Inter-Domain Routing Procedures 🤝

We believe many Internet domains will benefit from introducing IDPR 🌈. However, deciding to support IDPR in a given domain is an individual choice, left to the domain administrator. Not all domains MUST support IDPR.

Within a domain that supports IDPR, other inter-domain routing procedures, such as BGP and EGP, can comfortably coexist 💜. Each inter-domain routing procedure is independent of the others. The domain administrator sets up the relationship among them by deciding which of its traffic flows should use which inter-domain routing procedures, and then configuring that info for the policy gateways ⚙️.

Hosts in stub domains may have strict service requirements, so they'll benefit from the policy routing IDPR provides 🎯. However, the stub domain itself doesn't need to support IDPR for its traffic flows to use IDPR routes. Instead, a "proxy domain" MAY perform IDPR functions on behalf of the stub 🫧. The proxy domain MUST be reachable from the stub domain according to an inter-domain routing procedure that's independent of IDPR. The administrators of the stub and potential proxy domains negotiate the relationship together. Once they reach an agreement, the administrator of the stub domain SHOULD provide the proxy domain with its hosts' service requirements 📝.

IDPR policy routes MUST traverse a contiguous set of IDPR domains. So the degree of IDPR deployment in transit domains decides how many IDPR policy routes are available to Internet users 🌐. For a given traffic flow, if there's no contiguous set of IDPR domains between the source and destination, the traffic flow relies on an alternate inter-domain routing procedure to provide a route. But if there is a contiguous set of IDPR domains between the source and destination, the traffic flow may take advantage of policy routes provided by IDPR 🎀.

7. Implementation Experience 🧪

To date, there exist two implementations of IDPR: one is an independent prototype, and the other is an integral part of the gated UNIX process 💻. We describe each of these implementations, and our experience with them, in the following sections 📖.

7.1. The Prototype 🛠️

During the summer of 1990, the IDPR development group, made up of participants from USC, SAIC, and BBN, started work on a UNIX-based software prototype of IDPR, designed for implementation on Sun workstations 🖥️. This prototype consisted of multiple user-level processes that provided the basic IDPR functions, together with kernel modifications to speed up IDPR data message forwarding ⚡.

Most, but not all, of the IDPR functionality made it into the prototype. To get working software out as quickly as possible, we intentionally left out support for source policies and for multiple policy gateways connecting two domains 🏃‍♀️. This simplified configuration and route generation without compromising the basic functionality of IDPR.

The IDPR prototype software was extensively instrumented to provide detailed information for monitoring its behavior 📊. The instrumentation let us detect events including, but not limited to:

• Change in policy gateway connectivity to adjacent domains.
• Change in transit policies configured for a domain.
• Transmission and reception of link state routing information.
• Generation of policy routes, providing a description of the actual route.
• Transmission and reception of path control information.
• Change of path state, such as path setup or teardown.

With all that behavioral info available, we were able to track most events happening in our test networks, and so determine whether the prototype software provided the expected functionality 🔍.

7.1.1. Test Networks 🧪

In February 1991, the IDPR development group started experimenting with the completed IDPR prototype software 🎉. Each IDPR development site had its own testing environment, made up of a set of interconnected Sun workstations, with each workstation performing the functions of a policy gateway and route server:

• USC used a laboratory test network consisting of SPARC1+ workstations, with each pair of workstations connected by an Ethernet segment. The topology of the test network could be arbitrarily configured 🧪.
• SAIC used Sun3 workstations in networks at Sparta and at MITRE. These two sites were connected through Alternet using a 9.6kb SLIP link, and through an X.25 path across the DCA EDN testbed 🌉.
• BBN used SPARC1+ workstations at BBN and ISI, connected over both DARTnet and TWBnet 💜.

7.1.2 Experiments ✨

okay so the main goal of our experiments with the IDPR prototype was to prove it works at all 💅 we wanted to check that the prototype could:

• Monitor connectivity across and between domains.
• Update routing information when inter-domain connectivity changed or when new transit policies were configured.
• Distribute routing information to all domains.
• Generate acceptable policy routes based on current link state routing information.
• Set up and maintain paths for these policy routes.
• Tear down paths that contained failed components, supported stale policies, or attained their maximum age.

we also wanted to see whether it spotted and adapted to the events that directly hit policy routes, and how fast it did that 👀

our main test network was four separate administrative domains hooked up in a ring 💍 two of them were the host traffic source and destination, AD S and AD D, and the other two were transit domains doing the carrying work for the host traffic, AD T1 and AD T2. AD S and AD D each had one policy gateway connected to two other policy gateways, one in each transit domain. AD T1 and AD T2 each had at most two policy gateways, and each of those was connected to the others and to a policy gateway in the source or destination domain. this setup gave us two distinct inter-domain routes between AD S and AD D, which meant we could play with all kinds of component failure and transit policy reconfiguration scenarios in the transit domains 🌸

for the first round, we set up transit policies for AD T1 and AD T2 with zero access restrictions. then we booted up every policy gateway in our internetwork, loading in the domain-specific configs and starting the IDPR processes 🚀

we didn't use mapping servers for this. instead, we set up address/domain mapping tables in each policy gateway by hand 🛠️

after the policy gateways started up, each one immediately figured out its connectivity to the policy gateways in its own domain and in the adjacent domains. the representative policy gateway in each domain then generated a routing information message, and every other policy gateway in the internetwork received it 📨

to test route generation and path setup, we started a telnet session between a host in AD S and a host in AD D 🖥️ the telnet traffic made the path agent in the policy gateway in AD S ask its route server for a policy route. the route server generated one and handed it back to the path agent. the path agent then used that route to start path setup, and the telnet session connected right away ✨

once we knew the prototype could handle the basics, we moved on to changing network conditions 🌪️ the first test was a component failure along a path, and the prototype handled it like a pro 💪 to fake a failure, we killed the IDPR processes on a policy gateway in transit domain AD T1 that was on the current path. the policy gateways on either side of the dead one noticed the failure immediately 😳 then those two gateways, sitting in two different domains, each sent out a routing information message about the connectivity change and each started tearing down the path section it still had.

once the path was torn down, the path agent in AD S asked its route server for a new route to keep the telnet traffic going. the route server had already gotten the new routing information messages, so it generated a policy route through the other transit domain, AD T2. then the path agent in AD S set up a path for that new route. the telnet session stayed intact the entire time, through the failure and the reroute 🫶

next, we restarted the IDPR processes on the failed policy gateway in AD T1, which put it back in working order. the restored connectivity triggered routing information messages announcing the change in domain connectivity 🔄

with the topology back to where it started, we tested transit policy reconfiguration 🎀 the telnet traffic was riding a policy route through AD T2. we then changed the transit policy for AD T2 so it blocked traffic going from AD S to AD D. that change kicked off two things: routing information advertising the new transit policy for AD T2, and path teardown 🙅‍♀️

once the path was gone, the path agent in AD S asked its route server for a new route to carry the telnet traffic. the route server had received the new routing information message, so it generated a policy route through the original transit domain, AD T1. the path agent in AD S then set up a path for that route. the telnet session survived the whole policy change and reroute too 💖

honestly this set of experiments was simple, but it tested all of the major functionality of the IDPR prototype and showed that the prototype could adapt quickly and accurately to changes in the internetwork 🏆

---

7.1.3 Performance Analysis 📊

USC and SAIC members of the IDPR development group evaluated the performance of the path setup and message forwarding parts of the IDPR prototype. for path setup, we measured how much processing the source path agent and the intermediate policy gateways needed during setup. for message forwarding, we compared the processing each policy gateway needed when using IDPR forwarding with IP encapsulation versus using only IP forwarding. we also compared the processing needed when no integrity/authentication value was calculated for the message versus when the RSA/MD4 algorithms were used 🧮

our performance results were encouraging, but we're not listing them here 🙈 also, we didn't have much time to optimize the prototype software, even though we tried to make it efficient. so the performance measurements for the IDPR prototype should not be blindly extrapolated to other IDPR implementations ⚠️ if you want a copy of the path setup and message forwarding performance measurements for the prototype, contact Robert Woodburn (woody@sparta.com) and Deborah Estrin (estrin@usc.edu) 📩

---

7.2 The Gated Version 🌈

in 1992, SRI joined the IDPR development group, and together SRI, SAIC, and BBN finished the job of integrating IDPR into the gated UNIX process 🎉 so now IDPR comes as part of gated. the gated version has the full IDPR functionality plus a simple yet versatile user interface for configuring IDPR. since it runs as a single process, the gated version performs more efficiently than the multiple-process prototype 🏃‍♀️

the gated version of IDPR is freely available to the Internet community, which is so iconic of them 🥹 that means anyone with a UNIX-based machine can experiment with IDPR without spending any money or putting in any implementation effort 💸 by making IDPR this accessible, we can get real Internet experience by putting it into operational networks with real usage constraints and carrying host traffic with real service requirements. a pilot deployment and demonstration of IDPR is currently under way in selected locations in the Internet 🦋

---

8. Security Considerations 🔐

Refer to section 4 for details on security in IDPR.

---

9. Author's Address 💌

Martha Steenstrup
BBN Systems and Technologies
10 Moulton Street
Cambridge, MA 02138

Phone: (617) 873-3192
Email: msteenst@bbn.com