[算法]时间窗

《电力名词》第三版。 2100433B

从电力元件发生故障起至获得足够的原始采样数据(微机进行计算、判断)所需要的时间。

滑窗算法与跳窗算法类似，滑窗(Moving Window)算法也是通过限制各个时间窗口内所能接收的最大信元数对业务量进行控制。区别是，在滑窗算法中，时间窗口不是向前跳，而是每过一个信元时间向前滑动一次，滑动的长度是一个信元的时间。 以下是几种UPC算法。信元一旦被UPC判定是违约的，就要对其采取管制措施。

主要措施包括：

1． 丢弃违约信元甚至所在连接上的所有信元。这是对违约信元及其连接的最直接、最严厉的惩罚。在有些场合下，这种措施不太合理。因为用现有的业务量参数难以对业务特征进行完全准确的描述，而且在呼叫建立阶段这些参数常常难以确定。

2． 将违约信元打上标记（将信元头中的CLP置1），交换节点在网络发生拥塞时丢弃这些信元。显然，这对违约信元的处理要宽松一些。但它要求网络能够区分标记和未标记信元。会为违约者盗用资源提供机会。

3． 延迟违约信元来平滑业务特性。这种方法需要很大的缓冲区，并会增加时延。同样也会为违约者盗用资源提供机会。

4． 通知源端降低发送速率。这种方法的缺点是反应迟缓，难以及时保护履约连接的QoS。2100433B

与之相关的算法较多，有自适应组装算法，其优点是克服了固定门限组装算法无法适应输入业务动态变化的缺陷，获得较好的网络性能。为了减小IP分组的组装时延，有人提出了一种流量预测的组装算法，通过线性预测的方法预测数据突发长度，在数据突发组装完成之前就发送控制分组为其预留资源，将组装时间和偏置时间部分重叠，可以在很大程度上降低IP分组的时延，还有人提出了一种复合组装算法，通过将多种QoS等级的IP分组按照一定的顺序组装到一个数据突发中，可以提供更多等级的QoS保证。

[polynomial-time algorithm]

若一个算法的计算时间不超过其所求解问题的输入长度的一个多项式，则称该算法为多项式时间算法；其中计算时间和输入长度是以确定性图灵机为计算模型。通常认为只有多项式时间算法是可以求解大规模的实际问题，故多项式时间算法也称好算法或者有效算法。

若一个问题多输入仅限定于整数，而求解该问题多算法A的计算时间不超过其输入长度和其中整数的最大绝对值的一个多项式，则称A为伪多项式时间算法，比如，背包问题和划分问题，则可以认为它是理论上相对容易求解的困难问题。