Page MenuHomec4science
Files F120467529

routingpaths.cc
No OneTemporary
Actions

File Metadata

Created
Fri, Jul 4, 14:44

routingpaths.cc
View Options

#include <click/config.h>
#include <click/package.hh>
#include <clicknet/ether.h>
#include <click/etheraddress.hh>
#include <click/ipaddress.hh>
#include <click/args.hh>
#include <click/bitvector.hh>
#include <click/error.hh>
#include <click/glue.hh>
#include <clicknet/ip.h>
#include <click/router.hh>
#include <click/string.hh>
#include <click/vector.hh>
#include <click/confparse.hh>
#include <click/timestamp.hh>
#include "routingpaths.hh"
//#define DEBUG_CHATTER(arg, ...) do { if (_debug) { fprintf(stderr, "[%s] ", class_name()); fflush(stderr); click_chatter(arg, ## __VA_ARGS__);} } while (0)
//#define VERB_DEBUG_CHATTER(arg, ...) do { if (_verb_debug) { fprintf(stderr, "[%s] ", class_name()); fflush(stderr); click_chatter(arg, ## __VA_ARGS__);} } while (0)
//re-defined in kernel-compatible way:
#define DEBUG_CHATTER(arg, ...) do { if (_debug) { click_chatter(arg, ## __VA_ARGS__);} } while (0)
#define VERB_DEBUG_CHATTER(arg, ...) do { if (_verb_debug) { click_chatter(arg, ## __VA_ARGS__);} } while (0)
CLICK_DECLS
RoutingPaths::RoutingPaths() : timer(this)
{
}
RoutingPaths::~RoutingPaths()
{
}
int
RoutingPaths::configure(Vector<String> &conf, ErrorHandler *errh)
{
_multi_paths = false;
_debug = false;
_verb_debug = false;
_test_capa_one_hop = false;
_test_capa_one_hop_wifi = false;
_warning_n_N = false;
_print_routes_freq = 0;
_empty_eth = EtherAddress();
_time = 0;
_multirouting_2best_paths = false;
_k_value = 5;
_reset = false;
_csc_choice = "min";
_keep_routes = false;
adjacency_matrix = AdjacencyMatrix();
dijkstra_result = HashTable<VirtualNodeRouting,VirtualNodeRouting>();
me = NodeRouting();
EtherAddress addr_wifi, addr_plc, addr_wifi2;
int node_index = -1;
String rtl_name;
String compound_name;
String test_capa_one_hop_str;
_notify_invalid_links = false;
if(Args(this, errh).bind(conf)
.read_m("IP", me.ip)
//.read_m("ROUTING_LINKS", reinterpret_cast<Element *&>(_routing_links))
.read_m("ROUTING_LINKS", rtl_name)
.read_m("GW", _default_gw_ip)
.read("MULTI_PATHS", _multi_paths)
.read("DEBUG", _debug)
.read("VERB_DEBUG", _verb_debug)
.read("WIFI_ADDR", addr_wifi)
.read("PLC_ADDR", addr_plc)
.read("WIFI2_ADDR", addr_wifi2)
.read("CSC_CHOICE", _csc_choice)
.read("NODE_INDEX", node_index)
.read("PRINT_ROUTES", _print_routes_freq)
.read("TEST_CAPA_ONE_HOP", test_capa_one_hop_str)
.read("MULTIROUTING_2BEST_PATHS", _multirouting_2best_paths)
.read("NOTIFY_INVALID_LINKS", _notify_invalid_links)
.consume() < 0)
return -1;
if(test_capa_one_hop_str.compare("wifi") == 0) {
_test_capa_one_hop = true;
_test_capa_one_hop_wifi = true;
}
else if (test_capa_one_hop_str.compare("plc") == 0) {
_test_capa_one_hop = true;
_test_capa_one_hop_wifi = false;
}
if(node_index != -1){
//we are part of a compound element, we need to adapt the names of the elements...
String index_str = String(node_index);
String tempstr = String("node")+index_str.c_str();
compound_name = tempstr + "/";
}
_routing_links = (RoutingLinks*)router()->find(rtl_name, compound_name, errh);
if(_routing_links == 0) {
return errh->error("No RoutingLinks element %s%s.",
compound_name.c_str(), rtl_name.c_str());
}
if(_routing_links->cast("RoutingLinks") == 0)
return errh->error("%s%s is not a RoutingLinks.",
compound_name.c_str(), rtl_name.c_str());
if(!(_csc_choice.compare("min") == 0 || _csc_choice.compare("no") == 0 ))
return errh->error("Possible values for CSC_CHOICE are min or no");
if(!(addr_wifi != _empty_eth || addr_plc != _empty_eth))
return errh->error("Needs at least one interface address");
Timestamp now;
now.assign_now();
if(addr_wifi != _empty_eth && addr_plc != _empty_eth) {
if(addr_wifi2 != _empty_eth)
return errh->error("[RoutingPaths] Cannot provide both WIFI2 and PLC");
me.interfaces=Vector<EtherAddress>(2,_empty_eth);
me.is_wifi=Vector<bool>(2,true);
me.interfaces[INTERFACE2] = addr_plc;
me.interfaces[INTERFACE1] = addr_wifi;
me.is_wifi[INTERFACE2] = false;
DEBUG_CHATTER("[RoutingPaths %s] Has interfaces Wifi %s and PLC %s.",
now.unparse().c_str(),addr_wifi.unparse().c_str(), addr_plc.unparse().c_str());
set_wifi_addr(addr_wifi);
set_plc_addr(addr_plc);
}
else if(addr_wifi != _empty_eth && addr_wifi2 != _empty_eth) {
me.interfaces=Vector<EtherAddress>(2,_empty_eth);
me.is_wifi=Vector<bool>(2,true);
me.interfaces[INTERFACE2] = addr_wifi2;
me.interfaces[INTERFACE1] = addr_wifi;
DEBUG_CHATTER("[RoutingPaths %s] Has interfaces Wifi %s and Wifi2 %s.",
now.unparse().c_str(),addr_wifi.unparse().c_str(), addr_wifi2.unparse().c_str());
set_wifi_addr(addr_wifi);
set_wifi_addr(addr_wifi2);
}
else if(addr_plc != _empty_eth) {
me.interfaces=Vector<EtherAddress>(1,addr_plc);
me.unique_interface = INTERFACE2;
me.unique_interface_wifi = false;
DEBUG_CHATTER("[RoutingPaths %s] Has interface PLC %s.", now.unparse().c_str(), addr_plc.unparse().c_str());
set_plc_addr(addr_plc);
}
else if(addr_wifi != _empty_eth) {
me.interfaces=Vector<EtherAddress>(1,addr_wifi);
me.unique_interface = INTERFACE1;
me.unique_interface_wifi = true;
DEBUG_CHATTER("[RoutingPaths %s] Has interface Wifi %s.",now.unparse().c_str(), addr_wifi.unparse().c_str());
set_wifi_addr(addr_wifi);
}
else
return errh->error("[RoutingPaths] Wrong combination of given addresses");
me.last_time_seen_node = now;
me.last_time_seen_interfaces = Vector<Timestamp>(me.interfaces.size(), now);
if (_verb_debug)
_debug = true;
if (_routing_links && _routing_links->cast("RoutingLinks") == 0)
return errh->error("ROUTING_LINKS element is not a RoutingLinks");
timer.initialize(this);
timer.schedule_after_msec(1000);
DEBUG_CHATTER("[RoutingPaths %s] RoutingPaths configured with %d interfaces!",now.unparse().c_str(), me.interfaces.size());
if(_verb_debug) {
for (int i_node = 0;i_node < _routing_links->get_nodes_in_network().size();i_node++) {
VERB_DEBUG_CHATTER("[RoutingPaths %s] Node %d has %d interfaces",now.unparse().c_str(), i_node,
_routing_links->get_nodes_in_network()[i_node].interfaces.size());
}
}
_routes_table_mp = HashTable<MultiPathDemand, Vector<Vector<Route> > >();
_last_seen_routes_mp = HashTable<IPAddress, Vector<Vector<Route> > >();
return 0;
}
int
RoutingPaths::initialize(ErrorHandler *errh) {
Timestamp now;
if (_debug)
now.assign_now();
//srand (time(NULL));
DEBUG_CHATTER("[RoutingPaths %s] Initializing...", now.unparse().c_str());
VERB_DEBUG_CHATTER("[RoutingPaths %s] Setting RoutingLinks", now.unparse().c_str());
if(!_routing_links->set_routing_links(me))
return errh->error("Error while setting RoutingLinks element.");
DEBUG_CHATTER("[RoutingPaths %s] Done!", now.unparse().c_str());
return 0;
}
void
RoutingPaths::push(int port, Packet *p_in) {
Timestamp now;
if (_debug)
now.assign_now();
acne_header *acne_hdr;
if(port > 0) {
acne_hdr = (acne_header *)(p_in->data());
}
click_ip *ip=(click_ip *)(p_in->data() + (port>0)*sizeof(acne_header));
IPAddress src_addr(ip->ip_src.s_addr);
IPAddress dst_addr(ip->ip_dst.s_addr);
DEBUG_CHATTER("[RoutingPaths %s] Packet received from %s to %s on port %d",now.unparse().c_str(),
src_addr.unparse().c_str(), dst_addr.unparse().c_str(), port);
if(_multi_paths == false) {
// single (best) path: act as a router
if(port == 0) {
// comes from host: compute path, add routing header, add next hop mac address
// and forward (output corresponding to the interface)
DEBUG_CHATTER("[RoutingPaths %s] Packet must be source routed. Getting route...",now.unparse().c_str());
Route route = get_route(dst_addr);
if(dst_addr != _default_gw_ip && route.ip == _default_gw_ip) {
if(me.ip == _default_gw_ip) {
output(0).push(p_in);
return;
}
}
if(route.links.empty()) {
DEBUG_CHATTER("[RoutingPaths %s] No route to destination %s!", now.unparse().c_str(), route.ip.unparse().c_str());
p_in->kill();
return;
}
EtherAddress next_hop = route.links[0].dst;
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Adding source routing header...", now.unparse().c_str());
Packet *p_tmp = add_source_routing(p_in, route);
if(p_tmp == 0) {
return;
}
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Adding MAC header...", now.unparse().c_str());
int interface_out = _routing_links->get_interface(next_hop);
Packet *p_out = _routing_links->add_headers(p_tmp, next_hop, interface_out, REGULAR_TRAFFIC);
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Packet goes to output %s.", now.unparse().c_str(),
_routing_links->interface(interface_out).c_str());
output(1 + interface_out).push(p_out);
}
else {
// comes from device
bool is_for_me = false;
for (int i=0;i<me.interfaces.size();i++) {
if(are_last_bytes_in_addr(acne_hdr->_route._dst, me.interfaces[i])) {
is_for_me = true;
break;
}
}
if(is_for_me) {
// is for me: remove source routing header, go to output 0
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Packet is for me: to output 0", now.unparse().c_str());
Packet *p_out = delete_routing_header(p_in);
output(0).push(p_out);
}
else {
// must be routed (if I'm in the route): get next hop, update routing header,
// add next hop address and forward (output corresponding to the interface)
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Checking the route...", now.unparse().c_str());
EtherAddress next_hop;
Packet *p_temp = update_routing_header(p_in, next_hop);
if(next_hop==_empty_eth) {
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] I'm not in the route: discard packet.", now.unparse().c_str());
p_temp->kill();
return;
}
// packet must be forwarded
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Packet must be forwarded to %s. Adding MAC header...", now.unparse().c_str(), next_hop.unparse().c_str());
int interface_out = _routing_links->get_interface(next_hop);
if(interface_out == -1) {
click_chatter("[RoutingPaths %s] Warning: don't have a forwarding interface for this next_hop.", now.unparse().c_str());
p_temp->kill();
return;
}
Packet *p_out = _routing_links->add_headers(p_temp, next_hop, interface_out, REGULAR_TRAFFIC);
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Packet goes to output %s.", now.unparse().c_str(),
_routing_links->interface(interface_out).c_str());
output(1 + interface_out).push(p_out);
}
}
}
}
void
RoutingPaths::run_timer(Timer *t) {
assert(t == &timer);
if(_warning_n_N) {
click_chatter("[RoutingPaths] WARNING: only n=1 or n=2 and N=1 are supported for now.");
_warning_n_N = false;
}
/*
if(_routing_links->get_and_reset_has_changed()) {
// routing links has changed: recompute paths
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Adjacency matrix needs to be (re)computed. Computing...", now.unparse().c_str());
recompute_adjacency_matrix();
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Adjacency matrix computed!", now.unparse().c_str());
VERB_DEBUG_CHATTER("[RoutingPaths %s] %d virtual nodes", now.unparse().c_str(), adjacency_matrix.size());
HashTable<VirtualNodeRouting, uint32_t> min_distances;
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Computing paths...", now.unparse().c_str());
//dijkstra_compute_paths(VirtualNodeRouting(SRC_VN,me.ip), adjacency_matrix,min_distances, dijkstra_result);
bellmanford_compute_paths(VirtualNodeRouting(SRC_VN,me.ip), adjacency_matrix,min_distances, dijkstra_result);
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Paths computed!", now.unparse().c_str());
_routes_table_mp.clear();
}
*/
if(_print_routes_freq > 0) {
click_chatter(print_routes().c_str());
timer.schedule_after_sec(_print_routes_freq);
}
}
Vector<Route>
RoutingPaths::get_multipath (IPAddress dst, int n) {
Vector<Vector<Route> > multipaths = get_multipaths(dst, 1, n, true, false, false, true);
if(multipaths.empty())
return Vector<Route>();
return multipaths[0];
}
Vector<Route>
RoutingPaths::get_multipath_wifi (IPAddress dst, int n) {
Vector<Vector<Route> > multipaths = get_multipaths(dst, 1, n, true, true, false, true);
if(multipaths.empty())
return Vector<Route>();
return multipaths[0];
}
Vector<Route>
RoutingPaths::get_multipath_plc (IPAddress dst, int n) {
Vector<Vector<Route> > multipaths = get_multipaths(dst, 1, n, true, false, true, true);
if(multipaths.empty())
return Vector<Route>();
return multipaths[0];
}
Vector<Multipath>
RoutingPaths::get_multipaths_mp(IPAddress dst, int N, int n) {
Vector<Vector<Route> > routes = get_multipaths(dst,N,n);
Vector<Multipath> multipaths;
for(int i=0;i<routes.size();i++) {
Multipath multipath;
for(int j=0;j<routes[i].size();j++)
multipath.add_route(routes[i][j]);
multipaths.push_back(multipath);
}
return multipaths;
}
Vector<Vector<Route> >
RoutingPaths::get_multipaths(IPAddress dst, int N, int n) {
return get_multipaths(dst, N, n, true, false, false, true);
}
Vector<Vector<Route> >
RoutingPaths::get_multipaths_wifi(IPAddress dst, int N, int n) {
return get_multipaths(dst, N, n, true, true,false, true);
}
Vector<Vector<Route> >
RoutingPaths::get_multipaths_plc(IPAddress dst, int N, int n) {
return get_multipaths(dst, N, n, true, false, true, true);
}
Route
RoutingPaths::get_best_path_ack(IPAddress src_ip) {
Vector<Vector<Route> > multipaths = get_multipaths(src_ip,1,1,false,false,false,false);
if(multipaths.empty())
return Route();
Vector<Route> routes = multipaths[0];
if(routes.empty())
return Route();
else
return routes[0];
}
Route
RoutingPaths::get_best_path_ack(unsigned char *data) {
//using only the last bytes of an EtherAddress
IPAddress src_ip = _routing_links->get_ip(data);
if(_debug) {
Timestamp now;
now.assign_now();
String data_str = String::make_garbage(4);
if (char *x = data_str.mutable_c_str())
sprintf(x, "%02X%02X",data[0], data[1]);
DEBUG_CHATTER("[RoutingPaths %s] Found destination %s from last bytes %s",now.unparse().c_str(),
src_ip.unparse().c_str(),data_str.c_str());
}
return get_best_path_ack(src_ip);
}
String
RoutingPaths::print_routes() {
Vector<NodeRouting> nodes_in_network = _routing_links->get_nodes_in_network();
StringAccum s;
for(int i=0;i<nodes_in_network.size();i++) {
if (is_in_hash_table(_routes_to_print, nodes_in_network[i].ip)) {
s << "Multipaths to " << nodes_in_network[i].ip.unparse() << " are:\n";
for (int j=0;j<_routes_to_print[nodes_in_network[i].ip].size();j++) {
for(int k=0;k<_routes_to_print[nodes_in_network[i].ip][j].size();k++)
s << " " << _routes_to_print[nodes_in_network[i].ip][j][k].unparse() << ".\n";
s << " ---------------------------------------------------------- \n";
}
}
else
s << "Route to " << nodes_in_network[i].ip.unparse() << " is unknown.\n";
}
return s.take_string();
}
void
RoutingPaths::set_2bp(bool b) {
if(b!=_multirouting_2best_paths) {
_routes_table_mp_wifi.clear();
_routes_table_mp.clear();
_routes_table_mp_plc.clear();
}
_multirouting_2best_paths=b;
}
void
RoutingPaths::reset() {
_routes_table_mp_wifi.clear();
_routes_table_mp.clear();
_routes_table_mp_plc.clear();
_reset = true;
}
void
RoutingPaths::add_forbidden_multipath(Multipath mp) {
if(!is_in_vector(_forbidden_multipaths, mp)) {
_forbidden_multipaths.push_back(mp);
DEBUG_CHATTER("Add %s in forbidden multipath", mp.unparse().c_str());
}
DEBUG_CHATTER("Forbidden multipaths are now:");
for (int i=0;i<_forbidden_multipaths.size();i++) {
DEBUG_CHATTER("\t%s", _forbidden_multipaths[i].unparse().c_str());
}
}
void
RoutingPaths::rm_forbidden_multipath(Multipath mp) {
Vector<Multipath> new_vector;
for(int i=0;i<_forbidden_multipaths.size();i++) {
if(_forbidden_multipaths[i]!=mp)
new_vector.push_back(_forbidden_multipaths[i]);
}
_forbidden_multipaths=new_vector;
DEBUG_CHATTER("Removed %s, forbidden multipaths are now:", mp.unparse().c_str());
for (int i=0;i<_forbidden_multipaths.size();i++) {
DEBUG_CHATTER("\t%s", _forbidden_multipaths[i].unparse().c_str());
}
}
////////////////////////// PRIVATE FUNCTIONS ////////////////////////////////////
Vector<Vector<Route> >
RoutingPaths::get_multipaths (IPAddress dst, int N, int n, bool store_route, bool wifi_only, bool plc_only, bool check_order) {
// N multipaths of n paths
if (n>2) { // right now: n=1 or n=2
_warning_n_N = true;
n=2;
}
Timestamp now;
Timestamp start = Timestamp::now();
if(!_keep_routes && (_routing_links->get_and_reset_has_changed() || _reset)) {
// routing links has changed: recompute paths
_reset = false;
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Adjacency matrix needs to be (re)computed. Computing...", now.unparse().c_str());
_routes_table_mp.clear();
_routes_table_mp_wifi.clear();
_routes_table_mp_plc.clear();
Timestamp now2;
if(_debug)
now.assign_now();
recompute_adjacency_matrix();
if (_debug)
now2.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Adjacency matrix computed in %s seconds!", now2.unparse().c_str(),
(now2-now).unparse().c_str());
VERB_DEBUG_CHATTER("[RoutingPaths %s] %d virtual nodes", now.unparse().c_str(), adjacency_matrix.size());
}
else {
if(wifi_only) {
if(!_test_capa_one_hop && is_in_hash_table(_routes_table_mp_wifi, MultiPathDemand(dst, N, n))) {
check_paths_valid(dst, _routes_table_mp_wifi[MultiPathDemand(dst, N, n)], store_route, check_order);
return _routes_table_mp_wifi[MultiPathDemand(dst, N, n)];
}
}
else if (plc_only) {
if(!_test_capa_one_hop && is_in_hash_table(_routes_table_mp_plc, MultiPathDemand(dst, N, n))) {
check_paths_valid(dst, _routes_table_mp_plc[MultiPathDemand(dst, N, n)], store_route, check_order);
return _routes_table_mp_plc[MultiPathDemand(dst, N, n)];
}
}
else {
if(!_test_capa_one_hop && is_in_hash_table(_routes_table_mp, MultiPathDemand(dst, N, n))) {
check_paths_valid(dst, _routes_table_mp[MultiPathDemand(dst, N, n)], store_route, check_order);
return _routes_table_mp[MultiPathDemand(dst, N, n)];
}
}
}
if (_test_capa_one_hop) {
Vector<Route> best_path_vec;
Route route = get_route(dst);
best_path_vec.push_back(route);
Vector<Vector<Route> > best_mp;
best_mp.push_back(best_path_vec);
check_paths_valid(dst, best_mp, store_route, check_order);
return best_mp;
}
// compute N paths
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Computing %d paths to %s...", now.unparse().c_str(), N, dst.unparse().c_str());
//computes N paths by updating the adjacency matrix
AdjacencyMatrix adj_mat_loc = AdjacencyMatrix(adjacency_matrix);
Route path_loc;
uint32_t C_max_P = 10000;
if(_multirouting_2best_paths) { // only two best path instead of complete routing protocol
if(N>1) {
click_chatter("[RoutingPaths] N>1 not supported with multirouting_2best_paths");
N=1;
}
DEBUG_CHATTER("[RoutingPaths] Getting two best paths...");
Vector<Route> first_k_paths;
// get first n paths
if(wifi_only)
first_k_paths = get_k_shortest_paths(adjacency_matrix_wifi_only, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), n);
else if (plc_only)
first_k_paths = get_k_shortest_paths(adjacency_matrix_plc_only, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), n);
else
first_k_paths = get_k_shortest_paths(adjacency_matrix, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), n);
// set capa to be 1/weight (good order of magnitude)
for(int i=0;i<first_k_paths.size();i++) {
first_k_paths[i].max_capa = SCALE_WEIGHTS/first_k_paths[i].weight;
first_k_paths[i].max_capa_alone = first_k_paths[i].max_capa;
}
Vector<Vector<Route> > multipath = Vector<Vector<Route> >(1,first_k_paths);
if(wifi_only) {
if (!multipath[0].empty() && !multipath[0][0].links.empty())
_routes_table_mp_wifi.set(MultiPathDemand(dst, N, n), multipath);
else
_routes_table_mp_wifi.erase(MultiPathDemand(dst, N, n));
}
else if(plc_only) {
if (!multipath[0].empty() && !multipath[0][0].links.empty())
_routes_table_mp_plc.set(MultiPathDemand(dst, N, n), multipath);
else
_routes_table_mp_plc.erase(MultiPathDemand(dst, N, n));
}
else {
if (!multipath[0].empty() && !multipath[0][0].links.empty())
_routes_table_mp.set(MultiPathDemand(dst, N, n), multipath);
else
_routes_table_mp.erase(MultiPathDemand(dst, N, n));
}
check_paths_valid(dst, multipath, store_route, check_order);
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] We computed %d multipaths!", now.unparse().c_str(), multipath.size());
if(_debug) {
StringAccum s;
s << "[RoutingPaths] Multipaths are \n";
for(int j=0;j<multipath.size();j++) {
for (int i=0;i<multipath[j].size();i++)
s << " " << multipath[j][i].unparse() << " \n";
s << " --------------\n";
}
DEBUG_CHATTER(s.c_str());
}
return multipath;
}
else {
int k;
if(n==1 && N==1)
k = 1;
else
k = _k_value;
Vector<Multipath> sorted_multipaths;
Vector<Route> first_k_paths;
if(wifi_only)
first_k_paths = get_k_shortest_paths(adjacency_matrix_wifi_only, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), k);
else if(plc_only)
first_k_paths = get_k_shortest_paths(adjacency_matrix_plc_only, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), k);
else
first_k_paths = get_k_shortest_paths(adjacency_matrix, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), k);
//uint32_t C_tot_max = 0;
for (int i=0;i<first_k_paths.size();i++) {
path_loc = first_k_paths[i];
if (path_loc != Route()) {
VERB_DEBUG_CHATTER("[RoutingPaths] Updating capacity for path %s", path_loc.unparse().c_str());
if(wifi_only)
adj_mat_loc = update_capacities_adjacency_matrix_multi_paths(adjacency_matrix_wifi_only, path_loc, C_max_P, false);
else if(plc_only)
adj_mat_loc = update_capacities_adjacency_matrix_multi_paths(adjacency_matrix_plc_only, path_loc, C_max_P, false);
else
adj_mat_loc = update_capacities_adjacency_matrix_multi_paths(adjacency_matrix, path_loc, C_max_P, false);
//uint32_t C_first_path = C_max_P;
path_loc.max_capa = C_max_P;
path_loc.max_capa_alone = C_max_P;
Vector<Route> next_k_paths;
if (n>=2)
next_k_paths = get_k_shortest_paths(adj_mat_loc, VirtualNodeRouting(SRC_VN,me.ip), VirtualNodeRouting(DST_VN, dst), k);
if (next_k_paths.size() > 0) {
for (int j=0;j<next_k_paths.size();j++) {
Multipath current_mp;
current_mp.add_route(path_loc);
if (next_k_paths[j] == Route()) {
if(!is_in_vector(_forbidden_multipaths,current_mp))
if(insert_in_sorted_descent_vector(sorted_multipaths, current_mp))
DEBUG_CHATTER("[RoutingPaths] Inserting multipath %s", current_mp.unparse().c_str());
}
else {
VERB_DEBUG_CHATTER("[RoutingPaths] Computing max capacity for path %s", next_k_paths[j].unparse().c_str());
update_capacities_adjacency_matrix_multi_paths(adj_mat_loc, next_k_paths[j], C_max_P, true);
//if(C_max_P > path_loc.max_capa/20) { // add only path if capa greater than 5% of first path
next_k_paths[j].max_capa = C_max_P; // capacity with other route
update_capacities_adjacency_matrix_multi_paths(adjacency_matrix, next_k_paths[j], C_max_P, true);
next_k_paths[j].max_capa_alone = C_max_P; // capacity alone
current_mp.add_route(next_k_paths[j]);
//}
if(!is_in_vector(_forbidden_multipaths,current_mp))
if (insert_in_sorted_descent_vector(sorted_multipaths, current_mp))
DEBUG_CHATTER("[RoutingPaths] Inserting multipath %s", current_mp.unparse().c_str());
}
}
}
else {
Multipath current_mp;
current_mp.add_route(path_loc);
if(!is_in_vector(_forbidden_multipaths,current_mp))
if (insert_in_sorted_descent_vector(sorted_multipaths, current_mp))
DEBUG_CHATTER("[RoutingPaths] Inserting multipath %s", current_mp.unparse().c_str());
}
}
}
DEBUG_CHATTER("[RoutingPaths] Computed %d multipaths", sorted_multipaths.size());
Vector<Vector<Route> > best_multipaths;
for(int i=0;i<mymin(N, sorted_multipaths.size()); i++)
best_multipaths.push_back(sorted_multipaths[i]._routes);
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] We computed %d multipaths in %s seconds!", now.unparse().c_str(), best_multipaths.size(), (now - start).unparse().c_str());
if(_debug) {
StringAccum s;
s << "[RoutingPaths] Multipaths are \n";
for(int j=0;j<best_multipaths.size();j++) {
for (int i=0;i<best_multipaths[j].size();i++)
s << " " << best_multipaths[j][i].unparse() << " \n";
s << " --------------\n";
}
DEBUG_CHATTER(s.c_str());
}
if(wifi_only) {
if (!best_multipaths.empty() && !best_multipaths[0].empty() && !best_multipaths[0][0].links.empty())
_routes_table_mp_wifi.set(MultiPathDemand(dst, N, n), best_multipaths);
else
_routes_table_mp_wifi.erase(MultiPathDemand(dst, N, n));
}
else if(plc_only) {
if (!best_multipaths.empty() && !best_multipaths[0].empty() && !best_multipaths[0][0].links.empty())
_routes_table_mp_plc.set(MultiPathDemand(dst, N, n), best_multipaths);
else
_routes_table_mp_plc.erase(MultiPathDemand(dst, N, n));
}
else {
if (!best_multipaths.empty() && !best_multipaths[0].empty() && !best_multipaths[0][0].links.empty())
_routes_table_mp.set(MultiPathDemand(dst, N, n), best_multipaths);
else
_routes_table_mp.erase(MultiPathDemand(dst, N, n));
}
check_paths_valid(dst, best_multipaths, store_route, check_order);
return best_multipaths;
}
}
AdjacencyMatrix
RoutingPaths::update_capacities_adjacency_matrix_multi_paths(const AdjacencyMatrix mat, Route &path, uint32_t &max_achievable_capa, bool only_max_capa) {
uint32_t max_sum_weights = 0;
int tot_nb_links_contending = 0;
for(int i=0;i<path.links.size();i++) {
LinkRouting link = path.links[i];
uint32_t sum_weights = 0;
int nb_links_contending = 0;
for (int j=0;j<path.links.size();j++) {
if (i==j || _routing_links->are_contending(UndirectedLinkRouting(link), UndirectedLinkRouting(path.links[j]))) {
nb_links_contending++;
VirtualNodeRouting virtual_egress = VirtualNodeRouting(EGR_VN, path.links[j].src);
VirtualNeighbor virtual_neighbor = VirtualNeighbor(VirtualNodeRouting(ING_VN, path.links[j].dst),0);
int ind;
if(!is_in_hash_table(mat, virtual_egress) || (ind = find_in_vector(mat[virtual_egress], virtual_neighbor)) == -1)
sum_weights+=DEFAULT_WEIGHT;
else
sum_weights+=mat[virtual_egress][ind].weight;
}
}
if (sum_weights > max_sum_weights) {
max_sum_weights = sum_weights;
tot_nb_links_contending = nb_links_contending;
}
VirtualNodeRouting virtual_egress = VirtualNodeRouting(EGR_VN, path.links[i].src);
VirtualNeighbor virtual_neighbor = VirtualNeighbor(VirtualNodeRouting(ING_VN, path.links[i].dst),0);
int ind;
if(!is_in_hash_table(mat, virtual_egress) || (ind = find_in_vector(mat[virtual_egress], virtual_neighbor)) == -1)
path.links[i].weight == DEFAULT_WEIGHT;
else
path.links[i].weight = mat[virtual_egress][ind].weight;
}
if(max_sum_weights > 0)
max_achievable_capa = int_divide(SCALE_WEIGHTS, max_sum_weights);
else {
max_achievable_capa = 0;
tot_nb_links_contending = 1;
}
VERB_DEBUG_CHATTER("Max achievable capacity is %d (%d links contending)", max_achievable_capa, tot_nb_links_contending);
AdjacencyMatrix new_matrix = AdjacencyMatrix(mat);
if (!only_max_capa) {
for(int i=0;i<path.links.size();i++) {
Vector<UndirectedLinkRouting> contending_links = _routing_links->get_contending_links(path.links[i]);
contending_links.push_back(UndirectedLinkRouting(path.links[i].src, path.links[i].dst));
VERB_DEBUG_CHATTER("Links contending with %s are %s", path.links[i].unparse().c_str(), print_vector(contending_links).c_str());
for (int j=0;j<contending_links.size();j++) {
UndirectedLinkRouting cont_link = contending_links[j];
VirtualNodeRouting virt_src = VirtualNodeRouting(EGR_VN, cont_link.src);
VirtualNodeRouting virt_dst = VirtualNodeRouting(ING_VN, cont_link.dst);
int ind = find_in_vector(mat[virt_src], VirtualNeighbor(virt_dst,0));
if (ind == -1) {
virt_src = VirtualNodeRouting(EGR_VN, cont_link.dst);
virt_dst = VirtualNodeRouting(ING_VN, cont_link.src);
ind = find_in_vector(mat[virt_src], VirtualNeighbor(virt_dst,0));
}
VirtualNodeRouting virt_src_ing = VirtualNodeRouting(ING_VN, virt_src.eth);
int ind_src_ing_egr = find_in_vector(mat[virt_src_ing], VirtualNeighbor(virt_src,0));
if (ind != -1) {
if (mat[virt_src][ind].weight == new_matrix[virt_src][ind].weight) {
// link not modified yet
bool update_csc = false;
if(ind_src_ing_egr!=-1 && mat[virt_src][ind].weight == mat[virt_src_ing][ind_src_ing_egr].weight)
// must update CSC as well
update_csc = true;
int remaining_time = 1000;
for (int k=0;k<path.links.size();k++) {
if(_routing_links->are_contending(cont_link, path.links[k])) {
VirtualNodeRouting virt_src_path = VirtualNodeRouting(EGR_VN, path.links[k].src);
int ind_link_path = find_in_vector(mat[virt_src_path], VirtualNeighbor(VirtualNodeRouting(ING_VN, path.links[k].dst),0));
uint32_t capa_link;
if(mat[virt_src_path][ind_link_path].weight > 0)
capa_link = int_divide(SCALE_WEIGHTS, mat[virt_src_path][ind_link_path].weight);
else
capa_link = 0;
if(capa_link > 0)
remaining_time -= int_divide(1000*max_achievable_capa, capa_link);
else
remaining_time = 0;
VERB_DEBUG_CHATTER("[RoutingPaths] Link %s is contending with %s (capa %d): remaining_time = %d", cont_link.unparse().c_str(),
path.links[k].unparse().c_str(), capa_link, remaining_time);
if (remaining_time <= 0) {
remaining_time = 0;
break;
}
}
}
if (mat[virt_src][ind].weight >= remaining_time*int_divide(DEFAULT_WEIGHT, 1000)) {
new_matrix[virt_src][ind].weight = DEFAULT_WEIGHT;
}
else {
uint64_t weight64 = (uint64_t) mat[virt_src][ind].weight;
new_matrix[virt_src][ind].weight = (uint32_t) int_divide(weight64*1000, remaining_time);
if(update_csc && (new_matrix[virt_src_ing][ind_src_ing_egr].weight == mat[virt_src_ing][ind_src_ing_egr].weight ||
new_matrix[virt_src][ind].weight < new_matrix[virt_src_ing][ind_src_ing_egr].weight)) {
VERB_DEBUG_CHATTER("[RoutingPaths] Update CSC for %s->%s, was %s, is %s", virt_src_ing.unparse().c_str(),
new_matrix[virt_src_ing][ind_src_ing_egr].neighbor.unparse().c_str(),
String(new_matrix[virt_src_ing][ind_src_ing_egr].weight).c_str(),
String(new_matrix[virt_src][ind].weight).c_str());
new_matrix[virt_src_ing][ind_src_ing_egr].weight = new_matrix[virt_src][ind].weight;
}
}
update_csc = false;
VERB_DEBUG_CHATTER("[RoutingPaths] New weight for link %s (was %d, remaining time %d): %d", cont_link.unparse().c_str(), mat[virt_src][ind].weight,
remaining_time, new_matrix[virt_src][ind].weight);
EtherAddress src_eth = virt_src.eth;
virt_src = VirtualNodeRouting(EGR_VN, virt_dst.eth);
virt_dst = VirtualNodeRouting(ING_VN, src_eth);
virt_src_ing = VirtualNodeRouting(ING_VN, virt_src.eth);
ind_src_ing_egr = find_in_vector(mat[virt_src_ing], VirtualNeighbor(virt_src,0));
ind = find_in_vector(mat[virt_src], VirtualNeighbor(virt_dst,0));
if(ind != -1) {
if(ind_src_ing_egr!=-1 && mat[virt_src][ind].weight == mat[virt_src_ing][ind_src_ing_egr].weight)
// must update CSC as well
update_csc = true;
if (mat[virt_src][ind].weight >= remaining_time*int_divide(DEFAULT_WEIGHT, 1000))
new_matrix[virt_src][ind].weight = DEFAULT_WEIGHT;
else {
uint64_t weight64 = (uint64_t) mat[virt_src][ind].weight;
new_matrix[virt_src][ind].weight = (uint32_t) int_divide(weight64*1000, remaining_time);
if(update_csc && (new_matrix[virt_src_ing][ind_src_ing_egr].weight == mat[virt_src_ing][ind_src_ing_egr].weight ||
new_matrix[virt_src][ind].weight < new_matrix[virt_src_ing][ind_src_ing_egr].weight)) {
VERB_DEBUG_CHATTER("[RoutingPaths] Update CSC for %s->%s, was %s, is %s", virt_src_ing.unparse().c_str(),
new_matrix[virt_src_ing][ind_src_ing_egr].neighbor.unparse().c_str(),
String(new_matrix[virt_src_ing][ind_src_ing_egr].weight).c_str(),
String(new_matrix[virt_src][ind].weight).c_str());
new_matrix[virt_src_ing][ind_src_ing_egr].weight = new_matrix[virt_src][ind].weight;
}
}
VERB_DEBUG_CHATTER("[RoutingPaths] New weight for anti-link %s (was %d, remaining time %d): %d", cont_link.unparse().c_str(), mat[virt_src][ind].weight,
remaining_time, new_matrix[virt_src][ind].weight);
}
}
}
else
VERB_DEBUG_CHATTER("[RoutingPaths] Link %s->%s not found in adjacency matrix",
virt_src.eth.unparse().c_str(), virt_dst.eth.unparse().c_str());
}
}
}
// add a penalty of 10% for each link contending (non-perfect MAC)
max_achievable_capa -= ((tot_nb_links_contending-1)*max_achievable_capa)/10;
return new_matrix;
}
bool
RoutingPaths::are_neighbors(EtherAddress node1, EtherAddress node2) const {
return (is_in_vector(_routing_links->get_neighbor_links()[node1], RealNeighbor(node2)));
}
bool RoutingPaths::are_neighbors(LinkRouting link1, LinkRouting link2) const {
return are_neighbors(link1.src, link2.src) || are_neighbors(link1.src, link2.dst) ||
are_neighbors(link1.dst, link2.src) || are_neighbors(link1.dst, link2.dst);
}
Route
RoutingPaths::get_route(IPAddress dst) {
Timestamp now;
if (dst == me.ip)
return Route();
Route route = get_route_no_gw(dst);
if(_test_capa_one_hop)
return route;
if(route.links.empty()) {
if(_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] No route to %s, packet sent to default gateway", now.unparse().c_str(), dst.unparse().c_str());
if (_default_gw_ip == me.ip)
return Route();
if (is_in_hash_table(_routes_table_mp,MultiPathDemand(_default_gw_ip, 1, 1) ) && !_routes_table_mp[MultiPathDemand(_default_gw_ip, 1, 1)].empty() &&
!_routes_table_mp[MultiPathDemand(_default_gw_ip, 1, 1)][0].empty()) {
route = _routes_table_mp[MultiPathDemand(_default_gw_ip, 1, 1)][0][0];
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Got path to gateway! Path is %s", now.unparse().c_str(), route.unparse().c_str());
return route;
}
else {
VirtualRoute virtual_route = compute_shortest_path_to
(VirtualNodeRouting(DST_VN, _default_gw_ip),adjacency_matrix, dijkstra_result);
DEBUG_CHATTER("[RoutingPaths %s] Got virtual path to gateway! Virtual path is %s. Getting real path...", now.unparse().c_str(), virtual_route.unparse().c_str());
route = virtual_route_to_route(virtual_route);
route.ip = _default_gw_ip;
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Got real path! Path is %s", now.unparse().c_str(), route.unparse().c_str());
if (!route.links.empty()) {
uint32_t C_max_P;
update_capacities_adjacency_matrix_multi_paths(adjacency_matrix, route, C_max_P, true);
route.max_capa = C_max_P;
_routes_table_mp.set(MultiPathDemand(route.ip, 1, 1), Vector<Vector<Route> >(1,Vector<Route>(1,route)));
}
else
_routes_table_mp.erase(MultiPathDemand(route.ip, 1, 1));
}
}
return route;
}
Route
RoutingPaths::get_route_no_gw(IPAddress dst) {
Timestamp now;
if (_debug)
now.assign_now();
if(is_in_hash_table(_routes_table_mp, MultiPathDemand(dst, 1, 1)) && !_routes_table_mp[MultiPathDemand(dst, 1, 1)].empty() &&
!_routes_table_mp[MultiPathDemand(dst, 1, 1)][0].empty()) {
if (_debug)
now.assign_now();
Route route = _routes_table_mp[MultiPathDemand(dst, 1, 1)][0][0];
DEBUG_CHATTER("[RoutingPaths %s] Got real path! Path is %s", now.unparse().c_str(), route.unparse().c_str());
return route;
}
if (_test_capa_one_hop) {
Vector<NodeRouting> nodes = _routing_links->get_nodes_in_network();
DEBUG_CHATTER("Searching one-hop route...");
int ind_node = find_in_vector(nodes, NodeRouting(dst));
if (ind_node == -1) {
DEBUG_CHATTER("Destination node unknown");
return Route();
}
else {
NodeRouting node_dst = nodes[ind_node];
for (int i=0;i<node_dst.interfaces.size();i++) {
EtherAddress my_eth;
EtherAddress eth_dst = node_dst.interfaces[i];
if(_test_capa_one_hop_wifi)
if (me.unique_interface == INTERFACE1)
my_eth = me.interfaces[0];
else
my_eth = me.interfaces[INTERFACE1];
else
my_eth = me.interfaces[INTERFACE2];
int ind_neighbor = find_in_vector(_routing_links->get_neighbor_links()[my_eth], RealNeighbor(eth_dst));
if(ind_neighbor >= 0) {
RealNeighbor neighbor = _routing_links->get_neighbor_links()[my_eth][ind_neighbor];
Route route;
LinkRouting link = LinkRouting(my_eth, eth_dst, neighbor.weight);
route.links.push_back(link);
route.weight = neighbor.weight;
route.ip = dst;
DEBUG_CHATTER("Found route %s", route.unparse().c_str());
if (!route.links.empty()) {
uint32_t C_max_P;
update_capacities_adjacency_matrix_multi_paths(adjacency_matrix, route, C_max_P, true);
route.max_capa = C_max_P;
_routes_table_mp.set(MultiPathDemand(route.ip, 1, 1), Vector<Vector<Route> >(1,Vector<Route>(1,route)));
}
else
_routes_table_mp.erase(MultiPathDemand(route.ip, 1, 1));
return route;
}
}
DEBUG_CHATTER("Node is not a neighbor");
return Route();
}
}
DEBUG_CHATTER("[RoutingPaths %s] Getting path to destination %s...", now.unparse().c_str(), dst.unparse().c_str());
VirtualRoute virtual_route = compute_shortest_path_to
(VirtualNodeRouting(DST_VN, dst),adjacency_matrix, dijkstra_result);
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Got virtual path! Virtual path is %s. Getting real path...", now.unparse().c_str(), virtual_route.unparse().c_str());
Route route = virtual_route_to_route(virtual_route);
route.ip = dst;
if (_debug)
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Got real path! Path is %s", now.unparse().c_str(), route.unparse().c_str());
if (!route.links.empty()) {
uint32_t C_max_P;
update_capacities_adjacency_matrix_multi_paths(adjacency_matrix, route, C_max_P, true);
route.max_capa = C_max_P;
_routes_table_mp.set(MultiPathDemand(route.ip, 1, 1), Vector<Vector<Route> >(1,Vector<Route>(1,route)));
}
else
_routes_table_mp.erase(MultiPathDemand(route.ip, 1, 1));
return route;
}
Packet *
RoutingPaths::add_source_routing(Packet * p_in, Route source_route) {
Timestamp now;
if(source_route.links.size() > HDR_ROUTE_SIZE) {
click_chatter("[RoutingPaths %s] Route is too long", now.unparse().c_str());
return 0;
}
// the source and destination addresses are not included
// as hops in the source route
// add the extra header size and get a new packet
WritablePacket *p = p_in->push(sizeof(acne_header));
if (!p) {
if (_debug)
now.assign_now();
click_chatter("[RoutingPaths %s] Couldn't add space for acne header\n", now.unparse().c_str());
return p;
}
// add the fixed header
acne_header *hdr = (acne_header *)(p->data());
int last = source_route.links.size() - 1;
hdr->_type = REGULAR_TRAFFIC; // regular IP traffic
hdr->_hop = 0;
for (int b=0;b<NB_BYTES_HOP;b++) {
hdr->_route._dst[b] = source_route.links[last].dst.data()[6-NB_BYTES_HOP+b];
}
for (int i=0; i<source_route.links.size(); i++) {
unsigned char *data = source_route.links[i].dst.data();
for (int b=0;b<NB_BYTES_HOP;b++) {
hdr->_route._route[NB_BYTES_HOP*i+b] = data[6-NB_BYTES_HOP+b];
}
}
return p;
}
Packet *
RoutingPaths::update_routing_header(Packet *p_in, EtherAddress& next_hop) {
acne_header *hdr = (acne_header *)(p_in->data());
bool is_me = false;
for (int i=0;i<me.interfaces.size();i++) {
unsigned char *first_byte_this_hop = &hdr->_route._route[NB_BYTES_HOP*hdr->_hop];
if(are_last_bytes_in_addr(first_byte_this_hop, me.interfaces[i])) {
is_me = true;
break;
}
}
if (is_me) {
hdr->_hop++;
next_hop = get_eth_address_source_routing(hdr->_route._route, hdr->_hop);
}
else {
// I'm not in the route
next_hop = _empty_eth;
}
return p_in;
}
Packet *
RoutingPaths::delete_routing_header(Packet *p_in) {
p_in->pull(sizeof(acne_header));
click_ip *ip=(click_ip *)(p_in->data());
p_in->set_ip_header(ip, sizeof(click_ip));
return p_in;
}
EtherAddress
RoutingPaths::get_eth_address_source_routing(unsigned char *route, uint8_t hop) const {
unsigned char data[NB_BYTES_HOP];
for (int b=0;b<NB_BYTES_HOP;b++) {
data[b] = route[hop*NB_BYTES_HOP + b];
}
return _routing_links->get_ether_address(data);
}
Route
RoutingPaths::virtual_route_to_route(VirtualRoute virtual_route) {
Route route;
if (virtual_route.weight >= DEFAULT_WEIGHT)
return Route();
for(int i=0;i<virtual_route.route.size();i++) {
if (virtual_route.route[i].neighbor.type == EGR_VN) {
uint32_t weight = virtual_route.route[i+1].weight;
// check if one interface of next node is already in the route (loop in the real graph)
int ind_next_node_in_route = -1;
NodeRouting next_node = _routing_links->get_node_from_eth(virtual_route.route[i+1].neighbor.eth);
for (int j=0;j<next_node.interfaces.size();j++) {
int ind = route.is_in_route_src(next_node.interfaces[j]);
if (ind != -1) {
ind_next_node_in_route = ind;
break; // can appear only once
}
}
if(ind_next_node_in_route == -1)
route.links.push_back(LinkRouting(virtual_route.route[i].neighbor.eth, virtual_route.route[i+1].neighbor.eth, weight));
else // loop in real graph
route.links.erase(&route.links[ind_next_node_in_route], route.links.end());
}
}
route.weight = virtual_route.weight;
return route;
}
void
RoutingPaths::recompute_adjacency_matrix() {
// Note: recompute_adjacency_metric is very time-consuming, should be used rarely!
Timestamp now;
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Computing adjacency matrix...", now.unparse().c_str());
VERB_DEBUG_CHATTER("[RoutingPaths %s] Clearing adjacency matrix...", now.unparse().c_str());
adjacency_matrix.clear();
adjacency_matrix_wifi_only.clear();
adjacency_matrix_plc_only.clear();
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Adjacency matrix cleared!", now.unparse().c_str());
Vector<NodeRouting> nodes = _routing_links->get_nodes_in_network();
VERB_DEBUG_CHATTER("[RoutingPaths %s] %d nodes to transform", now.unparse().c_str(), nodes.size());
// add virtual nodes and corresponding links for all node in the network
for (int i_node = 0;i_node < nodes.size();i_node++) {
VERB_DEBUG_CHATTER("[RoutingPaths %s] Node %d has %d interfaces", now.unparse().c_str(), i_node,
nodes[i_node].interfaces.size());
NodeRouting this_node = nodes[i_node];
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Transforming node %d, with %d interfaces...", now.unparse().c_str(), i_node, this_node.interfaces.size());
// add virtual nodes X+ (with links to in-node egresses) and X- (links to in-node ingresses)
IPAddress addr_node;
addr_node = this_node.ip;
Vector<VirtualNeighbor> virtual_neighbors_plus;
Vector<VirtualNeighbor> virtual_neighbors_plus_wifi;
Vector<VirtualNeighbor> virtual_neighbors_plus_plc;
uint32_t min_weight = DEFAULT_WEIGHT;
// add ingress and egress node for each interface
for (int i=0;i < this_node.interfaces.size();i++) {
VERB_DEBUG_CHATTER("[RoutingPaths %s] Transforming interface %d of %d...", now.unparse().c_str(), i, this_node.interfaces.size());
EtherAddress addr_interface = this_node.interfaces[i];
Vector<RealNeighbor> neighbors = _routing_links->get_neighbor_links().get(addr_interface);
VirtualNodeRouting egr_node = VirtualNodeRouting(EGR_VN, addr_interface);
Vector<VirtualNeighbor> virtual_neighbors_egr;
// neighbors represents the real neighbors: add the corresponding virtual neighbors (egress->ingress)
for(int j=0;j < neighbors.size();j++) {
virtual_neighbors_egr.push_back(VirtualNeighbor(
VirtualNodeRouting(ING_VN, neighbors[j].neighbor), neighbors[j].weight));
if(neighbors[j].weight < min_weight)
min_weight = neighbors[j].weight;
}
adjacency_matrix.set(egr_node, virtual_neighbors_egr);
if(is_wifi_addr(addr_interface))
adjacency_matrix_wifi_only.set(egr_node, virtual_neighbors_egr);
if(is_plc_addr(addr_interface))
adjacency_matrix_plc_only.set(egr_node, virtual_neighbors_egr);
}
for (int i=0;i < this_node.interfaces.size();i++) {
EtherAddress addr_interface = this_node.interfaces[i];
VirtualNodeRouting ingr_node = VirtualNodeRouting(ING_VN, addr_interface);
Vector<VirtualNeighbor> virtual_neighbors_ingr;
Vector<VirtualNeighbor> virtual_neighbors_ingr_wifi;
Vector<VirtualNeighbor> virtual_neighbors_ingr_plc;
// add the in-node ingress->egress links
for (int j=0;j<this_node.interfaces.size();j++) {
EtherAddress addr_interface2 = this_node.interfaces[j];
uint32_t CSC = 0;
// if same interface, CSC is min_weight
if(i==j && _csc_choice.compare("no") != 0)
CSC = min_weight;
virtual_neighbors_ingr.push_back(VirtualNeighbor(VirtualNodeRouting(EGR_VN, addr_interface2), CSC));
if(is_wifi_addr(addr_interface2))
virtual_neighbors_ingr_wifi.push_back(VirtualNeighbor(VirtualNodeRouting(EGR_VN, addr_interface2), 0));
if(is_plc_addr(addr_interface2))
virtual_neighbors_ingr_plc.push_back(VirtualNeighbor(VirtualNodeRouting(EGR_VN, addr_interface2), 0));
}
// X+->egress, ingress->X-
virtual_neighbors_plus.push_back(VirtualNeighbor(VirtualNodeRouting(EGR_VN, addr_interface), 0));
virtual_neighbors_ingr.push_back(VirtualNeighbor(VirtualNodeRouting(DST_VN, addr_node), 0));
adjacency_matrix.set(ingr_node, virtual_neighbors_ingr);
if(is_wifi_addr(addr_interface)) {
virtual_neighbors_plus_wifi.push_back(VirtualNeighbor(VirtualNodeRouting(EGR_VN, addr_interface), 0));
virtual_neighbors_ingr_wifi.push_back(VirtualNeighbor(VirtualNodeRouting(DST_VN, addr_node), 0));
adjacency_matrix_wifi_only.set(ingr_node, virtual_neighbors_ingr_wifi);
}
if(is_plc_addr(addr_interface)) {
virtual_neighbors_plus_plc.push_back(VirtualNeighbor(VirtualNodeRouting(EGR_VN, addr_interface), 0));
virtual_neighbors_ingr_plc.push_back(VirtualNeighbor(VirtualNodeRouting(DST_VN, addr_node), 0));
adjacency_matrix_plc_only.set(ingr_node, virtual_neighbors_ingr_plc);
}
}
adjacency_matrix.set(VirtualNodeRouting(SRC_VN, addr_node), virtual_neighbors_plus);
adjacency_matrix.set(VirtualNodeRouting(DST_VN, addr_node), Vector<VirtualNeighbor>());
adjacency_matrix_wifi_only.set(VirtualNodeRouting(SRC_VN, addr_node), virtual_neighbors_plus_wifi);
adjacency_matrix_wifi_only.set(VirtualNodeRouting(DST_VN, addr_node), Vector<VirtualNeighbor>());
adjacency_matrix_plc_only.set(VirtualNodeRouting(SRC_VN, addr_node), virtual_neighbors_plus_plc);
adjacency_matrix_plc_only.set(VirtualNodeRouting(DST_VN, addr_node), Vector<VirtualNeighbor>());
if (_debug)
now.assign_now();
VERB_DEBUG_CHATTER("[RoutingPaths %s] Node transformed!", now.unparse().c_str());
}
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Adjacency matrix computed.", now.unparse().c_str());
}
void
RoutingPaths::dijkstra_compute_paths(VirtualNodeRouting source,
const AdjacencyMatrix adjacency_mat,
HashTable<VirtualNodeRouting,uint32_t> &min_distance,
HashTable<VirtualNodeRouting, VirtualNodeRouting> &previous)
{
min_distance.clear();
previous.clear();
for(AdjacencyMatrix::const_iterator it=adjacency_mat.begin();
it != adjacency_mat.end();it++) {
min_distance.set(it->first, DEFAULT_WEIGHT);
previous.set(it->first, VirtualNodeRouting());
}
min_distance.set(source,0);
SetNeighbor vertex_queue;
vertex_queue.insert_neighbor(VirtualNeighbor(source, min_distance[source]));
while (!vertex_queue.empty())
{
uint32_t dist = vertex_queue.begin().weight;
VirtualNodeRouting u = vertex_queue.begin().neighbor;
vertex_queue.erase_neighbor(vertex_queue.begin());
// Visit each edge exiting u
const Vector<VirtualNeighbor> neighbors = adjacency_mat[u];
for(int i=0; i < neighbors.size();i++) {
VirtualNodeRouting v = neighbors[i].neighbor;
uint32_t weight = neighbors[i].weight;
uint32_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v]) {
vertex_queue.erase_neighbor(VirtualNeighbor(v,min_distance[v]));
min_distance.set(v,distance_through_u);
previous.set(v,u);
vertex_queue.insert_neighbor(VirtualNeighbor(v,min_distance[v]));
}
}
}
}
void
RoutingPaths::bellmanford_compute_paths(VirtualNodeRouting source,
const AdjacencyMatrix adjacency_mat,
HashTable<VirtualNodeRouting,uint32_t> &min_distance,
HashTable<VirtualNodeRouting, VirtualNodeRouting> &previous)
{
min_distance.clear();
previous.clear();
for(AdjacencyMatrix::const_iterator it=adjacency_mat.begin();
it != adjacency_mat.end();it++) {
min_distance.set(it->first, DEFAULT_WEIGHT);
previous.set(it->first, VirtualNodeRouting());
}
min_distance.set(source,0);
bool weights_changed = true;
while (weights_changed) { // converge after at most (nb_nodes - 1) steps
weights_changed = false;
for(AdjacencyMatrix::const_iterator it=adjacency_mat.begin();
it != adjacency_mat.end();it++) {
VirtualNodeRouting u = it->first;
uint32_t dist = min_distance[u];
// Visit each edge exiting u
const Vector<VirtualNeighbor> neighbors = adjacency_mat[u];
for(int i=0; i < neighbors.size();i++) {
VirtualNodeRouting v = neighbors[i].neighbor;
uint32_t weight = neighbors[i].weight;
uint32_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v]) {
min_distance.set(v,distance_through_u);
previous.set(v,u);
weights_changed = true;
}
}
}
}
if (_debug) { // check
for(AdjacencyMatrix::const_iterator it=adjacency_mat.begin();
it != adjacency_mat.end();it++) {
VirtualNodeRouting u = it.key();
uint32_t dist = min_distance[u];
// Visit each edge exiting u
const Vector<VirtualNeighbor> neighbors = adjacency_mat[u];
for(int i=0; i < neighbors.size();i++) {
VirtualNodeRouting v = neighbors[i].neighbor;
uint32_t weight = neighbors[i].weight;
uint32_t distance_through_u = dist + weight;
if (distance_through_u < min_distance[v])
DEBUG_CHATTER("Error, negative weight cycle for %s and %s", u.unparse().c_str(), v.unparse().c_str());
}
}
}
}
VirtualRoute
RoutingPaths::compute_shortest_path_to(VirtualNodeRouting dst,
const AdjacencyMatrix adjacency_mat,
const HashTable<VirtualNodeRouting,VirtualNodeRouting> previous)
{
Timestamp now;
if (_debug)
now.assign_now();
VirtualRoute path;
VirtualNodeRouting null = VirtualNodeRouting();
int count_loop = 0;
while(dst != null) {
path.route.push_front(VirtualNeighbor(dst, 0));
if(path.route.size() > 1) {
int ind = find_in_vector(adjacency_mat[dst], path.route[1]);
if (ind >= 0) {
uint32_t weight = adjacency_mat[dst][ind].weight;
path.route[1].weight = weight;
path.weight += weight;
//VERB_DEBUG_CHATTER("[RoutingPaths %s] Virtual link %s added", now.unparse().c_str(), path.route[1].unparse().c_str() );
}
else { //should not happen
click_chatter("Warning, virtual node not in network");
return VirtualRoute();
}
}
dst = previous[dst];
count_loop++;
if(count_loop > 20)
break;
}
return path;
}
VirtualRoute
RoutingPaths::get_shortest_path_dij(const AdjacencyMatrix adj_mat, const VirtualNodeRouting src, const VirtualNodeRouting dst)
{
HashTable<VirtualNodeRouting,VirtualNodeRouting> dijkstra_result_loc;
HashTable<VirtualNodeRouting, uint32_t> min_distances;
dijkstra_compute_paths(src, adj_mat,min_distances, dijkstra_result_loc);
VirtualRoute virtual_path = compute_shortest_path_to(dst,adj_mat,dijkstra_result_loc);
return virtual_path;
}
VirtualRoute
RoutingPaths::get_shortest_path_bf(const AdjacencyMatrix adj_mat, const VirtualNodeRouting src, const VirtualNodeRouting dst)
{
HashTable<VirtualNodeRouting,VirtualNodeRouting> bf_result_loc;
HashTable<VirtualNodeRouting, uint32_t> min_distances;
bellmanford_compute_paths(src, adj_mat,min_distances, bf_result_loc);
VirtualRoute virtual_path = compute_shortest_path_to(dst,adj_mat,bf_result_loc);
return virtual_path;
}
Vector<Route>
RoutingPaths::get_k_shortest_paths(const AdjacencyMatrix adj_mat, const VirtualNodeRouting src, const VirtualNodeRouting dst, int K, VirtualRoute& virtual_best_path)
{
// Yen's algorithm for finding k-shortest paths (pseudo-code from Wikipedia)
//
// function YenKSP(Graph, source, sink, K):
// // Determine the shortest path from the source to the sink.
// A[0] = Dijkstra(Graph, source, sink);
// // Initialize the heap to store the potential kth shortest path.
// B = [];
// for k from 1 to K:
// // The spur node ranges from the first node to the next to last node in the shortest path.
// for i from 0 to size(A[k − 1]) − 1:
// // Spur node is retrieved from the previous k-shortest path, k − 1.
// spurNode = A[k-1].node(i);
// // The sequence of nodes from the source to the spur node of the previous k-shortest path.
// rootPath = A[k-1].nodes(0, i);
// for each path p in A:
// if rootPath == p.nodes(0, i):
// // Remove the links that are part of the previous shortest paths which share the same root path.
// remove p.edge(i, i + 1) from Graph;
// // Calculate the spur path from the spur node to the sink.
// spurPath = Dijkstra(Graph, spurNode, sink);
// // Entire path is made up of the root path and spur path.
// totalPath = rootPath + spurPath;
// // Add the potential k-shortest path to the heap.
// B.append(totalPath);
// // Add back the edges that were removed from the graph.
// restore edges to Graph;
// // Sort the potential k-shortest paths by cost.
// B.sort();
// // Add the lowest cost path becomes the k-shortest path.
// A[k] = B[0];
// B.pop();
// return A;
Timestamp now;
if (_debug)
now.assign_now();
// src should be SRC_VN, dst DST_VN
Vector<Route> k_shortest_paths; // corresponds to A
if (src.type == SRC_VN && dst.type == DST_VN) {
Vector<VirtualRoute> k_shortest_virt_paths; // corresponds to A (virtual)
VirtualRoute first_virt_path = get_shortest_path_dij(adj_mat, src, dst);
Route first_path = virtual_route_to_route(first_virt_path);
first_path.ip = dst.ip;
virtual_best_path = first_virt_path;
if (first_path == Route()) {
return Vector<Route>(1,Route());
}
k_shortest_paths.push_back(first_path);
k_shortest_virt_paths.push_back(first_virt_path);
VERB_DEBUG_CHATTER("Path %s found, k=1", first_path.unparse().c_str());
Vector<VirtualRoute> potential_virt_paths; // corresponds to B (virtual)
Vector<Route> potential_real_paths;
Vector<uint32_t> weights_potential_paths;
AdjacencyMatrix adj_mat_loc = adj_mat;
int k=1;
while(k<K) {
VirtualRoute last_path = k_shortest_virt_paths.back();
VirtualRoute rootPath;
for (int i=0;i < (last_path.route.size() - 2);i++) { //do not consider last link in virtual path (-> DST_VN)
VirtualNodeRouting spurNode = last_path.route[i].neighbor;
VERB_DEBUG_CHATTER("[RoutingPaths] Spur node is %s, root path is %s", spurNode.unparse().c_str(), rootPath.unparse().c_str());
for (int p=0;p<k_shortest_virt_paths.size();p++) {
bool remove;
// test if rootPath == p.nodes(0, i)
if (k_shortest_virt_paths[p].route.size() > i) {
remove = true;
for (int j=0;j<=i;j++) {
if (last_path.route[j]!=k_shortest_virt_paths[p].route[j]) {
remove = false;
break;
}
}
}
else
remove = false;
if (remove) {
int ind_neighbor = find_in_vector(adj_mat_loc[k_shortest_virt_paths[p].route[i].neighbor], k_shortest_virt_paths[p].route[i+1]);
if (ind_neighbor != -1) {
VERB_DEBUG_CHATTER("[RoutingPaths] Remove link between %s and %s", k_shortest_virt_paths[p].route[i].neighbor.unparse().c_str(),
k_shortest_virt_paths[p].route[i+1].unparse().c_str());
adj_mat_loc[k_shortest_virt_paths[p].route[i].neighbor][ind_neighbor].weight = DEFAULT_WEIGHT;
}
else //should not happen
click_chatter("[RoutingPaths %s] Error! Next node is not a neighbor", now.unparse().c_str());
// if node i is virtual source (i.e. we remove SRC_VN->EGR), remove as well ING->EGR (to avoid loops)
if (k_shortest_virt_paths[p].route[i].neighbor == src) {
for(int j=0;j<adj_mat_loc[k_shortest_virt_paths[p].route[i].neighbor].size();j++) {
VirtualNodeRouting egr_neighbor = adj_mat_loc[k_shortest_virt_paths[p].route[i].neighbor][j].neighbor;
VirtualNodeRouting ing_neighbor = VirtualNodeRouting(ING_VN, egr_neighbor.eth);
int ind = find_in_vector(adj_mat_loc[ing_neighbor], k_shortest_virt_paths[p].route[i+1]);
if(ind != -1) {
VERB_DEBUG_CHATTER("[RoutingPaths] Remove link between %s and %s", ing_neighbor.unparse().c_str(),
k_shortest_virt_paths[p].route[i+1].unparse().c_str());
adj_mat_loc[ing_neighbor][ind].weight = DEFAULT_WEIGHT;
}
else //should not happen
click_chatter("[RoutingPaths %s] Error! Next node is not a neighbor", now.unparse().c_str());
}
}
}
}
// nodes in rootPath cannot be included in the path (to avoid loops): remove them of adj_mat
for(int j=0;j<rootPath.route.size();j++) {
if (rootPath.route[j].neighbor.type == ING_VN || rootPath.route[j].neighbor.type == EGR_VN) {
NodeRouting node_path = _routing_links->get_node_from_eth(rootPath.route[j].neighbor.eth);
for (int l=0;l<node_path.interfaces.size();l++) {
adj_mat_loc.erase(VirtualNodeRouting(ING_VN, node_path.interfaces[l]));
adj_mat_loc.erase(VirtualNodeRouting(EGR_VN, node_path.interfaces[l]));
}
}
else
adj_mat_loc.erase(rootPath.route[j].neighbor);
}
// if spurNode is egress, remove corresponding ingresses (to avoid loops)
if (spurNode.type == EGR_VN) {
NodeRouting node_path = _routing_links->get_node_from_eth(spurNode.eth);
for (int l=0;l<node_path.interfaces.size();l++) {
adj_mat_loc.erase(VirtualNodeRouting(ING_VN, node_path.interfaces[l]));
}
}
// find shortest path
VirtualRoute spurPath = get_shortest_path_dij(adj_mat_loc, spurNode, dst);
// add weight of link between last node of rootPath and first node of spurPath
if (spurPath != VirtualRoute() && spurPath.route[0].neighbor == spurNode) {
VERB_DEBUG_CHATTER("[RoutingPaths] SpurPath is %s", spurPath.unparse().c_str());
VirtualRoute totalPath_virt = rootPath.concat_routes(spurPath, adj_mat);
// add shortest path to B
Route totalPath_real = virtual_route_to_route(totalPath_virt);
totalPath_real.ip = dst.ip;
if (totalPath_real != Route() && !is_in_vector(k_shortest_paths, totalPath_real)) {
potential_virt_paths.push_back(totalPath_virt);
potential_real_paths.push_back(totalPath_real);
weights_potential_paths.push_back(totalPath_virt.weight);
VERB_DEBUG_CHATTER("[RoutingPaths] Add potential path %s with weight %u", totalPath_real.unparse().c_str(), totalPath_virt.weight);
}
}
adj_mat_loc = adj_mat; // restore graph
rootPath.add_node(last_path.route[i]); // add spurNode to rootPath
}
assert(potential_virt_paths.size()==potential_real_paths.size());
assert(potential_virt_paths.size()==weights_potential_paths.size());
if(_verb_debug) {
VERB_DEBUG_CHATTER("List potential paths\n");
for(int count=0;count<potential_virt_paths.size();count++) {
VERB_DEBUG_CHATTER("%s", potential_virt_paths[count].unparse().c_str());
VERB_DEBUG_CHATTER("%s", potential_real_paths[count].unparse().c_str());
VERB_DEBUG_CHATTER("%u\n", weights_potential_paths[count]);
}
}
// find best path (minimum weight)
//if ((k + potential_virt_paths.size()) >= K) {
//while (k < K) {
int ind_min = find_min(weights_potential_paths);
if (ind_min != -1 && weights_potential_paths[ind_min] < DEFAULT_WEIGHT) {
if(!is_in_vector(k_shortest_paths, potential_real_paths[ind_min])) {
// insert best path in A
k_shortest_virt_paths.push_back(potential_virt_paths[ind_min]);
k_shortest_paths.push_back(potential_real_paths[ind_min]);
k++;
VERB_DEBUG_CHATTER("Path %s found, k=%d", potential_real_paths[ind_min].unparse().c_str(), k);
}
// remove best path from B
potential_virt_paths.erase(&potential_virt_paths[ind_min]);
potential_real_paths.erase(&potential_real_paths[ind_min]);
weights_potential_paths.erase(&weights_potential_paths[ind_min]);
}
else { // no more paths: break
VERB_DEBUG_CHATTER("Found %d/%d paths; no more paths", k, K);
k=K;
}
//}
// }
// else {
// int ind_min = find_min(weights_potential_paths);
// if (ind_min != -1 && weights_potential_paths[ind_min] < DEFAULT_WEIGHT) {
// // insert best path in A
// k_shortest_virt_paths.push_back(potential_virt_paths[ind_min]);
// k_shortest_paths.push_back(potential_real_paths[ind_min]);
// k++;
// VERB_DEBUG_CHATTER("Path %s found, k=%d", potential_real_paths[ind_min].unparse().c_str(), k);
// // remove best path from B
// potential_virt_paths.erase(&potential_virt_paths[ind_min]);
// weights_potential_paths.erase(&weights_potential_paths[ind_min]);
// }
// else { // no more paths: break
// VERB_DEBUG_CHATTER("Found %d paths; no more paths", k);
// k=K;
// }
// }
}
}
else
click_chatter("[RoutingPaths %s] WARNING: Paths can only be found between SRC_VN and DST_VN", now.unparse().c_str());
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] KShortestPaths done. Found %d paths", now.unparse().c_str(), k_shortest_paths.size());
return k_shortest_paths;
}
Vector<Route>
RoutingPaths::get_k_shortest_paths(const AdjacencyMatrix adj_mat, const VirtualNodeRouting src, const VirtualNodeRouting dst, int K)
{
VirtualRoute virtual_path;
return get_k_shortest_paths(adj_mat, src, dst, K, virtual_path);
}
void RoutingPaths::check_paths_valid(IPAddress dst, Vector<Vector<Route> > multipaths, bool store_route, bool check_order) {
if (check_order && _routing_links->get_has_order()) {
if (!equals_vector(multipaths, _last_seen_routes_mp[dst])) {
// paths are different: should notify dst in LinkState packets
Vector<Route> invalid_paths;
for(int i=0;i<_last_seen_routes_mp[dst].size();i++) {
for(int j=0;j<_last_seen_routes_mp[dst][i].size();j++) {
if(_notify_invalid_links && !is_in_vector(multipaths, _last_seen_routes_mp[dst][i][j]) && !_last_seen_routes_mp[dst][i][j].links.empty()) {
invalid_paths.push_back(_last_seen_routes_mp[dst][i][j]);
Timestamp now;
now.assign_now();
DEBUG_CHATTER("[RoutingPaths %s] Route %s has become invalid.",
now.unparse().c_str(), _last_seen_routes_mp[dst][i][j].unparse().c_str());
}
}
}
if (!invalid_paths.empty()) {
_routing_links->set_invalid_paths(invalid_paths);
_invalid_routes = invalid_paths;
}
_last_seen_routes_mp.set(dst, multipaths);
}
}
if(store_route)
_routes_to_print.set(dst, multipaths);
}
Vector<Route>
RoutingPaths::get_and_reset_invalid_routes() {
Vector<Route> invalid_paths = _invalid_routes;
_invalid_routes.clear();
return invalid_paths;
}
////////////////////// Handlers //////////////////////////////
static String
print_handler(Element *e, void *) {
RoutingPaths *rp = (RoutingPaths *)e;
return rp->print_routes();
}
int
RoutingPaths::get_route_handler(const String &s, Element *e, void *arg,
ErrorHandler *errh) {
RoutingPaths *rp = (RoutingPaths *)e;
Vector<String> arg_strings = parse_string(s,"/");
if (arg_strings.size() != 3)
return errh->error("Argument must be IP/N/n");
IPAddress ip = IPAddress(arg_strings[0]);
if (ip == IPAddress())
return errh->error("invalid IP address");
int N;
int n;
if(!cp_integer(arg_strings[1], &N))
return errh->error("Invalid N");
if(!cp_integer(arg_strings[2], &n))
return errh->error("Invalid n");
if(((intptr_t) arg) == 0)
rp->get_multipaths(ip, N, n, true, false, false, false);
else if(((intptr_t) arg) == 1)
rp->get_multipaths(ip, N, n, true, true, false, false);
else if(((intptr_t) arg) == 2)
rp->get_multipaths(ip, N, n, true, false, true, false);
return 0;
}
int
RoutingPaths::bool_handler(const String &s, Element *e, void *a,
ErrorHandler *errh) {
RoutingPaths *elmt = (RoutingPaths *)e;
int arg;
if(!cp_integer(s, &arg))
return errh->error("Debug must be 0 or 1");
if (!(arg == 0 || arg == 1))
return errh->error("Debug must be 0 or 1");
if(((intptr_t) a) == 0)
elmt->set_debug(arg==1);
if(((intptr_t) a) == 1)
elmt->set_verb_debug(arg==1);
if(((intptr_t) a) == 2)
elmt->reset();
if(((intptr_t) a) == 3)
elmt->set_keep_routes(arg==1);
return 0;
}
int
RoutingPaths::k_handler(const String &s, Element *e, void *arg,
ErrorHandler *errh) {
RoutingPaths *elmt = (RoutingPaths *)e;
int k;
if(!cp_integer(s, &k))
return errh->error("K must be an integer");
if(((intptr_t) arg) == 0)
elmt->set_k(k);
return 0;
}
int
RoutingPaths::multirouting_2best_paths_handler(const String &s, Element *e, void *,
ErrorHandler *errh) {
RoutingPaths *elmt = (RoutingPaths *)e;
int arg;
if(!cp_integer(s, &arg))
return errh->error("Arg must be 0 or 1");
if (!(arg == 0 || arg == 1))
return errh->error("Arg must be 0 or 1");
elmt->set_2bp(arg==1);
return 0;
}
int
RoutingPaths::forbidden_multipath_handler(const String &s, Element *e, void *arg,
ErrorHandler *errh) {
// format is addr1>addr2,addr2>addr3;addr4>addr5,addr6>addr7
RoutingPaths *elmt = (RoutingPaths *)e;
if(((intptr_t) arg) == 1 && s.equals("*"))
elmt->clear_forbidden_multipaths();
else {
Vector<String> arg_strings_mp = parse_string(s,";");
Multipath mp;
for(int i=0;i<arg_strings_mp.size();i++) {
Vector<String> arg_strings_route = parse_string(arg_strings_mp[i],",");
Route route;
for(int j=0;j<arg_strings_route.size();j++) {
Vector<String> arg_strings_link = parse_string(arg_strings_route[j],">");
if(arg_strings_link.size()!=2) {
click_chatter("Must have two addresses for a link");
return errh->error("Error in format");
}
EtherAddress eth1;
EtherAddress eth2;
click_chatter("%s %s", arg_strings_link[0].c_str(), arg_strings_link[1].c_str());
if (!cp_ethernet_address(arg_strings_link[0], &eth1) || !cp_ethernet_address(arg_strings_link[1], &eth2)) {
click_chatter("Could not parse addresses %s %s", arg_strings_link[0].c_str(), arg_strings_link[1].c_str());
return errh->error("Error in format");
}
LinkRouting link = LinkRouting(eth1, eth2, 0);
route.links.push_back(link);
}
mp.add_route(route);
}
if(((intptr_t) arg) == 0)
elmt->add_forbidden_multipath(mp);
if(((intptr_t) arg) == 1)
elmt->rm_forbidden_multipath(mp);
}
return 0;
}
void RoutingPaths::add_handlers() {
add_read_handler("print_routes", print_handler,0);
add_write_handler("get_route", get_route_handler, 0);
add_write_handler("get_route_wifi", get_route_handler, 1);
add_write_handler("get_route_plc", get_route_handler, 2);
add_write_handler("debug", bool_handler, 0);
add_write_handler("verb_debug", bool_handler, 1);
add_write_handler("reset", bool_handler, 2);
add_write_handler("keep_routes", bool_handler, 3);
add_write_handler("k", k_handler, 0);
add_write_handler("2bp", multirouting_2best_paths_handler, 0);
add_write_handler("add_forbidden_path", forbidden_multipath_handler, 0);
add_write_handler("rm_forbidden_path", forbidden_multipath_handler, 1);
}
ELEMENT_REQUIRES(RoutingLinks)
EXPORT_ELEMENT(RoutingPaths)
CLICK_ENDDECLS

Event Timeline

c4science · Help