Complex Netwrok理论与应用-p2p

Guntella：
搜索的改进：
1.迭代加深：
Improving search in peer-to-peer network
s以一个小ttl（与小于ttl步的节点都会收到消息）进行bfs搜索，如找不到增加ttl再进行bfs，直到找到目标或者达到ttl，w为两次的间隔。

P{3,5,8}，W=6

S进行ttl=3的bfs，3步以内的节点都会收到消息，如果找不到，或者在6s之内没能把结果返回给s，
进行ttl=5的bfs，2步以内的丢弃消息，3步的进行ttl=5-3=2的查询。
... ...

不能减少flooding，速度慢。

2.有向BFS：
direct BFS
通过选择一些高质量的邻居，把查询消息发给他们，通过他们进行bfs。

通过历史数据来确定邻居的质量，譬如，以前的查询中提供的结果多，返回的平均步数最少，消息队列最短... ...

3.本地索引：

通过在本地建立一个r步以内邻居的文件索引。
然后结合迭代加深的方法。

但是可以消除一定的flooding。

4.k遍历随机游走：
random walking

但是通过k个遍历器，在遍历的时候周期性的保持与s节点的联系。

性能优于迭代加深，消息量小。

5.基于gnutella的度的改进：

s查询所有的邻居，邻居返回它的邻居的信息（或直接找到），s从中找到度最大的节点重复上面的过程。o(n)