交换结构(switch fabric)作为交换机和路由器的核心,如何提高其交换容量可扩展性和服务质量可预测性,是近十年来网络研究的一个热点和难点问题。一个典型的交换结构由三部分组成:输入端口、输出端口和交换内核。为了避免来自不同输入端口的信元同时发往同一个输出端口,需要在输出端口或者输入端口设置缓冲区,从而形成输出排队和输入排队两大基本交换结构。尽管输出排队型交换结构可以提供良好的服务质量保证(100%的吞吐率,有界的延迟,带宽公平性等),然而其存储器的带宽却需要所有输入端口带宽总和,这极大限制了其扩展性。与之相比,输入排队型交换结构允许内部存储器的带宽工作在线速,其良好的可扩展性使其成为高性能路由器的主流交换结构。由于交换结构的调度算法负责将输入端口的信元通过交换内核发送至输出端口,所以它在提高交换设备的利用率及其服务质量保证方面起着关键性作用。本文从交换容量的可扩展性及服务质量可预测性的角度出发,研究了基于输入排队的不同类型交换结构下的调度算法设计。目前,核心交换机/路由器的主流交换结构一般采用交叉开关(crossbar)以保证交换内核无阻塞,并采用集中式调度器调度定长信元通过交叉开关。对于该交换结构,具有较强理论意义的一类算法为最大权重匹配算法,已证明对于任意容许的流量,均能达到100%的吞吐率,并且平均延迟有界,然而其算法的复杂度高达O(N3),本文从局部搜索的角度研究了最大权重匹配的近似算法,结合局部搜索的可并行计算的特点,提出了一种并行随机调度算法及一种并行确定性调度算法,并且证明了算法的稳定性,与已有近似算法相比,具有更低的平均延迟。缓冲交叉开关型交换结构由于具有分布式存储及分布式调度的特点,是构建特比特级(Terabit)路由器的一种理想选择。由于轮转型调度算法易于硬件实现,具有较高的应用价值,从而得到了广泛的研究。现有轮转型算法在调度均匀流量时具有逼近100%的吞吐率,然而对于非均匀的流量,现有轮转型算法的吞吐率却明显下降。为解决此问题,与当前的单轮转指针不同,本文提出了一类双轮转指针的调度算法,即在每个输入调度器均设置了主指针与辅助指针,主指针对应的队列具有最高的调度优先级,算法可以根据各个队列的状态来动态决定何时更新主指针,当主指针对应的队列被流控机制阻塞时,将根据辅助指针依次公平服务其他队列。仿真实验表明,对于每个交叉点缓冲区仅有一个信元的交换结构,基于双指针的调度算法可以显著提高该交换结构在已知多种非均匀流量下的性能。对于缓冲交叉开关型交换结构,一般采用基于份额的流控机制,在这种方式下,为了确保输入和输出端口都可以工作保持(work-conserving),每一个交叉点缓冲区大小至少需要线速乘以交换结构内部环路延迟,对于特比特级、多机柜的交换机,其交叉点缓冲