Mashed Articles

When we need to select an algorithm for a particular purpose, we should pay attention to its runtime characteristics: how fast it is; how much memory it uses; whether there’s a worst case for the algorithm’s execution speed; and so on. All these answers are expressed with the big-Oh notation, which I’ll describe later.

A common abstract data structure that’s used all the time in programming is the dictionary or associative array, which is sometimes known as a map. I call it an abstract structure because it can be implemented in myriad different ways, but it always has a specific interface. We’ll use the dictionary to investigate the runtime efficiency of various algorithms that can be used to implement it.

OK, so it’s not this kind of dictionary. We’re referring to a digital one. An associative array.

But first, a definition: a dictionary is a structure that holds name-value pairs. A name-value pair is an object that has a name – that’s used both to describe its value and as a key to find it – and a value, which can be anything at all. The classic example is a real-world dictionary, where the name is a word and its value is the word’s definition. However, don’t limit yourself to assuming the name is always some kind of text string. In reality, names can be integer values, bit strings, 128-bit GUIDs, dates or anything at all. That said, it’s helpful to assume that they’re text strings for now.

The dictionary has various operations that define its external interface. There’s the ‘Create’ operation, which creates a new dictionary, and the ‘Destroy’ operation, which releases any resources the dictionary is using and destroys the structure. A dictionary can only be used after ‘Create’ has been called, and once ‘Destroy’ is executed, it no longer exists. Since these operations are only used once each per dictionary, they won’t have much effect on the overall runtime and so we won’t discuss them any further.

When given a name, ‘Find’ will search for the name-value pair that matches and return its value or an error if the name is not found. ‘Exists’ will do the same, except it will merely return true or false according to whether the name is present or not. Since they’re virtually identical, apart from what they return, we’ll ignore ‘Find’ from now on.

Finally we have ‘Insert’ and ‘Delete’, which do what you’d expect: add a new name-value pair to the dictionary (returning an error if the name already exists), and remove the name-value pair that matches a given name, respectively. In general, ‘Delete’ won’t return an error if the name is not found, and sometimes ‘Insert’ will merely replace the value if the name already exists.

Now that we have our abstract data structure, let’s investigate first how to implement it and second analyse the efficiency of our implementations. We’ll look at a total of four implementations.

Name-value pairs

The first implementation is the most obvious: use an array of name-value pairs. ‘Exists’ is the first operation to think about. In essence, to see whether the given name is present, you would check every pair in the dictionary sequentially and stop when you found it. If the given name isn’t present, you would compare the name of every name-value pair to the given name. The more pairs there are, the longer it would take, but you can be even more precise than that. Suppose there were N pairs in the dictionary and each comparison took the same (constant) length of time – say t. Then it would take tN time units to find out the given name wasn’t present. Another way of putting this is that the time taken for the nonexistence check is proportional to N. In computer science, without going into too much rigorous mathematics, we say the runtime efficiency is O(N), pronounced ‘big-Oh of N’, although you can read it as ‘is proportional to N’.

So if it took so many seconds to find out that a given name wasn’t in a dictionary of 1,000 pairs, it would take twice as long for a dictionary of 2,000 pairs, and 10 times as long for a dictionary of 10,000 pairs.

What if the given name was in the dictionary? What could we say then? Well, it could be that the matching pair was the first item checked. In that scenario, we say the best case efficiency for ‘Exists’ is O(1), which you read as ‘is constant’ (in other words, it doesn’t depend at all on the number of items in the dictionary). But, of course, for that to happen, you’d have to be extremely lucky. You could be completely unlucky and be looking for the final item. Here the worst case efficiency is O(N) – the time taken would be proportional to the number of items in the dictionary.

On average, though, if you searched for every name in the dictionary, the efficiency would be O(N/2). Now comes the fun bit with big-Oh notation: since it essentially means ‘is proportional to’, you can take the 1/2 (a constant) out of the parentheses into the implied proportionality constant and say that the efficiency is O(N). We say that searching through the dictionary-as-array is O(N): twice as many items, twice as long.

‘Insert’ is simple: we add the new name-value pair to the end of the array, a constant O(1) operation. Hold on there though – we first have to search the array to find out if the name is already present or not. ‘Insert’ then degenerates to O(N), just like ‘Exists’. We get no benefits at all from the constant, quick, add-it-to-the-end operation; we still have to search.

‘Delete’, as I’m sure you can see, is at least O(N) as well – we have to do the search. There’s something else about ‘Delete’ that we have to take into account: we have to physically remove the name-value pair from the array. The simplest way of doing this is to simply take the final pair in the array and put it in the slot vacated by the pair that was removed: a constant O(1) operation. So, overall, ‘Delete’ is O(N); the search time will swamp the move-an-item time.

Sorted pairs

Let’s move on to the second implementation. This one is again an array, except this time we maintain the pairs in sorted order. This has the assumed requirement that the names are sortable and that, given any two unequal names, we can say that the first is smaller or greater than the second.

We’ll start off by analysing ‘Exists’ again. The array is in sorted order, so we can use binary search to try and find the name-value pair that matches. With binary search, we look at the middle item in the array. If it’s the one we want, we stop. If the one we want is less than this middle item, we know that, if it’s present at all, it’ll be in the first half of the array. If the one we want is greater than the middle item, we know it will be in the second half. We repeat this process with the half array we selected. We’ll either find the item immediately again, or we’ll have reduced the number of items we have to search to a quarter of the array. Ditto the next step, except we reduce the space we have to search to an eighth of the original array. And so on.

Again, consider the doesn’t-exist case. Say we start out with an array with 1,023 items. After one step, we’ll have discarded one item and will have identified a subarray of 511 items for the next step. After this next step, we’ll have reduced the search space to 255 items, and so on. At the 10th step we’ll have a tiny array of just one item, which we can easily compare. So all in all, we’ll have made 10 comparisons to find out that the given name is not present. What’s so special about 10? Well, it’s the logarithm to base two of 1024 (that is, 2ˆ10 = 1024). Again, without being too rigorous mathematically, we say ‘Exists’ is O(logN) when the name isn’t present.

Think of O(logN) this way: if it takes a particular length of time to find out that a given name isn’t present in a sorted array of 1,000 items, it will only take twice as long for an array of 1,000,000 items. If you square the number of items, you double the time taken. This is an extremely significant result, showing the importance of binary search. What if the given name is present? We can make the same analysis as before: best case is O(1), worst case is going to be the same as not finding it: O(logN), and so we say that, overall, ‘Exists’ is O(logN).

What about ‘Insert’ and ‘Delete’? Again, we have to search for the name, so it would seem that they’re both O(logN). But this time, consider what we must do to add (or remove) the name-value pair. For ‘Insert’, we have to make a hole in the array to put the new pair in, shuffling all the items greater than it along by one. For ‘Delete’, we have to shuffle the remaining pairs to close up the hole vacated by the removed pair. If we’re lucky, in both cases, we don’t have to move any items (that is, best case is O(1)); if we’re unlucky we have to move all of the remaining pairs (that is, worst case is O(N)). On average, it’s O(N) for all the shuffling we need to do. Since O(N) is bigger than O(logN) – for very large values of N the (in)efficiency of the moving of the items will swamp the efficiency of the search – we ignore the smaller proportionality and just use the larger one. We say ‘Insert’ and ‘Delete’ are both O(N).

Hash table

Now for the next implementation: the hash table. Without going into full detail, we have an array as the basic data structure. Again, we analyse ‘Exists’ first. To find an item in a hash table, we hash the given name to produce an index into the array. The hash is produced by a randomising type function that takes the name, chops it up and combines the parts to produce an integer value. That integer value is then reduced to a possible array index value by use of the mod operator. The hash function is designed so that similar names produce very different hash values.

Best case is that ‘Exists’ is O(1). That is, we create the hash for the given name, convert it to an index, go to that element in the array, and the pair we need is there and matches. No matter how many items are in the array, that process is constant. (Actually, the hash function is usually O(k) where k is the length of the name, but we’re ignoring that for now.)

What about worst case? Well, in practice we’ll find that many names will hash to the same array index value. These are called collisions and we need to implement a collision resolution strategy to deal with them. The simplest is known as chaining, where we chain the name-value pairs as, say, a linked list at each array element. In this case, once we’ve calculated the index, we then do a sequential search through the chain at that index.

To ensure that the chain is never too long, hash tables grow themselves periodically when their load factor (the number of pairs present divided by the number of array elements) reaches a particular value. To do this, a new array is created, and all the pairs are rehashed and inserted into the new array. This ensures that chains never grow beyond a few items, say five or 10. Since this isn’t dependent on the total number of items, it’s still constant and we say ‘Exists’ in a hash table is O(1) on average.

‘Insert’ is a more difficult operation to analyse. On the face of it, it’s O(1) – both the ‘Search’ and ‘Add’ functions are constant time operations in general – but every now and then, a reorganisation will take place on an insertion operation. In general, hash tables are written such that they double in size when they grow. This is a O(N) operation, but we can amortise it over all previous insertion operations, so that, overall, ‘Insert’ remains O(1). Best case then is O(1), worst case is O(N), amortised case is O(1).

The same types of arguments can be made about ‘Delete’, although in general we tend not to shrink a hash table anywhere near as often as we make it bigger. ‘Delete’ is then O(1), meaning that the amortised use of a hash table over all its operations is O(1). There is, of course, still that warning that every now and then you will hit the O(N) worst case on an insertion.

Binary tree

The next data structure we can use is a balanced binary search tree, such as a red-black tree. This, like the sorted array version, makes the assumption that names can be sorted.

In a binary tree, the efficiency of search operations is O(d), where d is the maximum depth of the tree (the number of levels from the root of the tree to the furthest leaf). Since a perfectly balanced binary search tree is equivalent to binary search on a sorted array (every link you decide to follow will enable you to ignore a whole chunk of the tree), ‘Exists’ is on average O(logN). Best case is still O(1), but what about worst case? That depends on the algorithm used to balance the binary tree. Balancing is never perfect but, using red-black trees as an example, we can prove that they’re constructed such that the longest path is a maximum of twice the length of the shortest path. If you like, O(2logN). Since 2 is a constant, we can take it out, making red-black trees O(logN) in the worst case for ‘Exists’.

For ‘Insert’ and ‘Delete’, there’s a lot of mathematics that can prove that they’re both O(logN) as well. In essence, the search is O(logN), and the addition of the new node or removal of the old node is O(1) on average.

So, overall, a red-black tree is O(logN) in all its operations. Perhaps more importantly, it has guaranteed O(logN) time even in the worst case. This means that some people will prefer to use a red-black tree for their dictionary instead of a hash table because they don’t want to hit the possibility of O(N) insertion.

Figure 1: Graphing some common big-Oh expressions (O(N^2) is cut off so we can see the others).

From this discussion, you should now have a basic understanding of how to read and understand big-Oh expressions and how to evaluate algorithms and data structures based on them. Figure 1, above, illustrates the runtime for various common big-Oh expressions.

Radix trees

Radix trees offer a further data structure that can be used for a dictionary. A radix tree stores prefixes to keys rather than complete keys in its nodes, and each node can have many children. A key is then found as a complete path through the tree from root to leaf – at each step down the tree, you compare another small part of the name to the next node.

Figure 2, below, shows an example radix tree storing a small set of words. In searching for ‘hostess’, we follow the left link from the root, matching host, then follow the middle link matching the ‘e’ and finally matching the ‘ss’ in the right node.
Unlike the other data structures we’ve looked at, the efficiency of a radix tree doesn’t depend on the number of name-value pairs, but instead on the length of the keys. All operations are essentially O(k), where k is the maximum name length in the radix tree. This can be greater than the balanced binary tree’s O(logN), for example, but in practice we find that the comparisons needed in a binary tree are also significant, so the radix tree can be a viable alternative.

Figure 2: A small radix tree, using middle dot to indicate end of word.

Ternary trees

Back in issue 282, I cited ternary search trees as a strong candidate for the data structure behind a dictionary. Ternary trees, like radix trees, have a runtime efficiency that’s dictated by the length of the keys rather than their number, but are much easier to implement. Ternary search trees and radix trees also have a further benefit: using them means you can easily produce a sorted list of names in the dictionary, as well as produce a prefix list (a list of names with a particular prefix).

Profiling

All of the efficiency results quoted in this article are theoretical. They are all of the form ‘for large values of N the efficiency is proportional to some expression in N’, but make no mention of the size of the constant of proportionality. Therefore, when deciding on which data structure to use in your dictionary, you should profile actual code running on your actual data. It’s pointless worrying, for example, about the efficiency of millions of items in a dictionary when you’ll only have 100.

Is your Windows 7 machine grinding to a halt already? Don’t despair as we’ll explain how to restore brand-new PC performance-and then go faster still.

There’s a lot to like about Windows 7, not least its many improvements over Vista: the new OS is faster, less demanding on resources, has better designed security and contains many new productivity-boosting features.

If you were an early Windows 7 adopter, though, you may already have noticed that one old problem still remains. The more you use your PC, adding and removing applications, the more junk builds up throughout your system, and the slower and more unstable it eventually becomes. You need to treat the problem, detoxing your PC on a regular basis to remove the leftovers – but how, exactly? Which areas of Windows 7 are most susceptible to this gradual degradation? Are there any tools or benchmarks you can use to reveal problem areas? How much can all this clutter slow you down, anyway, and what’s the best way to remove it all and restore your system to its optimum performance?

As we researched this article, one point was clear. Windows 7 is very different internally to Windows XP, and we couldn’t simply assume that old tricks, like optimising services, would work in the same way. What we needed to do was design a test, something that would reveal exactly why Windows 7 systems slowed down over time, and help uncover the best way to restore that initial new PC performance. And so that’s exactly what we did.

Designing the test

We started our trial by obtaining a powerful new 3XS Intel X58 Core i7 PC from Scan Computers. The machine featured a quad-core Intel Core i7 920 (which was overclocked by 20 per cent), 6MB of RAM and a speedy SATA 300 Samsung hard drive. It was an excellent performer that we knew wouldn’t choke unless it was faced with a set of major performance problems.

When the 3XS PC arrived, we installed the latest Windows 7 (Ultimate Edition, 32-bit) and driver updates and then set about establishing baseline measurements of our PC’s performance.

The best Windows boot time – which we’re defining as the time that elapses between the ‘Starting Windows’ message and the desktop appearing – was 22 seconds. Seeing the desktop means nothing if you can’t use it, so we also measured the time between the ‘Starting Windows’ message appearing and the point that we were able to launch IE and have it display our Google homepage 
(28 seconds).

We also used Task Manager to collect data on free memory and system activity (processes, threads, and so on). Finally we checked how long it took to launch apps, including Firefox and Outlook (both around four seconds).

With the performance of our clean system safely defined, we set about abusing it. We installed Windows Live tools, iTunes, Adobe Reader, browsers, antivirus apps, Microsoft Office, DVD-burning suites, video-editing tools, a large Outlook inbox, hundreds of fonts and more. We accepted every extra that was on offer, then reinstalled and updated the apps before moving plenty of files around to ensure hard drive fragmentation.

Installing apps like iTunes can slow down your system performance in several different ways.

And what did this do to the benchmarks? The plain Windows boot time increased by around a third, from 22 to 30 seconds. Our system was unusable after that for a long time, though, with IE not displaying Google for 140 seconds. Task Manager showed that system activity had more than doubled. Outlook now took five times as long to launch (21 seconds), and shutdown time increased by 50 per cent to 18 seconds.

So even a powerhouse like our 3XS system can be seriously affected by clutter. Now our really important tests began: discovering how to reverse this slowdown.

Defrag options

The hard drive is a big bottleneck on most PCs, and defragging has traditionally been one way to boost performance. Windows 7’s own defrag tool completed the task in a little over 20 minutes, confidently reporting that there was now 0 per cent fragmentation. But this had little effect on our PC, shaving one second off boot time and leaving other benchmarks unaffected. We weren’t convinced, and ran Auslogics Disk Defrag immediately afterwards. This produced some interesting information: it thought our drive was still 16 per cent fragmented. We told the program to optimise our file layout (go to ‘Settings | Program Settings | Algorithms | Move system files to the beginning of the disk’) and set it to work.

Auslogics Disk Defrag optimised the layout of files on your hard drive and gave a real speed improvement as a result.

This delivered real benefits. Boot time fell from 29 to 26 seconds; IE was usable after 107 seconds, a 23 per cent improvement; and launch time for Outlook fell by a third. We can’t guarantee you’ll see similar results, as every defrag situation is different, but it’s clear that Windows 7’s defrag tool alone won’t necessarily do the job. We advise you click Start, type defrag, click ‘Disk Defragmenter’ and make sure that scheduled defrags are turned off for the moment. Then install Auslogics Disk Defrag, turn on the option to relocate your system files, click ‘Settings | Program Settings | Schedule’ and set it to run every few days to keep your drive running optimally.

At your service

A near two-minute wait before we could access the web was far too long. To cut this down we needed to reduce the work that Windows had to do during the boot process, and one effective way to do this was to work on our Windows services. Launching the Services applet (‘services.msc’) revealed the many changes that could be made.

For instance, the Distributed Link Tracking Client maintains links between NTFS files across a network and is started by default. We don’t use the service, though, and you probably don’t either: double-clicking it and setting the Startup Type to ‘Disabled’ will turn it off. IP Helper is similarly pointless unless you have access to an IP6 network, and the Windows Media Player Network Sharing and Media Center Extender services can go unless you’re using them to share your music and videos.

Other services can be configured to start with a delay, giving priority to other tasks and helping your PC to become usable more quickly. The Background Intelligent Transfer Service is important when downloading Windows Updates, but it doesn’t have to be available when you start your PC. Double-click this and set its Startup Type to ‘Automatic (Delayed Start)’. Try the same with Disk Defragmenter, Windows Backup, Windows Search and Windows Update.

We noticed many unnecessary third-party services. Installing Nero 9 got us a Nero BackItUp Scheduler 4.0 service, for example; a LightScribe service assists when labelling discs; and a Visual Studio 2008 Remote Debugger had appeared from somewhere. We weren’t using any of these, so we disabled them all.

Many more could safely have their start-up type set to ‘Automatic (Delayed Start)’: Apple Mobile Device (bundled with iTunes), seven SQL Server services and five from VMware (part of VMware Workstation) all got this treatment. (Don’t choose anything security-related, though: vital services relating to firewalls or antivirus tools must be allowed to start as quickly as possible.)

These changes worked well, cutting our raw boot time from 26 to 24 seconds, while the ‘IE-usable’ time plummeted from 107 to 81 seconds: a significant improvement. But there was more to come.

Startup simplifications

Filling up a PC with numerous start-up programs will really slow it down, yet software authors continue to do this by default, so it’s a good idea to prune your start-up tasks on a regular basis.

Start by quickly browsing your ‘Start | All Programs’ menu. Is there anything you no longer need? Uninstall it now.

Next, we launched msconfig on our test PC, clicked the Startup tab and found 29 programs listed, many of them unnecessary. QuickTime, iTunes, Adobe Reader, Adobe Acrobat, Orbit Downloader, PowerDVD and RealPlayer are all very useful tools, but we didn’t want any of them to launch at boot time.

Other applications install some components that may or may not be useful to you. GoogleToolbarNotifier protects your Google toolbar search settings from unauthorised changes, for instance: that might be handy in some cases, but you may already have antivirus software that does something similar. Magix Movie Editor had added an application called Trayserver that appeared to be unnecessary, and our Cyberlink software had installed a host of tools that seemed less than essential, including ‘cyberlink brs’ (something to do with Blu-ray, apparently), Cyberlink MediaLibrary Service, the Language Application, the StartMen Application and the MUI StartMenu Application.

There may be a few redundant start-up programs that have been there since your PC arrived. Ours included LightScribe, a disc-labelling tool that we weren’t using, and CTXfiHlp, a Creative tool that apparently assists with providing Help functionality, but as we’ve yet to need that, the program felt like something we could do without. Another we found was LG Firmware Update, which checks online for new DVD drive firmware. That’s handy, but we don’t need to run it every boot. However, if you turn this off, make sure that you run it manually regularly.

A program to check for DVD firmware updates is useful, but you don’t need to run it at every boot. Disable this to save some time.

The precise results of all this tweaking will depend on how your PC is configured, but we saw immediate benefits. There was less disk thrashing at boot time, IE was now usable in only 71 seconds, and we’d freed up more than 100MB of RAM for the rest of our system.

Optimise your apps

We’ve concentrated on cleaning up Windows clutter, but your apps can also collect pointless add-ons.

Take Internet Explorer, for instance. While installing software, we accepted every offer of a shiny new IE add-on, with the result being that we now had four extra toolbars. Clicking ‘Tools | Manage Add-ons’ and disabling these freed up a surprisingly high 28 to 36MB of RAM, cut four seconds off the time it took for IE to load and then shaved half a second off every subsequent relaunch.

Typical Microsoft inefficiency? Apparently not. We had also accumulated eight Firefox extensions – AdBlock Plus, DownloadThemAll and so on – and uninstalling those halved the browser’s relaunch time and saved us around 26MB of RAM. So by all means keep the extensions you use, but remember that they come at a price – get rid of any that are surplus to requirements.

It’s a similar story with Microsoft Office. Outlook 2007, for instance, comes with many unnecessary add-ons, and programs like iTunes will install more (without even asking). Disabling all but the key search add-on saved 19MB of RAM on our test system (see the ‘Optimising Outlook’ box for the details), and while the initial launch appeared little different, subsequent launches now required only around 0.4 seconds. Clear unwanted emails out of your inbox for a further speed boost, then check Word, Excel and other Office components for further unnecessary add-ons (though don’t remove anything unless you’re sure you don’t need it).

Clean up your system

Congratulations, you’ve done the hard work – it’s time to clean up. Click Start, type cleanmgr and press [Enter] to launch Disk Cleanup. Follow the instructions and clean up as much of the junk that it finds as you can.

You can get more thorough clean-up help from a tool like CCleaner. It’s not a magic solution – we tried it, and cleaning our Registry made no difference at all to any benchmarks – but it does give you a central place to clean up your browser’s temporary files. That really did help, cutting another five seconds off the time it took IE to load and become usable.

After one further defrag to take advantage of our additional free hard drive space, that was it. So what had our efforts achieved?

Boot time, originally 22 seconds, had initially risen to 30, but we’d brought it back down to 24. The time it took IE to load and display Google, first 28 and at its height a horrible 140 seconds, was now 35.

Initial launch times for Outlook and Firefox were 25 per cent faster. Task Manager showed that system activity had fallen by 30 per cent. We had 300MB more RAM available, and our applications had been tuned to require less than they previously did.

Our work had got us close to the goal of brand-new PC performance. Now it was time to take the next step and make our system go faster than it had ever gone before.

No crime, no lag, no malware: 2020′s internet sounds like heaven. PC Plus checks out its foundations.

Safe, secure and speedy: that’s the internet of 2020. In a decade’s time, the web will be a very different place. There will be no crime, no malware and no fake online banking sites. Latency won’t be a problem. High-definition video will be smooth, and buffering will be a distant, nightmarish memory.

And that’s not all. The internet will have grown dramatically, making room for a new generation of connected devices: cars, phones, TVs, everything. Super-fast speeds are the rule, not the exception. To borrow a phrase, it just works.

At least, that’s what we hope the web will be like. To make it happen, engineers merely need to rethink the way the internet works and change pretty much everything. What could be simpler? Some big changes are already in progress. The explosion of internet-
enabled devices means that we’re running out of IP addresses even more quickly than expected: RIPE NCC’s Managing Director Axel Pawlik noted in January that the pool of unassigned IPv4 addresses would run out as early as 2011. But the move to IPv6, which can handle around “a trillion trillion trillion” addresses – 3.4×1038 if you’re feeling pedantic – is largely a software, not hardware, issue. “In most cases it’s very easy to reprogram connectivity software on a chip to ensure a device is IPv6 compatible,” Pawlik says.

But things aren’t progressing as straightforwardly as you would think. “Despite the simplicity of ensuring compatibility, widespread IPv6 take-up has so far been slow, and many of the best known digital devices available today, including the iPhone, do not yet support the next generation of IP addressing,” warns Pawlik. That lack of urgency is disappearing fast, with big names like Google implementing IPv6 support, router firms embracing the new system and new operating systems – including Windows and OS X – supporting it.

If we’re late embracing IPv6, the internet won’t grind to a halt – existing IP addresses will keep working – but as the European Commission reports, “the growth and also the capacity for innovation in IP-based networks would be hindered”. The EU is pushing IPv6 hard, and it expects European ISPs and “the top 100 European sites” to be IPv6-enabled this year.

As a happy by-product of IPv6, widespread adoption will make the internet more secure too. The IPsec security protocol is a compulsory part of IPv6, which means all IPv6 communications can be encrypted and authenticated.

Route masters

We’re using the internet in ways its creators couldn’t possibly have imagined, from the rise of video to the sheer number of connected devices. We’re constantly pushing the internet’s capacity, stability and security, and inevitably cracks are beginning to show.

Aaron Falk is the Chair of the Internet Research Task Force (IRTF) and Engineering Lead with the Global Environment for Network Innovations (GENI). “There are many areas where the current architecture is straining to meet the needs of the users,” he says. “In particular, the areas of mobility, security, and network management were not well addressed in the original architecture, leading to a patchwork of mechanisms. The greatest concern is not so much that today’s traffic is challenged but that the ad-hoc machinery being inserted into the network will inhibit future innovations. I worry about tomorrow’s applications more than today’s.”

The IRTF is a technological trouble-shooter for internet architecture, as Falk explains: “The IRTF hosts research groups that work in areas ‘adjacent’ to the IETF (Internet Engineering Task Force). This can be pre-standards technologies, hard problems that emerge from the IETF or operations communities, technologies where the internet may be one of many possible communications strategies, or architectural issues.”

He continues: “Sometimes research groups assist IETF working groups by bringing researcher expertise or otherwise ‘pre-baking’ technologies so they are ready for standardisation. For example, the Mobility Optimizations Research Group has been working on IP mobility solutions that feed into the MIPSHOP (Mobility for IP: Performance, Signalling and Handoff Optimization) working group for standardisation. Another example is the IRTF Research Group on Internet Congestion Control (ICCRG) which evaluates new congestion control proposals that arise in the IETF.”

I dream of GENI

One of the problems with the current web is that it’s too big and too important to muck around with. That’s where GENI comes in. The Global Environment for Network Innovations is funded by the US National Science Foundation, and it’s best described as a (serious) playground where new ideas can be tested out. “GENI will support two major types of experiments,” the organisation says. “Controlled and repeatable experiments, which will greatly help improve our scientific understanding of complex, large-
scale networks, and ‘in the wild’ trials of experimental services that ride atop or connect to today’s internet and that engage large numbers of human participants.

“We’re well underway on the second year of GENI prototyping, GENI Spiral 2,” Falk says. “One of our more exciting activities is what we are calling ‘meso-scale deployments’ of virtualisable, programmable routers, switches, and WiMax base stations on 14 campuses and two national research backbone networks. Deployments like these are particularly exciting because they’ll allow experimental applications and services built on GENI to directly reach real users on university campuses. Thus researchers will have the ability to build new services – perhaps incompatible with the current internet – and test them at-scale with real end-users.” One area of concern is routing tables, which the net’s backbone routers use to direct online traffic. The BGP (border gateway protocol) routing table has grown hugely, doubling in size between 2003 and 2009, and there are concerns that if the level of growth continues, router hardware won’t be able to cope. The IRTF’s Routing Research Group (RRG) is investigating alternatives, and its goal is to produce solid recommendations that the IETF can implement. Another related program is Rochester Institute of Technology’s Floating Cloud initiative, which hopes to address the problem of routing table growth by moving the routing tables from inside routers to network clouds. Initial testing took place on a dozen Linux boxes, and the next step is to try it on GENI.

The BGP routing table doubled in size between 2003 and 2009, and it’s still getting bigger.

GENI isn’t the only initiative that the NSF is helping to fund. Its Future Internet Architectures (FIA) program is offering $30million to fund projects that will transform the net. As the NSF puts it: “Proposals should not focus on making the existing internet better through incremental changes, but rather should focus on designing comprehensive architectures that can meet the challenges and opportunities of the 21st century.”

FIA is a continuation of FIND, the NSF’s Future Internet Design project. FIND asked researchers to redesign the internet from scratch, and FIA will narrow around 50 FIND projects down to two, three or four serious contenders.

Safety and security

With the existing internet, security is something that’s largely been bolted on as an afterthought – but the FIA program expects security to be a key consideration from the outset. That’s leading to some interesting ideas, including one security system that takes its cues from Facebook. Davis Social Links (DSL) adds a “social control layer” to the network that identifies you not by your IP address but by your social connections. If it works – and DSL is in the very, very early stages of development – it could make a major dent in problems such as spam and denial of service attacks.

Eugene Kaspersky, CEO of Kaspersky Lab, would like to take things even further. In October, he argued that the internet’s biggest weakness was anonymity, and that everyone should have online passports. “I’d like to change the design of the internet by introducing regulation – internet passports, internet police and international agreement – about following [web] standards,” he told ZDNet Asia.

Kaspersky explained further on the Viruslist.com blog: “When I say ‘no anonymity’, I mean only ‘no anonymity for security control’,” he writes, explaining that he couldn’t care less what people posted on blogs or downloaded through BitTorrent. “The only [requirement] – you must present your ID to your internet provider when you connect.” Kaspersky argues that such requirements are inevitable, with some EU countries already introducing digital IDs. “Another prototype of e-passports is the two-factor authentication we use to access corporate networks,” he says. “The only thing missing today is a common standard.”

Security guru Bruce Schneier isn’t convinced. “Mandating universal identity and attribution is the wrong goal,” he writes on Techtarget. “Accept that there will always be anonymous speech on the internet. Accept that you’ll never truly know where a packet came from. Work on the problems you can solve: software that’s secure in the face of whatever packet it receives, identification systems that are secure enough in the face of the risks. We can do far better at these things than we’re doing, and they’ll do more to improve security than trying to fix insoluble problems.”

The quest for improved security is attracting a lot of attention – and a lot of money. The US Defense Advanced Research Projects Agency (DARPA) awarded contracts worth $56million in January to two firms as part of its National Cyber Range security programme, which will enable network infrastructure experiments, new cyber testing capabilities and realistic testing of network technology. A month previously, Raytheon BBN Technologies was awarded an $81million contract by the Army Research Laboratory to build the largest communications lab in the US, again to research network security.

David Emm is part of Kaspersky Lab’s Global Research and Analysis Team. “It would be unrealistic to expect a wholesale re-architecture of the internet, or even of some of the technologies that are used online,” he says. “If we fix the problem by removing the facility, we run the risk of damaging legitimate activity too.”

There’s also the issue of displacement: if the internet becomes tougher to compromise, villains will simply switch to social engineering instead. As Emm points out, corporate email filtering to remove attached ‘.exe’ files simply spawned the use of links rather than attachments to spread viruses and other malware. “There has always been a human dimension to PC attacks,” he says. “Patching code is fairly straightforward once you know what you need to fix. But patching humans takes longer and requires ongoing investment.”

The last mile

There’s another big piece of architecture that needs upgrading: the bit between your ISP and you. Whether that’s a wired connection or a wireless one, today’s technology needs a serious speed boost. As Tim Johnson of broadband analyst Point Topic explains, “ Over the past 15 years or so we’ve seen the data speeds that typical home users get going up roughly 10 times every five years. I think that will continue over the next decade so that by 2020 many users will be getting a gigabit on their home broadband.

BT’s 21CN project is a software-driven network that aims to drive innovation.

“The big barriers that must be overcome to get there are (a) extending fibre all the way to the home, and (b) providing the backhaul capacity and the interconnect standards to make it useful,” he elaborates. “Both of those are do-able but I think it will be quite late in the teens before they are achieved.”

Johnson reckons that things will get particularly interesting when 100Mbps+ connections are the norm, as they will be able to deliver immersive, high-definition environments and “a huge new space of technology, applications and lifestyle possibilities”. But he’s not convinced the internet can even handle that – not in its current form, anyway.

“This kind of application is rather different from what the internet was designed for and is good at,” he says. “From an engineering point of view it will mean provisioning capacity that will allow users to set up assured end-to-end symmetrical calls of at least 20Mbps each way. There also needs to be a huge amount of standards development and investment to support setup and switching. […] It’s possible that this could all be done across the open internet, but my own belief is that as this type of traffic grows it will create the need for more dedicated capacity. IP and intelligent multiplexing will still rule, but the basic architecture will be different.”

Going mobile

In developed countries, the internet is moving away from the desktop and onto mobile phones and other wireless devices, while in developing countries the internet is primarily a mobile medium already. In both developed and developing countries the number of mobile internet users will increase dramatically in the next decade. So if you think the mobile networks are creaky now, things could get considerably worse in a decade.

For the mobile internet at least, the future may look an awful lot like the past. As Jon Crowcroft of the University of Cambridge writes: “We are so used to networks that are ‘always there’ – so-called infrastructural networks such as the phone system, the internet, the cellular networks (GSM, CDMA, 3G) – and so on that we forget that once upon a time (why, only in the 1970s) computer communications were fraught with problems of reliability, and challenged by very high cost or availability of connectivity and capacity.”

Noting that technologies such as email coped fine in those conditions, Crowcroft suggests that, “It appears that it’s worth revisiting these ideas for a variety of reasons: it looks like we cannot afford to build a Solar System-wide internet just yet, [but] it looks like one can build effective end-to-end mobile applications out of wireless communication opportunities that arise out of infrequent and short contacts between devices carried by people in close proximity, and then wait until these people move on geographically to the next hop. It’s interesting to speculate that these systems may actually have much higher potential capacity than infrastructural wireless access networks, although they present other challenges (notably higher delay).”

Such systems – variously called Intermittent, Opportunistic or Delay Tolerant networks – have a wide range of applications. They’re useful in emergencies and in areas where there isn’t an existing network infrastructure, and they’re particularly well suited to emerging applications where a constant signal can’t be guaranteed, such as internet-enabled cars.

While such networks could ultimately be deployed in remote areas, for most of us the future of the mobile internet is very similar to what we’ve already got. LTE (Long Term Evolution) is a kind of 3G network with knobs on, and in the UK at least it’s generating much more interest than the rival WiMax technology. When LTE begins to roll out later this year it will deliver theoretical speeds of up to 140Mbps, rising to 340Mbps after a 2011 upgrade. An even faster version of the network, LTE Advanced, is in the works. It’s worth noting, though, that even the first version of the LTE network will take several years to roll out nationwide.

And WiMax? In February this year, Patrick Plas – Alcatel-Lucent’s Chief Operating Officer for Wireless – told reporters that the company “is not putting a lot of effort into this technology any longer” as mobile networks were showing “a clear direction taken by the industry towards LTE”. That’s an honest indication of where the mobile internet is heading.

Looking ahead

Predicting the future is a tricky business, and predicting the future of the internet is doubly so. However, it’s clear that the next decade will see some dramatic changes in the way the web works. Some changes are definite – the move to IPv6 will happen, albeit more slowly than many would like – while other developments such as opportunistic networks may never become mainstream.

What we can predict is that the internet of 2020 will be coping with user numbers and traffic volumes that we can barely imagine. To be able to cope with that, the net will probably become a hybrid: a mix of old and new. As Falk puts it: “Recent interest in ‘clean slate’ network architectures encourages researchers to consider how the internet might be designed differently if, say, we knew then what we know now about how it will be used,” he says. “But that is not to say we must discard the current internet to fix the problems. The internet has tremendous value, has supported astronomical growth and changed the lives of millions of people. I believe research in new internet designs will provide insights on where the high-leverage points are on the current design thus allowing us to understand, justify, and deploy changes that will bring the greatest benefit.”