Transcript No Slide Title

P2P-SIP
Peer to peer Internet telephony using SIP
Kundan Singh and Henning Schulzrinne
Columbia University, New York
April 2005
http://www.cs.columbia.edu/IRT/p2p-sip
Agenda

Introduction


Architecture


SIP using P2P vs P2P over SIP; Components
that can be P2P
Implementation


What is P2P? and SIP? Why P2P-SIP?
Choice of P2P (DHT); Node join, leave;
message routing
Conclusions and future work
Total 33 slides
2
What is P2P?
Computer systems
Centralized

Distributed

mainframes
workstations
Client-server
Flat
Hierarchical
RPC
HTTP
DNS
mount
Share the resources of
individual peers
Peer-to-peer
Pure
Hybrid
Gnutella
Chord
Napster
Groove
CPU, disk, bandwidth,
information, …
Communication and collaboration
Magi
Groove
Skype
Napster
Gnutella
Kazaa
Freenet
Overnet
Kazaa
C
C
S
C
C
C
P
P
P
P
P
File sharing
SETI@Home
folding@Home
Distributed computing
3
P2P goals








Resource aggregation - CPU, disk, …
Cost sharing/reduction
Improved scalability/reliability
Interoperability - heterogeneous peers
Increased autonomy at the network edge
Anonymity/privacy
Dynamic (join, leave), self organizing
Ad hoc communication and collaboration
4
P2P file sharing

Napster


Gnutella


Flooding, TTL, unreachable nodes
FastTrack (KaZaA)


Centralized, sophisticated search
Heterogeneous peers
Freenet

Anonymity, caching, replication
5
P2P goals [re-visited]
•
•
•
If present => find it
Flooding is not scalable
Blind search is inefficient
P2P systems
Unstructured
Data availability
•
Decentralization
•
Scalability
•
Load balancing
•
Fault tolerance

Structured
Maintenance
•
Join/leave
•
Repair
Efficient searching
•
Proximity
•
Locality
Query time, number of messages, network usage,
per node state
6
Distributed Hash Table (DHT)

Types of search




Central index (Napster)
Distributed index with flooding (Gnutella)
Distributed index with hashing (Chord)
Basic operations
find(key), insert(key, value), delete(key),
but no search(*)
Properties/types
Every peer has
complete table
Chord
Every peer has one
key/value
Search time or
messages
O(1)
O(log(N))
O(n)
O(log(N)2)
O(1)
Join/leave messages O(n)
7
Why P2P-SIP?
REGISTER
[email protected] =>128.59.19.194
INVITE [email protected]
Contact: 128.59.19.194
Alice’s host
128.59.19.194
columbia.edu
Bob’s host
Client-server=> maintenance, configuration, controlled infrastructure
INVITE alice
P2P overlay
128.59.19.194
REGISTER
Alice
128.59.19.194
No central server, search latency
8
How to combine SIP + P2P?

SIP-using-P2P


Replace SIP location
service by a P2P
protocol
P2P-over-SIP

Additionally,
implement P2P using
SIP messaging
P2P network
FIND
INSERT
INVITE sip:[email protected]
INVITE alice
REGISTER
P2P-SIP
overlay
Alice
128.59.19.194
Alice
128.59.19.194
9
SIP-using-P2P



Reuse optimized and well-defined
external P2P network
Define P2P location service interface to
be used in SIP
Extends to other signaling protocols
10
P2P-over-SIP





P2P algorithm over SIP without change
in semantics
No dependence on external P2P
network
Reuse and interoperate with existing
components, e.g., voicemail
Built-in NAT/media relays
Message overhead
11
What else can be P2P?






Rendezvous/signaling
Configuration storage
Media storage
Identity assertion (?)
Gateway (?)
NAT/media relay (find best one)
12
What is our P2P-SIP?


Unlike server-based SIP architecture
Unlike proprietary Skype architecture


Robust and efficient lookup using DHT
Interoperability


Hybrid architecture


Lookup in SIP+P2P
Unlike file-sharing applications


DHT algorithm uses SIP communication
Data storage, caching, delay, reliability
Disadvantages

Lookup delay and security
13
Background: DHT (Chord)
1
54
8
58
10
14
47
Key
node
8+1 = 9
14
8+2 = 10
14
8+4 = 12
14
8+8 = 16
21
8+16=24
32
8+32=40
42



ith finger points
to first node that
succeeds n by at
least 2i-1

Stabilization for
join/leave

21
42
Identifier circle
Keys assigned to
successor
Evenly distributed
keys and nodes
Finger table: logN

38
32
38
24
30
0
1
2
3
4
5
6
7
8
14
Background: DHT (Chord)

Find


Map key to node
Join, Leave, or Failure

Update the immediate neighbors



Successor and predecessor
Stabilize: eventually propagate the info
Reliability

Log(N) successors; data replication
15
Design Alternatives
1
54
58
servers
47
42
38
38
8
d471f1
14 10
d46a1c
21
d467c4
d462ba
1
54
d4213f
10
32
24 30
Route(d46a1c)
d13da3
65a1fc
38
24 30
clients
Use DHT in
server farm
Use DHT for all
clients; But some
are resource limited
Use DHT among super-nodes
1.
2.
Hierarchy
Dynamically adapt
16
Architecture
User interface (buddy list, etc.)
On reset Signout,
transfer
On startup
Leave
Discover
Peer found/
Detect NAT
ICE
Signup,
Find buddies
IM,
call
User location
Find
Join
DHT (Chord)
Multicast REGISTER
REGISTER
Audio devices
REGISTER,
INVITE,
MESSAGE
SIP
Codecs
RTP/RTCP
SIP-over-P2P
P2P-using-SIP
17
Naming and authentication

SIP URI as node and user identifiers





Known node: sip:[email protected]
Unknown node: sip:[email protected]
User: sip:[email protected]
User name is chosen randomly by the
system, by the user, or as user’s email
Email the randomly generated password

TTL, security
18
SIP messages

1
DHT (Chord) maintenance

Query the node at distance 2k with node id 11
REGISTER
To: <sip:[email protected]>
From: <sip:[email protected]>
10
22
7
15
Find(11) gives 15
SIP/2.0 200 OK
To: <sip:[email protected]>
Contact: <sip:[email protected]>; predecessor=sip:[email protected]

Update my neighbor about me
REGISTER
To: <sip:[email protected]>
Contact: <sip:[email protected]>; predecessor=sip:[email protected]
19
SIP messages

User registration
REGISTER
To: sip:[email protected]
Contact: sip:[email protected]:8094

Call setup and instant messaging
INVITE sip:[email protected]
To: sip:[email protected]
From: sip:[email protected]
20
Node Startup
columbia.edu
sipd

REGISTER
SIP

DB

[email protected]
DHT

Detect peers
Discover peers: multicast REGISTER


58

12

14

REGISTER bob=12
SLP, bootstrap, host cache
Join DHT using node-key=Hash(ip)

REGISTER alice=42
42
REGISTER with SIP registrar
Query its position in DHT
Update its neighbors
Stabilization: repeat periodically
User registers using userkey=Hash([email protected])
32
21
Node Leaves

Chord reliability

REGISTER key=42

Graceful leave

REGISTER

42
OPTIONS
DHT

Un-REGISTER
Transfer registrations
Failure

42
Log(N) successors, replicate
keys


Attached nodes detect and
re-REGISTER
New REGISTER goes to new
super-nodes
Super-nodes adjust DHT
accordingly
22
Dialing Out (message routing)

INVITE sip:[email protected]
MESSAGE sip:[email protected]
INVITE key=42
302
Last seen
Call, instant message, etc.

INVITE

If existing buddy, use cache
first
If not found

DHT

SIP-based lookup (DNS
NAPTR, SRV,…)
P2P lookup

Use DHT to locate: proxy or
redirect to next hop
42
23
Implementation
31
29
1

31
30
sippeer: C++,
Unix (Linux), Chord

25
26
26

9

19
11
Node join and form
the DHT
Node failure is
detected and DHT
updated
Registrations
transferred on node
shutdown
15
24
Adaptor for existing phones


Use P2P-SIP
node as an
outbound proxy
ICE for
NAT/firewall
traversal

STUN/TURN
server in the
node
25
Hybrid architecture


Cross register, or
Locate during call
setup


DNS, or
P2P-SIP hierarchy
26
Offline messages

INVITE or MESSAGE fails






Responsible node stores voicemail, instant
message.
Delivered using MWI or when online
detected
Replicate the message at redundant nodes
Sequence number prevents duplicates
Security: How to avoid spies?
How to recover if all responsible nodes
leave?
27
Conferencing (further study)

One member becomes mixer



Fully distributed


Centralized conferencing
What if mixer leaves?
Many to many signaling and media
Application level multicast

Small number of senders
28
Evaluation
scalability

#messages depends on




Keep-alive and finger table refresh rate
Call arrival distribution
User registration refresh interval
Node join, leave, failure rates
M={rs+ rf(log(N))2} + c.log(N) + (k/t)log(N) + (log(N))2/N

#nodes = f(capacity,rates)


CPU, memory, bandwidth
Verify by measurement and profiling
29
Evaluation
reliability and call setup latency

User availability depends on






Super-node failure distribution
Node keep-alive and finger refresh rate
User registration refresh rate
Replicate user registration
Measure effect of each
Call setup latency

Same as DHT lookup latency: O(log(N))




Calls to known locations (“buddies”) is direct
DHT optimization can further reduce latency
User availability and retransmission timers
Measure effect of each
30
Explosive growth (further study)

Cache replacement at super-nodes






Last seen many days ago
Cap on local disk usage (automatic)
Forcing a node to become super node
Graceful denial of service if overloaded
Switching between flooding, CAN,
Chord, …
...
31
More open issues (further study)

Security





Optimization


Locality, proximity, media routing
Deployment


Anonymity, encryption,
Attack/DOS-resistant, SPAM-resistant
Malicious node
Protecting voicemails from storage nodes
SIP-P2P vs P2P-SIP, Intra-net, ISP servers
Motivation

Why should I run as super-node?
32
Conclusions
C
C
S
C
C
P
P
P
P

763
d46a1c
364
Route(d46a1c)
365
d471f1
d467c4
d462ba
d4213f
324
135

P
123
P2P useful for VoIP

C
427


Scalable, reliable
No configuration
Not as fast as client/server
P2P-SIP

Basic operations easy

d13da3
65a1fc
Implementation

564


sippeer: C++, Linux
Interoperates
Some potential issues


Security
Performance
http://www.cs.columbia.edu/IRT/p2p-sip
33
Backup slides
Napster
P1
P5


S
P2
P2
P4

Where is
“quit playing games” ?
Centralized index
File names =>
active holder machines
Sophisticated search

FTP

P3

Easy to implement
Ensure correct search
Centralized index



Lawsuits
Denial of service
Can use server farms
35
Gnutella
P
P
P
P
P
P



P
P
Flooding
Overlay network
Decentralized


P
Not scalable.


Robust
Use TTL. Query can
fail
Can not ensure
correctness
36
KaZaA (FastTrack)

P
P
P
P

P
P
Super-nodes
Election:

capacity

P

P
and availability

P


P
P
P

bandwidth, storage,
CPU
connection time
public address
Use heterogeneity of
peers
Inherently non-scalable

If flooding is used
37
FreeNet

2
1
P
P
12
P

3
File is cached on reverse
search path
Anonymity

7
4
6
11

10
P
5
8
P
9
P



P


Replication, cache
Similar keys on same node
Empirical log(N) lookup
TTL limits search
Only probabilistic
guarantee
Transaction state
No remove( )

Use cache replacement
38
Distributed Hash Tables

Types of search




Central index (Napster)
Distributed index with flooding (Gnutella)
Distributed index with hashing (Chord)
Basic operations
find(key), insert(key, value), delete(key), no search(*)
Properties/types
Every peer has
complete table
Every peer has one
key/value
Search time or
messages
O(1)
O(n)
Join/leave messages O(n)
O(1)
39
CAN
Content Addressable Network



Each key maps to one
point in the d-dimensional
space
Each node responsible for
all the keys in its zone.
Divide the space into
zones.
1.0
C
D
E
B
A
0.0
1.0
0.0
C
D
A
B
E
40
CAN
1.0
E
A
B
X
E
A
B
X Z
.75
C
C
.5
D
D
.25
(x,y)
0.0
0.0
.25
.5
.75
1.0
Node X locates (x,y)=(.3,.1)
Node Z joins
State = 2d
Search = dxn1/d
41
Chord

1
54
8
58

10
14

47
21
42
Identifier circle
Keys assigned to
successor
Evenly
distributed keys
and nodes
38
32
38
24
30
0
1
2
3
4
5
6
7 42 8
Chord
1
54
8
58
10
14
47
21

42

38
32
38

24
Key
node
8+1 = 9
14
8+2 = 10
14
8+4 = 12
14
8+8 = 16
21
8+16=24
32
8+32=40
42
Finger table: logN
ith finger points to first node that
succeeds n by at least 2i-1
Stabilization after join/leave
30
43
Tapestry
763
427


364
123
324
365
135
564
**4 => *64 => 364

N=2
N=1
N=0
064
?04
??0
164
?14
??1
264
?24
??2
364
?34
??3
464
?44
??4
564
?54
??5
664
?64
??6

ID with base B=2b
Route to numerically
closest node to the
given key
Routing table has O(B)
columns. One per digit
in node ID.
Similar to CIDR – but
suffix-based
44
Pastry



Prefix-based
Route to node with
shared prefix (with the
key) of ID at least one
digit more than this
node.
Neighbor set, leaf set
and routing table.
d471f1
d46a1c
d467c4
d462ba
d4213f
Route(d46a1c)
d13da3
65a1fc
45
Other schemes






Distributed TRIE
Viceroy
Kademlia
SkipGraph
Symphony
…
46
Comparison
Property/
scheme
Unstructured
CAN
Chord
Tapestry Pastry
Viceroy
Routing
O(N) or no
guarantee
d x N1/d
log(N)
logBN
logBN
log(N)
State
Constant
2d
log(N)
logBN
B.logBN
log(N)
Join/leave
Constant
2d
(logN)2
logBN
logBN
log(N)
Reliability
and fault
resilience
Data at Multiple
locations;
Retry on
failure; finding
popular content
is efficient
Multiple
peers for
each data
item; retry
on failure;
multiple
paths to
destination
Replicate data
on consecutive
peers; retry on
failure
Replicate data on
multiple peers; keep
multiple paths to each
peers
Routing load
is evenly
distributed
among
participant
lookup
servers
47
Server-based vs peer-to-peer
Reliability,
failover latency
DNS-based. Depends on client
retry timeout, DB replication
latency, registration refresh
interval
DHT self organization and
periodic registration refresh.
Depends on client timeout,
registration refresh interval.
Scalability,
number of users
Depends on number of servers
in the two stages.
Depends on refresh rate,
join/leave rate, uptime
Call setup
latency
One or two steps.
O(log(N)) steps.
Security
TLS, digest authentication,
S/MIME
Additionally needs a reputation
system, working around spy nodes
Maintenance,
configuration
Administrator: DNS, database,
middle-box
Automatic: one time bootstrap
node addresses
PSTN
interoperability
Gateways, TRIP, ENUM
Interact with server-based
infrastructure or co-locate peer node
with the gateway
48
Related work: Skype
From the KaZaA community
P
P
P

P
P
P
P

P

P
Host cache of some super nodes
Bootstrap IP addresses
Auto-detect NAT/firewall settings

P
P
P





Protocol among super nodes – ??
Allows searching a user (e.g., kun*)
History of known buddies
All communication is encrypted
Promote to super node


STUN and TURN
Based on availability, capacity
Conferencing
49
Reliability and scalability
Two stage architecture for CINEMA
a*@example.com
a1
s1
Master
a2
a.example.com
_sip._udp
SRV 0 0 a1.example.com
SRV 1 0 a2.example.com
Slave
sip:[email protected]
s2
sip:[email protected]
b*@example.com
s3
ex
example.com
_sip._udp
SRV 0 40 s1.example.com
SRV 0 40 s2.example.com
SRV 0 20 s3.example.com
SRV 1 0 ex.backup.com
b1
Master
b2
Slave
b.example.com
_sip._udp
SRV 0 0 b1.example.com
SRV 1 0 b2.example.com
Request-rate = f(#stateless, #groups)
Bottleneck: CPU, memory, bandwidth?
50
Failover latency: ?
Related work
P2P

P2P networks



Skype and related systems


Unstructured (Kazaa, Gnutella,…)
Structured (DHT: Chord, CAN,…)
Flooding based chat, groove, Magi
P2P-SIP telephony


Proprietary: NimX, Peerio,
File sharing: SIPShare
51
Why we chose Chord?

Chord can be replaced by another






As long as it can map to SIP
High node join/leave rates
Provable probabilistic guarantees
Easy to implement
X proximity based routing
X security, malicious nodes
52
Related work
JXTA vs Chord in P2P-SIP

JXTA



Protocol for communication (peers, groups,
pipes, etc.)
Stems from unstructured P2P
P2P-SIP

Instead of SIP, JXTA can also be used

Separate search (JXTA) from signaling (SIP)
53
Find(user)

Option-1: No REGISTER




Node computes key based on
user ID
Nodes join the overlay based on
ID
One node  one user
Option-2: With REGISTER



REGISTERs with nodes
responsible for its key
Refreshes periodically
Allows offline messages (?)
56
42
alice=42
42
12
REGISTER alice=42
58
12
bob=12
14
REGISTER bob=12
32
24
sam=24
24
54
P2P-SIP
Security – open issues (threats, solutions, issues)

More threats than server-based


Privacy, confidentiality
Malicious node



“free riding”, motivation to become super-node
Existing solutions



Focus on file-sharing (non-real time)
Centralized components (boot-strap, CA)
Assume co-operating peers (




Don’t forward all calls, log call history (spy),…
works for server farm in DHT
Collusion
Hide security algorithm (e.g., yahoo, skype)
Chord

Recommendations, design principles, …
55
P2P so far…
Kademlia protocol
eMule
Applejuice Client
Acquisitionx (Mac OS X)
MindGem
aMule
(Linux)
BitTorrent network
BearShare
eDonkey client (no longer
MLDonkey
ABC
BetBug
supported)
Azureus
MANOLITO/MP2P
network
Cabos
eMule
BitAnarch
Blubster
CocoGnut (RISC OS)
BitComet
LMule
Piolet
Gnucleus
BitSpirit
MindGem
Grokster
RockItNet
BitTornado
MLDonkey
iMesh Light
Napster network
BitTorrent
mlMac
gtk-gnutella (Unix)
Napigator
BitTorrent++
Shareaza
LimeWire (Java)
OpenNap
BitTorrent.Net
MLDonkey
xMule
WinMX
G3 Torrent
mlMac
iMesh Light
Peercasting
type networks
mlMac
Morpheus
ed2k
(eDonkey
2000
protocol)
MLDonkey
PeerCast
Phex
eDonkey
QTorrent
IceShare
Poisoned
eMule
SimpleBT
Freecast
Swapper
xMule
Shareaza
Shareaza
WPNP network
aMule
TomatoTorrent (Mac OS X)
XoloX
WinMX
Shareaza
TorrentStorm
Gnutella2
network
other
networks
FastTrack protocol
CAKE network
Adagio
Akamai
giFT
BirthdayCAKE
Caribou
Grokster
Alpine
Direct Connect network
Gnucleus
iMesh, iMesh Light
ANts P2P
BCDC++
iMesh Light
Kazaa , Kazaa Lite, K++, Diet
Ares Galaxy
CZDC++
MLDonkey
Kaza, CleanKazaa
Audiogalaxy network
DC++
mlMac
Mammoth
NeoModus Direct Connect
Carracho
Morpheus
MLDonkey
JavaDC
Chord
Shareaza
mlMac
DCGUI-QT
TrustyFiles
The Circle
Poisoned
HyperCast
Coral[5]
Freenet network
Joltid PeerEnabler
Entropy
Dexter
Freenet
Altnet
Diet-Agents
Frost
Bullguard
EarthStation 5 network
Applejuice network
eDonkey network
Gnutella network
Joltid
Kazaa, Kazaa Lite
Evernet
FileTopia
GNUnet
Grapevine
Groove
Hotwire
iFolder[6]
konspire2b
Madster/Aimster
MUTE
Napshare
OpenFT
Poisoned
P-Grid[7]
IRC @find XDCC
JXTA
Peersites [8]
MojoNation
Mnet
Overnet network
Scour
Scribe
Skype
Solipsis
SongSpy network
Soulseek
SPIN
SpinXpress
SquidCam [9]
Swarmcast
WASTE
Warez P2P 56
Winny