We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem therefore reduces to the problem of constructing a schedule for these permutation matrices. In this paper we derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm we first place tokens randomly in continuous time for each permutation matrix. If the $n$th token that appears corresponds to permutation matrix $M_k$ then we schedule matrix $M_k$ in the $n$th time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang, Chen, and Huang.
展开▼
机译:我们考虑在高速输入排队的交换机中为保留的流量提供延迟范围的问题。我们假设带宽需求矩阵是已知的,并且我们使用现在的标准方法将这个矩阵分解为置换矩阵的凸组合。因此,我们的问题减少到为这些置换矩阵构造时间表的问题。在本文中,我们推导了基于概率技术的四种算法的延迟边界。对于每种算法,我们首先为每个置换矩阵在连续时间内随机放置令牌。如果出现的第$ n $个令牌对应于置换矩阵$ M_k $,则我们在第$ n $个时隙中安排矩阵$ M_k $。这些算法的不同之处在于如何定义随机令牌过程。对于其中的两种算法,我们能够执行去随机化处理,从而获得确定性的时间表。我们通过数值计算表明,在许多情况下,所得到的延迟范围小于以前最著名的Chang,Chen和Huang的延迟范围。
展开▼