In this paper, we represent an improved algorithm of performance evaluation for communication protocol. It is an algorithm that analyzes Extended Timed Perti Net models including time which have been successfully used to model and evaluate the performance of distributed system. While Timed Petri Nets generally limted to free-choice and safe nets, our algorithm permits the construnction of elegant models of restricted concurrent processing. Furthermore, to reduce the state space size of Timed Reachability Graph, we improve the algorithm by using Maximum Firing Rule and sets of simultaneously firing transitions. Procedures for constructing of Timed Reachability Graphs and analyzing are presented, and we demonstrate the usefulness of this algorithm by applying it to the analysis of the communication protocol.