With the emergence of faster Web servers, faster modems and faster links, round-trip delays can dominate access latency for web traffic. We have invented a new technique called REFERENCE POINT CACHING, in which a server tells its client that it has cached pages referenced in a page the client just retrieved; this allows the client to retrieve the pages from its current connection, instead of creating a new connection to the referenced point. If the server does not have a cached copy, it sends the IP ADDRESS of the host in the URL, saving the client the need to do a DNS query. Reference point caching broadens the scope of HTTP caching to allow regional server caches specialized by topic, and allows search engines to return IP addresses along with the result of a query.
Our analyses based on web traces from Boston University show that 17.8 percent of user clicks on remote sites result in DNS lookups, and these can be avoided using REFERENCE POINT CACHING of IP ADDRESSES. Although the average DNS lookup time for a set of site names collected from the yahoo site was 835ms, many remote sites result in lookup times of the order of seconds. We are also collecting search traces from individual users, to show that the set of IP addresses followed during a search session are unlikely to be cached in the local DNS server since they are likely to be random.
Our simulated experiments using a set of Yahoo pages on travel resorts show that using a local server and reference point caching of pages, we could reduce the access latency by 72 percent. We are also setting up a local Newspaper server that will prefetch the newspapers registered by its users. Using this server, we intend to show the feasibility and usefulness of setting up regional servers. In order to build this server, we have written a web robot that periodically fetches series of pages from remote sites and a web compiler that selectively rewrites the references in the pages to refer to their local copy. We are also conducting experiments over a modem line to measure the benefits that home users will experience from these techniques.
This web system and associated ideas constitute roughly one half of Girish's thesis. A paper with these ideas (without the latest measurements) was submitted to SIGCOMM 98, but rejected (though it had favorable reviews) with the suggestion to add more extensive performance tests. Girish is currently working on additional measurements and completing the system.
The point of our research was to create an efficient network packet filter that is easily extensiable. Since work was done to show that context free grammars could be joined together quickly without hurting parsing proformance, we decided to experiment and see if grammars could be used for packet filtering. They of course can. The problem with using grammars for packet filtering is that they can not utilize predetermined knowledge of what they are parsing to improve preformance. For instance if you had a firewall grammar specification, and you knew that the first 128 bits were unimportant, a hand coded solution could skip these bits and parse only the bits after the first 128. A grammar based solution could not. At least until now.
We have developed a method for analyzing a grammar and determining what parts of that grammar are skipabable. A grammar is composed of production rules, a start symbol, non terminals and terminals. By determining which non terminals are skipable, we can determine which parts of the grammar we do not need to parse.
A non terminal is defined as skipable if the first k terminals that the non terminal derives are exactly equivilent to the cross product of the alphabet for k length. An example:
S --> A B
A --> 0
| 1
B --> 1
| 0
in this grammar A is determined as skipable since it derives all of the
alphabet. B is skipable also. to be precise A and B are 1 skipable. S
therefor, S is determined as 2 skipable, since it can derive all of the
strings of length 2 from the alphabet 0 and 1.
To determine the k that a non terminal is skipable by we used the classic first calculation. The problem with this calculation is that to determine first-1 sets we would need to calculate these sets, and then to determine the first 2 set we would need to calculate the first 1 set again and then the first 2 set, and so on.
We felt as though this was redundant (not to mention slow and costly), and so in order to achieve our ultimate goal we set off to develop an INCREMENTAL FIRST K calculation.
This is basicly the same as a standard first-k calculation, except now you save what has been computed as you recurse. for a given value of k it returns the first K of a non terminal, and it takes in the first K-1 for that non terminal.
Armed with an incremental first calculation we were able to determine what non terminals in a grammar were skipable, and by how much. We then proceeded to create an LR(1) parser, and when that was done we added a new action to the typical SHIFT, REDUCE, ACCEPT, ERROR parser which we called a SKIP action. Since we knew that a non terminal derived k terminals that could be skipped, we set up the parser to just end up in the state it would have of ended in if it had to SHIFT and REDUCE those values.
Once this was working we set out to Make a tomita parser that could handle non deterministic grammars. We did this because our ultimate goal was to create an efficient network packet filter, and the packet specifications could indeed be non deterministic.
We finaly added skipping to the Tomita parser in the same manner we added it to the LR(1) parser.
what we have now is a skipping tomita parser that can do a non deterministic parse of a specified grammar, and signal wether any, some or all the parses accepted.
What is left to be done (and what I am trying to currently do) is make only one pass over the input stream.
When our parser will be able to do this we will have a better network packet filter then what currently exists that runs faster, passes over the input only once, and is extensable quickly.
The goals of our research on TAO include the following:
The results of our ORB scalability and predictability experiments have appeared in RTAS '98, GLOBECOM '97, and IEEE Transactions on Computing.
Our research on ORB optimizations has focused on reducing the overhead incurred by TAO's protocol engine and ORB Core. The optimizations we've applied include optimizing for the common case; eliminating obvious waste; replacing general purpose methods with specialized, efficient ones; precomputing values, if possible; storing redundant state to speed up expensive operations; and passing information between layers; optimizing for the cache; minimizing dynamic memory allocation and data copying; reducing context switching and synchronization; and aligning the ORB concurrency and connection architecture with the features provided by the underlying OS.
The results of our real-time ORB optimizations have appeared in HICSS '98, OOPSLA '97, the Computer Communications journal, the ACM StandardView journal, and CACM.
Prepared by
Ron Cytron,
cytron@cs.wustl.edu
Prepared 9/98, Last Modified 9/98.