2 * Copyright (c) 2007-2008 Fabrizio Frioli, Michele Pedrolli
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.
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.
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.
19 * Please send your questions/suggestions to:
20 * {fabrizio.frioli, michele.pedrolli} at studenti dot unitn dot it
24 package example.bittorrent;
26 import peersim.core.*;
27 import peersim.config.*;
28 import peersim.edsim.*;
29 import peersim.transport.*;
32 * This is the class that implements the BitTorrent module for Peersim
34 public class BitTorrent implements EDProtocol {
36 * The size in Megabytes of the file being shared.
39 private static final String PAR_SIZE="file_size";
41 * The Transport used by the the protocol.
44 private static final String PAR_TRANSPORT="transport";
46 * The maximum number of neighbor that a node can have.
49 private static final String PAR_SWARM="max_swarm_size";
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.
55 private static final String PAR_PEERSET_SIZE="peerset_size";
57 * Defines how much the network can grow with respect to the <tt>network.size</tt>
58 * when {@link NetworkDynamics} is used.
61 private static final String PAR_MAX_GROWTH="max_growth";
63 * Is the number of requests of the same block sent to different peers.
66 private static final String PAR_DUP_REQ = "duplicated_requests";
70 * @see SimpleEvent#type "Event types"
72 private static final int KEEP_ALIVE = 1;
76 * @see SimpleEvent#type "Event types"
78 private static final int CHOKE = 2;
82 * @see SimpleEvent#type "Event types"
84 private static final int UNCHOKE = 3;
88 * @see SimpleEvent#type "Event types"
90 private static final int INTERESTED = 4;
93 * NOT_INTERESTED message.
94 * @see SimpleEvent#type "Event types"
96 private static final int NOT_INTERESTED = 5;
100 * @see SimpleEvent#type "Event types"
102 private static final int HAVE = 6;
106 * @see SimpleEvent#type "Event types"
108 private static final int BITFIELD = 7;
112 * @see SimpleEvent#type "Event types"
114 private static final int REQUEST = 8;
118 * @see SimpleEvent#type "Event types"
120 private static final int PIECE = 9;
124 * @see SimpleEvent#type "Event types"
126 private static final int CANCEL = 10;
130 * @see SimpleEvent#type "Event types"
132 private static final int TRACKER = 11;
136 * @see SimpleEvent#type "Event types"
138 private static final int PEERSET = 12;
142 * @see SimpleEvent#type "Event types"
144 private static final int CHOKE_TIME = 13;
147 * OPTUNCHK_TIME event.
148 * @see SimpleEvent#type "Event types"
150 private static final int OPTUNCHK_TIME = 14;
153 * ANTISNUB_TIME event.
154 * @see SimpleEvent#type "Event types"
156 private static final int ANTISNUB_TIME = 15;
159 * CHECKALIVE_TIME event.
160 * @see SimpleEvent#type "Event types"
162 private static final int CHECKALIVE_TIME = 16;
165 * TRACKERALIVE_TIME event.
166 * @see SimpleEvent#type "Event types"
168 private static final int TRACKERALIVE_TIME = 17;
171 * DOWNLOAD_COMPLETED event.
172 * @see SimpleEvent#type "Event types"
174 private static final int DOWNLOAD_COMPLETED = 18;
177 * The maxium connection speed of the local node.
182 * Stores the neighbors ordered by ID.
185 private example.bittorrent.Element byPeer[];
188 * Contains the neighbors ordered by bandwidth as needed by the unchocking
191 private example.bittorrent.Element byBandwidth[];
194 * The Neighbors list.
196 private Neighbor cache[];
199 * Reference to the neighbors that unchocked the local node.
201 private boolean unchokedBy[];
204 * Number of neighbors in the cache. When it decreases under 20, a new peerset
205 * is requested to the tracker.
207 private int nNodes = 0;
210 * Maximum number of nodes in the network.
212 private int nMaxNodes;
215 * The status of the local peer. 0 means that the current peer is a leecher, 1 a seeder.
217 private int peerStatus;
220 * Defines how much the network can grow with respect to the <tt>network.size</tt>
221 * when {@link NetworkDynamics} is used.
223 public int maxGrowth;
226 * File status of the local node. Contains the blocks owned by the local node.
228 private int status[];
231 * Current number of Bitfield request sent. It must be taken into account
232 * before sending another one.
234 private int nBitfieldSent = 0;
237 * Current number of pieces in upload from the local peer.
239 public int nPiecesUp = 0;
241 * Current number of pieces in download to the local peer.
243 public int nPiecesDown = 0;
246 * Current number of piece completed.
248 private int nPieceCompleted = 0;
251 * Current downloading piece ID, the previous lastInterested piece.
253 int currentPiece = -1;
256 * Used to compute the average download rates in choking algorithm. Stores the
257 * number of <tt>CHOKE</tt> events.
259 int n_choke_time = 0;
262 * Used to send the <tt>TRACKER</tt> message when the local node has 20 neighbors
263 * for the first time.
265 boolean lock = false;
268 * Number of peers interested to my pieces.
270 int numInterestedPeers = 0;
273 * Last piece for which the local node sent an <tt>INTERESTED</tt> message.
275 int lastInterested = -1;
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.
283 private int pieceStatus[];
286 * Length of the file. Stored as number of pieces (256KB each one).
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}
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.
302 int rarestPieceSet[];
305 * The five pending block requests.
307 int pendingRequest[];
310 * The maximum swarm size (default is 80)
315 * The size of the peerset. This is the number of "friends" nodes
316 * sent from the tracker to each new node (default: 50)
321 * The ID of the current node
323 private long thisNodeID;
326 * Number of duplicated requests as specified in the configuration file.
327 * @see BitTorrent#PAR_DUP_REQ
329 private int numberOfDuplicatedRequests;
332 * The queue where the requests to serve are stored.
333 * The default dimension of the queue is 20.
335 Queue requestToServe = null;
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.
342 Queue incomingPieces = null;
346 * @see BitTorrent#PAR_TRANSPORT
351 * The reference to the tracker node. If equals to <tt>null</tt>, the local
352 * node is the tracker.
354 private Node tracker = null;
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
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;
372 * Gets the reference to the tracker node.
373 * @return the reference to the tracker
375 public Node getTracker(){
380 * Gets the number of neighbors currently stored in the cache of the local node.
381 * @return the number of neighbors in the cache
383 public int getNNodes(){
388 * Sets the reference to the tracker node.
389 * @param t the tracker node
391 public void setTracker(Node t){
396 * Sets the ID of the local node.
397 * @param id the ID of the node
399 public void setThisNodeID(long id) {
400 this.thisNodeID = id;
404 * Gets the ID of the local node.
405 * @return the ID of the local node
407 public long getThisNodeID(){
408 return this.thisNodeID;
412 * Gets the file status of the local node.
413 * @return the file status of the local node
415 public int[] getFileStatus(){
420 * Initializes the tracker node. This method
421 * only performs the initialization of the tracker's cache.
423 public void initializeTracker() {
424 cache = new Neighbor[nMaxNodes+maxGrowth];
425 for(int i=0; i<nMaxNodes+maxGrowth; i++){
426 cache[i]= new Neighbor();
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
435 * <p>This method *must* be called after every call of {@link #removeNeighbor}
436 * in {@link #processEvent}.
439 private void processNeighborListSize(Node node, int pid) {
443 ev = new SimpleMsg(TRACKER, node);
444 Node tracker = ((BitTorrent)node.getProtocol(pid)).tracker;
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);
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
459 public void processEvent(Node node, int pid, Object event){
463 switch(((SimpleEvent)event).getType()){
465 case KEEP_ALIVE: // 1
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();
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);
492 case CHOKE: // 2, CHOKE message.
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
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);
511 case UNCHOKE: // 3, UNCHOKE message.
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)
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();
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);
539 // I request missing blocks to fill the queue
540 int block = getBlock();
542 while(block != -2){ //while still available request to send
543 if(block < 0){ // No more block to request for the current piece
545 if(piece == -1){ // no more piece to request
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);
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);
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);
574 cache[senderIndex].justSent();
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);
587 unchokedBy[senderIndex] = true; // I add the sender to the list
589 else // It should never happen.
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);
603 case INTERESTED: // 4, INTERESTED message.
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());
611 cache[e.peer].isAlive();
612 cache[e.peer].interested = value;
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);
625 case NOT_INTERESTED: // 5, NOT_INTERESTED message.
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());
633 cache[e.peer].isAlive();
634 if(cache[e.peer].interested == value)
635 cache[e.peer].interested = -1; // not interested
639 case HAVE: // 6, HAVE message.
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());
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);
653 e.isSeeder = isSeeder;
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);
665 case BITFIELD: // 7, BITFIELD message
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
674 // otherwise is a response with ack that follows a duplicate
676 //System.out.println("process, bitfield_resp_nack: sender is "+sender.getID()+", local is "+node.getID());
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());
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();
691 /*Response with ACK*/
692 if(!((BitfieldMsg)event).isRequest && ((BitfieldMsg)event).ack){
694 //System.out.println("process, bitfield_resp_ack: sender is "+sender.getID()+", local is "+node.getID());
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);
705 e.isSeeder = isSeeder;
707 if(nNodes==10 && !lock){ // I begin to request pieces
709 int piece = getPiece();
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);
730 System.out.println("Sender "+sender.getID()+" not alive");
733 if(((BitfieldMsg)event).isRequest && ((BitfieldMsg)event).ack){
734 //System.out.println("process, bitfield_req_ack: sender is "+sender.getID()+", local is "+node.getID());
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
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();
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);
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();
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);
790 System.out.println("Sender "+sender.getID()+" not alive");
794 case REQUEST: // 8, REQUEST message.
797 Node sender = ((IntMsg)event).getSender();
798 int value = ((IntMsg)event).getInt();
806 e = search(sender.getID());
809 cache[e.peer].isAlive();
811 requestToServe.enqueue(value, sender);
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);
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
828 ev = new IntMsg(PIECE, node, req.id, 16*8 * 1024);
829 ((Transport) node.getProtocol(tid)).send(node, req.sender, ev, pid);
831 // latency = ((Transport)node.getProtocol(tid)).getLatency(node,req.sender);
832 // EDSimulator.add(latency+downloadTime,ev,req.sender,pid);
833 cache[e.peer].justSent();
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
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);
845 case PIECE: // 9, PIECE message.
847 Node sender = ((IntMsg)event).getSender();
848 /* Set the correct value for the local uploading and remote
849 downloading number of pieces */
852 if(peerStatus == 1)// To save CPU cycles
854 //System.out.println("process, piece: sender is "+sender.getID()+", local is "+node.getID());
855 Element e = search(sender.getID());
857 if(e==null){ //I can't accept a piece not wait
862 cache[e.peer].isAlive();
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;
872 removeRequest(value);
873 requestNextBlocks(node, pid, e.peer);
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);
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);
892 if(status[currentPiece]==16){ // if piece completed, I change the currentPiece to the next wanted
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);
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);
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);
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);
922 if(nPieceCompleted == nPieces){
923 System.out.println("FILE COMPLETED for peer "+node.getID());
927 /* I set the currentPiece to the lastInterested. Then I extract
928 the queued received blocks
931 currentPiece = lastInterested;
932 int m = incomingPieces.dim;
933 while(m > 0){ // I process the queue
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
941 if(p==currentPiece && decode(pieceStatus[b],0)!= p){
942 pieceStatus[b] = temp.id;
944 removeRequest(temp.id);
945 requestNextBlocks(node, pid, s.peer);
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);
959 Node sender = ((IntMsg)event).getSender();
960 int value = ((IntMsg)event).getInt();
961 requestToServe.remove(sender, value);
964 case PEERSET: // PEERSET message
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();
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);
978 // Here I should call the Neighbor.justSent(), but here
979 // the node is not yet in the cache.
984 case TRACKER: // TRACKER message
988 Node sender = ((SimpleMsg)event).getSender();
989 //System.out.println("process, tracker: sender is "+sender.getID()+", local is "+node.getID());
992 Neighbor tmp[] = new Neighbor[peersetSize];
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()){
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);
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()){
1013 i= CommonState.r.nextInt(nMaxNodes+maxGrowth);
1016 if(cache[i].node != null){
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);
1027 case CHOKE_TIME: //Every 10 secs.
1031 ev = new SimpleEvent(CHOKE_TIME);
1032 EDSimulator.add(10000,ev,node,pid);
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
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;
1049 int luckies[] = new int[3];
1050 try{ // It takes the first three neighbors
1051 luckies[0] = byBandwidth[0].peer;
1053 luckies[1] = byBandwidth[1].peer;
1055 luckies[2] = byBandwidth[2].peer;
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;
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());
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();
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;
1094 byPeer[i].head20 = byPeer[i].valueUP;
1103 //System.out.println("process, optunchk_time");
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))
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();
1122 if(this.peerStatus == 1) // I'm a seeder, I don't update the event
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
1129 byPeer[i].head60 = byPeer[i].valueDOWN;
1131 ev = new SimpleEvent(ANTISNUB_TIME);
1132 EDSimulator.add(60000,ev,node,pid);
1133 long time = CommonState.getTime();
1136 case CHECKALIVE_TIME:
1139 //System.out.println("process, checkalive_time");
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();
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*/
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");
1160 removeNeighbor(cache[i].node);
1161 processNeighborListSize(node,pid);
1165 ev = new SimpleEvent(CHECKALIVE_TIME);
1166 EDSimulator.add(120000,ev,node,pid);
1169 case TRACKERALIVE_TIME:
1171 //System.out.println("process, trackeralive_time");
1173 ev = new SimpleEvent(TRACKERALIVE_TIME);
1174 EDSimulator.add(1800000,ev,node,pid);
1181 case DOWNLOAD_COMPLETED:
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.
1195 private int encode(int piece, int block){
1196 return (piece*100)+block;
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>
1206 private int decode(int value, int part){
1207 if (value==-1) // Not a true value to decode
1209 if(part == 0) // I'm interested to the piece
1211 else // I'm interested to the block
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
1221 public void setCompleted(int number){
1222 this.nPieceCompleted = number;
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.
1232 public void setStatus(int index, int value){
1233 status[index]=value;
1237 * Sets the status of the local node.
1238 * @param status The status of the node: 1 means seeder, 0 leecher
1240 public void setPeerStatus(int status){
1241 this.peerStatus = status;
1245 * Gets the status of the local node.
1246 * @return The status of the local node: 1 means seeder, 0 leecher
1248 public int getPeerStatus(){
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
1257 public int getStatus(int index){
1258 return status[index];
1262 * Sets the maximum bandwdith for the local node.
1263 * @param value The value of bandwidth in Kbps
1265 public void setBandwidth(int value){
1266 maxBandwidth = value;
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
1275 public boolean alive(Node node){
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.
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.");
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
1303 //System.err.println("i: " + i +" nMaxNodes: " + nMaxNodes);
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();
1320 //System.out.println(neighbor.getID()+" added!");
1324 System.out.println("Node not added, no places available");
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.
1335 public boolean removeNeighbor(Node neighbor) {
1337 if (neighbor == null)
1340 // this is the tracker's bittorrent protocol
1341 if (this.tracker == null) {
1342 for (int i=0; i< (nMaxNodes+maxGrowth); i++) {
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;
1354 // this is the bittorrent protocol of a peer
1357 Element e = search(neighbor.getID());
1360 for (int i=0; i<nPieces; i++) {
1361 rarestPieceSet[i] -= swarm[e.peer][i];
1362 swarm[e.peer][i] = 0;
1365 cache[e.peer].node = null;
1366 cache[e.peer].status = 0;
1367 cache[e.peer].interested = -1;
1368 unchokedBy[e.peer] = false;
1371 e.ID = Integer.MAX_VALUE;
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
1389 private boolean addRequest(int block){
1391 while(i>=0 && pendingRequest[i]!=-1){
1395 pendingRequest[i] = block;
1398 else { // It should never happen
1399 //System.err.println("pendingRequest queue full");
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
1409 private void removeRequest(int id){
1412 if(pendingRequest[i]==id)
1417 pendingRequest[i] = -1;
1419 pendingRequest[i] = pendingRequest[i-1];
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.
1430 private void requestNextBlocks(Node node, int pid, int sender){
1431 int block = getNewBlock(node, pid);
1433 if(unchokedBy[sender]==true && alive(cache[sender].node) && addRequest(block)){
1434 Object ev = new IntMsg(REQUEST, node, block,0);
1436 // long latency = ((Transport)node.getProtocol(tid)).getLatency(node,cache[sender].node);
1437 // EDSimulator.add(latency,ev,cache[sender].node,pid);
1439 ((Transport) node.getProtocol(tid)).send(node,cache[sender].node, ev, pid);
1440 cache[sender].justSent();
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);
1450 block = getNewBlock(node, pid);
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>
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
1468 if(block ==-2) // Pending request queue full
1471 int newPiece = getPiece();
1472 if(newPiece == -1){ // no more piece to request
1476 lastInterested = newPiece;
1477 Object ev = new IntMsg(INTERESTED, node, lastInterested,0);
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();
1487 if(!alive(cache[j].node)){
1488 //System.out.println("piece1 rm neigh "+ cache[j].node.getID() );
1490 removeNeighbor(cache[j].node);
1491 processNeighborListSize(node,pid);
1498 // block value referred to a real block
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.
1510 private int getBlock(){
1512 while(i>=0 && pendingRequest[i]!=-1){ // i is the first empty position from the head
1515 if(i==-1){// No places in the pendingRequest available
1516 //System.out.println("Pendig request queue full!");
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.
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.
1530 while(j<16 && decode(pieceStatus[j],0)==lastInterested){
1533 if(j==16) // No more block to request for lastInterested piece
1535 return encode(lastInterested,j);
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
1546 private int getPiece(){
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);
1554 else{ //Uses rarest piece first
1556 for(; j<nPieces; j++){ // I find the first not owned piece
1559 if(piece != lastInterested) // teoretically it works because
1560 // there should be only one interested
1561 // piece not yet downloaded
1565 if(piece==-1){ // Never entered in the previous 'if' statement; for all
1566 // pieces an has been sent
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;
1578 if(rarestPieceSet[i]==rarestPieceSet[rarestPieces[0]] && status[i]==0){ // if equal
1579 rarestPieces[nValues] = i;
1584 piece = CommonState.r.nextInt(nValues); // one of the less owned pieces
1585 return rarestPieces[piece];
1590 * Returns the file's size as number of pieces of 256KB.
1591 * @return number of pieces that compose the file.
1593 public int getNPieces(){
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.
1601 public Object clone(){
1604 prot = (BitTorrent)super.clone();
1606 catch(CloneNotSupportedException e){};
1608 ((BitTorrent)prot).cache = new Neighbor[swarmSize];
1609 for(int i=0; i<swarmSize; i++){
1610 ((BitTorrent)prot).cache[i] = new Neighbor();
1613 ((BitTorrent)prot).byPeer = new Element[swarmSize];
1614 for(int i=0; i<swarmSize; i++){
1615 ((BitTorrent)prot).byPeer[i] = new Element();
1618 ((BitTorrent)prot).unchokedBy = new boolean[swarmSize];
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);
1638 * Sorts {@link #byPeer} array by peer's ID. It implements the <i>InsertionSort</i>
1641 public void sortByPeer(){
1644 for(int j=1; j<swarmSize; j++) // out is dividing line
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,
1651 byPeer[i].copyTo(byPeer[i+1]); // shift item right,
1652 i--; // go left one position
1654 key.copyTo(byPeer[i+1]); // insert marked item
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.
1663 public void sortByBandwidth() {
1664 quicksort(0, swarmSize-1);
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.
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);
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".
1685 private int partition(int left, int right) {
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
1694 if (i >= j) break; // check if pointers cross
1695 swap(i, j); // swap two elements into place
1697 swap(i, right); // swap with partition element
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.
1711 private boolean greater(Element x, Element y) {
1713 * Null elements and seeders are shifted at the end
1716 if (x==null) return false;
1717 if (y==null) return true;
1718 if (x.isSeeder) return false;
1719 if (y.isSeeder) return true;
1721 // if the local node is a leecher
1722 if (peerStatus==0) {
1723 if ((x.valueDOWN - x.head20) >
1724 (y.valueDOWN -y.head20))
1729 // if peerStatus==1 (the local node is a seeder)
1731 if ((x.valueUP - x.head20) >
1732 (y.valueUP -y.head20))
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
1744 private void swap(int i, int j) {
1745 Element swap = byBandwidth[i];
1746 byBandwidth[i] = byBandwidth[j];
1747 byBandwidth[j] = swap;
1750 /** Searches the node with the given ID. It does a dychotomic
1752 * @param ID ID of the node to search.
1753 * @return the {@link Element} in {@link #byPeer} which represents the node with the
1756 public Element search(long ID){
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)
1764 if( byPeer[p].ID < ID ) //Wasteful second comparison forced by syntax limitations.
1769 p = low+((high-low)/2); //Next probe position.
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}.
1782 * ID of the represented node.
1784 public long ID = Integer.MAX_VALUE;
1786 * Index position of the node in the {@link example.bittorrent.BitTorrent#cache} array.
1788 public int peer = -1;
1790 * Number of blocks uploaded to anyone since the beginning.
1792 public int valueUP = 0;
1794 * Number of blocks downloaded from anyone since the beginning.
1796 public int valueDOWN = 0;
1798 * Value of either {@link #valueUP} or {@link #valueDOWN} (depending by
1799 * {@link example.bittorrent.BitTorrent#peerStatus}) 20 seconds before.
1801 public int head20 = 0;
1803 * Value of either {@link #valueUP} or {@link #valueDOWN} (depending by
1804 * {@link example.bittorrent.BitTorrent#peerStatus}) 60 seconds before.
1806 public int head60 = 0;
1808 * <tt>true</tt> if the node is a seeder, <tt>false</tt> otherwise.
1810 public boolean isSeeder = false;
1812 * Makes a deep copy of the Element to <tt>destination</tt>
1813 * @param destination Element instance where to make the copy
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;
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}.
1831 * Reference to the node in the {@link peersim.core.Network}.
1833 public Node node = null;
1835 * -1 means not interested<br/>
1836 * Other values means the last piece number for which the node is interested.
1838 public int interested;
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.
1847 * Last time a message from the node represented has been received.
1849 public long lastSeen = 0;
1851 * Last time a message to the node represented has been sent.
1853 public long lastSent = 0;
1856 * Sets the last time the neighbor was seen.
1858 public void isAlive(){
1859 long now = CommonState.getTime();
1860 this.lastSeen = now;
1864 * Sets the last time the local peer sent something to the neighbor.
1866 public void justSent(){
1867 long now = CommonState.getTime();
1868 this.lastSent = now;
1874 * Class type of the queues's items in {@link example.bittorrent.BitTorrent#incomingPieces}
1875 * and {@link example.bittorrent.BitTorrent#requestToServe}.
1885 * Public constructor. Creates a queue of size <tt>size</tt>.
1887 public Queue(int size){
1889 queue = new Request[size];
1890 for(int i=0; i< size; i++)
1891 queue[i]= new Request();
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>
1901 public boolean enqueue(int id, Node sender){
1903 queue[tail%maxSize].id = id;
1904 queue[tail%maxSize].sender = sender;
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.
1917 public Request dequeue(){
1920 value = queue[head%maxSize];
1925 else return null; //empty queue
1929 * Returns the status of the queue.
1930 * @return <tt>true</tt> if the queue is empty, <tt>false</tt>
1933 public boolean empty(){
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>
1943 public boolean contains(int value){
1946 for(int i=head; i<head+dim; i++){
1947 if(queue[i%maxSize].id == value)
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>
1960 public boolean remove(Node sender, int value){
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];
1978 * This class represent an enqueued request of a block.
1982 * The id of the block.
1986 * The sender of the request.