BGP Multi-Exit-Discriminator

The following is an extract from a recently submitted update of mine to the Quagga documentation. Republished here under the licence of the Quagga documentation1:

The BGP MED (Multi_Exit_Discriminator) attribute has properties which can cause subtle convergence problems in BGP. These properties and problems have proven to be hard to understand, at least historically, and may still not be widely understood. The following attempts to collect together and present what is known about MED, to help operators and Quagga users in designing and configuring their networks.

Read the rest of this entry »

Leave a Comment

SRAMs’ wireless bicycle gear shifting: Protocol analysis

It’s pretty rare that I get to blog about both cycling and networking. Hard to see how those two topics share any common ground. That’s about to change as SRAM, the American bicycle component maker, appear to have a wireless gear shifting system in advanced testing.

The system was seen at the Tour of California earlier this year, though disguised with decoy wires to make it seem like a wired, electronic system. It was also spotted recently at the USA Pro Cycling Challenge, now without the decoy wires.

You may ask, why on earth would bicycles need radio-controlled gear shifting? Which is a good question. One benefit seems to be that the wireless shifting weighs slightly less than either a conventional mechanically actuated system, or even a wired electrical one. However, that benefit surely will be very marginal. The lack of cabling may make installation and maintenance easier too. Perhaps. Another possibility is that SRAM were behind Shimano and Campagnolo in delivering an electronically controlled shifting system, and SRAM decided that going wireless would help differentiate their product from the other two. Who knows!

As someone who specialises in network protocols, I’m curious to know how it might work in terms of the messages sent, logical layers of the radio protocol, and how the different components communicate to co-ordinate shifting.

There are obvious questions: Is it secure? Are there any limitations? Will it be reliable? The brief answers to which are, yes it should be secure; yes, there seem to be some limitations over traditional shifting systems; and probably it should be quite reliable, however when it isn’t there could be quite strange behaviour.

The rest of this blog will go into the details of how this system works at a network protocol level, as gleaned from SRAMs’ patent on electronic shifting. It will look at the ramifications of the design decisions made, and also how this could affect the operation of the system in extreme circumstances where messages are lost due to, e.g., radio noise.

The quick summary:

The SRAM system, at least as described in their patent, has a number of limitations that are a consequence of the network protocol:

  • It can not support more than two front chain rings
  • It can not support intentional simultaneous shifting of front and rear dérailleurs

While radio noise is unlikely to be a significant problem, outside of deliberate interference or some unusual locations, should the system be affected by continued noise it may manifest itself as:

  • Missed rear shifts followed by an overshift of the rear
  • Overshifting rear shift, after an apparently normal front shift
  • Combined unintentional shift of both dérailleurs, on an intended front shift

The system should though be relatively robust against interference, due to its use of a low-bitrate network layer. It should be secure, due to use of strong encryption, so that only those with physical access to the bicycle (e.g. the rider) can control the gear system.

The system that goes into production may differ from the system described in SRAMs’ patent, and some or all of of these limitations may not apply to it. We won’t know till it is released.

Update 20150213: I’ve just noticed the very bottom of the SRAM patent mentions that the dérailleurs can transmit their current gear position. The patent mentions this might be used to allow the front mech to adjust its trim according to which gear the rear dérailleur is in. The patent does not mention this being used in the control protocol though, e.g. to have the dérailleurs ACK the shifter messages which could make the protocol more robust to missed messages. However, the hardware described in the patent is at least capable of this, and production systems could be enhanced this way. There may still be issues left in how the system appears to allow for shifting to be distributed over two shifters, I’d need to go back and re-check.

Read the rest of this entry »

Comments (10)

Graph distance using matrix multiplication in Octave

If A is a matrix of positive edge weights between nodes in a graph (from 0 to infinity), then power-iteration through multiplication of that matrix in the {R,min,plus} semi-ring will converge on the distances of the shortest-paths in that graph. For reference (my own mostly), this blog entry gives the GNU Octave code for it and an example.

Read the rest of this entry »

Leave a Comment

Transport Scotland and its attitude to active transport spending

Transport Scotland had planned to spend £27m on low-carbon, sustainable and active transport, of which cycling is but a part, over  3 years (I presume roughly from 2013 to 2015?). Which makes the annual budget be £9m.

Now, if you were about to hand out £424k of that £9m – just about 5% of the entire annual budget for low-carbon, sustainable, and active transport – you’d do your homework on it, wouldn’t you? You might want a detailed proposal, with goals and metrics, perhaps? You’d want to see some detailed proposals for what the campaign might cover, no? You’d possibly need some back and forth to give feedback and work out the details, which’d generate minutes and emails, right? Surely?

Not if you’re Transport Scotland. No. Transport Scotland, it seems, will hand out £424k – again that’s pretty much 5% of the entire annual, active transport budget – based on nothing more than barely 2-pages of a proposal. A proposal with the scantest of details, and which couldn’t have taken more than 30 minutes to write up. That’s all it takes to get £424k from Transport Scotland, at least in terms of anything that leaves a record, apparently.

This is Transport Scotland’s official stance, made in response to my Freedom of Information request about the commissioning of the Nice Way Code, which they re-iterated to the Scottish Information Commissioner, after I appealed on grounds of incredulity.

I think this stinks of a somewhat cavalier, uncaring, and dismissive attitude both to public money, and to active transport policy in Scotland. I would expect Transport Scotland to be a lot more careful with 5% of their budget for active transport.

I think that’s fairly scandalous.

Leave a Comment

The surprising centres of the Internet

A previous post, on “Barabási – Albert preferential attachment and the Internet“, gave a plot of  the Internet, as a sparsity map of its regular adjacency matrix, with the axes ordered by each ASes  eigencentrality:

Sparsity plot of the Internet adjacency matrix, with the nodes ordered by their Eigencentrality ranking.

Sparsity plot of the Internet adjacency matrix, for the UCLA IRL 2013-06 data-set, with the nodes ordered by their Eigencentrality ranking.

Each connection in the BGP AS graph is represented as a dot, connecting the AS on the one axis to the AS on the other. As the BGP AS graph is undirected, the plot ends up symmetric. The top-right corner of this plot shows that the most highly-ranked ASes are very densely interconnected. The distinct outline probably is indicative (characteristic?) of a tree-like hierarchy in the data.

Who are these top-ranked ASes though? Are they large, well-known telecommunications companies? The answer might be surprising.

Read the rest of this entry »

Leave a Comment

Code and error handling strategies and FSMs

We’ve had a discussion in the office on and off over a few days about error handling in programmes. Neither my office mate nor I are completely happy with what’s available out there. The state of the art in imperative/OO languages appears to be stuck at exceptions. The new Go programming language eschews them, essentially going back to having a named parameter for returning errors – which needs to be checked for.

The essential problem in programming is, of course, that code may follow a number of paths. Some of those paths are, at some level, the most common or desired paths (often, just 1 path). Other paths may be taken, e.g. because a resource was unavailable or because the requested action was inappropriate or unreasonable in some way. Of those other paths, some may still be reasonably commonly taken (e.g. a file not existing) and/or recoverable in some way. Other paths may be exceptional in some way such that it is unlikely  to recover from having taken them. These paths converge at function/procedure call nodes, where they have to be dispatched to direct programme flow onward to the appropriate further path.

My own sense is that path selection syntax/support in programming languages tends to divide all error/return handling into 1 of those 3 cases.

  1. The primary path(s)
  2. Recoverable error paths
  3. Unrecoverable error paths

What then are the ways to handle these cases?  In languages such as C, errors generally must be handled after each function call, acting on them according to return value or a modified parameter. There are of course other ways, such as signals and exceptions.

There is also another way, which I see much less often, but which has certain benefits, which is to use Finite State Machines (FSMs) to give objects an idempotent error state. This allows control-flow in calling code to bunch together operations without having to worry about errors, as the error-handling can be done later, separately.

This blog tries to go over these methods, and their benefits and pitfalls. I’d also be really interested to hear about other error-handling strategies, especially better ones! :)

Read the rest of this entry »

Comments (3)

Barabási – Albert preferential attachment and the Internet

The Barabási – Albert paper “Emergence of Scaling in Random Networks” helped popularise the preferential-attachment model of graphs, and its relevance to a number of real-world graphs. There’s a small, somewhat trivial tweak to that model that can be made which never the less changes its characteristics slightly, with the result possibly being more relevant to the BGP AS graph. GNU Octave and Java implementations are given for the original BA-model and the tweak. The tweak can also potentially improve performance of vectorised implementations, such as Octave/Matlab.

Read the rest of this entry »

Comments (1)

Older Posts »

Get every new post delivered to your Inbox.

%d bloggers like this: