Traffic Optimization and Congestion Avoidance in Distributed Systems

(1)

Abstract

The way users utilize the Internet has drastically changed in the last decade. Some years ago, the average user used to identify the Internet with the web browsing ap-plication. Nowadays there are multiple applications available for the users; the way people do shopping, mantain social relationships, do research and get entertainment has dramatically changed given the new bouquet of applications available on the Internet.

Historically, the Internet has a best-effort nature that does not match the require-ments of amny of these emerging applications. Real-time, delay-sensitive appli-cations need a more reliable infrastructure. For this reason, new communication models have been developed and new issues arose. In general, we can identify these communication models as Distributed Systems. In this thesis, we investigate the new issues that arose from different new applications (i.e. VoIP, delay-sensitive content delivery and live streaming) and the related communication infrastructure (client/server, Content Delivery Network, Peer to Peer).

For each application/infrastructure we describe the issues, we define a goal and then we describe the solution to fulfill such goal. To do so, we present three use-cases and go into details for each of them; at the end we conclude with some general findings obtained from the specific solutions applied to each of the investigated scenario.

(2)

(3)

(4)

You know you have a distributed system when the crash of a computer you have never heard of stops you from getting any work done. LESLIE LAMPORT

(5)

Acknowledgements

It would not have been possible to write this doctoral thesis without the help and support of the kind people around me, to only some of whom it is possible to give particular mention here. This thesis would not have been possible without the help, support and patience of my supervisors, Prof. Franco Russo, Prof. Stefano Giordano and Prof. Rosario Garroppo.

Then, I would like to thank my family. I miss them every day; my parents, brother and sister have given me their unequivocal support throughout, as always, for which my mere expression of thanks likewise does not suffice.

What a reader will find in these pages is the result of three years of work. What a reader will not find is the experience that I built everyday, the amazing gifts of friend-ship that I had the luck to receive from the people I met and made everything easier. A particular thanks to my friends Gianfranco, Alice, Martina, Andrea Dippi, Andrea E., Valentina, Mariella; thanks to them I enjoyed my stay in Pisa and I was able to do my job, during bad days and good days. And they were always there.

My personal and professional way would not have been complete without the expe-rience abroad at NEC Europe Laboratories of Heidelberg. A sincere thanks goes to my supervisor in NEC, Saverio Niccolini for his pragmatic advices and his faculty to go always straight to the point.

(6)

about my work and myself that I could not imagine my life today without this expe-rience.

Thanks to Davide that made me laugh everyday and made the first six months of my internship the funniest of the whole period. I will never forget it. Thanks to Maurizio, Stefano, Claudio, Vincenzo, Stefi, Mohamed because they were with me everyday and made the stay so far away from my family easier. A special thanks to Armin that is balancing my universe.

The most important thing that a reader will not find in these pages are the choices, the decisions that I had to take in the last year. All these decisions made me the person that I am today, and she is not the same person of three years ago. This is the result that really matters.

For any errors or inadequacies that may remain in this work, of course, the responsi-bility is entirely my own.

(7)

List of Figures

2.1 Server/Client Transactions in SIP Elements . . . 14

2.2 OCProxy Model Implemented in ns-2 . . . 16

2.3 Local Protection: Queuing Structure . . . 18

2.4 The recv Method . . . 22

2.5 The handle Method . . . 23

2.6 NLMS Algorithm Scheme . . . 30

2.7 Prediction-Based Controller (with Transaction Approach) . . . 33

2.8 SIP Message: 100Trying . . . 34

2.9 Via Header Field with ’oc’ Parameter . . . 34

2.10 Simulation Scenario . . . 36

2.11 SIP Signaling with CSD, Tiand Ts . . . 38

2.12 Goodput without Overload Control Mechanism . . . 41

2.13 Queuing Discipline Comparison: CFP and FIFO . . . 46

2.15 Goodput with Local + Remote Overload Control - Transaction vs TU approach 52 2.16 Goodput with Local + Remote Overload Control (Transaction approach with NMLS prediction) . . . 52

(14)

4.3 Locality Parameter: Different Strategies . . . 97

4.4 Configuration [0.8 0.1 0.1]: Locality Parameters . . . 100

4.5 Configuration [0.33 0.33 0.33]: Locality Parameters . . . 100

4.6 Estimated CDF of the Peers’ Lifetime . . . 103

4.7 Locality Parameter: Different Strategies . . . 105

4.8 The Observed Cost per Chunk (in cost unit) and the 99% C.I. . . 107

4.9 The Observed inter-PoP Traffic (in %) and the 99% C.I. . . 107

4.10 The Observed Average Chunk Delay (in s) and the 99% C.I. . . 108

4.11 The Observed Average Chunk Loss (in %) and the 99% C.I. . . 108

5.1 General Structure of a Mobile Carrier Network and Enabled Access to Distributed Content Caches by Means of Traffic Breakout . . . 126

5.2 Content Retrieval Costs for Different Cache Locations (dPSGW) and Different Cache Hit Rates (20% [circles], 60% [squares] and 80% [diamonds]) . . . 128

5.3 Logical Storage Space . . . 131

5.4 Total Aggregated Network Cost for Network-Driven Heuristic (circle) and the Network-Unaware Algorithm (square) Varying the Placement Repetition Interval 135 5.5 CDN Request Routing . . . 138

5.6 Operator-owned CDN . . . 138

6.1 Initialisation phase, Growth phase and Saturation . . . 143

6.2 Content-Period Evolution Distribution. . . 144

6.3 DIGGData Set Vote Distribution . . . 155

6.4 The time evolution of the popularity of one object (solid line). At each window the centroid is given (dashed line) and as are members of the cluster (thin grey lines). Figure 6.4(a) illustrates how clusters formed with the SA evolve with time. While figure 6.4(b) illustrates how clusters formed with the nROC evolve . . . . 157

(15)

LIST OF FIGURES

6.5 The Number of Clusters per Time-Interval for Both the SA and nROC Features . 158 6.6 Clusters Properties: nROC Feature (Figs 6.6(a), 6.6(b)) and SA Feature (Figs

6.6(c), 6.6(d)) . . . 159

6.7 Clusters Properties: Distribution of the Clusters obtained using the SA feature in the Time Interval 64-68 hours . . . 160

6.8 Classification Error: Digg Dataset . . . 162

6.9 DIGGDistribution of the Number of Hits. The Embedded Figure Includes the Outliers (95%) Accounting for less that x% . . . 163

6.10 Classification Error: Dataset Comparison . . . 165

6.11 Comparison with Linear Regression Model . . . 172

(16)

(17)

List of Tables

2.1 Queuing Structures Comparison . . . 43

2.2 Performance Comparison for Different Service Disciplines and Buffer Size B . . 43

2.3 CFP Performance for Different Buffer Size B . . . 43

4.1 Parameters of Chunk Level Simulation Study . . . 92

4.2 Classes of Peers: For each Class i, Percentage of Peers Belonging to it and Upload Bandwidth . . . 92

4.3 Topology Construction Strategies . . . 95

4.4 Overlay Performance in an Homogeneous Scenario . . . 99

4.5 Overlay Performance in an Homogeneous Scenario . . . 99

4.6 Cross-Area Traffic (%) in Homogeneous scenario . . . 100

4.7 Comparison between Cross-Area Traffic (%) . . . 101

4.8 Chunk Loss (%) . . . 102

4.9 Simulation Results: ISP’s Perspective . . . 106

4.10 Simulation Results: Users’ Perspective . . . 109

(18)

6.1 The Data Set . . . 153 6.2 Naïve Bayes classier prediction horizon accuracy on DIGG. . . 167 6.3 Naïve Bayes classier prediction horizon accuracy on YOUTUBE. . . 167

(19)

Abbreviations

ALTO Application Layer Traffic Optimization ATM Asynchronous Transfer Mode BD Bottleneck Domain BNF Backus-Naur Form CAPEX Capital Expenditure CCF Cluster Control Function CDF Cumulative Distribution Function CDN Content Delivery Network CDNCF CDN Control Function CFP Combined FIFO and Priority CI Confidence Interval CPS Calls per Second CSD Call Setup Delay DF Delivery Functio DHT Distributed Hash Table DPF Distribution Point Function EP Entry Point

FIFO First-In-First-Out

GPP 3rd Generation Partnership Projects

HD High Definition

IETF Internet Engineering Task Force IMS IP Multimedia Subsystem IP Internet Protocol IP Internet Protocol ISP Internet Service Provider

k-HST k-Hierarchically well-Separated Trees K-MST K-Minimum Spanning Trees KBN K Better Neighbors

KBNL KBN Topology with periodic LOC-AW KBNLD&BA KBNL with minimization of e2e delay

and Latest-BA

KLED&BA K-Lowest-End-To-End-Delay and Latest-BA

L-GW Local Gateway

LMMSE Linear Minimum Mean Square Error LOC-AW Locality Aware

LRU Least Recently Used

MPLS Multi Protocol Label Switching MST Minimum Spanning Tree NGN Next Generation Networks NLMS Normalized Least Mean Square OCProxy Overload Control Proxy OPEX Operational Expenditure OTT Over the Top Content P2P Peer to Peer PoP Point of Presence

PSTN Public Switched Telephone Network QoE Quality of Experience

(20)

RND&BA Random Topology and Latest-BA RNDL Random Topology with periodic LOC-AW RR Round Robin

SD Standard Definition SIP Session Initiation Protocol SKBN Simple K Better Neighbors

SKNB KBN Topology without periodic LOC-AW TCP Transmission Control Protocol

TDM Time Division Multiplexing TLS Transport Layer Security

TNC Target Network Cost TOF Traffic Offload Function TOO Topology Optimizer Oracle TU Transaction User Level UAC User Agent Client UAS User Agent Server UDP User Datagram Protocol UGC User Generated Contents VoD Video on Demand VoIP Voice over Internet Protocol

(21)

1

Introduction

Various definitions of distributed systems exist in the literature. For our purposes, we borrow the definition given by the authors of [1]:

A distributed system is a collection of independent computers that appears to its users as a single coherent system.

The main point of a distributed system is that it consists of components (i.e., computers) that are autonomous and the collaboration among them is transparent to the users (be they people or programs), that think they are dealing with a single system.

The scope of this thesis is not to go into the details of the principles of a distributed systems but to describe recent distributed applications with the relating systems and the emerging issues.

1.1 Research Motivation

In the last decade, the worldwide development of the Internet saw tremendous growth, not only in users adoption and transferred data volume, but also in the diversity of content and applications available. Most likely none of the researchers commissioned by the United States government

(22)

in the 1960s to start to build a distributed computer network would have imagined such a big success. Nowadays, it is more than realistic to image a normal user session composed by browse the web, send/receive email, buy on-line, chat/call friends, watch video and use social networks. All at the same time.

In the previous years, most of the users associated the Internet with just the web browsing ap-plication; nowadays, even though it is still one of the more successful application, there are new emerging applications. A common feature of such applications is the distributed nature; the user accesses to resources that can be in any network location. As an example, an user could download a content from a centralized server, from one of a network of servers or from another user that shares it.

The nature of the content is also variable; it could be delay-tolerant content (for example a file in a file-sharing application), delay-sensitive (for example a video in a video delivery) service or some status information about the location of another user stored in a centralized server that manages the signaling in a IP telephony application.

In any case, the best-effort nature of the Internet does not match the requirements of these dis-tributed applications. For this reason, ad hoc solutions to provide a reliable infrastructure need to be proposed.

To provide this reliability, many different strategies can be used; for example, implementing pri-oritized classes of service that receive a privileged treatment while being transmitted over the Internet. Moreover, the communication model among the Internet points is depending on the ap-plication; it can be client-server, multiple-servers based or P2P.

In this work, we will present some challenging scenarios where a particular application and its respective communication model is described and an optimization criterion has to be fulfilled. The challenge depends on the application and the communication model.

(23)

1.2 Thesis Organization

In Chapter 2, we will cope with the problem of server overload in a client-server model. Such communication model is used in VoIP applications which are based on the SIP signaling protocol. In this scenario, the goal is to reduce the load on the server that manages the signaling of the VoIP calls. We will go into the details of such protocol and propose a feedback-based solution that is able to self-regulate the traffic at the server and to avoid the congestion.

Then, we will investigate alternative communication models that try to balance the load con-trary to the client-server model. An overview of these alternative models will be provided in Chapter 3. It describes the baseline mechanism of a P2P infrastructure and the baseline func-tionalities of a CDN, moreover it describes the features and the differences of two emerging application: the Video on Demand and the Live Streaming video delivery. This is a preparatory chapter that gives the reader the basic concepts to understand the problems/solutions proposed in the following Chapters.

In Chapter 4, we will present a P2P communication model. In a P2P model, all the nodes contribute to increasing the resources of the system by taking the being client and server roles at the same time. While this approach solves the load-related problems, it introduces different new issues. The P2P network shares a given content and a new peer interested in this content could retrieve it from any other peer. Unluckily, the P2P application has no information about the other peers´location and the network layer. For this reason the application can only make sub-optimal choices deciding to retrieve the content from an inconvenient peer (in terms of network distance) and potentially generating a great unbalance in the operator infrastructure.

Given the great success of P2P applications such as file-sharing, this problem has a very high pri-ority and the research community is interested in a way to control P2P applications and optimize

(24)

the traffic with network-awareness functionalities. In more details, the traffic generated by the P2P application needs to be routed through paths that take into account the network layer and the network proximity without wasting the network resources in suboptimal paths.

Resuming, in this scenario, the goal is to optimize the network resources consumed by the P2P application by increasing the traffic locality without affecting the satisfaction of the P2P users.

In Chapter 4, we will present our solution investigating a new emerging P2P application. Fol-lowing the success of file-sharing application, new real-time application are being developed on top of a P2P infrastructure. In particular, we will focus on live streaming application.

Another way to solve the overload problem of the classical client-server model is to use a CDN. In a CDN, content is outsourced in multiple locations and the clients can retrieve a copy from the most convenient location. In Chapter 5, the design of a CDN for delay-sensitive content retrieval will be presented and the challenges that this presents in terms of network resources will be described. As for the P2P network, content is replicated in multiple points of the network infrastructure (the P2P nodes in the P2P network, the replica servers in a CDN) and when a user wants to retrieve a content, some decision have to be taken in order to choose the best network location (given some criteria). We will focus on a Operator-owned CDN; this responds to a very recent trend: Operators want to deploy their own CDN instead of rely on third-party CDN. More-over, by using their existing network layer information, they can design the CDN functionalities with network-awareness to better utilize their resources.

As a natural consequence of the design solutions proposed in Chapter 5, we will then present a study on the prediction of the popularity of content. In Chapter 6, we will present a study based on data mining to predict the popularity of a given content. This has implication on the CDN design, for example which content to outsource and to which location.

(25)

1.3 Contributions

In summary, in this thesis we will present the challenges of three communication models (client-server, CDN, P2P) related to particular applications (VoIP, delay-sensitive content out-sourcing, live streaming). For each of the presented case studies, we will propose solutions to optimize the performance for the involved players (the network, the users).

1.3 Contributions

The main contributions of the thesis can be summarized as:

• Definition of a local mechanism of Overload Control in the server-to-server communication in a SIP system for VoIP application.

• Definition of a feedbased remote mechanism of Congestion Avoidance based on back-load prediction in a SIP system.

• Description of a P2P architecture for live streaming application and definition of an overlay optimization algorithm to increase the traffic locality.

• Description of the baseline functionalities of a CDN and design of a Network-Aware Operator-Owned CDN for delay-sentitive content distribution.

• Content Popularity Prediction based on Data Mining; description of the translation from the data space to the feature space and classification of UGC using Affinity Propagation Algorithm.

(26)

(27)

2

Use Case: Overload Control in

Server-to-Server SIP

Communications

2.1 Voice over IP: an Overview

The possibility to provide a telephony-like service on the Internet started to become reality in the early 2000. The telephony over IP has seen the first market development around 2004 when a mass-market VoIP services that utilize existing broadband Internet access has been introduced. In this system, subscribers place and receive telephone calls in much the same manner as they would via the PSTN. To make it doable, new technologies, methodologies, communication pro-tocols, and transmission techniques for the delivery of voice communications and multimedia sessions over IP networks needed to be defined. In general, VoIP is a family of solutions to pro-vide it. Among the protocols that define the solutions to propro-vide telephone-service over IP, the SIP signaling protocol has been widely used for controlling communication sessions. The typical

(28)

communication model provided by SIP is a client/server model where the users that want to use the telephone service have to register to the SIP server of their domain. The SIP server manages the creation/modification/termination of the voice sessions routing the voice session request from the domain of the caller to the domain of the callee. The SIP server of the domain of the caller communicate to the SIP server of the domain of the callee in a server-to-server signaling channel (it is the most general case; if both caller/callee belong to the same domain, the SIP server can establish the voice session directly). Once the voice session is set up, the voice channel flows directly among caller/callee and does not involve the SIP server anymore. A big issue of the SIP systems is the overload of the SIP servers (server and proxy are used as synonymous in the remainder of the chapter). The overload control mechanism built-in in the SIP server is based on generating rejection messages and could not prevent the server from collapsing due to congestion. In this scenario, the chapter presents an overload mechanism implemented in the SIP server com-bining a local and a remote solution. The local part of the overload control mechanism is based on the appropriate queuing structure and buffer management of the SIP proxy. The remote over-load control mechanism is based on feedback reports provided by the SIP proxy to the upstream neighbors. These reports permit the traffic regulation necessary to avoid the critical condition of overload. The main presented contributions are the design of key components of a remote con-trol mechanism, the proposal of a new approach for dynamic load estimation, and the use of a prediction technique in the remote control loop.

2.2 Session Initiation Protocol for VoIP Application

The Session Initiation Protocol (SIP) plays a key role in modern communication networks. It is an application layer signaling protocol for creating, modifying, and terminating multimedia sessions. Defined by the IETF , SIP is the base protocol for IMS defined by the 3rd Generation Partnership

(29)

2.2 Session Initiation Protocol for VoIP Application

Projects (3GPP and 3GPP2) , which represents today’s standard platform for providing multime-dia applications in Next Generation Networks (NGN) , allowing the merging of cellular and fixed telecommunications worlds. In this scenario, the experiences matured with signaling systems in circuit switched telephone networks [80] point out the need of analysing the performance under overload conditions of the network elements involved in the signaling procedures. It is known that under overload conditions of signaling nodes, the call throughput (goodput) and the network revenue drop to zero even when transport resources are available. In the SIP scenario, the over-load occurs when the SIP servers do not have sufficient resources to handle all the SIP messages they receive. In this situation, the throughput of a SIP server can drop significantly and the server can enter into a congestion collapse. In addition to the messages produced by other SIP elements, the congested SIP server also generates messages internally, e.g. to retransmit a request if a re-sponse has not been received in time. This aspect is particularly relevant since overload in one server, which will become significantly less responsive, can lead to overload in its neighbors. In this manner, overload can spread in a network of SIP servers and eventually bring down the entire network. The reasons triggering the overload in a SIP network can be various, e.g. a swarm of users trying to initiate a SIP call around the same time for voting in a TV show or in an emergency situation, or the synchronized registration of many users due to a recovery after, for example, a large power outage or a misconfiguration by the service provider [53].

Even though the SIP protocol provides a limited overload control mechanism through its 503 Service Unavailableresponse code, the SIP servers are still vulnerable to overload. The SIP-PING WG is discussing some Internet-drafts aimed at defining the requirements for the manage-ment of overload in SIP [53], and discussing the models, assumptions and design considerations for a SIP overload control [94]. To reduce the negative effects on system performance of an overloaded SIP server, the authors of [94] define a system model, identifying fundamental com-ponents of an explicit SIP overload control mechanism. The model defines two kinds of overload control approaches: local and remote. The local overload control is based on the idea that the

(30)

server can monitor its current resource usage and decide to reject messages, which cannot be pro-cessed without overusing the local resources. The fundamental assumption behind local overload control is that it is less resource consuming to reject messages than to process them. The local approaches do not require cooperation between servers and protocol modification. Furthermore, these approaches can be used in conjunction with other mechanisms. On the contrary, the re-mote overload control requires the cooperation among the servers. In particular, the SIP proxy should provide load feedback to its upstream neighbors. The type of information conveyed in the overload control feedback permits to differentiate the mechanisms. Reporting the classification discussed in [94], the overload control mechanisms can be classified in:

• Rate-based, the key idea is to limit the request rate at which an upstream element is allowed to forward traffic to the downstream neighbor;

• Loss-based, which enables a SIP server to ask an upstream neighbor to reduce the number of requests it would normally forward to this server by a communication of a loss percent-age;

• Window-based, the key idea is to allow an entity to transmit a certain number of messages before it needs to receive a confirmation for the messages in transit.

The overload control algorithm plays a key role in the design of these mechanisms. The control algorithm determines the amount of traffic the SIP proxy is able to elaborate; the upstream neigh-bors should adapt their transmissions towards the SIP proxy taking into account this information. Overload control algorithms have been studied to a large extent in other fields of telecom-munication networks. However, solutions taking into account the peculiarities of SIP systems are under study. In this scenario, the chapter proposes a solution for SIP overload control that accounts for the model reported in [94]. The proposed solution is based on the combination of a local and a remote mechanism. The local mechanism permits to reduce overload problems in

(31)

2.3 Overload Control in SIP Communication: Related Works

case of sudden load peaks with a time duration shorter than the reaction time of the remote control mechanism. The local overload mechanism takes into account the results of a previous analysis reported in [38]. Shortly, it is based on a buffer system, where the SIP messages are served in a First-In-First-Out (FIFO) discipline when the SIP server is in normal conditions. In case the SIP server is in a critical state, the non-INVITE SIP messages are processed with high priority with respect to INVITE ones.

The remote overload control constitutes the main contribution of the chapter. In particular, we propose a novel approach for dynamic load estimation that is based on the idea that taking into account both the SIP messages in the queuing structure and the SIP state machines permits to have a more precise estimation of the system load. The differences between the proposed approach and the one presented in [83] are discussed, and their impact on overload control mechanism is evaluated by simulation. Then, the chapter proposes a remote control algorithm based on the prediction of feedback values obtained by means of the Normalized Least Mean Square (NLMS) predictor, which provides a good trade-off between complexity, accuracy and responsiveness.

2.3 Overload Control in SIP Communication: Related Works

Many papers have been written on the general topic of overload control in telecommunication networks. Among these, we can note that the SIP overload problem has some similarities with situations studied for specific services, such as web [96], or for the nodes of signaling system (SS7). In particular, a first study was aimed at qualitatively evaluating the similarities and differ-ences between the ISUP/SS7 and SIP networks [33]. Furthermore, the authors state the need for overload control in SIP, without providing quantitative results on negative effects of overload on system performance or proposing specific approaches for overload handling in SIP networks.

Recently, the SIPPING WG of the IETF started the discussion of the causes of overload and the description of the current solutions proposed in the SIP protocol to overcome it [53]. This RFC

(32)

explains the weaknesses of mechanism, and some recent simulation studies, such as [46] and [38], clearly highlight that the SIP mechanism based on 503 Service Unavailable response code does not avoid the negative effects of server overload. In [92] the authors suggest some modifica-tions to this mechanism, but unsatisfactory results push in new direcmodifica-tions. A detailed simulation analysis of the behavior of SIP servers under overload is presented in [46]. Furthermore, the au-thors point out two possible approaches to face overload: a remote and a local control (defined also in [94]). Then they discuss some novel mechanisms and algorithms; they conclude that per-forming overload control locally at a server provides a simple remedy for light overload, but it is ineffective in handling higher amounts of load. In these conditions, they show the effectiveness of distributed overload control mechanisms. The authors of [38] analyse various local overload con-trol strategies obtained by combining queuing structures and service disciplines. The results show that in light overload conditions, serving with high priority the non-INVITE messages improves the SIP server performance. This solution outperforms the bang-bang local overload control mechanism proposed in [69] and seems to produce results not worse than those obtained using the local control algorithm proposed in [46]. This chapter continues the study presented in [38], adding the remote control algorithm to the local mechanism.

A new system model based on feedback defining different degrees of cooperation among sender and receiver is proposed in [94]. In [68] the authors address the issue of network level congestion control in SIP based telephony networks by applying a local and a remote overload control mechanism. The authors of [83] compare different feedback-based approaches, based on the estimation of the proxy queuing delay experimented by the SIP messages as a meaningful parameter for feedback calculation. Other approaches in literature are focused on analysing the number of messages in the proxy buffer, for example [65]. In [56], the authors suggest to utilize a feedback value based on the acceptance rate and the processor occupancy.

The main contributions of this chapter are the novel algorithm for proxy load estimation, based on active state machines in the proxy, and the utilization of a prediction algorithm for producing

(33)

2.4 SIP Communication: the Model

the feedback values. To the best of authors’ knowledge, there is no work that uses an approach based on state machines for proxy load estimation and a predictor for obtaining the feedback values.

2.4 SIP Communication: the Model

This section describes the model of a generic SIP element and the most important protocol fea-tures needed for a correct understanding of the SIP simulation model, implemented in ns-2, which has been used in the simulation analysis.

The model of a generic SIP element can be represented by a set of four logical levels that are responsible for the action of receiving, elaborating and transmitting a message, where each one manages the message independently from the others.

The lowest level is the Syntax and Encoding level (specified using an augmented Backus-Naur Form grammar, BNF , fully described in section 25 of [79]). The next level is the Transport level that defines how a SIP element (i.e. UAC , UAS or SIP Server) sends requests/responses and receives responses/requests over the network.

The SIP protocol is independent from the transport layer and can run over TCP/UDP/TLS , thus it is developed mostly on UDP that allows faster setup phase.

The third level is the Transaction level; such level handles SIP message retransmissions, manages SIP timers, and matches responses to requests. The Transaction level has a client component (Client Transaction) and a server component (Server Transaction), each represented by a finite state machine. The Client Transaction sends the request, and the Server Transaction sends the response as defined in section 17 of [79]. Referring to a call between Alice and Bob, associated respectively to Atlanta and Biloxy proxies, Figure 2.1 shows the relationship between server and client transaction in SIP elements involved in the call.

(34)

Figure 2.1: Server/Client Transactions in SIP Elements

The fourth level is the Transaction User (TU) level; it can be metaphorically linked to the con-science of the person who decides when and whether to submit a request. For example, the dialing of the phone address required by the SIP based soft-phone is translated by the TU in a Client Transaction; furthermore during this operation, the TU also determines the IP address, the transport protocol, and the port number to use for sending the INVITE message.

All SIP elements, i.e. UAs and SIP proxy, contain a different TU that distinguishes them from each other.

2.5 SIP Proxy: the Logical Model

In order to simulate and test the effectiveness of different SIP overload control strategies, the Overload Control Proxy (OCProxy) model has been developed in ns-2 creating a new Agent class, the Agent/OCProxy. The logical architecture of the developed class is described in Figure 2.2, taking into account the logical model of SIP briefly described in Section 2.4. The Syntax and Encodinglevel is not implemented, while the Transport level implements only functions similar to UDP class. Main development activities have been focused on the TU and Transaction levels, taking into account that the OCProxy tasks are:

(35)

2.5 SIP Proxy: the Logical Model

• processing INVITE message, locating the caller and forwarding the request message to the next hop;

• generating the 100Trying;

• forwarding the successive messages associated to the dialog modifying the header (i.e. the VIA header field).

These actions involve the TU and the Transaction levels as depicted in Figure 2.2.

When a message arrives at the OCProxy, the Transport level transfers it to the TU one. The message is then enqueued by means of the recv method that manages the queuing system and activates a queue monitor for evaluating the filling status of the buffer as described in Section 2.6.1. The message to be processed is then transferred to the handle method.

The handle method analyses the message content and executes the appropriate actions, such as updating, creating or terminating the associated SIP state machine or sending the ACK message. The handle method represents the interface between the TU and the Transaction level (dotted line in Figure 2.2 indicates the information exchange between these levels, needed to manage the SIP state machines).

This information is obtained by the analysis of the SIP headers and identifies the transaction. By identifying a transaction (information for such scope are obtained by the analysis of the SIP header), it is possible to verify if the message belongs to an existing state machine or not. If the state machine does not exist, the message triggers the creation of a new one (client or server state machine depending on the request/response message type). On the other hand, if the state machine is already instantiated, the message triggers the appropriate transition.

The responses triggered by the server state machine directly interact with the Transport level through the send method. The responses triggered by the client state machine are passed to the TU for packet modification (i.e. add/remove header field, e.g. Via, modify message length) before forwarding to the send method (because, in a SIP proxy, the responses received by the client state

(36)

Figure 2.2: OCProxy Model Implemented in ns-2

machinehave to be forwarded to the next hop, see Figure 2.1).

When the proxy receives an INVITE, it generates a server state machine for the creation of the appropriate response and a client state machine to forward the request to the next hop. To this aim, the received INVITE is transferred from the Transaction level to the TU for packet modification, before forwarding it to the send method for transmission towards the next hop.

If the received message is a successful final response associated to INVITE, then the associated server state machinehas a transition to the state terminated; this event updates the counter at the Transaction level. The counter returns the number of INVITE state machines successfully terminated, which, as will be shown in Section 2.7, is used for session service rate estimation. The arrow between the handle method and the send method in the TU level shows the ACK path. The ACK does not create a transaction; for this reason it is received by the recv method and forwarded to the Transport level without involving the Transaction level.

Last but not least, both the client state machine and the server state machine could produce message retransmission, due to SIP timers expiration. In this case, the message retransmission is triggered at the Transaction level and the retransmitted packets are passed directly to the send method, without invoking the TU level (see lastpktSent path in Figure 2.2).

(37)

2.6 Mechanism for Local Overload Control

In this model, two methods need specific details: the recv and the handle method (flowcharts about them are shown in Figure 2.4 and 2.5 respectively). The first one is used for modeling different queuing strategies, in terms of service discipline and buffer management. Such method influences the strategies for local overload control mechanism.

The handle method simulates the message dequeuing and processing. It extracts the fields from the message header in order to identify the transaction making possible to check whether the message belongs to an existing transaction. If a state in the Transaction level already exists, the state machine and the associated counter are updated, otherwise, the message is associated to a new request. In this case, the handle method triggers a new server state machine (except the special case where the message is an ACK that is processed without creating a state machine). The OCProxy model handles different request types in different ways. The REGISTER request is processed sending back the appropriate response and triggering a server state machine. Other request types (e.g., INVITE) are forwarded towards the next hop after triggering a server state machine. It is to be noted that forwarding a request implies the creation of a new client state machine if the proxy is acting in a state f ul operation mode. The client state machine is then updated when the proxy receives a response and forwards it towards the next hop.

2.6 Mechanism for Local Overload Control

To locally detect a situation of congestion on a SIP proxy, we monitor the status of the queue at the TU level. Designing a suitable queuing strategy, we can prevent the congestion collapse of the proxy. The advantage of a local overload control mechanism is that it does not require any cooperation with proxy neighbors and it does not require protocol modification.

The idea of local overload control is to determine when a SIP proxy reaches a high load and to start reacting with as little effort as possible. To study the impact of the structure of queuing

(38)

Figure 2.3: Local Protection: Queuing Structure

system on SIP proxy performance, we have set up two different models: a single buffer and a two buffer structure. A logical example is given in Figure 2.3.

We have carried out simulation with different service disciplines that influence the local over-load mechanism.

First of all we have considered a single buffer structure characterized by a simple FIFO service discipline with no logic for local overload control mechanism. In a second set of simulation, we have enhanced the FIFO service disciplines with logic or local overload control mechanism. We have used the FIFO discipline when the proxy is not in overload state, otherwise the buffer is served using a priority discipline, assigning the highest priority to the non-INVITE messages; we describe the mechanism based on the "Combined FIFO and Priority" (CFP) service discipline. This service discipline is maintained until the proxy comes out from the overload condition, then

(39)

2.6 Mechanism for Local Overload Control

the proxy returns to adopt the FIFO discipline.

The CFP mechanism is based on a buffer system composed by two logical buffers for SIP mes-sages: one is reserved to INVITE messages and the other to non-INVITE ones. The service discipline is chosen according to the state of the proxy. In particular, when the system is not in overload state, the two logical buffers are served using a FIFO discipline, otherwise the two logi-cal buffers are served using a priority discipline, assigning the highest priority to the non-INVITE messages. This service discipline is maintained until the system exits the overload condition, re-turning to adopt the FIFO discipline. In order to highlight the rationale behind this strategy, we point out that INVITE messages refer generally to new sessions and non-INVITE messages to transactions or sessions that have previously been accepted into the system. The use of the CFP mechanism implies that in overload condition the finalization of sessions previously accepted by the system has higher priority than the admission of new ones.

Then we have considered the two buffer structure. We have implemented the local overload con-trol mechanism by serving the two buffers in Round Robin when the proxy is not in overload state, otherwise the proxy starts to serve the non-INVITE buffer. This service discipline is main-tained until the proxy comes out from the overload condition, then the proxy returns to adopt the Round Robin discipline.

The rationale behind the proposed strategies for local overload control is that INVITE messages generally refer to new sessions and non-INVITE messages to transactions or sessions that have previously been accepted into the system. Therefore, proposed strategy encourages the ending of sessions previously accepted by the system rather than accepting new ones.

To detect the overload condition two thresholds, T HHIGHand T HLOW, are used. The proxy enters

the overload state when its queue dimension is higher than T HHIGH, and exits from this state

when its queue dimension is smaller than T HLOW.

To detect the overload condition we have set two thresholds, T HHIGHand T HLOW, on the INVITE

(40)

the better results by setting T HHIGHand T HLOW as 80% and 60% of dimMAX respectively, where

dimMAXis the size of the INVITE buffer.

The proxy comes in the overload state when the number of INVITEs in the dedicated buffer is higher than T HHIGH, then to exit from this state the buffer occupancy must be under the T HLOW.

Having an higher watermarks imply slow react to overload while having a lower watermarks imply reject INVITE that could be served by the proxy; increasing beyond the 20% the distance between watermarks imply extend the rejection phase risking the proxy underutilization. These reasons explains our pick, confirmed by simulation analysis omitted for sake of brevity.

In the case of single buffer structure, the mechanisms managing the overload condition is similar to the two buffer structure, with the obvious difference that the thresholds and the parameter to consider refer to all queued SIP messages, since the system does not distinguish INVITE from non-INVITEmessages.

In order to set dimMAX , we consider that during a session the SIP proxy manages seven messages: one INVITE and six non-INVITE. Hence the size of the two buffers are set accordingly to this ratio, i.e. 1 to 6. The simulation study for the diverse queuing structures is carried out assuming the same overall buffer space for the queuing system, independently if it has one or two buffers. The overall buffer space is indicated as B. Then dimMAX is equal to 1/7 of B and represents the size of buffer reserved for INVITE messages, both in case of Round Robin or "Combined FIFO and Priority" service discipline. Obviously, in case of single buffer dimMAX is set equal to B. The detailed description of the simulation results regarding the Local overload control mechanism is reported in Section 2.9. The CPF strategy is the most performing; a detailed description of the ns-2 implementation of such strategy is provided in Section 2.6.1.

2.6.1 NS-2 Model of the CFP Overload Control Mechanism

The results of previous sections have shown that the best local strategy is the CFP. The ns-2 model of CFP has been implemented in the recv method. In particular, when a packet arrives at

(41)

2.7 Remote Overload Control Mechanism

the queue, two counters are updated (INV IT Earr and nnINV IT Earr) according to the message type. These statistics are useful for the estimations presented in Section 2.7. In the implemented model, the filling status of the buffer is checked, one of the four possible conditions is detected and the appropriate actions are derived:

• the queue dimension is higher than the buffer limit dimMAX → action 0;

• the queue dimension exceeds the maximum threshold value T HHIGHfor overload detection

→ action 1;

• the queue dimension is below the threshold T HLOW for end-of-congestion detection →

action 2;

• the queue dimension is between T HLOW and T HHIGH.

In this last case, two situations may happen:

1. The higher threshold T HHIGHhas been exceeded once → action 1;

2. The higher threshold T HHIGHhas not been exceeded yet → action 2;

Action 0 causes the message dropping; if it is an INVITE, the INV IT Edrop counter is in-creased else the nnINV IT Edrop counter is inin-creased. Action 2 executes the enqueuing of any kind of message while action 1 influences the local overload control mechanism. In the CFP local overload strategy, the action 1 is to assign highest priority to non-INVITE messages.

2.7 Remote Overload Control Mechanism

The remote overload control mechanism is based on explicit feedback communication between the receiving entity and its upstream neighbors to regulate input traffic and avoid congestion

(42)

(43)

(44)

collapse. A comparison of some algorithms implementing the rate-based, loss-based and window-based mechanisms is reported in [83]. The comparison results point out the rate-window-based mechanism as the most interesting; hence, we have focused our attention on it. In a remote control mechanism, the main elements to design are:

• the feedback parameter estimation, i.e., the algorithm used on the SIP proxy to calculate the feedback value;

• the feedback communication channel, i.e., the channel used by the SIP proxy to communi-cate to the upstream entities the feedback value;

• the feedback enforcement mechanism, i.e., the regulation mechanism used by the upstream entity to enforce feedback control, such as e.g., percentage throttle, leaky bucket, and token bucket.

2.7.1 The Feedback Parameter Estimation

In the proposed remote overload control mechanism, the feedback value is derived by the load estimated at the receiving SIP proxy; hence the load estimation algorithm plays a key role. As a consequence, this section describes a novel method for dynamic proxy load estimation and com-pares it with the approach presented in [83]. We refer to our method as Transaction approach because it is based on information at Transaction level while we refer to the other method as TU approachbecause it is based on information at TU level. The proxy load estimation derives from both the session service rate and the backload, both used for estimating the proxy queuing delay. This parameter represents the amount of time that the proxy needs to process the backload, and it is useful for calculating the allowed resources for new requests.

(45)

2.7.1.1 Backload Estimation

The backload takes into account the number of sessions waiting for service, Nwait, and the number

of sessions accepted by the proxy but not terminated yet, Nproc. Both in the TU approach and

the Transaction approach, Nwaitis the number of INVITE messages at the TU level. The first

difference between the two approaches is the estimation of Nproc.

• Transaction approach: Nproc is obtained by counting the number of active state

ma-chines in the proxy at the Transaction level;

• TU approach: the authors of [83] propose an estimation of Nproc taking into account the

number of non-INVITE messages (Nnninv) in the queue and the average number of message

per session (Lsess), i.e.

Nproc=

Nnninv

Lsess− 1

(2.1)

2.7.1.2 Session Service Rate Estimation

The second difference between the Transaction approach and the TU approach involves the session service rate estimation.

• Transaction approach: at the Transaction level, the session service rate is estimated as the number of INVITE (each time interval Tm) that has a transition to the state Terminated

in the INVITE server state machine. This event corresponds to the reception of a 200OK message from the Transport level. The basic idea of this approach is that the number of INVITE state machines in the Terminated state is equivalent to the number of served sessions.

(46)

• TU approach: the authors in [83] propose the following relation for calculating the session service rate µs= Nacc inv Tm (2.2) where N_invaccis the number of accepted INVITE messages in the time interval Tm. The basic

idea is that under normal working conditions, the actual session acceptance rate is roughly equal to the session service rate. Therefore, the session service rate can be estimated based only on the session start message. When traffic increases, the time to serve an INVITE increases as well and it could lead to INVITE retransmissions. The retransmissions fill the proxy queue at the TU level and are counted, if not dropped, in the overall estimation of the session service rate even if they refer to sessions already accepted. Using the Transaction approach, retransmissions are absorbed by the already existing state machines and do not increase the session service rate estimation. This is the reason why TU approach lead to overestimate the session service rate when traffic increases.

2.7.1.3 Proxy Queuing Delay Estimation

Taking into account the analysis of [83], a relevant parameter that could be used for estimating the proxy load is the proxy queuing delay (dq), defined as Nsess/µswhere Nsessis the overall backload

obtained by Nwait+ Nprocand µs is the current estimated session service rate of the proxy. The

definition implies that the overall proxy queuing delay is obtained adding the delay to process the sessions in the proxy queue (Nwait/µs) and the delay to process the sessions already accepted by

the proxy (Nproc/µs). Comparing the mean value Nproc/µsobtained by the two approaches (TU and

Transaction), where the related parameters are denoted using as apex TU and Tr respectively, the following relations are true (see Figures 2.14(a) and 2.14(b)):

(47)

2.7 Remote Overload Control Mechanism µTU_s > µTr_s (2.4) Hence, NTU_proc µTU < NTr_proc µTr (2.5)

From this analysis it is evident that the TU approach leads to underestimate the delay needed to terminate sessions accepted by the proxy. Taking into account the other factor

Nwait

µTU <

Nwait

µTr (2.6)

so in the overall calculation, always the following relation is true d_qTU< d_qTr. It means that the TU approachleads to underestimate the overall proxy backload with a slower reaction to traffic increase.

2.7.2 Feedback Calculation

As feedback value, at the time t0= nTmwe consider the available resources of the proxy taking

into account the sessions already in the system at t0. At this time, the available resources in terms of calls per second, denoted as η(nTm), can be calculated as

η(nTm) = µs(nTm) −

µs(nTm) · [dq(nTm) − Dq]

Tm

(2.7) The values of µs(nTm) and dq(nTm) vary depending on the utilized approach. µs(nTm) is the

estimated service rate and dq(nTm) is the estimated server queuing delay. Dqis the allowed

mes-sage queuing delay; we use the suggested value of 200ms obtained by [83]. We use as feedback the value η(nTm) normalized to nominal µsipto obtain a value ∈ [0,1]; indicating with Pbthe

blocking probability, the feedback value represents (1 − P_b). The upstream neighbors will reg-ulate the offered load in the time period (nTm, (n + 1)Tm] accordingly to the information on the

(48)

proxy’s available resources at the time nTm. We activate the remote control mechanism when the

estimated session service rate is greater or equal to the 80% of nominal session service rate µsip.

When the estimated session service rate µs is lower than the 80% of µsip, the feedback value is

1. It means that the traffic shaping at the sources is deactivated. So the communicated feedback value facc(n · Tm) is:

facc(nTm) =    1 if µs< 0.8 · µsip η(nTm) NSE· µsip otherwise (2.8)

NSE is the number of upstream neighbors of the proxy. The threshold value 0.8 · µsiphas been

set to avoid the event of blocking a call when the proxy resources are not fully utilized. Taking into account the relations (2.3)-(2.5), the following relation is true:

f_accTU> f_accTr (2.9)

It means that, using the TU approach, the proxy communicates an amount of available re-sources greater than that obtained using the Transaction approach. Hence, the probability to refuse a call is lower and the reaction to load increase in slower.

2.7.3 Prediction-Based Overload Control Mechanism

The main contribution of the chapter is the introduction of a prediction mechanism in the proxy. We start our analysis taking into account the main features in terms of complexity, accuracy and responsiveness that the prediction algorithm should provide. We utilize the results of [37] that proposes a comparative analysis among prediction algorithms, used for developing a dynamic and flexible prediction based resource allocation strategy. Among the different prediction algorithms compared in [37], the Normalized Least Mean Square (NLMS) predictor is the one providing the best trade-off between complexity, accuracy and responsiveness.

(49)

The general problem of prediction can be stated as follows: given a set of observations of a stochastic process x(n), generate an estimation ˆx(n + k) of the value x(n + k) that the process xwill assume k steps ahead. In other words, given a vector of p observations, x = [x(n), x(n − 1), · · · x(n − p + 1)], the predicted value ˆxis obtained by:

ˆ

x= ϒ(x) (2.10)

where the function ϒ is called predictor.

Different classes of predictors have been studied; however, taking into account the constraint on the complexity, the linear prediction class is the best suited for our aim. A linear prediction occurs whenever the function ϒ(x) is linear. In other words, the problem is to determine the impulse response h(n) of the linear filter h such that:

ˆ x(n + k) = x(n) ⊗ h(n) = p−1

∑

i=0 h(i) x(n − i) (2.11)

The filters coefficients can be determined according to arbitrary optimality criteria. One of the most famous and widely adopted prediction algorithm is the so-called Linear Minimum Mean Square Error (LMMSE)predictor, in which the values h(n) are derived by minimizing the Mean Square Error of prediction:

Eε2(n) = E h

(x(n + k) − ˆx(n + k))2i (2.12) The problem of this predictor is that the derivation of the LMMSE filter requires the knowl-edge of at least p values of the autocorrelation function of the stochastic process x(n) and the inversion of a p × p matrix. These facts make LMMSE unsuitable for being used as on-line tech-nique for predicting. To solve this problem, we consider the NLMS algorithm, which is based on an adaptive approach. It does not require prior knowledge of the autocorrelation structure of the stochastic sequence [43].

(50)

Figure 2.6: NLMS Algorithm Scheme

The algorithm scheme is shown in Fig. 2.6.

The filter coefficients are time varying and are tuned on the basis of the feedback information carried by the error ε(n). In the following, we denote the vector of filter coefficients at time n with h_n. The values of h adapt dynamically in order to decrease the Mean Square Error. Notice that ε(n) = x(n + k) − ˆx(n + k) and xn= [x(n), x(n − 1), · · · x(n − p + 1)]. The NLMS algorithm

operates as follows:

1. initialize the coefficients h₀;

2. for each new data, update the filter h(n) according to the recursive equation.

h_n+1= h_n+ αε(n)xn kxnk2

(2.13)

where kxnk2= xnxTn and α is a constant called step size.

(51)

Notice that, at time n, the values x(n + k), hence ε(n), are not known. Therefore, the value ε(n − k) is used, instead, and the one-step NLMS predictor update equation becomes:

h_n+1= h_n+ αε(n − 1)xn−1

kx_n−1k2 (2.14)

The computational complexity of a p−order NLMS algorithm is that of 2p + 1 multiplications and p + 1 additions.

2.7.3.1 Implementation of the Prediction-Based Overload Control Mechanism

The block diagram representing the implementation of the proposed prediction-based overload control mechanism is reported in Figure 2.7. The block diagram refers to its implementation in the ns-2 OCProxy simulation model, but its extension in an actual proxy is quite obvious. The NMLS predictor needs the configuration of two parameters: the order p and the step size α. The order p has been chosen equal to 20, since it produced a good performance during the simulation analysis. In the case of the α, it is relevant to note that one of the main advantage of using NLMS is that it is less sensitive to the step size with respect to other linear predictor. In our scenario, we choose the step value of 0.8 as trade-off between fast convergence and responsiveness to input change. We run different simulations to tune this parameter and we observe that the step size affects the feedback as a lowpass filter whose time constant is inversely proportional to it. For small value of α (i.e. α = 0.1) we observe that the prediction function slowly converges and is not able to follow sudden load increase. Thus, we obtain an ineffective prediction that means that the system performance are not improved by the use of the remote overload control. For value of α greater than 0.5, the prediction function is not sensitive to step size and results in a faster convergence of the algorithm and in a quicker response to load changes.

(52)

describe Figure 2.7, which refers to the adoption of the Transaction approach.

In particular, the measurement block registers the amount of INVITE in the queue at the TU level to obtain Nwait, and the session service rate, and the number of active state machines Nproc

in the Transaction level during the time interval [(n − 1)Tm, nTm]. Based on these values, the

measurement block calculates the available resource η(nTm) of the proxy. Then, the prediction

block returns the available proxy’s resources at the time (n + 1)Tmthat is a function of measured

proxy’s resources at time nTm, i.e. η(n + 1)Tm= f [η(nTm)]). Using the NMLS prediction scheme

of order p = 20, η[(n + 1)Tm] is calculated according to the NMLS predictor. We point out that the

Transaction approachrepresents the simplest prediction mechanisms that can be used in the structure shown in Figure 2.7. Indeed, indicating with ηe(nTm) the estimated resources available

at the proxy, calculated using (2.7), at the time nTmand ηp[(n + 1)Tm] the predicted value of η

at the time [(n + 1)Tm], the Transaction approach implies ηp[(n + 1)Tm] = ηe(nTm), i.e. the

utilization of a simple zero order geometric predictor as controller. The resource allocator block divides the available resources among the upstream neighbors and normalizes to the maximum session service rate to obtain the feedback value facc[(n + 1) · Tm] as a function of ηp[(n + 1)Tm].

This feedback value is used by the upstream neighbors to regulate their offered load in the time interval (nTm, (n + 1)Tm].

2.7.4 Feedback Communication Channel

As for the feedback communication channel, we refer to [93] as a starting point. It describes a mechanism to convey overload feedback from the receiving to the sending SIP entity and sug-gests to utilize an in-band channel. An in-band channel may piggyback the feedback information through some new header field of existing SIP messages. The authors of [93] define a new pa-rameter for the SIP Via header.

A SIP proxy can provide overload control feedback to its upstream neighbors by adding the new parameter, called the ’oc’ parameter to the topmost Via header field of a SIP response. Since

(53)

Figure 2.7: Prediction-Based Controller (with Transaction Approach)

the topmost Via header of a response will be removed by an upstream neighbor after processing it, overload control feedback contained in the ‘oc’ parameter will not travel beyond the next SIP server. A Via header parameter therefore provides hop-by-hop semantics for overload control feedback even if the next hop neighbor does not support this specification

To visualize how this parameter gets inserted in a SIP message, Figure 2.8 is a signaling message from U(1095) to U(905); U(1095) belongs to the domain of the OCProxy, which adds its feedback value in the ‘oc’ parameter in the Via header containing the IP address of the next hop (with IP address 10.0.0.1). Figure 2.9 instead shows how the ‘oc’ parameter gets stripped at intermediate hops by showing two elements, B and C, that support remote overload control mechanism by inserting in the Topmost of Via header its own value of feedback.

(54)

SIP/2.0 100 Trying To: <sip:U(905)@proxy(9).com> From: <sip:U(1095)@proxy(10).com>;tag=13617 CallId: 6809 CSeq: 66 INVITE Contact: <sip:U(905)@10.9.0.5>

Via: 10.0.0.1;branch=z9hG4bK30925; oc: 0.171659;

Figure 2.8: SIP Message: 100Trying

(55)

2.8 Simulation Scenario

2.7.5 Feedback Enforcement Mechanism

As feedback enforcement algorithm, we use the percentage-throttle mechanism. This mechanism is implemented by the upstream neighbors of the proxy to make sure the actual output load is conform to the regulated load value. To this aim, each sender generates a random value (between 0 and 1) and a call is blocked if the generated random value is greater than the feedback value.

2.8 Simulation Scenario

The simulation scenario is reported in Figure 2.10. The scenario is composed by (n + 1) domains, each one having a SIP proxy and a router. Each one of the first n domains contains m SIP User Agents (UAs), while the last one (denoted as bottleneck domain, BD) has n · m SIP UAs. The routers of the first n domains are directly connected with the router of the BD. Each UA belonging to the first n domains is involved in sessions with a particular UA of the BD and the roles of caller and called are inverted at the end of each SIP session; n is the number of domain simultaneously involved in SIP sessions. Hence, the SIP proxy of BD is the only bottleneck of the system and we will identify it as BD proxy. To focus our analysis on server-to-server overload problem, we assume edge proxy belonging to the n domains with an infinite capacity. In order to have only the BD proxy as bottleneck, the bandwidth of each link of the simulation scenario has been set to 100 Mbps, with a latency of 10 ms.

To estimate the load, λ, offered to the BD proxy, it is needed to take into account that each session involves the exchange of 7 SIP messages. Hence, the average SIP message arrival rate can be estimated as suggested in [69] with the following equation:

λ = 7 · m · n Ts+ Ti

(56)

(57)

2.8 Simulation Scenario

where Tsrepresents the session duration and it is modeled with an exponential random variable

with a mean value equal to 50 s, and Tiis the time interval between the receiving of the 200OK

response associated to the BYE request and the transmission of the INVITE request starting the set up phase of the successive session. Tiis modeled using an exponential random variable with a

mean value equal to 10 s. Details about Tsand Tiand on UA behavior are shown in Figure 2.11.

To be noted that equation (2.15) is an approximation of the actual offered load since in such equation the call set up delay (CSD) , defined as the difference between the instant when the caller sends the INVITE starting the session set up procedure and the instant when the callee receives the ACK concluding this procedure (see Figure 2.11), is not taken into account. This because the CSD is an unpredictable value that depends on system conditions and the approximation is accurate when the CSD is much lower than the duration of (Ts+ Ti) (i.e., in the vast majority of

the cases).

To evaluate the error introduced by the equation (2.15), we run simulations in the worst case scenario considered in the simulation analysis of the overload control mechanisms, i.e. with a normalized traffic load equal to 2. In this condition we measured the actual offered load, denoted as λa. After many simulation runs we observed that in the worst case the following relation holds

λa' 0.856 · λ (2.16)

Hence, we can conclude that using a well designed remote overload control mechanism, we can neglect the impact of the time needed to set up the call on the relation 2.15. It’s worth mentioning that in the worst case, we observe that only about the 1.7% of session set up attempts experiment the expiration of TimerB(details on SIP Timers can be found in [79]). Furthermore,

when TimerB expires, the User Agent starts with a new session after Ti seconds and this new

(58)