A model, analysis, and protocol framework for soft state-based communication

ABSTRACT

"Soft state" is an often cited yet vague concept in network protocol design in which two or more network entities intercommunicate in a loosely coupled, often anonymous fashion. Researchers often define this concept operationally (if at all) rather than analytically: a source of soft state transmits periodic "refresh messages" over a (lossy) communication channel to one or more receivers that maintain a copy of that state, which in turn "expires" if the periodic updates cease. Though a number of crucial Internet protocol building blocks are rooted in soft state-based designs --- e.g., RSVP refresh messages, PIM membership updates, various routing protocol updates, RTCP control messages, directory services like SAP, and so forth --- controversy is building as to whether the performance overhead of soft state refresh messages justify their qualitative benefit of enhanced system "robustness". We believe that this controversy has risen not from fundamental performance tradeoffs but rather from our lack of a comprehensive understanding of soft state. To better understand these tradeoffs, we propose herein a formal model for soft state communication based on a probabilistic delivery model with relaxed reliability. Using this model, we conduct queueing analysis and simulation to characterize the data consistency and performance tradeoffs under a range of workloads and network loss rates. We then extend our model with feedback and show, through simulation, that adding feedback dramatically improves data consistency (by up to 55%) without increasing network resource consumption. Our model not only provides a foundation for understanding soft state, but also induces a new fundamental transport protocol based on probabilistic delivery. Toward this end, we sketch our design of the "Soft State Transport Protocol" (SSTP), which enjoys the robustness of soft state while retaining the performance benefit of hard state protocols like TCP through its judicious use of feedback.

REFERENCES

• 1: Elan Amir , Steven McCanne , Randy Katz, Receiver-driven bandwidth adaptation for light-weight sessions, Proceedings of the fifth ACM international conference on Multimedia, p.415-426, November 09-13, 1997, Seattle, Washington, United States [doi>10.1145/266180.266395]
• 2: Elan Amir , Steven McCanne , Randy Katz, An active service framework and its application to real-time multimedia transcoding, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.178-189, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 3: Hari Balakrishnan , Hariharan S. Rahul , Srinivasan Seshan, An integrated congestion management architecture for Internet hosts, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.175-187, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 4: Anindo Banerjea , Domenico Ferrari , Bruce A. Mah , Mark Moran , Dinesh C. Verma , Hui Zhang, The Tenet real-time protocol suite: design, implementation, and experiences, IEEE/ACM Transactions on Networking (TON), v.4 n.1, p.1-10, Feb. 1996 [doi>10.1109/90.503757]
• 5: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 6: André Schiper , Kenneth Birman , Pat Stephenson, Lightweight causal and atomic group multicast, ACM Transactions on Computer Systems (TOCS), v.9 n.3, p.272-314, Aug. 1991 [doi>10.1145/128738.128742]
• 7: Kenneth Birman , Mark Hayden , Oznur Ozkasap , Zhen Xiao , Mihai Budiu , Yaron Minsky, Bimodal Multicast, Cornell University, Ithaca, NY, 1998
• 8: BOLOT, J.-C., AND TURLETTI, T. A Rate Control Mechanism for Packet Video in the Internet. In Proceedings IEEE lnfocom '94 (Toronto, Canada, June 1994), ACM.
• 9: Jean-Chrysostome Bolot , Thierry Turletti , Ian Wakeman, Scalable feedback control for multicast video distribution in the Internet, Proceedings of the conference on Communications architectures, protocols and applications, p.58-67, August 31-September 02, 1994, London, United Kingdom
• 10: CHANDY, K. M., RIFKIN, A., AND SCHOOL~n, E. Using Announce-Listen with Global Events to Develop Distributed Control Systems. Concurrency: Practice and Experience (1998), 1021-1027.
• 11: CHESSON, G. XTP/Protocol Engine Design. In Proceedings of the IFIP WG6.1/6.~ Workshop (Riischlikon, May 1989).
• 12: D. Clark, The design philosophy of the DARPA internet protocols, Symposium proceedings on Communications architectures and protocols, p.106-114, August 16-18, 1988, Stanford, California, United States
• 13: D. D. Clark , D. L. Tennenhouse, Architectural considerations for a new generation of protocols, Proceedings of the ACM symposium on Communications architectures & protocols, p.200-208, September 26-28, 1990, Philadelphia, Pennsylvania, United States
• 14: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 15: Stephen Deering , Deborah Estrin , Dino Farinacci , Van Jacobson , Ching-Gung Liu , Liming Wei, An architecture for wide-area multicast routing, Proceedings of the conference on Communications architectures, protocols and applications, p.126-135, August 31-September 02, 1994, London, United Kingdom
• 16: Luca Delgrossi , Ralf Guido Herrtwich , Frank Oliver Hoffmann , Sibylle Schaller, Receiver-initiated communication with ST-II, Multimedia Systems, v.2 n.4, p.141-149, Oct. 1994 [doi>10.1007/BF01210445]
• 17: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 18: FAI,K, A., AND PAXSON, V. Minutes of the "RUTS" IETF BOF, Dec. 1998. ftp://ftp.ee.lb!.gov/ietf/ruts-98-minutes.
• 19: Sally Floyd , Van Jacobson, Link-sharing and resource management models for packet networks, IEEE/ACM Transactions on Networking (TON), v.3 n.4, p.365-386, Aug. 1995 [doi>10.1109/90.413212]
• 20: Sally Floyd , Van Jacobson , Steve McCanne , Ching-Gung Liu , Lixia Zhang, A reliable multicast framework for light-weight sessions and application level framing, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.342-356, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 21: HANOLEY, M. SAP: Session Announcement Protocol. Internet Draft, Nov 19, 1996.
• 22: Mark Handley, Session directories and scalable Internet multicast address allocation, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.105-116, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 23: Mark Handley , Jon Crowcroft, Network text editor (NTE): A scalable shared text editor for the MBone, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.197-208, September 14-18, 1997, Cannes, France
• 24: HANDLEY, M., AND JACOBSON, V. sdr- A Multicast Session Directory. University College London.
• 25: HEORICK, C. Routing Information Protocol. Rutgers University, June 1988. RFC-1058.
• 26: JACOBSON, V. Session Directory. Lawrence Berkeley Laboratory, ftp://ftp.ee.lbl.gov/conferencing/sd.
• 27: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 28: JACOBSON, V. SIGCOMM '94 Tutorial: Multimedia conferencing on the Internet, Aug. 1994.
• 29: JACOBSON, V., AND MCCANNE, S. LBL Whiteboard. Lawrence Berkeley Laboratory ftp://ftp.ee.lbl.gov/conferencing/wb.
• 30: JACOBSON, V., AND MCCANNE, S. Visual Audio Tool. Lawrence Berkeley Laboratory. ftp://ftp.ee.lbl.gov/conferencing/vat.
• 31: JAIN, R. Congestion Control in Computer Networks: Issues and Trends. IEEE Network Magazine (May 1990), 24-30.
• 32: JAIN, R., P~AMAKRISHNAN, K., AND CH{U, D.-M. Congestion Avoidance in Computer Networks With a Connectionless Network Layer. Tech. Rep. DEC-TR-506, Digital Equipment Corporation, Aug. 1987.
• 33: LOUGHEED, K., AND REKHTER, Y. A Border Gateway Protocol (BGP). Cisco Systems and T. J. Watson Research Center, IBM Corp., June 1989. RFC-II05.
• 34: MCCAN~'E, S. Receiver-driven Layered Multicast. PhD thesis, University of California, Berkeley, Dec. 1996.
• 35: Steven McCanne , Van Jacobson, vic: a flexible framework for packet video, Proceedings of the third ACM international conference on Multimedia, p.511-522, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215315]
• 36: McQumr. AN, J., ET AL. A New Routing Algorithm for the ARPANET. IEEE 7h~nscations on Networking (May 1980).
• 37: MOCKAPETRIS, P. Domain Names - Implementation and Specification. SRI International, Menlo Park, CA, Nov. 1987. RFC-1035.
• 38: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 39: POINTCAST INC. PointCast Home Page. http://www.p oint cast. com.
• 40: Suchitra Raman , Steven McCanne, Scalable data naming for application level framing in reliable multicast, Proceedings of the sixth ACM international conference on Multimedia, p.391-400, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290808]
• 41: REALNETWORKS, INC. RealPlayer. http://www.real.com/.
• 42: REJAm, R., HANDLZY, M., AND ESTR~N, D. RAP: An Endto-end Rate-based Congestion Control Mechanism for Realtime Streams in the lnternet. IEEE lnfocom (1999).
• 43: PdVEST, R. The MD5 Message-Digest Algorithm. MIT Laboratory for Computer Science and RSA Data Security, Inc., 1992. RFC-1321.
• 44: Eve M. Schooler, A Multicast User Directory Service for Synchronous Rendezvous, California Institute of Technology, Pasadena, CA, 1996
• 45: SCHULZRINNE, H., CASNE,~, S., FREDERICK, R., AND JACOB- SON, V. RTP: A Transport Protocol for Real-Time Applications. Internet Engineering Task Force, Audio-Video Transport Working Group, Jan. 1996. I~FC-1889.
• 46: Puneet Sharma , Deborah Estrin , Sally Floyd , Van Jacobson, Scalable Timers for Soft State Protocols, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.222, April 09-11, 1997
• 47: Ion Stoica , Hui Zhang , T. S. Eugene Ng, A hierarchical fair service curve algorithm for link-sharing, real-time and priority services, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.249-262, September 14-18, 1997, Cannes, France
• 48: TURLETTI, T., AND BOLOT, J.-C. Issues with Multicast Video Distribution in Heterogeneous Packet Networks. In Proceedings of the Sixth International Workshop on Packet Video (Portland, OR., Sept. 1994).
• 49: Digital Subscriber Signalling System No. 1 (DSS I) - ISDN User-Network Interface Layer 3 Specification for Basic Call Control, 1993. ITU-T Recommendation Q.931.
• 50: Procedures for Establishing Communication between Three or more Audiovisual Terminals using Digital Channels up to 1920 kbit/s, 1997. ITU-T Recommendation H.243.
• 51: WALDSPUR(}ER, C. A., AND WEIHL, W. E. Lottery Scheduling: Flexible Proportional-Share Resource Management. In First Symposium on Operating Systems Design and Implementation (OSDI) (1995), USENIX Association, pp. 1-11.
• 52: C. A. Waldspurger , E. Weihl. W., Stride Scheduling: Deterministic Proportional- Share Resource Management, Massachusetts Institute of Technology, Cambridge, MA, 1995
• 53: ZHANG, L., DEF, RIN~, S., ESTRIN, D., SHENKER, S., AND ZAPPALA, D. R. SVP: A New Resource ReSerVation Protocol. IEEE Network Magazine (Sept. 1993), 8-18.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

General Terms:
Design, Management, Measurement, Performance, Reliability, Standardization, Theory