Communications of the ACM

packets and do not behave as session endpoints. The middleboxes advertise the mobile range of IP addresses into the public Internet, which means each packet destined for an address in this range will be forwarded to one of them. The LISP-MN network has a directory mapping identifiers of mobile nodes to their current locations. When such a middlebox receives its first packet for ident2 (or first in a long time), it gets ident2’s location loc2 from the directory, creates a dynamic link to ident2, and forwards the packet on it. Subsequent packets to ident2 use the same link.

The LISP-MN network is layered on top of the public Internet, so that dynamic LISP links are implemented by public UDP sessions. On the same machines as the three members of the LISP-MN network there are members of the public Internet with IP addresses addr3, addr4, and loc2, and these are the endpoints of the UDP sessions. When a mobile node changes its location, it notifies all the middleboxes with which it has dynamic links, and also updates the directory. The UDP sessions will move to the new location, but the LISP-MN links will remain.

Like Figures 3 and 4, Figure 5 uses vertical position to imply a usage graph. In this usage graph, the LISP-MN network is both bridged with the public Internet (at the same level) and layered on it. To avoid drawing the cycle, we depict the public Internet in two places. This graph shows a common pattern for interoperation of special-purpose IP networks with the public Internet.

Figure 3 is another example of a usage graph with a cycle in it. As in Figure 5, rather than drawing a cycle, we have put a network— here the campus IP network—in the figure twice. At the bottom level of the figure, the only physical connection between LANs is the campus IP network. The link shown is exactly the same as the link between 0.4 and 0.5 at the top level of the figure. When an IP packet is sent from source 2. 7 to destination 2. 8, it is encapsulated in a VLAN header with source M7 and destination M8. When that packet is traversing the VLAN link between M4 and M5, it is further encapsulated in an IP header with source 0.4 and destination 0.5.

same machine. The same verification pattern works for more complex security mechanisms, however. The common structures are a secure network layered on top of the public Internet, and a packet-filtering mechanism that prevents harm (including denial-of-service attacks) at the level of the public Internet. 1 The secure overlay carries only approved packets, as enforced by its ingress members. The packet filters are on different machines, and need only have enough knowledge to reject packets not belonging to sessions implementing links of the overlay.

These examples barely scratch the surface of network security. Nevertheless, a broad survey of security mechanisms24 has shown that the compositional model is important for understanding all aspects of security, and for working toward a comprehensive proof framework. The model is especially valuable for discovering how security interacts with other aspects of network architecture such as session protocols, routing, virtualization, and middleboxes.

The Usage Graph

One of the most interesting aspects of composition is that sometimes the “usage hierarchy” is a convenient fiction, because composition creates a usage graph with cycles. It is still useful to think in terms of usage hierarchies,

provided that we remember they are approximate abstractions with localized exceptions.

Mobility is a network service that preserves reachability to a network member, and may even preserve the member’s ongoing sessions, even though the member’s machine is moving. One kind of mobility is provided by LISP Mobile Node8, 9 (for a survey of all kinds of mobility, see Zave and Rexford23). With LISP-MN, a machine has a network member with a persistent IP address called an “identifier.” In a lower-level IP network, the machine has a member with a temporary, location-dependent IP address called a “location.” As a new and lightweight way to provide mobility, LISP-MN must interoperate with the public Internet. Figure 5 shows how. As in Figure 4, the public Internet is depicted as if it were one network.

At the top level of this figure, the public Internet is bridged with a LISP-MN network, which is a specialized IP network. The LISP-MN network owns a range of IP addresses, from which identifiers are drawn. Because of the bridging, a legacy host with IP address addr1 has been able to initiate a TCP session with a mobile node whose identifier is ident2.

The shared elements for bridging are the unlabeled middleboxes. In both networks these middleboxes resemble IP routers, in that they forward

Figures 5. The interoperation of LISP-MN with the public Internet.

Each link (solid line), session (dashed line), or path of links and forwarders (solid line broken with dots) is labeled above with the source of the packets traveling on it, and below with their destinations.