The following is a report to my host scientist at Tokyo University and
it functions as a summation of my work at the lab.  The topic is automated
multimedia content distribution and device selection, discovery and management.
It is written at a fairly low theoretic level so that even those not familiar
with the rudiments of graph theory can understand.

--- Begin ---
First we presume a networked world in which every device has a direct
connection and that the connection is "fast enough" for whatever we want to do;
not too farflung of an assumption (depending upon what we want to do ;-).

Imagine that we have a set of types -- each just basically a unique
descriptional name of what a stream of data represents.  Let us call this set
T.  Further imagine that we have a set of services -- provided, for example, by
any number of devices.  Services translate one type into another.  For example,
a service might translate the "MPEG4 Video" type into an "Analog Video" type,
or it might translate the "Analog Video" type into a "Human Display".  An
example of the former is a decoder; an example of the latter might be a
monitor.  Let us imagine that we could enumerate all the services (in all the
devices) in the world -- we will put them in a set called S.

It is important to note that, because our network is "fast enough" and all
devices are directly connected, we do not really need to care exactly what
device provides what service -- only that we know what services it provides.

Now, we almost have all the makings of a theoretically complete system.  What
we need is a way to enumerate all possible service combinations.  A graph does
this quite nicely.  A graph can be represented as two sets -- one set of
vertices and one set of edges (commonly notated as G(V,E)).  In our graph, the
types (T) will be our vertices and the services (S) our edges.  For
completeness in our graph model, I will add that an edge may be in set S if and
only if it maps from two (not necessarily unique) types of set T.

It is important to note at this point, that if we allow services to be
represented by vertices and types by edges, the end result is a system in which
graph traversal is a matter of choosing types to traverse from service vertices
instead of choosing services.  In practice we want exactly the opposite (in the
face of many possible non-unique service choices from a likely smaller set of
service types), we will want to choose the best (closest, fastest, biggest,
cheapest, etc.) service.

We now have a graph with every possible type in the world represented and edges
representing all possible service choices.  Clearly there are lots of edges
(services) coming from each vertex (type).  This is actually a good thing -- we
have lots of choices for providing service.  This construction is quite useful,
as we will see shortly.

First, however, we need one last piece.  Choosing the best path from one type
to another is impossible if we have no information about how good, bad, (close,
far, cheap, expensive, etc.) a particular service is.  Imagine that we do have
a set of criteria for deciding how good a particular service is.  For example,
let us say that we have some metrics for deciding the following:  closeness,
quality, speed, and cost.  Comparing them directly is impossible if we do not
use the same ranges for each.  (ie. if we use simple arithmetic to compare and
use a range of 1 to 100 for cost and 1 to 5 for quality, clearly cost will
dominate -- it uses bigger numbers).  To solve this problem, let us assume that
we either compare them individually (metric type by metric type) or use the
same range for all.  Either way it makes no difference.  What we have is a set
of metrics for comparing cost that can be used at each edge -- let us call the
set of types of metrics M.

We will make one final construct: a function C(e) to map an element of the set
of edges (services) to a cost metric -- in this case, a vector of metrics each
of which is a type from the above set M.

Before using these constructs, let us review them.  We have the set of all
possible stream types in the world: T, the set of all possible services in the
world: S.  We have a graph representing all possible combinations of all
possible services in the world; it is represented by G(T,S).  Finally, we have
a set of metric types, M and we have a cost function C which, given an edge
from S, will return an instance of one of each of the types from set M.

A system fulfills a service request by finding the best path from the requested
source to the requested destination.  For example, let us say that a user
wishes to watch TV on the closest, best set available.  He cares nothing for
what format the broadcasts come in and wants only to be able to change channels
in order to find, for example, a football game.  He requests "TV".  His
computer requests a mapping from a "TV Interface" type to a "Human Display"
type.  At the very least, the system is capable of using Dijkstra's algorithm
in O((T^2)+S) (and is likely capable of doing it much more quickly than that)
to finding the best path between the two types.  This optimal path would
necessarily take into account his desire to have a close display, but still
have it be the best possible.  Thus, it should choose the 27" wide screen
display in front of him instead of his PDA's 3" display.

Let us further presume that he wants to grab a coke from the kitchen, but but
does not want to miss the next play.  The system, if informed he has left the
room, using the same scheme as before, can continually update its service
selection.  In the hallway, the closest, best display may be his PDA, but in
the kitchen it is likely on the counter.  Each of these is selected in kind,
automatically, as he travels using the same means as the 27" display was
selected to begin with.  Each display's own individual characteristics (their
own particular input types, for example) are handled automatically by
resolution through the graph.

Now, theory is wonderful because it allows us to easily express something that,
practically speaking, is simply impossible to construct.  And here is the crux
of the problem you have likely been facing for some time: it is simply
impossible to represent every single element of the true global set S.

I will offer my own solution in a moment, but first will convey what I believe
to be the current STONE system solution (at least in ideal terms).  STONE
solves the problem of not being able to store all of S by storing only (some
of?) the local elements of S.  It then uses a forwarding scheme to have the
service request resolved (hopefully) by successive passing.  The only drawback
is that, as far as I can tell there is no way of making it fully capable of any
of the information that the cost function C can provide.  For example, choosing
the very closest service resolver to pass the request to may result in the
closest TV being selected, but not necessarily the best.

On top of this, the forwarding mechanism, while useful in wide area networks
where communication between only a certain number of directly-connected
neighboring nodes is possible, may not be the optimal solution in a local area
network in which, under most modern LAN architectures, snooping of all LAN
traffic is possible.  In other words, if the underlying architecture is a
contention-based medium (as is the case with non-switched ethernet and all
wireless protocols), one might want to use that to their advantage.

One way to use this while filling in our current world-view of what S should
look like would be to slowly fill in the edges of our graph while listening for
service availability broadcasts -- registering those services in some form of
leasing scheme similar to that seen in Jini (or DHCP for that matter).  Thus
each service expires at some point if it is not updated (presumably if it is no
longer reachable locally).

This method is only useful under the presumption that all the devices we want
to use are essentially reachable via network broadcast.  While I believe Jini
is satisfied with this model, and that it may work to some degree in people's
homes, I also believe it can be augmented once more into something better.

And with this one last augmentation, I conclude.  Again, prudence demands that,
if we have a tool of value in front of us, that we should make use of it in the
task at hand.  The current Internet domain naming structure is woven into the
very fabric of the modern Internet and we are unlikely to be rid of it in the
far-forseeable future.  (Indeed, why would we want to be -- it provides an
extensible hierarchical division of the entire intnernet?) If we were to
leverage this structure, however, we might be able to make entire domains
available to us at one time.  For example, our own home's domain's devices
(i.e., their services) and possibly those of our office might remain on a sort
of "fixed" or non-terminating lease.  If this is the case, those devices that
we "own" or at least have free domain over remain constantly usable for us.

The name of the game here is finding the exact subset of S that is usable for a
given user at any given time.  To be sure, given the local nature of devices
that a user might wish to make use of, those within broadcast range are likely
a good bet.  Including those in certain domains such as those in their home and
office is better.  What more they could want, I cannot currently imagine,
though I am certain some scenario could be dreamt involving such a situation.

In any case, so go my suggestions and the motivations behind them.  More than
anything, I believe that the theoretical model I have constructed here can be
of use in describing any given system or even the theoretical optimal system
making full use of S, were it possible (or, more pointedly, were it useful!).
--- End ---