IP-Multicasting Technology Part I:
History and Overview

192.16.151.8" = 0xC0019708

The value describes a specific IP node on the network. If, however, the first four bits of the address are set to "1110", the address no longer specifies a specific node. Instead, the address indicates an IP multicast address, an IP address that describes a subset of all network nodes with IP stacks. A specific node must configure itself to "listen" for a given multicast address or set of addresses.

Another IP address that has similarities to the multicast set is that of the IP broadcast address: "255.255.255.255". This address is a special case and describes the recipient of the packet as all IP nodes, i.e. the improper subset of IP nodes. IP broadcasts are typically frowned upon as the basis for a protocol since CPU cycles, though wasted on those machines that are not interested in a given packet's contents, are still required for packet content decoding and processing.

In the original class-based description of IP addressing, IP-multicast addresses are also referred to as "Class D" addresses (having the first four bits equal to "1110"). Class D provides a range of IP-Multicast addresses from "224.0.0.0" through "239.255.255.255". All Class A, B, and C network addresses are designated as "unicast", i.e. designed to specify a specific node on an IP network. (Class "E" addresses, with the first five bits as "11110" - 224.x.y.z through 255.x.y.z, is reserved for use by the IETF to test experimental protocols on the Internet).

Since IP-Multicast was implemented after the IETF's acceptance of such non-class-based IP addressing schemes as CIDR ("Classless Internet Domain Routing"), all IP-Multicast routing protocols provide subnet masks in their routing tables and are typically not referred to as Class D addresses. These non-class-based routing protocols are analogous to their unicast cousins - RIPv2, OSPF, and EIGRP.

2.1 Well-known IP-Multicast Address Ranges

As mentioned above, the range for IP multicast addresses is between "224.0.0.0" and "239.255.255.255". The Internet Assigned Number Authority (IANA) has reserved certain portions of this address space for "well-known" purposes. The first range of reserved addresses is:

224.0.0.0 through 224.0.0.255 (locally-scoped reserved)

224.0.0.1 All Hosts
224.0.0.2 All Multicast Routers
224.0.0.3 Unassigned
224.0.0.4 DVMRP Routers
224.0.0.5 MOSPF Routers
224.0.0.6 MOSPF Designated Routers (DR)
224.0.0.7 ST Routers
224.0.0.8 ST Hosts
224.0.0.9 RIPv2 Routers
224.0.0.10 IGRP Routers
224.0.0.11 Mobile-Agents
224.0.0.12 DHCP Server/Relay Agent
224.0.0.13 All PIM Routers
224.0.0.14 RSVP-Encapsulation
224.0.0.15 All CBT Routers
--- and so on to 224.0.0.255 -

This first range is locally scoped, i.e. a router will never forward them. The following well-known address space has a wider scope and routers will forward them.

224.0.1.0 through 224.0.1.255 (globally-scoped reserved)

224.0.1.0 VMTP Managers Group
224.0.1.1 NTP (Network Time Protocol)
224.0.1.2 SGI-Dogfight
224.0.1.3 rwhod
224.0.1.6 NSS (Name Service Server)
224.0.1.21 DVMRP on MOSPF
224.0.1.39 Cisco-RP-Announce
224.0.1.40 Cisco-RP-Discovery

Finally, an "Administratively Scoped" multicast address range has been set by the IANA for use within the confines of an origination and should never be seen on the Internet:

239.0.0.0 through 239.25.255.255 (Administratively-Scoped)

These addresses can be thought of as analogous to the 10.0.0.0/8 range given for administratively-scoped Class A unicast addresses (RFC 1918).

2.2 Mapping IP-Multicast Addresses to Ethernet MAC Addresses

One of the difficulties that Dr. Deering discovered while trying to deploy a practical IP-Multicast protocol suite on an Ethernet LAN was in mapping the range of IP multicast addresses to an equivalent set of Ethernet MAC multicast addresses. The 48-bit Ethernet MAC addressing scheme uses the least significant bit (LSB) of the first octet to specify unicast or multicast/broadcast - a 0 for unicast and a 1 for multicast/broadcast. This addressing is equivalent to saying that an Ethernet MAC address is multicast if the first byte is odd and, in the special case where all 48-bits are 1, that you have a MAC broadcast. Dr. Deering had to implement a many-to-one mapping of IP multicast addresses (groups) to MAC multicast addresses as follows:

• the upper 24-bits of the MAC address are always 0x01005E (the OUI - Organizationally Unique Identifier);
• the next bit of the MAC address is always zero;
• the remaining 23-bits of the MAC address are set equal to the last 23-bits of the IP multicast address;

Note that this process leaves a 32:1 IP-to-MAC mapping. Why? Well, an IP address is 32 bits (MSB="bit 0" and LSB="bit 31"). This amount minus the 4 required leading Class "D" bits leaves 28 bits. With only 23-bits being available in the MAC address, bits 4 through 8 of the IP multicast are not used in the MAC address. This result allows 2**5 or 32 for the number of IP multicasts that map to the same MAC address.

Why Dr. Deering did not simply "sign up" for a 16 contiguous block of upper-order 24-bit multicast prefixes (OUI) that would make up for the lack of address space in the lower 24 bits is an interesting historical question. The answer was based purely on finances - Dr. Deering's manager at Stanford could only afford one OUI to be reserved for his researcher's work, since the IEEE was charging $1,000 per OUI at the time. Thus, a deficit of $15,000 caused this strange dilemma, which would haunt multicast developers for the next decade!

2.3 Using IP-Multicast with non-Ethernet Media

While the canonical format of the FDDI (Fiber Distributed Data Interface) MAC multicast addresses make for reversed-octets (giving 0x80007Axxxxxx instead of Ethernet's 0x01005Exxxxx) on the wire, all other aspects of the mapping work as described in section 2.2 above.

Token Ring (TR) uses a similar format to FDDI and can, in theory, work with IP multicasting as well. However, many TR NICs (Network Interface Cards) cannot interrupt on a given multicast MAC address, which will cause unnecessary interrupts since the node must decode/analyze every packet as a possible multicast that might have interesting data. This fact is one reason that Ethernet is the LAN-of-choice when it comes to IP-Multicast.

3.0 IP-Multicast: The Protocols

This section gives a very brief overview of the operational characteristics of each of the five primary protocols of today's IP-Multicasting networks. Many other ancillary and experimental protocols are involved but will only be mentioned in the following sections as they relate to "the big five". Of the five, the IGMP membership and the PIM-SM routing protocols have the greatest deployment at the beginning of the new century. Any new enterprise/Internet rollouts will be unlikely to use DVMRP or even PIM-DM. MOSPF and some enhanced versions of BGPv4 will be competing with PIM-SM for greatest deployment for some years ahead. (In recent conferences held by Cisco on multicast-based video conferencing, PIM-SM and its ever-evolving versions were highly touted.)

[Special Note: if a user node wishes to participate in the Internet's Mbone applications and transmissions, DVMRP is still the only multicast routing protocol available - at least for now]

3.1 IGMP - Internet Group Message Protocol

IGMP is a very simple leave/join protocol that allows end-user nodes and their multicast-enabled routers to exchange messages that describe the wishes of the hosts to participate in multicast groups. Version one of this protocol (part of the RFC-1112 1991 document) was based on two primary messages - a Membership (Group) Query sent by the router and a Membership (Group) Report sent by the end-user nodes. Version two of the specification, which expands on the two primary messages, can be found in the RFC-2236 1997 document. A third version (RFC not yet assigned) has not yet been ratified by the IETF and adds a few additional features. Even with the additions of version two and version three, the resultant protocol is remarkably similar to Dr. Deering's original specification.

In IGMPv1, only two messages (Membership Query and Report) are defined. A "designated" (sometimes called the "dominant") multicast-enabled router, referred to as the "DR", sends out periodic queries to all nodes on a given attached network using the 224.0.0.1 multicast address. Each node that is configured to receive these multicast queries returns a separate report to all multicast groups (addresses) in which it wishes to participate after a random timer countdown. If another node on the segment hears a report for a specific group in which it participates before sending its own report, this other node cancels its own transmission of the report. The reason is simple - the DR only needs to know that one end-user would like to hear from that group. A common misconception is that a list of participant IP addresses exists in the DR. DVMRP, for example, only has a list of sources and groups (a (S,G) table in multicast terminology) for a given router interface (e.g. (194.15.1.1, 239.1.1.1), where 194.15.1.1 is the IP address of the node that is sourcing the multicast and 239.1.1.1 is the multicast address/group chosen by the source node). The DR places the newly discovered (S,G) entries in its table and continues. This procedure is how a "join" is accomplished. Note that these message packets cannot move beyond the locally attached routers due to the fact that the TTL (Time To Live) field is set to 1.

If it does not hear a report back for a multicast group that earlier had at least one participant, the DR then clears that (S,G) from its table on that interface. This procedure is how a "leave" is accomplished. No explicit "leave" message exists in version 1 of IGMP. This procedure can cause problems, of course, if a user "surfs" through a series of multicast group transmissions and settles on just one. The DR believes (for a few minutes) that all those groups must be presented on this LAN segment. If this occurrence happens more than a few times a minute, an incredible amount of traffic can be reproduced on the segment even though no end-user really wants to receive it!

Version two of IGMP provides the ability for an unsolicited "leave" message to be sent to the DR. So, the impact described above is essentially squelched. In addition, version one does not specify a defined way to elect a DR out of a possible number of qualifying multicast-enable routers; whereas version two uses the lowest IP address of the attached router interfaces to establish the DR. Version two also allows the DR to query only a specific multicast group instead of querying for all multicast participants in any group. Finally, version two provides a "maximum response time" field in the Query packet that is used to fine-tune the amount of random countdown performed by the end-user nodes in responding to Membership Query packets.

Version three, when deployed over the next year of so, will add a security feature ability to IGMP, allowing each end-user host to select which multicast source address it wishes to listen to for a given multicast group. This feature may seem confusing at first since one would think that only one IP source would exist for a given multicast group. However, if a malicious user sources a group on his/her machine simultaneously to a valid multicast group currently in use, that user could potentially create a DOS (Denial of Service) attack that could severely disrupt audio/video or data-cast applications (e.g. send erroneous stock market ticker information, take over the audio portion of an important announcement, etc.).

3.2 DVMRP - Distance Vector Multicasting Routing Protocol

While the IGMP protocol is clearly defined as the method by which end-user nodes are added to the DR's (S,G) table, the DRs must still find a path from the multicast sourcing node to these end-users. This area is where multicast routing protocols are important, and DVMRP, described in RFC 1075, is the preeminent multicast routing protocol.

DVMRP, loosely based on the analogous IP unicast inter-router protocol RIPv2 (Routing Information Protocol - version 2), uses "distance vector" techniques based on Bellman-Ford algorithms. Both DVMRP and RIPv2 protocols use the concept of next-best-hop and do not have a total picture of the router mesh inside each DR (only who its immediate router neighbors are). DVMRP has the same router mesh "width" as RIP, i.e. 32 hops maximum. This restriction obviously limits the deployment to small and medium sized enterprises. The Internet cannot ubiquitously use DVMRP for this reason. In addition, DVMRP uses only one metric - the number of hops, for best route determination.

Interestingly, DVMRP is similar to RIP version 2, not version 1. This similarity to the later version of RIP is because DVMRP provides support for classless IP addresses, i.e. those that use the subnet mask for all subnet calculations. This approach of sending the subnet masks along with network addresses is characteristic of RIP version 2 and can also be referred to as VLSM - Variable Length Subnet Masking - in some texts.

DVMRP uses a separate Multicast Routing Table (MRT) to store information regarding the routes back to a given multicast source. Note the use of "multicast source" rather than the destination, as would be the case in RIP. This behavior is due to the fact that IP-Multicast looks at the spanning tree as traversed backwards - from the end-users back to the source rather than source to end-users. Since a multicast group (address) addresses a group of nodes instead of a specific node, this approach is the only way that routing makes sense in the multicast world.

The multicast spanning tree is built through a series of floods, prunes, and grafts. A flood refers to the DVMRP insistence that all DVMRP multicast routers must transmit multicast packets to all outgoing interfaces. Of course, this insistence seems to be a bit of overkill since many of the DVMRP routers may have no end-user nodes that are interested in the multicast traffic (i.e. their (S,G) tables, discerned by IGMP, are empty). In this case, these routers send a "prune" message back "up the tree" (also called "upstream"), stating that they are not interested in the multicast traffic. This pruning effect is only transient, however. For after a couple of minutes, the pruned branches re-grow, giving a chance for the effected routers to either join back with the main tree (if users have requested multicast group traffic via IGMP) or just send another prune message.

Further, if it feels ready to re-enter the tree immediately, a multicast router can send a "graft" message upstream instead of waiting for this de-pruning process. Interestingly, current implementations of DVMRP maintain information on pruned branches but do not actually delete them from the internal database. With the high volume of prune/grow-back/graft operations in a typical multicast network, just toggling a state field in the entry saves router CPU cycles in exchange for the modest amount of additional memory required to track all branches.

The resultant spanning tree is referred to in a variety of ways in IP-Multicast documents, including as a "dense mode source distribution tree", a "shortest path tree" (SPT), or a "truncated broadcast tree". (The term "dense mode" refers to the fact the multicast traffic will penetrate much of the overall network and that this traffic flow is deliberate and desirable). Of the three terms, SPT is the most common designation. An SPT is in direct contrast to those protocols that use a "shared tree" that is based not on the multicast source's router, but rather on a designated "rendezvous point" router. PIM-SM uses this shared tree approach and will be discussed in greater detail in a later section.

To learn about its adjacent neighbors, a DVMRP router sends periodic "Hello" messages on all of its interfaces using the "All DVMRP router" multicast address - "224.0.0.4". Upon receiving a Hello message, the DVMRP router places its interface address in the "Neighbor List" field of the message. When it receives a "Hello" message and identifies its own interface address in this field, the router knows that a two-way adjacency has been successfully formed between itself and the neighbor that sent the message.

The DVMRP MRT typically has the following entries: source network, source network subnet mask, administrative distance, no-of-hops metric, uptime, expiration timer, next hop address and interface going towards the source, and information about the neighbor that sent the DVMRP route message. The entire multicast routing table is periodically transmitted to all DVMRP neighbors, helping to keep all DVMRP routers in synchronization with each other. As with RIPv2, convergence of a changed topology (down/up link-state change) within the router mesh can take time. Entries in the table are periodically deleted using the expiration timer and are re-learned from subsequent neighbor route updates.

As with IGMP, the DVMRP protocol takes advantage of the TTL (Time To Live) field of the IP header to specify the extent of the packets in terms of router mesh width. Typical TTL values are:

TTL Value 0 1 32 64 128 255

Scope of DVMRP Packet Restricted to the same host Restricted to the same subnetwork Restricted to the same site Restricted to the same region Restricted to the same continent Unrestricted in scope

In addition to the previously mentioned MRT, the DVMRP-enabled router also creates a Multicast Forwarding Table (MFT). This forwarding table is simply a vector of (S,G) values with their associated incoming interface, outgoing interface(s) and "prune status". The MFT is used by the line-card to quickly make the correct outgoing interface decision based on the multicast source and group. Note that the prune status is provided so that traffic is not forwarded out to branches that have requested that they not be part of the active tree.

During normal operation of the multicast router, a check is made using the MFT to ensure that a multicast packet seen on a given interface corresponds to the route back to the source that owns the group. This check kills any packet that was received on some other port due to a non-convergent router mesh, typically because of a recent topology change. This check is referred to as a Reverse Path Forwarding (RPF) check.

If the packet passes the RPF check, it is forwarded out to all interfaces downstream. Note that "pruning" messages may have severely depopulated this interface list. This reduction is crucial for a dense mode protocol such as DVMRP since without pruning, multicasting might look more like IP broadcasting, at least up to the final-hop multicast routers!

As previously stated, DVMRP does not scale well and is very "chatty". In addition, DVMRP requires a great deal of router memory to maintain the separate multicast routing and forwarding tables. This protocol is, however, the easiest multicast routing protocol to understand and is viable for small-to-medium networks, especially if only LANs are involved and most end-users need/want to receive much of the transmitted multicast traffic.

3.3 PIM - Protocol Independent Multicasting

A number of years ago, the IDRM (Inter-Domain Multicast Routing) working group of the IETF began development of a multicast routing protocol that would operate regardless of the unicast routing protocol being used. Indeed, one of the goals of PIM is to use existing routing/topology tables and not create multicast specific ones. This approach is in contrast to DVMRP, discussed in the previous section, and its use of a Multicast Routing Table.

The primary goal of the PIM protocol is to provide superior sparse mode operation, however, PIM does have a dense mode model as well. The committee's decision to provide both modes allowed PIM to be used as a total solution to IP-Multicast and not depend on DVMRP or MOSPF as the dense mode protocol. These two modes, sparse and dense, operate rather differently and are discussed in more detail in the next two subsections.

3.3.1 PIM-DM - Dense Mode

While both DVMRP and PIM-DM are both dense mode multicast protocols with a SPT (Shortest Path Tree) model, PIM-DM uses a very different approach to the in-line egress processing of the multicast group packets. While DVMRP uses a MRT and MFT to calculate which ports to transmit to for a given (S,G) combination, PIM-DM blindly transmits the multicast packet to all interfaces, as long as that interface has not been pruned. PIM-DM accepts this additional packet duplication in order to operate independently of the unicast routing tables and their resultant topology. In addition, no parent/child databases need be created using this very simplistic model. Needless to say, PIM-DM should only be used when a large percentage of the end-users require multicast traffic and very little of the users require WAN links to reach the sources (i.e. bandwidth is plentiful).

3.3.2 PIM-SM - Sparse Mode

When one refers to the PIM protocol for IP-Multicasting, one is usually referring to the sparse mode of operation. PIM-SM is one of the few IP-Multicast approaches that provides a more efficient mechanism for multicasting when only a small percentage of end-users need to listen to the group traffic and/or when WAN links are used to access the multicast sources. PIM-SM uses RPT (Rendezvous Point Trees) as its primary spanning tree, making use of single point of "rendezvous" (the "RP") between sources and recipients. The RP is a network manager-specified, multicast-enabled router that is usually quite close to the multicast sources. Because end-users are downstream from the RP based distribution tree, the designation for a particular multicast group is (*,G), i.e. all multicast groups are sourced from the same point - the RP. Thus, the existence of multiple RPs is possible, each being responsible for some subset of all required multicast groups.

Some difficulties must be overcome for this shared tree approach. Since the RPT is unidirectional and can only flow from the RP to the end-user, how do the RP and other downstream routers discover the additions of new group users? (Remember, the end-users "sign up" for group access using the standard IGMP protocol discussed previously). Also, how does a given last-hop router initially know the IP address of the RP?

The method of discovery of new group users involves a standard SPT (Shortest Path Tree) from the last-hop router back to the RP. Standard unicast routing tables are used and a "PIM Shared Tree Join" is performed. The only necessity is for each router along the way, all the way up to the RP itself, to add the (*,G) entry for the required multicast group. In this way, the end-user has "joined" the RPT for subsequent multicast packets for this group. When a given last-hop router discovers (via IGMP) that there are no more end-users for a given multicast group, a "Shared Tree Prune" message can be sent up the SPT towards the RP so that timeouts are not needed to prune the proper branches.

Several possible methods exist for a given last-hop router to initially know the IP address of the RP. The most straightforward approach would be to statically configure the RP's IP address into each router that might participate in multicasting. While simple, this method certainly does not scale well! Cisco proposed a more automatic method, based on a protocol that they call "Auto-RP" which uses a "Cisco-RP-Discovery" multicast packet with well-known address "224.0.1.40" and a "Cisco-RP-Announce" which uses "224.0.1.39". Version two of PIM-SM offers another option, outlining a bootstrap process to discover the RP's address. Whatever method is used, the multicast routers must know the RP's IP address since standard unicast routing is used to implement a group join operation. (Remember that PIM does not maintain its own routing table and depends on the unicast routing tables already existing in the router.)

One feature of PIM-SM that is not available in other sparse mode protocols (such as bi-directional Core-Based Trees, CBTs) is the ability for a given last-hop router to ask for a direct SPT back to a given multicast source without requiring the source to link to the shared RP tree. This feature allows a given sourcing node the option of providing service directly to a set of end-users without routing its multicast payloads through the RP.

How does a given multicast source provide its packet traffic to the RP? PIM-SM uses another SPT from the RP back to the source to solve this concern. The RP knows that the source exists due to a unicast packet that is sent from the source directly to the RP's IP address using a special PIM message called a "Source Registration". Once the unicast packet is received, the RP can now make the reverse connection back to the sourcing node.

3.4 MOSPF - Multicast Open Shortest Path First

Just as DVMRP was based on the RIPv2 distance-vector-based unicast routing protocol, the MOSPF (RFC 1584) multicast protocol is an extension of OSPF, a "link-state" unicast routing protocol. While distance-vector algorithms use simplistic best-route metrics (RIP uses just one - the number of hops) and know only about the directly attached neighbors, a "link-state" routing protocol uses a rich variety of metrics as well as a full topological model of the network within each OSPF-enabled router. OSPF routers require that a great deal more memory be at their disposal to create these topological maps. After a topology change, the map is re-calculated using a "Dijkstra" algorithm to provide the shortest path between any two given networks/subnetworks (hence the protocol's name).

OSPF (the latest version is v2 and is described in RFC 2328) uses a hierarchical representation of the router mesh and divides all routers and their associated network segments into "areas". Area "0" is special and typically referred to as the "backbone area". All other areas must tie at least one of their area routers into Area 0 (called Area Border Routers or ABRs). Thus, traffic that must route from one area to another must traverse Area 0.

OSPF, and thus MOSPF, uses a flooding technique to advise other OSPF routers of topology information. Unlike the RIP approach of sending the entire routing table in each flood, OSPF sends only the "delta" information, i.e. what has changed in the topology. This approach provides a significant bandwidth savings in those router-rich networks. The inter-router OSPF messages are called LSAs (Link-State Advertisements). In fact, the primary difference between OSPF and MOSPF was the addition of a new LSA that provides multicast group-specific information to the router mesh. In this way, MOSPF routers learn which ports of the router have interested listeners for a given multicast group. A Designated Router (DR) must be established and SPT (Shortest Path Trees) are used, just as with DVMRP, but the tree routing is performed with the Dijkstra algorithm, not with DVMRP's least-hops approach.

In order to reduce the computational effort required for the MOSPF router to figure all SPTs for all possible (S,G) combinations, the algorithm is only run after a multicast packet for a given group is seen in real-time. Then, and only then, does the MOSPF router place the resultant forwarding information into its own Multicast Forwarding Table (MFT). Even with this streamlining technique, a MOSPF router mesh could easily become overwhelmed computationally if a large number of sources and their users came joined at the same (or nearly the same) time. As a result, MOSPF is currently not a very viable IP-Multicast solution (although some MOSPF deployments do exist in corporate networks).

3.5 mroutes - Static Multicast Routing

Most vendors implement, in addition to some combination of the above IP-Multicast routing protocols, a straightforward way of adding routing and forwarding information statically, i.e. by using the router's management console/software to directly enter which incoming interfaces point back to multicast sources and which outgoing interfaces are to be transmitted to for a given multicast group. Although somewhat "brute force" and requiring a great deal of personnel time to maintain, this method is warranted for certain special scenarios - most of them dealing with security, e.g. firewalls to the Internet, secure areas of the enterprise network, anti-hack and anti-spoofing policies, and others. Cisco refers to its manual (static) multicast routing technique as mroutes.

Conclusion

While IP-multicasting has evolved since Dr. Deering first conceived and implemented it, the technology remains grounded in his initial work. This article has covered many of the basics of IP-multicasting and its affiliated protocols. The next articles in this series will explore the use of switches and will reveal additional technical details about the operation and use of IP-multicasting.