Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Implementation of the optimal bifurcation algorithm
/**
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));
}
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) ]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.