Simulation of network traffic using non-deterministic user behavior models

[0001] The invention relates to computer networking, and, in particular, to the testing computer networks.

[0002] Computer networks and network devices have grown increasingly complex and continue to experience increasing loads. This is especially true for network devices connected to the Internet. Networks providing services over the Internet may experience load conditions of millions of concurrent users. Under such circumstances, service providers often require considerable proof that devices and applications will operate correctly when deployed under such conditions.

[0003] Traditionally, stress testing of network devices involves generating random packets and sending the packets to the devices. The random packets typically contain no meaningful data, and do not accurately simulate how real users acts. Some network testing tools record sample sequences of user activity and then play the sequences back to the subject device many times. These testing methodologies fall short of actually simulating realistic user activity. For instance, real-world users do not send meaningless packets at regular intervals. Nor do millions of concurrent users merely repeat the same sequence of behavior.

[0004] In general, principles of the invention are directed to techniques for modeling user behavior and generating realistic network communications for testing the performance and scalability of a network system. For example, a testing engineer creates one or more probabilistic state machines to simulate patterns of user behavior. A control server distributes the state machines to a cluster of testing devices. The cluster of testing devices use the probabilistic state machines to generate the network communications in a manner that accurately simulates real-world user behavior.

[0005] In one embodiment, the invention is directed to a method that comprises generating a non-deterministic model of a behavior of a network user and generating network communications based on the model to simulate the behavior of the network user and test a network system.

[0006] In another embodiment, the invention is directed to a system comprising a network system and a load generating device coupled to the network system via a network. The load generating device outputs network communications based on a non-deterministic behavior model that simulates the behavior of a network user to test the network system.

[0007] In another embodiment, the invention is directed to a computer-readable medium containing instructions. The instructions cause a programmable processor to generate a non-deterministic model of a behavior of a network user and to generate network communications based on the model to simulate the behavior of the network user and test a network system.

[0008] The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.

[0012] FIG. 1 is a block diagram illustrating an exemplary testing environment 2 that operates in accordance with the principles of this invention. In this example, testing environment 2 includes a control server 4, a testing cluster 6, and a subject network system 8. Control server 4 includes an analysis module 18. Testing cluster 6 contains a set of one or more load generating devices 10A-10N (collectively, “load generating devices 10”). Network system 8 may be any device or set of devices connected to testing cluster 6 via a network, such that the device or the devices can receive and process network communications and can send network communications. For exemplary purposes, subject network system 8 is shown to contain a router 12 and application servers 14A through 14N (collectively, “application servers 14”).

[0013] A testing engineer 16 begins a testing process by generating a non-deterministic model of a behavior of a network user. Load generating devices 10 in testing cluster 6 then generate network communications based on the behavior model to simultaneously simulate the behavior of multiple network users and test network system 8. Testing engineer 16 and/or analysis module 18 may then analyze network communications from network system 8 to verify functionality of the network system.

[0014] The model may describe behavior that is realistic for a network user interacting with network system 8 when the network system is deployed in a non-testing environment. For example, the behavior model may specify potential network communications that a network user could send. Because the behavior model is non-deterministic, the behavior model may generate more than one sequence of network communications. For example, the behavior model may specify a delay corresponding to an average time that a user waits before sending the network communication. Further, each node in the behavior model may specify a distribution for how likely and how much the user is likely to deviate from the average time. In this manner, the generated network communication may vary from simulation to simulation.

[0015] In some embodiments, the non-deterministic behavior model comprises a probabilistic state machine (PSM) composed of a plurality of nodes interconnected by a set of directed edges. In these embodiments, each of the nodes represents one or more actions that a network user may perform on network system 8. For example, an action might be a Point to Point Protocol (PPP) login to access network system 8. Other example actions include an attempt to send an electronic message (e.g., e-mail, short message service (SMS), or instant message), a dynamic host configuration protocol (DHCP) address acquisition, a hypertext transfer protocol (HTTP) request, a file transfer protocol (FTP) file request, a network ping, a secure sockets layer (SSL) login request, a request sent via a virtual private network, an attempt to send a file to an application server, a request to stream media, a request to print a document, and other network communications.

[0016] Further, each node in a PSM may describe an average delay and a distribution of delay. The average delay associated with each node of a PSM specifies an approximate amount of time before a load generating device performs the action associated with the node. This is not a strict time, but rather is a true average. The actual delay may be more or less than the average delay. For instance, if a node of the PSM has an average delay of 600 seconds, one of load generating devices 10 executing the PSM may elect to only wait 500 seconds before performing the action specified by the node.

[0017] The delay distribution describes how the distribution of the delay before performing the action varies. For instance, a node could have a delay distribution describing a Poisson distribution. Other example distributions include the Gaussian (normal) distribution, Zipfian distribution, binomial distribution, beta distribution, chi-square distribution, uniform distribution, Pareto distribution, geometric distribution, and other probability distributions. In this manner, load generating devices 22 may more accurately mimic the variability associated with user behavior.

[0018] Each directed edge of a PSM represents a transition from a first node of the PSM to a second node of the PSM. In some cases the transition may lead to a different node. In others, the transition may return to the same node of the PSM.

[0019] In addition, each directed edge is associated with a specific weight, such that the sum of weights of all directed edges from a first node equals one. In one embodiment, the weight represents the probability that a user performs an action associated with a second node, given the first node. For example, if a node has three outgoing edges A, B, and C, and edge A has weight 0.3, edge B has weigh 0.6, and edge C has weight 0.1, then there is a 30% chance that a transition occurs in accordance with edge A, a 60% chance that a transition occurs in accordance with edge B, and a 10% chance that a transition occurs in accordance with edge C.

[0020] Testing engineer 16 tailors each action, average delay, delay distribution, and edge weight to simulate behavior that is realistic for a user interacting with network system 8 when the network system is deployed in a non-testing environment. For example, testing engineer 16 may develop a PSM based on the determination that an average user has a 60% chance of next activating a particular service after successfully completing a PPP login. In addition, testing engineer 16 may determine that the average user might wait 120 seconds before activating that service. Testing engineer 16 may base the behavior model on empirically collected data. Analyzing usage logs from a large enterprise would be a convenient and unobtrusive method of gathering actual user behavior.

[0021] After testing engineer 16 has completed designing all of the behavior models (e.g., PSMs), testing engineer 16 may supply the behavior models to control server 4. Control server 4 may then compile each of the behavior models into a series of commands or scripts that load generating devices 10 can process.

[0022] In one embodiment, control server 4 supports a “start” command and a “stop” command. The “start” command initiates a simulation. A simulation may be defined by a simulation name, a number of users, and a behavior model. The “simulation name” of the simulation specifies a handle for the simulation that can be used later to stop the simulation and identify sets of results data. The “number of users” of the simulation allows testing engineer 16 to simulate the behavior of multiple concurrent network users by generating network communications based on the behavior model. For instance, if testing engineer 16 invoked the start command with 500,000 as the value of the “number of users” parameter, testing cluster 6 creates network communications in accordance with the supplied behavior model in a manner that simulates the behavior of 500,000 users. The “behavior model” of the simulation specifies the particular behavior model to be used for simulation of real-world user behavior described by testing cluster 6.

[0023] Each time testing engineer 16 invokes the “start” command, control server 4 sends a set of simulation instructions to one or more load generating devices 10 in testing cluster 6. The simulation instructions embody a simulation. In other words, the simulation instructions comprise a simulation name, a number of users, and compiled behavior model. Load generating devices 10 follow the simulation instructions to generate network communications on subject network system 8.

[0024] Testing engineer 16 may invoke the “start” command multiple times to execute multiple simulations. For example, testing engineer 16 may generate a second non-deterministic model of a behavior of a network user. Testing engineer 16 may then use the “start” command to generate network communications based on the second model to simulate the behavior of a network user concurrently with a first behavior model. Thus, testing engineer 16 could test the performance of subject network system 6 for 10,000 users using a behavior model describing a PPP log-in session while concurrently simulating 60,000 users using a behavior model describing video downloading behavior. Testing engineer 16 may write one or more automated scripts to invoke the “start” command multiple times with respect to various combinations of behavior models and other parameters to perform an overall test set.

[0025] When executing in accordance to one or more behavior models, load generating devices 10 in testing cluster 6 may each use thousands of network addresses, and hence load generating devices 10 may use the behavior model to simultaneously simulate the behavior of one or more users. This allows a single load generating device to simulate the effect of thousands of users using different machines. In this way, the load generating devices 10 execute the instructions to generate network communications that simulate the network user.

[0026] In some embodiments, load generating devices 10 record information useful in analyzing the functionality of network system 8. For instance, load generating devices 10 might record response network communications from network system 8 and the length of time it takes to receive the response network communications.

[0027] The “stop” command of control server 4 ends execution of a simulation and retrieves recorded data from load generating devices 10. In one embodiment, the “stop” command has one parameter, “simulation name,” which indicates a simulation to stop. After invoking the “stop” command, analysis module 18 retrieves testing information from load generating devices 10. Analysis module 18 and/or testing engineer 16 may analyze network communications from network system 8 to verify functionality of the network system. Testing engineer 16 may write customized scripts or invoke other software tools or agents in analysis module 18 to perform all or parts of this analysis.

[0028] Simulating patterns of user behavior in this manner may have one or more advantages. For instance, when generating network communications to simulate thousands or millions of users, the randomized delays in performing actions may create sudden increases and decreases in activity in a manner that more accurately represents real-world loads. Customization is another potential advantage of testing environment 2. For example, the techniques allow testing engineer 16 to adjust the delays, probabilities and general construction of a behavior model. This may better allow testing engineer 16 to model real-world user behavior. In addition, test engineer 16 may be able to better design network tests that conform to patterns of behavior expected by different classes of potential purchasers of the devices under test. For instance, if the potential purchaser is more interested in testing the functionality and scalability of router 12 than application servers 14, testing engineer 16 can use behavior models that are especially demanding on the router. Alternatively, if the potential customer is interested in testing the functionality and scalability of application servers 14, and router 12 is a load distribution router, testing engineer 16 can use behavior models to test the ability of application servers 14 to handle traffic that is distributed between application servers 14.

[0029] FIG. 2 is a block diagram illustrating an exemplary PSM 20. In this example, PSM 20 has four nodes. Each node is a different state of PSM 20. In particular, each node specifies an action, an average delay, and a delay distribution.

[0030] A first node 22 serves as the start node of PSM 20. The start node represents the initial state of PSM 20. For example, when load generating device 10A in testing cluster 6 starts executing PSM 20, load generating device 10A waits a duration based on the amount of time specified by node 22. Further, the duration may be based on a distribution for user deviation from the average time. In this example, load generating device 10A waits on average 600 seconds, varied in accordance with a defined Poisson delay distribution. After waiting the duration, load generating device 10A performs the action specified by node 22. As explained above, the action may cause load generating device 10 to send a network communication to network system 8. In this example, the action specified by node 22 is a PPP login.

[0031] After executing the action of node 22, load generating device 10A selects a directed edge based on a weight associated with the directed edge. In particular, load generating device 10A selects a directed edge that is a member of a set of directed edges having node 22 as the source node. As shown in FIG. 2, load generating device 10A may transition to one of three states: node 26, node 24, or node 28. There is a 0.1 probability (i.e., 10% chance) that load generating device 10A transfers to node 26, a 0.6 probability that load generating device 10A transfers to node 24, and a 0.3 probability that load generating 10A transitions to node 28. Note that the sum of the probabilities of the edges add to one: 0.1+0.6+0.3=1.0. After selecting an edge, load generating device 10A transitions to an end node of the directed edge.

[0032] If load generating device 10A transitions to node 24, load generating device 10A waits on average 1200 seconds and then outputs network communications to simulate the activate service action. For example, the activate service action could be a command to stream video to load generating device 10A. From node 24, there is a 0.7 probability that load generating device 10A transitions to node 26 and a 0.1 probability that load generating device 10A transfers to node 28. In addition, there is a 0.2 probability that load generating device 10A transfers back to node 24. In this case, load generating device 10A again waits on average 1200 seconds and then performs the activate service action.

[0033] If load generating device 10A transitions to node 26, load generating device 10A waits on average 3600 seconds before outputting network communications to simulate the deactivate service function. Node 26 differs from nodes 22 and 24 because node 26 uses the Gaussian or normal distribution function instead of the Poisson distribution. Testing engineer 16 may have any number of reasons to use one distribution as opposed to another. Node 26 also demonstrates that PSM 20 is cyclic. That is, load generating device 10A can transition back to node 24 even if load generating device 10A has previously been in node 24. From node 26, there is a 0.2 probability that load generating device 10A transitions to node 24. In addition, there is a 0.1 probability that load generating device 10A transitions back to node 26 and a 0.7 probability that load generating device 10A transfers to node 28.

[0034] Node 28 is a terminal state. That is, node 28 has no outgoing edges. Thus after load generating device 10A waits on average 1200 seconds and performs the PPP logout action, PSM 20 is complete. In the context of testing environment 2, testing engineer 16 may instruct PSM 20 to start over. That is, there may be an additional outgoing edge proceeding from node 28 to node 22 with a probability of 1.

[0035] Other PSMs may be substantially more complex than PSM 20. For instance, if subject network system 8 is an electronic commerce server, a single PSM may have hundreds of states that encompass all of the activities that a customer of the server may perform. In addition, the actions associated with each node may be very complex. For example, an action at one node may be to start a Java Applet and send back information through the Java Applet.

[0036] FIG. 3 is a flowchart illustrating an example operation of testing environment 2 in accordance with the principles of this invention. A testing process 30 begins when testing engineer 16 generates one or more non-deterministic behavior models of user behavior (32). Generating behavior models may entail creating one or more PSMs that model user behavior. For instance, the process of identifying nodes and assigning delays, distributions, and edge weights is part of generating behavior models of user behavior. After generating the behavior models, testing engineer 16 loads the behavior models into control server 4 (34). In loading the behavior models, control server 4 compiles the behavior models into a series of commands or scripts that can be processed by load generating devices 10 in testing cluster 6 (36).

[0037] Next, testing engineer 16 starts a simulation of user behaviors (38). Testing engineer 16 may accomplish this by issuing the “start” command to control server 4 for a behavior models. For example, testing engineer 16 may send a command directing execution of the instructions and specifying a number of users to simulate. Testing engineer 16 may issue the “start” command multiple times to execute multiple simulations concurrently. Starting a simulation causes control server 4 to distribute simulation instructions to testing cluster 6 (40). After the simulation instructions are distributed, load generating devices 10 in testing cluster 6 run the simulation (42). That is, load generating devices 10 executes a behavior model contained in the simulation instructions to simulate the number of concurrent users specified by the simulation instructions.

[0038] After running the simulation for a specified period, testing engineer 16 stops the simulation or the simulation may automatically conclude (44). For example, testing engineer 16 or an automated software agent may issue a “stop” command to control server 4 for each simulation previously started. Stopping the simulation causes load generating devices 10 in testing cluster 6 to stop executing the behavior models and return result data to control server 4 (46). After retrieving the result data, analysis module 18 and/or testing engineer 16 may analyze the result data (48). For example, load generating devices 10 may collect actual network communications sent from network system 8 in response to network communications generated based on the behavior model. Analysis module 18 may then analyze the functionality of network system 8 by comparing the actual network communications from the network system with expected network communications from the network system. In another example, load generating devices 10 collect end user perceived response times to network requests from network system 8. Analysis module 18 may then plot cumulative distributions of the end user perceived response times. Analysis module 18 may subsequently use the cumulative distributions to analyze performance of network system 8. For instance, analysis module 18 may determine what fraction of the network requests network system 8 answered within a given time period.

[0039] Various embodiments of the invention have been described. These and other embodiments are within the scope of the following claims.