Saturday, September 12, 2009

HTB traffic control burst calculation inaccuracy

My previous Kubuntu 7.04's Linux 2.6.20 kernel uses a 1000 Hz timer kernel (refer to HZ constant defininition and fourth value of kernel ABI /proc/net/psched routine psched_show in sch_api.c). HTB's burst is calculated by tc binary using the formula : bitrate/timer frequency + maximum transfer unit.
Ubuntu 8.04's Linux 2.6.24 kernel have an improved packet scheduler timer resolution. It now uses high resolution timer, with nanosecond accuracy. Refer to psched_show in sch_api.c, and Fourth value of /proc/net/psched now returns 1 G (10^9). HTB burst calculation is now bitrate/10^9 + mtu.. Somehow this is will always a small value, and as a side-effect HTB qos scheduler no longer capable of delivering high bitrates accurately to stations.
My analysis based on my limited knowledge of the packet scheduler : the linux's packet scheduler is driven by calls to dequeue function. This might be driven by tx complete interrupt or something else. So it is not timer-driven. But the packet scheduler routines (such as sch_htb) keeps track of passing time using the value of packet scheduler timer (previously, 1KHz timer, and now, the 1 GHz timer). Htb adds tokens into the token bucket based on time passed between previously recorded time of change in the class (cl->t_c) and the current time (q->now) (see sch_htb.c:660). Herein lies the problem, the current time q->now is no longer the current time, because the timer frequency is in nanoseconds and there are tens if not hundreds of instructions being executed between the assignment of q->now (see htb_dequeue at sch_htb.c:894) and the usage of q->now. And, maybe, some interrupt has occurred (I dont really know, dequeue is not being called in the context of NMI, is it ?), and maybe one milliseconds has passed.. The inaccuracy of the size of the added token, causes the htb to prevent packets being sent in timely manner -> it thinks that the class not eligible to send package because token remaining is less than packet size, the token count is actually less than what it supposed to be.
This is what I thought, for now. The cure seem to be changing tc source code to assume 1KHz timer (which amounts to 1ms accuracy) when tc finds out that a nanosecond timer is in use, so the token buffer is large enough to cater for problems caused by time inaccuracies said above.

Sunday, September 6, 2009

Names in our code

This is just a summary of some rule-of-thumbs when developing source codes.

When coding, do these :
  • use descriptive names
  • please classify/categorize so we have shorter source files. Or, we have fewer source files in each folder (distribute files into category folders). In OOP, we should refactor into new classes if things gotten too crowded in one class, or even refactor the class into different packages. In PHP, we should refactor into new files and/or new folders.

Rules that were Anti-patterns :
  • don't use generic names like $query. When reading it, I don't have a clue what does it stands for, a query to the users table, or a query to delete a user, or what? OK, maybe it can be used if the scope is local, that is, I could easily look for the meaning in the same function or small file.
  • avoid long parameter list. It is difficult to find out which parameter means what. We could use: a value class in OOP languages, or associative array in PHP, or even object in PHP, to give meaningful parameter. When function insert(name,address,groupid,status,isAdmin) being called, it becames insert($name,$address,null,0,$isAdmin), and we must look elsewhere what does the 0 stand for. If we have $entity = array('name' => $name, 'address' => $address, 'groupid' => 0, 'isAdmin' => isAdmin); and call insert($entity); things are much easier to understand and easier to modify.