Concast

Multicast service is now a reality in many parts of the Internet. The multicast abstraction uses a single network address to represent a group of receivers. When a host sends a packet to a multicast group address, the network makes its best effort to deliver a copy to all receivers in the group. The sender need not know the identities of the receivers, and indeed cannot learn them via the multicast service itself. Internet multicast is a scalable service because it hides the number and identity of receivers behind a single address, and allows a sender to communicate with any number of receivers as a single entity. Efficient multicast service implementations will duplicate packets in the network as needed thereby reducing bandwidth consumption (as compared to unicast implementations).

An increasing number of applications now require a communication service in which a receiver collects messages from many senders . This leads to the question of whether a scalable service similar to multicast can be defined for messages flowing in the opposite direction--essentially an ``inverse multicast'' service. We propose and describe such a service, which we call concast. With concast, a single network address represents a group of senders. When multiple group members send packets addressed to a single destination, only a single packet is delivered to that destination (Figure). Where a multicast datagram has a unicast source address and a group destination address, a concast datagram contains a group source address and a unicast destination address. Thus concast, too, is scalable: it abstracts away the reality of multiple senders and allows a receiver to avoid implosion--that is, processing a number of incoming packets that grows with the size of the group. Like multicast, a good implementation will conserve bandwidth by reducing or eliminating redundant transmissions.

Figure: Multicast and concast services.

$\begin{figure}\centerpsfig{services}\end{figure}$

However, the precise definition of an ``inverse multicast'' service is non-obvious. In particular, two interesting questions arise. First, what packet is delivered to the receiver (as a result of the multiple senders' transmissions)? Second, when is this single packet delivered to the receiver? We refer to the answers to these questions as the merge semantics and the timing semantics, respectively. Various merge and timing semantics are possible, and give rise to different forms of concast service.

Concast-style (i.e. many-to-one) communication patterns arise in a wide range of distributed applications. Perhaps the most prominent example is the acknowledgments (positive or negative) sent by the receivers of a message in reliable multicast. Applications that gather data from distributed machines or sensors (e.g., load balancing, distributed monitoring systems) represent another large class that can benefit from some form of concast communication model.

This project is defining and implementing two concast service models. Like multicast, both are best-effort services. The first, simple concast, provides generic, application-independent merge semantics that are the exact opposite of multicast: the network ``fuses'' identical packets from different senders into one copy that is delivered to the receiver. It also provides application-independent timing semantics: delivery of the fused packet occurs as if it were the first transmitted copy. Observe that this simple service can be used to implement nack suppression, which is useful in implementing reliable multicast: the network forwards the first nack and discards all other nacks for the same message.

Our second model is called custom concast. Because different applications are likely to have rather different concast requirements, this form allows the user of the service to define the merge and timing semantics, either by downloading code in some form or by selecting them from a predefined set. Custom concast is thus an excellent match for active networks .

As evidence that concast is a useful service, we observe that simple concast can be used to prevent implosion, allowing arbitrarily large groups of senders to reply to queries (e.g. sent by multicast), provided some subset send identical messages. In particular, it can be used to suppress duplicate responses to a query or an error (as is the case with nacks).