btalgorithmrechoking.java

一个p2p仿真软件

/*
 * @(#)BTAlgorithmReChoking.java	ver 1.2  6/20/2005
 *
 * Copyright 2005 Weishuai Yang ([e-mail]). 
 * All rights reserved.
 * 
 */


package gps.protocol.BT.algorithm;
import gps.event.SimEvent;
import gps.event.SimEventHandler;
import gps.event.SimEventScheduler;
import gps.protocol.BT.BTEvent;
import gps.protocol.BT.BTSession;
import gps.protocol.BT.BTSocket;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.logging.Logger;

/**
 * BT Rechoking algorithm.
 * 
 * Choking is based on session rather than node.
 * i.e. it considers only connections for that file
 *
 * Choking algorithm should meet several criteria:
 * 
 * It should cap the number of simultaneous uploads for good TCP performance.
 * It should avoid choking and unchoking quickly, known as 'fibrillation'
 * It should reciprocate to peers who let it download.
 * It should try out unused connections once in a while to find out a better one, i.e. optimistic unchoking.
 * 
 * @author  Weishuai Yang
 * @version 1.2,  6/20/2005
 */
 
public class BTAlgorithmReChoking implements SimEventHandler {
	/**
	 * singleton reference to event scheduler
	 */
	protected static SimEventScheduler mScheduler=SimEventScheduler.getInstance();
	/**
	 * singleton reference to debug log
	 */
	protected static Logger mDebugLog = Logger.getLogger("Debug");
    /**
     * default peer number that each session can unchoke
     */
	public static final int DEFAULT_UNCHOKE_NUMBER=4;
    /**
     * default rechoking interval
     */
	public static final int DEFAULT_RECHOKING_INTERVAL=10; //10 sec
    /**
     * unchoke number
     */
	protected int mUnchokeNum=DEFAULT_UNCHOKE_NUMBER;
	/**
	 * rechoking interval
	 */
	protected int mUnchokeInterval=DEFAULT_RECHOKING_INTERVAL;

	/**
	 * rechoking running or not
	 */
	protected boolean mRunning=false;
	/**
	 * the session that runs the rechoking
	 */
	protected BTSession mSession=null;
	
	/**
	 * rechoking calls optimistic unchoking
	 */
	protected BTAlgorithmOptimisticUnchoking mBTAOU=null;
	
	/**
	 * downloading comprartor class
	 */
	private class InComparator implements Comparator
	{
		//sort the max at the head
		public int compare(Object c1, Object c2) {
			
			BTSocket btc1=(BTSocket)c1;
			BTSocket btc2=(BTSocket)c2;
			
			double now=mScheduler.getCurrent();
			double d1=btc1.calcInAverageSince(now-2*mUnchokeInterval);
			double d2=btc2.calcInAverageSince(now-2*mUnchokeInterval);
			if(d1>d2)
				return -1;
			else if(d1<d2)
				return 1;
			else
				return 0;
		} 
	}
	/**
	 * uploading comparator class
	 */
	private class OutComparator implements Comparator
	{
		//sort the max at the head
		public int compare(Object c1, Object c2) {
			
			BTSocket btc1=(BTSocket)c1;
			BTSocket btc2=(BTSocket)c2;
			
			double now=mScheduler.getCurrent();
			
			if(btc1.calcOutAverageSince(now-2*mUnchokeInterval)>btc2.calcOutAverageSince(now-2*mUnchokeInterval))
				return -1;
			else if(btc1.calcOutAverageSince(now-2*mUnchokeInterval)<btc2.calcOutAverageSince(now-2*mUnchokeInterval))
				return 1;
			else
				return 0;
		} 
	}

	/**
	 * downloading comparator
	 */
	private static InComparator mInComparator=null;
	/**
	 * uploading comparator
	 */
	private static OutComparator mOutComparator=null;
	
	/**
	 * constructs rechoking object
	 * @param session bt session this unchoking is working for
	 */
	public BTAlgorithmReChoking(BTSession session){
		mSession=session;	
		if(mInComparator==null)
		    mInComparator=new InComparator();
		if(mOutComparator==null)
		    mOutComparator=new OutComparator();
		
		mBTAOU=new BTAlgorithmOptimisticUnchoking(session);
	}

	/**
	 * chonstructs rechoking object with unchoke number and unchoke interveral set
	 * @param session bt session this unchoking is working for
	 * @param n unchoke number
	 * @param i unchoke intervel
	 */
	
	public BTAlgorithmReChoking(BTSession session, int n, int i){
		mSession=session;
		mUnchokeNum=n;
		mUnchokeInterval=i;
		
		if(mInComparator==null)
		    mInComparator=new InComparator();
		if(mOutComparator==null)
		    mOutComparator=new OutComparator();
		
		mBTAOU=new BTAlgorithmOptimisticUnchoking(session);
	}
	
	/**
	 * check running status
	 * @return true if running
	 */
	public boolean isRunning(){
		return mRunning;
	}
	
	/**
	 * starts rechoking
	 */
	public void run(){
		mRunning=true;
		handle(null);			
	}
	/**
	 * gets unchoke num set for this simulation
	 * @return allowed unchok numer
	 */
	public int getUnchokeNum(){
		return mUnchokeNum;
	}
	
	/**
	 * handles rechoking events
	 * @param e rechoking event
	 * @return true if already handled
	 */
	public boolean handle(SimEvent e){

	    if(mSession.mRemoved) {
	      	mRunning=false;
	      	return true;
	    }
	    
		if(!mRunning) return true;
		

		if(mSession.getConnections().size()==0){
			nextSchedule();	
			return true;
		}

	    //find out which one to unchoking.
		LinkedHashSet unchoked=mSession.getUnchokedList();
		LinkedList candidate=mSession.getPeerCandidateList();
		
		
		mDebugLog.info(mScheduler.getCurrent()+": "+mSession+" before rechoking unchoked is: "+unchoked+", candidate is: "+candidate);
		unchoked.clear();
		
		ArrayList conList=new ArrayList(mSession.getConnections().values());
		
		if(mSession.getDocument().isWhole()){
			//I'm a seed, unchoke mUnchokeNum fastest downloaders
			Collections.sort(conList, mOutComparator);
		}
		else{
			//I'm a leecher, unchoke mUnchokeNum fastest uploaders
			Collections.sort(conList, mInComparator);
		}
		
		BTSocket tmp=null;
		for(int i=0;((i<conList.size())&&(i<mUnchokeNum));i++)
		{
			tmp=(BTSocket)conList.get(i);
			if(tmp.mPeerInterested){
			    //only unchoke interested peers
				if(tmp.mAmChoking){
				    tmp.mAmChoking=false;
				    mSession.sendChoked(false, tmp.mCounterpart.mSession.getAgent());
				}
				candidate.remove(tmp.mCounterpart.mSession.getAgent());
				unchoked.add(tmp.mCounterpart.mSession.getAgent());
				//mDebugLog.info(mScheduler.getCurrent()+": "+mSession.getAgent()+" send unchoke to "+tmp.mCounterpart.mSession.getAgent()+" from rechoking");
			}
		}
		
		if(conList.size()>mUnchokeNum){

			for(int i=mUnchokeNum;i<conList.size();i++)
			{
				tmp=(BTSocket)conList.get(i);
				if(tmp.mPeerInterested){
					if(!tmp.mAmChoking){
						//mDebugLog.info(mScheduler.getCurrent()+": "+mSession.getAgent()+" send choke to "+tmp.mCounterpart.mSession.getAgent()+" from rechoking");
						mSession.sendChoked(true, tmp.mCounterpart.mSession.getAgent());
						tmp.mAmChoking=true;
					}
					if(tmp.mPeerInterested&&!candidate.contains(tmp.mCounterpart.mSession.getAgent()))			
						candidate.addLast(tmp.mCounterpart.mSession.getAgent());
				}
			}
		}
		
		mDebugLog.info(mScheduler.getCurrent()+": "+mSession+" after rechoking unchoked is: "+unchoked+", candidate is: "+candidate);

		nextSchedule();	
		return true;
	}
	
	/**
	 * sets up next rechoking event
	 */
	public void nextSchedule(){
		//schedule next rechoking envents
		ArrayList handlers=new ArrayList();
		handlers.add(this);
		handlers.add(mBTAOU);
		BTEvent bte=new BTEvent(mScheduler.getCurrent()+mUnchokeInterval, BTEvent.RECHOKING, handlers, null);
		mScheduler.enqueue(bte);
	}

	
	/**
	 * gets string description
	 * @return string description
	 */
	public String toString(){
		return "Choking Algorithm for "+mSession;
	}
}