Algorithms for the reduction of timed finite state graphs

摘要

A set of algorithms to reduce the size of timed finite state graphs are presented. In particular, we develop a more general algorithm for vertex folding than those presently existing. It is based on the law of conservation of transition time. We demonstrate the application of these reduction algorithms to a version of the stop-and-wait protocol.

rn

We have also developed a graph reduction software package incorporating all these algorithms which can be used in automated performance prediction. Graph reduction software tools such as these are important and form an integral part of automated protocol performance prediction tools[RUD 83].