Communications of the ACM

single administrative authority, which is responsible for providing the network’s services with their specified properties. Bridging is a composition operator in which sessions or services are implemented by a set of networks chained end-to-end. With bridging, the two endpoints of a session can be members of different networks. The public Internet consists of a large number of autonomous IP networks, composed by bridging.

There are several variations on bridging, depending on how much structure the bridged networks share. In the simplest case two bridged networks have identical designs and protocols, names of all network members are unique across both networks, and members of both networks have access to the routing and directories of the other. In this simple case, the networks can be bridged by shared links, and little changes except that the reach of both networks is extended. This is how public IP networks are bridged.

In other cases, bridged networks are less similar. They may have different or overlapping namespaces. They may have unshared routing, unshared directories, or other barriers. In these cases a member of one network can still reach a member of a bridged network, but only with the addition of compound sessions. A compound session is simply a session in which there is at least one middlebox acting as a joinbox. The joinbox serves as a destination for one simple session and a source for another simple session, and maintains state that associates the two simple sessions so it can forward packets from one to the other.d If two bridged networks have incompatible session protocols, then a joinbox, acting as a protocol converter, must be the shared element between them.

We will now introduce a simple, familiar example, which will illustrate bridging, trust, and service verification. Figure 4 shows two private networks communicating through the public Internet, although their relationships to the public Internet are d A joinbox must change at least one of the source or destination in the session header; it may or may not be a “proxy,” which is a ses-sion-protocol endpoint. For example, the NAT in Figure 4 is a joinbox and not a proxy.

ery network simply has a namespace,
and network members have names in
the namespaces of their networks. In
the literature of networking, names
in various networks are also referred
to as “service names,” “identifiers,”
and “locations.”
In every instance of layering compo-
sition, a network A uses a network B.
Some members of A must be running
on the same machines as members
of B, and interfacing with them to get
network services. If B must set up ses-
sions dynamically to serve A, then there
must be a directory mapping names in
A to the names of the members of B
on the same machines. For example,
a Web request is sent from a client to
a server having a domain name in the
Web namespace. For an IP network
to implement this communication, it
must discover the network name (IP
address) of the server, which will be the
destination of the TCP session carrying
the request. DNS is the directory pro-
viding this information.c
The new model does not constrain
internal implementation details of
networks. For example, although most
networks store member-specific for-
warding tables in individual members,
in SEATTLE there is a single (although
distributed) forwarding table used by
all members. 15 And although many
networks have centralized directories,
in Ethernets the directory information
obtained from the Address Resolu-
tion Protocol is cached in individual
members. Thus forwarding state and
directory state cannot always be dis-
tinguished by the way they are imple-
mented. But they can always be dis-
tinguished by what they are mapping:
forwarding state maps destination
names to members/names in the same
network, while directory state maps
names from one network to names in
another network.

Service properties and compositional reasoning. A network offers to its users one or more communication services, each specified as a set of properties, and some associated with the use of specific session protocols. Some properties are defined on individual sessions, while others are defined on c In cases where DNS maps a domain name to the server nearest the client, the domain name does not uniquely identify a server.

aggregates of sessions. In general, the properties fall into four categories:

• Reachability properties specify which receivers a member can send packets to.

• Performance properties specify quantities such as maximum latency, minimum bandwidth, maximum packet loss rate, and faults tolerated.

• Behavioral properties are more ser-vice-specific. In addition to TCP guarantees, they include synchronization, load balancing among user endpoints, and the requirement that a session must persist despite physical mobility of one or both endpoint machines.

• Security properties are diverse. For example, access control is the negation of reachability. Denial-of-service protection supports availability. Security properties on individual sessions include endpoint authentication, data confidentiality, data integrity, and privacy.

In addition to providing specified services, network designers and operators are also concerned with efficient resource allocation, so that the services are provided at minimal cost.

Basic reasoning about composition by layering is easy to explain. There should be a one-to-one mapping between implemented links and implementing sessions. The packet load on the link, possibly fragmented into smaller packets, becomes the packet load on the implementing session. The guaranteed properties of the session become the assumed properties of the implemented link.

Although such rigor is not always needed, it should be possible to reason that a network satisfies its service specifications, and that its use of resources is close to optimal. Network designers have been very successful at this, at least with respect to performance properties. They have learned to abstract the effects of used and using networks, and have developed effective optimization algorithms and tools for self-contained networks.

Reachability, behavioral, and security properties are not so well understood. Next, we discuss examples in which the new model captures the structures and relationships needed for reasoning compositionally about these properties.