Author: mrogers
Date: 2006-08-20 22:58:19 +0000 (Sun, 20 Aug 2006)
New Revision: 10220
Added:
trunk/apps/load-balancing-sims/phase6/
trunk/apps/load-balancing-sims/phase6/CongestionWindow.java
trunk/apps/load-balancing-sims/phase6/Node.java
trunk/apps/load-balancing-sims/phase6/Packet.java
trunk/apps/load-balancing-sims/phase6/Peer.java
trunk/apps/load-balancing-sims/phase6/Sim.java
trunk/apps/load-balancing-sims/phase6/messages/
trunk/apps/load-balancing-sims/phase6/messages/Message.java
trunk/apps/load-balancing-sims/phase6/messages/Request.java
trunk/apps/load-balancing-sims/phase6/messages/Response.java
trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
Removed:
trunk/apps/load-balancing-sims/phase6/Ack.java
trunk/apps/load-balancing-sims/phase6/CongestionWindow.java
trunk/apps/load-balancing-sims/phase6/Message.java
trunk/apps/load-balancing-sims/phase6/Node.java
trunk/apps/load-balancing-sims/phase6/Packet.java
trunk/apps/load-balancing-sims/phase6/Peer.java
trunk/apps/load-balancing-sims/phase6/Request.java
trunk/apps/load-balancing-sims/phase6/Response.java
trunk/apps/load-balancing-sims/phase6/RouteNotFound.java
trunk/apps/load-balancing-sims/phase6/Sim.java
Modified:
trunk/apps/load-balancing-sims/phase6/RequestState.java
Log:
Moved Messages into a separate package in preparation for FNP
Copied: trunk/apps/load-balancing-sims/phase6 (from rev 9966,
trunk/apps/load-balancing-sims/phase5-coalescing)
Deleted: trunk/apps/load-balancing-sims/phase6/Ack.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Ack.java 2006-08-08
14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Ack.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,13 +0,0 @@
-// Tell the sender how long each ack was delayed so it can measure the RTT
-
-class Ack
-{
- public final int seq; // Sequence number of an acked packet
- public final double delay; // Seconds the ack was delayed for coalescing
-
- public Ack (int seq, double delay)
- {
- this.seq = seq;
- this.delay = delay;
- }
-}
Deleted: trunk/apps/load-balancing-sims/phase6/CongestionWindow.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/CongestionWindow.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/CongestionWindow.java 2006-08-20
22:58:19 UTC (rev 10220)
@@ -1,74 +0,0 @@
-// AIMD congestion control
-
-class CongestionWindow
-{
- public final static int MIN_CWIND = 3000; // Minimum congestion window
- public final static int MAX_CWIND = 1000000; // Max congestion window
- public final static double ALPHA = 0.3125; // AIMD increase parameter
- public final static double BETA = 0.875; // AIMD decrease parameter
- public final static double GAMMA = 3.0; // Slow start divisor
-
- private double cwind = MIN_CWIND; // Size of window in bytes
- private int inflight = 0; // Bytes sent but not acked
- private boolean slowStart = true; // Are we in the slow start phase?
- private Peer peer; // The owner
-
- public CongestionWindow (Peer peer)
- {
- this.peer = peer;
- }
-
- public void reset()
- {
- peer.log ("congestion window decreased to " + MIN_CWIND);
- cwind = MIN_CWIND;
- peer.log ("returning to slow start");
- slowStart = true;
- }
-
- public int available()
- {
- return (int) cwind - inflight;
- }
-
- // Put bytes in flight
- public void bytesSent (int bytes)
- {
- inflight += bytes;
- peer.log (inflight + " bytes in flight");
- }
-
- // Take bytes out of flight
- public void bytesAcked (int bytes)
- {
- inflight -= bytes;
- peer.log (inflight + " bytes in flight");
- // Increase the window
- if (slowStart) cwind += bytes / GAMMA;
- else cwind += bytes * bytes * ALPHA / cwind;
- if (cwind > MAX_CWIND) cwind = MAX_CWIND;
- peer.log ("congestion window increased to " + cwind);
- }
-
- // Decrease the window when a packet is fast retransmitted
- public void fastRetransmission (double now)
- {
- peer.log (inflight + " bytes in flight");
- cwind *= BETA;
- if (cwind < MIN_CWIND) cwind = MIN_CWIND;
- peer.log ("congestion window decreased to " + cwind);
- // The slow start phase ends when the first packet is lost
- if (slowStart) {
- peer.log ("leaving slow start");
- slowStart = false;
- }
- }
-
- // Decrease the window when a packet is retransmitted due to a timeout
- public void timeout (double now)
- {
- peer.log (inflight + " bytes in flight");
- if (slowStart) fastRetransmission (now); // Leave slow start
- else reset(); // Reset the window and return to slow start
- }
-}
Copied: trunk/apps/load-balancing-sims/phase6/CongestionWindow.java (from rev
10158, trunk/apps/load-balancing-sims/phase5-coalescing/CongestionWindow.java)
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/CongestionWindow.java
2006-08-17 13:28:38 UTC (rev 10158)
+++ trunk/apps/load-balancing-sims/phase6/CongestionWindow.java 2006-08-20
22:58:19 UTC (rev 10220)
@@ -0,0 +1,74 @@
+// AIMD congestion control
+
+class CongestionWindow
+{
+ public final static int MIN_CWIND = 3000; // Minimum congestion window
+ public final static int MAX_CWIND = 1000000; // Max congestion window
+ public final static double ALPHA = 0.3125; // AIMD increase parameter
+ public final static double BETA = 0.875; // AIMD decrease parameter
+ public final static double GAMMA = 3.0; // Slow start divisor
+
+ private double cwind = MIN_CWIND; // Size of window in bytes
+ private int inflight = 0; // Bytes sent but not acked
+ private boolean slowStart = true; // Are we in the slow start phase?
+ private Peer peer; // The owner
+
+ public CongestionWindow (Peer peer)
+ {
+ this.peer = peer;
+ }
+
+ public void reset()
+ {
+ peer.log ("congestion window decreased to " + MIN_CWIND);
+ cwind = MIN_CWIND;
+ peer.log ("returning to slow start");
+ slowStart = true;
+ }
+
+ public int available()
+ {
+ return (int) cwind - inflight;
+ }
+
+ // Put bytes in flight
+ public void bytesSent (int bytes)
+ {
+ inflight += bytes;
+ peer.log (inflight + " bytes in flight");
+ }
+
+ // Take bytes out of flight
+ public void bytesAcked (int bytes)
+ {
+ inflight -= bytes;
+ peer.log (inflight + " bytes in flight");
+ // Increase the window
+ if (slowStart) cwind += bytes / GAMMA;
+ else cwind += bytes * bytes * ALPHA / cwind;
+ if (cwind > MAX_CWIND) cwind = MAX_CWIND;
+ peer.log ("congestion window increased to " + cwind);
+ }
+
+ // Decrease the window when a packet is fast retransmitted
+ public void fastRetransmission (double now)
+ {
+ peer.log (inflight + " bytes in flight");
+ cwind *= BETA;
+ if (cwind < MIN_CWIND) cwind = MIN_CWIND;
+ peer.log ("congestion window decreased to " + cwind);
+ // The slow start phase ends when the first packet is lost
+ if (slowStart) {
+ peer.log ("leaving slow start");
+ slowStart = false;
+ }
+ }
+
+ // Decrease the window when a packet is retransmitted due to a timeout
+ public void timeout (double now)
+ {
+ peer.log (inflight + " bytes in flight");
+ if (slowStart) fastRetransmission (now); // Leave slow start
+ else reset(); // Reset the window and return to slow start
+ }
+}
Deleted: trunk/apps/load-balancing-sims/phase6/Message.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Message.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Message.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,11 +0,0 @@
-// A high-level message (as opposed to a low-level packet)
-
-class Message
-{
- public final static int HEADER_SIZE = 30; // Sequence number, MAC, etc
- public final static int ID_SIZE = 16; // Size of unique request ID
- public final static int KEY_SIZE = 32; // Size of routing key
- public final static int DATA_SIZE = 1024; // Size of data block
-
- public int size; // Size in bytes
-}
Deleted: trunk/apps/load-balancing-sims/phase6/Node.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Node.java 2006-08-08
14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Node.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,197 +0,0 @@
-import java.util.HashMap;
-import java.util.HashSet;
-
-class Node implements EventTarget
-{
- public final static int STORE_SIZE = 10; // Max number of keys in store
- public final static double MIN_SLEEP = 0.01; // Seconds
-
- public double location; // Routing location
- public NetworkInterface net;
- private HashMap<Integer,Peer> peers; // Look up a peer by its address
- private int requestsGenerated = 0;
- private HashSet<Integer> recentlySeenRequests; // Request IDs
- private HashMap<Integer,RequestState> outstandingRequests;
- public LruCache<Integer> cache; // Datastore containing keys
- private boolean timerRunning = false; // Is the timer running?
-
- public Node (double txSpeed, double rxSpeed)
- {
- location = Math.random();
- net = new NetworkInterface (this, txSpeed, rxSpeed);
- peers = new HashMap<Integer,Peer>();
- recentlySeenRequests = new HashSet<Integer>();
- outstandingRequests = new HashMap<Integer,RequestState>();
- cache = new LruCache<Integer> (STORE_SIZE);
- }
-
- public void connect (Node n, double latency)
- {
- Peer p = new Peer (this, n.net.address, n.location, latency);
- peers.put (n.net.address, p);
- }
-
- public void connectBothWays (Node n, double latency)
- {
- connect (n, latency);
- n.connect (this, latency);
- }
-
- // Calculate the circular distance between two locations
- public static double distance (double a, double b)
- {
- if (a > b) return Math.min (a - b, b - a + 1.0);
- else return Math.min (b - a, a - b + 1.0);
- }
-
- // Convert an integer key to a routing location
- public static double keyToLocation (int key)
- {
- return key / (double) Integer.MAX_VALUE;
- }
-
- // Convert a routing location to an integer key
- public static int locationToKey (double location)
- {
- return (int) (location * Integer.MAX_VALUE);
- }
-
- // Called by Peer
- public void startTimer()
- {
- if (timerRunning) return;
- log ("starting retransmission/coalescing timer");
- Event.schedule (this, Peer.MAX_DELAY, CHECK_TIMEOUTS, null);
- timerRunning = true;
- }
-
- // Called by NetworkInterface
- public void handlePacket (Packet packet)
- {
- Peer peer = peers.get (packet.src);
- if (peer == null) log ("unknown peer!");
- else peer.handlePacket (packet);
- }
-
- // Called by Peer
- public void handleMessage (Message m, Peer prev)
- {
- log ("received " + m);
- // FIXME: ugly
- if (m instanceof Request)
- handleRequest ((Request) m, prev);
- else if (m instanceof Response)
- handleResponse ((Response) m);
- else if (m instanceof RouteNotFound)
- handleRouteNotFound ((RouteNotFound) m);
- }
-
- private void handleRequest (Request r, Peer prev)
- {
- if (!recentlySeenRequests.add (r.id)) {
- log ("rejecting recently seen " + r);
- prev.sendMessage (new RouteNotFound (r.id));
- // Don't forward the request to prev, it's seen it
- RequestState rs = outstandingRequests.get (r.id);
- if (rs != null) rs.nexts.remove (prev);
- return;
- }
- if (cache.get (r.key)) {
- log ("key " + r.key + " found in cache");
- if (prev == null)
- log (r + " succeeded locally");
- else prev.sendMessage (new Response (r.id, r.key));
- return;
- }
- log ("key " + r.key + " not found in cache");
- forwardRequest (new RequestState (r, prev, peers.values()));
- }
-
- private void handleResponse (Response r)
- {
- RequestState rs = outstandingRequests.remove (r.id);
- if (rs == null) {
- log ("unexpected " + r);
- return;
- }
- cache.put (r.key);
- if (rs.prev == null) log (rs + " succeeded");
- else {
- log ("forwarding " + r);
- rs.prev.sendMessage (r);
- }
- }
-
- private void handleRouteNotFound (RouteNotFound r)
- {
- RequestState rs = outstandingRequests.remove (r.id);
- if (rs == null) {
- log ("unexpected route not found " + r.id);
- return;
- }
- forwardRequest (rs);
- }
-
- private void forwardRequest (RequestState rs)
- {
- Peer next = rs.closestPeer();
- if (next == null) {
- log ("route not found for " + rs);
- if (rs.prev == null)
- log (rs + " failed");
- else rs.prev.sendMessage (new RouteNotFound (rs.id));
- return;
- }
- log ("forwarding " + rs + " to " + next.address);
- next.sendMessage (new Request (rs.id, rs.key));
- rs.nexts.remove (next);
- outstandingRequests.put (rs.id, rs);
- }
-
- private void log (String message)
- {
- Event.log (net.address + " " + message);
- }
-
- // Event callback
- private void generateRequest()
- {
- if (requestsGenerated++ > 10000) return;
- // Send a request to a random location
- Request r = new Request (locationToKey (Math.random()));
- log ("generating request " + r.id);
- handleRequest (r, null);
- // Schedule the next request
- Event.schedule (this, 0.123, GENERATE_REQUEST, null);
- }
-
- // Event callback
- private void checkTimeouts()
- {
- double deadline = Double.POSITIVE_INFINITY;
- for (Peer p : peers.values())
- deadline = Math.min (deadline, p.checkTimeouts());
- if (deadline == Double.POSITIVE_INFINITY) {
- log ("stopping retransmission/coalescing timer");
- timerRunning = false;
- }
- else {
- double sleep = deadline - Event.time(); // Can be < 0
- if (sleep < MIN_SLEEP) sleep = MIN_SLEEP;
- log ("sleeping for " + sleep + " seconds");
- Event.schedule (this, sleep, CHECK_TIMEOUTS, null);
- timerRunning = true;
- }
- }
-
- // EventTarget interface
- public void handleEvent (int type, Object data)
- {
- if (type == GENERATE_REQUEST) generateRequest();
- else if (type == CHECK_TIMEOUTS) checkTimeouts();
- }
-
- // Each EventTarget class has its own event codes
- public final static int GENERATE_REQUEST = 1;
- public final static int CHECK_TIMEOUTS = 2;
-}
Copied: trunk/apps/load-balancing-sims/phase6/Node.java (from rev 10162,
trunk/apps/load-balancing-sims/phase5-coalescing/Node.java)
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Node.java 2006-08-17
15:44:21 UTC (rev 10162)
+++ trunk/apps/load-balancing-sims/phase6/Node.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -0,0 +1,207 @@
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.ArrayList;
+import java.util.Collections;
+import messages.*;
+
+class Node implements EventTarget
+{
+ public final static int STORE_SIZE = 10; // Max number of keys in store
+ public final static double MIN_SLEEP = 0.01; // Seconds
+ public final static double SHORT_SLEEP = 0.05; // Poll the bw limiter
+
+ // Token bucket bandwidth limiter
+ public final static int BUCKET_RATE = 20000; // Bytes per second
+ public final static int BUCKET_SIZE = 40000; // Burst size in bytes
+
+ public double location; // Routing location
+ public NetworkInterface net;
+ private HashMap<Integer,Peer> peers; // Look up a peer by its address
+ private int requestsGenerated = 0;
+ private HashSet<Integer> recentlySeenRequests; // Request IDs
+ private HashMap<Integer,RequestState> outstandingRequests;
+ public LruCache<Integer> cache; // Datastore containing keys
+ public TokenBucket bandwidth; // Bandwidth limiter
+ private boolean timerRunning = false; // Is the timer running?
+
+ public Node (double txSpeed, double rxSpeed)
+ {
+ location = Math.random();
+ net = new NetworkInterface (this, txSpeed, rxSpeed);
+ peers = new HashMap<Integer,Peer>();
+ recentlySeenRequests = new HashSet<Integer>();
+ outstandingRequests = new HashMap<Integer,RequestState>();
+ cache = new LruCache<Integer> (STORE_SIZE);
+ bandwidth = new TokenBucket (BUCKET_RATE, BUCKET_SIZE);
+ }
+
+ public void connect (Node n, double latency)
+ {
+ Peer p = new Peer (this, n.net.address, n.location, latency);
+ peers.put (n.net.address, p);
+ }
+
+ public void connectBothWays (Node n, double latency)
+ {
+ connect (n, latency);
+ n.connect (this, latency);
+ }
+
+ // Calculate the circular distance between two locations
+ public static double distance (double a, double b)
+ {
+ if (a > b) return Math.min (a - b, b - a + 1.0);
+ else return Math.min (b - a, a - b + 1.0);
+ }
+
+ // Convert an integer key to a routing location
+ public static double keyToLocation (int key)
+ {
+ return key / (double) Integer.MAX_VALUE;
+ }
+
+ // Convert a routing location to an integer key
+ public static int locationToKey (double location)
+ {
+ return (int) (location * Integer.MAX_VALUE);
+ }
+
+ // Called by Peer
+ public void startTimer()
+ {
+ if (timerRunning) return;
+ log ("starting retransmission/coalescing timer");
+ Event.schedule (this, Peer.MAX_DELAY, CHECK_TIMEOUTS, null);
+ timerRunning = true;
+ }
+
+ // Called by NetworkInterface
+ public void handlePacket (Packet packet)
+ {
+ Peer peer = peers.get (packet.src);
+ if (peer == null) log ("unknown peer!");
+ else peer.handlePacket (packet);
+ }
+
+ // Called by Peer
+ public void handleMessage (Message m, Peer prev)
+ {
+ log ("received " + m);
+ // FIXME: ugly
+ if (m instanceof Request)
+ handleRequest ((Request) m, prev);
+ else if (m instanceof Response)
+ handleResponse ((Response) m);
+ else if (m instanceof RouteNotFound)
+ handleRouteNotFound ((RouteNotFound) m);
+ }
+
+ private void handleRequest (Request r, Peer prev)
+ {
+ if (!recentlySeenRequests.add (r.id)) {
+ log ("rejecting recently seen " + r);
+ prev.sendMessage (new RouteNotFound (r.id));
+ // Don't forward the request to prev, it's seen it
+ RequestState rs = outstandingRequests.get (r.id);
+ if (rs != null) rs.nexts.remove (prev);
+ return;
+ }
+ if (cache.get (r.key)) {
+ log ("key " + r.key + " found in cache");
+ if (prev == null) log (r + " succeeded locally");
+ else prev.sendMessage (new Response (r.id, r.key));
+ return;
+ }
+ log ("key " + r.key + " not found in cache");
+ forwardRequest (new RequestState (r, prev, peers.values()));
+ }
+
+ private void handleResponse (Response r)
+ {
+ RequestState rs = outstandingRequests.remove (r.id);
+ if (rs == null) {
+ log ("unexpected " + r);
+ return;
+ }
+ cache.put (r.key);
+ if (rs.prev == null) log (rs + " succeeded");
+ else {
+ log ("forwarding " + r);
+ rs.prev.sendMessage (r);
+ }
+ }
+
+ private void handleRouteNotFound (RouteNotFound r)
+ {
+ RequestState rs = outstandingRequests.remove (r.id);
+ if (rs == null) {
+ log ("unexpected route not found " + r.id);
+ return;
+ }
+ forwardRequest (rs);
+ }
+
+ private void forwardRequest (RequestState rs)
+ {
+ Peer next = rs.closestPeer();
+ if (next == null) {
+ log ("route not found for " + rs);
+ if (rs.prev == null) log (rs + " failed");
+ else rs.prev.sendMessage (new RouteNotFound (rs.id));
+ return;
+ }
+ log ("forwarding " + rs + " to " + next.address);
+ next.sendMessage (new Request (rs.id, rs.key));
+ rs.nexts.remove (next);
+ outstandingRequests.put (rs.id, rs);
+ }
+
+ private void log (String message)
+ {
+ Event.log (net.address + " " + message);
+ }
+
+ // Event callback
+ private void generateRequest()
+ {
+ for (int i = 0; i < 10000; i++) {
+ // Send a request to a random location
+ Request r = new Request (locationToKey (Math.random()));
+ log ("generating request " + r.id);
+ handleRequest (r, null);
+ }
+ }
+
+ // Event callback
+ private void checkTimeouts()
+ {
+ // Check the peers in a random order each time
+ ArrayList<Peer> shuffled = new ArrayList<Peer> (peers.values());
+ Collections.shuffle (shuffled);
+
+ double deadline = Double.POSITIVE_INFINITY;
+ for (Peer p : shuffled)
+ deadline = Math.min (deadline, p.checkTimeouts());
+ if (deadline == Double.POSITIVE_INFINITY) {
+ log ("stopping retransmission/coalescing timer");
+ timerRunning = false;
+ }
+ else {
+ double sleep = deadline - Event.time(); // Can be < 0
+ if (sleep < MIN_SLEEP) sleep = MIN_SLEEP;
+ log ("sleeping for " + sleep + " seconds");
+ Event.schedule (this, sleep, CHECK_TIMEOUTS, null);
+ }
+ }
+
+ // EventTarget interface
+ public void handleEvent (int type, Object data)
+ {
+ if (type == GENERATE_REQUEST) generateRequest();
+ else if (type == CHECK_TIMEOUTS) checkTimeouts();
+ }
+
+ // Each EventTarget class has its own event codes
+ public final static int GENERATE_REQUEST = 1;
+ public final static int CHECK_TIMEOUTS = 2;
+}
Deleted: trunk/apps/load-balancing-sims/phase6/Packet.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Packet.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Packet.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,35 +0,0 @@
-// A low-level packet (as opposed to a high-level message)
-
-import java.util.ArrayList;
-
-class Packet
-{
- public final static int HEADER_SIZE = 80; // Including IP & UDP headers
- public final static int ACK_SIZE = 8; // Size of an ack in bytes
- public final static int MAX_SIZE = 1450; // MTU including headers
- public final static int SENSIBLE_PAYLOAD = 1000; // Coalescing
-
- public int src, dest; // Network addresses
- public int size = HEADER_SIZE; // Size in bytes, including headers
- public int seq = -1; // Data sequence number (-1 if no data)
- public ArrayList<Ack> acks = null;
- public ArrayList<Message> messages = null;
-
- public double sent; // Time at which the packet was (re) transmitted
- public double latency; // Link latency (stored here for convenience)
-
- public void addAck (Ack a)
- {
- if (acks == null) acks = new ArrayList<Ack>();
- acks.add (a);
- size += ACK_SIZE;
- }
-
- // In real life the payload would be an array of bytes
- public void addMessage (Message m)
- {
- if (messages == null) messages = new ArrayList<Message>();
- messages.add (m);
- size += m.size;
- }
-}
Copied: trunk/apps/load-balancing-sims/phase6/Packet.java (from rev 10036,
trunk/apps/load-balancing-sims/phase5-coalescing/Packet.java)
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Packet.java
2006-08-10 22:40:48 UTC (rev 10036)
+++ trunk/apps/load-balancing-sims/phase6/Packet.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -0,0 +1,36 @@
+// A low-level packet (as opposed to a high-level message)
+
+import java.util.ArrayList;
+import messages.Message;
+
+class Packet
+{
+ public final static int HEADER_SIZE = 80; // Including IP & UDP headers
+ public final static int ACK_SIZE = 4; // Size of an ack in bytes
+ public final static int MAX_SIZE = 1450; // MTU including headers
+ public final static int SENSIBLE_PAYLOAD = 1000; // Coalescing
+
+ public int src, dest; // Network addresses
+ public int size = HEADER_SIZE; // Size in bytes, including headers
+ public int seq = -1; // Data sequence number (-1 if no data)
+ public ArrayList<Integer> acks = null;
+ public ArrayList<Message> messages = null;
+
+ public double sent; // Time at which the packet was (re) transmitted
+ public double latency; // Link latency (stored here for convenience)
+
+ public void addAck (int ack)
+ {
+ if (acks == null) acks = new ArrayList<Integer>();
+ acks.add (ack);
+ size += ACK_SIZE;
+ }
+
+ // In real life the payload would be an array of bytes
+ public void addMessage (Message m)
+ {
+ if (messages == null) messages = new ArrayList<Message>();
+ messages.add (m);
+ size += m.size;
+ }
+}
Deleted: trunk/apps/load-balancing-sims/phase6/Peer.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Peer.java 2006-08-08
14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Peer.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,285 +0,0 @@
-import java.util.LinkedList;
-import java.util.Iterator;
-import java.util.HashSet;
-
-class Peer
-{
- private Node node; // The local node
- public int address; // The remote node's address
- public double location; // The remote node's routing location
- private double latency; // The latency of the connection in seconds
-
- // Retransmission parameters
- public final static double RTO = 4.0; // Retransmission timeout in RTTs
- public final static double FRTO = 1.5; // Fast retx timeout in RTTs
- public final static double RTT_DECAY = 0.9; // Exp moving average
-
- // Coalescing
- public final static double MAX_DELAY = 0.1; // Coalescing delay, seconds
-
- // Out-of-order delivery with eventual detection of missing packets
- public final static int SEQ_RANGE = 1000;
-
- // Token bucket bandwidth limiter
- public final static int BUCKET_RATE = 2000; // Bytes per second
- public final static int BUCKET_SIZE = 4000; // Burst size in bytes
-
- // Sender state
- private double rtt = 5.0; // Estimated round-trip time in seconds
- private int txSeq = 0; // Sequence number of next outgoing data packet
- private int txMaxSeq = SEQ_RANGE - 1; // Highest sequence number
- private LinkedList<Packet> txBuffer; // Retransmission buffer
- private LinkedList<Deadline<Message>> msgQueue; // Outgoing messages
- private int msgQueueSize = 0; // Size of message queue in bytes
- private LinkedList<Deadline<Integer>> ackQueue; // Outgoing acks
- private int ackQueueSize = 0; // Size of ack queue in bytes
- private CongestionWindow window; // AIMD congestion window
- private double lastTransmission = 0.0; // Clock time
- private TokenBucket bandwidth; // Token bucket bandwidth limiter
-
- // Receiver state
- private HashSet<Integer> rxDupe; // Detect duplicates by sequence number
- private int rxSeq = 0; // Sequence number of next in-order incoming pkt
-
- public Peer (Node node, int address, double location, double latency)
- {
- this.node = node;
- this.address = address;
- this.location = location;
- this.latency = latency;
- txBuffer = new LinkedList<Packet>();
- msgQueue = new LinkedList<Deadline<Message>>();
- ackQueue = new LinkedList<Deadline<Integer>>();
- window = new CongestionWindow (this);
- bandwidth = new TokenBucket (BUCKET_RATE, BUCKET_SIZE);
- rxDupe = new HashSet<Integer>();
- }
-
- // Queue a message for transmission
- public void sendMessage (Message m)
- {
- log (m + " added to message queue");
- // Warning: until token-passing is implemented the length of
- // the message queue is unlimited
- double now = Event.time();
- msgQueue.add (new Deadline<Message> (m, now + MAX_DELAY));
- msgQueueSize += m.size;
- log (msgQueue.size() + " messages in queue");
- // Start the node's timer if necessary
- node.startTimer();
- // Send as many packets as possible
- while (send());
- }
-
- // Try to send a packet, return true if a packet was sent
- private boolean send()
- {
- if (ackQueueSize == 0 && msgQueueSize == 0) {
- log ("no messages or acks to send");
- return false;
- }
-
- // Return to slow start when the link is idle
- double now = Event.time();
- if (now - lastTransmission > RTO * rtt) window.reset();
- lastTransmission = now;
-
- // Work out how large a packet we can send
- int headersAndAcks = Packet.HEADER_SIZE + ackQueueSize;
- int payload = Packet.MAX_SIZE - headersAndAcks;
- if (payload > msgQueueSize) payload = msgQueueSize;
-
- int win = window.available() - headersAndAcks;
- if (win <= 0) log ("no room in congestion window for messages");
- if (payload > win) payload = win;
-
- int bw = bandwidth.available() - headersAndAcks;
- if (bw <= 0) log ("no bandwidth available for messages");
- if (payload > bw) payload = bw;
-
- // Delay small packets for coalescing
- if (payload < Packet.SENSIBLE_PAYLOAD && now < deadline()) {
- log ("delaying transmission of " + payload + " bytes");
- return false;
- }
-
- Packet p = new Packet();
-
- // Put all waiting acks in the packet
- for (Deadline<Integer> a : ackQueue) {
- double delay = now - (a.deadline - MAX_DELAY);
- p.addAck (new Ack (a.item, delay));
- }
- ackQueue.clear();
- ackQueueSize = 0;
-
- // Don't send sequence number n+SEQ_RANGE until sequence
- // number n has been acked - this limits the number of
- // sequence numbers the receiver must store for replay
- // detection. We must still be allowed to send acks,
- // otherwise the connection could deadlock.
-
- if (txSeq > txMaxSeq)
- log ("waiting for ack " + (txMaxSeq - SEQ_RANGE + 1));
- else {
- // Put as many messages as possible in the packet
- Iterator<Deadline<Message>> i = msgQueue.iterator();
- while (i.hasNext()) {
- Message m = i.next().item;
- if (m.size > payload) break;
- i.remove();
- msgQueueSize -= m.size;
- p.addMessage (m);
- payload -= m.size;
- }
- }
-
- // Don't send empty packets
- if (p.acks == null && p.messages == null) return false;
-
- // If the packet contains data, buffer it for retransmission
- if (p.messages != null) {
- p.seq = txSeq++;
- p.sent = now;
- txBuffer.add (p);
- window.bytesSent (p.size);
- }
-
- // Send the packet
- log ("sending packet " + p.seq + ", " + p.size + " bytes");
- node.net.send (p, address, latency);
- bandwidth.remove (p.size);
- return true;
- }
-
- private void sendAck (int seq)
- {
- log ("ack " + seq + " added to ack queue");
- double now = Event.time();
- ackQueue.add (new Deadline<Integer> (seq, now + MAX_DELAY));
- ackQueueSize += Packet.ACK_SIZE;
- log (ackQueue.size() + " acks in queue");
- // Start the node's timer if necessary
- node.startTimer();
- // Send as many packets as possible
- while (send());
- }
-
- // Called by Node when a packet arrives
- public void handlePacket (Packet p)
- {
- if (p.messages != null) handleData (p);
- if (p.acks != null) for (Ack a : p.acks) handleAck (a);
- }
-
- private void handleData (Packet p)
- {
- log ("received packet " + p.seq + ", " + p.size + " bytes");
- if (p.seq < rxSeq || rxDupe.contains (p.seq)) {
- log ("duplicate packet");
- sendAck (p.seq); // Original ack may have been lost
- }
- else if (p.seq == rxSeq) {
- log ("packet in order");
- // Find the sequence number of the next missing packet
- int was = rxSeq;
- while (rxDupe.remove (++rxSeq));
- log ("rxSeq was " + was + ", now " + rxSeq);
- // Deliver the packet
- unpack (p);
- sendAck (p.seq);
- }
- else if (p.seq < rxSeq + SEQ_RANGE) {
- log ("packet out of order - expected " + rxSeq);
- if (rxDupe.add (p.seq)) unpack (p);
- else log ("duplicate packet");
- sendAck (p.seq); // Original ack may have been lost
- }
- // This indicates a misbehaving sender - discard the packet
- else log ("warning: received " + p.seq + " before " + rxSeq);
- }
-
- private void handleAck (Ack a)
- {
- log ("received ack " + a.seq);
- double now = Event.time();
- Iterator<Packet> i = txBuffer.iterator();
- while (i.hasNext()) {
- Packet p = i.next();
- double age = now - p.sent;
- // Explicit ack
- if (p.seq == a.seq) {
- log ("packet " + p.seq + " acknowledged");
- i.remove();
- // Update the congestion window
- window.bytesAcked (p.size);
- // Update the average round-trip time
- rtt *= RTT_DECAY;
- rtt += (age - a.delay) * (1.0 - RTT_DECAY);
- log ("ack delay " + a.delay);
- log ("round-trip time " + (age - a.delay));
- log ("average round-trip time " + rtt);
- break;
- }
- // Fast retransmission
- if (p.seq < a.seq && age > FRTO * rtt) {
- p.sent = now;
- log ("fast retransmitting packet " + p.seq);
- node.net.send (p, address, latency);
- window.fastRetransmission (now);
- }
- }
- // Recalculate the maximum sequence number
- if (txBuffer.isEmpty()) txMaxSeq = txSeq + SEQ_RANGE - 1;
- else txMaxSeq = txBuffer.peek().seq + SEQ_RANGE - 1;
- log ("maximum sequence number " + txMaxSeq);
- // Send as many packets as possible
- while (send());
- }
-
- // Remove messages from a packet and deliver them to the node
- private void unpack (Packet p)
- {
- if (p.messages == null) return;
- for (Message m : p.messages) node.handleMessage (m, this);
- }
-
- // Called by Node, returns the next coalescing or retx deadline
- public double checkTimeouts()
- {
- log ("checking timeouts");
- // Send as many packets as possible
- while (send());
- if (txBuffer.isEmpty()) {
- log ("no packets in flight");
- return deadline();
- }
- double now = Event.time();
- for (Packet p : txBuffer) {
- if (now - p.sent > RTO * rtt) {
- // Retransmission timeout
- log ("retransmitting packet " + p.seq);
- p.sent = now;
- node.net.send (p, address, latency);
- window.timeout (now);
- }
- }
- return Math.min (now + MAX_DELAY, deadline());
- }
-
- // Work out when the first ack or message needs to be sent
- private double deadline()
- {
- double deadline = Double.POSITIVE_INFINITY;
- Deadline<Integer> ack = ackQueue.peek();
- if (ack != null) deadline = ack.deadline;
- Deadline<Message> msg = msgQueue.peek();
- if (msg != null) deadline = Math.min (deadline, msg.deadline);
- return deadline;
- }
-
- public void log (String message)
- {
- Event.log (node.net.address + ":" + address + " " + message);
- }
-}
Copied: trunk/apps/load-balancing-sims/phase6/Peer.java (from rev 10165,
trunk/apps/load-balancing-sims/phase5-coalescing/Peer.java)
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Peer.java 2006-08-17
16:19:51 UTC (rev 10165)
+++ trunk/apps/load-balancing-sims/phase6/Peer.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -0,0 +1,294 @@
+import java.util.LinkedList;
+import java.util.Iterator;
+import java.util.HashSet;
+import messages.Message;
+
+class Peer
+{
+ private Node node; // The local node
+ public int address; // The remote node's address
+ public double location; // The remote node's routing location
+ private double latency; // The latency of the connection in seconds
+
+ // Retransmission parameters
+ public final static double RTO = 4.0; // Retransmission timeout in RTTs
+ public final static double FRTO = 1.5; // Fast retx timeout in RTTs
+ public final static double RTT_DECAY = 0.9; // Exp moving average
+ public final static double LINK_IDLE = 5.0; // RTTs without a packet
+
+ // Coalescing
+ public final static double MAX_DELAY = 0.1; // Coalescing delay, seconds
+
+ // Out-of-order delivery with eventual detection of missing packets
+ public final static int SEQ_RANGE = 1000;
+
+ // Sender state
+ private double rtt = 5.0; // Estimated round-trip time in seconds
+ private int txSeq = 0; // Sequence number of next outgoing data packet
+ private int txMaxSeq = SEQ_RANGE - 1; // Highest sequence number
+ private LinkedList<Packet> txBuffer; // Retransmission buffer
+ private LinkedList<Deadline<Message>> msgQueue; // Outgoing messages
+ private int msgQueueSize = 0; // Size of message queue in bytes
+ private LinkedList<Deadline<Integer>> ackQueue; // Outgoing acks
+ private int ackQueueSize = 0; // Size of ack queue in bytes
+ private CongestionWindow window; // AIMD congestion window
+ private double lastTransmission = 0.0; // Clock time
+
+ // Receiver state
+ private HashSet<Integer> rxDupe; // Detect duplicates by sequence number
+ private int rxSeq = 0; // Sequence number of next in-order incoming pkt
+
+ public Peer (Node node, int address, double location, double latency)
+ {
+ this.node = node;
+ this.address = address;
+ this.location = location;
+ this.latency = latency;
+ txBuffer = new LinkedList<Packet>();
+ msgQueue = new LinkedList<Deadline<Message>>();
+ ackQueue = new LinkedList<Deadline<Integer>>();
+ window = new CongestionWindow (this);
+ rxDupe = new HashSet<Integer>();
+ }
+
+ // Queue a message for transmission
+ public void sendMessage (Message m)
+ {
+ log (m + " added to message queue");
+ // Warning: until token-passing is implemented the length of
+ // the message queue is unlimited
+ double now = Event.time();
+ msgQueue.add (new Deadline<Message> (m, now + MAX_DELAY));
+ msgQueueSize += m.size;
+ // Start the node's timer if necessary
+ node.startTimer();
+ // Send as many packets as possible
+ while (send());
+ }
+
+ // Try to send a packet, return true if a packet was sent
+ private boolean send()
+ {
+ if (ackQueueSize == 0 && msgQueueSize == 0) {
+ log ("no messages or acks to send");
+ return false;
+ }
+ log (ackQueue.size() + " acks in queue");
+ log (msgQueue.size() + " messages in queue");
+
+ // Return to slow start when the link is idle
+ double now = Event.time();
+ if (now - lastTransmission > LINK_IDLE * rtt) window.reset();
+ lastTransmission = now;
+
+ // Work out how large a packet we can send
+ int headersAndAcks = Packet.HEADER_SIZE + ackQueueSize;
+ int payload = Packet.MAX_SIZE - headersAndAcks;
+ if (payload > msgQueueSize) payload = msgQueueSize;
+ int win = window.available() - headersAndAcks;
+ if (payload > win) payload = win;
+ int bw = node.bandwidth.available() - headersAndAcks;
+ if (payload > bw) payload = bw;
+
+ // Delay small packets for coalescing
+ if (now < deadline (now)) {
+ log ("delaying transmission of " + payload + " bytes");
+ return false;
+ }
+
+ Packet p = new Packet();
+
+ // Put all waiting acks in the packet
+ for (Deadline<Integer> a : ackQueue) p.addAck (a.item);
+ ackQueue.clear();
+ ackQueueSize = 0;
+
+ // Don't send sequence number n+SEQ_RANGE until sequence
+ // number n has been acked - this limits the number of
+ // sequence numbers the receiver must store for replay
+ // detection. We must still be allowed to send acks,
+ // otherwise the connection could deadlock.
+
+ if (txSeq <= txMaxSeq) pack (p, payload); // OK to send data
+ else log ("waiting for ack " + (txMaxSeq - SEQ_RANGE + 1));
+
+ // Don't send empty packets
+ if (p.acks == null && p.messages == null) return false;
+
+ // If the packet contains data, buffer it for retransmission
+ if (p.messages != null) {
+ p.seq = txSeq++;
+ p.sent = now;
+ txBuffer.add (p);
+ window.bytesSent (p.size);
+ }
+
+ // Send the packet
+ log ("sending packet " + p.seq + ", " + p.size + " bytes");
+ node.net.send (p, address, latency);
+ node.bandwidth.remove (p.size);
+ return true;
+ }
+
+ private void sendAck (int seq)
+ {
+ log ("ack " + seq + " added to ack queue");
+ double now = Event.time();
+ ackQueue.add (new Deadline<Integer> (seq, now + MAX_DELAY));
+ ackQueueSize += Packet.ACK_SIZE;
+ // Start the node's timer if necessary
+ node.startTimer();
+ // Send as many packets as possible
+ while (send());
+ }
+
+ // Called by Node when a packet arrives
+ public void handlePacket (Packet p)
+ {
+ if (p.messages != null) handleData (p);
+ if (p.acks != null) for (int ack : p.acks) handleAck (ack);
+ }
+
+ private void handleData (Packet p)
+ {
+ log ("received packet " + p.seq + ", " + p.size + " bytes");
+ if (p.seq < rxSeq || rxDupe.contains (p.seq)) {
+ log ("duplicate packet");
+ sendAck (p.seq); // Original ack may have been lost
+ }
+ else if (p.seq == rxSeq) {
+ log ("packet in order");
+ // Find the sequence number of the next missing packet
+ int was = rxSeq;
+ while (rxDupe.remove (++rxSeq));
+ log ("rxSeq was " + was + ", now " + rxSeq);
+ // Deliver the packet
+ unpack (p);
+ sendAck (p.seq);
+ }
+ else if (p.seq < rxSeq + SEQ_RANGE) {
+ log ("packet out of order - expected " + rxSeq);
+ if (rxDupe.add (p.seq)) unpack (p);
+ else log ("duplicate packet");
+ sendAck (p.seq); // Original ack may have been lost
+ }
+ // This indicates a misbehaving sender - discard the packet
+ else log ("warning: received " + p.seq + " before " + rxSeq);
+ }
+
+ private void handleAck (int ack)
+ {
+ log ("received ack " + ack);
+ double now = Event.time();
+ Iterator<Packet> i = txBuffer.iterator();
+ while (i.hasNext()) {
+ Packet p = i.next();
+ double age = now - p.sent;
+ // Explicit ack
+ if (p.seq == ack) {
+ log ("packet " + p.seq + " acknowledged");
+ i.remove();
+ // Update the congestion window
+ window.bytesAcked (p.size);
+ // Update the average round-trip time
+ rtt = rtt * RTT_DECAY + age * (1.0 - RTT_DECAY);
+ log ("round-trip time " + age);
+ log ("average round-trip time " + rtt);
+ break;
+ }
+ // Fast retransmission
+ if (p.seq < ack && age > FRTO * rtt + MAX_DELAY) {
+ p.sent = now;
+ log ("fast retransmitting packet " + p.seq);
+ node.net.send (p, address, latency);
+ window.fastRetransmission (now);
+ }
+ }
+ // Recalculate the maximum sequence number
+ if (txBuffer.isEmpty()) txMaxSeq = txSeq + SEQ_RANGE - 1;
+ else txMaxSeq = txBuffer.peek().seq + SEQ_RANGE - 1;
+ log ("maximum sequence number " + txMaxSeq);
+ // Send as many packets as possible
+ while (send());
+ }
+
+ // Add messages to a packet
+ private void pack (Packet p, int payload)
+ {
+ Iterator<Deadline<Message>> i = msgQueue.iterator();
+ while (i.hasNext()) {
+ Message m = i.next().item;
+ if (m.size > payload) break;
+ i.remove();
+ msgQueueSize -= m.size;
+ p.addMessage (m);
+ payload -= m.size;
+ }
+ }
+
+ // Remove messages from a packet and deliver them to the node
+ private void unpack (Packet p)
+ {
+ if (p.messages == null) return;
+ for (Message m : p.messages) node.handleMessage (m, this);
+ }
+
+ // Called by Node, returns the next coalescing or retx deadline
+ public double checkTimeouts()
+ {
+ log ("checking timeouts");
+ // Send as many packets as possible
+ while (send());
+
+ double now = Event.time();
+ if (txBuffer.isEmpty()) {
+ log ("no packets in flight");
+ return deadline (now);
+ }
+ for (Packet p : txBuffer) {
+ if (now - p.sent > RTO * rtt + MAX_DELAY) {
+ // Retransmission timeout
+ log ("retransmitting packet " + p.seq);
+ p.sent = now;
+ node.net.send (p, address, latency);
+ window.timeout (now);
+ }
+ }
+ return Math.min (now + MAX_DELAY, deadline (now));
+ }
+
+ // Work out when the first message or ack needs to be sent
+ private double deadline (double now)
+ {
+ return Math.min (ackDeadline(), msgDeadline (now));
+ }
+
+ // Work out when the first ack needs to be sent
+ private double ackDeadline()
+ {
+ Deadline<Integer> firstAck = ackQueue.peek();
+ if (firstAck == null) return Double.POSITIVE_INFINITY;
+ return firstAck.deadline;
+ }
+
+ // Work out when the first message needs to be sent
+ private double msgDeadline (double now)
+ {
+ Deadline<Message> firstMsg = msgQueue.peek();
+ if (firstMsg == null) return Double.POSITIVE_INFINITY;
+ double deadline = firstMsg.deadline;
+ if (msgQueueSize < Packet.SENSIBLE_PAYLOAD) return deadline;
+ if (window.available() < Packet.SENSIBLE_PAYLOAD
+ + Packet.HEADER_SIZE)
+ return Double.POSITIVE_INFINITY; // Wait for an ack
+ if (node.bandwidth.available() < Packet.SENSIBLE_PAYLOAD
+ + Packet.HEADER_SIZE)
+ return Math.max (deadline, now + Node.SHORT_SLEEP);
+ return now;
+ }
+
+ public void log (String message)
+ {
+ Event.log (node.net.address + ":" + address + " " + message);
+ }
+}
Deleted: trunk/apps/load-balancing-sims/phase6/Request.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Request.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Request.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,28 +0,0 @@
-class Request extends Message
-{
- private static int nextId = 0;
-
- public final int id; // The unique ID of the request
- public final int key; // The requested key
-
- // Start a new request
- public Request (int key)
- {
- id = nextId++;
- this.key = key;
- size = Message.HEADER_SIZE + Message.ID_SIZE + Message.KEY_SIZE;
- }
-
- // Forward a request
- public Request (int id, int key)
- {
- this.id = id;
- this.key = key;
- size = Message.HEADER_SIZE + Message.ID_SIZE + Message.KEY_SIZE;
- }
-
- public String toString()
- {
- return new String ("request (" + id + "," + key + ")");
- }
-}
Modified: trunk/apps/load-balancing-sims/phase6/RequestState.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/RequestState.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/RequestState.java 2006-08-20
22:58:19 UTC (rev 10220)
@@ -2,6 +2,7 @@
import java.util.HashSet;
import java.util.Collection;
+import messages.Request;
class RequestState
{
Deleted: trunk/apps/load-balancing-sims/phase6/Response.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Response.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Response.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,18 +0,0 @@
-class Response extends Message
-{
- public final int id; // The unique ID of the request
- public final int key; // The requested key
-
- public Response (int id, int key)
- {
- this.id = id;
- this.key = key;
- size = Message.HEADER_SIZE + Message.ID_SIZE +
- Message.KEY_SIZE + Message.DATA_SIZE;
- }
-
- public String toString()
- {
- return new String ("response (" + id + "," + key + ")");
- }
-}
Deleted: trunk/apps/load-balancing-sims/phase6/RouteNotFound.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/RouteNotFound.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/RouteNotFound.java 2006-08-20
22:58:19 UTC (rev 10220)
@@ -1,18 +0,0 @@
-// Note: for the purposes of this simulation, RejectedLoop and RouteNotFound
-// are equivalent
-
-class RouteNotFound extends Message
-{
- public final int id; // The unique ID of the request
-
- public RouteNotFound (int id)
- {
- this.id = id;
- size = Message.HEADER_SIZE + Message.ID_SIZE;
- }
-
- public String toString()
- {
- return new String ("route not found (" + id + ")");
- }
-}
Deleted: trunk/apps/load-balancing-sims/phase6/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/Sim.java 2006-08-08
14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/Sim.java 2006-08-20 22:58:19 UTC
(rev 10220)
@@ -1,31 +0,0 @@
-// Interesting parameters to play with: txSpeed and rxSpeed, retransmission
-// timeout, window sizes, AIMD increase and decrease (Peer.java), queue sizes
-// (NetworkInterface.java), packet size (Packet.java).
-
-class Sim
-{
- public static void main (String[] args)
- {
- double txSpeed = 15000, rxSpeed = 15000; // Bytes per second
- // rxSpeed = Math.exp (rand.nextGaussian() + 11.74);
- // txSpeed = rxSpeed / 5.0;
-
- Network.reorder = true;
- Network.lossRate = 0.001;
-
- Node n0 = new Node (txSpeed, rxSpeed);
- Node n1 = new Node (txSpeed, rxSpeed);
- Node n2 = new Node (txSpeed, rxSpeed);
- Node n3 = new Node (txSpeed, rxSpeed);
-
- n0.connectBothWays (n1, 0.1);
- n1.connectBothWays (n2, 0.1);
- n1.connectBothWays (n3, 0.1);
- n2.connectBothWays (n3, 0.1);
-
- Event.schedule (n0, 0.0, Node.GENERATE_REQUEST, null);
-
- // Run the simulation
- Event.run();
- }
-}
Copied: trunk/apps/load-balancing-sims/phase6/Sim.java (from rev 10162,
trunk/apps/load-balancing-sims/phase5-coalescing/Sim.java)
Added: trunk/apps/load-balancing-sims/phase6/messages/Message.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/messages/Message.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/messages/Message.java 2006-08-20
22:58:19 UTC (rev 10220)
@@ -0,0 +1,13 @@
+// A high-level message (as opposed to a low-level packet)
+
+package messages;
+
+public class Message
+{
+ public final static int HEADER_SIZE = 30; // Sequence number, MAC, etc
+ public final static int ID_SIZE = 16; // Size of unique request ID
+ public final static int KEY_SIZE = 32; // Size of routing key
+ public final static int DATA_SIZE = 1024; // Size of data block
+
+ public int size; // Size in bytes
+}
Added: trunk/apps/load-balancing-sims/phase6/messages/Request.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/messages/Request.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/messages/Request.java 2006-08-20
22:58:19 UTC (rev 10220)
@@ -0,0 +1,30 @@
+package messages;
+
+public class Request extends Message
+{
+ private static int nextId = 0;
+
+ public final int id; // The unique ID of the request
+ public final int key; // The requested key
+
+ // Start a new request
+ public Request (int key)
+ {
+ id = nextId++;
+ this.key = key;
+ size = Message.HEADER_SIZE + Message.ID_SIZE + Message.KEY_SIZE;
+ }
+
+ // Forward a request
+ public Request (int id, int key)
+ {
+ this.id = id;
+ this.key = key;
+ size = Message.HEADER_SIZE + Message.ID_SIZE + Message.KEY_SIZE;
+ }
+
+ public String toString()
+ {
+ return new String ("request (" + id + "," + key + ")");
+ }
+}
Added: trunk/apps/load-balancing-sims/phase6/messages/Response.java
===================================================================
--- trunk/apps/load-balancing-sims/phase5-coalescing/messages/Response.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/messages/Response.java
2006-08-20 22:58:19 UTC (rev 10220)
@@ -0,0 +1,20 @@
+package messages;
+
+public class Response extends Message
+{
+ public final int id; // The unique ID of the request
+ public final int key; // The requested key
+
+ public Response (int id, int key)
+ {
+ this.id = id;
+ this.key = key;
+ size = Message.HEADER_SIZE + Message.ID_SIZE +
+ Message.KEY_SIZE + Message.DATA_SIZE;
+ }
+
+ public String toString()
+ {
+ return new String ("response (" + id + "," + key + ")");
+ }
+}
Added: trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
===================================================================
---
trunk/apps/load-balancing-sims/phase5-coalescing/messages/RouteNotFound.java
2006-08-08 14:39:02 UTC (rev 9966)
+++ trunk/apps/load-balancing-sims/phase6/messages/RouteNotFound.java
2006-08-20 22:58:19 UTC (rev 10220)
@@ -0,0 +1,20 @@
+// Note: for the purposes of this simulation, RejectedLoop and RouteNotFound
+// are equivalent
+
+package messages;
+
+public class RouteNotFound extends Message
+{
+ public final int id; // The unique ID of the request
+
+ public RouteNotFound (int id)
+ {
+ this.id = id;
+ size = Message.HEADER_SIZE + Message.ID_SIZE;
+ }
+
+ public String toString()
+ {
+ return new String ("route not found (" + id + ")");
+ }
+}
