Improving network efficiency in real-time groupware with general message compression

ABSTRACT

Groupware communicates by sending messages across the network, and groupware programmers use a variety of formats for these messages, such as XML, plain text, or serialized objects. Although these formats have many advantages, they are often so verbose that they overload the system's network resources. Groupware programmers could improve efficiency by using more compact formats, but this efficiency comes at the cost of increased complexity, reduced convenience, and reduced readability. In this paper we propose an alternate approach for improving efficiency -- an automatic compression system that transparently minimizes verbose formats. Our general message compressor -- GMC -- automatically finds and removes redundancy in message streams, without any knowledge of the contents or structure of the message, and without any need for the programmer to change the way they work. In tests with realistic message traces, GMC reduced text messages to 20% of their original size, XML messages to 8% of the original, and serialized objects to 9%. Although not as compact as a hand-coded representation, GMC provides most of the compression benefits with almost none of the work -- it allows groupware programmers to use convenient message formats without compromising transport efficiency.

REFERENCES

• 1: AT&T Corp. VNC - How it Works, available at www.uk. research.att.com/archive/vnc/howitworks.html, 1999.
• 2: James “Bo” Begole , Mary Beth Rosson , Clifford A. Shaffer, Supporting worker independence in collaboration transparency, Proceedings of the 11th annual ACM symposium on User interface software and technology, p.133-142, November 01-04, 1998, San Francisco, California, United States [doi>10.1145/288392.288588]
• 3: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 4: Tom Beigbeder , Rory Coughlan , Corey Lusher , John Plunkett , Emmanuel Agu , Mark Claypool, The effects of loss and latency on user performance in unreal tournament 2003®, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016556]
• 5: Jeff Dyck , Carl Gutwin , Sriram Subramanian , Christopher Fedak, High-performance telepointers, Proceedings of the 2004 ACM conference on Computer supported cooperative work, November 06-10, 2004, Chicago, Illinois, USA [doi>10.1145/1031607.1031636]
• 6: GarageGames. Torque Network Library Design Fundamentals, 2005. Available at: opentnl.sourceforge.net/doxydocs/fundamentals.html
• 7: Gracanin, D., Zhou, Y., and DaSilva, L. Quality of Service for Networked Virtual Environments. IEEE Communications Magazine, April 2004.
• 8: Gutwin, C. The Effects of Network Delays on Group Work in Real-Time Groupware. Proc. ECSCW 2001, 299--318.
• 9: Carl Gutwin , Reagan Penner, Improving interpretation of remote gestures with telepointer traces, Proceedings of the 2002 ACM conference on Computer supported cooperative work, November 16-20, 2002, New Orleans, Louisiana, USA [doi>10.1145/587078.587086]
• 10: Carl Gutwin , Steve Benford , Jeff Dyck , Mike Fraser , Ivan Vaghi , Chris Greenhalgh, Revealing delay in collaborative environments, Proceedings of the SIGCHI conference on Human factors in computing systems, p.503-510, April 24-29, 2004, Vienna, Austria [doi>10.1145/985692.985756]
• 11: Huffman, D., A method for the construction of minimum redundancy codes. Proceedings of the IRE, vol. 40, 1962, 1098--1101.
• 12: International Telecommunication Union (ITU), Standard T.120 - Data Protocols for Multimedia Conferencing, 1996.
• 13: ISO/IEC 8824-1. Abstract Syntax Notation One: Specification of Basic Notation. www.itu.int/ITU-T/studygroups/com17/languages/X.680amd1.pdf, 2006.
• 14: Ivan Marsic, Real-Time Collaboration in Heterogeneous Computing Environments, Proceedings of the The International Conference on Information Technology: Coding and Computing (ITCC'00), p.222, March 27-29, 2000
• 15: OSS-Nokalva Inc., Alternative binary representations of the XML Information Set based on ASN.1, Proc. W3C Workshop on Binary Interchange of XML Information Item Sets, www.w3.org/2003/08/binary-interchange-workshop/32-OSS-Nokalva-Position-Paper-updated.pdf, 2006.
• 16: Kyoung Shin Park , Robert V. Kenyon, Effects of Network Characteristics on Human Performance in a Collaborative Virtual Environment, Proceedings of the IEEE Virtual Reality, p.104, March 13-17, 1999
• 17: Phillips, W.G. Architectures for Synchronous Groupware. Technical Report 1999-425. Department of Computing and Information Science, Queen's University, 1999.
• 18: Mark Roseman , Saul Greenberg, TeamRooms: network places for collaboration, Proceedings of the 1996 ACM conference on Computer supported cooperative work, p.325-333, November 16-20, 1996, Boston, Massachusetts, United States [doi>10.1145/240080.240319]
• 19: Mark Roseman , Saul Greenberg, Building real-time groupware with GroupKit, a groupware toolkit, ACM Transactions on Computer-Human Interaction (TOCHI), v.3 n.1, p.66-106, March 1996 [doi>10.1145/226159.226162]
• 20: Rakkarsoft. Raknet Manual. Available at: http://www.rakkarsoft.com/raknet/manual/. 2004.
• 21: Schulzrinne, H., Casner, S., Frederick, R., Jacobson, V. RTP: A Transport Protocol for Real-Time Applications, Internet Engineering Task Force, Audio-Video Transport Working Group, Jan. 1996. RFC-1889.
• 22: Seroussi, G. and Lempel, A., Compression using Small Dictionaries with Applications to Network Packets, United States Patent 5389922, 1995.
• 23: Smed, J., Kaukoranta, K., and Hakonen, H. A Review on Networking and Multiplayer Computer Games. Technical Report 454, Turku Centre for Computer Science, 2002.
• 24: Tye, C., and Fairhurt, G. A Review of IP Packet Compression Techniques. PGNet 2003, Liverpool, 2003.
• 25: Ivan Vaghi , Chris Greenhalgh , Steve Benford, Coping with inconsistency due to network delays in collaborative virtual environments, Proceedings of the ACM symposium on Virtual reality software and technology, p.42-49, December 20-22, 1999, London, United Kingdom [doi>10.1145/323663.323670]
• 26: Ziv, J., and Lempel, A. A Universal Algorithm for Sequential Data Compression. IEEE Transactions on Information Theory, 23(3), 1977, 337--343.
• 27: Ziv, J., and Lempel, A. Compression of Individual Sequences via Variable Rate Encoding. IEEE Transactions on Information Theory, 24(5), 1978, 530--536.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Computer-supported cooperative work

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

General Terms:
Algorithms, Design, Experimentation, Human Factors

Keywords:
groupware performance, message compression, network delay