Part D
Special Topics
Pricing Communication Networks: Economics, Technology and Modelling.
Costas Courcoubetis and Richard Weber
Copyright 2003 John Wiley & Sons, Ltd.
ISBN: 0-470-85130-9
11
Multicasting
A unicasting service is one that requires the network to provide point-to-point transport
between just one information source and one receiver. A multicasting service extends this
idea by requiring the network to provide transport between one or more information sources
and a group of receivers. Multicasting services can be used for teleconferencing, software
distribution and the transmission of audio and video. A key characteristic of a multicasting
service is that it its cost must be optimized for the particular group of receivers to which it
provides service. This poses important resource management and control problems, which
add new complexity to pricing issues.
A special case of multicasting is broadcasting . Broadcasting is simple, in that the same
information is continually made available to all potential receivers, and so there is no need
to optimize network resources to the subset of receivers that is presently listening. The
transmission rates and network resource allocation are fixed, and the transmission cost is
independent of the customer group. If broadcasting technology is in place, then we can
multicast information by broadcasting it, but only granting the subscribers of the multicast
the permissions to access or decode it.
Multicasting over a data network such as the Internet requires far more complex resource
management than does broadcasting. This is because there are different mechanisms
available at the network level, and the identities of the end receivers can influence
routing decisions about which links of the network should carry the multicast traffic. Also,
whereas satellite broadcasting typically uses constant bit rate channels, applications that
use data network multicasting services may produce bursty data flows and have more
flexible quality of service requirements. In this chapter, we investigate the issues of
resource allocation and pricing that arise when multicasting services are to be provided
over a data network like the Internet. We see that the final resource allocation may
depend upon decisions taken by a large number of participants. This contrast with unicast,
where one of the two connected parties makes all the decisions about the properties
of the connection and is responsible for paying the bill. Hence, if one is to achieve
globally efficiency by giving appropriate incentives to the various decision-makers, there
are many delicate gaming aspects that can make pricing very complex. Of course,
we can always view a single unicast connection as the simplest case of a multicast
service, in which the sender and the receiver make independent decisions and so must
agree on common features of the connection, such as the bit rate and how to split the
network charge.
Pricing Communication Networks: Economics, Technology and Modelling.
Costas Courcoubetis and Richard Weber
Copyright 2003 John Wiley & Sons, Ltd.
ISBN: 0-470-85130-9
264 MULTICASTING
In Section 11.1 we set out some requirements for multicasting. In Section 11.2 we
describe some basic technologies for it. Section 11.3 considers mechanisms for providing
quality of service and Section 11.4 addresses flow control. Starting from a model for
allocating bandwidth to elastic multicast traffic, Section 11.5 considers issues of cost sharing
and the formation of the multicast tree. Section 11.6 is about settlement.
11.1 The requirements of multicasting
Multicasting is potentially a very promising network service for IP technology networks.
Great efficiency can be achieved by arranging that only one copy of the data transverses
any common paths on its way towards multiple destinations. For example, in satellite
broadcasting there is a single common path; all receivers share the same set of broadcast
channels, all of which are transmitted over the same link.
Multicasting services provide positive network externalities. Since a customer shares
common cost with other customers he can access services that he would otherwise find too
expensive. However, there is a negative externality, since a customer may not be able to
choose the precise type and quality of the service that he desires. His choices are restricted
because other customers in his multicast group value service differently or have different
technological capabilities. These issues make the pricing of multicasting services interesting,
but complex. As for unicast services, pricing plays an important role in controlling the way
network resources are shared. A pricing policy must fairly reflect the externality effects
and provide the right incentives for customers to join or leave a multicast session when it
is economically justified from the viewpoint of the multicast group as a whole.
Before looking at the economic aspects of a multicast service model, we consider the
technology aspects. Clearly, multicast services can provide savings in network resources.
Savings occur because network routers and switches can, at no cost, copy incoming packet
flows and direct resulting identical flows to more than one output link. The network gains
by taking information that is destined for multiple receivers and forwarding it over paths
for which receivers have common parts. An inefficient network could always use traditional
unicast technology to support a multicast service. However, this would lead to unsustainable
prices since a competitor who uses multicasting would have lower transmission costs and
so could offer lower prices.
The resource savings of multicast come at the cost increased complexity. Some difficult
tasks are the scheduling of the multicast packets at the routers, the routing of the packets
inside the network, addressing, congestion control, and quality of service issues, such
as the reliability and variability of transmission. These are the subject of undergoing
research. Furthermore, many decisions depend upon the assumptions that are made about
the semantics of the multicast service, and these are often not precisely defined. The
optimal solution of some fundamental multicast problems, such as constructing the least
cost multicast tree, are very difficult and cannot be solved under practical assumptions.
It is important to distinguish between multicasting’s network implementation and multi-
casting viewed as a service. For instance, multicasting’s network implementation through IP
is based on standard IP unicast concepts, which allow IP packets originating from a set of
sources to reach a set of destinations. The semantics of such a lower-level network service
are similar to IP: packets are transported unreliably, with no guarantee on synchronization
or delay. By contrast, a multicasting service at the application layer may have requirements
for reliability, an upper bound on packet delay, and a minimum rate guarantee. It may also
require there to be mechanisms for group management (controlling who joins or leaves the
MULTICASTING MECHANISMS AT THE NETWORK LAYER 265
multicast group), negotiating various economic and service specific terms, and charging
customers. The network provider may use a lower-level service, such as IP multicast, and
then add some additional protocols to meet these requirements, or he can use other mecha-
nisms. For instance, he may substitute unicast services if these can better provide the desired
service quality, although the economies of scale produced by the specialized multicasting
technology should make this rarely advantageous. In practice, multicasting services as seen
by the end customer, are mostly defined in a bottom-up fashion. They are not shaped by
the demand for some killer application, but by the capability of the multiplexing-specific
technology that have been implemented at the various network devices.
The problem with such a ‘technology-centred’ approach, compared to one that is
‘application-centred’, is that present multicasting technology has limited capability for
supporting real-world, revenue-generating services. For example, the simple IP multicast
service model, based on existing IP multicast technology, is suitable for simple low quality
teleconferencing applications. However, it seems overcomplicated for software distribution
or TV-like applications, where only one source exists and group management and payment
capabilities are of great importance. Indeed, the presently deployed ‘open’ IP multicast
service model was not defined with a commercial service in mind, and poses severe technical
restrictions to most reasonable charging mechanisms. The absence of group management
from the model and the increased routing complexity, are perhaps the most important
reasons why there has been slow deployment of multicast services in the Internet thus far.
The fact that there are as yet no well-defined multicast services at the application layer
leaves research in these areas truly open.
As far as pricing is concerned, some very important questions must be answered. Cost-
based pricing for multicast services is strongly tied up with game-theoretic notions of
bargaining and arbitration. Since transmission cost is partly common, how should it be
shared amongst the members of a multicast group? Should a customer who obtains greater
value from a service pay a greater fraction of the common cost? Clearly so, since customers
who obtain less value will leave if they obtain negative net benefit when they are asked
to pay equal share of the cost. What pricing mechanisms will make users reveal their true
utilities? A multicast service may be offered in an uncertain and dynamically changing
environment. The number and identity of the receivers may not be known in advance, but
fluctuate during the multicast session. How can one reduce the risk of customers paying
exceedingly high prices when there is small participation, or reduce the risk to the provider
if prices are fixed at the start? If the service can be offered at various quality levels, but
only one will be actually selected, perhaps because of a constraint imposed by the receiver
with the slowest access link, how should one charge such a receiver? How could one give
an incentive for that receiver to leave if that would increase the value of the service to all
other receivers? These questions illustrate the diversity of the issues that must be addressed,
and the complexity of designing a sound pricing policy.
In the following sections we extend the models that we have used for unicast flows
to discuss the state-of-the-art in different research areas that are relevant to pricing
multicast services.
11.2 Multicasting mechanisms at the network layer
The range of applications that multicasting can support depends strongly on the capabilities
of the network technology. Important high-level features include mechanisms for knowing
the exact number of receivers, controlling access and transmission, providing security, and
266 MULTICASTING
obtaining the quality of service required for the transport of the packet flows. In practice,
the network provides some basic mechanisms with simple features, and other mechanisms
must be built on top to fit each particular application.
The basic multicasting technology proposed for the Internet is IP multicast . In keeping
with the Internet philosophies of openness and simplicity, its service model defines the
notion of a ‘multicast group’ as a group of computers connected to the Internet, which
at the network layer is identified by one specific IP address. Any host on the Internet
(member or not of the multicast group) has an equal right to send packets to, or receive
packets from, members of the group. A packet received by one member of the group (i.e.
with an IP address of the multicast group) will be forwarded by to all other members of the
group in a best-effort fashion, similar to a standard IP packet. The packet will follow a tree
of routers (i.e. a ‘multicast tree’ that connects the sending computer to all other members
of the group), and will be duplicated at each branch of the tree.
There is no control over who joins or leaves the group, who transmits to the group, and
there is no knowledge at the network layer of the identity and number of the subscribed
members. A receiver makes its subscription request to its edge-routers (i.e. the router in its
LAN that is a node in the multicast tree of routers) using the Internet Group Membership
Protocol (IGMP). The wide area multicast tree is constructed by a network layer multicast
routing algorithm/protocol such as PIM, DVMRP, CBT or MOSFP.
Two approaches have been adopted for constructing this multicast tree, each with many
variations. The basic difference between the two approaches is in whether the routing tree
that is used to distribute the traffic is the same or different for each sender in the group. If
it is to be the same for all senders, the so-called ‘group-shared approach’, then one might
like it to be the tree of routers that connects all the members of the multicast group at least
cost. However, finding this tree is related to the Steiner tree problem, which is known to
be NP-complete. Instead of trying to find an optimal tree, one could use the ‘centre-based
approach’, which constructs the shared tree by first identifying a centre router (the ‘core’ for
the multicast group. Subsequently, each edge-router in a LAN with a host that is a member
of the multicast group sends a ‘join’ message to the core router. The paths followed by the
join messages define the multicast tree. If each sender is to have its own specific routing tree
to all destinations, the so-called ‘source-based approach’, then each such tree should ideally
approximate the optimal Steiner tree. We already mentioned that solving such problems is
hard. To provide a practical solution, some protocols in the Internet use existing underlying
unicast mechanisms to set up trees from each source to the destinations, and then merge
these where they overlap. An example of both approaches is shown in Figure 11.1.
In practice, network operators have been slow to deploy IP multicast because they are
reluctant to risk the stability and efficiency of their network to such an uncontrolled service
without the opportunity to extract corresponding revenues. Note that there is no flow control
on information transmitted over the multicast tree: a single source could end-up flooding a
large part of the network.
Some important features that are missing from the present multicast service model, but
which are necessary for a simple and efficient pricing structure, are receiver counting,
authentication and access control. There are addressing issues, which arise because multicast
addresses are not controlled by a central Internet authority and so a newly created multicast
group may choose an address already used by another group. There are inter-domain routing
difficulties, due to different ISPs using different routing algorithms for constructing their
parts of the multicast tree. These issues are presently motivating a search for new multicast
routing approaches based on different service models.