网络QoS原理与实现 [10]

DRR在Linux中的实现

前面介绍了DRR算法，这里我们看看如何在Linux中实现DRR。从上面DRR介绍中，我们知道，对于DRR整个调度算法有一个active_queue，每个class都有一个deficit和weight。Linux中的DRR算法实现于net/sched/sch_drr.c，从中可以发现定义如下：

struct drr_sched {
     struct list_head active;
     struct tcf_proto *filter_list;
     struct Qdisc_class_hash clhash;
};
struct drr_class {
     struct Qdisc_class_common common;
     unsigned int refcnt;
     unsigned int filter_cnt;
 
     struct gnet_stats_basic_packed bstats;
     struct gnet_stats_queue qstats;
     struct gnet_stats_rate_est rate_est;
     struct list_head alist;
     struct Qdisc *qdisc;
 
     u32 quantum;
     u32 deficit;
};


在这里filter_list用于保存挂在这个Qdisc下面的filter，用于对子class进行进一步分类。每个class的weight用quantum表示，即每次class的deficit用完后一次添加的数目。

其enqueue函数如下（有删节）：

static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
     struct drr_sched *q = qdisc_priv(sch);
     struct drr_class *cl;
 
     cl = drr_classify(skb, sch, &err); /* 首先进行利用q->filter_list进行分类 */
     len = qdisc_pkt_len(skb);
     err = qdisc_enqueue(skb, cl->qdisc); /* enqueue到子class的Qdisc中 */
     if (unlikely(err != NET_XMIT_SUCCESS)) {
          。。。
           return err;
     }
 
     if (cl->qdisc->q.qlen == 1) { /* class qdisc原来为空 */
           list_add_tail(&cl->alist, &q->active); /* 添加到active queue中 */
           cl->deficit = cl->quantum; /* 同时更新deficit到最大 = quantum */
     }
 
     /* 更新统计信息 */
     cl->bstats.packets++;
     cl->bstats.bytes += len;
     sch->bstats.packets++;
     sch->bstats.bytes += len;
 
     sch->q.qlen++;
     return err;
}


接下来看dequeue的实现 （有删节）：

static struct sk_buff *drr_dequeue(struct Qdisc *sch)
{
     struct drr_sched *q = qdisc_priv(sch);
     struct drr_class *cl;
 
     while (1) { /* 在此循环中对active queue进行RR调度 */
           cl = list_first_entry(&q->active, struct drr_class, alist); /* 取出第一个class */
           skb = cl->qdisc->ops->peek(cl->qdisc);
           if (skb == NULL) /* 没有pkt，退出 */
                goto out;
 
           len = qdisc_pkt_len(skb);
           if (len <= cl->deficit) { /* 一个可调度的class */
                cl->deficit -= len; /* 更新class的deficit */
                skb = qdisc_dequeue_peeked(cl->qdisc);
                if (cl->qdisc->q.qlen == 0) /* 此class调度后为空，移出active queue */
                     list_del(&cl->alist);
                sch->q.qlen--;
                return skb; /* 返回这个pkt */
           }
 
           cl->deficit += cl->quantum; /* class不可调度，顺便更新其下一轮的deficit */
           list_move_tail(&cl->alist, &q->active); /* class移到active queue末尾，等待下一轮 */
     }
out:
     return NULL;
}


待续