A common method to analyze the end-to-end delays suffered by connections in networks, with or without traffic regulation at intermediate nodes, consists of two steps. In a first step, a single-server analysis technique is developed to estimated the local worst case delay and characterize the output traffic, provided characterizations of all input traffic of the server. In a second step, starting from characterizations of all source traffic, local delay analysis is successively performed on each server along the path of the connection. As described earlier, the main disadvantage of this method is that the delay dependencies in successive servers without traffic regulation on a connection's path is ignored. So the obtained end-to-end delay bounds are very loose and the bursts are overestimated.
Figure 2: Algorithm Integrated.
Equation (10) can be used as the basis for improved end-to-end analysis methods, which better take into account delay dependencies. Algorithm Integrated, described in Figure 2, computes end-to-end delays in a cycle-free network with FIFO servers. It first partitions the network into subnetworks of one or two servers each (Step 1). It then identifies a topological ordering of subnetworks (Step 2). Next, it computes the local delays (Step 3.1) and the output traffic (Step 3.2) at each subnetwork. Finally, it determines the end-to-end delays by summing up the previously computed local delays (Step 4).
