Implementation of the optimal bifurcation algorithm

optimal-bifurcation.c

/**
      Implementation of the optimal bifurcation algorithm.
  
       - bw: Amount of bandwidth to distribute
       - N: Number of links
       - Cs: Capacities of each link, in descending order
       - hCs: Square roots of the capacities
       - b [output]: Bandwidths to send through each link
  
      Given a set of links whose capacities are the items of `Cs`, split the
      traffic `bw` into each link so that the average transmission time is minimal.
      (Assuming Poisson traffic, infinite queues for each link, and no other
      traffic being sent through the links)

      Preconditions:
      - Cs is sorted in descending order
      - hC == [ sqrt(C) for C in Cs ]
      - 0 <= bw <= sum(Cs)
      Postconditions:
      - sum(return) == bw
      - all(0 <= b <= C for b, C in zip(return, Cs))
 */
void optimal_bifurcation(double bw, size_t N, double *Cs, double *hCs, double *b) {
  size_t i;
  double Csum = 0, hCsum = 0;
  for (i = 0; i < N; i++) {
    if (bw <= Csum - hCsum * hCs[i]) break;
    Csum += Cs[i];
    hCsum += hCs[i];
  }
  double slope = (Csum - bw) / hCsum;
  for (size_t k = 0; k < i; k++)
    b[k] = Cs[k] - hCs[k] * slope;
  memset(b + i, 0, (N - i) * sizeof(*b));
}

optimal-bifurcation.py

from typing import Sequence
from math import sqrt

def optimal_bifurcation(bw: float, Cs: Sequence[float]) -> Sequence[float]:
  ''' Implementation of the optimal bifurcation algorithm.
  
       - bw: Amount of bandwidth to distribute
       - Cs: Capacities of each link through which `bw` can be sent, in descending order
  
      Given a set of links whose capacities are the items of `Cs`, split the
      traffic `bw` into each link so that the average transmission time is minimal.
      (Assuming Poisson traffic, infinite queues for each link, and no other
      traffic being sent through the links)
      
      Returns: array of bandwidths for each link.
      
      Preconditions:
      - Cs is sorted in descending order
      - 0 <= bw <= sum(Cs)
      Postconditions:
      - len(return) == len(Cs)
      - sum(return) == bw
      - all(0 <= b <= C for b, C in zip(return, Cs))
  '''
  assert 0 <= bw <= sum(Cs)
  return optimal_bifurcation_raw(bw, Cs, list(map(sqrt, Cs)))

def optimal_bifurcation_raw(bw: float, Cs: Sequence[float], hCs: Sequence[float]) -> Sequence[float]:
  ''' Implementation of the optimal bifurcation algorithm.
  
       - bw: Amount of bandwidth to distribute
       - Cs: Capacities of each link through which `bw` can be sent, in descending order
       - hCs: Square roots of the capacities
  
      Given a set of links whose capacities are the items of `Cs`, split the
      traffic `bw` into each link so that the average transmission time is minimal.
      (Assuming Poisson traffic, infinite queues for each link, and no other
      traffic being sent through the links)
      
      Returns: array of bandwidths for each link.
      
      Preconditions:
      - Cs is sorted in descending order
      - hC == [ sqrt(C) for C in Cs ]
      - 0 <= bw <= sum(Cs)
      Postconditions:
      - len(return) == len(Cs)
      - sum(return) == bw
      - all(0 <= b <= C for b, C in zip(return, Cs))
  '''
  i, N = 0, len(Cs)
  Csum, hCsum = 0, 0
  while i < N:
    if bw <= Csum - hCsum * hCs[i]: break
    Csum += Cs[i]
    hCsum += hCs[i]
    i += 1
  b = lambda k: Cs[k] - (Csum - bw) * hCs[k] / hCsum
  return [ (b(k) if k < i else 0) for k in range(N) ]