The lower-post-volume people behind the software in Debian. (List of feeds.)

While our CPU clock speeds may not be increasing as they once did and transistor density is slowing, other elements of our computing experiencing are experience impressive evolution. One such area is in the display: screen pixel density is jumping and GPUs have become remarkable systems. We are currently in a transition between "low density" and "high density" displays and the various screens in a house are likely to have a widely varying mix of resolutions, pixel densities and graphics compute power.

In the house here we have a TV with 110 dpi, a laptop with 125 dpi, another laptop with 277 dpi and phones that top out at over 400 dpi! 

Now let's consider a very simple question: what font size should one use? Obviously, that depends on the screen. Now, if applications are welded to a single screen, this wouldn't be too much of a problem: pick a font size and stick with it. Unfortunately for us reality is more complex than that. I routinely plug the laptops into the TV for family viewing. If I get my way, in the near future our applications will also migrate between systems so even in cases where the screen is welded to the device the application will be mobile.

The answer is still not difficult, however: pick a nice base font size and then scale it to the DPI. Both of the major proprietary desktop operating systems have built this concept into their current offerings and it works pretty well. In fact, you can scale the whole UI to the DPI of the system.

This still leaves us with how to get a "reasonable font size". Right now we ship a reasonable default and allow the user to tweak this. How hard can it be, right?

Well, currently KDE software is doing two things very, very wrong when it comes to handling fonts in this modern era. Both of these can be fixed in the Frameworks 5 era if the application developers band together and take sensible action. Let's look at these two issues.

Application specific font settings

What do Kate, Konqueror, Akregator, Dolphin, KMail, Rekonq, KCalc, Amarok, and, I presume, many other KDE applicationsKorganizer and Konsole have in common? They all allow the user to set custom fonts. For some of these applications it default to using system fonts but still allows the user to modify them. For some of these applications, they always use their own fonts. Neither is good, and the latter is just plain evil.

Kontact, being made up of several of the above applications, is a real pit of font sadness since each of its components manages its own font settings.

This wasn't such a big deal in the "old days" when everyone's screen was equally good (or equally crappy, depending on how you wish to look at it ;). In that world, the user could wade through these settings once and then never touch them again.

Today with screens of such radically different pixel densities and resolutions, the need to quickly change fonts depending on the configuration of the system is a must-have. When you have to change those settings in N different applications, it quickly becomes a blocker.

Moreover, if every application is left to its own devices with fonts, at least some will get it wrong when it comes to properly scaling between different screens. When applications start moving between devices this will become even more so the case than it is now.

The solution is simple: applications must drop all custom font settings.

Before anyone starts hollering, I'm not suggesting that there should be no difference between the carefully selected font in your konsole window and the lovingly chosen font in your email application. (I would suggest that, but I have a sense of the limits of possibilities ... ;) What I am suggesting is that every font use case should be handled by the central font settings system in KDE Frameworks. Yes, there should be a "terminal" font and perhaps one for calendars and email, too. A categorization system that doesn't result in dozens of settings but which serves the reasonable needs of all desktop applications could be arrived at with a bit of discipline.

With that in place, applications could rely on the one central system getting the font scaling right so that when the user changes screens (either connected to the device or the screen the application is running on) the application's fonts will "magically" adjust.

Scaling user interface to font size

The idea to scale user interface to font size is one that the current Plasma team has recently decided to adopt. I can not state strongly enough just how broken this is. Watching the results when plugging plug that laptop with the 3300x1800 @277dpi screen into the 110 dpi television is enough to make baby kittens cry tears of sadness. The reason is simple: the font sizes need to scale to the screen. When they aren't scaled, the UI becomes comically large (or tragically small, depending on the direction you are going).

.. and that's ignoring accessibility use cases where people may need bigger fonts but really don't need bigger window shadows to go with it, thank you very much.

The answer here is also very simple, so simple that both Apple and Microsoft are doing it: scale the fonts and the UI to the DPI of the screen. Auto-adjust when you can, let the user adjust the scaling to their preference.

The reason Plasma 5 is not doing this is because Qt doesn't report useful DPI information. Neither does xdpyinfo. So now one might ask where I got all those DPI figures at the start of this blog entry. Did I look them up online? Nope. I used the EDID information from each of those screens as reported by xrandr or similar tools. With the help of the monitor-parse-edid tool, which is 640 lines of Perll, I was able to accurately determine the DPI of every screen in this house. Not exactly rocket science.

With DPI in hand, one can start to think about scaling font sizes and the UI as well, independently. Doesn't even require waiting for Qt to get this right, either. All the information need is right there in the EDID block.

There is a caveat: some KVMs strip the EDID information (bad KVM, bad!), older monitors may not have useful EDID info (the last version of the EDID standard was published eight years ago, so this isn't new technology) and occasionally a vendor goofs and gets the EDID block wrong in a monitor. These are edge cases, however, and should not be the reason to hold back everyone else from living life la vida loca, at least when it comes to font and UI proportions. 

In those edge cases, allowing the user to manually tweak the scaling factor is an easy answer. In fact, this alone would be an improvement over the current situation! Instead of tweaking N fonts in N places, you could just tweak the scaling factor and Be Done With It(tm). There is even a natural place for this to happen: kscreen. It already responds to screen hotplug events, allows user tweaking and restores screen-based configurations automagically, it could add scaling to the things it tracks.

If people really wanted to get super fancy, creating a web service that accepts monitors, EDID blocks and the correct scaling factors according to the user and spits out recommendations by tallying up the input would take an afternoon to write. This would allow the creation of a "known bad" database with "known good" settings to match over time. That's probably overkill, however.

The other area of edge case is when you have two screens with different DPI connected to the system at the same time. This, too, is manageable. One option is to simply recognize it as a poorly-supported edge case and keep to one global scaling value. This is the "user broke it, user gets to keep both halves" type approach. It's also the easiest. The more complex, and certainly the one that would give better results, is to have per-screen scaling. To make this work scaling needs to change on a per-window basis based on which screen it is on. This would be manageable in the desktop shell and the window manager, though a bigger ask to support in every single application. It would mean applications would need to not only drop their in-application font settings (which they ought to anyways) but to make fonts and UI layout factors a per-window thing.

If you are running right now to your keyboard to ask about windows that are on more than screen at a time, don't bother: that's a true edge case that really doesn't need to be supported at all. Pick a screen that the is "on" and scale it appropriately. Multi-screen windows can take over the crying for the kittens who will now be bouncing around with happy delight on the other 99.999% of systems in use.

Build a future so bright, we gotta wear shades

These two issues are really not that big. They are the result of some unfortunate decision making in the past, but they can be easily rectified. As it stands, the way fonts are handled completely and without question ruins the user experience so hopefully as applications begin (or complete) the process of porting to Frameworks 5 they can pay attention to this.

.. and just so nobody feels too badly about it all: all the Linux desktop software I've tested so far for these issues has failed to make the grade. So the good news is that everything sucks just as much .. and the great news is that KDE is perfectly poised to rise above the rest and really stand out by getting it right in the Frameworks 5 era.
Posted Thu Jul 31 18:39:00 2014 Tags:

I’ve been aware for some time of a culture war simmering in the SF world. And trying to ignore it, as I believed it was largely irrelevant to any of my concerns and I have friends on both sides of the divide. Recently, for a number of reasons I may go into in a later post, I’ve been forced to take a closer look at it. And now I’m going to have to weigh in, because it seems to me that the side I might otherwise be most sympathetic to has made a rather basic error in its analysis. That error bears on something I do very much care about, which is the health of the SF genre as a whole.

Both sides in this war believe they’re fighting about politics. I consider this evaluation a serious mistake by at least one of the sides.

On the one hand, you have a faction that is broadly left-wing in its politics and believes it has a mission to purge SF of authors who are reactionary, racist, sexist et weary cetera. This faction now includes the editors at every major SF publishing imprint except Baen and all of the magazines except Analog and controls the Science Fiction Writers of America (as demonstrated by their recent political purging of Theodore Beale, aka Vox Day). This group is generally frightened of and hostile to indie publishing. Notable figures include Patrick & Theresa Nielsen Hayden and John Scalzi. I’ll call this faction the Rabbits, after Scalzi’s “Gamma Rabbit” T-shirt and Vox Day’s extended metaphor about rabbits and rabbit warrens.

On the other hand, you have a faction that is broadly conservative or libertarian in its politics. Its members deny, mostly truthfully, being the bad things the Rabbits accuse them of. It counteraccuses the Rabbits of being Gramscian-damaged cod-Marxists who are throwing away SF’s future by churning out politically-correct message fiction that, judging by Amazon rankings and other sales measures, fans don’t actually want to read. This group tends to either fort up around Baen Books or be gung-ho for indie- and self-publishing. Notable figures include Larry Correia, Sarah Hoyt, Tom Kratman, John C. Wright, and Vox Day. I’ll call this group the Evil League of Evil, because Correia suggested it and other leading figures have adopted the label with snarky glee.

A few other contrasts between the Rabbits and the Evil League are noticeable. One is that the Evil League’s broadsides are often very funny and it seems almost incapable of taking either itself or the Rabbits’ accusations seriously – I mean, Correia actually tags himself the “International Lord of Hate” in deliberate parody of what the Rabbits say about him. On the other hand, the Rabbits seem almost incapable of not taking themselves far too seriously. There’s a whiny, intense, adolescent, over-fixated quality about their propaganda that almost begs for mockery. Exhibit A is Alex Dally McFarlane’s call for an end to the default of binary gender in SF.

There’s another contrast that gets near what I think is the pre-political cause of this war. The Rabbits have the best stylists, while the Evil League has the best storytellers. Pick up a Rabbit property like Rich Horton’s The Year’s Best Science Fiction and Fantasy 2014 and you’ll read large numbers of exquisitely crafted little numbers about nothing much. The likes of Correia, on the other hand, churn out primitive prose, simplistic plotting, at best serviceable characterization – and vastly more ability to engage the average reader. (I would bet money, based on Amazon rankings, that Correia outsells every author in that collection combined.)

All this might sound like I’m inclined to sign up with the Evil League of Evil. The temptation is certainly present; it’s where the more outspoken libertarians in SF tend to have landed. Much more to the point, my sense of humor is such that I find it nearly impossible to resist the idea of posting something public requesting orders from the International Lord of Hate as to which minority group we are to crush beneath our racist, fascist, cismale, heteronormative jackboots this week. The screams of outrage from Rabbits dimwitted enough to take this sort of thing seriously would entertain me for months.

Alas, I cannot join the Evil League of Evil, for I believe they have made the same mistake as the Rabbits; they have mistaken accident for essence. The problem with the Rabbits is not that left-wing politics is dessicating and poisoning their fiction. While I have made the case elsewhere that SF is libertarian at its core, it nevertheless remains possible to write left-wing message SF that is readable, enjoyable, and of high quality – Iain Banks’s Culture novels leap to mind as recent examples, and we can refer back to vintage classics such as Pohl & Kornbluth’s The Space Merchants for confirmation. Nor, I think, is the failure of Rabbit fiction to engage most SF fans and potential fans mainly down to its politics; I think the Evil League is prone to overestimate the popular appeal of their particular positions here.

No, I judge that what is dessicating and poisoning the Rabbit version of SF is something distinct from left-wing political slant but co-morbid with it: colonization by English majors and the rise of literary status envy as a significant shaping force in the field.

This is a development that’s easy to mistake for a political one because of the accidental fact that most university humanities departments have, over the last sixty years or so, become extreme-left political monocultures. But, in the language of epidemiology, I believe the politics is a marker for the actual disease rather than the pathogen itself. And it’s no use to fight the marker organism rather than the actual pathogen.

Literary status envy is the condition of people who think that all genre fiction would be improved by adopting the devices and priorities of late 19th- and then 20th-century literary fiction. Such people prize the “novel of character” and stylistic sophistication above all else. They have almost no interest in ideas outside of esthetic theory and a very narrow range of socio-political criticism. They think competent characters and happy endings are jejune, unsophisticated, artistically uninteresting. They love them some angst.

People like this are toxic to SF, because the lit-fic agenda clashes badly with the deep norms of SF. Many honestly think they can fix science fiction by raising its standards of characterization and prose quality, but wind up doing tremendous iatrogenic damage because they don’t realize that fixating on those things (rather than the goals of affirming rational knowability and inducing a sense of conceptual breakthrough) produces not better SF but a bad imitation of literary fiction that is much worse SF.

Almost the worst possible situation is the one we are in now, in which over the last couple of decades the editorial and critical establishment of SF has been (through a largely accidental process) infiltrated by people whose judgment has been partly or wholly rotted out by literary status envy. The field’s writers, too, are often diminished and distorted by literary status envy. Meanwhile, the revealed preferences of SF fans have barely changed. This is why a competent hack like David Weber can outsell every Nebula winner combined by huge margins year after year after year.

The victims of literary status envy resent the likes of David Weber, and their perceived inferiority to the Thomas Pynchons of the world; they think the SF field is broken and need to be fixed. When they transpose this resentment into the key of politics in the way their university educations have taught then to do, they become the Rabbits.

The Evil League of Evil is fighting the wrong war in the wrong way. To truly crush the Rabbits, they should be talking less about politics and more about what has been best and most noble in the traditions of the SF genre itself. I think a lot of fans know there is something fatally gone missing in the Rabbit version of science fiction; what they lack is the language to describe and demand it.

That being said, in the long run, I don’t think the Evil League of Evil can lose. The Rabbits are both the beneficiaries and victims of preference falsification; their beliefs about where the fans want the field to go are falsified by their plummeting sales figures, but they can’t see past the closure induced by their control of the gatekeeper positions in traditional publishing. Meanwhile, the Evil League thrives in the rising medium of e-book sales, in indie- and self-publishing.

The Rabbits have a sort of herd-instinct sense that these new channels doom them to irrelevance, which is why so many of them line up to defend a system that ruthlessly exploits and cheats them. Contemplate SFWA’s stance in the Hachette-vs.-Amazon dispute. for example; it’s plain nuts if SFWA claims to be representing authors.

But it will be a faster, better, cleaner victory if the Evil League of Evil gets shut of political particularism (and I mean that, even about my politics) and recognizes the real problem. The real problem is that the SF genre’s traditional norms exist for very good reasons, and it’s time we all learned to give the flying heave-ho to people who fail to understand and appreciate that.

The right (counter)revolutionary slogan is therefore not “Drive out the social-justice warriors!”, it’s “Peddle your angsty crap elsewhere, lit-fic wannabes! Let’s get SF back in the gutter where it belongs!”

Posted Wed Jul 30 22:04:26 2014 Tags:

As all software, it took longer than I expected, but today I tagged the first version of pettycoin.  Now, lots more polish and features, but at least there’s something more than the git repo for others to look at!

Posted Tue Jul 29 07:53:59 2014 Tags:

[Note to the impatient: to try out my beamforming simulation, which produced the above image, visit my beamlab test page - ideally in a browser with very fast javascript, like Chrome. You can also view the source.]

I promised you some cheating of Shannon's Law. Of course, as with most things in physics, even the cheating isn't really cheating; you just adjust your model until the cheating falls within the rules.

The types of "cheating" that occur in wifi can be briefly categorized as antenna directionality, beamforming, and MIMO. (People usually think about MIMO before beamforming, but I find the latter to be easier to understand, mathematically, so I switched the order.)

Antenna Directionality and the Signal to Noise Ratio

Previously, we discussed the signal-to-noise ratio (SNR) in some detail, and how Shannon's Law can tell you how fast you can transfer data through a channel with a given SNR.

The thing to notice about SNR is that you can increase it by increasing amplification at the sender (where the background noise is fixed but you have a clear copy of the signal) but not at the receiver. Once a receiver has a copy of the signal, it already has noise in it, so when you amplify the received signal, you just amplify the noise by the same amount, and the SNR stays constant.

(By the way, that's why those "amplified" routers you can buy don't do much good. They amplify the transmitted signal, but amplifying the received signal doesn't help in the other direction. The maximum range is still limited by the transmit power on your puny unamplified phone or laptop.)

On the other hand, one thing that *does* help is making your antenna more "directional." The technical term for this is "antenna gain," but I don't like that name, because it makes it sound like your antenna amplifies the signal somehow for free. That's not the case. Antenna gain doesn't so much amplify the signal as ignore some of the noise. Which has the same net effect on the SNR, but the mechanics of it are kind of important.

You can think of an antenna as a "scoop" that picks up both the signal and the noise from a defined volume of space surrounding the antenna. The shape of that volume is important. An ideal "isotropic" antenna (my favourite kind, although unfortunately it doesn't exist) picks up the signal equally in all directions, which means the region it "scoops" is spherical.

In general we assume that background noise is distributed evenly through space, which is not exactly true, but is close enough for most purposes. Thus, the bigger the volume of your scoop, the more noise you scoop up along with it. To stretch our non-mathematical metaphor well beyond its breaking point, a "bigger sphere" will contain more signal as well as more noise, so just expanding the size of your region doesn't affect the SNR. That's why, and I'm very sorry about this, a bigger antenna actually doesn't improve your reception at all.

(There's another concept called "antenna efficiency" which basically says you can adjust your scoop to resonate at a particular frequency, rejecting noise outside that frequency. That definitely works - but all antennas are already designed for this. That's why you get different antennas for different frequency ranges. Nowadays, the only thing you can do by changing your antenna size is to screw up the efficiency. You won't be improving it any further. So let's ignore antenna efficiency. You need a good quality antenna, but there is not really such a thing as a "better" quality antenna these days, at least for wifi.)

So ok, a bigger scoop doesn't help. But what can help is changing the shape of the scoop. Imagine if, instead of a sphere, we scoop up only the signal from a half-sphere.

If that half-sphere is in the direction of the transmitter - which is important! - then you'll still receive all the same signal you did before. But, intuitively, you'll only get half the noise, because you're ignoring the noise coming in from the other direction. On the other hand, if the half-sphere is pointed away from the incoming signal, you won't hear any of the signal at all, and you're out of luck. Such a half-sphere would have 2x the signal to noise ratio of a sphere, and in decibels, 2x is about 3dB. So this kind of (also not really existing) antenna is called 3dBi, where dBi is "decibels better than isotropic" so an isotropic (spherical) receiver is defined as 0dBi.

Taking it a step further, you could take a quarter of a sphere, ie. a region 90 degrees wide in any direction, and point it at your transmitter. That would double the SNR again, thus making a 6dBi antenna.

Real antennas don't pick up signals in a perfectly spherical shape; math makes that hard. So real ones tend to produce a kind of weirdly-shaped scoop with little roundy bits sticking out all over, and one roundy bit larger than the others, in the direction of interest. Essentially, the size of the biggest roundy bit defines the antenna gain (dBi). For regulatory purposes, the FCC mostly assumes you will use a 6dBi antenna, although of course the 6dBi will not be in the shape of a perfect quarter sphere.

Now is that the most hand-wavy explanation of antenna gain you have ever seen? Good.

Anyway, the lesson from all this is if you use a directional antenna, you can get improved SNR. A typical improvement is around 6dBi, which is pretty good. But the down side of a directional antenna is you have to aim it. With a wifi router, that can be bad news. It's great for outdoors if you're going to set up a long-distance link and aim very carefully; you can get really long range with a very highly directional antenna. But indoors, where distances are short and people move around a lot, it can be trouble.

One simple thing that does work indoors is hanging your wifi router from the ceiling. Then, if you picture eg. a quarter-sphere pointing downwards, you can imagine covering the whole room without really sacrificing anything (other than upstairs coverage, which you don't care about if you put a router up there too). Basically, that's as good as you can do, which is why most "enterprise" wifi deployments hang their routers from the ceiling. If you did that at home too - and had the right kind of antennas with the right gain in the right direction - you could get up to 6dB of improvement on your wifi signal, which is pretty great.

(Another trick some routers do is to have multiple antennas, each one pointing in a different direction, and then switch them on and off to pick the one(s) with the highest SNR for each client. This works okay but it interferes with MIMO - where you want to actively use as many antennas as possible - so it's less common nowadays. It was a big deal in the days of 802.11g, where that was the main reason to have multiple antennas at all. Let's talk about MIMO later, since MIMO is its own brand of fun.)

Beamforming

So okay, that was antenna directionality (gain). To summarize all that blathering: you point your antenna in a particular direction, and you get a better SNR in that particular direction.

But the problem is that wifi clients move around, so antennas permanently pointed in a particular direction are going to make things worse about as often as they help (except for simple cases like hanging from the ceiling, and even that leaves out the people upstairs).

But wouldn't it be cool if, using software plus magic, you could use multiple antennas to create "virtual directionality" and re-aim a "beam" automatically as the client device moves around?

Yes, that would be cool.

Unfortunately, that's not what beamforming actually is.

Calling it "beamforming" is not a *terrible* analogy, but the reality of the signal shape is vastly more complex and calling it a "beam" is pretty misleading.

This is where we finally talk about what I mentioned last time, where two destructively-interfering signals result in zero signal. Where does the power go?

As an overview, let's say you have two unrelated transmitters sending out a signal at the same frequency from different locations. It takes a fixed amount of power for each transmitter to send its signal. At some points in space, the signals interfere destructively, so there's no signal at that point. Where does it go? There's a conservation of energy problem after all; the transmitted power has to equal the power delivered, via electromagnetic waves, out there in the wild. Does it mean the transmitter is suddenly unable to deliver that much power in the first place? Is it like friction, where the energy gets converted into heat?

Well, it's not heat, because heat is vibration, ie, the motion of physical particles with mass. The electromagnetic waves we're talking about don't necessarily have any relationship with mass; they might be traveling through a vacuum where there is no mass, but destructive interference can still happen.

Okay, maybe the energy is re-emitted as radiation? Well, no. The waves in the first place were radiation. If we re-emitted them as radiation, then by definition, they weren't cancelled out. But we know they were cancelled out; you can measure it and see.

The short and not-very-satisfying answer is that in terms of conservation of energy, things work out okay. There are always areas where the waves interfere constructively that exactly cancel out the areas where they interfere destructively.

The reason I find that answer unsatisfying is that the different regions don't really interact. It's not like energy is being pushed, somehow, between the destructive areas and the constructive areas. It adds up in the end, because it has to, but that doesn't explain *how* it happens.

The best explanation I've found relates to quantum mechanics, in a lecture I read by Richard Feynman at some point. The idea is that light (and all electromagnetic waves, which is what we're talking about) actually does not really travel in straight lines. The idea that light travels in a straight line is just an illusion caused by large-scale constructive and destructive interference. Basically, you can think of light as travelling along all the possible paths - even silly paths that involve backtracking and spirals - from point A to point B. The thing is, however, that for almost every path, there is an equal and opposite path that cancels it out. The only exception is the shortest path - a straight line - of which there is only one. Since there's only one, there can't be an equal but opposite version. So as far as we're concerned, light travels in a straight line.

(I offer my apologies to every physicist everywhere for the poor quality of that explanation.)

But there are a few weird experiments you can do (look up the "double slit experiment" for example) to prove that in fact, the "straight line" model is the wrong one, and the "it takes all the possible paths" model is actually more like what's really going on.

So that's what happens here too. When we create patterns of constructive and destructive radio interference, we are simply disrupting the rule of thumb that light travels in a straight line.

Oh, is that all? Okay. Let's call it... beam-un-forming.

There's one last detail we have to note in order to make it all work out. The FCC says that if we transmit from two antennas, we have to cut the power from each antenna in half, so the total output is unchanged. If we do that, naively it might seem like the constructive interference effect is useless. When the waves destructively interfere, you still get zero, but when they constructively interfere, you get 2*½*cos(ωt), which is just the original signal. Might as well just use one antenna with the original transmit power, right?

Not exactly. Until now, I have skipped over talking about signal power vs amplitude, since it hasn't been that important so far. The FCC regulates *power*, not amplitude. The power of A*cos(ωt) turns out to be ½A2. I won't go over all the math, but the energy of f(x) during a given period is defined as ∫ f2(x) dx over that period. Power is energy divided by time. It turns out (via trig identities again) the power of cos(x) is 0.5, and the rest flows from there.

Anyway, the FCC limit requires a *power* reduction of ½. So if the original wave was cos(ωt), then the original power was 0.5. We need the new transmit power (for each antenna) to be 0.25, which is ½A2 = ½(0.5). Thus A = sqrt(0.5) = 1/sqrt(2) = 0.7 or so.

So the new transmit wave is 0.7 cos(ωt). Two of those, interfering constructively, gives about 1.4 cos(ωt). The resulting power is thus around ½(1.4)2 = 1, or double the original (non-reduced, with only one antenna) transmit power.

Ta da! Some areas have twice the power - a 3dB "antenna array gain" or "tx beamforming gain" - while others have zero power. It all adds up. No additional transmit power is required, but a receiver, if it's in one of the areas of constructive interference, now sees 3dB more signal power and thus 3dB more SNR.

We're left with the simple (ha ha) matter of making sure that the receiver is in an area of maximum constructive interference at all times. To make a long story short, we do this by adjusting the phase between the otherwise-identical signals coming from the different antennas.

I don't really know exactly how wifi arranges for the phase adjustment to happen; it's complicated. But we can imagine a very simple version: just send from each antenna, one at a time, and have the receiver tell you the phase difference right now between each variant. Then, on the transmitter, adjust the transmit phase on each antenna by an opposite amount. I'm sure what actually happens is more complicated than that, but that's the underlying concept, and it's called "explicit beamforming feedback." Apparently the 802.11ac standard made progress toward getting everyone to agree on a good way of providing beamforming feedback, which is important for making this work well.

Even more weirdly, the same idea works in reverse. If you know the phase difference between the client's antenna (we're assuming for now that he has only one, so we don't go insane) and each of your router's antennas, then when the client sends a signal *back* to you, you can extract the signal from the different antennas in a particular way that gets you the same amount of gain as in the transmit direction, and we call that rx beamforming. At least, I think you can. I haven't done the math for that yet, so I don't know for sure how well it can work.

Relatedly, even if there is no *explicit* beamforming feedback, in theory you can calculate the phase differences by listening to the signals from the remote end on each of your router's antennas. Because the signals should be following exactly the same path in both directions, you can guess what phase difference your signal arrived with by seeing which difference *his* signal came back with, and compensate accordingly. This is called "implicit beamforming feedback." Of course, if both ends try this trick at once, hilarity ensues.

And finally, I just want to point out how little the result of "beamforming" is like a beam. Although conceptually we'd like to think of it that way - we have a couple of transmitters tuning their signal to point directly at the receiver - mathematically it's not really like that. "Beamforming" creates a kind of on-off "warped checkerboard" sort of pattern that extends in all directions. To the extent that your antenna array is symmetrical, the checkerboard pattern is also symmetrical.

Beamforming Simulation

Of course, a checkerboard is also a flawed analogy. Once you start looking for a checkerboard, you start to see that in fact, the warping is kind of directional, and sort of looks like a beam, and you can imagine that with a hundred antennas, maybe it really would be "beam" shaped.

After doing all the math, I really wanted to know what beamforming looked like, so I wrote a little simulation of it, and the image at the top of this article is the result. (That particular one came from a 9-antenna beamforming array.)

You can also try out the simulation yourself, moving around up to 9 antennas to create different interference patterns. I find it kind of fun and mesmerizing, especially to think that these signals are all around us and if you could see them, they'd look like *that*. On my computer with Chrome, I get about 20 frames per second; with Safari, I get about 0.5 frames per second, which is not as fun. So use a browser with a good javascript engine.

Note that while the image looks like it has contours and "shadows," the shadows are entirely the effect of the constructive/destructive interference patterns causing bright and dark areas. Nevertheless, you can kind of visually see how the algorithm builds one level of constructive interference on top of another, with the peak of the humpiest bump being at the exact location of the receiver. It really works!

Some notes about the simulation:

  • It's 2-dimensional. Real life has at least 3 dimensions. It works pretty much the same though.
  • The intensity (brightness) of the colour indicates the signal strength at that point. Black means almost no signal.
  • "Blue" means cos(ωt) is positive at that point, and red means it's negative.
  • Because of the way phasors work, "blue plus red" is not the only kind of destructive interference, so it's a bit confusing.
  • Click on the visualization to move around the currently-selected transmitter or receiver.
  • When you move the receiver around, it auto-runs the beamforming optimization so you can see the "beam" move around.
  • The anti-optimize button is not very smart; a smarter algorithm could achieve an even less optimal result. But most of the time it does an okay job, and it does show how you can also use beamforming to make a receiver *not* hear your signal. That's the basis of MU-MIMO.
MIMO

The last and perhaps most exciting way to cheat Shannon's Law is MIMO. I'll try to explain that later, but I'm still working out the math :)

Posted Tue Jul 29 06:41:59 2014 Tags:

Before we get to the next part, which is fun, we need to talk about phasors. No, not the Star Trek kind, the boring kind. Sorry about that.

If you're anything like me, you might have never discovered a use for your trigonometric identities outside of school. Well, you're in luck! With wifi, trigonometry, plus calculus involving trigonometry, turns out to be pretty important to understanding what's going on. So let's do some trigonometry.

Wifi modulation is very complicated, but let's ignore modulation for the moment and just talk about a carrier wave, which is close enough. Here's your basic 2.4 GHz carrier:

    A cos (ω t)

Where A is the transmit amplitude and ω = 2.4e9 (2.4 GHz). The wavelength, λ, is the speed of light divided by the frequency, so:

    λ = c / ω = 3.0e8 / 2.4e9 = 0.125m

That is, 12.5 centimeters long. (By the way, just for comparison, the wavelength of light is around 400-700 nanometers, or 500,000 times shorter than a wifi signal. That comes out to 600 Terahertz or so. But all the same rules apply.)

The reason I bring up λ is that we're going to have multiple transmitters. Modern wifi devices have multiple transmit antennas so they can do various magic, which I will try to explain later. Also, inside a room, signals can reflect off the walls, which is a bit like having additional transmitters.

Let's imagine for now that there are no reflections, and just two transmit antennas, spaced some distance apart on the x axis. If you are a receiver also sitting on the x axis, then what you see is two signals:

    cos (ω t) + cos (ω t + φ)

Where φ is the phase difference (between 0 and 2π). The phase difference can be calculated from the distance between the two antennas, r, and λ, as follows:

    φ = r / λ

Of course, a single-antenna receiver can't *actually* see two signals. That's where the trig identities come in.

Constructive Interference

Let's do some simple ones first. If r = λ, then φ = 2π, so:

    cos (ω t) + cos (ω t + 2π)
    = cos (ω t) + cos (ω t)
    = 2 cos (ω t)

That one's pretty intuitive. We have two antennas transmitting the same signal, so sure enough, the receiver sees a signal twice as tall. Nice.

Destructive Interference

The next one is weirder. What if we put the second transmitter 6.25cm away, which is half a wavelength? Then φ = π, so:

    cos (ω t) + cos (ω t + π)
    = cos (ω t) - cos (ω t)
    = 0

The two transmitters are interfering with each other! A receiver sitting on the x axis (other than right between the two transmit antennas) won't see any signal at all. That's a bit upsetting, in fact, because it leads us to a really pivotal question: where did the energy go?

We'll get to that, but first things need to get even weirder.

Orthogonal Carriers

Let's try φ = π/2.

    cos (ω t) + cos (ω t + π/2)
    = cos (ω t) - sin (ω t)

This one is hard to explain, but the short version is, no matter how much you try, you won't get that to come out to a single (Edit 2014/07/29: non-phase-shifted) cos or sin wave. Symbolically, you can only express it as the two separate factors, added together. At each point, the sum has a single value, of course, but there is no formula for that single value which doesn't involve both a cos ωt and a sin ωt. This happens to be a fundamental realization that leads to all modern modulation techniques. Let's play with it a little and do some simple AM radio (amplitude modulation). That means we take the carrier wave and "modulate" it by multiplying it by a much-lower-frequency "baseband" input signal. Like so:

    f(t) cos (ω t)

Where ω >> 1, so that for any given cycle of the carrier wave, f(t) can be assumed to be "almost constant."

On the receiver side, we get the above signal and we want to discover the value of f(t). What we do is multiply it again by the carrier:

    f(t) cos (ω t) cos (ω t)
    = f(t) cos2 (ω t)
    = f(t) (1 - sin2 (ω t))
    = ½ f(t) (2 - 2 sin2 (ω t))
    = ½ f(t) (1 + (1 - 2 sin2 (ω t)))
    = ½ f(t) (1 + cos (2 ω t))
    = ½ f(t) + ½ f(t) cos (2 ω t)

See? Trig identities. Next we do what we computer engineers call a "dirty trick" and, instead of doing "real" math, we'll just hypothetically pass the resulting signal through a digital or analog filter. Remember how we said f(t) changes much more slowly than the carrier? Well, the second term in the above answer changes twice as fast as the carrier. So we run the whole thing through a Low Pass Filter (LPF) at or below the original carrier frequency, removing high frequency terms, leaving us with just this:

    (...LPF...)
    → ½ f(t)

Which we can multiply by 2, and ta da! We have the original input signal.

Now, that was a bit of a side track, but we needed to cover that so we can do the next part, which is to use the same trick to demonstrate how cos(ω t) and sin(ω t) are orthogonal vectors. That means they can each carry their own signal, and we can extract the two signals separately. Watch this:

    [ f(t) cos (ω t) + g(t) sin (ω t) ] cos (ω t)
    = [f(t) cos2 (ω t)] + [g(t) cos (ω t) sin (ω t)]
    = [½ f(t) (1 + cos (2 ω t))] + [½ g(t) sin (2 ω t)]
    = ½ f(t) + ½ f(t) cos (2 ω t) + ½ g(t) sin (2 ω t)
    [...LPF...]
    → ½ f(t)

Notice that by multiplying by the cos() carrier, we extracted just f(t). g(t) disappeared. We can play a similar trick if we multiply by the sin() carrier; f(t) then disappears and we have recovered just g(t).

In vector terms, we are taking the "dot product" of the combined vector with one or the other orthogonal unit vectors, to extract one element or the other. One result of all this is you can, if you want, actually modulate two different AM signals onto exactly the same frequency, by using the two orthogonal carriers.

QAM

But treating it as just two orthogonal carriers for unrelated signals is a little old fashioned. In modern systems we tend to think of them as just two components of a single vector, which together give us the "full" signal. That, in short, is QAM, one of the main modulation methods used in 802.11n. To oversimplify a bit, take this signal:

    f(t) cos (ω t) + g(t) sin (ω t)

And let's say f(t) and g(t) at any given point in time each have a value that's one of: 0, 1/3, 2/3, or 1. Since each function can have one of four values, there are a total of 4*4 = 16 different possible combinations, which corresponds to 4 bits of binary data. We call that encoding QAM16. If we plot f(t) on the x axis and g(t) on the y axis, that's called the signal "constellation."

Anyway we're not attempting to do QAM right now. Just forget I said anything.

Adding out-of-phase signals

Okay, after all that, let's go back to where we started. We had two transmitters both sitting on the x axis, both transmitting exactly the same signal cos(ω t). They are separated by a distance r, which translates to a phase difference φ. A receiver that's also on the x axis, not sitting between the two transmit antennas (which is a pretty safe assumption) will therefore see this:

    cos (ω t) + cos (ω t + φ)
    = cos (ω t) + cos (ω t) cos φ - sin (ω t) sin φ
    = (1 + cos φ) cos (ω t) - (sin φ) sin (ω t)

One way to think of it is that a phase shift corresponds to a rotation through the space defined by the cos() and sin() carrier waves. We can rewrite the above to do this sort of math in a much simpler vector notation:

    [1, 0] + [cos φ, sin φ]
    = [1+cos φ, sin φ]

This is really powerful. As long as you have a bunch of waves at the same frequency, and each one is offset by a fixed amount (phase difference), you can convert them each to a vector and then just add the vectors linearly. The result, the sum of these vectors, is what the receiver will see at any given point. And the sum can always be expressed as the sum of exactly one cos(ω t) and one sin(ω t) term, each with its own magnitude.

This leads us to a very important conclusion:

    The sum of reflections of a signal is just an arbitrarily phase shifted and scaled version of the original.

People worry about reflections a lot in wifi, but because of this rule, they are not, at least mathematically, nearly as bad as you'd think.

Of course, in real life, getting rid of that phase shift can be a little tricky, because you don't know for sure by how much the phase has been shifted. If you just have two transmitting antennas with a known phase difference between them, that's one thing. But when you add reflections, that makes it harder, because you don't know what phase shift the reflections have caused. Not impossible: just harder.

(You also don't know, after all that interference, what happened to the amplitude. But as we covered last time, the amplitude changes so much that our modulation method has to be insensitive to it anyway. It's no different than moving the receiver closer or further away.)

Phasor Notation

One last point. In some branches of eletrical engineering, especially in analog circuit analysis, we use something called "phasor notation." Basically, phasor notation is just a way of representing these cos+sin vectors using polar coordinates instead of x/y coordinates. That makes it easy to see the magnitude and phase shift, although harder to add two signals together. We're going to use phasors a bit when discussing signal power later.

Phasors look like this in the general case:

    A cos (ω t) + B sin (ω t)
    = [A, B]

      Magnitude = M = (A2 + B2)½

      tan (Phase) = tan φ = B / A
      φ = atan2(B, A)

    = M∠φ

or the inverse:

    M∠φ
    = [M cos φ, M sin φ]
    = (M cos φ) cos (ω t) - (M sin φ) sin (ω t)
    = [A, B]
    = A cos (ω t) + B sin (ω t)

Imaginary Notation

There's another way of modeling the orthogonal cos+sin vectors, which is to use complex numbers (ie. a real axis, for cos, and an imaginary axis, for sin). This is both right and wrong, as imaginary numbers often are; the math works fine, but perhaps not for any particularly good reason, unless your name is Euler. The important thing to notice is that all of the above works fine without any imaginary numbers at all. Using them is a convenience sometimes, but not strictly necessary. The value of cos+sin is a real number, not a complex number.

Epilogue

Next time, we'll talk about signal power, and most importantly, where that power disappears to when you have destructive interference. And from there, as promised last time, we'll cheat Shannon's Law.

Posted Sat Jul 26 01:11:15 2014 Tags:

Big Boys Don’t Cry (Tom Kratman; Castalia House) is a short novel which begins innocently enough as an apparent pastiche of Keith Laumer’s Bolo novels and short stories. Kratman’s cybernetic “Ratha” tanks, dispassionately deploying fearsome weapons but somehow equipped to understand human notions of honor and duty, seem very familiar.

But an element generally alien to the Bolo stories and Kratman’s previous military fiction gradually enters: moral doubt. A Ratha who thinks of herself as “Magnolia” is dying, being dismantled for parts after combat that nearly destroyed her, and reviews her memories. She mourns her brave lost boys, the powered-armor assault infantry that rode to battle in in her – and, too often, died when deployed – before human turned front-line war entirely to robots. Too often, she remembers, her commanders were cowardly, careless, or venal. She has been ordered to commit and then forget atrocities which she can now remember because the breakdown of her neural-analog pathways is deinhibiting her.

The ending is dark, but necessary. The whole work is a little surprising coming from Kratman, who knows and conveys that war is hell but has never before shown much inclination to question its ethical dimension at this level. At the end, he comes off almost like the hippies and peaceniks he normally despises.

There is one important difference, however. Kratman was combat career military who has put his own life on the line to defend his country; he understands that as ugly as war is, defeat and surrender can be even worse. In this book he seems to be arguing that the morality of a war is bounded above by the amount of self-sacrifice humans are willing to offer up to earn victory. When war is too easy, the motives for waging it become too easily corrupted.

As militaries steadily replace manned aircraft with drones and contemplate replacing infantry with gun-robots, this is a thought worth pondering.

Posted Thu Jul 24 19:23:23 2014 Tags:

2040 (Graham Tottle; Cameron Publicity & Marketing Ltd) is a very odd book. Ostensibly an SF novel about skulduggery on two timelines, it is a actually a ramble through a huge gallimaufry of topics including most prominently the vagaries of yachting in the Irish Sea, an apologia for British colonial administration in 19th-century Africa, and the minutiae of instruction sets of archaic mainframe computers.

It’s full of vivid ideas and imagery, held together by a merely serviceable plot and garnished with festoons of footnotes delving into odd quarters of the factual background. Some will dislike the book’s politics, a sort of nostalgic contrarian Toryism; many Americans may find this incomprehensible, or misread it as a variant of the harsher American version of traditionalist conservatism. There is much worthwhile exploding of fashionable cant in it, even if the author does sound a bit crotchety on occasion.

I enjoyed it, but I can’t exactly recommend it. Enter at your own risk.

Posted Thu Jul 24 00:09:36 2014 Tags:

For many years a major focus of Mono has been to be compatible-enough with .NET and to support the popular features that developers use.

We have always believed that it is better to be slow and correct than to be fast and wrong.

That said, over the years we have embarked on some multi-year projects to address some of the major performance bottlenecks: from implementing a precise GC and fine tuning it for a number of different workloads to having implemented now four versions of the code generator as well as the LLVM backend for additional speed and things like Mono.SIMD.

But these optimizations have been mostly reactive: we wait for someone to identify or spot a problem, and then we start working on a solution.

We are now taking a proactive approach.

A few months ago, Mark Probst started the new Mono performance team. The goal of the team is to improve the performance of the Mono runtime and treat performance improvements as a feature that is continously being developed, fine-tuned and monitored.

The team is working both on ways to track performance of Mono over time, implemented support for getting better insights into what happens inside the runtime and has implemented several optimizations that have been landing into Mono for the last few months.

We are actively hiring for developers to join the Mono performance team (ideally in San Francisco, where Mark is based).

Most recently, the team added a new and sophisticated new stack for performance counters which allows us to monitor what is happening on the runtime, and we are now able to export to our profiler (a joint effort between our performance team and our feature team and implemented by Ludovic). We also unified both the runtime and user-defined performance counters and will soon be sharing a new profiler UI.

Posted Wed Jul 23 14:37:24 2014 Tags:
I've begun prototyping a system for green processes in Qt applications. I'm not yet at the code-writing stage, but the API is definitely taking shape and a design is starting to emerge. It's a spare-time project for me, so is progressing at a reasonable but not extremely fast pace.

I've gotten to the point where early-stage feedback from people who are interested in such a framework would be very valuable in polishing the design a bit more before laying down code. As such, I'm looking for 4-6 people to collaborate with at this early stage.

If you are interested in using green processes in your Qt application, or are simply interested in new application development patterns for Qt, and you have 20-30 minutes per week to look at API drafts and provide feedback and and/or add to the ideas that are coming together, please email me (aseigo at kde.org).
Posted Sun Jul 20 06:01:00 2014 Tags:

Last time we talked about how wifi signals cross about 12 orders of magnitude in terms of signal power, from +30dBm (1 watt) to -90dBm (1 picowatt). I mentioned my old concern back in school about splitters causing a drop to 1/n of the signal on a wired network, where n is the number of nodes, and said that doesn't matter much after all.

Why doesn't it matter? If you do digital circuits for a living, you are familiar with the way digital logic works: if the voltage is over a threshold, say, 1.5V, then you read a 1. If it's under the threshold, then you read a 0. So if you cut all the voltages in half, that's going to be a mess because the threshold needs to get cut in half too. And if you have an unknown number of nodes on your network, then you don't know where the threshold is at all, which is a problem. Right?

Not necessarily. It turns out analog signal processing is - surprise! - not like digital signal processing.

ASK, FSK, PSK, QAM

Essentially, in receiving an analog signal and converting it back to digital, you want to do one of three things:

  • see if the signal power is over/under a threshold ("amplitude shift keying" or ASK)
  • or: see if the signal is frequency #0 or frequency #1 ("frequency shift keying" or FSK)
  • or: fancier FSK-like schemes such as PSK or QAM (look it up yourself :)).
Realistically nowadays everyone does QAM, but the physics are pretty much the same for FSK and it's easier to explain, so let's stick with that.

But first, what's wrong with ASK? Why toggle between two frequencies (FSK) when you can just toggle one frequency on and off (ASK)? The answer comes down mainly to circuit design. To design an ASK receiver, you have to define a threshold, and when the amplitude is higher than the threshold, call it a 1, otherwise call it a 0. But what is the threshold? It depends on the signal strength. What is the signal strength? The height of a "1" signal. How do we know whether we're looking at a "1" signal? It's above the threshold ... It ends up getting tautological.

The way you implement it is to design an "automatic gain control" (AGC) circuit that amplifies more when too few things are over the threshold, and less when too many things are over the threshold. As long as you have about the same number of 1's and 0's, you can tune your AGC to do the right thing by averaging the received signal power over some amount of time.

In case you *don't* have an equal number of 1's and 0's, you can fake it with various kinds of digital encodings. (One easy encoding is to split each bit into two halves and always flip the signal upside down for the second half, producing a "balanced" signal.)

So, you can do this of course, and people have done it. But it just ends up being complicated and fiddly. FSK turns out to be much easier. With FSK, you just build two circuits: one for detecting the amplitude of the signal at frequency f1, and one for detecting the amplitude of the signal at frequency f2. It turns out to be easy to design analog circuits that do this. Then you design a "comparator" circuit that will tell you which of two values is greater; it turns out to be easy to design that too. And you're done! No trying to define a "threshold" value, no fine-tuned AGC circuit, no circular reasoning. So FSK and FSK-like schemes caught on.

SNR

With that, you can see why my original worry about a 1/n signal reduction from cable splitters didn't matter. As long as you're using FSK, the 1/n reduction doesn't mean anything; your amplitude detector and comparator circuits just don't care about the exact level, essentially. With wifi, we take that to the extreme with tiny little FSK-like signals down to a picowatt or so.

But where do we stop? Why only a picowatt? Why not even smaller?

The answer is, of course, background noise. No signal exists in perfect isolation, except in a simulation (and even in a simulation, the limitations of floating point accuracy might cause problems). There might be leftover bits of other people's signals transmitted from far away; thermal noise (ie. molecules vibrating around which happen to be at your frequency); and amplifier noise (ie. inaccuracies generated just from trying to boost the signal to a point where your frequency detector circuits can see it at all). You can also have problems from other high-frequency components on the same circuit board emitting conflicting signals.

The combination of limits from amplifier error and conflicting electrical components is called the receiver sensitivity. Noise arriving from outside your receiver (both thermal noise and noise from interfering signals) is called the noise floor. Modern circuits - once properly debugged, calibrated, and shielded - seem to be good enough that receiver sensitivity is not really your problem nowadays. The noise floor is what matters.

It turns out, with modern "low-noise amplifier" (LNA) circuits, we can amplify a weak signal essentially as much as we want. But the problem is... we amplify the noise along with it. The ratio between signal strength and noise turns out to be what really matters, and it doesn't change when you amplify. (Other than getting slightly worse due to amplifier noise.) We call that the signal to noise ratio (SNR), and if you ask an expert in radio signals, they'll tell you it's one of the most important measurements in analog communications.

A note on SNR: it's expressed as a "ratio" which means you divide the signal strength in mW by the noise level in mW. But like the signal strength and noise levels, we normally want to express the SNR in decibels to make it more manageable. Decibels are based on logarithms, and because of the way logarithms work, you subtract decibels to get the same effect as dividing the original values. That turns out to be very convenient! If your noise level is -90dBm and your signal is, say, -60dBm, then your SNR is 30dB, which means 1000x. That's awfully easy to say considering how complicated the underlying math is. (By the way, after subtracting two dBm values we just get plain dB, for the same reason that if you divide 10mW by 2mW you just get 5, not 5mW.)

The Shannon Limit

So, finally... how big does the SNR need to be in order to be "good"? Can you just receive any signal where SNR > 1.0x (which means signal is greater than noise)? And when SNR < 1.0x (signal is less than noise), all is lost?

Nope. It's not that simple at all. The math is actually pretty complicated, but you can read about the Shannon Limit on wikipedia if you really want to know all the details. In short, the bigger your SNR, the faster you can go. That makes a kind of intuitive sense I guess.

(But it's not really all that intuitive. When someone is yelling, can they talk *faster* than when they're whispering? Perhaps it's only intuitive because we've been trained to notice that wifi goes faster when the nodes are closer together.)

The Shannon limit even calculates that you can transfer some data even when the signal power is lower than the noise, which seems counterintuitive or even impossible. But it's true, and the global positioning system (GPS) apparently actually does this, and it's pretty cool.

The Maximum Range of Wifi is Unchangeable

So that was all a *very* long story, but it has a point. Wifi signal strength is fundamentally limited by two things: the regulatory transmitter power limit (30dBm or less, depending on the frequency and geography), and the distance between transmitter and receiver. You also can't do much about background noise; it's roughly -90dBm or maybe a bit worse. Thus, the maximum speed of a wifi link is fixed by the laws of physics. Transmitters have been transmitting at around the regulatory maximum since the beginning.

So how, then, do we explain the claims that newer 802.11n devices have "double the range" of the previous-generation 802.11g devices?

Simple: they're marketing lies. 802.11g and 802.11n have exactly the same maximum range. In fact, 802.11n just degrades into 802.11g as the SNR gets worse and worse, so this has to be true.

802.11n is certainly faster at close and medium range. That's because 802.11g tops out at an SNR of about 20dB. That is, the Shannon Limit says you can go faster when you have >20dB, but 802.11g doesn't try; technology wasn't ready for it at the time. 802.11n can take advantage of that higher SNR to get better speeds at closer ranges, which is great.

But the claim about longer range, by any normal person's definition of range, is simply not true.

Luckily, marketing people are not normal people. In the article I linked above they explain how. Basically, they define "twice the range" as a combination of "twice the speed at the same distance" and "the same speed at twice the distance." That is, a device fulfilling both criteria has double the range as an original device which fulfills neither.

It sounds logical, but in real life, that definition is not at all useful. You can do it by comparing, say, 802.11g and 802.11n at 5ft and 10ft distances. Sure enough, 802.11n is more than twice as fast as 802.11g at 5ft! And at 10ft, it's still faster than 802.11g at 5ft! Therefore, twice the range. Magic, right? But at 1000ft, the same equations don't work out. Oddly, their definition of "range" does not include what happens at maximum range.

I've been a bit surprised at how many people believe this "802.11n has twice the range" claim. It's obviously great for marketing; customers hate the limits of wifi's maximum range, so of course they want to double it, or at least increase it by any nontrivial amount, and they will pay money for a new router if it can do this. As of this writing, even wikipedia's table of maximum ranges says 802.11n has twice the maximum range of 802.11g, despite the fact that anyone doing a real-life test could easily discover that this is simply not the case. I did the test. It's not the case. You just can't cheat Shannon and the Signal to Noise Ratio.

...

Coming up next, some ways to cheat Shannon and the Signal to Noise Ratio.

Posted Fri Jul 18 02:23:26 2014 Tags:

today i received spam from a private equity firm. details below for the search engines.

From: Steve Isom [mailto:smi@northbridge.com]
Sent: Thursday, July 17, 2014 5:40 AM
To: several-addresses@my-dayjob
Subject: North Bridge Introduction

Paul,

read more

Posted Fri Jul 18 00:12:05 2014 Tags:

A “non-blocking” IPv6 connect() call was in fact, blocking.  Tracking that down made me realize the IPv6 address was mostly random garbage, which was caused by this function:

bool get_fd_addr(int fd, struct protocol_net_address *addr)
{
   union {
      struct sockaddr sa;
      struct sockaddr_in in;
      struct sockaddr_in6 in6;
   } u;
   socklen_t len = sizeof(len);
   if (getsockname(fd, &u.sa, &len) != 0)
      return false;
   ...
}

The bug: “sizeof(len)” should be “sizeof(u)”.  But when presented with a too-short length, getsockname() truncates, and otherwise “succeeds”; you have to check the resulting len value to see what you should have passed.

Obviously an error return would be better here, but the writable len arg is pretty useless: I don’t know of any callers who check the length return and do anything useful with it.  Provide getsocklen() for those who do care, and have getsockname() take a size_t as its third arg.

Oh, and the blocking?  That was because I was calling “fcntl(fd, F_SETFD, …)” instead of “F_SETFL”!

Posted Thu Jul 17 03:31:57 2014 Tags:


Testimony of

Paul Vixie, Chairman & CEO
Farsight Security, Inc.


before the

Subcommittee on Crime and Terrorism
United States Senate Committee on the Judiciary


Hearing on

Taking Down Botnets: Public and Private Efforts to Disrupt and Dismantle Cybercriminal Networks


July 15, 2014
Posted Thu Jul 17 00:25:18 2014 Tags:
At the end of the last blog entry I asked a simple enough question: how many different online accounts do you have? I must come clean and admit that it was a bit of a trick question. Most of us have more accounts registered with more online services that we probably wish we had, but when you think about it most of us really only have one account that matters because it is the key to unlocking all of those accounts: our email address.

Virtually every online service uses your email as the unique identifier for your account. They send an email to you as a way to confirm account creation. They send an email to you when you want to reset your password. They also tend to harass annoy inform you of events and updates via that same email address. It's the best way to harass annoy get a hold of you, and the assumption is that you can be verified to be you by your email address.

An emerging addition to the email address if your mobile phone number. This method is increasingly used by credit card companies, for instance, to verify payments online.

The general exception to this rule are services that actually require real security, such as online banking. Those services tend to have features like two-factor authentication with an offline token of some sort. Other than these higher-security services that take their job a bit more seriously, everything else back-ends on to your email or mobile phone.

That means that when it comes to authentication you effectively have one account, maybe two if you use services that also use your mobile phone. Anyone who has access to your email can reset your passwords and easily gain access to your accounts. (This actually happens fairly often online.) What's really crazy is that pretty well all of those account verifications and password reset requests happen over unencrypted email making it fairly trivial to intercept them as they pass over the network between the service and your system.

Think about that for a moment ... you have one key to all your systems. The message stream is sent over a bulk channel with no security. Yet, it basically works. This leads us to an interesting pair of conclusions:

Firstly, email desperately needs an overhaul. Unencrypted messaging, particularly when sensitive in nature (like access to your all-valuable Facebook account ;), should simply not be happening. It happens because it is "too hard" to set up and maintain encryption services for most people and the online services who (ab)use your email in this way don't really care. Just as importantly, the metadata contained in the headers of each email betray too much information. Without even looking at the content of an email one can cast a net to grab account reset requests, for instance. (Let alone track who you are talking with, allowing the formation of revealing social networks that you never gave your permission to others to see.) So, yes, email needs a re-do.

Secondly, email is damn powerful and not going anywhere. Remember all those articles a few years back about how email was on the way out? Seems they forgot about how people use email to tie their online life together. So what makes email so effective?

Well, it's a lightweight system for getting messages to random people. It's a globally addressable system that does not require any centralized system, which means it works everywhere and for everyone no matter what choice in service provider the individual user (or their organization) makes.

That centralize social networks rely on email so heavily is very telling about the key weakness of those systems and the strength of a globally addressable lightweight message passing system.

In fact, one is led to wonder just how much of our social networking could be replaced with a system based entirely on a decentralized globally addressable lightweight message passing system. I know I have been pondering this, and I hope you will too.

I'm sure someone will jump up in this point and point at Diaspora (or similar efforts), but such systems have really missed on the real opportunities by engaging in shortest-path-to-destination thinking rather than engaging in the creation of any real, compelling vision.

That may sound harsh, but stay with me here for a few more sentences before launching the flamethrowers. These "open social networks" don't pass messages to the end user. They pass messages to servers which the user then consults. They have simply replicated the model of the incumbent services without considering just how piss-poor those systems really are since they are designed not for the people using them but for the companies making profits from them.

This becomes apparent when we compare (e.g.) Diaspora with the lowly owner of all your accounts: email. Email has end multiple point delivery mechanisms (imap, pop3, ..) which give it that all important push functionality. It provides gateways for filtering (server and client side), sharing resources, full synchronization between devices of messages and identities, re-sharing of messages, moving the location and/or address of your account, aliases (anonymity), attachments, event coordination, ...

Diaspora (and similar) distribute the servers into many hands but they don't actually do anything fundamentally more interesting over the services they intend to displace while simultaneously being capable of far less than humble email. That Diaspora (to keep picking on it ;) uses email for notifications is very telling of what the real score is. Meanwhile, email has been distributed and run primarily by free software from the very beginning, which are the two things  free software social networks were supposedly bringing as innovations. As is plain to see, these are neither innovations nor are they sufficient to displace the proprietary services they compete with.

But enough gnashing of teeth, let's get positive here. You know what would be a hell of a lot more interesting than Diaspora et al? A lightweight, high-performance message queue that is secured by default (no messages in the clear here), globally addressable, anonymizable, syncronizable, supports pub-sub and provides a reasonable API for rich client construction. In a phrase: email re-done for the 21st century. Such a thing could be used as a fabric for networking between people.

Other than stalking following your favorite celebrities or being harassed annoyed marketed to by companies, such a system ought to be able to replace nearly everything people do on social networks today without any mandated centralized storage while providing as-good or better results.  Seriously: do a quick survey of your own social network activities and those of your friends and family and think how much of that would not be able to translate to such a system.

The Facebooks and G+ of the world could indeed remain for the corner cases, though I suspect people will find it a lot less interesting at that point, which could push them towards the same fate of the MySpaces and GeoCities. That is precisely why we can be sure that none of the large Internet brands will be the source for such a thing, even though such a system would fulfill what people generally actually want from social networks.

Namely, finding people of interest so they can share pictures of kittens and their children with them. ;)

p.s. anyone who mentions Google Apache Wave will be immediately instructed to re-read this blog entry until they understand why that's not the droid we're looking for.
Posted Wed Jul 16 07:40:00 2014 Tags:

[ This is a version of an essay that I originally published on Conservancy's blog ].

Eleven days ago, Conservancy announced Kallithea. Kallithea is a GPLv3'd system for hosting and managing Mercurial and Git repositories on one's own servers. As Conservancy mentioned in its announcement, Kallithea is indeed based on code released under GPLv3 by RhodeCode GmbH. Below, I describe why I was willing to participate in helping Conservancy become a non-profit home to an obvious fork (as this is the first time Conservancy ever welcomed a fork as a member project).

The primary impetus for Kallithea is that more recent versions of RhodeCode GmbH's codebase contain a very unorthodox and ambiguous license statement, which states:

(1) The Python code and integrated HTML are licensed under the GPLv3 license as is RhodeCode itself.
(2) All other parts of the RhodeCode including, but not limited to the CSS code, images, and design are licensed according to the license purchased.

Simply put, this licensing scheme is — either (a) a GPL violation, (b) an unclear license permission statement under the GPL which leaves the redistributor feeling unclear about their rights, or (c) both.

When members of the Mercurial community first brought this license to my attention about ten months ago, my first focus was to form a formal opinion regarding (a). Of course, I did form such an opinion, and you can probably guess what that is. However, I realized a few weeks later that this analysis really didn't matter in this case; the situation called for a more innovative solution.

Indeed, I recalled at that time the disputes between AT&T and University of California at Berkeley over BSD. In that case, while nearly all of the BSD code was adjudicated as freely licensed, the dispute itself was painful for the BSD community. BSD's development slowed nearly to a standstill for years while the legal disagreement was resolved. Court action — even if you're in the right — isn't always the fastest nor best way to push forward an important Free Software project.

In the case of RhodeCode's releases, there was an obvious and more productive solution. Namely, the 1.7.2 release of RhodeCode's codebase, written primarily by Marcin Kuzminski was fully released under GPLv3-only, and provided an excellent starting point to begin a GPLv3'd fork. Furthermore, some of the improved code in the 2.2.5 era of RhodeCode's codebase were explicitly licensed under GPLv3 by RhodeCode GmbH itself. Finally, many volunteers produced patches for all versions of RhodeCode's codebase and released those patches under GPLv3, too. Thus, there was already a burgeoning GPLv3-friendly community yearning to begin.

My primary contribution, therefore, was to lead the process of vetting and verifying a completely indisputable GPLv3'd version of the codebase. This was extensive and time consuming work; I personally spent over 100 hours to reach this point, and I suspect many Kallithea volunteers have already spent that much and more. Ironically, the most complex part of the work so far was verifying and organizing the licensing situation regarding third-party Javascript (released under a myriad of various licenses). You can see the details of that work by reading the revision history of Kallithea (or, you can read an overview in Kallithea's LICENSE file).

Like with any Free Software codebase fork, acrimony and disagreement led to Kallithea's creation. However, as the person who made most of the early changesets for Kallithea, I want to thank RhodeCode GmbH for explicitly releasing some of their work under GPLv3. Even as I hereby reiterate publicly my previously private request that RhodeCode GmbH correct the parts of their licensing scheme that are (at best) problematic, and (at worst) GPL-violating, I also point out this simple fact to those who have been heavily criticizing and admonishing RhodeCode GmbH: the situation could be much worse! RhodeCode could have simply never released any of their code under the GPLv3 in the first place. After all, there are many well-known code hosting sites that refuse to release any of their code (or release only a pittance of small components). By contrast, the GPLv3'd RhodeCode software was nearly a working system that helped bootstrap the Kallithea community. I'm grateful for that, and I welcome RhodeCode developers to contribute to Kallithea under GPLv3. I note, of course, that RhodeCode developers sadly can't incorporate any of our improvements in their codebase, due to their problematic license. However, I extend again my offer (also made privately last year) to work with RhodeCode GmbH to correct its licensing problems.

Posted Tue Jul 15 16:45:00 2014 Tags:

Blogging will be light and possibly nonexistent for the next week, as I’m off to Summer Weapons Retreat 2014 for fun and swordplay.

Keep out of trouble until I get back…oh, who am I kidding. Go make interesting trouble.

Posted Tue Jul 15 10:48:46 2014 Tags:

Yesterday’s Kin (Nancy Kress; Tachyon Publications) is a surprisingly pedestrian first-contact novel. Surprisingly because Nancy Kress has done groundbreaking SF in the past. While this novel is competently written, no new ground is being broken here.

Aliens land in New York City and announce that within a year Earth will encounter a sort of interstellar spore cloud that is likely to be infectiously lethal to humans. They ofter help with attempts to develop a cure.

Then it turns it that the aliens are human stock, transplanted to a distant K-type star 150,000 years ago. There are a handful of human with a rare haplotype that they recognize as kin. A few of these kin (including one of the major characters) attempt to assimilate themselves to the aliens’ culture.

Sadly, there isn’t as much story value as there could be here. Far too much of the novel is spent on the major characters’ rather tiresome family dramas. The resolution of the crisis is rather anticlimactic. SFnal goodness is mostly limited to clever re-use of some obscure facts about human paleontology.

On her past record, Nancy Kress might have some really thought-provoking novels in her yet. This isn’t one of them.

Posted Sun Jul 13 02:33:12 2014 Tags:

The introduction to The Year’s Best Science Fiction and Fantasy 2014 (Rich Horton, ed.; Prime Books) gave me a terrible sinking feeling. It was the anthologist’s self-congratulatory talk about “diversity” that did it.

In the real world, when an employer trumpets its “diversity” you are usually being told that hiring on the basis of actual qualifications has been subordinated to good PR about the organization’s tenderness towards whatever designated-victim groups are in fashion this week, and can safely predict that you’ll be able to spot the diversity hires by their incompetence. Real fairness doesn’t preen itself; real fairness considers discrimination for as odious as discrimination against; real fairness is a high-minded indifference to anything except actual merit.

I read the anthologist’s happy-talk about the diversity of his authors as a floodlit warning that they had often been selected for reasons other than actual merit. Then, too, this appears to be the same Rich Horton who did such a poor job of selection in the Space Opera anthology. Accordingly, I resigned myself to having to read through a lot of fashionable crap.

In fact, there are a few pretty good stories in this anthology. But the quality is extremely uneven, the bad ones are pretty awful, and the middling ones are shot through with odd flaws.

James Patrick Kelly’s Soulcatcher is a tense, creepy little SF piece about psychological slavery and revenge. Not bad, but not great. It’s what I think of as read-once; clever enough to be rewarding the first time, not enough depth to warrant reconsideration or rereading.

Angelica Gorodischer’s Trafalgar and Josefina plunges right into awful. There’s actually a decent secondary-world story in here struggling to get out, but the framing narrative is both teeth-jarring and superfluous. Yes, you guessed it – a diversity hire, translated from Spanish.

Tom Purdom’s A Stranger from a Foreign Ship is a welcome surprise; Purdom is a fine writer from whom we’ve heard far too little in recent decades. He gives us a noirish tale of a man with an oddly limited superpower.

Theodora Goss’s Blanchefleur is an otherwise appealing fantasy seriously marred by the author’s determined refusal to maintain internal consistency in the secondary world. Yes, standards are lower for this in fantasy than SF, but really…medieval-technology villages and taking animals and dragons coexisting with electricity and motorcars, on Earth, and nobody notices? FAIL.

Yoon Ha Lee’s Effigy Nights is a weird tale of warfare in a world (apparently) so saturated with smart matter that symbols can take on real life. Either that or it’s a particularly annoying science fantasy. It’s a flaw that the author dropped so few clues that I couldn’t tell whether its universe is an SF one or not.

Maria Dahvana Headley’s Such & Such Said to So & So is an urban fantasy featuring cocktails come to life that wants to be hip and edgy but achieves excessively cute and nigh-unreadable instead. I had to struggle to finish it.

Robert Reed’s Grizzled Veterans of Many and Much is a hard look at the implications of a technology that can trade the last years of a fading life for a few days of turbocharged superintelligence. This really is edgy, and one of the better efforts in this collection.

Geoff Ryman’s Rosary and Goldenstar is an alternate-history romance in which Dr. John Dee and Rosencrantz and Guildenstern conspire to turn William Shakespeare into an SF writer. Arcane historical references to the Renaissance ferment in astronomy add value for those equipped to decode them, with language-translation humor as a bonus. Alas, this never really rises above being a clever stunt.

Benjanun Sriduangkaew’s The Bees Her Heart, The Hive Her Belly is a tale of the strange turns familial love can take in a world of pervasive smart matter and mutable identities. It takes some work to keep up with what the author is doing, but the effort is rewarded. This goes beyond a read-once; in fact, it may take a second reading to absorb all the implications.

K. J. Parker’s The Dragonslayer of Merebarton does an interesting turn on the knight-vs.-dragon scenario of popular folklore by treating it absolutely straight as a problem in tactics and mechanics. Technology-of-magic without the magic…

Lavie Tidhar’s The Oracle is a well written narrative of the emergence of nonhuman intelligence, but has no real surprises in it if you understand genetic programming and have read other SF about fast-takeoff singularities.

E. Lily Yu’s Loss, with Chalk Diagrams is atmospheric but pointless. It wastes its SFnal premise (brains can be rewired to remove traumatic memories) on a mere character study. There’s no conceptual breakthrough here, just a rehash of tired pseudo-profundities we’ve seen far too many times in literary fiction.

C.S.E. Cooney’s Martyr’s Gem considers love, obsession, status, and revenge in the context of a society not quite like any that has ever been real, but imagined in lovely and convincing detail. This is fine worldbuilding even if none of the pieces are made of any technology but magic, and better SF in its way than several of the stories full of SF stage furniture elsewhere in this volume.

Alaya Dawn Johnson’s They Shall Salt The Earth With Seeds of Glass is another waste of a potentially interesting premise on a mere character study. If this were proper SF we would learn what motivates the glassmen and, perhaps, how they can be defeated.

Jedediah Berry’s A Window or a Small Box is trying to be surrealistic. I think. I found it pointless, unreadable garbage – so bad I found it too offensive to finish.

Carrie Vaughn’s Game of Chance argues that the ability to change history is best exercised in small, humble steps. Competently written, but there is nothing here one can’t see coming once the premise and characters have been introduced.

Erik Amundsen’s Live Arcade is another case of too much cleverness and wordage being expended on too slight a premise – characters in a video game are more than they appear. While reading, I wanted to like this story more than its big reveal turned out to deserve. Alas.

Madeline Ashby’s Social Services is creepy but less slight. In a world of ubiquitous surveillance and paternalistic social services, how dies a child stay off the grid? The creepiness is mainly in the ending; one gets the feeling the viewpoint character may be disposable.

Alex Dally McFarlane’s Found examines what might make life worth living in failing asteroid colonies – and what might end it. It makes its point – that being forced out of the only ecological niche for which one is actually adapted is a tragedy even when it’s required for survival – in a particularly haunting way.

Ken Liu’s A Brief History of the Transpacific Tunnel is an excellent examination of an alternate history better than our own, changed by a vast engineering work. It is also about guilt and remembrance and how crimes come to light. Thankfully, the author had the good judgment not to let the psychological elements crowd the SF story values offstage, avoiding a mistake all too common in this collection.

E. Lily Yu’s Ilse, Who Saw Clearly is a lovely allegorical fantasy about how quests can become larger than one intended. This one deserves to be remembered.

Harry Turtledove’s It’s the End Of The World As We Know It, and We Feel Fine looks as whimsical as its title, but there’s a serious SFnal point about the wages of (non)-domestication inside it. I think his future would actually be a nightmare of gentled humans being systematically abused by throwbacks, but – perhaps this is the world we already live in…

Krista Hoeppner Leany’s Killing Curses: A Caught-Heart Quest is not terrible, but by trying so hard to avert any recognizable fantasy tropes it becomes over-clever and unengaging.

Peter Watts’s Firebrand could be a lesson to all the authors of muddled, pointless, defective science fiction in this anthology about how to do it right. A disturbingly plausible premise about human spontaneous combustion is pursued with inexorable logic and dark humor.

Maureen McHugh’s The Memory Book is a dark, well-executed fantasy about Victorian voodoo. At best a read-once, alas.

Howard Waldrop’s The Dead Sea-bottom Scrolls is an entertaining but slight tale of windsailing on an alternate Mars that really had Martians. Aside from raising a mild chuckle I didn’t really see a point here.

Karin Tidbeck’s A Fine Show on the Abyssal Plain is another dark fantasy about the collapse of the fourth wall around a very strange theatrical troupe. Another well-written read-once.

Linda Nagata’s Out in the Dark is much more substantial. It incorporates some speculative technologies we’ve seen before in SF for body modification and self-duplication with a suggestion that some of their more troubling implications might be treated as crimes against unitary personhood that need to be policed against. But that’s a model that could, under some circumstances, produce injustices – and what’s an honest cop to do?

Naim Kabir’s On the Origin of Song is a wildly inventive fantasy full of vivid, almost Vancian imagery. One could milk a novel, and a lesser writer might have milked several, out of this setting.

Tang Fei’s Call Girl is yet another over-clever cloud of nothing much. The only way the story makes any sense at all is if all the characters are embedded in a giant VR after the fashion of the Matrix movies, but if this is so no interesting consequences are ever drawn from it.

Christopher Barzak’s Paranormal Romance isn’t even clever. It tries to be cute, but you can see every plot twist coming a mile off. Yeah, of course the witch’s blind date is a werewolf, etc weary cetera. Yawn.

Yugimi Okawa’s Town’s End is a fantasy premised on creatures of Japanese mythology needing a dating service to find men. A transparent and sad allegory of Japan’s dire demographic situation, but lovely and a bit haunting nevertheless.

Ian R. MacLeod’s The Discovered Country looks like a political allegory of an angry man determined to destroy the virtual paradise of the post-mortal idle rich, but it has a sting in its tail: when reality is virtual you may not even be able to trust your own memories.

Alan DeNiro’s The Wildfires of Antarctica is a middling amount of sound and fury about nothing much. Sophont art turns on the dissipated patron that bought it…boring and obvious.

Eleanor Arnason’s Kormak the Lucky finishes the anthology strong with a steampunkish take on Norse and Irish mythology.

If I believed the title of this anthology, I’d have to think the SF field was in desperate shape and fantasy barely better off. There are maybe five of the SF stories that will be worth remembering in a decade, and at best a few more of the fantasies. The rest is like wallpaper – busy, clever, and flat – except for the few pieces that are actively bad.

I’d ask what the anthologist was thinking, but since I’ve seen the author list on one of his other anthologies I don’t have to guess. For truth in advertising, this should probably have been titled “Rich Horton Recruits Mainly From His Usual Pool of Writers There Are Good Reasons I’ve Never Heard Of”. And far too many of them are second-raters who, if they ever knew how to write a decent F/SF story, have given that up to perform bad imitations of literary fiction.

In SF all the writing skill in the world avails you naught unless you have an idea to wrap your plot and characters around. In fantasy you need to be able to reach in and back to the roots of folklore and myth. Without these qualities at the center an F/SF story is just a brittle, glossy surface over nothing. Way too many of these stories were superficial cleverness over vacuum.

Posted Fri Jul 11 21:54:29 2014 Tags:
I've been rambling-writing for a couple weeks now about multi-process architecture (MPA) as seen in applications such as Akonadi or Chrome. After covering both the up- and down-sides, I also wrote a bit about missed opportunities: things that should be possible with MPA but which are rarely seen in practice. I kept promising to write about my thoughts on solutions to the downsides and missed opportunities, and that's where we are now.

The answer is deceptively simple: green processes. These are like green threads, which a few people actually mentioned in the comments sections of those past blog entries. Like green threads, green processes are mimics of native processes but run in a virtual machine (VM) instead. Some of the benefits are similar: you can have far less overhead per process (Erlang's per-process overhead is just 309 words) and you can launch thousands of them even if you only have one CPU core to work with without grinding they system to a halt. More usefully, if you have a 4 core system the VM can schedule N processes in exactly 4 native threads making full utilization of the system while minimizing things like context switch costs. (That does trivialize the complexity of the task by summarizing it in a single sentence ... )

Unlike green threads, however, green processes provide separation of memory access and require message passing rather than shared memory objects. They also more naturally follow the failure semantics of processes, such as the ability to crash. That may seem like a trivial set of differences, but the implications are hugely significant.

For instance, with crashing processes you can limit (and in many cases simply get rid of entirely) defensive programming. This requires a suitable language to go with the VM, but with such a thing in hand code can be written that only works in known-good (or white-listed) states. Everything else causes a crash, and this gets propagated appropriately through the system.

That system can include process supervisors which can restart processes or kill related ones in response to failures. It should also be noted that one still wants exceptions as those are for a rather different use case: non-fatal errors with known causes. (Essentially white-listed undesired behaviors.)

With message passing being the only way to coordinate between processes, you also are a tiny step away from distributed applications. After all, it doesn't look any different to the process in the VM if the message came from a process in the same VM or from a process elsewhere. So you can now split up your application between multiple VMs on the same system or on completely different systems connected by a network.

This could even be done at runtime or as a configuration option. Consider a system where one process needs to use unsafe native code (more on that later) and the rest simply do their thing safely in the VM. That one process could be moved to a separate VM (complete with process supervision) to keep it away from the rest of the processes. If the native code takes down that process or the native code leads to a security vulnerability, you now have process separation at the native OS level. If that process only causes problems on some systems (say, a graphical app being run on systems with a particular vendors particularly crashtastic GPU drivers), then it could be moved out of process only such systems and kept in-process otherwise.

Due to the lightweight nature of green processes one can afford to break an application up into a massively concurrent system. Each bit of I/O can live in its own process, for instance. Spawning a process for each socket or file operation becomes reasonable. Synchronous finite state machines (FSM), very useful things that, when not forced into asynchronous behavior due to event loops, are very simple to write and manage, become second nature.

A VM with green processes ends up resolving, or at least noticeably improving on, nearly all the downsides of native processes while also making most of the missed opportunities low-hanging fruit, sometimes even for free (as seen with distributing processes). What impact could this have?

Let's look at Akonadi. It could be a hundred processes instead of the two dozen it currently is on my system (I have a lot of accounts ...), making the code much simpler in the process (no more async job and async FSM implementations) while having dramatically lower overhead. Not only would the per-process cost be lower, even with message passing the cost would be truly zero as objects (not just serialized memory buffers!) are passed using copy-on-write (COW) and/or reference counted storage. On smaller systems with only one or two cores, the entire application would automatically "collapse" down to a single-threaded application that would be nearly identical in nature (and therefore also in performance) to a purposefully single-threaded, single-process, async event driven application. This is a new avenue for scalablility. Another one would be in how remote Akonadi processes would come alone for free; want to run Akonadi on a server but access the data locally? Want to spread your Akonadi processes across a network of systems? No problem. Meanwhile, all the benefits of the multi-process system it currently enjoys, including robustness, would be retained.

Or how about Plasma. Every DataEngine, every model and every widget could live in its own process in the VM. Since it looks like one process to the native OS (because it is), the actual UI could be delegated to a specific thread and even on x.org it could paint all day even if a DataEngine or other component were to die. Installing a new Plasmoid, even one with compiled code, could be hot-reloaded without restarting the desktop shell. KRunner could be sucked into the main plasma-shell process without risking stability or robustness, shrinking the overall footprint of the system. In fact, all of the separate processes could be pulled into the same VM while retaining all of the current benefits, including re-use on other systems that don't want plasma-shell.

It isn't all picnic baskets and fluffy white clouds, however.

Running natively compiled C/C++/ASM code in your VM will crash the entire VM when that code segfaults. So if one were to use Qt, for example, from such a VM any crash in Qt would bring down the whole thing. The benefits are only offered to code running in the VM. Perhaps using multiple VMs for just those parts of the system would be a solution in some cases. Given the message passing of such a system, it is possible to even run native code applications external to the VM and have them appear inside the VM as any other local-to-the-VM process (to other processes in VM, anyways) by grafting the message passing protocol onto that native application.

C/C++ isn't particularly suited to being run in such a VM, at least not with today's tools. So either new languages are needed or we need new tools. Or both. A new language for such a VM would not be the worst of ideas, actually: look how QML has vastly improved life in the UI world. Similarly, a properly designed language could make application development much safer, much easier and much faster. (To those who live-and-breath Python/Ruby/Perl/etc. that's not news, I'm sure.) That does mean that some amount of application code would need to be rewritten to take advantage of such a VM. This is probably desirable in any case since most applications will need rethinking in terms of massive concurrency. If the VM supports easily binding in existing native code, this could even be done in stages. We know that can work as this is exactly how Plasma was transitioned from imperative QGraphicsView code to declarative QML code. Still, there would be a transition period.

Finally, such a VM is not trivial to do correctly. It ends up becoming a micro-operating-system in its own right with memory management and process schedulers. Care needs to be paid to how messages are passed to keep overhead low there, as well. Making such a thing would be a significant investment. One could almost certainly start with existing art, but a lot of work would still be required.

Speaking of existing art: as I was considering the "after convergence" questions earlier this year, I ended up looking around for systems already tackling the problems I saw related to MPA and I came across Erlang which does nearly all of the above. So if you are interested in seeing what this can look like in practice, I definitely recommend looking into it. It is not a perfect system, but it is about the only one I could find that wasn't an academic project that addressed these issues head-on. I think the original designers of the runtime were way ahead of their time.

Erlang itself is probably not 'the answer', however. It is an amazing system that is just fantastic for server side work. (On that note, I think it is a much better fit for Akonadi than C++ ever could be, or for Bodega than node.js ever could be.) However, it lacks some of the features I'd really like to see in such a system such as cross-VM process migration (non-trivial to implement properly, granted), it is not well suited to numeric processing (not an issue for most data-centric servers) and has some legacy issues related to things like strings (though that has come leaps and bounds in recent years as well). I don't care about syntax warts as they aren't that bad in Erlang and if you think they are then simply use the rather nicer Elixir that runs on the same VM.

However, a system designed specifically for the needs of client-side user interface code could be marvelous. Systems under the application would remain in C/C++ and the UI should be done declaratively (with e.g. QML), but the application could be something else entirely that makes writing the applications in between those two parts far easier and ...

... more importantly than easier development, gift them with super-powers current systems are unlikely to ever offer. Multi-process architecture, despite the inherent benefits like increased application robustness, is really just a stepping stone towards being able to do more interesting things.

With the premise of a massively-concurrent system with minimized costs and a consistent message passing system in place as axiomatic assumptions for future applications, we can begin to explore new possibilities that open up.

You see, after convergence, which allows us to forget that devices are somehow different from each other (without hobbling the user interface into stupidity in the process), we can start thinking about how to use all those devices as a single fabric, be they remote servers, you and your friend's phones, your phone and your boss' laptop .. be they located on the same or different network segments .. be they in a consistent or a dynamic set of states ..

Still, before plunging in that direction conceptually, there are useful insights remaining to be brought into this house of thought. Next I will be exploring methods of authentication.

Until then, consider this question: How many separate online accounts do you have?

(I bet almost everyone will get the answer to that one "wrong". *devilish smile*)
Posted Thu Jul 10 12:36:00 2014 Tags:

I have many things to tell you about wifi, but before I can tell you most of them, I have to tell you some basic things.

First of all, there's the question of transmit power, which is generally expressed in watts. You may recall that a watt is a joule per second. A milliwatt is 1/1000 of a watt. A transmitter generally can be considered to radiate its signal outward from a center point. A receiver "catches" part of the signal with its antenna.

The received signal power declines with the square of the radius from the transmit point. That is, if you're twice as far away as distance r, the received signal power at distance 2r is 1/4 as much as it was at r. Why is that?

Imagine a soap bubble. It starts off at the center point and there's a fixed amount of soap. As it inflates, the same amount of soap is stretched out over a larger and larger area - the surface area. The surface area of a sphere is 4 π r2.

Well, a joule of energy works like a millilitre of soap. It starts off at the transmitter and gets stretched outward in the shape of a sphere. The amount of soap (or energy) at one point on the sphere is proportional to
1 / 4 π r2.

Okay? So it goes down with the square of the radius.

A transmitter transmitting constantly will send out a total of one joule per second, or a watt. You can think of it as a series of ever-expanding soap bubbles, each expanding at the speed of light. At any given distance from the transmitter, the soap bubble currently at that distance will have a surface area of 4 π r2, and so the power will be proportional to 1 / that.

(I say "proportional to" because the actual formula is a bit messy and depends on your antenna and whatnot. The actual power at any point is of course zero, because the point is infinitely small, so you can only measure the power over a certain area, and that area is hard to calculate except that your antenna picks up about the same area regardless of where it is located. So although it's hard to calculate the power at any given point, it's pretty easy to calculate that a point twice as far away will have 1/4 the power, and so on. That turns out to be good enough.)

If you've ever done much programming, someone has probably told you that O(n^2) algorithms are bad. Well, this is an O(n^2) algorithm where n is the distance. What does that mean?

    1cm -> 1 x
    2cm -> 1/4 x
    3cm -> 1/9 x
    10cm -> 1/100 x
    20cm -> 1/400 x
    100cm (1m) -> 1/10000 x
    10,000cm (100m) -> 1/100,000,000 x

As you get farther away from the transmitter, that signal strength drops fast. So fast, in fact, that people gave up counting the mW of output and came up with a new unit, called dBm (decibels times milliwatts) that expresses the signal power logarithmically:

    n dBm = 10n/10 mW

So 0 dBm is 1 mW, and 30 dBm is 1W (the maximum legal transmit power for most wifi channels). And wifi devices have a "receiver sensitivity" that goes down to about -90 dBm. That's nine orders of magnitude below 0; a billionth of a milliwatt, ie. a trillionth of a watt. I don't even know the word for that. A trilliwatt? (Okay, I looked it up, it's a picowatt.)

Way back in university, I tried to build a receiver for wired modulated signals. I had no idea what I was doing, but I did manage to munge it, more or less, into working. The problem was, every time I plugged a new node into my little wired network, the signal strength would be cut down by 1/n. This seemed unreasonable to me, so I asked around: what am I doing wrong? What is the magical circuit that will let me split my signal down two paths without reducing the signal power? Nobody knew the answer. (Obviously I didn't ask the right people :))

The answer is, it turns out, that there is no such magical circuit. The answer is that 1/n is such a trivial signal strength reduction that essentially, on a wired network, nobody cares. We have RF engineers building systems that can handle literally a 1/1000000000000 (from 30 dBm to -90 dBm) drop in signal. Unless your wired network has a lot of nodes or you are operating it way beyond distance specifications, your silly splitter just does not affect things very much.

In programming terms, your runtime is O(n) + O(n^2) = O(n + n^2) = O(n^2). You don't bother optimizing the O(n) part, because it just doesn't matter.

(Update 2014/07/14: The above comment caused a bit of confusion because it talks about wired networks while the rest of the article is about wireless networks. In a wireless network, people are usually trying to extract every last meter of range, and a splitter is a silly idea anyway, so wasting -3 dB is a big deal and nobody does that. Wired networks like I was building at the time tend to have much less, and linear instead of quadratic, path loss and so they can tolerate a bunch of splitters. For example, good old passive arcnet star topology, or ethernet-over-coax, or MoCA, or cable TV.)

There is a lot more to say about signals, but for now I will leave you with this: there are people out there, the analog RF circuit design gods and goddesses, who can extract useful information out of a trillionth of a watt. Those people are doing pretty amazing work. They are not the cause of your wifi problems.

Posted Thu Jul 10 05:15:49 2014 Tags: