互联网向云计算的持续转变进一步加剧了提高网络带宽的需求。在云计算架构中,业务和数据存放于一个共享的数据中心,并通过互联网被用户所获取。用户和数据中心之间以及在一个数据中心的不同服务器间需要传输大量的流量。为了满足互连高速低时延交换等要求,为多种流量需求设计一个统一的交换机架构是非常可取的。数据交换机通常有两种架构,输入队列交换机和输出队列交换机。由于输入队列交换机每个时隙仅允许每个输入/输出端口发送/接受一个数据包,无需加速,更适合于高速实现,因此也是目前应用最广泛的交换机架构。输入队列交换机的调度算法是实现低时延、高吞吐量性能的关键。另外随着交换机规模的增大,分布式调度也应运而生。本文主要对输入队列交换机的集中式和分布式迭代调度算法两大方面进行了探讨。首先,本文研究了输入队列交换机的集中式迭代调度算法。迭代调度算法能取得极大尺寸匹配(Maximal Size Matching, MSM),是当前应用最广泛的调度算法。迭代调度算法通常由请求、授权和接受三个阶段组成,虽然有些迭代调度算法能取得很好的性能,但是依然存在提升的空间。本文首先对已有算法RR/LQF(Round Robin with Longest Queue First)进行了两方面的改进。一方面,对请求阶段进行了调整,极大程度地降低了时延,提升了性能。另一方面,在复杂度上,提出了一种流水线更新数据包计数器的机制,将其复杂度从O(NlogN)降低为O(logN),更适合于高速扩展。其次,本文提出了一种最大-最小公平的集中式迭代调度算法GRR/LRR (Global Round Robin with Local Round Robin)。GRR/LRR首先采用全局轮询调度,即优先输入-输出对,来最大化匹配尺寸,当全局轮询失败时,进一步通过每个端口的局部轮询指针来进行调度。GRR/LRR的复杂度仅为0(1)。当GRR/LRR执行一次迭代时,能获得比其他相同复杂度和通信开销的算法更好的性能。当GRR/LRR执行多至N次迭代时,我们证明它只需2-1/N倍加速即可达到稳定。最重要的是,GRR/LRR在任何数据源下均能满足最大-最小公平性规则。最后,本文研究了输入队列交换机的分布式迭代调度算法。当交换机的单边端口数目超过64时,集中式调度器受其I/O接口的限制已无法实现。因此需要采用多芯片设计,在每个输入输出端口分布独立的调度器/选择器,即分布式调度器。此时,不同芯片之间的传播时延导致输入输出端口之间存在很大的往返时间(Round Trip Time, RTT),通常为多个时隙。在大部分现存的分布式调度算法中,数据包的最低排队时延总是大于RTT。为了打破这一瓶颈,本文提出了一种请求预测(Request Prediction, RP)机制,当其应用于很多迭代调度算法时,能将低负载时延降低至RTT以下。这种请求预测的思想非常简单,复杂度仅为O(1),而且应用于不同的调度算法时可进行不同的调整以获取更好的性能。