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)

发表评论

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

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

  • 2019年11月22日 星期五 at 05:39下午
    Permalink

    您好

    Reply
  • 2019年11月15日 星期五 at 08:10下午
    Permalink

    楼主你好,如果想把epidemic路由改成黑洞路由(就是只接收包不传包)应该在怎么修改呢?

    Reply