数十年来,Internet在高速发展的同时也面临着越来越多的挑战。自2005年以来,业界逐渐意识到下一代Internet需要从根本上对当前的Internet体系结构进行革新,其中包括全新的概念模型、功能组织以及相关支撑技术。基于这一现状,本论文以下一代Internet体系结构研究为背景,以国家自然科学基金资助的下一代Internet体系结构项目“单层用户数据交换平台体系结构”为依托,重点研究下一代Internet的支撑技术之一----能够适应自相似业务流的高速交换技术。相对于传统的交换结构而言,张正尚教授等人提出的负载均衡结构LB-BvN(Load Balanced Birkhoff-von Neumann switch architecture)在满足未来的高速交换需求和对自相似业务流的适应性上都具有突出优势。该结构由两级crossbar组成和必要的缓冲组成。其两级crossbar均采用确定的、周期性连接模式,这种O(1)复杂度的crossbar连接模式排除了算法调度时间对时槽长度的影响,在数据包长度一定的情况下,时槽长度仅与端口速率有关,这意味着端口速率可以提高到微电子乃至光传输技术的极限,从而为高速数据转发提供了可能。此外,其第1级crossbar能够将到达交换结构的业务流均匀散布到中间缓存,使之能够较好地适应自相似业务流。虽然负载均衡结构能够较好地满足未来的交换需求,但数据包在其输出端可能出现失序现象。数据包失序会导致TCP报文不必要的重传和拥塞窗口不必要的缩减,从而导致传输带宽的浪费和网络利用率的下降。国内外研究机构对这一问题展开了广泛的研究,然而现有解决失序问题的方案或者复杂度较高,或者性能不够理想。一方面,如果为解决数据包失序问题的复杂度高于O(1),则必然会使整个交换流程迟滞,从而损害了负载均衡结构原本的高速交换能力；另一方面,若片面地为实现以O(1)复杂度解决失序问题而付出过高的性能代价也是不可取的。考虑到负载均衡交换结构的优良特性,本论文将其作为研究方向,重点研究能以全流程O(1)复杂度解决数据包失序问题且具有更优交换性能的解决方案。论文主要研究内容和结论如下：(1)提出一种全流程复杂度均为O(1)的负载均衡交换结构SLBA (Smart Load Balanced switch Architecture), SLBA通过引入crossbar的反向通信模式和“智能维序”的重排序机制使数据包在“恰好”不失序的时刻“离开”交换机,从而以O(1)复杂度解决数据包失序问题。理论分析和仿真实验均表明SLBA是稳定的且在低负载时(<80%)其时延性能优于Byte-Focal。(2)由于SLBA对各种时延戳的处理较为复杂且在交换结构和线卡之间需要额外的通信,这使得在超大规模和多机柜交换环境中可能产生长往返时间(Round Trip Time, RTT)问题。为此,本文将Flow Splitter和Byte-Focal相结合分别提出CFSB (Combine Flow Splitter with Byte-Focal)和LB-IFS (Load Balanced switch based on Implicit Flow Splitter)结构。CFSB用显式的Flow Splitter和VCQ (Virtual Central Queuing)缓冲模式替代Byte-Focal中的DTS (Dynamic Threshold Scheme)策略和VOQ(Virtual Output Queuing)缓冲模式,在线卡和交换结构之间无需额外通信的前提下实现了全流程O(1)复杂度且获得了比Byte-Focal更优的交换性能。但CFSB无法保证数据包离开第1级crossbar时保持先入先出特性,这使得CFSB的第3级交换时延在某些流量环境中可能会恶化,同时相对于Byte-Focal, CFSB需要更大容量的重排序缓存。为解决这一问题,本文提出基于隐式Flow Splitter和双缓冲模式(Double-Buffering Mode, DBM)的负载均衡交换结构LB-IFS, LB-IFS在保证全流程复杂度为O(1)的前提下,避免了CFSB的这一问题,同时获得了更优的时延性能。(3)基于反馈机制的FTSA (Feedback-based Two-stage Switch Architecture)结构是迄今为止理论性能最优的负载均衡结构,但其缺陷在于调度算法复杂度较高且要求算法在极短的时间内完成。因此本论文从“开源”和“节流”两个角度来解决FTSA结构所存在的问题。所谓“开源”方案即拓展调度算法的时域空间,使得调度算法能够获得更大的时间区间；所谓“节流”方案即尽可能降低算法的复杂度,从而在降低算法耗时的同时,提高交换结构的高速交换能力和可扩展性。基于这种思想,本文首先提出“开源”方案DFTS (Double-Feedback-based Two-stage Switch architecture), DFTS通过“二次反馈”的方法使得调度算法与信元传输并行工作,从而有效拓展了调度算法的时域空间。(4)为降低FTSA结构现有算法的计算复杂度,本文通过将嵌入式系统中的优先级位图算法PBA (Priority Bitmap Algorithm)与FTSA所采用的EDF(Earliest Departure First)算法相结合提出“节流”方案PB-EDF (Priority Bitmap-based Earliest Departure First)算法。PB-EDF算法继承了PBA的两个优良特性：O(1)复杂度和确定的调度耗时。引入PB-EDF算法一方面能够有效降低调度耗时,另一方面,更为重要的是在性能优异的反馈制交换结构上实现了全流程O(1)复杂度。(5) DFTS的算法调度特征使得PB-EDF无法与之协同工作,基于这一原因,本文提出交换性能略有降低但能与PB-EDF协同工作的FFTS (Front-Feedback-based Two-stage Switch architecture)结构,FFTS采用“前置反馈”的方法有效拓展了算法的时域空间。作为这一思想的延伸,本文随后通过引入一种2-错列对称(2-Staggered Symmetry connection pattern,2-SS)的crossbar连接模式提出改进的交换结构FTSA-2-SS(FTSA using2-Staggered Symmetry connection pattern)。 FTSA-2-SS在获得与FFTS等价交换性能的前提下可为调度算法拓展更大的时域空间oFFTS和FTSA-2-SS均可与PB-EDF算法协同工作,从而可同时在“开源”和“节流”两个角度协同解决FTSA所存在的问题。本论文通过对负载均衡类交换结构的综合研究,针对下一代Internet的交换需求提出了一系列解决方案,理论分析和仿真结果都表明这些交换结构或交换技术均优于现有方案。