Monday, September 21, 2009

IXM and Self-Discovering Topology

The Illuminato X Machina's are modular, which means they can be connected to each other to distribute tasks and to adapt to their environment (or ecosystem, if you will). This is a little blog about how I wrote a sketch that makes all the IXM's act like a team to generate a network map representation of how they're connected to each other.

That way, something like this (note a 3d printed model of the Empire State building that Bre printed):

Turns into a representation on the computer like this:

Here's an up-close screenshot that I made with Mathematica (I wish I knew Octave or SciPy better, but I taught myself Mathematica a long time ago for some math homework in school, and I don't even think SciPy existed back then):

Here's a video of me YELLING REALLY LOUD BECAUSE I DIDN'T REALIZE how well the junky little video recorder I have could pick up my talking with the music right near me (ps thanks a lot, sony for making me carry around your stupid proprietary upload cable everywhere):

This is probably my favorite video ever, because it shows the Gradient auto-discovering topology sketch gradually figuring itself out, and updating as it gets new packets in real time:

So basically, if I had gray hair, and was born in the 1930's and worked at Los Alamos National Labs building supercomputers all the time, I would probably call this something like a "self-discovering topologically ambivalent computer achitecture with peer-to-peer team-based self-discovery." But I'm not, I don't, I didn't and so instead this is just "a simple little sketch that let's you connect the IXM's in any configuration, and it prints on the screen a network map version of the physical arrangement of the IXM nodes."

How I did it...

I adapted the packet gradient sketch (more on that to come, but if you're on the mailing list, you probably saw me post it a week or two ago), and I made a simple packet system that does the following:

  • "qz0" - reset the grid
  • "t0" - establish a gradient back to the PC
  • "i0" - hey, every IXM cell go generate a random number between 1-1000 and store it
  • "qzN" - tell me (the PC) what the cell ID is for the IXM connected directly to me (PC)
  • "qn0" - ok, now every IXM cell in the grid, exchange id's with any neighboring grids you're connected to
  • "ndN1" - I'm the PC, so my id is '1', and I'm at your North edge
  • "qp0" - ok, now everyone report up which id's you're connected to in the format of E123|456, where 123 is your id and 456 is the id of the IXM cell to the East of you
  • "qz0" - reset all your id's and get ready for the next thing I want you to do, which is probably go generate another edgelist and send it back up the gradient after I changed your layout by reconnecting you all in a different way
These are actually just typed into the Arduino-Illuminato IDE in the serial terminal, or even just with hyperterminal. But you can see from the mathematica files that I used a modified version of what someone wrote up on the Arduino playground for how to talk over serial using Mathematica.

I then get this whole set of edgelist pairs back over the PC serial port, and I used this little bit of Mathematica code to make it prettyful:

dat = ((FromCharacterCode[#]) & /@ {GetPort[1]})[[1]];

datpack = StringSplit[dat, "\n"];

tmpdat = Select[datpack, (Length[StringCases[#, "|"]] > 0) &];

Select[((#[[1]]) & /@
RegularExpression["qr.(\\d+?)\\|(\\d+)"] -> {"$1", "$2"}]),
(#[[2]] != "0") &];

(#[[1]] -> #[[2]]) & /@
Select[((#[[1]]) & /@
RegularExpression["qr.(\\d+?)\\|(\\d+)"] -> {"$1", "$2"}]),
(#[[2]] != "0") &],
PlotStyle -> {LightGray, Dashed, PointSize[Large], Arrowheads[.02]},
DirectedEdges -> True, EdgeRenderingFunction -> (Arrow[#1, 0.1] &),
VertexRenderingFunction ->
Function[{p, l}, {RGBColor[240, 173, 0], Point[p],
Text[l, {p[[1]], p[[2]] + .1}]}]

I've uploaded the sketch file up to the Liquidware "app store" over here, and I made a new icon for any app that I write for the IXM:

And here are some more screenshots of different topologies Chris, Matt, and I were experimenting with on a desk at Makerbot:

The "magic" all happens in the sketch with this code right here, which shows off the packet functions that Dave wrote overnight in his sleep :-)

//expect to parse packet of "qxN\n" for send me your id, or "qn0\n" for get your neighbors' id's
//or "qd4214\n" for the actual id, or "qs123\n" to set your id to the number specified
//or "qp0\n" for send all your neighbor info packets back
//or "qz\n" for reset
void doNeighborIdentify(u8 * packet) {
u32 sourceface, thispacketmyngen, thispacketmypgen, thispacketmyrgen;
int tempface;
long tempnid;
u8 t;

if (packetLength(packet) < 2) return;
sourceface = Body.source();

//reset gradient signal tokens
if (packet[1] == 'z') {
thispacketmyrgen = packet[2] - 48;
if (thispacketmyrgen <>=1000)) {
//only run request on the first packet i get with lowest n
//or if a second has ellapsed
myrgen = thispacketmyrgen;
last_millis_reset_packet = millis();
myidgen = MAXNBYNSIZE;
//myrgen = MAXNBYNSIZE;
deus_terminus_hop[DEUSEAST] =MAXNBYNSIZE;
deus_terminus_hop[DEUSWEST] =MAXNBYNSIZE;
neighbor_ids[DEUSNORTH]=0; neighbor_ids[DEUSSOUTH]=0; neighbor_ids[DEUSEAST]=0; neighbor_ids[DEUSWEST]=0;

//myidgen, myngen, mypgen, myrgen
if(sourceface != NORTH) { facePrint(NORTH,"qz"); facePrint(NORTH,myngen+48+1); facePrintln(NORTH); };
if(sourceface != SOUTH) { facePrint(SOUTH,"qz"); facePrint(SOUTH,myngen+48+1); facePrintln(SOUTH); };
if(sourceface != EAST) { facePrint(EAST,"qz"); facePrint(EAST,myngen+48+1); facePrintln(EAST); };
if(sourceface != WEST) { facePrint(WEST,"qz"); facePrint(WEST,myngen+48+1); facePrintln(WEST); };
//send me your id in a packet of "qdN4214\n" for example
if (packet[1] == 'x') {
if (packet[2]=='N') facePrint(sourceface,"N");
if (packet[2]=='S') facePrint(sourceface,"S");
if (packet[2]=='E') facePrint(sourceface,"E");
if (packet[2]=='W') facePrint(sourceface,"W");
facePrint(sourceface,myid); facePrintln(sourceface);
//set my id to the number you specified
if (packet[1] == 's') {
//set my neighbor_id's array to the id's of my neighbors
if (packet[1] == 'd') {
if (packet[2]=='N') neighbor_ids[DEUSNORTH] = tempnid;
if (packet[2]=='S') neighbor_ids[DEUSSOUTH] = tempnid;
if (packet[2]=='E') neighbor_ids[DEUSEAST] = tempnid;
if (packet[2]=='W') neighbor_ids[DEUSWEST] = tempnid;
//query my neighbors, then propagate the requst outwards
if (packet[1] == 'n') {
thispacketmyngen = packet[2] - 48;
if (thispacketmyngen < myngen ) {//only run requst on the first packet i get with lowest n
myngen = thispacketmyngen;
//query my neighbors
//propagate the request outwards
if(sourceface != NORTH) {
facePrint(NORTH,"qn"); facePrint(NORTH,myngen+48+1); facePrintln(NORTH);
if(sourceface != SOUTH) {
facePrint(SOUTH,"qn"); facePrint(SOUTH,myngen+48+1); facePrintln(SOUTH);
if(sourceface != EAST) {
facePrint(EAST,"qn"); facePrint(EAST,myngen+48+1); facePrintln(EAST);
if(sourceface != WEST) {
facePrint(WEST,"qn"); facePrint(WEST,myngen+48+1); facePrintln(WEST);

//send neighbor packet pairs back
if (packet[1] == 'p') {
thispacketmypgen = packet[2] - 48;
if (thispacketmypgen < mypgen ) {
mypgen = thispacketmypgen;
//print up my report-outs
ledOff(redPin); ledOff(bluePin); ledOn(greenPin);
if (neighbor_ids[DEUSNORTH] != 0) facePrintf(sourceface,"qrN%d|%d\n",myid,neighbor_ids[DEUSNORTH]);
if (neighbor_ids[DEUSSOUTH] != 0) facePrintf(sourceface,"qrS%d|%d\n",myid,neighbor_ids[DEUSSOUTH]);
if (neighbor_ids[DEUSEAST] != 0) facePrintf(sourceface,"qrE%d|%d\n",myid,neighbor_ids[DEUSEAST]);
if (neighbor_ids[DEUSWEST] != 0) facePrintf(sourceface,"qrW%d|%d\n",myid,neighbor_ids[DEUSWEST]);
//propagate the request outwards
if(sourceface != NORTH) {
facePrint(NORTH,"qp"); facePrint(NORTH,mypgen+48+1); facePrintln(NORTH);
if(sourceface != SOUTH) {
facePrint(SOUTH,"qp"); facePrint(SOUTH,mypgen+48+1); facePrintln(SOUTH);
if(sourceface != EAST) {
facePrint(EAST,"qp"); facePrint(EAST,mypgen+48+1); facePrintln(EAST);
if(sourceface != WEST) {
facePrint(WEST,"qp"); facePrint(WEST,mypgen+48+1); facePrintln(WEST);
//i got a report-out packet, send it back to the path of the deus, least-hop gradient
if (packet[1] == 'r') {
tempface = getDeusMinHopDir(); //direction of upstream gradient


Just in case, here is a link to more Flickr pictures, and some other videos I took while at Makerbot.

A video of me spreading new code through the IXM grid like an infection

A video of the gradient sketch

A really simple gradient sketch video

Enjoy :) And thanks again Bre for letting Chris, Matt, and me hang out at Makerbot on Saturday!


Unknown said...

looks awesome!!!
soooooo upset i missed it...

Matt said...

ha you shouldn't be tooo sad, i mean you were at maker faire rhode island, after all, weren't you? wow, we were like all over new england this weekend :) just needed someone in like maine, and there'd have been someone in each of the northeaster ocean-bound states simultaneously... ha

Chris said...

Let the video show that I stole your gradient! You must be cautious, because now I command one of the largest tribes of Illuminato X Machina's!

Less aware of their surroundings, they use their powers for what "they think" is good.

Matt said...

haha right... actually that's a good point, i'll upload a blog post on the gradient stealer sketch like tomorrow or the day after...