加权公平队列(WFQ)调度算法示例困惑及求解需求

我在进行WFQ算法的模拟练习，场景为所有数据包长度相同，每秒只能串行发送一个，权重配置为class 1: 0.5，class 2: 0.3，class 3: 0.2。对调度结果（先发送2个class 1的包，再发送2个class 3的包，接着发送1个class 2的包，跳过仍有等待数据包的class 1）存在疑问。

WFQ核心定义（来自《Computer Networking: a Top Down Approach》） #

WFQ与轮询的不同之处在于，每个类别在任意时间间隔内可获得差异化服务量。具体而言，每个类别i被分配权重w_i。当类别i有等待发送的数据包时，WFQ保证其获得的服务占比为w_i / sum(w_j)（分母为所有有等待数据包的类别权重之和）。最坏情况下，即使所有类别都有等待数据包，类别i仍能保证获得w_i / sum(w_j)的带宽占比（分母为所有类别权重之和）。因此，对于传输速率为R的链路，类别i的吞吐量至少为R * w_i / sum(w_j)。

调度结果的原因解释 #

这个场景下的WFQ采用了适配固定长度数据包的配额批量调度实现，核心逻辑是：

1. 将权重转换为整数比例：0.5:0.3:0.2 = 5:3:2，即每发送10个包，class 1应发5个、class 2发3个、class 3发2个，确保长期占比符合权重分配。
2. 调度时会优先填补配额缺口，避免低权重队列被长期饥饿：
   • 初始阶段高权重的class 1配额缺口最大，先发送2个包；
   • 此时class 1已发送数量超过当前累计发送数的对应比例（2/2=100% vs 目标50%），而class 3、class 2的配额缺口凸显；
   • 为保证公平性，转而调度class 3发送2个包，再调度class 2发送1个包，填补低权重队列的配额缺口；
   • 后续调度会优先发送class 1和class 2的包，补上之前的配额缺口，长期来看整体发送占比会趋近于权重分配。

伪代码实现 #

逐包虚拟时间调度（标准WFQ适配固定包长）

def wfq_per_packet_schedule(queues, weights, total_packets):
    # queues: 键为类别，值为对应队列剩余数据包数
    # weights: 键为类别，值为对应权重
    virtual_time = {cls: 0.0 for cls in queues}
    send_order = []
    
    for _ in range(total_packets):
        # 筛选有数据包的队列
        available = [cls for cls in queues if queues[cls] > 0]
        if not available:
            break
        # 选择虚拟时间最小的队列（虚拟时间相同时优先权重高的）
        selected = min(available, key=lambda x: (virtual_time[x], -weights[x]))
        # 发送数据包
        send_order.append(selected)
        queues[selected] -= 1
        # 更新虚拟时间：固定服务时间1 / 权重
        virtual_time[selected] += 1.0 / weights[selected]
    
    return send_order

批量配额调度（模拟练习中的实现逻辑）

def wfq_batch_schedule(queues, weights, batch_size=10):
    weight_sum = sum(weights.values())
    # 计算每个类别的目标发送比例
    ratios = {cls: w / weight_sum for cls, w in weights.items()}
    send_order = []
    total_sent = 0
    
    while any(q > 0 for q in queues.values()):
        sent_counts = {cls: send_order.count(cls) for cls in queues}
        # 计算当前批量内每个类别的目标发送数
        targets = {cls: (total_sent + batch_size) * ratios[cls] for cls in queues}
        # 按配额缺口发送数据包
        sent_in_batch = 0
        for cls in queues:
            if queues[cls] == 0:
                continue
            # 计算可发送的数量：取剩余包数和配额缺口的最小值
            send_num = min(queues[cls], int(targets[cls] - sent_counts[cls]))
            if send_num > 0:
                send_order.extend([cls] * send_num)
                queues[cls] -= send_num
                total_sent += send_num
                sent_in_batch += send_num
        # 若批量内无包可发（剩余包数不足），切换到逐包调度
        if sent_in_batch == 0:
            virtual_time = {cls: sent_counts[cls]/weights[cls] for cls in queues if queues[cls]>0}
            if not virtual_time:
                break
            selected = min(virtual_time.keys(), key=lambda x: virtual_time[x])
            send_order.append(selected)
            queues[selected] -= 1
            total_sent += 1
    
    return send_order

内容的提问来源于stack exchange，提问作者54skyxenon