Two of my hobbies are ballroom dancing and collecting motion picture and television soundtracks. I've taken lessons on the former for years, resulting in more enthusiasm than skill on my part. As for the latter, I have around 2000 CDs and albums cluttering up the palatial Overclock estate, along with all the computers, books, firearms, and notes on conspiracy theories.
Not too long ago, I was cruising around on Amazon.com looking for any classical music CDs that featured the tango Por Una Cabeza, which was featured in the movie True Lies. Thirty seconds of Googling for "true lies tango" had gotten me the title. When I typed that into Amazon's search engine, I got back several classical music CDs, and the soundtrack to True Lies.
On the surface, this might not seem unusual. Except that Por Una Cabeza does not appear on the soundtrack by Brad Fiedel. I knew this already because I owned soundtrack CD. There was absolutely no reference to the tango on the CD, in the liner notes, etc.
How did Amazon.com know that that tango was used in the movie? I don't think it did. I think the search engine merely noticed that people who searched for "Por Una Cabeza" also purchased the soundtrack to True Lies. So in a marketing move that seemed almost omniscient, and without really knowing why, it suggested that CD too. This is not the first time Amazon.com has startled me. (Actually, it startles me every month when my Visa bill arrives. One-click-ordering maybe works a little too well.)
This is a great example of what James Surowiecki talks about in his book The Wisdom of Crowds, where you leverage the combined knowledge of a very large sample of people, including both experts and amateurs. While a particular individual's knowledge may not add up to much, you get enough data points, start doing some correlations, or apply it all in a market-based system, and suddenly you not only have a lot of data, but some real information as well.
If you want some examples of the really counter-intuitive results you may get when you start looking at statistical correlations in large data sets, see Steven Levitt and Stephen Dubner's book Freakonomics. The controversial result that is mentioned in all the reviews is that the reduction in the crime rate correlates to the legalization of abortion. Unwanted babies that are not born do not grow up to become criminals. But this is merely one among many compelling chapters.
Peter Morville is a librarian, a librarian's librarian. He's the kind of librarian that might be (and probably has been) hired as a consultant by the Library of Congress or maybe Google. Morville invented the field of information architecture. His book Ambient Findability is about life in a world in which virtually any fact might be at your fingertips, if you only knew where to look for it, how to ask for it, and if it were organized to maximize its findability.
One of the topics Morville covers is the difference between organizing information in formal taxonomies versus the emerging folksonomies. Formal taxonomies are very expensive to create because they are labor intensive, but you are leveraging the wisdom, experience, and knowledge of highly trained experts in a field. The Library of Congress system of classifying books is a formal taxonomy. All those Latin words you had to learn in high-school biology were probably part of a formal taxonomy as well. Folksonomies may be very expensive to create as well, but the cost is widely distributed and the labor frequently donated, but you're leveraging a lot of people whose credentials are more or less unknown. Folksonomies abound on the web, ranging from del.icio.us (which is completely driven by users adding their own bookmarks categorized by tags that they themselves apply), to SlashDot (whose value-add is its editorial moderation as applied to the firehose of contributed news items), to the kind of information organization done by Amazon.com (in which software extracts patterns of behavior from a huge sample size with little or no human intervention).
It is this difference in economics between the formal taxonomy and the folksonomy that killed the original Yahoo, which the old coots in the audience may recall was once not a search engine but a formal taxonomy of web sites. It is also what made a star of Google, which is likely to become the emerging artificial intelligence that eventually conquers the planet.
I loved Malcolm Gladwell's book The Tipping Point, which applied theories of how an outbreak of disease becomes an epidemic to everything from fashion to open source software development. His more recent book Blink is about how sometimes snap judgements are more accurate than informed opinions formed by long studious research. The weakness in Blink is that Gladwell does not stress nearly enough that in all of his case studies of amazingly successful snap judgements, they were all made by the kinds of people you would want drawing up your formal taxonomies: experts in the field with decades of experience, whose brains contain finely honed neural networks capable of delivering useful snap judgements.
When the software refactoring folks talk about code smells, this is exactly what they are talking about: the sensation you get when you look at a piece of code, and something in the back of your mind tells you this looks funny. This is not an intuition that occurs to the average joe off the street. It is the result of many many hours spent finding that frackin' bug, and swearing, as God is my witness, I will never make this mistake again! There is nothing like a weekend spent at work to train your neural network to be more careful next time.
As useful as folksonomies obviously are, we need to keep a few experts around too for the value-add that their neural networks bring to the table. On the flip side, Surowiecki would tell us that it is just as bad having nothing but experts. True wisdom comes from having a wealth of experience, a breath of knowledge, and a diversity of opinions.
Sources
Malcolm Gladwell, Blink, Little, Brown, and Company, 2005
Malcolm Gladwell, The Tipping Point, Little, Brown, and Company, 2002
Steven Levitt, Stephen Dubner, Freakonomics, William Morrow, 2006
Peter Morville, Ambient Findability, O'Reilly, 2005
James Surowiecki, The Wisdom of Crowds, Doubleday, 2004
Sunday, January 07, 2007
Wednesday, January 03, 2007
Version Control as a Victim of the Times
Yesterday I spent a rather pleasant and relatively painless afternoon installing Subversion on one of Digital Aggregates' Linux servers. Subversion is the latest in a long line of version control systems, both proprietary and open source, to become popular. For me, version control has been one long strange trip which began with proprietary tools in the 1970s, adopting SCCS in the 1980s, moving to RCS, ClearCase, and CVS, and finally arriving at Subversion. We still keep our legacy C/C++ code in a CVS repository, but will keep at least all of our Java code in Subversion, and will probably use it to host future development of any kind.
I can't install, use, and manage a source code control system without knowing at least a little but about how it works under the hood. Looking back on my varied and hard-won experience in information technology and product development, I have come to the following conclusion: from strictly a user point of view, all of the version control systems I've used are pretty much the same. Yes, I can already hear the mob marching on the castle with flaming torches. But the fact is, there are a handful of basic things you always have to do when juggling multiple versions of digital stuff, and every version control system has to implement, with more or less success, the user's Platonic ideal of what such a system should do. Where they really differ is in how they are implemented, and what ancillary features they offer that take advantage of new enabling technologies.
Back in May I wrote about how architecture and design was driven not just by Moore's Law, which, broadly speaking, addresses just CPU horsepower, but also by similar exponential growth curves for things like network bandwidth, network connectivity, secondary storage density, and even bus width and speed. I argued that since these metrics were growing on very different curves, the architecture of today might not be the architecture of tomorrow, because what it took to design a balanced system would be so different in just a few years.
Version control systems have been victims of these different curves in a big way. Looking at how SCCS works versus how Subversion works under the hood, you can tell that the authors of both were looking at very different design points: "storage is expensive" versus "storage is cheap", or "development is economical because it is centralized" versus "development is expensive because it is distributed", "legacy code is relatively stable" versus "refactoring is a way of life" to name just a few. The legacy version control systems have not been able to keep up with the changing times.
And so, I am sure, in just a few years I will once again be installing and learning to manage and use yet another version control system. It seems unlikely, from a historical perspective, that Subversion will be the end-all and be-all.
The King is dead! Long live the King!
Sources
Ben Collins-Sussman et al., Version Control with Subversion, Subversion 1.2
Chip Overclock, "It's Not Just About Moore's Law", May 2006
I can't install, use, and manage a source code control system without knowing at least a little but about how it works under the hood. Looking back on my varied and hard-won experience in information technology and product development, I have come to the following conclusion: from strictly a user point of view, all of the version control systems I've used are pretty much the same. Yes, I can already hear the mob marching on the castle with flaming torches. But the fact is, there are a handful of basic things you always have to do when juggling multiple versions of digital stuff, and every version control system has to implement, with more or less success, the user's Platonic ideal of what such a system should do. Where they really differ is in how they are implemented, and what ancillary features they offer that take advantage of new enabling technologies.
Back in May I wrote about how architecture and design was driven not just by Moore's Law, which, broadly speaking, addresses just CPU horsepower, but also by similar exponential growth curves for things like network bandwidth, network connectivity, secondary storage density, and even bus width and speed. I argued that since these metrics were growing on very different curves, the architecture of today might not be the architecture of tomorrow, because what it took to design a balanced system would be so different in just a few years.
Version control systems have been victims of these different curves in a big way. Looking at how SCCS works versus how Subversion works under the hood, you can tell that the authors of both were looking at very different design points: "storage is expensive" versus "storage is cheap", or "development is economical because it is centralized" versus "development is expensive because it is distributed", "legacy code is relatively stable" versus "refactoring is a way of life" to name just a few. The legacy version control systems have not been able to keep up with the changing times.
And so, I am sure, in just a few years I will once again be installing and learning to manage and use yet another version control system. It seems unlikely, from a historical perspective, that Subversion will be the end-all and be-all.
The King is dead! Long live the King!
Sources
Ben Collins-Sussman et al., Version Control with Subversion, Subversion 1.2
Chip Overclock, "It's Not Just About Moore's Law", May 2006
Monday, December 25, 2006
Traffic Management
Traffic management turns out to be no less important in real-time systems than it is in your daily rush hour commute, in the network to which your telephone (no matter what kind it is) is connected, or even in the plumbing from your toilet to the sewer system. Freeways are engineered assuming that not everyone will try to get on them at the same time, and busier entrance ramps meter traffic with timed stop lights. Telephone systems assume that not everyone will go off hook simultaneously. And if you want to play a prank, try flushing all the toilets in your school or office building simultaneously.
Actually, don't. Even your sewer system is based on some stochastic assumptions, and when those assumptions are violated, congestion occurs. In the case of toilets, I think you know what kind of congestion I mean.
Even in relatively simple messaging systems involving a single process or a single Java virtual machine, shared resources can be temporarily exhausted if many components try to firehose messages at each other with no feedback mechanism to affect some kind of rate control. At best, performance slows down for a spell until things sort themselves out. At worst, buffer pools run dry, the heap is exhausted, and the entire system may even deadlock. This is a well known failure mode in real-time systems, yet I routinely see developers writing code that assumes that they can fire away messages as quickly and as often as possible with little or no regard as to whether the recepient is in a position to receive them.
There are a lot of mechanisms used in real-time systems that can control how quickly a message producer may send a message so as to not overwhelm the message consumer that receives it. (It's important to understand that producer and consumer are roles played by communicating applications for the duration of a single message exchange. An application may and typically will act as both a producer and a consumer.) Below are brief descriptions of some of the traffic management mechanisms I've encountered, from the simplest to the most complex.
XON/XOFF
XON/XOFF is a form of traffic management used for flow control that will be familiar to anyone who remembers ASCII terminals. XON is the ASCII character produced by typing control-Q. XOFF is a control-S. The X is a common abbreviation for "trans" as in "transmit". When the consumer's buffer is full (or nearly so) it sends an XOFF to the producer, who suspends sending until it receives an XON. XON/XOFF is probably the most widely used traffic management mechanism on the planet by virtue of it being implemented in nearly every RS-232 serial device in existence.
The downside of XON/XOFF is that it doesn't scale well with latency and bandwidth. Just to make the problem obvious, let's assume that your producer and consumer are using a 155 megabit per second (OC-3) communication channel over a geosynchronous satellite link. Data transmitted via geosynchronous satellites have a round-trip time (RTT) of about half a second just due to the speed of light; it takes a quarter of a second to get up to the satellite, another quarter of a second to get down again.
By the time the consumer sends an XOFF to the producer, the producer operating at full channel speed will already have sent over thirty-eight megabits of data that is just travelling along the radio signal up to the satellite and back down to earth, and will send another thirty-eight megabits in the time it takes the XOFF to travel from the consumer to the producer over that same channel.
To use a simple mechanism like XON/XOFF, the consumer has to be able send the XOFF to the producer while it still has seventy-seven megabits of slack in its input buffer in order to receive all the data that is in transit, or will be in transit, before the producer can shut off.
ACK/NAK
ACKnowledge and Negative AcKnowledge is probably the most straightforward traffic management mechanism. The producer is blocked upon sending a message until the consumer either acknowledges or fails to acknowledge receiving the message. It reliably prevents the producer from overwhelming the consumer.
Its biggest downside is performance. Assume the worst case where the producer sends one bit of data over that same satellite link, then waits for the acknowledgement from the consumer. It takes the one bit of data a quarter second to go from the producer to the consumer. Ignoring any processing latency, it takes the acknowledgement another quarter of a second to go from the consumer to the producer. It took a half-second to transmit a bit from producer to consumer before a second bit could be sent, so your 155Mb/s channel has an effective bandwidth of two bits per second. This is why communications channels are more efficient with larger packet sizes.
Suppose the producer instead sends a megabit before it waits for a reply. The first bit of that megabit still takes a quarter of a second to get from the producer to the consumer, and the last bit takes more than six milliseconds at 155Mb/s. Then the acknowledgment takes another quarter of a second to go from the consumer back to the producer. Your channel now has an effective bandwidth of just under two megabits per second. You are still only utilizing a little over one percent of your channel.
What is the magic number for packet size? With a simple protocol like ACK/NAK, there is no magic number. No matter how many bits you send before turning the channel around, you are still wasting bandwidth when you stop transmitting and wait for an acknowledgement.
The ACK/NAK pattern shows up more often than you might think, even if your application isn't using a communications network at all. Synchronous message passing, where the producer blocks waiting for the consumer to receive the message, is a form of the ACK/NAK pattern. Synchronous message passing does not scale well as the complexity of the application grows, yet it is very common in web services or in any remote procedure call (RPC) mechanism like DCE, Corba, or Axis. Applications may unwittingly make requests concurrently to each other, blocking waiting for an acknowledgement that will never come because the two ends are now deadlocked waiting for the other end.
Synchronous message passing can also be a subtle form of priority inversion. While an application acting as a producer is blocked waiting for an acknowledgement from its consumer, other perhaps higher priority applications are blocked trying to send messages to the blocked application in its role as a consumer.
Windowing and Credit
To use the full capacity of your data channel, you would like to keep it full all the time. To do that, the producer has to be able to put enough new data in the channel to keep it full while an acknowledgement for prior data travels from the consumer. Communications protocols handle this by implementing a windowing or credit mechanism.
A window is a fixed amount of data that may be outstanding at any one time, as yet unacknowledged by the consumer. The producer is allowed to send this much data before being forced to wait for an acknowledgement. The producer guarantees that it has at least this much buffer space so that it can save the data it has already sent, in case it receives a negative acknowledgement from the consumer and has to send it again. Examples of windowing protocols are ISDN's Link Access Protocol for the D-Channel (LAP-D) which is used for signaling in non-IP digital telephony, and IP's Transmission Control Protocol (TCP). The producer and consumer may agree on a window size as part of their initial connection setup, or the window size may be fixed as part of the protocol itself.
A credit is the amount of free buffer space in the consumer signalled to the producer as part of an acknowledgement. This feedback mechanism lets the producer know how much more data it is allowed to send before having to stop and wait for more credit. The consumer guarantees that it has buffer space at least as large as the credit it sends. Because a consumer may be receiving messages from more than one producer into the same buffer space, the credit that a producer sees may bear little relation to the amount of data it has actually sent to the consumer. TCP/IP also uses a credit mechanism.
The optimal window or initial credit size is the bandwidth-delay product. The bandwidth-delay product of our satellite link is the 155 megabits per second bandwidth multiplied by the half second RTT, or more than nine megabytes. Although most communication channels don't suffer the RTT of a geosynchronous satellite link, many, such as gigabit Ethernet, have substantially higher bandwidth, still yielding a large bandwidth-delay product. To make effective use of channels with high bandwidth or high RTT (or both), both the producer and the consumer require large amounts of memory for buffering outgoing and incoming data. (Think what implications there might be regarding the reliability of your communications network when you have a high bandwidth-delay product. In an unreliable network, the producer may well spend most of its time and network bandwidth retransmitting a huge amount of buffered data.)
The windowing and credit patterns also show up more often than you would think. They are both a form of asynchronous message passing in which the a limit is placed on how far ahead a producer may get ahead of a consumer before being blocked waiting for an acknowledgement. Allowing applications to use unfettered asynchronous message passing does not scale well as load increases. Resources in the underlying message passing mechanism can be quickly exhausted by an enthusiastic producer with a slow witted consumer. This can lead to a deadlock of the entire system.
Traffic Shaping and Policing
All of the flow control mechanisms discussed so far require consent between the producer and the consumer. Because they all involve temporarily pausing the producer, they also introduce jitter into the data stream. Jitter is variation in the inter-arrival time (IAT) of successive packets in the data stream.
Jitter isn't generally a problem for data transfer using applications like FTP. It can be inconvenient when using interactive applications like TELNET. But it wreaks havoc with data streams that have real-time constraints like audio or video streams or VOIP. Jittered packets in real-time streams may arrive too early for play back and have to be buffered, or too late and have to be discarded completely. (What the audio or video player or VOIP telephone may play back in place of the discarded packet is an interesting problem left as an exercise to the reader.)
Technologies like Asynchronous Transfer Mode (ATM) impose traffic contracts on individual data streams. A traffic contract is a formal description of the bandwidth and burstiness characteristics of the data stream plus any real-time contraints it may have regarding jitter. ATM devices police traffic by marking incoming packets that exceed their data stream's specified traffic contract. Marked packets may be immediately dropped by the hardware, or dropped later down stream should congestion occur. Your local speed trap is a form of traffic policing. ATM devices may shape traffic by timing the introduction of outgoing packets into the network to conform to their data stream's traffic contract. Timed stoplights at freeway entrance ramps are a form of traffic shaping.
Although traffic policing and shaping to an arbitrary traffic contract may sound complicated, there are relatively simple algorithms, such as the virtual scheduling algorithm described the ATM Forum's Traffic Management 4.0 specification, that implement them. Such algorithms are efficient enough that in ATM equipment they are implemented in commercially available chipsets.
Traffic shaping is implemented solely by the producer, and traffic policing solely by the consumer. Traffic shaping smooths data flow, while traffic policing prevents congestion. I like traffic policing and shaping mechanisms not only because I've implemented a few in commercial products, but also because they allow me to reason about the maximum inflow and outflow rates of packets while troubleshooting a customer system.
Connection Admission Control
Connection Admission Control (CAC) in its simplest form is a function that returns true or false when given a traffic contract as an argument. CAC decides whether a network device can handle a new connection with the specified contract. CAC takes into account the traffic contracts of all existing connections, and its intent is to guarantee the fulfillment of existing contracts even if that means rejecting a new connection request.
In service provider networks, rejecting a new connection often means rejecting revenue, so this is not done lightly. The ATM switch or other network device that can accept more connections than another similar device and still fulfill all of its contracts has a leg up on the competition. This kind of intelligence is typically the result of complex statistical traffic models. I have implemented several CAC algorithms in commercial products, but my designs were based upon theoretical work by Ph.D.s in ivory towers. (That didn't keep me from giving the occasional talk on the topic.)
SOA and EDA
I have tried to stress here and there that traffic management is important even if you are not using an actual communications network. Lately where I have seen its need emerge is in projects implementing a Service Oriented Architecture (SOA) or Event Driven Architecture (EDA), often over some kind of Enterprise Service Bus (ESB). Whether their designers realize it or not, these systems are real-time messaging systems, and suffer from all of the traffic management issues of more traditional communications systems.
For the past year I have been working with a team of engineers on an application that uses an implementation of the Java Business Integration (JBI) standard (JSR-208), a specification for a Java-based ESB. JBI defines both synchronous and asynchronous messaging passing mechanisms, but traffic management and flow control are left up to the applications that use it, by virtue of not being discussed in the specification. Companies using JBI or any other ESB (or indeed, implementing any kind of SOA or EDA at all) would be well advised to take into account issues of traffic management in their systems.
Sources
Chip Overclock, "Gene Amdahl and Albert Einstein", October 2006
N. Giroux, et al., Traffic Management Specification Version 4.0, ATM Forum, af-tm-0056.000, April 1996
L. He, et al., "Connection Admission Control Design for GlobeView-2000 ATM Core Switches", Bell Labs Technical Journal, 3.1, January-March 1998
J. L. Sloan, "Introduction to TCP Windows and Window Shifting/Scaling", Digital Aggregates Corp., April 2005
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
Ron Ten-Hove, at al., Java Business Integration (JBI), JSR-208, August 2005
Actually, don't. Even your sewer system is based on some stochastic assumptions, and when those assumptions are violated, congestion occurs. In the case of toilets, I think you know what kind of congestion I mean.
Even in relatively simple messaging systems involving a single process or a single Java virtual machine, shared resources can be temporarily exhausted if many components try to firehose messages at each other with no feedback mechanism to affect some kind of rate control. At best, performance slows down for a spell until things sort themselves out. At worst, buffer pools run dry, the heap is exhausted, and the entire system may even deadlock. This is a well known failure mode in real-time systems, yet I routinely see developers writing code that assumes that they can fire away messages as quickly and as often as possible with little or no regard as to whether the recepient is in a position to receive them.
There are a lot of mechanisms used in real-time systems that can control how quickly a message producer may send a message so as to not overwhelm the message consumer that receives it. (It's important to understand that producer and consumer are roles played by communicating applications for the duration of a single message exchange. An application may and typically will act as both a producer and a consumer.) Below are brief descriptions of some of the traffic management mechanisms I've encountered, from the simplest to the most complex.
XON/XOFF
XON/XOFF is a form of traffic management used for flow control that will be familiar to anyone who remembers ASCII terminals. XON is the ASCII character produced by typing control-Q. XOFF is a control-S. The X is a common abbreviation for "trans" as in "transmit". When the consumer's buffer is full (or nearly so) it sends an XOFF to the producer, who suspends sending until it receives an XON. XON/XOFF is probably the most widely used traffic management mechanism on the planet by virtue of it being implemented in nearly every RS-232 serial device in existence.
The downside of XON/XOFF is that it doesn't scale well with latency and bandwidth. Just to make the problem obvious, let's assume that your producer and consumer are using a 155 megabit per second (OC-3) communication channel over a geosynchronous satellite link. Data transmitted via geosynchronous satellites have a round-trip time (RTT) of about half a second just due to the speed of light; it takes a quarter of a second to get up to the satellite, another quarter of a second to get down again.
By the time the consumer sends an XOFF to the producer, the producer operating at full channel speed will already have sent over thirty-eight megabits of data that is just travelling along the radio signal up to the satellite and back down to earth, and will send another thirty-eight megabits in the time it takes the XOFF to travel from the consumer to the producer over that same channel.
To use a simple mechanism like XON/XOFF, the consumer has to be able send the XOFF to the producer while it still has seventy-seven megabits of slack in its input buffer in order to receive all the data that is in transit, or will be in transit, before the producer can shut off.
ACK/NAK
ACKnowledge and Negative AcKnowledge is probably the most straightforward traffic management mechanism. The producer is blocked upon sending a message until the consumer either acknowledges or fails to acknowledge receiving the message. It reliably prevents the producer from overwhelming the consumer.
Its biggest downside is performance. Assume the worst case where the producer sends one bit of data over that same satellite link, then waits for the acknowledgement from the consumer. It takes the one bit of data a quarter second to go from the producer to the consumer. Ignoring any processing latency, it takes the acknowledgement another quarter of a second to go from the consumer to the producer. It took a half-second to transmit a bit from producer to consumer before a second bit could be sent, so your 155Mb/s channel has an effective bandwidth of two bits per second. This is why communications channels are more efficient with larger packet sizes.
Suppose the producer instead sends a megabit before it waits for a reply. The first bit of that megabit still takes a quarter of a second to get from the producer to the consumer, and the last bit takes more than six milliseconds at 155Mb/s. Then the acknowledgment takes another quarter of a second to go from the consumer back to the producer. Your channel now has an effective bandwidth of just under two megabits per second. You are still only utilizing a little over one percent of your channel.
What is the magic number for packet size? With a simple protocol like ACK/NAK, there is no magic number. No matter how many bits you send before turning the channel around, you are still wasting bandwidth when you stop transmitting and wait for an acknowledgement.
The ACK/NAK pattern shows up more often than you might think, even if your application isn't using a communications network at all. Synchronous message passing, where the producer blocks waiting for the consumer to receive the message, is a form of the ACK/NAK pattern. Synchronous message passing does not scale well as the complexity of the application grows, yet it is very common in web services or in any remote procedure call (RPC) mechanism like DCE, Corba, or Axis. Applications may unwittingly make requests concurrently to each other, blocking waiting for an acknowledgement that will never come because the two ends are now deadlocked waiting for the other end.
Synchronous message passing can also be a subtle form of priority inversion. While an application acting as a producer is blocked waiting for an acknowledgement from its consumer, other perhaps higher priority applications are blocked trying to send messages to the blocked application in its role as a consumer.
Windowing and Credit
To use the full capacity of your data channel, you would like to keep it full all the time. To do that, the producer has to be able to put enough new data in the channel to keep it full while an acknowledgement for prior data travels from the consumer. Communications protocols handle this by implementing a windowing or credit mechanism.
A window is a fixed amount of data that may be outstanding at any one time, as yet unacknowledged by the consumer. The producer is allowed to send this much data before being forced to wait for an acknowledgement. The producer guarantees that it has at least this much buffer space so that it can save the data it has already sent, in case it receives a negative acknowledgement from the consumer and has to send it again. Examples of windowing protocols are ISDN's Link Access Protocol for the D-Channel (LAP-D) which is used for signaling in non-IP digital telephony, and IP's Transmission Control Protocol (TCP). The producer and consumer may agree on a window size as part of their initial connection setup, or the window size may be fixed as part of the protocol itself.
A credit is the amount of free buffer space in the consumer signalled to the producer as part of an acknowledgement. This feedback mechanism lets the producer know how much more data it is allowed to send before having to stop and wait for more credit. The consumer guarantees that it has buffer space at least as large as the credit it sends. Because a consumer may be receiving messages from more than one producer into the same buffer space, the credit that a producer sees may bear little relation to the amount of data it has actually sent to the consumer. TCP/IP also uses a credit mechanism.
The optimal window or initial credit size is the bandwidth-delay product. The bandwidth-delay product of our satellite link is the 155 megabits per second bandwidth multiplied by the half second RTT, or more than nine megabytes. Although most communication channels don't suffer the RTT of a geosynchronous satellite link, many, such as gigabit Ethernet, have substantially higher bandwidth, still yielding a large bandwidth-delay product. To make effective use of channels with high bandwidth or high RTT (or both), both the producer and the consumer require large amounts of memory for buffering outgoing and incoming data. (Think what implications there might be regarding the reliability of your communications network when you have a high bandwidth-delay product. In an unreliable network, the producer may well spend most of its time and network bandwidth retransmitting a huge amount of buffered data.)
The windowing and credit patterns also show up more often than you would think. They are both a form of asynchronous message passing in which the a limit is placed on how far ahead a producer may get ahead of a consumer before being blocked waiting for an acknowledgement. Allowing applications to use unfettered asynchronous message passing does not scale well as load increases. Resources in the underlying message passing mechanism can be quickly exhausted by an enthusiastic producer with a slow witted consumer. This can lead to a deadlock of the entire system.
Traffic Shaping and Policing
All of the flow control mechanisms discussed so far require consent between the producer and the consumer. Because they all involve temporarily pausing the producer, they also introduce jitter into the data stream. Jitter is variation in the inter-arrival time (IAT) of successive packets in the data stream.
Jitter isn't generally a problem for data transfer using applications like FTP. It can be inconvenient when using interactive applications like TELNET. But it wreaks havoc with data streams that have real-time constraints like audio or video streams or VOIP. Jittered packets in real-time streams may arrive too early for play back and have to be buffered, or too late and have to be discarded completely. (What the audio or video player or VOIP telephone may play back in place of the discarded packet is an interesting problem left as an exercise to the reader.)
Technologies like Asynchronous Transfer Mode (ATM) impose traffic contracts on individual data streams. A traffic contract is a formal description of the bandwidth and burstiness characteristics of the data stream plus any real-time contraints it may have regarding jitter. ATM devices police traffic by marking incoming packets that exceed their data stream's specified traffic contract. Marked packets may be immediately dropped by the hardware, or dropped later down stream should congestion occur. Your local speed trap is a form of traffic policing. ATM devices may shape traffic by timing the introduction of outgoing packets into the network to conform to their data stream's traffic contract. Timed stoplights at freeway entrance ramps are a form of traffic shaping.
Although traffic policing and shaping to an arbitrary traffic contract may sound complicated, there are relatively simple algorithms, such as the virtual scheduling algorithm described the ATM Forum's Traffic Management 4.0 specification, that implement them. Such algorithms are efficient enough that in ATM equipment they are implemented in commercially available chipsets.
Traffic shaping is implemented solely by the producer, and traffic policing solely by the consumer. Traffic shaping smooths data flow, while traffic policing prevents congestion. I like traffic policing and shaping mechanisms not only because I've implemented a few in commercial products, but also because they allow me to reason about the maximum inflow and outflow rates of packets while troubleshooting a customer system.
Connection Admission Control
Connection Admission Control (CAC) in its simplest form is a function that returns true or false when given a traffic contract as an argument. CAC decides whether a network device can handle a new connection with the specified contract. CAC takes into account the traffic contracts of all existing connections, and its intent is to guarantee the fulfillment of existing contracts even if that means rejecting a new connection request.
In service provider networks, rejecting a new connection often means rejecting revenue, so this is not done lightly. The ATM switch or other network device that can accept more connections than another similar device and still fulfill all of its contracts has a leg up on the competition. This kind of intelligence is typically the result of complex statistical traffic models. I have implemented several CAC algorithms in commercial products, but my designs were based upon theoretical work by Ph.D.s in ivory towers. (That didn't keep me from giving the occasional talk on the topic.)
SOA and EDA
I have tried to stress here and there that traffic management is important even if you are not using an actual communications network. Lately where I have seen its need emerge is in projects implementing a Service Oriented Architecture (SOA) or Event Driven Architecture (EDA), often over some kind of Enterprise Service Bus (ESB). Whether their designers realize it or not, these systems are real-time messaging systems, and suffer from all of the traffic management issues of more traditional communications systems.
For the past year I have been working with a team of engineers on an application that uses an implementation of the Java Business Integration (JBI) standard (JSR-208), a specification for a Java-based ESB. JBI defines both synchronous and asynchronous messaging passing mechanisms, but traffic management and flow control are left up to the applications that use it, by virtue of not being discussed in the specification. Companies using JBI or any other ESB (or indeed, implementing any kind of SOA or EDA at all) would be well advised to take into account issues of traffic management in their systems.
Sources
Chip Overclock, "Gene Amdahl and Albert Einstein", October 2006
N. Giroux, et al., Traffic Management Specification Version 4.0, ATM Forum, af-tm-0056.000, April 1996
L. He, et al., "Connection Admission Control Design for GlobeView-2000 ATM Core Switches", Bell Labs Technical Journal, 3.1, January-March 1998
J. L. Sloan, "Introduction to TCP Windows and Window Shifting/Scaling", Digital Aggregates Corp., April 2005
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
Ron Ten-Hove, at al., Java Business Integration (JBI), JSR-208, August 2005
Subscribe to:
Posts (Atom)
