改进遗传算法优化数据中心动态网络流量分配

背景知识

        通常对于大型的数据中心网络（Data Center Networks, 简称DCN）来说，每一台服务器的使用情况是非常不一样的，而平均使用的情况几乎不存在，大部分的情况都是70%的使用和流量需求会集中在一小部分的服务器上，而这个也是通过LAN网络构建云计算中心所必不可免的问题。

        如图是大部分情况下数据中心服务器使用的热点情况：

 

        可以看到，其实大部分资源是相对空置的，所以要令数据中心有更高的运算效率，可想而知就是把其他相对空置的服务器利用起来或者把他们的网络流量尽可能的分配给使用度较高的服务器。

        衡量一个数据中心的效率和优化的标准主要是单位时间的网络吞吐量（throughput）。那么如何做才可以提高网络吞吐量，从而提升数据中心的效率呢？

 

方法对比

       改进一

               添加无线网络，目前大部分的数据中心内都是使用有线网络的LAN模式，在原有的有线网络中加一个无线网络,可以达到舒缓数据传输伺服器使用不均衡所导致的传输延时,数据堵塞等问题.也可以尽量降低有线网络对于支架台（Rack）的依赖。

       改进二

                 在改进一的基础上，因为无线网络的是需要网络IP地址分配的，而IP地址的数量是有限的，所以如何动态的分配IP地址就是一个需要好好解决的问题，而改进二主要就是通过改进遗传算法，计算当前最适合的IP分配方式，从而使得总体网络的吞吐量最大。

 

遗传算法

      简介

              遗传算法其实就是模仿自然界中的生物繁殖过程，把整个过程看成三个部分：

              1. selection:选择个体

              2. crossover:交叉繁殖

              3. mutation: 变异

              简而言之，就是不断的重复计算以上三步，选择一个fitness的计算函数，当fitness达到最优的时候，就是算法的最优状态。具体介绍网上有很多，我主要讲一下这个算法的一些特点和如何改进之使得可以很好的用于动态网络中来。

      算法特点

              1. 该算法和神经网络等算法类似，都是无监督或者半监督的算法，所以在计算的过程中即使输入数据一样也有可能出现不一样的结果。

              2. 该算法考虑到了一些变异的情况，所以即使有特点1在，也不妨碍其成为一个更贴近实际情况的模拟算法。

      算法改进

              在动态网络中，类比生物繁殖的过程，也有一下几个概念：服务器、服务器组、数据中心。每个服务器组是有若干台服务器组成，所以我们类比到生物繁殖，可以把服务器等同于一个DNA，一个服务器组等同于一个个体人，而数据中心就是一个总体环境。

              而当我们在无线网络中是，可以重新组合不同的服务器成为一个服务器组，就类比于一个新的个体被繁殖生成。也就是通过crossover可以繁殖出来的新的一个generation,新的generation由多个新的“个体”组成。

              而每次迭代生成的generation都需要计算他的fitness情况，从而确定是否是最优的状态。其实就是无线网络中的IP如何分配的问题。

              具体如何根据现在有限网络的一些固有情况和无线网络的限制得出fitness计算函数和迭代过程的显示，可以查看参考文献[1]。

 

代码解释

       首先，写了一个生成模拟数的类，主要是随机数得出模拟的数据中心的网络使用情况，前提假设一共有8乘以8,64个服务器组（Rack），每个Rack最多可以20个服务器同时使用，超过15个被使用上了就表示该Rack是一个高使用率的节点。

       模拟了两个情况

       一个是比较极端的情况就是95%的使用率是在10个热点Rack上的，另一个是比较接近正常情况的情况，70%的使用率是在20个热点Rack上。

       情况一：

/* generate matrix of M1, 95% channels from 10 racks*/
void Simulation::GenerateM1(int i)
{
int m1[8][8]={0};
int x_sum=0;
srand((unsigned)time(NULL));
for(int j=0;j<10;j++){
int select = rand()%64;
int m,n;
m=floor((double)(select)/8);
n=select%8;
int channel = rand()%5;
int X=16+channel;
if(m1[m][n]==0){
m1[m][n]=X;
x_sum += X;
}
}
int total=ceil((double)x_sum/0.95);
int rest=total-x_sum;
int count_rest=rest;
while(count_rest!=0)
{
int r=rand()%64;
int m,n;
m=floor((double)(r)/8);
n=r%8;
if(m1[m][n]==0)
{
            m1[m][n]=1;
--count_rest;
}
}
char* filepath="M1_.txt";
//cout<ofstream outfile;
outfile.open(filepath,ios::app);
if(!outfile)
{
cerr<<"open error!"<exit(1);
}
outfile<for(int p=0;p<8;p++)
{
for(int q=0;q<8;q++)
{
outfile<}
outfile<}
outfile.close();
GA* ga=new GA(m1);
ga->select(ga->parent);
ga->crossover(ga->pairs);
ga->mutation(ga->children);
while(ga->check(ga->parent)==0)
{
ga->select(ga->parent);
ga->crossover(ga->pairs);
ga->mutation(ga->children);
}
//output
mutation_probability=ga->mutaion_probability;
fitness1 +=ga->MAX_FITNESS;
generation_count_1 +=ga->gen;
delete ga;
}

         情况二：

/* generate matric of M2, 70% chanels from 20 racks*/
void Simulation::GenerateM2(int i)
{
int m1[8][8]={0};
int x_sum=0;
srand((unsigned)time(NULL));
for(int j=0;j<20;j++){
int select = rand()%64;
int m,n;
m=floor((double)(select)/8);
n=select%8;
int channel = rand()%5;
int X=16+channel;
if(m1[m][n]==0){
m1[m][n]=X;
x_sum += X;
}
}

int total=ceil((double)x_sum/0.75);
int rest=total-x_sum;
int count_rest=rest;
while(count_rest>0)
{
int r=rand()%64;
int m,n;
m=floor((double)(r)/8);
n=r%8;
int channel = rand()%5+1;
if(m1[m][n]==0)
{
            m1[m][n]=channel;
count_rest -=channel;
}
}
char* filepath="M2_.txt";
//cout<ofstream outfile;
outfile.open(filepath,ios::app);
if(!outfile)
{
cerr<<"open error!"<exit(1);
}
outfile<for(int p=0;p<8;p++)
{
for(int q=0;q<8;q++)
{
outfile<}
outfile<}
outfile.close();
GA* ga=new GA(m1);
ga->select(ga->parent);
ga->crossover(ga->pairs);
ga->mutation(ga->children);
while(ga->check(ga->parent)==0)
{
ga->select(ga->parent);
ga->crossover(ga->pairs);
ga->mutation(ga->children);
}
//output 
   mutation_probability=ga->mutaion_probability;
fitness2 +=ga->MAX_FITNESS;
generation_count_2 +=ga->gen;
delete ga;
}

        改进的遗传算法

         1. 构造函数: 对数据进行初始化

     2. GA::select(Generation generate): 对每一个generation中的所有individuals随机两两一对, 得到很多对

     3. GA::crossover(vector pairs): 对所有的成对, 进行单点交叉, 生成若干个individuals , 所有的individual就形成了子代

     4. GA::mutation(Generation children): 对子代的每一个individual加以进行突变, 就是对每个individual中server按照特定的概率进行权重(weight)的变化

     5. GA::check(Generation generate): 对刚生成的子代中的每个个体计算他们的fitness, 选出最大的那一个, 作为后续是否能继续生成下一代的判断标准

     6. GA::fitness(Individual individual): 对每个个体的fitness的计算方法

      具体实现可以在资料下载中下载看，我就不都Post出来了。

 

 

参考资料

      [1]《Dynamic Scheduling for Wireless Data Center Networks》Yong Cui, Member, IEEE, Hongyi Wang, Xiuzhen Cheng, Senior Member, IEEE, Dan Li, Member, IEEE, and Antti Yla¨-Ja¨a¨ ski

 

资源下载

     实现代码下载

 

 

 转载请注明出处：http://blog.csdn.net/luoyun614/article/details/42610561