Distributed algorithms and protocols for scalable internet telephony

Distributed Algorithms and Protocols for Scalable Internet Telephony Jonathan Rosenberg Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Graduate School of Arts and Sciences COLUMBIA UNIVERSITY 2001
2001 c Jonathan Rosenberg All Rights Reserved ABSTRACT Distributed Algorithms and Protocols for Scalable Internet Telephony Jonathan Rosenberg Internet telephony service is defined as the provision of real-time, interactive, multimedia telecom- munications services between human users, using the public Internet. The most difficult problem in providing Internet telephony is to overcome the increased jitter, delay, and loss (as compared to circuit-switched networks) suffered by voice. Past work has separately investigated Forward Error Correction (FEC) and playout buffer adaptation mech- anisms to resolve these problems. We show that these mechanisms must be considered jointly.

We propose and simulate a number of algorithms for integrating FEC into playout buffer adaptation schemes, and show that they are superior to non-integrated algorithms. Receiving feedback about network transport quality is essential for supporting adaptive applications. We examine the issues surrounding scalability of transport feedback in large scale multicast groups. We present, analyze, and simulate a class of algorithms termed reconsideration, which support congestion controlled feedback in highly dynamic groups, and then show how the memory requirements of our algorithms can be reduced.

We consider signaling protocols for providing call establishment, management, features, and applications. After an analysis of existing Internet telephony signaling protocols, we propose a new protocol, the Session Initiation Protocol (SIP), which overcomes the limitations of existing protocols. We describe an implementation of this protocol in software, and discuss applications we have built with it. We consider interconnection with the telephone network, and focus on the problem of discovery of telephony gateways.

We show that this is a subset of a broader wide area service discovery problem. After reviewing existing protocols for resource discovery (and finding them lacking for wide area applications), we present a scalable protocol for wide area service discovery, which is ideal for discovery of gateways, amongst other resources. Finally, we consider the problem of a service architecture for Internet telephony, which provides features and complex applications to users. We review the service architectures that have been presented in the literature.

We then propose our architecture, the application component architecture, which combines the best aspects of existing work. We show how this architecture can be used to provide several complex applications. Contents List of Tables x List of Figures xi Acknowledgments xv Chapter 1 Introduction 1 1.1 Components of an Internet Telephony Service .3 Results for Receivers .4 Results for Senders .3 Review of Existing Recovery Mechanisms .4 Media Aware vs. Media Unaware Recovery .2 Magnitude of Error .3 Contribution of Resynchronization .5 Integrating FEC with Playout Buffers .1 The Coupling Effect .2 Reed-Solomon FEC .3 Conditions for Dependency .4 A Note on Applicability .2 Existing Playout Buffer Algorithms .3 New Playout Buffer Algorithms .1 Virtual Delay Algorithms .1 Formulation for Redundant Codecs .2 Formulation for Reed Solomon FEC .4 Proof of Correctness .5 Supporting Target Loss Probabilities .2 “Previous Optimal” Algorithm .3 Model-Based “Analytical” Playout Adaptation Algorithm .3 Comparisons of New Algorithms .1 Using FEC with Minimal Delays .2 Achieving a Specific Loss Target .3 Achieving a Varying Loss Target .6 Transport of Media-Unaware FEC .1 FEC Packet Structure .1 RTP Header of FEC Packets .4 Determination of the Set of Packets .7 Conclusion and Future Work.

79 Chapter 3 QoS Feedback 81 3.2 Overview of RTP .1 RTCP: Control and Management .3 Problems with RTCP Feedback .4 Requirements of a Solution for IP telephony .5 Taxonomizing the Solution Space .1 Feedback Destination: Where .2 Feedback Mechanism: How .3 Feedback Source: Who .4 Feedback Content: What .5 Congestion Control: When .3 Separate Multicast Groups .4 Event-Based Reporting .1 Computing the Send Probability .2 Computing the Scheduled Rate .3 Obtaining the ODE .4 Computing the Level of Congestion .5 Reconsideration as a Control Mechanism .6 Computing the Convergence Time .2 Modeling Delay and Loss .1 Number of Packets Sent for Conditional Reconsider- ation .2 Number of Packets Sent for Unconditional Reconsid- eration .3 Duration of Plateau Period .4 Steady State Behavior .6 Single User Joins Late .8 BYE Reconsideration Algorithm .1 Quantifying the Problem .2 Reverse Reconsideration Algorithm .2 Increasing the Sampling Probability .3 Reducing the Sampling Probability. 158 Chapter 4 Signaling Protocols 160 4.2 Requirements for a Signaling Protocol .3 Existing Signaling Protocols .2 SIP Network Servers .4 Addressing and Naming .5 Initiating, Modifying, and Terminating Calls .7 Session Description Protocol Usage .8 SIP as a Tool for New Services .1 Events and Threading .3 Server State Machine .4 Client State Machine .5 Mediator State Machine .6 Conclusions and Future Work. 196 Chapter 5 Gateway and Service Discovery 198 5.1 Service Location Protocol .1 Telephony Routing over IP (TRIP) .5 Multicast Push and Pull .6 Summary of Existing Architectures .5 Wide Area Service Discovery Protocol .3 BA URL’s and Attributes .9 Sending Multicast Advertisements .10 Scheduling Transmission of Advertisements .1 Timing Out Senders .2 Minimum Transmission Interval .12 Reducing the Storage Requirements of a BA. 241 Chapter 6 Application Architecture 242 6.2 Requirements for an Internet Telephony Service Architecture .2 Distributed Software Architectures .3 Distributed Component Architectures .1 General Purpose Languages .2 Domain Specific Languages .4 Application Component Architecture .3 Text-To-Speech Component .4 Additional Session Components .8 Third Party Call Control .3 Continued Processing of Third Party Calls .4 End User Initiates Call .9 Obtaining Data from End Users .1 Pre-Paid Calling Card .2 Click-to-dial .4 Web Form Entry for Call Center .5 Speech-to-text for the Hearing Impaired .6 Comparison to Existing Architectures .1 DFC and ECLIPSE .2 Distributed Software and Component Architectures .7 Conclusions and Future Work.

303 Chapter 7 Conclusion and Future Work 305 ix List of Tables 2.1 Locations of stations .2 Statistics of Traces .3 Resynchronization Time vs.5 Subjective Evaluation of Speech Quality. and SD of MSE for mix1 and mix2 .1 Operating Point of Summarizers in the Feedback Taxonomy .2 Operating Point of Polling in the Feedback Taxonomy .3 Operating Point of Separate Multicast Groups in the Feedback Taxonomy .4 Operating Point of Event Based Reporting in the Feedback Taxonomy .5 Transient Behavior for Various Group Sizes .6 Group Size Estimate with Sampling Algorithms. 157 x List of Figures 2.2 Mean loss probability for trace 1 .3 Mean loss probability for trace 2 .4 Mean loss probability for trace 3 .5 Conditional loss probability for trace 1 .6 Conditional loss probability for trace 2 .7 Conditional loss probability for trace 3 .8 Burst loss length distribution for trace 1 .9 Burst loss length distribution for trace 2 .10 Burst loss length distribution for trace 3 .11 Cumulative distribution of delay increase from playout buffers for trace 1 .12 Cumulative distribution of delay increase from playout buffers for trace 2 .13 Cumulative distribution of delay increase from playout buffers for trace 3 .14 RTT delay distribution, Columbia to U.15 RTT delay distribution, Columbia to USC .16 RTT delay distribution, Columbia to Germany .17 Evolution of RTT, Columbia to U.18 Evolution of RTT, Columbia to USC .19 Evolution of RTT, Columbia to Germany .20 Cumulative distribution of resynchronization times .21 Cumulative distribution of avg.22 Mix1 and mix2 .23 Preferences for mix1, mix2, or neither .24 Piggybacking FEC packets for a (5, 3) Reed Solomon code .25 Performance of Adaptively Virtual Algorithms on Trace 2 .26 Performance of Adaptively Virtual Algorithms on Trace 1 .27 Performance of Adaptively Virtual Algorithms on Trace 3 .28 Comparison of Loss and Delay Performance across All Algorithms .29 Performance of Algorithms in Achieving a Target Loss of 0.30 Performance of Algorithms in Achieving Varying Target Loss Probability .31 FEC packet structure .32 Parity header format .1 RTP fixed header format .2 Current RTCP Algorithm .6 Learning curve, step join with N =10,000 .7 Total packets sent, step join with N =10,000 .8 Effect of delay distribution on transient for conditional reconsideration .9 Linear joins: conditional reconsideration .10 Linear joins: unconditional reconsideration .11 Computing Psend with reconsideration. Analytical Scheduled Rate Integral.

analytical learning curve .15 Transient with Conditional Reconsideration .16 Transient with Unconditional Reconsideration .17 Steady State RTCP Packet Rate .18 Oscillating Steady State RTCP Packet Rate .19 Coefficient of Variation of Packets Transmitted .20 BYE Reconsideration Performance .21 Premature Timeout Problem .22 Reverse Reconsideration Algorithm .23 Group Size Estimate with Reverse Reconsideration .24 Comparison of SSRC Sampling Algorithms .1 Typical SIP deployment .2 Typical SIP INVITE message .3 SDP message example .4 gosSIP threading architecture .5 gosSIP state machine architecture .6 Example CPL+ script .1 Architecture for TRIP .2 Customer X uses gateway through bilateral provider relationships .3 Worst and best case topologies for indexed database query times .5 SA state machine .1 IN conceptual model .2 Call flow for a phone call .3 A usage in the DFC architecture .4 Application component architecture .5 Client interaction with dialog server for PIN collection .6 Message exchange for basic presence service .7 Call flow for interface to message component .8 Interface between the controller and session components .9 Signaling and media relationships in third party call control .10 3pcc basic flow .11 3pcc advanced flow .12 Hanging up with 3pcc .13 Alternative to hangup .14 3pcc where the end user initiates .15 Using HTTP as a stimulus protocol .16 Pre-Paid calling card service .17 Click-to-dial service .18 First half of auto-conference service .19 Call establishment phase of auto-conference .20 Call flow for web form entry for call center .21 Bidirectional translation services for the hearing impaired. 299 xiv xv Acknowledgments First and foremost, Professor Henning Schulzrinne deserves recognition for his tremendous con- tributions to this work, in addition to recognition for the immeasurable impact he has had on my career and professional development. Professor Schulzrinne provided guidance, knowledge, insight and direction whenever it was needed. He introduced me to many of the pioneers in the Internet, giving me an opportunity to learn from them as well.

He introduced me to the Internet Engineering Task Force (IETF), a professional organization through which much of this work has found a commercial outlet. I will be forever in his debt. Several other individuals deserve special recognition for their impact on this thesis. Lili Qiu deserves recognition as a key contributor of much of the work in transport chap- ter.

She prepared many of the simulations and the plots used in the section on playout buffer integration. She was also responsible for the fine tuning of parameters that took place for many of the algorithms. She contributed the idea of the previous optimal algorithm, and helped refine the formulation for the analytical algorithm. The taxonomy for feedback presented in the feedback section was the result of joint work with Joerg Nonnenmacher and Markus Hoffman from Bell Laboratories.

Daniel Rubenstein de- serves complete credit for the proof of the steady-state unconditional reconsideration rate. The initial concept of reconsideration (which we now call conditional reconsideration) was proposed by Henning Schulzrinne. The original concept of SSRC sampling was proposed by Steve Casner. Much of this work has been reviewed and commented on by members of the AVT working group in IETF, and in particular, Steve Casner, Colin Perkins and Bill Fenner.

The work on generating requirements for the general service discovery problem was done jointly with Erik Guttman from SUN Microsystems and Ryan Moats from AT&T Labs. Dave Oran from Cisco deserves credit for first recognizing that the bilateral model is nearly identical to the BGP4 model. Erik Guttman provided many comments on the WASRV protocol which made their way into this thesis. Dina Katabi contributed many ideas and thoughts on performance for WASRV.

Mark Handley (ACIRI), Henning Schulzrinne and Eve Schooler (Caltech) deserve recog- nition for the initial work on SIP. Pete Mataga from dynamicsoft contributed to many of the ideas on the component architecture for SIP, along with assistance in defining some of the combined services presented here.