What's the Frequency, Flik?

Science, Technology

The internet is pretty slick. Every attached computer has a unique address sort of like a phone number. (Sometimes, entire sub-networks lurk behind a single address through the miracles of IP and routing and such, just as entire switchboards of phones may lie behind the phone number of a main switchboard, but that's another story.)

Thanks to Transmission Control Protocol (TCP), files can be sent from one address to another with amazing efficiency. The brilliance of TCP's design lies in this: the rate at which stuff is sent automatically throttles up or down in response to network latency as measured by response time!

The Office – S5/E9: The Surplus from Vimeo.

Let's break it down. TCP is cool because "transmission control" sounds like "mission control" and that sounds like something NASA would have. But TCP is also cool because of how it works. Grossly simplified, it works like this:

  • You want to send that document requesting a pony to someone who has sent you a blind solicitation.
  • The networky stuff in your computer breaks the document into a bunch of "packets". Just like real parcels sent through UPS or Fedex or that other service, each packet is wrapped with a label explaining where it came from, where it's going, and so forth.
  • The packets follow various routes to their destination. As they arrive, the recipient (i.e., networky stuff on the other guy's computer) sends a receipt (called an "ack") to the sender. Meanwhile, the recipient uses the wrapper info to figure out whether all the packets have arrived, to put them in their correct order, and finally to reassemble the document. Transmission Accomplished!
  • The best part is the flow control. The sender starts by spraying out some packets and timing how long it takes to get a receipt for them. If the receipts come quickly, the sender sends more packets at a time. If the receipts come slowly, the sender sends fewer packets at a time (even stopping cold, if necessary). And since there's an ongoing flow of shipments and receipts and timing, the sender can avoid flooding the network but can also avoid letting bandwidth go to waste! Faster and faster! Slower and slower! No, faster! Slower! Strike that! Reverse it!

Flik, from Pixar's A Bug's Life

Now, here's the trippy science factoid du jour: researchers at Leland Stanford Junior University have discovered that Harvester Ants (including, apparently, the most venemous insect in the world) have been using TCP all along… behind Vint Cerf's and Bob Kahn's backs! Says the press release:

the rate at which harvester ants – which forage for seeds as individuals – leave the nest to search for food corresponds to food availability.

A forager won't return to the nest until it finds food. If seeds are plentiful, foragers return faster, and more ants leave the nest to forage. If, however, ants begin returning empty handed, the search is slowed, and perhaps called off.

They also found that the ants followed two other phases of TCP. One phase is known as slow start, which describes how a source sends out a large wave of packets at the beginning of a transmission to gauge bandwidth; similarly, when the harvester ants begin foraging, they send out foragers to scope out food availability before scaling up or down the rate of outgoing foragers.

Another protocol, called time-out, occurs when a data transfer link breaks or is disrupted, and the source stops sending packets. Similarly, when foragers are prevented from returning to the nest for more than 20 minutes, no more foragers leave the nest.

Further research into what these critters might teach us will be undertaken at the newly funded FourmiLab. Meanwhile, I leave you with a meditation on Proverbs 6:6 by e. e. cummings: go(perpe)go from his 1935 manuscript No Thanks (in George James Firmage, ed., E. E. Cummings: Complete Poems, 1904-1962, Revised, NY: Norton, 1994, p. 403 or thereabouts).

Last 5 posts by David

27 Comments

26 Comments

  1. John David Galt  •  Aug 26, 2012 @10:27 am

    So?

  2. Grifter  •  Aug 26, 2012 @12:49 pm

    Neat! I want my internet run by ants…

  3. darius404  •  Aug 26, 2012 @12:55 pm

    A Bug's Life was SO much better than Antz

  4. David  •  Aug 26, 2012 @2:32 pm

    Science: "Here's a phial of info about how packing works. Go to the monocot. Go to the conch.
    John David Galt: "So?"

    Science: "Behold these navigational facilities, and those birdbrains."
    John David Galt: "So?"

    Science: "Attend! An automaton!"
    John David Galt: "So?"

    Science: "Here. Throw this chicken."
    John David Galt: "I would prefer not to."

  5. AlphaCentauri  •  Aug 26, 2012 @3:51 pm

    Everyone else calls "Baba O'Reilly" "Teenage Wasteland," but my kids call it "Out here in the Fields," because they were so impressed by it in A Bugs Life.

  6. Joe Pullen  •  Aug 26, 2012 @4:04 pm

    I would like to find a way to blame TCP flow control for the speed at which money leaves our bank account – it would save a lot of arguments with the wife.

  7. En Passant  •  Aug 26, 2012 @4:21 pm

    Science: "Here. Throw this chicken."
    John David Galt: "I would prefer not to."

    Reflect on the tragedy of the unfortunate Adams and the still more unfortunate Colt in the solitary office of the latter. Perhaps recall the divine injunction: "A new commandment give I unto you, that ye love one another."

    No man that ever I heard of, ever committed a diabolical murder for sweet charity's sake. Mere self-interest, then, if no better motive can be enlisted, should, especially with high-tempered men, prompt all beings to charity and philanthropy.

  8. Grifter  •  Aug 26, 2012 @6:18 pm

    @David:

    That bit reads almost familiar, is it paraphrased from something?

    You made me SWLOL (snort with laughter, out loud).

  9. Bruce  •  Aug 26, 2012 @7:49 pm

    I think it was SLANT by Greg Bear that had an insect based computer.

  10. David  •  Aug 26, 2012 @7:50 pm

    @Grifter Only the last line. En Passant hath grok'd its allusion.

  11. James Pollock  •  Aug 26, 2012 @8:58 pm

    While you were praising the "efficiency" of TCP's "sliding window feature", you missed the significance of it. There are two (main) transport protocols used on the Internet, TCP and UDP. Both break transmissions into packets, which are sent one after the other as quickly as the network will allow (it is a different feature that actually slows things down if the router is congested).
    TCP is more inefficient that UDP, because it has a feature that UDP lacks, which is the "ACK' message. UDP works like normal mail… you put your packet in the mail, and the system does its best to route that packet to its destination, and it almost always works. TCP is more like registered mail… the receiver acknowledges receipt of each packet. This allows the sender to be certain that each packet has been received (and, act accordingly, typically by re-sending the lost packet).
    What the "sliding window" feature does is assess the reliability of network delivery, and allows the system to send acknowledgements less frequently than every packet. (If you send an ACK for every packet, then 50% of all the packets carried on your network are ACK messages, for an efficiency of 50%. The sliding window tells the sender to send 2, 4, 8 or even 16 packets before pausing to make sure an ACK has been received, thus reducing the number of ACK messages that need to be sent (but possibly increasing the number of packets that need to be resent if one goes missing.) This increases the efficiency of transmission relative to 1:1 ACK messages, but is not as efficient as UDP, which sends no ACK messages at all.
    TCP/IP is a bit of a misnomer, as not all IP messages are TCP (not by a long shot… depending on the type of information transmitted, the percentage of TCP traffic may be under 1%.
    Note that TCP/IP is hardware independent, and there is, in fact, an official TCP/IP standard that details how TCP/IP would work with carrier pigeons as network media.

  12. David  •  Aug 26, 2012 @9:18 pm

    @James Pollock

    While you were praising the "efficiency" of TCP's "sliding window feature", you missed the significance of it….
    …TCP is more inefficient that UDP….
    …not as efficient as UDP, which sends no ACK messages at all.

    While you were explaining differences between TCP and UDP, you seem to have missed the significance of my praise, which had nothing to do with how TCP stands relative to UDP.

    My interest was in protocols that guarantee delivery and respond appropriately to meta-info concerning success in that undertaking. Specifically, I drew attention to two of these: TCP and HAFB (harvester ant foraging behavior).

    UDP, in contrast, guarantees nothing. (Hence all the mildly amusing jokes like the one I retweeted last week.) That puts UDP outside the scope of what I was describing.

    Thanks for your comments about ack rates. They illustrate TCP's lovely efficiency.

  13. Karasu  •  Aug 27, 2012 @5:30 am

    Well, the obvious insect-computer I can think of is Hex in the discworld, which actually uses ants.

    (And Cheese)

    (For the mouse, of course)

  14. James Pollock  •  Aug 27, 2012 @7:24 am

    Well, TCP is nowhere near the pinnacle of efficiency amongst guaranteed-delivery protocols, either. There was considerable progress (and much flame-warring) over the topic of the best protocol back in the 90's. TCP most resembles XMODEM in it's design… none of the partisans (ZMODEM vs. Kermit vs. Punter as examples of the loudest partisans, if I recall).
    Apparently, ant technology hasn't spread worldwide; the nests near my house have not yet discovered the timeout, as no matter how many of the little invaders I kill, they keep coming in the house. In fact, household odiferous ants have exactly the opposite reaction, as a crushed ant releases a scent that triggers a flood.

  15. David  •  Aug 27, 2012 @7:59 am

    @James Pollock

    Thanks for your input. Indeed, TCP isn't tops. However, it is the protocol to which the researchers discovered a natural fourmilicious analog. The ants, man! Think of the ants! That's the link under discussion; nothing else.

    The deeper issue is knowing one's audience and its interests. Epitomizing protocol specifications and segment definitions? Wide of the mark. Linking a high level cartoon of the transport layer to the unexpected behavior of foraging insects? A bit closer to home. Ken mocking feckless would-be gainsayers with snort-related threats and pudendal buffoonery? Right On Target!

    I recall using ZModem back in the day when its error correction seemed to put it light years ahead of Kermit. We used modems back then, and most of the web was summarized in Scott Yanoff's circular. ;)

    Speaking of snorting, I hear yellowjackets also seek vengeance on their odiferous, squashed brethren. These stinky kinsman redeemers are indeed odious and feral.

  16. Gavin  •  Aug 27, 2012 @9:16 am

    I'd note that the packets are also numbered so that if disruption occurs they don't have to send all packets over again, just the ones that didn't get there. Learning about frames and packets is certainly interesting.

    I like how science is looking at the animal kingdom and learning where it can, like that mold that shows the most efficient ways to design transit systems by the way the mold grows from one food source to another and then links it back to other parts.

  17. Josh C  •  Aug 27, 2012 @11:51 am

    That's really neat, and a nice analogy. It does look like it reduces to "Harvester ants use closed-loop positive feedback in their foraging behavior." That's interesting, but doesn't seem revolutionary. Am I missing something?

  18. David  •  Aug 27, 2012 @12:29 pm

    Nope. It's light news.

  19. Alex Ponebshek  •  Aug 27, 2012 @2:08 pm

    Good analogy, but a technical correction: TCP does *not* regulate speed based on response times, only packets dropped entirely. Even if packets are taking longer and longer to round-trip, TCP keeps speeding up until packets are actually being lost.

  20. wgering  •  Aug 27, 2012 @2:58 pm

    "Popehat: come for the discussion of ant-based connection protocols, stay for the pudendal buffoonery."

    Yep, sounds accurate.

  21. George Martin  •  Aug 27, 2012 @7:43 pm

    James Pollock said:
    Note that TCP/IP is hardware independent, and there is, in fact, an official TCP/IP standard that details how TCP/IP would work with carrier pigeons as network media.

    That was an April 1st RFC (Request For Comment). The IETF (Internet Engineering Task Force) has a tradition of publishing humorous gag RFCs on April 1st. That particular one was: D. Waitzman (1 April 1999). IP over Avian Carriers with Quality of Service. RFC 2549. Updates RFC 1149, listed above. (see IP over Avian Carriers) That was one of the ones for 1999. If you use Google to search for RFC 2549, you will find it. Other April 1st RFcs for that year were:

    S. Glassman, M. Manasse, J. Mogul (1 April 1999). Y10K and Beyond. RFC 2550.

    and

    S. Bradner (1 April 1999). The Roman Standards Process — Revision III. RFC 2551.

    George

  22. George Martin  •  Aug 27, 2012 @7:53 pm

    Oops, RFC 1149 in 1990 was the original one. You can get a list of all of the April 1st RFCs here: http://en.wikipedia.org/wiki/April_1st_RFC

    George

    PS

    RFC 1149 starts with:

    A Standard for the Transmission of IP Datagrams on Avian Carriers

    Status of this Memo

    This memo describes an experimental method for the encapsulation of
    IP datagrams in avian carriers. This specification is primarily
    useful in Metropolitan Area Networks. This is an experimental, not
    recommended standard. Distribution of this memo is unlimited.

    Overview and Rational

    Avian carriers can provide high delay, low throughput, and low
    altitude service. The connection topology is limited to a single
    point-to-point path for each carrier, used with standard carriers,
    but many carriers can be used without significant interference with
    each other, outside of early spring. This is because of the 3D ether
    space available to the carriers, in contrast to the 1D ether used by
    IEEE802.3. The carriers have an intrinsic collision avoidance
    system, which increases availability. Unlike some network
    technologies, such as packet radio, communication is not limited to
    line-of-sight distance. Connection oriented service is available in
    some cities, usually based upon a central hub topology.

  23. Dustin  •  Aug 29, 2012 @10:40 pm

  24. Dustin  •  Aug 29, 2012 @10:41 pm

    Well, that didn't work.

  25. M.  •  Aug 30, 2012 @4:52 am

    Is it a European or an African swallow?

  26. Joe  •  Aug 31, 2012 @9:27 am

    The bumblebee (genus Bombus) with a brain the size of a pinhead, may be smarter than humans and computers in some respects. In the game of chess, humans and computers will often come to a draw. There is one mathematical puzzle, however, where apparently neither would stand a chance against this fuzzy hymenopteran.

    The travelling salesman problem.

    If you are a salesperson and you must visit a number of cities and businesses to sell your solution, the problem before you is how to hit every city and location at least once and to travel the shortest possible distance in the process. A concept that to this day that continues to elude my travel booking tool and my assistant.

    Computers solve this problem the hard way by calculating all the possible routes and distances before arriving at a solution, a process that could take hours depending on the complexity of the problem.

    However, apparently researchers have discovered that bumblebees solve this problem all the time. Given a selection of pollen-rich flowers, the bees don't hit the flowers in order of discovery, but rather take a broader approach and automatically find the shortest path to land on all the flowers at least once.

    Of course part of the problem may be because we have physicaconstraints in our model that the bumblebee doesn’t such as roads, available airline flights, airport locations, etc. so unlike the bumblebee we humans can’t plot a straight line from one appointment to the next for maximum efficiency.

1 Trackback