[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/17 08:34:16

Modified files:
        Documentation/misc/hemppah-progradu: masterthesis.tex 

Log message:
        Fixes

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/masterthesis.tex.diff?tr1=1.43&tr2=1.44&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.43 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.44
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.43       Fri Feb 
14 08:32:53 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Mon Feb 17 
08:34:16 2003
@@ -12,6 +12,7 @@
 \usepackage{url}
 \usepackage{booktabs}
 \usepackage{longtable}
+\usepackage{verbatim}
 
 %***********************
 %   Tyyliluokan pakolliset määritykset
@@ -383,10 +384,10 @@
 
 
 
-\parbox{90pt}{Routing} &                       
+\parbox{90pt}{Query routing} &                 
 \parbox{110pt}{Incorrect forwarding (hostile), incorrect routing (hostile)} &
 \parbox{110pt}{Query monitoring, cross check routing tables, verify routing 
tables, create routing table invariants} &
-Increases system complexity 
+\parbox{110pt}{Increases system complexity} 
 \\ \hline
 
 
@@ -420,14 +421,14 @@
 
 \parbox{90pt}{Sudden network partition} &
 \parbox{110pt}{Sub network is isolated from other network because of network 
disconnection} &
-\parbox{110pt}{Self-tuning, environment observatorion, backup connections} &
+\parbox{110pt}{Self-tuning, environment observatorion, localized network 
connection for minimun latency (backup connections)} &
 \parbox{110pt}{Creates more overhead/space requirements per node}
 \\ \hline
                 
 
 \parbox{90pt}{Searching} &
 \parbox{110pt}{Efficient searching requires exploiting of previous queries} &
-\parbox{110pt}{View trees, bloom filters its variations} &
+\parbox{110pt}{View trees, bloom filters and its variations} &
 \parbox{110pt}{Effective, but not flexible}
 \\ \hline
 
@@ -435,27 +436,27 @@
 \parbox{90pt}{Efficient data discovery} &
 \parbox{110pt}{Find resources efficiently, if resource exists (broadcasting)} &
 \parbox{110pt}{Super nodes, node clusters, caching techiques} &
-\parbox{110pt}{More effiecient, less network traffic, not comparable to DHT's 
efficiency}
+\parbox{110pt}{More efficient, less network traffic, not comparable to DHT's 
efficiency}
 \\ \hline
        
 
 \parbox{90pt}{Entity identification} &
 \parbox{110pt}{Identify participating entities reliably and efficiently        
} &
-\parbox{110pt}{Digital signatures, key infrastrucure} &
+\parbox{110pt}{Digital signatures, key infrastructure} &
 \parbox{110pt}{Not practically realizable}
 \\ \hline
                
 
 \parbox{90pt}{Fail Stop} &
 \parbox{110pt}{A faulty node stops working} &
-\parbox{110pt}{Environment observatorion, informing protocols} &
-\parbox{110pt}{Creates more network traffics, node's information can be 
outdated}
+\parbox{110pt}{Failure detectors, informing protocols} &
+\parbox{110pt}{Creates more network traffics, node's information can be 
outdated, failure detectors not reliable}
 \\ \hline
 
 
 \parbox{90pt}{Byzantine faults} &
 \parbox{110pt}{Faulty nodes may behave arbitrarily} &
-\parbox{110pt}{Byzantine replication protocols } &
+\parbox{110pt}{Byzantine replication protocols -> get information from 
multiple entities, trust majority's opinion} &
 \parbox{110pt}{Much research has been done on this field, practical solutions, 
decreases system's, performance slighly}
 \\ \hline
 
@@ -468,21 +469,21 @@
 
 
 \parbox{90pt}{Robustness} &
-\parbox{110pt}{How well system performs under hostile attacks/in the case of 
severe failure ?  } &
-\parbox{110pt}{Self-tuning, backup links, use diverse routing paths} &
+\parbox{110pt}{How well system performs under hostile attacks/in the case of 
severe failure ?} &
+\parbox{110pt}{Self-tuning, backup links, use diverse routing paths, power-law 
networks/properties} &
 \parbox{110pt}{Working solutions}
 \\ \hline
 
 
 \parbox{90pt}{Quality of Service} &
-\parbox{110pt}{The system cannot promise the quality of service in all cases} &
-\parbox{110pt}{Use Network proximity for better network performance 
(bandwidth, latency, jitter, packet loss)} &
-\parbox{110pt}{Increases system complexity, no real world experiences}
+\parbox{110pt}{The system can only provide (at most) best effort services)} &
+\parbox{110pt}{Use network proximity for better network performance 
(bandwidth, latency, jitter, packet loss)} &
+\parbox{110pt}{Increases system complexity, some initial experiences, need 
more research}
 \\ \hline
 
 
-\parbox{90pt}{Data availability} &
-\parbox{110pt}{Data might be temporary unavailable, or lost permanently} &
+\parbox{90pt}{Data availability/persistency} &
+\parbox{110pt}{Data might be temporarily unavailable, or lost permanently} &
 \parbox{110pt}{Data caching, data replication} &
 \parbox{110pt}{Working solutions, but creates more traffic and overhead per 
node}
 \\ \hline
@@ -491,7 +492,7 @@
 \parbox{90pt}{Data integrity/authenticity} &
 \parbox{110pt}{Integrity/originality of data is unknown} &
 \parbox{110pt}{Cryptographic content hashes, key architectures} &
-\parbox{110pt}{For data integrity, there are working solutions, for data 
authenticity, there are not working solutions/there are partial solutions, 
which are not practically realizable}
+\parbox{110pt}{For data integrity, there are working solutions, but for data 
authenticity, some of the solutions are partial, which may be practically 
realizable}
 \\ \hline
 
 
@@ -503,15 +504,16 @@
 
 
 \parbox{90pt}{Malicious nodes} &
-\parbox{110pt}{There are malicious nodes in the system how we are able to 
discover them ?} &
+\parbox{110pt}{How to identify malicious nodes in the system} &
 \parbox{110pt}{Create invariants for node behaviour, verify invariants, 
self-certifying data} &
 \parbox{110pt}{Partial solutions, self-certifying data most realiable}
 \\ \hline
 
 
+
 \parbox{90pt}{Mutual distrust} &
-\parbox{110pt}{Nobody trust anybody} &
-\parbox{110pt}{Different reputation methods, key infrastructures} &
+\parbox{110pt}{Nobody trusts anybody} &
+\parbox{110pt}{Reputation methods, key infrastructures} &
 \parbox{110pt}{Resource demanding, not practical to implement/not working 
solutions, no real world experience in a wide scale}
 \\ \hline
 
@@ -525,7 +527,7 @@
 
 \parbox{90pt}{Heterogeneity} &
 \parbox{110pt}{There are different kind of nodes in the system, in light of 
bandwidth and computing power} &
-\parbox{110pt}{Super peers (broadcasting), cluster (broadcasting) additional 
layer upn DHT, structural simplicity (DHTs)} &
+\parbox{110pt}{Super peers (broadcasting), cluster (broadcasting) additional 
layer upon DHTs, structural simplicity (DHTs)} &
 \parbox{110pt}{Working solutions, increases system complexity (additional 
layer)}
 \\ \hline
 
@@ -533,12 +535,12 @@
 \parbox{90pt}{Network proximity} &
 \parbox{110pt}{Can we take account the underlying network's properties better 
when forming overlay network (network-awareness for performance) ?} &
 \parbox{110pt}{Global Network Positioning, Lighthouse technique, trianqulated 
heuristics} &
-\parbox{110pt}{Increases system complexity, no real world experience in a wide 
scale}
+\parbox{110pt}{Increases system complexity, no real world experience in a wide 
scale, proposed solutions are susceptible to single point of failure}
 \\ \hline
 
 
 \parbox{90pt}{Locality} &
-\parbox{110pt}{In the case on DHTs, can we take account locality ?} &
+\parbox{110pt}{Could DHTs exploit locality properties better ?} &
 \parbox{110pt}{Constrained Load Balancing, using network properties for 
nearest neighbor selection} &
 \parbox{110pt}{Working solutions}
 \\ \hline
@@ -561,72 +563,81 @@
 \parbox{90pt}{Programming guidelines} &
 \parbox{110pt}{Set of programming guidelines/frameworks is needed for better 
interoperability between different systems} &
 \parbox{110pt}{Common frameworks and APIs} &
-\parbox{110pt}{Common framework/API is still missing, a lot of proposals has 
been made}
+\parbox{110pt}{Common framework/API is still missing, a lot of proposals have 
been made}
 \\ \hline
 
 
 \parbox{90pt}{Access Control} &
 \parbox{110pt}{Can we define access control levels in peer-to-peer network ?} &
-\parbox{110pt}{-} &
-\parbox{110pt}{Working solutions are missing, mainly because they are hard/not 
practically realizable}
+\parbox{110pt}{Schema-based rules} &
+\parbox{110pt}{Some initial experiences, need more research}
 \\ \hline
 
 
 \parbox{90pt}{System in flux} &
 \parbox{110pt}{Nodes join and leave system constantly: load balancing, 
efficiency ?} &
 \parbox{110pt}{Half-life phenomenon (for analysis), simple overlay maintenance 
and construction protocol} &
-\parbox{110pt}{Initial theoretical anasysis has been created, but not 
comprehensive model for analysing different system states}
+\parbox{110pt}{Initial theoretical analysis have been created, but not 
comprehensive model for analysing different system states and its variations 
(e.g. complex usage patterns)}
 \\ \hline
 
 
 \parbox{90pt}{Inconsistent behaviour} &
-\parbox{110pt}{Hostile node could act correctly with its neighbors, but 
incorrectly with other} &
+\parbox{110pt}{Hostile node could act correctly with its neighbors, but 
incorrectly with others} &
 \parbox{110pt}{Public keys, digital signatures} &
 \parbox{110pt}{Not practical approach/working proposal created yet}
 \\ \hline
 
 
 \parbox{90pt}{Hostile groups} &
-\parbox{110pt}{Joining node may join parallel network, formed a group of 
hostile nodes} &
-\parbox{110pt}{Use trusted nodes, based on history information} &
-\parbox{110pt}{Not 100\% sure if Centreal Authority is missing}
+\parbox{110pt}{Joining node may join parallel network, formed a group of 
hostile nodes, hostile node(s) controls the construction of the network} &
+\parbox{110pt}{Use trusted nodes, based on history information, Cryptography, 
key infrastructure} &
+\parbox{110pt}{Not 100\% sure if Centreal Authority (CA) is missing, not 
practical approach/working proposal created yet}
 \\ \hline
 
 
 \parbox{90pt}{External threats} &
-\parbox{110pt}{Viruses, troijans, sniffers} &
+\parbox{110pt}{Viruses, trojans, sniffers} &
 \parbox{110pt}{Data integrity/authenticity, distributed antivirus software} &
 \parbox{110pt}{Not much research has been done on this}
 \\ \hline
 
 
-\parbox{90pt}{Illegal overlay construction} &
-\parbox{110pt}{Hostile node(s) controls the construction of the network} &
-\parbox{110pt}{Cryptography, key infrastructure} &
-\parbox{110pt}{Not practical approach/working proposal created yet}
+\parbox{90pt}{Comprehensive simulations/analysis of peer-to-peer network} &
+\parbox{110pt}{Ability to simulate whole p2p network's usage patterns, network 
traffics, flux state etc} &
+\parbox{110pt}{Use same techniques as simulating/analysing the Internet} &
+\parbox{110pt}{Only small subset of peer-to-peer networks has been able to 
analyse, because of ad hoc properties of network, more poweful solutions needed}
 \\ \hline
 
+\parbox{90pt}{How to locate existing network} &
+\parbox{110pt}{Ability to simulate whole p2p network's usage patterns, network 
traffics, flux state etc} &
+\parbox{110pt}{gnutellahosts.com} &
+\parbox{110pt}{Only small subset of peer-to-peer networks has been able to 
analyse, because of ad hoc properties of network, more poweful solutions needed}
+\\ \hline
 
-\parbox{90pt}{Comprehensive simulations/analysis of peer-to-peer network} &
+\parbox{90pt}{Overlay management} &
 \parbox{110pt}{Ability to simulate whole p2p network's usage patterns, network 
traffics, flux state etc} &
-\parbox{110pt}{Use same techniques as simulating/analysing the Internet} &
+\parbox{110pt}{gnutellahosts.com} &
 \parbox{110pt}{Only small subset of peer-to-peer networks has been able to 
analyse, because of ad hoc properties of network, more poweful solutions needed}
 \\ \hline
-               
+
+
+
 
 \end{longtable}
 
 
 
 
+
 \begin{longtable}{|l|l|l|}
 \caption[Comparison of Broadicasting and Structured approaches]{Comparison of 
Broadicasting and Structured approaches} 
 \label{table_comparison_approach} \\
 
 \hline 
-\multicolumn{1}{|c|}{\textbf{Property}} & 
-\multicolumn{1}{c|}{\textbf{Structured}} & 
-\multicolumn{1}{c|}{\textbf{Broadcast}} 
+\multicolumn{1}{|c|}{\textbf{Property}} &
+\multicolumn{1}{c|}{\textbf{Unstructured}} & 
+\multicolumn{1}{c|}{\textbf{Structured}}  
+ 
 \\ \hline 
 \endfirsthead
 
@@ -634,8 +645,8 @@
 {{\tablename\ \thetable{} -- continued from previous page}} \\
 \hline 
 \multicolumn{1}{|c|}{\textbf{Property}} &
-\multicolumn{1}{c|}{\textbf{Structured}} &
-\multicolumn{1}{c|}{\textbf{Broadcast}}  
+\multicolumn{1}{c|}{\textbf{Unstructured}} &
+\multicolumn{1}{c|}{\textbf{Structured}}
 \\ \hline 
 \endhead
 
@@ -643,60 +654,64 @@
 
 
 
-
 \parbox{90pt}{Queries} &
-\parbox{100pt}{Controlled} &
-\parbox{100pt}{Uncontrolled} 
+\parbox{100pt}{Uncontrolled} &
+\parbox{100pt}{Controlled}  
 \\ \hline
 
 \parbox{90pt}{A way for performing queries} &
-\parbox{100pt}{Exact keys} &
-\parbox{100pt}{Keywords}
+\parbox{100pt}{Keywords} &
+\parbox{100pt}{Exact keys} 
 \\ \hline
          
 \parbox{90pt}{Query traffic} &
-\parbox{100pt}{O(1)/O(log n)} &
-\parbox{100pt}{O(n)/O(n\^2)}
+\parbox{100pt}{$O(n)/O(n^{2})$}  &
+\parbox{100pt}{$O(1)/O(log n)$} 
 \\ \hline
 
-\parbox{90pt}{Will find the data item ?} &
-\parbox{100pt}{Yes} &
-\parbox{100pt}{Not necessarily}
+\parbox{90pt}{Guaranteed data lookup} &
+\parbox{100pt}{Not necessarily} &
+\parbox{100pt}{Yes} 
 \\ \hline
 
 \parbox{90pt}{Overlay's structure} &
-\parbox{100pt}{Controlled and structured} &
-\parbox{100pt}{Uncontrolled and ad hoc}
+\parbox{100pt}{Uncontrolled and ad hoc}  &
+\parbox{100pt}{Controlled and structured}
 \\ \hline
                  
 \parbox{90pt}{Max. number of nodes} &
-\parbox{100pt}{Billions} &
-\parbox{100pt}{Millions}
+\parbox{100pt}{Millions} &
+\parbox{100pt}{Billions} 
 \\ \hline
                        
 \parbox{90pt}{Data placement} &
-\parbox{100pt}{Not local} &
-\parbox{100pt}{Local}
+\parbox{100pt}{Local} &
+\parbox{100pt}{Not local} 
 \\ \hline
                  
-\parbox{90pt}{Support for heterogeneiy} &
-\parbox{100pt}{No} &
-\parbox{100pt}{Yes}
+\parbox{90pt}{Support for heterogeneity} &
+\parbox{100pt}{Yes} &
+\parbox{100pt}{No} 
 \\ \hline
        
 \parbox{90pt}{Support for locality} &
-\parbox{100pt}{Partial}        &
-\parbox{100pt}{No}
+\parbox{100pt}{Yes} &
+\parbox{100pt}{Partial}        
 \\ \hline
          
-\parbox{90pt}{Possibilty for routing hotspots} & 
-\parbox{100pt}{Yes} &
-\parbox{100pt}{No}
+\parbox{90pt}{Possibility for routing hotspots} &
+\parbox{100pt}{No} &
+\parbox{100pt}{Yes} 
 \\ \hline
        
 \parbox{90pt}{Design/Implementation complexity} &
+\parbox{100pt}{Low} &
+\parbox{100pt}{High} 
+\\ \hline
+
+\parbox{90pt}{Fault-tolerant} &
 \parbox{100pt}{High} &
-\parbox{100pt}{Low}
+\parbox{100pt}{High}
 \\ \hline
 
 \end{longtable}
@@ -705,8 +720,8 @@
 
 
 \begin{longtable}{|l|c|c|c|c|l|}
-\caption[Comparison of Broadicasting and Structured approaches]{Comparison of 
Broadicasting and Structured approaches} 
-\label{table_comparison_approach} \\
+\caption[Different peer-to-peer lookup protocols]{Different peer-to-peer 
lookup protocols} 
+\label{table_p2p_protocols} \\
 
 \hline
 \multicolumn{1}{|c|}{\textbf{Protocol}} &
@@ -745,14 +760,14 @@
 \parbox{37pt}{$O$($d$)} &
 \parbox{37pt}{$O(dn^{\frac{1}{d}})$} &
 \parbox{85pt}{2$d$} &
-\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
+\parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner, where $d$ is the 
dimension of virtual key space}
 \\ \hline
 
 \parbox{37pt}{Pastry} &
 \parbox{37pt}{$O(\log^2{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$} &
+\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$, where $b$ is a configurable 
parameter for tuning digit-fixing properties (routing table)} &
 \parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
 \\ \hline
 
@@ -760,7 +775,7 @@
 \parbox{37pt}{$O(\log^2{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
 \parbox{37pt}{$O(\log{n})$} &
-\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$} &
+\parbox{85pt}{$(2^{b - 1})\frac{\log{n}}{b}$, where $b$ is a configurable 
parameter for tuning digit-fixing properties (routing table)} &
 \parbox{85pt}{System's performance may decrease if nodes are not homogeneous 
and nodes join and leave the system in a dynamic manner}
 \\ \hline
 
@@ -784,15 +799,15 @@
 \parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(1)$} &
 \parbox{37pt}{$O(\log^2{n})$} &
-\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}{$r(2b+2s+2l)$ (where r=number of resources provided, b=boot 
connections, s=short range connections, l=long range connections), typical 
connection configuration: 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}{Gnutella} &
 \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}{Typical configuration is 5 connections (2*5=10 total), however, 
depends on implementation} &
 \parbox{85pt}{Number of messages can grow as fast as $O(n^{2})$}
 \\ \hline
 
@@ -800,7 +815,7 @@
 \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}{Can be 1-10000 connections (aka social connections, connections 
are permament)} &
 \parbox{85pt}{Connection number depends on node's memory/network capabilities}
 \\ \hline
 
@@ -808,7 +823,7 @@
 \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}{$4r(\log{n}) + (\log{n})$, where r=number of resources 
provided)} &
 \parbox{85pt}{In this approach, node is treated as 'named resource'; in this 
approach, \emph{resources} self-organise (opposite to DHTs)}
 \\ \hline
 
@@ -824,8 +839,8 @@
 \parbox{37pt}{$O(\log^2{n})$} &
 \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}
+\parbox{85pt}{$2k+2+f$, where k = long range connections, 2 = node's 
neighbors, f = fault-tolerance connections)} &
+\parbox{85pt}{Space can be also $O(1)$. Additional space of $space^2$ can be 
used as a lookahead list for better performance}
 \\ \hline
 
 \parbox{37pt}{ODHDHT} &
@@ -837,11 +852,11 @@
 \\ \hline
 
 \parbox{37pt}{Plaxton} &
-\parbox{37pt}{-} &
+\parbox{37pt}{No support} &
 \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}
+\parbox{85pt}{Plaxton's algortihm is designed to operate in static environment 
(e.g., web cache)}
 \\ \hline
 
 \parbox{37pt}{PeerNet} &
@@ -856,7 +871,7 @@
 \parbox{37pt}{$O(2(\sqrt{n}*(log^2{n})) + (\sqrt{n} + (log^3{n})))$} &
 \parbox{37pt}{$O$($\sqrt{n}$)} &
 \parbox{37pt}{$O$(1)} &
-\parbox{85pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{Totalnumber of 
files}{\sqrt{n}}$} &
+\parbox{85pt}{$\frac{n}{\sqrt{n}} + c*(\sqrt{n}-1) + \frac{Totalnumber of 
files}{\sqrt{n}}$, where n is the number of nodes and c the number of 
contacts/foreign affinity group} &
 \parbox{85pt}{Insert/delete overhead is constant and performed background, 
System's performance may decrease if nodes are not homogeneous and nodes join 
and leave the system in a dynamic manner}
 \\ \hline