Routing and Multicasting Services

ROUTING AND MULTICASTING SERVICES

The Routing and Multicasting Services for NICE and the NII project (“NICE” for short) was funded by DARPA / ITO at the University of California, Santa Cruz (UCSC).

At UCSC, this project was part of the research carried out within the Computer Communication Research Group (CCRG) of the Baskin School of Engineering.

The principal investigators of this project were J.J. Garcia-Luna-Aceves and Anujan Varma.

Objective

The Internet is experiencing the widespread adoption of applications that support real-time reliable or unreliable distribution of multimedia information to multiple destinations (e.g., nv, vat, NeVot, wb and shdr). In addition, with the continuing decrease in hardware costs, very simple or special-purpose devices will soon have computing and communications capabilities of their own and enjoy Internetwork addressability traditionally assigned to mainframes, workstations, and more recently personal computers. As a result, very simple devices will become reachedable through the Internet; furthermore, traditional computing, storage, and media-distribution resources will be implementable by aggregating such simpler devices (e.g., a traditional Internet host becomes a network of devices). We refer to this next architectural step in the evolution of the Internet as the networked imbedded-computing environment (NICE). NICE implies the interconnection to the national information infrastructure of vast numbers of internetwork-addressable devices and traditional networked resources.

The emergence of NICE and new Internet real-time multimedia applications presents many new challenges on multicasting and routing. UCSC is carrying out a three-year research project focusing on reliable multicasting, multicast routing, scalable routing, and congestion control.

Approach

Our approach consisted of advancing the state of the art in the following areas:

  • End-to-End Reliable Multicast: Protocols that support scalable and reliable many-to-many communication on an end-to-end basis and eliminate the limitations of existing sender-initiated and receiver-initiated multicast protocols. The proposed protocols operate by the sources delegating retransmission responsibilities to the receivers, and by organizing the receivers of a session in a structure that reduces the number of acknowledgments flowing back to the sources.
  • Many-Cast Routing Architecture (MARA): We propose a novel scalable routing architecture and algorithms to support unicast, multicast, and `any-cast’ routing. This architecture is based on the notion of GDAGs, which generalizes the notion of multicast trees used in all previous approaches to multicasting and can support security requirements in a scalable manner. GDAGs can be viewed as multicast trees extended by added chords, so that a single GDAG services all the sources of a multicast group and reduces the dealy/length/cost of the paths from sources to receivers with respect to what a single multicast tree per group can provide.
  • Reliable Multicast within The Network: Protocols that support reliable multicast within the network for such network-control purposes as key distribution or reliable updates among routers or switches. These protocols either establish a group-oriented directed acyclic graph (GDAG) or use diffusing computations to carry out reliable multicast `on the fly.’ [This may be necessary, for example in distributed simulation networks with such mobile nodes as aircraft.]
  • Integrated Routing: Routing algorithms in MARA extend the techniques developed for link-vector algorithms and other types of algorithms to manage routing objects corresponding to links, nodes, distances to nodes, flows between nodes, or ATM virtual-path and virtual-channel layouts.

Recent Accomplishments

There are several mechanisms defined to protect the communication across links between neighboring nodes. However, today’s Internet routing and multicasting protocols provide few mechanisms, if any, to protect the exchange of control information. This project has developed the only known method to secure both classes of information in distance-vector routing protocols in constant space, which means that the overhead of the security mechanism is only linear with respect to the number of destinations. This method was applied to BGP and intra-domain routing protocols.

A new hierarchical routing algorithm was developed, which is called the Hierarchical Information Path-based Routing (HIPR) algorithm. HIPR is based on the incremental exchange of hierarchical routing trees, and can be viewed as the first distributed version of Dijkstra’s SPF algorithm running over a hierarchical graph. It has been shown that HIPR is far more efficient than OSPF in terms of time to converge, control messages exchanged, and computational overhead.

Prior specifications of the Core Based Tree (CBT) protocol have been shown to produce undetected loops and fail to construct multicast routing trees. To address the limitations of CBT, the Ordered Core based Tree (OCBT) protocol has been proposed. The Multicast Internet Protocol (MIP) was also developed, which is free of loops at every instant and incurs far less overhead than PIM. MIP’s design is based on the use of diffusing computations to distribute state information among routers regarding group membership along an acyclic graph.

End-to-end reliable multicast protocols that organize the set of receivers into a tree have been shown to be far more scalable and support higher maximum throughput than any other type of reliable multicast protocol proposed to date, such as sender initiated, receiver initiated, or ring-based protocols.

The Lorax protocol has been developed, which is the first known protocol that constructs and maintains a single shared acknowledgment (ACK) tree for concurrent reliable multicasting. Lorax eliminates the need to maintain an ACK tree for each source of a reliable multicast group, and can be used in combination with any of several tree-based reliable multicast protocols proposed to date. Lorax provides solutions to several open questions concerning the implementation of shared ACK trees. Preserving reliability during restructuring of the ACK tree is easily guaranteed using aggregated acknowledgments that propagate from each leaf towards the source. Lorax constructs and maintains a shared ACK tree. Overhead traffic is contained during initial ACK-tree construction by growing the ACK tree from a known root. Impatient nodes are quieted down and allowed to join the ACK tree by means of expanded ring searches that are narrow in scope. Hierarchical labeling of each node makes implicit routing of acknowledgments simple and preserves loop-free routing of such acknowledgments over the ACK tree at all times.

Architectural improvements to IP-multicast have been developed to encourage communication and cooperation between IP and higher-layer protocols. The first, called LMAS, is a generalization of internetwork multicasting. LMAS provides an extended set of semantics so that sources can restrict the delivery of packets to a subset of information. LMAS can be implemented using CBT or PIM. The second architecture, called Streams, allows higher-layer protocols place packets into application-defined logical streams, so that hosts may prune the routing of packets based on meaningful contexts. The third architecture, called RMA, introduces new routing services designed to support reliable multicast protocols. The cooperation between RMA and reliable multicast protocols provides very scalable and efficient reliable communication among hosts, and allows SRM, Lorax, and other reliable protocols to cooperate across an internet by providing a common interface.

A new multicast routing architecture called Shared-Tree Hierarchical Inter-Domain Multicast (SHIM) has been developed, which allows the use of shared tree protocols such as PIM-SM or CBT as the inter-domain routing protocol in a hierarchy that can include any routing protocol at the lowest level. The architecture consists of two protocols: one that encapsulates an entire routing domain to allow it to appear as a {\it virtual router} on a higher-level shared tree; and a second protocol that provides mechanisms for rendezvous point or core distribution and recursively applies the first protocol to produce trees of domains that contain trees of domains. SHIM differs from existing hierarchical multicast protocols in many ways. It is the first architecture to allow any multicast protocol at the lowest level while using a shared tree for higher-level routing. It provides a simple, efficient mechanism for RP or core location dissemination. SHIM aligns easily with existing unicast domains and it does not require explicit assignment of levels except at the highest level. SHIM is suitable for any shared tree protocol, such as PIM-SM or CBT, that forms a tree by sending join messages to some central router. It can also provide additional robustness for the shared tree protocol through the ability to replace a single rendezvous point or core with several routers that operate together in a distributed fashion and can tolerate members failing.

The Scalable Routing Information Protocol (SCRIP) has been implemented based on the loop-free path finding algorithm developed earlier in this project. SCRIP was implemented in gated and imports and exports routes from RIP. SCRIP has been debugged and tested and is running in a network of five PC routers. SCRIP converges as fast or faster than OSPF after network changes and requires an order of magnitude less load on the routers.

Technology Transition

The limitations of CBT were notified to members of the IETF. A new version of CBT has been released by Ballardi, which corrects most of the limitations identified by our analysis.

Collaboration with Bell Laboratories took place to implement some of the mechanisms introduced in Lorax as part of the Reliable Multicast Transport Protocol.

Publications

The following is the list of published papers describing our research results in this project. A more complete list of CCRG publications, including PDF format, can be found here.

Routing:

  • J.J. Garcia-Luna-Aceves and S. Murthy, “Supporting End-to-End Quality of Service with a Connectionless Routing Architecture,” accepted for publication in Computer Communications Journal, 1997.
  • B. Smith and J.J. Garcia-Luna-Aceves, “Efficient Security Mechanisms for The Border Gateway Routing Protocol,” accepted for publication in Computer Communications Journal, 1997.
  • J. Behrens and J.J. Garcia-Luna-Aceves, “Fast Dissemination of Link States Using Bounded Sequence Numbers with no Periodic Updates or Age Fields,” Proc. ICDCS’97 International Conference on Distributed Computing Systems, Baltimore, Maryland, May 27 – 30, 1997.
  • S. Murthy and J.J. Garcia-Luna-Aceves, “Loop-Free Internet Routing Using Hierarchical Routing Trees,” Proc. IEEE INFOCOM 97, Kobe, Japan, April 7–11, 1997.
  • B. Smith, S. Murthy, and J.J. Garcia-Luna-Aceves, “Securing Distance Vector Routing Protocols,” Proc. Internet Society Symposium on Network and Distributed System Security, San Diego, California, February 1997.
  • J.J. Garcia-Luna-Aceves and S. Murthy, “A Path Finding Algorithm for Loop-Free Routing,” IEEE/ACM Trans. Networking, February 1997.
  • B. Smith and J.J. Garcia-Luna-Aceves, “Securing the Border Gateway Routing Protocol,” Proc. Global Internet’96, London, UK, 20-21 November 1996.
  • S. Murthy and J.J. Garcia-Luna-Aceves, “Congestion-Oriented Shortest Multipath Routing,” Proc. IEEE INFOCOM 1996, San Francisco, March 1996.

Multicasting:

  • B.N. Levine and J.J. Garcia-Luna-Aceves, ``A Comparison of Reliable Multicast Protocols,” to appear in Multimedi a Systems (ACM/Springer), 1998.
  • B.N. Levine and J.J. Garcia-Luna-Aceves, “Improving Internet Multicast with Routing Labels,” Proc. IEEE ICNP ’97, Atlanta, Georgia, October 28–31, 1997.
  • L. Gu and J.J. Garcia-Luna-Aceves, “New Error Recovery Structures for Reliable Multicasting,” Proc. IC3N ’97: Sixth International Conference on Computer Communications and Networks, Las Vegas, Nevada, September 22–25, 1997.
  • J.J. Garcia-Luna-Aceves and B.N. Levine, “End-to-End Reliable Multicast,” in Multimedia Communications: Protocols and Applications, Chapter 6, Prentice-Hall, 1997.
  • C. Shields and J.J. Garcia-Luna-Aceves, “The Ordered Core Based Tree Protocol,” Proc. IEEE INFOCOM 97, Kobe, Japan, April 7–11, 1997.
  • M. Parsa and J.J. Garcia-Luna-Aceves, “A Protocol for Scalable Loop-Free Multicast Routing,” IEEE Journal on Selected Areas in Communications , April 1997, vol. 15, no. 3, pp. 316-331.
  • M. Parsa and J.J. Garcia-Luna-Aceves, “A Scalable and Loop-Free Multicast Internet Protocol,” Proc. SPIE Multimedia Computing and Networking 1997, San Jose, California, February 1997.
  • B.N. Levine, D. Lavo, and J.J. Garcia-Luna-Aceves, “The Case for Concurrent Reliable Multicasting Using Shared Ack Trees,” Proc. ACM Multimedia 1996 Boston, MA, November 18–22, 1996.
  • B.N. Levine and J.J. Garcia-Luna-Aceves, “A Comparison of Known Classes of Reliable Multicast Protocols,” Proc. International Conference on Network Protocols (ICNP-96), Columbus, Ohio, Oct 29–Nov 1, 1996.