动态非探测式路由选择策略设计及研究.docVIP

动态非探测式路由选择策略设计及研究 摘要：本文研究了动态的、非探测式的路由选择策略提高了自适应路由算法的传输效率，由于避免使用网络状态探测包，减少了缓存面积开销和额外能耗，是一种适合于片上网络自适应路由算法的选择策略设计方法。 关键词：路由选择策略；片上网络；自适应路由算法 中图分类号：TP212.9文献标识码：A文章编号：1007-9599 (2012) 06-0000-02 一、SDNS策略设计 简单动态非探测式路由选择策略（SDNS）是动态非探测式路由选择策略的一种具体实现算法。SNDS策略对各可选输出方向分配相同权值的等待时钟周期tc，对于第一个输出方向，如果数据包在tc内不能发送出去，说明此刻此方向阻塞，则直接转向下一个可选通道方向探测，按此方式轮询，直到数据包发送出去为止。 文献表明，在一致性的流量模型中，由于维序寻径的方式和一致性的流量模型相匹配，所以维序寻径能够给网络带来均衡的传输流量，避免数据包向网络的中央区域聚集，均匀使用网络资源，降低网络传输延迟。路由选择策略中的直线传输策略能够使数据包尽量按照类似维序寻径的方式传输。所以，在SDNS路由选择策略中，如果数据包直向传输的方向是S中的元素，则第一次传输方向的选择此方向作为当前数据包第一次尝试传输的方向目的是为了提高路由选择策略对不同传输模型的适应性。 进一步考虑在SNDS策略中应用直向传输策略的可行性。由于避免通道环相关的自适应路由算法限制的是某些转弯，因此直线方向一定不会使算法产生死锁。在网络负载不高的情况下，在直线传输方向上，数据包若能以较高的概率传输出去，数据包的传输类似于维序寻径的传输方式。将直线选择策略和SDNS路由选择策略结合起来，使自适应路由算法具有了静态路由算法的优点。当网络负载增大时，数据包若在直线传输产生拥塞，就能够迅速转向其他的方向传输，保证了算法的灵活性和适应性。 二、DOFS策略设计 由于没有探测式信息作为仲裁依据，SDNS策略只能够按照均等的概率探索可用通道。数据包头在探测阻塞的过程中可能会错过可用的通道，使得此数据包在节点上的传输延迟增加。这种情况发生的概率随着待选输出通道数的增加而增加。为解决这个问题，本文设计实现了另一种动态非探测式路由选择策略——数据包输出信息反馈策略（DOFS, Data Packet Output Information Feedback Selection）。 和SDNS选择策略相同，DOFS选择策略采用动态方向选择，以避免唯一输出方向长时间等待而导致的性能降低。DOFS选择策略转换方向的控制方法与SDNS策略相同，在此不赘述。与其不同的是，DOFS选择策略没有采用等概率探索的方式，而根据输出端口状态表动态地分配各个备选输出方向被请求的次数，从而提高请求成功的概率。DOFS利用已经传输数据包在本节点上探测以及最终发送结果的信息作为衡量各输出方向拥塞状况的依据，并更新输出端口状态表，以此作为DOFS策略仲裁的依据。 数据在请求通道时，如果输出端口对应方向邻居节点缓存的被占用，请求会被拒绝。DOFS选择策略将数据包在节点上探索可用通道过程中的信息记录下来，用nsend 和nrequest分别表示某一个输出方向实际传输的数据包数和请求传输的数据包数，用输出端口请求成功率routport反映输出端口发送数据包的能力，定义如下。routport值越大表示此方向阻塞的状况越轻，则赋予端口更大的权值。由于网络状况在不断变化，routport的准确性也随着时间延长而不断降低，所以考虑routport的时间有效性，设其时间影响因子为f(t)，如式(1)所示(1) 输出端口状态表 网络中的每个节点都有一个输出端口状态表，用来衡量各输出端口的数据包承载能力，第一列表示节点相邻方向通道，在网孔拓扑结构中每个节点最多有四个相邻节点，所以输出端口状态表有四行；第二列表示输出端口请求成功率；为了易于实现，本文将采用的输出端口状态表。按照实际应用的需要，状态表将记录最近发送nsend个数据片对应的nrequest值以及输出端口空闲到当前时刻的时间长度 ，其分别表征输出端口请求成功率以及其时间有效性。 DOFS策略中，输出端口状态表的规模由节点输出端口数量决定，而与网络规模不相关。大小在片上网络网孔拓扑结构下，节点端口数量恒定，因此使用输出端口状态表的网络设计具有良好的可扩展性。 输出端口状态表的使用和更新 节点上的数据包请求路由时，在自适应路由计算函数得到了一组死锁避免的输出方向集合S后，则查找集合中元素i对应的输出端口状态表项，并按 式计算出各方向请求成功率routport。对于i S，若routport min=r’outport i,