论文部分内容阅读
摘要：现代包交换机需要具有为不同的数据流提供不同的服务质量（QOS）的能力，同时随着网络规模和业务的增长，交换机的线卡数目会大量增加，线卡和交换矩阵需要分布在多个线柜中，它们之间的距离可能达到数十米，因此在设计交换机时不能忽视交换机内部的往返时延（RTT）。该文从这两个方面来讨论支持大RTT的组合输入和交叉点缓存排队（CICQ）交换结构实现服务质量保证问题，提出了基于扩展交叉点缓存的支持大RTT并提供基于流的性能保证的CICQ（CICQ-ECBs）交换结构，给出解除扩展交叉点缓存（ECB）阻塞机制，并用Counting方法证明了2倍加速的CICQ-ECBs交换结构能够实现PIFO-OQ仿效。
关键词：往返时间（RTT）;CICQ交换结构;输出排队交换仿效;推入先出（PIFO）;counting方法
中图分类号：TN915 文献标识码：A
文章编号：1009-3044（2020）10-0022-05
1概述
随着近几年宽带网络的发展，各种基于多媒体应用的网络服务，如远程会议、远程教育、视频点播等相继出现，这些网络业务通常有不同的QoS需求。交换机和路由器控制不同数据流的包的离开顺序，因此设计现代包交换机和路由器必须要考虑QoS的支持能力。另一方面，为适应网络业务的增长，交换机需要有大量的线卡支持大的端口数目，这种趋势导致物理空间和功耗的增加，迫使交换机变成分布式的结构，线卡和交换矩阵分布在多个线柜中，线卡和交换矩阵之间的连线达到数十米，因此交换机内部的往返时延（RTT）不能忽视。
随着现代VLSI技术的发展，已有可能在crossbar的交叉点上集成少量的存储器，构成组合的输入一交叉点排队（CombinedInput-Crosspoint Queued，CICQ）的交换机。由于在每个交叉点放置了少量缓存，CICQ交换去除了输入排队交换中输入输出端口必须同步的问题，使输入端口的调度和各个输出端口对交叉点的调度可独立、并行地进行，因此极大地简化了调度算法。对于一个采用基于信用（credit-based）流控的CICQ交换机而言，RTT为一个信用流控信息从crossbar内离开到达输入端口及一个信元从输入端口进入交叉点缓存的时间，如果以传输一个信元所需的时间（通常称为一个时隙）为单位表示RTT，则在最坏情况下每个交叉点需要RTT个信元的缓存空间，才能使交换机处于工作持续（Work-Conserving）状态，整个crossbar内的缓存容量就达到了RTTxN2。如果考虑基于流的服务质量问题，每个交叉点还需要更多的缓存，这在大型交换机中是很难实现的。
文献[6][11]提出在交叉矩阵的边缘或内部为每个输入端口放置一个容量为RTT个信元的存储模块，在其中设置Ⅳ个虚拟交叉点队列（VCQ），让N个交叉点共享的这RTT个信元的缓存空间，从而使整个crossbar内的缓存空间从RTTxN2变成N2 RTTxN。
交换机若要提供基于流的性能保证，就要按流来分配资源，每个流都可以获得它保证的带宽、时延或抖动性能。在0Q交换中，所有到达的信元都直接在输出端排队，按流组织队列，每个队列有一个相应的权值（给每个流分配的带宽），当一个信元到达时，输出调度器根据调度算法和队列权值来计算这个信元的离开时间[8-9]，并将信元插入到按离开时间排序的一个优先列表中，调度器按这个优先列表的顺序调度信元离开交换机，从而保证每个流的性能，这样的0Q交换机被称为PIFO（Push-In-Fist-Out）OQ交换机。
在CICQ中实现基于流的调度时，有可能出现这样的情况，交叉点中已有一个信元，一个新到达的信元有比交叉点信元有更早的离开时间，因为新信元赶不上交叉点中的信元，导致了“交叉点”阻塞问题。很多文献提出了去除交叉点阻塞的方法，文献[10]提出在输入端暂存已经传输到交叉点的信元的副本，当一个新到达信元的离开时间早于交叉点信元时，直接将信元传送到它的交叉点中，而将原交叉点信元的副本重新插入到队列中，由此解决交叉点阻塞问题，并证明了2倍加速、交叉点只有一个信元缓存的CICQ交换，使用这种解除阻塞机制，可以仿效PIFO-OQ交换。本文将这种解除阻塞机制扩展到支持大RTT的分布式CICQ交换中，并证明了我们提出的结构也可以仿效PIFO-OQ交换的性能。
本文首先提出一种能够提供基于流的性能保证、支持大RTT的CICQ交换结构，称之为扩展交叉点缓存的CICQ（cICQ-ECBs）交换结构;之后将文献中常用于OQ仿效证明的Counting方法擴展到CICQ-ECBs交换结构中，针对CICQ-ECBs交换结构提出了Counting方法的相关定义和OQ仿效的充分条件，最后给出CICQ-ECBs交换结构为满足OQ仿效所采用的调度算法和解除阻塞机制，证明了2倍加速的CICQ-ECBs交换机可以仿效一个PIFO-OQ交换的性能。
本文其余部分组织如下，第2节给出CICQ-ECBs交换结构，第3用Counting方法证明所提出的交换结构和调度策略能够提供0Q性能仿效。第4节为结束语。
2支持大RTT的CICQ-ECBs交换结构
为了使具有较大RTF的CICQ交换机能够提供基于流的性能保证，使用扩展交叉点缓存支持大RTT的CICQ交换结构The CICQ Switch with Extended CrosspointBuffers for Large RTF-CICQ-ECBs），如图1所示。
在一个NxN的CICQ-ECBs交换中，输人端对到达的信元按流组织虚拟队列，以避免队头阻塞，每个队列按预订的速率被分配一个权值。
为了达到OQ交换的性能，交换矩阵需要以2倍于端口的速率运行，因此在输出端也设置缓存，在输出缓存中信元也按流排队，以便提供基于流的性能保证。 带缓存crossbar的每个交叉点只有一个信元的缓存空间。在crossbar的边缘或内部为每个输入端口放置一个扩展交叉点缓存模块（ECB），在ECB中也按流组织虚拟队列。在本文中，将一个信元从输入端口i传输到EcB。和相应的流控信息从ECB;返回到输入端i所经历的时间用RTT个信元时隙表示。在2倍内部加速的情况下（输人端口到它的ECB之间以端口速率通信，不加速），为使交换机处于工作保持（Work-Conserving）状态，并且能够区分不同的数据流，每个输入-输出对（相应于每个交叉点）最坏情况下需要至少2xRTT个信元的缓存空间，按流组织虚拟队列，这样在每个ECB上需要2xRTTxN个信元的缓存空间，不依赖于流的数目。
带缓存的crossbar与每个ECB之间使用基于信用（Credit-based）的流控机制，当一个交叉点CP（i，j）有信元占用时，向相应的ECBi发送可用信用CPC（i，j）=0，当交叉点信元被传送到输出端后，可用信用变为CPC（i，j）=1。每个ECBi和它的输入端口之间也采用基于信用的流控，对每个交叉点提供2xRTT个信用，由去往这个交叉点的多个数据流共享，如果在ECBi中已有2xRTT个去往输出j的信元，则向输人端口i发送信用ECBC（i，j）=O，每当有一个信元被传输到交叉点后，向输入端口i发送可用的信用數目ECBC（i，j）。
分别在输入端和ECB上保存已发送到扩展交叉点缓存和交叉点上的信元的副本，用于解除ECB阻塞和交叉点阻塞。
采用“按虚拟流队列分组（Group-By-Virtual-Flow-Queue，简称GBVFQ）”插入策略，分别在输入端维持一个输入优先列表（Input Priority List，简称IPL）、在ECB上维持一个扩展交叉点优先级列表（ECB Priority List）列表，其中优先列表中的信元按流分组。
GBVFQ算法为：在输人端到达的信元按流排队，当一个信元到达一个非空的流队列时，信元被插入到输入优先列表中属于同一个流的上一个信元之后，这确保同一数据流的信元是按离开顺序排序的;当一个信元到达一个空的流队列时，信元被插入到输入优先列表IPL的头部。
在ECB中，从输入端到达的信元也按流排队，同样使用GBVFQ算法将到达的信元插入到EPL中。
3CICQ-ECBs交换以2倍加速实现PIFO-OQ仿效
文献[1]使用counting方法证明一个加速2倍的无缓存crossbar的CIOQ交换可以仿效一个OQ交换。为达到仿效OQ的目的，在CIOQ中的每个信元必须在要仿效的OQ（称为投影0Q）交换中对应的信元离开OQ之前的时间被传送到CIOQ的输出端。我们将这种Counting方法用于CICQ交换的OQ仿效的证明。
3.1Counting方法的相关定义
首先，根据CICQ-ECBs交换结构的特点给出Counting方法的相关定义。
投影OQ交换机：要仿效的OQ交换机，它确定了CICQ-ECBs交换机中每个信元的离开时隙，与CICQ-ECBs交换有相同的到达。
离开时间（Time-to-Leave，TTL）：TTL（c）等于信元c的离开时隙，由投影OQ指定。在CICQ-ECBs交换机中，因为采用分布式调度，信元只有在到达交叉点缓存后才能计算它的TTL，不会有去往同一输出端的两个信元有相同的TTL。
输出优先列表（Output Priority List，简称OPL）：每个输出端基于信元的TTL顺序对在输出端和它的交叉点中排队的信元建立输出优先列表，有最小TTL值的信元最先离开。
输入优先列表（IPL）：每个输入端对所有在此排队的信元维持一个有序列表。在信元到达输入端口时，因为没有这个信元要去往的输出端口的所有流的信息，所以在输入端还不能计算出它的TTL值，使用GBVFQ插入策略来维持输入优先列表中信元的顺序。在同一输入端口中的两个信元，如果都有ECB信用可用，则有较高的输人优先权的信元先被发送到ECB。
ECB优先列表（EPL）：信元从输入端口到达ECB后按流排队，每个ECB上有一个ECB调度器，负责将在此排队的信元传输到相应的交叉点缓存中，因此也需要维护一个优先列表。仍然采用GBVFQ插入策略来维持ECB优先列表中的信元顺序，在同一ECB上的两个信元，如果它们的交叉点都为空，则有较高ECB优先权的信元被传送到交叉点。
输出缓冲（Output Cushioll）：一个信元c的输出缓冲OC（c）为在c的输出优先列表中TTL值小于c的信元数目。
输入排头（Input Thread）：一个信元c的输入排头IT（c）为在c的输入缓存中有比c更高的输入优先权的信元数目。正处于从输入端到ECB传输途中的信元、ECB中的信元和交叉点中的信元，它们的IT为O。
ECB排头（ECB Thread）：一个信元c的ECB排头ET（c）为在c的扩展交叉点缓存中比c有更高的ECB优先权的信元数目。在交叉点中排队的信元的ET为O。
松弛度（Slackness）：在CICQ-ECBs交换机中，定义信元c的松弛度，L（c）为它的输出缓冲减去它的输入排头与ECB排头的和，即
L（c）=OC（c）-IT（c）-ET（c）
对于一个已在ECB中或在交叉点中等待的信元c，因为它的IT（c）=O，因此它的Uc）等价于
L（c）=OC（c）-ET（c）
3.2CICQ-ECBs实现oQ仿效的充分条件
在图l所示的CICQ-ECBs交换机中，一个信元时隙内最多有一个信元到达一个输入端口，最多有一个信元离开一个输出端口。带缓存的crossbar有2倍加速，因此在一个外部信元时隙内可能有两个信元从一个ECB离开进入相应的交叉点，以及可能有两个信元离开交叉点到输出队列。为便于分析，将每个外部时隙分为六个阶段： 到达阶段：一个新信元到达输入端口，被放置到它的虚拟流队列中，并将它的存储指针按GBVFQ规则插入到输人优先列表IPL中。
輸入调度阶段：输入调度器按照输入优先列表的顺序，从各个流队列中选择ECB上有空闲空间（ECBC（i，j）
关键词：往返时间（RTT）;CICQ交换结构;输出排队交换仿效;推入先出（PIFO）;counting方法
中图分类号：TN915 文献标识码：A
文章编号：1009-3044（2020）10-0022-05
1概述
随着近几年宽带网络的发展，各种基于多媒体应用的网络服务，如远程会议、远程教育、视频点播等相继出现，这些网络业务通常有不同的QoS需求。交换机和路由器控制不同数据流的包的离开顺序，因此设计现代包交换机和路由器必须要考虑QoS的支持能力。另一方面，为适应网络业务的增长，交换机需要有大量的线卡支持大的端口数目，这种趋势导致物理空间和功耗的增加，迫使交换机变成分布式的结构，线卡和交换矩阵分布在多个线柜中，线卡和交换矩阵之间的连线达到数十米，因此交换机内部的往返时延（RTT）不能忽视。
随着现代VLSI技术的发展，已有可能在crossbar的交叉点上集成少量的存储器，构成组合的输入一交叉点排队（CombinedInput-Crosspoint Queued，CICQ）的交换机。由于在每个交叉点放置了少量缓存，CICQ交换去除了输入排队交换中输入输出端口必须同步的问题，使输入端口的调度和各个输出端口对交叉点的调度可独立、并行地进行，因此极大地简化了调度算法。对于一个采用基于信用（credit-based）流控的CICQ交换机而言，RTT为一个信用流控信息从crossbar内离开到达输入端口及一个信元从输入端口进入交叉点缓存的时间，如果以传输一个信元所需的时间（通常称为一个时隙）为单位表示RTT，则在最坏情况下每个交叉点需要RTT个信元的缓存空间，才能使交换机处于工作持续（Work-Conserving）状态，整个crossbar内的缓存容量就达到了RTTxN2。如果考虑基于流的服务质量问题，每个交叉点还需要更多的缓存，这在大型交换机中是很难实现的。
文献[6][11]提出在交叉矩阵的边缘或内部为每个输入端口放置一个容量为RTT个信元的存储模块，在其中设置Ⅳ个虚拟交叉点队列（VCQ），让N个交叉点共享的这RTT个信元的缓存空间，从而使整个crossbar内的缓存空间从RTTxN2变成N2 RTTxN。
交换机若要提供基于流的性能保证，就要按流来分配资源，每个流都可以获得它保证的带宽、时延或抖动性能。在0Q交换中，所有到达的信元都直接在输出端排队，按流组织队列，每个队列有一个相应的权值（给每个流分配的带宽），当一个信元到达时，输出调度器根据调度算法和队列权值来计算这个信元的离开时间[8-9]，并将信元插入到按离开时间排序的一个优先列表中，调度器按这个优先列表的顺序调度信元离开交换机，从而保证每个流的性能，这样的0Q交换机被称为PIFO（Push-In-Fist-Out）OQ交换机。
在CICQ中实现基于流的调度时，有可能出现这样的情况，交叉点中已有一个信元，一个新到达的信元有比交叉点信元有更早的离开时间，因为新信元赶不上交叉点中的信元，导致了“交叉点”阻塞问题。很多文献提出了去除交叉点阻塞的方法，文献[10]提出在输入端暂存已经传输到交叉点的信元的副本，当一个新到达信元的离开时间早于交叉点信元时，直接将信元传送到它的交叉点中，而将原交叉点信元的副本重新插入到队列中，由此解决交叉点阻塞问题，并证明了2倍加速、交叉点只有一个信元缓存的CICQ交换，使用这种解除阻塞机制，可以仿效PIFO-OQ交换。本文将这种解除阻塞机制扩展到支持大RTT的分布式CICQ交换中，并证明了我们提出的结构也可以仿效PIFO-OQ交换的性能。
本文首先提出一种能够提供基于流的性能保证、支持大RTT的CICQ交换结构，称之为扩展交叉点缓存的CICQ（cICQ-ECBs）交换结构;之后将文献中常用于OQ仿效证明的Counting方法擴展到CICQ-ECBs交换结构中，针对CICQ-ECBs交换结构提出了Counting方法的相关定义和OQ仿效的充分条件，最后给出CICQ-ECBs交换结构为满足OQ仿效所采用的调度算法和解除阻塞机制，证明了2倍加速的CICQ-ECBs交换机可以仿效一个PIFO-OQ交换的性能。
本文其余部分组织如下，第2节给出CICQ-ECBs交换结构，第3用Counting方法证明所提出的交换结构和调度策略能够提供0Q性能仿效。第4节为结束语。
2支持大RTT的CICQ-ECBs交换结构
为了使具有较大RTF的CICQ交换机能够提供基于流的性能保证，使用扩展交叉点缓存支持大RTT的CICQ交换结构The CICQ Switch with Extended CrosspointBuffers for Large RTF-CICQ-ECBs），如图1所示。
在一个NxN的CICQ-ECBs交换中，输人端对到达的信元按流组织虚拟队列，以避免队头阻塞，每个队列按预订的速率被分配一个权值。
为了达到OQ交换的性能，交换矩阵需要以2倍于端口的速率运行，因此在输出端也设置缓存，在输出缓存中信元也按流排队，以便提供基于流的性能保证。 带缓存crossbar的每个交叉点只有一个信元的缓存空间。在crossbar的边缘或内部为每个输入端口放置一个扩展交叉点缓存模块（ECB），在ECB中也按流组织虚拟队列。在本文中，将一个信元从输入端口i传输到EcB。和相应的流控信息从ECB;返回到输入端i所经历的时间用RTT个信元时隙表示。在2倍内部加速的情况下（输人端口到它的ECB之间以端口速率通信，不加速），为使交换机处于工作保持（Work-Conserving）状态，并且能够区分不同的数据流，每个输入-输出对（相应于每个交叉点）最坏情况下需要至少2xRTT个信元的缓存空间，按流组织虚拟队列，这样在每个ECB上需要2xRTTxN个信元的缓存空间，不依赖于流的数目。
带缓存的crossbar与每个ECB之间使用基于信用（Credit-based）的流控机制，当一个交叉点CP（i，j）有信元占用时，向相应的ECBi发送可用信用CPC（i，j）=0，当交叉点信元被传送到输出端后，可用信用变为CPC（i，j）=1。每个ECBi和它的输入端口之间也采用基于信用的流控，对每个交叉点提供2xRTT个信用，由去往这个交叉点的多个数据流共享，如果在ECBi中已有2xRTT个去往输出j的信元，则向输人端口i发送信用ECBC（i，j）=O，每当有一个信元被传输到交叉点后，向输入端口i发送可用的信用數目ECBC（i，j）。
分别在输入端和ECB上保存已发送到扩展交叉点缓存和交叉点上的信元的副本，用于解除ECB阻塞和交叉点阻塞。
采用“按虚拟流队列分组（Group-By-Virtual-Flow-Queue，简称GBVFQ）”插入策略，分别在输入端维持一个输入优先列表（Input Priority List，简称IPL）、在ECB上维持一个扩展交叉点优先级列表（ECB Priority List）列表，其中优先列表中的信元按流分组。
GBVFQ算法为：在输人端到达的信元按流排队，当一个信元到达一个非空的流队列时，信元被插入到输入优先列表中属于同一个流的上一个信元之后，这确保同一数据流的信元是按离开顺序排序的;当一个信元到达一个空的流队列时，信元被插入到输入优先列表IPL的头部。
在ECB中，从输入端到达的信元也按流排队，同样使用GBVFQ算法将到达的信元插入到EPL中。
3CICQ-ECBs交换以2倍加速实现PIFO-OQ仿效
文献[1]使用counting方法证明一个加速2倍的无缓存crossbar的CIOQ交换可以仿效一个OQ交换。为达到仿效OQ的目的，在CIOQ中的每个信元必须在要仿效的OQ（称为投影0Q）交换中对应的信元离开OQ之前的时间被传送到CIOQ的输出端。我们将这种Counting方法用于CICQ交换的OQ仿效的证明。
3.1Counting方法的相关定义
首先，根据CICQ-ECBs交换结构的特点给出Counting方法的相关定义。
投影OQ交换机：要仿效的OQ交换机，它确定了CICQ-ECBs交换机中每个信元的离开时隙，与CICQ-ECBs交换有相同的到达。
离开时间（Time-to-Leave，TTL）：TTL（c）等于信元c的离开时隙，由投影OQ指定。在CICQ-ECBs交换机中，因为采用分布式调度，信元只有在到达交叉点缓存后才能计算它的TTL，不会有去往同一输出端的两个信元有相同的TTL。
输出优先列表（Output Priority List，简称OPL）：每个输出端基于信元的TTL顺序对在输出端和它的交叉点中排队的信元建立输出优先列表，有最小TTL值的信元最先离开。
输入优先列表（IPL）：每个输入端对所有在此排队的信元维持一个有序列表。在信元到达输入端口时，因为没有这个信元要去往的输出端口的所有流的信息，所以在输入端还不能计算出它的TTL值，使用GBVFQ插入策略来维持输入优先列表中信元的顺序。在同一输入端口中的两个信元，如果都有ECB信用可用，则有较高的输人优先权的信元先被发送到ECB。
ECB优先列表（EPL）：信元从输入端口到达ECB后按流排队，每个ECB上有一个ECB调度器，负责将在此排队的信元传输到相应的交叉点缓存中，因此也需要维护一个优先列表。仍然采用GBVFQ插入策略来维持ECB优先列表中的信元顺序，在同一ECB上的两个信元，如果它们的交叉点都为空，则有较高ECB优先权的信元被传送到交叉点。
输出缓冲（Output Cushioll）：一个信元c的输出缓冲OC（c）为在c的输出优先列表中TTL值小于c的信元数目。
输入排头（Input Thread）：一个信元c的输入排头IT（c）为在c的输入缓存中有比c更高的输入优先权的信元数目。正处于从输入端到ECB传输途中的信元、ECB中的信元和交叉点中的信元，它们的IT为O。
ECB排头（ECB Thread）：一个信元c的ECB排头ET（c）为在c的扩展交叉点缓存中比c有更高的ECB优先权的信元数目。在交叉点中排队的信元的ET为O。
松弛度（Slackness）：在CICQ-ECBs交换机中，定义信元c的松弛度，L（c）为它的输出缓冲减去它的输入排头与ECB排头的和，即
L（c）=OC（c）-IT（c）-ET（c）
对于一个已在ECB中或在交叉点中等待的信元c，因为它的IT（c）=O，因此它的Uc）等价于
L（c）=OC（c）-ET（c）
3.2CICQ-ECBs实现oQ仿效的充分条件
在图l所示的CICQ-ECBs交换机中，一个信元时隙内最多有一个信元到达一个输入端口，最多有一个信元离开一个输出端口。带缓存的crossbar有2倍加速，因此在一个外部信元时隙内可能有两个信元从一个ECB离开进入相应的交叉点，以及可能有两个信元离开交叉点到输出队列。为便于分析，将每个外部时隙分为六个阶段： 到达阶段：一个新信元到达输入端口，被放置到它的虚拟流队列中，并将它的存储指针按GBVFQ规则插入到输人优先列表IPL中。
輸入调度阶段：输入调度器按照输入优先列表的顺序，从各个流队列中选择ECB上有空闲空间（ECBC（i，j）