Kuro5hin.org: technology and culture, from the trenches
create account | help/FAQ | contact | links | search | IRC | site news
[ Everything | Diaries | Technology | Science | Culture | Politics | Media | News | Internet | Op-Ed | Fiction | Meta | MLP ]
We need your support: buy an ad | premium membership

Routing through a changing topology?

By Farq Q. Fenderson in Internet
Tue Oct 03, 2000 at 08:57:19 PM EST
Tags: etc (all tags)

One of my dreams is to see a somewhat Gibsonesque internet: an ambient one. Imagine turning on your PDA with an RF device in it, and sending your packets around the world. Wouldn't it be nice if your access was made possible by sending your packets through other PDAs?

The problem is routing. The network topology changes every second with people moving in and out of range. How do I send packets to Japan, let alone down the street? How do they find me? How do I know where the computer is that I want to send the packets? Basically, how on earth does one route through an everchanging network topology?

I've had a few ideas but I haven't had time to test them. One of them involved creating yet another program-a-robot game, in which robots would rout the packets, as if they were the PDA themselves, with scoring rules so that those that routed most efficiently would get more points. This was to encourage people to design the best possible routing system.

The more I think about it, though, the more I wonder whether it's actually possible. Is there actually enough data present to route efficiently with? How much route data should be transmitted? The whole route a given packet has taken? The last X hosts? Would GPS help? Any ideas?


Voxel dot net
o Managed Hosting
o VoxCAST Content Delivery
o Raw Infrastructure


Routing through a changing topology is like:
o Trying to find a date. 19%
o Trying to escape a 'date.' 8%
o Networking with tin cans & string. 6%
o Pretending friction doesn't exist. 22%
o host_no = (int)((rand() * no_hosts)/(RAND_MAX +1)); 42%

Votes: 61
Results | Other Polls

Related Links
o Also by Farq Q. Fenderson

Display: Sort:
Routing through a changing topology? | 29 comments (29 topical, editorial, 0 hidden)
Dern near impossible I'd say (2.09 / 11) (#1)
by Hillgiant on Tue Oct 03, 2000 at 06:15:35 PM EST

Today's PDA have prescious little processing power as it is. I really don't want some joker downloading Pr0n or /. summaries to eat up my processor clocks / ram / bandwidth.

"It is impossible to say what I mean." -johnny

It would be difficult to find somebody... (3.60 / 10) (#2)
by ramses0 on Tue Oct 03, 2000 at 06:17:22 PM EST

This is an incredibly interesting topic. If you haven't had the chance to take a networking course, you'd probably really enjoy it.

Anyway... It would seem like the number of nodes in the network would be prohibitive. The idea behind most routing algorithms is to lower the number of hops from the current node to the destination.

The only trouble is that there is absolutely no way to know if you're getting closer to that PDA halfway around the world or farther away. My guess would be that GPS would help tremendously in order to 'score' a routing algorithm. It's not perfect, but:

a) If you don't know whether a certain PDA is at the North Pole, or the South Pole, or Australia even, you have to send the packet to both places, and hope that it gets there.

b) with 100million nodes in the network, in order to reliably reach any particular node, you'd need to know where it is. Meaning that your node-cache table would be really really big.

Take a look at the Gnutella protocol for an example of this: Gnutella Protocol ... Besides all the buzz about mp3's and file-sharing capabilities of gnutella, it's still really interesting to read the protocol specification.

[ rate all comments , for great justice | sell.com ]

GPS Essential (3.71 / 7) (#3)
by Jonathan Walther on Tue Oct 03, 2000 at 06:52:32 PM EST

The problem is not so much how to get the data out, but how to get it to its target. We could make a simplifying assumption that noone on the network will be travelling faster than a certain speed (1000mph?), and do something like cell phones do. Cell phone networks have already solved the problem. It just needs massive implementation from a network point of view.

Does anyone present know how cell phones are located? I know little about them, other than there are neighborhood aggregators, and, as with the internet, there are "tiers", by which traffic is routed between larger and larger regions.

With this kind of topology, the network doesn't really change except at the leaf nodes. That simplifies things tremendously.

I don't think any "truly changing topology" solution will be feasable or practical until every PDA can broadcast at incredibly high speeds to any PDA within a certain distance of it. So a better question is: when will these things be available?

With builtin GPS, we can do something akin to packet radio; so again, the problem is solved. But where is the technology that would make it feasible? And how can we rely on our fellow citizens to be willing to let their PDA's be used for that purpose? Most people would much rather pay a utility company to route their traffic than go through a neighbors machine. Its something like the way we use public roads rather than driving across our neighbors lawns. The average customer will buy the PDA's that don't act as nodes on the network because they'll be cheaper. Why pay more to be part of such a thing? There will have to be an obvious cost benefit to routing through your neighbors. "Privacy" isn't a compelling enough reason to make such a network take off. I truly wish it was though. The mass of consumers that decide these things with their dollars are mostly idiots who don't understand cool things. I sigh for our future. <sigh>

(Luke '22:36 '19:13) => ("Sell your coat and buy a gun." . "Occupy until I come.")

Re: GPS Essential (4.50 / 4) (#14)
by charter on Wed Oct 04, 2000 at 02:55:11 AM EST

Does anyone present know how cell phones are located?

Sadly, yes. I spent a few years working for US West Wireless before they became Airtouch (currently Verizon).

Cell phone companies solved the routing problem with one word: infrastructure. And lots of it.

Every cell phone in the world has an identifying number called an ESN. If you have a cell phone, your ESN is probably printed on a sticker located at the back of the phone or on the battery case.

Whenever your phone is turned on, it's constantly broadcasting its ESN. This is what lets the wireless network locate your phone so that it can "deliver" a phone call to you.

(When people talk about a "cloned" cell phone, what they mean is that some naughty person has either captured or conned the ESN from a legitimate user's phone and programmed it into another phone. All the network cares about is your ESN, and it doesn't much care who's who. Often the cloning isn't caught until the legitimate user gets their bill and notices that it's thousands of dollars higher than it ought to be.)

An ESN is pretty much the same thing as a static IP, and there's really no reason why a wireless internet couldn't work as well as the current wireless telephone network. It'll just be awfully expensive and time-consuming to implement.

-- Charter

[ Parent ]
Re: GPS Essential (3.50 / 4) (#15)
by RadiantMatrix on Wed Oct 04, 2000 at 04:41:21 AM EST

Does anyone present know how cell phones are located?
A different reply mentions how to locate cellular phones in terms of them being network nodes, so I won't mention that here. Instead, I'll answer the other part of the question.
  1. How do they know which tower to use? The reason that most mobile phones are called cellular phones is that they operate in service "cells." Imagine a [highly irregular] honeycomb of coverage zones, with each cell being a tower's transmission range. When you pace a call, the phone broadcasts what amounts to a ping - the cell that responds with the best signal is then chosen to start the call. For the duration of the call, the phone and network work together to make sure that the signal is always coming from the most appropriate cell - thus your calls (usually) don't get dropped as you travel.
  2. How do you pinpoint a geographic location of a cellular phone? Each phone has a unique ID called an ESN - think of it as a network address. Each phone also continuously broadcasts a signal that is recieved by the cellular network towers. If you have three (or more) towers that are recieving this broadcast, you can triangulate the position of the phone. Scary eh?
Hope that adds something...
I'm not going out with a "meh". I plan to live, dammit. [ZorbaTHut]

[ Parent ]
Why I think backbones are a Good Thing (3.50 / 8) (#4)
by Miniluv on Tue Oct 03, 2000 at 07:01:08 PM EST

As available bandwidth in the last mile increases, the demand on bandwidth over the long haul increases with it, though at a somewhat slower rate. The problem here is that we're reaching the limits of media currently available, and the new media getting ready to be rolled out is literally too fast. Read here to see how MCI is planning on dealing with the long haul crunch.

The problem with peer to peer networking on a large scale is wasted bandwidth. The assumption is of course, that more nodes means more possible routes, and thus "shorter" routes. The issue isn't physical distance between routes, or even necessarily node count, as much as available bandwidth and latency between nodes. Two PDA's on a wireless network cannot offer the sort of bandwidth to match an OC-48 longhaul backbone run. Wireless devices are going to remain border devices for a long time to come, until wireless offers more bandwidth than we can dream of at this point.
"Its like someone opened my mouth and stuck a fistful of herbs in it." - Tamio Kageyama, Iron Chef 'Battle Eggplant'

My best guess: Dynamically updated routing or DNS. (3.71 / 7) (#5)
by Christopher Thomas on Tue Oct 03, 2000 at 08:03:56 PM EST

My best guess as to how to route to a moving target: a system of either dynamically updated routing tables or dynamically updated DNS tables.

Both are sub-optimal, but as you point out, something like this will eventually be needed.

  • Dynamically updated routing tables.

The cornerstone of this system is twofold - first, the assumption that all members of an IP subnet will be in the same general geographic area (dangerous assumption as you get to larger subnets), and secondly, the assumption that you will spend most of your time in one physical area. The system will survive the breakdown of either assumption, but performance will degrade.

The dynamic routing system would work by having your PDA publish to the local routing network the fact that it exists. The routers in the local subnet's backbone would add an entry to their tables saying, "yes, I can route to this PDA's IP", and in turn tell the backbone that they have a valid route to the PDA. When the PDA leaves the regional transciever's range, the transceiver tells the local routers that it can no longer route to that IP, and the local routers in turn propagate this information back up, to prevent stale routes from continuing to be tested.

As long as you're in your home subnet - the one in which your IP address would sanely reside - routing stays sane. When you move into a different subnet, there is no logical connection between your IP and the IP of your local gateway, but the routing tables still update themselves quickly enough for you to be found.

We do this to some extent already; the system above just enforces rapid updates and rapid _removal_ of dead routes.

Method number two:

  • Rapidly updated DNS tables.

In this scheme, you'd be assigned a dynamic IP by whatever network you happened to be passing through. When you change subnets/IPs, your DNS entry is updated at the local server, and is in turn propagated up the chain to the master DNS network in a matter of seconds.

This keeps routing sane.

The problems:
  • This would involve an overhaul of the DNS system. Current domain name control doesn't allow updates this quickly, or at least not easily, if I understand the administrivia involved.
  • Everyone would have to get their own personal domain name - you couldn't use (host)@(company.com) any more, as you'd vanish from the company's subnet whenever you moved out of their transciever range.
  • Complex handshaking would be required, because otherwise any twit who can forge packets could redirect your domain name using the same routing scheme that lets you be dynamically relocated.

The routing table method is probably more robust and least painful to implement, but it's an interesting problem either way.

It's called Nomadic Computing (3.75 / 8) (#6)
by jabber on Tue Oct 03, 2000 at 10:10:03 PM EST

And it has been the subject of research for a good many years.
A simple seach on google turns up dozens of references that address the routing issue quite nicely. Now... how do we secure it?

[TINK5C] |"Is K5 my kapusta intellectual teddy bear?"| "Yes"

Better alternatives coming soon (tm)! (3.75 / 8) (#7)
by Aztech on Tue Oct 03, 2000 at 10:12:54 PM EST

What you’re proposing is a kind of ‘PDA-nutella’, it's interesting to say the last, but not in the least bit practical. To start with IrDA has to go, whilst the speed can be potentially good (~4mbps) the range is bad, and that whole line-of-sight thing is a no-no. Unless everybody constantly walks round with their PDA positioned in their hand like zombies, it wouldn’t work.

You have to remember Bluetooth is already addressing these issues, there are a few classes of devices in Bluetooth, ‘Class I’ is basically close proximity mode, where the device will communicate with other devices at ~ 1mbps within a 30ft range, this is great for the ‘PAN’ (Personal Area Network) concept, i.e. automatically accessing your cell phone through your PDA or laptop etc, or syncing up with a colleague.

‘Class II’ devices allow a broader 300ft range at a slower ~ 400kbps speed, so for instance say you could be sitting in a Café that provide net facilities, so your PDA would be automatically linked up to the net without wires then automatically sync itself up with new messages, events etc. Think of this as a scaled down version of a wireless LAN (IEEE-802.11b).

Then we have the promise of 2.5G and 3G cellular networks, as you’re probably aware Handspring have just launched their GSM/PDS (PDS right?) modules, which obviously link you up to the net and provide voice facilities literally anywhere you go. This is an important step is getting PDA’s connected up, however the old dialup circuit switched concept has to go.

A service called GPRS (General Packet Radio Service) was launched in the UK this summer by Cellnet, it offers an always on 115kbps connection at a flat rate but at a costly $75 month, people have also commented the speed is more like 40-50kbps. This hasn’t hit mainstream yet due to the price and the inabilities of WAP to take advantage of the bandwidth, however, an always-on packet switched service is a step in the right direction.

3G are set to offer even more, the new standard UTMS is entirely packet switched so even your voice calls will just be sent as packets, opposed to distinctly allotting a frequency to your phone for each call. People have estimated a potential 2-4mbps to each node, not too bad for video stream? (hmm, p0rn on phones?)

Putting PDA’s aside, what I find intriguing is the guerrilla type network l0pht proposed, where everybody links up via wireless networks in a totally decentralised banner (again, the gnutella model). In urban areas could you imagine sticking a 802.11b PCMCIA board into your laptop/pda and being online through these guerrilla networks? It's certainly an underground alternative to potentially costly cellular networks, not to mention the potential for ensuring free speech. Wired has a story about such networks being patched together in London.


Re: Better alternatives coming soon (tm)! (2.66 / 3) (#13)
by Michael Leuchtenburg on Wed Oct 04, 2000 at 01:27:34 AM EST

Argh! EVIL distorted MS-ASCII. Hates it we do. Hopefully the Scoop community will see fit to add a filter... (just submitted a suggestion). But until then, and for other places: Does anyone know of a way to make IE not use the evil MS-ASCII characters? Is there a smartquote option in IE like there is in Office?

[ #k5: dyfrgi ]
[ TINK5C ]
[ Parent ]
Re: Better alternatives coming soon (tm)! (3.00 / 1) (#19)
by Aztech on Wed Oct 04, 2000 at 11:39:00 AM EST

doh! sorry about that ;)


[ Parent ]
Re: Better alternatives coming soon (tm)! (3.00 / 2) (#25)
by h2odragon on Wed Oct 04, 2000 at 04:52:07 PM EST

For those unaware of it: Demoroniser, a simple Perl script to filter MS-ASCII. All hail John Walker.

[ Parent ]
Gnutella problem (3.16 / 6) (#8)
by ronin on Tue Oct 03, 2000 at 10:15:08 PM EST

I think this points to sort of the same problem that Gnutella has. How do I find a file (or a route to a host)? I ask a neighbour who in turn asks 5 neighbours who each in turn ask 5 more. The speed of the response depends on the speed of the neighbours as well as the amount of traffic. This is not an ideal situation at all.

I colleague at work recently bought a wireless modem that does something like 128k. Speed wise it's ok, but it's wireless remember. The service provider essentially puts little wireless modem recievers with built in switches and routers all over the place (on telephone poles and whatnot - something like 5 per sq mile). They can determine distances or something like that and so they pass you along to the closest one as you move around.

I think that's a better solution than peer to peer DNS. It doesn't suffer as many scalability issues. Of course that sort of system - to become widespread and not suffer the incompatilbilities of too many vendors with incompatible protocols would need some work.

Viral Communication (3.00 / 6) (#9)
by FFFish on Tue Oct 03, 2000 at 10:59:34 PM EST

I had similar ideas way the heck back when infrared links first started gaining popularity.

My thinking was to create a very small version of the Citadel BBS system. It's discussion oriented and pretty free-form.

It'd spread virally, both the software and the message database. Who you read would mainly depend on who's computers your communicated with during the day. Theoretically, everyone's messages would eventually make it to everyone else; but it isn't really important for it to be quick. BBS discussion is asynchronous anyway.

Of course, I never did create this wonderful viral discussion tool. Good thing, too, or we'd all be trying to chat it up through our Palm pilots today... (or, worse, Casio databank watches!)

Re: Viral Communication (3.00 / 1) (#27)
by sbeitzel on Fri Oct 06, 2000 at 04:43:16 PM EST

Hmm. Sounds like the Lightweight Asynchronous Communications System (a.k.a. "Rumor Monger") on the Mac. That was pretty cool; you'd fire up the client and it would periodically send out its address over the LAN (this works because AppleTalk is a "chatty" networking protocol). It would also listen for other Mongers and then periodically it would exchange "rumors". Except for the bootstrapping (getting the initial communication partner), this is pretty much what Gnutella does.

[ Parent ]
The Wheel of progress (3.50 / 6) (#10)
by mihalis on Tue Oct 03, 2000 at 11:05:43 PM EST

As I thought about this I had a couple of ideas. Firstly it seems to me a more interesting problem than trying to get your packets all the way around the world via PDA would be to solve the problem of getting them to the nearest gateway. Once they get there the rest is easy. This seems more solvable and hence more interesting in the short term.

Secondly it occurred to me that networks already have a changing topology. If you think about it, hosts are not always on and routers sometimes throw away data when they fill up. Also there are bugs and other problems with hosts to the extent that network topology can eaily keep changing long enough that protocols have to deal with it. There are already protocols for establishing useful subsets of all theoretically connected hosts such that a coherent network can operate even in the case where there may be mulitple gateways between local subnets - e.g. the spanning tree algorithm (e.g. see this). The first time around all computers were slow and unreliable because that's the best we could do, but now we can apply similar techniques to computers that are deliberately small and "weedy" so that they fit in the pocket and don't need much power.

So if we assume all the local PDAs could use these known techniques to rapidly and spontaneously organise into a wireless LAN, then all we need to add on top is some kind of gateway discovery process which could be quite dumb and rely on broadcast - send out a "I need to get to the real internet folks" message on the local lan. Accept the quickest response and pump out the packets in that direction. Each wireless LAN would have heartbeats of some kind and you'd simply assume you'd left the last lan whenever you started getting different sequence numbers in the heartbeats (and hence try to re-establish the spanning tree), or you'd assume you were incommunicado if you stopped getting them.

So now if I had an antenna in the window of our office and this network worked over ranges of 5 feet I reckon there are enough Palms between me and the window to route my packets there so I could telnet to my home machine without my company being able to see the packets going through the firewall. I like it.
-- Chris Morgan <see em at mihalis dot net>

It's being done (3.00 / 6) (#11)
by AirBoss on Tue Oct 03, 2000 at 11:23:53 PM EST

A lot of the stuff you're talking about is already being done. The Internet _is_ dynamic, the topology _is_ constantly changing.

People have been answering the question "how on earth does one route through an everchanging network topology?" for years. The answer is dynamic routing protocols, which have been in use in some form or another for decades.

The only new idea here is that you want to use PDAs as routers, all running some kind of link-state routing protocol such as OSPF. They're better off sending all of their traffic to a gateway node, like your average LAN does, than trying to route through eachother -- PDAs are not optimized for routing, and it's not like your average PDA user wants his bandwidth/CPU hijacked by some freeloader grabbing the latest 15-meg tarball from ftp.kernel.org.

It's a neat idea, though. Just not practical, and really not that new.

See the IETF's MANET group. (3.60 / 5) (#12)
by jason on Wed Oct 04, 2000 at 01:13:02 AM EST

The MANET WG is working on precisely this. I liked TORA from a theoretical viewpoint, but AODV looks more practical. (I seem to recall there's a serious problem with TORA, but I can't remember it. Anyone else?) DSR is pretty cool, too, but I'm more interested in a huge ad-hoc network rather than smaller pockets.


Not today, not tomorrow... (2.20 / 5) (#16)
by operandi on Wed Oct 04, 2000 at 06:29:04 AM EST

Given current bw limitations, especially in wireless applications, you'd quickly find yourself in the same position as gnutella. Routers are Big Iron for a reason, because they are bottlenecks. Am I wrong?


Random ideas! (1.66 / 3) (#17)
by vinay on Wed Oct 04, 2000 at 10:33:46 AM EST


To build off of a few other ideas found in this thread: I like the idea of having some sort of gateway so that, upon entering into a particular service area (a working name.. yeah..), you register with the gateway and it then acts as your umm.. well, gateway to the net. It would route all packets (to dedicated, static servers, as well as to more dynamic hosts, such as other PDA's). In the case of sending/recieving info from other PDA's, the entire transaction would be handled by the gateways. My theory is that, once you register with a local gateway, it can reach you. The issue then becomes finding that right local gateway without broadcasting to half of creation. In response to this, I'd propose that maybe some kind of home gateway thingy be utilized (eloquent, ain't i?), much like a local calling area/area code. That way, you could send a message out to someone's home gateway, and then, if they're not there, it could route your message to the appropriate gateway. From then on, you could cache the new gateway, with perhaps some kind of lease. (heck, with proper permissions, maybe you could sync the lease with someone's addressbook/itinerary.. wow.. that'd be cool).

The one (admittedly) major issue I have with this scheme I cooked up is privacy. How do we insure that information we want private is kept that way while also seeking out information we want. As in, what if I want to talk to you, but don't want my location known? Conversely, what if I want to talk to you, and you don't want your location known? Any ideas?



HELLLLLLLLLLS NO. (security?) (2.00 / 3) (#18)
by vanguard(dc) on Wed Oct 04, 2000 at 10:40:12 AM EST

see my title.

In a perfect world, nobody steals, cheats, embezzles or blackmails...

but this is a REAL world, so no... because as long as we have "packets" traveling anywhere, there will be people sniffing for them. And using bouncing pda's makes that a bit too easy...


(pentest specialist!)

Re: HELLLLLLLLLLS NO. (security?) (3.00 / 1) (#21)
by Farq Q. Fenderson on Wed Oct 04, 2000 at 01:56:28 PM EST

Pretend for a moment that sniffing isn't an issue. This could be done with RSA keys, for example. Now all your packets (minus necessary routing info) are encrypted, and only your traget can decrypt them.

farq will not be coming back
[ Parent ]
also along these lines (3.33 / 3) (#20)
by piwowk on Wed Oct 04, 2000 at 01:51:13 PM EST

see the MIT Project Oxygen page:http://www.oxygen.lcs.mit.edu/.

Perhaps this is an instance of an "ad hoc&quo (3.66 / 3) (#22)
by akkem on Wed Oct 04, 2000 at 02:12:09 PM EST

The Monarch project at CMU has developed routing algorithms for use in "ad hoc" networks - networks where there's no set routing or infrastructure. The general scenario they're building for is a network made up of devices constantly coming in and out of range of each other. I think there's work in this area in the IETF as well.

Ad Hoc network resources (4.00 / 2) (#23)
by wildmage on Wed Oct 04, 2000 at 02:23:15 PM EST

I just so happens that I'm going to be doing my senior project on just this sort of thing. They're called Mobile Ad Hoc Networks (MANETs). Fortunately for me there's already been a lot of research out there by many colleges and compaines. Let me list some of the resources I've found:

Research at my school
Monarch Project
a Berkeley page
UCLA Internet Research Lab
Wireless Adaptive Mobility Laboratory
UCSC Computer Communication Research Group

You can also subscribe to the MANET mailling list (manet@itd.nrl.navy.mil) by going to the IETF page.

Jacob Everist
Memoirs of a Mad Scientist
Near-Earth Asteroid Mining

Subscription basis, or what? (3.00 / 2) (#24)
by paryl on Wed Oct 04, 2000 at 02:46:15 PM EST

The only thing I see wrong with this is the fact that you would have a free network. I mean, if you've got a constantly changing network topology where every segment is essentially a router, those devices aren't going to be able to handle the traffic load and still be able to check if a particular packet *should* be routed (IE, Are they a paying customer?) in an acceptable time-frame.

While I'd love to see a totally free, totally ubiquitous network that could handle routing of this degree, it would put the thousands of ISP's out there completely out of business. And while I'd like to think this is a good thing, those owning the businesses wouldn't think so and would fight it tooth and nail.

Don't get me wrong.. I think a network of this sort *should* be there, I just have trouble believing that it would actually make it.

we're working on it. (none / 0) (#26)
by belial on Wed Oct 04, 2000 at 05:11:36 PM EST

check http://www.seattlewireless.net/ It's a project to start a free wireless network and abolish recurrant telco fees.

[ Parent ]
cybiko already does this, kinda. . . (3.00 / 1) (#28)
by blintz on Tue Oct 10, 2000 at 04:57:05 AM EST

From their site: What is the Cybiko Wireless Internet Gate?

The Cybiko Wireless Internet Gate (CWIG) is a PC connected to the Internet and a Cybiko device containing special software connected to a PC. This system provides wireless internet access for all Cybiko units located in the Cybiko's range! [my emphasis]

This means you can send and receive e-mails and utilize other Internet access wirelessly, all through your Cybiko!

Can I Set Up the CWIG at Home?

Definitely! All you need is an online PC, an extra Cybiko unit, and special free software. This software will be free to download. Check our site for availability.

I've been thinking about this, too (none / 0) (#29)
by freakazoid on Fri Oct 13, 2000 at 06:42:09 PM EST

Someone has already posted stuff about wireless ad hoc networks, so I won't mention more here other than to say that amateur packet radio already does this sort of thing. Having packets passed around by other nodes in a semi-random manner is called "gossiping." It is similar to how Gnutella works.

An even nicer feature to me would be being able to connect into such a network anywhere and have it just work, without having to pay someone else for an IP address, domain name, whatever. Each device pulls its own weight, and bandwidth is just aggregated from whatever people happen to not be using at a time. It would be even more of a "best effort" network than it is today, but I don't see anything wrong with that. I talk a little about ideas surrounding a totally decentralized Internet on my web site, mostly around a DNS that's structured by consensus, similarly to usenet.

The best structure I've been able to come up with is UUCP-like path-based routing using onion routing, where the packet is repeatedly encrypted with the public key of each node in the path. The names of each node in the path would be public key IDs or fingerprints to create a very low probability of duplication, and with the ability to prove who owns a given node name. There would only need to be one such node per administrative domain, because routing internal to an administrative domain could be handled with conventional routing techniques, and it doesn't make sense to do onion routing *within* an administrative domain because the administrator typically knows all the private keys anyway and could track traffic until it hit its first hop outside of the domain anyway.

It would be interesting if this were possible using IPv6 encapsulated in the onion routing mechanism, except that with the current IPv6 allocation scheme there would only be room for 32 or maybe 40 bits of ID if each administrative domain is to have a /48. If you only allowed 256 subnets per ID, and allocated a /8 for the entire scheme, you could get 48 bits for the ID that is derived from the public key, which might be enough.

I plan to do a lot more thinking along these lines and write something up, and possibly implement something if there is enough interest. Most of my lines of thinking have involved replacing every existing application anyway, so it may not make too much sense to make it IPv6 based, i.e. web/ftp -> freenet or blocks, email/chat -> probably not much different since they're very datagram like, telnet -> eek, interactive performance would suck.

Feedback/flames welcome.

Routing through a changing topology? | 29 comments (29 topical, 0 editorial, 0 hidden)
Display: Sort:


All trademarks and copyrights on this page are owned by their respective companies. The Rest © 2000 - Present Kuro5hin.org Inc.
See our legalese page for copyright policies. Please also read our Privacy Policy.
Kuro5hin.org is powered by Free Software, including Apache, Perl, and Linux, The Scoop Engine that runs this site is freely available, under the terms of the GPL.
Need some help? Email help@kuro5hin.org.
My heart's the long stairs.

Powered by Scoop create account | help/FAQ | mission | links | search | IRC | YOU choose the stories!