ポエニーのネットワーク図

ポエニーのネットワークをgraphvizで書いてみました。(私の思うWinnyネットワーク)
unstructuredなP2Pのネットワークは、ある程度のランダムな要素で構成されるので、パワーポイントやワード図で手書きするとリアリティに欠けます。
そこで、前に熱く語っていた、シュミレータ(のようなもの)で仮想的なネットワークを作った後に、ノードを辿りながらdotスクリプトを吐き出して、それを画像に変換するという方法を試してみました。

大きい画像f:id:ultraist:20060214194414p
別のパターン:f:id:ultraist:20060214204422p

作るたびに違ったネットワークが作られるので、何度か試しているとネットワークの特徴が見えてきておもしろいです。

スクリプト生成用ソースコード↓

// poenynet.d
import std.stdio;
import std.stream;
import std.random;

const int[]       SPEED_LIST      = [15, 50, 120, 500, 1000];
const uint        NODE_NUM        = 50;
const uint        INIT_NODE_NUM   = 5;

int main()
{
    PoenyNode[NODE_NUM]         nodes;
    PoenyNode[INIT_NODE_NUM]    initial_node;
    uint    i = 0;
    bool    processing;
    
    // ノード初期化
    foreach (inout PoenyNode e; nodes) {
        e = new PoenyNode(SPEED_LIST[rand() % SPEED_LIST.length]);
        
        if (i < INIT_NODE_NUM) {
            initial_node[i] = e;
        } else {
            foreach (PoenyNode e; initial_node) {
                nodes[i].nodeMap[e.no] = e;
            }
        }
        ++i;
    }
    for (i = 0; i < INIT_NODE_NUM; ++i) {
        foreach (PoenyNode e; initial_node) {
            nodes[i].nodeMap[e.no] = e;
        }
    }
    
    // ネットワーク構築
    do {
        processing = false;
        foreach (PoenyNode e; nodes) {
            if (! e.connectionFull) {
                e.connect();
                if (! e.connectionFull) {
                    processing = true;
                }
            }
        }
    } while (processing);
    
    // 結果出力
    makeDotScript(nodes);
    
    return 0;
}

// dotスクリプト生成
void makeDotScript(PoenyNode[] nodes)
{
    File dot = new File("poeny.dot", FileMode.OutNew);
    
    dot.writef("digraph poenyNetwork {\n");
    foreach (PoenyNode node; nodes) {
        foreach (PoenyNode upper; node.upstream.values) {
            dot.writef("\t\"%s (%sKB/S)\" -> \"%s (%sKB/S)\";\n",
                node.no, node.speed, upper.no, upper.speed);
        }
    }
    
    dot.writef("}\n");
    
    dot.close();
}

// 仮想ポエニーノード
class PoenyNode
{
protected:
    static uint     s_no            = 0;
    const uint      UPSTREAM_MAX    = 2;
    const uint      DOWNSTREAM_MAX  = 5;
    const uint      NODE_NUM        = 5;
    
    override int opCmp(Object rhs)
    {
        return (cast(PoenyNode)rhs).speed - speed;
    }
    
    bool isUpstreamNode(PoenyNode node)
    {
        if (speed * 0.8 > node.speed 
            || speed * 4.3 < node.speed)
        {
            return false;
        }
        
        return true;
    }
    
public:
    uint            no;
    int             speed;
    PoenyNode[uint] upstream;
    PoenyNode[uint] downstream;
    PoenyNode[uint] nodeMap;
    
    bool connect()
    {
        PoenyNode node;
        
        if (nodeMap.length == 0) {
            return false; // もうダメポ
        }
        
        node = nodeMap.values.sort[0];
        node.nodeMap[no] = this;
        
        if (node !is this
            && isUpstreamNode(node) 
            && node.downstream.length < DOWNSTREAM_MAX
            && (no in node.downstream) == null
            && (no in node.upstream) == null)
        {
            bool ack = true;
            
            if (node.downstream.length > DOWNSTREAM_MAX * 0.8) {
                if (rand() % 2) {
                    ack = false;
                }
            }
            if (ack) {
                node.downstream[no]  = this;
                upstream[node.no]    = node;
                
                return true;
            }
        }
        
        if (node.nodeMap.length > NODE_NUM) {
            PoenyNode[] values = node.nodeMap.values;
            for (int i = 0; i < NODE_NUM; ++i) {
                uint index = rand() % values.length;
                nodeMap[values[index].no] = values[index];
            }
        } else {
            foreach (PoenyNode e; node.nodeMap) {
                nodeMap[e.no] = e;
            }
        }
        if ((node.no in nodeMap) != null) {
            nodeMap.remove(node.no);
        }
        
        return false;
    }
    
    bool connectionFull()
    {
        if (upstream.length < UPSTREAM_MAX) {
            return false;
        }
        
        return true;
    }
    
public:
    this(int speed)
    {
        this.speed     = speed;
        no             = s_no++;
    }
}

あまり深く考えずにrand()を使っているので、5回ほどトライしないとネットワークが完全に作れませんでした(完了せず無限ループする･･)。回線速度の分布も完全にランダムにしています。
ネットワークは、回線速度によって階層化され、最上の1000KB/Sノードは互いに繋がりあっているのが分かります。