多路复用器的行为和等待时间分布进行了数值实验

理论计算机科学电子笔记128（2005）25-44www.elsevier.com/locate/entcs一种BMAP/D/1定时器复用器G'abororHorva'th1 Mi kl'osTelek2布达佩斯技术经济大学电信系匈牙利布达佩斯摘要在本文中，我们介绍和分析了一个模型的多路复用队列的批马尔可夫到达过程和一个特殊的，基于定时器的，非工作守恒的服务纪律。本文证明了偏离嵌入过程是一个具有适当状态划分的M/G/1型过程，可以用矩阵几何方法有效地分析。 我们推导了计算等待时间分布的表达式。本文最后的数值实验，并指出了一些有趣的功能的系统。保留字：多路复用器队列，BMAP，矩阵几何法，等待时间分布1介绍在分组交换网络中存在网络协议，其中多路复用器从传入数据单元组成固定大小的分组在这样的多路复用器中，存在传输延迟的附加分量。当没有足够的数据组成一个完整的数据包时，多路复用器等待输入数据来填充数据包。 这种额外的延迟可以通过使用定时器当该定时器到期时，多路复用器发送不完整的分组。在本文中，我们讨论了一个连续时间矩阵几何模型，这种多路复用器的行为的情况下，批马尔可夫到达过程（BMAP）的到来。1电子邮件：ghorvath@hit.bme.hu2电子邮件：telek@hit.bme.hu1571-0661 © 2005 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.01.01126G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25本文的结构如下。第2节给出了所考虑的排队模型的描述，第3节提供了该排队模型的队列大小分析。基于排队长度分析，第4节给出了等待时间分布的计算。第5节对算法进行了总结。第6节给出了数值例子和结果分析。最后，第7节对本文进行了总结。2模型描述BMAP/D/1-Timer复接排队是一个连续时间随机过程。到达过程是连续时间批马尔可夫到达过程（[5]），其中批大小表示在到达时刻到达的数据单元的数量。服务器执行多路复用：它等待L个数据单元，从它们中编译一个包，并以确定性的服务时间间隔（根据FCFS服务规则）为其服务。如果没有足够的数据单元形成一个完整的输出包，服务器会等待更多的数据到达，从而导致作业的额外等待时间。为了减少等待时间，引入了计时器（T）。该定时器确保当数据单元到达队列的头部（位置1到L，因此它将被包括在下一个分组中）时，它将在时间T被服务，即使在此时间期间没有足够的到达来形成完整的分组。在这种情况下，服务器形成部分填充的输出分组，并以相同的服务时间（Service Time，简称TIME）为它服务。为了更好地描述服务机制，我们将其行为总结为以下3点。这3点将在后续章节中多次提及，并将在分析过程中用作需要不同治疗的3例病例：P1. 当队列中有L个或更多数据单元时，计时器不运行。服务器从队列中取出前L个数据单元，编译数据包，并启动服务。在服务结束后（时间1），队列大小仍然超过L，一个新的服务开始。在我们的模型中，队列只包含等待的数据单元;服务已经开始但尚未结束的数据单元不包括在内，它们存储在临时缓冲器中。P2.如果当服务开始时队列大小变得低于L但高于0（在取出其服务已经开始的L个数据单元之后），则定时器启动。当服务准备就绪并且队列仍然低于L时，没有新的服务开始，直到计时器过去，或者足够数量的数据到达（参见图1（b））。P3. 如果到达时队列为空，则G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2527⎢⎥如果到达时间低于L，则立即启动计时器。第一个服务可以在队列大小超过L或计时器超时时启动。当然，当服务器中的数据包没有离开系统时，服务无法启动（图2）。定时器值（T）甚至可以小于1。在这种情况下，如果到达时刻的剩余服务时间小于定时器，则只有进入空队列的到达可以由定时器检测该系统在T>0时是非功守恒的，在T= 0时是功守恒的我们在这里集中讨论第一种情况考虑到系统的要求，定时器的设置是一个工程问题。其代价是，如果定时器长，则分组利用率高，但等待时间增加。如果定时器较短，则等待时间较短，但是分组利用率较低。数据包利用率其特征在于分组中传输的平均数据量复接器的输入业务由基数为m的连续时间批马尔可夫到达过程描述[5]。它的m×m生成器是denospeaked d byD. 这一灵活的过程是通过三个步骤来完成的Di（Ki=0时其中[Dk]i，j对应于k个数据单元的平均值从i到j的状态转换。背景马尔可夫过程和计数过程由J（t）和N（t）表示。然后N（t），J（t）一起形成马尔可夫链，以下生成器：D0D1D2.⎢⎢Q=0⎢⎣⎥⎥D0D1... ⎥ ⎥D0... ⎥⎦. . .在下面的章节中，我们用P（k，t）表示这个马尔可夫链的瞬态转移矩阵，使用以下定义：[P（k，t）] i，j= Pr（N（t）= k，J（t）=j|N（0）= 0，J（0）=i）。（一）BMAP是马尔可夫分析中一种强有力的交通特征建模工具。它可以从测量的交通行为构建[7，4]。3分组队列长度分布第2节的排队系统可以由分组离开时刻的离散时间马尔可夫链来表征。在偏离处嵌入通常导致所谓的M/G/1型结构，在我们的例子中也是如此的.28G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25⎥⎥⎢. ⎥⎢⎥⎢⎥转移概率矩阵建立如下：⎡⎤你好⎢⎥⎥阿... ⎥⎢阿... ⎥X=0⎢（二）阿... ⎥⎢ ⎥⎢ ⎥阿... ⎥⎣ ⎦. . ..通常M/G/1型矩阵由它们的二次矩阵块定义。现在我们用它的块行来定义矩阵，因为它简化了定义。m×m块内部的状态反映了到达过程的状态从块i到块j的转换意味着队列大小从从最后一个出发时刻到j。矩阵行A对应于第2节的情况P1。在这种情况下，由于计时器不起作用，所以间隔出发时间正好是10秒在下一个嵌入点处，服务器将队列减少L，因此队列大小的变化等于在时间间隔内到达的时间减去L。故A为：⎡ ⎤P（0，）P（1，）P（2，）P（3，）.⎢⎢⎢⎢A=0⎢⎢⎢⎣⎥⎥P（0，n）P（1，n）P（2，n）. . .⎥⎥⎥P（0，n）P（1，n）. . . ⎥⎥. . .. . ..⎥⎦P（0，n）.、（3）L×m行其中P（k，k）由等式（1）给出。（一）.由于计时器的影响，B的定义更加复杂。我们进一步划分B，以区分完全空闲（P2）和不空闲（P3）。G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2529⎢⎥⎢·⎥⎢⎥..⎢⎥完全空闲（P3）情况：⎡ ⎤B组⎢ ⎥⎢⎢B=⎢⎣⎥⎥- 是的（四）B⎦第一块行（具有高度m）描述了从空闲总线的转换（这些总线由B表示，并且转换到第2部分中的P3），其他行描述从缓冲器级别1-在这两种情况下，定时器开始（如果批大小小于L，则在第一次到达之后B开始），并且下一次转换可能发生在第二次之后。级别1和L之间的队列大小的演变对于捕获定时器的效果是重要的。因此，我们定义了以下两个马尔可夫链生成器。连续时间马尔可夫链生成器Q遵循1和L之间的队列大小增加过程，Z（t）是时间t期间队列大小增加过程的转移概率矩阵（因此Z（t）=eQt）：⎡ ⎤ ⎡ ⎤D0D1... D L−2P（0，t）P（1，t）. P（L − 2，t）⎢我... D⎥⎢ ⎥P（0，t）. P（L − 3，t）⎢0Q=0L−3 ，Z（t）=⎢.- 是的（五）⎥- 是的. ..⎥⎢⎣ ⎦ ⎣D0. . ..⎥⎦P（0，t）图（t）描述了定时器的视频。[i（t）]i，j是从i（1≤i≤L）个数据单元开始的概率，但在下一次服务开始后，系统的状态将是j下一个服务可以在必要数量的数据单元到达时开始，直到时间t（等式1中的第一项）。（6）），或者在时间t，即使完整的分组没有出来，也提供缓冲器内容（等式（6）的第二项）6）。该概率矩阵由下式计算：⎡ ⎤ ⎡ ⎤DL−1D L...D KI m×m0...⎢∫t⎢⎥ ⎢ ⎥⎥ ⎢ ⎥QτDL−2DL−1. . . DK−1DKQt Im×m0. . . ⎥t =e0dτ·-是的⎣.. ........ DK+e⎥ ⎢ ⎥⎦ ⎣ ⎦D1D2............................... DK我m×m0.（六）.30G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25⎢⎥队列大小队列大小LL服务器服务器 （一）不（b）第（1）款Fig. 1. 可能的场景从1号到L号的缓冲器如果缓冲区大小为n1和L−1（B），则必须计算在缓冲区间隔（服务器繁忙期间）内到达的数据单元数量。如果到达的数据单元将缓冲器增加到L以上，则服务一个新的数据包在完成前一个数据包后立即开始（该事件由等式1的第一个矩阵项表示）。 7，并描绘在图1（a））。如果缓冲器液位仍然低于L（等式2的第二项），7，如图1（b）所示），由于定时器在缓冲器下降到L以下时开始计时，因此会产生一个最大长度为（T-R）+的额外延迟。由此可见：⎡ ⎤P（L − 1，）P（L，）.⎢ ⎥⎢ ⎥P（L−2， . . 联系我们B=.+Z（.），（7）- 是 的.. . . ⎥⎣ ⎦P（1，n）P（2，n） .如果在服务的开始阶段出现了紧急情况（B/S），我们有两种情况。在服务器繁忙期间（在空闲期间）可能没有到达。在这种情况下，下一个到达可以使队列高于L，立即引起新的分组服务的开始（等式1的第一项）。或者队列保持在L以下，并且等待时段到来（等待更多的数据单元）最大长度为T，因为到达空队列启动了定时器（等式8（图2（b））。第二种情况是在服务器繁忙期间到达。在这种情况下，到达可以使队列高于L，并且新分组的服务刚好在前一个分组的服务结束之后开始（等式2的第三项）。 图2（c）。 到达可以在L以时时G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2531下离开系统，并且等待周期以最大长度（T-（τ-τ））+开始，因为定时器在第一到达时间（τ）开始，并且当服务器变空时，从定时器τ-τ开始时间已经到期（等式10的第四项）。 8和32G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25L时间儿第一次到达时间儿T−1队列大小队列大小L服务器队列大小 （一）服务器队列大小L电子邮件（b）第（1）款L服务器服务器 （c）第（1）款不（d）其他事项图二. 可能出现的场景从空缓冲器开始图2（d））。 因此，我们有：ΣB=P（0，）（−D0）−1DΣDL+1Σ... D K+Σ+P（0，）（−D0）−1ΣD1D2 ...DL−1Σ·（T）+（八）+ P（L，n）P（L + 1，n）. + 的∫∆Σ+eD0τ·D D0Σ... DL−1·Z（τ −τ）·τ（（T− τ + τ）+）dτ。嵌入马尔可夫链（2）的稳态分布根据状态划分以如下方式划分：⎡Σ ΣΣ Σ⎤x=0 p0p1... p L−1pLpL+1...p2 L−1. . . 你好，``x0x 1其中p是大小为m的向量。 在本节中，我们定义了A和B块X。 稳态概率向量满足时间时间L2G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2533x=xX可以通过附录D中总结的矩阵分析方法获得。34G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）251ΣL⎪ΣL4等待时间分布等待时间分布P（W > w）是到达批次的等待时间（从其到达到其离开测量）超过给定阈值w的概率。如果某些参数保持不变，它可以很容易地计算出来。这些参数是：到达时的乘客长度（k）、剩余的服务器占用时间（t1）和从乘客下降到水平L以下的点测量的最大离开时间（t2）。如果我们知道这些参数的具体值，则等待时间分布PW（k，t1，t2）可以通过以下方式计算：⎧如果wt+，⎪⎪，k，k，、、、KPW（k，t1，t2）=如果k L，w≥t1+t2+，则为0我是说，、、、⎪⎪eQ（w−{k/L}如果k≥L， w≥t1+（T−）++否则，k，（九）其中h是大小为m的1的向量。第一项对应于服务器占用时间加上队列中分组的服务时间超过等待时间要求的情况在这种情况下，P（W > w）等于1。第二项包括等候时间规定确实得到满足的情况。如果等待时间要求大于服务器占用时间，加上队列中数据包的服务时间，再加上计时器引起的最大可能延迟，就会发生这种情况。后一个数量是如果缓冲器大小小于L，则为t2（这是t2的定义）。如果k≥L，则它是（T−T）+，因为当最后一个段在缓冲器中低于L时，服务器将被占用第三项意味着等待时间超过w，如果队列中的L长块（k属于该块）直到w−1才填满。[eQt]i是到达过程在时间t之前没有产生足够的到达以离开该块的概率，如果在开始时在块中有i个{k/L}（其中{}表示除法的余数）是到达后L长块内的缓冲器为了获得等待时间分布，我们必须将PW（k，t1，t2）乘以给定k，t1和t2参数的概率。由于生成的表达式很长，我们将其分为3部分，以使其更容易理解。这种划分是根据第2节中P1、P2、P3病例的划分。在每一部分中，我们产生的等待时间属性乘以G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2535通过它们的权重（q i），以及最后用于归一化结果的权重之和（qni）。P1最后一个离开点离开系统的位置在L以上（i > L，概率为pi）。假设标记的分组在时间t到达（从最后的服务时刻测量）。队列的长度将是最后一次离开时的队列大小（i）、在标记的数据单元之前到达的数据单元的数量（j）和到达的批次的大小（k）的总和。服务器忙至少在服务器空闲后，最后一个数据片段最多等待T− t。在这种情况下：Σ∞q1=∫∆Σ∞piΣ∞P（j，t）Dk·PW（i+j+k，−t，（T−）+）dt（10）I=L0j=0k=1该表达式考虑了在延迟期间的到达，因此权重如下（其也可以从等式2获得（10）通过设置PW（i，t1，t2）= 1）：qn1Σ∞=I=L∫∆pi eDt dtDA h0P2最后一个出发点在1和L-1之间离开系统。在排队期间到达的等待时间可以类似于前面的情况来计算，但是在排队之后队列仍然可以低于L。然后服务器变为空闲（由等式2的第二项表示）。11），并且计时器最多运行T−10（因为它在最后一次服务开始时启动因此，我们有：L−1q2=piΣ∞P（j，t）Dk·PW（i+j+k，−t，（T−）+）dt+i=10j=0（T−）+k=1ΣL−i−1+P（l，m）l=00L−l−i−1P（j，t）j=0Σ∞k=1Dk·PW（i+l+j+k，0， T−k−t）dt（十一）现在，我们涵盖了到达期间，加上到达，直到数据包完全填满或计时器过去。因此qn2是：qn22016年1月1日=pieDt dtDAh+100-1piL−i−1P（l，n）L−l−1T−P（j，t）dtDAhi=10i=1l=零j=00P3最后一次发车时系统为空。 对于挂起，服务器仍然很忙。 我们根据第一次到达的时间考虑2个子情况，36G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25发生在你之前或之后。在这两种情况下，计时器在第一次到达时启动。·第一次到达发生在10月。 等待时间概率由三个部分。第一个对应于第一个到达。第二项计算剩余的到达时间（以第一次到达的时间点为条件），第三项考虑的是当到达时间在L之后仍然低于LΣ∫∆Σ∞q3a=p0eD0tDk PW（k，−t，（TCU−+t）+）dt+0∫∆Σ∞+eD0tk=1Dl·0 ∫∆−t∞l=1∞Σ·0j=0P（j，s）Σk=1Dk PW（l+j+k，−t−s，（T−+t+s）+）ds dt+∫∆ΣL−1LΣ−l−1+eD0tDlP（i，−t）·0l=1（T−+t）+i=0时ΣL−l−i−1·0j=0P（j，s）Σ∞k=1Dk PW（l+i+j+k，0，T−k +t−s）ds dt（十二）这种情况的权重包括在等待期间的到达，以及qn3a∫∆=p00eDt dtDAh+（T−+t）+∫∆eD0t0100-1DKk=1L−k−1l=零P（l，n−t）·（十三）L−l−k−1·j=00P（j，s）ds dt DA h·清洗后，清洗器仍然是空的。第一项与第一次到达的等待时间有关。 如果第一个到达的批次大小小于L，则其他到达可能在（0，T）间隔（第二项）中的时间t到达，经历T-t剩余计时器值。因此，q3b和qn3b是：G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2537K0Σ∞q3b=p0eD0<$（−D0）−1k=1Dk PW（k，0，T）+L−1+p0eD0<$（−D0）−1Dl P（j，t）Dk PW（l+j+k，0，T-t）dt，l=10j=0k=1（十四）和qn3b =p0eD0<$（−D0）−1DAh+p0eD0<$（−D0）−1100-1DlL−l−1TP（j，t）dtD Ah.l=1j=00（十五）最后，等待时间分布计算如下：q1+q2+q3a+q3bP（W > w）=qn1+qn2+qn3a+qn3b可以类似地获得等待时间的第i时刻，因为知道相同的三个参数（k，t1，t2），所以等待时间时刻易于计算。5分析算法把第3节和第4节的结果放在一起，算法的工作原理如下：(i) 构造流量源的BMAP描述。如果有许多不同的流量源，每个流量源都必须由单独的BMAP建模，并通过Kronecker运算聚合在一起。例如，如果D（i）是传输源i的BMAP矩阵，并且我们有P个独立的BMAP，则聚合的BMAP被构造为：Di=D（1）D（2）···D（P）我我我(ii) 根据第3节构造A和B矩阵。在这个步骤中可能会出现数值问题。为了克服这些问题，我们使用了以下程序。• P（k，t）矩阵的计算根据附录C。的计算出的P（k，k）矩阵的个数决定了A和B的大小。• 在计算ε（t）时，两个量teQxdx和eQt可以是：使用随机化一起有效计算（见附录B）。38G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25•在 但是，积分可以通过transpezoid规则或辛普森法则 通过再次随机化计算eD0t(iii) 求解所得到的M/G/1型马尔可夫链的稳态。我们使用了[6]中提出的方法，总结见附录D。稳态概率的计算在它们变小时停止(e.g.、pi10−6）。(iv) 根据附录A计算等待时间分布。所有出现的数字问题已经提到。我们注意到，计算矩阵指数的矩阵或者很小（大小m×m）或不依赖于积分变量，因此代替数值积分可以通过随机化计算。唯一的例外是q3a，这里的数值积分是不可避免的.6数值结果我们在MATLAB中实现了上述讨论的计算方法，并在OMNeT++（[1]）中开发了 一 个 仿 真 工 具 来 检 查 表 达 式 和 MATLAB 实 现 的 正 确 性 。 图 中 显 示 了MATLAB（用线表示）和仿真结果（用点表示）。我们评估了以下示例。存在N个具有导通行为的跨导源。开和关周期分别以参数α和β呈指数分布。在开启时段期间，每个traffic源生成具有指数分布的到达时间间隔的traffic，强度为λ。在每个到达时刻，源生成k个数据单元，概率p（1−p）L-k/（1−（1−p）L），这是一个几何分布，参数p在L处截断。多路复用器组装包含最大L个数据单元。在示例中，这些参数具有以下值：L=8α=1/1000β=1/1500λ=50N=5P=（变化）=（变化）G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2539图3显示了不同计时器值的等待时间分布。我们使用参数p = 0。在这个例子中，x = 8，x = 2。为了放大定时器的效果，参数选择为低负载。该图验证了计时器值越高，等待时间越长的假设。此外，在曲线中可以观察到两个跳跃0.60.50.40.30.20.102 3 4 5 6 7 8 9 10不图三. 等候时间一个在2 ° C，一个在T+1 ° C。跳跃的解释如下。 假设队列中有给定数量的数据（ w）概率不会通过将服务时间减少到零而减少到零（即，当T> w时，将输出容量增加到无穷大），如图4所示，T= 8。在所有示例中，使用我们的MATLAB实现计算等待时间分布的一个点在Pentium 4T=1 ， 分 析T=3 ， 分 析T=5 ， 分 析T=1 ， 模 拟T=3 ， 模 拟T=5，模拟P（W>t40G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25一0.90.80.70.60.50.40.30.20.110.90.80.70.60.50.40.30.20.100.5 11.52.5 3.54.5服务时间（一）0电话：+86-510 - 8888888传真：+86-510 - 8888888服务时间（b）第（1）款见图4。 P（W > 5）vs.服务时间2.4 GHz机器，而模拟仅在约1分钟后才能给出可接受的结果唯一的例外是最后一个示例，其中在N= 15时执行花费了更长的时间（1-2分钟）。当然，使用C实现，我们的分析算法的速度可以大大提高7结论本文提出了一种计算BMAP/D/1-Timer多路复用器排队等待时间分布的模型和算法所提出的算法是专为一个高效的数值实现。最后给出了一个数值例子。分析结果与仿真结果吻合较好。在这个例子中，我们还研究了这种排队的等待时间分布的特殊性。A等待时间分布的数值方法表达式等式（10）、（11）、（12）和（14）式的积分很难有效地计算，因为数值积分通常很慢而且不准确。幸运的是，大多数的数值积分可以被消除。替换Eq。（九）根据上述表达式，大多数积分将采用以下形式：beQtdt，可通过随机化有效计算（见附录B）。为了完整起见，我们在这里给出了q1，q2，q3a和q3b，并消除了所有可能的数值积分。T=1 ， 分 析T=3 ， 分 析T=8 ， 分 析T=1 ， 模 拟T=3 ， 模 拟T=8，模拟P（W>5T=1，分析T=3，分析T=8 ， 分 析T=1 ， 模 拟T=3 ， 模 拟T=8，模拟P（W>5G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2541h{i+j+k}LLLΣ替换Eq。 （9）在Eq. （10），我们得到：Σ∞Σ∞q1=pi不好意思第一章P（j，t）dtDk h+第二章 P（j，t）dtDkeQ（w−LI=Lj=0k =10s（A.1）积分s1和s2的极限是从PW（k，t1，t2）的定义中推导（9））;低于s1，PW（·）等于1，高于s2，它等于零，因此：s1=min{ 0，.+[.i+j+k+|∆− w}LI+J+K+（A.2）s2=min{ 0，+[|∆+ (T CU− ∆)+ −w}L同样，Eq。 （11）可以转化为：100-1 Σ∞Σ∞. 第一章第二章Σ ΣΣQ2=i=1pij=0k =1P（j，t）dtDk h+0s1P（j，t）dtDkeQ（w− k）h{i+j+k}+（（T−100-1L−i−1L−i−1L−i−l−j−1pii=1l=零P（l，n）.l=零k=1（T−）+P（j，t）dtDk0eQ（w−k）h{i+j+k+k}+Σ∞k=L−i−l−jI{w<[i+j+k +k]|{\fnSimHei\bord1\shad1\pos（200，288）}P（j，t）dtDk h+0（T−）+42G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25I{[i + j + k + k]|n≤w<[i + j + k + l|+（T−P（j，t）dtDkQ（w− 1）Σh{i + j + k + l}。L LL0（A.3）其中，积分极限s1和s2已经由等式2定义。 （A.2）。q3a可以转换为以下形式G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）2543HL1LL更好的可计算1000-1。（2q3a=p0eD0tdtDk h+k=10∫∆Σ Σ+I{w T+}max（（2 −w）+，（−T）+）eD0tdtDk eQ（w−）h+K+p0 Σ∞K=L.伊什0伊什eD0tdtDk h+S1eD0tdtDk eQ（w−Σ{k}++p0∫∆Σ∞eD0tdtΣ∞Σ∞DlΣI{l+j+k L}. （2P（j，s）dsDk h+0l=1j =0k=10. （+（2−w−t）+P（j，s）ds+Σ∫∆−tΣΣ Σ+I{w T+}（−t−T）+P（j，s）ds DkeQ（w−）hk+l+j+.s−tΣΣs2−t+I{l+j+k≥L}P（j，s）dsDk h+0P（j，s）dsDks1−teQ（w− k）h{l+j+k}dt+p0∫∆eD0t0100-1Dll=1L−l−1i=0时P（i，−t）ΣL−l−i−1j=0L−l<$−i−j−1<$（T+t−w）+k=10P（j，s）dseQ（w−）hk+l+i+j+Σ∞+k=L−l−i−j.I{w<[n+i+k+ n]|}（T−0P（j，s）dsDk h++I（T−+t）+P（j，s）Q（w−ΣΣ{[+i+k+|n ≤w<[n+i+k+ n]|+（T−ds Dkeh{k+i+j+n}L LL0（A.4）Σ12∫44G. 霍瓦特湾Telek/Electronic Notes in Theoretical Computer Science 128（2005）25q n3 a 也可以被重写成数值上更有效的形式。 首先我们