SP.rar_gossip_gossip network_gossip协议

package newscast; import peersim.util.*; import peersim.core.*; import peersim.config.*; import peersim.cdsim.*; public class ReducedNewscast implements CDProtocol, Linkable { // =============== static fields ======================================= // ===================================================================== // We are using static temporary arrays to avoid garbage collection // of them. these are used by all SimpleNewscast protocols included // in the protocol array so its size is the maximum of the cache sizes /** Temp array for merging. Its size is the same as the cache size. */ protected static Node[] tn; /** Temp array for merging. Its size is the same as the cache size. */ protected static int[] ts; /** Identifier of the linkable protocol used as support */ private static int linkID; /** config parameter name for the cache size */ public static final String PAR_CACHE = "cache"; /** config parameter name for the cache size */ public static final String PAR_LINK = "linkableID"; // =================== fields ========================================== // ===================================================================== /** Neighbors currently in the cache */ protected Node[] cache; /** Time stamps currently in the cache */ protected int[] tstamps; /** True if active */ protected boolean active; // ====================== initialization =============================== // ===================================================================== public ReducedNewscast(String n) { final int cachesize = Configuration.getInt(n+"."+PAR_CACHE); linkID = Configuration.getPid(n+"."+PAR_LINK); if(ReducedNewscast.tn == null || ReducedNewscast.tn.length < cachesize) { ReducedNewscast.tn = new Node[cachesize]; ReducedNewscast.ts = new int[cachesize]; } cache = new Node[cachesize]; tstamps = new int[cachesize]; active=true; } // --------------------------------------------------------------------- public Object clone() throws CloneNotSupportedException { ReducedNewscast sn = (ReducedNewscast)super.clone(); sn.cache = new Node[cache.length]; sn.tstamps = new int[tstamps.length]; //System.arraycopy(cache, 0, sn.cache, 0, cache.length); //System.arraycopy(tstamps, 0, sn.tstamps, 0, tstamps.length); sn.active = true; return sn; } // ====================== helper methods ============================== // ==================================================================== /** * Returns a peer node which is accessible (has ok fail state). * This implementation starts with a random node. * If that is not reachable, proceed first towards * the older and then younger nodes until the first reachable is found. * @return null if no accessible peers are found, the peer otherwise. */ protected Node getPeer() { final int d = _degree(); //System.out.println(d); if( d == 0 ) return null; int index = CommonRandom.r.nextInt(d); Node result = cache[index]; if( result.isUp() ) return result; // proceed towards older entries for(int i=index+1; i<d; ++i) if( cache[i].isUp() ) return cache[i]; // proceed towards younger entries for(int i=index-1; i>=0; --i) if( cache[i].isUp() ) return cache[i]; // no accessible peer return null; } // -------------------------------------------------------------------- /** * Merge the content of two nodes and adds a new version of * the identifier. The result is in the static temporary arrays. * The first element is not defined, it is reserved for the freshest * new updates so it will be different for peer and this. * The elements of the static temporary arrays will not contain neither * peerNode nor thisNode. * @param thisNode the node that hosts this newscast protocol instance (process) * @param peer The peer with which we perform cache exchange * @param peerNode the node that hosts the peer newscast protocol instance * @param timestamp the timestamp now */ protected void merge( Node thisNode, ReducedNewscast peer, Node peerNode, int timestamp ) { int i1 = 0; /* Index first cache */ int i2 = 0; /* Index second cache */ boolean first; boolean lastTieWinner = CommonRandom.r.nextBoolean(); int i = 1; // Index new cache. first element set in the end // SimpleNewscast.tn[0] is always null. it's never written anywhere final int d1 = _degree(); final int d2 = peer._degree(); // cachesize is cache.length // merging two arrays while( i < cache.length && i1 < d1 && i2 < d2 ) { if( tstamps[i1] == peer.tstamps[i2] ) { lastTieWinner = first = !lastTieWinner; } else { first = tstamps[i1] > peer.tstamps[i2]; } if( first ) { if( cache[i1] != peerNode && !ReducedNewscast.contains( i, cache[i1] ) ) { ReducedNewscast.tn[i] = cache[i1]; ReducedNewscast.ts[i] = tstamps[i1]; i++; } i1++; } else { if( peer.cache[i2] != thisNode && !ReducedNewscast.contains( i, peer.cache[i2] ) ) { ReducedNewscast.tn[i]=peer.cache[i2]; ReducedNewscast.ts[i]=peer.tstamps[i2]; i++; } i2++; } } // if one of the original arrays got fully copied into // tn and there is still place, fill the rest with the other // array if( i < cache.length ) { // only one of the for cycles will be entered for(; i1<d1 && i<cache.length; ++i1) { if( cache[i1] != peerNode && !ReducedNewscast.contains( i, cache[i1] ) ) { ReducedNewscast.tn[i] = cache[i1]; ReducedNewscast.ts[i] = tstamps[i1]; i++; } } for(; i2<d2 && i<cache.length; ++i2) { if( peer.cache[i2] != thisNode && !ReducedNewscast.contains( i, peer.cache[i2] ) ) { ReducedNewscast.tn[i]=peer.cache[i2]; ReducedNewscast.ts[i]=peer.tstamps[i2]; i++; } } } // if the two arrays were not enough to fill the buffer // fill in the rest with nulls if( i < cache.length ) { for(; i<cache.length; ++i) { ReducedNewscast.tn[i] = null; } } //if(testNode==null)testNode=peerNode; //if(peerNode==testNode) System.out.println(CommonState.getTime()); } //private static Node testNode=null; // -------------------------------------------------------------------- protected static boolean contains(int size, Node peer) { for (int i=0; i < size; i++) { if (ReducedNewscast.tn[i] == peer) return true; } return false; } // -------------------------------------------------------------------- /** Normally it does the same as {@link #degree}. It is necessary to allow * other implementations of {@link #degree} in extending classes which fool * the system into * thinking that the graph is different from what it is. Methods of this class * should use this as degree.*/ protected int _degree() { int len = cache.length-1; while(len>=0 && cache[len]==null) len--; return len+1; } // ====================== Linkable implementation ===================== // ==================================================================== /** * Does not check if the index is out of bound * (larger than {@link #degree()}) */ public Node getNeighbor(int i) { return cache[i]; } //-------------------------------------------------------------------- public void removeNeighbor(int i) { int len = cache.length-1; while(len>=0 && cache[len]==null) len--; cache[i] = cache[len]; tstamps[i] = tstamps[len]; cache[len] = null; } public void removeNeighbor(Node node) { int len = cache.length-1; while(len>=0 && cache[len]==null) len--; if (len >= 0) { int where = len; while (where>=0 && cache[where]!=node) where--; if (where >= 0) { cache[where] = cache[len]; tstamps[where] = tstamps[len]; cache[len] = null; return; } } //System.out.print("X"); } public void reset(No