[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd...
From: |
Hermanni Hyytiälä |
Subject: |
[Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd... |
Date: |
Thu, 30 Jan 2003 07:01:23 -0500 |
CVSROOT: /cvsroot/gzz
Module name: gzz
Changes by: Hermanni Hyytiälä <address@hidden> 03/01/30 07:01:17
Modified files:
Documentation/misc/hemppah-progradu: progradu.bib
research_problems
Log message:
Misc notes and more refs
CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/progradu.bib.diff?tr1=1.58&tr2=1.59&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.37&tr2=1.38&r1=text&r2=text
Patches:
Index: gzz/Documentation/misc/hemppah-progradu/progradu.bib
diff -u gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.58
gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.59
--- gzz/Documentation/misc/hemppah-progradu/progradu.bib:1.58 Wed Jan 29
07:45:31 2003
+++ gzz/Documentation/misc/hemppah-progradu/progradu.bib Thu Jan 30
07:01:17 2003
@@ -1334,7 +1334,7 @@
@inProceedings{saia02dynamicfaultcontentnetwork,
title = "Dynamically Fault-Tolerant Content Addressable Networks",
- author = "Jared Saia, Amos Fiat, Steve Gribble, Anna Karlin, Stefan
Saroiu",
+ author = "Jared Saia, Amos Fiat, Steven Gribble, Anna Karlin, Stefan
Saroiu",
booktitle = {The 1st International Workshop on Peer-to-Peer Systems
(IPTPS'02)},
month = {March},
year = {2002},
@@ -1711,4 +1711,11 @@
url =
{http://www.cs.cornell.edu/info/projects/spinglass/public_pdfs/Kelips.pdf}
}
-
address@hidden,
+ author = {T.S. Eugene Ng, Hui Zhang},
+ title = {Predicting Internet network distance with coordiantes-based
approaches},
+ booktitle = {The 21st Annual Joint Conference of the IEEE Computer
and Communications Societies (INFOCOM '02)},
+ location = {New York, USA},
+ year = {2001},
+ url = {http://www.ieee-infocom.org/2002/papers/785.pdf}
+}
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.37
gzz/Documentation/misc/hemppah-progradu/research_problems:1.38
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.37 Tue Jan
28 08:17:24 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems Thu Jan 30
07:01:17 2003
@@ -153,19 +153,23 @@
This summary table is far from complete (and from total truth)
-Protocol: Insert/Delete Space Search # of network
connections
-Chord: O(log^2 n) O(log n) O(log n) 2(log n)
-CAN: O(d) O(d) O(dn^(1/d)) 2d
-Pastry: O(log^2 n) O(log n) O(log n) (2^b - 1)(log
n)/b
-Tapestry: O(log^2 n) O(log n) O(log n) (2^b - 1)(log
n)/b
-Kademlia: O(log n)* O(log n) O(log n) 2(log n)
-Viceroy: O(log n) O(1) O(log n) 11
-SWAN 1): O(1) O(1) O(log^2 n) r(2b+2s+2l)
(r=# of resurces provided, b=boot, s=short, l=long), typical link conf:
2*(6+7+8)=36
-Flooding: O(1) O(1) O(n)** typical conf:
5, depends on implementation --> 2*5=10 total
-Social: O(1)*** O(1)*** N/A*** can be
1-10000 connections (aka social connections, connections are permament)
-Skip graphs 1): O(log n) O(log n) O(log n) 4r(log n) +
(log n) (r=# of resurces provided)
-Symphony: O(log^2 n) O(log n)**** O(log n) 2k+2+f (k =
long, 2 = node's neighbors, f = fault-tolerance links)
-Plaxton et al: not supported O(log n) O(log n) 2(log n)
+Protocol: Insert/Delete Space Search
# of network connections
+Chord: O(log^2 n) O(log n) O(log n)
2(log n)
+CAN: O(d) O(d) O(dn^(1/d))
2d
+Pastry: O(log^2 n) O(log n) O(log n)
(2^b - 1)(log n)/b
+Tapestry: O(log^2 n) O(log n) O(log n)
(2^b - 1)(log n)/b
+Kademlia: O(log n)* O(log n) O(log n)
2(log n)
+Viceroy: O(log n) O(1) O(log n)
11
+SWAN 1): O(1) O(1) O(log^2 n)
r(2b+2s+2l) (r=# of resurces provided, b=boot, s=short, l=long), typical link
conf: 2*(6+7+8)=36
+Flooding: O(1) O(1) O(n)**
typical conf: 5, depends on implementation --> 2*5=10 total
+Social: O(1)*** O(1)*** N/A***
can be 1-10000 connections (aka social connections, connections are
permament)
+Skip graphs 1): O(log n) O(log n) O(log n)
4r(log n) + (log n) (r=# of resurces provided)
+SkipNet: O(log n)
+Symphony: O(log^2 n) O(log n)**** O(log n)
2k+2+f (k = long, 2 = node's neighbors, f = fault-tolerance links)
+ODHDHT 2): O(log n) O(log n) O(log n)/O(log^2 n)
2(log n)
+Plaxton et al 3): not supported O(log n) O(log n)
2(log n)
+PeerNet 4): O(log n) O(log n) O(log n)
O(log n)
+Kelips: ***** O(sqrt(n)) O(1)
n/sqrt(n) + c*(sqrt(n)-1) + 'Total number of files'/sqrt(n)
* = In Kademlia, there is no action required when nodes leaves the system
@@ -175,8 +179,16 @@
**** = Can be also O(1). Additional space of 'space^2' can be used as a
lookahed list for better performance
+***** = constant background overhead is: O(2(sqrt(n)*(log^2 n)) + (sqrt(n) +
(log^3 n))) (which includes convergence times for insertion/deletion of node)
+
1) = In these approaches, node is treated as 'named resource'; in this
approach, *resources* self-organise (opposite to DHTs).
-E.g., in Skip graphs, a peer (i.e. computer) needs 2k(log n) space for k
resources. SWAN requires O(1) space..
+E.g., in Skip graphs, a peer (i.e. computer) needs 2k(log n) space for k
resources. SWAN requires O(1) space..
+
+2) = There are two lookup algorithms. The other is log n, which is robus under
random deletion. The second is (log^2 n), which is also robust under spam
generating model
+
+3) = Plaxton's algortihm is designed to operate in static environment (web
cache)
+
+4) = Operates at network layer (not application level)
- - -
> Btw, how well Alpine can scale (e.g. number of users) ? Do you have any
> "real-
@@ -814,6 +826,7 @@
Solution:
-SkipNet is able to self-organise after a organization has been disconnected
from the network
-However, SkipNet uses Pastry as routing layer. Kademlia/Symphony would be
better choice
+-network partitions: techniques for maintaining DHT structure in real and
dynamic environment \cite{rowston03controlloingreliability}
Tuomas' example scenario #3:
'What will happen if a malicious node quantities large amounts of data in the
system ?'
@@ -822,7 +835,7 @@
1) centralized: Per node based quotas based on reliable identification of
publishers (usually requires CAs to work correctly)
2) decentralized: Per node based quotas based on the ip address of the node
-It seems to be that DHTs are unable to self-reorganise after a sudden
partitioning, because
+It seems to be that DHTs are unable to self-reorganise rapidly after a sudden
partitioning, because
a) every node has a fixed space in identifier space
b) system has a fixed identifier space, e.g. Pastry and Chord require a priori
knowledge about the size of the system
c) even if system is able self-reorganise, the key space is not uniformly
distributed anymore -> all nodes have to leave/rejoin --> lot of traffic
@@ -833,12 +846,26 @@
copying
-The question is: how well SWAN can self-organise, e.g. in the case of Tuomas'
scanario #2 ?
+Network proximity:
+-\cite{pias03lighthouse}, \cite{ng02predicting}
+
+Efficient searching:
+-result caching and view trees \cite{Bhattacharjee03resultcache} (insight:
store and and retrieve prior results from view tree)
+-bloom filters \cite{362692}
+
+Better load balancing techiques:
+-Better and simple load balancing \cite{byers03dhtbalancing} (insight: "power
of two choices" whereby an item is stored at the less loaded of two (or more)
random alternatives)
+
+One question is: how well SWAN can self-organise, e.g. in the case of Tuomas'
scanario #2 ?
Half-life phenomenon \cite{libennowell01observations}
Current decentralized, but structured \cite{chord, can, pastry, Tapestry etc.)
ignores the fact
that a P2P system is never in 'ideal' state. P2P system is always evolving
system.
+-techniques for maintaining DHT structure in real and dynamic environment
\cite{rowston03controlloingreliability}
+-this is not problem any more for structured p2p overlay networks
+-results can be directly applied to other DHTs
+
Half-life concept:
'Let there be N live nodes at time t. The doubling from time t is the time
that pass before
N new additional nodes arrive into the system. The halving time from time t is
the time
@@ -883,7 +910,9 @@
-e.g. -there is a single point of routing failure in these approaches
(h hops, little amount f of system are adversial)
-make searching/query model more flexible (keyword searching)
-use keywords/range searches instead of exact keys
- proposal for range searches: Scalable, Efficient Range Queries for Grid
Information Services \cite{andrzejak02rangequeries}
+ -proposal for range searches: Scalable, Efficient Range Queries for
Grid Information Services \cite{andrzejak02rangequeries}
+ -proposal for broadcast operation in DHT-based systems
\cite{ansaryefficientbroadcast03} (insight: k-ary tree is a spanning tree,
traverse spanning tree)
+ -proposal for complex queries in DHTs \cite{harren02complex} (insight:
use SQL-like mechanisms)
2) Decentralized, but unstructured
-make routing more scalable: reach more nodes, create less traffic
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., (continued)
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/24
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/27
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/27
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/27
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/28
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/28
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/28
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/29
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/29
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd...,
Hermanni Hyytiälä <=
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/30
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/31
- [Gzz-commits] gzz/Documentation/misc/hemppah-progradu prograd..., Hermanni Hyytiälä, 2003/01/31