4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just a bit of feedback: assuming that this is the same question as your recent directed-acyclic-network before, it seems much clearer now. --- How's your linear algebra? $\endgroup$ – Niel de Beaudrap Sep 11 '10 at 12:48
  • $\begingroup$ Yes, all connected to the same system. Linear Algebra, rusty, but it wasn't difficult then, so I'm sure I'd have no problem now. $\endgroup$ – flesh Sep 11 '10 at 13:07
  • 2
    $\begingroup$ If you are happy with the current choice of tags, please update your post and remove the note regarding bad tags. $\endgroup$ – Jukka Suomela Sep 12 '10 at 9:20
  • $\begingroup$ On this site, most people will read "graph" as "structure with vertices and edges", not as "drawing of one-variable function in Euclidean 2-space". You might want to clarify. $\endgroup$ – András Salamon Sep 13 '10 at 11:02
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks Aaron. Though perhaps my other question has confused matters somewhat. The previous node formalisation question describes a process that happens on one machine only. This question is purely about optimisation of network interactions between machines and is completely unrelated to the previous. With this one, the graph I'm talking about has X and Y axes. I was looking for some algebraic or calculus type techniques - purely mathematical models - that will allow me to describe how a system changes when I vary some of the parameters invloved. Does that make a bit more sense? $\endgroup$ – flesh Sep 11 '10 at 16:05
4
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, that's the kind of thing I'm looking at. If I had the time I would write a simulation. But I am sure there must be a mathematical approach to this, rather than a test and observe, though that would be useful.. $\endgroup$ – flesh Sep 12 '10 at 8:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.