高性能网络多级交换结构实时调度方法仿真

邹小花，夏 容

(南昌航空大学科技学院，江西 南昌 332020)

1 引言

高性能网络业务数量的不断增加，带动当代交换技术突飞猛进的发展。而多级交换技术为了满足人们的需要，朝着更高性能、高扩展性与高经济水平目标改进。单级交换结构由于环境影响、使用局限性的问题，其结构扩展性受到极大限制。为此各国学者、科研人员开始尝试使用若干个小型单级交换结构组成大型的多级交换网络，并利用网络多级交换技术优点，设计具有高性能与多端口的交换结构，为今后网络交换技术实时调度研究奠定基础。

殷晓超、韩国栋等人[1]使用交换网络多并行总线结构，同时完成多个信息流输入与输出的匹配，但由于调度方法繁琐和端口数量诸多，其结构扩展能力低，为此提出一种全新交换结构。该方法先使用模XY方式形成路由最小路径和网络信息流的平衡，再利用输出排队方法对路由各节点端口地方进行实时调度，最后根据信息控制方式对信息流包进行输送。该方法结构富有较高的扩展性，但是网络吞吐量较少；申志军、乌日更等人[2]针对交换结构中的信元矛盾、信元次序混乱、交换程序繁琐等问题，使用逆向传输机制对交换结果进行实时调度。首先使用crossbar逆向传输设备，很容易获得任意输入端口与其邻近端口的调度情况，同时对该端口反馈数据做改正处理，其次根据改正数据做调度计算，得到的结果可以有效解决信元矛盾与信元次序混乱，也不用在端口重新设立排序缓存。该方法可以对交换结构与调度过程中得到更高的时延能力，但没有保证网络负载均衡；臧韦菲、兰巨龙等人[3]发现多路径路由方式会导致信息中心网络负载不均衡与吞吐量减少，对此引入交换技术对多路径路由进行实时调度并改进。先使用SDN方法得到全部网络视图情况，再通过轮询与动态流调度方式进行网络负载均衡，提升网络吞吐量。为了降低控制器和设备间交换所带来其它负载，根据交换结构特征重新对信息流进行实时调度，最后使用分段路由方式对实时调度结果改进，得到崭新的路由，并进一步提升信息流量输送效率。该方法可以提升信息中心网络吞吐量，减少信息流完成时间，同时具有良好的负载均衡能力，但是其交换结构简单，扩展能力较低。

针对上述问题，本文提出高性能网络多级交换结构实时调度方法研究。通过信元交换方式组建多级交换结构基本元素，完成高性能网络多级交换结构设计，实现了高性能网络多级交换结构实时调度，最后根据仿真结果验证了本文方法的有效性。

2 多级交换结构实时调度方法实现

2.1 高性能网络多级交换结构设计

由于高性能网络内部链路拥挤，理想的交换结构需使用繁琐的集中式调度方式[4]，但在现实交换设备中不容易实现。为此引入一种想法：在交换网络中设立缓存，缓存装置能够有效解决多级交换网络存在问题，使其具有高吞吐量、负载均衡，有效缩短调度计算时间。

2.1.1 多级交换结构基本元素组建

高性能网络多级交换系统是由初始输入级、中间级、输出级三部分组成，其中，初始输入级与输出级使用都没有缓存空间交换结构，都是由r个没有缓存交换元素构成，n×m与m×n分别表示交换元素端口大小；而中间级则是由m个带有缓存输入端口r×r大小的交换元素构成，随意一个IS的入端口与CS的输入端口间仅仅只有一个缓存链路连接，而全部网络多级交换结构组成一个为N×N模式的交换系统，即N=n×r。每一条链路上缓存都是由一个分路设备与合路设备管理，各自完成链路上不相同目的端口信元的分路与合路作用。

为此，设定多级交换网络依然使用信元交换方法，在线路端口处完成信息包的分割和重组。链路输送与收到一个信元所经历的时间叫作一个时间隙[5]。交换结构的实时调度需在一个时间隙中完成，至此完成高性能网络多级交换结构基本元素的组建。

2.1.2 多级交换结构性能特征测算

为了更直观描述多级交换结构的特征，先给出一个简单例子：设定有一个信息流多级交换结构的初始传入端口为1号，输出端口为OS如图1所示。

图1 多级交换信元实时调度过程

从图1中可以看到该结构中删除了与信息流无关的交换元素与内部链路。

多级交换结构中信元实时调度流程[6]被认为是信息流经初始级负载均衡到中间级，然后调度出整个多级交换结构的流程。即在初始输入级，调度设备依据中间级缓存与链路的情况，把此信息流的信元均衡匹配到和其相邻全部中间级交换元素中，随后信元通过中间级元素与输出级实时调度出路由多级交换网络。同时把该部分信息流均衡到中间级链路流程里，其中有m个途径选择，该均衡特征可以由下面说明。

1)多级交换结构的扩展比

设定R表示多级交换结构能支撑最大端口链路速度，R′表示中间级模拟序列能支撑信元最大离开速度，则多级交换结构的扩展比用式(1)表示

(1)

多级交换结构的扩展比能够展现出其结构的规模[7]、内部途径数量、中间级链路使用情况、扩展能力等。在研究多级交换网络内部矛盾时，S越大，该内部矛盾发生情况就越小，在研究多级交换结构中间级链路使用价值时，并不是S值越大，使用价值越高。为此，要想得到多级交换结构较高性能与较小实现价值，就必须全方面考虑S的取值。

当S>n时，多级交换结构是稳定的。

根据上面研究得到，想要知道多级交换结构是否稳定，仅需观察一个信息流经过交换网络内部缓存过程中，所组成序列系统的稳定情况，假设此序列系统是稳定的，则该交换网络内部缓存是稳定的，多级交换网络结构是非常稳定的；反之，则不稳定。

不改变原有基础上，依旧仅研究初始端口1号输入地方，而目的端口为送出端口的信息流，详情如图1所示。设定P表示此信息流经过交换网络内部缓存过程中组成的序列系统。

针对该序列系统P，则假设λ表示信元送达流程中服从参数，得到λ≤R。同时为了满足该过程中流量均衡情况，设定λx(1≤x≤m，0≤λx≤λ)表示随意第x个中间级链路中VQ信元送达流程中服从参数，获得随意信元送达流程中服从参数与假设服从参数之间的关系式(2)

(2)

由于各中间级VQ位置是一样的，则设定初始级交换元素可以得到正确负载均衡，如式(3)所示

λx=λy，x≠y，1≤x，y≤m

(3)

式中，λy(1≤y≤m，0≤λy≤λ)表示随意第y个中间级链路中VQ信元送达流程中服从参数。根据式(2)与式(3)可知

(4)

关于中间级中每个VQ，其代表整个调度中信元提供服务流程。

而各VQ可以由n个初始端口的信息流共享，各信元进入与送达流程可以认为(n×λ)/m是输入服从参数的流程，M/M/1是服务时间服从参数为R′的序列系统。基于此设定VQ组成该序列系统为系统Q，为此序列系统m可以由P个序列系统Q组成。该系统出生率与死亡率分别表示为式(5)与式(6)

(5)

ui=R′，i≥0

(6)

式中i表示序列系统Q中用户数量。

下面验证序列系统Q稳定性。采用平稳分布方式对M/M/1系统稳定性进行描述。并根据出生与死亡流程有关知识可知出生率与死亡率的比例和

(7)

2)多级交换结构吞吐量能力分析

稳定性是多级交换结构取得高性能最关键条件，根据多级交换结构内部加入缓存，能够有效解决多级交换网络内部竞争所导致网络拥堵，该性能的升高直观表现在多级交换结构的吞吐量情况，以下推论过程反映出多级交换结构真实吞吐量性能情况。

当S>n时，多级交换结构可以达到100%吞吐量。根据该结构稳定性高，当S>n时，多级交换结构是非常稳定的，而中间级随意缓存情况都是稳定的，为此可以有效保存由竞争导致拥堵的信元，以保证信元不被丢弃[8]，根据吞吐量定义得到，此刻多级交换结构可以取得100%的吞吐量。

2.2 多级交换结构的实时调度

为了在每个时间隙传送更多信元，则采用HNN方式对其进行调度原则规定：①相同输出路线只可能收到一个信元；②相同输入线路中如果出现一样的地址的信元要依次按照先后顺序进行实时调度；③在提取出信元集合中，使用高优先级方法得出信元数最大化；④如果选择机会多时，尽可能降低输入同一传送线的信元多于一个的机会。

根据多级交换结构性能扩展到中间级缓存区，因此调度原则②做扩展时就符合要求了；调度原则③使用长队列高优先级方式，如果序列长度大于序列平均长度时，此序列的信元就被认为高优先级，在相同条件下，该系统应首先输送高优先级的信元；调度原则④，在相同时间隙上同一输入线路上可以多输送一个信元，如果条件选择多时，尽量避免这种事情发生。调度原则③与④的加入能够有效提升中间级缓存使用率，加强多级交换结构性能，缩短计算时间，降低平均时延。

使用HNN方法中的动态方程与能力方程分别为

(8)

(9)

(10)

式中τ表示电路时间常数，g表示增加系数。

采用的HNN是由N×S个神经元构成，N表示多级交换结构的输入线数，S表示输入序列数，(i，j)代表第i条输入线号，第j个输入序列的神经元。各神经元代表各序列的第一个信元。为了符合同一输入线路是同一个输出地址的信元，就需要按照先后次序输出，即原则(2)。

能量公式依据调度原则得到式(11)

(11)

公式中第一项代表同一条输出线路只能接收一个信元。(N×S)×(N×S)代表衔接矩阵H规模大小，Hij，pq代表神经元(i，j)与(p，q)之间连接权重。假设信元ij与信元pq有一样的目的地址，则Hij，pq=1，否则Hij，pq=0。在每一个时间隙中，该矩阵由每个序列的第一个信元的目的地址所组成。如果选择的信元没有拥堵时，该项目最小。第二项则代表优先级，如果选择的高优先级的信元最多，该项也是最小。该函数依据序列长度决定优先级，而在比较长序列里信元富有极高优先级

(12)

第三项使得神经元结束得出收敛数为1或者0。第四项代表尽可能降低同一输入线路的信元多余1个事情发生。当中T=1/5×it2，it代表第it次检测。增加这一项是为了验证前几次检测结果，尽可能调整同一输入线路的信元，降低在该符合条件时多级交换结构将一条输入线路输送若干个信元情况。随着检测次数越多，此项结果越接近0。

能量函数的最后三项能够有效提升中间级缓存设备的使用价值、减少信元时延、降低信元缺失、提升吞吐量、提高HNN收敛。

根据式(8)到式(12)可以知道HNN的被动公式为

(13)

其中Uij代表神经元的输入，Vij代表神经元输出，A，B，C，g均为正整数。因此HNN经常可以收敛到E的最小点，该神经元能够直接表示一个时间隙内输送的最优无拥堵信元集合。

综上所述，完成了高性能网络多级交换结构实时调度方法。

3 仿真结果与分析

为了验证高性能网络多级交换结构实时调度方法的有效性，进行了一次仿真。

从某企业的网络结构数据库中随机抽取2000个信元，以多级交换结构的扩展比S为指标，采用文献[2]方法和文献[3]方法做本文方法的对比方法，进行对比实验验证，得到多级交换结构的扩展比S的测试结果如表1所示。

表1 三种不同方法的扩展比对比结果

分析表1结果得出，文献[2]方法所设计的多级交换结构，其平均扩展比为1，文献[3]方法所设计的多级交换结构，其平均扩展比为1，本文方法设计的多级交换结构，其平均扩展比为4。根据方法步骤可知，扩展比S值越大，结构越稳定，因此对比实验结果得出，本文方法的扩展比最大，说明本文方法构建的多级交换结构最稳定。

吞吐量是判定实时调度效果的最直观指标，因此分别采用文献[2]方法、文献[3]方法和本文方法进行多级交换结构的实时调度。得到对比结果如图2所示：

图2 三种不同方法吞吐量对比结果

分析图2可知，采用文献[2]方法进行多级交换结构的实时调度，其吞吐量曲线随着信元数量的增加呈下降趋势，平均吞吐量约为55%；采用文献[3]方法进行多级交换结构的实时调度，其吞吐量曲线随着信元数量的增加呈上升趋势，平均吞吐量约为60%；采用本文方法进行多级交换结构的实时调度，其吞吐量曲线随着信元数量的增加先呈上升趋势，在信元数量达到600个时，保持稳定，平均吞吐量约为70%，稳定在80%。对比三种方法的实验结果得出，本文方法的吞吐量远高于两种传统方法的吞吐量，因此说明本文方法的实时调度效果最好。

负载均衡效果是评判实时调度效果是否理想的另一重要指标，分别测试文献[2]方法、文献[3]方法和本文方法三种方法的负载频率幅值对比结果如图3所示。

图3 三种不同方法的负载频率幅值对比结果

根据图3的实验结果可以知道，文献[2]方法的负载频率幅值波动较大，但幅值变化较为规律，文献[3]方法的负载频率幅值不仅波动较大，且幅值变化也不规律，本文方法的负载频率幅值波动较小，且幅值变化规律稳定。充分说明，本文方法的负载均衡性较好，实时调度效果最为理想。

4 结论

多级交换结构是实现网络路由交换器的关键部分，为此本文提出一种高性能网络多级交换结构实时调度方法。

1)首先构建网络多级交换系统，然后分析该系统结构功能，最后得到其具有较高稳定性与较高吞吐量。

2)实验结果表明，该方法简单操作，保证信元不被丢失，吞吐量接近100%，平均扩展比为4，负载均衡效果较高，为此该方法是解决网络实时调度的极佳方法。

3)本文所提方法可以为下一步网络数据安全的研究提供参考意见，为计算机项目的开发奠定了实用性的基础。