数据包转发[面试题]解决思路

数据包转发[面试题]
一个转发器能转发100个数据包每秒，数据包具有高中低的优先级，
当数据包数量过大时（比如150个每秒），
如何根据数据包的优先级实时丢弃低优先级的包以保证高优先级的数据包转发
（先丢低级的数据包，再丢中级的数据包，最后是丢高级的数包）。

设置高中低三个优先级队列不行，因为有延迟。

------解决方案--------------------
我在UDX协议中实现转发是这样实现的。

1.固定比例转发。

把要转发的三种数据放到三个队列中。记为。A,B,C，DATA[3];

我生成一个100字节表类是BYTE randtable[100];

然后，把，A，B，C，按百分比，我们自己设置的比，随即放入RANDTABLE.
randtable[90个A,5个B,5个C],但是ABC位子是随即分布的。

需要转发包时，从DATA[randtable（rand() % 100）]中取一个数据，转发即可。

转发的数据比就会是按你事先分配的百分比转发。

当出现某个队列为空时，随即分配下个队列。


2优先转发，直接取出优先队列数据转发，为空为止。

------解决方案--------------------
我局的可以这样
建3个链表/循环队列 a b c

然后再建一个有100个元素的 链表 d， d中的元素指向 a b c ， 有包过来的时候按照优先级更新到a b c ，然后同时更新链表d， 

如果包总数超过100个数目时，根据 a b c 头部的指针可以得到这时应该丢弃的包是在那个队列中， 然后从 a 或者 b 、c中丢掉， 同时把这个包从d 从丢弃。


只要管理a b c 的头部指针， 下一个应该被丢弃的包的位置总是可以知道，不需要太多的计算。 先拿到 a b c 的位置，就可以得到d中的位置，