contrib/psg/src/example/chord/ChordProtocol.java

   1 /**\r
   2  * \r
   3  */\r
   4 package example.chord;\r
   5 \r
   6 import peersim.config.Configuration;\r
   7 import peersim.core.CommonState;\r
   8 import peersim.core.Network;\r
   9 import peersim.core.Node;\r
  10 import peersim.edsim.EDProtocol;\r
  11 import peersim.transport.Transport;\r
  12 \r
  13 import java.math.*;\r
  14 \r
  15 import org.simgrid.msg.Host;\r
  16 import org.simgrid.msg.Msg;\r
  17 \r
  18 /**\r
  19  * @author Andrea\r
  20  * \r
  21  */\r
  22 public class ChordProtocol implements EDProtocol {\r
  23 \r
  24         private static final String PAR_TRANSPORT = "transport";\r
  25 \r
  26         private Parameters p;\r
  27 \r
  28         private int[] lookupMessage;\r
  29 \r
  30         public int index = 0;\r
  31 \r
  32         public Node predecessor;\r
  33 \r
  34         public Node[] fingerTable;\r
  35 \r
  36         public Node[] successorList;\r
  37 \r
  38         public BigInteger chordId;\r
  39 \r
  40         public int m;\r
  41 \r
  42         public int succLSize;\r
  43 \r
  44         public String prefix;\r
  45 \r
  46         private int next = 0;\r
  47 \r
  48         // campo x debug\r
  49         private int currentNode = 0;\r
  50 \r
  51         public int varSuccList = 0;\r
  52 \r
  53         public int stabilizations = 0;\r
  54 \r
  55         public int fails = 0;\r
  56 \r
  57         /**\r
  58          * \r
  59          */\r
  60         public ChordProtocol(String prefix) {\r
  61                 this.prefix = prefix;\r
  62                 lookupMessage = new int[1];\r
  63                 lookupMessage[0] = 0;\r
  64                 p = new Parameters();\r
  65                 p.tid = Configuration.getPid(prefix + "." + PAR_TRANSPORT);\r
  66         }\r
  67 \r
  68         /*\r
  69          * (non-Javadoc)\r
  70          * \r
  71          * @see peersim.edsim.EDProtocol#processEvent(peersim.core.Node, int,\r
  72          * java.lang.Object)\r
  73          */\r
  74         public void processEvent(Node node, int pid, Object event) {\r
  75                 // processare le richieste a seconda della routing table del nodo\r
  76                 p.pid = pid;\r
  77                 // currentNode = node.getIndex();\r
  78                 currentNode = (int) node.getID();\r
  79                 if (event.getClass() == LookUpMessage.class) {\r
  80                         LookUpMessage message = (LookUpMessage) event;\r
  81                         message.increaseHopCounter();\r
  82                         BigInteger target = message.getTarget();\r
  83                         Transport t = (Transport) node.getProtocol(p.tid);\r
  84                         Node n = message.getSender();\r
  85                         System.out.println("R process " + "at time="\r
  86                                         + CommonState.getTime() + " to dest:" + currentNode\r
  87                                         + " from src:" + n.getID() + " message: ("\r
  88                                         + message.getSender().getID() + ";" + message.getTarget()\r
  89                                         + ")");\r
  90                         if (target == ((ChordProtocol) node.getProtocol(pid)).chordId) {\r
  91                                 // mandare mess di tipo final\r
  92                                 Object msg = new FinalMessage(message.getHopCounter());\r
  93                                 System.out.println("S Final Message " + "at time="\r
  94                                                 + CommonState.getTime() + " from src:" + node.getID()\r
  95                                                 + " to dest:" + n.getID() + " message: "\r
  96                                                 + message.getHopCounter() + " HopCounter");\r
  97                                 t.send(node, n, msg, pid);\r
  98 \r
  99                         }\r
 100                         if (target != ((ChordProtocol) node.getProtocol(pid)).chordId) {\r
 101                                 // funzione lookup sulla fingertabable\r
 102                                 Node dest = find_successor(target);\r
 103                                 if (dest.isUp() == false) {\r
 104                                         do {\r
 105                                                 varSuccList = 0;\r
 106                                                 stabilize(node);\r
 107                                                 stabilizations++;\r
 108                                                 fixFingers();\r
 109                                                 dest = find_successor(target);\r
 110                                         } while (dest.isUp() == false);\r
 111                                 }\r
 112                                 if (dest.getID() == successorList[0].getID()\r
 113                                                 && (target.compareTo(((ChordProtocol) dest\r
 114                                                                 .getProtocol(p.pid)).chordId) < 0)) {\r
 115                                         fails++;\r
 116                                 } else {\r
 117                                         System.out.println("S process " + "at time="\r
 118                                                         + CommonState.getTime() + " from src:"\r
 119                                                         + node.getID() + " to dest:" + dest.getID()\r
 120                                                         + " message: (" + message.getSender().getID() + ";"\r
 121                                                         + message.getTarget() + ")");\r
 122                                         // t.send(message.getSender(), dest, message, pid);\r
 123                                         t.send(node, dest, message, pid);\r
 124 \r
 125                                 }\r
 126                         }\r
 127                 }\r
 128                 if (event.getClass() == FinalMessage.class) {\r
 129                         FinalMessage message = (FinalMessage) event;\r
 130                         System.out.println("R Final Message " + "at time="\r
 131                                         + CommonState.getTime() + " to dest:" + node.getID()+"\n");\r
 132                         lookupMessage = new int[index + 1];\r
 133                         lookupMessage[index] = message.getHopCounter();\r
 134                         index++;\r
 135                 }\r
 136         }\r
 137 \r
 138         public Object clone() {\r
 139                 ChordProtocol cp = new ChordProtocol(prefix);\r
 140                 String val = BigInteger.ZERO.toString();\r
 141                 cp.chordId = new BigInteger(val);\r
 142                 cp.fingerTable = new Node[m];\r
 143                 cp.successorList = new Node[succLSize];\r
 144                 cp.currentNode = 0;\r
 145                 return cp;\r
 146         }\r
 147 \r
 148         public int[] getLookupMessage() {\r
 149                 return lookupMessage;\r
 150         }\r
 151 \r
 152         public void stabilize(Node myNode) {\r
 153                 try {\r
 154                         Node node = ((ChordProtocol) successorList[0].getProtocol(p.pid)).predecessor;\r
 155                         if (node != null) {\r
 156                                 if (this.chordId == ((ChordProtocol) node.getProtocol(p.pid)).chordId)\r
 157                                         return;\r
 158                                 BigInteger remoteID = ((ChordProtocol) node.getProtocol(p.pid)).chordId;\r
 159                                 if (idInab(\r
 160                                                 remoteID,\r
 161                                                 chordId,\r
 162                                                 ((ChordProtocol) successorList[0].getProtocol(p.pid)).chordId))\r
 163                                         successorList[0] = node;\r
 164                                 ((ChordProtocol) successorList[0].getProtocol(p.pid))\r
 165                                                 .notify(myNode);\r
 166                         }\r
 167                         updateSuccessorList();\r
 168                 } catch (Exception e1) {\r
 169                         e1.printStackTrace();\r
 170                         updateSuccessor();\r
 171                 }\r
 172         }\r
 173 \r
 174         private void updateSuccessorList() throws Exception {\r
 175                 try {\r
 176                         while (successorList[0] == null || successorList[0].isUp() == false) {\r
 177                                 updateSuccessor();\r
 178                         }\r
 179                         System.arraycopy(\r
 180                                         ((ChordProtocol) successorList[0].getProtocol(p.pid)).successorList,\r
 181                                         0, successorList, 1, succLSize - 2);\r
 182                 } catch (Exception e) {\r
 183                         e.printStackTrace();\r
 184                 }\r
 185         }\r
 186 \r
 187         public void notify(Node node) throws Exception {\r
 188                 BigInteger nodeId = ((ChordProtocol) node.getProtocol(p.pid)).chordId;\r
 189                 if ((predecessor == null)\r
 190                                 || (idInab(\r
 191                                                 nodeId,\r
 192                                                 ((ChordProtocol) predecessor.getProtocol(p.pid)).chordId,\r
 193                                                 this.chordId))) {\r
 194                         predecessor = node;\r
 195                 }\r
 196         }\r
 197 \r
 198         private void updateSuccessor() {\r
 199                 boolean searching = true;\r
 200                 while (searching) {\r
 201                         try {\r
 202                                 Node node = successorList[varSuccList];\r
 203                                 varSuccList++;\r
 204                                 successorList[0] = node;\r
 205                                 if (successorList[0] == null\r
 206                                                 || successorList[0].isUp() == false) {\r
 207                                         if (varSuccList >= succLSize - 1) {\r
 208                                                 searching = false;\r
 209                                                 varSuccList = 0;\r
 210                                         } else\r
 211                                                 updateSuccessor();\r
 212                                 }\r
 213                                 updateSuccessorList();\r
 214                                 searching = false;\r
 215                         } catch (Exception e) {\r
 216                                 e.printStackTrace();\r
 217                         }\r
 218                 }\r
 219         }\r
 220 \r
 221         private boolean idInab(BigInteger id, BigInteger a, BigInteger b) {\r
 222                 if ((a.compareTo(id) == -1) && (id.compareTo(b) == -1)) {\r
 223                         return true;\r
 224                 }\r
 225                 return false;\r
 226         }\r
 227 \r
 228         public Node find_successor(BigInteger id) {\r
 229                 try {\r
 230                         if (successorList[0] == null || successorList[0].isUp() == false) {\r
 231                                 updateSuccessor();\r
 232                         }\r
 233                         if (idInab(\r
 234                                         id,\r
 235                                         this.chordId,\r
 236                                         ((ChordProtocol) successorList[0].getProtocol(p.pid)).chordId)) {\r
 237                                 return successorList[0];\r
 238                         } else {\r
 239                                 Node tmp = closest_preceding_node(id);\r
 240                                 return tmp;\r
 241                         }\r
 242                 } catch (Exception e) {\r
 243                         e.printStackTrace();\r
 244                 }\r
 245                 return successorList[0];\r
 246         }\r
 247 \r
 248         private Node closest_preceding_node(BigInteger id) {\r
 249                 for (int i = m; i > 0; i--) {\r
 250                         try {\r
 251                                 if (fingerTable[i - 1] == null\r
 252                                                 || fingerTable[i - 1].isUp() == false) {\r
 253                                         continue;\r
 254                                 }\r
 255                                 BigInteger fingerId = ((ChordProtocol) (fingerTable[i - 1]\r
 256                                                 .getProtocol(p.pid))).chordId;\r
 257                                 if ((idInab(fingerId, this.chordId, id))\r
 258                                                 || (id.compareTo(fingerId) == 0)) {\r
 259                                         return fingerTable[i - 1];\r
 260                                 }\r
 261                                 if (fingerId.compareTo(this.chordId) == -1) {\r
 262                                         // sono nel caso in cui ho fatto un giro della rete\r
 263                                         // circolare\r
 264                                         if (idInab(id, fingerId, this.chordId)) {\r
 265                                                 return fingerTable[i - 1];\r
 266                                         }\r
 267                                 }\r
 268                                 if ((id.compareTo(fingerId) == -1)\r
 269                                                 && (id.compareTo(this.chordId) == -1)) {\r
 270                                         if (i == 1)\r
 271                                                 return successorList[0];\r
 272                                         BigInteger lowId = ((ChordProtocol) fingerTable[i - 2]\r
 273                                                         .getProtocol(p.pid)).chordId;\r
 274                                         if (idInab(id, lowId, fingerId))\r
 275                                                 return fingerTable[i - 2];\r
 276                                         else if (fingerId.compareTo(this.chordId) == -1)\r
 277                                                 continue;\r
 278                                         else if (fingerId.compareTo(this.chordId) == 1)\r
 279                                                 return fingerTable[i - 1];\r
 280                                 }\r
 281                         } catch (Exception e) {\r
 282                                 e.printStackTrace();\r
 283                         }\r
 284                 }\r
 285                 if (fingerTable[m - 1] == null)\r
 286                         return successorList[0];\r
 287                 return successorList[0];\r
 288         }\r
 289 \r
 290         // debug function\r
 291         private void printFingers() {\r
 292                 for (int i = fingerTable.length - 1; i > 0; i--) {\r
 293                         if (fingerTable[i] == null) {\r
 294                                 System.out.println("Finger " + i + " is null");\r
 295                                 continue;\r
 296                         }\r
 297                         if ((((ChordProtocol) fingerTable[i].getProtocol(p.pid)).chordId)\r
 298                                         .compareTo(this.chordId) == 0)\r
 299                                 break;\r
 300                         System.out\r
 301                                         .println("Finger["\r
 302                                                         + i\r
 303                                                         + "] = "\r
 304                                                         + fingerTable[i].getIndex()\r
 305                                                         + " chordId "\r
 306                                                         + ((ChordProtocol) fingerTable[i]\r
 307                                                                         .getProtocol(p.pid)).chordId);\r
 308                 }\r
 309         }\r
 310 \r
 311         public void fixFingers() {\r
 312                 if (next >= m - 1)\r
 313                         next = 0;\r
 314                 if (fingerTable[next] != null && fingerTable[next].isUp()) {\r
 315                         next++;\r
 316                         return;\r
 317                 }\r
 318                 BigInteger base;\r
 319                 if (next == 0)\r
 320                         base = BigInteger.ONE;\r
 321                 else {\r
 322                         base = BigInteger.valueOf(2);\r
 323                         for (int exp = 1; exp < next; exp++) {\r
 324                                 base = base.multiply(BigInteger.valueOf(2));\r
 325                         }\r
 326                 }\r
 327                 BigInteger pot = this.chordId.add(base);\r
 328                 BigInteger idFirst = ((ChordProtocol) Network.get(0).getProtocol(p.pid)).chordId;\r
 329                 BigInteger idLast = ((ChordProtocol) Network.get(Network.size() - 1)\r
 330                                 .getProtocol(p.pid)).chordId;\r
 331                 if (pot.compareTo(idLast) == 1) {\r
 332                         pot = (pot.mod(idLast));\r
 333                         if (pot.compareTo(this.chordId) != -1) {\r
 334                                 next++;\r
 335                                 return;\r
 336                         }\r
 337                         if (pot.compareTo(idFirst) == -1) {\r
 338                                 this.fingerTable[next] = Network.get(Network.size() - 1);\r
 339                                 next++;\r
 340                                 return;\r
 341                         }\r
 342                 }\r
 343                 do {\r
 344                         fingerTable[next] = ((ChordProtocol) successorList[0]\r
 345                                         .getProtocol(p.pid)).find_successor(pot);\r
 346                         pot = pot.subtract(BigInteger.ONE);\r
 347                         ((ChordProtocol) successorList[0].getProtocol(p.pid)).fixFingers();\r
 348                 } while (fingerTable[next] == null || fingerTable[next].isUp() == false);\r
 349                 next++;\r
 350         }\r
 351 \r
 352         /**\r
 353          */\r
 354         public void emptyLookupMessage() {\r
 355                 index = 0;\r
 356                 this.lookupMessage = new int[0];\r
 357         }\r
 358 }\r