In Section 1 we informally introduced the service curve model. In this section we apply this method to derive a closed form for a lower bound on the worst-case end-to-end delay for Connection 0 in Section 4 using the service curve method.. We first derive a closed form for an upper bound on the service curve for a FIFO server, and then apply this result to derive the upper bound on the worst-case end-to-end delay lower bound on the worst case delay.
Let be the input traffic function of Connection i at Server k and be the constraint function of input traffic , and let be the output traffic of Connection i at Server k and be the constraint function of output traffic .
The service curve can be used to effectively evaluate the end-to-end delay suffered by traffic, as described in the following theorem.
Consider Server k in Figure 3 serving n+1 connections. Let
and
For any time t, the amount of data departing the server during [0,t) is , and is the time of the -th bit arrival at the server. Since the server uses a FIFO scheduling discipline, we know that bits of data from Connection i have departed the server during time interval [0,t). So
Therefore, by the definition, we know that if
then is a service curve of Connection i offered by Server k. Q.E.D
Let
and
The definition for service curve is very loose. For a connection, there are infinitely many functions that satisfy Inequality (C.26). For example, a function with zero value is a service curve by the definition. In the following, we define an approximation for the service curve of a FIFO server.
For any , if for , let , we have that
On the other hand, let for all , it is easy to know that
and
Therefore, we have that
and
This is a contradiction to Lemma C.6. Q.E.D
According to Theorem C.4, we have that . For , the maximum available service for Connection i during time interval [0,t) is . Therefore for all . Q.E.D
In order to use the above results, we need to accurately estimate the internal network traffic. Following Lemma C.6 gives a tight estimation about the constraint function of output traffic of each connection.
Let be the time such that . Without loss of generality, we assume that for and , for . After time , we assume that for and , for . Since at time , the queue length of Server k is , according to FIFO scheduling discipline, during , the output traffic of Connection i is zero. But after time , the output traffic of Connection j ( ) is zero. Hence
and
Therefore we have that
Q.E.D
Now we can approximate the service curves offered by servers to Connection 0 in the example presented in Section 4.
According to Theorem C.4, for k=1, we have
Figure 9: Connections at the First and the Second Server.
For k=2, we know that the traffic constraint functions for Connection 3 and Connection 4 are the same as . Furthermore, by Lemma C.6, the constraint function of Connection 2 is lower bounded by , where is the maximum queue length of the middle output port of the first switch when it only serves Connection 0 and Connection 1 and can be easy evaluated as
Substitute into , we have that . Therefore by Theorem C.4, we obtain that
Figure 10: Connections at the k-th switch.
For k>2, similarly, we can obtain that
where is the maximum queue length of the middle output port of the (k-1)-th server when it only serves Connection 0, Connection (2k-3), and Connection (2k-4) and can be easy evaluated as
Therefore, we have
Q.E.D
According to Theorem C.4, network service curve of Connection 0 can be estimated as following:
Therefore