CS475: Computer Networks - Traceroute (100 Points)

Assignment Goals

The goals of this assignment are:
  1. To implement a socket-based client
  2. To construct a message given a protocol specification format

Background Reading and References

Please refer to the following readings and examples offering templates to help get you started:

The Assignment

In this assignment, you will write an ICMP Ping program, and modify it to support the functionality of traceroute.

Part 1: The Ping Protocol

Investigate the ICMP RFC to discover the message format for a ping echo and echo reply message. ICMP messages use a checksum, so you will first construct the ping packet, compute its checksum, and then insert the checksum into the message data structure. Construct a sample ping message, and send a raw socket IP packet to the server of your choice. Await a reply, extract the message parameters from the packet into the same structure, and print them to the screen.

Part 2: Traceroute

Encapsulate your ping functionality from part 1 into a function, and call that function in a loop. Increment your sequence number and time-to-live (TTL) value on each packet sent. When you receive a response, compute and verify its checksum, extract and verify its sequence number (which should match your most recently sent checksum), and print its contents to the screen. Continue this loop while the ICMP code received is the TTL Expired message (ICMP code 11). Print the time elapsed between the time you sent this packet and the time you received this response, and the source IP address that sent you the reply. When you receive an ICMP Echo Reply message (ICMP code 0), do the same, but stop the loop. If you do not receive a reply for a particular TTL hop after some timeout that you may choose, print asterisks to the screen to indicate that no reply was received, and continue.

Socket Timeout

You can set a socket timeout in case a node doesn’t send you back an ICMP packet. When you set up your socket variable, if you call:

sock.settimeout(5)

This will set a timeout of 5 seconds. When you call:

try:
    packet, src = sock.recfrom(1024)
    # your code here to process the packet...
except socket.timeout:
    print("Timeout waiting for ICMP response")

You can catch an exception if the socket times out on receive, so that you don’t end up stuck in an infinite loop. You can modify your while loop so that you also quit the loop if the ttl reaches a certain value, like 16, indicating that you are in such an infinite loop.

Message Packing and Unpacking Using Python

In Python, you can use the struct package to bit-pack your messages for transmission according to a given protocol format. For example, an ICMP packet consists of the following fields, where the multi-byte fields are in network (big-endian) byte order:

  • 1 byte for the ICMP message type
  • 1 byte for the ICMP code
  • 1 unsigned short (2 bytes) for the checksum
  • 1 unsigned short (2 bytes) for the packet ID
  • 1 signed short (2 bytes) for the sequence number

We can represent this in Python easily using the struct package as follows:

import struct

format = '!BBHHh' # byte, byte, short (2 bytes), short, short, in ! network byte big-endian order
message = struct.pack(format, 0, 0, 0, 0, 0) # replace the 0's with each value specified in the format string

Similarly, struct.unpack takes a format string and a byte array, and returns a collection of variables, one for each field:

import struct

type, code, checksum, id, seq = struct.unpack(format, message) # see message and format above

Other Hints

Don’t forget to re-initialize your variables each time through the loop (for example, your checksum should start out as 0, and your initial icmptype is 8)! You should set the TTL each time through the loop (incrementing by 1 each time).

Submission

In your submission, please include answers to any questions asked on the assignment page in your README file. If you wrote code as part of this assignment, please describe your design, approach, and implementation in your README file as well. Finally, include answers to the following questions:
  • Describe what you did, how you did it, what challenges you encountered, and how you solved them.
  • Please answer any questions found throughout the narrative of this assignment.
  • If collaboration with a buddy was permitted, did you work with a buddy on this assignment? If so, who? If not, do you certify that this submission represents your own original work?
  • Please identify any and all portions of your submission that were not originally written by you (for example, code originally written by your buddy, or anything taken or adapted from a non-classroom resource). It is always OK to use your textbook and instructor notes; however, you are certifying that any portions not designated as coming from an outside person or source are your own original work.
  • Approximately how many hours it took you to finish this assignment (I will not judge you for this at all...I am simply using it to gauge if the assignments are too easy or hard)?
  • Your overall impression of the assignment. Did you love it, hate it, or were you neutral? One word answers are fine, but if you have any suggestions for the future let me know.
  • Using the grading specifications on this page, discuss briefly the grade you would give yourself and why. Discuss each item in the grading specification.
  • Any other concerns that you have. For instance, if you have a bug that you were unable to solve but you made progress, write that here. The more you articulate the problem the more partial credit you will receive (it is fine to leave this blank).

Assignment Rubric

Description Pre-Emerging (< 50%) Beginning (50%) Progressing (85%) Proficient (100%)
Algorithm Implementation (60%) The algorithm fails on the test inputs due to major issues, or the program fails to compile and/or run The algorithm fails on the test inputs due to one or more minor issues The algorithm is implemented to solve the problem correctly according to given test inputs, but would fail if executed in a general case due to a minor issue or omission in the algorithm design or implementation A reasonable algorithm is implemented to solve the problem which correctly solves the problem according to the given test inputs, and would be reasonably expected to solve the problem in the general case
Code Quality and Documentation (30%) Code commenting and structure are absent, or code structure departs significantly from best practice, and/or the code departs significantly from the style guide Code commenting and structure is limited in ways that reduce the readability of the program, and/or there are minor departures from the style guide Code documentation is present that re-states the explicit code definitions, and/or code is written that mostly adheres to the style guide Code is documented at non-trivial points in a manner that enhances the readability of the program, and code is written according to the style guide
Writeup and Submission (10%) An incomplete submission is provided The program is submitted, but not according to the directions in one or more ways (for example, because it is lacking a readme writeup) The program is submitted according to the directions with a minor omission or correction needed, and with at least superficial responses to the bolded questions throughout The program is submitted according to the directions, including a readme writeup describing the solution, and thoughtful answers to the bolded questions throughout

Please refer to the Style Guide for code quality examples and guidelines.