On Sat, Oct 04, 2003 at 01:51:36PM +0100, Jonathan Howard wrote: > >Recall that in NGR we always estimate "how long will it take to get the > >data if the message is (initially) routed to this node". It is > >important that we know what the estimate *means*. I don't think that is > >the case with the equasion you give above. > > I see you don't work with sub-symbolic AI. > The importance is for determining the preferred ordering. > With another important factor being getting the net nodes working > together for optimal results, i.e. evenly distributing the load by NG > specialisation. > > I think it's agreed that the best is for t/nGlobalSuccess to be optimal. > Without any other great idea of combining results I think it's best to > go with the node with best t/nSuccess. > > >I still don't see why our current approach doesn't achieve exactly the > >effect we want it to. > The current approach is equivalent to; > pSuccess*tSuccess + pFailure*tFailure - pSuccess*tGlobalSuccess OR > The average time for any outcome - pSuccess*tGlobalSuccess > It could be good, but my real test results favour Martin's. > I think lots of unsearched nodes are pulling down the tGlobalSuccess. > Generate you own, it may be different for a better connected node. > (Just needs tweaking to remove excessive values.)
tFailure includes the full time for a successful rerequest.
>
> ------
> COULD THIS BE THE CAUSE OF POOR INSERTS?
> The unsearched nodes are comming first. Without RTFS I'm thinking that
> these are being used for routing inserts.
No. We recently changed the retry time to only include successes (which
are usually slower), the previous behaviour meant the node routed too
much to QueryRejecting nodes, which could easily have broken inserts.
And there are probably more bugs.
>
> ------
> I can't explain why some of the nodes are showing up with no data.
> Some aren't getting connected but others are and have been for some
> time. Another bug maybe.
>
> -------
> Here are the spreadsheet formulas I'm using.
> Similar to current estimate
> =L3*M3 + F3*G3 + (1-F3)*(1-J3)*H3*I3 + (1-F3)*(1-H3)*J3*K3 - L3*D3
> martin's
> =M3 + (F3*G3 + (1-F3)*(1-J3)*H3*I3 + (1-F3)*(1-H3)*J3*K3)/L3
>
>
>
> /* -*- Mode: java; c-basic-indent: 4; tab-width: 4 -*- */
> package freenet.node.rt;
>
> import freenet.Key;
> import freenet.support.DataObject;
> import freenet.support.Comparable;
> import freenet.support.StringMap;
> import freenet.support.SimpleStringMap;
> import freenet.node.NodeReference;
> import freenet.Core;
> import freenet.support.Logger;
> import freenet.support.DataObjectPending;
> import java.io.DataOutputStream;
> import java.io.DataInputStream;
> import java.io.IOException;
> import java.io.PrintWriter;
>
> class StandardNodeEstimator extends NodeEstimator {
> // Apologies for the notation, but read the estimator function!
> RunningAverage rpConnectFailed, /*rpQueryRejected,*/ rpTransferFailed,
> rpSearchFailed;
> RunningAverage rtConnectFailed, rtConnected, /*rtQueryRejected,*/
> rtTransferFailed, rtSearchFailed, rpDNF;
> TimeEstimator etSuccessSearch, etTransferRate;
> TimeEstimator epDNFGivenConnectionAndNotRejectedOrSearchFailed, etDNF;
> static final int T_SUCCESS_SEARCH = 0;
> static final int T_TRANSFER_RATE = 1;
> static final int P_DNF = 2;
> static final int T_DNF = 3;
> static final int ESTIMATORS_END = T_DNF;
> // epDNFGivenConnectionAndNotRejected - probability of DNF given that we were
> not ConnectionFailed, and not QueryRejected or otherwise searchFailed; we can still
> get transferFailed, or success, or DNF
> // tTransferRate is the rate, in bytes per second
> NGRoutingTable ngrt;
> long lastConnectTime = -1;
> long lastConnectTryTime = -1;
> long lastAccessedTime = -1;
> long lastSuccessTime = -1;
> int connectTries = 0;
> int connectSuccesses = 0;
> int consecutiveFailedConnects = 0;
> int successes = 0;
> boolean needConnection;
>
> public StandardNodeEstimator(NGRoutingTable ngrt, NodeReference ref,
> RoutingMemory mem,
> RunningAverageFactory raf,
> TimeEstimatorFactory
> rtef,
> DataObjectPending dop,
> boolean
> needConnection) throws IOException {
> Core.logger.log(this, "Serializing in StandardNodeEstimator",
> Logger.MINOR);
> this.ngrt = ngrt;
> this.ref = ref;
> this.mem = mem;
> Core.logger.log(this, "NGRT "+ngrt+", ref "+ref+", mem "+mem,
> Logger.DEBUG);
> DataInputStream dis = dop.getDataInputStream();
> Core.logger.log(this, "DataInputStream "+dis, Logger.DEBUG);
> int version = dis.readInt();
> if(version != 1) throw new IOException("Unrecognized version
> "+version);
> rpConnectFailed = raf.create(dis);
> //rpQueryRejected = raf.create(dis);
> rpTransferFailed = raf.create(dis);
> rpSearchFailed = raf.create(dis);
> rpDNF = raf.create(dis);
> rtConnectFailed = raf.create(dis);
> rtConnected = raf.create(dis);
> // rtQueryRejected = raf.create(dis);
> rtTransferFailed = raf.create(dis);
> rtSearchFailed = raf.create(dis);
> Core.logger.log(this, "Serialized in all RunningAverage's",
> Logger.DEBUG);
> etSuccessSearch = rtef.create(dis);
> Core.logger.log(this, "Serialized in etSuccessSearch",
> Logger.DEBUG);
> etTransferRate = rtef.create(dis);
> Core.logger.log(this, "Serialized in etTransferRate",
> Logger.DEBUG);
> epDNFGivenConnectionAndNotRejectedOrSearchFailed = rtef.create(dis);
> Core.logger.log(this, "Serialized in etDNF",
> Logger.DEBUG);
> etDNF = rtef.create(dis);
> Core.logger.log(this, "Serialized in "+this,
> Logger.MINOR);
> successes = dis.readInt();
> lastSuccessTime = dis.readLong();
> lastAccessedTime = dis.readLong();
> dop.resolve(this);
> Core.logger.log(this, "Resolved "+this,
> Logger.DEBUG);
> this.needConnection = needConnection;
> }
>
> /**
> * Create one from scratch for a completely new node, using insanely
> * optimistic defaults
> * @argument k the initial specialization
> */
> public StandardNodeEstimator(NGRoutingTable ngrt, NodeReference ref,
> RoutingMemory mem,
> RunningAverageFactory raf,
> TimeEstimatorFactory
> rtef, Key k,
> double
> initTransferRate,
> boolean
> needConnection) {
> this.ngrt = ngrt;
> this.ref = ref;
> this.mem = mem;
> // Set all the failure probabilities to 0
> rpConnectFailed = raf.create(0);
> // rpQueryRejected = raf.create(0);
> rpTransferFailed = raf.create(0);
> rpSearchFailed = raf.create(0);
> rpDNF = raf.create(0);
> // Set all the failure times to 0 too. It will learn soon enough.
> rtConnectFailed = raf.create(0);
> rtConnected = raf.create(0);
> // rtQueryRejected = raf.create(0);
> rtTransferFailed = raf.create(0);
> rtSearchFailed = raf.create(0);
> // Now the RTEs
> epDNFGivenConnectionAndNotRejectedOrSearchFailed =
> rtef.createZero();
> etSuccessSearch = rtef.createZero();
> etTransferRate = rtef.createInitTransfer(initTransferRate);
> etDNF = rtef.createZero();
> this.needConnection = needConnection;
> lastAccessedTime = System.currentTimeMillis();
> }
>
> public double dnfProbability() {
> return rpDNF.currentValue();
> }
>
> public double dnfProbability(Key k) {
> return epDNFGivenConnectionAndNotRejectedOrSearchFailed.
> guessProbability(k);
> }
>
> public long estimate(Key k, int htl, long size, double requestFailTime,
> double pLegitDNF) {
> System.out.print(k+"\t"+
> htl+"\t"+size+"\t"+requestFailTime+"\t"+pLegitDNF);
> double estimate = 0F;
> // First the simple failures
> // would it be better just to remove the connectionFailed stuff... edt
> double pConnectFailed = needConnection ?
> rpConnectFailed.currentValue() : 0;
> double tConnectFailed = needConnection ?
> rtConnectFailed.currentValue() : 0;
> estimate = (pConnectFailed * (tConnectFailed + requestFailTime));
> double pSearchFailed = rpSearchFailed.currentValue();
> System.out.print("\t"+pSearchFailed);
> double tSearchFailed = rtSearchFailed.currentValue();
> System.out.print("\t"+tSearchFailed);
> double pTransferFailed = rpTransferFailed.currentValue();
> System.out.print("\t"+pTransferFailed);
> double tTransferFailed = rtTransferFailed.currentValue();
> System.out.print("\t"+tTransferFailed);
> estimate += (pSearchFailed * (tSearchFailed + requestFailTime)) +
> (pTransferFailed * (tTransferFailed + requestFailTime));
> // System.out.print("\t"+(pSearchFailed * (tSearchFailed +
> requestFailTime)));
> // System.out.print("\t"+(pTransferFailed * (tTransferFailed +
> requestFailTime)));
> // DNF probability does not incorporate CF or QR
> // Now DataNotFound
> double pDNF =
> epDNFGivenConnectionAndNotRejectedOrSearchFailed.
> guessProbability(k);
> if (pDNF==0)
> pDNF = pLegitDNF;
> System.out.print("\t"+pDNF);
> double tDNF = etDNF.guessTime(k) * htl;
> System.out.print("\t"+tDNF);
> double pNotConnectFailedOrSearchFailed =
> (1 - pConnectFailed) * (1- pSearchFailed);
> estimate += pNotConnectFailedOrSearchFailed
> * (pDNF - pLegitDNF) * (tDNF + requestFailTime);
> // System.out.print("\t"+pNotConnectFailedOrSearchFailed * (pDNF -
> pLegitDNF) * (tDNF + requestFailTime));
> // Success
> double pSuccess = pNotConnectFailedOrSearchFailed
> * (1 - pDNF);
> System.out.print("\t"+pSuccess);
> if(pSuccess > 1 || pSuccess < 0) {
> Core.logger.log(this, "pSuccess = "+pSuccess, Logger.ERROR);
> return Long.MAX_VALUE;
> }
> double tSuccess =
> etSuccessSearch.guessTime(k) + ((double)size) /
> etTransferRate.guessTransferRate(k);
> System.out.print("\t"+tSuccess);
> estimate += pSuccess * tSuccess;
> System.out.print("\t"+estimate+"\n");
>
> /* Core.logger.log(this, "rFT "+requestFailTime
> +" "+needConnection+" "+pConnectFailed+" "+tConnectFailed
> +" "+pSearchFailed+" "+tSearchFailed
> +" "+pTransferFailed+" "+tTransferFailed
> +" "+pDNF+" "+tDNF+" "+pLegitDNF
> +" "+tSuccess+" "+estimate,
> Logger.NORMAL);
> */
> return (long)estimate;
> }
>
> public void routeConnected(long time) {
> lastConnectTime = lastConnectTryTime = System.currentTimeMillis();
> connectTries++;
> connectSuccesses++;
> consecutiveFailedConnects = 0;
> rpConnectFailed.report(0);
> rtConnected.report(time);
> Core.logger.log(this, "Connected in "+time+"ms on "+ref,
> new Exception("debug"), Logger.DEBUG);
> lastAccessedTime = System.currentTimeMillis();
> }
>
> public void connectFailed(long time) {
> lastConnectTryTime = System.currentTimeMillis();
> connectTries++;
> consecutiveFailedConnects++;
> rpConnectFailed.report(1);
> rtConnectFailed.report(time);
> Core.logger.log(this, "Connect failed in "+time+"ms on "+ref,
> new Exception("debug"), Logger.DEBUG);
> }
>
> public void searchFailed(long time) {
> rpSearchFailed.report(1);
> rtSearchFailed.report(time);
> Core.logger.log(this, "Search failed in "+time+"ms on "+ref,
> new Exception("debug"), Logger.DEBUG);
> lastAccessedTime = System.currentTimeMillis();
> }
>
> public void transferFailed(Key key, long time, long size) {
> rpTransferFailed.report(1);
> rpSearchFailed.report(0); // the search succeeded
> epDNFGivenConnectionAndNotRejectedOrSearchFailed.
> reportProbability(key, 0);
> rpDNF.report(0.0);
> // transferFailed is a peer event to dataNotFound, transferSucceeded
> // and searchFailed
> rtTransferFailed.report(time);
> Core.logger.log(this, "Transfer failed in "+time+"ms ("+
> size+" bytes) on "+ref, new
> Exception("debug"),
> Logger.DEBUG);
> lastAccessedTime = System.currentTimeMillis();
> }
>
> public void dataNotFound(Key key, long searchTime, int htl) {
> epDNFGivenConnectionAndNotRejectedOrSearchFailed.
> reportProbability(key, 1.0F);
> rpDNF.report(1.0);
> rpSearchFailed.report(0); // the search succeeded
> // htl IS > 0
> etDNF.reportTime(key, searchTime/htl);
> Core.logger.log(this, "Data Not Found in "+searchTime+"ms on "+ref,
> new Exception("debug"), Logger.DEBUG);
> lastAccessedTime = System.currentTimeMillis();
> }
>
> public void transferSucceeded(Key key, long searchTime, int htl,
> long size, long
> transferTime) {
> successes++;
> lastSuccessTime = System.currentTimeMillis();
> epDNFGivenConnectionAndNotRejectedOrSearchFailed.
> reportProbability(key, 0);
> rpDNF.report(0.0);
> etSuccessSearch.reportTime(key, searchTime);
> rpSearchFailed.report(0); // the search succeeded
> rpTransferFailed.report(0); // the transfer succeeded
> if(size > 0 && transferTime > 0) {
> etTransferRate.reportTransferRate(key, ((double)size) /
>
> (double)transferTime);
> } else {
> Core.logger.log(this, "Not logging transfer rate because
> size="+
> size+",
> transferTime="+transferTime,
> new Exception("debug"),
> Logger.NORMAL);
> }
> Core.logger.log(this, "Transfer succeeded in "+transferTime+
> "ms on "+ref, Logger.DEBUG);
> lastAccessedTime = System.currentTimeMillis();
> }
>
> public int getDataLength() {
> return rpConnectFailed.getDataLength() +
> // rpQueryRejected.getDataLength() +
> rpTransferFailed.getDataLength() +
> rpSearchFailed.getDataLength() +
> rpDNF.getDataLength() +
> rtConnectFailed.getDataLength() +
> rtConnected.getDataLength() +
> // rtQueryRejected.getDataLength() +
> rtTransferFailed.getDataLength() +
> rtSearchFailed.getDataLength() +
> etSuccessSearch.getDataLength() +
> etTransferRate.getDataLength() +
>
> epDNFGivenConnectionAndNotRejectedOrSearchFailed.getDataLength() +
> etDNF.getDataLength();
> }
>
> public long lastConnectTime() {
> return lastConnectTime;
> }
>
> public long lastConnectTryTime() {
> return lastConnectTryTime;
> }
>
> public int successes() {
> return successes;
> }
>
> public long lastSuccessTime() {
> return lastSuccessTime;
> }
>
> public int connectTries() {
> return connectTries;
> }
>
> public int connectSuccesses() {
> return connectSuccesses;
> }
>
> public int consecutiveFailedConnects() {
> return consecutiveFailedConnects;
> }
>
> public long lastAccessedTime() {
> return lastAccessedTime;
> }
>
> public void toHtml(PrintWriter pw, String imagePrefix)
> throws IOException {
> String nodename = ref.firstPhysicalToString();
> pw.println("<html><head><title>Node status: "+nodename+
> "</title></head><body>");
> pw.println("<h1>Status for "+nodename+"</h1>");
> pw.println("<table border=\"0\">");
> pw.println("<tr><td>Last connected</td>");
> long now = System.currentTimeMillis();
> pw.println("<td>"+(lastConnectTime == -1 ? "never" :
> (Long.toString((now -
> lastConnectTime)/1000)+"s ago"))+
> "</td></tr>");
> pw.println("<tr><td>Last attempted</td>");
> pw.println("<td>"+(lastConnectTryTime == -1 ? "never" :
> (Long.toString((now -
> lastConnectTryTime)/1000)+"s ago"))+
> "</td></tr>");
> pw.println("<tr><td>Connection attempts</td>");
> pw.println("<td>"+connectTries+"</td></tr>");
> pw.println("<tr><td>Connection successes</td>");
> pw.println("<td>"+connectSuccesses+"</td></tr>");
> pw.println("<tr><td>Consecutive failed connections</td>");
> pw.println("<td>"+consecutiveFailedConnects+"</td></tr>");
> pw.println("<tr><td>Probability of connection failure</td>");
> pw.println("<td>"+rpConnectFailed.currentValue()+"</td></tr>");
> pw.println("<tr><td>Estimated time for connection failure</td>");
>
> pw.println("<td>"+(int)(rtConnectFailed.currentValue())+"ms</td></tr>");
> pw.println("<tr><td>Estimated time for connection success</td>");
> pw.println("<td>"+(int)(rtConnected.currentValue())+"ms</td></tr>");
> pw.println("<tr><td>Probability of search failure (QueryReject or
> timeout)</td>");
> pw.println("<td>"+rpSearchFailed.currentValue()+"</td></tr>");
> pw.println("<tr><td>Estimated time for search failure</td>");
> pw.println("<td>"+(int)(rtSearchFailed.currentValue())+"ms</td></tr>");
> pw.println("<tr><td>Probability of transfer failure</td>");
> pw.println("<td>"+rpTransferFailed.currentValue()+"</td></tr>");
> pw.println("<tr><td>Estimated time for transfer failure</td>");
>
> pw.println("<td>"+(int)(rtTransferFailed.currentValue())+"ms</td></tr>");
> pw.println("<tr><td>Overall probability of DataNotFound</td>");
> pw.println("<td>"+rpDNF.currentValue()+"</td></tr>");
> pw.println("<tr><td>Successful transfers</td>");
> pw.println("<td>"+successes+"</td></table>");
> pw.println("<h2>Estimators</h2>");
> for(int i=0;i<=ESTIMATORS_END;i++) {
> pw.println(graphName(i)+"<br>");
> TimeEstimator te = getEstimator(i);
> int et = estimatorType(i);
> pw.println("Minimum: "+te.formatFromRaw(te.lowestRaw(), et)+
> "<br>");
> pw.println("Maximum: "+te.formatFromRaw(te.highestRaw(), et)+
> "<br>");
> te.dumpHtml(pw);
> pw.println("<img src=\""+imagePrefix+graphName(i)+
> "\" width=\"640\" height=\"480\"><br>");
> }
> pw.println("</table></body></html>");
> pw.flush();
> }
>
> public int estimatorType(int estimator) {
> switch(estimator) {
> case T_SUCCESS_SEARCH:
> case T_DNF:
> return TimeEstimator.TIME;
> case P_DNF:
> return TimeEstimator.PROBABILITY;
> case T_TRANSFER_RATE:
> return TimeEstimator.TRANSFER_RATE;
> }
> throw new IllegalArgumentException();
> }
>
> public String graphName(int g) {
> switch(g) {
> case T_SUCCESS_SEARCH:
> return "tSuccessSearch";
> case T_TRANSFER_RATE:
> return "tTransferRate";
> case P_DNF:
> return "pDNF";
> case T_DNF:
> return "tDNF";
> default:
> return null;
> }
> }
>
> public int graphType(String graphName) {
> if(graphName.equals("tSuccessSearch"))
> return T_SUCCESS_SEARCH;
> else if(graphName.equals("tTransferRate"))
> return T_TRANSFER_RATE;
> else if(graphName.equals("pDNF"))
> return P_DNF;
> else if(graphName.equals("tDNF"))
> return T_DNF;
> else return -1;
> }
>
> public TimeEstimator getEstimator(int type) {
> switch(type) {
> case T_SUCCESS_SEARCH:
> return etSuccessSearch;
> case T_TRANSFER_RATE:
> return etTransferRate;
> case P_DNF:
> return epDNFGivenConnectionAndNotRejectedOrSearchFailed;
> case T_DNF:
> return etDNF;
> default:
> return null;
> }
> }
>
> public void writeTo(DataOutputStream out) throws IOException {
> out.writeInt(1); // version number
> rpConnectFailed.writeTo(out);
> // rpQueryRejected.writeTo(out);
> rpTransferFailed.writeTo(out);
> rpSearchFailed.writeTo(out);
> rpDNF.writeTo(out);
> rtConnectFailed.writeTo(out);
> rtConnected.writeTo(out);
> // rtQueryRejected.writeTo(out);
> rtTransferFailed.writeTo(out);
> rtSearchFailed.writeTo(out);
> etSuccessSearch.writeTo(out);
> etTransferRate.writeTo(out);
> epDNFGivenConnectionAndNotRejectedOrSearchFailed.writeTo(out);
> etDNF.writeTo(out);
> out.writeInt(successes);
> out.writeLong(lastSuccessTime);
> out.writeLong(lastAccessedTime);
> }
>
> private final static String[] REF_PROPERTIES =
> { "Address", "Connection Probability", "Consecutive Failures",
> "Connection Attempts", "Successful Connections",
> "Last Attempt", "Successful Transfers", "Connection Fail Time",
> "Connection Success Time", "NodeReference", "Node Version",
> "Search died probability", "Transfer died probability",
> "Search died time",
> "Open Outbound Connections", "Open Inbound Connections" };
>
> static class MyComparableStringMap
> extends SimpleStringMap implements ComparableStringMap {
> public MyComparableStringMap(Object[] values) {
> super(REF_PROPERTIES, values);
> }
>
> public int compareTo(Object o) {
> MyComparableStringMap sm = (MyComparableStringMap)o;
> // Connected nodes go at the top
> if(openConnections() == 0 && sm.openConnections() > 0)
> return 1;
> if(openConnections() > 0 && sm.openConnections() == 0)
> return -1;
> // Next sort by successes
> if(successes() < sm.successes())
> return 1;
> if(successes() > sm.successes())
> return -1;
> return 0;
> }
>
> protected int openConnections() {
> Integer outboundConnections = (Integer)objs[14];
> Integer inboundConnections = (Integer)objs[15];
> return outboundConnections.intValue() +
> inboundConnections.intValue();
> }
>
> protected int successes() {
> Integer successes = (Integer)objs[6];
> return successes.intValue();
> }
>
> public boolean equals(Object o) {
> if(o instanceof MyComparableStringMap)
> return compareTo(o) == 0;
> else return false;
> }
> }
>
> public ComparableStringMap getDiagProperties() {
> Object[] values = new Object[REF_PROPERTIES.length];
> values[0] = ref.firstPhysicalToString();
> values[1] = new Float(1.0 - rpConnectFailed.currentValue());
> values[2] = new Long(consecutiveFailedConnects);
> values[3] = new Long(connectTries);
> values[4] = new Long(connectSuccesses);
> long now = System.currentTimeMillis();
> long secsSinceLastAttempt = -1;
> if(connectTries > 0) {
> secsSinceLastAttempt = (now - lastConnectTryTime) / 1000;
> }
> values[5] = new Long(secsSinceLastAttempt);
> values[6] = new Integer(successes);
> values[7] = new Integer((int)rtConnectFailed.currentValue());
> values[8] = new Integer((int)rtConnected.currentValue());
> values[9] = ref;
> values[10] = ref.getVersion();
> values[11] = new Float(rpSearchFailed.currentValue());
> values[12] = new Float(rpTransferFailed.currentValue());
> values[13] = new Float(rtSearchFailed.currentValue());
> values[14] =
> new Integer(ngrt.countOutboundConnections(ref.getIdentity()));
> values[15] =
> new Integer(ngrt.countInboundConnections(ref.getIdentity()));
> return new MyComparableStringMap(values);
> }
> }
> _______________________________________________
> Devl mailing list
> [EMAIL PROTECTED]
> http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
--
Matthew J Toseland - [EMAIL PROTECTED]
Freenet Project Official Codemonkey - http://freenetproject.org/
ICTHUS - Nothing is impossible. Our Boss says so.
signature.asc
Description: Digital signature
_______________________________________________ Devl mailing list [EMAIL PROTECTED] http://dodo.freenetproject.org/cgi-bin/mailman/listinfo/devl
