论文部分内容阅读
Internet的迅速发展要求核心路由器必须不断地增加内部交换能力，并且提供一定的QoS控制。由于在目前存储器带宽的限制下，输入缓冲crossbar交换开关比传统的共享存储交换开关能提供更大的交换能力，因此这类开关已经在新一代的核心路由器中广泛使用。Crossbar交换开关的调度算法也成为目前研究的热点。 Crossbar交换开关调度算法的研究主要集中在三个方面，一是设计高效、公平的调度算法；二是设计支持组播的调度算法；三是设计支持QoS的调度算法。近年来，国内外学者对以上三个方面进行了大量的研究，然而这些研究工作有明显的不足，即算法的复杂性太高，很难用硬件实现。这也是众多算法只有极少数得到应用的原因。 本文针对以上不足，提出一种新的算法设计思想—大步调度思想。与其它设计思想相比，大步调度不是在每次调度，而是在更大的时间尺度上保证算法的公平性，因此减小了算法的复杂性。在大步调度思想的指导下，本文提出一种新的调度算法—ISP。与cisco路由器中使用的同类算法相比，ISP算法具有性能高、实现简单的优点。通过对ISP算法进行扩展，本文又提出了支持组播的EISP算法、支持区分服务／优先级调度的OSP算法和支持集成服务／带宽预约的RISP算法。本文还详细介绍了上述各种算法的硬件实现。 由于路由器交换变长报文，而crossbar交换定长的信元，因此变长的报文在交换开关的输入端口首先分割为定长的信元，信元到达开关的输出端口后再重新组成变长的报文。只有重组完毕的报文才能向输出链路发出。本文提出一种支持报文重组的模型—Pipe，并对重组后报文的调度进行了深入地分析。通过分析得到了在某种约束条件下，报文重组需要的缓冲区上限和报文重组延时的上限，对交换开关的设计具有一定指导意义。 本文最后还介绍了使用ISP算法和Pipe模型设计的交换开关原型—KDS50。该设计全部由FPGA／EPLD实现，交换能力可达50Gbps以上。通过Cadence verilog环境的仿真，本文还给出了对于不同长度的报文，KDS50的带宽利用率和延时特性。KDS50已在核心路由器的设计中使用。