Talk:Max-min fairness

Some code

Here is some Python 3.2 code I wrote to implement progressive filling. I haven't included it in the article because its incremental filling nature makes it inefficient compared to what the Computer Networks - Performance and Quality of Service (2010) textbook mentions. Moreover, it is unreasonably limited to working with integers only. I am not actually using it for traffic shaping, but for a different application instead for which it is suitable enough.

@functools.lru_cache(maxsize=1000)
def _mmfa_ipf(num_avail_shares, demands):
    """Return the sequence of shares corresponding to the provided number 
    of available shares and the sequence of demands. Max-min fair 
    allocation, implemented by an incremental progressive filling algorithm 
    is used. Note that the implemented algorithm is not entirely efficient 
    due to its incremental filling nature.
    
    num_avail_shares should be a non-negative int.
    
    demands should be a hashable sequence (such as a tuple, and not a list) 
    of non-negative ints.
    
    Results may be cached in memory.
    """
    
    demands, indexes =  list(zip(*sorted(zip(demands, range(len(demands))), 
                                         reverse=True)))
                            # This sorts 'demands' and get indexes.
#        indexes, demands = list(zip(*sorted(enumerate(demands), 
#                                            key=operator.itemgetter(1), 
#                                            reverse=True)))
#                                # alternative technique for above
    # Note that 'reverse' above can be set equal to False for any specific 
    # applications that require it. 
    demands = list(demands)
    indexes = sorted(range(len(indexes)), key=lambda k: indexes[k]) 
        # This transform indexes to make them useful later for restoring 
        # the original order.
    
    len_ = len(demands)
    shares = [0] * len_
    
    i = 0
    while num_avail_shares and any(demands):
        if demands[i]:
            num_avail_shares -= 1
            demands[i] -= 1
            shares[i] += 1       
        i = (i + 1) % len_
        
    shares = tuple(shares[k] for k in indexes)        
    return shares

--IO Device (talk) 03:52, 22 January 2011 (UTC)