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)。确切地说,节点A
有n 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
,但更严格,即消息队列过滤掉那些copies
为1
的消息。源代码如下:
//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
getMessagesWithCopiesLeft
在getMessageCollection()
的基础上,过滤掉那些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
发送消息m
给B
,那么传输完毕后,A
和B
的缓冲区都有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)
- The ONE使用笔记:DirectDelivery路由
- The ONE使用笔记:Epidemic路由
- The ONE使用笔记:SprayAndWait路由
- The ONE使用笔记:MaxProp路由
- The ONE使用笔记:Prophet路由
- The ONE使用笔记:实现Bubble Rap
微信赞赏
支付宝赞赏
@Songxiaoyu
这个不难解释,Epidemic很快将缓冲区填满,造成严重的丢包,极有可能会导致传递率下降。
除此之外,两个节点相遇的时间有限,但Epidemic要交换数据包很多,也许Epidemic在有限的时间内没能充分交换数据包或者传递了一些没有贡献的数据包,这也会导致投递率下降。
抱歉,没读过这篇文章。
同样谢谢了,我再研究研究
您好,请问Spray and Wait路由中当消息副本数等于1时,直到遇到目的节点才传输消息,这个是怎么实现的?我不太清楚哪句代码是实现这个功能的,求指导~~谢谢~~
函数update会调用exchangeDeliverableMessages(),达到你所说的目的。
/* try messages that could be delivered to final recipient */
if (exchangeDeliverableMessages() != null) {
return;
}
可以参考博文:The ONE使用笔记:DirectDelivery路由
http://sparkandshine.net/en/the-one-use-notes-direct-delivery-router/#4_exchangeDeliverableMessages
更新接收端的代码里Math.Ceil是向上取整
谢谢指正。
楼主,我运行了所有协议,缓存没有设成无限的情况下,发现Epidemic的传递率不是最高的,还不如SprayAndWait的传递率,不知道楼主的如何?
这个不难解释,Epidemic很快将缓冲区填满,造成严重的丢包,极有可能会导致传递率下降。
除此之外,两个节点相遇的时间有限,但Epidemic要交换数据包很多,也许Epidemic在有限的时间内没能充分交换数据包或者传递了一些没有贡献的数据包,这也会导致投递率下降。
Pingback: The ONE使用笔记:目录 | Spark & Shine