输入队列交换机中嵌套周期流优化调度问题的复杂性分析吴俊1李斌1(1扬州大学信息工程学院,江苏扬州225009)摘要许多网络应用需要网络交换节点能保证分组转发的时延，周期流量的调度是提供这一保证的重要手段。在流量负荷过载的情况下，如何进行优化调度是该领域的重要课题。本文首先依据交换机吞吐率和呼损率两个性能指标，分别定义了两种交换机周期流量调度的最优化问题。为了分析这些优化调度问题的复杂性，我们定义了一种受限的Max2Sat问题，并证明该Max2Sat问题是NP完全的。然后，通过将该问题多项式归约到交换机周期流优化调度问题，证明了仅有1和2嵌套周期流的交换机优化调度问题是强NP完全问题。并进一步利用该结果证明了任意嵌套周期的优化调度问题也是NP-hard的。关键词输入队列；交换机；分组调度；周期流；硬实时；NP完全TP18Onthecomplexityofoptimalschedulingmulti-ratenestedperiodictrafficinaninput-queuedswitchWuJun1LiBin1(1SchoolofInformationEngineering,YangzhouUniversity,激angsuYangzhou225009,China)AbstractManyapplicationsneedthattheswitchingnodesinanetworkcanguaranteethepacketdeadlines.Multi-rateperiodictrafficschedulingisanimportantmethodforprovidingsuchguarantee.Underoverloadingtraffics,makinganoptimalschedulingisakeyissue.Inthispaper,twooptimalschedulingproblems,respectivelyintermsofswitchthroughputandcallcongestionration,areproposed.Inordertoanalysisthecomplexity,weintroducearestrictedMax2Satproblem,andshowthattherestrictedMax2SatproblemisNPcomplete.Then,apolynomial-timereductionfromtheMax2SatproblemtotheoptimalschedulingproblemisgivenforprovingthattheoptimalschedulingproblemswithonlyoneandtwoperiodsarestronglyNPC.AndthisresultisgeneralizedtoshowthatanynestedperiodictrafficoptimalschedulingproblemsarealsoNP-hard.KeywordsInput-queued;Switch;PacketScheduling;Periodictraffic;hardreal-time;NPC1引言由于输出队列结构的交换机制存在严重的可扩展性问题，目前大量的高速交换节点采用了输入队列结构[1~5]或Broadcast-and-Select光纤交换机制[6~10]。这类交换节点在分组转发时有着共同的限制：同一时刻任意两个被转发的分组不能涉及同一个输入或输出端口(或收发器)，否则将产生冲突。因此在作分组调度决策时不仅要考虑分组调度的目标还要考虑冲突的解析。另一方面，随着多媒体信息的广泛使用，网络中实时流量所占比重日——————————————本课题得到国家自然科学基金(No.60873219)和(No.60903161)、江苏省自然科学基金(BK2009698)和(BK2007074)的资助.吴俊，男,1970年出生，副教授,主要研究领域为网络算法,协议工程和形式化方法E-mail:wujun@yzu.edu;李斌,男,1965年生，江苏靖江人,教授,主要研究领域为分布式人工智能,服务计算。益增多。这类实时流量一般要求分组在被转发到目的地时满足一定的时限要求。这要求网络的交换节点在作资源分配决策时能够考虑到流量的这种需求，即提供一种QoS保证的转发服务。支持QoS的交换机调度问题与网络的性能及服务能力密切相关，一直受到了广泛而深入地研究。解决这一问题的思路大致可以分为三种，区分服务方式、软实时调度和硬实时调度。区分服务方式只能提供统计意义上的质量保证，一般不能提供刚性的时延保证。[3]提出了一种基于博弈的帧调度算法，该算法在输入流量不过载的情况下可以达到100%的吞吐率且能够对不同的流提供不同带宽的服务。[8]中给出WDM光纤网络的一种自适应调度算法MLF-TTS，该算法兼顾了对实时流量的响应和非实时流量的性能。但由于这类算法难以提供刚性的服务质量保证，不能满足对时延、带宽等有着严格要求的应用。软实时调度算法一般通过对服务带宽的确保来提供时延的保证。这种带宽的保证可以通过将PGPS(Packet-by-PacketGeneralizedProcessorSharing)方法引入到交换机调度中加以解决。[2]将PGPS与稳定婚姻匹配算法相结合，为每条虚电路提供了服务带宽的保证。[5]采用Birkhoff-vonNeumann算法将流量矩阵分解...