1=i一个可行的连接关系可以看作是图论中的二分图的匹配，调度算法的核心就是在各个时刻根据VOQ的状态决定匹x(t)配，从而置相应的ij。在到达过程Ai(t)的建模中，作者设计并实现了简单的贝努力分布的业务和基于马尔可夫过程调制的ON-OFF过程的突发业务。需要指出的是，对于突发业务建模的方法很多，作者使用ON-OFF过程建模实现简单并且能够真实地反映核心路由器线路卡输入数据包切片后的到达情况[5]。
当前在输入排队调度算法中最为流行的是NickMckeown 于1994年 提出的iSLIP算法[5]，该算法以其高性能易于硬件实现成为了输入排队调度算法的里程碑，并且已经在Cisco 的GSR12000 路由器和Stanford 大学的Tiny Tera项目中得到了成功应用。算法已经被证明在均衡业务条件下可以达到100%吞吐率[4]。
3 ON-OFF模型分析
本文使用马尔可夫过程调制的ON-OFF过程对突发业务建模。把输入排队调度系统设定为离散时间系统，以固定间隔时隙(slot)为基本时间单位。
如图2 所示，ON －OFF过程可以考虑成一个恒定速率发送cell的信源通过一个随机开关后得到的随机过程。使用“ON” 区间表示开关闭合期，“OFF”区间表示开关开启期。所以在“ON”区间内，信元的到达速率恒定(本文中使用归一化到达率，信元到达率为1，即每个时隙均有信元到达)；在“OFF” 区间内，信元的到达率为0，即没有信元到达。ON-OFF 信源产生的突发业务如图3所示。
对于开关的ON 和OFF状态使用两个状态的一阶马尔可夫过程来调制，由图4可 见，由ON状态转移到自身的概率为1-P1 ，转移到OFF 的概率为P1， 由OFF状态转移到自身的概率为1-P2 ，由OFF 状态转移到ON 状态的概率为P2。本时刻的转移与当前信源所处状态有关，与上个时隙信元所处的状态无关。
以Sn表示本时隙的状态，Sn+1表示下一个时隙的状态，
则上述转移过程可以描述为：
P(Sn+1=ON ∣Sn=ON)＝1 －P1(3)
P(Sn+1=OFF∣ Sn=ON)＝P1(4)
P(Sn+1=OFF∣ Sn=OFF)=1－ P2(5)
P(Sn+1=ON ∣Sn=OFF)=P2(6)
一步概率转移矩阵为：
以Ti-j
表示从状态i出发首次进入状态j的时刻，则
P(TON-OFF=n ∣S1=ON)＝(1－ P1)n-1×P1(8)
P(TOFF-ON=n ∣S1=OFF)＝(1－ P2)n-1×P2(9)
由几何分布的定义可知，ON和 OFF状态保持时间分别服从参数为1－ P1和 1－ P2的几何分布。
在使用ON －OFF过程模拟突发业务时，一般设定如下几个参数：
(1)平均到达率λ，表示平均在一个时隙产生一个cell的概率；
(2)平均突发长度burst_length，表明突发数据包的平均大小(单位为cell)；
(3)ON区 间长度几何分布参数average_on；
(4)OFF区 间长度几何分布参数average_off。
在实际仿真中这几个参数满足如下关系式：
idle_length=burst_length×(1-λ)/λ(10)
average_on=(burst_length)/(1 ＋burst_length)(11)
average_off=(idle_length)/(1 ＋idle_length)(12)
说明：根据马尔可夫链稳态方程[1]可知