Hellos

[gdt]

Routing protocols discover the topology of the network (it's "layout" or its "interconnections" if you want to avoid the jargon word). A vital part of that is the question "are my neighbours still there".

That question is usually answered by a Hello protocol. The idea is simple enough: you send a Hello regularly; if you haven't received a Hello for a long while then your neighbour has left. That means the toplogy has changed, and the routing protocol has to recalculate the best routes.

This is computing, so there has to be twists. The first is that some links have a failure mode which is one way. To visualise this, unplug one core of a duplex fibre. The Hello protocol should tell a neighbour if it no longer sees carrier from it. Jargon-wise we name that signal "FERF" -- far end receive failure.

The second is how often to expect Hellos, how often to send Hellos, and how many Hellos to miss before declaring failure. Ten seconds is the traditional time in which to expect a Hello. Routers send out their Hello at half of this time, so traditionally five seconds. Three expired expectation periods expires before the link is declared down. It only takes one new Hello to mark the link as back up. These parameters are often negotiated in the initial exchange with a new neighbour.

Note that Hellos just check connectivity. There are more interesting modes of failure -- mismatched MTUs, MTU black holes, clock slips, and clock or power-related failures on runs of all-0s or all-1s. SONET/SDH has a nice trick here: the CRC is calculated for every segment and a run of failed CRCs marks a link as down. SONET/SDH hardware will fail to all-0s (Loss of Signal) or all-1s (Alarm Indication Signal), thus tripping the CRC detection. ATM has an even nicer trick where a good CRC marks the end of a packet.

The queueing for Hellos is important. This "neighbour control traffic" has its own DSCP (CS7 or 56) and its own ethernet Priority (7). That's the highest there is, and for good reason. If this control traffic fails, then it doesn't matter if other traffic gets through, as the routing protocol will take the link down. This is called "router blackholing".

Out-of-the-box queueing on Linux is poor. And as you might guess there's no queue for this Hello traffic. That's despite there being a lot of Hello-using protocols on Linux (LACP used by the "bond" module, etc). The queueing is about to change, but the CoDel plus statistical fair queueing mechanism simply drops Hellos earlier, rather than pulling them to the front of the queue. If you do configure a Hello-using protocol you should configure a priority queue or class-based queuing for the Hellos to prevent even slight starvation.

Another problem is Hello period. Thirty seconds to mark a link down seemed to be such a short time all those years ago. With IP telephony it is a disaster, as everyone will have hung up after that much silence. A lot of protocols can't have their timers wound down to less than one second, which means three seconds to declare link failure, which is not great but not entirely unacceptable. Obviously if you are going to wind timers down, then the express queueing for control traffic had better be working.

Another problem is the in-order delivery of TCP. Sure, it has a out-of-order mechanism, but an early error in BSD UNIX meant that implementors felt that they could not rely upon it. Some routing protocols use TCP, such as BGP, and we really want to insert and retrieve out-of-order packets without using the TCP out-of-order mechanism. If you are thinking that this means kernel support for the BGP over TCP routing protocol, well that's exactly what dedicated routers running atop of UNIX do.

Another problem is that Hellos scale linearly. Linear scaling is usually seen as a good thing. Until you want to run a lot of neighbours. As networking moves the control plane further and further from the forwarding plane then the number of neighbours is increasing. A university campus could reasonably want to neighbour every switch to a redundant pair of control plane servers: that's very much the "data centre network" design of both Cisco and Juniper.

Related to this scaling problem is the triggering of the Hello timers. As you can see there's lots of slack. But operating systems will try hard to schedule these timer expiries to a thousandth of a second. Linux is good here, with some nice timer options which allow for a range of times to be given and which will coalesce the wakeups. That's important because it reduces average power consumption -- that is, the amount of heat we need to expell from the router's chassis.

As you can see, Linux really needs in-kernel Hello processing to scale. Then the user space routing process only runs upon a toplogy change. That's a lot better than user-space trying to process a few thousand neighbour's wound-down Hellos from various networking protocols. That's not too hard to do: all it needs is a new socket protocol per routing protocol (PROTO_TCP_BGP4 PROTO_ENET_ISIS, PROTO_OSPF2 and so on). These protocols pass along bytes from user space, but deal with the Hellos themselves. Upon a failure they close the socket or send a signal (differing protocols would want differing choices there). You use setsockopt() to modify the timers.

The timers for all of these protocol handlers should funnel thought a core, that way all of the timers can be coalesced whilst being handled in priority order when they trigger (working from the physical upwards avoids bloackholing).

We used to say "the computer is the network" but increasingly the "network is the computer" -- computers aren't simply are hosts with a dumb ethernet interface anymore. They run substantial interior networks between virtual machines, and they participate in the exterior network using features which were once used only by they network (VLANs, bonding, etc). That's only going to accelerate as the only sane way to do data centre networking is to have the host participate in the control plane of the network. So we end up with specialist features which were once only required on routers. But we shouldn't be surprised by that: Linux has spent a lot of time acquring features which were once only the concern of mainframes or of supercomputers.