Searching for Tight Performance Bounds in Feed-Forward Networks

Download Now Date Added: Dec 2009
Format: PDF

Computing tight performance bounds in feed-forward networks under general assumptions about arrival and server models has turned out to be a challenging problem. Recently it was even shown to be NP-hard. The authors now address this problem in a heuristic fashion, building on a procedure for computing provably tight bounds under simple traffic and server models. They use a decomposition of a complex problem with more general traffic and server models into a set of simpler problems with simple traffic and server models. This set of problems can become prohibitively large, and they, therefore, resort to heuristic methods such as Monte Carlo. This shows interesting tradeoffs between performance bound quality and computational effort.