时隙交换网络中调度策略和性能研究

摘要

随着因特网的迅速发展，网络中新增了很多实时业务，例如视频和音频业务等。这些实时业务除了对网络吞吐量和时延有很高要求之外，还对时延抖动有严格要求。调度算法需要考虑吞吐量、时延、时延抖动和公平性四个方面的要求。时隙网络中的调度问题在忽略了同步和传播时延的情况下，一般可以表示成交换机中的调度问题，本文以交换机中调度为例，深入研究了高吞吐量低抖动的静态调度算法，可以证明时延和公平性的要求也可以相应满足。 以往的调度方法中通常将业务矩阵分解成排列矩阵的线性组合，为了达到低抖动，前人提出将业务矩阵分解成正交矩阵的组合。本文提出用遗传算法解决此低抖动分解问题，并和前人工作做了比较。 另一方面，本文深入研究了低抖动的调度问题，并将原调度模型中的矩阵分解和矩阵排列两步进行合并，提出了一种新模型，进而提出解决此问题的近似算法，接着又提出用遗传算法和遗传模拟退火混合算法解决此问题。在遗传算法方面，本文中设计了此问题特有的遗传算子包括编码、交叉和变异；在模拟退火方面，文中讨论了退火策略的制定方案。