btalgorithmpieceselection.java

p2p仿真

/*
 * @(#)BTAlgorithmPieceSelection.java	 ver 1.0  5/10/2005
 *
 * Copyright 2005 Weishuai Yang ([e-mail]). 
 * All rights reserved.
 * 
 */


package gps.protocol.BT.algorithm;
import gps.event.SimEventScheduler;
import gps.protocol.BT.BTDocument;
import gps.protocol.BT.BTPeer;
import gps.protocol.BT.BTSession;
import gps.protocol.BT.BTSocket;
import gps.Simulator;

import java.util.ArrayList;
import java.util.Random;
import java.util.TreeSet;
import java.util.logging.Logger;

/**
 * selects a suitable piece to request.
 * 
 * BitTorrent uses strict priority as a first policy for piece 
 * selection, i.e., once a single sub-piece has been requested, 
 * the remaining sub-pieces from that particular piece are 
 * requested before sub-pieces from any other piece. This does 
 * a good job of getting complete pieces as quickly as possible. 
 *
 * When selecting which piece to start downloading next, peers 
 * generally download pieces which the fewest of their own peers 
 * have first, a technique referred to as 'rarest first'. 
 *     
 * An exception to rarest first is when downloading starts. At 
 * that time, the peer has nothing to upload, so it's important 
 * to get a complete piece as quickly as possible. Rare pieces 
 * are generally only present on one peer, so they would be 
 * downloaded slower than pieces which are present on multiple 
 * peers for which it's possible to download sub-pieces from 
 * different places. For this reason, pieces to download are 
 * selected at random until the first complete piece is assembled, 
 * and then the strategy changes to rarest first.
 *
 * once all sub-pieces which a peer doesn't have are actively being 
 * requested, it sends requests for all sub-pieces to all peers. 
 * Cancels are set for sub-pieces which arrive to keep too much 
 * bandwidth from being wasted on redundant sends.
 * 
 * 
 * @author  Weishuai Yang
 * @version 1.0,  5/10/2005
 */

public class BTAlgorithmPieceSelection {
	
	/**
	 * singleton reference to event scheduler
	 */
	protected static SimEventScheduler mScheduler=SimEventScheduler.getInstance();
	/**
	 * singleton reference to debug log
	 */
	protected static Logger mDebugLog = Logger.getLogger("Debug");
	
	/**
	 * random number generator
	 */
	protected  Random random=null;
	
	/**
	 * constructs a piece selection object
	 * @param n seed for random object
	 */

	public BTAlgorithmPieceSelection(int n){
		random=new Random(n+Integer.parseInt(Simulator.getInstance().getProperties().getProperty("RandomSeed")));
		}
	
	/**
	 * select a suitable piece for request
	 * @param bts downloading session
	 * @param p bt peer from which to request
	 * @return selected piece index, negative if can't find one
	 */
	
	public int selectPiece(BTSession bts, BTPeer p){
	    //note: the slection must be specific to a peer
		//mDebugLog.info(mScheduler.getCurrent()+": "+bts.getAgent()+" trying to select a piece to download form "+p);

	 	
	 	final class RareNode implements Comparable{
 	        public RareNode(int k, int p){
 	            key=k;
 	            pieceindex=p;
 	        }
 	        public int key=0;
 	        public int pieceindex=0;
 	        public int compareTo(Object o) {
 	            if(key<((RareNode)o).key)
 	                return -1;
 	            else if(key==((RareNode)o).key){
 	            	//I don't want it totally sorted!
 	                return 0;
 	            }
 	            else return 1;
 	        }
 	    }
	 		
		BTDocument btd=bts.getDocument();
	 	//the connection to that peer
	 	BTSocket btc=bts.getConnection(p);
	 	
	 	
	 	//print pieces both nodes have
	 	//pieces this node already has
	 	boolean pieces[]=btd.getPieces();
	 	
	 	//pieces peer node has
	 	boolean peerPieces[]=btc.mBitField;
	 	/*
	 	StringBuffer sb=new StringBuffer(bts.getAgent()+"Pieces that "+bts.getAgent()+" has: ");
		for(int i=0;i<pieces.length;i++){
		    if(pieces[i]){
		        sb.append(i+" ");
		    }
		}
		
		sb.append("||| Pieces that "+p+" has: ");
		for(int i=0;i<peerPieces.length;i++){
		    if(peerPieces[i]){
		        sb.append(i+" ");
		    }
		}
		
		mDebugLog.info(mScheduler.getCurrent()+": "+sb.toString());
	 	*/
	 	
	 	//construct a list with pure ready pieces on the counterpart
	 	ArrayList morePieces=btc.comparePieces();

	 	//the counterpart doesn't have any piece for downloading
	 	if(morePieces.isEmpty()){
	 	   //mDebugLog.info(mScheduler.getCurrent()+": "+bts.getAgent()+" the counterpart "+p+" doesn't have more piece for downloading");
	 	    //System.out.println(mScheduler.getCurrent()+": "+bts.getAgent()+" the counterpart "+p+" doesn't have more piece for downloading");
	 	    return -1;
	 	}
	 	    

		/*
		StringBuffer sb2=new StringBuffer(bts.getAgent()+" Pieces that "+p+" have more: ");
		for(int i=0;i<morePieces.size();i++){
		        sb2.append(morePieces.get(i)+" ");
		}
		mDebugLog.info(mScheduler.getCurrent()+": "+sb2.toString());
		*/





		ArrayList partialList=btd.getPartialIndex();

		int partialNum=partialList.size();
		
		int particialCursor=0;
		int pieceCursor=0;
		
		/*
 		//some piece already get part, need to finish first
 		if(partialNum<downloading.size()){
 			mDebugLog.severe(mScheduler.getCurrent()+": partial pieces number is less than downloading number!!!");
 			return -1;
 		}
 		*/

		//totally random to find the first piece to download
	 	if(btd.isEmpty()&&(partialNum==0)){
	 		//if somebody is downloading, partial num can't be 0
		 	int index=random.nextInt();
		 	if(index<0) index=-index;
			//check other connections
		 	index=index%morePieces.size();
		 	int ret=((Integer)morePieces.get(index)).intValue();
		 	
		 	//mDebugLog.info(mScheduler.getCurrent()+": "+bts.getAgent()+" selected random piece "+ret+" to download from "+p);
		 	return ret;	
	 	}
	 	
	 	int selected = -2;
	 	
 		if(partialNum!=0){
 		 //try to find a partial piece   
 		    /*
 		    StringBuffer sb3=new StringBuffer(mScheduler.getCurrent()+": "+bts.getAgent()+" checking partial list ");
 		    for(int j=0;j<partialList.size();j++)
 		       sb3.append(" "+(Integer)partialList.get(j));
 		    mDebugLog.info(sb3.toString());	
			
 		    StringBuffer sb4=new StringBuffer(mScheduler.getCurrent()+": "+bts.getAgent()+" checking connection list ");
			for(int i=0; i<connectionList.size();i++){
				btc=(BTSocket)connectionList.get(i);
			    sb4.append(" "+btc+" "+btc.mRequestingPieceIndex);
			}
 		    mDebugLog.info(sb4.toString());	
 		    */
 		    
 		    
 		    for(int j=0;j<partialList.size();j++){
 		    	//if the piece in paritiallist is not included in more piece list, continue
 		        if(!morePieces.contains((Integer)partialList.get(j)))
 		            continue;
 		        
 		        //verify that it's not currently being downloaded
 		        selected=((Integer)partialList.get(j)).intValue();
 		        
		 		if(!btd.inDownloadingSet(selected)){
		 		    //mDebugLog.info(mScheduler.getCurrent()+": "+bts.getAgent()+" selected partial piece "+selected+" to download from "+p);	
		 			return selected;
		 		}
		 		else selected=-2;
 		    }
 		} 		
 	    
 		//no partial piece can be selected to download, have to find from rarest first
 		//rarelist already excluded the partial list
 		TreeSet rareSet=new TreeSet();
 		java.util.Collections.shuffle(morePieces,random);
 		for(int i=0;i<morePieces.size();i++){
 		    if(!partialList.contains(morePieces.get(i)))
 		       rareSet.add(new RareNode(bts.countPeersWithPiece(i), ((Integer)morePieces.get(i)).intValue()));
 		} 		
 		
 		ArrayList rareList=new ArrayList(rareSet);
		
 		//System.out.println("morePieces size "+morePieces.size()+"rareSet size "+rareSet.size()+" rareList size:"+rareList.size());

		/*
 		StringBuffer sb5=new StringBuffer(mScheduler.getCurrent()+": "+bts.getAgent()+" checking rarest list(size "+rareList.size()+") :");
		   for(int i=0; i<rareList.size();i++){
		        sb5.append(((RareNode)rareList.get(i)).pieceindex+"("+((RareNode)rareList.get(i)).key+")");
		   }
	 	
	 	mDebugLog.info(sb5.toString());	
		*/

	    for(int j=0;j<rareList.size();j++){
	        //verify that it's not currently being downloaded
			selected=((RareNode)rareList.get(j)).pieceindex;
			if(!btd.inDownloadingSet(selected)){
			    //mDebugLog.info(mScheduler.getCurrent()+": "+bts.getAgent()+" selected partial piece "+selected+" to download from "+p);	
				return selected;
			}
			else selected=-3;
	    }
	    
	    //mDebugLog.info(mScheduler.getCurrent()+": "+bts.getAgent()+" selected rarest piece "+selected+" to download from "+p);
	 	
		return selected;
	 } 
}