July 2007 Archives

A few weeks ago, Dan Wallach told me about his experience flying without ID. Dan had forgotten his ID and didn't have time to go back and get it. After some fumbling, the airlines and the TSA figured out that he could still fly as long as he went through secondary screening. I can more or less confirm this procedure.

On my flight back from ORD this morning, I presented my drivers license, which was expired by less than a week. The contractor checking my ID started counting on her fingers (figuring out what the date was? seeing if I was within some grace period?) and then asked me if I had an extension. I didn't¹ , so she told me I had to go through secondary screening. I said "OK", and she wrote "NO ID" on my ticket and sent me over to secondary, where I got the same slightly less cursory than usual screening as I would have gotten if I'd been randomly selected.

By the way, when did your right to be frisked by someone of the same gender turn into the requirement that you be frisked by someone of the same gender? I and two other men stood in line for about five minutes waiting for a male TSA agent to be available, even though a female agent was free. The man in front of me explicitly offered to waive the gender match requirement but no dice.

^1. Truth be told, I did have my passport, but I was curious what would happen. Also, I will note that the ticket counter agent took my ID with no problem.

The IETF Social was held Tuesday night at the House of Blues which is, as we all know, the hippest place in Chicago. Anyway, I'm there eating my pulled pork sandwich when some guy dressed in a cop uniform gets up on stage and announces that there are some dangerous fugitives in the audience, apparently dressed like uh, Hasidic diamond merchants. OK, OK, Dan Aykroyd owns the place so a little tribute sort of has to be expected, but then next thing I know the MC is announcing Cab Calloway, who, when I look over, appears to be somewhat younger, fatter, and less dead than I remembered him. He, of course, sang Minnie the Moocher.

This was followed by two vaguely Dan Aykroyd and John Belushi looking guys in dark suits singing what I believe to be the Blues Brothers set from the Palace Hotel Ballroom on the shores of Lake Wazzapamani. Now, I bow to few in my admiration for the genius of The Blues Brothers (27 years old now!), but when exactly did House of Blues cross over the line between tribute and parody?

Over at Yglesias, people are discussing this anti-universal health care ad:

A number of the commentors observe that this is a bit inartful, since movie theaters are not exactly bastions of state ownership. For instance:

Soooo...movie lines are government run? Movie tickets are Federally subsidized and not a matter of free-market supply and demand?

OK, so this is sort of a fair cop, since the advertisers brought up the comparison, but at some level these are different situations, or at least maybe are.

Queues serve two primary social purposes: exerting backpressure on demand and distributing load over time.

Exerting Backpressure on Demand
It doesn't take a queueing theorist to see that if a system can service 10 users an hour, then if the aggregate number of aggregate customers entering the system is 20 an hour on a permanent basis, then not all of them are going to be served. There are a lot of different ways to deal with this (rationing, auctions, etc.), but one is simply to implement a first-come-first-served policy. Everyone who can't be served immediately just has to wait in the queue. Now, if your aggregate demand exceeds your aggregate service capability, that means that the queue gets longer and longer. At some point, new users decide that they're not going to get served in any reasonable time and don't even bother to enter the queue. This provides a form of load management, sorting users to some extent by their willingness to wait. So, making people queue is one way of dealing with demand which would otherwise exceed capacity.

Load Distribution
The other major purpose queueing is load distribution. Lots of systems have extremely uneven demand profiles. If you average demand over time, it's less than the capacity of the system, but over short periods of time it significantly exceeds demand. You can of course deal with this by increasing capacity, but generally you just make people wait during periods of high demand and then catch up when demand is low. This lets you handle a plausible level of service even when you can't handle peak demand.

The flip side of load distribution—and this is where we get back to movie theaters—is that there are systems where the rate of service provision is extremely variable. In particular, any given movie theater room is only showing one movie at a time and people are only admitted every two hours or so. If that's at 12 PM, 2PM, 4PM, etc., and someone shows up at 1PM, they have to wait till 2 to get into the theater. This is true even if aggregate capacity far exceeds demand, i.e., the theater is always half empty. Even if people all show up at 1.59, only so many people can fit through the theater door at once, so you still end up queuing a bit. Now, obviously you could have 10 times as many movie theaters, thus reducing the amount of queuing, but nobody expects theaters to operate at 100x levels of overcapacity. It is worth noting, though, that there's a tradeoff between overcapacity (i.e., idleness) and forcing users to queue.

Now let's take the case of medical service, which is more complicated. When people talk about waiting for medical service, they're mostly using queuing as synechdoche for the system being overloaded and queuing as a form of pushback on demand. The implied claim, of course, is that free markets don't have this. Whether that's true or not (and if you were in Palo Alto on iDay you know it's not) queuing at movie theaters isn't that great a counterexample.

ARIN (the American Internet Registry)'s recent statement on v4 address allocation has generated a bit of a stir. The important text is:

WHEREAS, community access to Internet Protocol (IP) numbering Resources has proved essential to the successful growth of the Internet; and,

WHEREAS, ongoing community access to Internet Protocol version 4 (IPv4) numbering resources can not be assured indefinitely; and,

WHEREAS, Internet Protocol version 6 (IPv6) numbering resources are available and suitable for many Internet applications,

BE IT RESOLVED, that this Board of Trustees hereby advises the Internet community that migration to IPv6 numbering resources is necessary for any applications which require ongoing availability from ARIN of contiguous IP numbering resources; and,

BE IT ORDERED, that this Board of Trustees hereby directs ARIN staff to take any and all measures necessary to assure veracity of applications to ARIN for IPv4 numbering resources; and,

BE IT RESOLVED, that this Board of Trustees hereby requests the ARIN Advisory Council to consider Internet Numbering Resource Policy changes advisable to encourage migration to IPv6 numbering resources where possible.

Obviously, this is written in some sort of legal-speak, but the important bit is the section about "ongoing availability of contiguous IP numbering resources." Here's how to understand this: remember that IPv4 addresses are 32-bit numbers. If you only have one IP address, it doesn't much matter what it is, as long as it's valid. But if you have more than one, it's extremely convenient for all the numbers to be contiguous. Why? Because it's easier to talk about them.

This is pretty easy to see in the context of routing. Say I've just been assigned addresses A, B, and C. I want to tell all the links on which I'm connected to others "hey, if you want to talk to A, B, and C", talk to me. This requires me to send three separate data items and them to store three separate items. That's not so bad when I only have three addresses, but starts to get a little unwieldy if I have 3 million. It's much more convenient to have addresses which are sequential and then I can say "I have addresses A through A+2" (or A through "A+2000"). But you can only do this if your addresses are contiguous.¹

In the IP address world, we actually want something a little more than contiguous. We want bit alignment. IP addresses are 32-bit numbers and the way that blocks are expressed isn't by simple ranges but by prefixes. This is easier to write up with 8-bit addresses (0-255). So, when I get a block of addresses in this space, it looks like this: 240/5, which means "all the addresses with the first 5 bits the same as 240. When we write 240 in binary we get: 11110000 (I'm showing the fixed bits in red.). So, this leaves us with 3 bits to play with and they can take on any possible value. I.e.:

11110000
11110001
11110010
11110011
11110100
11110101
11110110
11110111

So, contiguous addresses are good, but packing them efficiently turns out to be a tricky problem, for two reasons:

• We have a federated assignment scheme, which means that a central registry assigns big blocks to the routing information registriesregional internet registries [correction from Kurtis Lindqvist -- EKR] (RIRs), who then assign them to others. IANA only doles out more addresses once the RIRs start to run out. This tends to cause fragmentation.
• When people overrun their allocations and need more addresses, they naturally want to have a new, contiguous, block. So, either way say now, in case they have fragmented blocks, or we say yes, creating an available hole for the block they used to have, which is fragmented (I don't actually know how often people are made to give up their old blocks).

The end result is that as you start to run out of room you reach a state where you still have empty space but that you can't assign it in as big blocks as you'd like. Incidentally, this situation isn't that different from what happens with dynamic memory allocation for software, although the time scale is a lot shorter in that case.

^1. For much the same reason, you see kidnappers in movies asking for nonsequential, unmarked bills.

About 4 months back I received a notice informing me that I had been selected for jury duty. [Strangely, I've lived in California for 15 years and never been selected, whereas I know people who've been selected multiple times. I don't have any statistical data and clearly random results can look like they have patterns, but I still wonder about the quality of their PRNG.] It intersected with a time when I was scheduled to be in Barcelona giving a talk so I availed myself of the one-time deferral. Of course this turned out to be a mistake because I was of course just as busy the new week they scheduled me for....

In case you have never had jury duty in Santa Clara county, the system works like this. You're required to be available all week but you're only on "standby". This means that you get a jury group number and have to call a number or check a Web site to see if you have to come in. Here's how this works:

1. The letter says "check back Friday after 5 for instructions".
2. Friday at 6 you check and it says "check back Monday between 11 and 12."
3. Monday at 11 you check and it says "check back Monday after 5."
4. Monday after 5 you check and it says "check back Tuesday between 11 and 12."

Lather, rinse, repeat.

I actually managed to make it through the whole week this way without ever having to go to the courthouse. I guess that's good, but on the downside I could never plan more than a few hours ahead and had to inconvenience a bunch of people who wanted to meet with me when I had to keep saying "I could maybe meet first thing in the morning but I won't know till after 5". I'm to

I found the whole process really inconvenient and I've heard from others that they had the same experience. I would have much rather just had to spend a single day at the courthouse but be guaranteed that that was the only day (unless I was selected for a trial, of course). The problem isn't so much missing a day of work (especially since I own a laptop) but rather not being able to plan anything all week.

Designing a system like this involves balancing a number of variables, so it's hard to back out exactly what the constraints must have been, but I'm guessing it's something like:

• It's dramatically more inconvenient for people to spend a day waiting in court than it is to not be able to plan their schedule more than 4 business hours in advance.
• The marginal utility of being in the call-in pool for a week is not much worse than the marginal utility of being in it twice for 2-3 days.
• It's very bad not to have enough jurors on any given day.

It seems to me that these explain most of the major features of the system, namely that:

• They have you on call for a week rather than there for a day.
• That the period is a week rather than having more frequent callups for two days at a time.
• That they have to make constant adjustments to titrate the number of jurors.

Of course, another explanation is that nobody thought very hard about it and since it's illegal for you not to do what you're told there's not a lot of incentive to think about what's convenient for jurors, so we get whatever system we have.