RFC 1478

An Architecture for Inter-Domain Policy Routing

📅 published June 1993, from ietf

An Architecture for Inter-Domain Policy Routing 🎀

okay so this is RFC 1478 📜, from the Network Working Group, written by M. Steenstrup of BBN Systems and Technologies and dated June 1993. It's an IAB standards track protocol, so this is a real spec that people build against 💅. The title block doesn't list anything it obsoletes or updates.

Status of This Memo 📝

this one is an IAB standards track protocol for the whole Internet community 🌍, and they're literally asking for discussion and suggestions to make it better 💬. for the current standardization state and status, check the current edition of the "IAB Official Protocol Standards" 📚. distribution of this memo is unlimited 🦋.

Abstract 🔮

okay the big idea: this is an architecture for inter-domain policy routing (IDPR) 🧚. IDPR's whole job is to construct and maintain routes between source and destination administrative domains, so user traffic gets the services it asked for while staying inside the constraints set for every domain it passes through 🛣️. it's built for an internetwork with tens of thousands of administrative domains, each with its own heterogeneous service requirements and restrictions 👑.

Contributors 🫶

the people who helped build the IDPR architecture are: Bob Braden, Lee Breslau, Ross Callon, Noel Chiappa, Dave Clark, Pat Clark, Deborah Estrin, Marianne Lepp, Mike Little, Martha Steenstrup, Zaw-Sing Su, Paul Tsuchiya, and Gene Tsudik 💖. Yakov Rekhter also gave lots of useful comments on an earlier draft, which is so iconic of him 🙌.

Table of Contents 🗂️

1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1. The Internet Environment. . . . . . . . . . . . . . . . . . . 4
2. Approaches to Policy Routing. . . . . . . . . . . . . . . . . . 5
2.1. Policy Route Generation . . . . . . . . . . . . . . . . . . . 5
2.1.1. Distance Vector Approach. . . . . . . . . . . . . . . . . . 5
2.1.2. Link State Approach . . . . . . . . . . . . . . . . . . . . 7
2.2. Routing Information Distribution. . . . . . . . . . . . . . . . 8
2.2.1. Distance Vector Approach. . . . . . . . . . . . . . . . . . 8
2.2.2. Link State Approach . . . . . . . . . . . . . . . . . . . .10
2.3. Message Forwarding along Policy Routes. . . . . . . . . . . .10
2.3.1. Hop-by-Hop Approach . . . . . . . . . . . . . . . . . . . .11
2.3.1.1. A Clarification . . . . . . . . . . . . . . . . . . . . .11
2.3.2. Source Specified Approach . . . . . . . . . . . . . . . . .12
3. The IDPR Architecture . . . . . . . . . . . . . . . . . . . . .13
3.1. IDPR Functions. . . . . . . . . . . . . . . . . . . . . . . .13
3.2. IDPR Entities . . . . . . . . . . . . . . . . . . . . . . . .13
3.2.1. Path Agents . . . . . . . . . . . . . . . . . . . . . . . .16
3.2.2. IDPR Servers. . . . . . . . . . . . . . . . . . . . . . . .17
3.2.3. Entity Identifiers. . . . . . . . . . . . . . . . . . . . .19
3.3. Security and Reliability. . . . . . . . . . . . . . . . . . .20
3.3.1. Retransmissions and Acknowledgements. . . . . . . . . . . .20
3.3.2. Integrity Checks. . . . . . . . . . . . . . . . . . . . . .21
3.3.3. Source Authentication . . . . . . . . . . . . . . . . . . .21
3.3.4. Timestamps. . . . . . . . . . . . . . . . . . . . . . . . .21
3.4. An Example of IDPR Operation. . . . . . . . . . . . . . . . .22
4. Accommodating a Large, Heterogeneous Internet . . . . . . . . .25
4.1. Domain Level Routing. . . . . . . . . . . . . . . . . . . . .25
4.2. Route Generation. . . . . . . . . . . . . . . . . . . . . . .27
4.3. Super Domains . . . . . . . . . . . . . . . . . . . . . . . .29
4.4. Domain Communities. . . . . . . . . . . . . . . . . . . . . .30
4.5. Robustness in the Presence of Failures. . . . . . . . . . . .31
4.5.1. Path Repair . . . . . . . . . . . . . . . . . . . . . . . .31
4.5.2. Partitions. . . . . . . . . . . . . . . . . . . . . . . . .33
5. References. . . . . . . . . . . . . . . . . . . . . . . . . . .XX
5. Security Considerations . . . . . . . . . . . . . . . . . . . .34
6. Author's Address  . . . . . . . . . . . . . . . . . . . . . . .34

1. Introduction ✨

as data comms tech evolves and more users show up, everyone wants more internetworking 📈. internetworks usually grow by hooking together autonomous, heterogeneous networks run by separate authorities 🔗. we use "administrative domain" (AD) for any group of contiguous networks, gateways, links, and hosts under one administrative authority 🏰. that authority picks the intra-domain routing procedures and addressing schemes, sets service restrictions for transit traffic, and defines service requirements for traffic generated locally 💅.

connecting administrative domains can widen the menu of services across the internetwork 🍓, so traffic with special service needs is more likely to actually get what it asked for ✨. but, plot twist, administrators offering special transit services are more likely to slap on strict access restrictions, to keep control over their domain's resources 🙈.

an internetwork with lots of domains, each with different service needs and restrictions, needs "policy routing" to move traffic between source and destination 🧭. policy routing covers the route generation and message forwarding procedures that produce and use routes which satisfy user service requirements and respect transit domain service restrictions all at once 💖.

with policy routing, each domain administrator sets "transit policies" that decide how and by whom the resources inside their domain can be used 🎀. transit policies are usually public, and they spell out the offered services, which include:

  • 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 starting inside their domain 🚀. source policies are usually private, and they spell out the requested services, which include:

  • Access restrictions: e.g., domains to favor or avoid in routes.
  • Quality: e.g., acceptable delay, throughput, or reliability.
  • Monetary cost: e.g., acceptable session cost.

in this document, we describe an architecture for inter-domain policy routing (IDPR), and we provide a set of functions that can form the basis for a suite of IDPR protocols and procedures 🦋.

1.1. The Internet Environment 🌍

the Internet is currently over 7000 operational networks strong, plus over 10,000 registered networks 🤯. for the last several years, the number of constituent networks has roughly doubled every year 📈! we don't expect the Internet to keep up that pace, but the IDPR architecture still has to be ready for the Internet five to ten years down the line 🔮. following the functional requirements for inter-autonomous system (i.e., inter-domain) routing set forth in [6], the IDPR architecture and protocols need to be able to handle O(100,000) networks spread across O(10,000) domains 💜.

internet connectivity has grown right alongside the number of component networks 🌸. 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 its collection of backbone, regional, metropolitan, and campus domains. but technological, economic, and political incentives have pushed the introduction of inter-domain links outside of that strict hierarchy 👀. so, the Internet now has the properties of both hierarchical and mesh connectivity. it's giving both 🕸️✨.

we expect the Internet to evolve in the following way 🔭. 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, so they can talk to other domains 📡. some domains may also 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", meaning domains that don't provide any transit service for other domains 🍰.

the bulk of Internet traffic will come from hosts in these stub domains, so the applications running on those hosts will decide the traffic service requirements 📱. we expect a lot of application diversity, including electronic mail, desktop videoconferencing, scientific visualization, and distributed simulation, to name a few 🎥. many of these applications have strict requirements on loss, delay, and throughput 😭.

ensuring that Internet traffic takes routes that provide the required services without breaking domain usage restrictions will be the job of policy routing on the Internet over the next several years 👑. refer to [1]-[10] for more information on the role of policy routing in the Internet 📚.

2. Approaches to Policy Routing 🧭

in this section, we assess the candidate approaches to policy routing 🔍. we focus on the "distance vector" and "link state" options for routing information distribution and route generation, and on the "hop-by-hop" and "source specified" options for forwarding data messages 🛣️. the IDPR architecture supports link state routing information distribution and route generation together with source specified message forwarding. we justify these choices for IDPR below 💅.

2.1. Policy Route Generation 🗺️

we present policy route generation from the distance vector perspective and from the link state perspective 🦋.

2.1.1. Distance Vector Approach 💖

okay so distance vector route generation splits the work of computing a single route across multiple routing entities along that route 🦋. that means it's potentially susceptible to routing loop formation and slow adaptation to changes in an internetwork 😭. BUT there are techniques you can apply during distance vector route generation to reduce how bad these problems get, or even wipe them out completely ✨. if you want a loop-free, quickly adapting distance vector routing procedure, go check out [13] and [14] 🎀

when policy route generation is happening, every recipient of a distance vector message has to assess whether the route is acceptable, then figure out which neighboring domains the message SHOULD be propagated to 💅. in the policy routing context, both of the following conditions are necessary for route acceptability 👑:

  • The route is consistent with at least one transit policy for each domain, not including the current routing entity's domain, contained in the route. So that each recipient can check the route against every constituent domain's transit policies, each routing entity SHOULD include its domain's identity and transit policies in each acceptable distance vector message it propagates 🔥.
  • The route is consistent with at least one source policy for at least one domain in the Internet. So that each recipient can check the route against particular domains' source policies, each domain MUST give other domains access to its source policies 🫶.

On top of that, at least one of the following conditions is also necessary for route acceptability 🌸:

  • The route is consistent with at least one of the transit policies for the current routing entity's domain. In this case, the routing entity accepts the distance vector message and compares the route with its other routes to the destinations listed in the message. If it decides the new route is preferable, it updates the message with its domain's identity and transit policies and propagates the message to the appropriate neighboring domains. We talk about distance vector message distribution in more detail in section 2.2.1 🦋.

The route is consistent with at least one of the source policies for the current routing entity's domain. In this case, the routing entity doesn't have to propagate the distance vector message, but it does keep the route around for traffic from local hosts heading to the destinations listed in the message 💜.

The routing entity discards any distance vector message that doesn't meet these necessary conditions 💀.

With distance vector policy route generation, a routing entity MAY select and store multiple routes with different characteristics, like qualities of service, to a single destination. It uses the quality of service information in the transit policies of accepted distance vector messages to tell routes apart by quality of service ⭐. Also, a routing entity MAY select routes that are specific to certain source domains, provided it has access to the source policies of those domains 🧚.

In the distance vector context, accounting for other domains' transit and source policies during route selection gives you all this flexibility, but it comes with these downsides 😩:

  • Each recipient of a distance vector message MUST bear the cost of verifying that the route is consistent with the constituent domains' transit policies.
  • Source policies MUST be made public. Thus, a domain MUST divulge potentially private information.
  • Each recipient of a distance vector message MUST bear the potentially high costs of selecting routes for arbitrary source domains. In particular, a routing entity MUST store the source policies of other domains, account for them during route selection, and maintain source-specific forwarding information. Also, there MUST be a mechanism for distributing source policy information among domains. Depending on the mechanism selected, distribution of source policies MAY add to the costs paid by each routing entity in supporting source-specific routing.

We note, however, that failure to distribute source policies to all domains MAY have unfortunate consequences. In the worst case, a domain may not learn of any acceptable routes to a given destination, even though acceptable routes do exist. For example, suppose that AD V is connected to AD W and that AD W can reach AD Z through either AD X or AD Y. Suppose also that AD W, as a recipient of distance vector messages originating in AD Z, prefers the route through AD Y to the route through AD X. Furthermore, suppose that AD W has no knowledge of AD V's source policy precluding traffic from traversing AD Y. Hence, AD W distributes to AD V the distance vector message containing the route WYZ but not the distance vector message containing the route WXZ.

AD V is thus left with no known route to AD Z, although a viable route traversing AD W and AD X does exist. 😱

link state route generation lets the computation of a single route live inside a single routing entity, the one at the source of the route ⭐. in the policy routing context, entities within a domain generate link state messages containing information about the originating domain. That includes the set of transit policies that apply and the connectivity to adjacent domains. They then distribute these messages to neighboring domains. Each recipient of a link state message stores the routing information for anticipated policy route generation and also distributes it to its neighboring domains 🫧. Based on the set of link state messages collected from other domains and on its domain's source and transit policies, a routing entity constructs and selects policy routes from its domain to other domains in the Internet 🧚.

we picked link state policy route generation for IDPR for these reasons 💖:

  • Each domain has complete control over policy route generation from the perspective of itself as the source.
  • The cost of computing a route is completely contained within the source domain. So routing entities in other domains need not bear the cost of generating policy routes that their domains' local hosts may never use.
  • Source policies MAY be kept private, and hence need not be distributed. Thus, there are no memory, processing, or transmission bandwidth costs incurred for distributing and storing source policies 🔐.

2.2. Routing Information Distribution 🦋

a domain's routing information, and the set of domains that routing information gets distributed to, each influence the set of generable policy routes that include the given domain 🌸. Specifically, a domain administrator MAY promote the generation of routes that obey its domain's transit policies by making sure its domain's routing information:

  • Includes resource access restrictions.
  • Is distributed only to those domains that are permitted to use these resources.

Both of these mechanisms, distributing restrictions with the routing information and restricting distribution of a domain's routing information, can be applied in both the distance vector and link state contexts 🎀.

2.2.1. Distance Vector Approach 🌷

A routing entity MAY distribute its domain's resource access restrictions by including the appropriate transit policy information in each distance vector message it accepts and propagates. Also, the routing entity MAY restrict distribution of an accepted distance vector message by limiting the set of neighboring domains it propagates the message to. In fact, restricting distribution of routing information is inherent in the distance vector approach, since a routing entity propagates only the preferred routes among all the distance vector messages it accepts 💅.

Restricting distribution of distance vector messages is easy, but coordinating restricted distribution among domains requires each domain to know the other domains' distribution restrictions. Each domain MAY have a set of distribution restrictions that apply to all distance vector messages generated by that domain, as well as sets of distribution restrictions that apply to distance vector messages generated by other domains 🧩.

As a distance vector message propagates among domains, each routing entity SHOULD exercise the distribution restrictions associated with each domain constituting the route constructed thus far. In particular, a routing entity SHOULD send an accepted distance vector message to a given neighbor only if distribution of that message to that neighbor is not precluded by any domain contained in the route 🚦.

To enable a routing entity to exercise these distribution restrictions, each domain MUST permit other domains access to its routing information distribution restrictions. However, we expect that domains MAY prefer to keep distribution restrictions private, just like source policies 🙈. There are at least two ways to make a domain's routing information distribution restrictions generally available to other domains 💜:

  • Prior to propagation of an accepted distance vector message, a routing entity includes in the message its domain's distribution restrictions (all of them, or only those that apply to the given message). This method requires no additional protocol for disseminating the distribution restrictions, but it MAY significantly increase the size of each distance vector message.
  • Each domain independently disseminates its distribution restrictions to all other domains, so that each domain will be able to exercise all other domains' distribution restrictions. This method requires an additional protocol for disseminating the distribution restrictions, and it MAY require a significant amount of memory at each routing entity for storing all domains' distribution restrictions.

We note that a domain administrator MAY describe the optimal distribution pattern of distance vector messages originating in its domain, as a directed graph rooted at its domain 🗺️. Furthermore, if all domains in the directed graph honor the directionality and the graph is also acyclic, no routing loops MAY form, because no two domains are able to exchange distance vector messages pertaining to the same destination ✨. However, an acyclic graph also means that some domains MAY be unable to discover alternate paths when connectivity between adjacent domains fails, as we show below 😬.

We reconsider the example from section 2.1.1. Suppose that the distance vector distribution graph for AD Z is such that all distance vectors originating in AD Z flow toward AD V. In particular, distance vectors from AD Z enter AD W from AD X and AD Y, and leave AD W for AD V. Now, suppose that the link between AD Z and AD X breaks. AD X no longer has knowledge of any viable route to AD Z, although such a route exists through AD W. To ensure discovery of alternate routes to AD Z during connectivity failures, the distance vector distribution graph for AD Z MUST contain bidirectional links between AD W and AD X, and between AD W and AD Y 🫶🔥

Okay so with link state routing info distribution, every recipient of a domain's link state message gets to know that domain's transit policies, and therefore its service restrictions 👀. For efficiency or privacy reasons, a domain can also restrict which domains its link state messages get sent to 🙈. So a domain is in complete control of distributing its routing info and of restricting who gets it 💅.

A domain's link state messages automatically travel to all other domains if no distribution restrictions are imposed 🌍. To make sure that distribution restrictions, when they're imposed, actually get applied 🔒, the domain may use source specified forwarding for its link state messages. That way the messages only get distributed and interpreted by the destination domains they were meant for ✨. Only those domains receive that domain's link state messages, so only they learn about its service offerings 💜.

IDPR went with link state for distributing routing info, and here's why 🫶:

  • A domain has complete control over the distribution of its own routing information.
  • Routing information distribution restrictions may be kept private and hence need not be distributed. Thus, there are no memory, processing, or transmission bandwidth costs incurred for distributing and storing distribution restrictions.

2.3. Message Forwarding along Policy Routes 🎀

To move data messages along a chosen policy route 🧚, a routing entity may use either hop-by-hop or source specified message forwarding.

2.3.1. Hop-by-Hop Approach 🌸

With hop-by-hop forwarding, each routing entity makes its own independent forwarding decision. It bases that on the message's source, destination, and requested services, plus whatever's in its forwarding information database 🗂️. Hop-by-hop forwarding only follows a source-selected policy route if all routing entities along the route have consistent routing info and use it consistently when generating and selecting policy routes and when establishing forwarding info. In particular, all domains along the route need consistent info about the source domain's source policies, plus consistent (but not necessarily complete) info about transit policies and domain adjacencies within the Internet. In general, this means each domain should know all other domains' source policies, transit policies, and domain adjacencies 🧠.

When hop-by-hop forwarding runs with inconsistent routing info, the route data messages actually traverse may not only differ from the route the source selected, but may also contain loops 🌀. Private source policies and restricted distribution of routing info are two potential causes of these inconsistencies among domains in the policy routing context 🕵️. We also expect inconsistencies in a large Internet, whether or not it supports policy routing, because some domains may not want to, or may not be able to, store routing info from the entire Internet 📚.

2.3.1.1. A Clarification 💀

In a previous draft, we presented an example that results in persistent routing loops when hop-by-hop message forwarding is used with distance vector routing info distribution and route selection. Here's the sequence of events 👀:

  • AD X receives a distance vector message containing a route to AD Z, which does not include AD Y. AD X selects and distributes this route as its primary route to AD Z.
  • AD Y receives a distance vector message containing a route to AD Z, which does not include AD X. AD Y selects and distributes this route as its primary route to AD Z.
  • AD X eventually receives the distance vector message containing the route to AD Z, which includes AD Y but not AD X. AD X prefers this route over its previous route to AD Z and selects this new route as its primary route to AD Z.
  • AD Y eventually receives the distance vector message containing the route to AD Z, which includes AD X but not AD Y. AD Y prefers this route over its previous route to AD Z and selects this new route as its primary route to AD Z.

So AD X selects a route to AD Z that includes AD Y, and AD Y selects a route to AD Z that includes AD X 😭.

Now suppose all domains along the route AD X selected, except AD Y, make forwarding decisions consistent with AD X's route. Also suppose all domains along the route AD Y selected, except AD X, make forwarding decisions consistent with AD Y's route. Neither AD X's selected route nor AD Y's selected route contains a loop 🤔. Still, data messages destined for AD Z and forwarded to either AD X or AD Y will keep circulating between AD X and AD Y until there's a route change 🔁. The reason is that AD X and AD Y have conflicting notions of the route to AD Z, with each domain existing as a hop on the other's route 🙃.

We note that while BGP-3 [8] is susceptible to such routing loops, BGP-4 [9] is not. We thank Tony Li and Yakov Rekhter for their help in clarifying this difference between BGP-3 and BGP-4 🫶.

2.3.2. Source Specified Approach 🦋

With source specified forwarding, the source domain dictates the forwarding decisions to the routing entities in each intermediate domain. Those entities then forward data messages according to the source specification. So the source domain makes sure any data message originating within it follows its selected routes 👑.

For source specified message forwarding, each data message must carry either an entire source specified route or a path identifier. Including the complete route in each data message costs a per-message transmission and processing cost for transporting and interpreting the source route 📦. Path identifiers don't incur these costs ✨. However, to use path identifiers, the source domain must initiate a path setup procedure before data message forwarding. That procedure forms an association between the path identifier and the next hop in the routing entities in each domain along the path. So path setup may impose an initial delay before data message forwarding can begin ⏳.

We have selected source specified message forwarding for IDPR data messages for the following reasons 💖:

  • Source specified message forwarding respects the source policies of the source domain, regardless of whether intermediate domains along the route have knowledge of these source policies.
  • Source specified message forwarding is loop-free, regardless of whether all domains along the route maintain consistent routing information.

Also, we have chosen path identifiers over complete routes to affect source specified message forwarding, because of the reduced transmission and processing cost per data message 🧚.

3. The IDPR Architecture ✨

Okay, now the fun part 🎀! We present the architecture for IDPR, including a description of the IDPR functions, the entities that perform those functions, and the features of IDPR that help it accommodate Internet growth 📈.

3.1. IDPR Functions 💅

Inter-domain policy routing 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.

3.2. IDPR Entities 🦋

okay so from IDPR's point of view, the internet is basically a bunch of administrative domains 💅 linked together by "virtual gateways" (more on those in a sec 🧚). Inside each domain, intra-domain routes carry the traffic and follow the transit policies the domain admins set up 🎀. Each domain administrator defines the set of transit policies that apply across their domain, plus the virtual gateways each policy applies between. Several different transit policies MAY be configured for the intra-domain routes connecting a pair of virtual gateways. A transit policy between two virtual gateways MAY also be directional 🙈. That means it can apply to traffic flowing one way between them but not the other way. Very precise, very iconic ✨

Virtual gateways (VGs) are the only connecting points IDPR recognizes between adjacent administrative domains 👑. Each virtual gateway is actually a collection of directly-connected "policy gateways" (more on these below) in two adjacent domains, and it only exists if the administrators of both domains have signed off on it 🫶. Domain administrators MAY agree to set up more than one virtual gateway between their domains. Say two domains are connected at two places that are super far apart 🌍. The admins MAY want to keep those spots separate at the inter-domain level, so they make two distinct virtual gateways. That's a power move 💜.

Policy gateways (PGs) are the physical gateways inside a virtual gateway 🔌. Each policy gateway forwards transit traffic according to the service restrictions set by its domain's transit policies that apply to its virtual gateway. A single policy gateway MAY belong to multiple virtual gateways 🧩. Within a domain, two policy gateways are "neighbors" if they're in different virtual gateways. Within a virtual gateway, two policy gateways are "peers" if they're in the same domain, and "adjacent" if they're in different domains. Peer policy gateways MUST be able to communicate over intra-domain routes that support the transit policies that apply to their virtual gateways, no excuses 😤. Adjacent policy gateways are "directly connected" if they're the only Internet addressable entities attached to the connecting medium. Note that this definition means it's not just point-to-point links that can do the job. Multiaccess networks MAY also serve as direct connections between adjacent policy gateways 🦋.

Combining multiple policy gateways into a single virtual gateway gets you three big wins 🏆:

  • A reduction in the amount of IDPR routing information that has to be distributed and maintained throughout the Internet.
  • An increase in the reliability of IDPR routes, thanks to redundant physical connections between domains.
  • An opportunity for load sharing of IDPR traffic among policy gateways.

Several different entities are responsible for performing the IDPR functions, and each one has its own job 🧚:

  • Policy gateways collect and distribute routing information, take part in path setup, forward data messages along established paths, and maintain forwarding information databases.
  • "Path agents" act on behalf of hosts to select policy routes, set up and manage paths, and maintain forwarding information databases.
  • Special-purpose servers maintain all the 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. Each route server also generates policy routes on behalf of its domain. It uses entries from its routing information database, plus source policy information that comes from configuration or straight from the path agents 💅.
    • Each "mapping server" is responsible for its database of mappings that resolve Internet names and addresses to administrative domains 🗺️.
    • 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. That configuration information covers source and transit policies, plus mappings between local IDPR entities and their Internet addresses 📋.

To maximize IDPR's manageability, one SHOULD embed all of IDPR's REQUIRED functionality within the IDPR protocols and procedures. But to minimize duplication of implementation effort, one SHOULD take advantage of REQUIRED functionality that's already provided by mechanisms outside of IDPR 🧠. Two cases are the big examples here: the mapping server functionality and the configuration server functionality. The mapping server's functions can be folded into an existing name service such as the DNS, and the configuration server's functions can be folded into the domain's existing network management system. Efficiency era 🍓.

Within the Internet, only policy gateways, path agents, and route servers MUST be able to generate, recognize, and process IDPR messages. The existence of IDPR is totally invisible to all other gateways and hosts 🫥. Mapping servers and configuration servers perform necessary but ancillary functions for IDPR, and they are NOT REQUIRED to execute the IDPR protocols. Background characters, but make it iconic 💜.

3.2.1. Path Agents 🌸

Any Internet host can reap the benefits of IDPR, as long as there's a path agent configured to act on its behalf and a way for the host's messages to reach that path agent 🦋. Path agents select and set up policy routes for hosts, taking service requirements into account. To get a host's service requirements, a path agent MAY either consult its configured IDPR source policy information or pull the service requirements straight out of the host's data messages. That second option only works if the information is actually in those data messages 👀.

Separating the path agent functions from the hosts means host software doesn't need to be modified to support IDPR, which is so relieving 🙌. It also means one path agent can bundle traffic from several different hosts onto a single policy route, as long as the source domains, destination domains, and service requirements are all the same for those host traffic flows. Policy gateways are the natural choice for the entities that handle path agent functions on behalf of hosts, since policy gateways are the only inter-domain connecting points IDPR recognizes 💅.

Each domain administrator decides which hosts their domain's path agents will handle. We expect a domain administrator will normally configure path agents in their domain to act on behalf of their domain's hosts only 🏠. But a path agent can be configured to act on behalf of any Internet host, and this flexibility lets one domain act as an IDPR "proxy" for another domain 🤝. Picture a small stub domain that wants policy routing for a few of its hosts but doesn't want to set up its whole domain for full IDPR functionality. That stub domain MAY wish to have policy routing available to a few of its hosts, and it MAY not want to support all of IDPR. Its administrator can negotiate the proxy function with the administrator of another domain, who agrees that their domain will provide policy routes on behalf of the stub domain's hosts. Teamwork makes the dream work 💖.

If a source domain supports IDPR and limits all of its domain egress points to policy gateways, then every message a host in that source domain sends to a host in another domain MUST pass through at least one policy gateway, and therefore one path agent, in the source domain 🚪. A host doesn't need to know how to reach any policy gateways in its domain. It only needs to know how to reach a gateway on its own local network. Gateways within the source domain direct inter-domain host traffic toward policy gateways, using default routes or routes derived from other inter-domain routing procedures 🧭.

If a source domain doesn't support IDPR and needs an IDPR proxy domain to give its hosts policy routing, the administrator of that source domain MUST carefully choose the proxy domain 🧐. All the gateways in between hosts in the source domain and path agents in the proxy domain forward traffic according to default routes or routes derived from other inter-domain routing procedures. For traffic from hosts in the source domain to reach the proxy domain with no special intervention, the proxy domain MUST lie on an existing non-IDPR inter-domain route from the source domain to the destination domain. So, to cut down on how much the domain administrator has to know about inter-domain routes when picking a proxy domain, we recommend picking the proxy domain from the set of adjacent domains 🗺️💡.

In either case, the first policy gateway to receive messages from an inter-domain traffic flow that starts in the source domain acts as the path agent for the host generating that flow 👑. Main character energy, and it's giving efficiency 💅✨.

3.2.2. IDPR Servers ✨

Okay so, IDPR servers are the entities that manage the IDPR databases and answer queries from policy gateways or other servers 💅 Each IDPR server MAY be a dedicated device, physically separate from the policy gateway, or it MAY be part of the policy gateway itself 🎀 Splitting the server functions away from the policy gateways cuts their processing and memory needs and boosts how much data traffic they can carry 🚀

The following IDPR databases: routing information, route, mapping, and configuration, MAY be distributed hierarchically, with partial redundancy throughout the Internet 🌸 That means there's a hierarchy of servers, and a server's spot in it decides how big its database is 🪜 At the bottom are the "local servers" that keep info for a single domain 🏠 At the top are the "global servers" that keep info for all domains in the Internet 🌈 There MAY be zero or more levels in between the local and global levels 💜

Hierarchical organization is lowkey a huge relief for most IDPR servers, since they don't have to carry info about big chunks of the Internet that their clients will never ask for 😭 Distributed databases with redundancy let clients spread their queries across servers, so no single server gets crushed 💪 And if you can't reach one IDPR server, that doesn't mean the whole service is gone, because a client MAY obtain the information from another server 🫶 We note that some IDPR databases, such as the mapping database, MAY grow so large that storing the entire thing on any single server isn't feasible 🙈

Good news: IDPR routing information databases don't need to be completely consistent to generate and use policy routes properly 🧠 That's because message forwarding along policy routes is completely specified by the source path agent ✨ Since there's no requirement for consistency, there's also no requirement for strict synchronization, which would be costly in message processing and transmission bandwidth 💸 Still, each IDPR route server SHOULD have a query/response mechanism for making its routing information database consistent with that of another route server, if necessary 🔁 A route server uses this mechanism to update its database after it detects a gap or potential error, like when it returns to service after being disconnected from the Internet 🔌

Now, a route server in one domain that wants to talk to a route server in another domain MUST establish a policy route to the other route server's domain 🛣️ To set that up, the route server MUST know the other route server's domain, and it MUST have enough routing information to construct a route to that domain 🧩 Route servers MAY often intercommunicate to get routing info, so you might expect a deadlock 🙃 where one route server needs routing info from another but doesn't have enough mapping and routing info to establish a policy route to it. Thankfully, such a deadlock SHOULD seldom persist, if the following IDPR functionality is in place 🌷

  • A mechanism that lets a route server gain access, during route server initialization, to the identities of the other route servers within its domain 📇 With this info, the route server need not establish policy routes just to query those route servers for routing information.
  • A mechanism that lets a route server gain access, during route server initialization, to its domain's adjacencies 🗺️ With this, the route server MAY establish policy routes to the adjacent domains to query their route servers for routing information when none is available within its own domain.
  • Once operational, a route server SHOULD collect (memory capacity permitting) all the routing information it can access 📦 A domain usually doesn't restrict distribution of its routing information. Instead, it distributes it to all other Internet domains 📣 So a route server in a given domain is likely to receive routing information from most Internet domains 🌍
  • A mechanism that lets an operational route server obtain the identities of external route servers it can get routing information from, plus the domains containing those route servers 🔍 This mechanism SHOULD NOT require mapping server queries 🙅 Rather, each domain SHOULD distribute, in its routing information messages, the identities of all route servers within its domain that MAY be queried by clients outside of its domain 💌

When a host in one domain wants to talk to a host in another domain, the path agent in the source domain MUST establish a policy route to a path agent in the destination domain 🛤️ But first, the source path agent MUST first query a mapping server to determine the identity of the destination domain 🔎 The queried mapping server MAY in turn contact other mapping servers to get a reply 📞 Just like with route servers, you could imagine a deadlock 😵‍💫 where a mapping server needs mapping information from an external mapping server, but the path agent handling the traffic doesn't have enough mapping info to determine that server's domain, and so can't establish a policy route to it.

We already covered how to minimize deadlock when obtaining routing information 🙌 For mapping info, there SHOULD be a mechanism that lets a mapping server gain access, during mapping server initialization, to the identities of other mapping servers and the domains they reside in 🧸 That way, when a mapping server needs to query an external mapping server, it already knows that server's identity and sends a message 💌 The path agent handling this traffic queries a local mapping server to resolve the external mapping server's identity to the proper domain, then proceeds to establish a policy route to that domain 🏁

3.2.3. Entity Identifiers 🪪

Every domain gets a unique identifier within the Internet 🌐 It's an ordinal number in the enumeration of Internet domains, determined by the Internet Assigned Numbers Authority (IANA), who is responsible for maintaining that information 📜

Each virtual gateway has a unique local identifier within a domain 🚪 It's derived from the adjacent domain's identifier together with the virtual gateway's ordinal number within an enumeration of the virtual gateways connecting the two domains 🔗 The administrators of both domains mutually agree upon that enumeration 🤝 Picking one enumeration that applies in both domains means nobody has to maintain a mapping between separate virtual gateway ordinal numbers in each domain 🧠

Each policy gateway and route server gets a unique local identifier within its domain 🏷️ It's an ordinal number in the domain administrator's enumeration of IDPR entities within that domain 💅 Combine it with the domain identifier and boom, you get a unique identifier within the Internet for that policy gateway or route server 🎉

3.3. Security and Reliability 🔐

Here's the big deal 🚨 The correctness of control information, and in particular routing-related information, distributed throughout the Internet is a critical factor in the Internet's ability to transport data 📡 As the number and heterogeneity of Internet domains grows, so does the potential for both information corruption and denial of service attacks 😬 So we imbued the IDPR architecture with a variety of mechanisms to:

  • Promote timely delivery of control information ⏰
  • Minimize acceptance and distribution of corrupted control information 🧹
  • Verify authenticity of a source of control information 🪪
  • Reduce the chances for certain types of denial of service attacks 🛡️

Consult [11] for a general security architecture for routing and [12] for a security architecture for inter-domain routing 📚

3.3.1. Retransmissions and Acknowledgements 📬

Okay, this one's serious 🥺 All IDPR entities MUST make an effort to accept and distribute only correct IDPR control messages 💯 Each IDPR entity that transmits an IDPR control message expects an acknowledgement from the recipient, and it MUST retransmit the message up to a maximum number of times when no acknowledgement is forthcoming 🔁 An IDPR entity that receives an IDPR control message MUST verify message content integrity and source authenticity before accepting, acknowledging, and possibly redistributing the message 🕵️

3.3.2. Integrity Checks 🧐

Integrity checks on message contents help promote the detection of corrupted information 🔎 Each IDPR entity that receives an IDPR control message MUST perform several integrity checks on the contents 📋 Individual IDPR protocols MAY apply more stringent integrity checks than those listed below 💪 The REQUIRED checks include confirmation of:

  • Recognized message version ✅
  • Consistent message length 📏
  • Valid message checksum 🧮

Each IDPR entity MAY also apply these integrity checks to IDPR data messages 📦 Although the IDPR architecture only requires data message integrity checks at the last IDPR entity on a path, it does not preclude intermediate policy gateways from performing these checks as well 🧃

3.3.3. Source Authentication 🕵️‍♀️

Authenticating a message's source promotes the detection of a rogue entity masquerading as another legitimate entity 🥷 Each IDPR entity that receives an IDPR control message MUST verify the authenticity of the message source 🛂 We recommend that the source of the message supply a digital signature for authentication by message recipients 🖋️ The digital signature SHOULD cover the entire message contents (or a hash function of them), so that it can serve as the message checksum as well as the source authentication information 💖

Each IDPR entity MAY also authenticate the source of IDPR data messages 🔐 However, the IDPR architecture does not require source authentication of data messages 🙃 Instead, we recommend that higher level (end-to-end) protocols, not IDPR, assume responsibility for data message source authentication 🫶 because verifying a digital signature takes a lot of computation 🧮

3.3.4. Timestamps ✨

okay so timestamps are how we catch outdated messages AND sneaky replays 🕵️‍♀️💅 Each IDPR control message MUST carry a timestamp supplied by the source, and that timestamp basically tells you how old the message is 🕰️ IDPR entities check the absolute value to confirm a message is still current, and they compare timestamps against each other to figure out which message has the freshest info 🦋 Which means all IDPR entities MUST possess internal clocks that are synced to some degree, otherwise the absolute value of a message timestamp means nothing 🙈 The sync granularity IDPR needs is on the order of minutes, and it can be done manually. So chill, honestly 🌸

Every IDPR entity that gets an IDPR control message MUST check that it's timely, bestie 💖 Any control message with a timestamp outside the acceptable range might be stale or corrupted, or it might have come from a source whose internal clock fell out of sync with the recipient's clock 😭

IDPR data messages carry timestamps too, but the IDPR architecture doesn't require timestamp acceptability checks on them ✨ Instead, we recommend that IDPR entities only check data message timestamps during problem diagnosis, like when they're looking into suspected message replays 🔍 ngl that's the move.

3.4. An Example of IDPR Operation

okay let's walk through an example so you can see IDPR in action 🎀 In this one we assume every domain supports IDPR, and every domain egress point is a policy gateway 💜

Say host Hx in domain AD X wants to talk to host Hy in domain AD Y. Hx doesn't need to know its own domain's identity, or Hy's domain, to send messages to Hy 🧚 It just forwards the message bound for Hy to one of the gateways on its local network, based on its local forwarding info. If that gateway is a policy gateway, the resident path agent figures out how to forward the message outside the domain. If it isn't, the gateway passes the message to another gateway in AD X using its local forwarding info. Eventually the message lands at a policy gateway in AD X, as described earlier in section 3.2.1 ✨

The path agent in the receiving policy gateway checks the message header, including source and destination addresses and any requested service info (like type of service), to figure out two things: is it intra-domain or inter-domain, and if it's inter-domain, does it need an IDPR policy route? 🧐 Specifically, the path agent tries to find a forwarding information database entry for that traffic flow. The forwarding info database should already have entries for:

  • All intra-domain traffic flows. Intra-domain forwarding information goes into the forwarding database as soon as it's received 🏡
  • Inter-domain traffic flows that don't need IDPR policy routes. Non-IDPR inter-domain forwarding info goes in as soon as it's received 🌐
  • IDPR inter-domain traffic flows that already have a path set up. IDPR forwarding information only gets integrated during path setup 🛤️

The path agent uses the message header contents to guide its search for a forwarding info database entry, and we suggest a radix search to find one 🌳 When the search ends, it either produces a forwarding info database entry, or a directive to generate one for an IDPR traffic flow. If the search ends at an existing entry, the path agent forwards the message according to that entry 💅

Now suppose the search says the traffic flow between Hx and Hy needs an IDPR route, and there's no entry for it yet. Then the path agent first figures out the source and destination domains tied to the message's addresses, before it tries to get a policy route 🗺️ It relies on mapping servers for domain info, but it caches all mapping server responses locally to limit future queries 💾 When resolving an address to a domain, it always checks its local cache before contacting a mapping server 🙌

After getting the source and destination domain info, the path agent tries to get a policy route to carry traffic from Hx to Hy 🚀 It relies on route servers for policy routes and caches all route server responses locally too, to limit future queries. When looking for a suitable policy route, it consults its local cache before contacting a route server. A cached policy route counts as suitable provided its associated source domain is AD X, its associated destination domain is AD Y, and it satisfies the service requirements in the data message or in source policy configuration ✨

If no suitable cache entry exists, the path agent queries the route server, giving it the source and destination domains plus the requested services 📨 When a route server gets a policy route query, it consults its route database. If it can't find a suitable route there, it tries to generate at least one route to domain AD Y, consistent with the services requested for Hx 🧠

A successful route query gets back a set of candidate routes, and the path agent makes its pick from them. We expect a path agent will normally choose a single route from that set, but the IDPR architecture doesn't stop a path agent from selecting multiple routes. A path agent might want multiple routes for things like fault tolerance or load balancing, though the IDPR architecture doesn't specify how the path agent should use multiple routes 🎯 Either way, a route server always sends back a response to a path agent's query, even if it didn't manage to find a suitable policy route 💌

If the policy route is a brand-new one from the route server, there's no existing path for it, so the path agent MUST set up such a path. But if the policy route is an existing route pulled from the path agent's cache, there might already be a path for it, set up for a different host traffic flow 🔁 The IDPR architecture lets multiple host traffic flows share the same path, as long as all the flows on that path travel between the same endpoint domains and have the same service requirements 🤝 It also doesn't stop a path agent from setting up distinct paths along the same policy route, so it can keep host traffic flows separate 🛣️

The path agent associates an identifier with the path. That identifier goes in every message traveling down the path, and the policy gateways along the path use it to decide how to forward the message. If the path already exists, the path agent uses the preexisting identifier. For new paths, though, it chooses a path identifier that's different from every other path it manages 🏷️ It also updates its forwarding info database to reference the path identifier, and it modifies its search procedure so it lands on the correct entry for a given data message header 💜

For new paths, the path agent starts path setup by communicating the policy route to policy gateways in intermediate domains. That includes the requested services, constituent domains, relevant transit policies, and the connecting virtual gateways 📮 Using this info, an intermediate policy gateway decides whether to accept or refuse the path, and which policy gateway to forward the path setup info to. The path setup procedure lets policy gateways set up a path in both directions simultaneously ↔️ After accepting a path, each intermediate policy gateway updates its forwarding info database with an entry linking the path identifier to the appropriate previous and next hop policy gateways 🔗 Paths stick around until they're torn down, whether because of failure, expiration, or when resources are scarce and the path gets preempted in favor of other paths 💀

When a policy gateway in AD Y accepts a path, it notifies the source path agent in AD X ✨ We expect the source path agent will normally wait until the path has been successfully established before using it to carry data traffic. But the IDPR architecture doesn't stop a path agent from forwarding data messages along a path before path establishment is confirmed 👀 In that case, the source path agent sends data messages along the path knowing the path might not yet be established at all intermediate policy gateways, so those data messages will be immediately discarded by any policy gateway that can't recognize the path identifier yet 🗑️

Data communication between Hx and Hy may happen over two separate IDPR paths: one from AD X to AD Y, and one from AD Y to AD X 🦋 Why? Inside a domain, hosts know nothing about path agents or IDPR paths, and path agents know nothing about other path agents' existing IDPR paths 🙃 So in AD Y, the path agent that terminates the path from AD X might not be the same path agent that receives traffic from Hy destined for Hx. In that case, receiving traffic from Hy forces the second path agent to set up a new path from AD Y to AD X 💅

4. Accommodating a Large, Heterogeneous Internet ✨

The IDPR architecture MUST be able to accommodate an Internet containing O(10,000) domains, supporting diverse source and transit policies 🌍 So we gave the IDPR architecture lots of features that let it function effectively in an environment like that 👑

4.1. Domain Level Routing 🌸

okay bestie, so the IDPR architecture does policy routing among administrative domains 🦋. It's domain to domain, not box to box. And the best part is that route servers only need routing information at the domain level. No intra-domain details go in IDPR routing information 💅.

So the size of a route server's routing information database doesn't depend on how many Internet gateways, networks, and links there are. It depends on how those things get grouped into domains and what services they offer ✨. That means the number of entries depends on the number of domains and the number and size of the transit policies those domains support 🔥.

Policy gateways only distribute IDPR routing information when detectable inter-domain changes occur. They may also elect to distribute it periodically (for example, on the order of once per day) as a backup 🧚. We expect that a pair of policy gateways within a domain will normally be connected so that when the primary intra-domain route between them fails, the intra-domain routing procedure can construct an alternate route 🫶. So an intra-domain failure is unlikely to be visible at the inter-domain level, and unlikely to force an inter-domain routing change. Therefore, policy gateways will not often generate and distribute IDPR routing information messages 💜.

IDPR entities rely on intra-domain routing procedures operating within domains to carry inter-domain messages across domains 🌈. Hence, IDPR messages must appear well-formed according to the intra-domain routing and addressing procedures in each domain traversed. Recall that source authentication information (refer to section 3.3.3 above) may cover the entire IDPR message. So the IDPR portion of such a message cannot be modified at intermediate domains along the path without causing source authenticity checks to fail 😭. That's why, at domain boundaries, IDPR messages require encapsulation and decapsulation according to the routing procedures and addressing schemes operating within the given domain 🎀.

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 message. Thus, for the Internet to support IDPR, only a small proportion of Internet entities require 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 service requirements are compatible 🍓. The size of the forwarding information database maintained by a policy gateway doesn't depend on the number of Internet hosts. It depends on how those hosts are grouped into domains, which hosts intercommunicate, and how much distinction a source domain wants to preserve among its traffic flows 💅. So the number of entries in an IDPR forwarding information database depends on the number of domains and the number of source policies supported by those domains. Plus, memory tied to failed, expired, or disused paths can be reclaimed for new paths, which means forwarding information for many paths can fit in a policy gateway's forwarding information database 🦋.

4.2. Route Generation 🧠

Route generation is the most computationally complex part of IDPR 💀, because of the number of domains and the number and heterogeneity of policies it has to accommodate. Route servers must generate policy routes that satisfy the requested services of the source domains and respect the offered services of the transit domains ✨.

We distinguish requested qualities of service and route generation with respect to them as follows:

  • Requested service limits include upper bounds on route delay, route delay variation, and monetary cost for the session, and lower bounds on available route bandwidth. Generating a route that must satisfy more than one quality of service constraint, for example route delay of no more than X seconds and available route bandwidth of no less than Y bits per second, is an NP-complete problem 🙈.
  • Optimal requested services include minimum route delay, minimum route delay variation, minimum monetary cost for the session, and maximum available route bandwidth. In the worst case, the computational complexity of generating a route that is optimal with respect to a given requested service is O((N + L) log N) for Dijkstra's shortest path first (SPF) search and O(N + (L * L)) for breadth-first (BF) search, where N is the number of nodes and L is the number of links in the search graph 🌸. Multi-criteria optimization, for example finding a route with minimal delay variation and minimal monetary cost for the session, may be defined in several ways. One approach is to assign each link a single value equal to a weighted sum of the values of the individual offered qualities of service, then generate a route that is optimal with respect to this new criterion. However, it may not always be possible to achieve the desired route generation behavior using such a linear combination of qualities of service 🥴.

To help contain the combinatorial explosion of processing and memory costs tied to route generation, we supply the following guidelines for generating suitable policy routes 🫧:

  • Each route server should only generate policy routes from the perspective of its own domain as source. It need not generate policy routes for arbitrary source/destination domain pairs. Thus, we can distribute the computational burden over all route servers 🤝.
  • Route servers should precompute routes for which they anticipate requests, and should generate routes on demand only in order to satisfy unanticipated route requests. Hence, a single route server can distribute its computational burden over time ⏳.
  • Route servers should cache the results of route generation, in order to minimize the computation associated with responding to future route requests 🧁.
  • To handle requested service limits, a route server should always select the first route generated that satisfies all of the requested service limits 🎯.
  • To handle multi-criteria optimization in route selection, a route server should generate routes that are optimal with respect to the first specified optimal requested service listed in the source policy. The route server should resolve ties between otherwise equivalent routes by evaluating these routes according to the other optimal requested services, in the order in which they are specified. With respect to the route server's routing information database, the selected route is optimal according to the first optimal requested service, but is not necessarily optimal according to any other optimal requested service 👀.
  • To handle a mixture of requested service limits and optimal requested services, a route server should generate routes that satisfy all of the requested service limits. The route server should resolve ties between otherwise equivalent routes by evaluating those routes as described in the multi-criteria optimization case above 🌈.
  • All else being equal, a route server should always prefer minimum-hop routes, because they minimize the amount of network resources consumed by the routes 🍃.
All domains need not execute the identical route generation procedure. Each domain administrator is free to specify the IDPR route generation procedure for route servers in its own domain, making the procedure as simple or as complex as desired 💖.

4.3. SuperDomains ✨

Okay so a "super domain" is itself an administrative domain 💅. It's made up of a bunch of contiguous domains with similar transit policies, and it only forms when the administrators of those constituent domains agree on it 🫶. The whole point is to shrink how much IDPR routing information gets passed around the Internet 🧚. If you've got n contiguous domains with consistent transit policies, the routing info for that group is roughly n times smaller when you treat the group as one super domain than when you treat it as n separate domains. That's some iconic math 📉✨.

But if the constituent domains' transit policies don't form a consistent set, you have to decide which transit policies go into the routing info for the super domain 🤔. There are two extremes, and both of them cut down the routing info for the constituent domains:

  • Option one: The transit policies the super domain supports come from the union of the access restrictions and the intersection of the qualities of service, across all the constituent domains. The super domain ends up offering fewer services than the constituent domains did, but nobody's access restrictions get broken 🛡️.
  • Option two: The transit policies the super domain supports come from the intersection of the access restrictions and the union of the qualities of service. Now the super domain offers more services than the constituent domains did, but the constituent domains' access restrictions have to get relaxed 😬.
Soooo, our recommendation is that domain administrators don't just go grouping domains into super domains willy-nilly 🙅‍♀️. Only do it if you fully understand what you're signing up for, bestie 💀.

Super domains also give the Internet a hierarchy 🌈. For model consistency, we assume there's one single super domain sitting at the very top, and it contains the set of all high-level domains 👑. A domain's identity is defined relative to that hierarchy. To be specific, a domain's identity may be defined by the domains that contain it, the domains it contains, or both 🎀.

Now, the universe of distribution for a domain's routing information (for AD X, say) usually only reaches the domains inside AD X's immediate super domain that sit at the same level of the hierarchy as AD X 🦋. That said, the IDPR architecture doesn't stop AD X from sending its routing info to domains way higher up the hierarchy, as long as the immediate super domain of those domains is also a super domain of AD X. For example, an administrator of one domain inside a super domain might want one of its transit policies advertised outside the immediate super domain, so other domains can use a quality of service the super domain doesn't offer on its own ✨. In that case, the super domain and the constituent domain can distribute routing info at the same level of the hierarchy, even though one of them actually contains the other 🤯.

One more thing, and it's a bit of a plot twist 😭. Super domains can limit how many routes are available to source domains that have access restrictions. Say a source domain AD X has source policies that keep its traffic from crossing a domain AD Y, and AD Y is contained in a super domain AD Z. If the domains inside AD Z don't advertise their routing info separately, then the route servers in AD X won't have enough info to build routes that go through AD Z but skip AD Y 💔. So the route servers in AD X have to generate routes that avoid AD Z altogether.

4.4. Domain Communities

A "domain community" is a group of domains that a given domain sends its routing information to 🫧, so domain communities can be used to limit how far routing information gets distributed 🚫. They're not just about saving money on sending and storing routing info. They also let a domain keep its routing info hidden from domains outside the community 🙈. Here's the twist: unlike a super domain, a domain community isn't necessarily an administrative domain 🧩. Also, forming a domain community may or may not need the consent of the member domains' administrators, and the community's definition can be implicit or explicit 🤷‍♀️.

Each domain administrator decides how far its domain's routing info gets distributed, so they can unilaterally define a domain community all on their own 💅. By default, that community includes all Internet domains. But the administrator can narrow the membership by describing the community as a neighborhood (defined, for example, in terms of domain hops) or as a list of member domains 📝.

A group of domain administrators can also mutually agree on how their domains' routing info gets distributed among themselves, and that's how they multilaterally define a domain community 🤝. Again, by default it includes all Internet domains. The administrators can restrict membership by describing the community as a list of member domains. And honestly? This kind of domain community could work as a multicast group for distributing routing info 📡✨.

4.5. Robustness in the Presence of Failures

The IDPR architecture has a bunch of features that make it resistant to failures in the Internet 💪🌸:

  • Multiple connections between adjacent policy gateways in a virtual gateway, and between peer and neighbor policy gateways across an administrative domain, mean fewer single-component failures show up at the inter-domain level 🧵.
  • Policy gateways send out IDPR routing information right after they detect a connectivity failure at the inter-domain level, and route servers immediately fold that info into their routing information databases 🚨. This means new policy routes won't include the domains that were involved in the connectivity failure 🙅‍♀️.
  • The routing information database query/response mechanism quickly updates the routing information database for a route server that previously failed, once that route server reconnects to the Internet 🔄.
  • To keep user service from getting disrupted when the primary path fails, policy gateways try local path repair right after detecting a connectivity failure 🛠️. On top of that, path agents may keep standby alternate paths that can take over as the primary path if needed 🦸‍♀️.
  • Policy gateways inside a domain keep an eye on domain connectivity all the time, so they can detect and identify domain partitions 👀. And IDPR can keep operating properly even when domains get partitioned 🎀.

4.5.1. Path Repair

Okay so if one or more entities on a policy route fail, the route might not be usable anymore 😩. If the failure is inside a domain, IDPR counts on the intra-domain routing procedure to find an alternate route across that domain, and the path itself stays the same 🧭. But if the failure is in a virtual gateway, policy gateways have to take responsibility for repairing the path 🛠️. The policy gateways closest to the failure are the first to notice it, so they can react the fastest to fix the path ⚡.

Now, handing path repair over to policy gateways in other domains might not be okay with some domain administrators 😬. The reason is that those policy gateways can't guarantee they'll build a path that satisfies the source policies of the source domain, since they have no idea what other domains' source policies say 🙃.

Even so, limited local path repair is doable 🌟. It can happen without spreading source policy information across the whole Internet, and without sharing detailed path information among policy gateways in a domain or in a virtual gateway 🫶. We say a path is "locally repairable" if there's an alternate route between two policy gateways that are separated by at most one policy gateway on the path 🔍. This definition covers path repair when routes between consecutive policy gateways fail, as well as when the policy gateways themselves fail 💖.

Here's how it goes: a policy gateway attempts local path repair, working in the forward direction of the path, as soon as it notices the next policy gateway on the path is no longer reachable 🏃‍♀️. The policy gateway has to hang on to enough of the original path setup information to repair the path locally 🧠. Using that setup info, it tries to find a route around the unreachable policy gateway. Specifically, it tries to make contact with either:

  • A peer of the unreachable policy gateway. In this case, the contacted policy gateway tries to find the next policy gateway after the unreachable one, on the original path 🔎.
  • A peer of itself, if the unreachable policy gateway is an adjacent policy gateway and the policy gateway doing the repair no longer has direct connections to any adjacent policy gateways 🥺. In this case, the contacted policy gateway tries to find a peer of the unreachable policy gateway, and that peer then tries to find the next policy gateway after the unreachable one, on the original path 🧚‍♀️.

If it successfully reaches the next policy gateway, the contacted policy gateway lets the requesting policy gateway know 🎉. Then the requesting, contacted, and next policy gateways all update their forwarding information databases so they match the new part of the path 🫶. But if it doesn't reach the next policy gateway, the contacted policy gateway starts tearing down the original path 💔. At that point, the source path agent is the one responsible for finding a new route to the destination 🦋.

4.5.2. Partitions 🧩

okay so a "domain partition" 💔 happens whenever there are at least two entities inside the domain that can no longer reach each other over ANY intra-domain route. ngl that's a whole lot of drama. And it's not just the inside that suffers, because partitions can also mess with inter-domain communication, especially when the partitioned domain is a transit domain 😭. So IDPR was built to keep partitioned domains usable and to maximize Internet connectivity even when a partition happens ✨ iconic.

When a domain gets partitioned, it splits into multiple distinct "components" 🫧. A domain component is a subset of the domain's entities where everyone in the subset can reach each other via intra-domain routes, but nobody outside the subset is reachable from inside it via intra-domain routes. Each component gets its own unique identifier: the identifier of the domain plus the ordinal number of the lowest-numbered operational policy gateway within that component 🆔. No negotiation is needed to figure out which gateway that is! Every policy gateway in the component discovers mutual reachability through intra-domain reachability information, so they all end up with the same view of who the lowest-numbered operational policy gateway is. periodt 💅

IDPR entities can detect and compensate for all domain partitions that isolate at least two groups of policy gateways from each other 🙌. They cannot, however, detect any domain partition that isolates groups of hosts only 🙈. Also, a partition can split a virtual gateway so its peer policy gateways end up in separate domain components. Even though the virtual gateway is now partitioned, it doesn't pick up any extra identities. From the adjacent domain's point of view, though, that virtual gateway now connects to two separate domain components 🦋.

Policy gateways use partition information to select routes across virtual gateways to the correct domain components 🗺️. They also pass partition information along to route servers as part of the IDPR routing information, so route servers know which domains are partitioned. Route servers do NOT know which hosts live in which components of a partitioned domain, because tracking that would take extensive computation and communication. Instead, when a route server discovers that the destination of a requested route is a partitioned domain, it tries to generate a suitable policy route to each component of the destination domain 🧚. Generating multiple routes like this maximizes the chances of getting at least one policy route that the source and destination hosts can actually use to communicate 🎀.

5. References 📚

  • [1] Rekhter, Y., "EGP and Policy Based Routing in the New NSFNET Backbone", RFC 1092, February 1989.
  • [2] Clark, D., "Policy Routing in Internet Protocols", RFC 1102, May 1989.
  • [3] Braun, H-W., "Models of Policy Based Routing", RFC 1104, June 1989.
  • [4] Leiner, B., "Policy Issues in Interconnecting Networks", RFC 1124, September 1989.
  • [5] Estrin, D., "Requirements for Policy Based Routing in the Research Internet", RFC 1125, November 1989.
  • [6] Little, M., "Goals and Functional Requirements for Inter-Autonomous System Routing", RFC 1126, July 1989.
  • [7] Honig, J., Katz, D., Mathis, M., Rekhter, Y., and Yu, J., "Application of the Border Gateway Protocol in the Internet", RFC 1164, June 1990.
  • [8] Lougheed, K. and Rekhter, Y., "A Border Gateway Protocol 3 (BGP-3)", RFC 1267, October 1991.
  • [9] Rekhter, Y. and Li, T. Editors, "A Border Gateway Protocol 4 (BGP-4)", Work in Progress, September 1992.
  • [10] ISO, "Information Processing Systems - Telecommunications and Information Exchange between Systems - Protocol for Exchange of Inter-domain Routeing Information among Intermediate Systems to Support Forwarding of ISO 8473 PDUs", ISO/IEC DIS 10747, August 1992.
  • [11] Perlman, R., "Network Layer Protocols with Byzantine Robustness", Ph.D. Thesis, Department of Electrical Engineering and Computer Science, MIT, August 1988.
  • [12] Estrin, D. and Tsudik, G., "Secure Control of Transit Internet-work Traffic", TR-89-15, Computer Science Department, University of Southern California.
  • [13] Garcia-Luna-Aceves, J.J., "A Unified Approach for Loop-Free Routing using Link States or Distance Vectors", ACM Computer Communication Review, Vol. 19, No. 4, SIGCOMM 1989, pp. 212-223.
  • [14] Zaumen, W.T. and Garcia-Luna-Aceves, J.J., "Dynamics of Distributed Shortest-Path Routing Algorithms", ACM Computer Communication Review, Vol. 21, No. 4, SIGCOMM 1991, pp. 31-42.

6. Security Considerations 🔐

Refer to section 3.3 for details on security in IDPR. 🛡️ This one is SERIOUS bestie, so go read that section before you ship anything 💀.

7. Author's Address 💌

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

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

the end, bestie!! 🌈🫶

📦 where this page comes from