/* * $Id: CDNMaster.java,v 1.3 2008/07/08 04:49:04 nemo Exp $ * * Copyright (c) 2008, Nemo Semret. * */ package edu.columbia.ee.e6773; import java.util.Vector; import java.util.Enumeration; import java.util.StringTokenizer; import java.util.Hashtable; import java.util.Collections; import java.util.Random; /** * Main application to run the game. * http://www.ee.columbia.edu/~nemo/teaching/Content_Delivery_Game.html * @author Nemo Semret */ public class CDNMaster { static double lambda = 0.0001; static double alpha = 2.0; static double xmin = 536870912; static boolean verbose; static public void main(String argv[]) throws Exception { StringTokenizer st; Hashtable args = new Hashtable(); Random rand = new Random(System.currentTimeMillis()); for (int i = 0; i < argv.length; i++) { st = new StringTokenizer(argv[i], "="); args.put(st.nextToken(), st.hasMoreTokens() ? st.nextToken() : ""); } int T = Integer.parseInt((String) args.get("T")); verbose = (args.get("v") != null); boolean evolution = (args.get("e") != null); Vector players = loadPlayers(); for (int day = 0; day < T; day++) { executeDay(players); System.out.println(); if (evolution) { // at most one player gets cloned, with probab .01, .0001, .. Collections.sort(players); for(int i=0; i< players.size(); i++) { if (rand.nextDouble() < 0.01) { clonePlayer(players, i); break; } } } } Collections.sort(players); double TU = 0; PlayerContainer p; Hashtable popCount = new Hashtable(); String className; Object count; for (int i=0; i < players.size(); i++) { p = (PlayerContainer) players.elementAt(i); TU += p.U; System.out.println(p); if (evolution) { className = p.agent.getClass().getName(); count = popCount.get(className); if (count == null) { count = new Integer(1); } else { count = new Integer(((Integer) count).intValue()+1); } popCount.put(className, count); } } System.out.println(String.format("Sc=%.2f\tTU=%.2f\tN=%d", new Double(CDNAgent.Sc), new Double(TU), new Integer(players.size()))); if (evolution) { System.out.println(popCount); } } static Vector loadPlayers() { Vector players = new Vector(); players.add(new PlayerContainer(new CDAgent_ag2672())); players.add(new PlayerContainer(new CDNAgent_GSchenato())); players.add(new PlayerContainer(new CDNAgent_ci2137())); players.add(new PlayerContainer(new Xavier())); players.add(new PlayerContainer(new AdaptMix())); return players; } static void clonePlayer(Vector players, int i) throws InstantiationException, IllegalAccessException { PlayerContainer p = (PlayerContainer) players.elementAt(i); players.add(new PlayerContainer(p.agent.getClass().newInstance())); if (verbose) System.err.println("Cloned " + p.name + " " + players.size()); } static double [] executeDay(Vector players) { int N = players.size(); long[][] b = new long[N][CDNAgent.K]; long[][] c = new long[N][CDNAgent.K]; // start day long X = (long) net.invisiblehand.math.Misc.powerLawRV(alpha, xmin); if (verbose) System.err.println("X=" + X); Enumeration pe = players.elements(); Vector actions = new Vector(); int[] m = new int [CDNAgent.K]; // cache copies in network k while(pe.hasMoreElements()) { boolean[] a = (boolean [])((PlayerContainer) pe.nextElement()).agent.startDay(X); for (int k=0; k < a.length; k++) { if (a[k]) m[k]++; } actions.addElement(a); } // course of day long D[] = new long[CDNAgent.K]; // users in network k double[] U = new double[N]; for (int i=0; i < N; i++) { U[i] = 0; } for (int k = 0; k < CDNAgent.K; k++) { D[k]= (long) net.invisiblehand.math.Misc.exponentialRV(lambda); long checksum = 0; double download_demand = D[k] * (m[k] > 0 ? (1.0 - CDNAgent.q) : 1.0); boolean kcongested = download_demand*X*8 >= CDNAgent.C[k]*60*60*24*1000000; if (verbose) System.err.println("k=" + k + " m=" + m[k]+ " D=" + D[k]+ (kcongested ? " !" : "")); for (int i = 0; i < N; i++) { if(((boolean[])actions.elementAt(i))[k]) { // player i cached on network k c[i][k] = (long) (D[k]*CDNAgent.q/m[k]); // cache hits for player i checksum += c[i][k]; U[i] += (c[i][k] * CDNAgent.V); U[i] -= (CDNAgent.Pc * X/1073741824.0 + CDNAgent.Sc); } else { c[i][k] = 0; } b[i][k] = (long) (download_demand / N); // downloads for player i if (!kcongested) { U[i] += (b[i][k] * CDNAgent.V); } U[i] -= (CDNAgent.Pb * b[i][k] * X/1073741824.0); checksum += b[i][k]; } if (verbose && ((D[k] - checksum) * 1.0/D[k] > 0.01)) // rounding error System.err.println("D[" + k + "] = " + D[k] + " != " + checksum); } // end of day long[] bi; long[] ci; PlayerContainer p; for (int i=0; i < N; i++) { bi = new long[CDNAgent.K]; ci = new long[CDNAgent.K]; for (int k=0; k < CDNAgent.K; k++) { bi[k] = b[i][k]; ci[k] = c[i][k]; } p = (PlayerContainer) players.elementAt(i); p.agent.endDay(bi, ci); p.U += U[i]; p.days++; printPlayerDay(p, bi, ci, U[i]); } return U; } static void printPlayerDay(Object player, long[] bi, long[] ci, double Ui) { StringBuffer s = new StringBuffer(); s.append(((PlayerContainer) player).name); s.append("\t"); for (int k = 0; k < bi.length; k++) { s.append(bi[k]); if (k < bi.length - 1) s.append(","); else s.append("\t"); } for (int k = 0; k < ci.length; k++) { s.append(ci[k]); if (k < ci.length - 1) s.append(","); else s.append("\t"); } s.append(String.format("%.2f", new Double(Ui))); System.out.println(s.toString()); } } class PlayerContainer implements Comparable { double U; CDNAgent agent; String name; int days; PlayerContainer(CDNAgent a) { U = 0; days = 0; agent = a; StringBuffer s = new StringBuffer(); StringTokenizer st = new StringTokenizer(a.toString(), "."); while(st.hasMoreTokens()) name = st.nextToken(); } public String toString() { return String.format("%s\t%15.2f\t%d", name, new Double(U), days); } /** Sort by U */ public int compareTo(Object x) { return (int) (U - ((PlayerContainer) x).U); } }