摘 要: 重点分析了RIP和OSPF协议在大型NoC中的适用性，在此基础上提出了一种分布式路由管理框架，它能有效地实现大型NoC动态路由" title="动态路由">动态路由方法。
关键词:动态路由管理  NoC  分布式

    据有关资料介绍，到2010年，单颗芯片集成的晶体管数量将达到10亿、工作频率将达到10GHz、特征尺寸将小于100nm(当特征尺寸为35nm时，集成在一颗芯片内的IP核可以达到1000以上)、工作电压将小于1V^[1]。因系统互连的可伸缩性受限于当前SoC所采用的基于总线的共享通信资源，而NoC可伸缩性好、能兼容已有IP核的设计和重用性、能满足SoC设计者将产品尽快地推向市场的时间要求。因此人们提议采用片上网络NoC(Network-on-Chip)来解决系统互连的可伸缩性问题^[2-6]。  NoC的概念源于计算机网络^[7]。OSI参考模型^[8]将计算机网络分成七层以减少设计复杂性，每层向上层提供特定的服务，并屏蔽本层的实现细节，只有同层的实体才能通信和交换数据。为便于研究和设计实现，NoC的通信复杂性也可以由OSI参考模型进行描述。与计算机网络相比，用于NoC的硅面积和功耗受到严格限制。
    NoC面向的应用不仅包括计算机系统内访存、中断，还包括视频、语音、实时控制信号传送等应用，因此，NoC必须提供可靠的高性能服务。要提供可靠服务及可伸缩性，NoC必须实现动态路由，为此，需要采用分布式路由管理策略。
    RIP^[9]和OSPF^[10]是因特网普遍使用的动态路由协议" title="路由协议">路由协议，本文着重分析了RIP和OSPF协议在NoC中的适用性，并在此基础上提出一种分布式路由管理框架，它能有效地实现NoC动态路由方法。
1 NoC的路由问题
    在英特网中，基于分组的通信代替了电路交换以增加通信的可靠性。NoC采用了因特网基于分组通信的思想，但是弱化了可靠通信的优点，因为在NoC中没有实现动态路由。当前，人们在研究NoC时都假定NoC是稳定的，不会发生链路" title="链路">链路或路由器失败，但是随着单颗芯片集成的晶体管数量和工作频率的增加以及特征尺寸减少和工作电压降低，使深亚微米问题日益严重，链路或路由器失败问题不可忽视。目前NoC普遍采用静态XY路由策略^[6]，它实现简单，但是不能处理链路或路由器失败等问题，而动态路由在路径发生变化时可以动态选择新的路由，因此NoC实现动态路由是必然选择。
下面分析英特网普遍使用的动态路由协议RIP和OSPF在NoC中的适用性。
1.1 RIP
    RIP协议使用距离向量路由，每台路由器维持一张路由表" title="路由表">路由表，存放可用的目的地址和能到达该目的地址的链路信息，并能将该信息送往所有邻居路由器。距离向量路由仅使用目的地址和邻居路由器信息，是一种简单路由机制。但是距离向量路由可能导致无限计数问题，若分组在链路失败，则可能导致在两个结点无限循环，该问题的解决方法对于NoC同样适用。例如，“split horizon with poisoned reverse”限制最大跳数，并触发更新^[9]。
1.2 OSPF
    OSPF协议使用链路状态，与RIP协议不同，它将邻居路由器信息广播给网络上所有的路由器。该机制基于“一张分布式表”，每台路由器均保留该表的备份，并按一定规则更新。其目标是每台路由器均有整个网络状态的相同视图；链路状态协议需要每台路由器均知道一条链路的up/down状态和通信代价，计算到达目的地的总代价。
    在NoC环境中，可通过实现静态路由表来简化链路状态协议的复杂性。NoC环境中不可能有新结点加入网络，路由表不会增加，当一条链路进入down状态时，只有相关表项需要从路由表中删除，不需要对NoC拓扑结构" title="拓扑结构">拓扑结构进行手工干预。因此可以对链路状态协议进行改造，使之适合于NoC。适合于NoC的链路状态协议简化模型描述如下：（1）每次上电时进行网络配置。网络拓扑、结点之间的距离及数目可提前预知，每个邻居的通信代价可在上电时通过计算得到，基于这些信息即可在每台路由器建立和存储路由表。（2）当网络拓扑发生明显变化时，如链路进入down状态或路由器失去功能时，发送ECHO分组，以计算新路径的通信代价并改变网络配置，其路由表要用最新的配置信息进行构建，但不需要在网络上频繁发送更新信息。（3）拓扑结构发生改变时，使用Dijkstra最短路径优先算法计算最佳路径。
2 大型NoC分布式路由管理框架
    通常，NoC路由器功能简单，不具有路由表的建立和管理功能，需由与NoC路由器邻近的CPU核完成。而目前所提议的NoC结构中路由器与IP核有一一对应关系，路由器与IP核通过惟一接口互连，但与路由器相连的IP核不一定具有计算功能(如存储器核)；为减少互连代价，一台NoC路由器可与邻近的多个IP核相连；为提高可伸缩性和可靠性， IP核可以通过多个网络接口与邻近的多个NoC路由器相连。一个CPU核可能完成邻近多台路由器路由表的建立和管理及路由转发表的分发工作（该CPU核称为路由主机Ghost）。但是，当网络规模变大时，使用一级编址方式路由转发表的规模将变得庞大，占用大量存储器资源和大量面积，消耗大量功耗。因此，本文提出一种适合大型NoC结构的分布式路由管理框架来解决这些问题。
    互连IP数N为1 024的一种NoC结构如图1所示，每个NoC路由器与邻近的四个IP核相连，采用二维环网(torus)或二维网格(mesh) 拓扑结构。其优点是网络规模相对较小，但是可伸缩性、可靠性相对较差，因此可以作为大型NoC低成本的组网方法。
为提高可伸缩性和可靠性，可采用IP核同时具有多个网络接口的NoC结构，其优点：(1)同一对IP核之间可并发进行数据传送，可伸缩性好。(2)通过自适应路由可提高NoC的可靠性与健壮性。(3)通过多到多CSM(Core-Switch Mapping)综合算法可降低功耗、提高吞吐率^[9]。IP核同时具有四个网络接口的NoC结构如图2所示。该结构也可使用二维环网或二维网格拓扑结构，其缺点是网络规模相对较大。

    NoC支持四类QoS服务，每类分组都设置专门的虚链路缓冲器(VCB)；输入端口控制器由分类部件和VCB构成，分类部件识别每一分组所属的类(该过程称为分类)，将分组放入相应的VCB中；路由管理单元根据分组头目的地址查找路由转发表确定分组输出端口(该过程称为路由查找，分类与路由查找可由一组硬件机制实现)，并将相应请求信号送往流控单元，对可用缓冲器计数器做减法，路由转发表由8读1写存储器实现，可供8个端口同时查找，路由转发表的内容由Ghost建立与更新；交换开关将输入端口控制器交换至输出端口控制器(该过程称为交换)。为简化交换开关设计，使用多路复接设备将同一端口所属的VCB进行时分复用，发生冲突时由专门的仲裁器进行仲裁，成功传送分组后须送流控信号给上一级路由器流控单元，对可用缓冲器计数器做加法；输出端口控制器由流控单元和调度器组成，流控单元实现链路流控算法，调度器则调度分组算法决定分组的服务顺序，分配网络资源给接受的每条连接。
    本文重点分析了因特网普遍使用的动态路由协议RIP和OSPF在NoC中的适用性，并在此基础上提出了一种分布式路由管理框架，该框架能有效地实现NoC动态路由方法。分布式路由管理框架下的高速路由查找算法将是下一步的重要研究内容。
参考文献
[1]  International technology roadmap for semiconductors.http://www.itrs.net,2006-02-28.
[2]  BENINI L, MICHELI G D. Networks on chips: A New SoC paradigm. IEEE Computers, Jan. 2002：70-78.
[3]  JANTSCH A, TENHUNEN H. Networks on chip. Kluwer Academic Publishers, 2003.
[4]  RIJPKEMA E. Trade-offs in the design of a router with both guaranteed and best-effort services for    networks on chip. Mar. 2003:350-355.
[5]  KARIM F. An interconnect architecture for network systems on Chips. IEEE Micro, 2002,22(5):36-45.
[6]  DALLY W, TOWLES B. Route packets, not wires: on-chip interconnection networks. 38th Design Automation
 Conference(DAC' 01), June 2001:684~689.
[7]  TANENBAUM A S. Computer networks, upper sadle river,  New Yersey: Pearson Education, Inc., 2003.
[8]  ZIMMERMANN H, OSI reference model - the ISO model of architecture for open systems interconnection. IEEE
 Transactions on Communications,1980,28(4):425-432.
[9]  HENDRICH C. Routing information protocol: RFC1058.IETF Network Working Group, June 1988.
[10] HENDRICH C. The OSPF specification: RFC1131. IETF Network Working Group, June 1988.