文献阅读交流:Epidemic

Epidemic当属机会网络(opportunistic networks)的开创性文章,本文列出我在读Epidemic论文的几个困惑,期待与您交流。

Epidemic论文

Epidemic论文如下:

A. Vahdat and D. Becker, “Epidemic routing for partially connected ad hoc networks,” Tech. Rep. number CS-200006, Duke Univ., no. CS-200006, pp. 1–14, 2000.

困惑1:两个节点相遇,如何交换消息?

两节点相遇时,由标号小的节点发起会话(如下图节点A),进行如下3部操作:

image

图1 节点相遇,交换消息

咋一看,只有节点A给B发送消息,但论文还有一句话,表明了两个节点交换信息。

In turn, each host then requests copies of messages that it has not yet seen.

那么可以理解成,两节点相遇时,标号小的节点A将自已的summary vector发给标号大的节点B,B做个差集运算,将所缺少消息的vector发给A,接下来,可能会有如下两种情况:

  • A将消息一次性发给B,随后,B再将消息一次性发给A,完成消息交换。我想这是论文的意思
  • A与B交替发消息,即A先发一个消息,B收到后同时也给A发一个消息,依此类推。这样的做的好处是:发消息时可以捎带(piggbacking)ACK消息

尽管这两种情况的目的是一样的,即完成消息交换,但实现有区别,性能上也有区别,前者可以直接发送batch of messages,后者可以捎带ACK消息。您觉得具体实现的时候,该怎么做?

还有一个问题,我看有些论文声称,交换summary vector浪费了transmissions,真的是这样吗?交换summary vector可以避免吗?

困惑2:多个节点相遇,如何建立节点对pair-wise?

两个节点相遇的时候,标号小的节点发起会话,如下:

When two hosts come into communication range of one another, the host with the smaller identifier initiates an anti-entropy session

假设一个节点A进入到community(多个节点),这意味着一个节点A同时与多个节点相遇,这个时候,怎么来确定论文所说的random pair-wise?

我的理解是这样的,节点A与多个节点相遇,此时每个节点都在竞争信道,谁竞争到了就发起会话(假设节点B,但这样不能保证标号小的节点先发起会话啊),另一个节点就看谁先收到该消息(如离B越近越快收到消息),这样就建立了节点对pair-wise。

我参照着wifiMAC协议CSMA/CA来理解的,不知道我这样理解对不对,求科普。

困惑3:既然是无线传输,为什么不充分利用广播的特性?

假设节点ABCDE相遇,即在各自的传输范围内,按照Epidemic的思路,节点ABCDE要两两相互消息,最后的结果是ABCDE的buffer是一样的。那么问题就来了,既然是无线传输,为什么不充分利用广播的特性,如A给B发送消息,CDE其实也可以收得到的(广播或者overhear)。

The ONE仿真器的Epidemic就是节点对传消息,尽管有多个邻居节点,这样仿真合理吗?合理性在哪?

困惑4:投递率delivery probability可以达到100%?

论文声称特写的条件下,投递率delivery probability可以达到100%,原文如下:

we ran the 10m simulation in a 100mx 500marea (still large, i.e., for mobile sensors) with all other parameters set to their default values, and achieved 100% message delivery with a 9,610 second average delivery time

我想的是,尽管消息的TTL是无限的,节点的buffer也是无限的,那也不能保证delivery probability能达到100%,因为还取决于移动模型(纵观全文,我没找有关移动模型的介绍)。试想这样的情况,节点A在5s的时候发一个消息B,但节点B在5s后,没有跟其他节点再相遇,那这个消息铁定是不能成功投递的。

困惑5:The ONE仿真器,转移执行权是否合理?

The ONE仿真器实现的router,update开头是一样的,即:

 super.update();
 if (isTransferring() || !canStartTransfer()) {
     return; 
 }

 if (exchangeDeliverableMessages() != null) {
     return; 
 }

举个例子说明exchangeDeliverableMessages是干嘛的,假设轮到A做update,但A发现其邻居节点B有消息m恰好目的节点就是A,那么A交出执行权给B,B做update,将m发给A。这样做合理吗?

更多困惑期待与您交流:-)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

5 thoughts on “文献阅读交流:Epidemic

  • 2017年03月16日 星期四 at 05:04下午
    Permalink

    博主你好,EpidemicRouter进行summary vector交换的代码是在哪个地方? 我感觉EpidemicRouter.java里面没找到和这个意思相近的函数,即使是tryAllMessagesToAllConnections()

    Reply
    • 2017年03月16日 星期四 at 11:24下午
      Permalink

      恩,的确没有。我过挺长时间才转过弯来,仿真器,不同于模拟器。

      Reply
      • 2017年03月17日 星期五 at 10:14上午
        Permalink

        但是这样不就没有Epidemic所说的那效果,这不很影响仿真结果么。难道写DTN的仿真大家都这么干吗?仿真代码和论文idea不同步?

      • 2017年03月17日 星期五 at 09:03下午
        Permalink

        随着对ONE仿真器的了解,这种情况比比皆是,并没有如实反映真实网络(比如消息的发送与接收),但这是仿真器,并不是模拟器,只要仿真过程合理,结果是接受的。

        在ONE中的Epidemic,你可以理解成交换summary vector时间忽略不计,相对于要交换一系列数据包,这样假设是可以接受的。进一步简化,可以假设每个节点都知道其他节点都有哪些信息(这样,计算summary vector差集也就免了)。

        回到Epidemic,其核心思想是flooding-based,即将消息尽可能地扩散到所其他节点(恨不得除他本身和目的节点外,其他节点都是转发节点)。从这一点来说,这样的仿真结果(比如投递率,delivery probability)是可以接受的。

        当然,如果你的工作声称可以减少summary vector交换所带来的开销,那再把这一点考虑进去。

      • 2017年03月19日 星期日 at 08:24下午
        Permalink

        谢谢^_^