The ONE使用笔记:DirectDelivery路由

DirectDelivery路由无疑是最简单的,其他的路由的update,最开始的代码与DirectDelivery是一样的。本文介绍DirectDelivery,旨在进一步了解ActiveRouter.updateMessageRouter.updateisTransferringcanStartTransferexchangeDeliverableMessages

1. DirectDelivery

1.1 路由策略

DirectDelivery路由策略很简单,每个节点携带自创建的消息,不断移动,直到遇到目的节点,才把消息传递出去,整个通信过程从不借助其他节点。这点方法优点很明显,开销是最低的,但缺点也很明显,效率是最低的。作为路由的一种极端,通常作为benchmark与其他协议进行比较。

1.2 源代码

DirectDelivery的源代码是最简单的,其他的路由的update,最开始的代码与DirectDelivery是一样的,比如判断该节点是否正在传输数据。DirectDeliveryRouterupdate源代码如下:

//DirectDeliveryRouter
public void update() {
    super.update();   //调用父类的update, 详情见2
    if (isTransferring() || !canStartTransfer()) { //判断能否进行传输,详情见3
        return; 
    }

    if (exchangeDeliverableMessages() != null) { //若有目的节点就在本节点或者邻居节点的消息,详情见4
        return; 
    }
}

2. super.update

DirectDeliveryRouter的继承关系是这样的:DirectDeliveryRouter —> ActiveRouter –> MessageRouterupdate都会被重写并调用上一层的update

2.1 MessageRouter.update

相当于应用于的update,取决于具体应用,类似乎于事件处理函数取决于具体事件,其源代码如下:

//MessageRouter.java 
public void update() {
for (Collection<Application> apps : this.applications.values()) { //update the status of transfer(s) on every simulation interval 
    for (Application app : apps) {
            app.update(this.host);
        }
    }
}

2.2 ActiveRouter.update

ActiveRouter.update主要做5件事,其源代码如下:

//ActiveRouter.java
public void update() {
    super.update(); //调用MessageRouter的update()

    /*** in theory we can have multiple sending connections even though currently all routers allow only one concurrent sending connection ***/
    for (int i=0; i<this.sendingConnections.size(); ) {
        boolean removeCurrent = false;
        Connection con = sendingConnections.get(i);

        /*** 1. 处理已完成传输的数据包 ***/
        if (con.isMessageTransferred()) {
            if (con.getMessage() != null) {
                transferDone(con);
                con.finalizeTransfer();
            }
            removeCurrent = true;
        }
        /*** 2. 中止那些断开链路上的数据包 ***/
        else if (!con.isUp()) {
            if (con.getMessage() != null) {
                transferAborted(con);
                con.abortTransfer();
            }
            removeCurrent = true;
        }

        /*** 3. 必要时,删除那些最早接收到且不正在传输的消息 ***/
        if (removeCurrent) {
            if (this.getFreeBufferSize() < 0) {
                this.makeRoomForMessage(0);  //必要时,删除那些最早接收到且不正在传输的消息
            }
            sendingConnections.remove(i); 
        } else {
            i++;  //index increase needed only if nothing was removed
        }
    }

    /*** 4. 丢弃那些TTL到期的数据包(只在没有消息发送的情况) ***/
    if (SimClock.getTime() - lastTtlCheck >= ttlCheckInterval && sendingConnections.size() == 0) {
        dropExpiredMessages();
        lastTtlCheck = SimClock.getTime();
    }

    /*** 5. 更新能量模板 ***/
    if (energy != null) {
        /* TODO: add support for other interfaces */
        NetworkInterface iface = getHost().getInterface(1);
        energy.update(iface, getHost().getComBus());
    }
}

由上可见,ActiveRouter.update主要做以下5件事:

3. isTransferring和canStartTransfer

判断该节点能否进行传输消息,存在以下情况一种以上的,直接返回,不更新:

  • 本节点正在传输,sendingConnections.size() > 0
  • 没有邻居节点,即没有节点与之建立连接,connections.size() == 0
  • 有邻居节点,但有链路正在传输(想想无线信道),!con.isReadyForTransfer()
  • 缓冲区没有消息,this.getNrofMessages() == 0

3.1 isTransferring

isTransferring涵盖了上述的前3种情况,其源代码如下:

//ActiveRouter.java
public boolean isTransferring() {
    //情形1:本节点正在传输
    if (this.sendingConnections.size() > 0) {
        return true;
    }

    List<Connection> connections = getConnections();

    //情型2:没有邻居节点
    if (connections.size() == 0) {
        return false;
    }

    //情型3:有邻居节点,但有链路正在传输
    for (int i=0, n=connections.size(); i<n; i++) {
        Connection con = connections.get(i);
        if (!con.isReadyForTransfer()) {
            return true;
        }
    }

    return false;
}

值得注意的是,只有当与邻居相连的所有链路都是空闲的,才能传输,这是因为无线的传输介质是广播的。而且每次传输只能有一个connection进行传输,可见The ONE仿真了无线信道,但其他没法收到这个广播包。

(1)判断链路是否空闲

The ONE的链路用Connection类表示,一条链路能用于传输需要同时满足两个条件:其一,该链路是建立的;其二,该链路是空闲的。相关成员变量如下:

//Connection.java
private boolean isUp;       //连接是否建立
protected Message msgOnFly; //连接是否被占用

(2)isReadyForTransfer

理解了上述的点,判断一条链路可否用于通信就很简单了,源代码如下:

//Connection.java
public boolean isReadyForTransfer() {
    return this.isUp && this.msgOnFly == null;
}

3.2 canStartTransfer

canStartTransfer判断该节点能否开始传输,缓冲区有消息,并且有邻居节点,才返回真。源代码如下:

//ActiveRouter.java
protected boolean canStartTransfer() {
    if (this.getNrofMessages() == 0) {  //缓冲区空
        return false;
    }
    if (this.getConnections().size() == 0) { //没有连接建立,即没有邻居节点
        return false;
    }

    return true;
}

4. exchangeDeliverableMessages

exchangeDeliverableMessages用于交换该节点与邻居节点间的消息,这些消息的目的节点是该节点或者其邻居节点。值得注意的是:该节点可能会有多个邻居节点(The ONE表示为多个connection),但只能让一个connection传输数据,想想无线信道。所以,只有有一个消息能传输到目的节点,就返回。exchangeDeliverableMessages先看本节点是否有消息的某个邻居节点,如果没有,再查看邻居节点是否有消息的目的节点是本节点。其源代码如下:

//ActiveRouter.java
protected Connection exchangeDeliverableMessages() {
    List<Connection> connections = getConnections();
    if (connections.size() == 0) {
        return null;
    }

    //getMessagesForConnected()返回那些目的节点就是邻居节点的消息
    //tryMessagesForConnected,尝试将上述返回的消息发送到目的节点(值得注意的是:只能发一个)
    Tuple<Message, Connection> t = tryMessagesForConnected(sortByQueueMode(getMessagesForConnected()));
    if (t != null) {
        return t.getValue(); // started transfer
    }

    //如果没发送成功,看邻居节点的缓冲区是否有消息的目的节点是该节点,若是,尝试传输
    for (Connection con : connections) {
        if (con.getOtherNode(getHost()).requestDeliverableMessages(con)) {
            return con;
        }
    }

    return null;
}

4.1 getMessagesForConnected

getMessagesForConnected返回本节点缓冲区的那些目的节点在其邻居节点的消息,这些消息只要投递成功,就成功达到目的节点。源代码如下:

//ActiveRouter.java
//返回那些消息的目的节点是某个邻居节点
protected List<Tuple<Message, Connection>> getMessagesForConnected() {
    if (getNrofMessages() == 0 || getConnections().size() == 0) {
        return new ArrayList<Tuple<Message, Connection>>(0);
    }

    List<Tuple<Message, Connection>> forTuples = new ArrayList<Tuple<Message, Connection>>();
    for (Message m : getMessageCollection()) {    //遍历缓冲区每个消息
        for (Connection con : getConnections()) { //遍历每个邻居节点
            DTNHost to = con.getOtherNode(getHost());
            if (m.getTo() == to) { //消息的目的节点是邻居节点
                forTuples.add(new Tuple<Message, Connection>(m,con));
            }
        }
    }

    return forTuples;
}

4.2 tryMessagesForConnected

tryMessagesForConnected尝试着将消息传输出去,只要有一个成功(意味着该信道被占用),就返回。详情可参考之前博文《The ONE使用笔记:深入源码理解消息转发过程》。

4.3 requestDeliverableMessages

requestDeliverableMessages如果本节点没有消息的目的节点是邻居节点,那么看看邻居节点是否有消息的目的节点在本节点。DTNHostrequestDeliverableMessages调用ActiveRouterrequestDeliverableMessages。源代码如下:

//ActiveRouter.java
public boolean requestDeliverableMessages(Connection con) {
    if (isTransferring()) {
        return false;
    }

    DTNHost other = con.getOtherNode(getHost()); //即得到本节点

    ArrayList<Message> temp = new ArrayList<Message>(this.getMessageCollection()); //do a copy to avoid concurrent modification exceptions (startTransfer may remove messages)
    for (Message m : temp) {
        if (other == m.getTo()) {
            if (startTransfer(m, con) == RCV_OK) {
                return true;
            }
        }
    }
    return false;
}

至此,DirectDelivery路由介绍完毕。其他的路由都是在此基础上,即在本节点与邻居节点都没有可直接传输到目的节点的消息,根据一定的策略,选择消息,转发到其他节点。

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

发表评论

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

10 thoughts on “The ONE使用笔记:DirectDelivery路由

  • 2017年02月22日 星期三 at 04:21下午
    Permalink

    您好,我一路追踪下来

    exchangeDeliverableMessages( ) ->tryMessagesForConnected( )->ActiveRouter.startTransfer( ) ->
    Connection.startTransfer( ) ->
    CBRConnection.startTransfer( ) ->
    DTNHost.receiveMessage( ) –> ActiveRouter.receiveMessage( ) –> MessageRouter.receiveMessage( )

    请问为什么最终只是看到ml.messageTransferStarted( )–>nrofStarted++; 而不是messageListener中的messageTransferred()–>nrofDelivered++ 呢?

    这里的exchangeDeliverableMessages( )不是说“用于交换该节点与邻居节点间的消息,这些消息的目的节点是该节点或者其邻居节点。”消息应该被delivered了呀

    Reply
  • 2016年04月29日 星期五 at 07:52下午
    Permalink

    你好,请问在消息机制中的reponseSize属性是不是设置成1就会自动回复呢?还有我最近在用ONE实现带有缓存节点的网络,如何在检测到请求的消息在缓存节点上存在的时候就返回呢?

    Reply
    • 2016年04月30日 星期六 at 05:55上午
      Permalink

      reponseSize实际上是消息大小message size。默认值为0,表示不需要response。

      Reply
  • 2016年04月14日 星期四 at 07:41下午
    Permalink

    请问,DTNHost other = con.getOtherNode(getHost()); //即得到本节点 意思是:邻居节点有消息的就是本节点么?

    Reply
    • 2016年04月15日 星期五 at 02:59上午
      Permalink

      不是。建议你再看看博文。

      //如果没发送成功,看邻居节点的缓冲区是否有消息的目的节点是该节点,若是,尝试传输
      for (Connection con : connections) {
      if (con.getOtherNode(getHost()).requestDeliverableMessages(con)) {
      return con;
      }
      }

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

    特别是第二个判断? 是判断消息是否已经到达目的节点吗?那还要判断邻居节点是否是目的节点干嘛呢?如果邻居节点是目的节点的话 不是还要传输一次吗?

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

    你好我想问问 这个路由算法的update()里 判断了if (isTransferring() || !canStartTransfer()) { //判断能否进行传输,详情见3 return; }if (exchangeDeliverableMessages() != null) { //若有目的节点就在本节点或者邻居节点的消息,详情见4 return; }判断完什么也不做是什么意思啊 这里始终不是很了解。希望给予指导。

    Reply
    • 2015年09月09日 星期三 at 07:35下午
      Permalink

      假设A与B相遇,A有消息,其目的节点是B(或者说B有消息,其目的节点是A)。exchangeDeliverableMessages() != null,意思是说A与B完成一个消息的交换,本次循环就结束了。你可以理解成此时信道被占用了,不能再发送其他消息了。

      Reply