Graduate Seminar – David Lastine

Date/Time
Date(s) - 19 Feb 2014
1:10 PM - 2:00 PM

Location
3043 ECpE Building Addition

Title: Are you sure your network performance is better?

Speaker: David Lastine, ECpE Graduate Student

Adviser: 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.

back to Seminars list