Next: References Up: No Title Previous: Example: TCP Retransmission

Future Work and Summary

Markov analysis requires that we know the probability of traversing each transition, i.e. the average number of times each branch in the program flow graph is traversed in all executions of the program. The best way for determining these probabilities is still an open issue. First, we could reuse one of the two methods used in compiler technology, which are the collection run-time statistics and the use of static branch prediction heuristics ([Bal93], [Wag94]).

However, we see a third alternative specific to protocol configuration, which is to do the branch prediction at two different points in time. At implementation time, the author of a protocol building block analyses the algorithm used and determines environment variables influencing the performance that can be easily determined by the application programmer.

As an example, we analyze how the probability of the N_A and ALARM events in the retransmission timer management module may depend on the environment (i.e. the application and the network) in which this module is used. For each packet that triggers starting the retransmission timer, either an acknowledgement will be received (N_A event) or the timer will go off (ALARM event). If the timer works correctly (i.e. does not go off too early [Jac88]), each time-out indicates a packet loss.

Thus, the probability of an ALARM event is (almost) equal to the probability of a packet loss on the network that is used. Different network types have different packet loss rates, and also loose packets for different reasons. One possible cause of packet loss is that the packet was damaged during network transmission. For ``wired'' networks, this is usually an infrequent event (<<1%[Jac88]). For wireless networks, in contrast, packet losses occur very frequently (say 20%). The fact whether the application (and thus the building block contained used by the application) is more often used on a wired or on a wireless network can be easily determined by the application programmer. The assumption on the average packet loss rate for these networks is hidden in the protocol library. Moreover, when the application frequently uses a datagram network such as the Internet for making wide area connections, a further (and more common) reason for packet loss is network congestion. Again, this fact can be easily decided by the application programmer. The value of 5%packet losses used in our example was derived by assuming that an Internet connection is used, and that congestion avoidance is effective. For other probabilities, the applicability of this analytical approach is less clear ( e.g. the probability given in the example that (?N_A >= N_Clock) is true should be considered as ``for demonstrational purposes only''. The actual probability depends on a complex relationship between the data volume sent, the window size used, and other factors).

Applying code optimizations such as inlining and header prediction to protocol code requires identifying the most frequently executed parts. In this paper, we have shown how to automate this using Markov analysis of the the frequencies of different external events that can activate the protocol automaton (such as application-data-, network-packet- or timer-events), and the outcome probability of internal test nodes nodes within the automaton. Future work will have to address the issue of best way to determine the transition probabilities required for this analysis.

Next: References Up: No Title Previous: Example: TCP Retransmission
Wed Aug 9 15:22:05 MET DST 1995