Sunday, July 03, 2011

Smart phone chorded keyboard

In 2007 I blogged about five finger keyboards, also known as chorded keyboards, as an alternative to the dinky and hard-to-use physical keyboards on mobile phones. Five buttons located on the edge of the phone, under the fingertips in normal use, could be used to enter text whenever needed, without having to waste time moving fingers from one key to another. In 2008 I built a simple demo of the idea in JavaScript.

Over the past few years smart phones have become common, and their preferred entry method is via a pop-up "soft" keyboard on a touch sensitive screen. Mostly we use one finger to hunt-and-peck text into these, but some interesting alternatives have been developed, like sliding your finger across the keyboard from key to key, or using gestures. Gizmode has a nice article on some interesting new ways to capture text into an Android phone.

Android 2.3 Soft Keyboard

If we implemented a chording keyboard on a touch-sensitive screen, how would it compare with what's out there already? Let's start with the default soft keyboard that ships with Android 2.3. It has 34 soft keys, of which 29 yield characters and 5 functions (e.g. backspace). You tap a key briefly to get its character or function. 28 of the character-bearing soft keys have a extra character value that you access by pressing and holding the soft key, providing a total of 62 characters and functions. These extra values include the numerals and special characters used for punctuation and maths. As on PC keyboards, the extra values appear above base values on each soft key, so it's easy to work out which soft key to press in order to get an extra character. For example:
3
e
15 of the Android 2.3 keyboard's soft keys carry additional letter variants, that is, the base letter plus a diacritic of óne type or ànother, 57 variants in all. They aren't visible on the soft keyboard, but each relates to a base letter on the soft keyboard. For example, you access the diacritic variants of the letter "e" by pressing and holding the base letter "e". A pop-up appears with its diacritic variants following the default "3" which appears in the upper half of the soft "e" key:
3èéêëęě
You choose between these options by sliding your finger sideways. The focus moves across the list of options in sympathy. The character that has focus when you lift your finger from the screen is taken.

Soft Chording Keyboard

Let's design a phone app to capture text using chording key principles, but with the fingers touching soft keys on the phone's screen. Ideally, the fingers should only have to move up and down in one place. With my adult male fingers, I can only fit three fingertips across the width of my HTC Wildfire's touch screen. A classic chording keyboard with three buttons would give us 2^3-1 = 7 different characters, way too few (I'm using the notation A^B to mean A to the power of B). If we take into account the sequence of touches and allow for sequences of 1, 2 or 3 touches then we get 3*2*1 combinations that include all three fingers plus 3*2 combinations that include only two fingers plus 3 combinations that use only one finger = 15 different characters, still way too few. If we take into account the sequence in which the finger tips touch the screen and also the sequence in which they leave the screen then we can encode 3*2*1 * 3*2*1 + 3*2*2 + 3*1 = 51 combinations. Better, but we're still short of the 62 characters that the Android 2.3 keyboard can encode, ignoring case shift and diacritics. We will have to allow individual fingers to press and release their assigned soft key more than once in a coding sequence. Then the sky is the limit.

While we're about it, let's note that most pop-up keyboards take up a lot of real estate. If the user needs to fill in a multiple field form then the pop-up keyboard will likely cover most of the form. It would be nice if our chording keyboard used up less screen space, but still guide the novice user through character selection. Here's a sample "home page" for our pop-up chording keyboard:
Backspace Blank Shift: Aa New line
Put three fingertips on this line to enter text
We have a list of four common functions/characters across the top. A production version would use symbols rather than words. The lower half is where the user's fingertips will rest. We could predefine three blocks and require the user to put a fingertip in each, but lining up fingertips with blocks would take time. Instead, the user is free to place three fingertips anywhere on the line of text, and the keyboard app will find them. When this is done, the top line is replaced by cues that lead the user through the process of selecting a character. The user then lifts and lowers fingers in various sequences to choose characters. At any time the user can lift all fingers simultaneously to cancel the process and return to the home page. Once selection starts, here's how the first set of cues might look:
a-m n-z 12#
(==) (==) (==)
a-m gives access to the first half of the alphabet, n-z to the second. 12# gives access to numbers and special symbols. (==) marks where the user's fingertip happens to lie. The app writes the cues above each fingertip. If the user lifts finger 1, selection of a character in the range a-m will start. The cues will change, and the keyboard pop-up might then look like this:
a-d e-h i-m
(---) (==) (==)
(---) marks where fingertip 1 was before it was lifted; the other two are still down. The keyboard app wouldn't actually display the (==) or (---), they're only there to assist with the explanation. The first cue a-d is italicised to indicate that the user should lower that finger to choose that option. If the user lifts finger 2 then the pop-up might change to:
e f-g h
(---) (---) (==)
Bold cues show tell the user that if that soft key is chosen, the selection process will arrive at a character. In this case, lowering finger 1 will select the letter e. After that, the user could lower finger 2 so all three fingertips are on the glass. The keyboard would return to the top character selection page, ready to start the next character.

Accessing Diacritic Variants

We can allow users to access diacritic variants of letters in a similar way to the Android soft keyboard. Once you complete a sequence that yields the letter "e" for example, then the selected letter, and the secondary character that shares its soft key, and the diacritic variants of the selected letter could appear in the cue area like this:
e3èéêëęě

(==) (---) (==)
The selected character "e" has the focus. If you ignore this cue and lower finger 2 to start selecting the next character, "e" will be chosen as the next input character. If you pause, focus will move to "3", the secondary character that shares the "e" soft key. If you pause longer, focus will move cyclically further to the right, wrapping back to the left once it runs off the right edge, so you can select any variant just by waiting. Alternatively, you can slide your fingers to the left or right, and the focus will move left or right in sympathy. Whatever character has focus when you lower finger 2 will be selected. Fingertips that slide off the side of the screen will be ignored. The base letter and the focus will be located at the right of the string of options if fingertip 3 is the only one in contact with the screen, so that it has room to slide left. After a sideways slide you might have to lift all fingertips and re-centre them, which is undesirable, but you won't have to be too fussy about where you locate them, so it should be quick.

Character Code Points

Starting from the home position with three fingertips on the screen, you have a choice of three movements – raise any one of your three fingers. After any of these movements, you have another three choices, and so on. You are navigating a trinary tree, with a single character at each leaf position and cues at non-terminal nodes. A five level balanced trinary tree would have 1 root with 3 child nodes, 9 grandchild nodes, 27 great-grandchild nodes and 81 great-great-grandchild nodes. Each successive level is reached by raising or lowering one fingertip. Of the 27 great-grandchild nodes, one will have all fingers raised, which position we reserve to end the current character selection sequence as an "Oops!" gesture. So we will lose three potential code points, leaving 78. Of these 78 leaf nodes, some have all three fingers down. We discard these because that configuration is required to start the next character. All fingers down can be reached after four moves by raising two fingers and then lowering two fingers, 3*2*2*1 possible sequences = 12 code points; or by raising and lowering a finger and then doing the same again, 3*1*3*1 = 9 code points (we accept "all fingers down" as valid if this happens at level 2). That leaves 57 code points, five less than the number of characters and functions that appear on the Android soft keyboard. But one of the Android keys is not needed (12# selects special characters), and our home page includes four common functions to compensate. All of the code points can be accessed with only four finger up-down movements.

In practice, we may choose to follow the example set by Samuel Morse and allocated shorter code sequences to more common characters, and longer code sequences to less common sequences, to reduce the average number of finger movements needed to code a character. The sample screens above allocate 2/3 of the code space to the alphas, although they form only 42% of the Android character set. We also need to group the special characters so that we can give cues that will guide the novice user to find each character required. They can be divided into the 10 numerals, characters that can be drawn with one continuous line stroke @&()_-,./ and characters that require more than one line stroke !#$%+=:;"?

If we introduce longer and shorter code sequences then we will also be able to include other characters that are present on the PC keyboard but not the Android 2.3 keyboard, such as `~[]{}<>

How Quick Would It Be?

Could a chording keyboard achieve reasonable text entry rates in the hands of a practised use? You can benchmark your own digital dexterity by resting your wrist on a flat surface and drumming three fingertips on it, as if you were impatiently waiting for someone. Try different patterns. It's an easy action for the fingers. Many folk can clock 10 taps per second; that's 20 finger movements per second. If we use a balanced trinary tree for our coding and include an extra movement to get all fingers on the screen to start each character, we need 5 finger movements per character entered (ignoring capitals and diacritics), so our fingers are theoretically capable of entering 20/5 = 4 characters per second or 48 words per minute, faster than the average typer on a full-sized PC keyboard. How fast we would be when typing a given text is another question which only experimentation can answer. Of course you can type letters at a furious pace if you simply drum your fingertips on a PC keyboard, but you will get the same three or four letters repeated over and over again. Once you start moving your fingers around the keyboard to find particular letters, the process slows down greatly.

Wednesday, March 02, 2011

Rhino Poaching

A tide of rhino poaching has swept down through Africa, and has reached South Africa where the largest pool of surviving rhinos are to be found. Rhinos are killed for their horns, which are believed to have medicinal properties by many in South-East Asia. The horns are also used to make ceremonial dagger handles. Armed conflicts have arisen between gangs of poachers seeking rhinos and the rangers whose job it is to protect wildlife. Some poachers have lost their lives in these exchanges. Many people have responded to these developments with great anger, and some have expressed the opinion that the poachers got no more than they deserved. It seems that to them that the lives of rhinos are more important than those of the humans that hunt them. Others have suggested that the South African army should be deployed to protect the rhinos from further poaching.

Before one picks a fight, or accepts an invitation to fight from another, it is prudent to size up the opposition. There are about 2.5 billion people in South-East Asia, while there are only 45 million residents in South Africa. If it comes to outright conflict or even just economic jostling, there is no way that South Africans, or the rhinos, can win this fight. Enlisting the army won't solve the problem either. Rhino horn fetches a higher price than its weight in gold. For that kind of money, the cooperation of an army can be bought, and they come with their own weapons.

After centuries of hunting and poaching, rhinos are quite rare, and they have been accorded the status of being an officially endangered species. It is illegal to trade in rhino products. That has had little effect, other than to drive the price of rhino horn up. Rhinos have become an icon of endangered animals in Africa, a subject of passionate discussion. It has become difficult to engage in rational debate on this subject.

Suppose, just for argument's sake, that it was cattle horn that was so sought after by people in South-East Asia, that for some reason they were unable to raise enough cattle to meet their demand for cattle horn, and that they approached Africa willing to pay high prices for it. How would we respond? Would we build high electrified fences around our cattle and deploy armed guards to protect them? Probably not. It's more likely that a wave of entrepreneurs would buy land and start more cattle farms, steadily raising production until the demand was met. The law of supply and demand tells us that as the production of cattle horn increased, so its price would drop. The incentive for buyers to seek out poachers, or for poachers to engage in the risky business poaching, would be much reduced. As the supply of cattle horn became more plentiful and its price dropped, more and more people would be able to buy it and to test its supposed medicinal properties for themselves. Health researchers would be able to scientifically test its efficacy against various diseases, and to report these results. If it turned out that cattle horn was indeed a cure for a wide range of diseases then large numbers of humans would be able to benefit from this discovery, and cattle production would increase further. If on the other hand it turned out that cattle horn was no better for curing diseases than toe-nail clippings (which it chemically resembles) then demand for cattle horn would diminish, although still continue at a lower level since some folk would remain convinced of its curative powers regardless of what the researchers said.

Let us now return to reality, where it is rhino horn that is in such demand that rhinos are being driven rapidly towards extinction. If we really want to avoid this outcome, and indeed to see an increase in the number of rhinos as time goes by, we should legalise rhino farming and the sale of rhino horn produced on these farms. This would enable a far greater number of people in South-East Asia to enjoy the supposed benefits of rhino horn, and also provide new employment opportunities and prosperity for many in Africa, where rhinos flourish when given the opportunity.

Some readers may respond with horror to the suggestion that rhinos be bred on farms for the production of rhino horn. But we breed cows, pigs, sheep, goats and chickens for food, hide, and many other uses, so why not other species? Rhino meat is perfectly edible, so it's not that the rest of the beast need be discarded. Rhinos are better adapted to the semi-arid areas of Africa than are domesticated animals, and are not susceptible to many of the diseases that afflict cattle. If rhinos are farmed for their horns and meat then those rhinos that remain in game reserves are far less likely to be massacred for their horns. Let us not allow our emotions to cloud our judgment to the point that we inadvertently drive free-range rhinos to extinction, and deny future generations the joy of seeing these wonderful animals roaming free in the wild.

Sunday, February 07, 2010

Backup and Recovery Considerations

Or – Why Murphy was an Optimist

Every IT system is subject to failure. When things go wrong, we try to recover, usually by using a backup copy that we took just in case. This post deals with some of the considerations that one should keep in mind when planning for backup and recovery. It doesn't attempt to cover the details of the backups that are required for any specific IT technology, they are so diverse, and in many cases so complex, that it's impossible for a blog post to cover the ground. Instead, it deals with questions like how should you plan for backup and recovery.

Along the way, we also take a sidelong look at Murphy's Law, which as we all know states:
Anything that can go wrong, will go wrong.
You may also have heard the claim that Murphy was an optimist. That sounds absurd, given the totally bleak outlook of Murphy's law, but in fact it's perfectly true, for reasons that everyone who is responsible for planning backup and recovery needs to know. We'll deal with that issue too.

Planning Backup and Recovery

Backup and recovery doesn't just happen – especially the recovery part. If you want to be able to recover from your backups when things go wrong, you have to plan carefully. There are three major variations in the way that you can do the planning. I call them foresight, on-demand, and hindsight.

Foresight Planning

This is the hard way of doing the job. Before anything goes wrong, you sit down and think carefully about all the things that could possibly go wrong, and then you apply Murphy's rule and assume that if something can go wrong, it will go wrong sooner or later. You then work out what backups and other evasive action you will need to take in order to recover from each scenario when it goes wrong. This is doing the hard yards in advance, and there are several reasons why it's difficult and rather unrewarding to do:
  • Few other people on your organization will agree with you that your worst-case scenarios could come about. Ah, don't worry about it, it will never happen! is a phrase that you will get sick of hearing. It's hard to get the cooperation that you need from other folk with this mode of preparation.
  • If you do a really good job and handle the catastrophe when it happens without even breaking a sweat, no one will even know what a good job you did. They'll all think that your particular patch is a really easy one to handle.
  • In particular, your boss won't know what a valuable contribution you make to his peaceful sleep till you move on to better things and someone less well prepared than you takes over.
On-Demand Planning

This is a more risky way of handling the problem. You wait for something to go wrong, and when it does, you size up the situation and then make a brilliant, intuitive move to fix it all in one stroke. Well, maybe not one stroke – would you believe two strokes, or maybe three? This approach has a number of advantages, but also some potential downside:
  • You don't have to spend so much time persuading other folks to cooperate with you on solving the problem, or even persuading them that it can happen, because you only spring into action once it has happened.
  • You don't have to worry that your hard work will go unappreciated. Your boss will probably arrive at your desk at some time, and maybe his boss too if you can't fix the problem quickly. They may offer you a lot of helpful suggestions on approaches that you could take, and perhaps a few precautions that you could and should have taken beforehand. They may also suggest a lot of interesting new career moves that you could make if things don't work out, quickly.
Hindsight Planning

Hindsight planning is popularly carried out by folk between about 1AM and 4AM in a darkened room, staring at the ceiling. There are no distractions, so you can really focus on the job and do it right.

The big advantage of hindsight planning is the most accurate and economic way of getting the job done. With the benefit of hindsight, you know exactly what backups you should have taken when, and exactly what recovery procedures you should have undertaken when things went wrong. Next time, you'll know exactly how to handle the situation. If there is a next time.

The big drawback of hindsight planning is that you may never get an opportunity to put your hard-won wisdom into practice. You may be following a new career, one of those recommended to you by your manager.

Which Planning Strategy is Right for You?

We all know one size doesn't really fit all, so which of the three strategies is right for you? Probably a mixture of all three. There is a limit to the patience and cooperation that you can expect from your co-workers, so if you go flat out for the foresight model, you will irritate your colleagues. They will warn you off, and if you persist and really get up their noses, they'll go out of their way to sabotage you.

The on-demand model is risky, but also offers rich returns if you pull it off. Everyone knows that you pulled it off, and they will all think that you're a hero. Well, most of them. There's always a few malcontents. Because of its high risk elements, you may want to mix in a large element of the foresight method. Prepare for the problem, but when it happens, be sure to spend some time telling everyone how unlikely it was that this problem should ever occur. Let the tension build, and once you have your audience, tell them that there is one maneuver that might just save their bacon, then pull your ace from the bottom of the pack.

No matter how smart you are, there are going to be times when something slips through the gaps, and you will find yourself in hindsight mode. Providing you have more successes than failures, you will likely get away with it. Your management will know that no one else is going to achieve a 100% success rate, especially no one who's prepared to work for peanuts like you earn. Cover your back in advance by always asking (in writing) for a few more backups that you actually need, and keep track of the ones that don't get taken. Don't complain about the missed backups, just keep a note of them in your back pocket. Then when you find that you have totally run out of options and your back is to the wall, announce that you can save the situation by using one of the backups that you know isn't there. With horror, and an audience, you discover that it isn't there, and you pass the buck to some other poor sucker. Just don't pull this stunt too often, or your colleagues will get wise to you, and sabotage you out of a job in self defense.

Murphy Revisited

So getting back to Murphy, just why was he an optimist, and what does it have to do with you? Look carefully at his law:
Anything that can go wrong, will go wrong.
There's an unspoken assumption in this statement – that if something can't go wrong, it won't. This turns out to be a really dangerous assumption, as anyone who has scars on their back from years of backup and attempted recovery will know. I would like to offer you my rule, that is particularly relevant for folk who are responsible for planning and executing backup and recovery:
The most difficult problems to recover from are those that you knew could never happen.
There are two reasons why this is true.

Firstly, when they do happen, you simply can't bring yourself to accept that they really did happen You waste precious minutes or hours staring at the forensic evidence in stunned disbelief. While you do, the few precious opportunities that you might have had to escape from your doom slip by, unnoticed

Secondly, once you are able to accept the fact that the unthinkable has happened, you have absolutely no plan in mind to recover from it. You sit there staring at a blank page, with a ring of anxious faces surrounding you, looking at you with gradually fading hope.

The moral of this story is:

Always Have a Plan

Think through everything that could go wrong in advance. Brainstorm with other people and get their ideas too. If they're too busy and preoccupied with their own problems to help out, invest in a few drinks after work some time and, once they have started to chill, entertain them with a few horror stories about things that went wrong at other places. Chuckle with them over other people's misfortunes. Don't tell them that in some of these stories, you were the fall guy – keep it light, keep them laughing. After a while their creative juices will start to flow, and they'll reward you with a few horror scenarios of their own. Take discreet notes.

Once you have an inventory of potential problems, categorize them by probability and impact, as best you can. Remember, probability is never zero. If you don't believe me, ask Heisenberg. Once you have the list, start working on ways in which you could potentially recover should a given problem arise. You will not be able to develop a 100% recovery strategy for 100% of the problems, life is too short, so you have to prioritize. Develop detailed plans for the more likely, bigger impact disasters on your list, and less detailed plans for the less likely or less impactful items on your list. Your goal is not perfection, it's survival. For the raft of problems that seem too bizarre to happen, you can develop one simple, common solution – like keeping $2,000 and your passport in a plain brown envelope in your bottom drawer.

How Many Backups Do You Need?

Just to pick up on one common problem that you are pretty sure to encounter – you can't do recovery without backups. The more problem scenarios you develop and solutions you create to handle them, the more backups you are likely to need.

Sooner or later a delegation will come to your desk and tell you that you're taking too many backups, burning too much valuable removable media and/or bandwidth to backup sites, and too much processor time taking backups. They may point out for example that you still take daily backups of a database that is no longer needed, because the company sold off the division that used that database two years ago. Don't admit that this small fact had slipped your notice. You need to do some homework in advance. Find out the major laws that apply to the retention of financial records in your country, like the Sarbanes-Oxley act in the USA for example, and quote some of the penalties that may be imposed if these laws are broken. Point out that you wouldn't be backing up the data if it wasn't still online, occupying valuable disk space that is denied to you, and suggest that some guy who used to work with the system, but who has since left the company (and ideally the country too) once told you that other systems still in operation post updates to the supposedly discontinued system, and these have to be journalled to comply with record retention legislation. By now your accusers will be shuffling their feet and glancing sideways at one another. At this stage, throw them a fig-leaf so they can beat a hasty retreat from your desk without feeling that they have come away completely empty-handed. Offer to take the backups only once a week instead of daily.

You must always take complaints of this sort seriously, and make time to have a detailed discussion with your accuser about the various backups that you are taking, why you're taking them (better keep notes, or you'll forget yourself), and whether the need is still as great as it seemed when the backup was first put into the roster.

But as you sit down to have this conversation, be sure to kick off an extra, unscheduled backup to cover the time that you will be busy in the meeting and unable to monitor the systems. Just in case.

Monday, May 04, 2009

Methodologies considered risable

A recent blog on The Agile Fallacy got me thinking. I've been programming for 45 years and still am, although slowly. I have seen the wheel go round many times, and I have a somewhat different perspective to that expressed in the blog. I won't mention any specific technologies because that will only yank various folk's chains. In the 1960's most big development projects delivered late and lousy. It became a standing joke that programmers used all of the project time and budget to deliver the first 90% of the agreed deliverable, and an equal amount of time and money to deliver the other 90%, assuming they were allowed to carry on that long. Peter Jackson famously remarked that movies don't actually get "released", they escape into the wild, and the same can be said for most large application development efforts. Whatever isn't done right at the time of release is done later, and called maintenance. The programmer's ultimate refuge is to claim "the users' requirements changed", even if the requirements were to implement double-entry bookkeeping which has been around in its present form for about 800 years. I rambled on about this issue in an earlier blog entry.

Fred Brooks, manager of IBM's OS/360 development project, wrote The Mythical Man Month to describe many of the pitfalls found in the 1960's. A lot of DP managers (that's what we used to call them) got fired as a result of non-delivery, and in self-defense they developed "methodology", elaborate systems of checks and balances, reports and reviews, that slowed the whole development process down to a point where there were far fewer ugly surprises. You can tell that "methodology" was a con game from the start by its name – "methodology" should mean the study of methods, not the practice thereof. It should have been called just "methods", but that was far to simple a word for the grand collusion then underway. With the introduction of "methodology" productivity plummeted, but the DP managers got to keep their jobs, and that's what counted most (to them).

The underlying problem with predicting how long development will take is that the productivity of individual programmers varies hugely. A research project at Dartmouth College back in the 1960's showed that the slowest student programmers were over 100 times slower than the fastest. The only reason that the study showed "only" a factor of 100 is that the researchers got tired of waiting for the last few laggards, closed the lab and went home. Sadly, you can't tell which programmers are fast and which are slow just by looking that them, so it's hard to pick a winning team. Ornate methodologies overlay so many admin tasks on all programmers that the difference in productivity between the best and the worst is masked.

While DP managers were happy with "methodologies", the really competent programmers were totally frustrated with them because they knew that they were being hobbled. As they say, "how can you fly like an eagle when you are surrounded by turkeys?" Some of the more cunning ones solved the problem by developing revolutionary new "methodologies" that allowed them to deliver running code dozens of times more quickly than the old, high-bulk "methodologies". On inspection, these new "methodologies" succeeded by jettisoning most of the padding that had been packed into the old ones, thus allowing the good programmers to get the job done fast. In order to allow them to use these new techniques, the practitioners had to dress them up with fancy new names, buzzwords, smoke, and mirrors.

Things went well for a while with the competent programmers delivering code at speed, but after a while the rest of the industry demanded the right to catch up. Snake oil salesmen were quick to "analyse and to codify" the new fast-track methodologies, and to come up with books and courses that would allow any pedestrian programmer to fly like an eagle. Or so they said. Institutions all over the world tried the new panacea, and found out the hard way that they didn't work for them. The new paradigms became discredited, but the fast programmers now had the bit between their teeth, and they realized that the way forward was to coin a new name for low-bulk programming every time the previous name got discredited. To date we have seen a number of iterations of this particular wheel, with the smart programmers soaring like eagles while the rest of the pack follow behind, crashing through the undergrowth and gobbling wildly as they struggle to become airborne.

So what should we do about this problem? The reality is, we can't afford to do without the really competent programmers, and if the new methodology game is the price that we have to pay in order to allow them to get the important stuff done fast, so be it. Just be aware that your mileage may vary.

Wednesday, December 03, 2008

Five Fingered Keyboards (3)

I have at long last put together a small demo of a five finger keyboard, as discussed in a previous entry in this blog. I have released it as an open source project on Google Code, here. It's an HTML page with embedded JavaScript that illustrates the concept of a sequence-sensitive chording keyboard. The version that I uploaded, v0.1, is limited and buggy, but it's a beginning.

Wednesday, November 05, 2008

DIV_SRC could cut news feeds' bandwidth by 90%

The Internet is taking over from printed newspapers, magazines and journals. It is also enabling ordinary people like me to publish their thoughts, hopes and ideas in blogs such as this one, almost free of charge. Major news feed sites such as as BBC News, CNN and Slashdot.org have millions of readers word-wide, and the amount of bandwidth consumed by people browsing news feeds is large and growing fast.

News feeds change their front pages often, and for this reason they make them uncacheable, or if they can be cached then it's only for a minute or so. Pretty much every time a person browses a news feed, they get a complete copy of the page from one of the news feed's servers. But if you look at a news feed you will find that it is made up of a number of short stories, often with links to fuller versions of the story. As time goes by, new stories are added and the older ones get pushed down the page, eventually falling off the end into an archive. If you look at a given news feed twice in ten minutes then the chances are good that while the content may have moved around a bit, most of it will be unchanged. And while you probably wouldn't look at the same news feed that frequently, if you consider all the people who share your ISP, and hence your ISP's caching proxy server, the ISP may have to fetch a given news feed page in its entirety thousands of times a day, even if 90% of it is unchanged from one fetch to the next. This places a large and growing load on the news feed's servers and bandwidth, and on the ISP's upstream bandwidth.

I have written an open source program called DIV_SRC, the package can be downloaded from Google Code. The tool allows large, composite HTML pages like news feeds to be broken into sections. The base page references these sections with <div src="URI"> tags (or any other tag types that the caller chooses). DIV_SRC.js is a client-side JavaScript program that finds all of the section references of this sort in the base page and fetches the referenced content using AJAX. A demo news feed shows that if news feeds used DIV_SRC then their main pages, which are necessarily dynamic, would shrink to about 5% of their current size. The individual stories that they carry could then be cached by browsers and caching proxy servers, reducing the news feeds' bandwidth bill by 90% and giving better response times to users.

No server-side coding is required to implement DIV_SRC, it can run off a vanilla web server that delivers nothing but the usual static files of HTML, images, style sheets and JavaScript. The DIV_SRC.js JavaScript code is compact, less than 5KB in terse form.

DIV_SRC could also be used by blogging engines to reduce bandwidth consumption and to improve response times. Blog pages delivered from blog engines such as Blogspot.com come with the HTTP header Cache-control: max-age=0, which prevents browsers and caching proxy servers from caching blog pages. This ensures that every viewer always gets to see the latest version of the page, which is good, but at a cost. If the blog is popular then browsers all over the Internet will be getting fresh copies from the blog server every time the blog is viewed. By using DIV_SRC, blogging engines could ensure that browser users continue to see the latest version of each blog, but the unchanged sections of the blog will not have to be transmitted from the blog server to the browser every time a given blog is viewed. Each blog entry would be stored as a separate static HTML file which could be cached by browsers and/or caching proxy servers anywhere in the Internet.

There are some issues that would have to be addressed, like what happens if a browser without AJAX capabilities (such as a mobile phone browser) accesses a composite page. This question and several others are dealt with in the Problems page of the project's website.

Sunday, September 07, 2008

Cattle shown to align north-south

A recent BBC article reported that a group of scientists had studied a large number of Google map images looking for cattle, and had found that most of them adopt a north-south orientation. The resolution of the images wasn't good enough for the researchers to distinguish which way the animals were pointing, north or south. They followed up with field studies of wild deer in the Czech Republic and determined that most of them faced north while about one third faced south. They checked, and the animals didn't track the sun as it moved across the sky, their orientation was consistently north-south regardless of the time of day. Their conclusion was that the animals possess a magnetic sense, and that they line up with the earth's magnetic field. We believe that migratory birds can sense the earth's magnetic field and use it for navigation but no organ has yet been found in large mammals that confers the ability to discern magnetic fields, but perhaps one will be found one day. The researchers do not offer any compelling explanation for why the animals would benefit from lining up with the earth's magnetic field.

It seems to me that there is another, simpler explanation for this behaviour. Each hemisphere of the earth undergoes seasonal variations - summer, autumn, winter, and spring. During winters sunlight is diminished and the growth of vegetation slows down. Animals deplete the available grazing, and in their natural state when unencumbered by fences they migrate in an equatorial direction to reach pastures where the daylight hours are longer and the vegetation more plentiful. During the winter they deplete much of the available vegetation, and when spring and summer returns, they reverse the process, migrating towards the poles to exploit the new vegetation that grows in response to lengthening days. So their orientation may simply reflect the general direction that they're migrating in when observed. If so, one would expect to see a strong correlation between the local seasons and their orientation - they should be pointing predominantly towards the poles in spring and summer, and predominantly towards the equator during autumn and winter.

It is not necessary to suppose that the animals have magnetic senses in order to point north or south. Bees navigate by the orientation of the sun in the sky, automatically making allowance for the apparent movement of the sun across the sky. If they can manage this calculation with their small brains then mammals should be able to do so as well.