Worst-case Traffic for Oblivious Routing Functions
Worst-case Traffic for Oblivious Routing Functions
复制标题
DOI：
10.1145/564870.564872
复制
发表时间：
2002-08
影响因子：
2.3
通讯作者：
Brian Towles;W. Dally
中科院分区：
文献类型：
--
作者：
Brian Towles;W. Dally
本文提出了一种算法，在任意互连网络拓扑结构上为任意不经意路由算法寻找最坏情况的业务模式。由遗忘路由算法提供的信道负载的线性使问题能够被映射到一个bipartitemmaximum-weight匹配，它可以在多项式时间内解决的多项式路径数的路由功能。找到确切的最坏情况下的性能是以前棘手的，我们展示了一个例子，传统的表征技术高估了一个特定的路由算法的吞吐量的47%。
This paper presents an algorithm to find a worst-case trafficpattern for any oblivious routing algorithm on an arbitrary interconnectionnetwork topology. The linearity of channel loading offered by obliviousrouting algorithms enables the problem to be mapped to a bipartitemaximum-weight matching, which can be solved in polynomial time forrouting functions with a polynomial number of paths. Finding exact worstcaseperformance was previously intractable, and we demonstrate an examplecase where traditional characterization techniques overestimate thethroughput of a particular routing algorithm by 47%.