High level executable network abstract machine

• US 7,149,678 B2
• Filed: 03/28/2002
• Issued: 12/12/2006
• Est. Priority Date: 03/28/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Veanes, Margus, Gurevich, Yuri, Glässer, Uwe
• Primary Examiner(s): PHAN, THAI Q
• Application Number:
  US10/112,319
• Publication Number:
  US 20030191797A1
• Time in Patent Office: 1,720 Days
• Field of Search: 703/2, 703/22, 709/223, 709/201, 709/202, 709/232, 709/239, 700/49, 700/97
• US Class Current: 703/22
• CPC Class Codes: B33Y 50/00 Data acquisition or data processing for additive manufacturing
• CPC Class Codes: G06F 2111/04 Constraint-based CAD
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network

Abstract

A generic algorithm for simulating communications software in the network environment, based on the model of plural Abstract State Machines (ASMs) is discussed. Other properties and behaviors can supplement the generic case, for example, network topology, delaying behaviors, message transport reliability, and message priority. Plural executing agents, each a sequential abstract state machine, are combined to simulate the behavior of a dynamic network environment. Agent and message behavior is altered based on the proposed or selected network under simulation. The desired behaviors and constraints are coded, compiled, and executed using an executable abstract state machine language.

Claims

1. A system for simulating network behavior on a computer comprising:

plural executable abstract state machines each programmed to simulate an agents behavior according to simulated network conditions under test;

at least some of said simulated agents create messages, plural of the created messages comprising at least four specific properties consisting of;

message size, message type, message time-to-live, message sender, message receiver and message payload;

at least some of said simulated agents deliver messages; and

the simulated network behavior is represented by the aggregate state changes created by the individual simulated agents as the plural created messages pass through a dynamic simulated network topology according to the at least four specific properties.

2. A computerized system for simulating network behavior comprising:

an abstract state machine language compiler for compiling a design specification into plural executable abstract state machine modules;

an endpoint agent abstract state machine module operational to create plural simulated messages, each such message with a message destination property and to place the plural messages in a message box; and

a delivery agent abstract state machine module operational to choose a message from a message box, to determine a message destination property for the chosen message, to determine a message disposition based on the message destination property in relation to a network topology, and to dispose of the chosen message;

wherein two or more of the created simulated messages comprise at least three specific network simulation properties consisting of;

message size, message type, message time-to-live, message sender and message payload.

3. The system of claim 2 further comprising:

an interleaving module that selects a next endpoint agent or delivery agent for execution wherein the selection is made non-deterministically.

4. The system of claim 2 wherein the delivery agent models a router'"'"'s behavior using data structures comprising an address table and a routing table.

5. The system of claim 2 wherein the delivery agent models a subnet'"'"'s behavior wherein the subnet'"'"'s behavior comprises at least a TCP subnet behavior and having tables for translating multicast addresses into multiple unicast addresses and for routing unicast messages.

6. The system of claim 2, further comprising:

a mapping function for mapping a message to an adjacent endpoint agent; and

a mapping function for mapping a message to an adjacent delivery agent according to a message delivery protocol comprising a TCP and UPD protocol.

7. In a computer system, a method of simulating the behavior of interacting network components, where behaviors of a network'"'"'s components are described in a network design specification, the method comprising:

translating the network design specification into an executable specification comprising plural executable abstract state machines comprising plural delivery agents and plural endpoint agents;

creating by a first endpoint agent plural simulated messages and placing the messages in a message box associated with a first delivery agent and wherein two or more of the plural created simulated messages comprise at least four specific properties consisting of;

message size, message type, message time-to-live, message sender, message destination, and message payload;

choosing by the first delivery agent from the message box, a simulated message;

determining a delivery destination for the simulated message by the first

delivery agent, said delivery destination determined using a mapping function including a network topology specific to the first delivery agent; and

forwarding by the first delivery agent the chosen message to a message box

associated with an agent determined with the mapping function;

whereby aggregate behavior of a dynamic network is modeled as plural messages pass through a network topology and wherein metrics comprising results of a proposed network are provided at the end of a network simulation.

8. The method of claim 7, wherein forwarding further comprises:

determining that the message has a broadcast property and forwarding the message to plural message boxes.

9. The method of claim 7, wherein choosing further comprises:

choosing the simulated message from amongst other simulated messages in the message box, based on a priority property assigned to the chosen message.

10. The method of claim 7, wherein the chosen message is forwarded to the message box of an adjacent local endpoint agent identifiable in an address table.

11. The method of claim 7, wherein the chosen message is forwarded to the message box of an adjacent delivery agent determined in a routing table.

12. The method of claim 7, wherein forwarding further comprises:

determining to forward the chosen message to the message box associated with an adjacent delivery agent based on the destination property value associated with the chosen message.

13. A computer-readable medium having thereon a computer-executable network communications simulation program comprising:

an endpoint agent abstract state machine module for creating and placing simulated messages in a message box wherein three or more of the simulated messages comprise at least four specific properties consisting of;

message size, message type, message time-to-live, message sender, message destination, and message payload; and

a delivery agent abstract state machine module for choosing messages from a message box and for determining the disposition of the chosen message based on a destination property of the chosen message and a network topology represented by a mapping function available to the delivery agent;

wherein, the mapping function may direct the message disposition to a message box of a delivery agent or an endpoint agent.

14. The computer-readable medium of claim 13, wherein the mapping function is an address table for mapping addresses of multicast groups to addresses of related group members.

15. The computer-readable medium of claim 13, wherein the mapping function is a routing table mapping non-local addresses to neighboring delivery agents.

16. The computer-readable medium of claim 13, wherein a network identification number is associated with the delivery agent and is compared to a message destination value associated with a message in order to determine that the message should be delivered to a local endpoint agent.

17. The computer-readable medium of claim 13, wherein the disposition of messages further comprises:

discarding a message if the message has passed through a maximum allowable number of delivery agents.

18. The computer-readable medium of claim 13, wherein the choosing of messages further comprises:

choosing a message based on a message type value assigned to the message.

19. The computer-readable medium of claim 13, wherein the choosing of messages further comprises:

choosing a message based on a message delay value assigned to the message.

20. The computer-readable medium of claim 13, wherein the disposition of messages further comprises:

determining whether the chosen message has a messages delivery value of broadcast, multicast, or point-to-point.

21. The computer-readable medium of claim 13, wherein the module creating and placing messages in a message box, generates messages with varied bursts of intensity.

22. The computer-readable medium of claim 13, wherein the module creating messages assigns a message property indicating a message delivery reliability.

23. The computer-readable medium of claim 13, further comprising:

a module for generating a graphical representation of state changes for plural endpoint agents and delivery agents.