Fishnet Assignment 1: Ping and Flood

In this assignment, you will work in teams of two to develop a single C program that is a Fishnet node. We will extend the nodes and network with functionality throughout the quarter. The goals of this first assignment are to become familiar with the Fishnet development environment and to understand packet forwarding concepts.

0 News

1. May 3: add this 0 News section
2. May 2: TA is holding lab hour on Monday May 5 3pm-5pm in uAPE lab(same lab)
3. May 2: Packet identification specification change (red line in Flooding 4)
4. April 31: Flooding specification change (red line in Flooding 2)

1 Preliminaries

1. Subscribe the class mailing list (instruction is on the class page).

2. Work through the Introduction to Fishnet handout.

2 What to Develop

1. Flooding

   Your node "floods" each packet it handles so that the packet reaches all other nodes connected to the network. You decide how flooding functionality with the following constraints:

   1. A node broadcasts a packet by calling fish_send(ALL_NEIGHBORS, <packet>)

   2. A node MUST broadcast every received packet, unless it has received that packet before or the ttl of the packet reaches 0. The node MAY not flood the packet if it is only (i.e. non-broadcast) destined to the node

   3. Two packets are consider identical if they have the same source address, destination address and packet id.

   4. Two packets are consider identical if they have the same source address and packet id.

2. Ping

   Your node can "ping" another node (bounce a packet off of it) to check that it is working. You implement ping with the folloing constraints:

   1. The command are "p <dest_addr>" and "pa" to ping a single node or all nodes. The space is a single space character.

   2. A ping request is a packet of struct echo_packet with code field ECHO_PROTOCOL_REQUEST.

   3. A ping response is a packet of struct echo_packet with code field ECHO_PROTOCOL_REPLY.

   4. A node MUST reply a ping request that destined to the node or the ALL_NEIGHBORS address, by sending a ping response to the source node of the ping request. You MAY not reply if the source and the destination of the request are the same (the sample solution doesn't).

3. Neighbor Discovery

   Your node continuously probes the network to discover its neighbors in the network topology with these constraints:

   1. The commands are "n" and "xn" to start and stop neighbor discovery respectively. The space is a single space character.

   2. You MUST use the Ping mechanism defined above

   3. The probing rate should be no less than 2000 milli seconds per probe

   Note you discover, not decide who your neighbors are. You will need to use timers fish_scheduleevent(), to implement periodic background activity. Also check the real topology at http://[hostname running fishhead]:[port] to verify your neighbor discovery works right.

3 Design Philosophy

Robustness Principle

An important rule of thumb in building network protocols is Be conservative in what you do, be liberal in what you accept from others.. This helps different implementations of a protocol (e.g., the sample solution, your program, and your classmates programs) to work together reliably. This principle means you should be careful to send packets that strictly comply with the intended usage of the packet formats as described in fish.h so that other nodes can handle them, but you should do the best you can with whatever packets you receive from other nodes. Of course, you will get it right, but they will send broken packets. In particular, other nodes shouldn't be able to crash your node by sending it bad packets. If your node does crash, it's your responsibility to find out what happened and fix it.

Interoperable Designs

It is also possible that different students will design protocols that are not compatible with each other in the class Fishnet, even if everyone's code is robust as defined above. We hope that strict adherence to the packet formats and their intended usage will result in compatible protocols, without any further revisions for specifications or constraints on your designs, but we can't guarantee this. Therefore, you must check that your implementation interoperates with the sample executable (hw1-sol). It is everyone's responsibility to work towards compatible, interoperable protocol designs. We can do this by checking incompatibilities and discovering what further design details we need to make together, as a class. This is a very real issue in the Internet, and part of what you will learn during the course.

Simple and Elegant Implementation

The above constitutes the intellectual bulk of your assignment. It is probably simplest to implement the functions in the order they are given above. As you write your program, keep in mind we are expecting robust, interoperable and neat code, not complex data strucutures or algorithms. If you are writing thousands of lines of code then you are probably doing something the hard way and should talk to us about it. In the end, well structured, self-explanatory code with necessary comment is always better than heavy-commented but messy code.

4 Discussion Questions

1. Describe one advantage and one disadvantage of the "upcall" style of programming.

   Upcall programming is particularly good for network (or layering) implmentations. The upper layer only has to register events with their event handlers, this allows flexibility that different layer implementations with a simple interface. The downside is harder to control because event occurs asychronously, and memory leaks are harder to trace because data structures are passed between different functions possibly implemented by different people.

2. Flooding includes a mechanism to prevent packets from circulating indefinitely, and the TTL field provides another such mechanism. Why have both? What would happen if we only had flooding checks? What would happen if we had only the TTL?

   Both flooding checks and TTL checks can prevent packets from looping forever. The main reason is efficiency: Let's suppose we have two networks consist 3 nodes and 10000 nodes respectively. Flooding is much more effective in small network because the packet disappears once it has visited every node twice while the packet will bounce O(TTL) times before it got pruned. On the other hand, TTL is much more effective in large networks such as Internet, because it ensures the spread area is never beyond diameter TTL. Note both mechanisms require nodes to be co-operative, a malicious node can create forever loops by not decreasing the TTL or simply increasing the packet id.

3. When your node pings a remote node using its particular destination address (rather than the network broadcast address), how many requests does the remote node receive and why? How many responses does your node receive and why?

   The number of duplicates received equals the number of neighbors, because new packet gets flooded to every node at most twice. Same as echo replies.

4. When your node pings a remote node using its particular destination address (rather than the network broadcast address), how many request and response packets do other nodes handle? How many of these packets are unnecessary, and could probably be eliminated with smarter networking protocols?

   The number of duplicates received equals the number of neighbors of that node. If the packet follow the shortest path to the destination, only the nodes along the path will receive (and forward) those packets. This can possibly eliminate O(N) packets if the path length is a small constant.

5. Describe one design decision you could have made differently (if you are allowed to change Fishnet) and the pros and cons compared to the decision you made.

   We accept any answers that make sense.

5 Test and Turn-In

1. Login into ieng9.ucsd.edu

2. Make sure your program compiles with the make hw1 command.

3. Run three nodes using your program hw1 only. Then run three nodes using our sample solution hw1-sol program. Try to ping each other from every node under different fishnet topology (do ./fishhead -h for topology options)

4. Answer the discussion questions in the end of hw1.c

5. Put all team member names and emails at the end of hw1.c

6. Use turnin in ieng9.ucsd.edu to turn in hw1.c
   

   turnin -c cs123b hw1.c

6 Grading

1. Program correctness (6 points) - we will test your program with normal cases.

2. Program robustness (4 points) - we will test your program with other cases like corrupted packets.

3. Program structure (2 points)

4. Discussion Questions (10 points) - This part will NOT be graded if you did not write the code

April 24, 2003
UCSD CSE123b Communications Software