contrib/psg/src/example/bittorrent/BitTorrent.java

   1 /*
   2  * Copyright (c) 2007-2008 Fabrizio Frioli, Michele Pedrolli
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU Lesser General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Lesser General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Lesser General Public License
  14  * along with this program; if not, write to the Free Software
  15  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16  *
  17  * --
  18  *
  19  * Please send your questions/suggestions to:
  20  * {fabrizio.frioli, michele.pedrolli} at studenti dot unitn dot it
  21  *
  22  */
  23
  24 package example.bittorrent;
  25
  26 import peersim.core.*;
  27 import peersim.config.*;
  28 import peersim.edsim.*;
  29 import peersim.transport.*;
  30
  31 /**
  32  *      This is the class that implements the BitTorrent module for Peersim
  33  */
  34 public class BitTorrent implements EDProtocol {
  35         /**
  36          *      The size in Megabytes of the file being shared.
  37          *      @config
  38          */
  39         private static final String PAR_SIZE="file_size";
  40         /**
  41          *      The Transport used by the the protocol.
  42          *      @config
  43          */
  44         private static final String PAR_TRANSPORT="transport";
  45         /**
  46          *      The maximum number of neighbor that a node can have.
  47          *      @config
  48          */
  49         private static final String PAR_SWARM="max_swarm_size";
  50         /**
  51          *      The maximum number of peers returned by the tracker when a new
  52          *      set of peers is requested through a <tt>TRACKER</tt> message.
  53          *      @config
  54          */
  55         private static final String PAR_PEERSET_SIZE="peerset_size";
  56         /**
  57          *      Defines how much the network can grow with respect to the <tt>network.size</tt>
  58          *  when {@link NetworkDynamics} is used.
  59          *      @config
  60          */
  61         private static final String PAR_MAX_GROWTH="max_growth";
  62         /**
  63          *      Is the number of requests of the same block sent to different peers.
  64          *      @config
  65          */
  66         private static final String PAR_DUP_REQ = "duplicated_requests";
  67
  68         /**
  69          *      KEEP_ALIVE message.
  70          *      @see SimpleEvent#type "Event types"
  71          */
  72         private static final int KEEP_ALIVE = 1;
  73
  74         /**
  75          *      CHOKE message.
  76          *      @see SimpleEvent#type "Event types"
  77          */
  78         private static final int CHOKE = 2;
  79
  80         /**
  81          *      UNCHOKE message.
  82          *      @see SimpleEvent#type "Event types"
  83          */
  84         private static final int UNCHOKE = 3;
  85
  86         /**
  87          *      INTERESTED message.
  88          *      @see SimpleEvent#type "Event types"
  89          */
  90         private static final int INTERESTED = 4;
  91
  92         /**
  93          *      NOT_INTERESTED message.
  94          *      @see SimpleEvent#type "Event types"
  95          */
  96         private static final int NOT_INTERESTED = 5;
  97
  98         /**
  99          *      HAVE message.
 100          *      @see SimpleEvent#type "Event types"
 101          */
 102         private static final int HAVE = 6;
 103
 104         /**
 105          *      BITFIELD message.
 106          *      @see SimpleEvent#type "Event types"
 107          */
 108         private static final int BITFIELD = 7;
 109
 110         /**
 111          *      REQUEST message.
 112          *      @see SimpleEvent#type "Event types"
 113          */
 114         private static final int REQUEST = 8;
 115
 116         /**
 117          *      PIECE message.
 118          *      @see SimpleEvent#type "Event types"
 119          */
 120         private static final int PIECE = 9;
 121
 122         /**
 123          *      CANCEL message.
 124          *      @see SimpleEvent#type "Event types"
 125          */
 126         private static final int CANCEL = 10;
 127
 128         /**
 129          *      TRACKER message.
 130          *      @see SimpleEvent#type "Event types"
 131          */
 132         private static final int TRACKER = 11;
 133
 134         /**
 135          *      PEERSET message.
 136          *      @see SimpleEvent#type "Event types"
 137          */
 138         private static final int PEERSET = 12;
 139
 140         /**
 141          *      CHOKE_TIME event.
 142          *      @see SimpleEvent#type "Event types"
 143          */
 144         private static final int CHOKE_TIME = 13;
 145
 146         /**
 147          *      OPTUNCHK_TIME event.
 148          *      @see SimpleEvent#type "Event types"
 149          */
 150         private static final int OPTUNCHK_TIME = 14;
 151
 152         /**
 153          *      ANTISNUB_TIME event.
 154          *      @see SimpleEvent#type "Event types"
 155          */
 156         private static final int ANTISNUB_TIME = 15;
 157
 158         /**
 159          *      CHECKALIVE_TIME event.
 160          *      @see SimpleEvent#type "Event types"
 161          */
 162         private static final int CHECKALIVE_TIME = 16;
 163
 164         /**
 165          *      TRACKERALIVE_TIME event.
 166          *      @see SimpleEvent#type "Event types"
 167          */
 168         private static final int TRACKERALIVE_TIME = 17;
 169
 170         /**
 171          *      DOWNLOAD_COMPLETED event.
 172          *      @see SimpleEvent#type "Event types"
 173          */
 174         private static final int DOWNLOAD_COMPLETED = 18;
 175
 176         /**
 177          *      The maxium connection speed of the local node.
 178          */
 179         int maxBandwidth;
 180
 181         /**
 182          *      Stores the neighbors ordered by ID.
 183          *  @see Element
 184          */
 185         private example.bittorrent.Element byPeer[];
 186
 187         /**
 188          *      Contains the neighbors ordered by bandwidth as needed by the unchocking
 189          *      algorithm.
 190          */
 191         private example.bittorrent.Element byBandwidth[];
 192
 193         /**
 194          *      The Neighbors list.
 195          */
 196         private Neighbor cache[];
 197
 198         /**
 199          *      Reference to the neighbors that unchocked the local node.
 200          */
 201         private boolean unchokedBy[];
 202
 203         /**
 204          *      Number of neighbors in the cache. When it decreases under 20, a new peerset
 205          *      is requested to the tracker.
 206          */
 207         private int nNodes = 0;
 208
 209         /**
 210          *      Maximum number of nodes in the network.
 211          */
 212         private int nMaxNodes;
 213
 214         /**
 215          *      The status of the local peer. 0 means that the current peer is a leecher, 1 a seeder.
 216          */
 217         private int peerStatus;
 218
 219         /**
 220          *      Defines how much the network can grow with respect to the <tt>network.size</tt>
 221          *  when {@link NetworkDynamics} is used.
 222          */
 223         public int maxGrowth;
 224
 225         /**
 226          *      File status of the local node. Contains the blocks owned by the local node.
 227          */
 228         private int status[];
 229
 230         /**
 231          *      Current number of Bitfield request sent. It must be taken into account
 232          *      before sending another one.
 233          */
 234         private int nBitfieldSent = 0;
 235
 236         /**
 237          *      Current number of pieces in upload from the local peer.
 238          */
 239         public int nPiecesUp = 0;
 240         /**
 241          *      Current number of pieces in download to the local peer.
 242          */
 243         public int nPiecesDown = 0;
 244
 245         /**
 246          *      Current number of piece completed.
 247          */
 248         private int nPieceCompleted = 0;
 249
 250         /**
 251          *      Current downloading piece ID, the previous lastInterested piece.
 252          */
 253         int currentPiece = -1;
 254
 255         /**
 256          *      Used to compute the average download rates in choking algorithm. Stores the
 257          *      number of <tt>CHOKE</tt> events.
 258          */
 259         int n_choke_time = 0;
 260
 261         /**
 262          *      Used to send the <tt>TRACKER</tt> message when the local node has 20 neighbors
 263          *      for the first time.
 264          */
 265         boolean lock = false;
 266
 267         /**
 268          *      Number of peers interested to my pieces.
 269          */
 270         int numInterestedPeers = 0;
 271
 272         /**
 273          *      Last piece for which the local node sent an <tt>INTERESTED</tt> message.
 274          */
 275         int lastInterested = -1;
 276
 277         /**
 278          *      The status of the current piece in download. Length 16, every time the local node
 279          *      receives a PIECE message, it updates the corrisponding block's cell. The cell
 280          *      contains the ID for that block of that piece. If an already owned
 281          *      block is received this is discarded.
 282          */
 283         private int pieceStatus[];
 284
 285         /**
 286          *      Length of the file. Stored as number of pieces (256KB each one).
 287          */
 288         int nPieces;
 289
 290         /**
 291          *      Contains the neighbors's status of the file. Every row represents a
 292          *      node and every a cell has value O if the neighbor doesn't
 293          *      have the piece, 1 otherwise. It has {@link #swarmSize} rows and {@link #nPieces}
 294          *      columns.
 295          */
 296         int [][]swarm;
 297
 298         /**
 299          *      The summation of the swarm's rows. Calculated every time a {@link #BITFIELD} message
 300          *      is received and updated every time HAVE message is received.
 301          */
 302         int rarestPieceSet[];
 303
 304         /**
 305          *      The five pending block requests.
 306          */
 307         int pendingRequest[];
 308
 309         /**
 310          *      The maximum swarm size (default is 80)
 311          */
 312         int swarmSize;
 313
 314         /**
 315          *      The size of the peerset. This is the number of "friends" nodes
 316          *      sent from the tracker to each new node (default: 50)
 317          */
 318         int peersetSize;
 319
 320         /**
 321          * The ID of the current node
 322          */
 323         private long thisNodeID;
 324
 325         /**
 326      *  Number of duplicated requests as specified in the configuration file.
 327          *      @see BitTorrent#PAR_DUP_REQ
 328          */
 329         private int numberOfDuplicatedRequests;
 330
 331         /**
 332          *      The queue where the requests to serve are stored.
 333          *      The default dimension of the queue is 20.
 334          */
 335         Queue requestToServe = null;
 336
 337         /**
 338          *      The queue where the out of sequence incoming pieces are stored
 339          *      waiting for the right moment to be processed.
 340      *  The default dimension of the queue is 100.
 341          */
 342         Queue incomingPieces = null;
 343
 344         /**
 345          *      The Transport ID.
 346          *      @see BitTorrent#PAR_TRANSPORT
 347          */
 348         int tid;
 349
 350         /**
 351          *      The reference to the tracker node. If equals to <tt>null</tt>, the local
 352          *      node is the tracker.
 353          */
 354         private Node tracker = null;
 355
 356         /**
 357          *      The default constructor. Reads the configuration file and initializes the
 358          *      configuration parameters.
 359          *      @param prefix the component prefix declared in the configuration file
 360          */
 361         public BitTorrent(String prefix){ // Used for the tracker's protocol
 362                 tid = Configuration.getPid(prefix+"."+PAR_TRANSPORT);
 363                 nPieces = (int)((Configuration.getInt(prefix+"."+PAR_SIZE))*1000000/256000);
 364                 swarmSize = (int)Configuration.getInt(prefix+"."+PAR_SWARM);
 365                 peersetSize = (int)Configuration.getInt(prefix+"."+PAR_PEERSET_SIZE);
 366                 numberOfDuplicatedRequests = (int)Configuration.getInt(prefix+"."+PAR_DUP_REQ);
 367                 maxGrowth = (int)Configuration.getInt(prefix+"."+PAR_MAX_GROWTH);
 368                 nMaxNodes = Network.getCapacity()-1;
 369         }
 370
 371         /**
 372          *      Gets the reference to the tracker node.
 373          *      @return the reference to the tracker
 374          */
 375         public Node getTracker(){
 376                 return tracker;
 377         }
 378
 379         /**
 380          *      Gets the number of neighbors currently stored in the cache of the local node.
 381          *      @return the number of neighbors in the cache
 382          */
 383         public int getNNodes(){
 384                 return this.nNodes;
 385         }
 386
 387         /**
 388          *      Sets the reference to the tracker node.
 389          *      @param t the tracker node
 390          */
 391         public void setTracker(Node t){
 392                 tracker = t;
 393         }
 394
 395         /**
 396          *      Sets the ID of the local node.
 397          *      @param id the ID of the node
 398          */
 399         public void setThisNodeID(long id) {
 400                 this.thisNodeID = id;
 401         }
 402
 403         /**
 404          *      Gets the ID of the local node.
 405          *      @return the ID of the local node
 406          */
 407         public long getThisNodeID(){
 408                 return this.thisNodeID;
 409         }
 410
 411         /**
 412          *      Gets the file status of the local node.
 413          *      @return the file status of the local node
 414          */
 415         public int[] getFileStatus(){
 416                 return this.status;
 417         }
 418
 419         /**
 420          *      Initializes the tracker node. This method
 421          *      only performs the initialization of the tracker's cache.
 422          */
 423         public void initializeTracker() {
 424                 cache = new Neighbor[nMaxNodes+maxGrowth];
 425                 for(int i=0; i<nMaxNodes+maxGrowth; i++){
 426                         cache[i]= new Neighbor();
 427                 }
 428         }
 429
 430         /**
 431          *      <p>Checks the number of neighbors and if it is equal to 20
 432          *      sends a TRACKER messages to the tracker, asking for a new
 433          *      peer set.</p>
 434          *
 435          *      <p>This method *must* be called after every call of {@link #removeNeighbor}
 436          *      in {@link #processEvent}.
 437          *      </p>
 438          */
 439         private void processNeighborListSize(Node node, int pid) {
 440                 if (nNodes==20) {
 441                         Object ev;
 442                         long latency;
 443                         ev = new SimpleMsg(TRACKER, node);
 444                         Node tracker = ((BitTorrent)node.getProtocol(pid)).tracker;
 445                         if(tracker != null){
 446 //                              latency = ((Transport)node.getProtocol(tid)).getLatency(node, tracker);
 447 //                              EDSimulator.add(latency,ev,tracker,pid);
 448                                 ((Transport) node.getProtocol(tid)).send(node, tracker, ev, pid);
 449                         }
 450                 }
 451         }
 452
 453         /**
 454          *      The standard method that processes incoming events.
 455          *      @param node reference to the local node for which the event is going to be processed
 456          *      @param pid BitTorrent's protocol id
 457          *      @param event the event to process
 458          */
 459         public void processEvent(Node node, int pid, Object event){
 460
 461                 Object ev;
 462                 long latency;
 463                 switch(((SimpleEvent)event).getType()){
 464
 465                         case KEEP_ALIVE: // 1
 466                         {
 467                                 Node sender = ((IntMsg)event).getSender();
 468                                 int isResponse = ((IntMsg)event).getInt();
 469                                 //System.out.println("process, keep_alive: sender is "+sender.getID()+", local is "+node.getID());
 470                                 Element e = search(sender.getID());
 471                                 if(e!= null){ //if I know the sender
 472                                         cache[e.peer].isAlive();
 473                                         if(isResponse==0 && alive(sender)){
 474                                                 Object msg = new IntMsg(KEEP_ALIVE,node,1,0);
 475 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node, sender);
 476 //                                              EDSimulator.add(latency,msg,sender,pid);
 477                                                 ((Transport) node.getProtocol(tid)).send(node, sender, msg, pid);
 478                                                 cache[e.peer].justSent();
 479                                         }
 480                                 }
 481                                 else{
 482                                         System.err.println("despite it should never happen, it happened");
 483                                         ev = new BitfieldMsg(BITFIELD, true, false, node, status, nPieces);
 484 //                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 485 //                                      EDSimulator.add(latency,ev,sender,pid);
 486                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 487                                         nBitfieldSent++;
 488                                 }
 489
 490                         };break;
 491
 492                         case CHOKE: // 2, CHOKE message.
 493                         {
 494                                 Node sender = ((SimpleMsg)event).getSender();
 495                                 //System.out.println("process, choke: sender is "+sender.getID()+", local is "+node.getID());
 496                                 Element e = search(sender.getID());
 497                                 if(e!= null){ //if I know the sender
 498                                         cache[e.peer].isAlive();
 499                                         unchokedBy[e.peer]= false; // I'm choked by it
 500                                 }
 501                                 else{
 502                                         System.err.println("despite it should never happen, it happened");
 503                                         ev = new BitfieldMsg(BITFIELD, true, false, node, status, nPieces);
 504 //                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 505 //                                      EDSimulator.add(latency,ev,sender,pid);
 506                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 507                                         nBitfieldSent++;
 508                                 }
 509                         };break;
 510
 511                         case UNCHOKE: // 3, UNCHOKE message.
 512                         {
 513                                 Node sender = ((SimpleMsg)event).getSender();
 514                                 //System.out.println("process, unchoke: sender is "+sender.getID()+", local is "+node.getID());
 515                                 Element e = search(sender.getID());
 516                                 if(e != null){ // If I know the sender
 517                                         int senderIndex = e.peer;
 518                                         cache[senderIndex].isAlive();
 519                                         /* I send to it some of the pending requests not yet satisfied. */
 520                                         int t = numberOfDuplicatedRequests;
 521                                         for(int i=4;i>=0 && t>0;i--){
 522                                                 if(pendingRequest[i]==-1)
 523                                                         break;
 524                                                 if(alive(cache[senderIndex].node) && swarm[senderIndex][decode(pendingRequest[i],0)]==1){ //If the sender has that piece
 525                                                         ev = new IntMsg(REQUEST, node,pendingRequest[i],0);
 526 //                                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 527 //                                                      EDSimulator.add(latency,ev, sender,pid);
 528                                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 529                                                         cache[senderIndex].justSent();
 530                                                 }
 531                                                 if(!alive(cache[senderIndex].node)){
 532                                                         System.out.println("unchoke1 rm neigh "+ cache[i].node.getID() );
 533                                                         removeNeighbor(cache[senderIndex].node);
 534                                                         processNeighborListSize(node,pid);
 535                                                         return;
 536                                                 }
 537                                                 t--;
 538                                         }
 539                                         // I request missing blocks to fill the queue
 540                                         int block = getBlock();
 541                                         int piece;
 542                                         while(block != -2){ //while still available request to send
 543                                                 if(block < 0){ // No more block to request for the current piece
 544                                                         piece = getPiece();
 545                                                         if(piece == -1){ // no more piece to request
 546                                                                 break;
 547                                                         }
 548                                                         for(int j=0; j<swarmSize; j++){// send the interested message to those
 549                                                                                                         // nodes which have that piece
 550                                                                 lastInterested = piece;
 551                                                                 if(alive(cache[j].node) && swarm[j][piece]==1){
 552                                                                         ev = new IntMsg(INTERESTED, node, lastInterested,0);
 553 //                                                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[j].node);
 554 //                                                                      EDSimulator.add(latency,ev,cache[j].node,pid);
 555                                                                         ((Transport) node.getProtocol(tid)).send(node, cache[j].node, ev, pid);
 556                                                                         cache[j].justSent();
 557                                                                 }
 558
 559                                                                 if(!alive(cache[j].node)){
 560                                                                         //System.out.println("unchoke2 rm neigh "+ cache[j].node.getID() );
 561                                                                         removeNeighbor(cache[j].node);
 562                                                                         processNeighborListSize(node,pid);
 563                                                                 }
 564                                                         }
 565                                                         block = getBlock();
 566                                                 }
 567                                                 else{ // block value referred to a real block
 568                                                         if(alive(cache[senderIndex].node) && swarm[senderIndex][decode(block,0)]==1 && addRequest(block)){ // The sender has that block
 569                                                                 ev = new IntMsg(REQUEST, node, block,0);
 570 //                                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 571 //                                                              EDSimulator.add(latency,ev,sender,pid);
 572                                                                 ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 573
 574                                                                 cache[senderIndex].justSent();
 575                                                         }
 576                                                         else{
 577                                                                 if(!alive(cache[senderIndex].node)){
 578                                                                         System.out.println("unchoke3 rm neigh "+ cache[senderIndex].node.getID() );
 579                                                                         removeNeighbor(cache[senderIndex].node);
 580                                                                         processNeighborListSize(node,pid);
 581                                                                 }
 582                                                                 return;
 583                                                         }
 584                                                         block = getBlock();
 585                                                 }
 586                                         }
 587                                         unchokedBy[senderIndex] = true; // I add the sender to the list
 588                                 }
 589                                 else // It should never happen.
 590                                 {
 591                                         System.err.println("despite it should never happen, it happened");
 592                                         for(int i=0; i<swarmSize; i++)
 593                                                 if(cache[i].node !=null)
 594                                                         System.err.println(cache[i].node.getID());
 595                                         ev = new BitfieldMsg(BITFIELD, true, false, node, status, nPieces);
 596 //                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 597 //                                      EDSimulator.add(latency,ev,sender,pid);
 598                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 599                                         nBitfieldSent++;
 600                                 }
 601                         };break;
 602
 603                         case INTERESTED: // 4, INTERESTED message.
 604                         {
 605                                 numInterestedPeers++;
 606                                 Node sender = ((IntMsg)event).getSender();
 607                                 //System.out.println("process, interested: sender is "+sender.getID()+", local is "+node.getID());
 608                                 int value = ((IntMsg)event).getInt();
 609                                 Element e = search(sender.getID());
 610                                 if(e!=null){
 611                                         cache[e.peer].isAlive();
 612                                         cache[e.peer].interested = value;
 613                                 }
 614                                 else{
 615                                         System.err.println("despite it should never happen, it happened");
 616                                         ev = new BitfieldMsg(BITFIELD, true, false, node, status, nPieces);
 617 //                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 618 //                                      EDSimulator.add(latency,ev,sender,pid);
 619                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 620                                         nBitfieldSent++;
 621                                 }
 622
 623                         }; break;
 624
 625                         case NOT_INTERESTED: // 5, NOT_INTERESTED message.
 626                         {
 627                                 numInterestedPeers--;
 628                                 Node sender = ((IntMsg)event).getSender();
 629                                 //System.out.println("process, not_interested: sender is "+sender.getID()+", local is "+node.getID());
 630                                 int value = ((IntMsg)event).getInt();
 631                                 Element e = search(sender.getID());
 632                                 if(e!=null){
 633                                         cache[e.peer].isAlive();
 634                                         if(cache[e.peer].interested == value)
 635                                                 cache[e.peer].interested = -1; // not interested
 636                                 }
 637                         }; break;
 638
 639                         case HAVE: // 6, HAVE message.
 640                         {
 641                                 Node sender = ((IntMsg)event).getSender();
 642                                 //System.out.println("process, have: sender is "+sender.getID()+", local is "+node.getID());
 643                                 int piece = ((IntMsg)event).getInt();
 644                                 Element e = search(sender.getID());
 645                                 if(e!=null){
 646                                         cache[e.peer].isAlive();
 647                                         swarm[e.peer][piece]=1;
 648                                         rarestPieceSet[piece]++;
 649                                         boolean isSeeder = true;
 650                                         for(int i=0; i<nPieces; i++){
 651                                                 isSeeder = isSeeder && (swarm[e.peer][i]==1);
 652                                         }
 653                                         e.isSeeder = isSeeder;
 654                                 }
 655                                 else{
 656                                         System.err.println("despite it should never happen, it happened");
 657                                         ev = new BitfieldMsg(BITFIELD, true, false, node, status, nPieces);
 658 //                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 659 //                                      EDSimulator.add(latency,ev,sender,pid);
 660                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 661                                         nBitfieldSent++;
 662                                 }
 663                         }; break;
 664
 665                         case BITFIELD: // 7, BITFIELD message
 666                         {
 667                                 Node sender = ((BitfieldMsg)event).getSender();
 668                                 int []fileStatus = ((BitfieldMsg)event).getArray();
 669                                 /*Response with NACK*/
 670                                 if(!((BitfieldMsg)event).isRequest && !((BitfieldMsg)event).ack){
 671                                         Element e = search(sender.getID());
 672                                         if(e == null) // if is a response with nack that follows a request
 673                                                 nBitfieldSent--;
 674                                         // otherwise is a response with ack that follows a duplicate
 675                                         // insertion attempt
 676                                         //System.out.println("process, bitfield_resp_nack: sender is "+sender.getID()+", local is "+node.getID());
 677                                         return;
 678                                 }
 679                                 /*Request with NACK*/
 680                                 if(((BitfieldMsg)event).isRequest && !((BitfieldMsg)event).ack){
 681                                         //System.out.println("process, bitfield_req_nack: sender is "+sender.getID()+", local is "+node.getID());
 682                                         if(alive(sender)){
 683                                                 Element e = search(sender.getID());
 684                                                 ev = new BitfieldMsg(BITFIELD, false, true, node, status, nPieces); //response with ack
 685 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 686 //                                              EDSimulator.add(latency,ev,sender,pid);
 687                                                 ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 688                                                 cache[e.peer].justSent();
 689                                         }
 690                                 }
 691                                 /*Response with ACK*/
 692                                 if(!((BitfieldMsg)event).isRequest && ((BitfieldMsg)event).ack){
 693                                         nBitfieldSent--;
 694                                         //System.out.println("process, bitfield_resp_ack: sender is "+sender.getID()+", local is "+node.getID());
 695                                         if(alive(sender)){
 696                                                 if(addNeighbor(sender)){
 697                                                         Element e = search(sender.getID());
 698                                                         cache[e.peer].isAlive();
 699                                                         swarm[e.peer] = fileStatus;
 700                                                         boolean isSeeder = true;
 701                                                         for(int i=0; i<nPieces; i++){
 702                                                                 rarestPieceSet[i]+= fileStatus[i];
 703                                                                 isSeeder = isSeeder && (fileStatus[i]==1);
 704                                                         }
 705                                                         e.isSeeder = isSeeder;
 706
 707                                                         if(nNodes==10 && !lock){ // I begin to request pieces
 708                                                                 lock = true;
 709                                                                 int piece = getPiece();
 710                                                                 if(piece == -1)
 711                                                                         return;
 712                                                                 lastInterested = piece;
 713                                                                 currentPiece = lastInterested;
 714                                                                 ev = new IntMsg(INTERESTED, node, lastInterested,0);
 715                                                                 for(int i=0; i<swarmSize; i++){// send the interested message to those
 716                                                                                                                 // nodes which have that piece
 717                                                                         if(alive(cache[i].node) && swarm[i][piece]==1){
 718 //                                                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[i].node);
 719 //                                                                              EDSimulator.add(latency,ev,cache[i].node,pid);
 720                                                                                 ((Transport) node.getProtocol(tid)).send(node, cache[i].node, ev, pid);
 721                                                                                 cache[i].justSent();
 722                                                                         }
 723                                                                 }
 724
 725                                                         }
 726
 727                                                 }
 728                                         }
 729                                         else
 730                                                 System.out.println("Sender "+sender.getID()+" not alive");
 731                                 }
 732                                 /*Request with ACK*/
 733                                 if(((BitfieldMsg)event).isRequest && ((BitfieldMsg)event).ack){
 734                                         //System.out.println("process, bitfield_req_ack: sender is "+sender.getID()+", local is "+node.getID());
 735                                         if(alive(sender)){
 736                                                 if(addNeighbor(sender)){
 737                                                         Element e = search(sender.getID());
 738                                                         cache[e.peer].isAlive();
 739                                                         swarm[e.peer] = fileStatus;
 740                                                         boolean isSeeder = true;
 741                                                         for(int i=0; i<nPieces; i++){
 742                                                                 rarestPieceSet[i]+= fileStatus[i]; // I update the rarestPieceSet with the pieces of the new node
 743                                                                 isSeeder = isSeeder && (fileStatus[i]==1); // I check if the new node is a seeder
 744                                                         }
 745                                                         e.isSeeder = isSeeder;
 746                                                         ev = new BitfieldMsg(BITFIELD, false, true, node, status, nPieces); //response with ack
 747 //                                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 748 //                                                      EDSimulator.add(latency,ev,sender,pid);
 749                                                         ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 750                                                         cache[e.peer].justSent();
 751                                                         if(nNodes==10 && !lock){ // I begin to request pieces
 752                                                                 int piece = getPiece();
 753                                                                 if(piece == -1)
 754                                                                         return;
 755                                                                 lastInterested = piece;
 756                                                                 currentPiece = lastInterested;
 757                                                                 ev = new IntMsg(INTERESTED, node, lastInterested,0);
 758                                                                 for(int i=0; i<swarmSize; i++){// send the interested message to those
 759                                                                                                                 // nodes which have that piece
 760                                                                         if(alive(cache[i].node) && swarm[i][piece]==1){
 761 //                                                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[i].node);
 762 //                                                                              EDSimulator.add(latency,ev,cache[i].node,pid);
 763                                                                                 ((Transport) node.getProtocol(tid)).send(node, cache[i].node, ev, pid);
 764                                                                                 cache[i].justSent();
 765                                                                         }
 766                                                                 }
 767
 768                                                         }
 769                                                 }
 770                                                 else {
 771                                                         Element e;
 772                                                         if((e = search(sender.getID()))!=null){ // The sender was already in the cache
 773                                                                 cache[e.peer].isAlive();
 774                                                                 ev = new BitfieldMsg(BITFIELD, false, true, node, status, nPieces); //response with ack
 775 //                                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 776 //                                                              EDSimulator.add(latency,ev,sender,pid);
 777                                                                 ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 778                                                                 cache[e.peer].justSent();
 779                                                         }
 780                                                         else{ // Was not be possible add the sender (nBitfield+nNodes > swarmSize)
 781                                                                 ev = new BitfieldMsg(BITFIELD, false, false, node, status, nPieces); //response with nack
 782 //                                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,sender);
 783 //                                                              EDSimulator.add(latency,ev,sender,pid);
 784                                                                 ((Transport) node.getProtocol(tid)).send(node, sender, ev, pid);
 785                                                         }
 786                                                 }
 787
 788                                         }
 789                                         else
 790                                                 System.out.println("Sender "+sender.getID()+" not alive");
 791                                 }
 792                         };break;
 793
 794                         case REQUEST: // 8, REQUEST message.
 795                         {
 796                                 Object evnt;
 797                                 Node sender = ((IntMsg)event).getSender();
 798                                 int value = ((IntMsg)event).getInt();
 799                                 Element e;
 800                                 BitTorrent senderP;
 801                                 int remoteRate;
 802                                 int localRate;
 803                                 int bandwidth;
 804                                 int downloadTime;
 805
 806                                 e = search(sender.getID());
 807                                 if (e==null)
 808                                         return;
 809                                 cache[e.peer].isAlive();
 810
 811                                 requestToServe.enqueue(value, sender);
 812
 813                                 /*I serve the enqueued requests until 10 uploding pieces or an empty queue*/
 814                                 while(!requestToServe.empty() && nPiecesUp <10){
 815                                         Request req = requestToServe.dequeue();
 816                                         e = search(req.sender.getID());
 817                                         if(e!=null && alive(req.sender)){
 818 //                                              ev = new IntMsg(PIECE, node, req.id);
 819                                                 nPiecesUp++;
 820                                                 e.valueUP++;
 821                                                 senderP = ((BitTorrent)req.sender.getProtocol(pid));
 822                                                 senderP.nPiecesDown++;
 823                                                 remoteRate = senderP.maxBandwidth/(senderP.nPiecesUp + senderP.nPiecesDown);
 824                                                 localRate = maxBandwidth/(nPiecesUp + nPiecesDown);
 825                                                 bandwidth = Math.min(remoteRate, localRate);
 826                                                 downloadTime = ((16*8)/(bandwidth))*1000; // in milliseconds
 827
 828                                                 ev = new IntMsg(PIECE, node, req.id, 16*8 * 1024);
 829                                                 ((Transport) node.getProtocol(tid)).send(node, req.sender, ev, pid);
 830
 831 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,req.sender);
 832 //                                              EDSimulator.add(latency+downloadTime,ev,req.sender,pid);
 833                                                 cache[e.peer].justSent();
 834
 835                                                 /*I send to me an event to indicate that the download is completed.
 836                                                 This prevent that, when the receiver death occurres, my value nPiecesUp
 837                                                 doesn't decrease.*/
 838                                                 evnt = new SimpleMsg(DOWNLOAD_COMPLETED, req.sender);
 839 //                                              EDSimulator.add(latency+downloadTime,evnt,node,pid);
 840                                                 ((Transport) node.getProtocol(tid)).send(node, node, evnt, pid);
 841                                         }
 842                                 }
 843                         }; break;
 844
 845                         case PIECE: // 9, PIECE message.
 846                         {
 847                                 Node sender = ((IntMsg)event).getSender();
 848                                 /*      Set the correct value for the local uploading and remote
 849                                 downloading number of pieces */
 850                                 nPiecesDown--;
 851
 852                                 if(peerStatus == 1)// To save CPU cycles
 853                                         return;
 854                                 //System.out.println("process, piece: sender is "+sender.getID()+", local is "+node.getID());
 855                                 Element e = search(sender.getID());
 856
 857                                 if(e==null){ //I can't accept a piece not wait
 858                                         return;
 859                                 }
 860                                 e.valueDOWN++;
 861
 862                                 cache[e.peer].isAlive();
 863
 864                                 int value = ((IntMsg)event).getInt();
 865                                 int piece = decode(value,0);
 866                                 int block = decode(value,1);
 867                                 /* If the block has not been already downloaded and it belongs to
 868                                         the current downloading piece.*/
 869                                 if(piece == currentPiece && decode(pieceStatus[block],0)!= piece){
 870                                         pieceStatus[block] = value;
 871                                         status[piece]++;
 872                                         removeRequest(value);
 873                                         requestNextBlocks(node, pid, e.peer);
 874
 875                                 }else{ // Either a future piece or an owned piece
 876                                         if(piece!=currentPiece && status[piece]!=16){ // Piece not owned, will be considered later
 877                                                 incomingPieces.enqueue(value, sender);
 878                                         }
 879
 880                                 }
 881                                 ev = new IntMsg(CANCEL, node, value,0);
 882                                 /* I send a CANCEL to all nodes to which I previously requested the block*/
 883                                 for(int i=0; i<swarmSize; i++){
 884                                         if(alive(cache[i].node) && unchokedBy[i]==true && swarm[i][decode(block,0)]==1 && cache[i].node != sender){
 885 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[i].node);
 886 //                                              EDSimulator.add(latency,ev,cache[i].node,pid);
 887                                                 ((Transport) node.getProtocol(tid)).send(node, cache[i].node, ev, pid);
 888                                                 cache[i].justSent();
 889                                         }
 890                                 }
 891
 892                                 if(status[currentPiece]==16){ // if piece completed, I change the currentPiece to the next wanted
 893                                         nPieceCompleted++;
 894                                         ev = new IntMsg(HAVE, node, currentPiece,0);
 895                                         for(int i=0; i<swarmSize; i++){ // I send the HAVE for the piece
 896                                                 if(alive(cache[i].node)){
 897 //                                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[i].node);
 898 //                                                      EDSimulator.add(latency,ev,cache[i].node,pid);
 899                                                         ((Transport) node.getProtocol(tid)).send(node, cache[i].node, ev, pid);
 900                                                         cache[i].justSent();
 901                                                 }
 902                                                 if(!alive(cache[i].node)){
 903                                                         //System.out.println("piece3 rm neigh "+ cache[i].node.getID() );
 904                                                         removeNeighbor(cache[i].node);
 905                                                         processNeighborListSize(node,pid);
 906                                                 }
 907                                         }
 908                                         ev = new IntMsg(NOT_INTERESTED, node, currentPiece,0);
 909                                         for(int i=0; i<swarmSize; i++){ // I send the NOT_INTERESTED to which peer I sent an INTERESTED
 910                                                 if(swarm[i][piece]==1 && alive(cache[i].node)){
 911 //                                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[i].node);
 912 //                                                      EDSimulator.add(latency,ev,cache[i].node,pid);
 913                                                         ((Transport) node.getProtocol(tid)).send(node, cache[i].node, ev, pid);
 914                                                         cache[i].justSent();
 915                                                 }
 916                                                 if(!alive(cache[i].node)){
 917                                                         //System.out.println("piece4 rm neigh "+ cache[i].node.getID() );
 918                                                         removeNeighbor(cache[i].node);
 919                                                         processNeighborListSize(node,pid);
 920                                                 }
 921                                         }
 922                                         if(nPieceCompleted == nPieces){
 923                                                 System.out.println("FILE COMPLETED for peer "+node.getID());
 924                                                 this.peerStatus = 1;
 925                                         }
 926
 927                                         /*      I set the currentPiece to the lastInterested. Then I extract
 928                                                 the queued received blocks
 929                                                 */
 930
 931                                         currentPiece = lastInterested;
 932                                         int m = incomingPieces.dim;
 933                                         while(m > 0){ // I process the queue
 934                                                 m--;
 935                                                 Request temp = incomingPieces.dequeue();
 936                                                 int p = decode(temp.id,0); // piece id
 937                                                 int b = decode(temp.id,1); // block id
 938                                                 Element s = search(temp.sender.getID());
 939                                                 if(s==null) // if the node that sent the block in the queue is dead
 940                                                         continue;
 941                                                 if(p==currentPiece && decode(pieceStatus[b],0)!= p){
 942                                                         pieceStatus[b] = temp.id;
 943                                                         status[p]++;
 944                                                         removeRequest(temp.id);
 945                                                         requestNextBlocks(node, pid, s.peer);
 946                                                 }
 947                                                 else{ // The piece not currently desired will be moved to the tail
 948                                                         if(p!= currentPiece) // If not a duplicate block but belongs to another piece
 949                                                                 incomingPieces.enqueue(temp.id,temp.sender);
 950                                                         else // duplicate block
 951                                                                 requestNextBlocks(node, pid, s.peer);
 952                                                 }
 953                                         }
 954                                 }
 955                         }; break;
 956
 957                         case CANCEL:
 958                         {
 959                                 Node sender = ((IntMsg)event).getSender();
 960                                 int value = ((IntMsg)event).getInt();
 961                                 requestToServe.remove(sender, value);
 962                         };break;
 963
 964                         case PEERSET: // PEERSET message
 965                         {
 966                                 Node sender = ((PeerSetMsg)event).getSender();
 967                                 //System.out.println("process, peerset: sender is "+sender.getID()+", local is "+node.getID());
 968                                 Neighbor n[] = ((PeerSetMsg)event).getPeerSet();
 969
 970                                 for(int i=0; i<peersetSize; i++){
 971                                         if( n[i]!=null && alive(n[i].node) && search(n[i].node.getID())==null && nNodes+nBitfieldSent <swarmSize-2) {
 972                                                 ev = new BitfieldMsg(BITFIELD, true, true, node, status, nPieces);
 973 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node,n[i].node);
 974 //                                              EDSimulator.add(latency,ev,n[i].node,pid);
 975                                                 ((Transport) node.getProtocol(tid)).send(node, n[i].node, ev, pid);
 976
 977                                                 nBitfieldSent++;
 978                                                 // Here I should call the Neighbor.justSent(), but here
 979                                                 // the node is not yet in the cache.
 980                                         }
 981                                 }
 982                         }; break;
 983
 984                         case TRACKER: // TRACKER message
 985                         {
 986
 987                                 int j=0;
 988                                 Node sender = ((SimpleMsg)event).getSender();
 989                                 //System.out.println("process, tracker: sender is "+sender.getID()+", local is "+node.getID());
 990                                 if(!alive(sender))
 991                                         return;
 992                                 Neighbor tmp[] = new Neighbor[peersetSize];
 993                                 int k=0;
 994                                 if(nNodes <= peersetSize){
 995                                         for(int i=0; i< nMaxNodes+maxGrowth; i++){
 996                                                 if(cache[i].node != null && cache[i].node.getID()!= sender.getID()){
 997                                                         tmp[k]=cache[i];
 998                                                         k++;
 999                                                 }
1000                                         }
1001                                         ev = new PeerSetMsg(PEERSET, tmp, node);
1002 //                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node, sender);
1003 //                                      EDSimulator.add(latency,ev,sender,pid);
1004                                         ((Transport) node.getProtocol(tid)).send(node,sender, ev, pid);
1005                                         return;
1006                                 }
1007
1008                                 while(j < peersetSize){
1009                                         int i = CommonState.r.nextInt(nMaxNodes+maxGrowth);
1010                                         for (int z=0; z<j; z++){
1011                                                 if(cache[i].node==null || tmp[z].node.getID() == cache[i].node.getID() || cache[i].node.getID() == sender.getID()){
1012                                                         z=0;
1013                                                         i= CommonState.r.nextInt(nMaxNodes+maxGrowth);
1014                                                 }
1015                                         }
1016                                         if(cache[i].node != null){
1017                                                 tmp[j] = cache[i];
1018                                                 j++;
1019                                         }
1020                                 }
1021                                 ev = new PeerSetMsg(PEERSET, tmp, node);
1022 //                              latency = ((Transport)node.getProtocol(tid)).getLatency(node, sender);
1023 //                              EDSimulator.add(latency,ev,sender,pid);
1024                                 ((Transport) node.getProtocol(tid)).send(node,sender, ev, pid);
1025                         }; break;
1026
1027                         case CHOKE_TIME: //Every 10 secs.
1028                         {
1029                                 n_choke_time++;
1030
1031                                 ev = new SimpleEvent(CHOKE_TIME);
1032                                 EDSimulator.add(10000,ev,node,pid);
1033                                 int j=0;
1034                                 /*I copy the interested nodes in the byBandwidth array*/
1035                                 for(int i=0;i< swarmSize && byPeer[i].peer != -1; i++){
1036                                         if(cache[byPeer[i].peer].interested > 0){
1037                                                 byBandwidth[j]=byPeer[i]; //shallow copy
1038                                                 j++;
1039                                         }
1040                                 }
1041
1042                                 /*It ensures that in the next 20sec, if there are less nodes interested
1043                                         than now, those in surplus will not be ordered. */
1044                                 for(;j<swarmSize;j++){
1045                                         byBandwidth[j]=null;
1046                                 }
1047                                 sortByBandwidth();
1048                                 int optimistic = 3;
1049                                 int luckies[] = new int[3];
1050                                 try{ // It takes the first three neighbors
1051                                         luckies[0] = byBandwidth[0].peer;
1052                                         optimistic--;
1053                                         luckies[1] = byBandwidth[1].peer;
1054                                         optimistic--;
1055                                         luckies[2] = byBandwidth[2].peer;
1056                                 }
1057                                 catch(NullPointerException e){ // If not enough peer in byBandwidth it chooses the other romdomly
1058                                         for(int z = optimistic; z>0;z--){
1059                                                 int lucky = CommonState.r.nextInt(nNodes);
1060                                                 while(cache[byPeer[lucky].peer].status ==1 && alive(cache[byPeer[lucky].peer].node) &&
1061                                                           cache[byPeer[lucky].peer].interested == 0)// until the lucky peer is already unchoked or not interested
1062                                                         lucky = CommonState.r.nextInt(nNodes);
1063                                                 luckies[3-z]= byPeer[lucky].peer;
1064                                         }
1065                                 }
1066                                 for(int i=0; i<swarmSize; i++){ // I perform the chokes and the unchokes
1067                                         if((i==luckies[0] || i==luckies[1] || i==luckies[2]) &&  alive(cache[i].node) && cache[i].status != 2){ //the unchokes
1068                                                 cache[i].status = 1;
1069                                                 ev = new SimpleMsg(UNCHOKE, node);
1070 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node, cache[i].node);
1071 //                                              EDSimulator.add(latency,ev,cache[i].node,pid);
1072                                                 ((Transport) node.getProtocol(tid)).send(node,cache[i].node, ev, pid);
1073                                                 cache[i].justSent();
1074                                                 //System.out.println("average time, unchoked: "+cache[i].node.getID());
1075                                         }
1076                                         else{ // the chokes
1077                                                 if(alive(cache[i].node) && (cache[i].status == 1 || cache[i].status == 2)){
1078                                                         cache[i].status = 0;
1079                                                         ev = new SimpleMsg(CHOKE, node);
1080 //                                                      latency = ((Transport)node.getProtocol(tid)).getLatency(node, cache[i].node);
1081 //                                                      EDSimulator.add(latency,ev,cache[i].node,pid);
1082                                                         ((Transport) node.getProtocol(tid)).send(node,cache[i].node, ev, pid);
1083                                                         cache[i].justSent();
1084                                                 }
1085                                         }
1086                                 }
1087
1088                                 if(n_choke_time%2==0){ //every 20 secs. Used in computing the average download rates
1089                                         for(int i=0; i<nNodes; i++){
1090                                                 if(this.peerStatus == 0){ // I'm a leeacher
1091                                                         byPeer[i].head20 = byPeer[i].valueDOWN;
1092                                                 }
1093                                                 else{
1094                                                         byPeer[i].head20 = byPeer[i].valueUP;
1095                                                 }
1096                                         }
1097                                 }
1098                         }; break;
1099
1100                         case OPTUNCHK_TIME:
1101                         {
1102
1103                                 //System.out.println("process, optunchk_time");
1104
1105                                 ev = new SimpleEvent(OPTUNCHK_TIME);
1106                                 EDSimulator.add(30000,ev,node,pid);
1107                                 int lucky = CommonState.r.nextInt(nNodes);
1108                                 while(cache[byPeer[lucky].peer].status ==1)// until the lucky peer is already unchoked
1109                                         lucky = CommonState.r.nextInt(nNodes);
1110                                 if(!alive(cache[byPeer[lucky].peer].node))
1111                                         return;
1112                                 cache[byPeer[lucky].peer].status = 1;
1113                                 Object msg = new SimpleMsg(UNCHOKE,node);
1114 //                              latency = ((Transport)node.getProtocol(tid)).getLatency(node, cache[byPeer[lucky].peer].node);
1115 //                              EDSimulator.add(latency,msg,cache[byPeer[lucky].peer].node,pid);
1116                                 ((Transport) node.getProtocol(tid)).send(node,cache[byPeer[lucky].peer].node, msg, pid);
1117                                 cache[byPeer[lucky].peer].justSent();
1118                         }; break;
1119
1120                         case ANTISNUB_TIME:
1121                         {
1122                                 if(this.peerStatus == 1) // I'm a seeder, I don't update the event
1123                                         return;
1124                                 //System.out.println("process, antisnub_time");
1125                                 for(int i=0; i<nNodes; i++){
1126                                         if(byPeer[i].valueDOWN >0 && (byPeer[i].valueDOWN - byPeer[i].head60)==0){// No blocks downloaded in 1 min
1127                                                 cache[byPeer[i].peer].status = 2; // I'm snubbed by it
1128                                         }
1129                                         byPeer[i].head60 = byPeer[i].valueDOWN;
1130                                 }
1131                                 ev = new SimpleEvent(ANTISNUB_TIME);
1132                                 EDSimulator.add(60000,ev,node,pid);
1133                                 long time = CommonState.getTime();
1134                         }; break;
1135
1136                         case CHECKALIVE_TIME:
1137                         {
1138
1139                                 //System.out.println("process, checkalive_time");
1140
1141                                 long now = CommonState.getTime();
1142                                 for(int i=0; i<swarmSize; i++){
1143                                         /*If are at least 2 minutes (plus 1 sec of tolerance) that
1144                                         I don't send anything to it.*/
1145                                         if(alive(cache[i].node) && (cache[i].lastSent < (now-121000))){
1146                                                 Object msg = new IntMsg(KEEP_ALIVE,node,0,0);
1147 //                                              latency = ((Transport)node.getProtocol(tid)).getLatency(node, cache[i].node);
1148 //                                              EDSimulator.add(latency,msg,cache[i].node,pid);
1149                                                 ((Transport) node.getProtocol(tid)).send(node,cache[i].node, msg, pid);
1150                                                 cache[i].justSent();
1151                                         }
1152                                         /*If are at least 2 minutes (plus 1 sec of tolerance) that I don't
1153                                         receive anything from it though I sent a keepalive 2 minutes ago*/
1154                                         else{
1155                                                 if(cache[i].lastSeen <(now-121000) && cache[i].node != null && cache[i].lastSent < (now-121000)){
1156                                                         System.out.println("process, checkalive_time, rm neigh " + cache[i].node.getID());
1157                                                         if(cache[i].node.getIndex() != -1){
1158                                                                 System.out.println("This should never happen: I remove a node that is not effectively died");
1159                                                         }
1160                                                         removeNeighbor(cache[i].node);
1161                                                         processNeighborListSize(node,pid);
1162                                                 }
1163                                         }
1164                                 }
1165                                 ev = new SimpleEvent(CHECKALIVE_TIME);
1166                                 EDSimulator.add(120000,ev,node,pid);
1167                         }; break;
1168
1169                         case TRACKERALIVE_TIME:
1170                         {
1171                                 //System.out.println("process, trackeralive_time");
1172                                 if(alive(tracker)){
1173                                         ev = new SimpleEvent(TRACKERALIVE_TIME);
1174                                         EDSimulator.add(1800000,ev,node,pid);
1175                                 }
1176                                 else
1177                                         tracker=null;
1178
1179                         }; break;
1180
1181                         case DOWNLOAD_COMPLETED:
1182                         {
1183                                 nPiecesUp--;
1184                         }; break;
1185
1186                 }
1187         }
1188
1189         /**
1190          *      Given a piece index and a block index it encodes them in an unique integer value.
1191          *      @param piece the index of the piece to encode.
1192          *      @param block the index of the block to encode.
1193          *      @return the encoding of the piece and the block indexes.
1194          */
1195         private int encode(int piece, int block){
1196                 return (piece*100)+block;
1197
1198         }
1199         /**
1200          *      Returns either the piece or the block that contained in the <tt>value</tt> depending
1201          *      on <tt>part</tt>: 0 means the piece value, 1 the block value.
1202          *      @param value the ID of the block to decode.
1203          *      @param part the information to extract from <tt>value</tt>. 0 means the piece index, 1 the block index.
1204          *      @return the piece or the block index depending about the value of <tt>part</tt>
1205          */
1206         private int decode(int value, int part){
1207                 if (value==-1) // Not a true value to decode
1208                         return -1;
1209                 if(part == 0) // I'm interested to the piece
1210                         return value/100;
1211                 else // I'm interested to the block
1212                         return value%100;
1213         }
1214
1215         /**
1216          *      Used by {@link NodeInitializer#choosePieces(int, BitTorrent) NodeInitializer} to set
1217          *      the number of piece completed from the beginning in according with
1218          *      the distribution in the configuration file.
1219          *      @param number the number of piece completed
1220          */
1221         public void setCompleted(int number){
1222                 this.nPieceCompleted = number;
1223         }
1224
1225         /**
1226          *      Sets the status (the set of blocks) of the file for the current node.
1227          *  Note that a piece is considered <i>completed</i> if the number
1228          *  of downloaded blocks is 16.
1229          *  @param index The index of the piece
1230          *  @param value Number of blocks downloaded for the piece index.
1231          */
1232         public void setStatus(int index, int value){
1233                 status[index]=value;
1234         }
1235
1236         /**
1237          *      Sets the status of the local node.
1238          *      @param status The status of the node: 1 means seeder, 0 leecher
1239          */
1240         public void setPeerStatus(int status){
1241                 this.peerStatus = status;
1242         }
1243
1244         /**
1245          *      Gets the status of the local node.
1246          *      @return The status of the local node: 1 means seeder, 0 leecher
1247          */
1248         public int getPeerStatus(){
1249                 return peerStatus;
1250         }
1251
1252         /**
1253          *  Gets the number of blocks for a given piece owned by the local node.
1254          *      @param index The index of the piece
1255          *      @return Number of blocks downloaded for the piece index
1256          */
1257         public int getStatus(int index){
1258                 return status[index];
1259         }
1260
1261         /**
1262          *      Sets the maximum bandwdith for the local node.
1263          *      @param value The value of bandwidth in Kbps
1264          */
1265         public void setBandwidth(int value){
1266                 maxBandwidth = value;
1267         }
1268
1269         /**
1270          *      Checks if a node is still alive in the simulated network.
1271          *      @param node The node to check
1272          *      @return true if the node <tt>node</tt> is up, false otherwise
1273          *      @see peersim.core.GeneralNode#isUp
1274          */
1275         public boolean alive(Node node){
1276                 if(node == null)
1277                         return false;
1278                 else
1279                         return node.isUp();
1280         }
1281
1282         /**
1283          *      Adds a neighbor to the cache of the local node.
1284          *  The new neighbor is put in the first null position.
1285          *      @param neighbor The neighbor node to add
1286          *  @return <tt>false</tt> if the neighbor is already present in the cache (this can happen when the peer requests a
1287          *      new peer set to the tracker an there is still this neighbor within) or no place is available.
1288          *      Otherwise, returns true if the node is correctly added to the cache.
1289          */
1290         public boolean addNeighbor(Node neighbor){
1291                 if(search(neighbor.getID()) !=null){// if already exists
1292                 //      System.err.println("Node "+neighbor.getID() + " not added, already exist.");
1293                         return false;
1294                 }
1295                 if(this.tracker == null){ // I'm in the tracker's BitTorrent protocol
1296                         for(int i=0; i< nMaxNodes+maxGrowth; i++){
1297                                 if(cache[i].node == null){
1298                                         cache[i].node = neighbor;
1299                                         cache[i].status = 0; //chocked
1300                                         cache[i].interested = -1; //not interested
1301                                         this.nNodes++;
1302
1303                                         //System.err.println("i: " + i +" nMaxNodes: " + nMaxNodes);
1304                                         return true;
1305                                 }
1306                         }
1307                 }
1308                 else{
1309                         if((nNodes+nBitfieldSent) < swarmSize){
1310                                 //System.out.println("I'm the node " + this.thisNodeID + ", trying to add node "+neighbor.getID());
1311                                 for(int i=0; i<swarmSize; i++){
1312                                         if(cache[i].node == null){
1313                                                 cache[i].node = neighbor;
1314                                                 cache[i].status = 0; //choked
1315                                                 cache[i].interested = -1; // not interested
1316                                                 byPeer[nNodes].peer = i;
1317                                                 byPeer[nNodes].ID = neighbor.getID();
1318                                                 sortByPeer();
1319                                                 this.nNodes++;
1320                                                 //System.out.println(neighbor.getID()+" added!");
1321                                                 return true;
1322                                         }
1323                                 }
1324                                 System.out.println("Node not added, no places available");
1325                         }
1326                 }
1327                 return false;
1328         }
1329
1330         /**
1331          *      Removes a neighbor from the cache of the local node.
1332          *      @param neighbor The node to remove
1333          *      @return true if the node is correctly removed, false otherwise.
1334      */
1335         public boolean removeNeighbor(Node neighbor) {
1336
1337                 if (neighbor == null)
1338                         return true;
1339
1340                 // this is the tracker's bittorrent protocol
1341                 if (this.tracker == null) {
1342                         for (int i=0; i< (nMaxNodes+maxGrowth); i++) {
1343
1344                                 // check the feasibility of the removal
1345                                 if ( (cache[i] != null) && (cache[i].node != null) &&
1346                                          (cache[i].node.getID() == neighbor.getID()) ) {
1347                                         cache[i].node = null;
1348                                         this.nNodes--;
1349                                         return true;
1350                                 }
1351                         }
1352                         return false;
1353                 }
1354                 // this is the bittorrent protocol of a peer
1355                 else {
1356
1357                         Element e = search(neighbor.getID());
1358
1359                         if (e != null) {
1360                                 for (int i=0; i<nPieces; i++) {
1361                                         rarestPieceSet[i] -= swarm[e.peer][i];
1362                                         swarm[e.peer][i] = 0;
1363                                 }
1364
1365                                 cache[e.peer].node = null;
1366                                 cache[e.peer].status = 0;
1367                                 cache[e.peer].interested = -1;
1368                                 unchokedBy[e.peer] = false;
1369                                 this.nNodes--;
1370                                 e.peer = -1;
1371                                 e.ID = Integer.MAX_VALUE;
1372                                 e.valueUP = 0;
1373                                 e.valueDOWN = 0;
1374                                 e.head20 = 0;
1375                                 e.head60 = 0;
1376                                 sortByPeer();
1377
1378                                 return true;
1379                         }
1380                 }
1381                 return false;
1382         }
1383
1384         /**
1385      *  Adds a request to the pendingRequest queue.
1386          *      @param block The requested block
1387          *      @return true if the request has been successfully added to the queue, false otherwise
1388          */
1389         private boolean addRequest(int block){
1390                 int i=4;
1391                 while(i>=0 && pendingRequest[i]!=-1){
1392                         i--;
1393                 }
1394                 if(i>=0){
1395                         pendingRequest[i] = block;
1396                         return true;
1397                 }
1398                 else { // It should never happen
1399                            //System.err.println("pendingRequest queue full");
1400                         return false;
1401                 }
1402         }
1403
1404         /**
1405          *      Removes the block with the given <tt>id</tt> from the {@link #pendingRequest} queue
1406          *  and sorts the queue leaving the empty cell at the left.
1407          *      @param id the id of the requested block
1408          */
1409         private void removeRequest(int id){
1410                 int i = 4;
1411                 for(; i>=0; i--){
1412                         if(pendingRequest[i]==id)
1413                                 break;
1414                 }
1415                 for(; i>=0; i--){
1416                         if(i==0)
1417                                 pendingRequest[i] = -1;
1418                         else
1419                                 pendingRequest[i] = pendingRequest[i-1];
1420                 }
1421         }
1422
1423         /**
1424          *      Requests new block until the {@link #pendingRequest} is full to the sender of the just received piece.
1425          *      It calls {@link #getNewBlock(Node, int)} to implement the <i>strict priority</i> strategy.
1426          *      @param node the local node
1427          *      @param pid the BitTorrent protocol id
1428          *      @param sender the sender of the just received received piece.
1429          */
1430         private void requestNextBlocks(Node node, int pid, int sender){
1431                 int block = getNewBlock(node, pid);
1432                 while(block != -2){
1433                         if(unchokedBy[sender]==true && alive(cache[sender].node) && addRequest(block)){
1434                                 Object ev = new IntMsg(REQUEST, node, block,0);
1435
1436 //                              long latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[sender].node);
1437 //                              EDSimulator.add(latency,ev,cache[sender].node,pid);
1438
1439                                 ((Transport) node.getProtocol(tid)).send(node,cache[sender].node, ev, pid);
1440                                 cache[sender].justSent();
1441                         }
1442                         else{ // I cannot send request
1443                                 if(!alive(cache[sender].node) && cache[sender].node!=null){
1444                                         System.out.println("piece2 rm neigh "+ cache[sender].node.getID() );
1445                                         removeNeighbor(cache[sender].node);
1446                                         processNeighborListSize(node,pid);
1447                                 }
1448                                 return;
1449                         }
1450                         block = getNewBlock(node, pid);
1451                 }
1452         }
1453
1454         /**
1455          *      It returns the id of the next block to request. Sends <tt>INTERESTED</tt> if the new
1456          *      block belongs to a new piece.
1457          *      It uses {@link #getBlock()} to get the next block of a piece and calls {@link #getPiece()}
1458          *      when all the blocks for the {@link #currentPiece} have been requested.
1459          *      @param node the local node
1460          *      @param pid the BitTorrent protocol id
1461          *      @return -2 if no more places available in the <tt>pendingRequest</tt> queue;<br/>
1462          *                      the value of the next block to request otherwise</p>
1463          */
1464         private int getNewBlock(Node node, int pid){
1465                 int block = getBlock();
1466                 if(block < 0){ // No more block to request for the current piece
1467
1468                         if(block ==-2) // Pending request queue full
1469                                 return -2;
1470
1471                         int newPiece = getPiece();
1472                         if(newPiece == -1){ // no more piece to request
1473                                 return -2;
1474                         }
1475
1476                         lastInterested = newPiece;
1477                         Object ev = new IntMsg(INTERESTED, node, lastInterested,0);
1478
1479                         for(int j=0; j<swarmSize; j++){// send the interested message to those
1480                                                                         // nodes which have that piece
1481                                 if(alive(cache[j].node) && swarm[j][newPiece]==1){
1482 //                                      long latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[j].node);
1483 //                                      EDSimulator.add(latency,ev,cache[j].node,pid);
1484                                         ((Transport) node.getProtocol(tid)).send(node,cache[j].node, ev, pid);
1485                                         cache[j].justSent();
1486                                 }
1487                                 if(!alive(cache[j].node)){
1488                                         //System.out.println("piece1 rm neigh "+ cache[j].node.getID() );
1489
1490                                         removeNeighbor(cache[j].node);
1491                                         processNeighborListSize(node,pid);
1492                                 }
1493                         }
1494                         block = getBlock();
1495                         return block;
1496                 }
1497                 else{
1498                         // block value referred to a real block
1499                         return block;
1500                 }
1501         }
1502
1503         /**
1504          *      Returns the next block to request for the {@link #currentPiece}.
1505          *      @return an index of a block of the <tt>currentPiece</tt> if there are still
1506          *                      available places in the {@link #pendingRequest} queue;<br/>
1507          *                      -2 if the <tt>pendingRequest</tt> queue is full;<br/>
1508          *                      -1 if no more blocks to request for the current piece.
1509          */
1510         private int getBlock(){
1511                 int i=4;
1512                 while(i>=0 && pendingRequest[i]!=-1){ // i is the first empty position from the head
1513                         i--;
1514                 }
1515                 if(i==-1){// No places in the pendingRequest available
1516                                   //System.out.println("Pendig request queue full!");
1517                         return -2;
1518                 }
1519                 int j;
1520                 //The queue is not empty & last requested block belongs to lastInterested piece
1521                 if(i!=4 && decode(pendingRequest[i+1],0)==lastInterested)
1522                         j=decode(pendingRequest[i+1],1)+1; // the block following the last requested
1523                 else // I don't know which is the next block, so I search it.
1524                         j=0;
1525                 /*      I search another block until the current has been already received.
1526                         *       If in pieceStatus at position j there is a block that belongs to
1527                         *       lastInterested piece, means that the block j has been already
1528                         *       received, otherwise I can request it.
1529                         */
1530                 while(j<16 && decode(pieceStatus[j],0)==lastInterested){
1531                         j++;
1532                 }
1533                 if(j==16) // No more block to request for lastInterested piece
1534                         return -1;
1535                 return encode(lastInterested,j);
1536         }
1537
1538         /**
1539          *      Returns the next correct piece to download. It choose the piece by using the
1540          *      <i>random first</i> and <i>rarest first</i> policy. For the beginning 4 pieces
1541          *      of a file the first one is used then the pieces are chosen using <i>rarest first</i>.
1542          *      @see "Documentation about the BitTorrent module"
1543          *      @return the next piece to download. If the whole file has been requested
1544          *      -1 is returned.
1545          */
1546         private int getPiece(){
1547                 int piece = -1;
1548                 if(nPieceCompleted < 4){ //Uses random first piece
1549                         piece = CommonState.r.nextInt(nPieces);
1550                         while(status[piece]==16 || piece == currentPiece) // until the piece is owned
1551                                 piece = CommonState.r.nextInt(nPieces);
1552                         return piece;
1553                 }
1554                 else{ //Uses rarest piece first
1555                         int j=0;
1556                         for(; j<nPieces; j++){ // I find the first not owned piece
1557                                 if(status[j]==0){
1558                                         piece = j;
1559                                         if(piece != lastInterested) // teoretically it works because
1560                                                                                                 // there should be only one interested
1561                                                                                                 // piece not yet downloaded
1562                                                 break;
1563                                 }
1564                         }
1565                         if(piece==-1){ // Never entered in the previous 'if' statement; for all
1566                                                    // pieces an has been sent
1567                                 return -1;
1568                         }
1569
1570                         int rarestPieces[] = new int[nPieces-j]; // the pieces with the less number of occurences\
1571                         rarestPieces[0] = j;
1572                         int nValues = 1; // number of pieces less distributed in the network
1573                         for(int i=j+1; i<nPieces; i++){ // Finds the rarest piece not owned
1574                                 if(rarestPieceSet[i]< rarestPieceSet[rarestPieces[0]] && status[i]==0){ // if strictly less than the current one
1575                                         rarestPieces[0] = i;
1576                                         nValues = 1;
1577                                 }
1578                                 if(rarestPieceSet[i]==rarestPieceSet[rarestPieces[0]] && status[i]==0){ // if equal
1579                                         rarestPieces[nValues] = i;
1580                                         nValues++;
1581                                 }
1582                         }
1583
1584                         piece = CommonState.r.nextInt(nValues); // one of the less owned pieces
1585                         return rarestPieces[piece];
1586                 }
1587         }
1588
1589         /**
1590          *      Returns the file's size as number of pieces of 256KB.
1591          *      @return number of pieces that compose the file.
1592          */
1593         public int getNPieces(){
1594                 return nPieces;
1595         }
1596         /**
1597          *      Clone method of the class. Returns a deep copy of the BitTorrent class. Used
1598          *      by the simulation to initialize the {@link peersim.core.Network}
1599          *      @return the deep copy of the BitTorrent class.
1600          */
1601         public Object clone(){
1602                 Object prot = null;
1603                 try{
1604                         prot = (BitTorrent)super.clone();
1605                 }
1606                 catch(CloneNotSupportedException e){};
1607
1608                 ((BitTorrent)prot).cache = new Neighbor[swarmSize];
1609                 for(int i=0; i<swarmSize; i++){
1610                         ((BitTorrent)prot).cache[i] = new Neighbor();
1611                 }
1612
1613                 ((BitTorrent)prot).byPeer = new Element[swarmSize];
1614                 for(int i=0; i<swarmSize; i++){
1615                         ((BitTorrent)prot).byPeer[i] = new Element();
1616                 }
1617
1618                 ((BitTorrent)prot).unchokedBy = new boolean[swarmSize];
1619
1620                 ((BitTorrent)prot).byBandwidth = new Element[swarmSize];
1621                 ((BitTorrent)prot).status = new int[nPieces];
1622                 ((BitTorrent)prot).pieceStatus = new int[16];
1623                 for(int i=0; i<16;i++)
1624                         ((BitTorrent)prot).pieceStatus[i] = -1;
1625                 ((BitTorrent)prot).pendingRequest = new int[5];
1626                 for(int i=0; i<5;i++)
1627                         ((BitTorrent)prot).pendingRequest[i] = -1;
1628                 ((BitTorrent)prot).rarestPieceSet = new int[nPieces];
1629                 for(int i=0; i<nPieces;i++)
1630                         ((BitTorrent)prot).rarestPieceSet[i] = 0;
1631                 ((BitTorrent)prot).swarm = new int[swarmSize][nPieces];
1632                 ((BitTorrent)prot).requestToServe = new Queue(20);
1633                 ((BitTorrent)prot).incomingPieces = new Queue(100);
1634                 return prot;
1635         }
1636
1637         /**
1638          *      Sorts {@link #byPeer} array by peer's ID. It implements the <i>InsertionSort</i>
1639          *      algorithm.
1640          */
1641         public void sortByPeer(){
1642                 int i;
1643
1644                 for(int j=1; j<swarmSize; j++)   // out is dividing line
1645                 {
1646                         Element key = new Element();
1647                         byPeer[j].copyTo(key) ;    // remove marked item
1648                         i = j-1;           // start shifts at out
1649                         while(i>=0 && (byPeer[i].ID > key.ID)) // until one is smaller,
1650                         {
1651                                 byPeer[i].copyTo(byPeer[i+1]);      // shift item right,
1652                                 i--;            // go left one position
1653                         }
1654                         key.copyTo(byPeer[i+1]);         // insert marked item
1655                 }
1656
1657         }
1658
1659         /**
1660          *      Sorts the array {@link #byBandwidth} using <i>QuickSort</i> algorithm.
1661          *      <tt>null</tt> elements and seeders are moved to the end of the array.
1662          */
1663         public void sortByBandwidth() {
1664         quicksort(0, swarmSize-1);
1665     }
1666
1667         /**
1668          *      Used by {@link #sortByBandwidth()}. It's the implementation of the
1669          *      <i>QuickSort</i> algorithm.
1670          *      @param left the leftmost index of the array to sort.
1671          *      @param right the rightmost index of the array to sort.
1672          */
1673         private void quicksort(int left, int right) {
1674         if (right <= left) return;
1675         int i = partition(left, right);
1676         quicksort(left, i-1);
1677         quicksort(i+1, right);
1678     }
1679
1680         /**
1681          *      Used by {@link #quicksort(int, int)}, partitions the subarray to sort returning
1682          *      the splitting point as stated by the <i>QuickSort</i> algorithm.
1683          *      @see "The <i>QuickSort</i> algorithm".
1684          */
1685         private int partition(int left, int right) {
1686         int i = left - 1;
1687         int j = right;
1688         while (true) {
1689             while (greater(byBandwidth[++i], byBandwidth[right]))      // find item on left to swap
1690                 ;                               // a[right] acts as sentinel
1691             while (greater(byBandwidth[right], byBandwidth[--j])) {      // find item on right to swap
1692                 if (j == left) break;  // don't go out-of-bounds
1693                         }
1694             if (i >= j) break;                  // check if pointers cross
1695             swap(i, j);                      // swap two elements into place
1696         }
1697         swap(i, right);                      // swap with partition element
1698         return i;
1699     }
1700
1701         /**
1702          *      Aswers to the question "is x > y?". Compares the {@link Element}s given as
1703          *      parameters. <tt>Element x</tt> is greater than <tt>y</tt> if isn't <tt>null</tt>
1704          *      and in the last 20 seconds the local node has downloaded ("uploaded" if the local node is a
1705          *      seeder) more blocks than from <tt>y</tt>.
1706          *      @param x the first <tt>Element</tt> to compare.
1707          *      @param y the second <tt>Element</tt> to compare
1708          *      @return <tt>true</tt> if x > y;<br/>
1709          *                      <tt>false</tt> otherwise.
1710          */
1711     private boolean greater(Element x, Element y) {
1712                 /*
1713                  * Null elements and seeders are shifted at the end
1714                  * of the array
1715                  */
1716                 if (x==null) return false;
1717                 if (y==null) return true;
1718                 if (x.isSeeder) return false;
1719                 if (y.isSeeder) return true;
1720
1721                 // if the local node is a leecher
1722                 if (peerStatus==0) {
1723                         if ((x.valueDOWN - x.head20) >
1724                                 (y.valueDOWN -y.head20))
1725                                 return true;
1726                         else return false;
1727                 }
1728
1729                 // if peerStatus==1 (the local node is a seeder)
1730                 else {
1731                         if ((x.valueUP - x.head20) >
1732                                 (y.valueUP -y.head20))
1733                                 return true;
1734                         else return false;
1735                 }
1736     }
1737
1738         /**
1739          *      Swaps {@link Element} <tt>i</tt> with <tt>j</tt> in the {@link #byBandwidth}.<br/>
1740          *      Used by {@link #partition(int, int)}
1741          *      @param i index of the first element to swap
1742          *      @param j index of the second element to swap
1743          */
1744         private void swap(int i, int j) {
1745         Element swap = byBandwidth[i];
1746         byBandwidth[i] = byBandwidth[j];
1747         byBandwidth[j] = swap;
1748     }
1749
1750         /**     Searches the node with the given ID. It does a dychotomic
1751          *      search.
1752          *      @param ID ID of the node to search.
1753          *      @return the {@link Element} in {@link #byPeer} which represents the node with the
1754          *      given ID.
1755          */
1756         public Element search(long ID){
1757                 int low = 0;
1758                 int high = swarmSize-1;
1759                 int p = low+((high-low)/2);              //Initial probe position
1760                 while ( low <= high) {
1761                         if ( byPeer[p] == null || byPeer[p].ID > ID)
1762                                 high = p - 1;
1763                         else {
1764                                 if( byPeer[p].ID < ID )  //Wasteful second comparison forced by syntax limitations.
1765                                         low = p + 1;
1766                                 else
1767                                         return byPeer[p];
1768                         }
1769                         p = low+((high-low)/2);         //Next probe position.
1770                 }
1771                 return null;
1772         }
1773 }
1774
1775 /**
1776  *      This class is used to store the main informations about a neighbors regarding
1777  *      the calculation of the Downloading/Uploading rates. Is the class of items in
1778  *      {@link example.bittorrent.BitTorrent#byPeer} and {@link example.bittorrent.BitTorrent#byBandwidth}.
1779  */
1780 class Element{
1781         /**
1782          *      ID of the represented node.
1783          */
1784         public long ID = Integer.MAX_VALUE;
1785         /**
1786          *      Index position of the node in the {@link example.bittorrent.BitTorrent#cache} array.
1787          */
1788         public int peer = -1;
1789         /**
1790          *      Number of blocks uploaded to anyone since the beginning.
1791          */
1792         public int valueUP = 0;
1793         /**
1794          *      Number of blocks downloaded from anyone since the beginning.
1795          */
1796         public int valueDOWN = 0;
1797         /**
1798          *      Value of either {@link #valueUP} or {@link #valueDOWN} (depending by
1799          *      {@link example.bittorrent.BitTorrent#peerStatus}) 20 seconds before.
1800          */
1801         public int head20 = 0;
1802         /**
1803          *      Value of either {@link #valueUP} or {@link #valueDOWN} (depending by
1804          *      {@link example.bittorrent.BitTorrent#peerStatus}) 60 seconds before.
1805          */
1806         public int head60 = 0;
1807         /**
1808          *      <tt>true</tt> if the node is a seeder, <tt>false</tt> otherwise.
1809          */
1810         public boolean isSeeder = false;
1811         /**
1812          *      Makes a deep copy of the Element to <tt>destination</tt>
1813          *      @param destination Element instance where to make the copy
1814          */
1815         public void copyTo(Element destination){
1816                 destination.ID = this.ID;
1817                 destination.peer = this.peer;
1818                 destination.valueUP = this.valueUP;
1819                 destination.valueDOWN = this.valueDOWN;
1820                 destination.head20 = this.head20;
1821                 destination.head60 = this.head60;
1822         }
1823 }
1824
1825 /**
1826  *      This class stores information about the neighbors regarding their status. It is
1827  *      the type of the items in the {@link example.bittorrent.BitTorrent#cache}.
1828  */
1829 class Neighbor{
1830         /**
1831          *      Reference to the node in the {@link peersim.core.Network}.
1832          */
1833         public Node node = null;
1834         /**
1835          *      -1 means not interested<br/>
1836          *      Other values means the last piece number for which the node is interested.
1837          */
1838         public int interested;
1839         /**
1840          *      0 means CHOKED<br/>
1841          *      1 means UNCHOKED<br/>
1842          *      2 means SNUBBED_BY. If this value is set and the node is to be unchocked,
1843          *      value 2 has the priority.
1844          */
1845         public int status;
1846         /**
1847          *      Last time a message from the node represented has been received.
1848          */
1849         public long lastSeen = 0;
1850         /**
1851          *      Last time a message to the node represented has been sent.
1852          */
1853         public long lastSent = 0;
1854
1855         /**
1856          * Sets the last time the neighbor was seen.
1857          */
1858         public void isAlive(){
1859                 long now = CommonState.getTime();
1860                 this.lastSeen = now;
1861         }
1862
1863         /*
1864          * Sets the last time the local peer sent something to the neighbor.
1865          */
1866         public void justSent(){
1867                 long now = CommonState.getTime();
1868                 this.lastSent = now;
1869         }
1870
1871 }
1872
1873 /**
1874  *      Class type of the queues's items in {@link example.bittorrent.BitTorrent#incomingPieces}
1875  *      and {@link example.bittorrent.BitTorrent#requestToServe}.
1876  */
1877 class Queue{
1878         int maxSize;
1879         int head = 0;
1880         int tail = 0;
1881         int dim = 0;
1882         Request queue[];
1883
1884         /**
1885          *      Public constructor. Creates a queue of size <tt>size</tt>.
1886          */
1887         public Queue(int size){
1888                 maxSize = size;
1889                 queue = new Request[size];
1890                 for(int i=0; i< size; i++)
1891                         queue[i]= new Request();
1892         }
1893
1894         /**
1895          *      Enqueues the request of the block <tt>id</tt> and its <tt>sender</tt>
1896          *      @param id the id of the block in the request
1897          *      @param sender a reference to the sender of the request
1898          *      @return <tt>true</tt> if the request has been correctly added, <tt>false</tt>
1899          *      otherwise.
1900          */
1901         public boolean enqueue(int id, Node sender){
1902                 if(dim < maxSize){
1903                         queue[tail%maxSize].id = id;
1904                         queue[tail%maxSize].sender = sender;
1905                         tail++;
1906                         dim++;
1907                         return true;
1908                 }
1909                 else return false;
1910         }
1911
1912         /**
1913          *      Returns the {@link Request} in the head of the queue.
1914          *      @return the element in the head.<br/>
1915          *                      <tt>null</tt> if the queue is empty.
1916          */
1917         public Request dequeue(){
1918                 Request value;
1919                 if(dim > 0){
1920                         value = queue[head%maxSize];
1921                         head++;
1922                         dim--;
1923                         return value;
1924                 }
1925                 else return null; //empty queue
1926         }
1927
1928         /**
1929          *      Returns the status of the queue.
1930          *      @return <tt>true</tt> if the queue is empty, <tt>false</tt>
1931          *      otherwise.
1932          */
1933         public boolean empty(){
1934                 return (dim == 0);
1935         }
1936
1937         /**
1938          *      Returns <tt>true</tt> if block given as parameter is in.
1939          *      @param  value the id of the block to search.
1940          *      @return <tt>true</tt> if the block <tt>value</tt> is in the queue, <tt>false</tt>
1941          *      otherwise.
1942          */
1943         public boolean contains(int value){
1944                 if(empty())
1945                         return false;
1946                 for(int i=head; i<head+dim; i++){
1947                         if(queue[i%maxSize].id == value)
1948                                 return true;
1949                 }
1950                 return false;
1951         }
1952
1953         /**
1954          *      Removes a request from the queue.
1955          *      @param sender the sender of the request.
1956          *      @param value the id of the block requested.
1957          *      @return <tt>true</tt> if the request has been correctly removed, <tt>false</tt>
1958          *      otherwise.
1959          */
1960         public boolean remove(Node sender, int value){
1961                 if(empty())
1962                         return false;
1963                 for(int i=head; i<head+dim; i++){
1964                         if(queue[i%maxSize].id == value && queue[i%maxSize].sender == sender){
1965                                 for(int j=i; j>head; j--){ // Shifts the elements for the removal
1966                                         queue[j%maxSize]= queue[(j-1)%maxSize];
1967                                 }
1968                                 head++;
1969                                 dim--;
1970                                 return true;
1971                         }
1972                 }
1973                 return false;
1974         }
1975 }
1976
1977 /**
1978  *      This class represent an enqueued request of a block.
1979  */
1980 class Request{
1981         /**
1982          *      The id of the block.
1983          */
1984         public int id;
1985         /**
1986          *      The sender of the request.
1987          */
1988         public Node sender;
1989 }