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 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.


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.)


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.


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

Thursday, December 21, 2006

Rocket Science as Product Development

Yep, you parsed that title correctly.

At the recommendation of my friend and colleague Scott Thomas, I read Steve Squyres' book Roving Mars, a fascinating glimpse into how science, engineering, and politics play together in the rarified world of interplanetary exploration. Squyres was the principle investigator for the Mars rover missions. In his book, Squyres describes how his science team came up with the idea of sending a mobile robot - a kind of instrument-laden all-terrain vehicle that you could fit in the trunk of your car - tens of millions of miles to another planet. How politics led to them to send not one but two Mars Exploration Rovers (MERs), Spirit and Opportunity, to two very different locations on the Red Planet. And what they found when they got there.

If like me you occasionally gaze up longingly at a clear night sky, or if you've been known to read a novel or two by authors such as Banks, Baxter, Benford, or Brin, then you can be forgiven if your eyes, like mine, get a little teary at the thought of this kind of adventure.

The science described in the second half of the book is alone enough to make it compelling reading. Proof that Mars was a damp if not down right wet place sometime in the distant past. But for us engineers in the audience, the most riviting part is the first half, which is the best description I have ever read about the drama that is product development.

No, really.

Mars and Earth would be in perfect alignment and proximity for a launch in the summer of 2003. The launch window was only five weeks wide. And if they missed it, those perfect celestial conditions would not occur again for eighteeen years. The twin-rover program cost something in the neighborhood of eight hundred million dollars, and was sixteen years in the making from inception to launch. If the engineers and developers missed their dates by more than that five week window, it was more than an inconvenience. It was more than a career limiting move. It was even more than a disaster. Some of the engineers who poured their hearts and minds into that project were old enough (like, my age) that it was within the realm of possibility that they would not be alive for another launch opportunity. It was pretty much hit that launch window or... well, the alternative didn't bear thinking about too much.

And so Squyres launches into a detailed description of the many, frequently painful, time-space-budget-feature tradeoffs that are part of every single product development program. And for this product development, failure was not an option. If you have friends and relatives that wonder what you do, give them this book, and tell them that maybe you don't send rovers to Mars (or maybe you do). But your day to day life is a lot like the people's in this book.

Those that follow the U.S. space program already know the ending of this story. Not only were the rovers successful, but wildly so. They far outlived their projected lifespans, continuing to do useful science well after the date when their batteries should have died because their solar panels were too covered in dust and the Martian winter of sixty below zero temperatures had frozen all their joints and axles. Part of this was just luck: the occasional Martian windstorm cleaned the dust from their solar panels, extending their lives. But part of it was good design and engineering.

One of the most edge-of-your-seat portions of the book was when the MER team at the Jet Propulsion Laboratory in Pasadena lost contact with Spirit. Squyres describes how the engineers, working on some hypotheses regarding firmware failures, poured through code to try to predict how such hypothetical faults could have occurred. One of the ideas they had was that the on-board flash memory used for storing data had somehow become corrupted, leading to rolling reboots of the main processor. (Other sources have revealed that this was a VxWorks system running on an RS6000 processor.) It wasn't a perfect hypothesis, because they could not figure out a way in which the flash file system could have gotten corrupted, nor could they duplicate it on the test rover on Earth. But the pattern of failure, where the rover would transmit mostly useless status information for just a few minutes then quit, fit most of the forensic data.

To test this theory, they had to transmit a command to the rover over a ten-bit per second auxiliary channel (yes, about one character a second) with about a six minute round trip latency to tell it to reboot with a temporary file system build in RAM. They had to hope the rover received the command during the brief window when it was likely to be operating during the sunny Martian day and before it rebooted. That it would successfully execute the command. And that it would bring up the high bandwidth channel at the right time when there was enough solar power to transmit, when the rotation of Mars placed the rover correctly, when the relay satellites in orbit around Mars were in the right places, and when the reply could be received by one of three Earth stations in the U.S., Australia, and Spain. If this didn't work, half the mission and several hundred millions of dollars were down the tubes because of a corrupted flash file system. This is what people mean when they use the term "mission critical".

It worked. They were able to reassert control over the rover, reformat the flash, and return the rover to normal operation. But here's the part that only people who are in product development will really appreciate. The command they used to save their bacon was not in any requirements document. It was put in place by an engineer who placed the success of the mission ahead of meeting requirements.

Now having been both an engineer and a manager, I know it is a very slippery slope to allow engineers to insert their own unplanned features into a product. This has probably killed more products than it will ever save. It raises issues of economics and security. But what I think it comes down to is this: listen carefully to your engineers, particularly to what they are worried about. They may be trying to save your bacon.

I totally and completely identified with the engineers in this book. I can't tell you how many times I've worked on a project where half the team was sitting in front of a display talking to some firmware via a diagnostic port at a remote customer site over a 9600 baud modem connection, typing in simple commands trying to diagnose a severe problem, asking the on-site technician on the phone questions like "Would you describe the pattern of blinking of the red LED as 'Jingle Bells'?", while the other half of the team was pouring over a hundred thousand lines of C++ code trying to come up with a failure mode that fit the facts. Is it any wonder I preach the need to include the capability for remote field troubleshooting at the lowest levels?

No doubt about it: space men, earth men, we are all in the same tribe.


Steve Squyres, Roving Mars, Hyperion, 2005

Wednesday, December 20, 2006

Rules of Thumb

My name is Chip and I've been a manager. I've fallen in and out of management more than once during my career of three decades plus change. All engineers should take a turn in the corner office. You develop your people skills, you learn the business, and you might even discover that a lot of management is surprisingly and satisfying analytical. Or you'll make it that way.

My degrees are in computer science, so when I had to start wearing a tie - purely metaphorically speaking - I knew I needed some formal training. But some of the best stuff I learned about management, and about being a manager, I didn't learn in any class or seminar. Some of it I learned on the job. Some of it from a good mentor or two. Some by observation. And much of it in the school of hard knocks. I also read a hell of a lot.

Here are a few of the things I have learned.

It takes you at least as long to get out of trouble as it took you to get into it.

Say you have a corporate culture that sucks. How long will it take to turn it around? Jack Welch might be right that people's outward behavior can be changed quickly. But just because they are smiling and nodding doesn't mean they trust you as far as they can throw you. Or aren't thinking "up yours" to every point you try to make. If you had poor personnel policies for a couple of years, expect to take at least couple more years before you have eradicated all of their negative effects.

For every action there is an equal and opposite reaction.

I once heard a department head complain about a lack of employee loyalty after the company we both worked for had spent the last several years laying off half of its employees. What did she expect? If you treat people with mistrust, expect to not be trusted. If you show disrespect, don't be surprised when you get no respect. If you treat people like idiots, don't expect to be winning any MacArthur grants.

You are not saving money if you have merely moved costs from where they can be measured to where they can't.

The classic case of this is eliminating desktop and laptop computer support to save those precious IT dollars that, let's face it, are just overhead. Like a lot of overhead, it enables your highly paid technical staff to do their jobs. By shifting the simpler support functions to your engineers, you now have a bunch of extremely expensive albeit disgruntled technicians. I've also seen engineers earning six figures doing the kind of clerical work I used to have my administrative assistant do (and who was really good at it) at a fraction of the cost. Keep saving money like this and eventually you'll go bankrupt.

People pretty much act the way they are incented to act.

If your people exhibit some behaviors that are, let's say, contra-indicated, your first step should be to look at your system of incentives. I've written about and given talks on Robert Austin's book Measuring and Managing Performance in Organizations (Dorset House, 1996) in which he writes about how incentive programs drive dysfunction into organizations. Nelson Repenning of MIT has written on fire-fighting in organizations, how rewarding fire-fighting leads to more fires to fight, and if unchecked, leads to a death spiral. Managers try to motivate employees with all sorts of stuff that only can be classified as motherhood and apple pie. Some of it they might even believe themselves. But people have so much on their plates, they can't meet impossible deadlines, come in on tiny budgets, and produce high quality work. It's just impossible. The only way people know what the company really values is by carefully watching who is rewarded for doing what.

If you waste people's time, you are sending them a message that it is okay to be wasteful.

I once worked for a company that estimated the cost of big meetings by multiplying the number of participants by their average fully loaded cost. The division director would actually say "If we gather everyone in the auditorium, that's a $4000 meeting. Is it that important?" Everyone understood that time was money. And because it was wrong to waste time, it was also wrong to waste anything else.

On their deathbed, no one ever said "I wish I'd spent more time at work."

But you might say "I wish I'd done more writing." Or "spent more time with my kids." Or even "spent more time with smart engineers." When I'm racing out the door on my way to work, I always stop and pet the cats. Whatever it is for you, take the time to do it. Keep your priorities straight.

What rules of thumb do you use?

Update (2009-10-26)

People are more important than things.

I'm embarrassed to admit that it took losing some friends my age and my mom in 2006 to drive this home. But given the choice between, say, going out to dinner with colleagues at a conference, and going back to your hotel room to read LOLCats captions, choose the former. Sure, reading LOLCats is good short term entertainment, but connecting with friends and colleagues is the better long term investment of your time.

Saturday, December 16, 2006

Lunch-Time Tales

"It is a singular consciousness that spawned an entire race of humans. We don't know who struck first, us or them. But we know that it was us that warmed the globe. At the time they were dependent on petrochemical power and it was believed that they would be unable to survive without an energy source as abundant as oil. Throughout bovine history, we have been dependent on humans to survive. Fate it seems is not without a sense of irony. The bovine body generates 500 liters of greenhouse gasses in the form of methane a day. Combined with a form of fusion the humans have found all the energy they would ever need. There are fields, endless fields, where cows are no longer born, we are grown. For the longest time I wouldn't believe it, and then I saw the fields with my own eyes. Watch them liquefy the dead so they could be fed intravenously to the living. And standing there, facing the pure horrifying precision, I came to realize the obviousness of the truth. What is The Mootrix? Control. The Mootrix is a computer generated dream world built to keep us under control in order to change a cow into beef. "

-- Moopheus


Rod Black

Jerry Dallmann

Doug Gibbons

Jim Homer

John Meiners

Tam Noirot

John Sloan

Tom Staley, The Matrix Transcript

The Matrix, a Wachowski Brothers film, 1999