2 /* Copyright (c) 2010. The SimGrid Team.
3 * All rights reserved. */
5 /* This program is free software; you can redistribute it and/or modify it
6 * under the terms of the license (GNU LGPL) which comes with this package. */
8 import org.simgrid.msg.Host;
10 import org.simgrid.msg.Comm;
11 import org.simgrid.msg.Msg;
12 import org.simgrid.msg.MsgException;
13 import org.simgrid.msg.Process;
14 import org.simgrid.msg.Task;
16 * Main class of the simulation, contains the logic of a node.
18 public class Node extends Process {
26 protected RoutingTable table;
30 protected int deadline;
32 * FIND_NODE which have succeeded.
34 protected int findNodeSuccedded = 0;
36 * FIND_NODE which have failed
38 protected int findNodeFailed = 0;
42 public Node(Host host, String name, String[]args) {
43 super(host,name,args);
47 public void main(String[] args) throws MsgException {
48 //Check the number of arguments.
49 if (args.length != 2 && args.length != 3) {
50 Msg.info("Wrong argument count.");
53 this.id = Integer.valueOf(args[0]);
54 this.table = new RoutingTable(this.id);
56 if (args.length == 3) {
57 this.deadline = Integer.valueOf(args[2]).intValue();
58 Msg.info("Hi, I'm going to join the network with the id " + id + "!");
59 if (joinNetwork(Integer.valueOf(args[1]))) {
63 Msg.info("I couldn't join the network :(");
67 this.deadline = Integer.valueOf(args[1]).intValue();
68 Msg.info("Hi, I'm going to create the network with the id " + id + "!");
69 table.update(this.id);
72 Msg.debug("I'm leaving the network");
73 Msg.debug("Here is my routing table:" + table);
78 public void mainLoop() {
79 double next_lookup_time = Msg.getClock() + Common.RANDOM_LOOKUP_INTERVAL;
80 while (Msg.getClock() < this.deadline) {
83 comm = Task.irecv(Integer.toString(id));
86 if (Msg.getClock() >= next_lookup_time) {
88 next_lookup_time += Common.RANDOM_LOOKUP_INTERVAL;
95 Task task = comm.getTask();
100 catch (Exception e) {
104 Msg.info(findNodeSuccedded + "/" + (findNodeSuccedded + findNodeFailed) + " FIND_NODE have succedded.");
107 * @brief Try to make the node join the network
108 * @param idKnown Id of someone we know in the system
110 public boolean joinNetwork(int idKnown) {
111 boolean answerGot = false;
112 double timeBegin = Msg.getClock();
113 Msg.debug("Joining the network knowing " + idKnown);
114 //Add ourselves and the node we know to our routing table
115 table.update(this.id);
116 table.update(idKnown);
117 //Send a "FIND_NODE" to the node we know.
118 sendFindNode(idKnown,this.id);
119 //Wait for the answer.
125 comm = Task.irecv(Integer.toString(id));
132 Task task = comm.getTask();
133 if (task instanceof FindNodeAnswerTask) {
135 //Retrieve the node list and ping them
136 FindNodeAnswerTask answerTask = (FindNodeAnswerTask)task;
137 Answer answer = answerTask.getAnswer();
140 if (answer.getDestinationId() == this.id) {
141 //Ping everyone in the list
142 for (Contact c : answer.getNodes()) {
143 table.update(c.getId());
155 catch (Exception ex) {
157 Msg.info("FIND_NODE failed");
159 } while (!answerGot && trials < Common.MAX_JOIN_TRIALS);
160 /* Second step: Send a FIND_NODE in a node in each bucket */
161 int bucketId = table.findBucket(idKnown).getId();
162 for (int i = 0; ((bucketId - i) > 0 ||
163 (bucketId + i) <= Common.IDENTIFIER_SIZE) &&
164 i < Common.JOIN_BUCKETS_QUERIES; i++) {
165 if (bucketId - i > 0) {
166 int idInBucket = table.getIdInPrefix(this.id,bucketId - i);
167 this.findNode(idInBucket,false);
169 if (bucketId + i <= Common.IDENTIFIER_SIZE) {
170 int idInBucket = table.getIdInPrefix(this.id,bucketId + i);
171 findNode(idInBucket,false);
174 Msg.debug("Time spent:" + (Msg.getClock() - timeBegin));
178 * Send a request to find a node in the node's routing table.
180 public boolean findNode(int destination, boolean counts) {
181 int queries, answers, totalQueries = 0, totalAnswers = 0;
183 boolean destinationFound = false;
185 double timeBeginReceive;
186 double timeout, globalTimeout = Msg.getClock() + Common.FIND_NODE_GLOBAL_TIMEOUT;
187 //Build a list of the closest nodes we already know.
188 Answer nodeList = table.findClosest(destination);
189 Msg.debug("Doing a FIND_NODE on " + destination);
191 timeBeginReceive = Msg.getClock();
193 queries = this.sendFindNodeToBest(nodeList);
194 totalQueries += queries;
196 timeout = Msg.getClock() + Common.FIND_NODE_TIMEOUT;
201 comm = Task.irecv(Integer.toString(id));
207 Task task = comm.getTask();
208 if (task instanceof FindNodeAnswerTask) {
209 FindNodeAnswerTask answerTask = (FindNodeAnswerTask)task;
210 //Check if we received what we are looking for.
211 if (answerTask.getDestinationId() == destination) {
212 table.update(answerTask.getSenderId());
213 //Add the answer to our routing table
214 for (Contact c: answerTask.getAnswer().getNodes()) {
215 table.update(c.getId());
220 nodesAdded = nodeList.merge(answerTask.getAnswer());
224 timeout += Msg.getClock() - timeBeginReceive;
225 timeBeginReceive = Msg.getClock();
230 timeout += Msg.getClock() - timeBeginReceive;
231 timeBeginReceive = Msg.getClock();
236 catch (Exception e) {
239 } while (answers < queries && Msg.getClock() < timeout);
240 destinationFound = nodeList.destinationFound();
241 } while (!destinationFound && (nodesAdded > 0 || answers == 0) && Msg.getClock() < globalTimeout && steps < Common.MAX_STEPS);
243 if (destinationFound) {
247 Msg.debug("Find node on " + destination + " succedded with " + totalQueries + " queries and " + totalAnswers + " answers");
250 Msg.debug("Find node on " + destination + " failed");
251 Msg.debug("Queried " + queries + " nodes to find " + destination + ", got " + totalAnswers + " answers");
252 Msg.debug(nodeList.toString());
257 return destinationFound;
260 * Sends a "PING" request to a node
261 * @param destination Ping destination id.
263 public void ping(int destination) {
264 boolean destinationFound = false;
265 double timeout = Msg.getClock() + Common.PING_TIMEOUT;
266 PingTask pingTask = new PingTask(this.id);
267 /* Sending the ping task */
268 pingTask.dsend(Integer.toString(destination));
272 Task task = Task.receive(Integer.toString(this.id),Common.PING_TIMEOUT);
273 if (task instanceof PingAnswerTask) {
274 PingAnswerTask answerTask = (PingAnswerTask)task;
275 if (answerTask.getSenderId() == destination) {
276 this.table.update(destination);
277 destinationFound = true;
288 catch (Exception ex) {
290 } while (Msg.getClock() < timeout && !destinationFound);
293 * Sends a "FIND_NODE" request (task) to a node we know.
294 * @brief id Id of the node we are querying
295 * @brief destination id of the node we are trying to find.
297 public void sendFindNode(int id, int destination) {
298 Msg.debug("Sending a FIND_NODE to " + Integer.toString(id) + " to find " + destination );
299 FindNodeTask task = new FindNodeTask(this.id,destination);
300 task.dsend(Integer.toString(id));
303 * Sends a "FIND_NODE" request to the best "alpha" nodes in a node
306 public int sendFindNodeToBest(Answer nodeList) {
307 int destination = nodeList.getDestinationId();
309 for (i = 0; i < Common.alpha && i < nodeList.size(); i++) {
310 Contact node = nodeList.getNodes().get(i);
311 if (node.getId() != this.id) {
312 this.sendFindNode(node.getId(),destination);
318 * Does a random lookup
320 public void randomLookup() {
324 * Handles an incomming task
325 * @param task The task we need to handle
327 public void handleTask(Task task) {
328 if (task instanceof KademliaTask) {
329 table.update(((KademliaTask) task).getSenderId());
330 if (task instanceof FindNodeTask) {
331 handleFindNode((FindNodeTask)task);
333 else if (task instanceof PingTask) {
334 handlePing((PingTask)task);
338 public void handleFindNode(FindNodeTask task) {
339 Msg.debug("Received a FIND_NODE from " + task.getSenderId());
340 Answer answer = table.findClosest(task.getDestination());
341 FindNodeAnswerTask taskToSend = new FindNodeAnswerTask(this.id,task.getDestination(),answer);
342 taskToSend.dsend(Integer.toString(task.getSenderId()));
344 public void handlePing(PingTask task) {
345 Msg.debug("Received a PING from " + task.getSenderId());
346 PingAnswerTask taskToSend = new PingAnswerTask(this.id);
347 taskToSend.dsend(Integer.toString(task.getSenderId()));