Transcript Addressing the P2P Bootstrap Problem for Small Overlay Networks

Addressing the P2P Bootstrap
Problem for Small Overlay Networks
David Wolinsky, Pierre St. Juste,
P. Oscar Boykin, and Renato Figueiredo
ACIS P2P Group
University of Florida
Motivation
• Users want to be connected
– Online games
– Exchange media
• Family pictures and movies
• Favorite music
– Social networking
• How can they get connected?
Issues
• Centralized systems are not user centric
– Invasive, record / monitor you
– Limited flexibility, expandability
– Have costs associated with it
• Decentralized / P2P solutions are difficult
– Bootstrapping requires a dedicated
community with many users or
dedicated bootstrap servers
– Has to support NAT traversal
– Must be able to identify users and
communicate with them
Contributions
• Explore bootstrapping issues in transparent,
decentralized P2P systems
• Investigate the use of publicly available
overlays as bootstrap systems
• Present our techniques in creating a small
overlay using XMPP and Brunet
– XMPP / Jabber – Popular chat protocol
– Brunet – open source (structured) overlay
software
Outline
•
•
•
•
•
•
Introduction
Overlays Bootstrapping from Overlays
Using Existing Overlays
Implementation through Recursion
Implementation through XMPP
Conclusions
Outline
•
•
•
•
•
•
Introduction
Overlays Bootstrapping from Overlays
Using Existing Overlays
Implementation through Recursion
Implementation through XMPP
Conclusions
Considerations
• Transparent decentralized NAT traversal is
hard
– Who provides the STUN / TURN server?
– How do users configure their software to point to
that server?
• How are users supposed to find each other?
– Exchange IP addresses with each other?
– Run their computers on a LAN – using multicast /
broadcast software?
Bootstrapping
I want to use
P2P AppY!
We are using
P2P AppY!
Bootstrapping
Overlay Service Providers
I want to use
P2P AppY!
We are using
P2P AppY!
Reflection Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
Bootstrapping
Overlay Service Providers
1A) Reflection request
I want to use
P2P AppY!
We are using
P2P AppY!
Reflection Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
I want to use
P2P AppY!
We are using
P2P AppY!
Reflection Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
I want to use
P2P AppY!
We are using
P2P AppY!
Reflection Service Providers
Rendezvous Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
Rendezvous Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
Relay Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
• Relaying – Communication through the overlay to instigate NAT
traversal or for when NAT traversal fails
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
3A) Relay, connect to me at
these network addresses
Relay Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
• Relaying – Communication through the overlay to instigate NAT
traversal or for when NAT traversal fails
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
3B) Relay, connect to me at
these network addresses
3A) Relay, connect to me at
these network addresses
Relay Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
• Relaying – Communication through the overlay to instigate NAT
traversal or for when NAT traversal fails
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
3B) Relay, connect to me at
these network addresses
3A) Relay, connect to me at
these network addresses
3C) Relay, connect to me at
these network addresses
Relay Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
• Relaying – Communication through the overlay to instigate NAT
traversal or for when NAT traversal fails
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
3A) Relay, connect to me at
these network addresses
3B) Relay, connect to me at
these network addresses
3D) Relay, connect to me at
these network addresses
3C) Relay, connect to me at
these network addresses
Relay Service Providers
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
• Relaying – Communication through the overlay to instigate NAT
traversal or for when NAT traversal fails
Bootstrapping
Overlay Service Providers
1A) Reflection request
1B) List of mapped
public addresses
We are using
P2P AppY!
I want to use
P2P AppY!
Reflection Service Providers
2A) Rendezvous, I am interested
in AppY, is anyone else?
2B) List of remote
overlay addresses
Rendezvous Service Providers
3A) Relay, connect to me at
these network addresses
3B) Relay, connect to me at
these network addresses
3D) Relay, connect to me at
these network addresses
3C) Relay, connect to me at
these network addresses
Relay Service Providers
4. Connected – Let’s use our application!
• Reflection – Peers need global IDs so that they can communicate
with each other
• Rendezvous – The ability to identify peers with a common interest
• Relaying – Communication through the overlay to instigate NAT
traversal or for when NAT traversal fails
Outline
•
•
•
•
•
•
Introduction
Overlays Bootstrapping from Overlays
Using Existing Overlays
Implementation through Recursion
Implementation through XMPP
Conclusions
Existing Overlays
Overlay
The Good
The Bad
BitTorrent Very popular!
Very centralized! Limited NAT traversal
Gnutella
Completely Decentralized
Can be difficult to find rare values, no
NAT traversal
Skype
Completely Decentralized with
rendezvous and relaying, limited
NAT traversal
Closed source, no external NAT
traversal support, must use Skype
transports
XMPP
Federated (Centralized /
Decentralized)
Only some servers provide NAT
traversal
Kademlia
Completely decentralized and
very efficient rendezvous
No NAT traversal or relaying support
Brunet
Completely decentralized,
supports all requirements
Academic, limited adoption
Outline
•
•
•
•
•
•
Introduction
Overlays Bootstrapping from Overlays
Using Existing Overlays
Implementation through Recursion
Implementation through XMPP
Conclusions
Brunet – Overview
• Brunet provides
– Generic overlay library
– Abstracted transports library
– NAT traversal via STUN and TURN
– Structured overlay with DHT
• IPOP / SocialVPN builds upon Brunet to create
IP overlays
• Developers can use IPOP or tap directly into
Brunet
• Publicly available PlanetLab overlay
Abstraction
• EdgeListeners handle creating
outgoing links and handling
incoming links
• Edges store state for links
• Connections store overlay
information for links and represent
• Connection Managers create links,
verify bidirectional connectivity,
and add to routing
• Node constructs the environment
and provides basic routing
primitives
Node (Overlay Management)
Routing
Connection Managers –
Structured /
Bootstrapping / Direct
Connections (Verified
bidirectional links)
Edges (Links to remote nodes)
EdgeListener (Transport Manager)
EdgeListener / Edges
• Generic transports library
• Examples:
– UDP – good for NAT traversal
– TCP – works when firewalls block UDP
– Relay – route through overlay node – useful when a direct link is not
available (firewall / NAT)
– Xmpp – route through XMPP server – useful for bootstrapping as well
as relaying
– Subring – route through another Brunet overlay – useful for
bootstrapping as well as relaying
– Pathing – Allows multiple overlays to use the same EdgeListener
• Primitives
– EdgeListener::CreateEdgeTo(Address) – create a link to a remote
address
– EdgeListener::Subscribe(Listener) – Listener receives packets and
incoming edges
– Edge::Send(Data)
Initiating Private Communication
Overlay Link
Public / Private
Overlay Mapping
Overlay
Communication
Public
Private
Overlay
Initiating Private Communication
Overlay Link
Public / Private
Overlay Mapping
Overlay
Communication
Public
Private
Overlay
1) Reflection – New peer
joins the public overlay
Initiating Private Communication
Overlay Link
Public / Private
Overlay Mapping
Overlay
Communication
2) Rendezvous – Peer
queries DHT for Private
overlay peers
DHT Entry for
Private Overlay
Public
Private
Overlay
1) Reflection – New peer
joins the public overlay
Initiating Private Communication
Overlay Link
Public / Private
Overlay Mapping
Overlay
Communication
2) Rendezvous – Peer
queries DHT for Private
overlay peers
DHT Entry for
Private Overlay
Public
Private
Overlay
1) Reflection – New peer
joins the public overlay
Initiating Private Communication
Overlay Link
Public / Private
Overlay Mapping
Overlay
Communication
DHT Entry for
Private Overlay
2) Rendezvous – Peer
queries DHT for Private
overlay peers
Public
Private
Overlay
1) Reflection – New peer
joins the public overlay
3) Relay – Send
“ConnectTo” message
through the public overlay
via Subring transport
Initiating Private Communication
Overlay Link
Public / Private
Overlay Mapping
Overlay
Communication
DHT Entry for
Private Overlay
2) Rendezvous – Peer
queries DHT for Private
overlay peers
Public
Private
Overlay
1) Reflection – New peer
joins the public overlay
3) Relay – Send
“ConnectTo” message
through the public overlay
via Subring transport
4) Peer is connected to the
private overlay, multiplexing
public overlay’s socket via
Pathing transport
Outline
•
•
•
•
•
•
Introduction
Overlays Bootstrapping from Overlays
Using Existing Overlays
Implementation through Recursion
Implementation through XMPP
Conclusions
Introducing the Federation
• XMPP is a federation
– Over 70 distinct and active service providers
– Including GoogleTalk, Jabber.org, and Live Journal
– Can establish friendships across providers – Users
from GoogleTalk can chat with Jabber.org users
• Overlay bootstrapping features:
– Each peer has a unique identifier in the form of
name@service_provider/unique_string
– Supports sending binary messages called IQ
– Some servers support “Jingle” an XMPP service to
discover STUN and TURN servers
Bootstrapping through XMPP
Jingle
Provider
XMPP
Server
Overlay Link
Private
Overlay
Public / Private
Overlay Mapping
Overlay
Communication
A
Bootstrapping through XMPP
Jingle
Provider
XMPP
Server
Overlay Link
Private
Overlay
Public / Private
Overlay Mapping
Overlay
Communication
A
1) Connect to server
Bootstrapping through XMPP
Jingle
Provider
2) Reflection – New peer
contacts jingle provider
XMPP
Server
Overlay Link
Private
Overlay
Public / Private
Overlay Mapping
Overlay
Communication
A
1) Connect to server
Bootstrapping through XMPP
Jingle
Provider
3) Rendezvous – Monitor
presence notification
2) Reflection – New peer
contacts jingle provider
Friend of A
XMPP
Server
Overlay Link
Private
Overlay
Public / Private
Overlay Mapping
Overlay
Communication
B
A
1) Connect to server
Bootstrapping through XMPP
Jingle
Provider
3) Rendezvous – Monitor
presence notification
2) Reflection – New peer
contacts jingle provider
Friend of A
XMPP
Server
Overlay Link
Private
Overlay
Public / Private
Overlay Mapping
Overlay
Communication
B
A
1) Connect to server
4) Relay
– Send“Connect”
“Connect”via
IQ relay
4) Relay
– Exchange
peers
found
by by
rendezvous
IQ to
with
peers
found
rendezvous
Bootstrapping through XMPP
Jingle
Provider
3) Rendezvous – Monitor
presence notification
2) Reflection – New peer
contacts jingle provider
Friend of A
XMPP
Server
Overlay Link
Private
Overlay
Public / Private
Overlay Mapping
Overlay
Communication
B
A
A
1) Connect to server
4) Relay
– Send“Connect”
“Connect”via
IQ relay
4) Relay
– Exchange
peers
found
by by
rendezvous
IQ to
with
peers
found
rendezvous
5) Peer is connected
to the private overlay
Outline
•
•
•
•
•
•
Introduction
Overlays Bootstrapping from Overlays
Using Existing Overlays
Implementation through Recursion
Implementation through XMPP
Conclusions
How Well Does it Work?
In Seconds
Reflection
Rendezvous
Relaying
Connected
XMPP
.035
.110
.243
20.3
Brunet
3.05
.330
.533
23.22
• Time to bootstrap 5 peers behind 5 different port restricted cone NATs
• Tests were repeated 5 times – averages shown
• Reflection is time for the private peer to become aware – Brunet slowed
due to booting public node first
• Rendezvous
– XMPP presence notification from the server
– Brunet measures a DHT look up
• Relaying
– XMPP – time to relay a packet through the server
– Brunet – time to relay a packet through the overlay
• Connected – time until all nodes are part of a new overlay
• Recent work has discovered a bug that makes connectivity much faster (on
the order of a few seconds)
Experiences
• Supporting XMPP is not the same as being in
the Federation – Facebook supports XMPP
clients but does not support IQ (data
messages)
• GoogleTalk blocks communication from
PlanetLab
• Cross-domain XMPP initiation appears delayed
– up to 30 seconds between
jabber.rootbash.com and GoogleTalk
Our Use (1) – SocialVPN
• SocialVPN uses XMPP friendships to establish
VPN links
• Originally, XMPP was only used to exchange
certificate and then links were formed through
our public Brunet overlay
• Now if our public overlay is down – Peers can
direct links via XMPP
• What happens if XMPP is down – Peers can form
direct links via the overlay
• SocialVPN is no longer dependent on our overlay!
Choosing Overlays
• Goal achieved– Completely transparent solution
– Reflection for identity
– Rendezvous to find peers
– Relaying to establish direct links
• Limited our choices to XMPP and Brunet
• Issue with XMPP – Users must be friends in order
to have successful rendezvous
• Future work – Use Kademlia for rendezvous to
automatically create XMPP friends and use XMPP
for relaying and reflection
Thank you!
Questions?
More at www.ipop-project.org
Discovery / Rendezvous
Over here, Alice!
Bob, where
are you?
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
NAT Device
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device
DST: 77.23.192.67:20000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
192.168.1.1
NAT Device
NAT Device
128.212.33.44
77.134.53.114
Private Network
Private Network
172.16.1.1
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device
NAT Device
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
192.168.1.1
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
Private Network
Private Network
128.212.33.44
77.134.53.114
172.16.1.1
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
NAT Device
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
Private Network
Private Network
128.212.33.44
77.134.53.114
172.16.1.1
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
NAT Device
X
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
X
Private Network
77.134.53.114
172.16.1.1
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
NAT Device
X
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
X
Private Network
172.16.1.1
77.134.53.114
Successful NAT traversal
192.168.1.1
Private Network
NAT Device
NAT Device
128.212.33.44
77.134.53.114
172.16.1.1
Private Network
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
NAT Device
X
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
X
Private Network
172.16.1.1
77.134.53.114
Successful NAT traversal
SRC: 192.168.1.1:1000 NAT Device
DST: 77.134.53.114:12345
NAT Device
SRC: 172.16.1.1:20000
DST: 128.212.33.44:54321
192.168.1.1
128.212.33.44
Private Network
172.16.1.1
77.134.53.114
Private Network
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
NAT Device
X
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
X
Private Network
172.16.1.1
77.134.53.114
Successful NAT traversal
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.134.53.114:12345
DST: 77.134.53.114:12345
SRC: 77.134.53.114:12345
DST: 128.212.33.44:54321
192.168.1.1
128.212.33.44
Private Network
NAT Device
SRC: 172.16.1.1:20000
DST: 128.212.33.44:54321
172.16.1.1
77.134.53.114
Private Network
Bootstrapping – NATs
Node behind a NAT to a node on a public IP
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.23.192.67:20000
DST: 77.23.192.67:20000
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
SRC: 77.23.192.67:20000
DST: 128.212.33.44:54321
128.212.33.44
Public Network
77.23.192.67
Failed NAT traversal
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
NAT Device
X
SRC: 192.168.1.1:1000
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 192.168.1.1:1000
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
X
Private Network
172.16.1.1
77.134.53.114
Successful NAT traversal
SRC: 192.168.1.1:1000 NAT Device SRC: 128.212.33.44:54321
DST: 77.134.53.114:12345
DST: 77.134.53.114:12345
SRC: 77.134.53.114:12345
DST: 192.168.1.1:1000
192.168.1.1
128.212.33.44
Private Network
SRC: 77.134.53.114:12345
DST: 128.212.33.44:54321
NAT Device SRC: 128.212.33.44:54321
DST: 172.16.1.1:20000
SRC: 172.16.1.1:20000
DST: 128.212.33.44:54321
172.16.1.1
77.134.53.114
Private Network
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
NAT Device
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
192.168.1.1
Private Network
NAT Device
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
192.168.1.1
Private Network
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 128.212.33.44.54321
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 128.212.33.44.54321
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 128.212.33.44.54321
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
NAT traversal initiated by a relay
Public Node
77.23.192.67:3000
NodeID:FEED
NAT Node
NAT Node
192.168.1.1:1000
128.212.33.44:54321
NodeID:BEEF
192.168.1.1:1000
77.134.53.114:12345
NodeID:DEAD
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 128.212.33.44.54321
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
BE T
EF o D
at EA
BE D,
EF Co
’s nne
Pu c
bl t to
ic
In
fo
NAT traversal initiated by a relay
Public Node
77.23.192.67:3000
NodeID:FEED
NAT Node
NAT Node
192.168.1.1:1000
128.212.33.44:54321
NodeID:BEEF
192.168.1.1:1000
77.134.53.114:12345
NodeID:DEAD
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 128.212.33.44.54321
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
Public Node
77.23.192.67:3000
NodeID:FEED
to fo
ct In
ne blic
on Pu
,C s
D F’
EA E
D t BE
To F a
E
BE
BE T
EF o D
at EA
BE D,
D
EF Co
EA
’s nne
D
’s
Pu c
Pu
bl t to
ic
bl
ic
In
fo
In
fo
NAT traversal initiated by a relay
NAT Node
NAT Node
192.168.1.1:1000
128.212.33.44:54321
NodeID:BEEF
192.168.1.1:1000
77.134.53.114:12345
NodeID:DEAD
Bootstrapping – Reflection to Relaying
Reflection (via STUN)
Q: What’s my public info
SRC: 192.168.1.1:1000
DST: 77.23.192.67:20000
Q: What’s my public info
NAT Device SRC: 128.212.33.44.54321
DST: 77.23.192.67:20000
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 128.212.33.44.54321
R: 128.212.33.44.54321
SRC: 77.23.192.67:20000
DST: 192.168.1.1:1000
192.168.1.1
Private Network
128.212.33.44
Public Network
77.23.192.67
NAT Node
Public Node
77.23.192.67:3000
NodeID:FEED
to fo
ct In
ne blic
on Pu
,C s
D F’
EA E
D t BE
To F a
E
BE
BE T
EF o D
at EA
BE D,
D
EF Co
EA
’s nne
D
’s
Pu c
Pu
bl t to
ic
bl
ic
In
fo
In
fo
NAT traversal initiated by a relay
SRC: 128.212.33.44:54321
DST: 77.134.53.114:12345
NAT Node
SRC: 77.134.53.114:12345
DST: 128.212.33.44:54321
192.168.1.1:1000
128.212.33.44:54321
NodeID:BEEF
192.168.1.1:1000
77.134.53.114:12345
NodeID:DEAD
Supporting Recursion
• NAT traversal always multiplexes a single UDP socket, thus
for Cone NAT systems, the peer has a common public IP
and port
• Each overlay has a unique Path
• Upon creating a link, an RPC from the
creator to the receiver specifies which
Path the link belongs
• Requires that a single pathway can be
multiplexed
Private
Overlay
Broadcast
Overlay
Multicast
Overlay
Public
Overlay
– TCP does this by using different source ports
– UDP requires an additional header
containing source and destination remote
IDs (Something TCP will require too if NAT
traversal is to be supported)
Path0
Path1
Path2
Pathing
EdgeListener
Path3