• Jon Paul Maloy's avatar
    tipc: improve link congestion algorithm · f21e897e
    Jon Paul Maloy authored
    The link congestion algorithm used until now implies two problems.
    
    - It is too generous towards lower-level messages in situations of high
      load by giving "absolute" bandwidth guarantees to the different
      priority levels. LOW traffic is guaranteed 10%, MEDIUM is guaranted
      20%, HIGH is guaranteed 30%, and CRITICAL is guaranteed 40% of the
      available bandwidth. But, in the absence of higher level traffic, the
      ratio between two distinct levels becomes unreasonable. E.g. if there
      is only LOW and MEDIUM traffic on a system, the former is guaranteed
      1/3 of the bandwidth, and the latter 2/3. This again means that if
      there is e.g. one LOW user and 10 MEDIUM users, the  former will have
      33.3% of the bandwidth, and the others will have to compete for the
      remainder, i.e. each will end up with 6.7% of the capacity.
    
    - Packets of type MSG_BUNDLER are created at SYSTEM importance level,
      but only after the packets bundled into it have passed the congestion
      test for their own respective levels. Since bundled packets don't
      result in incrementing the level counter for their own importance,
      only occasionally for the SYSTEM level counter, they do in practice
      obtain SYSTEM level importance. Hence, the current implementation
      provides a gap in the congestion algorithm that in the worst case
      may lead to a link reset.
    
    We now refine the congestion algorithm as follows:
    
    - A message is accepted to the link backlog only if its own level
      counter, and all superior level counters, permit it.
    
    - The importance of a created bundle packet is set according to its
      contents. A bundle packet created from messges at levels LOW to
      CRITICAL is given importance level CRITICAL, while a bundle created
      from a SYSTEM level message is given importance SYSTEM. In the latter
      case only subsequent SYSTEM level messages are allowed to be bundled
      into it.
    
    This solves the first problem described above, by making the bandwidth
    guarantee relative to the total number of users at all levels; only
    the upper limit for each level remains absolute. In the example
    described above, the single LOW user would use 1/11th of the bandwidth,
    the same as each of the ten MEDIUM users, but he still has the same
    guarantee against starvation as the latter ones.
    
    The fix also solves the second problem. If the CRITICAL level is filled
    up by bundle packets of that level, no lower level packets will be
    accepted any more.
    Suggested-by: default avatarGergely Kiss <gergely.kiss@ericsson.com>
    Reviewed-by: default avatarYing Xue <ying.xue@windriver.com>
    Signed-off-by: default avatarJon Maloy <jon.maloy@ericsson.com>
    Signed-off-by: default avatarDavid S. Miller <davem@davemloft.net>
    f21e897e
msg.c 15.7 KB