\section{Participant Library}

When a high-level protocol (or an application) opens a channel via
some low-level protocol, it identifies the peer with which it wants to
communicate by giving the peer's address. More precisely, as seen in
Section~\ref{upi}, the high-level protocol passes a participant
list---an argument of type {\var Part}---to {\var xOpen}.  The
participant list is simply an array of participant addresses where, by
convention, the high-level protocol identifies itself in the first
element of the array.  Although in general the high-level protocol can
list an arbitrary number of participants---a group of peers---that are
to communicate via the newly established channel, in a unicast
(one-to-one) communication, only a single other participant is
identified.

\subsection{Participant Addresses}

Each element of a participant array is actually not just an address,
but a {\em stack} of addresses; each address in the stack is a byte
string of some length.  The motivation for using a stack of addresses
to identify each participant will become clear in a moment.  For now,
here are the four operations for manipulating participant addresses
provided by the participant library:

\begin{quote}
{\var void partInit(Part *participants, int number)}\\
\\
{\var int partLength(Part *participants)}\\
\\
{\var void partPush(Part *participant, char *address, int length)}\\
\\
{\var char *partPop(Part *participant)}\\
\end{quote}

The first operation initializes a participant list that is to hold the
address stacks for the specified {\var number} of participants.  For a
typical one-to-one channel, {\var number} is two. The second operation
returns the number of participants in the participant list; e.g., two.

The third and fourth operations are used to add (remove) addresses to
(from) the address stack of a single {\var participant}.  {\var
partPush} pushes the specified {\var address} of {\var length} bytes
onto the stack, while {\var partPop} pops the next address off the
stack.  Giving a {\var length} of 0 to {\var partPush} denotes a
special {\it wildcard} address, indicating to the low-level protocol
that it is free to substitute any meaningful value.  This could be
used, for example, to allow a server to accept connections from any
client.  {\var partPop} does not include a length field since the
returned address is a NULL-terminated character string.

Now to the question of why each participant is identified by a stack
of addresses. The short answer is that addresses are too complicated
to be stored as a simple byte string. To see why, consider the
following.  First, each protocol expects participants to identify
themselves and their peers with a compound address of the form
$\langle$demux key, host address$\rangle$. Second, each protocol
defines its own notion of what participant addresses should look like.
That is, when high-level protocol HLP opens a channel (session) via
low-level protocol LLP, it identifies its peer according to LLP's
definition of addresses. Third, while all protocols define what they
expect in the form of a demux key, only a few protocols are in the
business of defining network addresses for hosts.  (IP is the only
such protocol in the Internet protocol suite.) Thus, so as not to
overly restrict the type of addresses accepted by any one
protocol---thereby making it possible to flexibly configure different
protocols on top of each other---the $x$-kernel allows protocols to
{\it under specify} the form of addresses they accept.

Practically speaking, this means that at the top of the protocol
graph, the application identifies each participant by first pushing a
host address onto the participant stack, and then pushing a demux key
that will be understood by the topmost protocol onto the stack. The
topmost protocol then pops off the first component (the demux key), but
only pops the host address off the stack if it is interested in
defining its own notion of a host address. Suppose it is not. Then,
the protocol pushes a new demux key onto the stack---one that is
meaningful to the protocol upon which it depends---and opens that
protocol. It never sees, nor cares about, the type of the host address.
This happens all the way down the protocol graph---pop off the demux
key and replace it with a demux key that the next lower level will
understand---until a protocol that cares about host addresses is
encountered. Such a protocol pops both the demux key {\bf and} the
host address off the address stack, translates the host address into
some lower-level host address, and pushes this new host address, along
with a new demux key, onto the stack.

In other words, no protocol is restricted to to being composed with
protocols that expect a certain type of host address; that is, the
protocol is under specified. Another way of saying this is that
address stacks allow protocols to be {\it polymorphic} with respect to
addresses it never examines.

\subsection{Relative Protocol Numbers}

It should be clear that the $x$-kernel was defined to allow a great
deal of flexibility in how protocols are composed together; to avoid
situations where protocol A must be composed on top of protocol B
because A contains hard-coded dependencies on B. Being able to
configure the protocol graph explicitly is one mechanism that advances
this goal. The address stack mechanism just described is another. We
now describe a third mechanism---how protocols specify their demux
key.

In most conventional protocols, a low-level protocol uses a {\em
relative} protocol number to identify the protocols above it. For
example, IP identifies UDP with protocol number 17 and TCP with
protocol number 6.  It looks for these numbers in the header of an
arriving packet to decide which high level protocol the packet should
be passed to.  These numbers are relative in that they only make sense
to IP; if we were to configure a protocol graph in which UDP and TCP
were above some other protocol, it could use some different set of
numbers to decide which protocol should receive arriving packets.

The downside of relative addressing is that the low-level protocol
needs to know about all the protocols that might be configured above
it so that it can give them distinct relative protocol numbers. To
circumvent this, protocols that have been especially
designed to use the $x$-kernel use an {\em absolute} addressing
scheme. The protocol number by which a given protocol is addressed
is independent of which protocol is doing the addressing.

The $x$-kernel reconciles these two approaches by maintaining a table
of relative protocol numbers. Rather than embed protocol numbers in
the protocol source code, protocols learn the protocol numbers of
protocols above them by querying this table using the following
operation:

\begin{quote}
{\var ProtId relProtNum(Prot hlp, Prot llp)}
\end{quote}

\noindent This operation returns the protocol number of the high-level
protocol relative to the low-level protocol.  This number will have to
be cast into the appropriate type before it can be used.

The table of relative protocol numbers can then be configured with
information that allows protocols to identify themselves according to
the standard specifications, as well as to be more freely composed in
non-standard ways. For example, the relative protocol number table
might be configured as follows:

\begin{verbatim}
#
# prottbl
#
# This file describes absolute protocol id's 
# and gives relative protocol numbers for those
# protocols which use them
#

eth         1    
{
        ip         x0800
        arp        x0806
        rarp       x8035
        #
        # ethernet types x3*** are not reserved
        #
        blast      x3001
}
ip          2
{
        icmp       1
        tcp        6
        udp        17
        #
        # IP protocol numbers n, 91 < n < 255, are unassigned
        #
        blast      101
}
arp         3
rarp        4
udp         5
tcp         6
icmp        7
blast       8
rpc         9
\end{verbatim}

This table specifies, for example, that IP is known by protocol number
{\var x0800} in the context of (relative to) protocol ETH, and that
UDP is known by protocol number {\var 17} relative to IP. Both of
these examples are valid according to the standard specifications for
ETH, IP, and UDP. Since the relative protocol numbers are carried in
the packets, it is important to use the standard values if you want
your implementation to interoperate with someone else's.  Protocol
BLAST is a non-standard protocol that one might want to configure on
top of either ETH or IP; it is given protocol numbers {\var x3001} and
{\var 101}, respectively, in these two contexts.

Notice that in addition to giving certain relative protocol numbers,
this table also assigns each protocol an absolute identifier; e.g., IP
is given id {\var 2} and BLAST is given id {\var 8}. For example, when
protocol BLAST uses {\var partRelProtNum} to learn what protocol
number to use to identify RPC, the operation returns {\var 9}; RPC's
absolute protocol number. Unlike relative protocol numbers, absolute
numbers are not transmitted in packets, so they need only be locally
consistent.