What could have been
Back just after I left Sun, Larry McVoy was circulating The Sourceware Operating System Proposal. Sun delayed, linux happened, and now Sun is fighting against HP and IBM, both armed with linux.
Imagine the world if Sun had instead found it in its heart to open source what was then SunOS 4.1, which already ran on SPARC, x86, MIPS and Motorola platforms. Linux would probably be 5 years ahead of where it is now, Sun would still be selling tons of hardware, and SCO would have shut the doors back in the .com boom.
equilibrium,
balance of body and mind
holding quicksilver.
Owning technology can be a lot like quicksilver, to hold it you have to open your hands. Attempt to control by tightening your grip and it escapes.
Jim on 07.07.04 @ 06:53 PM PST [link]
Ukraine's Snickers Bar
"Young girl, come and try my tasty salo, it's super salo." link
But its not the first time I've run across Chocolate Meat
The question becomes... is it Atkins-friendly?
And another question for all of you Atkins devotees, are you an honest-to-cripes Atkins dieter with the little urine test strips and the blood analysis and the better living through diabetes rhetoric, or are you just some wannabe who hates salads?
Jim on 07.07.04 @ 04:44 PM PST [link]
Even Microsoft does Mesh
Microsoft Research appears to have gotten on the Community Wireless train.
Researchers in Microsoft Research Redmond, Cambridge, and Silicon Valley are working to create wireless technologies that allow neighbors to connect their home networks together. There are many advantages to enabling such connectivity and forming a community mesh network. For example, when enough neighbors cooperate and forward each others packets, they do not need to individually install an Internet "tap" (gateway) but instead can share faster, cost-effective Internet access via gateways that are distributed in their neighborhood. Packets dynamically find a route, hopping from one neighbor's node to another to reach the Internet through one of these gateways. Another advantage is that neighbors can cooperatively deploy backup technology and never have to worry about losing information due to a catastrophic disk failure. A third advantage is that this technology allows bits created locally to be used locally without having to go through a service provider and the Internet. Neighborhood community networks allow faster and easier dissemination of cached information that is relevant to the local community.
Source and binaries to their implementation are also available.
Microsoft Research has implemented ad-hoc routing and link quality measurement in a module that they call the Mesh Connectivity Layer (MCL). Architecturally, MCL is a loadable Microsoft Windows driver. It implements a virtual network adapter, so that to the rest of the system the ad-hoc network appears as an additional (virtual) network link. MCL routes using a modified version of DSR (which they claim as an IETF protocol, though it isn't) that they call Link Quality Source Routing (LQSR).
Their MCL driver implements an interposition layer between layer 2 (the link layer) and layer 3 (the network layer). To higher layer software, MCL appears to be just another Ethernet link, albeit a virtual link. To lower layer software, MCL appears to be just another protocol running over the physical link. It has several other interesting features as well, including support for a proposed improvement to ETX that they call ETT (Expected Transmission Time).
More interesting, given yesterday's discussion, is that Microsoft has already published results on using multiple radios.
Victor Bahl has also published a proposal to allow co-ordinated channel hopping called Slotted Seeded Channel Hopping (SSCH) that requires no leader election or other centralization. This isn't 802.11s Frequency Hopping, but rather a method to allow multiple 802.11b, 802.11g or 802.11a radios to change channels in a co-ordinated manner in order to increase capacity. The paper shows that this can acheive results comparible to using several radios, while the cost and complexity of the resulting solution will be much lower.
There are other interesting papers on the page as well. here they show that ETX is a near-optimal routing metric when all the nodes are stationary (as they would be in a neighborhood mesh network). Presumably they then discovered an improvement (ETT, above).
There is even a paper co-authored by Jim Kujiya on building a low-cost steerable array using dielectric phase shifters. I met Jim Kujiya back in 1991-1993 when Jamie was acting as the Electronic Theatre chair for SIGGRAPH 93. Kujiya is probably best known for his work on the Evans & Sutherland frame buffer, so its good to see him doing things outside of computer graphics.
So if you're a VC who has funded a mesh-based product company, you might want to ask a few questions at your next board meeting. Questions such as, "Why didn't you tell me that Microsoft is doing mesh?" and "Why did you (use my money to) pay to license TBFPR?" And then ask yourself how you're going to make your investment back from a company who's only competence seems to be in using other people's hardware with other people's software?
Jim on 07.07.04 @ 04:26 PM PST [link]
Do Mesh Networks Scale? Another (biased) View
Glenn reports that Francis daCosta of Mesh Dynamics says that mesh networks won't scale, at least, not without using multiple radios (on multiple channels).
Francis makes several statements, lets analyze:
1- Radio is a shared medium and forces everyone to stay silent while one person holds the stage. Wired networks, on the other hand, can and do hold multiple simultaneous conversations.
Nothing about radio forces everyone (presumably all stations) to stay silent while one "person" (station?) holds the stage. This is a property of several MAC protocols used in radio-based networks, including CSMA/CA (used in 802.11), but is not a fundamental property of radio networks.
(Further, "interference" is a receiver artifact, but we won't go into that now.)
These aren't even new results. Gupta, Gray and Kumar published an empirical paper several years ago named An experimental scaling law for ad hoc networks that showed this in a real world experiment. Their results were that 802.11 ad-hoc networks scale at c/n^1.68, where 'c' is capacity and 'n' is the number of nodes in the network. The problem is indemic to the 802.11 MAC protocol, which is not adaptive, and requires that all stations be able to hear each other.
2- In a single radio ad hoc mesh network, the best you can do is (1/2)^^n at each hop. So in a multi hop mesh network, the Max available bandwidth available to you degrades at the rate of 1/2, 1/4, 1/8. By the time you are 4 hops away the max you can get is 1/16 of the total available bandwidth.
Agreed (for 802.11 in ad-hoc), but this was shown in the Gupta, Gray and Kumar paper cited above. Old news.
But this is not true once you are willing to throw out the 802.11 MAC protocol.
Tim Shepard's 1995 thesis "Decentralized Channel Management in Scalable Multihop Spread-Spectrum Packet Radio Networks" (and the more concise paper based on it) - which demonstrates that one can build a practical network whose capacity increases the more stations you add.
The rate of increase is square root of N, for N stations, and this contrasts sharply with daCosta's viewpoint. Of course, as I've already stated, daCosta is speaking about 802.11 without naming it.
The key ideas of Dr. Shepard's thesis are to build a network of cooperative repeaters, use no more power than necessary, and to schedule the transmissions from each node. He even proposes a novel method of scheduling the stations in a completely distributed fashion.
Many have noted that I am a fan of the chipsets from Atheros, but few have ever queried 'Why'. (Nigel Ballard did once, at a PTP meeting where I spoke the day after leaving Vivato.)
The reason 'Why' is that the Atheros chipsets do not implement the 802.11 MAC protocol. It is straight-forward to implement your own MAC layer on top of the Atheros design, and the madwifi driver proves it. While there are other chipsets with a similar architecture today.
You connect the dots.
3- That does not sound too bad when you are putting together a wireless sensor network with limited bandwidth and latency considerations. It is DISASTROUS if you wish to provide the level of latency/throughput people are accustomed to with their wired networks. Consider the case of just 10 client stations at each node of a 4 hop mesh network. The clients at the last rung will receive -at best- 1/(16,0000) of the total bandwidth at the root.
Unfortunately, this point fails as well. Tim's thesis quite clearly shows that it can work in a 1,000 node network. There are still limits, especially in the area of latency (read the thesis!), but work proceeds on asyncronous radio relays
4- Why has this not been noticed as yet? Because first there are not a lot of mesh networks around and second, they have not been tested under high usage situations. Browsing and email don’t count. Try video - where both latency and bandwidth matter - or VOIP where the bandwidth is a measly 64Kbps but where latency matters. Even in a simple 4 hop ad hoc mesh network with 10 clients, VOIP phones wont work well beyond the first or second hop – the latency and jitter caused by CSMA/CA contention windows (how wireless systems avoid collisions) will be unbearable.
Fortunately these effects are very easy to model in a simulation environment. Most of the IETF work on mobile ah-hoc routing shows results based on the simulation environments "ns", "glomosim" and the commercial "opnet". Some of these packages contain (or have access to) quite accurate models of the wireless channel, and even the 802.11 MAC and PHYs
daCosta is going to propose multiple radios as a solution to the problems he shows. (See, I can predict the future too!)
Obligory disclosure: Francis and I have known each other for a few years now, and we may develop some hardware for him if things work out. Its early in the relationship, and given my personal/professional history over the last 5 years, I'm far less willing to enter into partnerships than I was. There are problems with this "multi-channel" approach, but it might provide some benefit. Its also likely that my mention here will scorch the relationship when/if Francis ever reads thsi.
The real solution, however is to not use a MAC protocol that was designed for something very different.
Coverage on a few more points:
I think many of the ideas in this are wrong-headed.
It promulgates the "spectrum as property" lie, when the real solution is to treat spectrum as a commons.
It proposes a 500mW (27dBm) power limit for unlicensed operation, but this is only 3dBm lower than the highest current limits in all of the ISM and U-NII bands, and it can be quite challenging to find (or design) a Wi-Fi card that will generate more than 200mW (23dBm). Some solutions exist. I do agree with Sascha that the transmit power should be adjustable, (and therefore, I've enabled it on this unit.) I don't have the "full-auto" stuff working yet though. Natch.
It provokes conspiracy theories about the demise of CoMeta and its investor's motives. The simple truth is that it was a group of old-farts with a pile of money looking to cash in on the WiFi craze. So they went off tilting at windmills following the Don Quixote de la Mancha of this modern age, Dr. Brilliant.
There is an old addage known as Hanlon's Razor: Never attribute to malice that which is adequately explained by incompetence. Intel, ATT and IBM all had different agendas. AT&T thought it would get to sell a lot of leased lines and DSL. IBM Global Services was to provide all the logistics. It was a money grab by extremely dumb players, pure and simple. What makes it worse is that Larry Brilliant had failed before at exactly the same game when Aerzone went thud, followed by the rest of Softnet.
It views WCA and the "wireless industry" as the enemy, insisting that they have deliberately slowed innovation, and this, dear reader, is some serious tilting at windmils:
Look there, friend Sancho Panza, where 30 or more monstrous giants rise up, all of whom I mean to engage in battle and slay, and with whose spoils we shall begin to make our fortunes. For this is righteous warfare, and it is God's good service to sweep so evil a breed from off the face of the earth."
Sascha may not be familiar with The Inventors Dilemma. It is an excellent book written by Clayton Christensen (in 1997) about how successful businesses decline and fail. The basic hypothesis is simple: Successful businesses grow and eventually dominate their target market. When they fail, it is usually because a newer company with different technology eats their lunch.
But, according to Christensen, this happens because the newer technology is "disruptive". It doesn't compete head-to-head with the incumbent giant, but initially gains its success in an adjacent market before taking the incumbent head-on. The interesting part of this is that the incumbent always takes decisions, which are in themselves rational, sensible and defensible in respect of its primary market and this naturally leads to its demise. It can never get into the position of being able to compete directly with the "disruptive" technology.
Finally, I'm of the opinion that Sascha is chasing rabbits with his advocacy of A-HSLS. He may have read this presentation (warning, its PowerPoint, PDF is here), and then failed to notice that TBRPF and OLSR are only mentioned in passing.
TBRPF is the 'mesh' protocol used by many people who are attempting to market "mesh" equipment. It has an advantage in being an IETF standard, but as far as I know, no open or free implementations exist.
I think OLSR (which is also an IETF RFC standard) is a better protocol, if only because several implementations exist, all of them free (as in speech) software.
Of course, the router heads at Cisco have proposed manet extentions to OSPF. If you've followed this far, you may find this presentation by Fred Baker of Cisco to be good reading.
I do, however agree that ETX is a good choice for a routing metric for wireless networks. I just happen to know someone who is implementing ETX in OLSR.
Community wireless" or free networks will happen, and they will grow in a 'bottom up' fashion. They will not, however, be a purely "wireless cloud" covering the skyline. There is far too much utility in getting the data off the wireless network and onto a wired network.
OK, so to review:
1) 802.11 won't scale. Mesh based networks based on 802.11's MAC won't scale. I agree.
There are commodity "Wi-Fi" chipsets that allow one to completely bypass the 802.11 MAC, however.
2) Mesh can scale.
There are information-theoretic proofs that it will. These go far beyond both daCosta's and Meinrath's presented analysis.
3) Community wireless networks will happen, and there is nothing that the carriers or telcos can do that will stop it.
p.s. this article may be full of hints about what I'm working on at 2am. It may also be the case that I am full of crap.
Jim on 07.07.04 @ 02:03 AM PST [link]