Title: Are you sure your network performance is better?
Speaker: David Lastine, ECpE Graduate Student
Advisor: Arun K. Somani, Associate Dean for Research, Jerry R. Junkins Chair Professor
Abstract: Many point to multipoint or multipoint to multipoint routing problems in practice are solved by heuristic algorithms that make calls to a shortest path function. The relative performance of routing algorithm heuristics is often evaluated by simulating them on well-known topologies.
When multiple shortest paths exist, the actual path returned by a shortest path algorithm depends on the order in which nodes or edges are listed in a data structure. If the shortest path algorithm is a building block of a heuristic solving a more complex routing algorithm, then the solution found by the heuristic does not depend just on the topology but on data structure order as well.
Differences in the solutions found can have a significant impact if routing is being done for dynamic connections in a network that has to reject some request due to lack of resources. We consider a couple of heuristics that when given a set of nodes find a simple cycle in the network which includes these nodes. We show that for a couple of topologies, the number of blocked request in a simulation is sensitive enough to data structure order that it can determine which algorithm appears to perform better.