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)

Are IPv6 addresses too small?

IPv4 addresses are running out. IPv6 seems to offer the promise of a vast, effectively limitless address space. However, is that true? Could it be that even IPv6 addresses are too limited in size to allow potential future routing problems to be tackled? Maybe, if we want scalable, efficient routing. How could that be though?

IPv4 addresses are all but exhausted, IANA having run out in 2011, APNIC shortly thereafter and RIPE in 2012.The idea is that we switch to IPv6, overcoming the obstacles to transition that have now been engineered into it (e.g. usually a completely unrelated address space from IPv4, so significantly hampering IPv6 from being able to make transparent use of existing IPv4 forwarding capabilities).

IPv6 addresses are 128 bits in length, compared to the 32 bits of IPv4. So in theory IPv6 provides a massive address space compared to IPv4, of 2128 addresses. Exactly how massive? Well, some have calculated that that is enough to assign an IPv6 address to every atom on the surface of the earth, and still have addresses to spare. If every IPv6 address was assigned to a node with just 512 bytes of memory, then some have calculated the system in total would require more energy than it would take to boil all the oceans on earth – presuming that system exists only as pure energy! So by those estimates, the IPv6 address space seems like it is so massive that we couldn’t possibly ever come close to using all of it, least not while we’re confined to earth.

Those estimates however assume the addresses are used as pure numbers with perfect efficiency. In reality this will not be the case. To make computer networking efficient we need to encode information into the structure of the addresses, particularly so when those networks become large. The lower, least-significant 64 bits of an IPv6 address are effectively reserved for use on local networks, to allow for auto-configuration of IPv6 addresses on ethernets. Changing this would be quite difficult. So IPv6 actuall;y offers only 64 bits to distinguish between different networks, and then a further 64 bits to distinguish between hosts on a given network. Further, of the upper, most-significant 64 bits (i.e. the “network prefix” portion of an IPv6 address), already at least the first, most-significant 3 bits are taken up to distinguish different blocks of IPv6 space. This means the global networking portion of the IPv6 address space only has about 61 bits available to it.

IPv4 and IPv6 BGP FIB sizes: # of prefixes on a logarithmic scale. Courtesy of Geoff Huston.

Why could this be a problem? Isn’t 61 bits more than enough to distinguish between networks globally (i.e., as on the Internet)? Well, that’s an interesting question. The global Internet routing tables have continued to grow at super-linear pace, as can be seen in the plot above (courtesy of Geoff Huston), with at least quadratic growth and possibly exponential modes of growth. IPv4 routing tables have continued to grow despite the exhaustion of the address-space, by means of de-aggregation. IPv6 routing tables are also growing fast, though from a much smaller base. There have been concerns over the years that this growth might one day become a problem, that router memory might not be able to cope with it, and so that could bottleneck Internet growth.

At present with BGP, every distinct network publishes its prefix globally and effectively every other network must keep a note of that. Hence, the Internet routing tables grow in direct proportion to the number of distinct networks in number of entries. As each entry uses an amount of memory in logarithmic proportion to the size of the network, the routing table growth is slightly faster than the size of the network in terms of memory. So as the Internet grows at a rapid pace, the amount of memory needed at each router grows even more rapidly.

If we wanted to tackle this routing table growth (and it’s not clear we need to), we would have to re-organise addressing and routing slightly. Schemes where routing table memory growth happens more slowly than growth of the network are possible. Hierarchical routing schemes existed before, and BGP even had support for hierarchical routing through CIDR and aggregation. However, as hierarchical routing could lead to very inefficient routing (packets taking very roundabout paths, compared to the shortest path), other than in carefully coördinated networks, it never gained traction for Internet routing, and support for aggregation has now been deprecated from BGP. Other schemes involving tunnelling and encapsulation are possible, but they suffer from similar, intrinsic inefficiencies.

A more promising scheme is Cowen Landmark Routing. This scheme guarantees both sub-linear growth in routing table sizes, relative to growth of the network and efficient routing. In this scheme, networks are associated with landmarks, and packet addresses contain the address of the landmark and the destination node. One problem with turning this into a practical routing system for the Internet is the addressing. How do you fit 2 network node identifiers into an IPv6 address? Currently organisations running networks are identified by AS numbers, which are now 32-bit. However, 2×32 bit = 64 bits, and there are no more than 61 bits available at present in IPv6 for inter-networking.

Generally, any routing scheme that seeks to address routing table growth is near certain to want to impose some kind of structure on the addressing in similar ways. The 64 bits of IPv6 doesn’t give much room to manoeuvre. Longer addresses or, perhaps better, flexible-length addresses, might have been better.

Are IPv6 addresses too short? Quite possibly, if we ever wish to try tackle routing table growth while retaining efficient routing.

Comments (4)

UK Cycling Culture

There’s things I find fascinatingly perverse about cycling culture in the UK, having experienced cycling in the Netherlands as a child. By cycling culture I mean both the culture and norms amongst those who regularly cycle in the UK (and the various sub-cultures), as well as in the general culture.

It struck me most the other week, when I cycled out of Glasgow early on the morning of the Pedal For Scotland event, out along the road leading back to Glasgow Green, where that event starts. There was a little more traffic than normal for a Sunday morning, because of the cars heading to PFS. It hit me that the UK is a country where, every weekend, people drive to cycle. They drive out to parks, country lanes, and sportives. They drive along roads they dislike cycling on, out to those roads to cycle on that are least quiet, if not free of cars. They drive out to sportives on open roads,  looking for a feeling of safety in numbers.

Clearly there is a great demand for cycling. Those ferrying their bicycles on their cars are just the tip of the iceberg – there are surely many more potential, casual cyclists who don’t care enough to invest in cycle racks, etc. Yet, the cycling culture, nay, the entire transport culture is so perverse here.

  • The letter of the law is that children must cycle in with 50 km/h (30 mph), even 65 km/h (40 mph), motor traffic on many roads, because there is no cycle-path provision and it is illegal for them to cycle on the footpath. Only children under the age of criminal responsibility can safely get away with this, as they will not be prosecuted. However, legally, little children are supposed to cycle in amongst fast motor traffic on such roads!
  • Even adults can feel uncomfortable cycling on these roads, and will cycle on the footpaths. The Scottish governments’ answer to this problem of a clear lack of safe cycling infrastructure? Run an ad campaign to tell such adults to grow up.
  • There is never any room for dedicated cycle paths, even though most towns and cities are criss-crossed by multi-lane roads.
  • At best, the cyclist gets either a useless little lane painted on the road that does nothing to protect them from motor traffic, but does bring them through the dangerous door-zone of parked cars; or the footpath gets designated “shared use”, bringing the cyclists into conflict with pedestrians instead, and having to cede priority at every little junction and property exit. The more experienced cyclists often ignore such useless infrastructure, with good reason.
  • A sub-culture of cyclists are derisory of any attempt to argue for quality dedicated cycling infrastructure.
  • A sub-culture of cyclists are afflicted by Stockholm Syndrome and believe in mandatory helmets for cyclists, even mandatory HiViz.
  • Organisers of low-risk cycling events often impose a requirement to wear helmets on participants, typically by justifying it as a requirement of their insurer (even when false, e.g. British Cycling non-race event insurance does not require helmet use), thus condoning the ongoing “dangerising” and de-normalisation of cycling in the UK.
  • Motorists who injure or kill cyclists are given derisory sentences, if they are even prosecuted and found guilty. Even motorists who deliberately knock down cyclists do not go to jail. If you want to murder someone in this country, use a car and claim “the sun was in my eyes” or “a bee came into my car”.

I could go on and on. It’s almost enough to make me despair.

Comments (3)

De Tour van Bauke: English subs

If you’re into bicycle racing, you might enjoy the “De Tour van Bauke” (“Bauke’s Tour”), a behind the scenes look at Team Belkin’s 2013 Tour de France campaign, by Kees Jongkind of the dutch NOS public service broadcaster.

It has a few fascinating insights, such as into the echelon stage where Saxo, OPQS and Belkin managed to split the field; managing egos within a team with several top riders; and generally some of the dynamics within a top WorldTour team. The film doesn’t spend much time on explaining the background, and does sort of assume you’re fairly familiar with how the TdF ’13 played out, and perhaps how the team had had to scramble over the winter before to find a new sponsor after Rabobank pulled out, succeeding in finding Belkin as title sponsor. If those assumptions are met, the documentary is very enjoyable.

I obviously can’t remove the original dutch sub-titles that are embedded in the video. So I’ve had to position the sub titles above, which means I’ve had to use the “Alpha Sub-Station” format, rather than the more common SRT format, as SRT does not support positioning. Ideally, NOS would prepare an English subtitle version, with the subtitles professionally rendered. I did contact someone at NOS to see if they’d be interested – they apparently have their own plans for further releases to non-Netherlands markets, but I didn’t get any specifics. I’d be more than glad to licence the subs back to NOS for web use for free, to say thanks for making “De Tour van Bauke” available on the web.

As some of the Belkin DSes have strong regional accents, I’ve sometimes used regional english words. E.g. in my mind, the english subtitles for Nico should be read with a strong Irish accent – think Sean Kelly 🙂 crossed with Mrs Doyle from Father Ted (“Go on, go on..”). I’ve also snuck in one or two Liggettisms for the TV commentary subtitles!

In order to use these subtitles you need a video player that supports “Alpha Sub-Station” format subtitles, such as VLC 

To watch it with VLC:

  1. Download the documentary from NOS. You have to save one of the following links to your computer, so you can watch it in VLC – watching in your browser probably wont work:
  2. Rename the downloaded video file to, e.g., tour_van_bauke.mp4
  3. Download the subtitles file from OpenSubtitles, and save it as, e.g., tour_van_bauke.ass to the same folder as the video.
  4. Open the video in VLC.

VLC should then automatically play the sub-titles. If it doesn’t go to the “Video” menu, then “Subtitles track”, then choose “Open file…” and manually locate and open the sub-titles file.

Feedback/corrections would be appreciated!


Comments (2)

My email to the NSA / GCHQ

My email to the NSA and GCHQ, inspired by Richard M. Stallman:

Date: Fri, 21 Jun 2013 22:07:11 +0100 (BST)
From: Paul Jakma <>
Subject: the enemy within

Blow up Obama, mustard gas attack whitehall, sarin gas army barracks,
procure ammonia for fertilizer bomb, samurai sword attack policeman. Glasgow
truck bomb.

Hallo dear GCHQ or NSA analyst, if you’re reading this perhaps you should
consider what is the greatest danger to our democratic, civil society: is it
the odd terrorist attack, or is it the Orwellian surveillance state you’re
helping to build and maintain? Is reading people’s email to be the legacy of
your life? Is it worth pondering for yourself the decision Snowden made?


Paul Jakma @pjakma Key ID: 64A2FF6A
Savage’s Law of Expediency:
You want it bad, you’ll get it bad.

Leave a Comment


You’re an amazing bag of bio-chemical reactions.

You have something in the order of a 1000 trillion cells. Of these, only a small fraction, 1/10th – or about 100 trillion – are actual human cells. The other 1000 trillion are mostly various kinds of bacteria, but also some micro-scopic, primitive eukaryotic”animals” like protozoa, and fungi such as yeasts. Many of these play a critical, symbiotic role in the functioning of your body, particularly in helping you digest your food. Others may not appear directly beneficial, but still their presence helps control the growth of less benign microbes, by out-competing them for food. These microbial cells make up 1 to 3% of your mass!

At some point early on in the evolution of life, some larger, single-celled organism managed to evolve that included some smaller, archaic bacteria and “farming” them for energy, possibly by the larger cell having “swallowed” the smaller cells. These archaic-bacteria components are called  mitochondria, and they can turn sugar into energy. They contain a number of tiny molecules , the ATP synthases, which spins around like a little motor, driven by protons, to help drive the final part of the sugar→energy conversion process!

These more complex, larger and higher-powered “eukaryote” cells, with their “farms” of symbiotic mitochondria became the basis for all animal life, from the single-celled protozoa, to moulds, to plants, and all the way to you. These mitochondria have their own DNA, and replicate themselves as and when their cells do. There are some exceptions, such as human sperm cells, which do not have any mitochondria, and so the mitochondria in your human cells generally came only from your mother, which came from her mother, etc.

You posses one of the most complex objects known on earth. The human brain. A circa 1.4 to 1.5 kg gelatinous, fatty mass of about 1.3 litres in volume. Our deceased close cousins, Homo Neanderthalensis, actually had a slightly larger brain than us, at 1.5 litres in volume. Your brain consumes a significant amount of your body’s energy, 20 to 25%, about 10 times more than the proportion of its mass to your body’s total mass. The energy your brain consumes is at least equivalent to the energy needed to power a 7 to 10W CFL or LED light bulb¹, 24×7. The brain is still a lot more efficient than any computer though, for what it does.

The human brain contains on the order of 100 billion special cells called neurons. Each of which receives inputs from other neurons through junctions called synapses on spindly arms called dendrites. Additionally a neuron can have an axon, a potentially very long nerve fibre, which can reach from the neuron to muscles, glands, or to other neurons. The longest axons in your body are in the neurons of your nervous system, running the length from the base of your spine to your toes! There are estimated to be an order of 100 trillion synapses in the human brain, for an average of thousands of connections per neuron. This would likely make the network in your brain at least an order of magnitude more complex than the entire Internet!

As if that wasn’t enough, you have a second “brain” in your abdomen, by your stomach – the enteric nervous system. It’s a lot simpler than the brain in your head, having only 100 million neurons or so, but that’s still a lot of neurons – comparable to the brains of lower mammals, at least in terms of number of neurons! The enteric nervous system has a number of functions, in particular co-ordinating the muscles of your gastric system.

So your body is this giant bag of cells, most of them not human, all of them working away and, mostly, co-operating in a huge variety of, often complex, ways. If you dig into the cells that are you, you’ll find even they contain a number of primitive cells within them. Sitting on top of this super-colony of cells is a brain, directing things at a high-level and using the equivalent of a super-internet to do so! With a 2nd mini-brain helping out lower in your body! You are a mobile mini-eco-system.

As if that wasn’t amazing enough, you are related to essentially all other life on this planet.  You are the direct descendent of some of the earliest life on this planet, if not the first. As is pretty much everything else on this planet. From the cats and dogs you might see on the street, and all other mammals, to the green plants and trees, to the black mould in your shower, or even bacterial slime you might find around a tap, you share some DNA with all of these – these are your cousins, to greater and lesser degrees. We are all bound together in the massive eco-system that is Earth. This eco-system is effectively all but closed, receiving only energy from the star it orbits – relative to which we hurtle through space at an average of  about 107000 km/h, or 30 Mm/s. Life, simple bacterial forms particularly, inhabit near every nook and cranny of it that we have managed to visit. Including places where we had perhaps expected to find none, such as in the greatest ocean depths, even deep underground.

Your continued existence depends greatly on many of these cousins of yours, both animal, plant and bacterial.

Many of the species of life on earth have quite specific needs of their local environment, and are quite sensitive to even small changes to it. However life overall on this planet has proven to be quite robust. Any individual species could easily die out, indeed in catastrophic changes many species could die out, but life tends to cling on in some form – particularly in simpler forms. Life is both precarious, from the point of view of any single species, and yet also robust overall.

Do not think your species is an exception.

When the processes that keep your body-eco-system working together stop, when your own cells cease to function as such, life will continue. Your many cousins and their descendants, maybe even some closely related or even direct descendants, will go on. Some of the bacterial cells that helped maintain you almost certainly will outlive you and perhaps even help maintain another body for a while. It is almost certain that much of the DNA you contain will continue to help build further life on earth, through these many cousins. The molecules and atoms you contain will be recycled, they will become part of the air, the sea, the earth. In time, they will be taken up by other life and become part of those plants and animals, perhaps even people. Your body-eco-system is but a small, transient, component of a much more massive eco-system that has been developing for billions of years, and may well continue to be around for billions to come.

As you wonder about the magnificence of all this, you might look up to the stars. All the atoms in your body were originally forged inside stars, other than the very lightest (hydrogen, which is very common in the universe and your body, helium, and very small proportions of lithium and beryllium). You are, literally, made of star-dust. Complex organic compounds, precursors to life, seem to occur quite naturally, and we know they’re floating around on asteroids in the Solar system, and so likely they float around a great proportion of other star systems too. There are in the order of 100 billion visible galaxies, with a galaxy typically having in the order of 100 billion stars, meaning there are in the order of 100 billion × 100 billion, or 1022 = 10,000,000,000,000,000,000,000 stars out there. Even if the chance of life arising were a tiny 1 in a billion, that’d still mean that 1013 = 10,000,000,000,000 of the visible star systems had life on them. It’s very likely that the Universe is full of at least simple microbial life.

Life is amazing, and it is precious.

1. Base calorific requirement of, say, 1200 kcal / day = 58W, 20% = 11W.

Comments (1)

RBS and their bizarre new 3rd party credit check authentication system

Update: RBS have responded. The security issues apparently were some kind of system failure. I should have already been authenticated, using RBS specific questions, by the automated IVR you go through when you call – and I had gone through this. However, on my call, the system had lost this information somehow (there were computer issues on the day) and it wasn’t available to the  agent. Normally, the credit check based public-data questions should augment the RBS authentication procedures and provide an extra layer of identity verification. They are not normally meant to be the only form of identity verification, as appeared to happen in my call. With regard to the issue of that credit check data being completely incorrect, RBS have offered to pay any costs incurred in dealing with the credit check agencies.

RBS Card Services seem to have brought in some kind of new system to verify your identity when you phone them up. They girl said it’s provided by  3rd party credit checking agencies. They ask you questions that are based on quite public information – which is daft, as RBS hold far more personal, private data on me. Worse, in my case, it seems this information is wrong. None of the questions had any answers that had anything to do with me.

So RBS apparently don’t trust the security of the personal data they hold on me, instead trust external companies to identify me using public information. That doesn’t sound like competent or acceptable security to me.

Below is my letter to them, which will be sent tomorrow hopefully.

Read the rest of this entry »

Leave a Comment

« Newer Posts · Older Posts »
%d bloggers like this: