RFC 1102

Policy Routing in Internet Protocols 🎀

Okay bestie, this is RFC 1102, and this is Part 1 of 6 ✨ It's a Request for Comments from the Network Working Group, written by D. Clark of the M.I.T. Laboratory for Computer Science, dated May 1989 📅 The header doesn't list any RFCs it obsoletes or updates, so it's just doing its own thing 🦋

1. Status of this Memo 🌸

The whole point of this RFC is to get people talking about specific problems on the Internet and possible ways to fix them 🗣️ None of the solutions in here are meant to be standards for the Internet 🙅‍♀️ and distribution of this memo is unlimited 💖

not a standard, bestie! it's a discussion starter 💅

2. Introduction 🧚

Okay so, the routing function is a core part of the Internet protocols 🌈 It decides which networks and gateways a packet goes through on its way from source to destination. Lots of routing protocols have been used on the Internet, and they all share one idea: pick one route out of all the available ones by minimizing some measure of the route, like delay ⏱️ But lately it's become important to pick routes so that certain classes of customers are the only ones using certain network resources 👑 These are called resource policies, and the existing Internet tech is pretty bad at enforcing them 💀 This document proposes a way to bake policy controls into the Internet ✨

Next up, the Internet's resources (networks, links, and gateways) get split into Administrative Regions, or ARs 🍓 Each AR has its own somewhat autonomous administration, with its own goals: which customers it wants to serve, what quality of service it promises, and how it gets its costs back 💸 To build a route across the Internet, you have to choose a sequence of ARs that together supply a path from source to destination. That sequence is called a Policy Route, or PR 🛤️ Every AR that a PR passes through is going to care that the PR was built properly 🧐 So each AR may want to make sure the user of the PR is authorized, the requested quality of service is supported, and the cost of the service can be recovered 🫶

In the abstract, a Policy Route is a series of ARs, which are assumed to have globally distinct identifiers ✨ (Global names for ARs suggest that the name space of ARs is flat. That's a simplifying assumption made in this RFC, but it should be possible to extend the scheme so ARs can nest, which would reduce the amount of global information. Adding structure to the space of ARs is an exercise for later study 📚) Before a PR can actually be used, though, it has to be reduced to more concrete terms: a series of gateways that connect the sequence of ARs 🔌 These gateways are called Policy Gateways 🚪

Presently, the closest thing to policy routing in the Internet is EGP, the Exterior Gateway Protocol 🧩 EGP was built so regions of the Internet could share reachability information even though they didn't fully trust each other 🤝 In that sense, the regions hooked together by EGP could each be viewed as Administrative Regions. But EGP's mechanisms imposed a topological restriction on how the Administrative Regions could interconnect 🙃 In practice, that has proved unsatisfactory 😭 Policy matters are driven by human concerns, and those have not turned out to be friendly to topological constraints, or to constraints of almost any sort 🙈

The proposals in this memo are designed to allow as wide a latitude as possible in building and enforcing policies 🦋 In particular, no topological restrictions are assumed. The approach here is driven by the belief that since policies reflect human concerns, the system should mainly be concerned with enforcing policy, rather than synthesizing it 🫶 The proposal lets both end points and transit services express and enforce local policy concerns 💜

3. Policy Routes 💖

Almost all approaches to policy control share, to some degree, the idea of a Policy Route 🌷 What makes a policy approach distinct is the procedure used to synthesize the Policy Route 🧪 One way to synthesize routes is to associate each distinct policy with a subset of all the gateways in the system, then run a routing algorithm across that subset. This has several drawbacks 😬 It requires a distinct routing computation for every policy, which may be prohibitively expensive 💸 It requires global agreement on the nature and scope of each policy, which clashes with the desire of Administrative Regions to set up their own independent policy assertions 🙅‍♀️ And it almost inevitably implies a topological restriction on how regions interconnect 🙃

Another synthesis approach is to have each Policy Gateway examine incoming packets and determine, based on local policy constraints, the most appropriate next AR 🤔 This might possibly work, but again it has drawbacks. First, it implies a substantial amount of computation at each Policy Gateway 🥵 More importantly, it removes route selection from the place where it would most naturally happen, which is the end points of the connection 📍

It's useful to think of the interconnected ARs as a marketplace 🛍️ where various services are offered and users pick among them to get packet transport. By that analogy, the actual selection of the Policy Route should be made by the end ARs that want to send the packets, not by the Policy Gateways 💅 Look at the phone system: the customer is the one who picks which long distance carrier to use, whether to buy a fixed price service or pay as they go, and so on 📞 So in this proposal, Policy Routes are synthesized at the end point where the packet originates, and they're attached to packets to direct them through the right series of ARs 🧭 In other words, Policy Routes are a form of source routing 🗺️ The job of synthesizing a Policy Route is shared between the source AR and the particular source host 🫂

So in this architecture, the function of the Policy Gateway isn't to synthesize the Policy Route, it's to verify it 🔍 The following sections address two questions: how a Policy Route is verified, and how a Policy Route is synthesized ✨

When you decide that Policy Routes should be synthesized at the end point, it's important to tell apart the aspects of routing that reflect legitimate policy concerns from the aspects that really relate to the detailed operation of the ARs 🧠 For example, if you represented Policy Routes with the existing Internet source route mechanism, which lets the end point specify a series of gateways the packet should pass through, then way too much function would move from the internals of the Internet out to the end points 😵 The end point would have to know exactly which gateways are up and operational at any particular moment, and that degree of knowledge cannot be justified by policy concerns 🙅‍♀️ On top of that, you'd need to run a systemwide gateway reachability protocol 📡

This proposal tries to strike a balance 🎀 The end point specifies the concerns that legitimately relate to policy, and local determination in the Policy Gateways handles the more specific details needed for reliable operation 💪 This leads to a two-level routing model. The abstract Policy Route, a series of administrative regions, is specified by the end point as a form of source route, and each Policy Gateway selects the next actual Policy Gateway to use for forwarding the packet 🚀 In other words, the abstract Policy Route is made concrete incrementally 🧩 This division of function does require that the source AR know whether there are faults that have partitioned pairs of ARs that are normally connected together 💔 That implies a global reachability protocol to be run to give information to the source AR, but it only needs to concern itself at the level of ARs, not at the level of gateways 🌍 A later section on cost-recovery discusses gateway selection in more detail 💜

An objection to a scheme like source routing is that the potentially bulky source route must be in every packet, and must be evaluated for each packet 😩 One fix for this performance problem is a limited form of route setup. The actual Policy Route is carried only in the first packet of a sequence, and a short identifier, or "handle," is included in subsequent packets of the sequence 🎫 Each Policy Gateway evaluates the PR on first encounter and caches the result 🗄️ The cached result is then retrieved for later packets using the handle in the packet 🔑 The idea of a handle and caching, and the need for a form of route setup, get discussed later 📖

4. Verification of Policy Routes 🛡️

As a packet arrives at a Policy Gateway, trying to enter an AR, the Policy Gateway must decide whether it's legitimate to forward this packet and, if so, which next Policy Gateway the packet should exit the AR through (assuming the final destination isn't within the AR) 🚦 The information the Policy Gateway has to support its decision determines the range of policies that can be enforced 📊 So deciding what information is available is a central feature of this proposal 🌟

4.1. Identifying the User 👤

Classic routing decisions, the ones that minimize some cost, are typically driven only by the destination of the packet 🎯 At a minimum, policy decisions must be based on both the source and the destination of the packet 🫵 Even then, source and destination addresses may not be enough to determine policy, because an AR may support different users with different rights 👥 and a single user may want to exercise different rights at different times ⏰ I suggest that, to identify the user proposing to use this particular Policy Route, it's sufficient for the packets to contain the source host and AR, the destination host and AR, and, optionally, a User Class Identifier, or UCI 🪪 A later section discusses how to prevent misuse of the user class identifier 🚨

In fact, the source and destination host addresses may not be needed to support the practical range of policy decisions required at intermediate ARs 🤷 Only the source and destination AR information may be necessary 🙌 If individual host addresses are used, that implies intermediate ARs will want to keep track of the rights of individual hosts 😓 It would be much simpler if the source AR could be trusted to permit only the proper hosts to use certain PRs 🥰 I'll consider this further in a later section, when I discuss the role of the Policy Controller 🔮

4.2. Verifying the Route ✨

Okay so the packet carries an abstract Policy Route, which is basically a series of AR identifiers 🦋. To validate that route, each Policy Gateway could store the complete selection of acceptable policy routes and then require that an incoming packet's Policy Route exactly matches one of the stored entries. Bestie, that is giving overkill 💀. It probably overspecifies the situation and causes an information explosion. On the other end of the scale, Policy Gateways could just be sensitive to the source AR and the destination AR. But ngl, in some cases, especially billing, that doesn't give enough constraints 🙈. So this proposal suggests that when deciding whether a given Policy Route is valid, a Policy Gateway should look at the source and destination ARs, and also the ARs immediately abutting the AR in question. We call those the entry and exit ARs 💅.

Picture the verification info inside a Policy Gateway as a bunch of templates 🎀. Each template is tied to a valid set of users, described by the source and destination host address and the optional User Class. It also contains the four ARs we just talked about: Source, Destination, Exit, and Entry. An incoming packet should be forwarded if, and only if, there is a template matching the information in the packet ✨. These templates are called Policy Terms 👑.

4.3. Conditions 🌸

Okay, so Policy Terms as we've described them so far can't express a realistic range of policies 😭. What we need is the ability to attach a number of conditions to a Policy Term. These conditions describe the circumstances under which the term is valid 🧚. They might include what type of service (TOS) is available, what times of day the term is valid, what accounting options are valid, and so on. A time-of-day condition, for example, would let networks like time-sharing systems offer their off-peak capacity to a wider community 🍓.

In general these conditions could be pretty arbitrary. The important constraint is that any condition imposed by the Policy Gateway must be understood by the end point, so the end point can generate Policy Routes that conform to the condition 🫶. If that isn't the case, and the Policy Gateway attaches capricious conditions to its policy terms, then end points will build Policy Routes in good faith that get rejected. That leads to a failure to obtain service and serious dissatisfaction among users 😤. For this reason, the nature of policy conditions needs to be negotiated in advance 🤝.

The most interesting and difficult conditions are the ones that relate to the dynamic state of the network 🔥. An excellent example is a bilateral mutual aid agreement between two transit ARs, where each agrees to carry the other's load if the other goes down. To capture that agreement, each might want to put in Policy Terms with the condition that they're only valid if some other AR is nonfunctional 🙈. Earlier, when we talked about Policy Route synthesis, the ARs had to run a global up-down protocol to describe the connectivity of ARs. This protocol is enough to let the Policy Gateway know that some other AR is nonfunctional. But the dynamics of this system need care, so that the end points in the PR have a consistent view of the up-down status of the world. Otherwise you'd get transient service outages, which again would lead to user dissatisfaction 😭💜.

In general, this proposal asserts that policies should not be based on highly dynamic phenomena 🦋. Administrative Regions should be thought of as stable entities that don't change state rapidly. Highly dynamic characteristics, like queue length, should be handled by proper engineering inside the AR 🛠️. Precisely because conditions have to be propagated globally, basing a condition on a highly dynamic parameter is likely to lead to system instability 💀.

4.4. Ownership of Policy Gateways 🎀

Remember in Section 1, when we said all the resources of the network are partitioned among the ARs? Well, that doesn't extend to the Policy Gateways 🥺. They sit on the boundary between ARs. So either the Policy Gateway has to be made of two physical halves connected by a wire, or there has to be a joint agreement for who owns and operates the gateway. This is a matter for further study 🧐✨.

5. Examples of Policy Terms 🎀

okay so this section is where the theory gets real 💅 It shows how policy terms would actually be used to write down a bunch of practical policies. Before we can give examples we need a notation for policy terms. It's not the most compact form ever, but it's totally enough for simple examples 🦋

A Policy Term is written like this:

((Hs,ARs,ARent),(Hd,ARd,ARexit),UCI,Cg)

where:

• Hs is the source host address,
• ARs is the source AR,
• ARent is the entry AR,

and these three values make up the first "element" of the term, describing the permitted access looking toward the source. For the destination it's the same deal: there's an element with the host address, the adjacent AR, and the ultimate AR 💖

The term also has some global info:

• UCI is the User Class Id, and
• Cg are any global conditions.

Sometimes an element doesn't want to constrain one of the values, so we use the "*" symbol as a wild-card match ✨

Okay, next up is a topology so we can see what's going on. H elements are hosts, G elements are Policy Gateways, and the numbered elements are ARs 🌸

      H1 ---  1 --- G1 -----  2 ------ G2 ----- 3 ----- H2
              |                                 |
              |                                 |
              |                                 |
              |---- G3 -----  4 ------ G4 ------|------ G5 --- 5
                              |                                |
                              |                                |
                              |                               H4
                              H3

In this picture there are four hosts, five gateways, and five Administrative Regions. Iconic 🙌

First, let's look at AR 2. It has no hosts attached and models a transit service, like the NSF network 🌈 It might have a super simple policy: it'll carry any traffic between universities with no further constraint. If we let AR 1 and AR 3 be the regions of two particular universities, its policy term could be written as:

AR2: ((*,1,*),(*,3,*),*,*).

This says that AR 2 agrees to carry traffic from AR 1 to AR 3, without caring about the entry and exit AR, and for any hosts in those ARs. Bestie, that's a whole lot of commas 😭

The notation works, but it's very bulky, because a new term is needed for every pair of universities. There are a few ways to compact it. First, we can use the * and a new symbol, "-", to broaden the terms a bit. For example:

AR2: ((*,1,*),(*,*,-),*,*)

would assert that AR 1 can use AR 2 to talk to any directly attached AR. The "-" means the exit AR must be the destination AR. In other words, the destination AR has to be directly attached to AR 2. If AR 2 only attaches to universities, this gives the proper constraint 🎓

Another approach is to use the User Class ID:

AR2:((*,*,*),(*,*,*),University,*)

says that any traffic of any sort with the User Class of University is acceptable 💅

Another, and maybe the most suitable notation, comes from noticing that the difference between source and destination is actually kind of artificial 🤯 Naming the two ends helps in this memo, but either end can be a source, depending on who sends the first packet. (A later section explores the bi-directional nature of PRs.) So a more general form of a PR is to allow any number of elements. A Policy Term can have more than two elements, and that means a PR is valid if it uses any two of them.

For example, if university 5 wanted to use the AR 2 service, AR 2 might write a Policy Term like this:

AR2:((*,1,*),(*,3,*),(*,5,*),*,*)

which would permit a policy route between hosts in any two of the ARs 1, 3 and 5 🦋

All the terms so far are about the policies of AR 2. If university 1 wanted to subscribe to this service and use it to reach any other site, it would write terms of its own. For example:

AR1: ((*,1, -),(*,*,2),*,*).

This term says that any host in AR 1 can use AR 2 as a path to any host in any AR. Again we use the "-" notation, this time to show that the entry AR is the same as the source AR, which in this case is the AR writing the term 💜

The ARs numbered 3 and 5 are a little more interesting 👀 AR 3 is directly attached to AR 2, but AR 5 isn't. Instead, AR 5 is attached to AR 3. If AR 3 wants to use AR 2 for general transit service, it has to write a term similar to the one AR 1 wrote:

AR3: ((*,3,-),(*,*,2),*,*).

If AR 5 wants to use AR 2, more terms are needed. Since AR 2 isn't directly attached, AR 5 can't name it as the exit AR in its own term. The directly attached AR, which is AR 3, is all that can be named:

AR5: ((*,5,-),(*,*,3),*,*).

Then AR 3 has to agree to carry the transit traffic for AR 5:

AR3: ((*,5,-),(*,*,2),*,*)

AR 3 might not want to carry every form of transit traffic for AR 5, only certain sorts or traffic going to certain places. That can be expressed by restricting the previous term. For example:

AR3: ((*,5,-),(*,2,-),*,*)

would permit traffic from AR 5 to cross AR 3 to reach AR 2, but only to hosts directly in those ARs 🚦

For some more examples, let's think about AR 4, which might represent the AR of a commercial user 🏢 It connects together that user's hosts, for example H3, and it's connected to the rest of the environment to allow cross-communication. Given the terms so far, no traffic will flow into this AR 🙈

If AR 1 wants to permit communication with AR 4, it could add:

AR1: ((*,1,-),(*,4,-),*,*)

This would permit communication between hosts directly in each AR, but no transit traffic. In particular, H3 and H2 can't talk to each other yet. There are several different terms that would let them talk 🫶

The direct path would be the following:

AR4: ((*,4,-),(H2,3,-),*,*)
AR3: ((*,3,-),(H3,4,-),*,*).

This would permit a direct connection through G4 ⭐ Note, for variety, that each term is set up so that any host in the local AR can match, but only one host in the other AR. The combination happens to permit only H3 and H2 to communicate 💅

If G4 weren't there, another path would go via AR 2, which could be permitted by suitable terms in ARs 1, 2, 3 and 4 🌸

Even if G3 and G4 exist, no transit traffic will flow across AR 4 from 1 to 3, even if 1 and 3 want it to:

AR1: ((*,1,-),(*,3,4),*,*) and
AR3: ((*,3,-),(*,1,4),*,*),

the lack of a term for AR 4 will block a valid PR via that path 🚫 Only if AR 4 added:

AR4:((*,1,-),(*,3,-),*,*)

would AR 4 start offering a transit path from 1 to 3 🧚

If AR 4 added:

AR4: ((*,4,-),(*,*,*),*,*)

then any host in AR 4 could talk to any host anywhere else, but AR 4 still wouldn't become a transit service. Main character energy, but not a transit hub 👑

These examples show how individual ARs can offer Policy Terms that combine to form a route. The notation proposed here probably isn't enough to express the full range of policies we might need. For example, it may be desirable to have lists of ARs as part of a term, as well as single values and "*". Other notation might be proposed to allow exclusion of a limited set of ARs. It may also be appropriate to write elements that are directional, so that connections can be "opened" in one direction but not in others. That idea is vague in a connectionless architecture, but it seems to relate to some real policy requirements 🦋

In general, the problem of expressing policy terms in compact form is the same as the problem of constructing compact access control lists 🔐 There's still an ongoing argument about whether access control lists should be ordered, and whether they should permit exclusion, and so on. It would seem the exact same issues come up here. Some experience trying to express real policies may give guidance on the expressive power needed 💜

6. Cost Recovery ✨

okay bestie, so almost the whole Internet was paid for like a big capital purchase and then handed to users as a free good 🎁. there are a few cost recovery examples, but they're based on an annual subscription fee instead of a charge for how much you actually use 🙈. there's also a growing vibe that accounting for usage, even if you don't bill for it, is a huge part of managing resources well 📊. so tools for accounting and billing MUST be a central part of any policy mechanism 🔥.

BUT here's the tea 🍵: the administrative regions are autonomous, so we can't force one billing policy on everyone 🙅‍♀️. some regions MAY keep service free or do an annual fee 🌸. others MAY charge based on resources consumed, and even then the details vary, since some MAY charge by the packet and others MAY charge by the byte 🧃. it's the same energy as the phone system, where local and long distance carriers sell service either as a monthly fee or a fee-per-minute with time-of-day conditions attached ☎️. so the billing problem is honestly complicated, because the user would obviously want to minimize cost while juggling all those conditions 🧠💅.

If we're actually going to charge for use, there's also the collection problem 💸. using the phone system as our example, there are two strategies for collecting revenue. the first is the pre-divestiture mode, where the source AR (or the destination AR for a collect call) is the single collection point for every AR involved in the call 📞. after divestiture, we get a new paradigm, where the transit AR bills the customer separately 🧾.

there are lots of reasons to support both collection formats 🫶. the main reason for separate billing is that not all regions MAY want to charge the user in the same units of currency. some might want real dollars, while others might want some kind of private allocation units 💵🪙. on the flip side, having a single point of collection is super convenient, because it cuts out a ton of duplicate effort 🙌. it does, however, require a bigger degree of trust and coordination among ARs 🤝.

single point collection also solves another sticky problem: lost packets 😭. for most types of service, the user would be offended if they had to pay for a bunch of packets that never made it to the destination 💀. if each region bills for its own traffic separately, then to avoid billing for packets lost between that AR and the destination, you need some kind of lost packet reporting. that report travels backward through the system and decrements the counters of all the intervening ARs 🔙. with single point collection, the usage meters can live in the destination AR and get periodically propagated to the billing AR, if that's a different region 📈.

the lost packets thing makes a really important link between billing and policy 👀. if a Policy Route takes packets through a region with known unreliability, the regions before it on the path MAY be quite unwilling to forgive charges for packets that successfully crossed their own region, only to get lost further down the route 😤. a billing policy is basically a way of saying "I want to divorce myself from that other region's reliability" 🚪. so the conditions in the policy terms, and the matching policy routes, MUST be able to capture two distinct conditions 🎯.

the first is whether there's a bilateral agreement between two ARs where one agrees to act as the collection agent for the other 🤙. chaining a bunch of these agreements lets a single collection point handle the entire policy route 🔗. the second is whether an AR will accept the packet and byte counts from the next AR downstream as the basis of billing, or whether it insists billing be based on the counts at its own exit point 📏. this lets an AR build a wall between itself and a later unreliable AR 🧱. you can imagine certain regions agreeing to carry traffic into unreliable regions, but only grudgingly, knowing the user frustration MAY get aimed at all the ARs indiscriminately 😩. a specific policy condition can make it clear to the end user which ARs don't see themselves as interworking harmoniously 🫠.

to enforce all this, the abstract PR that's included in the packet MUST be augmented with a few conditions 📦. first, each AR gets a 3-way flag that says whether billing should be collected separately for that region, propagated back to the source (the normal telephone company paradigm), or propagated toward the destination (the collect call vibe) 🔀. second, there's a flag that says whether the region is expected to accept the packet and byte counts from the next region downstream as the basis of billing ✅. third, there has to be a charge code: a unique number that kinda looks like a credit card number, and that bills MAY be sent to 💳✨. the Policy Terms in the Gateways MUST similarly be augmented so they can be verified 🔐. how the charge code is managed (making sure it's unique and that nobody abuses it) gets covered later 👀.

these conditions are about agreements between two ARs, so they're a bit different from the ones we already talked about, like time of day 🕰️. the ones about AR agreements get called "bilateral conditions," and the others get called "global conditions." 💜 even though bilateral conditions are about an agreement between two ARs, they can still have global effects 🌍.

---

7. Gateway Selection 🚪

okay so back in Section Two, this memo proposed that the end point would specify an abstract Policy Route as a series of ARs, and the Policy Gateway at the entry to each AR would convert the next hop into a concrete route by picking which Policy Gateway to exit this region through 🗺️. plot twist: this selection isn't totally free of policy drama 🎭. some extra conditions are REQUIRED in the Policy Terms to make it all work properly 🛠️.

for each Policy Gateway to pick the next one on the route, it needs a table listing every potential Policy Gateway that connects adjacent regions 📋. this info changes super slowly and is pretty easy to spread around 🐌. the more dynamic part is whether each gateway is up 🟢. so all of the Policy Gateways attached to a given AR MUST run a local up-down algorithm 🧪. ideally that algorithm can tell not just that the other gateways are up, but that their interfaces are up and they're actually forwarding traffic properly ✅. designing this test is a little tricky 😅. the good news is we don't need a strategy for spreading this info globally, since only the other Policy Gateways attached to each region need it 🙌.

the policy issue with concrete routes shows up when several gateways connect the same two administrative regions 🧩. right now, the exit Policy Gateway from any region (which is also the entry gateway for the next region) gets chosen by the entry Policy Gateway for that region. so each region MAY pick its own exit gateway, but it has zero say over its entry gateway 🙃. sometimes a region really wants control over its entry gateway, though 😤. picture two parallel transit regions: one charges by usage, the other is a free good 🆓. from the user's side, the move is to minimize use of the charging AR and max out the free AR 🧠. but that MAY lead to gross overloads in the free AR, plus it looks like discrimination against the charging AR 📉. so the owner of the free AR might impose a policy saying it can only be used to reach certain points that aren't directly connected to the billing AR, and traffic has to enter the free AR at the point closest to the destination 📍. basically, the free AR needs to pick its own entry gateway so it can minimize its costs (which, fun fact, nobody is billing it for) and shove as much of the cost as possible onto the other network 💅😈.

you can control all these gateway selection options by adding more bilateral conditions to the Policy Terms and the Policy Route in the packet 🎛️. at every boundary between ARs, there are only so many ways to select the Policy Gateway 🔢. it's selected by the entry side, by the exit side, or by some collaborative algorithm agreed through a bilateral agreement 🤝. (there could be several of these algorithms, which means the spec might need more complexity to handle them 🌀. for example, if two adjacent ARs agreed to use a common routing metric for some type of service, they MAY agree to route together based on that metric 📏.)

letting the AR on the far side of the gateway pick the gateway is a really interesting implementation problem 🤔. you could send a message ahead of the packet asking the next AR to select its entry gateway 📨. it would work out its own exit gateway, then work backwards to minimize its costs (for example) to pick the potential entry gateway into the immediate region 🔙. honestly that's complicated to describe and would probably be complicated to build 😵‍💫. one way to focus the problem is to notice that routes are bi-directional, because packet flows are bi-directional, and it's super desirable for packets from both directions to take the same route 🔁💖. once a packet comes back along the reverse route, the gateway it comes out of is exactly the gateway that SHOULD be used for future traffic in the other direction 🎯. but each gateway, whether it's in the forward or reverse direction, MUST remember a decision that was made by another AR 🧠📝.

for this to work, gateways can't be stateless 🙅. if each Policy Gateway keeps a cache of recently computed Policy Routes, specifically remembering which gateway was computed for each abstract route, then by checking whether the forward direction or the reverse direction is allowed to constrain the gateway across this boundary, both policies can be enforced 🎉. but that means building gateways with state, which hasn't exactly been culturally accepted on the Internet 🙈. so I'm treating the virtues of state in Policy Gateways as a separate topic 💭. I believe fairly simple algorithms exist for setting up the required bindings in the Policy Gateways, but that's a problem for later study 📚✨.

8. Flow States 🌸

okay so the last section hinted that the gateway needs to keep some state so it can tie the forward and reverse halves of a flow together. that fixed one specific problem: linking the routing decision made in each direction so each one can be used in the other direction. but there are actually a few more reasons the two halves should be tied together 🎀

• There's a ton of overhead in accounting and collecting for usage, so it's clearly the move to have both halves of the flow metered jointly 💅
• If the route isn't bi-directional, a failure in the node leaves you with a uni-directional link. uni-directional links are known to cause weird, glitchy behavior in protocols 💀
• For resource management, intermediate nodes may want to pass flow control information back to the source of the flow. if identifiable reverse-direction packets are passing through the gateway, that info can get piggy-backed onto those packets 🦋

an extra perk of keeping state in the gateway is that it greatly cuts down the overhead of handling incoming packets ✨ the Policy Gateway has a bunch of decisions to make when forwarding a packet: it must validate the Policy Route against its terms, it must create or modify an accounting record, and it must select the next Policy Gateway. doing all of that from scratch for every single incoming packet is just not it 🙅‍♀️ once those decisions are made, the results should be cached so they can be reused for later packets 🧚

the stateless gateway was proposed as part of the Internet design to keep the architecture robust, and honestly, iconic behavior 👑 if the gateway has no state, a crash can't endanger an on-going connection. but if there is state and it gets lost in a crash, a flow could get disrupted 😭

so when you move from a gateway with no state to one that caches information, the cached info has to be something that can be lost and then rebuilt. the idea of only keeping the state in gateways that can be easily reconstructed is what I call "soft state." periodt 💜

---

9. Synthesis and Selection of Policy Routes 🦋

in this proposal, a packet carries a Policy Route, and each Policy Gateway along the way verifies it 🫶 this section is about how that Policy Route gets created in the first place.

PR creation can't be fully automatic. it will generally need human judgment, because policies are matters of human concern 🌈 so the approach is a joint one, where the system supports the people setting policy.

most of the time, the PR you want gets picked from the valid ones by first finding all valid PRs, then choosing one that meets the user's requirements and has the lowest real cost 💖 we'll call these two stages synthesis and selection.

to synthesize a PR across a sequence of ARs, you have to find a Policy Term in each AR that would allow such a PR. the Policy Terms in each adjacent AR must be compatible in their billing conditions and other particulars. picture finding a sequence of Policy Terms that match, rather like dominoes, all the way from the source to the destination 🍓

for a Policy Term at some AR to be acceptable as part of a PR, the following must be true:

• The Source and Destination Host address and UCI must match the term,
• The Source and Destination AR must match the term,
• The Entry and Exit AR must match the adjacent AR in the route,
• The conditions in the term relating to the adjacent AR (e.g., billing) must match the conditions in the term from that region.

these are exactly the checks the Policy Gateway would run when validating the PR when it's actually used 👀

as the route gets synthesized from matching terms, the global conditions of each term are noted, and the combination of those becomes the condition under which the PR is valid. at the starting point of synthesis, the user may have indicated constraints on the acceptable conditions, which limits the candidate terms in the synthesis 🎀

the result of PR synthesis is kinda like a link-state routing algorithm where each Policy Term acts as an abstract link 🧠 you end up with a potentially long list of possible PRs to each destination AR, each with its attached conditions. the selection process has to pick out the one that's actually going to be used. it can be based on the conditions and on the cost of each PR ✨

to figure out the cost, you'd need to be able to ask each AR to identify the cost of using that Policy Term in the context of this particular set of Entry and Exit ARs. either there has to be an architected protocol for reporting these costs, or the cost determination has to be left to humans, outside the system 🙃 the problem with architected cost reporting is that some ARs may bill in real dollars, while others bill in abstract usage authorizations that have no meaning outside that AR. still, I believe we should try to define a representation for reporting the billing basis associated with each AR. that's a matter for later study 📚

synthesis might be automated, but selection probably isn't 🙈 cost minimization will help prune the list, and some routes may get rejected automatically based on conditions, but part of selection will generally need human judgment. put that together with the fact that synthesis can be costly, and it means two things: synthesis and selection can't be done for each packet, or even each time a transport connection is established. and it shouldn't be done separately for each host in the AR 💅

instead, each AR should have one (or more) Policy Servers, which are servers inside the AR that support the management of PRs. a Policy Server would do a bunch of jobs:

• It would store the Policy Terms for the AR, and make them available to the Policy Gateways and the Servers of other ARs as appropriate.
• It would synthesize potential PRs to reach other ARs, and remember which of these have been selected for use.
• It will respond to requests from hosts in the AR for PRs, and return them so they can be included in outgoing packets.
• It will participate on behalf of the AR in AR up-down protocols, and other inter-AR routing algorithms.
• It will remember the location of all Policy Gateways attached to this AR.
• It will provide the management interface for the people who have to set AR policy: setting local Policy Terms, selecting Policy Routes, and so on.

a host that wants to send packets outside its local AR has to get a PR to put into those packets first 🌸 normally, it does this by sending a request to the local Policy Server, giving the desired destination and other negotiable conditions. (for example, the TOS is negotiable, but the current time is not ⏰) based on that input, the Server must pick the most appropriate PR and return it 🫶

at this point, human intervention isn't reasonable because it would take way too long 😭 by now, enough selection has to have been done that automated PR selection is possible. the most direct way to do this is for the manual selection process to produce an ordered (or partially ordered) list of potential PRs, and then search that list in order until a PR matching the destination and conditions turns up. that PR is what gets returned 🏆

10. Security ✨

okay bestie, security time, and this part is kinda scary but also so interesting 😭 there are a bunch of spots where somebody could totally abuse this scheme. almost always the abuse is about stealing network resources or charging people wrongly, which is a different vibe from corrupting or leaking data 🫣 mechanisms that make sure resources get used properly and charged right usually tolerate minor abuse so the whole thing stays easy to run 💅 and control is often about detecting and recovering instead of preventing. the authors think that's probably fine here too 🫶 a single lonely packet that isn't part of any sequence might be too tiny to bill or control. but if a real stream of packets goes unaccounted for, that's a lot less okay 💀

there are three general ways to abuse it 🔥 first, you could falsify the user identification info in the PR: the source and destination host, the User Class Id, and the charge code. second, you could take a valid PR and misuse it intact. third, you could read a valid charge code out of a PR and then make extra charges against it.

to stop fake user info from getting into a PR, the PRs should be sealed or signed using a crypto sealing technique 🔐 since Policy Servers are where PRs come from, the Server can do the sealing. that means the seal or digital signature of each Server needs to be known, but you don't need every host to be known, which is so efficient 🎀 the Server would be trusted to seal only valid PRs. it must only put User Class Ids and charge codes into PRs from a source permitted to use them, for example.

assuming a public key system, each Policy Server could have its own key pair, with the public half advertised in some way 🗝️ exactly which parts of the PR need to be sealed is still a matter for further study 🤓

if the Policy Server breaks that trust and uses a UCI or charge code with an unauthorized host, there are two sub-cases: the false source host is in the same AS, or it's outside it. if it's outside, you can catch it by inspecting the PR, since the relation between AR and network number is (almost) static. one approach is to make an AR identifier part of the charge code, so the code gets rejected unless that AR is the source AR for the packet. this works, but it stops you from using charge codes from a foreign location 😬 other, more general techniques could probably be proposed.

if the false source host is inside the AR, then further steps are required to prevent the problem. one general solution is to note that a PR is valid only if it was sealed by a Policy Server. any AR trying to collect for usage should keep a copy of the PR as proof that the route was used. if there seems to be unauthorized use of a charge code, the owner can ask to see the PR that generated the charge, which will show the Policy Server that constructed the route. if it's unauthorized, action can be taken against the AR that owns that Server, with the sealed PR as evidence 🕵️‍♀️ in other words, detection and redress may be more effective than prevention.

if we can assume the Policy Server for a particular region is as trustworthy as that AR requires, there's still the problem of one region's Server trying to steal from another AR 👀 this could be done by taking a valid PR and sending data forward along it from the "middle" of the route. then what looks like it's coming from one source is actually coming from another source in a different AR.

this would require that packets coming back along the route toward the original source get rerouted to the false source, which would mean the whole routing function within the AR has been corrupted. it's unlikely this would go long undetected 🫠 but if direct control of this class of fraud is needed, it could be achieved by requiring any AR intending to charge against a particular PR to get a confirmation from time to time. that confirmation would be sealed by the Server of the source AR and would say that its policy gateway has in fact forwarded some number of packets using this PR. the authors admit this sort of function is probably overkill, but this class of fraud still needs to be considered 😭

obviously a more detailed study is required for the problem of resource theft, but I believe a mechanism can be made to work based on:

• Local trust of the Policy Server within each AR.
• Sealing of the PR by the Server.
• Selective validation of the seal at the Policy Gateway.
• Selective consistency checking of the PR at the Policy Gateway.
• Use of the seal on the PR as evidence of the source of the PR.

---

11. An Experimental Program -- Migration to Policy Routing 🧚

the proposal above calls for several Internet components that aren't around today: the Policy Route IP option, Policy Gateways, Policy Servers, and support protocols like the global AS up-down protocol and the local (to the AS) Policy Gateway up-down protocol. so any plan for introducing policy routing has to include a way to experiment with the concept without changing all the hosts and gateways already in place 🫠

since the Policy Server is a new component that can be added to the Internet without changing any existing components, it's easy to put in place. so that becomes the central part of an experimental plan 🎯 later, it's possible to imagine adding policy controls to some of the gateways. the most difficult part will be modifying all the hosts to use the PR IP option. based on our experience with adding minor features like IP subnetworks, it will never be possible to get the PR option into all the hosts, so policy routing must be made to work anyway 💀

taking these difficulties into account, here's a concrete experimental plan in three phases 📋

in Phase I, software for a Policy Server is created and made available to all potential ARs. as part of its function, it has two "temporary" features that mimic the function of the missing host and gateway support ✨

to mimic the function of the policy gateway, two policy Servers are placed "near" a current function gateway that happens to connect the two ARs, one on each side of it, representing their respective ARs. these two Servers then fool the current gateway as follows:

• The current gateway is given the two Servers as neighbors in its routing exchanges. In this way, the Servers can control which network numbers are advertised. This is similar to the way "gated" is used today to control routes.
• A packet entering the AR is directed to the "near" Server inside the AR, which performs the functions of the Policy Gateway and then resends the packet. This may require the use of a regular source route in some cases, but can probably just be done by rewriting the destination IP address in the packet. (Note that the IP PR option proposed in the Appendix has fields for the original IP source and destination, so that these fields can be reused in forwarding the packet from gateway to gateway.)

to deal with the lack of host support for the PR option, we again make use of the Server 🫶 since the Server is the recipient of all routing information coming into the AR (it was set up as the neighbor of the current gateway at the actual AR boundary), it alone knows the proper routes out. internally, it advertises itself as the default gateway to all networks outside the AR, so it receives all the packets intending to leave the region. rather than the host, it adds the PR option and then sends the packet on to the Policy Gateway (or the matching Server in the next AR playing its part) for relaying.

by controlling how routes are propagated by the regular gateways, it's possible to stop hosts from manually setting up routes to bypass the Servers. in any event, enforcement isn't the primary concern in Phase I of the experiment 🙈

in Phase II, certain of the current gateways get augmented with the Policy Gateway functions. this makes enforcement easier and gets rid of the extra hop the packet had to make in Phase I, when it passed from one Server to another through the current gateway. at the same time, some of the hosts get modified to insert the IP PR option into the packet at the source. this will explore the problems of PR selection 🔍

in Phase III, the PR design is proposed for general implementation 👑

---

12. Policy Route Setup 🎀

one objection to this scheme is the large size of the IP PR option. with all the information proposed in this memo, it's larger than the IP header itself 😭 however, this problem can easily be avoided, because the PR option seldom needs to be sent 🙌

since the Policy Gateways are going to cache the result of processing the PR, the cache holds the equivalent of the PR. all that's required is a very short option in the packet, which is a handle that lets the gateway find the correct cache entry 🧠 this handle would be included in the original IP PR option and then repeated in every packet. the Policy Server that generated the PR could select the handle, so it would be unique for each AR. perhaps the AR id and a 16 bit UID would be sufficient 🍓

the full PR option needs to be in the packet only if the cached information in the gateway is lost. if a gateway crashes or the route changes, the end point must reconstruct the caches in the series of gateways that form the route. the end point could determine that this was necessary either when a gateway reports explicitly that it does not have an entry corresponding to a handle, or when the host determines that it is not getting the desired service 🕵️

this sort of action can be thought of as an extension of the idea of retransmitting. in transport protocols such as TCP, the host keeps track of the behavior of the network, and if it believes something is wrong (e.g., there is a lack of an acknowledgment), it takes action to restore the desired service 🔄 other examples include switching to another gateway if the currently active adjacent gateway seems to be down. sending the full PR option in the packet is just another example of allowing the end node to restore the state of the connection if it seems to be broken 🦋

using this model, most packets would have only a short option (perhaps 12 bytes) 💜

this idea of restoring the state in the gateway as needed achieves the idea of "soft state" mentioned earlier, and allows gateways with state to achieve the same robustness associated with datagram networks 🌈 that's the whole vibe, honestly, iconic 🌈

Author's Address

David D. Clark
Massachusetts Institute of Technology
Laboratory for Computer Science
545 Main Street
Cambridge, MA 02139

Phone: (617) 253-6003

Email: ddc@LCS.MIT.EDU