中共湖南省委党校湖南行政学院彭劲杰 (原名彭孟良)

  1引言

    通过高性能互连系统将多个CPU构成并行计算机集群系统，是获得高性能计算的有效途径。为了提高互连系统的性能，人们从许多方面进行了大量研究，如互连硬件设备性能、并行系统的网络拓扑结构和路由算法等等。由于硬件性能受限于当前的工艺水平，且网络拓扑结构的研究非常成熟，路由算法就成了研究热点。

    在路由的实现过程中，互连网络所采用的信息交换技术决定了信息可以沿着路径传输的延时和带宽。因此信息交换技术是反映互联网性能的一个重要因素。最基本的信息交换技术有电路交换（CircuitSwitch）和报文交换（PacketSwitch）两种，其他许多改进方法都是针对这两种技术的性能改善方法，比如虫孔交换（WormholeSwitch）是对报文交换中有的路径上信息单元不足一个报文；虚跨步交换（Virtual Cut-through Switch）是鉴于电路交换与报文交换之间的技术。这些技术的改进是针对物理链路的要求而来的，而不是针对应用特点的延时与带宽需求进行的。

    从应用的角度来看，一个集群系统上往往运行了多种应用程序。不同应用的数据有不同的特点，对信息交换的性能有不同的要求，比如有的要求是低延时，而有的要求高带宽，这就要求有与之相适应的信息交换技术。电路交换与报文交换二者有不同的特点，任何一种方法都不能同时满足所有应用。为此，需要研究与多种应用需求相适应的信息交换技术。

    为了提高信息交换对应用需求的适应性，文献[2]提出了一种基于高性能输入队列的交换技术。该技术通过改进链路上设备的缓冲区来提高系统的交换性能，其优点是能适应一定范围内的信息提供高带宽低延时的服务，其缺点是需要增设缓冲区，对底层进行修改。但是不同应用的QoS标准不同，其方法只能针对应用的低延时或高带宽的多种要求同时进行优化。本文提出自适应信息交换技术的思想，是为了提高网络的信息交换性能并且可以满足不同应用的多种需求。

    2传统的信息交换技术

    2.1电路交换

    在数据传输前要在源和目的之间首先建立一条物理路径，然后在这条路径上一次将数据传送完，再释放该物理路径。

    其中物理路径的建立是通过向网络注入路由头微片来实现的（这个路由头微片包括目的地址和其他控制信息，路由探测头向目的前进，在通过中间路由器传输的同时保留物理链路。当探测头到达目的时，就建立了一条完整的路径，并向源结点返回应答）。路径建立后，消息内容就可以以硬件路径的整个带宽传送。

    电路交换的优点是：①简单，就类似于源与目的之间建立一条物理专线；②传送带宽高，因为其传送可以占领整个带宽性能。当应用中需要传送的消息很长时（消息传输时间远远大于路径建立时间），这种交换技术非常有效。

    电路交换的缺点是：①路径建立延时很长。路径的建立要求路径的每个器件都空闲；②整个消息发送期间都要占领该物理路径，有可能阻塞其他的消息，影响网络的整体利用率。

    2.2报文交换

    针对电路交换要占用整个路径的缺点，是将消息划分成固定长度的许多报文，每个报文从源结点到目的结点独立路由，报文在向下一个结点转发之前完全缓冲在每个中间结点，不需要占领独立的物理通道。为了便于控制，每个报文的前几个字节包含路由和控制信息，称作报文头。中间路由器析取头信息，确定报文转发的输出链路。

    报文交换的优点是：①不需要建立物理路径，消息传送的延时小，对消息较短和延时受限的应用来说很有意义；②在报文交换中，只要某段预留路径空闲有效的时间段，有数据需要传输时通信链路就可以充分利用，器件的并行性较好，网络的利用率高。

    报文交换的缺点是：①消息需要进行分片，会带来额外开销；②由于每个消息片独立路由，一条消息的多个报文会出现乱序等现象，整个传送的完成需要等待传送最慢的消息片；③消息传送需要有超时机制对是否传送完成进行判断，和报文重复丢弃等复杂情况进行管理。

    3.自适应信息交换

    不同的应用对消息交换有不同的要求。比如在集群系统上运行科学计算中的障碍同步操作（Barrie），消息较短，操作的延时直接决定了多机并发工作的性能。这种情况就是延时受限。而对于数据挖掘应用，数据库服务器需要将某一维的所有数据进行传送，数据量大，传送的及时完成对应用服务性能有直接影响。这种需要高带宽的应用就是带宽受限。一个集群系统同时运行这些应用，就要求网络交换技术具有一定的适应性。

    3.1两种交换方式的互补性

    经分析，电路交换的优点是带宽高，但是建立链路时间太长时，同样会影响数据传递的效果；在报文交换机制中，每个片会带来额外的数据包处理开销等，如果这些开销太大，同样会引起系统的整体性能。二者结合起来，则有较理想的效果。

    电路交换与报文交换相互补的方法是指对于一个消息，如果能很快建立一条物理链路，则可以选择进行电路交换；如果在链路上的某几个结点之间能很快建立一条物理链路，则这些结点间能进行电路交换，而路径上的其余结点间采用报文交换。

    互补交换是自适应交换中的一种交换方式。在互补交换中，只需要少量的链路建立时间。

    3.2自适应信息交换思想

    所谓自适应信息交换技术就是根据实际应用的需要，自适应地选择数据交换方法，如算法一所示。算法一中，对有延时要求的短消息，自适应信息交换会选择报文交换机制进行数据传递；而对有带宽要求的长消息且比较易于建立链路，自适应信息交换会选择电路交换；对链路建立时间很长的，自适应信息交换会选择电路交换与报文交换互补的方式。

    输入：目的结点T、源结点S、数据信息M、网络拓扑结构、各结点间链路建立的统计时间信息交换的延时

    输出：信息交换方法

    算法开始：如果M短且有 要求延时短， 则输出 报文交换 如果 T与S间的链路建立时间 ≤ 阈值， 则 输出 电路交换 输出 互补交换

    算法结束

    算法一信息交换机制的选择算法

    在算法一中，需要直到各结点之间路由链路的建立时间统计情况。这些统计情况是一些历史信息，并且根据每次链路的建立情况进行修改。

    3.3自适应信息交换机制

    分别设置数据信息量的信息交换下阀值x1和上阀值x2；

    分别设置数据信息量的信息交换下阀值y1和上阀值y2。

    设置数据记忆长度N。

    近期历史记录中采用电路交换的N个数据信息，记为n1i(i=1,2,…,N)，其信息量大小为s1i，完成信息交换的延时为t1i。

    近期历史记录中提取采用电路交换的N个数据信息，记为n2j(j=1,2,…,N)，其信息量大小为s2j，完成信息交换的延时为t2j。

    具体算法实现方式如下：

    如果数据信息位于灰色区域，采用电路交换；

    否则，

    如果数据信息位于绿色区域，采用报文交换

    否则，

    如果可接受延时/数据信息量，采用报文交换

    否则，采用电路交换

    具体算法计算公式：(略)

    4结束语

    针对当今信息交换不能满足集群中多种应用需求，本文研究提出了自适应交换的思想。在研究中提出了互补交换的思想，并给出了自适应交换选择的算法。今后的工作需要将该思想进行工程实现和验证。