Example: TCP Retransmission Timer Control

In this section, we illustrate our approach on the example of the Esterel module handling the management of the TCP retransmission timer. This module originates from a prototype specification of the complete TCP protocol in Esterel [Cas94a] (see Figure 2).

The Esterel module implements the management of the TCP retransmission timer. It reacts on the reception of three external events: (1) N_S: a signal indicating that the application requests the transmission of a data packet. Its value is the next sequence number to be sent. (2) N_A: a signal indicating the receipt of an acknowledgement. Its value is the acknowledged sequence number. (3) ALARM: a signal indicating a packet loss.

In an Esterel program, a control transfer can occur in two different ways: first, each if statement introduces two arcs, one leading to the basic block that is executed when the if test is true, and one leading to the basic block that is executed when the if test is false. Second, each await in the Esterel program has one arc for each external event defined for the protocol configuration. The arcs will be referred to as branches in the following. The Esterel code shown in the Appendix contains the branch probabilities we assume for the retransmission management module, and Figure 1 shows the Markov chain. The average number of times each state is visited in the TCP protocol can now be calculated by setting up the system of linear equations defined in the previous section. The result is the vector V=(1, 172, 172, 2000, 1900, 1710, 100, 100, 1539, 171, 152, 1, 99). We observe that some states are visited much more frequently than others. States 4 and 5 are the most frequently visited states with a probability of and .

This information can be used for code optimization. Let us assume that we choose to optimize our protocol code by inlining some of the calls to the function SET_ALARMthat appear in , and . Let us also assume that the speed gain achieved per function inlining is G time_unitsand the code increase cost is C size_unit. The gain achieved by inlining the function calls SET_ALARMin is then equal to xxG. Its cost is equal to C ( is the number of calls to SET_ALARMin . It is always equal to 1 in our example).

States with a high ratio = /(xC) are the most interesting candidates for inlining. An heuristic that could be used to optimize the code speed for a given code size constraint is to inline the functions in the order of descending until the code size limit is reached. We see that the function SET_ALARMof is the most interesting candidate for inlining. In fact by applying inline expansion to , we achieve 81%of the maximum time saving with only 50%of the maximum code size cost (the maximum gain and cost result from inlining all function calls).