RFC 1383

An Experiment in DNS Based IP Routing

📅 published December 1992, from ietf

An Experiment in DNS Based IP Routing 🦋

  • Request for Comments: 1383
  • Working group: Network Working Group
  • Author: C. Huitema, INRIA
  • Date: December 1992
  • Category: Experimental Protocol
  • Obsoletes / Updates: Nothing listed in this document

Status of This Memo 📜

Okay bestie, so this memo is defining an Experimental Protocol for the Internet community 🧪. Feedback and suggestions for improvement are literally requested, so speak up! For the standardization state and status of this protocol, go check the current edition of the "IAB Official Protocol Standards" 📚. Distribution of this memo is unlimited 🌈.

Table of Contents 🗂️

1. Routing, scaling and hierarchies ......................    1
2. Routing based on MX records ...........................    2
3. Evaluation of DNS routing .............................    3
3.1 Loops and relays .....................................    4
3.2 Performances and scaling .............................    5
3.3 Tunneling or source routing ..........................    6
3.4 Choosing a gateway ...................................    6
3.5 Routing dynamics .....................................    6
3.6 DNS connectivity .....................................    7
3.7 On the way back ......................................    8
3.8 Flirting with policy routing .........................    8
4. Rationales for deployment .............................    9
4.1 The good citizens ....................................   10
4.2 The commercial approach ..............................   10
5. The experimental development ..........................   11
5.1 DNS record ...........................................   11
5.2 Interface with the standard IP router ................   12
5.3 The DNS query manager ................................   12
5.4 The real time forwarder ..............................   12
5.5 Interaction with routing protocols ...................   13
6. Acknowledgments .......................................   13
7. Conclusion ............................................   13
8. References ............................................   14
9. Security Considerations ...............................   14
10. Author's Address .....................................   14

1. Routing, scaling and hierarchies ✨

Okay so the Internet's routing is kinda blowing up 💥. Recent studies flagged the risk of "routing explosion": there are already more than 5000 networks announced in the NSFNET routing tables, and more than 7000 in the EBONE routing tables. Those numbers keep growing, and that causes a few problems:

  • The size of the routing tables grows linearly with the number of connected networks. Handling bigger tables means more resources in all "intelligent" routers, especially the "transit" and "external" routers that can't rely on default routes 😩.
  • The volume of information carried by route exchange protocols like BGP grows with the number of networks. That eats more network resources and makes the reaction to routing events slower 🐢.
  • Transit network administrators have to make explicit administrative decisions if they want to implement "routing policies" for each and every additional "multi-homed" network 🙃.

The current "textbook" fix for routing explosion is "hierarchical routing" based on hierarchical addresses 🌳. It's well documented in routing protocols like IDRP, and it's one of the reasons for deploying the CIDR [3] addressing structure on the Internet. But this textbook solution, while often perfectly adequate, has a number of inconveniences, especially with "multihomed stubs", e.g., customer networks that are connected to more than one service provider 🫠.

So this proposal presents a scheme for simple routing 🎀. It's complementary to the classic "hierarchical routing" approach, but it's easy to implement and low cost for "multi-homed" domains 💅. The whole solution is a generalization of the "MX record" scheme that's already used for mail routing 💌.

2. Routing based on MX records 💌

Okay, MX records are already used by mail routing to create a little bit of decoupling 🧩. They separate the "domain names" used for user registration from the mailbox addresses. They're especially useful for sending mail to "non connected" domains: the MX record points to one or several Internet hosts that agree to relay mail toward the target domain 📮.

Here's the glow-up: we want to generalize this for packet routing 🦋. Imagine a routing domain D, containing several networks, subnetworks and hosts, that's connected to the Internet through a couple of IP gateways. These gateways are dual homed, which means each one has an address inside the domain D (say D1 and D2) and an address on the Internet (say I1 and I2) 👯. The gateways also have a special vibe: they keep information to themselves and don't announce any reachability info about the networks inside "D" to the Internet 🤫.

Those networks still get properly registered, though! A name server that's accessible from the Internet holds the in-addr.arpa records that enable reverse "address to name" lookup 🔍. It also holds the network-level equivalent of MX records, called "RX records" ✨. So for any host address Dx inside D, you can get RX records pointing to the Internet addresses of the gateways, I1 and I2 🎯.

Now, a standard Internet router Ix can't, in principle, send a packet to the address Dx, because it has no matching routing information 😭. BUT if that router has been modified to use our scheme, it will query the DNS with the name built from Dx in the in-addr.arpa domain, get the RX records, and forward the packet toward I1 (or I2) using some form of "source routing" 🚀. The gateway I1 (or I2) receives the packet. Its routing tables contain information on the domain D, so it can relay the packet on to the host Dx 🥰.

At this point, readers should be convinced that we've presented a scheme that:

  • avoids changes in host IP addresses as topology changes, without requiring extra overhead on routing (provided that the routing employs some form of hierarchical information aggregation/abstraction) 🙌,
  • allows support for multihomed domains without requiring additional overhead on routing and without requiring hosts to have explicit knowledge of multiple addresses 💖.
They should also forcingly scratch their head and mumble that things can't be this simple 🙈. Honestly? Same. You should look at the details carefully before assuming the solution really works.

3. Evaluation of DNS routing 🧐

When you hear about schemes like this, a few questions pop up immediately:

  • Should all relays access the DNS? What about possible loops? 🔁
  • Will the performance be adequate? ⏱️
  • How does one choose the best gateway when several are announced? What happens if the gateway is overloaded, or unreachable? 🚧
  • What if the directory cannot be accessed? 📕
  • How does it work in the reverse direction? ↩️
  • Should we use tunnelling or loose source routing? 🚇
  • Can we be more general? 🌍

There may be even more questions, but these ones, at least, were taken into account when setting up our experiment 🧪.

3.1. Loops and relays 🔄

Earlier, we mentioned that packets would be directed toward the access gateway I1 or I2 by means of "source routing" or "tunnelling". Stricto sensu, that isn't actually necessary 🤷‍♀️. You could imagine the packet simply being routed "as if it was directed towards I1 or I2". Then the next relay would, in turn, also access the DNS to get routing information and forward the packet along.

This strategy has an advantage: it leaves the header untouched and lets the transit nodes choose the best routing toward the destination, based on their knowledge of reachability status 🧭. However, it has two important disadvantages:

  • It would oblige all intermediate relays to access the DNS 😬,
  • It would oblige all these relays to exploit the DNS information consistently 🫨.

Obliging all intermediate gateways to access the DNS is impractical in the short term 🙅‍♀️. It would mean updating each and every transit relay before deploying the scheme. It could also have a big performance impact, because the "working set" of transit relays is typically much wider than that of stub gateways, so the argument about the efficiency of caches may not apply 😵. This might even stay impractical in the long term, since the volume of DNS traffic could become excessive 📈.

The second argument would still apply even if the performance problem were solved 🥲. Say several RX records are registered for a given destination, like I1 and I2 for Dx in our example, and a "hop by hop routing" strategy is used. There's a fair risk that some relays would send the packet toward I1 while others send it toward I2. That means inefficient routing and the possibility of loops 🌀.

To keep things coherent, we propose that all routing decisions be made at the source, or by one of the first relays near the source 💜.

3.2. Performances and scaling 📊

Using the DNS to acquire routing information has a twofold performance impact 🫶:

  • The initial DNS exchanges needed to load the information may cause a response time penalty for users 🐌,
  • The extra DNS traffic may contribute to overloading the network 🚦.

Good news: we already have experience with DNS routing on the Internet, thanks to the "mail" application 📬. After the introduction of the "MX record", mail routing slowly evolved from a hardwired hierarchy (think: send all mail to the addresses in the ".FR" domain to the french gateway) toward a decoupling between the name hierarchy used for registration and the physical hierarchy used for delivery 🎉.

If we consider that the mail application represents about 1/4th of Internet traffic, and that a mail message seldom includes more than half a dozen packets, then DNS access is already needed at least once for every 24 packets 🤯. The performance isn't apocalyptic, or someone would have complained! 😂 Generalizing this, we can suppose that a given host has a "working set" of IP destinations, and that some caching strategy should be enough to ease the performance hit 🧠.

In the scheme we propose, the DNS is only accessed once, either by the source host or by an intelligent router near the source host 🎯. The routing decision is made only once, and consistent routing is pursued across the Internet until the packet reaches an access router to the remote domain 🛣️.

The volume of DNS traffic through the NSFNET, as collected by MERIT, is currently about 9% 📉. When a host wants to establish communication with a remote host, it usually needs to obtain the name to IP address mapping 🪪. Getting the extra information (I1 or I2 in our example) should, in most cases, incur one more DNS lookup at the source. That lookup would, at most, double the volume of DNS traffic 👀.

3.3. Tunneling or source routing ✨

Okay so source directed routing (the thing we just talked about 💅) can be done in one of two ways: plain source routing, or some kind of encapsulation protocol. To keep things simple, we're going with source routing, as defined in [1]. Then we don't have to invent a special tunnelling protocol, and we don't have to make hosts implement one either. Less stuff, more slay 🧚

3.4. Choosing a gateway 🌸

The easy fix would be to allow only one RX record per destination, which would guarantee consistent decisions in the network. Honestly though, that's giving bad. A single access point is a single point of failure, and it'd only be connected to one transit network, which keeps that "customer locking" effect of hierarchical routing 🙃

So we propose that RX records look like MX records: each gateway address gets a preference identifier attached. When the source host makes a routing decision based on RX records, it should do the following:

  • List all possible gateways,
  • Prune all gateways in the list which are known as "unreachable" from the local site,
  • If the local host is present in the list with a preference index "x", prune all gateways whose preference index is larger than "x" or equal to "x".
  • Choose one gateway in the list. If the list is empty, consider the destination as unreachable.

These evaluations shouldn't be repeated for every single packet, so routers should keep a cache of the most frequently used destinations to speed things up 🏎️

3.5. Routing dynamics 💫

In theory, you could pull "distance" info out of the local routing table and mix it with the preference index to pick the "best" gateway. In practice (as shown in the mail context) that's super hard to test, so you have to lean on more heuristic approaches. The easiest one is to always pick the "preferred gateway", i.e., the gateway with the minimal preference index. Or, alternatively, you could choose one gateway at random from the list. This spreads traffic across several routes, which is known to give better load sharing and more redundancy in the network 🦋

Because this decision only happens once, the particular algorithm can be left as a purely local matter. One domain might decide based purely on the RX record, another purely on the routing info to the gateways listed in the RX record, and a third might use some weighted combination of both 🍓

Perhaps the most important feature is coping rapidly with network errors, i.e., detecting that one of the routes has become "unreachable". Honestly we lack experience here, and this is where the experiment will help 🙈 A few possible solutions, e.g.,:

  • Let intermediate gateways rewrite the loose source route in order to replace an unreachable access point by a better alternative,
  • Monitor the LSR options in the incoming packets, and use the reverse LSR,
  • Monitor the "ICMP Unreachable" messages received from intermediate gateways, and react accordingly,
  • Regularly probe the LSR, in order to check that it is still useful.

A particularly interesting line would be combining these connectivity checks with transport control protocol acknowledgments. But that would need an important modification of the TCP codes, and it's not practical in the short term. So we won't try any such interaction in the early experiments 🫶

Also, the management of these reachability informations should be taken into account when caching the results of DNS queries.

3.6. DNS connectivity 🌈

It's obvious that a scheme relying on RX records is only valid if those records can be accessed. By definition, that's not the case for the target domain itself, since it sits at the outer fringes of the Internet 😭

So a domain that wants connectivity using the RX scheme has to replicate its domain name service info, including the RX records, and provide them through servers accessible from the core of the Internet. A very obvious way to do that is to locate replicated name servers for the target domain in the access gateways "I1" and "I2" 💜

3.7. On the way back 🔁

A source located in the fringe domain, when accessing a core Internet host, will have to choose an access relay, I1 or I2 in our example.

A first approach is to let the access gateway relay the general routing information provided by the routing domains through the fringe network. Then fringe hosts get the same connectivity as core hosts and don't have to use source directed routing. The upside is that packets stay untouched, but it can cause problems if the transit network needs to send back an ICMP packet: it'll have to specify a source route through the access gateway for that packet. This would be guaranteed if the IP packets are source routed, since the reverse source route would be used automatically for the ICMP packet. So we're led to recommend that all IP packets leaving a fringe domain be explicitly source routed 🎯

The source route could be inserted by the access gateway when the packet exits the fringe domain, if the gateway has been made aware of our scheme. It could also be set by the source host, which would then have to explicitly choose the transit gateway, or by the first router in the path, usually the default router of the host sending the packets. As we expect hosts will be easier to modify than routers, we'll develop suitable algorithms here 🛠️

The fringe hosts will have to know the set of available gateways, and all temporarily unreachable gateways shall indeed be pruned. Without more information, the gateway will be chosen according to some preference order, or possibly at random.

It's very clear that if a "fringe" host wants to communicate with another "fringe" host, it has to insert two relays in the LSR: one for the domain that sources the packet, and one for the domain where the destination resides 🤝

3.8. Flirting with policy routing 💋

The current memo assumes that all gateways to a fringe domain are equivalent. The objective of the experiment is to test and evaluate a simple form of directory-based routing, not to provide a particular "policy routing" solution. Still, it should be pointed out that some form of policy routing could be implemented as a simple extension to our RX scheme 👀

In the proposed scheme, RX records are only qualified by an "order of preference". It wouldn't be very difficult to also qualify them with a "supported policy" indication, e.g., the numeric identifier of a particular "policy". The impact on the choice of gateways is obvious:

  • When going towards a fringe network, one should prune from the usable list all the gateways that do not support at least one of the local policies,
  • When exiting a fringe network, one should try to assess the policies supported by the target, and pick a corresponding exit gateway,
  • When going from a fringe network towards another fringe network, one should pick a pair of exit and access gateways that have matching policies.

Dave Clark has proposed a similar but more general approach under the title "route fragments" 🧩 The problems here are that we don't know how to identify policies, we don't know whether a simple numeric identifier is good enough, and we probably need to provide a way for end users to assess the policy on a packet-per-packet or flow-per-flow basis. In short, we should try to keep the initial experiment simple. If it's shown to be successful, we'll have to let it evolve towards some standard service, and it'll be reasonable to provide policy hooks at that stage ✨

4. Rationales for deployment 🎀

Readers should be convinced, after the previous section, that the DNS-IP routing scheme is sleek and safe. But they're probably also convinced that a network which is only connected through our scheme will enjoy somewhat fewer services than one with full traditional connectivity 🥲 We can see two major reasons for people to go along with this kind of scheme:

  • Because they're good network citizens and want to suffer their share in order to ease the general burden of the Internet,
  • Because they're financially induced to do so.

We'll examine these two rationales separately 👑

4.1. The good citizens 🫶

The Internet has a strong tradition of cooperative spirit: individual users are ready to suffer a bit and "do the right thing" if this conduct can be demonstrated to improve the global state of the network, and it isn't overly painful.

Refraining from recording your internal networks in the international connectivity tables is mainly an advantage for your Internet partners, and in particular for the backbone managers. The normal way to relieve this burden is to follow a hierarchical addressing plan, as suggested by CIDR. But when that plan can't be followed, e.g., when the topology just changed while the target hosts haven't yet been renumbered, our scheme offers an alternative to "just announcing one more network number in the tables". So it can help reduce the routing explosion problem 💖

4.2. The commercial approach 💰

Announcing network numbers in connectivity tables does have a significant cost for network operators:

  • larger routing tables means more memory, hence more expensive routers,
  • more networks means larger and more frequent routing messages, hence more network resources consumed,
  • more remote networks means more frequent administrative decisions if policies have to be implemented.

These costs are very significant not only for regionals, but also for backbone networks. So from an economic point of view, it would be very reasonable for a backbone to charge regionals according to the number of networks they announce. A similar line of reasoning can be applied by the regionals, who could give their customers the choice between:

  • being charged for announcing an address of their choice,
  • or being allocated, at a lower cost, a set of addresses in an addressing space belonging to the regional.

Our scheme may prove an interesting tool if the charge for individual addresses, which are necessary for "multi homed" clients, becomes too high 🤑

5. The experimental development 🧪

The experimental software, implemented under BSD Unix in a "socket" environment, contains two tasks:

  • a real time forwarder, which is implemented inside the kernel and handles the source demanded routes,
  • a DNS query manager, which transmits the source routing information to the real time forwarder.

In this section, we'll describe the real time forwarder, the query manager, the format of the DNS record, and the interface with the standard IP routers 💅

5.1. DNS record 🎀

okay so in a definitive scheme we'd need to define a brand new DNS record type with its own "RX" format 💅. then we'd have to teach that format to the domain name service software. not super hard, but it would probably take a couple of months, so the early experiments will just use the general purpose "TXT" record 🧚

this record is built for easy general purpose extensions in the DNS, and its content is just a text string ✨. the RX record has three fields:

  • a record identifier made of the two characters "RX". this keeps it separate from other experimental uses of the "TXT" record 🫶
  • a cost indicator, encoded on up to 3 numerical digits. the positive integer should be less than 256 so future evolutions have room 🔥
  • an IP address, written as a text string in the "dot" notation 🌸

the three strings get separated by a single comma. an example record would look like this:

 ___________________________________________________________________
 |         domain          |   type |   record |   value           |
 |            -            |        |          |                   |
 |*.27.32.192.in-addr.arpa |   IP   |    TXT   |   RX, 10, 10.0.0.7|
 |_________________________|________|__________|___________________|

which means that for all hosts whose IP address starts by the three octets "192.32.27" the IP host "10.0.0.7" can be used as a gateway, and that the preference value is 10. 🍓

5.2. Interface with the standard IP router 🦋

so we built our real time forwarder "on the side" of a standard IP router. it acts like a particular subnetwork connection. we just tell the IP router that some destinations should be forwarded to a particular "interface", which is our real time forwarder 🌈

knowing which destinations should go through our services is super important ngl. the service is useless for destinations that are directly reachable, so we have to monitor the "unreachable" destinations 👀. we do that by watching the "ICMP" messages that signal unreachable destination networks, and copying them over to the DNS query manager 💜

there are situations, like fringe networks, where the router already knows that destinations outside the local domain have to go through the real time forwarder. in that case it totally makes sense to declare the real time forwarder as the "default route" for the host 👑

5.3. The DNS query manager 💖

when the ICMP message comes in, the query manager updates the local routing table. any new packet bound for the requested destination now gets routed through the real time forwarder ✨

at the same time, the query manager sends a DNS request to read the RX records for that destination. once the response arrives, it selects a gateway and passes the info along to the real time forwarder 🧚

5.4. The real time forwarder 🔥

when the real time forwarder gets a packet, it checks whether a gateway is known for that destination. if it is, the forwarder looks at the packet and inserts the necessary source routing information. then it forwards the packet, either by resending it through the general IP routing program or by forwarding it straight to the network interface tied to the intermediate gateway 🚀

if the gateway isn't known yet, the packet goes into a waiting queue 🫠. every time the query manager sends new gateway info to the real time forwarder, the queue gets processed, and packets whose info is now available get forwarded. packets in this waiting queue "age": their time to live counts get decremented at regular intervals. if it hits zero, the packet gets destroyed, though an ICMP message may be forwarded 💀

sometimes the DNS query manager just can't find RX info for a particular destination 😭. in that case it tells the real time forwarder that the destination is unreachable. the info goes into the destination table, the queued packets for that destination get destroyed, and new packets for it won't be forwarded

the information in the destination table is not permanent 🙈 each line gets a time to live, and the aging lines get removed periodically.

5.5. Interaction with routing protocols 🌸

all that "destination unreachable" monitoring is mostly about leaving standard IP routing, and the kernel code behind it, completely untouched 🧸

if the IP routing code can be modified, and the local host has full routing tables, then it can decide to send packets to the real time forwarder more efficiently. for example, it can make that a default action for networks that aren't announced in the local tables. this is the better practice, because it avoids the risk of losing the first packet that would otherwise have triggered the ICMP message 🙌

6. Acknowledgments 🫶

we'd love to thank Yakov Rekhter, who contributed a number of really helpful comments 💜

7. Conclusion 🌈

this memo suggests an experiment in directory based routing 🔮. the author believes this technique can be deployed in the current Internet infrastructure, and that it may help us "buy time" before the probably painful migration towards IPv7 😭

the corresponding code is under development at INRIA 🇫🇷. it will be placed in the public domain. interested parties are kindly asked to contact the authors for more details ✨

8. References 📚

[1] Postel, J., "Internet Protocol - DARPA Internet Program Protocol
    Specification", STD 5, RFC 791, DARPA, September 1981.

[2] Clark, D., "Building routers for the routing of tomorrow",
    Message to the "big-internet" mailing list, reference
    <9207141905.AA06992@ginger.lcs.mit.edu>, Tue, 14 Jul 92.

[3] Fuller, V., Li, T., Yu, J., and K. Varadhan, "Supernetting:  an
    Address Assignment and Aggregation Strategy", RFC 1338, BARRNet,
    cisco, Merit, OARnet, June 1992.

9. Security Considerations 💀

Security issues are not discussed in this memo.

this section is short and sweet, but it's still a really serious one 🙈 nothing else is said about security here, so don't go assuming anything 🫢

10. Author's Address 🧚

Christian Huitema
INRIA, Sophia-Antipolis
2004 Route des Lucioles
BP 109
F-06561 Valbonne Cedex
France

Phone: +33 93 65 77 15
EMail: Christian.Huitema@MIRSA.INRIA.FR
📦 where this page comes from