在确定网络拓扑结构后，路由算法用来决定消息通过网络到达目的地的路径。路由 算法的目标是在网络拓扑结构所提供的路径中均匀地分配流量，避免热点的出现并尽量减少竞争，改善网络的延迟和吞吐量。在实现这些性能目标的同时，遵守设计约束，避免关键路径过长、面积过大。虽然路由电路本身的功耗通常较低，但特定的路由算法会直接影响到跳数，从而大大影响到消息传输的能量消耗。此外，路由算法实现的路径多样性对于提高网络故障时的可用性也影响很大。
路由算法的类型
路由算法一般分为三类：确定性的、流量无关（oblivious）的和适应性的。虽然路由算法五花八门，但NoC最常用的路由算法是最简单的维度排序路由（dimension-ordered routing, DOR）。DOR是确定性路由算法的一个例子，在这种算法中，所有从A到B的信息总是途径同一路径，消息逐个维度地穿越网络，如下图所示。流量无关的路由算法中，消息可以选择不同的路径，但不考虑网络拥堵情况。更复杂的算法可以是自适应的，消息的路径取决于网络拥堵情况。
不同的路由算法
路由算法也可以分为最小化和非最小化的。最小化路由算法只选择源和目的地之间跳数最少的路径，非最小化路由算法允许选择可能会增加跳数的路径。在没有拥堵的情况下，非最小化路由会增加延迟和功耗，但在拥堵的情况下，可能会降低延迟。
避免死锁
在选择或设计一个路由算法时，不仅要考虑其对延迟、功耗、吞吐量和可靠性的影响，大多数应用还要求网络保证无死锁，下图就展示了一种可能出现的死锁。
由于死锁，网络中的4个包无法继续前进
确定性维度排序路由（DOR）
DOR可以由允许哪些转弯来描述，如下图所示。a可能导致死锁，而b中没有循环，不会产生死锁。
二维Mesh网络中的转弯
DOR既简单又无死锁，但也消除了Mesh网络中的路径多样性，降低了吞吐量，在平衡网络负载方面效果很差。
流量无关路由
这种路由算法选择路径时不考虑网络的状态，实现也可以很简单。如Valiant在Universal schemes for parallel communication一文中提出的随机如路由算法，对于从s到d的一个包，随机选择一个中间目的地d’，首先从s路由到d’，再从d’路由到d。通过在路由到最终目的地之前先路由到一个随机选择的中间目的地，Valiant的算法能够在整个网络中实现负载平衡，但这是以牺牲一定局部最优性为代价的，增大最大通道负载，减小网络带宽。
流量无关路由算法的例子
这种算法可以被限制为只支持最小路径，如上图所示a和b的区别。这种算法在于X-Y路由一起使用时是无死锁的。
自适应路由
一个更复杂的路由算法可以是自适应的，也就是说，信息从A到B的路径取决于网络的流量情况。自适应的路由决策可以依赖于局部或全局的信息，如缓冲区占用率、延迟等信息。和之前一样，这种算法也可以被限制为只支持最小路径，但也可以采用misrouting，允许往其他非最小的路径路由，这种情况下可能出现活锁。
对于一个完全自适应的路由算法，死锁可能是一个问题。另一个挑战是保持一致性协议可能需要的消息间排序，可以采用再目的地重新排序信息的机制，或者对某一类特定消息的路由进行限制，防止乱序。
自适应路由中的转弯
我们先前介绍了路由算法中的转弯，现在讨论转弯模型如何更广泛地应用于无死锁的自适应路由算法。
转弯模型
之前一个二维网络中的八个转弯只允许其中四个可能的转弯，现在我们允许其中六个转弯以提升算法的灵活性，如上图所示，这三种转弯模式都是无死锁的，但需要注意的是下面这种模型是可能产生死锁的。
转弯模型中的死锁
还有一些更复杂的模型，如奇偶转弯模型中，根据当前节点是在奇数列还是偶数列，消除一组的两个转弯，这种方式同样可以消除死锁，且提供更好的适应性。
多播路由
到目前为止，我们一直专注于单播（即一对一）的路由算法。然而，经常会出现这样的情况：一个核心需要向多个核心发送同一消息，这被称为广播（如果系统中的所有内核都需要得到信号）或多播（如果系统中的一个子集的内核需要得到信号），如在共享内存系统中基于广播和基于目录的缓存一致性协议。一个简单的组播实现是简单地发送多个单播，但这大大增加了流量，导致延迟高、吞吐量低。
Virtual circuit tree mul- ticasting: A case for on-chip hardware multicast support和Towards the ideal on-chip fabric for 1-to-many and many-to-1 communication等文提供了NoC组播路由的一些方法。
实现
路由算法可以在源节点或每个路由器内使用查找表来实现，组合电路可以作为基于表的路由的替代方案。实现方式需要权衡利弊，并不是所有的路由算法都能通过每一种实现方式来实现，如下表所示。
路由算法的实现方法
源节点路由
路由路径可以被嵌入到数据包的header。这种方式有几个好处，如延迟低（路由不需要计算或查询）、路由硬件少、源节点路由表可以灵活配置、支持不规则的拓扑结构、源-目的地的路由可以存储在表中供随机选择以提升负载平衡；也有一些缺点，如需要在数据包中额外存储路径（且根据网络变大而变大）、难以根据网络条件动态避免拥堵。
节点表
这种方法在每一跳时查询路由表，可以实现自适应算法，并且在做决定时可以利用每一跳的网络拥堵信息。路由表也可以是可编程的，可以通过改变路由表来绕过网络中的故障，但缺点在于增加了数据包的延迟。
组合电路路由
对简单的路由算法来说，消息可以对目的地的坐标进行编码，通过组合电路以确定接下来的路径，延迟可以非常低。通过在组合电路中实现路由决策，该算法被限定为一种拓扑结构和一种路由算法，牺牲了通用性。
2-D Mesh网络中的路由电路
自适应路由
自适应路由算法需要跟踪网络拥堵程度的机制，并更新路由路径。路由的调整可以通过修改header、在电路中添加是否拥堵的信号作为输入、实时更新路由表条目等方法实现。这种方式的好处是通过基于网络条件的路由决策，网络可以实现更高的带宽，并减少数据包的拥堵延迟；缺点是实现复杂，基于拥堵的路由决策需要额外的电路，增加路由决策的延迟和路由器的面积，可能需要从相邻的路由器沟通额外的信息，这种额外的通信可能会增加网络面积和功耗。