[Java知识库]DirectDelivery路由

1.DirectDelivery

1.1路由策略

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

1.2源代码

完整源码：

/* 
 * Copyright 2010 Aalto University, ComNet
 * Released under GPLv3. See LICENSE.txt for details. 
 */
package routing;

import core.Settings;

/**
 * Router that will deliver messages only to the final recipient.
 */
public class DirectDeliveryRouter extends ActiveRouter {

	public DirectDeliveryRouter(Settings s) {
		super(s);
	}
	
	protected DirectDeliveryRouter(DirectDeliveryRouter r) {
		super(r);
	}
	@Override
	public void update() {
		super.update();
		if (isTransferring() || !canStartTransfer()) {
			return; // can't start a new transfer
		}
		
		// Try only the messages that can be delivered to final recipient
		if (exchangeDeliverableMessages() != null) {
			return; // started a transfer
		}
	}
	
	@Override
	public DirectDeliveryRouter replicate() {
		return new DirectDeliveryRouter(this);
	}
}

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

//DirectDeliveryRouter
public void update(){
        super.update();//调用父类的update,详情见2
        if(isTransferring()||!canStartTransfer()){
            return;//判断能否进行传输，详情见3
        }
        if(exchangeDeliverableMessages()!=null){
            return;//若有目的节点就在本节点或者邻居节点的信息，详情见4
        }
    }

2 super.update

DirectDeliveryRouter的继承关系是这样的：

update都会被重写并调用上一层的update。
super用法：当前类的直接父类对象的引用

1、super(实际参数):在子类的构造方法中调用父类的构造方法
	注意: 
		1. 只能用在构造方法中
		2. 只能是构造方法的第一条有效语句
		3. 如果一个构造方法的第一行不是 this() / this(实参) / super(实参),默认是super()
2、super. : 当子类中存在和父类同名的成员变量,需要使用super 指定父类的重名的成员变量.

this用法：this关键字就是本类对象的引用。

2.1 MessageRouter.update

相当于应用式的update,取决于具体应用，类似于时间处理函数取决于具体时间，其源代码如下：

//MessageRouter.java
public void update(){
for(Collection<Application> apps: this.applications.values()){
    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);
			
			/* finalize ready transfers */
			/***1.处理已完成传输的数据包***/
			if (con.isMessageTransferred()) {
				if (con.getMessage() != null) {
					transferDone(con);
					con.finalizeTransfer();
				} /* else: some other entity aborted transfer */
				removeCurrent = true;
			}
			/* remove connections that have gone down */
			 /***中止那些断开链路上的数据包***/
			else if (!con.isUp()) {
				if (con.getMessage() != null) {
					transferAborted(con);
					con.abortTransfer();
				}
				removeCurrent = true;
			} 
			
			/***3.必要时，删除那些最早接收且不正在传输的消息***/
			if (removeCurrent) {
				// if the message being sent was holding excess buffer, free it
				if (this.getFreeBufferSize() < 0) {
					this.makeRoomForMessage(0);//必要时，删除那些最早接收且不正在传输的消息
				}
				sendingConnections.remove(i);
			}
			else {
				/* index increase needed only if nothing was removed */
				i++;
			}
		}
		
		/* time to do a TTL check and drop old messages? Only if not sending */
		/***4.丢弃那些TTL到期的数据包(只在没有消息发送的情况)***/
		if (SimClock.getTime() - lastTtlCheck >= TTL_CHECK_INTERVAL && 
				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件事：
1.处理已完成传输的数据包
2.中止那些断开链路上的数据包
3.必要时，删除那些最早接收到且不正在传输的消息
4.丢弃那些TTL到期的数据包
5.更新能量模板

3.1 isTransferring

isTransferring涵盖了上述的前三种情况，其源代码如下：

//ActiveRouter.java
public boolean isTransferring() {
//情形1：本节点正在传输
		if (this.sendingConnections.size() > 0) {
			return true; // sending something
		}
		
		List<Connection> connections = getConnections();
	//情形2：没有邻居节点
		if (connections.size() == 0) {
			return false; // not connected
		}
	//情形3：有邻居节点，但有链路正在传输
		for (int i=0, n=connections.size(); i<n; i++) {
			Connection con = connections.get(i);
			if (!con.isReadyForTransfer()) {
				return true;	// a connection isn't ready for new transfer
			}
		}
		
		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
		}
		
		// didn't start transfer to any node -> ask messages from connected
		//如果没发送成功，看邻居节点中的消息是否要传给本节点，若是，尝试传输
		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) {
			/* no messages -> empty list */
			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尝试将消息传输出去，只要有一个成功（意味着该信道被占用），就返回。

4.3 requestDeliverableMessages

requestDeliverableMessages如果本节点没有消息的目的节点是邻居节点，那么看看邻居节点是否有消息的目的节点就在本节点（若本节点没有消息要传给目的节点，那么看看邻居节点是否有消息传给本节点）。DTNHost的requestDeliverableMessages调用ActiveRouter的requestDeliverableMessages。源代码如下：

//ActiveRouter.java
public boolean requestDeliverableMessages(Connection con) {
		if (isTransferring()) {
			return false;
		}
		
		DTNHost other = con.getOtherNode(getHost());//即得到本节点
		/* do a copy to avoid concurrent modification exceptions 
		 * (startTransfer may remove messages) */
		ArrayList<Message> temp = 
			new ArrayList<Message>(this.getMessageCollection());
		for (Message m : temp) {
			if (other == m.getTo()) {
				if (startTransfer(m, con) == RCV_OK) {
					return true;
				}
			}
		}
		return false;
	}
	

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