source: routing/routing.cc @ f0b96ba

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <deque>
#include <iterator>

#include <getopt.h>

#include "graph.h"
#include "routing.h"

#include "net.h"
#include "route_table.h"

typedef set<string> addr_set_t;
typedef map<string, string> addr_map_t;
typedef map<string, set<string> > addr_set_map_t;

using namespace std;

// Functor called by a for_each to remove a node (address) from the graph
class node_remover : public unary_function<string, void> {
    protected:
        graph &g;
    public:
        node_remover(graph& gg) : g(gg) { }
        void operator()(const string &s) { g.remove_node(s); }
};

// Functor called by for_each to remove a node (leaf) from the given set.
class leaf_remover : public unary_function<string, void> {
    protected:
        addr_set_t &l;
    public:
        leaf_remover(addr_set_t& ll) : l(ll) { }
        void operator()(const string &s) { l.erase(s); }
};

// Functor called by for_each to print a node's forwarding table to a file with
// the name of the node (a parameter) in the outdir specified at object
// creation time.  Also in the object are sets of destination objects, a map
// from node name to addresses, and the map from interfaces to leaf nodes.  The
// full routing matrix is also a parameter at creation time.
class node_writer : public unary_function<string, void> {
    protected:
        addr_set_t& addrs;          // All destination addresses
        addr_set_map_t& node_addrs; // Node name to address set map
        addr_set_map_t& children;   // Leaf nodes attached to an interface
        routing& r;                 // The routing
        const string& outdir;       // The output directory
        bool compress;              // True if we are compressing tables
        ostream *verbose;           // Pointer to verbouse output stream
        mutable int num;            // Number of calls to this functor
    public:
        node_writer(addr_set_t& a, addr_set_map_t& na, addr_set_map_t& c,
            routing& rr, const string& od, bool cm, ostream *v) : 
            addrs(a), node_addrs(na), children(c), r(rr), outdir(od),
            compress(cm), verbose(v), num(0) { }

        void operator()(const string &n) const {
            string out_fn = outdir + "/" + n ;      // destination filename
            ofstream out(out_fn.c_str());           // output stream
            addr_set_t& my_addrs = node_addrs[n];   // this node's addresses
            route_table rt;                         // The routes to compress

            // Build the route table
            for (addr_set_t::const_iterator d = addrs.begin(); 
                    d != addrs.end(); 
                    d++) {
                // Find the best route to each destination.  Because a node may
                // have multiple addresses, we have to check each outgoing
                // interface and pick the shortest.
                string src;     // outgoing interface of best route
                int best = 0;   // length of best route
                string nh;      // The next hop IP address for shortest route

                for (addr_set_t::const_iterator i = my_addrs.begin(); 
                        i != my_addrs.end(); i++) {
                    if (src.empty() || r.path_cost(*i, *d) < best ) { 
                        src = *i;
                        best = r.path_cost(*i, *d);
                    }
                }

                // Ignore single hop paths unless not compressing.
                if (r.path_cost(src, *d) > 1 || !compress) {
                    nh = r.next_hop(src, *d);

                    if ( !nh.empty() ) {
                        // Insert the nodes as the /24 containing them
                        Net n(*d);
                        n.set_mask(24);
                        rt.insert(n, Host(nh));
                    }
                }
                else nh = *d;

                // Output children of the destination unless they are this
                // node's children and we are compressing.
                if ( my_addrs.count(*d) == 0 || !compress) {
                    addr_set_map_t::iterator c = children.find(*d);

                    if ( c != children.end()) {
                        Host gw = Host(nh);
                        for (addr_set_t::const_iterator i = (*c).second.begin();
                                i != (*c).second.end(); i++) 
                            rt.insert(Net(*i), gw);
                    }
                }

            }
            // Collapse the route map (if we're compressing) and print it
            if (compress) rt.collapse();
            out << rt;
            if (verbose && ++num % 10 == 0)
                *verbose << num << '\r';
        }
};

// Functor to output a leaf node's routing table.  The table has the same name
// as the node and is output into outdir.  The parent_addr map (node to parent
// address) is passed in.
class leaf_writer : public unary_function<string, void> {
    protected:
        addr_map_t& parent_addr;    // Parent address map
        addr_set_t& addrs;          // All destination addresses
        addr_set_map_t& children;   // Leaf nodes attached to an interface
        const string& outdir;       // The output directory
        bool compress;              // Compress routing tables
        ostream *verbose;           // Verbose output
        mutable int num;            // Number of calls on this functor
    public:
        leaf_writer(addr_map_t& pa, addr_set_t& a, addr_set_map_t& c, 
                const string& od, bool cm, ostream *v ) :
            parent_addr(pa), addrs(a), children(c), outdir(od), compress(cm),
            verbose(v), num(0) { }
        void operator()(const string &n) const {
            string out_fn = outdir + "/" + n;
            ofstream out(out_fn.c_str());

            // Compressed leaves have a single default route
            if (compress) 
                out << "10.0.0.0/8 " << parent_addr[n] << endl;
            else {
                // For uncompressed leaves, all thr routes go to the parent,
                // but we have to enumerate them as all addresses and the
                // children of any address with leaves.
                string my_parent = parent_addr[n];

                out << my_parent << "/32 " << my_parent << endl;
                for (addr_set_t::const_iterator d = addrs.begin(); 
                        d != addrs.end(); d++) {
                    out << *d << "/32 " << my_parent << endl;

                    addr_set_map_t::iterator c = children.find(*d);
                    
                    if ( c != children.end() ) {
                        for (addr_set_t::const_iterator i = (*c).second.begin();
                                i != (*c).second.end(); i++) 
                            out << *i << "/32 " << my_parent << endl;
                    }
                }
            }
            if (verbose && ++num % 10 == 0) 
                *verbose << num << '\r';
        }
};


void parse_graph_description(graph& g, addr_set_t& nodes, addr_set_t& addrs,
        addr_set_t& leaves, addr_map_t& leaf_addr, addr_set_map_t& node_addrs,
        istream *in=0) {
    // Create the basic data structures from the input format.  The input is a
    // series of lines of the form:
    // node: addr,addr,addr
    // or
    // addr: addr,addr,addr
    //
    // The first line lists a node's interfaces and the second the
    // interconnections between addresses.  The nodes are captured in nodes and
    // leaves (a potential leaf is in both, nodes with multiple interfaces are
    // only in nodes).  Addrs is all addresses, leaf_add maps a leaf node to
    // its only address, node_addrs maps each node or leaf to its address(es).
    // g is the grahp of address interconnections.
    string line;    // Currnet line
    if (!in ) in = &cin;

    while (getline(*in, line, '\n')) {
        string::size_type p = line.find(':');   // String offsets for parsing
        string::size_type q;                    // String offsets for parsing
        string name;                            // Node name
        string ename;                           // Edge name (an address)
        graph::node *node = 0;                  // Curren graph node (address)
        bool make_node;                         // True if this is a node
        addr_set_t my_addrs;                    // Current set of node addrs

        if (p != string::npos) {
            name = line.substr(0, p);
            if (name.find_first_not_of("0123456789.") != string::npos) {
                make_node = true;
            }
            else {
                node = g.get_node(name);
                addrs.insert(name);
                make_node = false;
            }
        }
        else continue;
        p += 2;
        while ( (q = line.find(',', p)) != string::npos) {
            ename = line.substr(p, q-p);
            if (make_node) {
                my_addrs.insert(ename);
            }
            else {
                g.get_node(ename);
                node->add_edge(ename, 1.0);
            }
            p = q+1;
        }
        ename = line.substr(p);
        if (make_node) {
            my_addrs.insert(ename);

            nodes.insert(name);
            node_addrs[name] = my_addrs;
            if (my_addrs.size() == 1) {
                // Potential leaf node.  No need to cross connect, but we do
                // need to list it and its interfaces as leaves.  We won't know
                // if it is a leaf node until we find out if it is on a lan.
                leaves.insert(name);
                leaf_addr[name] = ename;
            }
            else {
                // Not a leaf.  Add it to nodes and interconnect its interfaces.
                for (addr_set_t::const_iterator i = node_addrs[name].begin();
                        i != node_addrs[name].end(); i ++) {
                    for (addr_set_t::const_iterator j =node_addrs[name].begin();
                            j != node_addrs[name].end(); j ++) {
                        if ( *i != *j && !g.has_edge(*i, *j)) {
                            graph::node *a = g.get_node(*i);
                            g.get_node(*j);
                            a->add_edge(*j, 1.0);
                        }
                    }
                }
            }
        }
        else {
            g.get_node(ename);
            node->add_edge(ename, 1.0);
        }
    }
}

void trim_leaves(graph &g, addr_set_t& nodes, addr_set_t& leaves, 
        addr_map_t& leaf_addr, addr_set_t& addrs, addr_map_t& parent_addr, 
        addr_set_map_t& children) {
    // Leaves is the set of nodes that may be leaves - nodes connected to one
    // node.  Walk that set, eliminate false positives, and for the real leaves
    // remove them from the node set, the addr_set and set their parent_addr
    // (the upstream interface), and add the leaf to the parent interface's
    // children map.

    addr_set_t graph_remove;    // nodes to remove from the graph
    addr_set_t leaf_remove;     // leaves to remove from the leaves set.

    for (addr_set_t::const_iterator l = leaves.begin(); l != leaves.end(); 
            l++) {
        string la = leaf_addr[*l];          // leaf address
        graph::node *ln = g.get_node(la);   // leaf address node
        if (ln-> degree() == 1 ) {
            graph::edge e = *ln->begin();           // edge
            string pa = e.get_node_name();          // parent address
            addr_set_map_t::iterator c = children.find(pa); // children entry 

            parent_addr[*l] = pa;
            if (c != children.end() ) 
                (*c).second.insert(la);
            else {
                children[pa] = addr_set_t();
                children[pa].insert(la);
            }
            // This is a confirmed leaf, so get it out of nodes.
            nodes.erase(*l);
            // NB cannot remove parent address as it may be a destination from
            // other palces in the net.
            graph_remove.insert(la);
            addrs.erase(la);
        }
        else {
            // Not a leaf after all, leave it in nodes and remove it from
            // leaves.
            leaf_remove.insert(*l);
        }

    }
    // Clean up the data structures we've been pulling things from.
    for_each(graph_remove.begin(), graph_remove.end(), node_remover(g));
    for_each(leaf_remove.begin(), leaf_remove.end(), leaf_remover(leaves));
    g.fix_edges();
}
enum { OUTPUT_OPT='o', DEBUG_OPT='d', NOCOMPRESS_OPT='C', INPUT_OPT='f'};
struct option opts[] = {
    { "output", required_argument, 0, OUTPUT_OPT}, 
    { "input", required_argument, 0, INPUT_OPT}, 
    { "debug", no_argument, 0, DEBUG_OPT}, 
    { "uncompressed", required_argument, 0, NOCOMPRESS_OPT}, 
};

void fatal(const string& my_name) {
    cerr << "Usage: " << my_name << 
        ": [options] [outputdir [filename]]" << endl;
    exit(20);
}


int main(int argc, char**argv) {
    addr_set_t nodes;           // Set of nodenames (not addresses)
    addr_set_t addrs;           // All valid destination addresses
    addr_set_t leaves;          // Leaf nodes
    addr_map_t parent_addr;     // Map from leaf address to parent address
    addr_map_t leaf_addr;       // Map from leaf node name to leaf address
    addr_set_map_t node_addrs;  // Map from each node to its addresses
    addr_set_map_t children;    // Map from a parent addess to its 
                                // leaf children
    graph g;                    // Graph represention
    string my_name = argv[0];   // The name of the program
    string outdir;              // Output directory
    string uncompressed_dir;    // Output for uncompressed routing tables
    int fl;                     // Option parsing
    bool debug=false;           // True for debugging output
    ifstream *inf = 0;          // Input file, if any

    while (( fl = getopt_long(argc, argv, "o:dC:", opts, 0)) != -1) {
        switch (fl) {
            case DEBUG_OPT:
                debug = true;
                break;
            case OUTPUT_OPT:
                outdir = optarg;
                break;
            case INPUT_OPT:
                if (!(inf = new ifstream(optarg))) {
                    cerr << "Cannot open " << optarg << endl;
                    fatal(my_name);
                }
                break;
            case NOCOMPRESS_OPT:
                uncompressed_dir=optarg;
                break;
        }
    }
    argc -= optind;
    argv += optind;
    if (argc > 0 && outdir.empty()) {
        outdir = argv[0];
        argc--; argv++;
    }
    if (argc > 0 && !inf) {
        if (!(inf = new ifstream(optarg))) {
            cerr << "Cannot open " << optarg << endl;
            fatal(my_name);
        }
        argc--; argv++;
    }

    if (outdir.empty()) fatal(my_name);

    parse_graph_description(g, nodes, addrs, leaves, leaf_addr, node_addrs,inf);
    trim_leaves(g, nodes, leaves, leaf_addr, addrs, parent_addr, children);

    routing r = routing(g, debug ? &cerr: 0);

    for_each(nodes.begin(), nodes.end(), 
            node_writer(addrs, node_addrs, children, r, outdir, true,
                debug ? &cerr : 0));
    if (debug) cerr << endl;
    for_each(leaves.begin(), leaves.end(), 
            leaf_writer(parent_addr, addrs, children, outdir, true,
                debug ? &cerr : 0));
    if (debug) cerr << endl;

    if (!uncompressed_dir.empty()) {
        for_each(nodes.begin(), nodes.end(), 
                node_writer(addrs, node_addrs, children, r, 
                    uncompressed_dir, false, debug ? &cerr : 0));
        if (debug) cerr << endl;
        for_each(leaves.begin(), leaves.end(), 
                leaf_writer(parent_addr, addrs, children, 
                    uncompressed_dir, false, debug ? &cerr : 0));
        if (debug) cerr << endl;
    }

}