dasebe / optimalwebcaching Goto Github PK

PFOO-U is painfully slow on traces above 50 million requests. Technically, it should be a linear-time algorithm and should outperform PFOO-L. But PFOO-L is orders of magnitude faster in practice, due to its simplicity. In addition, PFOO-U is single threaded and memory bound.

Some parts of the code are reused from boost.

I tried PFOO-U with a short test trace and discovered what appears to be an impossible solution. My trace was

1 1 10
2 1 10
3 2 10
4 1 10
5 2 10
6 2 10
7 2 10
8 1 10

ran with cache size = 11 and max-valued step size, and my solution from PFOO (using OHRGoal/PFOO-U/pfoou) was

// output from PFOO-U
// ID, Size, Utility, decision_var, is_hit

1 10 0.1    1    0
1 10 0.05   1    1
2 10 0.05   0.1  0
1 10 0.025  1    1    **
2 10 0.1    1    0.1  **
2 10 0.1    1    1
2 10 0      0    1
1 10 0      0    1

I've highlighted the two rows that I believe yield an impossible solution as caching both objects entirely would exceed the cache size. The regular FOO-U (OHRgoal/FOO/foo) implementation seems to yield the correct integer hit rate of 4/8

// output from FOO
// Time, ID, Size, decision_var

1 1 10 1
2 1 10 0.1
3 2 10 1
4 1 10 0.1
5 2 10 1
6 2 10 1
7 2 10 0
8 1 10 0

As a result of this the miss rate from PFOO-U (3/8) is less than the miss rate from FOO-U (4/8) on this trace which seems like it violates the claim from the paper that PFOO-L ≤ FOO-L ≤ OPT ≤ FOO-U ≤ PFOO-U

Hello. Previously, we closely followed your work on "LFO: Towards Lightweight and Robust Machine Learning for CDN Caching" [HotNets'18]. We conducted some tests based on the dataset you provided ("We use a 2016 request trace from the CDN of an anonymous top-ten US website. Recorded on a San Francisco CDN server, the trace spans about a week (500 million requests).") for evaluation purposes.

Unfortunately, we noticed that the dataset is no longer available for download on your homepage (https://www.microsoft.com/en-us/research/people/daberg/data-and-software/). Moreover, the above link contains the trace in 2018 instead of 2016. As we aim to reproduce our algorithm's experimental results using your dataset, we were wondering if there are any alternative means to obtain this dataset. Many thanks!

Hi,

I want to get the decision from PFOO. But when I run the command like ./pfoou [trace name] [cachesize in bytes] [pivot rule] [step size] [output name], I can only obtain some numbers like fluid2 1.0000 4 12 0.3333 1.0833 4 in the output file. Is it supposed to see the binary cached decision for each request in the output file?

If this is not the correct way, can you provide some instruction how to obtain these binary decisions from PFOO? Thanks!