The ONE使用笔记:Epidemic路由

Epidemic路由是DTN路由协议中的另一个极端,即所有节点将消息传递给所有邻居结点。本文结合源代码,介绍Epidemic路由的一些技术细节,包括tryAllMessagesToAllConnections, tryMessagesToConnections, tryAllMessages

1. Epidemic

1.1 路由策略

DirectDelivery路由是一个极端,即从不复制消息,只有碰到目的节点,才交付消息。Epidemic是另一个极端,采用泛洪(Flooding)机制,只要有机会,就将消息传递给邻居节点,正如其名,类似于病毒的“接触-感染”。显然,只要节点的缓冲区足够大,Epidemic的投递率是最高的,即上限,故Epidemic通常作为benchmark与其他协议进行比较。

介绍Epidemic的官方论文如下:

VAHDAT, Amin, BECKER, David, et al. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, 2000. BibTex

该论文的核心内容是当节点相遇时(如A遇见B),A将其summary vector传递给B,B可以求得两节点消息队列的差集,发给A,如此,A便可知道传递哪些消息给B,即A有但B没有的消息。 示意图如下:

image_thumb[1]

图1 Epidemic路由消息交换示意图

1.2 源代码

EpidemicRouter.javaupdate源代码如下:

//EpidemicRouter.java
public void update() {
    super.update();
    if (isTransferring() || !canStartTransfer()) {
        return; 
    }

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

    // then try any/all message to any/all connection
    this.tryAllMessagesToAllConnections(); //参见2
}

可见EpidemicRouterDirectDiliveryRouter基础上添加了this.tryAllMessagesToAllConnections()。关于DirectDeliveryRouter参见之前的博文《The ONE使用笔记:DirectDelivery路由》。

2. tryAllMessagesToAllConnections

假设轮到节点A做update(),A有10个邻居节点。tryAllMessagesToAllConnections只要能将节点A的缓冲区中的一个消息传递给某个邻居节点就返回。这一点结合无线信道的特性就很好理解了,The ONE将MAC层抽象了,并不支持广播,而是将节点间的连接像有线一样,在本例,A有10个邻居,即有10个connections。但The ONE保持了无线数据传输的特性,即broadcast medium,节点A传输了一个消息,相当于占用了该信道,其他消息也就不能传输了。

2.1 tryAllMessagesToAllConnections

tryAllMessagesToAllConnections遍历所有connections(相当于遍历邻居节点),遍历节点A缓冲区的消息,若有消息能传输,则返回。相关源代码及注释如下:

//ActiveRouter.java
protected Connection tryAllMessagesToAllConnections() {
    List<Connection> connections = getConnections();  //取得所有邻居节点
    if (connections.size() == 0 || this.getNrofMessages() == 0) {
        return null;
    }

    List<Message> messages = new ArrayList<Message>(this.getMessageCollection()); //取得缓冲区所有消息
    this.sortByQueueMode(messages);

    return tryMessagesToConnections(messages, connections);
}

//tryMessagesToConnections(messages, connections);
protected Connection tryMessagesToConnections(List<Message> messages, List<Connection> connections) {
    for (int i=0, n=connections.size(); i<n; i++) {
        Connection con = connections.get(i);
        Message started = tryAllMessages(con, messages);
        if (started != null) {
            return con;
        }
    }
    return null;
}

//tryAllMessages(con, messages); 只要有一个消息能传递,就返回
protected Message tryAllMessages(Connection con, List<Message> messages) {
    for (Message m : messages) {
        int retVal = startTransfer(m, con);
        if (retVal == RCV_OK) {  //accepted a message, don't try others
            return m;
        } else if (retVal > 0) { //系统定义,只有TRY_LATER_BUSY大于0,即为1
            return null;          // should try later -> don't bother trying others
        }
    }
    return null; // no message was accepted
}

2.2 startTransfer的返回值

startTransfer(m, con)的返回值如下:

//MessageRouter.java    startTransfer(m, con)的返回值
public static final int RCV_OK = 0;                 //OK
public static final int TRY_LATER_BUSY = 1;         //busy receiver
public static final int DENIED_OLD = -1;            //an old (already received) message 
public static final int DENIED_NO_SPACE = -2;       //not enough space in the buffer for the msg
public static final int DENIED_TTL = -3;            //messages whose TTL has expired
public static final int DENIED_LOW_RESOURCES = -4;  //a node low on some resource(s
public static final int DENIED_POLICY = -5;
public static final int DENIED_UNSPECIFIED = -99;   //unspecified reason

专题: DTN路由协议 (2/6)

发表评论

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

51 thoughts on “The ONE使用笔记:Epidemic路由

  • 2017年03月28日 星期二 at 03:12下午
    Permalink

    博主,我是刚接触的the one,想请教一下那个如何设置每隔一段时间可以产生数据包

    Reply
  • 2017年02月28日 星期二 at 11:51下午
    Permalink

    博主,请问如何将ONE中的二维节点扩展成三维的,能否给我一点思路?

    Reply
    • 2017年03月01日 星期三 at 04:55上午
      Permalink

      三维的,你是指?

      以我的理解,三维归根结底还是节点与节点间的连接建立与断开,这样的话,把移动模型转化为ONE的标准事件就可以了(如1 CONN 1 5 UP)。

      Reply
      • 2017年03月01日 星期三 at 08:08上午
        Permalink

        之前移动模型中有x,y两坐标,我是指现在要加一个z坐标

      • 2017年03月01日 星期三 at 10:13上午
        Permalink

        您好,博主,我指的三维是之前模型已经有x,y两个坐标,现在如何考虑再扩展z坐标?

      • 2017年03月01日 星期三 at 06:03下午
        Permalink

        我不确定he ONE是否支持三维的移动模型。但至少可以转换为标准连接事件(比如用脚本语言事先处理下移动模型),导入ONE,这样就可以仿真了。

  • 2016年04月19日 星期二 at 09:57下午
    Permalink

    Spark 您好!在不同的社区之间传递信息时我才用Epdemic路由算法,当节点到达目的社区并将消息传递给目的社区内的节点后,我将不是目的社区但是在目的社区内的节点携带的消息副本删除。这样做可以减少缓存占用和不必要的继续传递的资源消耗。这是一种方法。另一种我想把Epdemic进行优化,用到社区消息传递中。优化的Epdemic已经很多,我想采用一个比较好的。您看我这两种方法哪一个会在社区间消息传递效果更好呢?

    Reply
    • 2016年04月20日 星期三 at 07:59下午
      Permalink

      要是有一种策略能删除已经投递消息的副本(方法一),自然很好,可以获得很大的性能提升。

      方法二,不知道你的应用场景,不知道你是怎么划分社区的,也不知道你的社区消息是怎么投递的,更不知道你要怎么改进Epidemic。。。你问我最后投递效果,实在答不上来!

      Reply
      • 2016年04月20日 星期三 at 09:26下午
        Permalink

        嗯谢谢您的回答

  • 2016年04月18日 星期一 at 08:50下午
    Permalink

    Spark您好!我想请问一下,如果我把消息传到了目的社区,此时我想把不是这个社区的节点携带的消息副本删除能实现吗?应该怎么写代码呢?

    Reply
    • 2016年04月19日 星期二 at 03:32上午
      Permalink

      当然可以,不过这样的假设恐怕很unreasonable。至于代码实现,提供一个思路,至于优化取决于你的情况。

      遍历本社区的节点,若有含有该消息,则删除。

      Reply
      • 2016年04月19日 星期二 at 05:38下午
        Permalink

        谢谢您的回答,我的问题是目的节点在目的社区,不是目的社区的节点携带消息副本到达了目的社区并将消息传给了是目的社区内的节点,这个时候我想把目的社区内不是本社区的节点携带的消息副本删除。这个代码您能给我一点提示吗?具体怎么遍历目的社区内的节点呢?多谢。。。

      • 2016年04月20日 星期三 at 07:51下午
        Permalink

        以下代码可以得到网络中的所有节点,你在此基础上,再进行你的操作。

        hosts=SimScenario.getInstance().getHosts();

      • 2016年04月20日 星期三 at 10:12下午
        Permalink

        帅哥这个我知道,我就是不知道怎么判断节点属于某一社区。您能在给我一点提示吗?

      • 2016年04月20日 星期三 at 10:53下午
        Permalink

        那你做了社区划分(community detection)没?

        你是想问怎么对节点进行社区划分?

      • 2016年04月21日 星期四 at 09:58上午
        Permalink

        我的问题就是说消息副本进入了目的社区并将信息传给了目的社区内的节点,这时接收了消息的节点将发送反馈消息给目的社区内的节点,告知不属于目的社区内的节点将所携带的消息副本删除。就是这段代码我该怎么实现。这里我最重要的我觉得是怎么判断哪些节点是否属于目的社区哪些不属于。

      • 2016年04月23日 星期六 at 12:56上午
        Permalink

        假设你给每个社区编了号,目的节点所在社区为C1,那么,其他节点的社区编号如果等于C1,就属于目的社区了。

  • 2015年12月09日 星期三 at 11:51上午
    Permalink

    As we all know, in epidemic, nodes continuously replicate and transmit messages to newly discovered contacts that do not already possess a copy of the message.
    I got two questions:
    when the message is already delivered to the destination —
    1. how does the network deal with the remaining copies? (Maybe 1. TTL 2. FIFO)
    2. Would the nodes which carry the copies continue to forward them to other contacts that do not possess the copy ?

    Reply
    • 2015年12月09日 星期三 at 04:58下午
      Permalink

      1. Random in default as shown in MessageRouter.java. Change the behavior by:

      Group.sendQueue = 1(or 2) # identity random and FIFO respectively

      2. Yes.

      Reply
      • 2015年12月09日 星期三 at 05:40下午
        Permalink

        您好!
        关于问题2,我有个疑问,在message delivered之后,message的副本继续在网络中以epidemic的方式复制和传递显然是没有意义的。
        在one的epidemic的实现里,有没有一个方法来处理这种问题,使得message delivered之后,message的副本不会再继续复制和传递?
        我看到您博文中提到的这篇epidemic的论文中,提到他们想要设计一个acknowledgments of message delivery来处理这个问题,但是当时的实验里,没有用这个。

      • 2015年12月09日 星期三 at 06:32下午
        Permalink

        删除delivered messages在网络中的其他副本是个技术活(因为没有end-to-end path),我没看到ONE有类似的实现,不知道那个response size是不是可以用于此目的。

        我提到acknowledgments of message delivery?本博文没提到呀。

      • 2016年04月18日 星期一 at 08:47下午
        Permalink

        帅哥你把副本删除这个问题解决了吗

  • 2015年12月01日 星期二 at 10:35下午
    Permalink

    博主你好!我想知道某一节点和他邻居节点相遇的次数,要怎么获得呢?

    Reply
    • 2015年12月02日 星期三 at 06:03下午
      Permalink

      你可以考考下report/TotalEncountersReport.java (A report of the distribution of how many encounters (contacts) a node has had)

      Reply
  • 2015年08月28日 星期五 at 01:10上午
    Permalink

    请问epidemic算法的SV信息交换相关代码在ONE的epidemic.java里没有体现吗?

    Reply
    • 2015年08月28日 星期五 at 06:29下午
      Permalink

      没有。int retVal = startTransfer(m, con);如果对方已有消息m,那么retVal返回就不会是RCV_OK,接着遍历下一个消息。

      Reply
      • 2015年08月28日 星期五 at 11:36下午
        Permalink

        谢谢您的回复,我理解的是one并没有刻意去模拟SV信息的交互过程,如果想做机会网络编码效率相关的试验(比如SV信息中稍带数据等),ONE不太适合,不知道这样认为对吗?请问有其他好的可以模拟机会网络编码的软件吗?谢谢您的帮助

      • 2015年08月29日 星期六 at 02:08上午
        Permalink

        很高兴听到你也做DTN网络编码。关于其他仿真器,我最开始是用ns2, ns3,但ns2/3有个问题,就是不支持不含有位置信息的数据集(而很多论文的仿真结果是基于现实的数据集,比如infocom06),因为这个我才转到The ONE。

      • 2015年08月29日 星期六 at 10:01下午
        Permalink

        谢谢您,可否分享几篇您的研究成果给我学习下?另外我一直纠结个问题,one里面好像也没有支持具体的网络编码呀?比如我之前提到的问题epidemic的SV信息里我想加入一些东西,这样的想法在ONE里该在哪里去做哪?可否指点下思路,谢谢您的帮助。

      • 2015年08月30日 星期日 at 06:38下午
        Permalink

        有点惭愧,至今只提交了一篇论文,等收到录用通知的时候,再发给你。另,网络编码部分得自已实现。你是打算用线性网络编码 还是 异域网络编码?

      • 2015年08月31日 星期一 at 12:06上午
        Permalink

        谢谢您的指点,看来得自己增加代码来模拟编码解码流程了,在one里面。我才入门,整学习线性编码:)谢谢您的帮助,祝好,也请您有新成果的时候记得博客上共享哦。

      • 2015年09月09日 星期三 at 03:55下午
        Permalink

        我看了下,你是在成都,电子科大?可以简单分享下你的研究工作吗?

      • 2015年09月09日 星期三 at 10:29下午
        Permalink

        我是SCU的,之前学习的是进化算法效率改进,无奈数学基础差,现在转了个方向学机会网络,无意中发现您的博客对我帮助很大,就一直关注了,谢谢你!另外您在数学讨论栏目里有篇文章我有点小问题看不懂给您在博客留言了,可否请您方便的时候看看,谢谢您!

      • 2015年09月10日 星期四 at 04:52下午
        Permalink

        数学讨论栏里留言?我没看到耶,刚才去看了下,待审核和垃圾评论都没看到,你确信留了?看来你看了一些机会网络的综述性文章,咱们不妨在这方面深入交流下。你邮箱多少,我给你发邮件吧。

      • 2015年09月10日 星期四 at 10:18下午
        Permalink

        谢谢您的关心,我的问题是:可否请您指点下帕雷托法则与长尾理论和 泊松分布与幂律分布间的联系吗?另外请问您提到均匀网络和泊松分布有关,能请您指点下怎么理解吗?另外我的邮箱是471615939@qq.com还请多帮忙指点,有好的文章和资料麻烦指点我阅读下,谢谢您的帮助!

      • 2015年09月10日 星期四 at 11:10下午
        Permalink

        我的理解是均匀网络(在DTN指节点对相遇时间均匀)的度分布服从泊松分布;度服从幂律分布为非均匀网络,通常的协议设计是social-aware。

  • 2015年04月03日 星期五 at 11:18下午
    Permalink

    博主有麻烦您了。。。Epidemic路由算法应该是洪泛算法呀,为什么“tryAllMessagesToAllConnections只要能将节点A的缓冲区中的一个消息传递给某个邻居节点就返回”?

    Reply
  • 2015年04月02日 星期四 at 06:50下午
    Permalink

    博主您好,我想问一下,如果我想定义自私节点(每个节点以人为确定的各个节点不相同的概率转发收到的信息,而非转发全部的信息),我应该在哪定义呢?是在movement定义移动模型还是应该在routing中重写消息的接收和转发方法?

    Reply
    • 2015年04月02日 星期四 at 07:58下午
      Permalink

      或者说需要在DTNhost里修改?

      Reply
    • 2015年04月02日 星期四 at 08:49下午
      Permalink

      这概率不影响节点的移动吧,那修改movement就没意义了。其实你的目的是给每个节点添加一个新的属性:概率。那修改DTNHost吧,并且修改update方法。对了,你的概率是静态的?仿真前就已知的?

      Reply
      • 2015年04月02日 星期四 at 09:12下午
        Permalink

        是静态的,在配置文件中定义。是修改DTNhost里的update方法吗?

      • 2015年04月02日 星期四 at 11:16下午
        Permalink

        改EpidemicRouter的update方法。