Anycast: Networking Introduction

There are many methods of handling the requirement for a highly available system. I’d like to talk about one of the methods we use to distribute workload geographically: Anycast.

The first place to start is with an overview of packet networking, particularly IP networking. Unfortunately we have to start there because a lot of people have no actual idea how packet networking works—for systems administrators, it’s what you plug the cable into. For programmers, it’s an API you call that lets you stream data across the world (and nothing more).

Of course, that’s ignoring the details of how IP networking actually works, and while the devil is in the details, knowing the details lets you take advantage of nifty hacks. Just like knowing that an unsigned integer is the same as 32 booleans, knowing how packet networking works allows all sorts of nifty things.

Packet networking works by co-operation: you have a file (or whatever) that you want to send from your computer, A to another computer, B via the Internet. Computer A (your computer) splits up the file into multiple chunks called packets, and puts the IP address of B into the packet. Then it puts this packet into another addressable chunk called a frame (frames use MAC addresses).

[Some comenters have correctly noted that this paragraph is wrong on modern networks—it actually just goes straight to the gateway. I’ll do a dedicated post on this behavior once I have the time/gear to test it.] Here’s where it gets interesting. If your computer doesn’t already know how to map B’s address to a MAC address, it will send out a special type of frame called an ARP query, which basically asks everyone on the local area network “who has this IP address?” If your computer doesn’t get a response, then it’ll look at your local routing table to find out where to send packets that it doesn’t know have a MAC (frame) address for for:

[root@computerA ~]# /sbin/ip route
192.168.22.0/26 dev eth0  proto kernel  scope link  src 192.168.22.8
169.254.0.0/16 dev eth0  scope link
default via 192.168.22.1 dev eth0

In this case, it’ll try to use the default route unless it has a better (that is, more-specific) route to B. So it needs to put the default router’s MAC address into the lower-layer/external frame’s destination address before it sends it out:

[root@computerA ~]# /sbin/arp -en
Address                  HWtype  HWaddress           Flags Mask            Iface
192.168.22.2             ether   00:23:AB:AF:80:00   C                     eth0
192.168.22.1             ether   00:00:0C:07:AC:DD   C                     eth0

So it addresses the frame (in this case) to the MAC (HW) address of the gateway (192.168.22.1 / 00:00:0C:07:AC:DD), and send it on its merry way. The frame leaves your computer with the packet inside, and gets to the gateway.

Now, the default route address is a network address on a router. A router is a computer with two or more network interfaces which knows how to take packets from one interface, and send them out another interface. The routing table on my wifi router at my house would have four entries (this isn’t my actual home router, just what it would look like):

[root@router ~]# /sbin/ip route
192.168.22.0/26 dev eth0  proto kernel  scope link  src 192.168.22.1
192.168.1.0/24 dev eth1  proto kernel  scope link  src 192.168.1.254
169.254.0.0/16 dev eth0  scope link
default via 192.168.1.1 dev eth1

As you can see, it knows about the same subnet as computer A, and also has its own default route to forward packets it receives but doesn’t know what to do with. At this point, the router will take the packet it received on eth0, replace the frame it came in, and send it out eth1 on to the next router (in this case, the cable modem).

Eventually, the packet will be handed around from one router to another, until it hits a router that has lots of interfaces. Usually this is what is sitting on the other end of your cable or DSL line. This box has thousands of routes in its routing table, costs hundreds of thousands of dollars, and has custom-designed hardware for taking packets from one network port and sending them out another.

All these routers co-operate to build a knowledge base of what the network looks like. The view each router has is often simplistic: a single upstream network interface with an upstream gateway, and a downstream LAN network for its locally connected hosts. Upstream of your wifi router, you’ve got the ISP’s interior routing—where your ISP’s routers talk to each other to figure out how to send your packet to computer B.

If your packet needs to leave your ISP (let’s say you’re on Cable, and your friend with computer B is on DSL), then it goes into an even bigger router that has a view of some or all of the Internet, and has calculated the easiest way (that is, the one bouncing through the fewest number of companies) to send your packet to computer B.

Here’s the upshot of all this: each individual router has its own view of the network. It gets this information either statically configured by the network administrator, or it calculates it from information it receives from other routers. As it turns out, because of how routers co-operate to figure out who to send the packet towards next, there is a tremendous loophole that can be used for geographically distributed services.

Continued in:

1. Anycast: Networking Introduction
2. Anycast: The Loophole
3. Anycast: The Interface
4. Anycast: Handling Routes
5. Anycast: DGRAM vs. STREAM
6. Anycast: IP-SLA HOWTO