The ONE使用笔记:SprayAndWait路由

DirectDelivery和Epidemic是两种极端,前者,从不复制,只有碰到目的节点,才交付信息;后者,将消息复制给碰到的节点。路由协议设计核心是如何让投递率(delivery probability)接近Epidemic,同时让开销尽可能的小,即选择哪些消息传递给哪些节点。本文介绍Spray and Wait路由。

1. 路由策略

介绍Spray and Wait路由的文章如下:

SPYROPOULOS, Thrasyvoulos, PSOUNIS, Konstantinos, et RAGHAVENDRA, Cauligi S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In : Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking. ACM, 2005. p. 252-259. BibTex

相对于Epidemic,SprayAndWait降低消息在网络中的份数,即对复制次数做一些限制。正如其名,SprayAndWait包含两个阶段(假设每个消息初始化为L copies,即网络中含有某消息最多L份):

  • Spray:当碰到一个节点时,决定多少份给该节点。最简单的分发策略是一份一份地发;还有另一种分发策略是每次将一半copies给遇到的节点(Binary Spray and Wait),当节点只有一份消息时,就退化成DirectDelivery了
  • Wait:只要copies大于1,就将消息分给碰到的节点,直到1。当节点只有一份的时候,就等待碰到目的节点(想想DirectDelivery)

论文证明了减半分发(Binary Spray and Wait)是最优的(the minimum expected delay)。确切地说,节点An copies,遇到节点B,此时将n/2 copies(上取整)给B,节点A留下n/2 copies(下取整)。

2. SprayAndWait

2.1 设置文件

由上述分析可知,SprayAndWait需要事先知道消息的份数以及分发策略,相关设置字段如下:

//*_settings.txt
Group.router = SprayAndWaitRouter
SprayAndWaitRouter.nrofCopies = 10      //消息的份数
SprayAndWaitRouter.binaryMode = true    //true为一半一半地分,false为一份一份地分

//SprayAndWaitRouter.java
public static final String NROF_COPIES = "nrofCopies"; //identifier for the initial number of copies setting
public static final String BINARY_MODE = "binaryMode"; //identifier for the binary-mode setting
public static final String SPRAYANDWAIT_NS = "SprayAndWaitRouter";  //SprayAndWait router's settings name space

public SprayAndWaitRouter(Settings s) {
    super(s);
    Settings snwSettings = new Settings(SPRAYANDWAIT_NS);
    initialNrofCopies = snwSettings.getInt(NROF_COPIES);
    isBinary = snwSettings.getBoolean( BINARY_MODE);
}

2.2 增加消息字段

每个消息需要一个字段保存份数copies,因此,需要为Message添加新的字段。我之前的做法是直接修改Message类,今天看了SprayAndWaitRouter.java的源码,原来还可以这样:重写createNewMessage,在原来基础上利用函数msg.addProperty添加字段。源代码如下:

//SprayAndWaitRouter.java    
@Override
public boolean createNewMessage(Message msg) {
    makeRoomForNewMessage(msg.getSize());
    
    msg.setTtl(this.msgTtl);
    msg.addProperty(MSG_COUNT_PROPERTY, new Integer(initialNrofCopies)); //添加字段
    addToMessages(msg, true);
    return true;
}

//MSG_COUNT_PROPERTY为SprayAndWaitRouter.copies
public static final String MSG_COUNT_PROPERTY = SPRAYANDWAIT_NS + "." +    "copies"; 

取得和更新该字段值的方法如下(可参见下面的getMessagesWithCopiesLeft函数):

Integer nrofCopies = (Integer)m.getProperty(MSG_COUNT_PROPERTY); //取值
msg.updateProperty(MSG_COUNT_PROPERTY, nrofCopies);              //更新

2.3 update

SprayAndWait的update函数很简单,类似于Epidemic的tryAllMessagesToAllConnections,但更严格,即消息队列过滤掉那些copies1的消息。源代码如下:

//SprayAndWaitRouter.java
public void update() {
    super.update();
    if (!canStartTransfer() || isTransferring()) {
        return; 
    }
    if (exchangeDeliverableMessages() != null) {
        return;
    }

    //获取缓冲区有效消息集合,即copies大于1的消息
    List<Message> copiesLeft = sortByQueueMode(getMessagesWithCopiesLeft());
    if (copiesLeft.size() > 0) {
        this.tryMessagesToConnections(copiesLeft, getConnections());
    }
}

2.3.1 getMessagesWithCopiesLeft

getMessagesWithCopiesLeftgetMessageCollection()的基础上,过滤掉那些copies小于1的消息,源代码如下:

//SprayAndWaitRouter.java
protected List<Message> getMessagesWithCopiesLeft() {
    List<Message> list = new ArrayList<Message>();
    for (Message m : getMessageCollection()) {
        Integer nrofCopies = (Integer)m.getProperty(MSG_COUNT_PROPERTY);
        assert nrofCopies != null : "SnW message " + m + " didn't have " + "nrof copies property!";
        if (nrofCopies > 1) {
            list.add(m);
        }
    }
    return list;
}

2.4 更新消息的份数

假设A发送消息mB,那么传输完毕后,AB的缓冲区都有m,都需要对m更新copies。值得注意的是,更新发送端和接收端都由A发起,源代码如下:

//ActiveRouter.java
public void update() {
    super.update();
    ...
    if (con.isMessageTransferred()) {  //消息是否传输完毕,即是否过了(1.0*m.getSize())/this.speed没
        if (con.getMessage() != null) {
            transferDone(con);       //更新发送端
           con.finalizeTransfer();    //更新接收端
        }
    }
    ...
}

//Connection.java    更新接收端
public void finalizeTransfer() {
    this.bytesTransferred += msgOnFly.getSize();
    getOtherNode(msgFromNode).messageTransferred(this.msgOnFly.getId(), msgFromNode); //更新接收端
    clearMsgOnFly();
}

2.4.1 更新发送端

//SprayAndWaitRouter.java
@Override
protected void transferDone(Connection con) {
    //步骤1:取得消息的copies
    Integer nrofCopies;
    String msgId = con.getMessage().getId();
    Message msg = getMessage(msgId);
    if (msg == null) {
        return; 
    }
    nrofCopies = (Integer)msg.getProperty(MSG_COUNT_PROPERTY);
    
    //步骤2:更新消息的copies
    if (isBinary) {
        nrofCopies /= 2;
    } else {
        nrofCopies--;
    }
    msg.updateProperty(MSG_COUNT_PROPERTY, nrofCopies);
}

2.4.2 更新接收端

//SprayAndWaitRouter.java  
@Override
public Message messageTransferred(String id, DTNHost from) {
    Message msg = super.messageTransferred(id, from);
    
    //步骤1:取得消息的copies
    Integer nrofCopies = (Integer)msg.getProperty(MSG_COUNT_PROPERTY);
    assert nrofCopies != null : "Not a SnW message: " + msg;

    //步骤2:更新消息的copies
    if (isBinary) {
        nrofCopies = (int)Math.ceil(nrofCopies/2.0);
    } else {
        nrofCopies = 1;
    }
    msg.updateProperty(MSG_COUNT_PROPERTY, nrofCopies);
    
    return msg;
}

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

发表评论

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

7 thoughts on “The ONE使用笔记:SprayAndWait路由