有关Bcube拓扑结构节点分层方法的思考

 Bcube是SIGCOMM2009提出的一种云计算数据中心网络拓扑结构，虽然说目前业界使用的DCN拓扑结构仍然以树形结构为主，但这丝毫不能影响Bcube在学术界地位，如果你做的工作只能适用于clos型结构，必然就会有人那Bcube来质疑你。

Bcube是以服务器作为交换核心，整个结构采用递归定义，结构虽然工整但是比较复杂。因此对交换机归类就对我们研究网络自配置有一定的意义（其他方面的意义还没有深入思考过）。

对Bcube switch的归类，我们打算采用基于层次的划分，虽然在拓扑图上看switch的层次明显，但是在只有拓扑邻接矩阵和节点设备类型作为输入的情况下，也并不是很容易。经过研究，我们基于以下规律设计拓扑层次划分算法：处于同一层次的switch所连接的server是没有交集的。因此我们的算法设计如下：

将所有server和switch节点装入两个链表中（serverlist，switchlist），从switch中取出一个节点，然后在serverlist中找出与这个switch相连的节点，把一个标志位置为1，然后再取出别的switch节点，当所有serverlist中的节点标志位都为1的时候，把switchlist里剩的元素的layer都加1，然后在把所有server的标志位置回0，重新开始这个过程，知道switchlist为空。当然在这个过程中肯定会出现回溯。所以在实现上我采用了递归的方法，整个算法过程有点类似于打印数字全排列。具体的代码如下：

 

public class BcubeLayer {
	public static List<Node> switches = new LinkedList<Node>();
	public static List<Node> server = new LinkedList<Node>();
	
	
	/////////////////////////初始化，把配置文件的信息读进来/////////////////////////
	public static void init(String properties){
		Properties prop = new Properties();
		InputStream inStream = null;
		try {
			inStream = new FileInputStream(properties);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		try {
			prop.load(inStream);
		} catch (IOException e) {
			e.printStackTrace();
		}
		Enumeration enums = prop.keys();
		while (enums.hasMoreElements()) {
			String key = (String) enums.nextElement();
			PropReading pr = new PropReading();
			
			if(pr.BcubeLeaf(key)==true){
			//	System.out.println(key);
				Node n = new Node();
				n.layer=0;
				n.number=key;
				n.type=0;
				n.state=0;
				n.relation=pr.GetRelationship(key, properties);
				server.add(n);
			}else{
				System.out.println(key);
				Node n = new Node();
				n.layer=0;
				n.number=key;
				n.type=1;
				n.state=0;
				n.relation=pr.GetRelationship(key, properties);
				switches.add(n);
			}
		}
		
		for(int i = 0 ; i < switches.size() ; i++){
			switches.get(i).show();
		}
		System.out.println("..........................");
		for(int i = 0 ; i < server.size() ; i++){
			server.get(i).show();
		}
		System.out.println("..........................");
	}
	
	
	///////////////////////分层////////////////////////////
	public static void layer(){
		//server list变成空，同属于某一层的switch被找到
		int flag = 0;
		for(int i = 0 ; i < server.size(); i++){
			if(server.get(i).state==0){
				flag=1;
				break;
			}
		}
		System.out.println(flag+"=============");
		if(flag == 0){
			for(int i = 0 ; i < switches.size(); i++){
				if(switches.get(i).state==1){
					switches.get(i).layer++;
				}
			}
			for(int i = 0 ; i < server.size() ; i++){
				server.get(i).state = 0;
			}
		}
		
		//switch list变成空，算法结束
		int flag2 = 0;
		for(int i = 0 ; i < switches.size() ; i++){
			if(switches.get(i).state == 0){
				flag2=1;
				break;
			}
		}
		System.out.println(flag2+"........");
		if(flag2 == 0){return;}	
		
		for(int i = 0 ; i < switches.size() ; i++){		
			if(switches.get(i).state==0&&switches.get(i).layer==0){
				//System.out.println(switches.get(i).number);
				List<Integer> relateserver = new LinkedList<Integer>();
				int flag3 = 0;
				for(int m = 0; m<switches.get(i).relation.size();m++)
					for(int j = 0; j<server.size() ; j++){
						if(switches.get(i).relation.get(m).equals(server.get(j).number) && server.get(j).state==0){
							relateserver.add(j);
						}else if(switches.get(i).relation.get(m).equals(server.get(j).number) && server.get(j).state!=0){
							flag3=1;
							break;
						}
					}
				if(flag3==0){
					for(int n = 0 ; n < relateserver.size() ; n++){
						server.get(relateserver.get(n)).state = 1;
					}
					switches.get(i).state=1;
					layer();
					switches.get(i).state=0;
				}
			}
		}		
	}

		
	
	public static void main(String args[]){
		init("bcube-test'.properties");
		layer();
		for(int i = 0 ; i < switches.size() ; i++){
			switches.get(i).show();
		}
		for(int i = 0 ; i < server.size() ; i++){
			server.get(i).show();
		}
	}
}