[bwm-tools-devel] COMMIT - r55 - in trunk: bwmd include lib

[SVN C. <sv...@li...>]

Author: nkukard
Date: 2005-01-21 08:46:58 +0200 (Fri, 21 Jan 2005)
New Revision: 55

Modified:
   trunk/bwmd/autoclass.c
   trunk/bwmd/ipq.c
   trunk/include/autoclass.h
   trunk/include/flow.h
   trunk/lib/xmlConf.c
Log:
* Misc optimizations and pre-tos work


Modified: trunk/bwmd/autoclass.c
===================================================================
--- trunk/bwmd/autoclass.c	2005-01-21 06:45:35 UTC (rev 54)
+++ trunk/bwmd/autoclass.c	2005-01-21 06:46:58 UTC (rev 55)
@@ -22,86 +22,204 @@
 */
 
 #include "autoclass.h"
+#include "flow.h"
 
 
-// Band calculation functions, tcp
-long int tcpPortToBand(long int bandNum, u_int16_t port)
+
+// Auto classify by port
+static unsigned char autoClassify_port(struct ip_packet_t *ip_packet, unsigned char prioClassifier)
 {
-	long int ret = bandNum;
+	unsigned char prio = 0;
+
+
+	// Priority calculation functions, tcp
+	static unsigned char tcpPortToPrio(u_int16_t port)
+	{
+		unsigned char ret = 0;
+			
+			
+		// Decide band to pump packet into	
+		switch (port)
+		{
+			// AUTH
+			case 113:
+				ret = 20;
+				break;
+			// SSH
+			case 22:
+			// TELNET
+			case 23:
+				ret = 25;
+				break;
+			// HTTP
+			case 80:
+			// PROXY?
+			case 8080:
+			case 3128:
+			case 3130:
+			// HTTPS
+			case 443:
+				ret = 65;
+				break;
+			// CVS
+			case 2401:
+				ret = 70;
+				break;
+			// POP3
+			case 110:
+			// IMAP
+			case 143:
+				ret = 75;
+				break;
+			// FTP
+			case 20:
+			case 21:
+				ret = 80;
+				break;
+		};
+	
+		return ret;
+	}
+
+	
+	// Priority calculation functions, udp
+	static unsigned char udpPortToPrio(u_int16_t port)
+	{
+		unsigned char ret = 0;
 		
 		
-	// Decide band to pump packet into	
-	switch (port)
+		// Decide band to pump packet into	
+		switch (port)
+		{
+			// DNS
+			case 53:
+				ret = 10;
+				break;
+			// NTP
+			case 123:
+				ret = 15;
+				break;
+			// RADIUS
+			case 1645:
+			case 1646:
+			case 1812:
+			case 1813:
+				ret = 30;
+				break;
+			default:
+				// Traceroute	
+				if (port >= 33434 && port <= 33465)
+					ret = 5;
+				break;
+		};
+	
+		return ret;
+	}
+
+
+	// Process a TCP packet
+	if (ip_packet->protocol == IPPROTO_TCP)
 	{
-		// AUTH
-		case 113:
-			ret = 20;
-			break;
-		// SSH
-		case 22:
-		// TELNET
-		case 23:
-			ret = 25;
-			break;
-		// HTTP
-		case 80:
-		// PROXY?
-		case 8080:
-		case 3128:
-		case 3130:
-		// HTTPS
-		case 443:
-			ret = 65;
-			break;
-		// CVS
-		case 2401:
-			ret = 70;
-			break;
-		// POP3
-		case 110:
-		// IMAP
-		case 143:
-			ret = 75;
-			break;
-		// FTP
-		case 20:
-		case 21:
-			ret = 80;
-			break;
-	};
+		struct tcphdr *tcph = (struct tcphdr *) (ip_packet + (ip_packet->ihl * 4));
+/*	
+		fprintf(stderr,"  tcp -> sport = %i, dport = %i, prec = 0x%x\n", ntohs(tcph->source), 
+			ntohs(tcph->dest), IPTOS_PREC(ip_packet->tos));
+*/
+		if (!(prio = tcpPortToPrio(ntohs(tcph->dest))))
+			prio = tcpPortToPrio(ntohs(tcph->source));
+	}
 
-	return ret;
+	// Process a ICMP packet
+	else if (ip_packet->protocol == IPPROTO_ICMP)
+	{
+//		struct icmphdr *icmph = (struct icmphdr *) (ip_packet + (ip_packet->ihl * 4));
+
+/*
+		fprintf(stderr,"something: icmp = %i, type = %i\n", icmph->code, icmph->type);
+*/
+		prio = 5;
+	}
+
+	// Process a UDP packet
+	else if (ip_packet->protocol == IPPROTO_UDP)
+	{
+		struct udphdr *udph = (struct udphdr *) (ip_packet + (ip_packet->ihl * 4));
+/*	
+		fprintf(stderr,"  udp -> sport = %i, dport = %i\n", ntohs(udph->source), 
+			ntohs(udph->dest));
+*/
+		if (!(prio = udpPortToPrio(ntohs(udph->dest))))
+			prio = udpPortToPrio(ntohs(udph->source));
+	}
+
+	return prio;
 }
+
 	
-// Band calculation functions, udp
-long int udpPortToBand(long int bandNum, u_int16_t port)
+// Auto classify by ip header TOS value
+static unsigned char autoClassify_tos(struct ip_packet_t *ip_packet, unsigned char prioClassifier)
 {
-	long int ret = bandNum;
-	
-	
-	// Decide band to pump packet into	
-	switch (port)
+	unsigned char prio = 0;
+	// Get type of  service
+	unsigned char tos = IPTOS_TOS(ip_packet->tos);
+
+
+	// Decide what we doing...
+	if (tos == IPTOS_LOWDELAY)	
 	{
-		// DNS
-		case 53:
-			ret = 10;
-			break;
-		// NTP
-		case 123:
-			ret = 15;
-			break;
-		// RADIUS
-		case 1645:
-		case 1646:
-		case 1812:
-		case 1813:
-			ret = 30;
-			break;
-	};
-	
-	if (port >= 33434 && port <= 33465)
-		ret = 5;
-	
-	return ret;
+/*
+ * 1. LOW DELAY
+ *  - PRIO 10
+ * 	- high drop probability
+ */
+	}
+	else if (tos == IPTOS_THROUGHPUT)
+	{
+/*
+ * 2. THROUGHPUT
+ *  - long queue?
+ *  - low drop probability
+ */
+	}
+	else if (tos == IPTOS_RELIABILITY)
+	{
+/*
+ * 3. RELIABILITY
+ *  - low drop probability
+ */
+	}
+	else if (tos == IPTOS_MINCOST)
+	{
+/*
+ * 4. MIN COST
+ *  - PRIO 90
+ *  - high drop probability
+ */
+	}
+
+	return prio;
 }
 
+
+// Auto classify packet and return priority (1 - best, 100 - worst)
+unsigned char autoClassify(struct ip_packet_t *ip_packet, unsigned char prioClassifier)
+{
+	unsigned char prio;
+
+
+	// Classify by port
+	if (prioClassifier == AUTOCLASS_PORT)
+		prio = autoClassify_port(ip_packet,prioClassifier);
+	// Classify by TOS
+	else if (prioClassifier == AUTOCLASS_TOS)
+		prio = autoClassify_tos(ip_packet,prioClassifier);
+	// Default - this will basically match if we have AUTOCLASS_NONE
+	else
+		prio = 50;
+
+	return prio;
+}
+
+
+
+

Modified: trunk/bwmd/ipq.c
===================================================================
--- trunk/bwmd/ipq.c	2005-01-21 06:45:35 UTC (rev 54)
+++ trunk/bwmd/ipq.c	2005-01-21 06:46:58 UTC (rev 55)
@@ -22,6 +22,7 @@
 */
 
 
+#include <math.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
@@ -31,7 +32,10 @@
 #include "libipq.h"
 
 
+#define QUEUE_HEAD 1
+#define QUEUE_TAIL 2
 
+
 // Destroy the ipq handle
 static void destroyIPQHandle(struct ipq_handle *h)
 {
@@ -91,6 +95,8 @@
 	int status;
 	int result;
 	int drop = 0;
+	// Default to inserting at queue tail
+	unsigned char queuePos = QUEUE_TAIL;
 
 
 	// Our find functions
@@ -138,94 +144,171 @@
 	if (!foundQueue)
 	{
 		struct ip_packet_t *ip_packet = (struct ip_packet_t *) packet->payload->payload;
-		long int bandNum = -1;
-		
+		unsigned char prio = 0;
+
 /*		
 		fprintf(stderr,"auto packet queue -> protocol = %i, src = %i.%i.%i.%i, dest = %i.%i.%i.%i, tos = 0x%x\n", ip_packet->protocol, 
 				ip_packet->u_saddr.addr.a, ip_packet->u_saddr.addr.b, ip_packet->u_saddr.addr.c, ip_packet->u_saddr.addr.d, 
 				ip_packet->u_daddr.addr.a, ip_packet->u_daddr.addr.b, ip_packet->u_daddr.addr.c, ip_packet->u_daddr.addr.d, 
 				IPTOS_PREC(ip_packet->tos));
-*/				
-		// Process a TCP packet
-		if (ip_packet->protocol == IPPROTO_TCP)
-		{
-			struct tcphdr *tcph = (struct tcphdr *) (packet->payload->payload + (ip_packet->ihl * 4));
-/*	
-			fprintf(stderr,"  tcp -> sport = %i, dport = %i, prec = 0x%x\n", ntohs(tcph->source), 
-				ntohs(tcph->dest), IPTOS_PREC(ip_packet->tos));
 */
-			bandNum = tcpPortToBand(bandNum,ntohs(tcph->dest));
-			if (bandNum == -1)
-				bandNum = tcpPortToBand(bandNum,ntohs(tcph->source));
+		
+		prio = autoClassify(ip_packet,foundFlow->prioClassifier);
+			
+		// If we didn't get anything set band number to 50, 50/50	
+		if (prio == 0)
+			prio = 50;
 
+		foundQueue = foundFlow->pktQueues[prio];
+	}
+	
+	
+	// Lock flow before we fuck with it
+	g_mutex_lock(foundQueue->lock);
+	g_mutex_lock(P_FLOW(foundQueue,lock));
+
+
+/*  This is my current work on implementing RED - nk...@lb... */
+#if 0	
+	{
+		/* Saved variables */
+		unsigned int avg;  // Average queue size
+		unsigned long int q_time;  // Last time a packet was received
+		unsigned int count;  // Packets since last one marked
+		/* Fixed params */
+		Wq;  // Weight of queue
+		min_th;  // Min threshold of queue
+		max_th;  // Max threshold of queue
+		max_p;  // Max value for Pb
+		/* Other */
+		float Pa;  // Current packet marking probability
+		q;  // Current queue size
+		time;  // Current time
+		float Pb;
+
+
+		avg = 0;
+		count = -1;
+
+
+		LOOP WITH PACKETS
+
+		calculate new average
+		
+		if queue is non empty
+		{
+			// Exponential weighted moving average (EWMA)	
+			avg = (1 - Wq) * avg + Wq * q;
 		}
+		else
+		{
+		}
 
-		// Process a ICMP packet
-		if (ip_packet->protocol == IPPROTO_ICMP)
+		if (min_th <= avg && avg < max_th)
 		{
-/*
-			struct icmphdr *icmph = (struct icmphdr *) (packet->payload->payload + (ip_packet->ihl * 4));
+			count++;
 
-			fprintf(stderr,"something: icmp = %i, type = %i\n", icmph->code, icmph->type);
-*/
-			bandNum = 5;
+			Pb = max_p * (avg - min_p) / (max_th - min_th);
+			// Favour small packets
+			Pb = Pb * (packet_size / max_packet_size);
+		
+			Pa = Pb / (1 - count & Pb);
+		
+			// FIXME - mark packet with Pa
+				mark packet
+				count = 0;
 		}
-
-		// Process a UDP packet
-		if (ip_packet->protocol == IPPROTO_UDP)
+		else if (max_th <= avg)
 		{
-			struct udphdr *udph = (struct udphdr *) (packet->payload->payload + (ip_packet->ihl * 4));
-/*	
-			fprintf(stderr,"  udp -> sport = %i, dport = %i\n", ntohs(udph->source), 
-				ntohs(udph->dest));
-*/
-			bandNum = udpPortToBand(bandNum,ntohs(udph->dest));
-			if (bandNum == -1)
-				bandNum = udpPortToBand(bandNum,ntohs(udph->source));
+			// FIXME - mark packet;
+			count = 0;	
 		}
-	
-		// If we didn't get anything set band number to 50, 50/50	
-		if (bandNum == -1)
-			bandNum = 50;
+		else
+			count = -1;
 
-		foundQueue = foundFlow->pktQueues[bandNum];
+		if queue is empty
+			q_time = time();
+		
+		CONTINUE LOOP
+		
+
+		
 	}
+#endif
+
+
+
+
+
+
 	
-	
-	// Lock flow before we fuck with it
-	g_mutex_lock(foundQueue->lock);
-	g_mutex_lock(P_FLOW(foundQueue,lock));
-
 	// Check first of all if we fucked over our one of our queue limits
 	if (will_exceed_pkt_queue(foundQueue,PKT_SIZE(packet)) || 
 			will_exceed_flow_queue(foundQueue->parentFlow,PKT_SIZE(packet)))
 		drop = 1;
+	// Or checkif we fell over our soft curve, slow start algo
+	else
+	{
+		long int maxQueueSize, curQueueSize, avgQueueSize;
 
 
+		/* Check if we must use our queue's size or parent flow queue size */
 #if 0
-	// Check second of all if we fucked our min threshold over
-	else if (TH_EXCEEDED(foundQueue,min_th))
-	{
-		int j = 1 + (int) (10.0 * rand() / (RAND_MAX + 1.0));
-
-		if (TH_EXCEEDED(foundQueue,max_th))
+		if (foundQueue->maxSize)
 		{
-			if (j > 5)
-				drop = 1;
+	   		maxQueueSize = foundQueue->maxSize;
+			curQueueSize = foundQueue->curSize;
 		}
 		else
 		{
-			if (j < 3)
-				drop = 1;
+#endif
+	   		maxQueueSize = P_FLOW(foundQueue,maxQueueSize);
+			curQueueSize = P_FLOW(foundQueue,curQueueSize);
+			avgQueueSize = P_FLOW(foundQueue,avgQueueSize);
+#if 0
 		}
-	}
 #endif
+		
+		// Check if we have limits to exceed
+		if (maxQueueSize && curQueueSize > 0 && avgQueueSize > 0)
+		{
+			float avgProb = 0, curProb = 0, prob = 0;
+			int min_th = 10;
+			double drand = drand48();
+			
 
+			// nice soft curve flow based on average queue size, starts slow, increases fast will hit 100% probability at 75%	
+			// FIXME - this is based on the flow's queue size, it should be configurable to the queue's queue size
+			//avgProb = powf((P_FLOW(foundQueue,avgQueueSize) / maxQueueSize * 1.25),3);
+			avgProb = powf((((float) avgQueueSize / (float) maxQueueSize) * 1.25),3);
+			// current queue size & threshold curve... sort of flatish, but starting slowish
+			curProb = powf(((float) curQueueSize / (float) maxQueueSize) + powf(((float) min_th / (float) 150),3),2) / 2;
+			prob = avgProb + curProb;
+			// Check if we should drop packet
+			drop = drand < prob;
+/*
+			logMessage(LOG_DEBUG, "%s: Packet Drop Probability: %f (%li:%li) %f (%li:%li)\t%f\t%i\n",
+					P_FLOW(foundQueue,flowName),
+					avgProb,avgQueueSize,maxQueueSize,
+					curProb,curQueueSize,maxQueueSize,
+					avgProb + curProb,
+					drop);
+*/
+		}
+
+	}
+	
 	// Check if we must pass the packet
 	if (!drop)
 	{
 		// Lock, queue... adjust stats
-		foundQueue->packets = g_list_append(foundQueue->packets,packet);
+		if (queuePos == QUEUE_TAIL)
+			foundQueue->packets = g_list_append(foundQueue->packets,packet);
+		else if (queuePos == QUEUE_HEAD)
+		{
+			// FIXME - APPEND TO LAST QUEUE
+		}
+
 		foundQueue->curSize += PKT_SIZE(packet);
 		P_FLOW(foundQueue,curQueueSize) += PKT_SIZE(packet);
 		foundQueue->curLen++;
@@ -327,7 +410,6 @@
 				break;
 
 			case IPQM_PACKET: 
-					
 				// Get packet details...
 				g_mutex_lock(runnerData->IPQLock);
 				m = ipq_get_packet(buf);

Modified: trunk/include/autoclass.h
===================================================================
--- trunk/include/autoclass.h	2005-01-21 06:45:35 UTC (rev 54)
+++ trunk/include/autoclass.h	2005-01-21 06:46:58 UTC (rev 55)
@@ -26,12 +26,17 @@
 
 
 #include <stdlib.h>
+#include "flow.h"
 
-// Band calculation functions, tcp
-long int tcpPortToBand(long int bandNum, u_int16_t port);
 
-// Band calculation functions, udp
-long int udpPortToBand(long int bandNum, u_int16_t port);
+// Classificaiton types...
+#define AUTOCLASS_NONE  0
+#define AUTOCLASS_PORT	1
+#define AUTOCLASS_TOS	2
 
 
+// Auto classify packet and return priority (1 - best, 100 - worst)
+unsigned char autoClassify(struct ip_packet_t *ip_packet, unsigned char prioClassifier);
+
+
 #endif

Modified: trunk/include/flow.h
===================================================================
--- trunk/include/flow.h	2005-01-21 06:45:35 UTC (rev 54)
+++ trunk/include/flow.h	2005-01-21 06:46:58 UTC (rev 55)
@@ -90,7 +90,7 @@
 
 	// Shaping	
 	struct flow_t *parent;  // STATIC, not specified, determined - pointer to parent
-	int prio;  // STATIC - Flow priority
+	unsigned char prioClassifier;  // STATIC - Flow priority auto classifier
 	unsigned long int nfmark;  // STATIC - nfmark value i must match auto to queues
 	long int maxQueueSize;  // STATIC - max length in bytes of queue
 	long int maxQueueLen;  // STATIC - and/or length in items
@@ -118,6 +118,7 @@
 
 	float curThroughput; // Current throughput
 	unsigned int curThroughputAge; // How many microseconds since last throughput update
+	unsigned int avgQueueSize;  // Average queue size
 	struct timeval lastThroughputUpdate;  // Last time the throughput was updated
 	
 	unsigned int accumMs;  // Accumulated number of microseconds

Modified: trunk/lib/xmlConf.c
===================================================================
--- trunk/lib/xmlConf.c	2005-01-21 06:45:35 UTC (rev 54)
+++ trunk/lib/xmlConf.c	2005-01-21 06:46:58 UTC (rev 55)
@@ -29,6 +29,7 @@
 #include <time.h>
 #include <libxml/xmlmemory.h>
 #include <libxml/parser.h>
+#include "autoclass.h"
 #include "common.h"
 #include "flow.h"
 #include "xmlConf.h"
@@ -415,6 +416,8 @@
 			done = 1;
 		if (!done && !xmlStrcmp(key,"report-timeout"))
 			done = 1;
+		if (!done && !xmlStrcmp(key,"prio-classifier"))
+			done = 1;
 		if (!done && !xmlStrcmp(key,"burst-rate"))
 			done = 1;
 		if (!done && !xmlStrcmp(key,"max-rate"))
@@ -645,6 +648,7 @@
 		long int maxRate,
 		long int burstRate,
 		unsigned long int nfmark,
+		unsigned char prioClassifier,
 		float parent_th,
 		int reportTimeout)
 {
@@ -676,6 +680,9 @@
 	flow->burstRate = burstRate;
 	flow->nfmark = nfmark;
 
+	// Set the priority classifier
+	flow->prioClassifier = prioClassifier;
+
 	flow->parent_th = parent_th;
 	
 	flow->counterTimeout = reportTimeout;
@@ -720,6 +727,7 @@
 	gettimeofday(&flow->lastThroughputUpdate,NULL);
 	flow->curThroughputAge = 0;
 	flow->curThroughput = 0;
+	flow->avgQueueSize = 0;
 	// Set last time we calculated credit and the rest...
 	flow->accumMs = 0;
 	gettimeofday(&flow->lastCreditCalc,NULL);
@@ -746,22 +754,18 @@
 	if (flow->maxQueueLen == -1)
 	{
 		if (flow->maxRate != 0)
-			flow->maxQueueLen = 5;  // Seems an OK value for normal use?
+			flow->maxQueueLen = ((flow->burstRate + flow->maxRate) / 2 / 750)  * 2;  // Seems an OK value for normal use?
 		else
 			flow->maxQueueLen = 0;
 	}
 	if (flow->maxQueueSize == -1)
 	{
 		if (flow->maxRate != 0)
-			flow->maxQueueSize = 4096;  // Let us queue at least 2 big packets and some small ones
+			flow->maxQueueSize = (flow->burstRate + flow->maxRate);  // Normal use, this should be ok?
 		else
 			flow->maxQueueSize = 0;
 	}
 
-	// Calculate our thresholds
-	//flow->min_th = (flow->maxRate / 750);
-	//flow->max_th = (flow->maxRate / 750) * 4;
-
 	// Blank all queues
 	for (i = 0; i < NUM_PRIO_BANDS; i++) 
 	{
@@ -928,6 +932,7 @@
 					char *p;
 					long int statsLen, maxQueueSize, maxQueueLen, maxRate, burstRate, reportTimeout;
 					unsigned long int nfmark;
+					unsigned char prioClassifier = AUTOCLASS_PORT;
 					float parent_th;
 
 					
@@ -968,9 +973,24 @@
 						reportTimeout = 30;
 					}
 
+					// Work out automatic classifier to use
+					if ((p = g_hash_table_lookup(tagProperties,"prio-classifier")) != NULL)
+					{
+						if (strcasecmp(p,"tos") == 0)
+							prioClassifier = AUTOCLASS_TOS; 
+						else if (strcasecmp(p,"port") == 0)
+							prioClassifier = AUTOCLASS_PORT; 
+						else if (strcasecmp(p,"none") == 0)
+							prioClassifier = AUTOCLASS_NONE; 
+						else
+							fprintf(stderr,"ERROR: %s - Tag value for \"prio-classifier\" is invalid, please read manual\n",flowName);
+					}
+					else
+						prioClassifier = AUTOCLASS_NONE;
+					
 					// Create our flow
 					newFlow = createFlow(flowName,parentFlow,statsLen,maxQueueSize,maxQueueLen,maxRate,burstRate,nfmark,
-							parent_th,reportTimeout);
+							prioClassifier,parent_th,reportTimeout);
 					
 					flows = g_list_append(flows,newFlow);
 				}