织梦搭建商城网站,开个公司大概需要多少钱,爱站网备案查询,安徽企业网站制作目录
一、概述
二、路由算法的类型
三、避免死锁
四、实现
4.1 源路由实现
4.2 基于节点查找表的路由实现
4.3 组合电路实现
五、总结 一、概述 路由算法#xff08;routing algorithm#xff09;#xff0c;即决定数据包在网络拓扑中从起点到终点路径的算法。路由算…目录
一、概述
二、路由算法的类型
三、避免死锁
四、实现
4.1 源路由实现
4.2 基于节点查找表的路由实现
4.3 组合电路实现
五、总结 一、概述 路由算法routing algorithm即决定数据包在网络拓扑中从起点到终点路径的算法。路由算法的目标是尽可能地在网络拓扑中均匀分配网络流量以避免出现热点hotspot并最小化竞争contention从而降低网络延迟并提高吞吐量。
二、路由算法的类型 路由算法总体上可以分成三大类确定性路由deterministic routing、无关路由oblivious routing和自适应路由adaptive routing。 尽管目前已经提出了各种各样的路由算法但是在片上网络中应用最广泛的路由算法是简单的维序路由dimension-order routingDOR。维序路由是一种确定性路由算法所有从节点A向节点B移动的数据包都通过相同的路径。在DOR中数据包在网络拓扑中按照确定的顺序移动先在一个维度下移动到与目的节点相匹配的位置然后在下一个维度下移动到与目的节点相匹配的位置以此类推最终抵达终点。 另一类路由算法是无关路由oblivious routing数据包从节点A向节点B移动时可以有多种不同的路径选择然而路径的选择不考虑网络的拥塞congestion。例如一个路由器能够预先随机挑选一条可选路径然后发送数据包。 第三类路由算法是更为复杂的自适应路由adaptive routing一个数据包从节点A移动到节点B的路径取决于当前的网络流量traffic情况。 路由算法也可以按照最短路由与非最短路由进行分类。最短路由仅选择跳数最小的路径。非最短路由可以选择跳数非最小的路径。在没有拥塞的情况下采用非最短路由的数据包会通过额外的节点和链路因此增加延迟与功耗。但是选择非最短路径来避免或减少拥塞往往会比选择存在拥塞的最短路径具有更低的传输延迟。
三、避免死锁 在选择或设计路由算法时不仅需要考虑延迟、功耗、吞吐量和可靠性大多数应用也要求网络能够保证无死锁。简单来说死锁是由多个数据包在传输路径上形成了打结的环路knotted cycle造成的。下图展示了一个由4个数据包的路径形成的死锁A、B、C和D分别代表有路由器的网络节点有箭头的折线代表数据包的流动方向。其中每个数据包都等待着当前被其他数据包所占据的路径释放因此每个数据包都无法移动从而形成死锁。可以看到数据包之间的依赖和占用关系形成了一个环路每个数据包都无法进一步向自己的目的节点传输。 死锁可以通过以下两种方式避免 设计路由算法以避免在网络中形成打结的环路设计数据流控制协议flow control protocol以避免路由器缓冲器buffer的占用和请求构成循环依赖。 四、实现 本节讨论各种路由算法的实现选择。路由算法可以通过在源节点或在路径上每个节点的路由器中使用查找表来实现另外还可以使用组合电路来替代基于查找表的方式实现。具体实现时会有各种各样的权衡取舍并且不是所有的路由算法都能被每一种实现方式所支持。
4.1 源路由实现 路由算法能够采用很多种方式实现。首先路由信息可以在源节点处集成到数据包的报头中这种方式叫作源路由。例如对于2×3的mesh结构从左下角到右上角的路由可以编码为EENNNX其中的符号含义E 表示东east),N 表示北north),S表示南south),W 表示西west),X 表示弹出eject)]在数据包的路由过程中每一跳的路由器将会从路由报头中读取上述编码中最左边的方向信息并根据这个方向信息将数据包发送到具体的输出链路上同时去除报头中当前路由器所使用过的方向信息。
4.2 基于节点查找表的路由实现 许多复杂的算法都是使用路由表来实现的其中每个节点的路由器都维护了一张表来记录数据包为抵达某个特定的目的地而需采用的输出链路。在这个机制下数据包在每一跳的路由器处获取路由信息而不是在起点处获取所有的路由信息。这个机制也支持自适应路由算法因为每一跳都可以利用网络的拥塞信息进行相应的自适应决策。
4.3 组合电路实现 数据包可以编码目的节点的坐标并且在路径上每个节点的路由器中使用比较器来决定是否接收即从本节点弹出或传递这个数据包。因为其开销小简单的路由算法在路由器中一般都以组合电路的形式实现。 对源路由而言数据包必须有足够的空间以携带用来指定整条路径的所有数据位。组合电路实现的路由仅要求数据包携带目的节点标识符。实现路由算法的整个电路非常简单并且具有非常低的延迟。下图展示了一个在2D mesh 拓扑中基于当前缓冲区占用情况计算下一跳的组合电路。其中路由选择也可以采用维序路由而不考虑缓冲区中的队列长度。 五、总结 本文介绍了片上网络的路由设计与实现路由可以分成确定性路由deterministic routing、无关路由oblivious routing和自适应路由adaptive routing。实现方式可以大体上分成源路由实现、基于节点查找表的路由实现和组合电路实现。
