Home > Articles > Software Development & Management

  • Print
  • + Share This
From the author of

18.6 Optimizing for the Most Common or Important Case

Huffman coding is an example of this principle. It is a form of compression that encodes each symbol with a variable-length quantity, where the shorter quantities are used to encode more frequently occurring symbols.

In networking protocols the "optimize for most common or important case" principle might be applicable to implementation or to protocol design. An example of an implementation that optimizes for the usual case is one in which a "common" IP packet (no options, nothing else unusual) is switched in hardware, whereas if there is anything unusual about the packet it is sent to the dungeon of the central processor to be prodded and pondered when the router finds it convenient.

An example of this principle in protocol design is to encode "unusual" requests, such as source routing, as an option. This is less efficient in space and in parsing overhead, when such requests appear, than having the capability encoded in a fixed portion of the header. However, in the usual case, when they do not appear, it is far more efficient to have them not appear in the packet at all.

Another interesting example is the IPv6 length extension. The fixed part of the header contains a 2-byte field for packet length. However, if the packet is longer than that, the 2-byte packet length in the header is set to 0; 8 additional bytes are required to carry an option that will carry a 4-byte packet length. When I commented to someone that this seemed like an incredible kludge—and that there should just be a 4-byte length field if people thought 2 bytes was not long enough— someone pointed out that this could be an example to illuminate the "optimize for the usual case" principle. In the normal case, the length field requires 2 bytes of header. In the weird, longer-than-65,000-bytes case, it requires 10 bytes to encode the length, but I suppose with a packet that large you'd never miss the 10 bytes of overhead.

    Real-World-Protocol

    The "leave a message with my son" protocol. (I have his permission for including this, by the way.) This was more of an issue when my son was about 10. People would call and insist on leaving a message with him. He'd jot it down on a little scrap of paper somewhere, or if he couldn't find a pencil and paper scrap, he'd just intend to remember it. Years later I'd find a telephone number on a scrap of paper, or have him say, "Oh yeah. Someone called the other day. I've forgotten who it was and what it was about."

    Surprisingly, the "leave a message with my daughter" protocol seems to work just fine.

    Andy Tanenbaum suggested a method of turning this protocol into an "optimize for the most important case." He suggested making up a bunch of sticky notes with the message "your boss called" (assuming that's the most important phone call I might get) and placing them all near the phone. If someone other than my boss called, my son could do his usual thing, but if it was indeed my boss, my son could simply move a sticky note directly onto the phone.

  • + Share This
  • 🔖 Save To Your Account