Weaker in numbers
TL;DR
Phones failed at the Halloween parade because cell networks are built on scarcity: a shared pool, sized by a 1917 formula for ordinary days, that collapses when everyone needs it at once. Phone-to-phone networks are abundant: every person brings a radio, so crowds add capacity.
On Saturday night the Village Halloween Parade walked up Sixth Avenue again, as it has nearly every year since a puppeteer named Ralph Lee started it in 1974. It still has one rule that makes it unlike anything else in the city: anyone in costume can join. The organizers count about fifty thousand marchers and more than two million people along a route of 1.4 miles.
The most common complaint afterwards had nothing to do with the crowd itself. It was that phones stopped working. Given the nature of our work, I take that complaint seriously. The issues highlighted around connectivity time and again describe a philosophy, and once you see it you notice it everywhere: our networks are designed to be weaker in numbers.
The arithmetic of one block
The figures below use assumptions that favor the network.
| One 80 meter stretch of Sixth Avenue | |
|---|---|
| Spectators, by the organizers’ count | 2 million+ |
| On the route at one moment, if one in ten is there | 200,000 |
| People along one 80 meter stretch of the 2.25 km route | ≈ 7,100 |
| Cell capacity serving that stretch, every carrier combined (generous) | 1 Gbps |
| Each person’s share if everyone sends at once | ≈ 140 kbps |
| Time to send one 3 MB photo at that share | ≈ 3 min |
Not everyone sends at once, but at 7 pm on Halloween on Sixth Avenue, many people do.
Those seven thousand people carry seven thousand phones, each with a Bluetooth radio and a Wi-Fi radio that can reach the phone beside it. Almost all of that hardware sits idle, waiting in line for one antenna on a rooftop.
Erlang and the busy hour
In 1908 a Danish mathematician named Agner Krarup Erlang joined the Copenhagen Telephone Company to answer a practical question: how many circuits does an exchange need? In 1917 he published the formula that answered it. Give it the number of circuits and the expected traffic, and it tells you what fraction of calls will be refused.
The formula rests on two ideas. The first is the busy hour. You size the system for the busiest hour of an ordinary day, not for the rarest one. The second is the grade of service. You decide in advance what share of attempts you will refuse, typically one in a hundred, and you build exactly enough to hit it. Refusals are planned.
Refusals stay near zero up to the design point, then climb steeply. Make the hour a quarter busier and one attempt in ten is refused. Double it and the pool turns away 41 percent. Mobile data networks are far more sophisticated than a 1917 telephone exchange, but they are still planned around a busy hour and a fixed pool, and any fixed pool under rising demand has this shape. A parade sits beyond the right edge of the chart.
Erlang’s math was correct for copper circuits and human operators, which really were scarce. The constraint has changed since: every phone is now a radio, yet networks still route everything through the shared pool.
Correlated demand and the moments that matter
The busy hour also assumes demand is spread out, with people calling for their own unrelated reasons. The moments people care about most break that assumption, because they are the moments when everyone cares at once.
When an earthquake shook Virginia in August 2011, the surge of calls congested AT&T, Verizon, Sprint, T-Mobile and Frontier across the Mid-Atlantic, with service disrupted for as long as an hour. No equipment failed. Everyone was checking on someone at the same moment.
In a network built on a shared pool, importance and congestion become the same variable. The probability that your message fails rises with the probability that it matters. A bank is solvent until everyone wants their money on the same morning. A cell network works until something happens that is worth telling someone about.
Metcalfe’s law and capacity per person
In 1983 Robert Metcalfe offered a rule of thumb that the value of a network grows with the square of the number of people on it. Skeptics argue the true growth is closer to n log n. Either way, value climbs as people join, because every newcomer can reach everyone already there.
Capacity per person in a tower network does the opposite. It falls as one over n. On Saturday night the network was worth the most at the exact moment it delivered the least.
Spatial reuse and the cocktail party
A crowded party holds dozens of conversations in one room at the same time. A loudspeaker in that room can carry only one.
Voices fade with distance. Each conversation fills only a small bubble of air, so a few meters away another pair can use the same air for something else. The loudspeaker is built to be heard by everyone, which means it occupies the entire room. A cell tower is a loudspeaker. Phones talking to the phones beside them are a cocktail party. Radio engineers call this spatial reuse: the same spectrum used again and again in many small places at once, and it is one of the biggest reasons wireless capacity has grown at all.
Bluetooth and most Wi-Fi share the 2.4 GHz band, the same band a microwave oven uses, because water absorbs it well. People are mostly water. In a dense crowd every body soaks up a little signal, each link reaches less far, and each bubble shrinks. Smaller bubbles mean more of them fit on the same block. The density that overloads the tower lets a crowd of phones hold more conversations at once.
Mesh network capacity scaling
Mesh networks have limits too. In 2000 Piyush Gupta and P. R. Kumar proved that in a large wireless network where devices send to random, distant destinations, throughput per device falls as the network grows, roughly as one over the square root of n log n. That result is the dashed line in the chart above.
That bound assumes random, distant destinations. Physics charges for distance, not for company. Later work found ways around the bound. Grossglauser and Tse showed that mobility increases capacity, because moving people carry messages closer to where they are going. In 2007 Ayfer Özgür, Olivier Lévêque and David Tse showed that with cooperation, the total capacity of a dense network can grow in step with the number of devices in it.
Crowd traffic is not random. “Where are you” is a question for someone two blocks away, not two states away. So is the photo of your friend’s costume and the plan to meet at the corner of Bleecker. Most of what a crowd wants to say never needs to leave the crowd. Local questions can be answered locally, in a few short hops, and the tower can be left for what genuinely needs to leave the block.
Abundant here does not mean infinite. It means supply arrives with demand. In a tower network a person who shows up brings only a need. In a network between devices the same person brings a need and a radio, in the same pocket.
Scarcity and abundance in network design
Every architecture carries an opinion about other people. In a scarcity network, the stranger beside you is a competitor for a thin slice of air, and every new arrival makes your message a little less likely to arrive. In an abundant network the stranger beside you is part of the reason it gets there.
When Bettencourt, West and their colleagues measured cities, they found that wages and invention grow faster than population, with an exponent around 1.15, while infrastructure such as roads grows slower, around 0.85. A city is a machine for making density pay. We moved into cities because together we are more than the sum of us, and then we built the one piece of urban infrastructure that charges us for being close.
The parade works the same way. It has no stage and no ticket for the route, and everyone who comes adds to it.
Offline Protocol and crowd networking
Offline Protocol builds for this. Our software lets phones and other devices connect directly over Bluetooth and Wi-Fi Direct and relay for each other, using the internet when it is there rather than depending on it. The test I hold us to is the inverse of the Erlang curve: the more people show up, the better it should work.
Next October fifty thousand people will walk up Sixth Avenue again, carrying more radios than any tower could ever serve. I would like the network to behave like the parade, open to anyone who shows up and better for every person who does.
Sources and further reading
- Village Halloween Parade, official site and history, route and attendance.
- A. K. Erlang, “Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges” (1917), summarised in Erlang B formula and Agner Krarup Erlang.
- 2011 Virginia earthquake: carrier congestion across the Mid-Atlantic.
- Metcalfe’s law, and B. Briscoe, A. Odlyzko and B. Tilly, “Metcalfe’s law is wrong”, IEEE Spectrum (2006).
- P. Gupta and P. R. Kumar, “The capacity of wireless networks”, IEEE Transactions on Information Theory (2000).
- M. Grossglauser and D. Tse, “Mobility increases the capacity of ad hoc wireless networks”, IEEE/ACM Transactions on Networking (2002).
- A. Özgür, O. Lévêque and D. Tse, “Hierarchical cooperation achieves optimal capacity scaling in ad hoc networks”, IEEE Transactions on Information Theory (2007), preprint.
- L. Bettencourt, J. Lobo, D. Helbing, C. Kühnert and G. West, “Growth, innovation, scaling, and the pace of life in cities”, PNAS (2007).
Frequently asked questions
Why does my phone stop working in a big crowd?
Everyone in range of a cell site shares its fixed capacity. Cells are sized for the busiest hour of an ordinary day with a small, planned share of refused attempts, and that share rises steeply once demand passes the design point. A parade is far past it.
What is the Erlang B formula?
A formula A. K. Erlang published in 1917 while working for the Copenhagen Telephone Company. It gives the probability that a new call is refused when a fixed group of circuits is busy, and it is still the basis for sizing shared capacity against a target failure rate.
What is spatial reuse in wireless networks?
Using the same radio spectrum in many places at once. Short links only occupy a small area, so many can run side by side without interfering. It is why a room full of people can hold dozens of conversations at once while one loudspeaker can carry only one.
Does a mesh network get slower as it grows?
It depends on how far messages travel. Gupta and Kumar showed in 2000 that per-device throughput falls as a network grows when destinations are random and far away. Later work showed total capacity of a dense network can grow in step with the number of devices, and most of what a crowd says is local.
Why does a crowd weaken Bluetooth and Wi-Fi range?
Both use the 2.4 GHz band, which water absorbs well, and people are mostly water. In a dense crowd each link reaches less far, which shrinks the area it occupies and leaves room for more links to run at the same time.
What does Offline Protocol build?
Software that lets phones and other devices connect directly over Bluetooth and Wi-Fi Direct and relay for each other, using the internet when it is there rather than depending on it.