Daniel Brookshier's Blog

August 2003 Archives

Six Degrees of Seperation

It's a Small Small World After-all

August, 7 2003, the BBC reported that an article in Science had been published about an experiment that proves that by simply forwarding email among acquaintances, it only takes a chain of five to seven emails to reach a specific email user unknown by the original emailer. Why is that important? It helps prove that you can write P2P applications that let you find people or information by at most 6 steps away. This is known as Small World (first tested by psychologist Stanley Milgram) or its more popular moniker, Six Degrees of Separation (A.K.A. the Kevin Bacon theory).

Six Degrees = A Lot of People

But there is a problem with Six Degrees. There were actually a lot of people emailed in the course of the search. Think of a pyramid. You email ten friends and they email ten friends who email ten friends. At 3 levels about 1,110 might be sent with each person having ten friends. At 6 degrees it is a maximum of 1,111,110 emails. If each person knew 100 people, at 6 degrees of separation, it would be 1,010,101,010,100 people. More than enough to reach everyone on the planet. That's a lot of spam and a lot of network traffic. See the problem?

Searching for a Friendster

The six degrees problem depends on who or what you are looking for. It could be a specific person, a type of person, or even a someone at a location, a or a person who has something you want. The experiment would probably have failed if repeated too many times because the emails would be treated as an intrusion and thus spam.

www.friendster.com/ is a similar idea in connectivity (join and look for turbogeek@cluck.com). Friendster is of course a web site with a large database. They also have to pay for big servers and a lot of bandwidth. What if we duplicated a similar idea in JXTA? How could it be done?

JXTA Friends

Here is the concept. I have a JXTA pipe listening to an address that is the equivalent of my email address (one of the few things as unique as your social security number). I have a list of my friends and their email addresses. If you know me, then you know my email address and can access my friends in my address book. With access to the book, you can connect to the friend's address book to continue your search if I don't have the person you are looking for in mine.

To use the system, just connect to the pipe with my email address and ask for a contact with a person you are looking for. If I have it, I return it. If I do not have it, I can ask my friends via the same mechanism.

Too Many Friends

There is a slight flaw in this straight forward design. If we have a lot of a lot of people in the network, the number of messages could be quite large. In fact, this is the same problem Gnutella has with its search mechanism. But the answer is not too hard to solve. Just put more information on each peer and set limits on how deep searches can go. Start by replicating your friend's address books.

By duplicating address books we decrease the number of hops for each connection. Since there is a tendency for friends to flock together and thus have each other's email addresses we also reduce duplicate searches. So, in just one hop we access the close group of friends and those that are looser acquaintances (we know this by the frequency of duplicated entries among the friends).

Duplicating address books does add a little bit of storage. For example, 100 friends,each with 100 of their friends at say 256 bytes per entry is 2.5 meg. This seems like a small number with todays disk drives (my little Apple laptop has a paltry 60 Gigs). Yes, it is a waste of space to a certain degree, but is cheaper than a terabyte of disk space on a centralized web server. It also means you and your friends have a great backup mechanism for those all important address books. The best benefit though is that you save a little less than ten thousand connections for each peer contacted.

Of course there would be more to do. Security is one of the more important pieces. In addition, if we are really going to go after true 6 degrees, that's still a lot of connections. Luckily the six degrees network finds the right guy within just two or three hops. No one said software was a simple profession.

Smarter Searching

The numbers can probably be made much better. With a few networking techniques and ways to qualify the route taken, the search can be optimized. Of course I'm just talking about people in this example. If we were looking for a specific type of person (like an accountant or politician), the search space would be much smaller. It's smaller because the odds are that there is a lawyer of accountant known by at least one of your friends.

Its a Big Gulp World

Small worlds are a little easier to see when looking for types of things like the accountant or politician. Small world is a slightly different idea than pure six degrees of separation. A better example might be Starbucks Coffee, McDonalds,7-Eleven, and Wal-Mart. How close are you to one of these businesses? In effect, you are as close to one of these as are a great number of people throughout the United States and increasingly throughout the world. The network of the franchise has made the world much smaller. For example, you may need to drive a few blocks to get a coke at a 7-Eleven rather than always driving to Dallas, Texas where the original store was located. Your world is effectively smaller.

What if we replace the idea of convenience store with a peer? The peer is often just a small computer with its limited resources. A 7-Eleven is small and has a limited selection and inventory. What types of things can we put in a peer that are similar to the convenience store?

We can create small worlds in two ways. This first is to locate information geographically. For example a computer with Starbucks locations would only have addresses within a few miles of the PC (actually a large number in most neighborhoods). Another method is to repeat information. Repeating info is the same idea as the franchise or chair where each location looks identical to the next except it is conveniently located near you wherever you are. Convenience would be in relation to your geographic location via the network, LAN, ISP, etc.

Six Degree and Small Worlds networking has a lot of promise. But what can you really do with this type of software? What are other applications worth pursuing? Since P2P is here to stay, what can we use it for? I have a few ideas, but what are yours?

My Apple Does Java

From MS to Apple: Don't hate me because my computer is beautiful.

I now own an Apple. Its a nice 17" PowerBook. I still own an XP P IV 2GHz laptop and a few desktop PC's, but the Apple is used for 99% of my work.

Why an Apple? Because it is as close to Linux as I can get without having to install it myself. Linux is cool, but I like something I can blame a real company for glitches. Imagine calling you PC manufacturer to complain that your application is not running.

Support: What version of Windows are you running?

Linux User: I'm running Red Hat, the latest drop.

Support: **click**

There is also the nice feeling you get when you unpack your computer and it boots. The last laptop that I tried to convert to Linux... It was not pleasant. Suffice it to say, the experience sucked and I spent more time looking for drivers than writing software. Not that I hate Linux, but I need to spend more time working than fiddling with my OS.

Apple's Java

One of the coolest things about the Apple version of Java is its implementation of the Java shared archive (JSA). The JSA has optimized standard Java classes that would otherwise be loaded from classes.jar. The key is that these are loaded into shared memory thus saving a lot of memory and startup time for Java applications. See Java shared archive for more information.

Just to be clear, I don't work for Apple (wouldn't mind an offer though). This has just been my opinion based on current experience./p>

The Riddle of the Spinx

RTFM==QED

Sometimes you do something that surprises people. Jaws drop and wonder is seen in your friend’s eyes. You too can tap into these secrets of the ancients. See a source of hidden knowledge, known only to select few. Answer the riddle of the Sphinx, just by reading the manual.

A little knowledge, creativity and some imagination and you can change the way people think. I have just recently done just that. I do it a lot because I have a habit of reading the manual and exploring how I can apply what I have read in ways the authors have not expected. It’s a bad habit from school where I was bored with dry assignments, so I twisted them to be interesting to me, rather than the teacher. Yes, I was a rebel…

I Robot

What I have done recently is to mix a couple disassociated things to create something not really intended by the designers. The first is Robot class in the java.awt package. This is certainly one of those read-the-manual things. You may have not heard of the Robot class. Robot was probably added to Java in 1.4 to help with testing. First it can capture an image of the entire desktop or just a part of it. This is quite a cool considering that in the past Java was limited to its own windows. The second, and very surprising feature is that it can send mouse and keyboard events to the operating system. In effect, controlling the entire desktop. Quite a departure from what you thought Java could do eh?

A Remote Possibility

Of course what this meant to me was that I could do more than capture the desktop or control things for a test. This meant I could control the computer from a Java application. Specifically I wanted to do it remotely. More specifically, using JXTA.

JXTA-Remote-Desktop was born! No need to dig up bodies and piece the monster together. Just pick up a couple of pieces and read the manuals. The Jr. Frankenstein kit.

Open Source A Me

What is JXTA-Remote-Desktop(JRD)? First it is open source and hosted here at java.net. It’s a simple implementation of the remote desktop idea, like PC Anywhere, Go To My PC, or VNC. It is written in 100% Java using JXTA as a transport. The key difference from the competitors (it is hard to compete with VNC because it is free), is that JRD can connect any two PC's even if there is DHCP, a firewall, or a NAT**.

JXTA's P2P network uses other generic computers to act as middlemen for HTTP tunneling and relay of messages. This is not a big security hole because the computer behind the firewall must be a willing party to the communication, just like other HTTP tunneling applications. JXTA also has its own addressing scheme so NAT and DHCP are not a problem.

JXTA is certainly not the best choice (message rather than stream based, and it has unpredictable data rates), but it is the only choice for this type of application. Think about your average PC. You can't get to it with a URL because it has no web address. You can't depend on its IP address because it changes. And there’s usually a NAT or firewall preventing direct access. JXTA lets you access almost any connected PC no matter what its current IP address or topology.

How good is JRD? Well, it is not as good as VNC yet. There still needs to be a little work to get the screenshots to be a little more efficient. Most remote applications use the native OS to get just what changes on the screen while JRD is limited to screen shots. JRD can become better through a combination of compression and differencing techniques similar to Internet video. The I/O of mouse and keyboard are delayed quite a bit so the user does not get too far ahead of the screen updates.

JXTA-Remote-Desktop is getting closer to being a viable application. The code works and there is even a multiplatform installer. I will also have an article at P2PJournal.com soon to explain the code. Since it is open source, I am looking for help to improve it. High on my wish list is better video differencing. I challenge you to look at the code and come up with an innovating solution to this devilish problem.

More to come! Up next, running Java and JXTA applications on an Apple Macintosh!

** NAT is an acronym for Network Address Translation. Most cable modems and DSL routers implement NAT. A NAT prevents anyone from directly contacting a PC from outside your home network.

Just a Little JXTA Muse

Blog Away

Am I crazy? I write books, mentor, and architect code (oh and code what I design). I also like to juggle knives, torches, MS XP CD’s, and other implements of mass destruction. I run a couple of Java user groups, and of course, I am a Java guy. And now I blog, therefore I am.

A blog can be a diary, soap box, and a place of information. You might get the first two here, but information is my goal. Be warned my passions are Java and JXTA… and very, very bad puns. With any luck the info will keep you coming back for more...despite the bad puns.

For today's blog, on the off chance that you have not heard about JXTA, let me introduce you.

JXTA I Suppose

It’s amazing to me that every few months there is yet another Java API. Between Sun and the open source community, it’s hard to keep up. But what’s important and what gives you the most bang for the buck? I believe that JXTA is worth your effort. Oh, JXTA is short for Juxtapose.

What the heck is JXTA? Simply it is a way to interconnect home and work PC’s together. Sounds simple, but it really isn’t. The first problem is the barrier to addressing most PC’s. With NAT, DHCP, and firewalls, most PC’s cannot see each other. Web pages, email, and instant messaging are our key protocols, but they suck for applications. Worse is that to host more than a web page costs a lot of money.

Another problem with today's internet, even if you can address millions of computers, how do you find the one you want? Looking for the right data, service, or person? There is no Google for your neighbor’s PC. What if you want to talk with a group of computers? How do you constrain the messages to ‘just’ those PC’s? The more computers there are, the harder it gets.

JXTA solves the addressing problem and has some of the tools for the second. JXTA is a Peer-to-Peer protocol and API developed by Sun, and its also an open source community. JXTA includes routing, message delivery, addressing, and more for P2P computing.

Why JXTA? With JXTA, anyone can create and deploy an Internet application without laying out a load of cash. You no longer need to have a web site and an application server to do interesting applications on the web. JXTA lets you do very interesting and powerful applications with just your PC and those you interact with. It is the missing link that lets anyone write an Internet application. JXTA is the Internet for the masses.

Are servers dead then? Not at all because they still have their place. JXTA can reduce or eliminate your dependence on them. There is a point where having to pay out cash is inevitable, but you can do a whole lot for a lot less and many applications will need no server to be a success.

Sometimes servers do make sense. If you need a central authority for credit card transactions or connecting to the database to check inventories. For these types of things, mixing P2P with the normal web infrastructure of servers and especially web services makes sense and will cost less in infrastructure than just web-based applications.

There is more protocol magic in JXTA like message relays, dynamic routing, and of course a little security. JXTA is also language neutral, so it is more than just Java. I’d explain it all here, but I have a whole book for that. There are a few articles on the net and other JXTA books too. Plenty of resources for learning JXTA. I plan on making this blog yet another place to look for ideas and information about JXTA and P2P.

Time for you to learn a little JXTA. Head to jxta.org, to learn more about JXTA.

If you can really connect any computer in the world, there is a key problem of which one? We'll talk about that soon. Stay tuned!

Punishment

What came first, the chicken or the egg?

The egg.

A chicken must first eggzist!!!

This work is licensed under a Creative Commons License.