Transcript DSL (PPT, 3 lectures) - Department of Computer Science

Davis Social Links
S. Felix Wu
Computer Science Department
University of California, Davis
[email protected]
http://www.cs.ucdavis.edu/~wu/
Internet
• Basic datagram service between one IP
address and another
• Routing: exchanging the information
regarding the address space and how to
reach them.
• “Allow by Default”
• Applications built on top of the services
– MySpace, Facebook, Orkut, SecondLife,
LiveJournal, LinkedIn, Wikipedia, Skype,
Google, Bittorrent, LimeWire, Youtube,
IM,…
09/10/2007
Davis Social Links
2
Easy to Send & Receive
• Many, if not most, in our society can
quickly learn how to use Email &
Internet.
• You don’t need to understand the low
level details (e.g., how SMTP, BGP,
OLSR or AODV really works or what
my current IP address is) before you
can communicate with your friends as
long as you know their identity!
09/10/2007
Davis Social Links
3
Urgent! Please contact me!
FROM:MR.CHEUNG PUI
Hang Seng Bank Ltd
Sai Wan Ho Branch
171 Shaukiwan Road
Hong Kong.
Please contact me on my personal box [[email protected]]
Let me start by introducing myself. I am Mr. Cheung Pui,director of operations of
the Hang Seng Bank Ltd,Sai Wan Ho Branch. I have a obscured business
suggestion for you.
Before the U.S and Iraqi war our client Major Fadi Basem who was with the Iraqi
forces and also business man made a numbered fixed deposit for 18 calendar
months, with a value of Twenty Four millions Five Hundred Thousand United
State Dollars only in my branch. Upon maturity several notice was sent to him,…
09/10/2007
Davis Social Links
4
ITRI considers this as a spam!
09/10/2007
Davis Social Links
5
Easy to Send & Receive
• Easy for both the good users and the
spammers. (fair simplicity)
• The spammers abuse the “sending” right,
while the good users have very limited
options to counter back.
– how easy can we change our email address?
– how often do we need to do that?
• A “receiver” or “the owner of the
identity” should have some control.
– But, that means also “burden” to the users.
09/10/2007
Davis Social Links
6
Easy to Send & Receive
• Easy for both the good users and the
spammers. (fair simplicity)
• The spammers abuse the “sending”
right, while the good users have very
limited options to counter back.
– how easy can we change our email address?
– how often do we need to do that?
• A “receiver” or “the owner of the
identity” should have some control.
– But, that means also “burden” to the users.
09/10/2007
Davis Social Links
7
Possible Ideas of Future Internet
• Allow by Default versus Deny by Default
• Receiver versus Sender controllability
• Reconsider the role of Service Providers
versus P2P
09/10/2007
Davis Social Links
8
DSL (Davis Social Links)
A
B
Principle:
– Effective human communication reflects
the social/trust relationship and
reputation within our society.
Design:
– Can we integrate and enhance our cyber
communication system with the human
social/trust model?
A
09/10/2007
F
F
Davis Social Links
F
B
9
09/10/2007
Davis Social Links
10
Social Networking
• Social Network services
– Friendster, MySpace, Facebook, Orkut,
LinkedIn..
• Social Links, Interest Keywords,
Search & Community Services
09/10/2007
Davis Social Links
11
Social Networks: # of Users
http://en.wikipedia.org/wiki/List_of_social_networking_sites
•
•
•
•
•
•
•
•
FaceBook
Friendster
Hi5
LinkedIn
MySpace
Orkut
Yahoo! 360o
… among many others.
09/10/2007
Davis Social Links
~34M
~47M
~50M
~12M
~200M
~47M
~4M
12
09/10/2007
Davis Social Links
13
Social Network Access Interfaces
• FBML - Facebook Markup Language
• FQL - Facebook Query Language
• REST (REpresentational State Transfer)
Web API
• FBJS - Implementation of Javascript on
the Facebook platform
09/10/2007
Davis Social Links
14
DSL (Davis Social Links)
A
B
Principle:
– Effective human communication reflects
the social/trust relationship and
reputation within our society.
Design:
– Can we integrate and enhance our cyber
communication system with the human
social/trust model?
A
09/10/2007
F
F
Davis Social Links
F
B
15
The same message content
• “M” from Cheung Pui
• “M” from Cheung Pui via IETF mailing list
• “M” from Cheung Pui via Karl Levitt
09/10/2007
Davis Social Links
16
Social Link Identification
• “M” from Cheung Pui
 Probably a spam
• “M” from Cheung Pui via IETF mailing list
 Probably not interesting
• “M” from Cheung Pui via Karl Levitt
 Better be more serious…
09/10/2007
Davis Social Links
17
Social Link Identification
• “M” from Cheung Pui
 Probably a spam
• “M” from Cheung Pui via IETF mailing list
 Probably not interesting
• “M” from Cheung Pui via Karl Levitt
 Better be more serious…
Either “M” is important, or
Karl’s machine has been subverted!
09/10/2007
Davis Social Links
18
A Social Link
Trust Attribute
representing a trust relationship between two directly
communicating entities
09/10/2007
Davis Social Links
19
A Direct Social Link
Trust Attribute
Karl is a very well respected individual to me!
I suspect that Karl is too busy to install the latest patches!
09/10/2007
Davis Social Links
20
Message Value & Prioritization
Link Ranks
Reputation
Incentives
Other Trust Metrics
09/10/2007
Application IDS
Davis Social Links
21
DSL (Davis Social Links)
A
B
One important goal:
– Can we build a P2P social network
service?
– Allows Search/Crawl and Control
– Scalable and Secure/Robust
– “Control” implies relatively more dynamic
social network!
A
09/10/2007
F
F
Davis Social Links
F
B
22
A Path of Social Links
09/10/2007
Davis Social Links
23
Receiving an email via a Path of Social Links
09/10/2007
Davis Social Links
24
A Couple of Issues first…
• How to discover the social route
path, if no direct social link
exists?
• How to prevent spammers from
easily discovering a large number
of valid social paths?
09/10/2007
Davis Social Links
25
Social Keywords
Soccer, BGP, Davis,
California, Intrusion
Detection,…
09/10/2007
Davis Social Links
26
Social Keywords
Soccer, BGP, Davis,
California, Intrusion
Detection,…
Ownership
Social keywords represents my interests and the
semantic/social interpretation of myself.
09/10/2007
Davis Social Links
27
Cultural & Natural Language
工研院, BGP, 台灣,
Students, Committee, Soccer
09/10/2007
Davis Social Links
28
IP
• IP address is all we need to communicate
and everything else is on top of IP.
• IP is global “routable” identity
• However, too simple to be perfect?!
– Can we remove the need for global routable
identities?
09/10/2007
Davis Social Links
29
Identifier & Keyword
• Under DSL, each peer has its own decision or
policy regarding what “social keywords” to
announce, and it can change the announcement
itself any time.
• NO global unique network-wide identifier
– No unique IP address or email address in the
“network” layer
– Identity only in the application layer
• Relative Peering relationship only
– Local “link” identity
09/10/2007
Davis Social Links
30
DSL
• Let’s decide some of the “everything else”
– Global Flooding (w/o GRI)
• Then, we decide the possible candidates
for us to communicate
– Scope-limiting
• Finally, we rely on the Application layer to
nail down the “one” or “ones”.
09/10/2007
Davis Social Links
31
Multiple Social Links
BGP, Davis, California,
Intrusion Detection,…
Soccer, Wine, Bike,
Davis, California,…
09/10/2007
Davis Social Links
32
Policy-Driven Forwarding
BGP, Davis, California,
Intrusion Detection,…
Soccer, Wine, Bike,
Davis, California,…
09/10/2007
Davis Social Links
33
Propagation & Aggregation
09/10/2007
Davis Social Links
34
Aggregation
Ownership
Similar to Scope-Limited
Flooding in Gnutella/Freenet, but
more scalable with aggregation.
Ownership
09/10/2007
Davis Social Links
35
Scalability & Locality
???
soccer
Ownership
football
Ownership
09/10/2007
Davis Social Links
36
Scalability & Locality
Davis
soccer
Ownership
football
Ownership
09/10/2007
Davis Social Links
37
How to find “content X”?
Owner of X
Other Peers
Remember that under DSL there is no
such thing called “global identifier”.
09/10/2007
Davis Social Links
38
Use the right “keywords for X”!
soccer
Owner of X
Other Peers
Query
Davis
soccer
09/10/2007
Davis Social Links
39
Layering
Application
Application
TCP/IP
DSL Social Layer
Link
Social Link
Layer-2
IP-like
Traditional layer-2
09/10/2007
Davis Social Links
40
A Social/Overlay Link
09/10/2007
Davis Social Links
41
Davis - Washington DC - Sacramento
• Social path discovery
• Sending the real messages along the path
09/10/2007
Davis Social Links
42
Route Discovery
Keywords and aggregated keywords
.
.
.
.
“content addressable emails”
09/10/2007
Davis Social Links
43
Function F(incoming) = outgoing
Policy driven
Maybe itself a service
Davis CA
Northern California
001
002
Potential
Senders
Potential
Receivers
DSL ID
incoming
outgoing
001
Davis California
Japan
002
Japan
Northern California
003
09/10/2007
Davis Social Links
44
Forwarding: Source Routing
Sender:
Data packet SR
003, 001
09/10/2007
Davis Social Links
45
Forwarding: Source Routing
Sender:
Data packet SR
003, 001
001
003
09/10/2007
Davis Social Links
46
Privacy and Accountability
• No single intermediate node will have the
knowledge, at least in the network layer,
about “who is talking to who on what”.
– In DSL, no global identifier.
• However, the messages themselves contain
sufficient information to trace back toward
the “social path”, if necessary and nodes are
collaborative.
– BTW, this (tracing on a per packet/email basis) is
impossible for today’s Internet, even for “route
path”.
09/10/2007
Davis Social Links
47
09/10/2007
Davis Social Links
48
Problems with Overlay
• Triangle Overlay Routing
– Davis, Washington DC, Sacramento
– Traffic following the Social/Overlay path
• You can still bed DDoS’ed or Spammed!
– IP/email addresses are still there.
09/10/2007
Davis Social Links
49
MANET in Airport, Train, Flight
Application
DSL Social Layer
Social Link
Layer-2
Who has the 1307th piece of media X?
Promotion on new Pizza toppings A,B, & C!
Who has seen this lost baby girl in the past 3 minutes?
Who wants to play OK-bridge or Warcraft-III?
09/10/2007
Davis Social Links
50
DSL-wifi
• Link Established
– representing a neighbor relationship in the application
layer
A (WiFi)
09/10/2007
M (WiFi + WiMAX)
Davis Social Links
B (WiMAX)
51
MANET
• MANET (Mobile Ad Hoc Network)
– Network Layer Identify
WiFi
WiFi
WiFi
WiFi
WiFi
WiFi
09/10/2007
Davis Social Links
52
Infrastructure-less Content Sharing
• Conference/Meeting
– File Transfer
• Infrastructure Infrastructure-less
• Identification
A (WiFi)
M (WiFi + WiMAX)
09/10/2007
Davis Social Links
B (WiMAX)
53
DSL Routing
Application/Service Layer
Application/Service Layer
Transport Layer
Transport Layer
IP/Network Layer
Route and Discovery Layer
MAC Layer
MAC Layer
WiFi
WiMAX
xDSL
PON
WiFi
PHY Layer
WiFi
09/10/2007
WiMAX
xDSL
WiMAX
xDSL
PON
PHY Layer
PON
WiFi
Davis Social Links
WiMAX
xDSL
PON
54
DSL Keyword Propagation
D (WiFi+WiMAX)
C (WiMAX)
E (WiFi)
S (WiFi)
B (WiFi + Bluetooth)
A (Bluetooth)
F (WiFi + WiMAX)
09/10/2007
Davis Social Links
55
A “Relative” Identity under DSL
• “Key words” plus one DSL path
– Why will this be sufficient for
communication?
– Especially, when even the DSL
information itself is decentralized?
(I.e., in general, no one single DSL
router knows the complete DSL path.)
09/10/2007
Davis Social Links
56
09/10/2007
Davis Social Links
57
DSL in a Social Network
Davis
Soccer
Owner of X
Other Peers
Query
AppTest
09/10/2007
Davis Social Links
58
Examples
• I want to find all the pizza places in Davis.
– Can I do it without yet another service
provider?
– How about “unpopular topics”?
• Can I find the contact information for
Felix Wu in Davis (who is interested in
soccer)?
09/10/2007
Davis Social Links
59
DSL vs. Google
09/10/2007
Davis Social Links
60
“Google”
• It’s about the “content”
– Data-centric networking.
• Input to the Engine
– A set of key words characterizing the target
document.
• Output
– A set of documents/links matching the
keywords
09/10/2007
Davis Social Links
61
“DSL”
• It’s also about the “content”
– Application will decide the mechanism to
further the communication.
• Input to the Decentralized Engine
– A set of key words characterizing the target
document (plus the aggregation keywords).
• Output
– A set of DSL entities with the DSP (Davis
Social Path pointer) matching the keywords
09/10/2007
Davis Social Links
62
DSL Search Engine
Receiver or
Content
Sender or
Reader
DSL Social World
We are not just connecting the IP addresses!
We are connecting all the contents that can be interpreted!
09/10/2007
Davis Social Links
63
Google vs. DSL
• Google is essentially a “routing” framework
between the contents and their potential
consumers.
• Google decides how to extract the “key
words” from your (the owner) web page or
document.
09/10/2007
Davis Social Links
64
Google vs. DSL
• Google is essentially a “routing” framework
between the contents and their potential
consumers.
• Google decides how to extract the “key
words” from your (the owner) web page or
document.
• A DSL “owner/receiver to be” has the
complete control over that. A balance
between:
– How I would like others to know about me?
• And, I might want different folks to know me in
different ways!
– How I can differentiate myself from other Felix
09/10/2007 Wu?
Davis Social Links
65
Applications
• 911-like scenarios (power/infrastructure)
• Commercial and non-Commercial
Advertisements for the local community.
• Ad Hoc Peer-to-Peer Sharing without the
Internet!
09/10/2007
Davis Social Links
66
Unstructured P2P
Where is this piece of music?
What is the location of this content?
What is the current IP address of this
skype user?
09/10/2007
Davis Social Links
67
Structured P2P
09/10/2007
Davis Social Links
68
DHT-based BT Tracker
Sharing/Downloading
FreeBSD 5.4 CD images
Index key
(ContentDependent)
PUT & GET
09/10/2007
Davis Social Links
The owner of the
identifier matching
this hash entry will
be the tracker for
the corresponding
index key!
69
DHT-based P2P
PUT & GET
Index key
09/10/2007
Routing from a key
to an identifier
Davis Social Links
70
DHT vs. DSL
• DHT
– [Contents, Keys, Identifiers]
– Conceptually, we have a global hash table!
• DSL
– [Contents, Keys, Relative Identifiers]
– Social/trust relationships along the route path
09/10/2007
Davis Social Links
71
No Unique Identifier!!!
• Two peers might announced exactly the
same set of keywords!
• Both of them will receive the query, and
this might not be a problem.
• Usually, end2end applications can tell which
one (or ones) is really wanted.
09/10/2007
Davis Social Links
72
Trackerless BitTorrent
Owner of X
Other Peers
Query
AppTest
09/10/2007
Davis Social Links
73
09/10/2007
Davis Social Links
74
Tracker Volunteer
Content/Key
Tracker
Volunteer
Other Peers
Query
AppTest
09/10/2007
Davis Social Links
75
Tracker Volunteers
Content/Key
Tracker
Volunteers
Other Peers
Query
AppTest
09/10/2007
Davis Social Links
76
DSL-Torrent
• How to seed your torrent?
– Use DSL to search for all the volunteers
– You can screen out “unqualified” trackers by
not contacting them. (owner controllability)
• How to contact/select the tracker(s)?
– Use the keywords, of course
– But, use the right aggregation keywords to
reach the trackers closer to the “UCDavis”
social circle!
09/10/2007
Davis Social Links
77
09/10/2007
Davis Social Links
78
Tracking the BT clients
• Seed
• Tracker
• With Trackerless, the inspector might
become the tracker itself to record all the
IP addresses of the peers
– Traceability vs. Privacy
• How about DSL-Torrent?
09/10/2007
Davis Social Links
79
Applications
• 911-like scenarios (power/infrastructure)
• Commercial and non-Commercial
Advertisements for the local community.
• Ad Hoc Peer-to-Peer Sharing without the
Internet!
09/10/2007
Davis Social Links
80
Applications
• 911-like scenarios (power/infrastructure)
• Commercial and non-Commercial
Advertisements for the local community.
– What is a community?
• Ad Hoc Peer-to-Peer Sharing without the
Internet!
09/10/2007
Davis Social Links
81
Community-Oriented Social Network
• Peers sharing some common interests
• Communities intersect
• Community as a boundary for information
flow and policy
09/10/2007
Davis Social Links
82
Community-Oriented Social Network
• Peers sharing some common interests
• Communities intersect
• Community as a boundary for information
flow and policy
• How to establish a community?
• How to maintain the membership?
• How to set the inter- & intra- community
policy?
09/10/2007
Davis Social Links
83
Forming a Community
• “UCDavis as a community”
• “When should we have a community for
Aggie?”
– Davis, California, Aggie
09/10/2007
Davis Social Links
84
Scope-Limiting Keyword
Propagation
Davis
Soccer
09/10/2007
Davis Social Links
85
Scope-Limiting Keyword
Propagation/Flooding
Davis
Soccer
09/10/2007
Davis Social Links
86
Scope-Limiting Keyword
Propagation/Flooding
Davis
Soccer
09/10/2007
Davis Social Links
87
Penalization on Spams
• If Karl had forwarded lots of junk mails to
Felix, then Felix will lower the priority of
the social link between them.
• Karl will be informed about the downgrade.
• Karl needs to investigate “which messages”
(from which incoming DSLs) were causing
the downgrade and penalize toward the
sources.
09/10/2007
Davis Social Links
88
DSL Email
09/10/2007
Davis Social Links
89
DSL Route Discovery
& Trust Management
09/10/2007
DSL Forwarding Plane
Davis Social Links
90
Parallel/Overlay Communication
09/10/2007
Davis Social Links
91
DSL is an old idea!
A
B
We, as human, have been using similar
communication principles. Maybe it is a
good opportunity to re-think about our
cyber communication system.
Identity is a per-application, contextoriented, and sometime relative issue.
Forming cyber communities of interests for
application.
A
09/10/2007
F
F
Davis Social Links
F
B
92
DSL is still an old idea!
A
B
Many applications already have “social
network like” structure to enable P2P
sharing across Internet.
e.g., media sharing, on-line game,
restaurant recommendation,…
Should we push these into a generic Social
Network layer-3 to support all the
applications?
A
09/10/2007
F
F
Davis Social Links
F
B
93
A Different Internet?!
• Current Internet: every IP address will be
able to communicate with every other IP
address!
– Allow by Default
• DSL-based “Internet”: we have a large
number of “pairs” (two entities and their
corresponding direct social link)
– Deny by Default
09/10/2007
Davis Social Links
94
Comparison
• IP/email:
– Convergence to an absolute consistent state
– IP/email addresses are all you need, but the
controllability is biased toward the sender
• DSL:
– Convergence to a relative consistent state
– No global network identity. Every DSL entity
defines its own relative identity based on origin
keywords.
– Controllability is more balanced with other
application challenges.
09/10/2007
Davis Social Links
95
Spam on DSL
• Still needs much more evaluation on how
the spammer can exploit the DSL
framework.
• But, maybe some spammers will no longer
spam economically!
– Social network will give the merchants much
better channels to send their advertisements!
– Using spam to deliver product information over
DSL might seriously hurt the sales on the social
channels.
– Still there will still be some global spam
activities.
09/10/2007
Davis Social Links
96
09/10/2007
Davis Social Links
97
Acknowledgement
A
Lerone Banks
Dimitri DeFigueiredo
Felix Huang
Juan Lang
Xiaoming Lu
Matt Spear
Shih-Ming Tsang
Shawn Ye
B
more info: [email protected]
A
09/10/2007
F
F
Davis Social Links
F
B
98
Questions?
[email protected] or DSL to me
09/10/2007
Davis Social Links
99