8 dstats = collections.defaultdict(int)
9 astats = collections.defaultdict(int)
15 "igmp.ggp.cbt.egp.igp.idrp.mhrp.narp.ospf.eigrp*p1:"
16 "udp.st.nvp.rdp.ddp.pvp.mtp.srp.smp.136:"
18 "ip.gre.etherip.l2tp:"
19 "hopopt.shim6.ipv6.ipv6route.ipv6frag.ipv6icmp.ipv6nonxt.ipv6opts*4:"
34 def _parse_classes(classes):
37 <CLASSLIST> ::= <CLASS> ":" CLASSLIST
39 <CLASS> ::= <PROTOLIST> "*" <PRIORITYSPEC>
41 <DFLTCLASS> ::= "*" <PRIORITYSPEC>
42 <PROTOLIST> ::= <PROTO> "." <PROTOLIST>
44 <PROTO> ::= <NAME> | <NUMBER>
45 <NAME> ::= --see http://en.wikipedia.org/wiki/List_of_IP_protocol_numbers --
46 --only in lowercase, with special characters removed--
49 <PRIORITYSPEC> ::= <THOUGHPUT> [ "#" <SIZE> ] [ "p" <PRIORITY> ]
50 <THOUGHPUT> ::= NUMBER -- default 1
51 <PRIORITY> ::= NUMBER -- default 0
52 <SIZE> ::= NUMBER -- default 1
54 classes = map(lambda x:x.split('*',2),classes.split(':'))
55 priorex = re.compile(r"(?P<thoughput>\d+)?(?:#(?P<size>\d+))?(?:p(?P<priority>\d+))?")
61 prio = priorex.match(cls[1])
66 int(prio.group("thoughput") or 1),
67 int(prio.group("priority") or 0),
68 int(prio.group("size") or 1),
71 cls[0] = map(clsmap, cls[0].split('.'))
78 class ClassQueue(object):
84 self.classspec = _parse_classes(_classes)
86 self.queues = [ collections.deque() for cls in xrange(len(self.classspec)) ]
90 for cls, (protos, (thoughput, prio, size)) in enumerate(self.classspec)
96 for cls in xrange(len(self.classspec))
97 for protos, (thoughput, prio, size) in ( self.classspec[cls], )
102 for cls in xrange(len(self.classspec))
103 for protos, (thoughput, prio, size) in ( self.classspec[cls], )
108 for cls, (protos, (thoughput, prio, size)) in enumerate(self.classspec)
109 for i in xrange(thoughput)
112 filter(lambda x : self.priomap[x] == prio, order)
113 for prio in reversed(sorted(set(self.priomap)))
115 for order in self.order:
116 random.shuffle(order)
118 if None not in self.classmap:
119 raise RuntimeError, "No default class: a default class must be present"
122 self.queues.append(collections.deque())
123 self.priomap.append(-1)
124 self.sizemap.append(_size)
125 self.order.insert(0, [len(self.queues)-1])
130 def __nonzero__(self):
140 self.cycle_update = True
142 self.queues = [ collections.deque() for cls in xrange(len(self.classspec)) ]
144 def queuefor(self, packet, ord=ord, len=len, classmask=0xEC):
145 if len(packet) >= 10:
146 proto = ord(packet[9])
147 rv = self.classmap.get(proto)
149 rv = self.classmap.get(None)
152 rv = self.classmap.get(None)
153 return proto, rv, self.sizemap[rv]
155 def get_packetdrop_p(self, qlen, qsize, packet):
156 pdrop = ((qlen * 1.0 / qsize) - 0.5) * 2.0
160 def append(self, packet, len=len, dstats=dstats, astats=astats, rng=random.random):
161 proto,qi,size = self.queuefor(packet)
166 if lq > (size/2) and _red:
167 pdrop = self.get_packetdrop_p(lq, size, packet)
171 classes = self.classes
172 if qi not in classes:
174 self.cycle_update = True
187 def appendleft(self, packet):
188 self.queues[-1].append(packet)
191 def pop(self, xrange=xrange, len=len, iter=iter, pop=collections.deque.pop):
192 return self.popleft(pop=pop)
194 def popleft(self, xrange=xrange, len=len, iter=iter, enumerate=enumerate, zip=zip, pop=collections.deque.popleft):
196 classes = self.classes
199 # shortcut for non-tos traffic
200 rv = pop(queues[iter(classes).next()])
204 if self.cycle_update:
206 filter(classes.__contains__, order)
207 for order in self.order
209 self.cycle = map(itertools.cycle, cycle)
210 self.cyclelen = map(len,cycle)
211 self.cycle_update = False
213 for prio, (cycle, cyclelen) in enumerate(zip(self.cycle, self.cyclelen)):
215 for i in xrange(cyclelen):
224 # Needs to update the cycle
226 self.cycle_update = True
228 raise IndexError, "pop from an empty queue"
230 def dump_stats(self, astats=astats, dstats=dstats, dump_count=dump_count):
231 if dump_count[0] >= 10000:
232 dstatsstr = "".join(['%s:%s\n' % (key, value) for key, value in dstats.items()])
233 astatsstr = "".join(['%s:%s\n' % (key, value) for key, value in astats.items()])
234 fd = open('dropped_stats', 'w')
235 iovec.writev(fd.fileno(), "Dropped:\n", dstatsstr, "Accepted:\n", astatsstr)
241 queueclass = ClassQueue
243 def init(size = 1000, classes = _classes, logdropped = 'False', red = True):
244 global _size, _classes, _logdropped
248 _logdropped = logdropped.lower() in ('true','1','on')
252 open('dropped_stats', 'w').close()