examples/java/kademlia/RoutingTable.java

   1 /* Copyright (c) 2012-2014. The SimGrid Team.
   2  * All rights reserved.                                                     */
   3
   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. */
   6
   7 package kademlia;
   8 import java.util.Collections;
   9 import java.util.Vector;
  10
  11 import org.simgrid.msg.Msg;
  12 /**
  13  * @brief Contains the various data of a routing table.
  14  */
  15 public class RoutingTable {
  16         /**
  17          * Bucket list
  18          */
  19         private Vector<Bucket> buckets;
  20         /**
  21          * Id of the routing table owner
  22          */
  23         private int id;
  24         /**
  25          * Constructor
  26          */
  27         public RoutingTable(int id) {
  28                 this.id = id;
  29                 buckets = new Vector<Bucket>();
  30                 for (int i = 0; i < Common.IDENTIFIER_SIZE + 1; i++) {
  31                         buckets.add(new Bucket(i));
  32                 }
  33         }
  34         /**
  35          * Returns an identifier which is in a specific bucket of a routing table
  36          * @brief id id of the routing table owner
  37          * @brief prefix id of the bucket where we want that identifier to be
  38          */
  39         public int getIdInPrefix(int id, int prefix) {
  40                 if (prefix == 0) {
  41                         return 0;
  42                 }
  43                 int identifier = 1;
  44                 identifier = identifier << (prefix - 1);
  45                 identifier = identifier ^ id;
  46                 return identifier;
  47         }
  48         /**
  49          * Returns the corresponding node prefix for a given id
  50          */
  51         public int getNodePrefix(int id) {
  52                 for (int j = 0; j < 32; j++) {
  53                         if ((id >> (32 - 1 - j) & 0x1) != 0) {
  54                                 return 32 - j;
  55                         }
  56                 }
  57                 return 0;
  58         }
  59         /**
  60           * Fins the corresponding bucket in a routing table for a given identifier
  61           */
  62         public Bucket findBucket(int id) {
  63                 int xorNumber = id ^ this.id;
  64 //              Msg.info("Number:" + xorNumber.toString(16));
  65                 int prefix = this.getNodePrefix(xorNumber);
  66
  67                 return buckets.get(prefix);
  68         }
  69         /**
  70          * Updates the routing table with a new value.
  71          */
  72         public void update(int id) {
  73
  74                 Bucket bucket = this.findBucket(id);
  75                 if (bucket.contains(id)) {
  76                         Msg.debug("Updating " + Integer.toString(id) + " in my routing table");
  77                         //If the element is already in the bucket, we update it.
  78                         bucket.pushToFront(id);
  79                 }
  80                 else {
  81                         Msg.debug("Adding " + id + " to my routing table");
  82                         bucket.add(id);
  83                         if (bucket.size() > Common.BUCKET_SIZE)  {
  84                                 //TODO: Ping the least seen guy and remove him if he is offline.
  85                         }
  86                 }
  87         }
  88         /**
  89          * Returns the closest notes we know to a given id
  90          */
  91         public Answer findClosest(int destinationId) {
  92                 Answer answer = new Answer(destinationId);
  93
  94
  95                 Bucket bucket = this.findBucket(destinationId);
  96                 bucket.addToAnswer(answer,destinationId);
  97
  98                 for (int i = 1; answer.size() < Common.BUCKET_SIZE &&
  99                 ((bucket.getId() - i) >= 0 ||
 100                 (bucket.getId() + i) <= Common.IDENTIFIER_SIZE); i++) {
 101                         //Check the previous buckets
 102                         if (bucket.getId() - i >= 0) {
 103                                 Bucket bucketP = this.buckets.get(bucket.getId() - i);
 104                                 bucketP.addToAnswer(answer,destinationId);
 105                         }
 106                         //Check the next buckets
 107                         if (bucket.getId() + i <= Common.IDENTIFIER_SIZE) {
 108                                 Bucket bucketN = this.buckets.get(bucket.getId() + i);
 109                                 bucketN.addToAnswer(answer, destinationId);
 110                         }
 111                 }
 112                 //We sort the list
 113                 Collections.sort(answer.getNodes());
 114                 //We trim the list
 115                 while (answer.size() > Common.BUCKET_SIZE) {
 116                         answer.remove(answer.size() - 1); //TODO: Not the best thing.
 117                 }
 118
 119                 return answer;
 120         }
 121
 122         @Override
 123         public String toString() {
 124                 String string = "RoutingTable [ id=" + id + " " ;
 125                 for (int i = 0; i < buckets.size(); i++) {
 126                         if (buckets.get(i).size() > 0) {
 127                                 string += buckets.get(i) + " ";
 128                         }
 129                 }
 130                 return string;
 131         }
 132
 133 }