Facolt`
a di Ingegneria
Laurea Specialistica in Ingegneria Informatica
Design and validation of a
methodology for distributed
relay service for NAT traversal
in a peer-to-peer VoIP network
Relatori:
Candidato:
Prof. Luigi Rizzo
Ludovico Manfredi Cavedon
Prof. Paolo Ancilotti
Prof. Fulvio Risso
Contents
Introduction 11
1 Voice Over IP (VoIP) 14
1.1 Advantages of VoIP . . . 14
1.2 Issues of VoIP . . . 15
1.3 Network performance requirements . . . 15
1.3.1 Delay . . . 16
1.3.2 Jitter . . . 17
1.3.3 Bandwidth . . . 17
1.3.4 Packet Loss . . . 18
1.4 Signaling protocols . . . 18
1.5 Media transport protocols . . . 19
1.5.1 RTP . . . 19
1.5.2 RTCP . . . 20
2 Session Initiation Protocol (SIP) 21 2.1 Purpose of SIP . . . 22 2.2 Transport Protocol . . . 23 2.3 SIP resources . . . 24 2.3.1 Address Of Record . . . 25 2.4 SIP architecture . . . 25 2.4.1 SIP entities . . . 25 2.5 SIP messages . . . 28 2.5.1 Requests . . . 28 2.5.2 Responses . . . 29
2.5.3 Header fields . . . 29 2.6 Message routing . . . 29 2.6.1 Transactions . . . 29 2.6.2 Dialogs . . . 30 2.6.3 Direct connectivity . . . 31 2.6.4 Record-Routing . . . 33 2.7 SIP requests . . . 33 2.7.1 REGISTER . . . 33
2.7.2 INVITE, ACK and BYE . . . 34
2.7.3 SUBSCRIBE and NOTIFY . . . 35
2.8 Authentication . . . 36
2.9 SIP issues . . . 38
2.9.1 Dialog usages . . . 38
2.9.2 Multi-homed hosts . . . 39
2.9.3 NAT support . . . 40
2.10 SIP and VoIP . . . 40
2.10.1 SDP . . . 40 2.10.2 Session Negotiation . . . 43 2.10.3 ANAT . . . 44 3 Peer-to-peer Networking 45 3.1 VoIP and P2P . . . 46 3.1.1 Skype . . . 47
3.2 Centralized peer-to-peer networks . . . 47
3.3 Decentralized peer-to-peer networks . . . 48
3.3.1 Unstructured peer-to-peer networks . . . 48
3.3.2 Structured peer-to-peer networks and Distributed Hash Tables (DHTs) . . . 50
3.4 DHT algorithms . . . 53
3.4.1 Chord: ring topology . . . 53
3.4.2 Pastry: tree and ring topology . . . 56
3.4.3 Tapestry: tree topology . . . 58
CONTENTS
3.4.5 CAN: hypercube topology . . . 59
3.4.6 Kelips . . . 60
3.4.7 Comparison of DHT algorithms . . . 60
3.5 Hybrid approach: BitTorrent . . . 63
3.6 Bootstrap . . . 64
3.7 P2P issues . . . 65
4 Network Address Translation (NAT) 66 4.1 NAT Behavior . . . 69
4.1.1 Mapping . . . 69
4.1.2 Filtering . . . 70
4.1.3 Hairpinning support . . . 72
4.1.4 Other NAT behaviors . . . 73
4.1.5 Legacy NAT classification . . . 74
4.2 NAT Traversal . . . 75
4.2.1 Relaying . . . 75
4.2.2 Connection reversal . . . 76
4.2.3 UDP hole punching . . . 76
4.2.4 UDP hole punching with Symmetric NAT . . . 80
4.2.5 TCP hole punching . . . 81
4.2.6 NAT keep-alive . . . 81
4.3 NAT Traversal with SIP . . . 82
4.3.1 Symmetric Response Routing . . . 82
4.3.2 SIP Outbound . . . 84
4.4 STUN . . . 84
4.4.1 STUN messages . . . 85
4.4.2 Message structure . . . 87
4.4.3 STUN and SIP . . . 88
4.4.4 Limitations of STUN . . . 89
4.5 STUN Relay Usage . . . 89
4.5.1 Messages . . . 89
4.5.2 Allocate Requests . . . 91
4.6 ICE . . . 93
4.6.1 Transport Addresses . . . 94
4.6.2 Creating the offer . . . 95
4.6.3 Creating the answer . . . 95
4.6.4 The candidate pairs . . . 96
4.6.5 Connectivity checks . . . 97
4.7 NAT & P2P . . . 98
5 P2P-SIP 99 5.1 Distributed Location Service . . . 99
5.1.1 SIP as protocol for DHT maintenance . . . 101
5.2 Message routing . . . 102
5.3 NAT and P2P-SIP . . . 102
5.4 Related work . . . 103
5.4.1 SOSIMPLE . . . 103
5.4.2 SIPpeer . . . 104
5.4.3 IETF . . . 104
5.5 Pending issues . . . 106
5.5.1 Direct connectivity for signaling . . . 106
5.5.2 Ensuring reachability of peers behind NAT . . . 107
5.5.3 Location of rendez-vous and relay peers . . . 107
6 ALEX 108 6.1 ALEX role in dual-stack IPv4/IPv6 environment . . . 109
6.2 ALEX procedures . . . 111
6.2.1 ALEX-Item format . . . 113
6.2.2 Creation of the validation tables . . . 115
6.2.3 Address validation phase . . . 116
6.2.4 Backward compatibility . . . 117
6.2.5 Connection caching . . . 117
6.2.6 Using ALEX in non-INVITE dialogs . . . 118
6.3 ALEX for NAT traversal . . . 118
CONTENTS
6.3.2 ALEX procedures . . . 121
6.3.3 Connection caching . . . 121
7 Distributed Relay Service 123 7.1 Determination of the outbound peer . . . 124
7.2 Protocol overview . . . 124
7.3 Protocol specification . . . 125
7.3.1 Relay addresses advertisement . . . 125
7.3.2 Relay service subscription . . . 126
7.3.3 Relaying for media traffic . . . 129
7.3.4 Subscribing to new peers . . . 129
7.3.5 Active fetch . . . 130
7.3.6 Gathering of addresses . . . 130
7.4 Usage with ALEX . . . 131
7.5 Strengths and costs . . . 132
7.6 Efficiency of the Distributed Relay Service . . . 133
7.6.1 NAT diffusion statistics . . . 134
7.6.2 Peer lifetime statistics . . . 137
7.6.3 File-sharing and VoIP P2P statistics . . . 138
7.6.4 Selection of peers for the relay service overlay . . . 139
7.6.5 Load on relaying peers . . . 141
7.7 Simulation of the evolution of the unstructured network graph 144 7.7.1 Simulation environment . . . 144
7.7.2 Simulation objectives . . . 146
7.7.3 Clustering coefficient . . . 146
7.7.4 Node degree . . . 150
7.7.5 Policies . . . 150
7.7.6 Initial conditions of simulation . . . 151
7.7.7 Protocol parameters evaluation . . . 154
7.7.8 Conclusions on simulation results . . . 160
8 Conclusions and future work 163 8.1 Future work . . . 165
A Implementation analysis 166
A.1 OpenWengo . . . 166
A.1.1 PhApi . . . 167
A.1.2 Development pattern . . . 167
A.1.3 Threading and signals . . . 169
A.2 SIPDHT . . . 170
A.3 Work on WengoPhone . . . 171
A.3.1 Bugfixing . . . 171
A.3.2 Generic SIP account . . . 172
A.3.3 Integration with SIPDHT . . . 174
A.4 ALEX on Wengophone . . . 175
A.5 Future development . . . 176
B Relevant Statistics 177 B.1 Exponential distribution . . . 177
B.1.1 Memorylessness property . . . 178
B.2 Power-law: Pareto distribution . . . 178
B.3 Weibull Distribution . . . 179
B.3.1 Modified Weibull distribution . . . 179
Acknowledgments 181
List of Tables
1.1 Speech codecs . . . 18
2.1 SIP methods . . . 28
2.2 SIP responses . . . 29
2.3 Major SIP headers . . . 30
4.1 Mapping between STUN and BEHAVE classification . . . 75
4.2 ICE candidate pairs ordered lists . . . 97
2.1 Example of SIP message . . . 22
2.2 SIP “trapezoid” . . . 32
2.3 SUBSCRIBE/NOTIFY flow . . . 36
2.4 Authentication message flow . . . 37
2.5 SDP offer example . . . 43
2.6 ANAT offer example . . . 44
3.1 Centralized peer-to-peer network . . . 48
3.2 Unstructured decentralized peer-to-peer network . . . 49
3.3 DHT lookups . . . 52
3.4 Chord ring topology . . . 54
3.5 Chord finger table of node n7 . . . 55
3.6 Tree + ring topology, with 3-bit keys and b = 1 . . . 57
3.7 XOR metric derived tree for ID 101 . . . 59
3.8 3-torus topology . . . 60
4.1 Typical network configuration of NAT . . . 67
4.2 NAT address and port mapping . . . 70
4.3 NAT endpoint-independent filtering . . . 71
4.4 NAT address-dependent filtering . . . 71
4.5 NAT address and port dependent filtering . . . 72
4.6 NAT external hairpinning . . . 73
4.7 Relaying . . . 76
4.8 Connection reversal . . . 77
LIST OF FIGURES
4.10 UDP hole punching when clients are behind the same NAT . . 79
4.11 Direct connection when clients are behind the same NAT . . . 79
4.12 UDP hole punching when clients are behind multiple levels of NAT . . . 80
4.13 STUN Message Header Structure . . . 87
4.14 STUN Message Attribute Structure . . . 87
4.15 STUN Relay Usage network layout . . . 90
4.16 Example of ICE SDP offer . . . 96
4.17 Example of ICE SDP answer . . . 96
4.18 ICE STUN validation checks . . . 98
5.1 Diagrams of P2P-SIP Location service approach . . . 100
6.1 Example of SIP dialog in case of dual-stack entities . . . 110
6.2 Example of SIP dialog in case of dual-stack entities . . . 112
6.3 Example of INVITE message with ALEX-Item entries . . . 114
6.4 Example of 180 RINGING message with ALEX-Item entries . 116 6.5 Candidates for a host behind NAT . . . 120
7.1 Outbound peer redundant subscriptions . . . 132
7.2 Probability tree for sessions across NAT . . . 135
7.3 CDF of peer lifetime after θ minutes . . . 140
7.4 Mean lifetime for different values of θ . . . 141
7.5 CDF Weibull distribution . . . 142
7.6 Subscription per relaying peer for different values of θ and p . 143 7.7 Probability a peer is actually doing media relay, for different values of θ and c . . . 144
7.8 Graph with high clustering . . . 147
7.9 Local clustering coefficient for an undirected graph . . . 148
7.10 Evolution of number of nodes starting from empty overlay . . 152
7.11 Evolution of in-degree distribution from every 10000 seconds of simulated time . . . 153
7.12 Evolution of in-degree distribution from different initial con-ditions . . . 153
7.13 In-degree for different advertising policies . . . 155
7.14 Out-degree for different advertising policies . . . 156
7.15 Bad links distribution for different policies for periodically con-tacting other nodes . . . 157
7.16 In-degree distribution for different policies for periodically con-tacting other nodes . . . 158
7.17 In-degree distribution for different maximum number of known nodes . . . 159
7.18 Bad links distribution for different maximum number of known nodes . . . 159
7.19 In-degree distribution for different number of advertised nodes 160 7.20 Bad links distribution for different values of θ . . . 161
A.1 Overview of the Wengophone NG project . . . 168
A.2 PhApiWrapper and PhApi libraries . . . 169
A.3 PAC schema . . . 170
A.4 Example of SIPDHT peer registration request . . . 171
A.5 Example of SIPDHT successful response to a DHT GET request172 A.6 SipAccount new hierarchy . . . 173
A.7 Modified WengoPhone login window . . . 173
A.8 SipAccount new hierarchy . . . 174
Introduction
The evolution of computer networks leaded to the deployment nearly om-nipresent broadband IP-based networks. The cheapness and increasing per-formance of data transmission through the Internet favored the development of new services over this infrastructure. Those services are often in substi-tution and enrichment of traditional one, which are typically provided over dedicated circuits.
One example is Television-over-IP (or IpTV ): the usage of the Internet as a transmission channel, instead of the common broadcast channels (air, cable, satellite) added interactivity to television. This means letting the user chose what watch and when (Video-on-Demand), but also let the user influence the program (e.g.: voting).
What is under the focus of this work, however, are the technologies that are leading to the gradual moving of the traditional circuit-switched phone line (PSTN1) over IP-based networks: VoIP (Voice over IP ), also called IP telephony.
This transition is happening at different levels. Under the eyes of the public, software applications that emulate a traditional phone are very pop-ular, and often distributed by a provider that is offering interconnection with the PSTN. Less evidently, some providers are pushing hardware devices that route analog voice signal coming from a traditional telephone, through an Internet connection, like a home ADSL. In third place, also the infrastruc-ture of PSTN has changed: the dedicated physical telephone line remains such only between the customer premises and the first aggregation point of the provider; from there on, all the voice traffic is usually routed over a
country-wide packet-switched network.
On a separated parallel track, another new technology took shape: the so called peer-to-peer (P2P ) network paradigm, in opposition to the traditional client/server one.
For the Internet surfer, working the “peer-to-peer way” means being less dependent and under control of a central authority (e.g. avoiding control on file sharing content). For a service provider, working the “peer-to-peer way” means being more scalable and needing less investment on hardware resources, because the providing of the service is distributed among all the peers; in this way users share their resources with the other users.
Skype[78] is the most clear proof of how these two technologies (VoIP and P2P) can be very effective if put together. They distributed a multi-platform P2P-based VoIP application, which required no configuration and had an easy to use GUI2. They also offered a very cheap interconnection with the PSTN. Currently, Skype network is reaching peaks of 9 million on-line users at the same time.
Skype, however, is a proprietary and closed solution. For this reason, it is not interoperable with other products and poses some security concerns.
This graduation thesis is going firstly to investigate the current protocols for doing VoIP (chapter 1) and in particular the Session Initiation Protocol (SIP, in chapter 2).
Then peer-to-peer overlays are examined (chapter 3), devoting particular care to DHT (Distributed Hash Table) algorithms.
Afterwards, the focus will move on Network Address Translation (NAT ) in chapter 4. NAT is largely employed in SOHO3 networks as well as in big networks installations, because it reduces the need of public IP addresses and is believed to increase network security. However it requires many protocols to be modified to work correctly. NAT traversal techniques will be analyzed, along with the issues that NAT creates for SIP and P2P protocols.
Chapter 5 will analyze how the integration between SIP and P2P is done, and what issues still need to be solved.
2Graphical User Interface 3Small Office – Home Office
INTRODUCTION
In chapter 6 a solution for effective direct connectivity between SIP UAs will be proposed, in particular extending it to the case of NATted UAs.
In order to perform NAT traversal in a peer-to-peer environment, how-ever, the help of another peer is needed (offering relay service). Therefore, in chapter 7 a methodology for Distributed Relay Service will be proposed. This solution will be also validated by means of statistical considerations and simulation.
In the end, in chapter 8, conclusion about this work will be drawn, and possible future development in this field will be considered.
