Local Knowledge Networking

Introduction

This is a compilation of ideas for a project on local knowledge networking. It is related to the recent Peer to Peer phenomenon, but attempts to distill out a more formal framework for understanding such systems.

What is Local Knowledge Networking?

Local Knowledge Networks establish computing sessions without central control, with no fragile global state, thus are more adaptive during failure and are more robust. They propagate requests via alternative techniques such as rings of neighbors. Study of these systems has yet been sparse. Sun has started a core effort in this area, Jxta, and has developed an earlier digital collection library system, LOCKSS. Sun's recent acquisitions of Grid, Cobalt and InfraSearch are potential components of local knowledge fabrics.

Project Goal:

Create tools for analyzing Local Knowledge Networks by building a prototype "Peer" system, using existing components being developed within Sun, while in parallel building concrete, Java based, multi-agent models for investigating system properties such as scaling, session management and local trust models.

Interest to Sun:

Our industry is fundamentally changing:

Server Hardware: Clayton Christensen (Innovator's Dilemma) is right: technologies and their companies do reinvent themselves. In Sun's case, the large server world is being challenged by lighter weight, more agile small systems such as Cobalt, a recent acquisition.
Hardware Clusters: These small systems are being clustered into loose knit computing fabrics by software like Gridware, another recent Sun acquisition.
Server Software: A similar reinvention is occurring in the enterprise software running on large servers. These are being broken into more autonomous agent services, such as LOCKSS, a Sun/Stanford collaboration.
Client Software: The client too is being similarly reinvented as "peers", launching the current P2P phenomenon. Sun recently acquired the InfraSearch peer system, and sponsored the O'Reilly P2P conference.

As is our network:

The Broken Network: The network is the computer. And it's broken! It is in Sun's interest to move from the Web's Hub/Spoke network, with little inter connectivity outside of clients to servers, to a strongly interconnected, combinatorial, "network effect" internet.
The Mending Network: The network is not only broken, it is mending. P2P systems are routing around today's weaknesses. Thus the network future is very likely to be a hybrid of "good networking" (Multicast, IPSec, IPv6, DynamicDNS, ...) with messy Peer networking.

But we are starting to understand the basics:

Big is Different: Big isn't only large, its different. The current network is surprisingly poorly understood. Recent "Net Cartography" work has helped improve our understanding. Similarly, recent findings in Small Worlds and Dynamic Graph analysis has proven that as complex as these network are, they have surprising useful and simple emergent behavior such as "small diameters", "power-law link distributions", and "local clustering".
Super Peers: Recent theoretical work by the P2P community, such as Clip2, has considerably improved poor scaling artifacts by introducing "super peers", nodes which seek to reduce the network's randomness by using results of simulation and measurement.
Jxta: The Jxta project is interested in early theoretical analysis and simulation and sees it as a logical synergy between Jxta and SunLabs.

This project brings fundamental understanding to these changes by using Java based multi-agent modeling tools to simulate these systems and their networking, and by building a prototype peer system based on these simulations.

Problems to overcome:

Web vs. Internet: The explosion of the web has distorted the establishment of the internet as envisioned by its architects. Thus end to end transparency has diminished, and the hoped for "network effect" offered by full inter connectivity has not been realized. Instead a "hub and spoke" clustering has vastly diminished the potential of the internet.
Broken Net: Thus many important internet technologies have been left behind or misused in the rush to establish "The Web". Examples:

DHCP has become the norm. This is fine, but has left the edge of the network "nameless" due to the lack of an associated DynamicDNS which would quickly bind a DHCP address to a long lived DNS name.
Multicast, which is a key component in autonomous session management via connecting to "channels" rather than machines, has not been widely deployed. It is not required for most web applications and is typically left off as default on ISP routers and systems.
NAT, network address translation, has become the popular way to service several address within a home, rather than having the ISPs provide home subnets. This causes few problems for clients, but renders contacting the home system as a service very difficult, if not impossible.
IPSec and other global network security methods have not flourished due to https being "good enough" for client/server needs. This has left client-client authentication and authorization in a vacuum. [One possible exception: ssh]

Mending Net: There has arisen a host of "Peer to Peer" applications to adjust to these difficulties. Their approach is to "route around" the difficulties by providing alternatives to the Web Centric network. Early analysis shows these systems weak in terms of scaling, search path length and security, but add-on infrastructure components such as Clip2's reflector/SuperPeer have evolved to manage these weaknesses.

Key questions to answer:

This project focuses on these core questions:

Local Knowledge Feasible? Is it possible to establish peer node sessions via purely "local" interactions without the aid of centralized services?
If So, How? If so, how manage the local systems via "advertisements" and "requests" to achieve Small Worlds effects? I.e. will a sparse set of peers connected in PeerCasting (mix of unicast and multicast) neighbor rings produce "6 degree's of separation" effects using only bare node properties such as the node user set's geographic location, name, occupations, ages, interests and so on.
If Not, How Fix? If not, how do we incrementally add centralized services which remain robust under failure and network reconfiguration, and which then in turn re-enable local knowledge systems.
Peer Dynamics? How large a web of neighbors is required to establish full connectivity among (required) peers in such a PeerCasting environment? Include random failures and nodes going on/off line, possibly using local time criteria.
Scale? How does such a system scale? What parameters affect the scaling? (I.e. can power laws emerge rather than exponential scaling?)
Visualize? How do we visualize such a system? Large networks are often unwieldy and difficult to conceptualize.
Model? How do we model the algorithms and methodology of such a system before trying to build it?

Project Approach:

The project has three components:

Jxta: Become an early user of Jxta for infrastructure so as to not to have to re-invent the basic infrastructure.
Prototype: Define a very simple application of the system which is based on local knowledge networking.
Simulate: Model this via the RePast agent modeling system. (The key systems today are Swarm, RePast and Ascape.) Compare w/ more traditional network simulation systems if resources available.

This is designed to easily fit within a broader Peer theme or project as its theoretical component.

Deliverables and Time Line:

Deliverables:

Critique/experiences paper/talk on early use Jxta.
Prototype application using Jxta framework
Two Java RePast models based on application, studying

Scaling
Search path.

Extra Credit:

Reuse of the two model's Java agent algorithms in running application
Move onto Trust/Reputation implementation and model
Transfer one or more components into the Jxta core

Time line: I'd like to scope the effort to be modest; 9-12 months to the first three deliverables. This will allow easy redirection of the project toward more ambitious goals if the initial findings prove hopeful.

Motivation, History and Status:

P2P: Although the recent P2P activities, such as the Feb '01 OReilly conference, present opportunities in this space, they lack a formal framework such as I am proposing. [Interesting to note: several of the current set of applications have begun including theoretical modeling. FreeNet, for example, has become a fairly sophisticated university research project with one considerably mature network theorist]
Theory: In addition, I see many recent findings in the Complex Adaptive Systems community offering more direct help. Examples include

The Small Worlds work of Watts/Strogatz.
Network evolution work of Barabasi, Albert, and Jeong
Link discovery of communities work by Kleinberg
Modeling systems such as Swarm, RePast, Ascape.

SFI BusNet: Thus I've started preliminary work with Santa Fe Institute's Business Network, of which Sun is a member, in this area, including:

Attended Complex System Summer School 2000
Formed the SFI BusNet BOF for Complexity in computing and networking.
Co-chair of BusNet panel, March 2001 including Dave Rosenthal presenting LOCKSS
Have been accepted to the SFI Workshop "The Internet as a Complex Adaptive System"

Jxta: On the Jxta front, have been given the Jxta P2P Platform Specification, version 0.98 and have visited four times with Jxta managers and engineers. [Li Gong, Bill Yeager, Juan Soto]
RePast: Recently I've begun Java model implementation using RePast. Initial findings is that such a system offers promise and is mature and performant enough for use in this area. Visualization of massive network difficult, but preliminary "offset link" idea promising.

Project Details Thus Far:

Small Worlds: I started out by performing literature searches after attending the SFI Summer School to look into how independent agent systems might be important to our computing and networking technologies. One of the key ideas I found is the Small Worlds findings of Watts and Strogatz. They investigated why the famous "6 degrees of separation" effect might occur. Their findings were very revealing: a small amount of randomization of a network produces a smaller "diameter" for the graph.

Clustering vs Diameter: They then applied agent modeling systems to look at the statistics of these small worlds graphs. By adjusting the randomness from low to high, they were able to see rapid evolution of a small diameter (potentially short P2P paths), while still preserving natural local clustering.

Agent Modeling: I also found that, over the last decade, the use of multi-agent computer modeling systems has progressed considerably. Initial Connection Machine (Star Logo) work evolved into the current mature systems (Swarm, RePast, Ascape, StarLogo) .. all of which are either entirely written in Java or in Swarm's case, provide a Java interface. It is now common for researchers to include model results with their network analysis papers; as do Watts/Strogats above.
Initial RePast model: To judge the usability of these multi-agent modeling systems, I built an initial RePast model to look at performance, adaptability, programmability, maturity. The model has a rectangular array of nodes, coupled by network links. The dynamics of the system is random time to live for links and random neighborhood size.

click for large view

Visualization of Large Models: Although the initial usage was promising, one problem proved difficult. The large (order 1000) networks could easily have many nodes (order 2-3 thousand) which were impossible to disambiguate due to overlapping. This was solved using a link displacement technique:

Mentors and Friends: A small group of three of us have begun meeting for a Friday Complexity Lunch (Randy Smith, Helen Cunningham and myself). These meeting have been absolutely invaluable, providing insights and references galore, as well as badly needed math pointers. Similarly, a growing number of researchers interested in P2P topics have banded together to discuss further work on the sunlabs-themes-p2p list. Hopefully this project will fit within that wider theme. Finally, meetings with Dave Rosenthal to discuss the LOCKSS system and associated challenges formed the initial spark for the project.

Issues/Risks:

Peer Modeling: Can a Peer system be effectively modeled?
Size: Is the net too massive for meaningful use of these techniques?
Local Knowledge: Are local knowledge systems realistic?
Fixable: If not, can they be fixed.
Jxta: is it the right platform? Are there fallbacks?
Multicast: currently not widely deployed but if it were, would the project remain valid?
Agent vs Network: Use of agent modeling rather than more traditional network tools.
Singleton: One person project may lack critical mass.
Math: Although I love the stuff, I'm not a mathematician.

Related Work:

This project is a bridge between two worlds: the newly emerging P2P systems development, and the theoretical work being done in complex systems and in grid/network analysis.

Within Sun, there are several projects working on Local Knowledge Systems:

LOCKSS: David Rosenthal's Lots Of Copies Keeps Stuff Safe library collection collaboration with Stanford uses peer servers to insure integrity of the system while providing local caches for optimal client access.
Jxta: A light-weight infrastructure effort for peer implementations.
GridWare: The Sun Grid Engine software finds a pool of idle resources creating a computing fabric.
Cobalt: A network server appliance which is ideal for highly distributed, low cost computing.
InfraSearch: A novel search platform based on Gnutella's file system.
Brazil: A highly modular network and web toolkit easily adaptable to local, peer systems.

Theory work of interest includes:

Network Cartography: The CAIDA group's KJ Claffy and others have provided profound understanding of the internet via extreme detail mapping and analysis tools, most in Java for wide deployability.
Small Worlds: Several research projects are looking at the area of very large graphs with small diameter and local clustering. These produce the "6 Degrees of Separation" effects where any two individuals on the planet are connected by no more than 5 intermediates.
Dynamic Networks: Initial Small Worlds work considered static networks with randomization. More recent work considers the actual formation of the network, starting with a few nodes which then grow links probabilistically to nodes depending how many links those nodes already have. This has produced results more in agreement with the large networks being studied: Web, Movie Stars, Power Grid, and Citations. (I.e. power law distribution of links rather than exponential)
Link Analysis: Google's initial work for searching weighted results on in-link popularity rather than on pure lexical or metadata content. Ongoing work shows node clustering among systems building important network features including Cliques, Authorities, and Hubs.
Complex Adaptive Systems: From 50,000 feet, all local knowledge systems are aggregations of parts of a larger whole. If the interactions between the parts are "interesting", emergent behaviors greater than the sum of the parts emerge. This is called "complexity" and is becoming a broad, cross discipline study.

Industry efforts include:

Napster, Gnutella, Freenet: These are the three big initial efforts, primarily built for file sharing. Napster is the only one using a central control element, the Napster Server, which has rendered it vulnerable to political attack. Gnutella decentralizes at the cost of potentially poor performance, but is none the less very successful and effective. Freenet is migrating from autonomous network file system to almost an infrastructure of its own right, receiving considerable university attention in the UK.
Beyond File Sharing: Application areas beyond file sharing are emerging in the P2P world:

Writable Web: Self organizing web communities attempting to make creating and managing web content as easy as reading it!
Computer Sharing: Seti@Home and others are looking into how loosely couple computers.
Computing Grids: Gridware and others are building more tightly integrated computer sharing.

Peertal: Countless other peer systems are being developed. The Peertal site keeps a long list of projects they have validated as being "real" from their standpoint. The list today (2/7/01) stands at 113 companies.
Infrastructure: A new breed of peer is being developed to add back in the benefits of central control but without single points of failure. Clip2 is an example which improves Gnutella (and others) by performing theoretical analysis and large scale measurements to infer how the system can be improved by introducing smart SuperPeers into the system.
Enterprise: Another breed of peer is looking at reducing enterprise administration and configuration complexity by personalizing/peerifying enterprise networks and business processes.