Algorithms to Live By

by Brian Christian

  I happened to be copying, or rsyncing, the old X Consortium archives from my house to MIT over this ten-millisecond-long path.… SmokePing [was] reporting latencies averaging well over one second, along with bad packet loss, just while copying a file.… I took Wireshark, and there were these bursts of really strange behavior.… This looked like no TCP [sawtooth] I expected at all. It should never occur that way.

  In plain English, he saw something … very weird. As the saying goes, “the most exciting phrase to hear in science, the one that heralds new discoveries, is not ‘Eureka!’ but ‘That’s funny.’”

  At first Gettys thought that something was wrong with his cable modem. What his family had been calling a problem in the Internet seemed like a traffic jam at their own wall socket. Packets meant for Boston weren’t getting stuck midway there; they were getting stuck in the house.

  But the deeper Gettys looked into it, the more concerned he grew. The problem didn’t affect just his home router and modem, but every home router and modem. And the problem wasn’t just in networking devices—it was in computers themselves, in desktops, laptops, tablets, and smartphones, woven into Linux, Windows, and OS X. And it wasn’t just in end-user hardware, either: it touched the very infrastructure of the Internet itself. Gettys sat down to lunches with key players at Comcast, Verizon, Cisco, and Google, including Van Jacobson and Vint Cerf, and slowly started to piece the puzzle together.

  The problem was everywhere. And the problem was bufferbloat.

  A buffer is essentially a queue whose function is to smooth out bursts. If you walked into a doughnut shop at roughly the same time as another customer, it wouldn’t do for the very momentarily overwhelmed cashier to make one of you leave the store and come back another time. Customers wouldn’t have it, of course, but neither would management: such a policy is virtually guaranteed to underutilize the cashier. Putting the customers in a queue instead ensures that the average throughput of the store approaches its maximum throughput. That’s a good thing.

  This superior resource utilization comes with a very real cost, however: delay. When Tom took his daughter to a Cinco de Mayo festival in Berkeley, she set her heart on a chocolate banana crêpe, so they got in line and waited. Eventually—after twenty minutes—Tom got to the front of the line and placed his order. But after paying, they then had to wait forty more minutes to actually get the crêpe. (Like Jim Gettys, Tom quickly found himself fielding a substantial volume of familial complaints.) Taking orders turned out to take less time than making crêpes, so the queue to order was just the first part of the problem. At least it was visible, though; customers knew what they were in for. The second, longer queue was invisible. So in this case it would have been a much happier outcome for all if the crêpe stand had just cut off the line at some point and put up a sign that they weren’t taking orders for a bit. Turning customers away would have made everyone better off—whether they ended up in a shorter crêpe line or went elsewhere. And wouldn’t have cost the crêpe stand a dime of lost sales, because either way they can only sell as many crêpes as they can make in a day, regardless of how long their customers are waiting.

  This is precisely the phenomenon that Jim Gettys was observing in his home cable modem. Because he was uploading a file, his computer was sending the modem as many upstream packets as it could handle. And the modem was pretending to handle a lot more than it actually could, turning none away while building up a massive queue. So when Gettys tried to download something at the same time—to visit a webpage or check email—his ACK packets would get stuck behind the upload, having to wait in line at the modem to leave the house. Because his ACKs then took forever to return to the web and email servers, the servers would in turn throttle their own downstream connection speeds to a corresponding crawl.

  It was like trying to have a conversation where every time you say “uh-huh” it is delayed by ten or twenty seconds. The speaker is going to slow way down, assuming you aren’t comprehending them, and there’s nothing you can do about it.

  When a networking buffer fills up, what typically happens is called Tail Drop: an unceremonious way of saying that every packet arriving after that point is simply rejected, and effectively deleted. (Turning new customers away from the crêpe stand once the line gets too long would be a version of Tail Drop in a human context.) Given the postal metaphor for packet switching, it might seem a bit odd to imagine a mail carrier who simply vaporizes every parcel that doesn’t fit onto the truck that morning. Yet it’s precisely such “packet drops” that lead a computer to notice that one of its packets hasn’t been acknowledged, prompting AIMD to start halving the bandwidth. Dropped packets are the Internet’s primary feedback mechanism. A buffer that’s too large—a restaurant taking every order no matter how short-staffed the kitchen, a modem taking every packet that comes in regardless of how long it’ll take to send them on—prevents this moderation from happening as it should.

  Fundamentally, buffers use delay—known in networking as “latency”—in order to maximize throughput. That is, they cause packets (or customers) to wait, to take advantage of later periods when things are slow. But a buffer that’s operating permanently full gives you the worst of both worlds: all the latency and none of the give. Smoothing out bursts is great if you are, on average, clearing things at least as quickly as they’re arriving—but if your average workload exceeds your average work rate, no buffer can work miracles. And the bigger the buffer is, the further behind you’ll get before you start signaling for help. One of the fundamental principles of buffers, be they for packets or patrons, is that they only work correctly when they are routinely zeroed out.

  For decades, computer memory was sufficiently expensive that there was simply no reason to build modems with oodles of unnecessary memory capacity. Thus, there had simply been no way for a modem to build up a queue bigger than it could handle. But at some point, as economies of scale in the computer industry radically lowered the cost of memory, modem manufacturers started giving their machines gigabytes of RAM because that was effectively the smallest amount of RAM they could get. As a result, the ubiquitous device buffers—in modems, routers, laptops, smartphones, and in the backbone of the Internet itself—became thousands of times too big, before people like Jim Gettys sounded the alarm to do something about it.

  Better Never than Late

  Take your most basic problem as a single person … someone likes you, you don’t like them back. At one point, that used to be kind of an awkward situation. You had to have a conversation, it was weird. Now what do you do? Someone likes you, you don’t like them back? You just pretend to be busy … forever.

  —AZIZ ANSARI

  Now is better than never.

  Although never is often better than right now.

  —THE ZEN OF PYTHON

  Singer Katy Perry has 107% more Twitter followers than her home state of California has people. The most-followed person on Twitter, as of early 2016 she counts some 81.2 million accounts among her fans. This means that even if 99% of her fans never message her at all—and even if that most devoted 1% who message her do so only once per year—then she still gets 2,225 messages a day. Every single day.

  Imagine if Perry were committed to answering each fan message in the order received. If she could reply to 100 a day, then the fans’ expected wait time for a response would soon be measured in decades. It’s fair to imagine that most fans would prefer a slim chance of getting a reply right away to a guaranteed reply ten or twenty years hence.

  Note that Perry doesn’t have this problem when she leaves a venue and must run a gauntlet of fans expecting an autograph or a few words. Perry does what she can, moves on, and the lost opportunities dissipate. The body is its own flow control. We can’t be in more than one place at one time. At a crowded party we inevitably participate in less than 5% of the conversation, and cannot read up or catch up on the remainder. Photons that miss the retina aren’t queued for later viewing. In real life, packet loss is almost t
otal.

  We use the idiom of “dropped balls” almost exclusively in a derogatory sense, implying that the person in question was lazy, complacent, or forgetful. But the tactical dropping of balls is a critical part of getting things done under overload.

  The most prevalent critique of modern communications is that we are “always connected.” But the problem isn’t that we’re always connected; we’re not. The problem is that we’re always buffered. The difference is enormous.

  The feeling that one needs to look at everything on the Internet, or read all possible books, or see all possible shows, is bufferbloat. You miss an episode of your favorite series and watch it an hour, a day, a decade later. You go on vacation and come home to a mountain of correspondence. It used to be that people knocked on your door, got no response, and went away. Now they’re effectively waiting in line when you come home.

  Heck, email was deliberately designed to overcome Tail Drop. As its inventor, Ray Tomlinson, puts it:

  At the time there was no really good way to leave messages for people. The telephone worked up to a point, but someone had to be there to receive the call. And if it wasn’t the person you wanted to get, it was an administrative assistant or an answering service or something of that sort. That was the mechanism you had to go through to leave a message, so everyone latched onto the idea that you could leave messages on the computer.

  In other words, we asked for a system that would never turn a sender away, and for better or worse we got one. Indeed, over the past fifteen years, the move from circuit switching to packet switching has played itself out across society. We used to request dedicated circuits with others; now we send them packets and wait expectantly for ACKs. We used to reject; now we defer.

  The much-lamented “lack of idleness” one reads about is, perversely, the primary feature of buffers: to bring average throughput up to peak throughput. Preventing idleness is what they do. You check email from the road, from vacation, on the toilet, in the middle of the night. You are never, ever bored. This is the mixed blessing of buffers, operating as advertised.

  Vacation email autoresponders explicitly tell senders to expect latency; a better one might instead tell senders to expect Tail Drop. Rather than warning senders of above-average queue times, it might warn them that it was simply rejecting all incoming messages. And this doesn’t need to be limited to vacations: one can imagine an email program set to auto-reject all incoming messages once the inbox reached, say, a hundred items. This is ill-advised for bills and the like, but not an unreasonable approach to, say, social invitations.

  The idea of encountering a “full” inbox or “full” voicemail is an anachronism now, a glaring throwback to the late twentieth century and the early 2000s. But if the networks that connect our newfangled phones and computers, with their effectively infinite storage, are still deliberately dropping packets when things get fast and furious, then maybe there’s reason to think of Tail Drop not as the lamentable consequence of limited memory space but as a purposeful strategy in its own right.

  As for network bufferbloat, the ongoing story is a complicated but happy one, involving large-scale efforts by hardware and operating system manufacturers to make fundamental changes to network queues. There’s also a proposal for a new backchannel for TCP, the first such modification in many years: Explicit Congestion Notification, or ECN. Fully extricating the Internet from bufferbloat will draw on all of these changes and require the patience of many years. “This is a long-term swamp,” says Gettys.

  But there’s a lot to look forward to about a post-bufferbloat future. With their inherent latency, buffers are bad for most interactive processes. When we speak via Skype, for example, we generally prefer an occasionally staticky signal now to a clear recording of what our caller said three seconds ago. For gamers, even a 50-millisecond lag could be the difference between fragging and being fragged; in fact, gaming is so sensitive to latency that all important gaming honors are still contested in person, with players boarding airplanes to gather and compete over a network serving just a single room. And much the same is true for anything else where being in sync matters. “If you want to play music with your friends, even in [your] metropolitan area, you care about tens of milliseconds,” Gettys notes, imagining a whole host of new applications and businesses that might spring forth to take advantage of the interactive potential of low latencies. “A generalization I take away from this whole experience is that engineers should think about time as a first-class citizen.”

  Apple’s Stuart Cheshire concurs that it’s high time for latency to become a top priority for network engineers. He’s appalled that companies who advertise “fast” Internet connections refer only to high bandwidth, not to low delay. By analogy, he notes that a Boeing 737 and a Boeing 747 both fly at about five hundred miles per hour; the former can hold 120 passengers, while the latter carries three times as many. So “would you say that a Boeing 747 is three times ‘faster’ than a Boeing 737? Of course not,” Cheshire exclaims. Capacity does matter sometimes: for transferring large files, bandwidth is key. (If you’ve got a huge amount of cargo to move, a container ship may well trump thousands of trips by a 747.) For interhuman applications, however, a quick turnaround time is often far more important, and what we really need are more Concordes. And indeed, bringing latencies down is one of the current frontiers of networking research, and it will be interesting to see what that brings.

  Meanwhile, there are other battles to be waged. Gettys snaps his attention away for a second, looking out of the frame. “It’s not working for you? I’m talking to someone at the moment, and I’ll deal with it when I’m finished. We’re wrapping up here—uh, no, the 5 GHz is working at the moment, the 2.4 GHz channel has hung. It’s the infamous bug. I’ll reboot the router.” Which seems an opportune moment to say our good-byes and release our bandwidth to the commons, to the myriad flows making their additive increase.

  11 Game Theory

  The Minds of Others

  I’m an optimist in the sense that I believe humans are noble and honorable, and some of them are really smart.… I have a somewhat more pessimistic view of people in groups.

  —STEVE JOBS

  An investor sells a stock to another, one convinced it’s headed down and the other convinced it’s going up; I think I know what you think but have no idea what you think I think; an economic bubble bursts; a prospective lover offers a gift that says neither “I want to be more than friends” nor “I don’t want to be more than friends”; a table of diners squabbles over who should treat whom and why; someone trying to be helpful unintentionally offends; someone trying hard to be cool draws snickers; someone trying to break from the herd finds, dismayingly, the herd following his lead. “I love you,” says one lover to another; “I love you, too,” the other replies; and both wonder what exactly the other means by that.

  What does computer science have to say about all this?

  Schoolchildren are taught to conceive of literary plots as belonging to one of several categories: man vs. nature, man vs. self, man vs. man, man vs. society. Thus far in this book we have considered primarily cases in the first two categories—that is to say, computer science has thus far been our guide to problems created by the fundamental structure of the world, and by our limited capacities for processing information. Optimal stopping problems spring from the irreversibility and irrevocability of time; the explore/exploit dilemma, from time’s limited supply. Relaxation and randomization emerge as vital and necessary strategies for dealing with the ineluctable complexity of challenges like trip planning and vaccinations.

  In this chapter we shift the focus and consider the remaining two genres—that is, man vs. man and man vs. society: in effect, the problems that we pose and cause each other. Our best guide to this terrain comes from a branch of mathematics known as game theory, a field that in its classical incarnation had an enormous impact on the twentieth century. In the past couple of decades, cross-pollination between game theory
and computer science has produced the field of algorithmic game theory—which has already begun to have an impact on the twenty-first.

  Recursion

  Now, a clever man would put the poison into his own goblet because he would know that only a great fool would reach for what he was given. I am not a great fool, so I can clearly not choose the wine in front of you. But you must have known I was not a great fool—you would have counted on it—so I can clearly not choose the wine in front of me.

  —THE PRINCESS BRIDE

  Arguably the most influential economist of the twentieth century, John Maynard Keynes, once said that “successful investing is anticipating the anticipations of others.” For a share of stock to be sold at, say, $60, the buyer must believe he can sell it later for $70—to someone who believes he can sell it for $80 to someone who believes he can sell it for $90 to someone who believes he can sell it for $100 to someone else. In this way, the value of a stock isn’t what people think it’s worth but what people think people think it’s worth. In fact, even that’s not going far enough. As Keynes put it, making a crucial distinction between beauty and popularity:

  Professional investment may be likened to those newspaper competitions in which the competitors have to pick out the six prettiest faces from a hundred photographs, the prize being awarded to the competitor whose choice most nearly corresponds to the average preferences of the competitors as a whole; so that each competitor has to pick, not those faces which he himself finds prettiest, but those which he thinks likeliest to catch the fancy of the other competitors, all of whom are looking at the problem from the same point of view. It is not a case of choosing those which, to the best of one’s judgment, are really the prettiest, nor even those which average opinion genuinely thinks the prettiest. We have reached the third degree where we devote our intelligences to anticipating what average opinion expects the average opinion to be. And there are some, I believe who practice the fourth, fifth, and higher degrees.