一种基于通道依赖关系图的片上互联网络容错路由方法

摘要

一种基于通道依赖关系图的片上互联网络容错路由方法，首先，对应用程序的通信特性进行分析，建立应用程序模块的通信关系二分图，生成通信关系矩阵ATM，同时，生成无故障情况下的通道依赖关系有向图CDG，通过粗、细粒度故障检测，生成故障情况下的通道依赖关系有向图FCDG，应用转向模型最终生成对应的无环通道依赖关系有向图AFCDG及相应的数据流通信矩阵FCM，其次对ATM和FCM进行矩阵分析，选择可连通的单VC或多VC的AFCDG并对VC顺序进行设置，最后通过比较获得最佳的负载均衡路由方案，该方法通过粗，细粒度的故障检测方法最大限度地利用可用资源，构造基于单VC或多VC的带权重无环通道依赖关系有向图AFCDG实现避免死锁及负载均衡的目的。

主权项

1.一种基于通道依赖关系图的片上互联网络容错路由方法，其特征在于，包括以下步骤：步骤一、首先对应用程序模块的通信特性进行分析，分析应用程序模块是否存在通信要求，根据应用程序模块之间是否存在通信要求生成二分图，二分图中的应用程序模块分别列于源节点和目标节点两侧，实线表示对应的应用程序模块间有通信需求；并生成相应的应用程序模块通信关系矩阵ATM，ATM由对应的通信关系二分图生成，ATM中元素1表示横纵坐标对应的两应用程序模块之间存在通信需求，元素0表示应用程序模块之间不存在通信需求；步骤二、步骤二、将无故障的片上互联网络拓扑结构生成无故障情况下的通道依赖关系有向图CDG；考虑故障模型及故障分布情况，通过粗、细粒度故障检测，根据不同粒度分析模式去除发生故障的链路，生成故障存在情况下的通道依赖关系有向图FCDG；将FCDG拓扑图中构成通道环路的路径去除，生成对应的无环通道依赖关系有向图AFCDG；根据AFCDG生成片上互联网络对应的数据流连通性矩阵FCM，FCM包含无环网络拓扑结构所有的连接信息，与特定的应用程序的通信要求无关；步骤三、对ATM和FCM进行矩阵分析，选择可连通的AFCDG：首先选择单VC情况下寻找满足通信要求的FCM，即对于ATM矩阵中任意非零元素T_i，j，当FCM矩阵对应元素a_i，j亦非零时，此时FCM矩阵对应的单VC AFCDG满足通信要求，基于单VC的AFCDG容错路由方法无法满足应用通信要求，需要采用多个VC并对顺序进行设置，每个VC组合采用转向模型，2VC情况下对于ATM矩阵中任意非零元素T_i，j，FCM矩阵组合满足FCM⁰中FCM¹中FCM⁰为VC0对应的AFCDG，FCM¹为VC1对应的AFCDG，VC0和VC1采用转向模型可以进行选择，数据传输可以经由中间节点n从源节点i传输到目标节点n，满足通信要求，VC＞2解决方案相同；步骤四、通过比较通道利用率和最小、最大通道负载，获得最佳的负载均衡路线，具体为：1、对于数据流i，它的源节点和目标节点分别为S_i和D_i，在AFCDG图上增加虚拟顶点S_i和D_i，将虚拟顶点通过增加路径与AFCDG图连接起来，即增加S_i指向(S_i，x)的路径，和(x，D_i)指向D_i的路径，这里(S_i，x)为AFCDG中所有由节点S_i指向节点x的物理链路，(x，D_i)为AFCDG中所有由节点x指向节点D_i的物理链路；2、每个链路具有初始权重值W＝1，当有数据流i流过该链路时，该链路的权重将进行更新，W′为更新后权重，具体采用的权重计算公式如下：$W^{\prime }=\left\{\begin{array}{cc}\frac{1}{1-\frac{{\Sigma }_i{d}_i}{C}}& C>{\Sigma }_i{d}_i\\ \infty & C\le {\Sigma }_i{d}_i\end{array}\right.$其中C表示链路的带宽，d_i表示通过该链路的数据流i所占用的的带宽；3、Dijktra的权重最短路径算法为每条数据流选择“最大可用带宽”的路径。数据流分配按照由高到低的带宽需求依次进行分配，最小权重路径采用Dijktra算法计算获得；4、确定该数据流的路径之后将虚拟顶点S_i和D_i以及增加的路径从AFCDG删除，再用同样的方法对其他数据流依次进行分析，通过这种方式数据的传输总是选择最高可用带宽的路径为主选项进行传输，这样数据传输路径分配方法中不会发生局部路径过负载，而其余路径闲置或低负载的情况，使通道负载相对平衡。