DirectDelivery
路由无疑是最简单的,其他的路由的update
,最开始的代码与DirectDelivery
是一样的。本文介绍DirectDelivery
,旨在进一步了解ActiveRouter.update
、MessageRouter.update
、isTransferring
、canStartTransfer
、exchangeDeliverableMessages
。
目录
1. DirectDelivery
1.1 路由策略
DirectDelivery
路由策略很简单,每个节点携带自创建的消息,不断移动,直到遇到目的节点,才把消息传递出去,整个通信过程从不借助其他节点。这点方法优点很明显,开销是最低的,但缺点也很明显,效率是最低的。作为路由的一种极端,通常作为benchmark与其他协议进行比较。
1.2 源代码
DirectDelivery
的源代码是最简单的,其他的路由的update
,最开始的代码与DirectDelivery
是一样的,比如判断该节点是否正在传输数据。DirectDeliveryRouter
的update
源代码如下:
//DirectDeliveryRouter public void update() { super.update(); //调用父类的update, 详情见2 if (isTransferring() || !canStartTransfer()) { //判断能否进行传输,详情见3 return; } if (exchangeDeliverableMessages() != null) { //若有目的节点就在本节点或者邻居节点的消息,详情见4 return; } }
2. super.update
DirectDeliveryRouter
的继承关系是这样的:DirectDeliveryRouter —> ActiveRouter –> MessageRouter
。update
都会被重写并调用上一层的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件事:
- 处理已完成传输的数据包,详情可参考博文《The ONE使用笔记:深入源码理解消息接收过程》
- 中止那些断开链路上的数据包
- 必要时,删除那些最早接收到且不正在传输的消息
- 丢弃那些TTL到期的数据包(只在没有消息发送的情况),详情可参考博文《The ONE使用笔记:消息生存时间TTL及丢包》
- 更新能量模板,本人还未涉及,暂不展开讨论
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
如果本节点没有消息的目的节点是邻居节点,那么看看邻居节点是否有消息的目的节点在本节点。DTNHost
的requestDeliverableMessages
调用ActiveRouter
的requestDeliverableMessages
。源代码如下:
//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)
- The ONE使用笔记:DirectDelivery路由
- The ONE使用笔记:Epidemic路由
- The ONE使用笔记:SprayAndWait路由
- The ONE使用笔记:MaxProp路由
- The ONE使用笔记:Prophet路由
- The ONE使用笔记:实现Bubble Rap
微信赞赏
支付宝赞赏
您好,我一路追踪下来
exchangeDeliverableMessages( ) ->tryMessagesForConnected( )->ActiveRouter.startTransfer( ) ->
Connection.startTransfer( ) ->
CBRConnection.startTransfer( ) ->
DTNHost.receiveMessage( ) –> ActiveRouter.receiveMessage( ) –> MessageRouter.receiveMessage( )
请问为什么最终只是看到ml.messageTransferStarted( )–>nrofStarted++; 而不是messageListener中的messageTransferred()–>nrofDelivered++ 呢?
这里的exchangeDeliverableMessages( )不是说“用于交换该节点与邻居节点间的消息,这些消息的目的节点是该节点或者其邻居节点。”消息应该被delivered了呀
消息开始传输,并不能保证该消息就成功投递(比如在传输过程连接中断)。真正的消息传输完成是在MessageRouter.java中的messageTransferred函数,包含有如下代码:
for (MessageListener ml : this.mListeners) {
ml.messageTransferred(aMessage, from, this.host, isFirstDelivery);
}
你再去看MessageStatsReport.jave的messageTransferred就有this.nrofDelivered++。
你可以进一步参考如下博文:
The ONE使用笔记:深入源码理解消息转发过程
http://sparkandshine.net/en/the-one-use-notes-understand-deeply-process-message-transfer-with-source-code/
The ONE使用笔记:深入源码理解消息接收过程
http://sparkandshine.net/en/the-one-use-notes-understand-deeply-process-message-receive-with-source-code/
The ONE使用笔记:深入源码理解消息监听器
http://sparkandshine.net/en/the-one-use-notes-understand-deeply-message-listener-with-source-code/
你好,请问在消息机制中的reponseSize属性是不是设置成1就会自动回复呢?还有我最近在用ONE实现带有缓存节点的网络,如何在检测到请求的消息在缓存节点上存在的时候就返回呢?
reponseSize实际上是消息大小message size。默认值为0,表示不需要response。
请问,DTNHost other = con.getOtherNode(getHost()); //即得到本节点 意思是:邻居节点有消息的就是本节点么?
不是。建议你再看看博文。
//如果没发送成功,看邻居节点的缓冲区是否有消息的目的节点是该节点,若是,尝试传输
for (Connection con : connections) {
if (con.getOtherNode(getHost()).requestDeliverableMessages(con)) {
return con;
}
}
我自己有实现过Bubble Rap,详情见这里:
http://sparkandshine.net/en/the-one-use-notes-implement-bubble-rap/
特别是第二个判断? 是判断消息是否已经到达目的节点吗?那还要判断邻居节点是否是目的节点干嘛呢?如果邻居节点是目的节点的话 不是还要传输一次吗?
你好我想问问 这个路由算法的update()里 判断了if (isTransferring() || !canStartTransfer()) { //判断能否进行传输,详情见3 return; }if (exchangeDeliverableMessages() != null) { //若有目的节点就在本节点或者邻居节点的消息,详情见4 return; }判断完什么也不做是什么意思啊 这里始终不是很了解。希望给予指导。
假设A与B相遇,A有消息,其目的节点是B(或者说B有消息,其目的节点是A)。exchangeDeliverableMessages() != null,意思是说A与B完成一个消息的交换,本次循环就结束了。你可以理解成此时信道被占用了,不能再发送其他消息了。