We present a novel technique that speeds up state-space exploration (SSE) for evolving programs with dynamically allocated data. SSE is the essence of explicit-state model checking and an increasingly popular method for automating test generation. Traditional, non-incremental SSE takes one version of a program and systematically explores the states reachable during the program's executions to find property violations. Incremental SSE considers several versions that arise during program evolution: reusing the results of SSE for one version can speed up SSE for the next version, since state spaces of consecutive program versions can have significant similarities. We have implemented our technique in two model checkers: Java PathFinder and the J-Sim state-space explorer. The experimental results on 24 program evolutions and exploration changes show that for non-initial runs our technique speeds up SSE in 22 cases from 6.43% to 68.62% (with median of 42.29%) and slows down SSE in only two cases for -4.71% and -4.81%.

In this paper, an almost peer-to-peer (AP2P) clock synchronization protocol is proposed. AP2P is almost peer-to-peer in the sense that it provides the desirable features of a purely hierarchical (client/server) clock synchronization protocol while avoiding the undesirable consequences of a purely peer-to-peer one. In AP2P, a unique node is elected as a leader in a distributed manner. Each non-leader node adjusts its clock rate based on message exchanges with its neighbors, taking into consideration that neighbors that are closer to the leader have more effect on the adjustment than the neighbors that are further away from the leader. We compare the performance of AP2P with that of the server time protocol (STP), which is a purely hierarchical clock synchronization protocol. Simulation results, which have been conducted on several network topologies, have shown that AP2P can provide a clock synchronization accuracy that is indistinguishable from that of STP. Furthermore, AP2P is more fault-tolerant because it can recover from certain types of failures that STP cannot recover from.

In this paper, we report our work on extending the J-Sim network simulator to be an integrated environment for both simulation and model checking of network protocols. We also present a case study in which we model-checked AODV in J-Sim.

A reliable multicast protocol for wireless mobile multihop ad hoc networks (ReMHoc) is proposed. ReMHoc ensures the eventual delivery of the multicast data to all the multicast group members. ReMHoc is receiver-initiated and NACK-based, and it makes use of feedback suppression in order to avoid negative acknowledgement (NACK) and retransmission implosion. The loss recovery burden is distributed over the multicast group members in order to reduce recovery latency and end-to-end delay. Simulations (using GloMoSim 2.0) have demonstrated the scalability of ReMHoc.

In response to the important role that multicasting plays in wireless mobile multihop ad hoc networks, we study in this paper the reliability of the on-demand multicast routing protocol (ODMRP) in terms of the delivery of data packets. Using GloMoSim 2.0, the simulation results have shown that using ODMRP, the average miss ratio does not always increase with increasing the speeds of mobility of the mobile hosts in the ad hoc network. Instead, there is a "sweet spot" of values of the mobility speeds of the mobile hosts. In addition, the average miss ratio decreases with increasing the number of multicast group members, which indicates that ODMRP has more packet delivery capabilities for denser multicast groups.

Existing network simulators perform reasonably well in evaluating the performance of network protocols, but lack the capability of verifying and validating the correctness of network protocols. In this paper we have extended J-Sim - an open-source, component-based compositional network simulation environment - with the model checking capability to explore the state space created by a network protocol until either the entire state space is explored (if the state space is finite) or an error (e.g., a violation of a user-defined safety assertion) is discovered. We also exploit protocol-specific properties in the process of exploring the state space, to reduce the size of the state space and to guide the (best-first) search towards paths that can potentially locate errors in less time. As a proof of concept, we have demonstrated use of the J-Sim model checker in locating errors in an automatic repeat request (ARQ) protocol. As compared to the Maude LTL model checker, the J-Sim model checker can locate errors in a timely manner and with shorter error traces.