[Gzz-commits] gzz/Documentation/misc/hemppah-progradu mastert...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/02/12 06:11:12

Modified files:
        Documentation/misc/hemppah-progradu: masterthesis.tex 
                                             research_problems 
Added files:
        Documentation/misc/hemppah-progradu: 
                                             application_level_overlay.eps 

Log message:
        Application overlay figure, finished tables

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/application_level_overlay.eps?rev=1.1
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.36&tr2=1.37&r1=text&r2=text
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.57&tr2=1.58&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.36 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.37
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.36       Tue Feb 
11 09:42:58 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Wed Feb 12 
06:11:11 2003
@@ -702,149 +702,166 @@
 \multicolumn{1}{|c|}{\textbf{Protocol}} &
 \multicolumn{1}{c|}{\textbf{Insert/Delete}} & 
 \multicolumn{1}{c|}{\textbf{Space}} & 
-\multicolumn{1}{c|}{\textbf{Search}} &
+\multicolumn{1}{c|}{\textbf{Lookup}} &
 \multicolumn{1}{c|}{\textbf{\# of network connections}} &
 \multicolumn{1}{c|}{\textbf{Notes}}
 \\ \hline
 
 \parbox{37pt}{Chord} &
 \parbox{37pt}{$O(\log^2{n})$} &
-\parbox{37pt}{$O$(log $n$)} &
-\parbox{37pt}{$O$(log $n$)} &
-\parbox{50pt}{2(log $n$)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n}$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{2$(\log{n})$} &
+\parbox{85pt}{}
 \\ \hline
 
 \parbox{37pt}{CAN} &
 \parbox{37pt}{$O$($d$)} &
 \parbox{37pt}{$O$($d$)} &
 \parbox{37pt}{$O(dn^{\frac{1}{d}})$} &
-\parbox{50pt}{2$d$} &
-\parbox{50pt}{}
+\parbox{85pt}{2$d$} &
+\parbox{85pt}{}
 \\ \hline
 
 \parbox{37pt}{Pastry} &
 \parbox{37pt}{$O(\log^2{n})$} &
-\parbox{37pt}{$O$(log $n$)} &
-\parbox{37pt}{$O$(log $n$)} &
-\parbox{50pt}{$2^{b - 1}\frac{\log{n}}{b}$} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$} &
+\parbox{85pt}{}
 \\ \hline
 
 \parbox{37pt}{Tapestry} &
 \parbox{37pt}{$O(\log^2{n})$} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{$2^{b - 1}\frac{\log{n}}{b}$} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$} &
+\parbox{85pt}{}
 \\ \hline
 
 \parbox{37pt}{Kademlia} &
-\parbox{37pt}{$O$(log n)*} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{2(log n)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$2(\log{n})$} &
+\parbox{85pt}{There is no action required when nodes leaves the system}
 \\ \hline
 
 \parbox{37pt}{Viceroy} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{11} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{11} &
+\parbox{85pt}{}
 \\ \hline
 
 \parbox{37pt}{SWAN} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(1)} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(\log^2{n})$} &
-\parbox{50pt}{r(2b+2s+2l) (r=\# of resurces provided, b=boot, s=short, 
l=long), typical link conf: 2*(6+7+8)=36} &
-\parbox{50pt}{}
+\parbox{85pt}{$r(2b+2s+2l)$ (r=\# of resurces provided, b=boot, s=short, 
l=long), typical link conf: 2*(6+7+8)=36} &
+\parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
 \\ \hline
 
 \parbox{37pt}{Gnutellas} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(n)} &
-\parbox{50pt}{typical conf: 5, depends on implementation --> 2*5=10 total} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(n)$} &
+\parbox{85pt}{typical conf: 5, depends on implementation --> 2*5=10 total} &
+\parbox{85pt}{Number of messages can grow as fast as $O(n^{2})$}
 \\ \hline
 
 \parbox{37pt}{Social} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(n)} &
-\parbox{50pt}{can be 1-10000 connections (aka social connections, connections 
are permament)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(n)$} &
+\parbox{85pt}{can be 1-10000 connections (aka social connections, connections 
are permament)} &
+\parbox{85pt}{}
 \\ \hline
 
 \parbox{37pt}{Skip Graphs} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{4r(log n) + (log n) (r=\# of resurces provided)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$4r(\log{n}) + (\log{n})$ (r=\# of resurces provided)} &
+\parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
 \\ \hline
 
 \parbox{37pt}{SkipNet} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{2(log n)} &
-\parbox{50pt}{} 
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$2(\log{n})$} &
+\parbox{85pt}{} 
 \\ \hline
 
 \parbox{37pt}{Symphony} &
 \parbox{37pt}{$O(\log^2{n})$} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{2k+2+f (k = long, 2 = node's neighbors, f = fault-tolerance 
links)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$2k+2+f$ (k = long, 2 = node's neighbors, f = fault-tolerance 
links)} &
+\parbox{85pt}{Space can be also $O(1)$. Additional space of $space^2$ can be 
used as a lookahed list for better performance}
 \\ \hline
 
 \parbox{37pt}{ODHDHT} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)/O(log\^2 n)} &
-\parbox{50pt}{2(log n)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$2(\log{n})$} &
+\parbox{85pt}{There are two lookup algorithms. The other is $O(\log{n})$, 
which is robus under random deletion. The second is $O(\log^2{n})$, which is 
also robust under spam generating model}
 \\ \hline
 
 \parbox{37pt}{Plaxton} &
 \parbox{37pt}{-} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{$O$(log n)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$O(\log{n})$} &
+\parbox{85pt}{Plaxton's algortihm is designed to operate in static environment}
 \\ \hline
 
 \parbox{37pt}{PeerNet} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{37pt}{$O$(log n)} &
-\parbox{50pt}{$O$(log n)} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{37pt}{$O(\log{n})$} &
+\parbox{85pt}{$O(\log{n})$} &
+\parbox{85pt}{Operates at network layer}
 \\ \hline
 
 \parbox{37pt}{Kelips} &
 \parbox{37pt}{} &
 \parbox{37pt}{$O$($\sqrt{n}$)} &
 \parbox{37pt}{$O$(1)} &
-%\parbox{50pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{Totalnumber of 
files}{\sqrt{n}}$} &
-\parbox{50pt}{}
+\parbox{85pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{Totalnumber of 
files}{\sqrt{n}}$} &
+\parbox{85pt}{Constant background overhead is: $O(2(\sqrt{n}*(log^2{n})) + 
(\sqrt{n} + (log^3{n})))$}
 \\ \hline
 
 \parbox{37pt}{Freenet} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(1)} &
-\parbox{37pt}{$O$(n)} &
-\parbox{50pt}{??} &
-\parbox{50pt}{}
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(1)$} &
+\parbox{37pt}{$O(n)$} &
+\parbox{85pt}{??} &
+\parbox{85pt}{}
 \\ \hline 
 
 
 \end{longtable}
+
+Insert/Delete: 
+Number of messages when a node joins or leaves the network.
+
+Space: 
+Space required for a node's neighbors
+
+Search: 
+Number of messages when an object lookup is performed
+
+\begin{figure}
+\centering
+\includegraphics[width=10cm, height=10cm]{application_level_overlay.eps}
+\caption{P2P Application Level Overlay}
+\label{fig:application_level}
+
+\end{figure}
 
 
 
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.57 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.58
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.57      Tue Feb 
11 09:46:12 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Wed Feb 12 
06:11:11 2003
@@ -190,7 +190,7 @@
 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)        O(log n)        O(log n)                
2(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)
+ODHDHT 2):             O(log n)        O(log n)        O(log 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)
@@ -346,7 +346,7 @@
 
 **** = 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)
+***** = 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).