1 /* Copyright (c) 2012-2013. The SimGrid Team.
2 * All rights reserved. */
4 /* This program is free software; you can redistribute it and/or modify it
5 * under the terms of the license (GNU LGPL) which comes with this package. */
7 import java.util.Collections;
8 import java.util.Vector;
10 import org.simgrid.msg.Msg;
12 * @brief Contains the various data of a routing table.
14 public class RoutingTable {
18 private Vector<Bucket> buckets;
20 * Id of the routing table owner
26 public RoutingTable(int id) {
28 buckets = new Vector<Bucket>();
29 for (int i = 0; i < Common.IDENTIFIER_SIZE + 1; i++) {
30 buckets.add(new Bucket(i));
34 * Returns an identifier which is in a specific bucket of a routing table
35 * @brief id id of the routing table owner
36 * @brief prefix id of the bucket where we want that identifier to be
38 public int getIdInPrefix(int id, int prefix) {
43 identifier = identifier << (prefix - 1);
44 identifier = identifier ^ id;
48 * Returns the corresponding node prefix for a given id
50 public int getNodePrefix(int id) {
51 for (int j = 0; j < 32; j++) {
52 if ((id >> (32 - 1 - j) & 0x1) != 0) {
59 * Fins the corresponding bucket in a routing table for a given identifier
61 public Bucket findBucket(int id) {
62 int xorNumber = id ^ this.id;
63 // Msg.info("Number:" + xorNumber.toString(16));
64 int prefix = this.getNodePrefix(xorNumber);
66 return buckets.get(prefix);
69 * Updates the routing table with a new value.
71 public void update(int id) {
73 Bucket bucket = this.findBucket(id);
74 if (bucket.contains(id)) {
75 Msg.debug("Updating " + Integer.toString(id) + " in my routing table");
76 //If the element is already in the bucket, we update it.
77 bucket.pushToFront(id);
80 Msg.debug("Adding " + id + " to my routing table");
82 if (bucket.size() > Common.BUCKET_SIZE) {
83 //TODO: Ping the least seen guy and remove him if he is offline.
88 * Returns the closest notes we know to a given id
90 public Answer findClosest(int destinationId) {
91 Answer answer = new Answer(destinationId);
94 Bucket bucket = this.findBucket(destinationId);
95 bucket.addToAnswer(answer,destinationId);
97 for (int i = 1; answer.size() < Common.BUCKET_SIZE &&
98 ((bucket.getId() - i) >= 0 ||
99 (bucket.getId() + i) <= Common.IDENTIFIER_SIZE); i++) {
100 //Check the previous buckets
101 if (bucket.getId() - i >= 0) {
102 Bucket bucketP = this.buckets.get(bucket.getId() - i);
103 bucketP.addToAnswer(answer,destinationId);
105 //Check the next buckets
106 if (bucket.getId() + i <= Common.IDENTIFIER_SIZE) {
107 Bucket bucketN = this.buckets.get(bucket.getId() + i);
108 bucketN.addToAnswer(answer, destinationId);
112 Collections.sort(answer.getNodes());
114 while (answer.size() > Common.BUCKET_SIZE) {
115 answer.remove(answer.size() - 1); //TODO: Not the best thing.
122 public String toString() {
123 String string = "RoutingTable [ id=" + id + " " ;
124 for (int i = 0; i < buckets.size(); i++) {
125 if (buckets.get(i).size() > 0) {
126 string += buckets.get(i) + " ";