Transcript Analytical work on 7DS

7DS: Node Cooperation in
Mostly Disconnected Networks
Henning Schulzrinne
(joint work with Arezu Moghadan, Maria Papadopouli, Suman
Srinivasan and Andy Yuen)
Dept. of Computer Science
Columbia University
Problems with Wide Area
Wireless
•
•
802.11 currently hard to deploy across city or large area
2.5G/3G wireless networks not suitable for large data volumes
– cost and network design
•
•
Problem: How can mobile devices / gadgets get and generate
information?
Examples:
– PDAs and smartphones
• digital content such as news, maps, tourist information,
entertainment
– digital still and video cameras  MB of data
Solution: 7DS!
Concept
• Use local peer-to-peer wireless networks to
exchange information
– Peers can get information they do not have
from another peer
• Model core Internet data applications
– Internet  mobile: web access (retrieval)
– Mobile  Internet: email (messaging)
• Once wireless 7DS network set up, it could be
used for any purpose
– Getting web pages from peers
– Sending e-mails
– File transfer to selected client
Illustration
In the absence of the Internet, nodes
can exchange information amongst
themselves
Internet
Realization
System architecture
web
browser
proxy
search engine
Internet
email
client
email
queue
Design
• Peer-to-peer network set up using
zeroconf
– Protocol enables devices to get IP
address and communicate without a
DHCP / other server
• Proxy server serves content
– If connected to Internet, functions
normally
– If not connected, connects to peers to
get information
Design
• Search engine
– Allows self / peers to search within the
device’s database for necessary
information
• Multicast querying system
– Allows peers to query systems in peerto-peer network
– Searches can be for files or keywords
• Transport System
– To forward e-mail
Design
Connection & Proxy Server
• Connection set up using zeroconf protocol
– Similar to AppleTalk, Microsoft NETBIOS, Novell
IPX
– Uses link-local addressing, multicast DNS, DNS
service discovery
• Proxy server
– Peer’s user client uses localhost proxy server by
default
– Detects Internet connection availability
– If Internet, normal network operation
– No Internet, peer-to-peer data exchange
Search Engine
• Provides ability to
query self for results
• Searches the cache
index using Swish-e
library
• Presents results in
any of three formats:
HTML, XML and
plain text
• Similar in concept to
Google Desktop
Query multicast engine
• Used to actually
exchange information
among peers
• Requesting peer
broadcasts a query to
the network
• Responding peers reply
if they have information
– Send encoded string
with list of matching
items
• Requesting peer
retrieves suitable
information
Analytical work on 7DS
• Email upload application
– How to remove message replicas upon email
delivery?
– Impact of a feedback channel?
• P2P file exchange
– Throughput related to content popularity model
– How to improve dissemination for unpopular
content?
• Push based vs. Pull based data dissemination
– Bloom filter based vs. query based strategy
– Optimal design parameters for Bloom filter
based algorithm
Email Delivery App
• How to remove redundant message replicas upon
email delivery?
– Time-based (TB): purge message upon TTL
expiration TB(TTL)
– Hop-based (HB): purge message when
dissemination tree reaches specific depth and
breadth HB(breadth,depth)
– Feedback (FB): receive notification upon message
delivery
• 4 Schemes: TB, HB, TB/FB, HB/FB
• Storage cost (number of message replicas)
Arrival to AP
17 min on avg
TB(170)
HB(2,6)
HB(3,4)
HB(4,3)
HB(7,2)
No Feedback
3169
114
102
75
50
Feedback(FB)
54
41
32
29
18
Email Delivery App (Cont ‘d)
• Hop-based scheme is
superior, with smaller
expected cost and variance
• Expedited (100sec) and
reliable message delivery
(Pd=1) possible at small
cost
– 50 replicas for HB(7,2)
• With feedback HB(7,2) has
a cost of 18 replicas
Stopping time: time when all message replicas are purged
Message delivery time: time when email message is delivered
FB and NFB schemes have same message delivery time statistically
Stopping time and message delivery time is the same for FB schemes
Conclusion
• 7DS promises to allow local connectivity
• Exchange of information within local
network
• No user intervention unless absolutely
necessary
• New step in practical, large-scale
wireless networking with gadgets?
– Remains to be seen