Today is the final post in our CS4FN Christmas Computing Advent Calendar – it’s been a lot of fun rummaging in the CS4FN back catalogue, and also finding out about some new things to write about.
Each day we published a blog post about computing with the theme suggested by the picture on the advent calendar’s ‘door’. Our first picture was a woolly jumper so the accompanying post was about the links between knitting and coding, the door with a picture of a ‘pair of mittens’ on led to a post about pair programming and gestural gloves, a patterned bauble to an article about printed circuit boards, and so on. It was fun coming up with ideas and links and we hope it was fun to read too.
We hope you enjoyed the series of posts (scroll to the end to see them all) and that you have a very Merry Christmas. Don’t forget that if you’re awake and reading this at the time it’s published (6.30am Christmas Day) and it’s not cloudy, you may be able to see Father Christmas passing overhead at 6.48am. He’s just behind the International Space Station…
And on to today’s post which is accompanied by a picture of a Christmas Tree, so it’ll be a fairly botanically-themed post. The suggestion for this post came from Prof Ursula Martin of Oxford University, who told us about the ‘wood computer’.
It’s a Christmas tree!
The Wood Computer
by Jo Brodie, QMUL.
Other than asking someone “do you know what this tree is?” as you’re out enjoying a nice walk and coming across an unfamiliar tree, the way of working out what that tree is would usually involve some sort of key, with a set of questions that help you distinguish between the different possibilities. You can see an example of the sorts of features you might want to consider in the Woodland Trust’s page on “How to identify trees“.
Depending on the time of year you might consider its leaves – do they have stalks or not, do they sit opposite from each other on a twig or are they diagonally placed etc. You can work your way through leaf colour, shape, number of lobes on the leaf and also answer questions about the bark and other features of your tree. Eventually you narrow things down to a handful of possibilities.
What happens if the tree is cut up into timber and your job is to check if you’re buying the right wood for your project. If you’re not a botanist the job is a little harder and you’d need to consider things like the pattern of the grain, the hardness, the colour and any scent from the tree’s oils.
Historically, one way of working out which piece of timber was in front of you was to use a ‘wood computer’ or wood identification kit. This was prepared (programmed!) from a series of index cards with various wood features printed on all the cards – there might be over 60 different features.
Every card had the same set of features on it and a hole punched next to every feature. You can see an example of a ‘blank’ card below, which has a row of regularly placed holes around the edge. This one happens to be being used as a library card rather than a wood computer (though if we consider what books are made of…).
Image of an edge-notched card (actually being used as a library card though), from Wikipedia.
I bet you can imagine inserting a thin knitting needle into any of those holes and lifting that card up – in fact that’s exactly how you’d use the wood computer. In the tweet below you can see several cards that made up the wood computer.
This is a practical 'wood identification kit'.
The manual multi-access key is poked through different holes on the identification cards, which represent specific characteristics of the wood, to help determine which one you’re handling. pic.twitter.com/CLNkFyRlMJ
One card was for one tree or type of wood and the programmer would add notch the hole next to features that particularly defined that type. For example you’d notch ‘has apples’ for the apple tree card but leave it as an intact hole on the pear tree card. If a particular type of timber had fine grained wood they’d add the notch to the hole next to “fine-grained”. The cards were known, not too surprisingly, as edge-notched cards.
You can see what one looks like here with some notches cut into it. You might have spotted how knitting needles can help you in telling different woods apart.
Holes and notches
Edge-notched card overlaid on black background, with two rows of holes. On the top a hole in the first row is notched, on the right hand side two holes are notched. Image from Wikipedia.
Each card would end up with a slightly different pattern of notched holes, and you’d end up with lots of cards that are slightly different from each other.
Example ‘wood computer’. At the end of your search (to find out which tree your piece of wood came from) you are left with two cards for fine-grained wood. If your sample has a strong scent then it’s likely it’s the tree in the card on the right (though you could arrive at the same conclusion by using the differences in colour too). The card at the top is the blank un-notched card.
How it works
Your wood computer is basically a stack of cards, all lined up and that knitting needle. You pick a feature that your tree or piece of wood has and put your needle through that hole, and lift. All of the cards that don’t have that feature notched will have an un-notched hole and will continue to hang from your knitting needle. All of the cards that contain wood that do have that feature have now been sorted from your pile of cards and are sitting on the table.
You can repeat the process several times to whittle (sorry!) your cards down by choosing a different feature to sort them on.
The advantage of the cards is that they are incredibly low tech, requiring no electricity or phone signal and they’re very easy to use without needing specialist botanical knowledge.
Teachers: we have a classroom sorting activity that uses the same principles as the wood computer. Download our Punched Card Searching PDF from our activity page.
The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
We are nearly coming to the end of our CS4FN Christmas Computing Advent Calendar with one more post to come tomorrow. If you’ve missed any you can catch up by scrolling to the end where there’s a complete list so far.
Today’s advent calendar window shows Father Christmas’ sleigh with a sack full of presents ready for delivery. Today’s theme is about the many different online ways that you can now ‘track’ his movements around the world. This follows on from yesterday’s bonus post about how you can actually see (cloud permitting) his sleigh ‘in person’ as it flies overhead at 7:12am on Christmas Day. In reality it’s International Space Station whizzing past – but other interpretations are available.
You can track Father Christmas as he dashes through the sky, delivering presents.
In 1955, so the story goes, an American department store published a newspaper advert with a phone number for children to call so that they could speak to Father Christmas. Unfortunately a misprint meant that the wrong number was given and instead people found they were talking to the US military’s Air Defense Command (now called North America Air Defense Command or NORAD).
Realising the mistake, but also spotting a great public relations opportunity, the team capitalised on this and began to make an annual event of it.
NORAD uses radar and geosynchronous* satellites to monitor Father Christmas. The satellites are able to detect infrared (heat) radiation and apparently Rudolph’s red nose gives quite a strong signal. This data is then shared with everyone via their website, though they don’t know in advance what route he’ll take.
If you’re visiting the website hover over the different bits of the picture as there are linked activities and extra information too.
*geo = Earth, synchronous = matching / following (like when you sync devices), the satellite follows the Earth’s orbit and is always above the same spot, so effectively (from the Earth’s point of view) the satellite appears not to move (it is moving but it follows the Earth’s rotation).
FlightRadar24 is a great website for telling you the answer to “what was that aircraft that’s just flown by?” It tracks the flight of aircraft all over the globe in real time, using a signal transmitted by the aircraft’s beacon (called a transponder) which announces where it is. Father Christmas’ sleigh has its own transponder too which is transmitting its location to receivers around the world.
An aircraft, or Santa’s sleigh, gets information about where it is from a GPS satellite (very similar to using a maps app on a smartphone and it telling you where you are and whether you should go left or right) and it then transmits this location info, along with other data, through its transponder.
There are thousands of receivers here on Earth, many of them in people’s homes and gardens (you can even apply to host a receiver antenna, or build your own with a Raspberry Pi) and whenever Santa’s sleigh passes over one of these ‘ground stations’ its signal is picked up and collected by FlightRadar24. The receivers are in different places so they are receiving the same signal at slightly different times and this information can be used to work out (by triangulation) how fast the sleigh is moving and in what direction.
Google’s Santa Tracker has lots of games to play while you wait for Santa and his sleigh to take flight, including Code Boogie where you can try and program some dancing elves. You move little blocks (a bit like Scratch) to copy the dance moves and, if you get it right, it will show you the underlying JavaScript code.
Dave Holmes, a developer who works at Google and who works on the Santa Tracker project says “Santa Tracker launched in 2004, and has been an important project at Google ever since. While there’s a small core team dedicated to Santa, up to 20 or so Googlers volunteer to help make it happen every year, and it’s become a true community effort. It’s also a way for our developers to try things and see what Google products can do … I like to say that everything I’ve learned at Google, I learned from Santa.”
Google has also added some ‘Easter eggs‘ to its search page – try typing in Christmas or where is Santa to https://www.google.com/. You can also colour in some images online at their Christmas-themed Art Coloring Book, from Google’s Arts and Culture.
Back in the early 1990s email was very new but right from the start people used it to send each other amusing things. One of them was a rather literal consideration of the physics of a sleigh that is laden with gifts and a traditionally overweight Santa, led by a team of reindeer moving at unlikely speeds (after all Father Christmas has to get around the entire world to deliver presents, in just one day). The author (unknown) began –
“No known species of reindeer can fly. BUT there are 300,000 species of living organisms yet to be classified, and while most of these are insects and germs, this does not COMPLETELY rule out flying reindeer which only Santa has ever seen.”
But then goes on to point out that such a gift-delivery system would be working far beyond normal levels and would probably end in disaster, suggesting that –
“In short, they will burst into flame almost instantaneously, exposing the reindeer behind them, and create deafening sonic booms in their wake. The entire reindeer team will be vaporized within 4.26 thousandths of a second. Santa, meanwhile, will be subjected to centrifugal forces 17,500.06 times greater than gravity. A 250-pound Santa (which seems ludicrously slim) would be pinned to the back of his sleigh by 4,315,015 pounds of force.”
Fortunately Father Christmas has his own magic, meaning that we don’t need to worry too much about him disobeying the laws of physics. But he and his reindeer really deserve those cookies, milk and carrots!
The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
This short post, part of our CS4FN Christmas Computing Advent Calendar, is to let you know that you may be able to watch Santa’s sleigh as it goes overhead. It doesn’t matter if you believe in Father Christmas or not, whether you’ll actually see his sleigh really only depends on how cloudy it is! In fact Santa’s sleigh follows the orbit of the International Space Station (ISS) remarkably closely…
Santa’s sleigh. Father Christmas will soon be tethering the sack of gifts to the sleigh with very strong straps (not shown) because he’ll be flying very fast and very high.
In the unlikely event that any small children are awake early on Christmas Day 2022 and it’s not as cloudy as it is today (Sat 24 Dec 2022) in London then you might be able to catch a bright light passing overhead at 7.12 in the morning. It’s a largely overhead pass so the easiest of the three listed below to see. The others are lower in the sky and may be harder depending on what else is in your landscape.
Father Christmas does a number of ‘test runs’ before heading back to the North Pole, apparently.
CS4FN Advent – Day 23: Bonus material – see “Santa’s sleigh” flying overhead (23 December 2021) – this post (an extra one so that people can get ready to track Father Christmas!)
Our CS4FN Christmas Computing Advent Calendar has now been running for 23 days! That’s one post every single day, matching a computing-themed blog post to the image on the front of the advent calendar. If you’d like to see how well we’ve managed this please scroll to the end where you can find all of our previous Advent Calendar posts.
Today’s picture is of Father Christmas who, we’ll assume, is re-checking his list and packing his sleigh ready for a long flight around the world, where he’ll be collecting cookies as he goes.
Father Christmas, about to do his pre-flight checks (twice).
As the song implies, he takes particular care over his list checking it twice to make sure there are no mistakes. In that respect he’s a little like computer scientists who put systems in place to make sure that when they send data to someone else that person can tell quickly if it’s arrived correctly. Today’s post is about reducing errors (and trying to avoid introducing errors). (We don’t know what data collection methods Father Christmas used though.)
1. Reducing errors: check digits
Once I’d reached the age of about 12 my parents started to let me go by myself to my friend’s house which was about a 15 minute walk away. When I arrived I would use my friend’s parents’ landline phone (with permission) to “give 3 rings” to my parents. This meant that I rang my parents’ number – but they didn’t answer, instead they let the phone ring three times and then I hung up. That way they knew the call was from me (our pre-agreed code) but no-one was charged to make or receive a call and they knew I’d arrived safely. (Obviously if the phone rang for longer they’d know it was probably from someone else and answer it).
Computer scientists also use an agreed code when sending data to another person or computer over a network – they want to make sure their data arrived safely too. Data is* sent as binary 1s and 0s and sometimes there’s a scrambling error in the transmission resulting in a 1 arriving as a 0, or a 0 arriving as a 1. A neat way to find out if this might have happened is to double-check what it was supposed to be, by using something called a parity bit (parity means ‘equal’) or check digit. This digit is added to each block of data you’re sending and computer scientists came up with this to let you check if the arriving data looks correct.
Here’s how it works
Suppose you want to send a message consisting of the numbers 6, 13, 2 and 12. These numbers can be converted into binary for data transmission: for example 6 in binary is 0110, 13 is 1101, 2 is 0010 and 12 is 1100. In the 5-row table below these are written in black (the top line is 6 and the fourth row is 12 – we’ll come to the red numbers in a moment).
We’ll now add a parity bit to each row, according to a rule, to make them five digits long.
The rule is that if the binary number has an odd number of 0s we even it up by adding another 0. If there’s an even number of 0s we just add a 1.
In the 1st row 0110 has an even number of zeroes so a 1 is added, 1101 has an odd number of zeroes so an extra 0 is added. Once we’ve checked all four rows we end up with a new parity column (shown in red on the right to make it stand out) on the right. We can also add a new parity row at the bottom as well, by doing the same thing for each of the numbers but read as a column. The first column has an even number of zeroes so we add a 1, the next just has one odd zero so we add a 0 there and so on.
We’ve added extra data to be sent, but this redundancy check (the extra info isn’t part of the message itself but helps support it) makes it easier for the person receiving the information to know if it’s OK or where any problem is.
0
1
1
0
1
1
1
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
0
1
Let’s pretend you’ve just pressed send and your 1s and 0s are winging their way to your friend.
Unfortunately there was a small error in transmission and one of the numbers has ‘flipped’. Will your friend be able to tell which one it is? (Remember they don’t know what your message actually said, they can only see what’s arrived).
Here’s the (slightly scrambled) data that they receive.
0
1
1
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
0
1
They can use the parity bit information to check each row and column. The first row looks fine – two zeroes (even) and the parity bit one says 1 so that’s right. The second row looks wrong though – there’s an even number of zeroes so you’d expect a 1 in the parity bit – but it says 0, so you know there’s a mistake somewhere in row 2, but your friend won’t know where yet. They need to check the columns too.
Column 1 looks good, there are two zeroes and the parity bit says 1 so that’s correct. Column 2 has an even number of zeroes so you’d expect the parity bit to be 1, but it’s 0. So we know the problem is in Row 2 and Column 2. If we look at where they intersect we can see that a 1 has flipped to a 0, shown below in bold and blue. Your friend can correct the data and translate the binary back into the original numbers.
0
1
1
0
1
1
0
0
1
0
0
0
1
0
0
1
1
0
0
1
1
0
1
0
1
You could try this with a friend or family member. Think up any 4 numbers between 0 (binary 0000) and 15 (binary 1111) then transmit your binary code with one error and see if they can work out which data bit flipped. Or… you can do it as a magic trick with a pack of cards (see the activity at the end).
*are, for the pedants 🙂
Further reading
Writing together: Clarence ‘Skip’ Ellis – about Clarence Ellis who used his knowledge of computing to bypass parity checks. The company he worked for was running out of punched cards (we’ll look at these in more depth later in the week) which the company’s computer used to store data. He was able to find a way for his colleagues to re-use the cards they already had, without triggering parity check problems – in doing so the payroll program could be run and everyone could get paid.
Handy binary cheat sheet. (Repeated after the dividing black line to show how the binary number is formed).
2. Trying not to introduce errors: when spellcheck goes worng
Another thing Father Christmas needs to do is check that he has the correct names of all the good children he’ll be giving presents to. He might use a spellchecker for this – this is something that reads the words in a document and compares them to a pre-set list. If a word is spelled in an unusual way the computer will alert you and ask if you want to change it to the one in the list or if you want to add it as a new spelling to the list. It would spot that I spelled ‘wrong’ wrongly in the heading for this section and ask if I meant ‘wrong’ instead of ‘worng’.
Find and replace
Sometimes people want to change a word in their document that appears many times. For example you might put TBA (which can mean ‘to be agreed’ or ‘to be arranged’) as a temporary placemarker in a Word document and later decide that every time the document says ‘TBA’ you’d prefer it to say “to be determined” instead. You don’t have to manually delete and retype every single instance of ‘TBA’, you can ‘automate’ the process using the Find and Replace option. Word will then find every ‘TBA’ automatically and change it to ‘to be determined’.
Sometimes this doesn’t go quite as expected.
In the UK the word ‘ass’ just means donkey but in the US it’s a slightly less polite word for bottom. A slightly more polite word might be ‘butt’ so you – being polite – want to make sure that any time the word ‘ass’ appears in a particular document it’s replaced with the word ‘butt’. This is unfortunate though if you happen to be the editor of a book about donkeys, which is now suddenly about bottoms.
It’s much worse if your document talks about your class at school (clbutt?). Or perhaps it’s some homework about the assassination of an American president (buttbuttination?). Or maybe you need a new password (pbuttword), or even a new passport (pbuttport). Your document is now absolute gibberish and you would not pbutt any exams with that. Where’s spellcheck when you need it?
These types of mistakes are not that uncommon, I’ve even done it myself with the addresses of schools where I send copies of our CS4FN magazine to teachers.
I had a column in my address database which said things like UK, U.K. or United Kingdom and I decided I wanted them all to match and say “United Kingdom”. So… I used find and replace and asked my computer to turn every mention of ‘UK’ or ‘U.K.’ into United Kingdom. It worked beautifully… but I didn’t check the other columns.
I discovered my mistake when ‘Luke’ at a school on ‘Duke Road’ didn’t get his copy of the magazine and it was returned to me by the Post Office as the address was unreadable. I then had to correct both Lunited Kingdome’s name and his DUnited Kingdome Road address 😉 Oops.
Here are some other examples
Trivial Pursuit makers change all mentions of "km" to "kilometres" as a universal find and change. Can't see what could go wrong there. pic.twitter.com/956hYeJw3B
and here’s what happened when someone changed TBA to ‘to be determined’ without noticing that the string of letters also appears in the word basketball.
Once universally replaced mentions of "TBA" in a course guide with "to be determined." Result: a "basketobedeterminedll" course.
— Truly 'Triple Vaccinated for Extra Creaminess' S. (@hotincleveland) January 5, 2017
3. Magic trick activity: parity check with playing cards
You could demonstrate the parity checking (that we did above with 1s and 0s) as a card trick – you just need an assistant and an audience. If you look closely at the pattern of cards in the picture above, and the pattern of 1s and 0s further up in this post you might notice a similarity…
Give a pack of shuffled cards to an audience member and ask them to deal out 16 cards in four rows either face up or face down (their choice). An example is shown in the left of the picture above. Tell them that in a moment you’re going to ask them to turn over a card while you’re not looking and later, you’ll tell them which card they flipped over. Announce that your assistant is going to make it ‘even harder’ by adding an extra column and row (I bet you can see where this is going). Of course, your assistant is adding a parity bit to the rows and columns (but your audience doesn’t know that) – an example is shown in the middle picture above.
Now avert your eyes (or get someone to blindfold you) and ask the audience member to turn over one card from the grid without telling you which. (Example in the picture on the right, above).
When you look at the grid you can quickly work out which one has been turned over, using exactly the same method we used with the 1s and 0s above.
This trick is a variation of one invented by New Zealand computer scientist, Tim Bell, and you can find more information about it and detailed instructions (as well as ideas to make it seem like you’re really a magician) in our free booklet called The Magic of Computer Science: card tricks special. The trick is called ‘The Out of Body Experience‘ and you can find it on pages 24-31 (pages 13 – 16 of the 33 page PDF).
The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
Every day from the 1st to the 25th of December this blog will publish a Christmas Computing post, as part of our CS4FN Christmas Computing Advent Calendar. On the front of the calendar for each day is a festive cartoon which suggests the post’s theme – today’s is a star, so today’s post is about finding your way: navigation.
Follow that star…
In modern cities looking up at the night sky is perhaps not as dramatic as it might have been in the past, or in a place with less light pollution. For centuries people have used stars and the patterns they form to help them find their way.
There are many ways our explorations of space have led to new technologies, though satellites have perhaps had the most obvious effect on our daily lives. Early uses were just for communication, allowing live news reports from the other side of the world, with networks that span the globe. More recently GPS – the Global Positioning System has led to new applications and now we generally just use our phones or satnav to point us in the right direction.
Victorian engineer Charles Babbage designed, though never built the first mechanical computer. The first computers had actually existed for a long time before he had his idea, though. The British superiority at sea and ultimately the Empire was already dependent on them. They were used to calculate books of numbers that British sailors relied on to navigate the globe. The original meaning of the word computer was actually a person who did these calculations. The first computers were humans.
Babbage became interested in the idea of creating a mechanical computer in part because of computing work he did himself, calculating accurate versions of numbers needed for a special book: ‘The Nautical Almanac’. It was a book of astronomical tables, the result of an idea of Astronomer Royal, Nevil Maskelyne. It was the earliest way ships had to reliably work out their longitudinal (i.e., east-west) position at sea. Without them, to cross the Atlantic, you just set off and kept going until you hit land, just as Columbus did. The Nautical Almanac gave a way to work out how far west you were all the time.
Maskelyne’s idea was based on the fact that the angle from the moon’ to a person on the Earth and back to a star was the same at the same time wherever that person was looking from (as long as they could see both the star and moon at once). This angle was called the lunar distance.
The lunar distance could be used to work out where you were because as time passed its value changed but in a predictable way based on Newton’s Laws of motion applied to the planets. For a given place, Greenwich say, you could calculate what that lunar distance would be for different stars at any time in the future. This is essentially what the Almanac recorded.
Now the time changes as you move East or West: Dawn gradually arrives later the further west you go, for example, as the Earth rotates the sun comes into view at different times round the planet). That is why we have different time zones. The time in the USA is hours behind that in Britain which itself is behind that in China. Now suppose you know your local time, which you can check regularly from the position of the sun or moon, and you know the lunar distance. You can look up in the Almanac the time in Greenwich that the lunar distance occurs and that gives you the current time in Greenwich. The greater the difference that time is to your local time, the further West (or East) you are. It is because Greenwich was used as the fixed point for working the lunar distances out, that we now use Greenwich Mean Time as UK time. The time in Greenwich was the one that mattered!
This was all wonderful. Sailors just had to take astronomical readings, do some fairly simple calculations and a look up in the Almanac to work out where they were. However, there was a big snag. it relied on all those numbers in the tables having been accurately calculated in advance. That took some serious computing power. Maskelyne therefore employed teams of human ‘computers’ across the country, paying them to do the calculations for him. These men and women were the first industrial computers.
Before pocket calculators were invented in the 1970s the easiest way to do calculations whether big multiplication, division, powers or square roots was to use logarithms(not to be confused with algorithm). The logarithm of a number is just the number of times you can divide it by 10 before you get to 1. Complicated calculations can be turned in to simple ones using logarithms. Therefore the equivalent of the pocket calculator was a book containing a table of logarithms. Log tables were the basis of all other calculations including maritime ones. Babbage himself became a human computer, doing calculations for the Nautical Almanac. He calculated the most accurate book of log tables then available for the British Admiralty.
The mechanical computer came about because Babbage was also interested in finding the most profitable ways to mechanise work in factories. He realised a machine could do more than weave cloth but might also do calculations. More to the point such a machine would be able to do them with a guaranteed accuracy, unlike people. He therefore spent his life designing and then trying to build such a machine. It was a revolutionary idea and while his design worked, the level of precision engineering needed was beyond what could be done. It was another hundred years before the first electronic computer was invented – again to replace human computers working in the national interest…but this time at Bletchley Park doing the calculations needed to crack the German military codes and so win the World War II.
The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
Each day throughout December (until Christmas Day) we’ll be publishing a computing-themed blog post suggested by the picture on the front of our Advent Calendar. Today’s image on the door of the CS4FN Christmas Computing Advent Calendar is a Christmas wreath which made me think of wires and of weaving.
A Christmas wreath
You might remember that our first advent calendar post was about the links between coding and knitting. Today’s post looks at an even more literal version of that: core rope memory.
1. Core rope memory: the Apollo space mission’s woven computer memory
by Jo Brodie, QMUL.
Firstly it looks like this.
Rope memory from the Apollo Guidance Computer. Image from Wikipedia.
Secondly it got us to the Moon!
Probably the world’s first portable computer
Core rope memory was made up of small ‘eyelets’ or beads of metal called ferrite that can be magnetised (these ring-shaped magnets were known as magnetic cores) and copper wire which was woven through some of the eyelets but not others. An electrical current passing through the wires made the whole thing work. A wire that passed through an eyelet would be read as a binary 1 when the current was on but if it passed around one then it would be read as 0. This meant that a computer program, made up of sequences of 1s and 0s, could be permanently stored by the pattern that was woven.
This type of memory was woven in the 1960s for NASA’s Apollo moon mission by women who were skilled textile workers. They would work in pairs and use a special hollow needle to thread the copper wire through one magnetic core and then the other person would thread it back through a different one, following instructions from another program which indicated which of the eyelets to use.
That program was first developed on a computer (the sort that took up a whole room back then) and then translated into instructions for a machine which helped the weavers get the wire threads into the correct position. It was very difficult to undo a mistake so a great deal of care was taken to get things right the first time, especially as it could take up to two months to complete one block of memory. Some of the rope weavers were overseen by Margaret Hamilton, one of the women who developed the software used on board the spacecraft.
Margaret Hamilton, in 1969, standing next to listings of the software she and her MIT team produced for the Apollo project. Image from Wikipedia.
Several of these pre-programmed core rope memory units were combined and installed in the guidance computers of the Apollo mission spacecraft, to fly astronauts safely to the Moon and back.
NASA needed on-board guidance systems to control the spacecraft independently of Mission Control back on Earth. They needed something that didn’t take up too much room or weigh too much, that could survive the shaking and juddering of take-off and background radiation – core rope memory fitted the bill perfectly.
It packed a lot* of information into a small space and was very robust as it could only break if a wire came loose or one of the ferrite eyelets was damaged (which didn’t happen). To make sure though, the guidance computer’s electronics were protected by being sealed from the atmosphere. They survived and worked well, guiding the Landing Modules safely onto the Moon.
*well, not by modern standards! The guidance computer contained only around 70 kilobytes of read only memory.
2. A brief history of the digital revolution, part 1: from birth to the moon
The Royal Institution Christmas Lectures 2008 invited you on a high tech trek to build the ultimate computer. The Christmas Lectures talk a lot about the current cutting-edge of computer technology, but what were things like in the early days of the digital revolution? The researcher for the 2008 Christmas Lectures, Lewis Dartnell, takes us through the story.
Electronic computers have come a long way since their birth only 50 years ago. One of the very first digital computers was built at the University of Manchester, a prototype called Manchester Mark I. The machine was revolutionary, with its complex processing circuits and storage memory to hold both the program being run and the data it was working on. The Mark I was first run on 21 June 1948 and paved the way as a universal computer that is truly versatile and can be reprogrammed at will, rather than being hard-wired for a single particular task.
A vacuum-tube (specifically a voltage-regulator tube) in use. Image from Wikipedia.
These earliest computers used technology called vacuum tubes, which were essentially just like filament light bulbs. Because they get so hot, such vacuum tubes were really power hungry and not very reliable. Typically, computers like the Manchester Mark I, processing using vacuum tubes, could only be run for a few hours at a time before one of the vacuum tubes broke and had to be replaced. The biggest break-through in modern computing came with the invention of the transistor, a small electronic component that can perform the same function as a vacuum tube, but is much more energy efficient and reliable. The beauty of the transistor is that computer scientists found ways of making them smaller and smaller, and to connect a number of them together into a single miniaturized processing board called an integrated circuit. These came to be known as microchips, and form the basis of all the computers made today.
A major drive for the development of microchip technology was the Apollo programme, begun in 1961 to land humans on the Moon. Although the vast majority of the complex calculations to do with plotting the trajectory and navigating to the moon were performed by enormous banks of computers back on Earth, it was crucial for the spacecraft to have their own on-board computer system. This was called the Apollo Guidance Computer (AGC), and both the command module and the lunar module, which actually made the descent to the surface of the moon, had one each. These ground-breaking computers provided the astronauts with crucial flight information, helped them make course corrections and to touch-down gently on the moon’s surface. Because it’s absolutely crucial to reduce the amount of mass and power usage on a spacecraft as far as possible, developing these guidance computers really pushed the technology in miniaturising integrated circuits.
The Display and Keyboard Interface (known as DSKY and pronounced Diskee) of the Apollo mission’s guidance computer. Image from Wikipedia
The Apollo Guidance Computer not only helped drive the early development of microchips, but it also suffered one of the most infamous computer crashes in history. During the descent down to the Moon’s surface the AGC started displaying two error messages that the two astronauts, Neil Armstrong and Buzz Aldrin, weren’t familiar with. Engineers back at mission control on Earth quickly tried to identify the error code, and what it might mean for the lunar landing. Something that had never happened in any of the training simulations was now overloading the flow of data into the computer, the first time it had ever been used for real. Time was running out with only a limited amount of rocket fuel on-board and the Moon rushing up towards them. Luckily the computer entered a fail-safe mode, aborting low-priority calculations but able to continue with the critical tasks for the landing.
It wasn’t until the investigation afterwards that it was realized just how lucky Neil Armstrong and Buzz Aldrin had really been. The root of the problem was that the real attempt at the Moon landing was the first time an important radar system had been plugged into the computer, sending data into the AGC that wasn’t needed for the landing. This almost totally overloaded the computer, but by amazing luck, the amount of spare processing power built into the system for safety was almost exactly the amount being wasted by the un-needed radar, and the AGC didn’t crash completely.
The story of the digital revolution continues in part 2.
3. Activity 1 – make your own core rope memory
A nice craft activity is to create a cut-down version with beads and coloured threads. You string 8 beads (with a gap between them) on one thread to form a single ‘byte’ (of 8 binary bits). You then take other threads and pass them through when you want that bead to read 1, or over, when you want that bead to read 0. One way of deciding whether it’s 1 or 0 is to pick a word (or maybe your name) and use enough threads so you have one for each letter.
Using binary encoding for each letter (so capital letter A would be 01000001 if you’re following this conversion from binary to letters table) and put that letter’s thread through or over each of the 8 beads to ‘spell’ out the letter in binary.
My name’s Jo so mine would have only three threads (one to hold the 8 beads and two to spell my name). One thread would go over, through, over, over, through, over, through, over to spell the capital letter J (01001010) and over, through, through, over, through, through, through, through to spell lowercase o (01101111). Let’s hope you have a slightly longer name!
4. Activity 2 – create an origami laurel wreath
Not only do we have a wreath-themed activity in our back catalogue (!) but in a delightful coincidence this story also relates to Apollo (the Greek god). If you’re wondering what origami might have to do with computing it’s just another way of looking at algorithms and instructions. Also, decomposition (breaking a problem into smaller parts) because you can re-use the instructions needed for the laurel wreath to make other origami items. We like using ‘unplugged’ activities like this to demonstrate computing concepts.
Create an origami laurel wreath from nested triangles of paper.
The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
We’re doing a post a day for Advent 2021 with a mix of new articles and ones from our extensive CS4FN (Computer Science For Fun) archives. CS4FN has been going since 2005 and we have hundreds of articles to choose from, on a huge variety of topics.
We hope you’re enjoying our daily posts and if you’ve missed any just scroll to the end to catch up with the full set.
Today is Day 20 of the CS4FN Christmas Computing Advent Calendar and the picture today is a gift tag, which is a way of addressing a gift. So today’s post is all about internet addresses.
The @ symbol of your email address first appeared in the Middle Ages. Monks would translate and copy books, but there were often problems when the bookbinders put the pages together in the wrong order. To get round this the monks repeated the last line of each page on the top of the next. This was very laborious so they came up with quick abbreviations even for small but common words like “ad”. It is Latin for “at” or “to”, and the medieval monks sometimes wrote ‘d’ like a mirrored ‘6’. The @ symbol was born. Morse code was updated in 2003 with a special code for @ (•–•-•) so that people could send email addresses by Morse code!
2. La Chiocchiola pasta
by Jo Brodie, QMUL.
In 1999 an Italian pasta company decided to create a pasta shape to celebrate the humble @ symbol. “@” had already been in use in email addresses for several decades (since the 1960s) but was becoming more popular as the use of email expanded and spread beyond businesses, the military and academia (universities etc).
The ‘cyberpasta’ was called “La Chiocchiola” which is the Italian word for snail and you can probably see why they use that word to describe the similarly-shaped symbol. The pasta was awarded a prize from the National Museum of Pasta in Rome where samples of the @ shape were displayed and also given away free. Thanks to the Internet Archive you can even see a copy of the English language version of the pasta company’s website from May 1999 (only a few months after Google was founded).
3. Do @ me
by Jo Brodie, QMUL.
We can thank Ray Tomlinson for the earliest use of the @ symbol to separate an individual computer use from the network they’re using, and to act as an addressing system. Millions of people use Gmail and have an email address ending in gmail.com but (generally) each one gets only their own messages thanks to whatever unique set of letters and numbers is in front of the @. He chose the symbol because it’s a character that never appears in people’s name so could be used as a marker to separate the person from the machine or network. This neat and simple solution made it possible for people to send email anywhere in the world.
Further reading
How does email work? (31 May 2021) Namecheap – a detailed guide to what happens after you press SEND.
Type any web address like www.google.com into a browser address bar, press enter and that address is instantly converted behind the scenes into a series of numbers.
The web address is known as a domain name and it’s an easy to remember version of the website’s address. The series of numbers is called the IP address (which stands for Internet Protocol). The human-readable domain name is translated into the machine-readable IP address by the DNS (Domain Name System) which acts as the internet’s ‘address book’. A DNS server can ‘look up’ the domain name in a list and find the corresponding IP address.
Everything that is connected to the internet has its own IP address including smartphones, laptops, networked printers etc and IP addresses have been in use for decades, helping direct traffic around the internet. We don’t usually see these IP addresses (we don’t generally need to!) but they look like a string of digits chunked into 4 groups, for example 198.51.100.0.
Each of those four ‘chunks’ is actually represented by an 8-digit binary number (or ‘octet’), so the range of each 8-digit octet goes from 00000000 (zero) to 11111111 (255). As 11111111 is the largest 8-digit binary number possible, no chunk can be above 255.
There are four octets (each containing 8 digits) in an IP address
Each of the octets can range from 00000000 to 11111111 (represented by 0 to 255)
Every IP address is therefore made up of a string of 32 (4 octets x 8 digits) ones or zeroes in a particular combination.
This means that there are 232 (two to the power of 32) possible IP address combinations giving an enormous number of over 4 billion addresses (which can be written as 4,294,967,296 or 4.294967296 × 109). Note that it’s “2” because in binary it’s either a 1 or a 0.
You might think that this would give us plenty of addresses to be going on with, but no! It was predicted that as more devices were connected to the internet, as its use expanded, we’d eventually start to run out and sure enough in 2011 we actually began to run out of these 32-bit addresses. Fortunately a new internet protocol (version 6, so it’s IPv6) was developed that uses 128 bits, which means there’s now a possible 2128 variations, giving an even more enormous number of 3.402823669 x 1038 addresses. Well, that should keep us going for a while!
Smart electricity meters are clever meters that are connected to the Internet so they can send data back to the power company about your minute by minute electricity usage for billing purposes. If burglars could get hold of data from a smart electricity meter they can tell whether you are in or not (See Smart meter snooping).
How could anyone other than the power company get the data though? A German research team led by Dario Carluccio decided to see if it was possible. They have shown that the data from at least one kind of smart meter can be intercepted by anyone with the right software. Data needs to be encrypted – transmitted using an uncrackable code – to be safe from prying eyes. For the smart meter they examined that wasn’t done securely. They could not only intercept the data, they could even tamper with what was sent back to the company, which could be used, for example to lower their bills. All you needed was what is known as the ‘MAC address‘ of the smart meter. A MAC address is just the unique network name that a computer uses to identify itself- all computers connecting to the Internet have one. Unless special security is used any computer can pretend it is some other computer just by using the target computer’s MAC address when asked to identify itself. With the smart meter to send bogus data you essentially just need to get another computer to use the smart meter’s MAC address before sending data. The researchers demonstrated this by change the electricity usage data in a way that made the graph of peaks and troughs of usage read the message “U have been hacked”!
(A device’s MAC address is used locally, to identify it to your home broadband whereas the IP address identifies your device to the internet so that it can receive information from anyone, anywhere).
The creation of this post was funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.
It’s Day 19 of the CS4FN Christmas Computing Advent Calendar. Every day throughout Advent we’ll be doing our best to publish a computing-themed post that relates to the picture on the advent calendar’s door. If you’d like to judge how well we’ve done please scroll to the end of this post where we have a full list of our attempts on Days 1 to 18.
Yesterday’s picture was a Christmas cracker, so our theme was cyber security (cracking and hacking into computers). We’re staying quite close with that theme with today’s jingle bells – bells also put me in mind of warnings, and today’s post is about computing scams. So keep your bells pealed and your eyes peeled 🙂 Learn about scams and tell other people about them so they can avoid them too.
Jingle bells, warning you of festive scams
Gone Phishing
Fake emails or text messages asking for bank details including passwords is known in the trade as ‘Phishing‘ – it’s an example of social engineering, in which someone tries to manipulate someone else into giving away information. Like fishing the criminals scatter lots of bait and once in a while someone bites on the hook and replies. Criminals have even created fake Internet banking sites, direct copies of the real sites, in an attempt to scam customers’ details. This type of crime would never have been possible before computers. Few criminals would have the ability or funds to build a fake copy of your bank in the high street, but they can write programs to simulate them online.
Scammers love Christmas. It’s the perfect time of year to try and extract money or information (or both) from frazzled, busy and distracted Christmas shoppers.
“We’re sorry we missed you”
This popular phishing scam will come via text, saying that there’s a problem with delivering your item and you need to pay some small amount of money to rearrange delivery.
In the run up to Christmas so many people are expecting deliveries so this scam is successful because even if only a small percent of people fall for it that’s still a lot of people. The text message will contain a link that looks like it’s for the genuine web address of a delivery company where you might already have an account. But… the link’s taken you to the scammer’s replica website in the hope that you hand over your login information and possibly your bank card details to pay. The scam is quite subtle as once you fill in your details and press send you are then redirected to the genuine company’s website, so it’s easy to miss what’s happened at first.
How to stay safe: were you expecting this text message? If not, be alert. Look at the link carefully – does it seem correct? If it seems fake you can forward the message from any mobile phone to 7226 (which spells SPAM on your keypad). Learn about scams (See further reading) and tell people about them so they know what to watch out for.
See how well you do on Google’s Phishing Quiz (you can make up a fake email address to use) – some are genuine, some are trying to steal information. Can you spot which is which?
Some phishing attempts are a bit more involved. You might get a phone call from someone claiming that ‘bad people’ have ‘got into your internet’ and you need to take immediate action to prevent being cut off. Sometimes the scammers pretend to be from a well-known computer company (such as Microsoft) or from the company that provides you with your broadband internet.
Sometimes they’ll try and engage you in conversation – this is ‘social engineering’. This is a to try and gain your trust while keeping you anxious that something has gone wrong and which they are going to help you with. They may even use some tricks to convince you they’re legitimate. If you use a Windows computer they might ask you to open up the Event Viewer and count the errors, suggesting that there’s a problem (in reality it’s all pretty normal and harmless).
The next thing they might want you to do is to download some ‘desktop sharing’ software onto your computer. The software is real enough (and can be used genuinely to help people) but in this case they want to be able to access your computer and cause havoc. What they probably want to do is see if you have online banking (so they can steal your money) or they might delete some important files and say they’ll give them back only if you pay them. Don’t let them in!
How to stay safe: you can just hang up! Definitely don’t download any software, don’t visit any links they suggest you go to and don’t give them any information.
This ‘friend in need’ scam will likely come via WhatsApp. Someone pretending to be a family member or friend gets in touch claiming they’re contacting you from a new phone after their old one was lost or stolen. They then claim they need money for some urgent reason and ask you to send them some via online banking.
This scam relies on people’s kindness and goodwill, and not wanting to be seen to be stingy or unhelpful, but sadly it causes thousands of pounds to be stolen and it’s often very difficult to recover that money.
How to stay safe: be suspicious. Try and contact your friend / family member in another way to check it’s really them. Or do a bit of social engineering yourself – make up something and ask them about it. Rather than admit they don’t know about it they’ll probably answer ‘yes’ and give themselves away!
We’ve been posting a computing-themed article linked to the picture on the ‘front’ of the advent calendar for the last 17 days and today is no exception. The picture is of a Christmas cracker so today’s theme is going to be computer hacking and cracking – all about Cyber Security.
If you’ve missed any of our previous posts, please scroll to the end of this one where we have a full list.
A cracker, ready to pop
The terms ‘cracker’ and ‘hacker’ are often used interchangeably to refer to people who break into computers though generally the word hacker also has a friendlier meaning – someone who uses their skills to find a workaround or a solution (e.g. ‘a clever hack’) whereas a cracker is probably someone who shouldn’t be in your system and is up to no good. Both people can use very similar skills though – one is using them to benefit others, the other to be benefit themselves.
We have an entire issue of the CS4FN magazine all about Cyber Security – it’s issue 24 and is called ‘Keep Out’ but we’ll let you in to read it. All you have to do is click on this very secret link, then click on the magazine’s front cover to download the PDF. But don’t tell anyone else…
Both the articles below were originally published in the magazine as well as on the CS4FN website.
You arrive in your holiday hotel and ask about Wi-Fi. Time to finish off your online game, connect with friends, listen to music, kick back and do whatever is your online thing. Excellent! The hotel Wi-Fi is free and better still you don’t even need one of those huge long codes to access it. Great news, or is it?
You always have to be very cautious around public Wi-Fi whether in hotels or cafes. One common attack is for the bad guys to set up a fake Wi-Fi with a name very similar to the real one. If you connect to it without realising, then everything you do online passes through their computer, including all those user IDs and passwords you send out to services you connect to. Even if the passwords they see are encrypted, they can crack them offline at their leisure.
Things just got more serious. A group has created a way to take over hotel Wi-Fi. In July 2017, the FireEye security team found a nasty bit of code, malware, linked to an email received by a series of hotels. The malware was called GAMEFISH. But this was no game and it certainly had a bad, in fact dangerous, smell! It was a ‘spear phishing’ attack on the hotel’s employees. This is an attack where fake emails try to get you to go to a malware site (phishing), but where the emails appear to be from someone you know and trust.
Once in the hotel network, so inside the security perimeter, the code searched for the machines running the hotel’s Wi- Fi and took them over. Once there they sat and watched, sniffing out passwords from the Wi-Fi traffic: what’s called a man-in-the-middle attack.
The report linked the malware to a very serious team of Russian hackers, called FancyBear (or APT28), who have been associated with high profile attacks on governments across the world. GAMEFISH used a software tool (an ‘exploit’) called EternalBlue, along with some code that compiled their Python scripts locally, to spread the attack. Would you believe, EternalBlue is thought to have been created by the US Government’s National Security Agency (NSA), but leaked by a hacker group! EternalBlue was used in the WannaCry ransomware too. This may all start to sound rather like a farfetched thriller but it is not. This is real! So think before you click to join an unsecured public Wi-Fi.
Just between the two of us: mentalism and covert channels
Secret information should stay secret. Beware ‘covert channels’ though. They are a form of attack where an illegitimate way of transferring information is set up. Stopping information leaking is a bit like stopping water leaking – even the smallest hole can be exploited. Magicians have been using covert channels for centuries, doing mentalism acts that wow audiences with their ‘telepathic’ powers.
In the 1950’s Australian couple Sydney and Lesley Piddington took the entertainment world by storm. They had the nation perplexed, puzzled and entertained. They were seemingly able to communicate telepathically over great distances. It all started in World War 2 when Sydney was a prisoner of war. To keep up morale, he devised a mentalism act where he ‘read the minds’ of other soldiers. When he later married Lesley they perfected the act and became an overnight sensation, attracting BBC radio audiences of 20 million. They communicated random words and objects selected by the audience, even when Lesley was in a circling aeroplane or Sydney was in a diving bell in a swimming pool. To this day their secret remains unknown, though many have tried to work it out. Perhaps they used a hidden transmitter. After all that was fairly new technology then. Or perhaps they were using their own version of an old mentalism trick: a code to transmit information hidden in plain sight.
Sounds mysterious
Sydney had a severe stutter, and some suggested it was the pauses he made in words rather than the words themselves that conveyed the information. Using timing and silence to code information seems rather odd, but it can be used to great effect.
In the phone trick ‘Call the wizard’, for example, a member of the audience chooses any card from a pack. You then phone your accomplice. When they answer you say “I have a call for the wizard”. Your friend names the card suits: “Clubs … spades … diamonds … hearts”. When they reach the suit of the chosen card you say: “Thanks”.
Your phone friend now knows the suit and starts counting out the values, Ace to King. When they reach the chosen card value you say: “Let me pass you over”. Your accomplice now knows both suit and value so dramatically reveals the card to the person you pass the phone to.
This trick requires a shared understanding of the code words and the silence between them. When combined with the background count, information is passed. The silence is the code.
Timing can similarly be used by a program to communicate covertly out of a secure network. Information might be communicated by the time a message is sent rather than its contents, for example
Codes on the table
Covert channels can be hidden in the existence and placement of things too. Here’s another trick.
The receiving performer leaves the room. A card is chosen from a pack by a volunteer. When the receiver arrives back they are instantly able to tell the audience the name of the card. The secret is in the table. Once the card has been selected, pack and box are replaced on the table. The agreed code might be:
If the box is face up and its flap is closed: Clubs.
If the box is face up and its flap is open: Spades.
If the box is face down and its flap is closed: Diamonds.
If the box is face down and its flap is open: Hearts.
That’s the suits taken care of. Now for the value. The performers agree in advance how to mentally chop up the card table into zones: top, middle and bottom of the table, and far right, right, left and far left. That’s 3 x 4 unique locations. 12 places for 12 values. The pack of cards is placed in the correct pre-agreed position, box face up or not, flap open or closed as needed. What about the 13th possibility? Have the audience member hold their hand out flat and leave the cards on it for them to ‘concentrate’ on.
Again a similar idea can be used as a covert channel to subvert a security system: information might be passed based on whether a particular file exists or not, say.
Making it up as you go along
These are just a couple of examples of the clever ideas mentalists have used to amaze and entertain audiences with feats of seemingly superhuman powers. Our cs4fn mentalism portal has more. Some claim they have the powers for real, but with two dedicated performers and a lot of cunning memory work, it’s often hard to decipher performers’ methods. Covert channels can be similarly hard to spot.
Perhaps the Piddingtons secret was actually a whole range of different methods. Just before she died Lesley Piddington is said to have told her son, “Even if I wanted to tell you how it was done, I don’t think I would be able”. How ever it was done, they were using some form of covert channel to cement their place in magic history. As Sydney said at the end of each show “You be the judge”.
Gosh, Christmas is just around the corner! It’s Day 17 of the CS4FN Christmas Computing Advent Calendar and we’ve posted a blog post every day since 1 December, and you can catch up with all of those posts at the end of this one. We’ll publish a new post every day during Advent, so check back each day.
In doing this we’re also celebrating CS4FN’s own history, revisiting some of our older posts and articles. CS4FN began in 2005 and was created by Profs Peter McOwan and Paul Curzon at QMUL to introduce the subject of computing in a fun way, highlighting the joy of creativity and thinking about things in interesting ways.
If you know a computing schoolteacher in the UK who might like FREE copies of our CS4FN magazine for their classroom please ask them to subscribe.
Today’s advent calendar picture is of a reindeer and, if you’ve been following our advent calendar, you probably won’t be too surprised that I’ve managed to find a CS4FN article which features reindeer!
Email, texting, Instant Messaging, Instant response…one of the things about modern telecoms is that they fuel our desire to “talk” to people anytime, anywhere, instantly. The old kind of mail is dismissed as “snail mail”. A slow network is a frustrating network. So why would anyone be remotely interested in doing research into slow networks? Professor Jon Crowcroft of the University of Cambridge and his team are, and his kind of network could be the network of the future. The idea is already being used by the dolphins (not so surprising I suppose given according to Douglas Adams’ “The HitchHiker’s Guide to the Galaxy” they are the second most intelligent species on Earth…after the mice).
From node to node
Traditional networks rely on having lots of fixed network “nodes” with lots of fast links between them. These network nodes are just the computers that pass on the messages from one to the other until the messages reach their destinations. If one computer in the network fails, it doesn’t matter too much because there are enough connections for the messages to be sent a different way.
There are some situations where it is impractical to set up a network like this though: in outer space for example. The distances are so far that messages will take a long time – even light can only go so fast! Places like the Arctic Circle are another problem: vast areas with few people. Similarly, it’s a problem under the sea. Signals don’t carry very well through water so messages, if they arrive at all, can be muddled. After major disasters like Hurricane Katrina or a Tsunami there are also likely to be problems.
It is because of situations like these that computer scientists started thinking about “DTNs”. The acronym can mean several similar things: Delay Tolerant Networks (like in space the network needs to cope with everything being slow), Disruption Tolerant Networks (like in the deep sea where the links may come and go) or Disaster Tolerant Networks (like a Tsunami where lots of the network goes down at once). To design networks that work well in these situations you need to think in a different way. When you also take into account that computers have gone mobile – they no longer just sit on desks but are in our pockets or handbags, this leads to the idea of a “ferrying network” or as Jon Crowcroft calls them: “Pocket Switched Network”. The idea is to use the moving pocket computers to make up a completely new kind of network, where some of the time messages move around because the computers carrying them are moving themselves, not because the message itself is moving. As they move around they pass near other computers and can exchange messages, carrying a message on for someone else until it is near another computer it can jump to.
From Skidoo to you
How might such networks be useful in reality? Well one already exists for the reindeer farmers in the Arctic Circle. They roam vast icy wastelands on skidoos, following their reindeer. They are very isolated. There are no cell phone masts or internet nodes and for long periods they do not meet other people at all. The area is also too large to set up a traditional network cheaply. How can they communicate with others?
They have set up a form of pocket switched network. Each carries a laptop on their skidoo. There is also a series of computers sitting in tarns spread around the icy landscape. When the reindeer farmers want a service, like delivering a message, the laptop stores the request until they pass within range of one of the other computers perhaps on someone else’s skidoo. The computer then automatically passes the message on. The new laptop takes the message with it and might later pass a tarn, where the message hops again then waits till someone else passes by heading in the right direction. Eventually it makes a hop to a computer that passes within range of a network point connected to the Internet. It may take a while but the mail eventually gets through – and much faster than waiting for the farmer to be back in net contact directly.
Even the dolphins are in on the act. US scientists wanted to monitor coastal water quality. They hit on the idea of strapping sensors onto dolphins that measure the quality wherever they go. Only problem is dolphins spend a lot of time in deep ocean where the results can’t easily be sent back. The solution? Give them a normal (well dolphin adapted) cell phone. Their phone stores the results until it is in range of their service provider off the coast. By putting a receiver in the bays the dolphins return to most frequently, they can call home to pass on the data whenever there. The researchers encountered an unexpected problem though. The dolphin’s memory cards kept inexplicably filling up. Eventually they realised this was because the dolphins kept taking trips across the Atlantic where they came in range of the European cell networks. The European telecom companies, being a friendly bunch, sent lots of text messages welcoming these newly appeared phones to their network. The memory cards were being clogged up with “Hellos”!
The Cambridge team are investigating how similar networks might best be set up and used for people on the move, even in busy urban environments. To this end they have designed a pocket switched network called Haggle. Using networks like Haggle, it might be possible to have peer-to-peer style networks that side-step the commercial networks. If enough people join in then messages could just hop from phone to phone, using bluetooth links say, as they passed near each other. They might eventually get to the destination without using any long distance carriers at all.
The more the merrier
With a normal network, as more people join the network it clogs up as they all try to use the same links to send messages at the same time. Some fundamental theoretical results have shown that with a pocket switched network, the capacity of the network can actually go up as more people join – because of the way the movement of the people constantly make new links.
Pocket switched networks are a bit like gases – the nodes of the network are like gas molecules constantly moving around. A traditional network is like a solid – all the molecules, and so nodes, are stationary. As more people join a gaseous network it becomes more like a liquid, with nodes still moving but bumping into other nodes more often. The Cambridge team are exploring the benefits of networks that can automatically adapt in this way to fit the circumstances: making phase transitions just like water boiling or freezing.
One of the important things to understand to design such a network is how people pass others during a typical day. Are all people the same when it comes to how many people they meet in a day? Or are there some people that are much more valuable as carriers of messages. If so those are the people the messages need to get to to get to the destination the fastest!
To get some hard data Jon and his students have been handing out phones. In one study a student handed out adapted phones at random on a Hong Kong street, asking that they be returned a fixed time later. The phones recorded how often they “met” each other before being returned. In another similar experiment the phones were given out to a large number of Cambridge students to track their interactions. This and other research shows that to make a pocket switched network work well, there are some special people you need to get the messages to! Some people meet the same people over and over, and very few others. They are “cliquey” people. Other more “special” people regularly cross between cliques – the ideal people to take messages across groups. Social Anthropology results suggest there are also some unusual people who rather than just networking with a few people, have thousands of contacts. Again those people would become important message carriers.
So the dolphins may be the “early adopters” of pocket switched networks but humans may be not far behind. If so it could completely change the way the telecom industry works…and if we (or the dolphins) ever do decide to head en-mass for the far reaches of the solar system, pocket switched networks like Haggle will really come into their own.
This article is based on a talk given by Jon Crowcroft at Queen Mary University of London in January 2007.
Missed one of our festive puzzles?
We’ve posted some Christmas kriss-kross and pixel puzzles (with the answers being posted the day later). If you’ve missed the earlier posts here’s a bumper edition of all of the Advent puzzles so far (and the answers will come tomorrow).
cs4fn 