Internet Multicast Routing

Algorithms that are already used to route non-multicast messages through an internet can be modified and extended to allow actual protocol support for multicasting. A lot of work has been done in this area and I intend to show this with reference to Spanning Tree routing. This information is taken from Stephen Deering's doctoral dissertation.

Some terms should be explained:

Spanning Tree Routing

ST routing is being adopted as the standard routing protocol for all types of IEEE 802 LAN's at the datalink layer.

ST already supports multicast routing across multiple sub-networks, using broadcast delivery (i.e. any packet marked as multicast is broadcast to all sub-networks, each of which have to figure out which nodes are group members, if any).

An arbitrary topology of routers and sub-networks is is converted into a loop-free topology by having some routers "ignore" their connection to some of their attached sub-networks. Loops in the internetwork are bad for performance of multicast/broadcast because packets may be forwarded to the same sub-network more than once.

A distributed spanning tree algorithm is computed by all the routers in the internetwork. One router is "elected" to be the root of the spanning tree. For each sub-network, one of the routers (the one closest to the root) is chosen as the designated router.

Routers can now classify all the sub-networks they are attached to as:

Routers listen to all the packets that pass by on their parent and child sub-nets. They store tuples of:

(host, branch, time-left)

in a routing cache. branch indicates which network attached to the router is the next hop on the path to host, which is the destination. The time-left value indicates how long since the last packet for host was received. Stale values can be flushed from the cache after a certain period of quiet time. This helps to ensure that the routes in the cache do not become inaccurate, if a node crashes for example. The crashed node will originate no more messages and the cache will eventually discard the old route and have to locate a new route.

The cache is kept up-to-date by watching the passing packets. Each message on a child or parent sub-net carries its source address. This information together with the address of the sub-net the message arrived from forms one of the tuples in the routing cache.

If a router receives a packet and it does not have an entry in its cache corresponding to the destination address it forwards the message on all braches except the arrival branch. This should ensure that it reaches the destination.

Spanning Tree Truncated Broadcast

With regard to TB, packets are delivered by means of spanning tree rooted at the sender. Hops to leaf networks which have no members of the destination group are omitted.

Spanning Tree routing already provides for multicast by means of broadcast delivery. The need here is for some way of identifying leaf sub-nets so that they can be pruned from the spanning tree. This is fairly easy to do. The sub-net itself indicates to its designated router that some (one or more) of its nodes are members of a group. If this information is not forthcoming from a particular sub-net then it can be pruned. Some sort of Group Membership Protocol is needed. This is fairly easy to implement.

Each incoming multicast packet is forwarded to all sub-nets on which a router with a child sub-net or a the destination group is present, excluding the sub-net the packet arrived on and ignored sub-nets for that router.

Truncated Broadcast

TB eliminates some unnecessary packet hops. These are hops onto leaf sub-nets which have no group member present to receive the multicast. In this way some bandwidth is freed up and the protocol becomes more efficient. Note: there are still some unnecessary packet hops under Truncated Broadcast routing. These hops occur on sub-nets in the interior of the internetwork.

Multicast delivery (follows) can be used to eliminate these interior hops.

Multicast Routing

To perform true MR, routers need more information. They need to know which branches of the tree lead to sub-nets with members of the destination group. Some explicit mechanism is needed for groups to register themselves with routers throughout the internetwork. The group membership protocol which I mentioned above provides that mechanism. Groups never source messages and so their addresses are not picked up by routers in the usual way.

Sub-nets with group members present can identify themselves to other routers. If one member broadcasts some sort of "group-members-here" report the routers will see this information and store it. This report will be seen throughout the network. Multicast can be achieved by having each router forward multicast packets only on branches that lead to the destination group. This information on branches would be got from the router's group presence records (part of the Group Membership Protocol).

If this is adopted there is a possible scaling problem. As the internet grows larger more and more bandwidth might be taken up in broadcasting these "group-members-here" reports. This can be prevented easily, however. Routers can forward memberships reports in batches instead of as received.

Hierarchical Routing

As the internetwork grows larger the whole routing algorithm faces scaling problems. The algorithm must be able to scale itslef commensurately to the growth of the internetwork. A greater number of sub-nets and larger, more dispersed multicast groups will have to be dealt with.

This can be done. A group of sub-nets can be thought of as a region. Routers can be used to route between regions rather than sub-nets. As the internetwork grows a hierarchy of regions can be built up. A low-level region will represent a group of sub-nets. A high-level region will represent a group of regions.

The Group Membership Protocol will become slightly more complicated, as it now has to deal with regions having group members within them, not just sub-nets. Using this method of scaling avoids many of the problems and much extra administrative detail is mitigated.