Traffic Engineering with Portals

Suppose you invented portals. Like you were able to make a pair of portals, and if you stepped through one you’d come out the other, wherever it was. What would you do with them?

Well the first thing to do is obviously to solve the world’s energy problems. Anchor one portal above another, so that if you fall through the lower portal, you’ll come out of the upper portal — just above where you were. Add a turbine generator and pour in some water and BAM, infinite energy.

Two Portals → Free Energy

But what next?

Say you want to bring the world together. Build “hubs” all over the world, that connect to each other. If you build a million hubs, that’s one per every ~7000 people. That might be enough.

How can you connect the hubs, so that it’s easy to get from any hub to any other?

If you connect every hub directly to every other hub with a portal, then you can always get from a starting hub to a destination hub in one hop. But that’s… less than practical. You would need to make one million squared equals one trillion portals: over a hundred portals per person on Earth. Where would we even put them all?

One million portals per hub is too many. Let’s go minimal instead. How about connecting the portals in a big ring? Two portals per hub: one that goes to the next hub in the ring, and one that goes to the previous hub. That’s a reasonable number of portals to build, but it might take a while to get from one hub to another. Worst case, you need to traverse 500,000 portals.

To compare the methods so far:

Method | Portals/Hub | Worst #Hops
-------+-------------+------------
Clique | 1000,000    | 1
Ring   | 2           | 500,000

Maybe there’s a sweet spot in the middle?

Trees are a nice data structure. Let’s try making a tree! Arrange the hubs in a binary tree. This tree will have depth ~20, and each hub (except the root) will have 3 portals: one to go to its parent, and two to go to its children. To get from a source hub to a destination hub, you walk up the tree to the common ancestor, then down the tree to the destination. Worst case, that’s 38 hops. Not bad!

…except that half of all paths take you through the root hub. That hub is going to get way too much traffic: about half a million times the traffic of most other hubs. In contrast, the previous approaches would have a uniform traffic distribution, meaning that if travellers pick source and destination hubs uniformly at random, then each hub will receive equal traffic.

Method | Portals/Hub | Worst #Hops | Traffic Distribution
-------+-------------+-------------+---------------------
Clique | 1000,000    | 1           | Uniform
Ring   | 2           | 500,000     | Uniform
Tree   | 3           | 38          | Skewed

So trees aren’t great for navigation because too many travellers would need to cross the root. Is there a way to get a small number of portals, a small number of hops, and a uniform distribution of traffic across the hubs?

Why yes there is! Give each hub a 20 digit binary id. Then build 20 portals per hub: one to toggle each digit in its id. For example, if we’re at hub 10000000000000000000, then taking the third portal (out of 20) will bring us to the hub with id 10100000000000000000, because that’s the id you get when you toggle the third bit.

To get from a starting hub to a destination hub, you just need to take portal number N for each bit position N in which the starting hub’s id differs from the destination hub’s id. Worst case, that’s 20 hops. And the traffic will be uniform: it won’t be biased toward any particular hub.

(We’ve been aiming for one million hubs, but there are 2^20 ids, which is a bit larger. No biggie, though. We can just build a few tens of thousands of additional hubs to fill out every id.)

This is a much better portal layout than the previous ones. It’s actually usable!

Method       | Portals/Hub | Worst #Hops | Traffic Distribution
-------------+-------------+-------------+---------------------
Clique       | 1000,000    | 1           | Uniform
Ring         | 2           | 500,000     | Uniform
Tree         | 3           | 38          | Skewed
Bit Flipping | 20          | 20          | Uniform

Puzzle

Can you do better? Reduce the portals/hub or #hops, while keeping the traffic uniform, and the navigation method simple (don’t want travellers to get lost!).

If you want to puzzle it out, stop here. Try to find a nice portal layout.

---

I wasn’t sure how much better you could do.

I was worried you would need a really complex portal layout, and there would be a tradeoff between comprehensibility and efficiency.

There’s not.

You can get 4 one way portals/hub and 20 hops worst case, with a very simple navigation rule.

Solution

Like the last approach, give each hub a 20-bit id. Give every hub two outbound portals, a “zero” portal and a “one” portal. The “zero” portal takes you to the hub whose id you can get by (i) shifting every bit in the id one to the left, and (ii) using 0 as the rightmost bit. Similarly, the “one” portal shifts the bits one to the left and uses 1 as the rightmost bit.

Let’s look at an example, using 4 digit ids instead of 20 digit ids for simplicity. Say you want to get from the hub with id 0110 to the hub with id 1000. You would first follow portal “one”, then portal “zero”, then portal “zero”, then portal “zero”. That is: you just spell out your destination address! Here’s where that will take you:

          0110
portal_1: 1101
portal_0: 1010
portal_0: 0100
portal_0: 1000

In general, if you want to get from abcd to WXYZ, you take portals W, X, Y, Z, in that order:

          abcd
portal_W: bcdW
portal_X: cdWX
portal_Y: dWXY
portal_Z: WXYZ

If you get lost and want to go home, it’s easy. You don’t even need to know what hub you’re at. Just follow portal a, then portal b, then portal c, then portal d, and you’re home.

So you get to your destination in 20 hops. The whole scheme is beautifully symmetric, so the traffic will be uniformly spread across the hubs.

How efficient is 4 portals/hub and 20 hops worst case? Could there be a much better solution out there, waiting to be found?

Nope! This solution is nearly optimal, if you assume that portals are meant to be taken one-way to prevent traffic jams. Four portals/hub gives you 2 entrance portals and 2 exit portals, which means that you’re making a binary choice with every hop. Twenty binary choices in a row allows you to reach at most 2^20 (equals one million) possible destinations. So we couldn’t do any better!

Well… we could get a little better. This analysis assumed that you’re definitely going to make 20 hops, but you could also stop after fewer, which would open up more possible destinations. If you take up to 19 hops, but are allowed to stop early, how many possible destinations is that? It’s 1 (if you stop at your starting hub) + 2 (if you take one hop) + 4 (if you take two hops) + … + 2^19, which is 2^20-1 (let’s ignore the -1).

So an optimal solution would require 19 hops instead of 20 worst case. So we’re very close to optimal, while having a solution that’s easy to describe and has a uniform traffic distribution!

Method       | Portals/Hub | Worst #Hops | Traffic Distribution
-------------+-------------+-------------+---------------------
Clique       | 1000,000    | 1           | Uniform
Ring         | 2           | 500,000     | Uniform
Tree         | 3           | 38          | Skewed
Bit Flipping | 20          | 20          | Uniform
Bit Shifting | 4           | 20          | Uniform

So that’s why you should hire me if you’re looking for a traffic engineer for portals.