面向包-电路交换片上路由器的回退转向路由算法及所用路由器

摘要

本发明公开了一种面向包-电路交换片上路由器的回退转向路由算法及所用路由器，该算法是一种自适应路由算法，根据片上网络拥塞情况进行路由仲裁，根据链路资源的占用情况动态改变路由路径。该算法记录满足路由条件的输出端口，在遇到拥塞后重新选择输出端口，实现回退路由，从而可以充分利用网络资源，有效避免拥塞，提高平均吞吐量，减少平均包延迟；该路由器包括依次连接的输入状态机、优先级编码器、地址译码器、仲裁器和输出状态机；本发明在选择路由路径时，不向180度方向折回路由，并且不向远离目的节点的方向路由，所以不会引起死锁或活锁的问题。本发明成本低、性能高，适用于实现高性能的片上网络系统。

主权项

一种面向包-电路交换片上路由器的回退转向路由算法，其特征在于该路由算法为自适应路由算法，根据片上网络拥塞情况进行路由仲裁，根据链路资源的占用情况动态改变路由路径，记录满足路由条件的输出端口，在遇到拥塞后重新选择输出端口，实现回退路由，避免拥塞；具体步骤如下：1)如果X方向和Y方向的输出端口同时满足路由条件并且至少有一个方向不被占用，那么存储这两个输出端口号；如果只有X方向或Y方向中的一个输出端口满足路由条件且不被占用，那么只储存这一个输出端口号；如果没有输出端口同时满足路由条件且不被占用，那么不存储任何输出端口号；2)在满足路由条件并且链路不被占用时，先选择X方向的链路向下一级路由器传递路由请求信息；如果X方向的下一级路由器反馈路由失败信号或者X方向不满足路由条件，则在满足路由条件并且链路不被占用时，选择Y方向的链路向另一个下一级路由器传递路由请求信息；如果Y方向的下一级路由器又反馈路由失败信号，则向上一级路由器反馈路由失败信号。