 Multicasting
Alan Holt
Internet communication is predominantly unicast in
nature, in that there is only one sender and receiver. Communication with
multiple receivers, either from a single source or multiple sources, is
called "multicasting". The delivery of electronic mail provides
a simple example of multicasting. A user can send an email message to many
recipients simultaneously by specifying multiple addresses in the email
header. The message is then delivered to all recipients whose address is
listed in the To: (or Cc:) field.
This method of multicasting is somewhat crude, as a
copy of the mail message is generated for each recipient. The objective of
true multicasting is to deliver data (to multiple receivers) without
unnecessary duplication of messages. For broadcast network technologies such as Ethernet, when one station sends a
packet to another, all stations in the broadcast domain "hear"
the packet. If the destination address matches the MAC address of the network interface (because it is the intended
recipient of the packet), the packet is forwarded to the next layer of the
protocol stack, otherwise the packet is discarded.
Unicasting in this environment is merely a matter of
"filtering" unwanted packets at
the MAC layer. Broadcasting (above the MAC layer) is relatively
straightforward and packets can be delivered to multiple recipients without
duplication. Broadcasting, however, does not discriminate between hosts
that wish to receive (broadcasted) packets and those that do not. This is an important distinction
between broadcasting and multicasting. Although both are methods of
transmitting to multiple receivers, multicasting implements a more
selective delivery method than broadcasting. Furthermore, broadcasting
methods do not work well in routing networks with loops, as packets will
eventually get forwarded back
"upstream" causing a continual build up of duplicate traffic.
Time-to-live (TTL) counters can limit some of the duplication, but this is not an ideal solution.
Flooding techniques can prevent excessive duplication
of traffic. Routers keep track of each received packet and can then
determine whether a message is a duplicate. The dynamic routing protocol
OSPF uses flooding methods to propagate link-state advertisements
throughout an autonomous system (AS). However, for applications with high
bandwidth requirements, such as steaming video, this is not a viable
solution as routers would have to keep track of large amounts of state
information. If multicast methods are to provide a selective multi-receiver
delivery function, then hosts need a means of informing the network that
they wish to receive multicast traffic.
Internet Gateway Multicast Protocol (IGMP) enables
receivers to signal to routers their desire to join (or leave) a multicast
group. Routers will not, therefore, forward packets to networks that do not
have any downstream receivers. Multicast schemes also prevent packets being
forwarded around routing loops by using spanning tree techniques to create
a directed loopless graph from a subset of network links. Multicast traffic
is then forwarded from the source towards the receivers over the links that
form the spanning tree. A number of applications are conducive to multicast
packet delivery (video/audio streaming, for example).
This article introduces multicast concepts and reviews
some of the multicast functionality of Linux. Multicast protocols can be
divided into two areas: sending and receiving, and routing. I will cover
both these areas in this article, introducing IP multicast addressing and
the IGMP protocol. I'll also look at multicast routing protocols and
algorithms. Finally, I'll present a simple application to demonstrate
multicast sending and receiving.
Multicast Addressing
On Ethernet networks, a packet can be delivered to
multiple destinations by using the broadcast address, which is the 48-bit
hexadecimal number ff:ff:ff:ff:ff:ff. Sending to multiple recipients is
fairly straightforward, as Ethernet is an inherently broadcast network
technology. Upon receiving a packet with the broadcast address, the MAC
layer will forward the packet up the protocol stack. Ethernet also supports
a second multi-receiver addressing scheme. An Ethernet address with the
low-order bit set in the high-order octet specifies that the address is a
multicast address (that is 01:00:00:00:00:00).
The lower-order octets are set to reflect the
multicast group to which the packet is being delivered. When the MAC layer
receives a packet with such an address, it will only forward it up the
protocol stack if the host machine has joined that multicast group. IP uses
class D addresses for multicasting. The high-order bits of the class D IP
address are set to 1110, thus multicast addresses lie in the range
224.0.0.0 to 239.255.255.255.
IP multicast addresses must be mapped into an Ethernet
address. This is done by assigning the low-order 23 bits of the IP address
to the low-order 23 bits of the Ethernet address 01:00:5e:00:00:00. This
mapping is illustrated in Figure 1. For example, 225.10.10.1 results in an
Ethernet address of 00:01:5e:0a:0a:01. Because only the low-order 23 bits
are used, the mapping does not result in a unique address, therefore,
225.138.10.1 also maps to 00:01:5e:0a:0a:01.
The multicast group addresses in the range 224.0.0.0
to 224.0.0.255 are reserved by IANA (the Internet Assigned Number
Authority) for routing, low-level topology discovery, and maintenance
protocols. Packets addressed to groups in this range are not forwarded by
routers. Table 1 shows some examples of IANA assigned addresses. The
command-line below sends a ping to the all-hosts multicast group address:
$ ping -c2 224.0.0.1
A number of replies should be received (depending upon
how many multicast-capable machines reside on your network). The remaining
multicast address space (224.0.1.0 to 238.255.255.255) is globally scoped
and can be used for general multicast applications. See Table 1.
IGMP
The IGMP enables hosts to inform local multicast
routers, called designated routers (DR), that they wish to join a multicast
group. A host declares its membership of a multicast group by sending an
IGMP host membership report on the all-hosts multicast group address
(224.0.0.1). The DR (or DRs, as there may be more than one) will then send
join messages upstream, towards the source so that the necessary routing
can be set up for that multicast group. If a host on the same subnet has
already registered its membership of the same group, then routing will have
already been established and no action is necessary. An application
requests to join a multicast group by setting the IP_ADD_MEMBERSHIP socket option:
struct ip_mreq mreg;
setsocketopt(socket, IPPROTO_IP, IP_ADD_MEMBERSHIP,
(char *) &mreq, sizeof(mreg));
In the Linux kernel, the ip_mc_join_group function is called when the setsocketopt system call is invoked. If an application has previously
joined the multicast group and the interface is currently a member, then an IGMP message is not sent; the kernel merely increments the number of users for that
group for that particular interface:
if (im->multiaddr == addr) {
im->users++; ip_mc_add_src(in_dev, &addr,
MCAST_EXCLUDE, 0, 0, 0); 4
goto out;
}
Consequently, when an application leaves a group,
either by closing the socket or setting the IP_DROP_MEMBERSHIP option, im->users is decremented.
When im->users reaches zero, an IGMP leave message is sent. The DR will periodically poll hosts on the subnet
to determine continued membership. If no hosts respond to the query, then
the router removes itself from the multicast tree. In fact, the tree is
"pruned" all the way back to the first router with downstream
receivers for that group. To support sending and receiving of multicast
packets on a Linux machine, the kernel must be built with the option CONFIG_IP_MULTICAST=y. This is typically automatically set with most
distributions. An interface can be configured for multicasting by setting
the multicast flag with ifconfig. Again, this is likely to be unnecessary as most device
drivers set it automatically. To check that multicasting is configured on a
network interface (assuming your network interface is eth0), issue the
command:
$ ifconfig eth0 | grep MULTICAST
UP BROADCAST RUNNING MULTICAST MTU:1500 Metric:1
See Figure 2.
Routing Protocols
The purpose of multicast routing protocols is the
efficient delivery of packets from a source (or sources) to all members of
a multicast group. In this section, I'll describe three examples of
multicast protocols: DVMRP, MOSPF, and PIM.
Distance Vector Multicast Routing Protocol (DVMRP) is
a multicast routing protocol based upon the RIP unicast routing protocol.
As the name suggests, it is a distance vector protocol. Furthermore, it
uses the reverse-path multicast (RPM) algorithm (multicast routing
algorithms are discussed later). DVMRP initially floods multicast data and
prunes branches of the tree with no downstream receivers.
Multicast Open Shortest Path First (MOSPF), like its
unicast counterpart OSPF, derives routing information based on link states
advertisements generated by routers. From the link state information, MOSPF
is able to determine the topology of the network. Unlike DVMRP, it does not
have to flood multicast traffic and then prune back.
There are two variants of Protocol Independent
Multicast (PIM): dense mode (DM) and sparse mode (SM). PIM-DM is similar to
DVMRP in that it initially floods then prunes back. Routing protocols such
as DVMRP, MOSPF, and PIM-DM are most suitable for dense multicast
environments where receivers are highly concentrated within a specific
area. PIM-SM was designed to operate in environments where receivers are
few and widely distributed (sparse environments). Furthermore, PIM-SM
(unlike DVMRP, MOSPF, and PIM-DM) is not an extension of any unicast
routing protocol. With PIM-SM, traffic is routed over a
"shared" tree. That means the tree is the same for all members
of the group, regardless of which one is the source. This is in contrast to
dense mode protocols where a new tree is formed for each source and group.
PIM-SM, therefore, requires less routing resources. With PIM-SM, routers
with downstream group members are required to register with a rendezvous
point (RP). The source sends packets to the RP (some router configured for
the part), which then forwards them to downstream DRs with group members.
To support multicast routing, the Linux kernel has to
be built with the following options set:
CONFIG_IP_ROUTER=y
CONFIG_IP_MROUTE=y
CONFIG_NET_IPIP=y
This allows routing of multicast traffic with mrouted, for example, which is
an implementation of DVMRP. If you want to use PIM (with pimd) then the
PIMv1 and PIMv2 kernel options also need to be set.
Multicast Routing Algorithms
IEEE-802 MAC bridges use a spanning tree algorithm to
ensure duplicate MAC frames are not propagated over the bridged network.
The spanning tree algorithm can also be used for multicasting routing, as
it forms a loop-less tree structure over the network. The network diagram
in Figure 3 shows a multicast source and a set of distributed receivers
interconnected by a (partially messed) router network. A shared spanning
tree is formed (bold lines) between the routers with downstream receivers.
Routers v1, v2 , v3, and v4 are part of the spanning
tree because they have downstream receivers: r1 , r2 , r3, and r6
(receivers that have issued a join to the multicast group). Router v1 has
no receivers directly connected to it but does have receivers downstream,
so it must participate in the spanning tree. Router v5 is not part of the
spanning tree because r5 has not issued a join. Receiver r4 has not issued
a join, but r3 has, so v4 is part of the tree.
This algorithm, however, only implements a single
tree across the network for all multicast senders and receiver groups.
Consequently, the path between any given sender and its receiving group
(through the spanning tree) may not be optimum. For example, if a second
multicast source were introduced at router v4, and r6 was a member of the
multicast group to which it was sending, then the traffic would take a
suboptimal path via v2 and v1 instead of the more direct route over the
link connecting v4 and v3. In addition to increased propagation delays,
traffic is concentrated on specific links of the network (those that make
up the spanning tree), which can lead to congestion.
Reverse-Path Forwarding
The solution to this problem is to build multiple
spanning trees, one for each sender/receiver group. A technique called
reverse-path forwarding is used for this purpose. The term reverse-path
forwarding actually covers a number of multicast routing algorithms.
Packets are multicasted in a router network by forwarding them on all
interfaces other than the one on which it arrived. When a router receives a
multicast packet on some ingress interface it checks to see whether the
packet is eligible for forwarding by performing a reverse-path check. If
the interface on which the packet arrived is on the shortest path back to
source, it is forwarded (hence the term reverse-path); otherwise, it is
discarded.
The most basic form of the reverse-path forwarding
algorithm is reverse-path flooding (RPF). Figure 4 illustrates how RPF
works. Router v1 receives a multicast packet on link 1. It performs a
reverse-path check, determines that link 1 is indeed on the shortest path
back to the source, and so forwards the packet out on all links other than
link 1. Routers v2 and v3 also perform the reverse-path check and forward
the packet in the same way. However, both v2 and v3 will receive a
duplicate of the packet from each other on link 5. As this (duplicate)
packet arrives on a link that is not on the shortest path, it fails the
reverse-path check and is discarded. In this regard, the RPF algorithm
exhibits some "broadcast" behavior in that packets are sent
unnecessarily.
The problem of packet duplication is more pronounced
when multi-access networks are involved because there are potentially many
routers forwarding (duplicate) multicast traffic onto the network.
Reverse-path broadcasting (RPB) is another reverse-path forwarding
algorithm and is designed to prevent this duplication of packets. The RPB
algorithm is an enhancement to the flooding variant RPF. For any given
source, one router is selected as parent of each link. The router that
advertises the lowest cost to the source is designated as the parent (in
the event of tie, the parent router is the one with the lowest IP address).
Only the designated parent forwards multicast traffic.
The RPF and RPB algorithms deliver packets (for a
given source) over a shortest path broadcast tree. Packets are forwarded
regardless of whether there are downstream receivers. This method is
acceptable for small networks, but for large internets, undue load can be
placed on network and router resources. Truncated reverse-path broadcasting
(TRPB) is an enhancement to RPB, whereby leaf networks, with no group
members, are deleted from the broadcast tree. Leaf networks are networks
that no other router uses to get to the multicast source. The final variant
is reverse-path multicasting (RPM). The RPM algorithm implements a more
aggressive pruning strategy, in that the broadcast tree is pruned as far as
those routers that have downstream members.
A Simple Multicast Application
Now I'll show how to implement a simple
multicast sender and receiver. Listing 1 shows the C code for the receiver
program (mrec.c). The code is not dissimilar from that of a unicast
receiver. It opens a datagram socket (specified by the option the SOCK_DGRAM) using the socket system call. This means that the UDP transport
protocol is used (rather than TCP). The option IP_ADD_MEMBERSHIP is set with the setsockopt system call. This
causes the host to join the multicast group by issuing an IGMP host
membership report. In this case, the group is 225.10.10.1, which is
hardcoded in the mreq struct. Similarly, the UDP is hardcoded to 12345 (not the best
programming practice but will suffice for the purpose of this
illustration). The program then goes into an infinite loop receiving
multicast packets just as it would for unicast communication.
The code for the sender application is shown in
Listing 2 (msend.c). There is little difference between sending multicast
packets and unicast packets. The only real difference is that a multicast
address is given as the destination address (again, hardcoded to
255.10.10.1) instead of a regular unicast
address; and that the TTL has to be set. The TTL for a multicast packet is
set to one by default; the setting in the Linux kernel can be found in the
source file net/ipv4/af_inet.c:
sk->protinfo.af_inet.mc_ttl = 1;
This limits the scope of the packet to the local
network. When the designated router receives the packet, it will decrement
the TTL by one (to zero) and the packet will be discarded. The TTL,
therefore, has to be set to a value greater than one in order to extend the
scope of the packet beyond the local network.
The setsockopt is used to set the IP_MULTICAST_TTL option. Note that,
if it is not necessary to send multicast packets beyond the local network,
then even this step would not be needed. Setting the TTL (greater than 1)
only affects packets with globally scoped addresses. Packets with
IANA-reserved addresses are not forwarded by routers regardless of the
value the TTL.
Compile the mulitcast send and receive programs:
$ gcc -o msend msend.c
$ gcc -o mrec mrec.c
Start the receive program:
$ ./mrec &
[1] 16031
Use the netstat -g command to determine in which multicast groups the host is
a member. It shows that the host (on eth0) is a member of the all-hosts
group 224.0.0.1 (ALL-SYSTEMS.MCAST.NET) and, as
a result of running mrec, group 255.10.10.1:
$ netstat -g
IPv6/IPv4 Group Memberships
Interface RefCnt Group
--------------- ------ ---------------------
lo 1 ALL-SYSTEMS.MCAST.NET
eth0 1 225.10.10.1
eth0 1 ALL-SYSTEMS.MCAST.NET
Now run msend:
$ ./msend hello
hello
If everything works correctly, the string passed to msend on the command line (in
this example, "hello") is displayed on screen. This is the
output from mrec,
which it received from msend. To test this fully, run mrec on two (or more) other networked machines. If msend is run on this machine,
both instances mrec should
display the "hello" message (almost) simultaneously. If your
routers are configured for multicasting routing, then this application
should work on machines on different networks. Otherwise, make sure the
machines should be connected to the same network.
Summary
Using unicast methods to transmit data to multiple
hosts is inefficient and broadcasting merely forwards packets regardless of
whether there are any downstream receivers. Also, broadcasting is
problematic in routed networks with loops as packets (eventually) get
forwarded back up stream.
Multicasting provides an efficient method of
delivering packets to multiple receivers. Protocols (such as IGMP) enable
hosts to signal to routers their desire to join (or leave) a multicast
group. In this way, multicast packets are delivered selectively to those
parts of the network with downstream receivers.
Most multicasting routing algorithms are based on
reverse-path forwarding, of which there are a number of variants. The
algorithm forms a spanning tree for each multicast source/group. This
method is favored by dense routing protocols such DVMRP and PIM-DM. PIM-SM,
on the other hand, is designed for sparse multicast environments, packets
are forwarded along a shared tree from a rendezvous point in the network.
Alan Holt is a senior lecturer in the Department of
Computing and Mathematical Sciences, University of Waikato, New Zealand. He
worked as network engineer for AT&T in the UK for 13 years. Alan holds
BSc and PhD degrees in computer science and telecommunications,
respectively. He can be contacted at: aholt@cs.waikato.ac.nz.
|