This paper studies approximate distributed routing schemes on dynamic communication networks. The paper focuses on dynamic weighted general graphs where the vertices of the graph are fixed but the weights of the edges may change. Our main contribution concerns bounding the cost of adapting to dynamic changes. The update efficiency of a routing scheme is measured by the number of messages that need to be sent, following a weight change, in order to update the scheme. Our results indicate that the graph theoretic parameter governing the amortized message complexity of these updates is the local density D of the underlying graph, and specifically, this complexity is ${\tilde\Theta}(D)$ . The paper also establishes upper and lower bounds on the size of the databases required by the scheme at each site.

Subscription required for access to full text.

Dynamic Routing Schemes for General Graphs

Researchers have proposed a variety of metrics to measure important graph properties, for instance, in social, biological, and computer networks. Values for a particular graph metric may capture a graph’s resilience to failure or its routing efficiency. Knowledge of appropriate metric values may influence the engineering of future topologies, repair strategies in the face of failure, and understanding of fundamental properties of existing networks. Unfortunately, there are typically no algorithms to generate graphs matching one or more proposed metrics and there is little understanding of the relationships among individual metrics or their applicability to different settings. We present a new, systematic approach for analyzing network topologies. We first introduce the dK-series of probability distributions specifying all degree correlations within d-sized subgraphs of a given graph G. Increasing values of d capture progressively more properties of G at the cost of more complex representation of the probability distribution. Using this series, we can quantitatively measure the distance between two graphs and construct random graphs that accurately reproduce virtually all metrics proposed in the literature. The nature of the dK-series implies that it will also capture any future metrics that may be proposed. Using our approach, we construct graphs for d = 0, 1, 2, 3 and demonstrate that these graphs reproduce, with increasing accuracy, important properties of measured and modeled Internet topologies. We find that the d = 2 case is sufficient for most practical purposes, while d = 3 essentially reconstructs the Internet AS- and router-level topologies exactly. We hope that a systematic method to analyze and synthesize topologies offers a significant improvement to the set

Systematic Topology Analysis and Generation Using Degree Correlations

Stefan Geens in Stockholm, editor of the Ogle Earth blog, brings you news about virtual globes, with a special focus on Google Earth. Recently he showcased this video demonstration of Perceptive Pixel's display technology.

Perceptive Pixel, Inc. was founded by Jeff Han in 2006 as a spinoff of the NYU Courant Institute of Mathematical Sciences to develop and market the most advanced multi-touch system in the world.

There's a recent Fast Company article about Jeff Han, as well:

Han began his presentation. His fingertips splayed, he placed them on the cobalt blue 36-inch-wide display before him and traced playful, wavy lines that were projected onto a giant screen at his back. He conjured up a lava lamp and sculpted floating blobs that changed color and shape based on how hard he pressed. ("Google should have something like this in their lobby," he joked.) With the crowd beginning to stir, he called up some vacation photos, manipulating them on the monitor as if they were actual prints on a tabletop. He expanded and shrank each image by pulling his two index fingers apart or bringing them together. A few oohs and aahs bubbled up from the floor.

Suppressing a smile, Han told the assembled brain trust that he rejects the idea that "we are going to introduce a whole new generation of people to computing with the standard keyboard, mouse, and Windows pointer interface." Scattering and collecting photos like so many playing cards, he added, "This is really the way we should be interacting with the machines." Applause rippled through the room. Someone whistled. Han began to feel a little bigger.

But he was far from finished. Han pulled up a two-dimensional keyboard that floated slowly across the screen. "There is no reason in this day and age that we should be conforming to a physical device," he said. "These interfaces should start conforming to us." He tapped the screen to produce dozens of fuzzy white balls, which bounced around a playing field he defined with a wave of the hand. A flick of a finger pulled down a mountainous landscape derived from satellite data, and Han began flying through it, using his fingertips to swoop down from a global perspective to a continental one, until finally he was zipping through narrow slot canyons like someone on an Xbox. He rotated his hands like a clock's, tilting the entire field of view on its axis--an F16 in a barrel roll. He ended his nine-minute presentation by drawing a puppet, which he made dance with two fingers.

He basked in the rock-star applause. This is the best kind of affirmation, he thought. The moment you live for.

Can't touch this GUI: Jeff Han's Perceptive Pixel technology

The op-ed page of the LA Times solicited commentary from a full slate of futurist technology pundits who, as it turns out, have nothing but good things to say about the year ahead. The future is so bright, I've got to go buy some tech stocks! Most of them are plugging specific products or services; either that, or analysis has devolved into the old tired/wired dichotomy. Aside from the one-phrase bylines, there are no financial interest disclosures here. I thought those had become de rigueur in the business and financial press, but apparently not so for editorials.

Aside from Ballmer, none featured here are in the hardware business. None are in the infrastructure business. Is this a signal? Are we done there? What of Intel, AMD, Motorola, Broadcom, etc.?

I am especially struck by the pundits' more-of-the-same ideas; perhaps this is partly due to the too-near horizon established by the paper. Ballmer is spun up about policy-based ring-tones; what is that, like, a few hundred lines of code? Sherman is touting Second Life. Several are enamored of YouTube and the slow collapse of broadcast. Barry sees nothing but upside -- freedom! -- in having your entire life's "state" on a memory stick; not content to simply ignore the question of risk, he concludes that the lowest risk option is to carry your digital medical records, tax returns, and a lifetime of recorded communications (voice, video, text, other) in something that could drop from your pocket onto the city sidewalk without notice.

Where are the new applications, the new ideas? The "personal genomics kit" is tantalizing, but Brockman offers no explanation. You can find more here and here. I think people might be as much or more interested in a kit of the variety described by Freeman Dyson -- more of a "toy with consequences", along the lines of a high school chemistry set. (I note that there are as yet zero Google hits for that phrase.)

A few thoughts:

The Internet may start to experience some major growing pains in 2007. IPv6 has been stillborn, known routing problems remain unresolved, and the IPv4 address space is nearing its limits. From the consumer perspective, we are nearly at the end of end to end; by the end of 2007, we may see the start of a trend in which residential broadband Internet service ceases to include a public IP address. 2008 could bring the era of double- and triple-NATted networks.

Vista enhancements notwithstanding, and the industry alarmists put aside, Internet security is in a rather dismal state.

What will they think of next?

Sound familiar?

Track your shared bills and expenses. Effortlessly.

Buxfer: Track Your Money

In an article in this week's Nature, "Safe handling of nanotechnology", a team from the Woodrow Wilson International Center for Scholars argues that "the pursuit of responsible nanotechnologies can be tackled through a series of grand challenges." (Full text is openly available) The editor summarizes thusly:

The spectre of possible harm — real or imagined — is threatening to slow the development of nanotechnology.

If they and their colleagues can rise to these challenges — which include development of new ways of measuring exposure to nanomaterials and assessing the health and environmental impact of that exposure — the true extent of any risks involved should become clear.

The Wilson Center covers itself with a press release:

Society is in danger of squandering the powerful potential of nanotechnology due to a lack of clear information about its risks.

"We are running out of time to ‘get it right.’"

These are the five challenges:

1. instruments to assess environmental exposure to nanomaterials

2. methods to evaluate the toxicity of nanomaterials

3. models for predicting the potential impact of new, engineered nanomaterials

4. ways of evaluating the impact of nanomaterials across their life cycle, and

5. strategic programs to enable risk-focused research

The lead author has a Q&A:

It's very clear that we are moving into a new era in many ways. It's very clear that conventional ways of doing things and thinking just aren't going to be up to the job of dealing with some of these new technologies and products.

They go on:

TR: Have you considered a Wikipedia for nanotechnology research?

AM: The Wikipedia idea is something that has been talked about. And I think that either that or something like that is a very exciting idea. Of course you've always got the issue of validating the information which is there. But certainly I think that's one of the innovative ways that we can look at this.

TR: Has anyone actually looked into establishing a sort of nanowiki?

AM: Not to my knowledge. But there are the beginnings of it.

The reliability of information collected from at large Internet users by open collaborative wikis such as Wikipedia has been a subject of widespread debate. This paper provides a practical proposal for improving user confidence in wiki information by coloring the text of a wiki article based on the venerability of the text. This proposal relies on the philosophy that bad information is less likely to survive a collaborative editing process over large numbers of edits. Colorization would provide users with a clear visual cue as to the level of confidence that they can place in particular assertions made within a wiki article.

Congratulations to Tom, who has been published in this month's issue of First Monday.

The material his article covers was first presented at last year's PhreakNIC Conference. Video of the talk (Google Video) is available. The point where Tom talks about his reliability system for Wikipedia is about 30 minutes into the presentation.

Puppy smoothies: Improving the reliability of open, collaborative wikis

HANDY ONE-LINERS FOR SED (Unix stream editor) Apr. 26, 2004 compiled by Eric Pement - pemente[at]northpark[dot]edu version 5.4

This puts the K in K-rad.

SED one-liners

The Department of Homeland Security Institute for Discrete Sciences is a research institute focused on select topics in data sciences, discrete simulation, and discrete mathematics. These topics, collectively labeled "discrete sciences," represent enabling computational technologies for present and future challenges in homeland security.

Vision: A tightly coupled partnership harnessing the characteristic strengths of select national laboratories, universities, and industrial partners in discrete sciences R&D for homeland security.

Mission: Enable scalable, integrated simulation and information analyses for science-based threat characterization and response while creating a human and institutional plant for discrete sciences technology.

Worth a look ...

Institute for Discrete Sciences

Did the Industrial Memetics Institute submit anything for this call?

Original research papers on the following topics are sought:

* Studies of human-computer trust
* Socio-technical examinations of reputation systems
* Trust-building systems for online interaction

The deadline for this call has already passed, but it may point to a continuing interest in these topics from the editors of this magazine. You could always submit something for a general issue on these and related topics. Also, keep an eye out for this issue to arrive -- it's scheduled for Spring 2007.

Calls for Papers: Special Issue on Security and Usability, IEEE Technology and Society Magazine