source: routing/routing.cc @ e8f2d4c

Last change on this file since e8f2d4c was f24fc8d, checked in by Ted Faber <faber@…>, 12 years ago

Routing under here, too

  • Property mode set to 100644
File size: 12.8 KB
Line 
1#include <iostream>
2#include <fstream>
3#include <sstream>
4#include <string>
5#include <vector>
6#include <set>
7#include <map>
8#include <deque>
9#include <iterator>
10
11#include <getopt.h>
12
13#include "graph.h"
14#include "routing.h"
15
16#include "net.h"
17#include "route_table.h"
18
19typedef set<string> addr_set_t;
20typedef map<string, string> addr_map_t;
21typedef map<string, set<string> > addr_set_map_t;
22
23using namespace std;
24
25// Functor called by a for_each to remove a node (address) from the graph
26class node_remover : public unary_function<string, void> {
27    protected:
28        graph &g;
29    public:
30        node_remover(graph& gg) : g(gg) { }
31        void operator()(const string &s) { g.remove_node(s); }
32};
33
34// Functor called by for_each to remove a node (leaf) from the given set.
35class leaf_remover : public unary_function<string, void> {
36    protected:
37        addr_set_t &l;
38    public:
39        leaf_remover(addr_set_t& ll) : l(ll) { }
40        void operator()(const string &s) { l.erase(s); }
41};
42
43// Functor called by for_each to print a node's forwarding table to a file with
44// the name of the node (a parameter) in the outdir specified at object
45// creation time.  Also in the object are sets of destination objects, a map
46// from node name to addresses, and the map from interfaces to leaf nodes.  The
47// full routing matrix is also a parameter at creation time.
48class node_writer : public unary_function<string, void> {
49    protected:
50        addr_set_t& addrs;          // All destination addresses
51        addr_set_map_t& node_addrs; // Node name to address set map
52        addr_set_map_t& children;   // Leaf nodes attached to an interface
53        routing& r;                 // The routing
54        const string& outdir;       // The output directory
55        bool compress;              // True if we are compressing tables
56        ostream *verbose;           // Pointer to verbouse output stream
57        mutable int num;            // Number of calls to this functor
58    public:
59        node_writer(addr_set_t& a, addr_set_map_t& na, addr_set_map_t& c,
60            routing& rr, const string& od, bool cm, ostream *v) : 
61            addrs(a), node_addrs(na), children(c), r(rr), outdir(od),
62            compress(cm), verbose(v), num(0) { }
63
64        void operator()(const string &n) const {
65            string out_fn = outdir + "/" + n ;      // destination filename
66            ofstream out(out_fn.c_str());           // output stream
67            addr_set_t& my_addrs = node_addrs[n];   // this node's addresses
68            route_table rt;                         // The routes to compress
69
70            // Build the route table
71            for (addr_set_t::const_iterator d = addrs.begin(); 
72                    d != addrs.end(); 
73                    d++) {
74                // Find the best route to each destination.  Because a node may
75                // have multiple addresses, we have to check each outgoing
76                // interface and pick the shortest.
77                string src;     // outgoing interface of best route
78                int best = 0;   // length of best route
79                string nh;      // The next hop IP address for shortest route
80
81                for (addr_set_t::const_iterator i = my_addrs.begin(); 
82                        i != my_addrs.end(); i++) {
83                    if (src.empty() || r.path_cost(*i, *d) < best ) { 
84                        src = *i;
85                        best = r.path_cost(*i, *d);
86                    }
87                }
88
89                // Ignore single hop paths unless not compressing.
90                if (r.path_cost(src, *d) > 1 || !compress) {
91                    nh = r.next_hop(src, *d);
92
93                    if ( !nh.empty() ) {
94                        // Insert the nodes as the /24 containing them
95                        Net n(*d);
96                        n.set_mask(24);
97                        rt.insert(n, Host(nh));
98                    }
99                }
100                else nh = *d;
101
102                // Output children of the destination unless they are this
103                // node's children and we are compressing.
104                if ( my_addrs.count(*d) == 0 || !compress) {
105                    addr_set_map_t::iterator c = children.find(*d);
106
107                    if ( c != children.end()) {
108                        Host gw = Host(nh);
109                        for (addr_set_t::const_iterator i = (*c).second.begin();
110                                i != (*c).second.end(); i++) 
111                            rt.insert(Net(*i), gw);
112                    }
113                }
114
115            }
116            // Collapse the route map (if we're compressing) and print it
117            if (compress) rt.collapse();
118            out << rt;
119            if (verbose && ++num % 10 == 0)
120                *verbose << num << '\r';
121        }
122};
123
124// Functor to output a leaf node's routing table.  The table has the same name
125// as the node and is output into outdir.  The parent_addr map (node to parent
126// address) is passed in.
127class leaf_writer : public unary_function<string, void> {
128    protected:
129        addr_map_t& parent_addr;    // Parent address map
130        addr_set_t& addrs;          // All destination addresses
131        addr_set_map_t& children;   // Leaf nodes attached to an interface
132        const string& outdir;       // The output directory
133        bool compress;              // Compress routing tables
134        ostream *verbose;           // Verbose output
135        mutable int num;            // Number of calls on this functor
136    public:
137        leaf_writer(addr_map_t& pa, addr_set_t& a, addr_set_map_t& c, 
138                const string& od, bool cm, ostream *v ) :
139            parent_addr(pa), addrs(a), children(c), outdir(od), compress(cm),
140            verbose(v), num(0) { }
141        void operator()(const string &n) const {
142            string out_fn = outdir + "/" + n;
143            ofstream out(out_fn.c_str());
144
145            // Compressed leaves have a single default route
146            if (compress) 
147                out << "10.0.0.0/8 " << parent_addr[n] << endl;
148            else {
149                // For uncompressed leaves, all thr routes go to the parent,
150                // but we have to enumerate them as all addresses and the
151                // children of any address with leaves.
152                string my_parent = parent_addr[n];
153
154                out << my_parent << "/32 " << my_parent << endl;
155                for (addr_set_t::const_iterator d = addrs.begin(); 
156                        d != addrs.end(); d++) {
157                    out << *d << "/32 " << my_parent << endl;
158
159                    addr_set_map_t::iterator c = children.find(*d);
160                   
161                    if ( c != children.end() ) {
162                        for (addr_set_t::const_iterator i = (*c).second.begin();
163                                i != (*c).second.end(); i++) 
164                            out << *i << "/32 " << my_parent << endl;
165                    }
166                }
167            }
168            if (verbose && ++num % 10 == 0) 
169                *verbose << num << '\r';
170        }
171};
172
173
174void parse_graph_description(graph& g, addr_set_t& nodes, addr_set_t& addrs,
175        addr_set_t& leaves, addr_map_t& leaf_addr, addr_set_map_t& node_addrs,
176        istream *in=0) {
177    // Create the basic data structures from the input format.  The input is a
178    // series of lines of the form:
179    // node: addr,addr,addr
180    // or
181    // addr: addr,addr,addr
182    //
183    // The first line lists a node's interfaces and the second the
184    // interconnections between addresses.  The nodes are captured in nodes and
185    // leaves (a potential leaf is in both, nodes with multiple interfaces are
186    // only in nodes).  Addrs is all addresses, leaf_add maps a leaf node to
187    // its only address, node_addrs maps each node or leaf to its address(es).
188    // g is the grahp of address interconnections.
189    string line;    // Currnet line
190    if (!in ) in = &cin;
191
192    while (getline(*in, line, '\n')) {
193        string::size_type p = line.find(':');   // String offsets for parsing
194        string::size_type q;                    // String offsets for parsing
195        string name;                            // Node name
196        string ename;                           // Edge name (an address)
197        graph::node *node = 0;                  // Curren graph node (address)
198        bool make_node;                         // True if this is a node
199        addr_set_t my_addrs;                    // Current set of node addrs
200
201        if (p != string::npos) {
202            name = line.substr(0, p);
203            if (name.find_first_not_of("0123456789.") != string::npos) {
204                make_node = true;
205            }
206            else {
207                node = g.get_node(name);
208                addrs.insert(name);
209                make_node = false;
210            }
211        }
212        else continue;
213        p += 2;
214        while ( (q = line.find(',', p)) != string::npos) {
215            ename = line.substr(p, q-p);
216            if (make_node) {
217                my_addrs.insert(ename);
218            }
219            else {
220                g.get_node(ename);
221                node->add_edge(ename, 1.0);
222            }
223            p = q+1;
224        }
225        ename = line.substr(p);
226        if (make_node) {
227            my_addrs.insert(ename);
228
229            nodes.insert(name);
230            node_addrs[name] = my_addrs;
231            if (my_addrs.size() == 1) {
232                // Potential leaf node.  No need to cross connect, but we do
233                // need to list it and its interfaces as leaves.  We won't know
234                // if it is a leaf node until we find out if it is on a lan.
235                leaves.insert(name);
236                leaf_addr[name] = ename;
237            }
238            else {
239                // Not a leaf.  Add it to nodes and interconnect its interfaces.
240                for (addr_set_t::const_iterator i = node_addrs[name].begin();
241                        i != node_addrs[name].end(); i ++) {
242                    for (addr_set_t::const_iterator j =node_addrs[name].begin();
243                            j != node_addrs[name].end(); j ++) {
244                        if ( *i != *j && !g.has_edge(*i, *j)) {
245                            graph::node *a = g.get_node(*i);
246                            g.get_node(*j);
247                            a->add_edge(*j, 1.0);
248                        }
249                    }
250                }
251            }
252        }
253        else {
254            g.get_node(ename);
255            node->add_edge(ename, 1.0);
256        }
257    }
258}
259
260void trim_leaves(graph &g, addr_set_t& nodes, addr_set_t& leaves, 
261        addr_map_t& leaf_addr, addr_set_t& addrs, addr_map_t& parent_addr, 
262        addr_set_map_t& children) {
263    // Leaves is the set of nodes that may be leaves - nodes connected to one
264    // node.  Walk that set, eliminate false positives, and for the real leaves
265    // remove them from the node set, the addr_set and set their parent_addr
266    // (the upstream interface), and add the leaf to the parent interface's
267    // children map.
268
269    addr_set_t graph_remove;    // nodes to remove from the graph
270    addr_set_t leaf_remove;     // leaves to remove from the leaves set.
271
272    for (addr_set_t::const_iterator l = leaves.begin(); l != leaves.end(); 
273            l++) {
274        string la = leaf_addr[*l];          // leaf address
275        graph::node *ln = g.get_node(la);   // leaf address node
276        if (ln-> degree() == 1 ) {
277            graph::edge e = *ln->begin();           // edge
278            string pa = e.get_node_name();          // parent address
279            addr_set_map_t::iterator c = children.find(pa); // children entry
280
281            parent_addr[*l] = pa;
282            if (c != children.end() ) 
283                (*c).second.insert(la);
284            else {
285                children[pa] = addr_set_t();
286                children[pa].insert(la);
287            }
288            // This is a confirmed leaf, so get it out of nodes.
289            nodes.erase(*l);
290            // NB cannot remove parent address as it may be a destination from
291            // other palces in the net.
292            graph_remove.insert(la);
293            addrs.erase(la);
294        }
295        else {
296            // Not a leaf after all, leave it in nodes and remove it from
297            // leaves.
298            leaf_remove.insert(*l);
299        }
300
301    }
302    // Clean up the data structures we've been pulling things from.
303    for_each(graph_remove.begin(), graph_remove.end(), node_remover(g));
304    for_each(leaf_remove.begin(), leaf_remove.end(), leaf_remover(leaves));
305    g.fix_edges();
306}
307enum { OUTPUT_OPT='o', DEBUG_OPT='d', NOCOMPRESS_OPT='C', INPUT_OPT='f'};
308struct option opts[] = {
309    { "output", required_argument, 0, OUTPUT_OPT}, 
310    { "input", required_argument, 0, INPUT_OPT}, 
311    { "debug", no_argument, 0, DEBUG_OPT}, 
312    { "uncompressed", required_argument, 0, NOCOMPRESS_OPT}, 
313};
314
315void fatal(const string& my_name) {
316    cerr << "Usage: " << my_name << 
317        ": [options] [outputdir [filename]]" << endl;
318    exit(20);
319}
320
321
322int main(int argc, char**argv) {
323    addr_set_t nodes;           // Set of nodenames (not addresses)
324    addr_set_t addrs;           // All valid destination addresses
325    addr_set_t leaves;          // Leaf nodes
326    addr_map_t parent_addr;     // Map from leaf address to parent address
327    addr_map_t leaf_addr;       // Map from leaf node name to leaf address
328    addr_set_map_t node_addrs;  // Map from each node to its addresses
329    addr_set_map_t children;    // Map from a parent addess to its
330                                // leaf children
331    graph g;                    // Graph represention
332    string my_name = argv[0];   // The name of the program
333    string outdir;              // Output directory
334    string uncompressed_dir;    // Output for uncompressed routing tables
335    int fl;                     // Option parsing
336    bool debug=false;           // True for debugging output
337    ifstream *inf = 0;          // Input file, if any
338
339    while (( fl = getopt_long(argc, argv, "o:dC:", opts, 0)) != -1) {
340        switch (fl) {
341            case DEBUG_OPT:
342                debug = true;
343                break;
344            case OUTPUT_OPT:
345                outdir = optarg;
346                break;
347            case INPUT_OPT:
348                if (!(inf = new ifstream(optarg))) {
349                    cerr << "Cannot open " << optarg << endl;
350                    fatal(my_name);
351                }
352                break;
353            case NOCOMPRESS_OPT:
354                uncompressed_dir=optarg;
355                break;
356        }
357    }
358    argc -= optind;
359    argv += optind;
360    if (argc > 0 && outdir.empty()) {
361        outdir = argv[0];
362        argc--; argv++;
363    }
364    if (argc > 0 && !inf) {
365        if (!(inf = new ifstream(optarg))) {
366            cerr << "Cannot open " << optarg << endl;
367            fatal(my_name);
368        }
369        argc--; argv++;
370    }
371
372    if (outdir.empty()) fatal(my_name);
373
374    parse_graph_description(g, nodes, addrs, leaves, leaf_addr, node_addrs,inf);
375    trim_leaves(g, nodes, leaves, leaf_addr, addrs, parent_addr, children);
376
377    routing r = routing(g, debug ? &cerr: 0);
378
379    for_each(nodes.begin(), nodes.end(), 
380            node_writer(addrs, node_addrs, children, r, outdir, true,
381                debug ? &cerr : 0));
382    if (debug) cerr << endl;
383    for_each(leaves.begin(), leaves.end(), 
384            leaf_writer(parent_addr, addrs, children, outdir, true,
385                debug ? &cerr : 0));
386    if (debug) cerr << endl;
387
388    if (!uncompressed_dir.empty()) {
389        for_each(nodes.begin(), nodes.end(), 
390                node_writer(addrs, node_addrs, children, r, 
391                    uncompressed_dir, false, debug ? &cerr : 0));
392        if (debug) cerr << endl;
393        for_each(leaves.begin(), leaves.end(), 
394                leaf_writer(parent_addr, addrs, children, 
395                    uncompressed_dir, false, debug ? &cerr : 0));
396        if (debug) cerr << endl;
397    }
398
399}
Note: See TracBrowser for help on using the repository browser.