Distributed Memory Programming

9.6 Models

Simply counting the number of bytes of traffic over a certain interval for a running application does indeed give you a numeric value for communication rate ... after you've got it running and taking up communication-bandwidth. But what can you do before you have it running to estimate the kind of response your application is likely to experience?

Various models or estimates of communication behavior (called cost because, as has been harped on so often in this text, it costs to communicate) have been developed; they differ mostly in the number of parameters they utilize, directly related to the level of scrutiny the entire communications mechanism is subjected to. For your edification, we present two of those models, one from the outfield of the estimation ballpark, as it were, the other from, say, 2nd-base ... if you want to see something from the catcher's point-of-view, we can certainly direct you to any number of very learned papers and dissertations, full of abstract terminology and formulas, but, realistically speaking, adding only decimal places to the values obtainable from the models you see here:

Simplest

Let's get our feet wet with the most general expression of communication cost; we'll present the formula, define the terms, and then give a quick explanation of its meaning:

  • C = L + M / B

    C
    communication time (seconds)

    This is what we're after, after all: how much time can we expect to spend doing communication?

    L
    latency (seconds)

    This term is tossed around a great deal in network communications; here's a quick overview of some important points:

    • Time to send a zero-length message from one node to another

      All we're trying to measure, here, is the actual cost of the setup, nothing related to any real message, just "what does the structure cost: the buffer management, the network interface, the network itself...?", and we make sure that the message doesn't have any effect by not sending any.

    • Some factors which affect latency:

      There are a number of things working together that add up to "why does it take so long to get from here to there":

      • Operating system

        The OS has its own overhead for this operation: allocation of buffers, initialization of the network interface, setting up intra-node communication paths between the application and the network device, locking files, etc. After all, you're using shared resources, and the OS is tasked with making sure that they're used properly and without hinderance.

      • Context switching

        Under most operating systems, utilization of network interfaces is a privileged activity: you-the-common-user are not allowed to just stroll up and start punching buttons and throwing bytes around, that's what device drivers are for, and device drivers are not intended for unrestricted use by the common user. So, in order to get your message from your application out onto the wire, it has to be passed between what's known as user-space, which is where you do your work, and kernel-space, which is where the operating system does its work. This involves a very complex and time-consuming amount of effort: instruction stacks have to be saved and replaced, program counters have to be positioned, program segments have to be brought in from virtual memory or from disk ... context switching is not something you want to do very often, and good operating systems and communications libraries try to make sure that it is done as little as possible.

      • Layers of communication software

        Communications is not simply a matter of shouting really loudly down a hollow tube; in fact, the International Standards Organization (ISO) has established a 7-tiered structure for network communications, and only one of those layers has anything at all to do with the physical medium (wire, fiber-optic, cotton-string, etc.). Each of those layers has a whole suite of software to bring it into existence, and your message is going to traverse all of those layers -- twice (except for the lowest layer), once going out, and once coming in.

    B
    bandwidth (bytes/sec)

    How wide is the pipe?", or, "how much traffic can you get through the Lincoln Tunnel, at rush-hour?"

    • Maximum rate of information transfer

      Assuming no blockages on either input (the producers are all producing at top capacity) or output (the consumers are all consuming at top capacity), this is how many bytes will flow past a given point in the network in any given second.

    • Some factors which affect bandwidth:

      But, of course, there are blockages, or, more specifically, there are things that act to keep effective bandwidth (not the theoretical figure, but the actually experienced one) from reaching or staying at the rated-maximum:

      • Communication link speeds

        Networks are not constructed from one unbroken wire stretching from one machine to another (not generally, that is), but, instead, are made up of different links, usually based on segments betwwen routers, hosts, or signal-enhancers, and all of those links can have different transmission characteristics; in fact, it would be safe to say that no network is faster than its slowest link.

      • Network topology

        The logical layout of the network has a tremendous effect on end-to-end performance, most simply in terms of "how many hosts/routers/bridges/etc. does my message have to go through in order to get where it's going?" The more network nodes between the sending- and receiving-ends, the more times each byte has to be handled, and the longer everything is going to take.

      • Moving data between buffers

        Buffering happens multiple times to data, at multiple locations, and every time it does, it adds a very significant amount of time to the operation. At a minimum, you can expect that your message will have to be buffered once on your end (moving from user-space to kernel-space for transmission), and once on the other end (exactly the reverse), but it can also happen any number of times in the middle, most commonly when moving between links of different capacities when the message has to be split and sent on in smaller chunks or segments (this is called "packet segmentation").

      • Other outstanding message traffic

        Your message will almost certainly not be the only one taking up space on the network, and the more peers it has to keep it company, the more likely they all will be to experience network congestion (think of the Lincoln Tunnel at rush hour ... in fact, think of the Lincoln Tunnel collapsing in the middle, and not being re-opened for weeks or months -- that's roughly analogous to what can happen when major circuits get overloaded, or a farmer with a backhoe digs a furrow where he shouldn't have).

    M
    message length (bytes)

    Don't forget to add on all of the bytes taken up by the message header (and trailer, in many cases): the sender's address, the receivers address, checksums, priority information, segmentation or sequencing data, routing information, Mother's maiden name, ...

So, finally, we put all (3) of the pieces together and ... well, wait, that's not really fair: there are only 3 terms (latency, message-length and bandwidth), but we've seen how each one of those terms is, in fact, an estimation of the effects of a much larger number of factors, each set of which is probably mutually-interacting (meaning that you can't simply add a bunch of representative numbers together in order to take them into account), the whole mess taken together being no better, really, than a more-or-less educated guess.

Still, as guesses go, this one does put us into the right ballpark, and does carry a fair amount of intuitive weight: the total amount of time spent communicating is equal to the amount of time it takes to just do the mechanics (latency) plus the fraction of the pipe it fills up (message-length divided by maximum bandwidth).