计算机网络 - STP 生成树协议

生成树协议

一个简单实现，单线程事件驱动模拟。

#include <cstdio>
#include <algorithm>
#include <set>
#include <list>
#include <string>
using namespace std;

const int MAX_VALUE = 2147483647;

struct BPDU {
    int rid;
    int cost;
    int sid;
    int port;
    friend bool operator < (BPDU a, BPDU b) {
        if(a.rid != b.rid) return a.rid < b.rid;
        if(a.cost != b.cost) return a.cost < b.cost;
        if(a.sid != b.sid) return a.sid < b.sid;
        if(a.port != b.port) return a.port < b.port;
        return true;
    }
};

list<pair<BPDU, int> > events;
set<int> net[201];
struct NetFlag {
    bool dp = true;
} netFlag[201];

struct Bridge {
    int id;
    int link[16];
    int cost[16];
    BPDU minBPDU;
    void receive(BPDU bpdu, int from) {
        int minValue = MAX_VALUE;
        for(int i=0; i<16; i++) {
            if(link[i] == from) {
                minValue = min(minValue, cost[i]);
            }
        }
        bpdu.cost += minValue;
        if(minBPDU < bpdu) return;
        minBPDU = bpdu;
        for(int i=0; i<16; i++) {
            if(link[i] == 0) continue;
            events.push_back(make_pair(BPDU{minBPDU.rid, minBPDU.cost, id, i}, link[i]));
        }
    }

} bridge[201];

void spaningTree() {
    for(int i=1; i<=200; i++) {
        for(int j=0; j<16; j++) {
            int linkNet = bridge[i].link[j];
            if(linkNet != 0) {
                events.push_back(make_pair(BPDU{i, 0, i, j}, linkNet));
            }
        }
    }
    while(events.size() != 0) {
        BPDU bpdu = events.front().first;
        int target = events.front().second;
        events.pop_front();
        for(auto it=net[target].begin(); it!=net[target].end(); it++) {
            bridge[*it].receive(bpdu, target);
        }
    }
}

void link(int b, int p, int l, int c) {
    bridge[b].link[p] = l;
    bridge[b].cost[p] = c;
    net[l].insert(b);
}

string role[201][16];

int main() {
    for(int i=1; i<=200; i++) {
        bridge[i].id = i;
        bridge[i].minBPDU = BPDU{i, 0, i, 0};
    }

    freopen("1.in", "r", stdin);
    int m; scanf("%d", &m);
    for(int i=1; i<=m; i++) {
        char opt[1024];
        scanf("%s", opt);
        int b, p, l, c;
        scanf("%d%d%d%d", &b, &p, &l, &c);
        link(b, p , l, c);
    }

    spaningTree();

    for(int i=1; i<=200; i++) {
        for(int j=0; j<16; j++) {
            role[i][j] = "BP";
        }
    }

    for(int i=1; i<=200; i++) {
        int rid = bridge[i].minBPDU.rid;
        int sid = bridge[i].minBPDU.sid;
        int port = bridge[i].minBPDU.port;
        int cost = bridge[i].minBPDU.cost;
        int toNet = bridge[sid].link[port];

        if(i != rid) {
            int minCost = MAX_VALUE, rp;
            for(int j=0; j<16; j++) {
                int linkNet = bridge[i].link[j];
                int linkCost = bridge[i].cost[j];
                if(linkNet == 0) continue;
                if(linkNet == toNet && linkCost < minCost) {
                    minCost = linkCost;
                    rp = j;
                }
            }
            role[i][rp] = "RP";
        }
    }

    for(int i=1; i<=200; i++) {
        if(net[i].size() == 0) continue;
        int minCost = MAX_VALUE, db, dp;
        for(auto it=net[i].begin(); it!=net[i].end(); it++) {
            int tb = *it;
            if(bridge[tb].minBPDU.cost < minCost) {
                minCost = bridge[tb].minBPDU.cost;
                db = tb;
            }
        }
        minCost = MAX_VALUE;
        for(int j=0; j<16; j++) {
            int linkNet = bridge[db].link[j];
            int linkCost = bridge[db].cost[j];
            if(linkNet == i && linkCost < minCost) {
                minCost = linkCost;
                dp = j;
            }
        }
        role[db][dp] = "DP";
    }

    for(int i=1; i<=200; i++) {
        for(int j=0; j<16; j++) {
            int linkNet = bridge[i].link[j];
            if(linkNet == 0) continue;
            printf("%d %d %d %s\n", i, j, linkNet, role[i][j].c_str());
        }
    }
}

附件下载

网络模型描述标准4.0(3).pdf
bridge.cpp