Project 2 - Routing Protocols

Resources

• Project 2 handout: PDF
• Files for this project are in project2.tar.gz
• Frequently Asked Questions
• Grading Rubric

• OPTIONAL: A sample implementation of project 1 (Simple IRC Server) that you may use is in sircd.tar.gz
• OPTIONAL: A graphical tool for generating simple network topologies for this project: graphthing-15441.tar.gz
  (the source code to the program is also available: graphthing-15441-src.tar.gz)
• OPTIONAL: Our reference binary implementation of the routing daemon (srouted). Please make sure your IRC server runs on top of it correctly. It should run on the Andrew x86 Linux machines. reference-srouted.tar.gz

Clarifications / Updates

• GRADING CLARIFICATION: One additional special case was added to regrade criteria.

• BUG FIX: The reference srouted might not correctly send back responses for commands sent to it on the local port if you sent multiple commands in the same write() or send(). This has been fixed in the version above. Thanks to Ian Kalinowski for pointing this out.
• BUG FIX: The rtworkload.pl script for the last extra credit option didn't work correctly (it didn't do anything and just exited with "WORKLOAD FINISHED") on (some?) cluster machines. Thanks to Pongsin Poosankam for isolating the problem and fixing this.
• BUG FIX: The genworkload.pl script for the last extra credit option (and if you wanted to use it for testing) had a bug where all the port numbers in the config file was 6667. This has been fixed in the project2.tar.gz tarball above.
• TYPO: The genconfig.pl script said that if you didn't have a group number to choose a random number between 120 < x < 4500. This should be 120 < x < 450, as otherwise the port numbers generated will be too large (bigger than 2¹⁶). Everyone should have a group number though, so you should be using that number.

• TYPO: In Section 5.2 of the handout (DSR Protocol Specification), the Destination field says should say:

  "In a both a ROUTE_DISCOVERY and a ROUTE_REPLY packet, the name of the destination nick that is being searched for."

  This has been fixed in the handout PDF above. (Note that this is not a critical fix, as the destination field is really unnecessary in the ROUTE_REPLY since you can already match it up with the ROUTE_DISCOVERY using the sequence number)

• REFERENCE IMPLEMENTATION: We have provided a sample implementation of the routing daemon (srouted) above. Please make sure that your IRC server can talk to it correctly as we will use it instead of your routing daemon to test (to avoid penalizing you twice for routing daemon bugs). Note that our implementation supports several features that you do not have to implement: namely, it supports multiple connections to the local port, and prints informative error messages if you send invalid commands to the local port.

• CLARIFICATION: To help you debug and to ensure that your programs don't accidently fail during our testing, please set the SO_REUSEADDR socket option on all your TCP sockets that listen for incoming connection (i.e., that you call bind on). This will eliminate the "Address already in use" errors from the bind() call if you reuse the same port very soon after killing an old server. In other words, before you bind the TCP socket, call:

  int optval = 1;
  setsockopt(listenfd, SOL_SOCKET, SO_REUSEADDR, 
  	   (const void *)&optval , sizeof(int));
  /* check for errors! */
  

• BUG FIX: In our sample IRC server implementation, there is a bug on the main function in the file sircd.c. THe lines that say:

  while (ready && (current_fd < max_fd)){
  	if (FD_ISSET(current_fd, &read_fds)){
  		service_client(current_fd);
  		ready --;
  	}
  	current_fd ++;
  }
  

  Should instead say:

  while (ready && (current_fd < max_fd)){
          if (current_fd != listen_sock && FD_ISSET(current_fd, &read_fds)){
                  service_client(current_fd);
                  ready --;
          }       
          current_fd ++;
  }
  

  This has been fixed in the sample implementation above. Ignore this if you didn't use the sample implementation.
• BUG FIX: In our sample IRC server implementation, there is a bug in the accept_new_client function in the file sircd.c. The lines that say:

  clnt = new_client(new_sock, hent->h_name);
  

  Should instead say:

  clnt = new_client(new_sock, hent ? hent->h_name : inet_ntoa(cltaddr.sin_addr));
  

  This is in case gethostbyaddr fails to find a mapping for the host ip address (which can happen if the client has a private IP address for example). This has been fixed in the sample code above. Ignore this if you didn't use the sample IRC server.

• CLARIFICATION: In DVR, you should not add a route with infinite distance to your routing table if the destination is not already in there.
• CLARIFICATION: In DVR, when a route is set to infinity, the garbage collection timeout begins and is *not* restarted if you get another update that is infinity.

• TYPO: In Section 5.3 (page 8), DSR Requirements, the second point should say:

  2. A route discovery packet should not traverse the same path more than once (i.e., it should not go in a loop)

  This has been corrected in the above handout.

• TYPO: In section 5.2 (page 7), the Destination field said:

  "In a ROUTE_DISCOVERY packet, the name of the destination node or document being searched for..."

  This should instead say:

  "In a ROUTE_DISCOVERY packet, the name of the destination nick being searched for..."

  And the Path size field said:

  "... This is incremented each time a new node ID or document is appended to the path field."

  This should instead say:

  "... This is incremented each time a new nodeID is appended to the path field."

  Thanks to Ahmed Hussain for pointing this out. This has been fixed in the handout PDF above.

• EXTRA TOOL: A simple graphical interface for generating network topologies is now available above (it is also included in the ./util directory of the main tarball). See the enclosed README for documentation.

• TYPO: The example network spec in genconfig.pl was wrong. It should have been:

  1 2 3
  2 1 3 5
  3 1 2 4
  3 1 2
  4 3 5
  5 2 4 6
  6 5
  

  It has been fixed in the new tarball (note: the original code was not changed, just the example in the documentation). Thanks to Ricardo Colon for pointing that out.

• CODE FIX: A minor fix has been made to the optional project files rtlib.c that prevented the command line from being parsed correctly on Mac OS X/Darwin and possibly other *BSDs. (Note that we will only test on the Andrew Linux machines; this update is just a convenience)
• SIMPLIFICATION: You may assume that no routing packet (for DVR or DSR) will exceed 1012 bytes. Note that this means if your routing table has more than 50 entries (in DVR), it will not fit in a single packet. If there are more, you may break up a routing advertisement into multiple packets (we will not test with more than 50 destinations). [Remember that rt_recvfrom(...) will discard any bytes in the packet that do not fit in the buffer. You might want to think about why we don't want to set the packet size much larger than 1KB -- Hint: think about IP packet fragmentation.]
• SIMPLIFICATION: You may assume that no line in the local port mini-protocol will exceed 512 bytes (including the trailing newline).