Bruce Zenel from Columbia University outlined some issues they have encountered in implementing general purpose proxies for mobile computing environment and how they deal with those issues.

Syam Gadde from Duke University presented a distributed Internet object cache model called CRISP which consists of cooperating caching servers and a centralized mapping server and reported some early studies of CRISP caches.

Tzi-cker Chiueh from State University of New York at Stony Brook presented the architecture of Artery, a distributed system specifically designed to support network game development. Some techniques for reducing network backswith are explained in detail.

Extended Discussion

The first speaker was Paul Leach from Microsoft. The title of his talk is "Query Routing: Applying Systems Thinking to Internet Search".

Paul started by pointing out that with the exponential growing rate of the Internet, we need a scalable way of search the contents provided by the Internet. Traditional ways of handling scalability use hierarchy and hints. The example Paul gave are traditional name servers such as DNS. The problem with these systems, however, is that you can search on only one attribute. On the other hand, Paul observed that the reason these systems are scalable is because it has the compression property, namely, index information gets compressed as it goes up the tree from children to the parent node. Paul pointed out that this compression property is essential for scalability.

Paul then gave the architecture of the query routing approach. The architecture is a hierarchical tree, with base servers at the leaves that answer queries, and index servers at the internal nodes that redirect queries to base servers or other index servers that have a "better" idea of which index servers or base servers can answer the query. To achieve scalability, the index information (forward knowledge) must posses the compression property. There are three such indexes: centroids, attributes with hierarchical structures and types. Centroids are essentially unions of the database records. The parent in the indexing tree gets the union of the child's centroids. There are cases where this might not scale, resulting in the root index node flooded with all the indexing information. Paul said they haven't started looking at real databases. But he argued that since there are only 4.3 billion people, we can afford to have the root node containing a few bytes for every single people that tells where to go to look for more details. However, he said they couldn't make the same claim about documents.

Finally, Paul summarized their approach: (1)It generalized the DNS technology to multiple searchable attributes. (2)It identified three scalable types of index information. (3)It identified the requirement for index scalability - the compression property. (4)It used hint and hierarchy to achieve scalability.

Discussion:

• Franz Kaashoek (MIT) questioned about the status of the system. Paul said he has implemented a prototype. Although the database itself doesn't scale, the prototype does generate centroids for multiple levels and propagate scheme information.

• Fred Douglis (AT&T Labs) asked about queries on documentations. Paul answered that the same compression property exists for documentation queries. If the query searches for all documents that contains A near B, we change that to A and B. The idea is to prune search as much as possible.

• Sape Mullender (University of Twente) asked what are the prospects for automatically generated indexes. Paul said that they can automatically generate centroids from actual data. But to preserve the integrity of the index databases, the hierarchical indexes can't be generated automatically.

The next speaker was Bruce Zenel from Columbia University. The title of his talk is "General Purpose proxies: solved and unsolved problems". This is basically an experience paper that describes the issues Bruce and his colleagues have encountered in implementing general purpose proxies for mobile computing environment and how they deal with those issues.

Bruce started by showing a picture of the computing environment that the proxies operate on. It consists of a group of "mobile hosts" communicating with "fixed hosts" via a "proxy". The purpose of the proxy is to process information flowing from the servers (fixed hosts) to mobile hosts to improve quality of service. Types of processing include compression, removal of parts of the data, store-forward data, and replacement of protocols. The reason the proxy is called general purpose proxy is because it is a general execution environment where one can download code that filters protocols such as HTTP, NFS, TCP and MPEG.

Bruce then described eight issues that they went into in implementation of the general purpose proxies. The first issue is routing. Basically they had to build a new routing protocol to guarantee that the proxy is in the data path between the server and the client. The second issue is connection semantics. They used the technique of socket migration (from the client to the proxy) to achieve user transparency. The third issue is TCP end-to-end semantics, which they didn't deal with because of its complexity. The forth issue is adaptation. To achieve that, two types of controls are applied to the proxy. Internal control directly controls the mobile application. External control takes environment information from the network around the mobile host and feeds the information into the filter, allowing it to make decisions on how to process the data. The fifth issue is security. They developed a two-party authentication system as well as an encryption layer on top of the authentication layer. The sixth issue is proxy location. The routing protocol allows variable placement of the proxy. However, once the proxy is placed, its location is fixed. This relates to the seventh issue: proxy mobility. They didn't allow proxy to move after being placed because proxy is a large process and proxy mobility will bring up many issues related to process migration, which they decided to push off for future work. The last issue is adaptation in terms of application vs protocol. There are basically two approaches: adapting network protocols and adapt the applications. They decided to go with the protocol approach because there are many applications but few protocols. As a result, each protocol filter will have more of an impact than a singular rewritten application.

Discussion:

• Jay Lepreau (University of Utah) pointed out that Bruce was unduly pessimistic about the results in end-to-end semantics. Bruce didn't agree and said that there is lesser guarantee that the data is going to make to the application. The data is only at the proxy when you get the acknowledgement.

• John Carter (University of Utah) asked about disconnected operation. Bruce said they were only interested in systems that are at least partially connected and didn't look at disconnected systems at all.

• Alan Nemeth (Digital Equipment Corp.) and Brett Fleisch (University of California, Riverside) raised the issue of failure management. Bruce responded that failure is a difficult problem and they haven't done that yet.

The next speaker was Syam Gadde (picture below) from Duke University. The title of his talk is "Reduce, Reuse, Recycle: An Approach to Building Large Internet Caches".

He started with the motivation of his work: the increasing Internet usage and the need to develop new techniques to reduce traffic on Internet. Several studies have shown that cache shared among many users can achieve 50% or greater hit ratios. And more sharing could be achieved with more users. So their goal is to design a caching architecture that scales to a large number of users and is easily extensible to accommodate the growth of the number of users.

Syam proceeded to present their new caching architecture, CRISP, which stands for Caching & Replication for Internet Service Performance. CRISP consists of two types of nodes: caching servers that cache objects on behalf of the clients and handle requests, and mapping servers that maintain an index for the whole cooperative cache. As requests miss in caching servers, this generates a query to the mapping service, which either returns a miss at which point the caching server goes to the Internet or returns a re-aim that tells it which proxy to forward the request to.

Syam then claimed that the mapping service is not a bottleneck because CPU usage is very low - only on the order of a cache lookup for every query. I/O is negligible because they assume that the map fits in physical memory. Furthermore, each message includes either a URL or an IP address. As a result, network requirement is also low. Syam added that if it turns out that the mapping server is saturated, one can use multiple mapping servers and partition URL spaces among them. The answer to the centralized point of failure argument is that failure of the mapping service only degraded performance, it doesn't compromise correctness.

Next Syam pointed out three advantages of using a centralized mapping service. First, the mapping service could add to the representativeness for the cooperative caching. Second, it could coordinate global replacement strategies. And finally, the mapping service makes it simple to increase the cache capacity.

Then Syam showed some performance number of the CRISP mapping server and comparison of CRISP to Harvest. In conclusion, performance of CRISP is a little better than that of Harvest for 2,3 and 4 nodes cases.

In summary, Syam said that CRISP could provide scalable cache consistency as well as making it extensible to larger number of users. It could be a powerful tool to implement global replacement policies if that turns out to be a nice thing.

Discussion:

• John Howell (Dartmouth College) asked if the cost of storing all the index information on the mapping node is low, then why won't you replicate the mapping service to all nodes. Syam said keeping consistency between different maps is not simple. Michael Rabinovich (AT&T Labs) added that mapping service and cache service may interfere with each other and broadcast to all nodes would be bad.

The last speaker was Tzi-cker Chiueh from State University of New York at Stony Brook. The title of his talk was "Distributed Systems Support for Networked Games".

Tzi-cker started by describing the generic model for network games. Basically a virtual state is shared among nodes distributed over the network. When the human participants do something, these update-events are exchanged among the nodes to maintain the consistency of the shared state. He pointed out that there is nothing special about the model compared to a distributed shared virtual memory system.

As far as the communication aspect of network game development is concerned, there are two fundamental challenges. The first is to provide a high-level API that hides all network transport details. The other issue is scalability. The system should work on more than 10,000 nodes. The solution they propose is a middle-ware specifically designed to support network-based multi-user interaction systems. Tzi-cker then pointed out the shortcomings of the earliest work in this area, Distributed Interactive Simulation Protocol(DISP). Early versions of DISP requires full replication and strong consistency. There's no support for environment objects. Also, later generations of DISP model apply ad hoc optimizations which should be generalized.

The proposed model, Artery Distributed Systems, provides a shared memory programming model that frees the application programmers from dealing with communication. The model exploits application-specific semantics to maximize network bandwidth efficiency. Finally, It allows programmers to share common code. Tzi-cker then showed the system architecture of the model. Underneath is the DISP protocol. Each node consists of a simulation process where you specify what you should do when something happens and an artery networking module which provides shared memory abstraction to simulation process. In addition, there is an environment state server that keeps objects under control of any of the participants.

Tzi-cker proceeded to describe in detail the techniques incorporated in Artery and emphasized that none of these ideas is new. The first idea is "dead reckoning". Studies have shown that most network traffic is due to position updates. The basic idea is to predict the position change of the simulated entity and suppress the update message if the difference between the actual position and the predicted one is within certain threshold. The second idea is Dynamic Group Consistency Model(DGCM). The idea is to decompose the virtual world into regions and only maintain consistency within the region. The last idea is to reduce per packet overhead by aggregating multiple small packets into one big packet.

Discussions:

• John Chapin (MIT) asked if the multicast protocols are set up to allow extremely fast group changes. Tzi-cker said this is an interesting issue posted by this architecture but they haven't dealt with it.

• John Carter (University of Utah) raised the issue of time skew over Internet. Tzi-cker said they were trying to work on it.

• Brett Fleisch (University of California, Riverside) asked if we could exploit DSM techniques to replace the multicast groups. For example, the virtual memory can be split into segments, each region is a segment. Tzi-cker said it's more or less the same thing.

• Freeman Rawson III (IBM) asked how to control the latency to get real-time. Tzi-cker responded that if you're really serious about this type of DOD simulation, you probably want to use real-time protocols.

• Gary Nutt (University of Colorado) asked how do you know where the object is in which region. Tzi-cker said this is done by sending a register message to the environment state server (each region has an environment object server) every time you enter a region.

Panel Discussion:

• Freeman Rawson III (IBM) what systems and structures do we need to make failures attractable on the Internet. Someone answered that there there are some research projects that deal with this issue. For instance Margo Selzer did a paper in HotOS on geographic push caching. Bob Frankston (Microsoft) expressed the concern that most active pages are least cacheable because they change the fastest. Margo Selzer (Harvard University) disagreed and said their tracing analysis indicate the increase in the percentage of active traffic. A secondary issue is that people are more interested in hit counts and who is accessing the data. she believed that the commercial force will such that better accounting is necessary in order to make caching palatable. Paul Leach (Microsoft) commented that Jeff and himself are proposing an Internet draft on caching information such as how many times something is accessed and send that to the server in demand.

• David Black (Open Group Research Institute) noticed that people seem to treat the Internet as a large distributed read-only system and asked what kind of infrastructure we need to make the Internet read/write. Pei Cao (University of Wisconsin-Madison) responded that the first issue we need to address is cache consistency. The current approach is weakly consistent. She proposed the invalidation based protocols that provides strong consistency and their data demonstrated that it is no more expensive than the current approaches. Margo Selzer (Harvard University) raised the concern that invalidation protocols break down when network partitions. Lease based approach is better in dealing with failures.

• Noah Mendelsohn (Lotus Development) noticed that people who drive a lot of the web technologies are changing the structures, for example, new technologies such as java ,dynamic html, active X lead the Internet to a more distributed computing environment. Noah was concerned about whether we are at risk by still basing our studies in old traces. Paul Leach (Microsoft) said that one needs to identify the invariants and base the architecture on those factors that will likely remain the same.

• Frans Kaashoek (MIT) asked what kinds of applications are driving the Internet into a truly distributed systems. Tzi-cker pointed out that the Internet Service Provider (ISP) will provide a lot of computation services such as compression. John Chapin (MIT) suggested David Gelernter's book "Mirror Worlds" which is essentially a distributed system.

• Mary Baker (Stanford) pointed out that updates to web is different from the traditional small-scale distributed file system. We need to understand the web updates style Before we decide which protocol is the most efficient.

• Freeman Rawson III (IBM) raised the concern about time-constrained applications such as electronic commerce and pages that are both heavily read and frequently updated such as stock information. How does it compare to distributed file system. Jeff pointed out that for really high speed applications, you can build private networks that provides real-time guarantees. One needs to integrate lower-level QoS provided by the network with the web level QoS. HTTP currently doesn't support QoS abstraction. Alan Nemeth (Digital Equipment Corp.) added that simultaneous delivery can be more important than real-time to financial people.

• David Black (Open Group Research Institute) said that the file system discussion has distracted him because it seems that people are trying to turn the Internet into a well-behaved LAN. But the Internet fundamentally will not do that.

• David Presotto (Bell Labs) asked Paul how can you keep the system from killing the root since caching is more difficult for the index databases. Paul said they haven't worked on the cache issue. But their system does less work at the root than current systems that do everything at root. Therefore they're making the system incrementally better.