This is automatically generated documentation. Edit after the "COMMENTS" heading; changes to the main body will be lost.

InferIPAddrColors Element Documentation


InferIPAddrColors -- Click element; Infer a graph-coloring for IP addresses.



Ports: 1 input, 1 output
Processing: agnostic
Drivers: userlevel
Package: models


Takes IP packets on its single input and emits them unchanged, while inferring a graph coloring for the IP addresses visible on the packets. InferIPAddrColors assumes that all packets come from a single link, and that any address corresponds to at most one side of the link. Call the sides red and blue. Then, every packet has a red source address and a blue destination address, or vice versa (assuming no source addresses are forged). The InferIPAddrColors element attempts to infer which addresses are red and which are blue. Output the coloring by calling the write_file or write_text_file handler. Keyword arguments are:

Boolean. If false, packets are passed through without affecting the coloring. Default is true.
Filename. Read this color file for seed colors.


write_text_file (write-only)
Argument is a filename, or `-' for standard output. Writes the current color assignment in text to the specified file.
write_file (write-only)
Argument is a filename, or `-' for standard output. Writes the current color assignment in binary to the specified file.
active (read/write)
Returns or sets the ACTIVE parameter.
clear (write-only)
Erases all accumulated color state when written.
stop (write-only)
Stops the driver, and sets ACTIVE to false, when written.
ncolors (read-only)
Returns the current number of nominal colors. (A written file will have fewer colors, since this handler doesn't compress the color count using aggregation.)


InferIPAddrColors works incrementally, but its algorithm is equivalent to this offline algorithm. Initialize a working set W with all IP addresses seen. Repeat these steps until W is empty:

Initialize two empty sets R and B, corresponding to new "red" and "blue" colors.
Remove a single address from W and add it to R (color it red).
Remove an address X from W, where the trace pairs X an element of either R or B. That is, some packet had a red (or blue) address as source address and X as destination address, or vice versa. Add X to the other color set, so if it was paired with a red address, add it to B. If X was paired with both red and blue addresses, then the address graph isn't consistent with our assumptions; add it to either R or B.
Repeat step 3 until no elements of W were paired with previously colored addresses by the trace. These steps result in an initial address coloring, possibly using more than 2 colors. The next step reduces this color count as much as possible using topological assumptions, namely that red colors cluster close to themselves in the address space (and the same for blue).

Pick a color pair and bless them as RR and BB, primary red and primary blue. We'll go over the remaining color pairs and merge them into RR and BB. (Conceivably a bad choice of RR and BB might screw up the results.)
Initialize a prefix level P to 31.
Search for a residual color X, not RR and BB, so that some P-aggregate contains at least one packet colored X; any number of packets with other residual colors; and some packets with at most one of the colors RR and BB. That is, the aggregate can contain RR packets but no BB packets, or vice versa. If you find such a residual color, then merge that color into the primary color that it shares an aggregate with, and merge its complement into the other primary color. For example, if X shares a P-aggregate with RR (but not BB), then merge X with RR and X's complement with BB. Then return to step 2. If you find no such color, then decrement P and try step 3 again, unless P is 8 or less, in which case quit. As a special case, ignore residual colors X whose complements share a P-aggregate with the same primary color as X. This will merge most colors together into a single color pair. There may be some residuals.


The write_text_file handler writes a text file whose lines consist of an IP address, a space, and a color number. The write_file handler writes a binary file, preceded by several lines of text boilerplate. The binary data starts after a $packed_be or $packed_le line, and consists of many 8-byte records; the first 4 bytes are the IP address in host order, the second 4 the color. Byte order is big-endian for $packed_be and little-endian for $packed_le.


IPAddrColorPaint, TestIPAddrColors

Generated by 'click-elem2man' from 'inferipaddrcolors.hh' on 24/Feb/2006.


elements/inferipaddrcolors.txt · Last modified: 2006/02/24 10:50 by clickdoc
Recent changes RSS feed Driven by DokuWiki