IEEE Computer Architecture Letters · 2008 · 34 citations · 14 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer NetworksInterconnection NetworksMesh NetworksRoutingRouting AlgorithmsRouting ArchitectureHeuristic AlgorithmsLatency-dominated Performance AnalysisMinimal RoutingMultidimensional Mesh NetworksOblivious RoutingRouting In Mesh NetworksThroughputWorst-case Optimization
This letter presents a new oblivious routing algorithm for 3D mesh networks called randomized partially-minimal (RPM) routing that provably achieves optimal worst- case throughput for 3D meshes when the network radix fc is even and within a factor of 1/k <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> of optimal when k is odd. Although this optimality result has been achieved with the minimal routing algorithm OITURN for the 2D case, the worst-case throughput of OITURN degrades tremendously in higher dimensions. Other existing routing algorithms suffer from either poor worst-case throughput (DOR, ROMM) or poor latency (VAL). RPM on the other hand achieves near optimal worst-case and good average-case throughput as well as good latency performance.
14
Alfred V. Aho, Margaret J. Corasick · Communications of the ACM · 1975 · 2.9K citations · Full text
Deep packet inspection using parallel bloom filters
Sarang Dharmapurikar, P. Krishnamurthy, Todd Sproull et al. · IEEE Micro · 2004 · 435 citations
Deterministic memory-efficient string matching algorithms for intrusion detection
Nathan Tuck, Timothy Sherwood, Brad Calder et al. · 2005 · 397 citations
Gigabit rate packet pattern-matching using TCAM
Yu Fang, Randy H. Katz, T. V. Lakshman · 2004 · 295 citations