Searching for Tight Performance Bounds in Feed-Forward Networks

Abstract. Computing tight performance bounds in feed-forward net-works 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 [1]. We now address this problem in a heuristic fashion, build-ing on a procedure for computing provably tight bounds under simple traffic and server models. We 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 we therefore resort to heuristic methods such as Monte Carlo. This shows interesting tradeoffs between performance bound quality and computational effort. 1 Motivation and Related Work When designing or analyzing a network, one of the most important aspects is its performance under various load conditions. A number of methods for that kind of analysis have been devised, among them network calculus, which describe