Update Time info

Suman requested that I look at the update time closer, here's a graph of the amount of time the update calculation took versus when during the trace the update was run. This is a normal file with no delay added to the calculation.

There seem to be a couple spikes during the trace where the calculation takes about 5.5 seconds, these occur mostly in the warm up period and then infrequently afterwards. Only 58 of the roughly 2400 of the calculation taking longer than 1 second to compute.

The warmup period in this trace takes approximately 1,900 seconds.

Results with another trace

I ran the simulation on another trace file with delays added to simulate slower processors. I did basically the same tests as before, the main difference with this run was I used slightly more varied delays with a trace of a large delay of 1 second. Here are the results:

Hit Ratio
This is the delay from each period, as you can see again, most of them are fairly close together towards the end. The exception being the trace file with 1 second delay, this one did considerably worse for a hit ratio than the others. Also we see again the areas where the hit ratio drops drastically in the traces with no delay and the trace with 10ms delay. I think these must be areas with a lot of packets that don't fit the rules in the cache and therefore generate a cache miss.

Cumulative Hit RatioAgain the results are fairly similar compared to the other trace. Two interesting things here, the 10ms delay simulation performed better than the simulation with no delay. The other thing to notice is the 1 second delay simulation is again much lower than the rest of the traces.

Update Time
Here we see why the simulation with 1 second delay performed worse than the rest of the simulations. It looks like the delay was large enough that it made the calculation of the new ruleset much more difficult, the update delay doesn't even get below 3 seconds in this case.

update

I'm running a similar test as in the previous post with another trace file to compare the results. The simulations take a while to run but I should have enough traces by the end of the week.

Hit Ratio vs Cache Update Time

I ran the simulator with a tracefile and added delay to the rule cache update method to simulate this running on a slower system, I used the trace5a trace file and ran 5 different simulations: no update delay, 1 millisecond update delay, 30 millisecond delay, 60 millisecond delay, and 100 millisecond delay.

The results are as follows:

Hit Ratio
The hit ratios for each individual update period varied during the start but they all converged to around 98% towards the end. I'm not quite sure about the spikes downward in the hit ratio graph, there were likely just periods where there were a lot of cache misses in this trace. This could be verified by looking at the results of another trace file.

Cumulative Hit Ratio

The overall averaged hit ratio was better with less delay but this could likely be due to the variation between the hit ratios in the start of the simulation.


Update TimesHere is just a graph of the average update time for the different simulations, there doesn't seem to be as distinct between the time delays as I would have liked to see but there seems to be a general distinction between the no delay simulation, the mild delay simulations, and the 100 millisecond delay simulations. I am not sure why the other ones are so close but it might have to do with the rules being calculated over different packet intervals.

Overall it seems that the update time most effects the hit ratio while the cache starts up and the averaged hit ratio but the hit ratio for individual periods seems to be fairly consistent with delay.

Traces

I'm running some traces on the simulator with different delay values and once they finish I will be able to graph the output and we should see what the correlation is between the cache update time and the hit ratio.

New code version

I talked with Dheeraj and he said that in the new version of the rule cache code that he sent to David would take care of the timing issue that we were seeing before. He also mentioned that this new version didn't use the large trace files so it will not have to do file I/O and should run faster in the rule cache update.

I am going to run the simulation a couple times and put a delay in the update rule cache method to see how the hit ratio differs with different delays in the calculation of the new rule set.

Change the code?

From a brief meeting with Suman today, we might have to make a slight change in the code to account for the problem I mentioned in the previous post as far as the hit ratio not being effected by the cache update time.

I took a look at the code for the rule cache simulator. I think the change will have to be with how the simulator determines when the next cache update will occur. I am meeting with Dheeraj later this week and I will ask him about this.

I found some code that Dheeraj had commented out that looks like it will do what we want for the change in the code, I'm going to uncomment it and give it a try to see if this solves the problem.

changing cache update time

I tried having the simulation program sleep for 10 milliseconds (this would have about doubled the average cache update time) and I ran one of the traces through that I had done previously.

I compared the hit ratios and they were exactly the same which means that simply using the sleep function did not work as I wanted due to the way the simulation program simulates the flows. Basically when the program is sleeping, no packets are being processed so they just wait until the program wakes up and are handled then so the hit ratio is not effected at all by that approach.

I am going to need to look into other ways of simulating the program running on different speed processors.

The next steps

The next step in the project is to determine how the hit ratio changes based on the processor/memory that the program is being run on. We want to simulate this by changing the time that the cache management update takes to compute, more time representing a slower processor.

I am currently going through the code to try to determine the best way to increase the computation time of the rule cache update. I am trying to determine if something like a sleep function would give the desired results.

I am going to try to meet with Dheeraj to go over some changes that were made to the code.

Hit Ratios

Today I took a look at the hit ratio. The trace files are the same ones as the previous graphs that showed the cache update delay so you can see how the hit ratio corresponds to that.

I first graphed the Hit ratio of one of the traces (trace3a) as you can see here:
This is the hit ratio as it is calculated over each beacon interval (the Trace Time on the x-axis). As you can see this varies quite a bit from one interval to another. I then decided that it may be more helpful to look at the average hit ratio, or cumulative hit ratio as it says in the output of the program.

I graphed this for the three traces from the cache update time from before, the results are here:

The cumulative hit ratio seems to start out high in the warm up period and then settle around a certain percent. The ending cumulative hit ratios from the trace were 97.69% for trace3a, 97.97% for trace5a, and 97.89% for trace6a.

sampling factor

I compared the traces I ran with sampling factors of 1, 1024, and 2048 and all other parameters the same, the results were very similar. The traces with 1024 and 2048 sampling intervals both had the average update time of approximately 8.5 milliseconds. The trace with a sampling factor of 1 was just slightly better for time to calculate the update with just under 8 milliseconds.

It appears that the sampling factor size does not greatly effect the calculation of the new rule set.

Cache Update Times

I ran the simulation with three different trace files of actual traffic. All of the trace files give similar times to update the rule cache, the time starts out fairly high, around half a second and then quickly decreases to a couple milliseconds and the average seemed to stabilize between 8 and 9 milliseconds. This is the overall average of the time to calculate the new ruleset.

The traces were run with cache size of 10, window size of 1024, and a sampling interval of 1024. You can see the values for the cache update time in the graph below:

I am running one of the traces again with a sampling factor of 1 to compare the results to these traces.

update

I figured out that I was giving the simulator program on baleen a bad trace file, I have been able to run the simulator with a trace now. The problem is this takes quite a while to run, I'm going to start the program running on a trace file and let it go for a while and record the output to get the average cache update delay.

Once the simulation is done running I can graph the update delay or other various statistics like the filetrace in the previous post. I should have some results in the next post.

work summary

I tried to run the rulecache simulation on the baleen machine to get the timing with the actual traffic traces. I was unable to do so because the program would seg fault and crash.

I did discover that in the newer version of the files on baleen already calculate the average time to update the rule cache and print this value out with the other statistics.

I found some filetraces of the program that were on baleen. I took a look at the filetrace_5dims-0updatetime.out trace file. This runs the simulation with the RHL size varrying between 16 and 23. I graphed the average time to update the rule cache as the simulation was running and here are the results:As you can see the average update time starts out high and then goes down to a couple milliseconds as the simulation runs. The last average update time was 8.99 milliseconds.

I took a look at some of the other filetraces on baleen, some of them start with RHL size of 1, this had a significantly higher update time, around 2-3 seconds.

If I can't get the program to run I will next take a look at the correlation between the RHL size and the time to update the cache in the other traces.

updated timing results

The previous entry was timing over the whole window size in the simulation, we want to see how long it takes to perform the rule cache update one time, so here are some preliminary results for how long it takes per packet.
The graph is percentage of packets (Y axis) versus time to compute new the new rule set (in microseconds) on the X axis. As you can see a majority of the calculations took 2 microseconds. The average time over the packets is 2.4 microseconds. This was done on my machine (3.4Ghz P4 with HT and 1 GB Ram) using the test trace file.

I am working on getting the timing data using one of the actual trace files, those results should be up within the next few days.

Cache Management Timing

I think I managed to get the correct timing for the rule cache management delay. From the test flow record that I have, the delay seems to be between 3 ms to 7 ms running on my home computer (3.4Ghz P4 HT with 1GB RAM).

The next step is now to test this on other machines and compare the results.

Cache management timing

Meet with Dheeraj this afternoon to go over the code, he helped me identify where the cache management component was running.

Working on getting timing information for this. Hopefully will have something for the presentation tomorrow (10/31).

update

I was able to get the program to output the current time while it is running, this has granularity down to the microsecond so it should be precise enough for what we want to do.

Now I need to determine which part of the program is the cache manager and put some statements around it and see how long it takes to run.

Project Summary and Status Oct 11th

Project: Smart Rule Cache
Working with Suman and Dheeraj

Objective: Create a classification system using a small amount of specialized hardware (to reduce cost) while maintaining line speed classification of packets similar to the hardware based solutions. This is accomplished by caching the rules used for classification in unique ways using a cache manager.

Status:
Received cache manager program from Dheeraj, need to investigate the time it takes for this to run. The hardware component will be classifying packets, there is an amount of time between when the cache manager is done collecting samples to when it creates the new set of rules and updates the cache. We want to see what effect this time will have on the hit rate since the packets that go through during this time are classified with the old rules.

Project writeup due 10/12

First Post

Blog site is created, looking at ways to get it hosted from the CS pages site, pages.cs.wisc.edu, but this will work for now.