Analog Concurrency: Boarding a Plane
18 Apr 2007
Last week my family and I returned from a visit with the in-laws and boarded a fully-booked Continental Airlines flight at Sacramento Airport bound for New York-La Guardia. Typical of air travel these days, it took nearly a half-hour to shuffle the nearly 140 passengers on board. There were crying kids, wimpering animals in pet carriers, amorphous lines, bustling mobs, and a cavalcade of renegades who believe boarding by row number can’t possible apply to them.
From a civilian’s perspective, this was just one more example of the headache and disorganization we come to expect while being carted into passenger carriers like Guernseys onto a cattle car. From an engineer’s perspective, though, it’s actually an interesting and tantalizingly thorny optimization problem.
Airlines allow passengers to loiter and congregate around the gate until the plane is ready to be boarded. At that point, some flavor of queue is requested by loudspeaker announcement. Such a queue is necessary because the gate crew needs to serialize access to several distinct shared resources: the boarding pass scanner, the jetway, the airplane hatch, and the aisle on the airplane itself. If a queue did not exist, either the unruly mob would just jockey for position to get past the boarding pass scanner one by one (everyone holding out their barcoded passes like floor traders on the New York Stock Exchange), or they would simply bum-rush the jetway and deadlock shoulder-to-shoulder at the airplane hatch or have access to their seat starved out by more agressive passengers.
The type of queue used by Continental is a relatively simple priority queue where passengers with a higher priority are always cleared before passengers of a lower priority, while multiple passengers of the same priority are serviced on a first-come, first-serve basis. The highest priority people in the Continental queue, aside from flight crew and airport personnel, are the first-class flyers and elite frequent flyer members. The second priority is for families with small children or those requiring extra time to get seated, such as those in wheelchairs or other physical challenges. The third priority is for standard frequent flyer members. The remaining peons are assigned lower priorities based on the distance of their seat assignment from the back fo the plane.
Obviously, the aim of this type of queue is not to file folks into the plane as quickly as possible, nor it is necessarily to be fair to all passengers. Though it nicely meters people through the boarding scanner, jetway, and hatch, it causes some stalls as higher priority passengers arrive late to the gate and a fair amount of contention for elbow room along the length of the aisle. By not uniformly filling the plane from window seat to aisle seat and from the rear of the plane forward, people get blocked on their way back to their seat while other passengers coopt the aisle to put their baggage in the overhead bins or let a latecomer into their row. Lower priority passengers suffer a much longer trip time to their seat and are in conflict for limited blankets, pillows, and storage space.
Other carriers, such as Southwest Airlines, implement a different form of priority queue that tries to be more fair to all passengers. People are segmented into one of five priority levels labeled A through E. For the most part, it people are assigned a priority upon check-in on a first-come, first-serve basis, though those with special needs may get a priority boost. Once at the gate, passengers queue up in separate lines reserved for each priority. Once boarding begins, everyone in A goes first, then B, and so on. Because Southwest does not have assigned seating, this system also creates significant aisle contention. Some people like windows, some like aisles, but nobody likes the middle. So windows and aisles fill up first, with the aisle folks generally having to get up and stand in the aisle to usher through the latecomers saddled with the middle seat.
A Survey of Solutions: From Weak To Weird
As I was waiting in line, I started thinking about how to speed boarding through increasing parallelism and lessening the bottlenecks on shared resources. The boarding problem looks a lot like a standard concurrency problem in disguise, with issues like fairness, bandwidth, arrival ordering, and resource contention in all of their glory. Imagine it as a stream of messages that need to get routed as quickly as possible to their destinations. At various points along the way, the messages get signed, transformed, filtered, and otherwise serialized. Messages at or near their destination require sorting, processing, and storage.
Obviously, there is a limit to how much performance gain we can get from choosing a different queuing algorithm. The ideal queue is one that loads the plan from window to aisle, from rear of the plane forward, with no exceptions, no latecomers, no preferred boarding. This reduces resource contention everywhere except in the aisle while folks load the overhead bins or take a little extra time inching to their seat. Short of eliminating carry-on baggage or the elderly and infirm, the airlines are not going to make much further progress this way and still keep their customers.
We could have multiple lines leading to multiple boarding pass scanners, but that would just cause a backup on the jetway. We could make a wider jetway that could handle four or more abreast, but then they would just back up at the hatch. Similarly, a wider hatch causes a back up at the aisle. A wider aisle is probably unrealistic, though, since the bean-counters at the airline would want to fill up the extra space with seats.
Thinking radical for a moment, we know that the best we could ever do would be to load everyone at exactly the same time. Imagine if we preloaded people in a 747-sized overhead scaffold and simply popped open the top of the plane and dropped them into their seats like a bowling pin setter at a bowling alley. Not practical, but it’s clearly our performance upper-bound.
Less radical is borrowing the methodology used by FedEx for loading and unloading cargo planes. FedEx planes are designed as empty hulls. Cargo is loaded into wheeled covered pallets whose cross-section is exactly the same shape as the interior of the plane but only about six to eight feet deep. When it’s time to load a plane, the handlers simply roll a bunch of these pallets in through the back of the plane like LifeSavers into a roll.
What if the airlines made seating pods of six rows each? While waiting for your plane to board, you could find your pod inside the airport, load your overhead bin, sit down and get comfortable. Once your plane was ready, the handlers would roll your pod and all the rest in through the back of the plane. The performance boost comes from drastically reducing jetway, hatch, and aisle contention increasing the numbers of paths to seats and by widening the window of time that passengers have to get seated.
How about you? Got any crazy ideas how to better board a plane?