1. Epidemic
- 1.1 路由策略
- 1.2 源代码
2. tryAllMessagesToAllConnections
- 2.1 tryAllMessagesToAllConnections
- 2.2 startTransfer的返回值

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没有的消息。示意图如下：

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

1.2 源代码

EpidemicRouter.java的update源代码如下：

//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
}

可见EpidemicRouter在DirectDiliveryRouter基础上添加了this.tryAllMessagesToAllConnections()。关于DirectDeliveryRouter参见之前的博文《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

Epidemic路由