[SlugFiller]

Well, now that I've managed to get over the memory issues, and since I've given more than enough time for people to volunteer to help with this, with no response, it's time to restart the discussion about this subject.
I've thought hard on where to put this discussion, Development, Mods, Feature Requests, but I've realized that regardless of where I actually put it, it will most likely be moved here, so I might as well save some moderators the trouble.

Following is a thorough description of the feature and the algorithm. I try to explain all aspects as laymen-ly as possible. Try to follow through.

Endgame
The feature's aim is to ensure maximal download with respect to upload in a general(=no assumptions) network.
The idea is, that if download can be controlled using upload, and that upload is controlled by each client to maximize download, then clients that can upload more would be able to download more.
The system itself is designed so that it is controlled by other's upload. If uploaded to, it effects the system's preferences on who to upload to. This creates a form of chain-reaction that eventually leads to the uploaders controlling their own download.
However, the requiremeny of generality makes it so that even if others don't use the system, the most download that can be received from them through selective upload is achieved. In combination with the current CS, this could translate into shaping, but this is the fault of the current CS, not AR.

Advantages
A client's advantage is defined as a weighted sum of future downloads that can be achieved by uploading to that client now.
Note that a client's advantage changes over time.

We define the "state" of the network, as a combination of all of the factors in the network effect transfers, such as clients connected, currently ongoing transfers, corrent queues and status of the credit systems of all clients, downloading and shared files, etc etc, even including the users' state of mind, or even the current weather, since a lightning bolt could potentially cut a download.
Now, there are two factors which change the state of the network. First there's time, since the network is dynamic(as is the weather and the users' state of mind). Second, are uploads and downloads since they effect credit systems and hence effect the actions of clients connected to the network.

We can therefore, from a given state, choose between a selection of future states simply by choosing who to upload to. The issue then becomes, which upload would result in the most desired state?

To examine what is "desired" we first define the value of a future download. If a future download is of X bytes and starts T seconds into the future, than it's value is:

X*(gamma^T)

Where gamma is some constant that is smaller than one.
This means that the same amount of download would have more value if it comes sooner. A download coming in letter has an exponentially lower value. This makes sense, since we would prefer a download now, not in a century.
The reasons for the decrease being exponential rather than inverse-linear are mostly because it makes following equasions simpler.

Now, we define the advantage of a state. From any given state, the future downloads we receive depends on the uploads we make. If we make all the wrong uploads at all the wrong times, we might end up with no download at all. We therefore define the advantage as being the maximal sum of values of future downloads achieveable from the state.
Meaning, the state's advantage is the sum value of future downloads we would get if from that state we would continue to make our uploads optimally.

Now we can finally define the advantage of a client mathematically. The advantage of a client at a given point of time is the advantage of the state that would be reached after uploading to that client, plus the value of the download that would be achieved while making that upload.
Obviously, this means that the higher a client's advantage is, the more desireable it is to upload to that client, in order to get the download, both of getting to that state, and of getting from that state.

Calculating advantages
This is where things get tricky. If you go over the above mathematical definition of advantage, you can't help but notice that a large part of it depends on what happens in a possible future. This is not something you can calculate in a straight-forward manner. Some future-prediction is needed here.

Fortunately, if the above definition of advantage is formed mathematically, it can be reduced to the following equasion which depends only on the current and last network states(and not on all the future ones):

A-U*Prev_Max=D+Max*(gamma^T)-Prev_Max

Where:
A is the sum advantages of the uploads made since the last network state. This is calculated as the advantages of the clients, times the amount of upload made to each one.
U is the total amount of upload done to all clients.
D is the total download received between the last state and the current one.
Prev_Max is the maximal advantage of all clients in the last state.
Max is the maximal advantage of all clients in the current state.
T is the time that passed between the last and current state.
gamma is some constant smaller than one, representing the time-decay of download values.
(Feel free to go over the equasions and verify that the above holds true)

Now the above still doesn't fully offer a method for calculating all advantages, it is a way to incrementally verify if a certain calculation is correct.

From this point, what AR does is try to fit some simple mathematic function, representing the advantages of clients at any given time, to satisfy the above equasion for all of the downloads and uploads measured so far.
It does this, using a "filter".

Filters
Filters are a simple yet effective method for fitting a function to a certain mathematical condition.

In general mathematical form, filters try to solve the following:
There are two given functions, H and F.
X1...Xn are vectors that satisfy:
Xn=H(Xn-1)
Y1...Yn are vectors that are given. The filter must find X1...Xn(given H, it's enough to find one of them), so that Y1...Yn are closest to F(X1)...F(Xn).
"Closest" is defined as "sum(|Yi-F(Xi)|^2)" being minimal.

Here's how filters help calculate advantages:
Suppose we could make a sophisticated simulator that would predict the actions of the network and compute the advantages of all clients. That simulator would only be dependant on it's code and memory. We therefore define the series X1...Xn as the code of the simulator and it's memory at various times. Since we know how code and memory combine, we simply define H as running a cycle of the simulator. H doesn't depend on the simulator itself, only on how a computer is built, so H is given.
Now, we would expect the simulator to fullfil the advantage equasion above. We therefore define F(Xi) as the subtraction of the two sides of the equasion for the result of a given code and memory Xi at the time i. We can calculate F for any code Xi once we have the uploads and downloads of a given cycle. So F is also given.
Note that in a perfect simulator, F(Xi) would be 0 for every i. This is because a perfect simulator would satisfy the above equasion, so the subtraction of the two sides would result in 0. We therefore define Y1...Yn as a series of 0s.
The result is, that by using the filter we find the code and current state-memory for a simulator that should calculate advantages in the most accurate possible way.

(Side note: For those of you being skeptic about whether such a simulator can be found, I should mention similar methods were used to create a simulator that predicted stocks profit opportunities at over 70% success rate. I would think a mostly computer-driven network is not nearly as unpredictable as stocks)

Now the main advantage of filters is that their calculation is ongoing, and they don't need to know the internals of H and F, only to be able to compute them. Just by calculating different Hs and Fs at given times, they can find an optimal X series. This means that you don't have to remember all past downloads and uploads to calculate different values of F, but you can simply calculate as you go.

How do filters work
Filters work in a very simple manner.
Given a value Y1 at a given time, they calculate and store the set of all X1s where F(X1)=Y1(Or, if none exist, the set of closest ones).
Then, when the next Y2 is received, it intersects that set with those that satisfy F(H(X1))=Y2, and then stores the resulting new intersection state-set of X2=H(X1).
This continues, where at time i the filter has all of the possible values of Xi which satisfy all previous measurements, and given a new Yi it reduces it to the smaller set containing only values which are still possible.

Of course, it's impossible to save or intersect an infinite set on computer. Instead filter algorithms reduce the sets to linear or parabolic spaces, which can be stored through a finite set of points within the set, and where intersection is simply projection onto a super-surface.
The difference between F and H to a linear reduction of them is overcome by constantly extending the "possibile values surface" by a small error value in each direction, to represent the values that may have been removed through the linearization.

Also, since only one possibility for Xi can be used for calculating a possibility for the current advantages, the mean(average) of all possible Xi`s is used.

Summary
Using a single recursive formula, AR aims to create a simulator that predicts client advantages, and hence predicts opportunities to get download through upload.

While I did not elaborate on the specific formulas that make out the filter, or the "computer function" H, I think the main point of how AR works is sufficiently understood.

The actual AR source code is available with the rest of SF-IOM, for anyone willing to take a look. Suggestions for improving the filter or the function H would be more than welcome.

If you have any more questions about the system, don't hesitate to ask.

[wtb]

As I wrote in the testing thread:

Quote

Well, if it's mathematical help you need - that I could provide! It's however been quite some time since I last looked at the emule code and I'd certainly need some specific pointers as to what AR should do and how it interacts.
But I'd certainly be willing to help you, if you want.

I'll have a look at the current source tomorrow, to see what you use for the filter and the "computer function"...

Could you maybe give me some information, in how many cases those NaNs occur and the general data types used? Could you produce a list of vectors and other values that occur during run time?

[SlugFiller]

Well, logging all of that information could take alot of diskspace.
It's not too difficult though, especially with the latest code. Just add a few lines that flush the entire memory of CNetwork and CFilter at various places to a file.

The data types I use are simply doubles. I use large arrays of doubles to represent vectors, matrices, and whatnot.

As to when the NaNs occur, seemingly as soon as the first or second filter update finishs, even without any error being injected into the mean case.

Quote

I'll have a look at the current source tomorrow, to see what you use for the filter and the "computer function"...

Luckily, with the latest code revision, I've added tell-tale marks for where those are in the code.

The calculation of H is done in "forward pass". There is convinient commenting, and as of recent, debug log sorrounding that area.
Xn-1 is loaded using m_filter.LoadSigma, H is applied, and then Xn is stored using m_filter.SaveSigma. This applies to several "sigma points" which represent different possible values for Xn.
Right below it, in "backward pass" is the calculation of F. Once again, LoadSigma is used, And SetSigmaError stores the resulting Yn.

As for the filter itself, it's all conviniently place in the class CFilter, including comments on the matrix math involved. I use a Central Difference Filter(CDF). A simple google search should give you a PDF with all of the related math, and also preformance/quality-comparison with other common filters. Quite frankly, I looked more into the end results than I did into the math, so most of what such a PDF like that would teach you, I didn't even go over.

P.S. Don't forget to apply the fixes I've mentioned in the other thread to make sure you have a non-crashing version.

[gcostanza]

You complain noone helps you but do you realize that the problem you're trying to solve is most probably NP-complete?

[SlugFiller]

Quote

do you realize that the problem you're trying to solve is most probably NP-complete?

It's not NP-complete since:
-You can't reduce SAT to it, not by a long shot.
-There is such a thing as "almost a solution" to this problem. An accurate solution isn't needed, and that's assuming one even exists.
-Unlike NP problems, complete or otherwise, brute-forcing it won't necessarily give you an accurate solution. So, most likely, it can't be reduced to SAT either, though I'd love an offer on how you would go about doing that if you've got one.

The system as whole is very heuristic. That is as much as needed, since similar systems successfully solve similar but tougher problems.

[Enig123]

@SlugFiller

Acording to AR you descripted with detail, I suspect bad mods with credit shaping which happened to download the same file as you do will get more rating with the algorithm. If yes, AR is encourage those bad features.

If I'm wrong, please correct me and give me more explanation on how can AR cooperate with anti-leecher.

[SlugFiller]

Quote

I suspect bad mods with credit shaping which happened to download the same file as you do will get more rating with the algorithm

A user can only get good rating if uploading to them alters the state of the network in a profitable way.
Uploading to a shaper doesn't effect their own behavior, and hence does not effect the network(except for ending up not uploading to others, in which case it is equivalent to stopping upload). The same applies to 0-upload leechers.
Actually, as a slightly unwanted side-effect, it applies to anyone without a U/D dependant credits system of sorts. If uploading to a client doesn't alter the client's behavior, then that client cannot generate an advantage.

[wtb]

Sorry taht I hadn't yet time to look trough the code!
I hope the weekend will provide some time...

[Phoebe]

SlugFiller, on Oct 12 2005, 05:47 PM, said:

Advantages
A client's advantage is defined as a weighted sum of future downloads that can be achieved by uploading to that client now.

Clients upload at a fixed rate, uploading to a client likely won't affect that client's own upload speed.
Unless that client's upload setting was changed or that client is being choked, but the AR is too simple to be able to predict human behavior and too complex a formula to simply avoid uploading to choked clients.

Of course, this is assuming the AR will have a complete and accurate view of all of the eD2K network transactions. We wouldn't need the AR in the first place if we had that much information on all other clients.

What the AR can do is monitor the uploads and downloads on a limited part of network.
In this situation, if a subset of the network uploading to a client increase how much that client uploads to that subset of the network, it's most likely because that client redirected it's upload capacity from the rest of the network to that subset of the network. In other words, that client is using a CS, and the monitored subset of the network can benefit from that client's CS.
Thus the AR effectively is a sophisticated formula used to find the best upload targets for a reverse CS.

(I doubt this is the kind of 'help' you wanted)

This post has been edited by Phoebe: 18 October 2005 - 02:08 PM

[SlugFiller]

Quote

Clients upload at a fixed rate, uploading to a client likely won't affect that client's own upload speed.

It's not meant to effect the amount of upload, but rather to whom said upload goes to.
By uploading to a user you effect that user's AR, causing it to upload to certain users, which effects their AR, and so on and so forth, until someone's AR is effected so that you are uploaded to.
The "sum download" I was talking about in the quote you've made is the sum download to the client measuring advantages. Advantages are from client, to client, at a certain point in time.

Quote

Thus the AR effectively is a sophisticated formula used to find the best upload targets for a reverse CS.

That's pretty close.
AR is, essentially, a sophisticated way to predict and exploit whatever CS is used by the other client.
For example, with the rest of the network using the normal CS, it would, theoretically, turn into a trader/shaper. The difference from a normal method for doing that is that it doesn't assume the other side uses the normal CS and can work with(read: exploit) other CSs.
In the end goal, various clients running AR would essentially be trying to exploit each other through controlling upload(thus, AR is the single shaping tool against AR). However, since they are all striving for max download, no one can be left out(Would not satisfy the others if getting no download). The bandwidth would therefore be divided according to their respective power over the network, as in, the amount of upload they have and the amount of different people they can effect with it.

Quote

(I doubt this is the kind of 'help' you wanted)

Well, I was hoping for help as to why it keeps turning into NaNs, and ways to solve this, perhaps alternate H or filter methods, or whatever.
But it's good that you're raising questions. The more you know, the better position you are at to help me.

[gcostanza]

SlugFiller, on Oct 13 2005, 05:54 PM, said:

Quote

do you realize that the problem you're trying to solve is most probably NP-complete?

It's not NP-complete since:
-You can't reduce SAT to it, not by a long shot.

I know I owe you a reply but I was travelling a bit and had no spare time. Just wanted to let you know that asking me to reduce the problem to a SAT is very rude! It's like asking an engineer to demonstrate that the bridge he designed will not fall under some weight by providing the probability equations of all its electrons.

Now this task is way over my Philosopher's (not mathematician's) head but would it suffice that I reduce the problem to the TSP (Travelling Salesman Problem). Since the SAT is reducible to the TSP and by definition there exists a polynomial-time reduction between any two NP-complete problems this should prove NP-completeness with enough authority.

The proof seems quite trivial to me (pending dramatic mistakes) but this is more an intellectual discussion because, as you said, even a non-optimal solution can be acceptable. You will still have to prove, though, that your solution is better that e.g. simple credit shaping using the official credit system or no credit shaping at all (that proof is conspicuously missing).

Furthermore I'd like to ask you how do you justify the assumption that each state of your system is conditionally independent of the past states. This is a requirement for the system to be a Markov process which in turn is the basic assumption of a Kalman filter. I don't see any transformation applicable to emule's reality that could help and without that we're walking on a path that is born from quite a big error.

[SlugFiller]

Quote

I know I owe you a reply but I was travelling a bit and had no spare time. Just wanted to let you know that asking me to reduce the problem to a SAT is very rude! It's like asking an engineer to demonstrate that the bridge he designed will not fall under some weight by providing the probability equations of all its electrons.

The funny part is, that you think this is something that doesn't happen.
Well, maybe not with electrons, but weight-per-point is required.
That aside, SAT-reduction is the minimal requirement for NP completeness.

Quote

would it suffice that I reduce the problem to the TSP (Travelling Salesman Problem).

Yes, since TSP is reduced to SAT.
A reduction is a (polinomially) decidable function f, where f takes cases from the reduced problem to cases in the problem reduced to, in a way that the solution remains the same(Note: This relies on the True/False solution model).
So, if you reduce TSP to the a problem using f, and we know SAT reduces to TSP using g, then SAT reduces to the problem using h=fg.
So a reduction from TSP derives a reduction from SAT(and if you know the SAT->TSP reduction, then you can get the specific reduction easily).

Quote

The proof seems quite trivial to me

Not so to me. Mind explaining it?
By the way, I notice here you say "reduce the problem to TSP", even though it should be the other way around.

Quote

You will still have to prove, though, that your solution is better that e.g. simple credit shaping using the official credit system or no credit shaping at all (that proof is conspicuously missing).

Credit shaping assumes that the other side uses the official credits system. It's enough to consider the case where the other side might be using an inverse credits system - lowering credits as download is received. Credit shaping is therefore inferior even to no shaping.
However, when the other side is using the official credits system, no shaping is obviously inferior to shaping, since it provides less credits and therefore less downloads.

My system is superior since it can be both, decided according to experiemental results. It detects the credits system used by the other side and, more specifically, how to best exploit it. As such, it cannot be fooled, provided it's results are sufficiently accurate.

Quote

Furthermore I'd like to ask you how do you justify the assumption that each state of your system is conditionally independent of the past states.

A state is inherantly dependant on all previous states.
A state reached is dependant on the upload made and the state it was made from.
All prior states an actions are actually a part of what the state is.
Like I've said in the first post, a state represents the conditions throughout the universe, including the memory of all computers and humans, and also cosmic events. The state, as used by the simulator, can be viewed as a form of extremely lossy compression of that.

Aside from the influence of previous states on future states in the function H, the filter itself is used so that the effects of past states and measurements are remembered and reused.

Quote

This is a requirement for the system to be a Markov process which in turn is the basic assumption of a Kalman filter.

You're forgetting "hidden state" in Markov chains. It represents the unmeasureable part of the state. The model usually represents it as potentially being a compression of all previous actions.
This is also a part of the Kalman filter. If the state is completely measureable, then X simply represents constant parameters for function F, and H=identity. However, Kalman filters do not define H as an identity. In the case of hidden states, it represents the conditional alteration of the hidden states according to the previous states and other parameters within X.

Even though most(though not all) experiementation with hidden states involved alot of measurement and only a small amount of hidden information, it is still possible to consider the actions over the entire network as being a hidden state to be estimated.

This post has been edited by SlugFiller: 19 October 2005 - 03:29 PM

[Phoebe]

SlugFiller, could you tell me exactly what data (used for the AR calculations) does the AR system shares with other clients, when does it shares it and how often?

[SlugFiller]

It doesn't, at all.
Any information received from other clients is considered unreliable. It trusts only the network's behavior - only the upload and download it personally experiences.

Look at the description I've made at the first post. It fully describes the algorithm in which AR works with two exceptions:
-The function H used by the filter isn't described. You can find out the main part of it by google searching for "LSTM".
-The actual filter algorithm isn't described, though you can read about it by google-searching for "CDF" or "Central Difference Filter".

The function F used by the filter is fairly described by the advantage equasion.

The actual help I need is more mathematic than algorithmic: I need help on how to modify(or replace) the filter algorithm and the function H to receive the numerically desired results, or perhaps tips on why they currently diverge even for 0-error.
Since they are mostly algebric in nature, the issue of understanding them is a matter of understanding the algebra behind them.

Experience with matlab could help.

[Phoebe]

Although I know the system will work, I also estimate there will be so much 'white noise' that the system will have little positive effect, will make your upload allocation alot more unfair in a way that RandQueue could never even hope to achieve and will also most likely be vulnerable to many exploits (as many exploits as it is complex, and it's very complex).

Not that that would stop me from trying to help you, it's just that, being a programmer not a mathematician, I don't use algebra for something that can be handled more simply by an algorithm. Yet to be able to help you I'll would to understand how all your formulas and algorithms work alone and together, then find the flaw(s) of the system.
Unless I get lucky and find the flaw early in the analysis, it would be faster for me to simply redesign the system from scratch using your experience and findings as a guide...

[SlugFiller]

Quote

Although I know the system will work

Well, if the numerical instability is resolved...

Quote

I also estimate there will be so much 'white noise' that the system will have little positive effect

I would settle for a small move in the right direction per queue cycle. It would be better than, well, anything currently available.

Quote

(as many exploits as it is complex, and it's very complex)

Actually, simpler things are easier to exploit. Consider that the exploiter must be able to reverse engineer the exploited algorithm, so for the exploiter, simpler is better.
Besides, it's so unpredictable, I can't even imagine the possibility of exploiting it.

Quote

being a programmer not a mathematician

Could have fooled me.
Your skill with probabilities far outweighs mine, and I used to consider myself good with that.
This could potentially be helpful here.

Quote

Unless I get lucky and find the flaw early in the analysis, it would be faster for me to simply redesign the system from scratch using your experience and findings as a guide...

Well, aside from the H formula and the formulas for CDF, I've pretty much gave you everything you need to design your own system.
You could probably also just take the advantage formula and use a different filter for it, one you are more familiar with, and trust more.

I did, by the way, write large portions of the code from scratch several times, to the point in which I am fairly certain that the issue is either mathematical divergence, or numerical instability.
Unfortunately, I've failed to determine a cause for the latter, and don't know how to identify or prevent the prior.