How can I model this usage scenario mathematically?

Question

I want to create a fairly simple mathematical model that describes usage patterns and performance trade-offs in a system.

The system behaves as follows:

• clients periodically issue multi-cast packets to a network of hosts
• any host that receives the packet, responds with a unicast answer directly
• the initiating host caches the responses for some given time period, then discards them
• if the cache is full the next time a request is required, data is pulled from the cache not the network
• packets are of a fixed size and always contain the same information
• hosts are symmetic - any host can issue a request and respond to requests

I want to produce some simple mathematical models (and plotted X/Y graphs) that describe the trade-offs available given some changes to the above system:

• What happens where you vary the amount of time a host caches responses? How much data does this save? How many calls to the network do you avoid? (clearly depends on activity)
• Suppose responses are also multi-cast, and any host that overhears another client's request can cache all the responses it hears - thereby saving itself potentially making a network request - how would this affect the overall state of the system?
• Now, this one gets a bit more complicated - each request-response cycle alters the state of one other host in the network, so the more activity the quicker caches become invalid. How do I model the trade off between the number of hosts, the rate of activity, the "dirtyness" of the caches (assuming hosts listen in to other's responses) and how this changes with cache validity period? Not sure where to begin.

I don't really know what sort of mathematical model I need, or how I construct it. Clearly it's easier to just vary two parameters, but particularly with the last one, I've got maybe four variables changing that I want to explore.

Help and advice appreciated.

Answer 1

I think you want a Petri net with transition guards and a global clock. (Other formalisms would also work, but I'm going with this one because it relates to the discussion on your other question.)

Draw a graph -- vertices and directed edges -- where the vertices are your nodes, and the edges are the communication channels from one node to another. It sounds as though there's an edge between every node, if all nodes are capable of broadcast, but perhaps I'm misreading. In any case, the important thing is that you decorate each edge with a rule or set of rules, and the edge only "opens" when the rules are satisfied. (These rules are called guard expressions.)

For example, to make "vary the amount of time a host caches responses" rigorous, you could make the rule for an edge, "if I receive a message, I wait 3 seconds according to the global clock before I pass it on." I don't understand your dirty-cache issue well enough to offer anything yet, but I think the conceptual point you need first is this notion of enabling or disabling a transition according to the rules of the system.

Answer 2

You can try a Jackson network, which is well-studied in queueing theory. Jackson networks provide a formalism for modeling systems of servers (ie, hosts) that process messages/items at varying rates and pass messages between one another, and they can handle notions like fixed-capacity caches and linked processing rates.

Your analysis will be easier than what's usually needed for these models because you're considering a constant processing speed.

I'll also second Aaron's answer about looking at Petri nets, which are another useful formalism that can represent what you're after. What you want isn't just the formalism by itself, which is nothing more than a way to logically express your requirements, but the ability to leverage existing analytical results about the performance of these systems from the Petri net / Jackson network literature. After you've figured out how to model your system as one of these networks, you can try and use known properties of these networks to determine answers to your questions. With Jackson networks, you usually end up with results like, "as hosts become more active, and the cache size drops, the expected processing time changes by X".

This question would be a wonderful candidate for crossposting on the Operations Research Exchange, since we're in the territory of stochastic and queueing models.

Answer 3

I have coded exactly such a system in the past. Are you studying a peer to peer content delivery network by any chance?

I don't believe it is easy to create an analytical solution to this

My study was based on simulation, which was around 2k lines of code built on top of a simulation library. The simulation would be more useful too, because it can be adjusted easily to different parameters, whereas developing a general mathematical model with a lot of variables wouldn't be so easy.