Despite what most computer science professors will tell you, the day to day tasks of the average software developer actually require surprisingly little math. Sure, you’ll occasionally need to remember how to compare algorithm performance, or perhaps some really basic statistics, but in general it’s more about just having the experience to be able to skip the math part and get right to coding the solution.
Every once in a while, though, you get slapped with the need for actual math. It happened to me recently when I faced a pretty simple problem, but one that required me to go searching for an actual mathematical formula.
I’ve been working on some peer to peer code that downloads data from a peer mesh. Each peer broadcasts that it needs some data, and then waits for a little while for the responses from its peers. This peer mesh could be 2 computers, or 200, or even 2000, so I needed a good way to choose which peer to download the data from.
I came up with 3 big metrics: hop count, round-trip time, and a load factor. Hop count is essentially how many PCs the broadcasted request had to be relayed through until it reached the PC that eventually answered. Round-trip time is pretty self explanatory. Load factor is, more or less, how busy the answering PC is at the time it responded to the requesting peer. Choosing a peer means comparing these metrics for each of the responding peers. This process has a cool nerdy name called multi-criteria decision analysis, or MCDA for short.
MCDA has tons of math behind it, and when I started researching a good way to do this, I got scared pretty quickly. Indeed, there are entire branches of information theory dedicated to solving MCDA problems. I started to recall classic computer science problems such as that stupid travelling salesman, and pondered whether or not I should just do a random selection of peers rather than bother with all this hard thinkin’.
Rather than give up, I decided to just step back for a minute and see if there was an easy solution. I realized that I needed to somehow convert the different units of each of these metrics into a common unit that I could compare easily. This meant converting the differing units into a percentage, which of course is unit-less. I then need a way to weight each of these percentages according to my arbitrary business rules. I knew that if I raised my percentages to a fractional power, and then multiplied each of these weighted percentages together, I would get a value that when compared with 1 would give me the rank. A value less than 1 means that the numerator in my percentages is “better” than the denominator, a value greater than 1 means the opposite. This can be represented by the following equation:
As it turns out, this is called a weighted product model. Yay, I rediscovered centuries old math. I won’t take credit for coming up with that fancy notation above. Instead, my notation was decidedly less impressive. In the below equation, h = hops, t = round-trip time, l = load, and w = weight.
For example, if I wanted to weight hops at 20%, round-trip time at 30%, and load at 50%, I would do:
The result is that my numerator (3/175/47.6) is a better choice than my denominator (5/67/88).
One thing to remember here is that this is the relative rank. It’s the rank when you compare peer 1 and peer 2. It is not an absolute rank. To handle this, I used LINQ’s wonderful built in sorting functionality. By implementing IComparable<T> on my peer objects, I was able to get a list of peers ordered best to worst.
The last thing I did was to sum up all the relative ranks and divide each rank by that sum. This gave me a “rank percentage” which I can use for selection. Keeping with the above example, the numerator would be chosen roughly 67% of the time versus the denominator because (1/(1 + .4928)) = .6698. Once you have this percentage, you generate a random number and if it falls in the “range” created by your percentage (0 to 67 goes to the numerator, 68 to 100 goes to the denominator, etc.), you choose the corresponding peer.
So yeah, this is high school math. I understand that. The point is I can’t remember the last time I used something like this, and it was kind of fun to figure it out. I really need to get back into re-learning all the math I forgot since high school and college.