XIA 101

Warning: for some reason, GitHub is no longer showing the DAG addresses inside of the text in the graph form, but as the commands to generate them. For example, you see the commands <math>\bullet\rightarrow XID_1</math> instead of a graph. If you find this confusing, consider reading section 2 of the paper Linux XIA: An Interoperable Meta Network Architecture to Crowdsource the Future Internet. That section is a close equivalent to this page.

XIA's central goal is an evolvable and secure Internet architecture. By evolvable, XIA means having an explicit, well defined, incremental path to introduce changes to its network protocol, which is called the eXpressive Internet Protocol (XIP). These changes are introduced and removed in units; each of these units is a principal. By secure, XIA means providing the capabilities to deliver security guarantees to applications. XIA's main vehicles to carry evolution and enable security guarantees are, its expressive network addresses and the intrinsic security found at its network identifiers, respectively. The remainder of this page presents the key concepts of XIA's design and puts these concepts together to form sample addresses. While the content here serves as a quick introduction or a refresher, readers might want to complement this section with the paper XIA: Efficient support for evolvable internetworking.

In order for principals to influence the forwarding mechanism of XIP, they must introduce their own identifiers. These identifiers are called eXpressive IDentifiers (XIDs), and name any object or concept that principals define. Each XID is the pairing of a principal type (32 bits) and a name or ID (160 bits). Example of principals and corresponding XIDs are the Autonomous Domain (AD) principal, which names XIA networks, the Host (HID) principal, which names any machine (virtual or not) with an XIA stack, and the Content (CID) principal, which names immutable content.

Intrinsic security cryptographically links each XID's name to some property. For example, AD XIDs are the hash of public keys of the networks they name, HID XIDs are the hash of public keys of the machines they name, and CID XIDs are the hash of the contents of the file they name. When a network delivers to an application the file corresponding to the requested XID <math>CID_1</math>, the application can verify that it received the correct file by hashing the content of the file and comparing the hash against the content name <math>CID_1</math>. The hash of a public key allows an application to obtain the corresponding public key from any source, trusted or not, verify that it is the correct public key, and from there, bootstrap a secure communication to the entity bound to that public key. While it is desirable to have intrinsic security for all XIDs, this is not always attainable.

XIP addresses amalgamate principals' behaviors to accomplish application-level intents, and are represented as single-component, single-source, single-sink directed acyclic graphs (DAGs) of XIDs. The ultimate intent of a packet is expressed in the XID of the sink node of the destination address. The entry node of an address, represented by a dot (<math>\bullet</math>), has the sole purpose of pointing to where the navigation of the DAG begins, and thus the simplest, nonempty XIP address is <math>\bullet\rightarrow XID_1</math>. While destination addresses must be nonempty, source addresses can be empty. All other (internal) nodes of an address represent XIDs, and each node is associated with between one and four strictly prioritized outgoing edges; four being the maximum fanout supported in XIP addresses.

Routers are required to forward packets according to the intent expressed in each DAG destination address. Therefore, a valid set of packet forwarding decisions at routers must correspond to a successful traversal of the DAG from entry node to sink to achieve the final intent. How is this accomplished? First, the XIP header records the DAG as a collection of nodes and their prioritized edges. Additionally, the XIP header records a dynamic LastNode pointer to one of the nodes in the DAG. This pointer, initially set to the entry node, reflects the portion of the DAG that has been realized by this packet by forwarding decisions so far. Thus, when the packet reaches the intended destination, the LastNode will point to the sink.

To forward a packet, a router first inspects the LastNode field to identify the progress made through the DAG so far. For each of the outgoing edges from the referenced node, in priority order, the router attempts to forward on the corresponding XID. If that XID is local to that router (for example, the XID is an AD and the router is in that domain), the router updates the LastNode field of the packet and either recurses on the forwarding decision, or, when LastNode points to the sink, delivers the packet to the corresponding principal of the sink node. Otherwise, if the XID is non-local, the router forwards the packet toward the designated XID, as normal. Finally, if the router cannot forward along any of the outgoing edges of the DAG, the address is not reachable and the packet is dropped.

Among the many address structures that DAGs afford, three addressing patterns are commonly used to date: scoping, fallback, and iterative refinement. Scoping a CID to a given host can be accomplished with an address like <math>\bullet\rightarrow HID_1\rightarrow CID_1</math>; this address requires packets first be forwarded to host <math>HID_1</math>, and from there, on to <math>CID_1</math>. When a new principal is being deployed, chances are that many routers in the network do not know it, this can be addressed with the fallback pattern, which uses a lower priority edge to route to a well-known principal in case the new principal is not known by the router making the routing decision. For example, assuming that principal CID is not largely deployed, one can still reach <math>CID_1</math> even if <math>HID_1</math> is the only host aware of the CID principal (dashed edges reflect lower priority):

Finally, the iterative refinement pattern combines scoping and fallback patterns. In the event host addresses such as <math>HID_1</math> are not globally routable, we can have <math>CID_1</math> fall back to an AD XID (<math>AD_1</math>) where <math>HID_1</math> is presumed to reside: