11.25.06
Review of “Revisiting IP Multicast”
Despite the fact that IP Multicast has been widely studied in the last fifteen years, none of the proposed infrastructures to implement this service model has been widely deployed and has been proven convincing. In fact, it is still under question whether the benefits implied by the introduction of IP Multicast would compensate and overreach the complexity of its deployment and management in the network level. However, the authors notice how several applications could largely benefit from an underlying multicast communication service, and how the spreading of such applications is dramatically increasing. It is the case, for instance, of multiplayer games, Internet TV technology, video conferencing, file sharing, software updates and more. Thus, the paper revisits IP multicast and proposed a novel approach, called Free Riding Multicast (FRM) for its deployment.
The proposal focuses on inter-domain routing, even if it can be extended to intra-domain routing as well (and the authors mention how this could be done). The design aims at leveraging unicast routes and augmenting BGP to include per-prefix group membership information. This way, FRM deployment and configuration, as well as the required protocol mechanisms, are kept simple.
The ideas at the core of FRM are two: i) decoupling of group membership advertising from multicast forwarding, and ii) multicast source routing. The key challenges are: i) space and bandwidth overhead due to maintaining and disseminating group membership information, and ii) efficiency of the packet forwarding operation on each router. We briefly summarize how these issues are addressed in the design.
The aforementioned design principles are implemented by distinguishing and treating separately the border router in the access domain for the source (Rs) and the other transit border routers (Rt). Specifically, group membership advertising, routing and state based forwarding is performed on Rs, whereas all the Rt will be devoted only to forwarding according to a different scheme.
In quality of Rs, each border router discovers through an intra-domain multicast protocol the set of active groups in its local domain. This state information is stored locally, and Bloom Filters are used in order to limit the memory requirement (even if, as the authors point out, this state information does not need to be stored directly on the line cards). In particular, for every prefix in the routing table, a Bloom Filter GRP_BF is introduced which indicates whether a group should be routed along the corresponding path. The use of this hashing data structure originates false positives: to limit their effect, filter rules propagated from the upstream domains are used. The sizing of the Bloom Filters takes into consideration the number of filter rules allowed.
As mentioned, each Rs computes locally the multicast routing source tree by scanning the BGP table. Packet forwarding at Rs can happen in two ways: using GRP_BF and using caching. In the former case, all the GRP_BF are queried and, in case of match, the packet is routed according to the corresponding prefix. The information about the routing sub-tree along each route found must be added to the packet (in the so-called “shim header”). This operation requires O(pxd) time, where p is the number of matches and d the average AS path length. To speedup the forwarding operation, per-group caching of the (per-computed) routing information can be performed. Cache accesses translate into exact match lookups, and a LRU cache replacement policy is adopted to manage the cache content. Moreover, the experimental evaluation shows that caches can be accommodated in RAM on line cards.
The information in the “shim” header is used by the transit routers to forward the packets. Notice that such routing information must be replicated in every packet addressed to a group, and that its size is theoretically dependent upon the one of the dissemination tree. Bloom Filters are again exploited in order to avoid explosion in the header size. Specifically, each routing tree is encoded in a TREE_BF. Such data structure is then queried with a (src-Rt,dst-Rt) pair to determine whether the packet should be routed along the link from src-Rt to dst-Rt. A bound on the size of the TREE_BF is set: big trees must be splitted into sub-trees and transmitted through different packets. Clearly, the only state information needed on the transit routers to route packets is the list of the neighboring ISPs. On the other hand, the addition of a per-packet skim header and of possible packet replications leads to an overhead in bandwidth consumptions. Eliminating the leaves of the dissemination tree from the shim header and aggregating links when a high percentage of outgoing links from a router belongs to the dissemination tree are exploited to further reduce the shim header overhead. Finally, hashing of the neighbor edges information on each transit router allows efficiently querying the TREE_BF in hardware (e.g.: through the use of TCAMs).
The authors present a performance evaluation where they analyze the feasibility of the proposal, the amount of state needed and the bandwidth overhead with and without optimizations. The experiments presented, as well as the description of a prototypical implementation, in my opinion make sense and strengthen the discussion.
Finally, the paper discusses how their model can allow the ISPs to better control the use of multicast both on a user basis and on a group basis. They consider the possibility to do access control and to charge for the service (dependent upon the group size). Moreover, a better control from the ISPs should allow limiting the exposure to malicious users.
In general, I have a good opinion about this paper. I appreciated the fact of considering a different way to think about IP Multicast, and I also liked the way every idea was thought and developed in depth.
A different approach I had thought about consisted in propagating and storing the routing information in the transit routers the same way it is stored in the source router (with per-group Bloom Filters). Multicast packets would be routed basing on the group information, and the shim header would not be used any more. I imagine that this approach could be problematic if the system has more sources for the same group, and their dissemination trees clearly intersect in a router Rint. Nonetheless, I believe that routing would be performed properly if each router was prevented from transmitting a packet towards the incoming direction.
FRM has several advantages over the scheme I just described. First, it reduces the amount of state on transit routers. It has to be noticed that, to handle updates, GRP_BF are counting Bloom Filters (in fact, each bit is represented through 3 bytes – which seems to be quite a lot, however). Second, a small cache and a limited-size GRP_BF data structure are justified on a source router by the fact that they will handle only a restricted number of groups. But, if the same were used on transit routers, they would probably need to handle more information and be bigger. Therefore, the entire scheme would not be effective. Third, updates in the dissemination trees (due to group changes, etc.) must be handled only in the source router (and not be propagated to transit routers).
In this context, having a limited overhead on the packet headers seems reasonable (also considering that TREE_BF are simple Bloom Filters). I think that the most obvious criticism is that a malicious user could create a lot of traffic by setting all the bits in the shim header to 1. The authors argue that a user doing that would attack its own ISP and be exposed to the control of the ISP itself. However, there may be cases where packets headers get modified within their path from a transit router to another one, and it is not clear how such attacks could be handled.
I have one small additional issue concerning the use of the cache on source routers. In many scenarios, the groups are dynamic. If dissemination trees are cached and the cache is not refreshed with a sufficient frequency, some recipients may fail to receive packets they are interested in. Depending on the application, it may be better to periodically recompute the dissemination trees which are cached.
To conclude, I think that the paper proposes a novel idea and nice technical tricks to handle bandwidth and memory requirement issues. The aspect that may deserve more discussion is, in my opinion, security (which, by the way, affects any multicast architecture).