Mesh-based content routing using XML

ABSTRACT

We have developed a new approach for reliably multicasting time-critical data to heterogeneous clients over mesh-based overlay networks. To facilitate intelligent content pruning, data streams are comprised of a sequence of XML packets and forwarded by application-level XML routers. XML routers perform content-based routing of individual XML packets to other routers or clients based upon queries that describe the information needs of downstream nodes. Our PC-based XML router prototype can route an 18 Mbit per second XML stream.Our routers use a novel Diversity Control Protocol (DCP) for router-to-router and router-to-client communication. DCP reassembles a received stream of packets from one or more senders using the first copy of a packet to arrive from any sender. When each node is connected to n parents, the resulting network is resilient to (n − 1) router or independent link failures without repair. Associated mesh algorithms permit the system to recover to (n − 1) resilience after node and/or link failure. We have deployed a distributed network of XML routers that streams real-time air traffic control data. Experimental results show multiple senders improve reliability and latency when compared to tree-based networks.

REFERENCES

• 1: XMLBiaster. http://www.xralblaster, org/.
• 2: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 3: ARMSTRONG, S., ET AL. Multicast transport protocol. RFC 1301, Internet Engineering Task Force, 1992.
• 4: An Efficient Multicast Protocol for Content-Based Publish-Subscribe Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.262, May 31-June 04, 1999
• 5: Anindo Banerjea, Simulation study of the capacity effects of dispersity routing for fault tolerant realtime channels, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.194-205, August 28-30, 1996, Palo Alto, California, United States
• 6: BESTAVROS, A. An adaptive information dispersal algorithm for time-critical reliable communication. In Network Management and Control, Volume II, I. Frish, M. Malek, and S. Panwar, Eds. Plenum Publishing Co., New York, New York, 1994, pp. 423--438.
• 7: BRAY, T., ET AL. Extensible markup language 1.0 (second edition), http : //www.w3. org/TR/REC-xml/, W3C Recommendation, 2000.
• 8: BYERS, J. W., LUBY, M., AND MITZENMACHER, M. Accessing multiple mirror sites in parallel: Using tornado codes to speed up downloads. In Proc. IEEE Infocom (Mar. 1999), pp. 275-283.
• 9: John W. Byers , Michael Luby , Michael Mitzenmacher , Ashutosh Rege, A digital fountain approach to reliable distribution of bulk data, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.56-67, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 10: Antonio Carzaniga , David S. Rosenblum , Alexander L. Wolf, Achieving scalability and expressiveness in an Internet-scale event notification service, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.219-227, July 16-19, 2000, Portland, Oregon, United States [doi>10.1145/343477.343622]
• 11: CHAMBERL1N, D., ET AL. XQuery 1.0; A XML query language, http: //www.w3.org/TR/xquery/W3C Working Draft, 2001.
• 12: CHAWATHE, Y., MCCANNE, S., AND BREWER, E. RMX: Reliable multicast for heterogeneous networks. In Proc. IEEE lnfocom (Mar. 2000), pp. 795-804.
• 13: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 14: Sally Floyd , Van Jacobson , Ching-Gung Liu , Steven McCanne , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, IEEE/ACM Transactions on Networking (TON), v.5 n.6, p.784-803, Dec. 1997 [doi>10.1109/90.650139]
• 15: Hugh W. Holbrook , David R. Cheriton, IP multicast channels: EXPRESS support for large-scale single-source applications, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.65-78, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 16: JANNOTTI, J., GIFFORD, D. K., JOHNSON, K., KAASHOEK, M. F., AND O'TOOLE, J. Overcast: Reliable multicasting with an overlay network. In Proc. USENIX OSDI (Oct. 2000), pp. 197-212.
• 17: Dah Ming Chiu , Stephen Hurst , Miriam Kadansky , Joseph Wesley, TRAM: A Tree-based Reliable Multicast Protocol, Sun Microsystems, Inc., Mountain View, CA, 1998
• 18: P. Karn , C. Partridge, Improving round-trip time estimates in reliable transport protocols, ACM SIGCOMM Computer Communication Review, v.17 n.5, p.2-7, Oct./Nov. 1987
• 19: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 20: LABOVITZ, C., AHUJA, A., ABOSE, A., AND JAHANIAN, F. Routing stability and convergence. In Proc. ACM SIGCOMM (Aug. 2000), pp. 115-126.
• 21: LEMPEL, A., AND ZIV, J. A universal algorithm for sequential data compression. IEEE Trans. on Information Theory 23, 3 (May 1977), 337-343.
• 22: L1N, J.-C., AND PAUL, S. RMTP: A reliable multicast transport protocol. In Proc. IEEE lnfocom (Mar. 1996), pp. 1414- 1424.
• 23: MANBER, U. Finding similar files in a large file system. In Proc. Winter USENIX (Jan. 1994), pp. 1-10.
• 24: MAXEMCHUK, N. F. Dispersity Routing in Store and Forward Networks. PhD thesis, University of Pennsylvania, May 1975.
• 25: A. J. McAuley, Reliable broadband communication using a burst erasure correcting code, Proceedings of the ACM symposium on Communications architectures & protocols, p.297-306, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 26: Steven McCanne , Van Jacobson , Martin Vetterli, Receiver-driven layered multicast, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.117-130, August 28-30, 1996, Palo Alto, California, United States
• 27: L. E. Moser , P. M. Melliar-Smith , D. A. Agarwal , R. K. Budhia , C. A. Lingley-Papadopoulos, Totem: a fault-tolerant multicast group communication system, Communications of the ACM, v.39 n.4, p.54-63, April 1996 [doi>10.1145/227210.227226]
• 28: Brian Oki , Manfred Pfluegl , Alex Siegel , Dale Skeen, The Information Bus: an architecture for extensible distributed systems, Proceedings of the fourteenth ACM symposium on Operating systems principles, p.58-68, December 05-08, 1993, Asheville, North Carolina, United States
• 29: Vern Paxson, End-to-end internet packet dynamics, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.277-292, June 1999 [doi>10.1109/90.779192]
• 30: PENDARAKIS, D., SHI, S., VERMA, D., AND WALDVOGEL, M. ALMI: An application level multicast infrastructure. In Proc. USENIX Syrup. on lnternet Technologies and Systems (USITS) (Mar. 2001), pp. 49-60.
• 31: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 32: Luigi Rizzo, Dummynet: a simple approach to the evaluation of network protocols, ACM SIGCOMM Computer Communication Review, v.27 n.1, p.31-41, Jan. 1997 [doi>10.1145/251007.251012]
• 33: RlZZO, L., AND VICISANO, L. A reliable multicast data distribution protocol based on software DEC techniques. In Proc. IEEE HPCS (June 1997).
• 34: Douglas J. Santry , Michael J. Feeley , Norman C. Hutchinson , Alistair C. Veitch, Elephant: The File System that Never Forgets, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, p.2, March 28-30, 1999
• 35: Stefan Savage , Thomas Anderson , Amit Aggarwal , David Becker , Neal Cardwell , Andy Collins , Eric Hoffman , John Snell , Amin Vahdat , Geoff Voelker , John Zahorjan, Detour: Informed Internet Routing and Transport, IEEE Micro, v.19 n.1, p.50-59, January 1999 [doi>10.1109/40.748796]
• 36: SEGALL, B., ARNOLD, D., BOOT, J., HENDERSON, M., AND PHELPS, T. Content based routing with Elvin4. In Proc. AUUG2K (June 2000).
• 37: STOICA, I., NG, T. S. E., AND ZHANG, H. Reunite: A recursive unicast approach to multicast. In Proc. IEEE Infocom (Mar. 2000), pp. 1644-1653.
• 38: TRIDGELL, A. Efficient Algorithms for Sorting and Synchronization. PhD thesis, Australian National University, Apr. 2000.
• 39: TRIDGELL, A., AND MACKERRAS, P. The rsync algorithm. Tech. Rep. TR-CS-96-05, Australian National University, 1997.
• 40: VOLPE NATIONAL TRANSPORTATION CENTER, AUTOMA- TION APPLICATIONS DIVISION. Aircraft situation display to industry functional description and interfaces. DTS-56 report, Aug. 2000.
• 41: WHETTEN, B., AND TASKALE, G. An overview of reliable multicast transport protocol II. 1EEE Network 14, 1 (Jan. 2000), 37-47.
• 42: Wo, L., SHARMA, R., AND SMITH, B. Thin streams: An architecture for multicasting layered video. In ProctEEElnt'l Workshop on Network and Operating System Support for Digital Audio and Video (May 1997).
• 43: Rajendra Yavatkar , James Griffoen , Madhu Sudan, A reliable dissemination protocol for interactive collaborative applications, Proceedings of the third ACM international conference on Multimedia, p.333-344, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215288]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.2 Document Preparation

          Nouns: XML

General Terms:
Algorithms, Languages, Performance, Reliability