Kleinrock Square-Root Channel Capacity Delay Formula

Allocate surplus bandwidth by the square root of traffic—never proportionally!

In ARPANET packet-switching design, Leonard Kleinrock (1964) proved a famous surprise: if a network architect has Total Capacity Budget C_tot (Mbps) to split across two M/M/1 links carrying Poisson packet rates lambda_1 and lambda_2 (pkt/s) of mean service rate mu (pkt/Mbit, so minimum stability loads are F_1 = lambda_1 / mu and F_2 = lambda_2 / mu with C_tot > F_sum = F_1 + F_2), splitting C_tot proportionally to traffic starves the lighter link, while splitting surplus bandwidth equally starves the heavier link! Minimizing traffic-weighted mean packet delay T = (lambda_1 / Gamma) / (mu * C_1 - lambda_1) + (lambda_2 / Gamma) / (mu * C_2 - lambda_2) yields Kleinrock’s Square-Root Channel Capacity Law: first give every link its exact offered load lambda_i / mu, then allocate Excess Bandwidth (C_tot - F_sum) in proportion to SQRT(lambda_i)!

Verify on Link1_Arrival lambda_1 = 900 pkt/s (B2), Link2_Arrival lambda_2 = 100 pkt/s (B3 -> Total Gamma = 1,000 pkt/s), Packet_Rate_per_Mb mu = 100 pkt/Mb (10 kbit/pkt -> F_1 = 9.0 Mbps, F_2 = 1.0 Mbps, F_sum = 10.0 Mbps, B4), and Total_Bandwidth_Budget C_tot = 20.0 Mbps (10.0 Mbps surplus, B5): Since SQRT(900) = 30 and SQRT(100) = 10 (weights 0.75 and 0.25), Optimal Link 1 Capacity is C_1* = 9.0 + 10.0 * 0.75 = 16.50 Mbps and Optimal Link 2 Capacity is C_2* = 1.0 + 10.0 * 0.25 = 3.50 Mbps! Minimum Mean Packet Delay is T_min = 1000 * (30 + 10)^2 / (1000 * 100 * 10) = 1.6000 ms (vs 2.0000 ms under Equal-Excess 14.0 / 6.0 Mbps—a full 20.0% latency reduction without buying 1 Kbps of extra bandwidth)!

Kleinrock Square-Root Link Capacity & Minimum Delay Formula

Check ergodicity C_tot > (lambda_1 + lambda_2) / mu first: if Total Capacity C_tot <= F_sum, at least one M/M/1 queue saturates (rho >= 1) and steady-state delay explodes to infinity!

=LET(lm_1, B2, lm_2, B3, mu_p, B4, c_tt, B5, IF(OR(lm_1 <= 0, lm_2 <= 0, mu_p <= 0, c_tt <= 0), "Invalid Network Input", LET(f_sm, (lm_1 + lm_2) / mu_p, IF(c_tt <= f_sm, "Unstable Queue (C_tot <= Load)", ROUND(1000 * (SQRT(lm_1) + SQRT(lm_2)) ^ 2 / ((lm_1 + lm_2) * mu_p * (c_tt - f_sm)), 4)))))

Equal-Excess Benchmark Delay Formula

Notice that Proportional Allocation C_i = C_tot * (lambda_i / (lambda_1 + lambda_2)) gives both links identical utilization rho = 0.50 here (18.0 & 2.0 Mbps), which ALSO yields 0.9*(1/900) + 0.1*(1/100) = 2.0000 ms—still 25% slower than Kleinrock’s 1.6000 ms!

=LET(lm_1, B2, lm_2, B3, mu_p, B4, c_tt, B5, ex_c, c_tt - (lm_1 + lm_2) / mu_p, IF(ISTEXT(E4), E4, ROUND(1000 * (2 / (mu_p * ex_c)), 4)))

Further reading

• Arte Sheets Lesson — Pollaczek-Khinchine M/G/1 Queue Waiting Time & Variance
• Arte Sheets Lesson — Token Bucket Rate Limiter Max Burst & Sustained Rate