Standards & Protocols
Multicast OSPF
By Mike Rodbell
The OSPF protocols are based on link-state mechanisms that calculate routes through the network
through compilation and traversal of the state of the various interconnections in the network. Some of the additional features provided by OSPF include hierarchical routing and load balancing.
Last month, we reviewed a multicast routing technology based on the relatively simple distance vector algorithms. This month, we’ll take a look at a different approach to “dense mode” multicast routing. Remember that by “dense mode,” I am referring to a type of multicast routing that is
used when the information source and recipients are relatively close (in terms of routing hops) to one another.
While the distance-vector multicast routing protocol (DVMRP) is based on the routing information protocol (RIP), as its name implies, the multicast extensions to open shortest path first (MOSPF) is based on the open shortest path first (OSPF) routing protocols and techniques. The OSPF protocols are based on link-state mechanisms that calculate routes through the network through compilation and
traversal of the state of the various interconnections in the network. Some of the additional features provided by OSPF include hierarchical routing and load balancing. The MOSPF set of extensions are designed to provide an incremental improvement to the basic OSPF capabilities, taking advantage of the underpinnings provided by the basic OSPF services.
Without going into the specifics of the OSPF routing protocols, this month I’ll take a look at what can be accomplished through the use of the
link-based nature of MOSPF. Where DVMRP required some rather significant reliance on observing the actual flow of the packets for the truncated reverse-path multicast (TRPM) algorithms, MOSPF implementations needn’t spend much additional energy on directly monitoring the flow of packets through the network. Pruning activities are implicit with the link state tables providing the road map for the multicast packets through the network.
MOSPF has both advantages and disadvantages. With every router containing
a complete picture of the network area topology, well-informed and optimized routing decisions can be made. Multicast packets need only traverse the network towards well-known group members; no additional pruning activities should be required as in DVMRP (see last month’s Standards and Protocols column “First-Generation Multicast Routing” in
Communication Systems Design
). However, this strong routing foundation presents some shortcomings. Considerably more information must be exchanged
to maintain the routing databases in the participating routers within the system. If the network architecture remains relatively static, this information needn’t be exchanged all that frequently. However, as routers (and corresponding routes) come and go, a fair amount of information must be exchanged, and the route calculations must be performed on each topology change.
Hierarchical routing concepts of operation
One of the more fundamental aspects of OSPF-based routing is that of
routing hierarchies. By dividing a network into a collection of autonomous systems, each containing a set of areas, the OSPF view of a network is subdivided in a manner that helps to limit the degree to which large routing tables must be maintained. In the spirit of this approach, the MOSPF routers maintain a database of the local groups that details all of the locally attached groups. As can be seen in
Figure 1
, each autonomous system in OSPF can contain several areas that
are interconnected through a backbone architecture.
Rather than having all nodes in an area take responsibility for routing (as in the case of distance vector implementations), MOSPF employs a designated router (DR) and a backup designated router (BDR) to take responsibility for collecting and distributing the list of multicast groups within the DR’s (or BDR’s) subnetwork. The collection of the multicast group memberships is handled through the Internet group management protocol (IGMP), which we
discussed a few months back. To collect the group membership information, the DR issues and collects responses to IGMP host membership queries. Once the DR has collected the group membership information, it then is responsible for reporting the membership information to all other routers in its area. As this information is accumulated for each area, it is communicated to routers in the other areas participating in the autonomous system through announcements between the routers providing access to the
autonomous system’s backbone.
Optimizing information delivery
The MOSPF routers employ a technique referred to as the “Dijkstra algorithm” to compute a shortest-path tree. This tree provides the information required to determine all multicast routing decisions within the routing area. As each router receives a packet requiring a new multicast route, it traverses its link state database to identify the direction(s) in which a multicast packet must be routed to reach all interested
destinations. After the initial packet is received for the intended group (over the same interface), all subsequent packets can then be routed to the same destinations. As the packets traverse the network, all routers must employ the same algorithm, traversing their network topology database to identify where they must forward the multicast packets.
Forwarding database
Each routing node in the network maintains a database of all links in the network. In addition to the unicast information held on
behalf of the standard OSPF routing algorithm, MOSPF provides additional information identifying the location of all multicast group memberships in the router’s area. If we take as an example the routing topology shown in
Figure 2
, there are a set of routes that are used for multicast forwarding and a separate set of routes that do not warrant transmission of the multicast routes. In this example, I’ve shown a single routing source (MSA) and several multicast
destinations (MD
X
). If we assume that this represents only a single multicast session (source:group pairing), then the path taken by each multicast router can be easily determined by referring to its local routing database. As each multicast packet is received, the multicast route cache is referenced. If the source:group pair appears in the router’s cache, then the packet is forwarded on all acceptable multicast paths (as shown by the red lines between routers and destinations). If the
source:group pair does not appear in the cache, the Dijkstra algorithm is employed and the resulting routing information is added to the cache once the packet is forwarded.
Routing between areas
When a multicast group membership spans multiple areas, a different set of protocol mechanisms and routing algorithms are employed. In a multi-area network architecture as shown in
Figure 1
, there are a set of area border routers (ABR) that are responsible for the forwarding
of traffic between areas. All of the communication traffic between areas is processed by the ABRs with the routing information and corresponding traffic being exchanged over the backbone area. As in the case of intra-area routing, MOSPF extends the concept of the area routers through the definition of a new type of network element, the multicast area-border router (MABR).
The MABR provides services that summarize its local area’s multicast group participation and limits the flow of multicast
routing information in such a manner that routes are advertised into the backbone, but not flooded into the attached areas. As a result, all interarea multicast transmissions must flow through the backbone for routing into the areas that are advertising participation. In support of these algorithms a new type of router, the wildcard multicast receiver, is added to the mix of devices. This wildcard element is responsible for the routing of multicast traffic to and from the backbone.
One of the shortcomings of
the multiple area routing algorithms is that it becomes nearly impossible to assemble complete shortest path routing trees. Given that the network topologies are fragmented into areas to limit the size of the routing databases (and corresponding routing traffic), the MABRs interact to identify the shortest paths over the backbone area. The corresponding local area routes are not introduced until such time that the traffic must be routed to local area members.
As a protocol in a newly emerging technical
area, MOSPF can be viewed as both a useful tool and a set of technical challenges. Through its legacy as an incremental improvement on an existing and well-understood routing protocol (OSPF), MOSPF provides several advantages in (relative) ease of implementation and fielding. However, as I’ve mentioned in this article, there are some specific technical shortcomings in the deployment of MOSPF. Routing table sizes can become quite large as network topologies grow. Operation over a widely-distributed
sparse-mode network can be cumbersome, exacerbating the routing database size issues. Finally, all routing decisions must be based on traversal of the link-state trees. If interoperability with other routing mechanisms (such as DVMRP) is required, significant work must be performed to ensure that the systems will work. In recognition of some of these shortcomings, a good bit of research has been performed in the development of protocol independent multicast (PIM) and sparse-mode multicast protocols that can operate
over widely distributed networks without requiring specific mechanisms in the underlying routing protocols.
Mike Rodbell is director of embedded software development for CIENA Communications Inc. He has developed voice and data communication systems for a wide range of commercial and military systems. He holds a BSCS from Trinity College of Hartford, CT, and an MSEE from Loyola College of Baltimore, MD. He can be reached at mrodbell@ciena.com or www.ciena.com.
Puzzled by a network processing design issue?
