Hacker News new | past | comments | ask | show | jobs | submit login

Just today I was reminded of this paragraph when we thought about completely different discrete optimalization problem with the expectation that there must be some way to solve it analytically instead of numerically.

But in case of CM router, “the average number of 1 bits in a message address.” is surprisingly useful quantity, because for the most straightforward implementation of hypercube routing the number of one bits in address is equal to number of links the message must traverse. The algorithm is essentially this: find address bit set to one, clear it and send the message down the link with same number as was the order of that bit, if address is all zeros, message has reached the destination (the same thing can be implemented without changing the address seen on wire by each router XORing its node ID with address in message and getting the same bitvector, but I believe most implementations actually modify the message address in each router).




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: