|
 The
logical hypercube overlay network topology organizes the applications
into a logical n-dimensional hypercube. Each node is identified by a
label (e.g., "010"), which indicates the position of the
node in the logical hypercube.
One advantage of
using a hypercube is that each node has at most log(N) neighbors,
where N is the total number of nodes. Also, the longest route in
the hypercube is log(N). One disadvantage of hypercubes is that
they completely ignore the physical network infrastructure. Another
disadvantage is that the hypercube construction must be done
sequentially, i.e., one node at a time. Therefore, for large groups,
it can take a long time before the overlay network is built. Also, the
departure of a single node may require substantial changes to the
overlay topology.
We refer to [HCOverlay]
for a detailed description of a protocol that builds hypercube
topologies. The protocol has been tested with up to 10,000 nodes
running on up to100 hosts (see [BEAM99]
and [LORIN01]
).
- Delaunay
Triangulation
 A
Delaunay triangulation is a special type of triangulation. Its main
characteristic is that for each circumscribing circle of a triangle
formed by three nodes, no other node of the graph is in the interior
of the circle. Each node in a Delaunay triangulation has (x,y)
coordinates which depict a point in the plane. In Figure 1.3, we
show a Delaunay triangulation of five nodes and the circumscribing
circles of some of its triangles.
An
advantage of the Delaunay triangulation overlay network topology is
that it can be constructed in a distributed fashion. Therefore,
Delaunay triangulations can be built very quickly. In a
Delaunay triangulation, each node has, on the average, six
neighbors. In the worst-case, the number of neighbors of a
node is N-1, where N is the total number of nodes.
If the coordinates
of a node in the Delaunay triangulation reflect the node’s
geographical location, then nodes in the overlay network are likely
to be neighbors if their geographical location is close. However,
Delaunay triangulations are not aware of the layer-3 network
infrastructure.
A protocol that
builds a Delaunay triangulation overlay network is described in [HCOverlay].
The Delaunay triangulation topology has been tested with up to
10,000 running on up to 100 computers (see [LIEBE01b]
).
There are several
criteria to evaluate an overlay network topology. We discuss how the
hypercubes and logical Delaunay triangulations perform for some
important criteria.
- Need for global
information: The
scalability of an overlay network, in terms of the achievable size
of the overlay network, is limited if the state information at a
node grows fast with the number of nodes in the overlay network. In
both HyperCast topologies, the state information at each node is
limited (with the exception of worst-case scenarios in the Delaunay
triangulation).
- Effort to build
and maintain the overlay topology: Ideally,
the number of computations performed after a node joins or leaves
the overlay network should be constant. The hypercube satisfies this
for adding nodes to the overlay network, but not for removing them.
The Delaunay triangulation satisfies this for both the average case
of adding nodes and the average case of removing them.
- Need for a routing
protocol in the overlay: For
data forwarding in an overlay network, nodes generally maintain a
routing table which determines the next-hop for the data towards its
destination or destinations. Most existing overlay network
approaches require the nodes to run a shortest path algorithm in
order to establish the routing tables. In contrast, hypercubes and
Delaunay triangulations can use the logical addresses of nodes
(binary strings or coordinates) to determine next hop routing
information. This eliminates the need for routing protocols.
- Match of the overlay
network to the Internet topology:
Data forwarding in overlay networks is done at the application
level. Therefore, data may traverse the IP network several times
before it reaches its destination or destinations. This may
result in inefficient use of network capacity and increased delays
compared to transmission at the IP layer. These disadvantages, which
are shared to some degree by all overlay network topologies, are
least pronounced if the overlay network is constructed with respect
to the of the underlying Internet topology. Since the overlay
topologies of HyperCast are constructed without awareness of the
Internet topology, the overlay networks may not be good matches for
the underlying Internet topology. We refer to [LIEBE01a]
for a comparative evaluation of the HyperCast and other overlay
network topologies.
Data
is exchanged in the overlay network as formatted messages. Data
transmission between two members of an overlay network can be done with
either UDP or with TCP. An application selects a specific overlay
topology and a specific protocol for data transport when it instantiates
an overlay socket.
In
HyperCast, all data is transmitted along trees that are embedded
in the overlay network topology. For each member of an overlay network,
there is an embedded spanning tree in the overlay network with that
member as the root of the tree. Given the root of an
embedded tree, each member of an overlay network can locally determine
its children and parent with respect to that tree. Each member forwards
data to its children or parent in an embedded tree with respect to a
specific node.
Hence,
an important requirement for HyperCast overlay topologies is that, given
the root of an embedded tree, each member of an overlay network can
locally determine its children and parent with respect to that tree. The
node forwards data either to its children or to its parent.
Multicast
transmission in an overlay network is transmitted in the embedded tree
that has the multicast sender as root. If an overlay member receives a
multicast message, it passes the message to the application and forwards
the message to all of its child nodes in the embedded tree.
Unicast
transmission is performed by sending data upstream in an embedded tree.
A unicast message is forwarded to the parent in the embedded tree that
has the destination as the root.
The HyperCast
software is built around the notion of an overlay socket (OL Socket). An
Overlay socket is an endpoint for communication in an overlay network.
An overlay socket provides application programs an interface for
communications over a logical overlay topology. The application
programming interface (API) of an OL Socket offers applications the
ability to
- join
and leave existing overlays;
- send
data to all or a subset of members of the overlay network;
- and
receive data from the overlay.
The HyperCast software is
structured around components which are part of an overlay socket
or that interact with an overlay socket. The main components of an
overlay socket are shown in the figure below:
- Overlay
Node (OL Node): The overlay node implements the protocol that
establishes the overlay network topology. Currently, two overlay network topologies are supported: a logical
hypercube, and a logical Delaunay triangulation. The overlay
node is the only component of an overlay socket that is aware of the overlay topology.
- Forwarding Engine:
The forwarding engine is responsible for sending, receiving, and
forwarding messages in the overlay network. The forwarding engine
communicates with the overlay node to obtain next hop routing
information for messages.
- Application
Transmit Buffer and Application Receive Buffer: The application
transmit buffer contains untransmitted messages which are buffered
due to rate control or congestion control constraints. The
application receive buffer contains messages which are received but
have not yet been read by the application. If the receive operation
uses upcalls, there is no need for application receive buffers.
- Message
Store: The message store is a repository of transmitted messages
which buffers messages and maintains state information about
messages. The message store aids in the provisioning of services
with various reliability semantics, synchronization, and others.
- Statistics: Each
component of an overlay socket supports an interface for monitoring
and managing its properties. The interface for accessing statistics
is similar for all components.
- Adapters:
Messages in the overlay can be transmitted over different transport
protocols, UDP or TCP. The adapters provide the interfaces for a
specific transport protocol. Each overlay socket has two adaptors.
The node adapter is the network interface for the overlay
node, the socket adapter is the network interface for application
data.
The
following components are external to an overlay socket but
interact closely with an overlay socket.
Writing
Programs with HyperCast |
The overlay networks of HyperCast adapt each time an application joins
or leaves the overlay network. Specifically, when a node fails the
overlay network repairs itself.