Page MenuHomec4science
Files F121205278

routinglinks.cc
No OneTemporary
Actions

File Metadata

Created
Wed, Jul 9, 07:42

routinglinks.cc
View Options

#include <click/config.h>
#include "routinglinks.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
RoutingLinks::RoutingLinks() : timer(this)
{
}
RoutingLinks::~RoutingLinks()
{
}
int
RoutingLinks::configure(Vector<String> &conf, ErrorHandler *errh)
{
_has_changed = true;
_static = false;
_debug = false;
_verb_debug = false;
_has_order = true;
_neighbor_links = Links();
#ifdef CLICK_USERLEVEL
if(_static)
_ff = FromFile();
#endif
_interface_out = HashTable<EtherAddress, int>();
_neighbors = HashTable<int, Vector<RealNeighbor> >();
_seq_number_ls = Vector<uint8_t>();
_empty_eth = EtherAddress();
_print_network_freq = 0;
_print_network = false;
_print_parsable_network = false;
_use_MPR = false;
_trigger_ls_packets = false;
_stop_processing = false;
_MPRs = Vector<EtherAddress>();
_nodes_in_network = Vector<NodeRouting>();
_order_elmt = 0;
_delete_ls_packet = false;
_active = true;
_now.assign_now();
_last_print_network = _now;
_begin = _now;
String neighbors_name;
String order_name;
String compound_name;
int node_index = -1;
if(Args(this, errh).bind(conf)
.read("STATIC", _static)
#ifdef CLICK_USERLEVEL
.read("FILENAME", FilenameArg(), _ff.filename())
#endif
//.read("NEIGHBORS_ELMT", reinterpret_cast<Element *&>(_neighbors_elmt))
.read("NEIGHBORS_ELMT", neighbors_name)
.read("ORDER_ELMT", order_name)
.read("DEBUG", _debug)
.read("VERB_DEBUG", _verb_debug)
.read("PRINT_NETWORK", _print_network_freq)
.read("PRINT_PARSABLE_NETWORK", _print_parsable_network)
.read("MPR_SEL", _use_MPR)
.read("NODE_INDEX", node_index)
.read("ACTIVE", _active)
.complete() < 0)
return -1;
if (_verb_debug)
_debug = true;
DEBUG_CHATTER("[RoutingLinks] Configuring RoutingLinks...");
if(_print_network_freq > 0)
_print_network = true;
else if(_debug) {
_print_network = true;
_print_network_freq = DEFAULT_FREQ_PRINT;
}
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 + "/";
}
if (!_static) {
if (order_name.length() > 0)
_order_elmt = (Order*)router()->find(order_name, compound_name, errh);
if(_order_elmt == 0) {
click_chatter("Warning: no Order element %s%s.",
compound_name.c_str(), order_name.c_str());
_has_order = false;
}
else if(_order_elmt->cast("Order") == 0)
return errh->error("%s%s is not an Order.",
compound_name.c_str(), order_name.c_str());
if (_has_order)
_order_elmt->set_rtl(this);
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 + "/";
}
_neighbors_elmt = (Neighbors*)router()->find(neighbors_name, compound_name, errh);
if(_neighbors_elmt == 0) {
return errh->error("No Neighbors element %s%s.",
compound_name.c_str(), neighbors_name.c_str());
}
if(_neighbors_elmt->cast("Neighbors") == 0)
return errh->error("%s%s is not a Neighbors.",
compound_name.c_str(), neighbors_name.c_str());
_neighbors_elmt->set_rl_elmt(this);
timer.initialize(this);
timer.schedule_after_msec((uint32_t)1000 * MAX_FREQ_LS_PACKET_SEC);
mask_bcast = IPAddress("255.255.255.0").in_addr();
_last_seq_numbers_ls_neighbors = HashTable<EtherAddress, uint8_t>();
_neighbors_changed = false;
}
else {
if(_print_network) {
timer.initialize(this);
timer.schedule_after_msec((uint32_t)1000 * _print_network_freq);
}
// read text file
#ifdef CLICK_USERLEVEL
VERB_DEBUG_CHATTER("[RoutingLinks] Reading text file...");
if (_ff.initialize(errh) < 0)
return errh->error("Could not open file");
String line;
int nb_line=0;
while (1) {
nb_line++;
if (_ff.read_line(line, errh, true) <= 0) {
break;
}
if (line.starts_with("NODE")) {
VERB_DEBUG_CHATTER("[RoutingLinks] Adding node...");
Vector<EtherAddress> interfaces;
Vector<String> addresses = parse_string(line.substring(4), " ");
IPAddress ip;
if (!cp_ip_address(addresses[0], &ip))
return errh->error("Error in file at line %d: invalid IP address %s", nb_line, addresses[0].c_str());
for (int i=1;i<addresses.size();i++) {
EtherAddress eth;
if (!cp_ethernet_address(addresses[i], &eth))
return errh->error("Error in file at line %d: invalid Ethernet address %s length %d %s", nb_line,
addresses[i].c_str());
if(!is_in_vector(interfaces, eth)) {
interfaces.push_back(eth);
}
else {
click_chatter("[RoutingLinks] Warning: an address appears twice at line %d.", nb_line);
}
}
if(interfaces.empty())
click_chatter("[RoutingLinks] Warning: node at line %d has no interface: node not added.", nb_line);
else {
NodeRouting node = NodeRouting(ip, interfaces);
if(!is_in_vector(_nodes_in_network, node)) {
_nodes_in_network.push_back(node);
}
else {
click_chatter("[RoutingLinks] Warning: an address appears twice: node at line %d not added.", nb_line);
}
VERB_DEBUG_CHATTER("[RoutingLinks] Node added!");
}
}
else if (line.starts_with("LINK")) {
VERB_DEBUG_CHATTER("[RoutingLinks] Adding link...");
Vector<String> link_elements = parse_string(line.substring(4), " ");
if(link_elements.size() != 3) {
return errh->error("Error in file at line %d: invalid link", nb_line);
}
EtherAddress interfaces[2];
for(int i=0;i<=1;i++) {
if (!cp_ethernet_address(link_elements[i], &interfaces[i]))
return errh->error("Error in file at line %d: invalid interface address %s", nb_line, link_elements[i].c_str());
}
VERB_DEBUG_CHATTER("[RoutingLinks] Interfaces parsed!");
double weight;
if (!cp_double(link_elements[2], &weight)) {
return errh->error("Error in file at line %d: invalid weight", nb_line);
}
VERB_DEBUG_CHATTER("[RoutingLinks] Weight parsed! Weight is %d", weight);
for(int i=0;i<=1;i++) {
int i0=i;
int i1=(i+1)%2;
RealNeighbor neighbor = RealNeighbor(interfaces[i1], (uint32_t) weight);
if(is_in_hash_table(_neighbor_links, interfaces[i0])) {
int ind = find_in_vector(_neighbor_links[interfaces[i0]], neighbor);
if(ind == -1)
_neighbor_links[interfaces[i0]].push_back(neighbor);
else {
if(neighbor.weight < _neighbor_links[interfaces[i0]][ind].weight)
_neighbor_links[interfaces[i0]][ind].weight = neighbor.weight;
}
}
else
_neighbor_links.set(interfaces[i0], Vector<RealNeighbor>(1,neighbor));
}
VERB_DEBUG_CHATTER("[RoutingLinks] Link added!");
}
}
#endif
DEBUG_CHATTER("[RoutingLinks] RoutingLinks configured, with %d nodes.", _nodes_in_network.size());
if(_verb_debug) {
int count=0;
for (Vector<NodeRouting>::const_iterator it_node=_nodes_in_network.begin();
it_node!=_nodes_in_network.end();it_node++) {
count++;
VERB_DEBUG_CHATTER("[RoutingLinks] Node %d has %d interfaces", count, it_node->interfaces.size());
}
}
}
DEBUG_CHATTER("[RoutingLinks] RoutingLinks configured");
return 0;
}
int
RoutingLinks::initialize(ErrorHandler *errh) {
DEBUG_CHATTER("[RoutingLinks] Initializing...");
Element::initialize(errh);
if(!_static) {
_neighbors_elmt->registerListener(this);
}
DEBUG_CHATTER("[RoutingLinks] Done!");
return 0;
}
void
RoutingLinks::push(int port, Packet *p_in) {
if(!_static) {
empower_header *empower_hdr = (empower_header *)(p_in->data());
linkstate_header *ls_hdr = (linkstate_header *)(p_in->data() + sizeof(empower_header));
if(ls_hdr->_type == LS_PACKET) {
if(!_active) {
p_in->kill();
return;
}
linkstate_packet *ls_pkt = (linkstate_packet *)(p_in->data() + sizeof(empower_header) + sizeof(linkstate_header) + ls_hdr->_nb_retr*sizeof(MPR));
EtherAddress src_eth(ls_pkt->_src_eth_int);
// if broadcast, retransmit it if it has not been seen yet
if(!is_in_vector(me.interfaces, src_eth)) {
if(is_valid_seq_number_ls(src_eth, ls_pkt->_seq)) {
StringAccum s;
if(_debug) {
_now.assign_now();
s << "[RoutingLinks " << _now.unparse() << "] Got a LinkState packet from ";
s << src_eth.unparse();
s << ", seq number ";
s << String((int)ls_pkt->_seq);
s << ", last seen ";
s << String((int)_last_seq_numbers_ls_neighbors[src_eth]);
s << ".";
}
bool retransmit = false;
StringAccum s2;
if(ls_hdr->_MPR_retr_bool) {
s2 << "MPRs are ";
for(int i=0;i<ls_hdr->_nb_retr;i++) {
EtherAddress mpr = EtherAddress(ls_hdr->_retr[i].eth);
s2 << mpr.unparse();
if(i<(ls_hdr->_nb_retr-1))
s2 << " ";
if(!retransmit && is_in_vector(me.interfaces, mpr)) {
retransmit = true;
if(!_verb_debug)
break;
}
}
s2 << ".";
}
else
retransmit = true;
if(retransmit && _debug)
s << " (Must be retransmitted.)";
DEBUG_CHATTER(s.c_str());
VERB_DEBUG_CHATTER(s2.c_str());
_last_seq_numbers_ls_neighbors.set(src_eth, ls_pkt->_seq);
p_in->pull(sizeof(empower_header));
p_in->pull(sizeof(linkstate_header) + ls_hdr->_nb_retr*sizeof(MPR));
process_in_ls_packet(p_in);
if(retransmit && me.interfaces.size() > 0) {
WritablePacket *p = Packet::make(100, 0, p_in->length(), 10);
if (!p) {
click_chatter("[RoutingLinks] couldn't create packet\n");
p_in->kill();
return;
}
memcpy(p->data(), p_in->data(), p_in->length());
p_in->kill();
for(int i=0;i<me.interfaces.size();i++) {
Packet *p_out;
if(i==me.interfaces.size()-1)
p_out = add_headers(p, EtherAddress::make_broadcast(), i, ROUTING_CTRL, LS_PACKET);
else
p_out = add_headers(p->clone()->uniqueify(), EtherAddress::make_broadcast(), i, ROUTING_CTRL, LS_PACKET);
if(p_out) {
DEBUG_CHATTER("[RoutingLinks] Packets sent on interface %s", interface(i).c_str());
output(i).push(p_out);
}
else
click_chatter("[RoutingLinks] Error when adding headers, cannot send.");
}
}
else {
p_in->kill();
}
return;
}
else {
_now.assign_now();
VERB_DEBUG_CHATTER("[RoutingLinks %s] Got an invalid LinkState packet from %s, transmitted by %s seq number %d (have seen %d)", _now.unparse().c_str(),
src_eth.unparse().c_str(), EtherAddress(empower_hdr->_route._src).unparse().c_str(), ls_pkt->_seq, _last_seq_numbers_ls_neighbors[src_eth]);
if(!(ls_pkt->_seq == _last_seq_numbers_ls_neighbors[src_eth] || is_valid_seq_number_ls(src_eth, ls_pkt->_seq)))
_last_seq_numbers_ls_neighbors.set(src_eth, ls_pkt->_seq);
p_in->kill();
return;
}
}
else {
VERB_DEBUG_CHATTER("[RoutingLinks] Useless packet. is from me:%d", is_in_vector(me.interfaces, src_eth));
p_in->kill();
return;
}
}
else {
VERB_DEBUG_CHATTER("[RoutingLinks] Useless packet, is not LinkState packet");
p_in->kill();
return;
}
}
else { // should not happen
p_in->kill();
return;
}
}
void
RoutingLinks::neighborsChanged() {
_now.assign_now();
DEBUG_CHATTER("[RoutingLinks] Notified by Neighbors element.");
_neighbors_changed = true;
_last_discovered_neighbor = _now;
_must_warn_new_neighbors = true;
_has_different_network = true;
timer.schedule_now();
}
void
RoutingLinks::set_invalid_paths(Vector<Route> paths) {
if (_invalid_paths.empty())
_invalid_paths = paths;
else
_invalid_paths = concat_vectors(_invalid_paths, paths);
_trigger_ls_packets = true;
timer.schedule_now();
}
void
RoutingLinks::run_timer(Timer *t) {
assert(t == &timer);
if(!_active) {
timer.schedule_after_sec(MAX_FREQ_LS_PACKET_SEC);
return;
}
if(!_static) {
_now.assign_now();
if((_now-_begin).sec() < 30) { // wait 30 seconds before doing anything
timer.schedule_after_sec((_now-_begin).sec());
return;
}
DEBUG_CHATTER("[RoutingLinks %s] Timer is scheduled...", _now.unparse().c_str());
bool update_weight = time_to_update_weight();
if(_neighbors_changed || update_weight || !_invalid_paths.empty()) {
if (!_invalid_paths.empty())
DEBUG_CHATTER("[RoutingLinks %s] Network has changed: invalid paths.", _now.unparse().c_str());
if (update_weight)
DEBUG_CHATTER("[RoutingLinks %s] Network has changed: weight must be updated.", _now.unparse().c_str());
if (_neighbors_changed)
DEBUG_CHATTER("[RoutingLinks %s] Network has changed: has been notified by Neighbors.", _now.unparse().c_str());
_neighbors_changed = false;
change_neighbors(update_weight);
_has_changed = true;
if(update_weight)
_last_weight_update = _now;
push_linkstate_packets(false);
compute_my_cont_links();
}
if(((_now - _last_time_sent_ls).sec() >= MIN_FREQ_LS_PACKET_SEC || _trigger_ls_packets) && (_now - _last_time_sent_ls).sec() >= MAX_FREQ_LS_PACKET_SEC) {
DEBUG_CHATTER("[RoutingLinks %s] Push LinkState packets (triggered %s)", _now.unparse().c_str(), String(_trigger_ls_packets).c_str());
_trigger_ls_packets = false;
push_linkstate_packets(false);
}
if((_now - _last_time_neighbors_checked).sec() >= MIN_FREQ_LS_PACKET_SEC || _delete_ls_packet) {
DEBUG_CHATTER("[RoutingLinks %s] Checking neighbors...", _now.unparse().c_str());
_last_time_neighbors_checked = _now;
bool has_changed = false;
_delete_ls_packet = false;
uint32_t timeout = MAX_LOST_LS_PACKET*MIN_FREQ_LS_PACKET_SEC;
Vector<NodeRouting> new_nodes_in_network = Vector<NodeRouting>(1,_nodes_in_network[0]);
for(int i=1;i<_nodes_in_network.size();i++) {
// check for nodes/interfaces timeouts and delete if some
Vector<EtherAddress> new_interfaces;
Vector<Timestamp> new_last_time_seen;
for(int j=0;j<_nodes_in_network[i].interfaces.size();j++) {
if((_now - _nodes_in_network[i].last_time_seen_interfaces[j]).sec() >= timeout || !is_in_hash_table(_neighbor_links, _nodes_in_network[i].interfaces[j])) {
DEBUG_CHATTER("[RoutingLinks] Timeout: deleting interface %s from network", _nodes_in_network[i].interfaces[j].unparse().c_str());
_last_seq_numbers_ls_neighbors.erase(_nodes_in_network[i].interfaces[j]);
delete_one_hop_neighbor(_nodes_in_network[i].interfaces[j]);
_two_hop_neighbors.erase(_nodes_in_network[i].interfaces[j]);
_removed_neighbors.push_back(_nodes_in_network[i].interfaces[j]);
has_changed = true;
}
else {
new_interfaces.push_back(_nodes_in_network[i].interfaces[j]);
new_last_time_seen.push_back(_nodes_in_network[i].last_time_seen_interfaces[j]);
}
}
_nodes_in_network[i].interfaces = new_interfaces;
_nodes_in_network[i].last_time_seen_interfaces = new_last_time_seen;
if((_now - _nodes_in_network[i].last_time_seen_node).sec() >= timeout || _nodes_in_network[i].interfaces.empty()) {
DEBUG_CHATTER("[RoutingLinks] Timeout: deleting node %s from network", _nodes_in_network[i].ip.unparse().c_str());
has_changed = true;
}
else
new_nodes_in_network.push_back(_nodes_in_network[i]);
}
_nodes_in_network = new_nodes_in_network;
if(has_changed) {
change_neighbors(false);
DEBUG_CHATTER("[RoutingLinks %s] Network has changed: interfaces removed.", _now.unparse().c_str());
_has_changed = true;
_has_different_network = true;
}
}
if(_print_network) {
if((_now - _last_print_network).sec() >= _print_network_freq) {
_nodes_in_network[0].last_time_seen_node = _now;
_nodes_in_network[0].last_time_seen_interfaces = Vector<Timestamp>(me.interfaces.size(), _now);
_nodes_in_network[0].last_time_cont_links = Vector<Timestamp>(me.interfaces.size(), Timestamp());
if (_print_parsable_network)
print_network_parsable();
else
click_chatter(print_network().c_str());
print_statistics();
_last_print_network = _now;
}
}
timer.schedule_after_sec(MAX_FREQ_LS_PACKET_SEC);
}
else { // only print network
if (_print_parsable_network)
print_network_parsable();
else if(_print_network)
print_network();
timer.schedule_after_sec(_print_network_freq);
}
}
bool
RoutingLinks::set_routing_links(NodeRouting _me) {
me = _me;
if(!_static) {
_nodes_in_network.push_back(me);
for(int i=0;i<me.interfaces.size();i++) {
LastAddrBytes bytes = LastAddrBytes(me.interfaces[i]);
_lastbytes2eth[bytes] = me.interfaces[i];
if(_debug) {
_now.assign_now();
click_chatter("[RoutingLinks %s] Setting eth %s for bytes %s",
_now.unparse().c_str(), me.interfaces[i].unparse().c_str(), bytes.unparse().c_str());
}
_neighbors.set(i, Vector<RealNeighbor>());
//_seq_number_ls.push_back((uint8_t) rand() % MAX_SEQ_NB);
_seq_number_ls.push_back((uint8_t) click_random(0, MAX_SEQ_NB-1));
}
}
DEBUG_CHATTER("[RoutingLinks] RoutingLinks set by RoutingPaths, with %d interfaces!", me.interfaces.size());
return true;
}
int
RoutingLinks::get_interface(EtherAddress eth) {
if(!is_in_hash_table(_interface_out, eth)) {
for(int i=0;i<me.interfaces.size();i++) {
if(is_in_vector(_neighbor_links[me.interfaces[i] ], RealNeighbor(eth))) {
VERB_DEBUG_CHATTER("[RoutingLinks] Getting out interface for %s: it's %d", eth.unparse().c_str(), i);
_interface_out.set(eth, i);
return i;
}
}
}
else
return _interface_out[eth];
return -1;
}
EtherAddress
RoutingLinks::get_ether_address(unsigned char *data) const {
for(int i=0;i<me.interfaces.size();i++) {
for (int i_int=0;i_int < _neighbors[i].size();i_int ++) {
const unsigned char *data_this_addr = _neighbors[i][i_int].neighbor.data();
bool is_same = true;
for(int b=0; b<NB_BYTES_HOP;b++) {
if (data[b] != data_this_addr[6-NB_BYTES_HOP+b]) {
is_same = false;
break;
}
}
if (is_same)
return _neighbors[i][i_int].neighbor;
}
}
return _empty_eth;
}
EtherAddress
RoutingLinks::get_ether_address(LastAddrBytes data) const {
if(!is_in_hash_table(_lastbytes2eth, data))
return _empty_eth;
return _lastbytes2eth[data];
}
Packet *
RoutingLinks::add_headers(Packet *p_in, EtherAddress next_hop, int interface_out, uint8_t type) {
if(type == ROUTING_CTRL)
click_chatter("[RoutingLinks] WARNING! For ROUTING_CTRL messages, must precise routing type (LS_PACKET or CL_PACKET). Sending as a LS_PACKET");
return add_headers(p_in, next_hop, interface_out, type, LS_PACKET);
}
String
RoutingLinks::interface(uint8_t inter) {
if(me.interfaces.size() > 1) {
if(inter == INTERFACE2)
return "PLC/WIFI2";
else if(inter == INTERFACE1)
return "WIFI";
else return "";
}
else {
if(me.unique_interface == INTERFACE2)
return "PLC/WIFI2";
else if(me.unique_interface == INTERFACE1)
return "WIFI";
else return "";
}
}
NodeRouting
RoutingLinks::get_node_from_eth(EtherAddress eth) {
for(int i=0;i<_nodes_in_network.size();i++) {
if (is_in_vector(_nodes_in_network[i].interfaces, eth))
return _nodes_in_network[i];
}
return NodeRouting();
}
String
RoutingLinks::print_network() const {
int undefined_links=0;
int links = 0;
int good_links = 0;
StringAccum s;
Timestamp now;
now.assign_now();
Vector<NodeRouting> nodes_in_network_copy = insertion_sort(_nodes_in_network);
for(int i=0;i<nodes_in_network_copy.size();i++) {
if(nodes_in_network_copy[i].ip == me.ip)
s << "Node " << nodes_in_network_copy[i].ip.unparse() << "\n";
else if(!_static)
s << "Node " << nodes_in_network_copy[i].ip.unparse() << " (time " << (now - nodes_in_network_copy[i].last_time_seen_node).sec() << ")" << "\n";
else
s << "Node " << nodes_in_network_copy[i].ip.unparse() << "\n";
for(int j=0;j<nodes_in_network_copy[i].interfaces.size();j++) {
EtherAddress eth = nodes_in_network_copy[i].interfaces[j];
if(i==0) {
s << " Interface " << eth.unparse() << "\n";
}
else if(!_static)
s << " Interface " << eth.unparse() << " (time " << (now - nodes_in_network_copy[i].last_time_seen_interfaces[j]).sec() << ")" << "\n";
else
s << " Interface " << eth.unparse() << "\n";
if(is_in_hash_table(_neighbor_links, eth)) {
for(int k=0;k<_neighbor_links[eth].size();k++) {
links++;
if(_neighbor_links[eth][k].weight == DEFAULT_WEIGHT)
undefined_links++;
else if(_neighbor_links[eth][k].weight < THRES_WEIGHT_GOOD_NEI)
good_links++;
s << " -> " << _neighbor_links[eth][k].unparse() << "\n";
}
}
}
s <<"\n";
}
s << "At " << now.unparse() << ", " << nodes_in_network_copy.size() << " nodes, " << links << " links (unidirectional), "
<< undefined_links << " links with capacity 0, " << good_links << " are good links.\n";
return s.take_string();
}
void RoutingLinks::add_forbidden_link(EtherAddress eth) {
_forbidden_link.set(eth,1);
change_neighbors(false);
}
void RoutingLinks::add_forbidden_link(IPAddress ip) {
Vector<EtherAddress> interfaces = _ip_to_eth_interfaces[ip];
for(int i=0;i<interfaces.size();i++) {
if(interfaces[i]!=EtherAddress())
_forbidden_link.set(interfaces[i],1);
}
change_neighbors(false);
}
void RoutingLinks::rm_forbidden_link(EtherAddress eth) {
_forbidden_link.erase(eth);
change_neighbors(false);
}
void RoutingLinks::rm_forbidden_link(IPAddress ip) {
Vector<EtherAddress> interfaces = _ip_to_eth_interfaces[ip];
for(int i=0;i<interfaces.size();i++) {
if(interfaces[i]!=EtherAddress())
_forbidden_link.erase(interfaces[i]);
}
change_neighbors(false);
}
void RoutingLinks::add_contending_links(UndirectedLinkRouting link1, UndirectedLinkRouting link2) {
_contending_links_matrix[link1].set(link2,true);
_contending_links_matrix[link2].set(link1,true);
}
static String
print_handler(Element *e, void *param) {
RoutingLinks *rl = (RoutingLinks *)e;
return rl->print_network();
}
static String
print_contending_links_handler(Element *e, void *param) {
RoutingLinks *rl = (RoutingLinks *)e;
return print_vector(rl->get_current_contending_links());
}
int
RoutingLinks::stop_node_handler(const String &, Element *e, void *,
ErrorHandler *) {
RoutingLinks *rl = (RoutingLinks *)e;
rl->notify_end();
return 0;
}
int
RoutingLinks::contending_links_handler(const String &s, Element *e, void *arg,
ErrorHandler *errh) {
RoutingLinks *elmt = (RoutingLinks *)e;
if(((intptr_t) arg) == 0) {
Vector<String> arg_strings = parse_string(s,">");
if (arg_strings.size() != 2) {
click_chatter("Argument must be eth1>eth2");
return errh->error("Argument must be eth1>eth2");
}
EtherAddress eth1, eth2;
if(!cp_ethernet_address(arg_strings[0], &eth1) || !cp_ethernet_address(arg_strings[1].substring(1), &eth2)) {
click_chatter("Error while parsing addresses %s (%s) or %s (%s)", arg_strings[0].c_str(), eth1.unparse().c_str(),
arg_strings[1].c_str(), eth2.unparse().c_str());
return errh->error("Error while parsing addresses");
}
elmt->get_contending_links(LinkRouting(eth1,eth2,0));
}
else if (((intptr_t) arg) == 1) {
Vector<String> str_links = parse_string(s,",");
if(str_links.size()!=2) {
click_chatter("Argument must be eth1>eth2,eth3>eth4");
return errh->error("Argument must be eth1>eth2,eth3>eth4");
}
EtherAddress eth1, eth2, eth3, eth4;
Vector<String> arg_strings1 = parse_string(str_links[0],">");
Vector<String> arg_strings2 = parse_string(str_links[1],">");
if (arg_strings1.size() != 2 || arg_strings1.size() != 2) {
click_chatter("Links must be eth1>eth2");
return errh->error("Links must be eth1>eth2");
}
if(!cp_ethernet_address(arg_strings1[0], &eth1) || !cp_ethernet_address(arg_strings1[1], &eth2) ||
!cp_ethernet_address(arg_strings2[0], &eth3) || !cp_ethernet_address(arg_strings2[1], &eth4)) {
click_chatter("Error while parsing addresses");
return errh->error("Error while parsing addresses");
}
elmt->add_contending_links(UndirectedLinkRouting(eth1,eth2), UndirectedLinkRouting(eth3,eth4));
}
return 0;
}
int
RoutingLinks::debug_handler(const String &s, Element *e, void *,
ErrorHandler *errh) {
RoutingLinks *elmt = (RoutingLinks *)e;
int debug;
if(!cp_integer(s, &debug))
return errh->error("Debug must be 0 or 1");
if (!(debug == 0 || debug == 1))
return errh->error("Debug must be 0 or 1");
elmt->set_debug(debug==1);
return 0;
}
int
RoutingLinks::active_handler(const String &s, Element *e, void *,
ErrorHandler *errh) {
RoutingLinks *elmt = (RoutingLinks *)e;
int active;
if(!cp_integer(s, &active))
return errh->error("Active must be 0 or 1");
if (!(active == 0 || active == 1))
return errh->error("Active must be 0 or 1");
elmt->set_active(active==1);
return 0;
}
int
RoutingLinks::forbidden_link_handler(const String &s, Element *e, void *arg,
ErrorHandler *errh) {
RoutingLinks *rp = (RoutingLinks *)e;
EtherAddress eth;
IPAddress ip;
if (cp_ethernet_address(s, &eth)) {
if(((intptr_t) arg) == 0)
rp->add_forbidden_link(eth);
if(((intptr_t) arg) == 1)
rp->rm_forbidden_link(eth);
}
else if(cp_ip_address(s, &ip)) {
if(((intptr_t) arg) == 0)
rp->add_forbidden_link(ip);
if(((intptr_t) arg) == 1)
rp->rm_forbidden_link(ip);
}
else if(((intptr_t) arg) == 1 && s.equals("*")) {
rp->clear_forbidden_links();
}
else
return errh->error("Must be an IP or an Ethernet address, or * for rm");
return 0;
}
void RoutingLinks::add_handlers() {
add_read_handler("print_network", print_handler,0);
add_read_handler("print_contending_links", print_contending_links_handler,0);
add_write_handler("stop_node", stop_node_handler, 0);
add_write_handler("debug", debug_handler, 0);
add_write_handler("active", active_handler, 0);
add_write_handler("get_contending_links", contending_links_handler, 0);
add_write_handler("add_contending_links", contending_links_handler, 1);
add_write_handler("add_forbidden_link", forbidden_link_handler, 0);
add_write_handler("rm_forbidden_link", forbidden_link_handler, 1);
}
IPAddress
RoutingLinks::get_ip(unsigned char *data) {
String str_data = String(data, NB_BYTES_HOP);
if (is_in_hash_table(_str_to_ip, str_data))
return _str_to_ip[str_data];
NodeRouting node_eth;
for(int i=0;i<_nodes_in_network.size();i++) {
for(int j=0; j<_nodes_in_network[i].interfaces.size(); j++){
if(are_last_bytes_in_addr(data, _nodes_in_network[i].interfaces[j])){
node_eth = _nodes_in_network[i];
break;
}
}
}
_str_to_ip.set(str_data, node_eth.ip);
return node_eth.ip;
}
IPAddress
RoutingLinks::get_ip(EtherAddress eth) {
if (is_in_hash_table(_eth_to_ip, eth))
return _eth_to_ip[eth];
NodeRouting node_eth;
for(int i=0;i<_nodes_in_network.size();i++) {
if(is_in_vector(_nodes_in_network[i].interfaces, eth)) {
node_eth = _nodes_in_network[i];
break;
}
}
if(node_eth.ip != IPAddress())
_eth_to_ip.set(eth, node_eth.ip);
return node_eth.ip;
}
bool
RoutingLinks::are_contending(UndirectedLinkRouting a, UndirectedLinkRouting b) {
return (a==b || is_in_hash_table(_contending_links_matrix[a], b) || is_in_hash_table(_contending_links_matrix[b], a));
}
Vector<UndirectedLinkRouting>
RoutingLinks::get_contending_links(LinkRouting link) {
Vector<UndirectedLinkRouting> links;
UndirectedLinkRouting ulink = UndirectedLinkRouting(link.src, link.dst);
if(is_in_hash_table(_contending_links_matrix, ulink)) {
for(HashTable<UndirectedLinkRouting,bool>::iterator it = _contending_links_matrix[ulink].begin();
it!=_contending_links_matrix[ulink].end(); ++it) {
links.push_back(it.key());
}
}
_current_link = link;
_current_cont_links = links;
return links;
}
////////////////////////// PRIVATE FUNCTIONS ////////////////////////////////////
void
RoutingLinks::change_neighbors(bool update_weight) {
// responsible for getting neighbors from Neighbors element
_now.assign_now();
if (!_stop_processing) {
if(_debug) {
StringAccum s;
s << "Checking neighbors";
if (update_weight)
s << " (time to update weights)";
s << "...";
DEBUG_CHATTER(s.c_str());
}
LinksTable links_table = _neighbors_elmt->get_outgoing_links();
for(LinksTable::iterator it = links_table.begin(); it!=links_table.end(); ++it) {
NeighborLink link = it.value();
uint32_t weight;
if(link.capa > 0)
weight = mymin(int_divide(SCALE_WEIGHTS,link.capa), DEFAULT_WEIGHT); // weight=SCALE_WEIGHTS/capacity in kb/s
// weight=1->10000 for capa ~0.05->~500Mb/s
else
weight = DEFAULT_WEIGHT;
int index_interface;
if(me.interfaces.size() == 1) {
if(link.interface == me.unique_interface)
index_interface = 0;
else {
index_interface = -1;
DEBUG_CHATTER("[RoutingLinks] Got message from wrong interface.");
}
}
else {
index_interface = link.interface;
}
if(index_interface != -1) {
RealNeighbor neighbor = RealNeighbor(link.eth_addr,weight);
int ind = find_in_vector(_neighbors[index_interface], neighbor);
if(ind == -1) {
_neighbors[index_interface].push_back(neighbor);
DEBUG_CHATTER("[RoutingLinks] Got new neighbor: addr %s, interface %s, capacity %d ",
link.eth_addr.unparse().c_str(), interface(link.interface).c_str(), link.capa);
}
else {
if (update_weight) {
DEBUG_CHATTER("[RoutingLinks] Updating capacity for neighbor %s: new capacity %d",
link.eth_addr.unparse().c_str(), link.capa);
_neighbors[index_interface][ind].weight = weight;
}
}
}
}
for(int i=0;i<me.interfaces.size();i++) {
Vector<RealNeighbor> new_neighbors;
for(int j=0;j<_neighbors[i].size();j++) {
if(!is_in_hash_table(links_table, _neighbors[i][j].neighbor) || is_in_vector(_removed_neighbors, _neighbors[i][j].neighbor) ||
_forbidden_link[_neighbors[i][j].neighbor] > 0) {
// delete neighbor
DEBUG_CHATTER("[RoutingLinks] Delete neighbor (%d %d %d): addr %s, interface %s, weight %d ",is_in_hash_table(links_table, _neighbors[i][j].neighbor),
is_in_vector(_removed_neighbors, _neighbors[i][j].neighbor), _forbidden_link[_neighbors[i][j].neighbor],
_neighbors[i][j].neighbor.unparse().c_str(), interface(i).c_str(), _neighbors[i][j].weight);
delete_one_hop_neighbor(_neighbors[i][j].neighbor);
}
else
new_neighbors.push_back(_neighbors[i][j]);
}
_neighbors.set(i, new_neighbors);
}
for(int i=0;i<me.interfaces.size();i++) {
_neighbor_links.set(me.interfaces[i], _neighbors[i]);
}
DEBUG_CHATTER("[RoutingLinks] Neighbors checked!");
}
}
void
RoutingLinks::push_linkstate_packets(bool delete_interface) {
_now.assign_now();
if (!_stop_processing) {
_last_time_sent_ls = _now;
if(!_active)
return;
DEBUG_CHATTER("[RoutingLinks %s] Creating Linkstate packets.", _now.unparse().c_str());
if(_use_MPR) {
DEBUG_CHATTER("[RoutingLinks] Computing MPRs...");
bool infinite_loop;
_MPRs = select_MPRs(infinite_loop);
if(infinite_loop) {
bool verb_debug = _verb_debug;
_verb_debug = true;
select_MPRs();
_verb_debug = verb_debug;
}
}
for(int i=0;i<me.interfaces.size();i++) {
StringAccum s;
Vector<RealNeighbor> neighbors = _neighbors[i];
EtherAddress src_addr(me.interfaces[i]);
if(_debug) {
s << "For interface ";
s << interface(i);
s << " neighbors are ";
}
int payload = sizeof(linkstate_packet) + (neighbors.size())*sizeof(ShortNeighbor);
if (_invalid_paths.size() > 0)
payload += sizeof(invalid_routes_packet) + _invalid_paths.size()*sizeof(FormatedRoute);
WritablePacket *p = Packet::make(100, 0, payload, 10);
if (!p) {
click_chatter("[RoutingLinks] couldn't create packet\n");
continue;
}
memset(p->data(), 0, p->length());
linkstate_packet *ls_pkt = (linkstate_packet *) (p->data());
ls_pkt->_seq = _seq_number_ls[i];
ls_pkt->_src_ip_node = me.ip.in_addr();
ls_pkt->_src_eth_int = src_addr;
ls_pkt->_nb_neighbors = (uint8_t) neighbors.size();
ls_pkt->_has_invalid_routes = false;
ls_pkt->_delete_interface = delete_interface;
ls_pkt->_has_different_neighbors = _must_warn_new_neighbors;
ls_pkt->_is_reliable = _neighbors_elmt->get_is_reliable();
if(me.interfaces.size() > 1)
ls_pkt->_is_wifi = me.is_wifi[i];
else
ls_pkt->_is_wifi = me.unique_interface_wifi;
_seq_number_ls[i]= ((_seq_number_ls[i] + 1) % MAX_SEQ_NB);
_must_warn_new_neighbors = false;
for(int n=0;n<neighbors.size();n++) {
ls_pkt->_neighbors[n].eth = neighbors[n].neighbor;
ls_pkt->_neighbors[n].weight = neighbors[n].weight;
s << neighbors[n].unparse();
}
if (_invalid_paths.size() > 0) {
ls_pkt->_has_invalid_routes = true;
invalid_routes_packet *inv_rt_pkt = (invalid_routes_packet *) (p->data() + sizeof(linkstate_packet) + (neighbors.size())*sizeof(ShortNeighbor));
inv_rt_pkt->_nb_invalid_routes = (uint8_t) _invalid_paths.size();
for(int n=0;n<_invalid_paths.size();n++) {
inv_rt_pkt->_invalid_routes[n] = FormatedRoute(_invalid_paths[n]);
}
_invalid_paths.clear();
}
s << ".";
if(_debug) {
_now.assign_now();
click_chatter("[RoutingLinks %s] %s", _now.unparse().c_str(), s.c_str());
}
if(_debug) {
click_chatter("Sending LinkState packet (seq %d) from me with %d neighbors. They are: ", ls_pkt->_seq,ls_pkt->_nb_neighbors);
for(int i=0; i<ls_pkt->_nb_neighbors;i++)
click_chatter("%s", RealNeighbor(ls_pkt->_neighbors[i].eth, ls_pkt->_neighbors[i].weight).unparse().c_str());
}
for(int j=0;j<me.interfaces.size();j++) {
Packet *p_out;
if(j==me.interfaces.size()-1)
p_out = add_headers(p, EtherAddress::make_broadcast(), j, ROUTING_CTRL, LS_PACKET);
else
p_out = add_headers(p->clone()->uniqueify(), EtherAddress::make_broadcast(), j, ROUTING_CTRL, LS_PACKET);
if(p_out) {
DEBUG_CHATTER("[RoutingLinks] Packets sent on interface %s", interface(j).c_str());
output(j).push(p_out);
}
else
click_chatter("[RoutingLinks] Error when adding headers, cannot send.");
}
if(me.interfaces.size() == 0) //should not happen
p->kill();
}
}
}
void
RoutingLinks::process_in_ls_packet(const Packet *p) {
_now.assign_now();
linkstate_packet *ls_pkt = (linkstate_packet *)(p->data());
NodeRouting src_node(IPAddress(ls_pkt->_src_ip_node));
EtherAddress src_interface(ls_pkt->_src_eth_int);
LastAddrBytes lastbytes = LastAddrBytes(src_interface);
if(!is_in_hash_table(_lastbytes2eth, lastbytes)) {
DEBUG_CHATTER("[RoutingLinks %s] Setting eth %s for bytes %s",
_now.unparse().c_str(), src_interface.unparse().c_str(), lastbytes.unparse().c_str());
_lastbytes2eth[lastbytes] = src_interface;
}
add_in_vector_unique(_ip_to_eth_interfaces[src_node.ip], src_interface);
int ind = find_in_vector(_removed_neighbors, src_interface);
if(ind >= 0)
_removed_neighbors.erase(&_removed_neighbors[ind]);
if(ls_pkt->_has_different_neighbors) {
_last_discovered_neighbor = _now;
_has_different_network = true;
}
String interface_str;
if(ls_pkt->_is_wifi) {
interface_str = String("WIFI");
set_wifi_addr(src_interface);
}
else {
interface_str = String("PLC");
set_plc_addr(src_interface);
}
DEBUG_CHATTER("[RoutingLinks %s] LinkState packet from node %s, interface %s (%s), with %d neighbors.", _now.unparse().c_str(),
src_node.ip.unparse().c_str(), src_interface.unparse().c_str(), interface_str.c_str(),
(int) ls_pkt->_nb_neighbors);
StringAccum s;
if(_debug)
s << "Neighbors are ";
if (ls_pkt->_delete_interface) {
_delete_ls_packet = true;
ind = find_in_vector(_nodes_in_network, src_node);
if (ind != -1) {
int ind_int = find_in_vector(_nodes_in_network[ind].interfaces, src_interface);
if (ind_int != -1) {
_neighbor_links.erase(_nodes_in_network[ind].interfaces[ind_int]);
}
}
}
else {
if(!_active)
return;
ind = find_in_vector(_nodes_in_network, src_node);
int ind_int = 0;
if(ind == -1) {
ind = _nodes_in_network.size();
_nodes_in_network.push_back(src_node);
_nodes_in_network[ind].interfaces.push_back(src_interface);
_nodes_in_network[ind].last_time_seen_interfaces.push_back(_now);
_nodes_in_network[ind].last_time_cont_links.push_back(Timestamp());
_nodes_in_network[ind].last_time_seen_node = _now;
_last_discovered_neighbor = _now;
DEBUG_CHATTER("[RoutingLinks %s] Network has changed: LS packet from new node.", _now.unparse().c_str());
_has_changed = true;
_has_different_network = true;
}
else {
_nodes_in_network[ind].last_time_seen_node = _now;
ind_int = find_in_vector(_nodes_in_network[ind].interfaces, src_interface);
if(ind_int == -1) {
ind_int = _nodes_in_network[ind].interfaces.size();
_nodes_in_network[ind].interfaces.push_back(src_interface);
_nodes_in_network[ind].last_time_seen_interfaces.push_back(_now);
_nodes_in_network[ind].last_time_cont_links.push_back(Timestamp());
_last_discovered_neighbor = _now;
DEBUG_CHATTER("[RoutingLinks %s] Network has changed: LS packet from new interface.", _now.unparse().c_str());
_has_changed = true;
_has_different_network = true;
}
else {
_nodes_in_network[ind].last_time_seen_interfaces[ind_int] = _now;
}
}
Vector<RealNeighbor> neighbors = Vector<RealNeighbor>();
LinksTable links = _neighbors_elmt->get_outgoing_links();
bool is_one_hop = is_in_hash_table(links, src_interface) & _use_MPR;
EtherAddress node_address_one_hop = _empty_eth;
if(is_one_hop) {
node_address_one_hop = representant_one_hop(ind);
if(node_address_one_hop == _empty_eth) {
node_address_one_hop = src_interface;
_one_hop_neighbors.set(node_address_one_hop, Vector<RealNeighbor>());
}
else {
if(!is_good_neighbor(node_address_one_hop) &&
links[src_interface].capa > links[node_address_one_hop].capa) {
_one_hop_neighbors.set(src_interface, _one_hop_neighbors[node_address_one_hop]);
_one_hop_neighbors.erase(node_address_one_hop);
for(int i=0;i<_one_hop_neighbors[src_interface].size();i++) {
EtherAddress thn = _one_hop_neighbors[src_interface][i].neighbor;
if(is_in_hash_table(_two_hop_neighbors, thn)) {
int ind_nei = find_in_vector(_two_hop_neighbors[thn], RealNeighbor(node_address_one_hop));
if(ind_nei !=-1)
_two_hop_neighbors[thn][ind_nei] = RealNeighbor(src_interface, src_interface);
}
}
node_address_one_hop = src_interface;
}
}
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = _two_hop_neighbors.begin();
it!=_two_hop_neighbors.end(); ++it) {
int ind = find_in_vector(it.value(), RealNeighbor(node_address_one_hop, src_interface));
if(ind != -1) {
_two_hop_neighbors[it.key()].erase(&_two_hop_neighbors[it.key()][ind]);
if(_two_hop_neighbors[it.key()].empty())
_two_hop_neighbors.erase(it.key());
}
}
}
for(int i=0; i<ls_pkt->_nb_neighbors;i++) {
EtherAddress neighbor_eth(ls_pkt->_neighbors[i].eth);
RealNeighbor real_neighbor = RealNeighbor(neighbor_eth, ls_pkt->_neighbors[i].weight);
neighbors.push_back(real_neighbor);
if(is_one_hop && !is_good_neighbor(neighbor_eth) && !is_in_vector(me.interfaces, neighbor_eth)) {
if(!is_in_vector(_one_hop_neighbors[node_address_one_hop], real_neighbor))
_one_hop_neighbors[node_address_one_hop].push_back(real_neighbor);
if(!is_in_hash_table(_two_hop_neighbors, neighbor_eth))
_two_hop_neighbors.set(neighbor_eth, Vector<RealNeighbor>(1, RealNeighbor(node_address_one_hop, src_interface, ls_pkt->_neighbors[i].weight)));
else
_two_hop_neighbors[neighbor_eth].push_back(RealNeighbor(node_address_one_hop, src_interface, ls_pkt->_neighbors[i].weight));
}
if(_debug) {
s << real_neighbor.unparse();
}
}
_neighbor_links.set(src_interface, neighbors);
if((_now - _nodes_in_network[ind].last_time_cont_links[ind_int]).sec() >= MAX_FREQ_CONT_LINKS) {
// compute contending links for links out of interface src_interface
_now.assign_now();
_nodes_in_network[ind].last_time_cont_links[ind_int] = _now;
DEBUG_CHATTER("[RoutingLinks %s] Getting contending links for links out of interface %s",
_now.unparse().c_str(),src_interface.unparse().c_str());
// first: get links contending because close to source (interface src_eth)
// also store my neighbors to improve performance (avoid doing twice the same thing)
DEBUG_CHATTER("[RoutingLinks] Getting source neighbors");
HashTable<UndirectedLinkRouting,bool> links_contending_src;
int nb_links = 0;
int nb_cont_links = 0;
for(int n=0;n<neighbors.size();n++) {
links_contending_src.set(UndirectedLinkRouting(src_interface, neighbors[n].neighbor),true);
if(is_in_hash_table(_neighbor_links, neighbors[n].neighbor)) {
Vector<RealNeighbor> neighbors2 = _neighbor_links.get(neighbors[n].neighbor);
for (int n2=0;n2<neighbors2.size();n2++) {
UndirectedLinkRouting link_loc = UndirectedLinkRouting(neighbors[n].neighbor, neighbors2[n2].neighbor);
if(!is_in_hash_table(links_contending_src, link_loc)) // this link has not been added yet
links_contending_src.set(link_loc,true);
}
}
}
// second: for each link out of me, get links contending because close to the destination
DEBUG_CHATTER("[RoutingLinks] Getting destination neighbors (have %d source neighbor links)", links_contending_src.size());
for(int j=0;j<neighbors.size();j++) {
UndirectedLinkRouting this_link = UndirectedLinkRouting(src_interface, neighbors[j].neighbor);
if(!is_in_hash_table(_contending_links_matrix,this_link))
_contending_links_matrix.set(this_link, links_contending_src);
else {
for(HashTable<UndirectedLinkRouting,bool>::iterator it = links_contending_src.begin();it!=links_contending_src.end(); ++it) {
if(!is_in_hash_table(_contending_links_matrix[this_link], it.key()))
_contending_links_matrix[this_link].set(it.key(),true);
}
}
if (is_in_hash_table(_neighbor_links, neighbors[j].neighbor)) {
Vector<RealNeighbor> neighbors_dst = _neighbor_links.get(neighbors[j].neighbor);
for(int n=0;n < neighbors_dst.size();n++) {
if (is_in_hash_table(_neighbor_links, neighbors_dst[n].neighbor)) {
Vector<RealNeighbor> neighbors2 = _neighbor_links.get(neighbors_dst[n].neighbor);
for (int n2=0;n2<neighbors2.size();n2++) {
UndirectedLinkRouting link_loc = UndirectedLinkRouting(neighbors_dst[n].neighbor, neighbors2[n2].neighbor);
if(!is_in_hash_table(_contending_links_matrix[this_link], link_loc))
_contending_links_matrix[this_link].set(link_loc,true);
}
}
}
}
nb_links++;
nb_cont_links += _contending_links_matrix[this_link].size();
}
_now.assign_now();
Timestamp diff = (_now - _nodes_in_network[ind].last_time_cont_links[ind_int]);
DEBUG_CHATTER("[RoutingLinks %s] Got contending links for %d links (%s) in %s seconds (%d contending links in total)",
_now.unparse().c_str(), nb_links, src_interface.unparse().c_str(), diff.unparse().c_str(), nb_cont_links);
_computed_cont_links++;
}
}
if(ls_pkt->_has_invalid_routes) {
invalid_routes_packet *inv_rt_pkt = (invalid_routes_packet *) (p->data() + sizeof(linkstate_packet) + ls_pkt->_nb_neighbors*sizeof(ShortNeighbor));
for (int n=0;n<inv_rt_pkt->_nb_invalid_routes;n++) {
FormatedRoute froute = (FormatedRoute) inv_rt_pkt->_invalid_routes[n];
bool is_for_me = false;
for (int i=0;i<me.interfaces.size();i++) {
if (are_last_bytes_in_addr(froute._dst, me.interfaces[i])) {
is_for_me = true;
break;
}
}
if (is_for_me && _order_elmt) {
click_chatter("[RoutingLinks] Route %s has become invalid", froute.unparse().c_str());
_order_elmt->notify_invalid_route(froute,IPAddress(ls_pkt->_src_ip_node));
}
}
}
if(_debug) {
_now.assign_now();
click_chatter("[RoutingLinks %s] %s", _now.unparse().c_str(), s.c_str());
}
}
void RoutingLinks::compute_my_cont_links() {
if((_now - _last_compute_my_neighbors).sec() >= MAX_FREQ_CONT_LINKS) {
// compute contending links for links out of interface src_interface
_last_compute_my_neighbors.assign_now();
for(int i=0;i<me.interfaces.size();i++) {
EtherAddress src_interface = me.interfaces[i];
Vector<RealNeighbor> neighbors = _neighbors[i];
DEBUG_CHATTER("[RoutingLinks %s] Getting contending links for links out of interface %s",
_now.unparse().c_str(),src_interface.unparse().c_str());
// first: get links contending because close to source (interface src_eth)
// also store my neighbors to improve performance (avoid doing twice the same thing)
DEBUG_CHATTER("[RoutingLinks] Getting source neighbors");
HashTable<UndirectedLinkRouting,bool> links_contending_src;
int nb_links = 0;
int nb_cont_links = 0;
for(int n=0;n<neighbors.size();n++) {
links_contending_src.set(UndirectedLinkRouting(src_interface, neighbors[n].neighbor),true);
if(is_in_hash_table(_neighbor_links, neighbors[n].neighbor)) {
Vector<RealNeighbor> neighbors2 = _neighbor_links.get(neighbors[n].neighbor);
for (int n2=0;n2<neighbors2.size();n2++) {
UndirectedLinkRouting link_loc = UndirectedLinkRouting(neighbors[n].neighbor, neighbors2[n2].neighbor);
if(!is_in_hash_table(links_contending_src, link_loc)) // this link has not been added yet
links_contending_src.set(link_loc,true);
}
}
}
// second: for each link out of me, get links contending because close to the destination
DEBUG_CHATTER("[RoutingLinks] Getting destination neighbors (have %d source neighbor links)", links_contending_src.size());
for(int j=0;j<neighbors.size();j++) {
UndirectedLinkRouting this_link = UndirectedLinkRouting(src_interface, neighbors[j].neighbor);
if(!is_in_hash_table(_contending_links_matrix,this_link))
_contending_links_matrix.set(this_link, links_contending_src);
else {
for(HashTable<UndirectedLinkRouting,bool>::iterator it = links_contending_src.begin();it!=links_contending_src.end(); ++it) {
if(!is_in_hash_table(_contending_links_matrix[this_link], it.key()))
_contending_links_matrix[this_link].set(it.key(),true);
}
}
if (is_in_hash_table(_neighbor_links, neighbors[j].neighbor)) {
Vector<RealNeighbor> neighbors_dst = _neighbor_links.get(neighbors[j].neighbor);
for(int n=0;n < neighbors_dst.size();n++) {
if (is_in_hash_table(_neighbor_links, neighbors_dst[n].neighbor)) {
Vector<RealNeighbor> neighbors2 = _neighbor_links.get(neighbors_dst[n].neighbor);
for (int n2=0;n2<neighbors2.size();n2++) {
UndirectedLinkRouting link_loc = UndirectedLinkRouting(neighbors_dst[n].neighbor, neighbors2[n2].neighbor);
if(!is_in_hash_table(_contending_links_matrix[this_link], link_loc))
_contending_links_matrix[this_link].set(link_loc,true);
}
}
}
}
nb_links++;
nb_cont_links += _contending_links_matrix[this_link].size();
}
_now.assign_now();
Timestamp diff = (_now - _last_compute_my_neighbors);
DEBUG_CHATTER("[RoutingLinks %s] Got contending links for %d links (me: %s) in %s seconds (%d contending links in total)",
_now.unparse().c_str(), nb_links, src_interface.unparse().c_str(), diff.unparse().c_str(), nb_cont_links);
_computed_cont_links++;
}
}
}
bool
RoutingLinks::is_valid_seq_number_ls(const EtherAddress eth, const uint8_t seq_nb) const {
if(!is_in_hash_table(_last_seq_numbers_ls_neighbors, eth))
return true;
uint8_t last_seq_nb = _last_seq_numbers_ls_neighbors[eth];
return is_valid_seq_number(last_seq_nb, seq_nb);
}
bool
RoutingLinks::is_valid_seq_number(const uint8_t last_seq_nb, const uint8_t seq_nb) const {
for(uint8_t i=1; i<=MAX_LOST_LS_PACKET;i++) {
if(seq_nb == (last_seq_nb + i) % MAX_SEQ_NB)
return true;
}
return false;
}
void
RoutingLinks::print_network_parsable() const {
for(int i=0;i<_nodes_in_network.size();i++) {
StringAccum s;
s << "NODE ";
s << _nodes_in_network[i].ip.unparse();
s << " ";
for(int j=0;j<_nodes_in_network[i].interfaces.size();j++) {
s << _nodes_in_network[i].interfaces[j].unparse();
s << " ";
}
click_chatter(s.c_str());
}
for(int i=0;i<_nodes_in_network.size();i++) {
for(int j=0;j<_nodes_in_network[i].interfaces.size();j++) {
EtherAddress eth = _nodes_in_network[i].interfaces[j];
if (is_in_hash_table(_neighbor_links, eth)) {
for(int k=0;k<_neighbor_links[eth].size();k++) {
StringAccum s;
s << "LINK ";
s << eth.unparse();
s << " ";
s << _neighbor_links[eth][k].neighbor.unparse();
s << " ";
s << _neighbor_links[eth][k].weight;
click_chatter(s.c_str());
}
}
}
}
}
void
RoutingLinks::print_statistics() {
for(int i=0;i<me.interfaces.size();i++) {
if(i==me.interfaces.size()-1) {
int nb_MPRs = _MPRs.size();
StringAccum s;
s << "\nNode has ";
s << String(nb_MPRs);
s << " MPRs. They are ";
for(int j=0;j<nb_MPRs;j++) {
s << _MPRs[j].unparse();
if(j<(nb_MPRs-1))
s << ", ";
}
s << ". Have computed contending links for "+String(_computed_cont_links)+"interfaces.\n\n";
click_chatter(s.c_str());
_computed_cont_links = 0;
if(nb_MPRs > 8) {
bool verb_debug = _verb_debug;
_verb_debug = true;
select_MPRs();
_verb_debug = verb_debug;
}
}
}
}
bool
RoutingLinks::time_to_update_weight() {
_now.assign_now();
bool result = ((_now - _last_discovered_neighbor).sec() <= 20 && (_now - _last_weight_update).sec() >= 20) ||
((_now - _last_discovered_neighbor).sec() <= 60 && (_now - _last_weight_update).sec() >= 60) ||
((_now - _begin).sec() <= (BEGIN_DURATION+20) && (_now - _last_weight_update).sec() >= 5) ||
((_now - _begin).sec() <= (BEGIN_DURATION+60) && (_now - _last_weight_update).sec() >= 20) ||
((_now - _begin).sec() <= (BEGIN_DURATION+300) && (_now - _last_weight_update).sec() >= 60) ||
((_now - _last_weight_update).sec() >= MIN_TIME_WEIGHT_UPDATE);
return result;
}
Vector<EtherAddress>
RoutingLinks::select_MPRs(bool &infinite_loop) {
infinite_loop = false;
if(_two_hop_neighbors.size() > 0) {
Vector<EtherAddress> MPRs = Vector<EtherAddress>();
Vector<EtherAddress> toremove = Vector<EtherAddress>();
LinksTable links = _neighbors_elmt->get_outgoing_links();
HashTable<EtherAddress, Vector<RealNeighbor> > one_hop_neighbors = _one_hop_neighbors;
HashTable<EtherAddress, Vector<RealNeighbor> > two_hop_neighbors = _two_hop_neighbors;
StringAccum s;
if(_verb_debug) {
VERB_DEBUG_CHATTER("[RoutingLinks] There are %d one hop neighbors", one_hop_neighbors.size());
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = one_hop_neighbors.begin();
it!=one_hop_neighbors.end(); ++it) {
s << it.key().unparse();
s << ": ";
for(int i=0;i<it.value().size();i++) {
s << it.value()[i].neighbor.unparse();
if(i<(it.value().size()-1))
s << " ";
}
s<<".\n";
}
s << "\n";
VERB_DEBUG_CHATTER(s.c_str());
s.clear();
VERB_DEBUG_CHATTER("[RoutingLinks] There are %d two hop neighbors.", two_hop_neighbors.size());
}
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = two_hop_neighbors.begin();
it!=two_hop_neighbors.end(); ++it) {
if(is_good_neighbor(it.key()) || it.value().empty()) {
for(int i=0;i<it.value().size();i++) {
int ind = find_in_vector(_one_hop_neighbors[it.value()[i].neighbor], RealNeighbor(it.key()));
if(ind!=-1)
_one_hop_neighbors[it.value()[i].neighbor].erase(&_one_hop_neighbors[it.value()[i].neighbor][ind]);
}
_two_hop_neighbors.erase(it.key());
toremove.push_back(it.key());
}
else {
if(_verb_debug) {
s << it.key().unparse();
s << ": ";
for(int i=0;i<it.value().size();i++) {
s << it.value()[i].neighbor.unparse();
if(i<(it.value().size()-1))
s << " ";
}
s<<".\n";
}
if(it.value().size() == 1) {
EtherAddress mpr = it.value()[0].neighbor;
if(!is_in_vector(MPRs, mpr)) {
MPRs.push_back(mpr);
for(int i=0;i<one_hop_neighbors[mpr].size();i++) {
toremove.push_back(one_hop_neighbors[mpr][i].neighbor);
}
}
}
}
}
s<<"\n";
VERB_DEBUG_CHATTER(s.c_str());
s.clear();
for(int i=0;i<MPRs.size();i++) {
one_hop_neighbors.erase(MPRs[i]);
VERB_DEBUG_CHATTER("[RoutingLinks] %s is MPR (unique neighbor).", MPRs[i].unparse().c_str());
}
for(int i=0;i<toremove.size();i++)
two_hop_neighbors.erase(toremove[i]);
toremove.clear();
VERB_DEBUG_CHATTER("[RoutingLinks] %d two hop neighbors remaining.", two_hop_neighbors.size());
int max_degree = 0;
EtherAddress best_neighbor;
int count = 0;
bool debug = false;
while(two_hop_neighbors.size() > 0) {
if(count > _nodes_in_network.size()) {
click_chatter("\n\n\n WARNING: Infinite loop in MPR selection, count=%d\n\n Remaining two hop neighbors are:\n", count);
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = two_hop_neighbors.begin();
it!=two_hop_neighbors.end(); ++it) {
s << it.key().unparse();
s << ", is neighbor from ";
for(int i=0;i<it.value().size();i++) {
s << it.value()[i].neighbor.unparse();
if(i<(it.value().size()-1))
s << " ";
}
s<<".\n";
click_chatter(s.c_str());
s.clear();
infinite_loop = true;
}
break;
}
HashTable<EtherAddress, Vector<EtherAddress> > good_local_neighbors = HashTable<EtherAddress, Vector<EtherAddress> >();
uint32_t max_capa = 0;
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = one_hop_neighbors.begin();
it!=one_hop_neighbors.end(); ++it) {
if(links[it.key()].capa > max_capa) {
for(int i=0;i<it.value().size();i++) {
if(is_in_hash_table(two_hop_neighbors, it.value()[i].neighbor)) {
max_capa = links[it.key()].capa;
break;
}
}
}
}
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = one_hop_neighbors.begin();
it!=one_hop_neighbors.end(); ++it) {
//TODO: CHECK FOLLOWING LINE
if(is_good_neighbor(it.key()) || ((uint32_t)1000 * links[it.key()].capa >= (uint32_t)750 * max_capa) ) {
if(debug)
VERB_DEBUG_CHATTER("[RoutingLinks] %s is good neighbor", it.key().unparse().c_str());
int degree = 0;
for(int i=0;i<it.value().size();i++) {
EtherAddress thn = it.value()[i].neighbor;
if(is_in_hash_table(two_hop_neighbors, thn)) {
if(debug)
VERB_DEBUG_CHATTER("[RoutingLinks] %s is in two_hop_neighbors", thn.unparse().c_str());
// consider this two-hop neighbor only if it's a "good" neighbor
uint32_t min_weight = DEFAULT_WEIGHT;
uint32_t weight = DEFAULT_WEIGHT;
for(int j=0;j<two_hop_neighbors[thn].size();j++) {
RealNeighbor ohn = two_hop_neighbors[thn][j];
if(ohn.neighbor == it.key()) {
weight = ohn.weight;
if(weight < THRES_WEIGHT_GOOD_NEI)
break;
}
//TODO: CHECK FOLLOWING LINE
if((is_good_neighbor(ohn.neighbor) || ((uint32_t)1000 * links[ohn.neighbor].capa >= (uint32_t)750 * max_capa) ) &&
ohn.weight < min_weight)
min_weight = ohn.weight;
}
if(debug)
VERB_DEBUG_CHATTER("[RoutingLinks] weight is %d, min_weight is %d", weight, min_weight);
//TODO: CHECK FOLLOWING LINE
if(weight < THRES_WEIGHT_GOOD_NEI || ( (uint32_t)1000 * weight <= (uint32_t)1250 * min_weight) ) {
if(!is_in_hash_table(good_local_neighbors, it.key()))
good_local_neighbors.set(it.key(), Vector<EtherAddress>());
if(!is_in_vector(good_local_neighbors[it.key()], thn)) {
degree++;
good_local_neighbors[it.key()].push_back(thn);
int ind = get_ind_node_routing(thn);
if(ind != -1) { // might happen at the beginning, but not a problem
for(int j=0;j<_nodes_in_network[ind].interfaces.size();j++) {
good_local_neighbors[it.key()].push_back(_nodes_in_network[ind].interfaces[j]);
}
}
}
}
}
}
if(degree > max_degree) {
max_degree = degree;
best_neighbor = it.key();
}
}
}
VERB_DEBUG_CHATTER("[RoutingLinks] %s is MPR (degree %d).", best_neighbor.unparse().c_str(), max_degree);
if(best_neighbor != _empty_eth) {
MPRs.push_back(best_neighbor);
for(int i=0;i<good_local_neighbors[best_neighbor].size();i++)
two_hop_neighbors.erase(good_local_neighbors[best_neighbor][i]);
one_hop_neighbors.erase(best_neighbor);
}
else {
if(_verb_debug) {
debug = true;
VERB_DEBUG_CHATTER("[RoutingLinks] There are %d one hop neighbors", one_hop_neighbors.size());
for(HashTable<EtherAddress, Vector<RealNeighbor> >::iterator it = one_hop_neighbors.begin();
it!=one_hop_neighbors.end(); ++it) {
s << it.key().unparse();
s << ": ";
for(int i=0;i<it.value().size();i++) {
s << it.value()[i].neighbor.unparse();
if(i<(it.value().size()-1))
s << " ";
}
s<<".\n";
}
s << "\n";
VERB_DEBUG_CHATTER(s.c_str());
s.clear();
VERB_DEBUG_CHATTER("[RoutingLinks] max_capa is %d", max_capa);
}
}
VERB_DEBUG_CHATTER("[RoutingLinks] %d two hop neighbors remaining.", two_hop_neighbors.size());
max_degree = 0;
best_neighbor = _empty_eth;
count++;
}
return MPRs;
}
else {
DEBUG_CHATTER("[RoutingLinks] No two hop neighbors.");
return Vector<EtherAddress>();
}
}
Vector<EtherAddress>
RoutingLinks::select_MPRs() {
bool b;
return select_MPRs(b);
}
bool
RoutingLinks::is_good_neighbor(EtherAddress eth) {
LinksTable links = _neighbors_elmt->get_outgoing_links();
if(is_in_hash_table(links, eth)) {
uint32_t weight;
if(links[eth].capa > 0)
weight = mymin(int_divide(SCALE_WEIGHTS, links[eth].capa), DEFAULT_WEIGHT); // weight=SCALE_WEIGHTS/capacity in kb/s
// weight=1->10000 for capa ~0.05->~500Mb/s
else
weight = DEFAULT_WEIGHT;
return weight < THRES_WEIGHT_GOOD_NEI;
}
else
return false;
}
//bool
//RoutingLinks::is_neighbor(EtherAddress eth) {
// return is_in_hash_table(_neighbors_elmt->get_outgoing_links(), eth);
//}
void
RoutingLinks::delete_one_hop_neighbor(EtherAddress eth) {
if(is_in_hash_table(_one_hop_neighbors, eth)) {
for(int k=0;k<_one_hop_neighbors[eth].size();k++) {
EtherAddress two_hop_neighbor = _one_hop_neighbors[eth][k].neighbor;
if(is_in_hash_table(_two_hop_neighbors, two_hop_neighbor)) {
int ind = find_in_vector(_two_hop_neighbors[two_hop_neighbor], RealNeighbor(eth));
if(ind != -1) {
_two_hop_neighbors[two_hop_neighbor].erase(&_two_hop_neighbors[two_hop_neighbor][ind]);
if(_two_hop_neighbors[two_hop_neighbor].empty())
_two_hop_neighbors.erase(two_hop_neighbor);
}
}
}
_one_hop_neighbors.erase(eth);
}
}
int
RoutingLinks::get_ind_node_routing(EtherAddress eth) {
int ind = -1;
for(int i=(_nodes_in_network.size()-1);i>=0;i--) {
if(is_in_vector(_nodes_in_network[i].interfaces, eth)) {
ind = i;
break;
}
}
return ind;
}
EtherAddress
RoutingLinks::representant_one_hop(int ind) {
EtherAddress node_address_one_hop = _empty_eth;
for(int i=0;i<_nodes_in_network[ind].interfaces.size();i++) {
if(is_in_hash_table(_one_hop_neighbors, _nodes_in_network[ind].interfaces[i])) {
node_address_one_hop = _nodes_in_network[ind].interfaces[i];
break;
}
}
return node_address_one_hop;
}
void
RoutingLinks::notify_end() {
click_chatter("[RoutingLinks] Cleaning up...");
for(int i=0;i<me.interfaces.size();i++) {
_neighbors.set(i, Vector<RealNeighbor>());
}
push_linkstate_packets(true);
timer.clear();
_stop_processing = true;
}
Packet *
RoutingLinks::add_headers(Packet *p_in, EtherAddress next_hop, int interface_out, uint8_t type, uint8_t type_rtg) {
if(_debug) {
_now.assign_now();
click_chatter("[RoutingLinks %s] Adding headers to %p of type %d for interface %d...",
_now.unparse().c_str(), p_in, (int) type, interface_out);
}
// add the ethernet header
WritablePacket *p;
switch (type) {
case REGULAR_TRAFFIC: {
p = p_in->push(sizeof(click_ether));
if (!p) {
click_chatter("[RoutingLinks] Couldn't add space for new Ethernet header\n");
return p;
}
click_ip *ip = (click_ip *)(p->data() + sizeof(empower_header) + sizeof(click_ether));
p->set_ip_header(ip, sizeof(click_ip));
break;
}
case ROUTING_CTRL: {
if(_use_MPR) {
StringAccum s;
if(_MPRs.size() > 0) {
s << "MPRs are ";
for(int i=0;i<_MPRs.size();i++) {
s << _MPRs[i].unparse();
if(i<(_MPRs.size()-1))
s << " ";
}
s << ".";
DEBUG_CHATTER(s.c_str());
}
}
p = p_in->push(sizeof(linkstate_header) + _MPRs.size()*sizeof(MPR) + sizeof(click_ether) + sizeof(empower_header));
if (!p) {
click_chatter("[RoutingLinks] Couldn't add space for new headers\n");
return p;
}
linkstate_header *ls_hdr = (linkstate_header *) (p->data() + sizeof(click_ether) + sizeof(empower_header));
ls_hdr->_type = type_rtg;
ls_hdr->_MPR_retr_bool = _use_MPR;
ls_hdr->_nb_retr = _MPRs.size();
for(int j=0;j<_MPRs.size();j++) {
ls_hdr->_retr[j].eth = _MPRs[j];
}
if (!p) {
click_chatter("[RoutingLinks] Couldn't add space for new headers\n");
return p;
}
empower_header *empower_hdr = (empower_header *) (p->data() + sizeof(click_ether));
empower_hdr->_type = ROUTING_CTRL;
for (int b=0;b<NB_BYTES_HOP;b++) {
empower_hdr->_route._src[b] = me.interfaces[interface_out].data()[6-NB_BYTES_HOP+b];
}
for (int b=0;b<NB_BYTES_HOP;b++) {
empower_hdr->_route._dst[b] = next_hop.data()[6-NB_BYTES_HOP+b];
}
if (!p) {
click_chatter("[RoutingLinks] Couldn't add space for new headers\n");
return p;
}
break;
}
default:
return 0;
}
click_ether *eth_hdr = (click_ether *) (p->data());
eth_hdr->ether_type = htons(ETHERTYPE_EMPOWER);
memcpy(eth_hdr->ether_shost, me.interfaces[interface_out].data(), 6);
memcpy(eth_hdr->ether_dhost, next_hop.data(), 6);
p->set_mac_header(p->data());
return p;
}
// returns a Route from a FormatedRoute. Links are unweighted.
Route
RoutingLinks::get_route_from_froute(FormatedRoute froute) {
if(!_debug && is_in_hash_table(_froute_to_route, froute))
return _froute_to_route[froute];
Route route;
EtherAddress last_eth = get_ether_address(LastAddrBytes(&froute._src[0]));
NodeRouting previous_node = get_node_from_eth(last_eth);
for(uint8_t i=0; i<HDR_ROUTE_SIZE; i++) {
if(previous_node == NodeRouting()) {
_now.assign_now();
click_chatter("[RoutingLinks %s] WARNING: when getting route from froute, got a 0 RoutingNode for %s",
_now.unparse().c_str(), last_eth.unparse().c_str());
return Route();
}
LastAddrBytes bytes = LastAddrBytes(&froute._route[i*NB_BYTES_HOP]);
EtherAddress dst_link = get_ether_address(bytes);
if(dst_link == EtherAddress())
break;
EtherAddress addr;
if(is_wifi_addr(dst_link))
addr = previous_node.get_wifi_interface();
else if(is_plc_addr(dst_link))
addr = previous_node.get_plc_interface();
else {
_now.assign_now();
click_chatter("[RoutingLinks %s] WARNING: got ethernet address %s, neither wifi nor PLC",
_now.unparse().c_str(), dst_link.unparse().c_str());
return Route();
}
if(addr == EtherAddress()) {
_now.assign_now();
click_chatter("[RoutingLinks %s] WARNING: got ethernet address 0 for node %s, next hop %s",
_now.unparse().c_str(), previous_node.ip.unparse().c_str(), dst_link.unparse().c_str());
return Route();
}
route.links.push_back(LinkRouting(addr, dst_link, 0));
previous_node = get_node_from_eth(dst_link);
last_eth = dst_link;
}
_froute_to_route[froute] = route;
return route;
}
EXPORT_ELEMENT(RoutingLinks)
CLICK_ENDDECLS

Event Timeline

c4science · Help