现有网络需要同时支持电路和分组业务，使用1个交换平面同时转发2种业务有利于设备的共享和网络的融合.针对该需求，在Clos交换网络的基础上提出了电路与分组的混合交换网络及调度机制.在混合交换网络中，调度机制为电路业务分配专用通路，同时利用剩余带宽为分组业务提供尽力而为的转发服务.仿真结果表明，混合交换可以满足电路业务对服务质量的要求，并可以为分组业务提供较高的吞吐率.
Both circuit and packet traffics are supported in present communication networks. Forwarding those two traffics over the same switching fabric favors the sharing of network devices and the integration of networks. A combined circuit/packet switching fabric and dispatching scheme was proposed based on Clos-network switches. Dedicated paths were reserved for circuit traffic by dispatching scheme in the switching fabric. Meanwhile the remaining bandwidth is used to provide packet traffic with best-effort forwarding. Simulation shows that quality of service requirement of circuit traffic is satisfied, and a high throughput is achieved for packet traffic.
现有网络需要同时支持电路和分组业务.电路业务主要承载电信网中的实时话音，而分组业务主要承载Internet中的数据.为支持2种业务的转发，交换网络也相应地分为电路交换和分组交换2类.其中电路交换以同步时分复用为基础，能提供恒定的带宽和时延.但是由于数据通道是专用的，因此信道利用率比较低.而分组交换以异步时分复用为基础，发送速率灵活可变，信道利用率较高，但是传输过程中的时延和时延抖动无法保证.
现有的网络设备中，2种业务分别通过不同的交换平面转发[1]，这不利于设备资源的共享及电信网络和Internet的融合.混合交换是指在同一交换平面中同时完成电路和分组业务的转发，并能为电路业务提供严格的带宽、时延及时延抖动的保证，同时尽力满足分组业务转发的需要.此外，多媒体业务虽然用IP分组承载，但具有电路业务的特征[2]，采用混合交换可以为其提供所需的转发服务.混合交换技术还可以用在支持差异化服务Differentiated Services的网络[3]中，为指定业务提供具有带宽和时延保证的逐跳服务(per-hop behavior).
1 Clos交换网络结构及调度机制介绍Clos交换网络是一种由小规模交换单元构成的多级交换网络，最早用于解决单级Crossbar交换网络中交叉点数目过多的问题[4]. Clos交换网络凭借模块化、无内部阻塞等优点，在分组交换中获得了广泛的应用.它具有以下特征.
1) 交换单元被排列为3级：输入级、中间级和输出级，相应的交换单元分别称为输入级模块(IM，input module)、中间级模块(CM，central module)和输出级模块(OM，output module)；
2) 每个交换单元与相邻级的一个交换单元通过唯一的链路相连接；
3) 每个交换单元都是无内部阻塞的.
Clos交换网络的结构如图 1所示，其中输入级有k个n×m的IM，中间级有m个k×k的CM，输出级有k个m×n的OM，Clos交换网络的输入(输出)端口数N=n×k.
|
图 1 Clos交换网络 |
根据缓存位置的不同，Clos交换网络可以分为不同的类型，其中Memory-Space-Memory(MSM，IM和OM内部有信元缓存，可用于缓解输出端口冲突)型Clos交换网络具有调度简单、不存在信元乱序等优点.其调度算法主要用于为信元进行路由分配，并解决IM和CM输出端口的冲突.常见调度算法是CRRD (concurrent round-robin dispatching)类算法[5]，它通过请求—应答—接受模式解决端口冲突.基于优先级调度的CRRD算法中，高优先级业务可以在端口竞争中获得优先应答，从而增加所占带宽，减少平均时延.但是该方法不能保证高优先级业务的时延抖动，因此无法用于为电路业务提供严格的服务质量(QoS, quality of service)保证.另一方面，低优先级业务只有在高优先级业务发送结束后才会获得转发的机会，会导致其吞吐率下降.
2 混合交换网络混合交换网络内部采用定长信元承载电路和分组业务，而在输入端口处区分业务类型，将变长分组封装为定长信元，并在头部进行标记，以区分信元类型.笔者在MSM型Clos交换网络的基础上提出混合交换网络.它首先在IM(i)-OM(j)间建立具有一定带宽的虚拟通道(VP, virtual path)[6]，记为VP(i, j)，作为IM(i)和OM(j)间电路业务转发的通路；然后将VP(i, j)映射为CM内部周期性重复的连接状态，并同时为分组业务分配路由.混合交换网络中将CM内部的链路分为以下2类.
1) 准静态链路：周期性重复连接的链路.相应的端口在指定的时隙建立连接并转发相应的信元，无需再进行匹配.准静态链路构成了IM-OM间的VP，为电路业务提供具有QoS保证的服务.
2) 动态链路：除准静态链路外的其他链路，用于为分组业务提供尽力而为的服务.
假定准静态链路重复的周期为F个时隙，并将这F个时隙称为1帧.在1帧内，每个CM输出(输入)端口可以只有部分时隙被配置为准静态链路，而其余部分作为动态链路. 图 2所示为CM某输出端口的链路配置.标记为阴影的时隙表示端口在该时隙会被配置为准静态链路，并与指定输入端口建立连接.不同的阴影表示不同的VP.标记为白色的时隙表示端口被配置为动态链路，可根据调度算法的匹配结果与任意输入端口建立连接.由于1帧包含F个时隙，因此每个端口最多可以建立F条准静态链路.混合交换采用时分复用的方式在1条级间链路上建立多条准静态链路.这是因为一方面，交换模块间的连线往往采用高速串行链路，无法使用空分复用[1]；另一方面，时分复用可以不受物理连线数目的限制，可以建立更多的准静态链路.因此与文献[1]中所采用的复用方式相比，时分复用的方式更适合于本文的需求.
|
图 2 CM输出端口的链路配置 |
假定混合交换网络内部的级间链路速率为L，则每条准静态链路所提供的带宽为Δ=L/F(Δ也是电路业务的最小颗粒度).为记录端口的配置信息，CM输出端口处需要维护一个长度为F的队列，称为配置队列，用于记录1帧内各时隙的状态以及对应端口.配置队列一方面可用于指导信元的发送，另一方面用于在调度算法进行匹配时避免冲突.混合交换网络中，IM内按VOMQ(virtual OM queue)排队，IM(i)内存储发送往OM(j)信元的队列，记为VOMQ(i, j).每个VOMQ内部，信元再按照电路和分组业务分别排队，以防止电路业务被阻塞.在OM输出端口处，同样按照业务类型分别排队.由于在混合交换网络内部，同一IM-OM间的电路业务可以使用相同的路由进行转发，因此可共享对应VP所提供的带宽.只要VP的带宽不小于电路业务所需的带宽，就可以保证对应信元在1帧内到达相应的OM.因此准静态链路的建立不需要针对特定的外部业务流，这一方面使得内部时隙和帧的划分(包括F的取值)与外部电路业务无关，简化了交换网络的硬件设计；另一方面不需要为每个业务单独建立队列，简化了IM内部的队列管理.
3 混合调度机制混合调度机制需要一方面解决IM和CM输出端口的冲突，为信元完成路由分配；另一方面还需要实时调整为电路业务分配的带宽.每个VOMQ需要记录对应电路业务所需的带宽(记为BN)以及已分配的带宽(记为BA).当有新电路业务需要建立时，交换网络从信令中获取该业务所需带宽，BN增加相应带宽；而当有电路业务结束时，BN则减少相应带宽.根据BN与BA的关系，可以确定是否需要为该电路业务建立或释放准静态链路.每时隙，混合调度机制需要依次执行以下操作.
1) 当BN≤BA－Δ时，释放相应的准静态链路；
2) 当BN>BA时，建立新的准静态链路；
3) 为未发送的分组业务建立动态链路.
由于根据配置队列可以获取当前时隙的链路配置，所以当需要释放准静态链路时，VOMQ只需要根据配置队列的信息，直接向相应的IM和CM输出端口发送释放请求，当收到请求后，输出端口从配置队列中清除相应的信息.每释放1条准静态链路后，将BA更新为BA－Δ.
当IM-OM间的电路业务带宽不是Δ的整数倍时，准静态链路中会有一些空闲时隙，混合交换网络需要有一定的链路扩展或加速，以使得IM和CM之间的链路带宽大于外部链路和空闲时隙所占带宽的容量之和，从而避免吞吐率下降.由调度机制的操作步骤1) 可知，当BA－BN < Δ时，相应的准静态链路会被释放，BA会减小至BA－BN < Δ，因此每个VP的空闲带宽至多为Δ.而由于VP是针对每个IM-OM对建立的，因此每个IM最多有k条空闲的准静态链路.当只采用链路扩展时，需满足mkL≥nkL+k2Δ，因此m≥⌈(nkL+k2Δ)/kL⌉=⌈n+k/F⌉(⌈x⌉表示大于等于x的最小整数).当仅采用链路加速时，假定外部链路速率为L，而内部链路速率为SL，S为加速比，需满足nkSL≥nkL+k2Δ(Δ=SL/F)，因此S≥nkL/(nkL－k2L/F)=n/(n－k/F).当F增加时，所需链路数和加速比都会减少，但是增加F会造成配置队列长度的增加，使用的缓存也会随之增加，因此需要根据实际情况选择合适的F.
准静态链路和动态链路对路由分配的要求是一样的，因此可以采用同一调度算法.其区别主要在于准静态链路在对应VP的带宽减少时才能释放，而动态链路则只需要保持一个时隙.使用分治调度算法进行路由分配，每个时隙内，该算法需要分为max (k, m)(max (k, m)表示取k和m中较大的值)个子时隙，每个子时隙分为请求—应答2个过程.
1) 请求：VOMQ按DSRR(desynchronized static round-robin)方式[7]通过IM输出端口向CM转发请求.由于所有IM中的配置是一致的，因此每个子时隙内CM收到的请求去往同一OM.
2) 应答：CM从接收到请求中选择一个，向对应VOMQ返回应答，并在IM和CM输出端口的配置队列中记录相应的信息.
分治调度算法采用了串行匹配的思想，因此相对于CRRD类算法来说，一次匹配需要有较多的子时隙完成.但是分治调度算法在IM和CM间传递的信息较少，每个子时隙内执行的操作也比较简单，因此并不会造成匹配时间过长.混合交换进行路由分配时，需要在1个时隙内执行2次分治调度算法，因此每个时隙要分为2max (k, m)个子时隙，前max (k, m)个子时隙用于建立准静态链路，而后max (k, m)个子时隙用于建立动态链路. CM进行仲裁前，需要在配置队列中查找当前时隙是否为准静态链路，只有当不是准静态链路时，才返回相应的应答.当建立1条准静态链路后，除在配置队列中记录相应信息外，还要将BA更新为BA+Δ；而建立1条动态链路后，需要在下一时隙发送分组业务队列中的信元，并清除配置队列中的信息.
4 性能分析混合交换的性能通过仿真进行验证，并与支持优先级的CRRD算法进行对比.仿真环境为m=n=k=8的Clos交换网络，混合交换中取F=16，CRRD算法中电路业务为高优先级，而且在IM内进行8次迭代，以达到最大匹配.仿真中输入端口按照不同负载产生电路与分组业务.仿真开始时随机选择若干输出端口建立电路业务的连接，之后按指定速率产生信元；而分组业务服从Bernoulli到达，输出端口均匀分布.端口的业务负载记为λ(0≤λ≤1)，电路和分组的业务负载分别记为λC和λP(0≤λC，λP≤1，λ=λC+λP).仿真验证以下性能指标.
1) 电路和分组业务的吞吐率
图 3所示为在不同业务负载下，2种调度机制的电路和分组业务吞吐率. 图 3(a)中电路业务负载保持不变(λC=0.5)，而分组业务不断增加(λP=0.0~0.5)；图 3(b)中分组业务负载为0，而电路业务负载不断增加(λC=0.0~1.0).从图 3(a)中可以看出，电路业务的吞吐率一直可以达到100%，说明2种算法在电路业务负载较低(λC≤0.5) 时，都可以保证较高的吞吐率，而且不会受到分组业务的影响.而混合交换中分组业务吞吐率高于CRRD算法，说明混合交换在满足电路业务的同时，可以更好地满足分组业务的需要.从图 3(b)中可以看出，当电路业务负载较高时，混合交换依然保持100%的吞吐率，而CRRD类算法则出现了吞吐率的下降.这是由于电路业务建立时随机选择了输出端口，造成业务分布不均匀，CRRD类算法中指针不能完全去同步化[5]，因此吞吐率下降.而混合交换通过建立VP，保证带宽能满足电路业务的需要，因此吞吐率不会受到影响.
|
图 3 电路与分组业务的吞吐率 |
2) 电路业务的时延
图 4所示为2种机制下，输入、输出端口间的电路业务的时延分布.从图 4中可以看出，CRRD类算法一次仿真中时延的分布较为分散；而混合交换中时延为6保持不变，时延抖动为0.因此，混合交换可以提供比CRRD算法更好的时延抖动保证.由于混合交换采用准静态链路进行信元的转发，信元到达后需要等待所需链路.而CRRD算法在信元到达后直接为其匹配，因此其平均时延比混合交换小，但是无法保证时延抖动.
|
图 4 电路业务的时延分布 |
现有通信网络既要支持分组交换，还要支持电路交换.针对该需求，在MSM型Clos交换网络的基础上，提出了混合交换网络及调度机制，可以在同一交换网络中同时支持电路和分组业务的转发，减少了网络设备的种类，增强了通信的灵活性，有助于电信网络和Internet的融合.除用于同时支持2种业务外，所提出的混合交换网络及调度机制还可用于在Internet为不同的业务提供差别服务，提供相应的QoS.经仿真验证，混合交换能在不同业务模型下为电路业务提供严格的QoS保证，并且为分组业务提供了较高的吞吐率.
| [1] | Lusala A K, Legat J. A hybrid NoC combining SDM-TDM based circuit-switching with packet-switching for real-time applications[C]//2012 IEEE 10th International New Circuits and Systems Conference. Montreal, QC, Canada: IEEE Press, 2012: 17-20. |
| [2] | Chang Linhuang, Lee T H, Chu Hungchi, et al. QoS-aware path switching for VoIP traffic using SCTP[J]. Computer Standards & Interfaces, 2013, 35(1): 158–169. |
| [3] | Blake S, Black D, Carlson M, et al. RFC 2475—1998, an architecture for differentiated services [S]. New York: IETF, 1998: 12-25. |
| [4] | Clos C. A study of nonblocking switching networks[J]. Bell System Technical Journal, 1953, 32(2): 406–424. doi: 10.1002/bltj.1953.32.issue-2 |
| [5] | Eiji O, Jing Zhigang, Roberto R C, et al. Concurrent round-robin-based dispatching schemes for Clos-network switches[J]. IEEE/ACM Transactions on Networking, 2002, 10(6): 830–844. doi: 10.1109/TNET.2002.804823 |
| [6] | Liew S Y, Lee T T. Bandwidth assignment with QoS guarantee in a class of scalable ATM switches[J]. IEEE Transactions on Communications, 2000, 48(3): 377–380. doi: 10.1109/26.837040 |
| [7] | Li Xin, Zhou Zhen, Hamdi M. Space-memory-memory architecture for Clos-network packet switches[C]//2005 International Conference on Communications. Seoul, South Korea: IEEE Press, 2005: 1031-1035. |