[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/11 07:30:01

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

Log message:
        Problems table

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/masterthesis.tex
diff -u gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.29 
gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.30
--- gzz/Documentation/misc/hemppah-progradu/masterthesis.tex:1.29       Wed Feb 
 5 07:32:50 2003
+++ gzz/Documentation/misc/hemppah-progradu/masterthesis.tex    Tue Feb 11 
07:29:59 2003
@@ -10,6 +10,8 @@
 \usepackage{amsfonts}    %  AmS-LaTeX fontit
 \usepackage{graphicx}    %  EPS-tiedostojen ottaminen mukaan, PS-temput,...
 \usepackage{url}
+\usepackage{booktabs}
+\usepackage{longtable}
 
 %***********************
 %   Tyyliluokan pakolliset määritykset
@@ -350,6 +352,252 @@
 Furthermore, the majority of these systems are unable to interoperate 
together. According to recent seminar \cite{uclaseminar}, held in the 
University of UCLA, 
 there are few projects that analyse systems' different approaches. However, 
the most important question is that how existing approaches can be combined 
into one 
 practical and high performance approach, currently known as ``Gnutella++''.  
+
+\chapter{Open Problems in P2P}
+\scriptsize
+
+%\begin{tabular*}{|llll|}
address@hidden|lllr|}
+\begin{longtable}{|l|l|l|l|}
+\caption[Open problems in P2P]{Open problems in P2P} 
\label{table_problems_p2p} \\
+
+\multicolumn{4}{c}{} \\ \cmidrule(l){1-4}
+\textbf{Problem} & \textbf{Problem description} & \textbf{Solutions} & 
\textbf{Comments/Status}
+\\ \midrule
+
+\parbox{90pt}{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 
+\\ \hline
+
+
+\parbox{90pt}{DoS attack} &
+\parbox{110pt}{Distributed, controlled burden againts specific computer(s)} &
+\parbox{110pt}{Client puzzles, load balancing, traffic measurements, traffic 
models, replication} &
+\parbox{110pt}{Only partial solutions, traffic models most effective}
+\\ \hline 
+
+
+\parbox{90pt}{Sybil attack} &
+\parbox{110pt}{Single hostile entity present multiple entities} &
+\parbox{110pt}{Identify all nodes simultaneously across the system, collect 
pool of nodes which are validated, distributed node ID creation} &
+\parbox{110pt}{Not practically realizable, research focused on persistence, 
not on identity distinction}
+\\ \hline 
+       
+
+\parbox{90pt}{Spam attack} &
+\parbox{110pt}{Hostile entity creates false versions of data} &
+\parbox{110pt}{Do not trust to single entity, get information from multiple 
entities, trust on majority's opinion} &
+\parbox{110pt}{Easy to implement, creates more network traffic} 
+\\ \hline
+
+
+\parbox{90pt}{Resource spoofing} &
+\parbox{110pt}{Hostile entity gives wrong information about the data which 
entity is responsible for/knows about} &
+\parbox{110pt}{Do not trust to single entity, get information from multiple 
entities, trust on majority's opinion} &
+\parbox{110pt}{Easy to implement, creates more network traffic} 
+\\ \hline
+               
+
+\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}{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}{Effective, but not flexible}
+\\ \hline
+
+
+\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}
+\\ \hline
+       
+
+\parbox{90pt}{Entity identification} &
+\parbox{110pt}{Identify participating entities reliably and efficiently        
} &
+\parbox{110pt}{Digital signatures, key infrastrucure} &
+\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}
+\\ \hline
+
+
+\parbox{90pt}{Byzantine faults} &
+\parbox{110pt}{Faulty nodes may behave arbitrarily} &
+\parbox{110pt}{Byzantine replication protocols } &
+\parbox{110pt}{Much research has been done on this field, practical solutions, 
decreases system's, performance slighly}
+\\ \hline
+
+
+\parbox{90pt}{Richness of queries} &
+\parbox{110pt}{Query languages should be more powerful} &
+\parbox{110pt}{SQL-like queries} &
+\parbox{110pt}{Hard to implement, increases system complexity, not much 
research has been done}
+\\ \hline
+
+
+\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}{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}
+\\ \hline
+
+
+\parbox{90pt}{Data availability} &
+\parbox{110pt}{Data might be temporary unavailable, or lost permanently} &
+\parbox{110pt}{Data caching, data replication} &
+\parbox{110pt}{Working solutions, but creates more traffic and overhead per 
node}
+\\ \hline
+
+
+\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}
+\\ \hline
+
+
+\parbox{90pt}{Anonymity} &
+\parbox{110pt}{Anonymity cannot be provided in all cases} &
+\parbox{110pt}{Remailers, pre-routing} &
+\parbox{110pt}{Total anonymity cannot be provided yet}
+\\ \hline
+
+
+\parbox{90pt}{Malicious nodes} &
+\parbox{110pt}{There are malicious nodes in the system how we are able to 
discover them ?} &
+\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}{Resource demanding, not practical to implement/not working 
solutions, no real world experience in a wide scale}
+\\ \hline
+
+
+\parbox{90pt}{Lack of motivation to cooperate} &
+\parbox{110pt}{All participants do not behave like they should be, instead 
they go for own profit} &
+\parbox{110pt}{Different reputation methods} &
+\parbox{110pt}{No real world experience in a wide scale}
+\\ \hline
+
+
+\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}{Working solutions, increases system complexity (additional 
layer)}
+\\ \hline
+
+
+\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}
+\\ \hline
+
+
+\parbox{90pt}{Locality} &
+\parbox{110pt}{In the case on DHTs, can we take account locality ?} &
+\parbox{110pt}{Constrained Load Balancing, using network properties for 
nearest neighbor selection} &
+\parbox{110pt}{Working solutions}
+\\ \hline
+
+
+\parbox{90pt}{Hotspots} &
+\parbox{110pt}{What will happen if some resource is extremely popular and only 
one node is hosting it ?} &
+\parbox{110pt}{Caching, multisource downloads, replication, load balancing} &
+\parbox{110pt}{For query hotspots, caching and multisource downloads 
efficiently reduces hotspots, for routing hotspots, benefits are smaller}
+\\ \hline
+
+
+\parbox{90pt}{Scalability} &
+\parbox{110pt}{Broadcasting doesn't scale when performing searches} &
+\parbox{110pt}{Super peers, peer clusters, mutual index caching} &
+\parbox{110pt}{Better scalability, but not comparable to DHTs}
+\\ \hline
+
+
+\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}
+\\ \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}
+\\ \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}
+\\ \hline
+
+
+\parbox{90pt}{Inconsistent behaviour} &
+\parbox{110pt}{Hostile node could act correctly with its neighbors, but 
incorrectly with other} &
+\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}
+\\ \hline
+
+
+\parbox{90pt}{External threats} &
+\parbox{110pt}{Viruses, troijans, 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}
+\\ \hline
+
+
+\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
+
+                                                       
+
+\end{longtable}
 
 \chapter{Gzz System}
 
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.54 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.55
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.54      Tue Feb 
11 03:52:23 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Tue Feb 11 
07:29:59 2003
@@ -214,7 +214,8 @@
 
 3) p2p open problems table:
 
-                                       Problem description                     
        Solutions                                       Comments/Status
+
+Problem                                        Problem description             
                Solutions                                       Comments/Status
 Routing:                               Incorrect forwarding (hostile),         
        Query monitoring, cross check                   Increases system 
complexity
                                        incorrect routing (hostile)             
        routing tables, verify routing tables,          
                                                                                
        create routing table invariants
@@ -224,28 +225,28 @@
                                        
 Sybil attack:                          Single hostile entity present multiple  
        Identify all nodes simultaneously               Not practically 
realizable,
                                        entities                                
        across the system, collect pool of nodes        research focused on 
persistence,
-                                                                               
        which are validated, distributed                not on distinction
+                                                                               
        which are validated, distributed                not on identity 
distinction
                                                                                
        node ID creation        
                                        
-Spam attack:                           Hostile entity creates false versions   
        Do not trust to single entity,                  Efficient, easy to 
implement,
+Spam attack:                           Hostile entity creates false versions   
        Do not trust to single entity,                  Easy to implement,
                                        of data                                 
        get information from multiple entities,         creates more network 
traffic
                                                                                
        trust on majority's opinion
                                        
-Resource spoofing:                     Hostile entity gives wrong information  
        Do not trust to single entity,                  Efficient, easy to 
implement,
+Resource spoofing:                     Hostile entity gives wrong information  
        Do not trust to single entity,                  Easy to implement,
                                        about the data which entity is 
responsible      get information from multiple entities,         creates more 
network traffic
                                        for/knows about                         
        trust on majority's opinion
                                        
 Sudden network partition:              Sub network is isolated from other 
network      Self-tuning, environment observatorion,         Creates more 
overhead/space
                                        because of network disconnection        
        backup connections                              requirements per node
                                        
-Searching:                             Efficient searching requires exploiting 
        View trees, bloom filters                       Effective, but not 
flexible
-                                       of previous queries                     
        
+Searching:                             Efficient searching requires exploiting 
        View trees, bloom filters and its               Effective, but not 
flexible
+                                       of previous queries                     
        variations
                                        
-Efficient data discovery:              Find resources efficiently, if resource 
        Super nodes, node clusters,                     Morre effiecient, less 
network traffic,
+Efficient data discovery:              Find resources efficiently, if resource 
        Super nodes, node clusters,                     More effiecient, less 
network traffic,
                                        exists (broadcasting)                   
        caching techiques                               not comparable to DHT's 
efficiency
                                        
-Entity identification:                 Identify participating entities 
reliably        Digital signatures, key infrastrucure           Research 
focused on persistence,
-                                       and efficiently                         
                                                        not on distinction of 
identity
+Entity identification:                 Identify participating entities 
reliably        Digital signatures, key infrastrucure           Not practically 
realizable
+                                       and efficiently                         
                                                        
 
 Fail Stop:                             A faulty node stops working             
        Environment observatorion, informing            Creates more network 
traffics,
                                                                                
        protocols                                       node's information can 
be outdated
@@ -260,7 +261,7 @@
 Robustness:                            How well system performs under hostile  
        Self-tuning, backup links, use                  Working solutions
                                        attacks/in the case of severe failure ? 
        diverse routing paths
                                        
-Quality of Service, QoS:               The system cannot promise the quality 
of        Use Network proximity                           Increases system 
complexity, no real world 
+Quality of Service:                    The system cannot promise the quality 
of        Use Network proximity                           Increases system 
complexity, no real world 
                                        service in all cases                    
        for better network performance                  experiences
                                                                                
        (bandwidth, latency, jitter, packet 
                                                                                
        loss)
@@ -279,7 +280,7 @@
 Malicious nodes:                       There are malicious nodes in the 
system,        Create invariants for node behaviour,           Partial 
solutions, self-certifying data most realiable
                                        how we are able to discover them ?      
        verify invariants, self-certifying data
                                        
-Mutual distrust:                       Nobody trust anybody, this is a problem 
        Different reputation methods, key               Resource demanding, not 
practical to
+Mutual distrust:                       Nobody trust anybody                    
        Different reputation methods, key               Resource demanding, not 
practical to
                                                                                
        infrastructures                                 implement/not working 
solutions, no real world
                                                                                
                                                        experience in a wide 
scale
                                                                                
                                                        
@@ -315,8 +316,8 @@
                                        in peer-to-peer network ?               
                                                        because they are 
hard/not practically realizable
                                        
 System in flux:                                Nodes join and leave system 
constantly:         Half-life phenomenon (for analysis),            Initial 
theoretical anasysis has been created, but
-                                       load balancing, efficiency ?            
        simple overlay and construction protocol        not comprehensive model 
for analysing different
-                                                                               
                                                        system states
+                                       load balancing, efficiency ?            
        simple overlay maintenance and construction     not comprehensive model 
for analysing different
+                                                                               
         protocol                                       system states
                                                                                
                                                        
 Inconsistent behaviour:                        Hostile node could act 
correctly with           Public keys, digital signatures                 Not 
practical approach/working proposal created yet
                                        its neighbors, but incorrectly with 
other