COSC 2010 / 2100 Data Structures

Fall 2014

Homework Assignment #6 : Internet Packet Defragmentation

"I was never one to patiently pick up broken fragments and glue them together again
and tell myself that the mended whole was as good as new.
What is broken is broken - and I'd rather remember it as it was at its best
than mend it and see the broken places as long as I lived."
-- Margaret Mitchell

Due: Thursday, October 30th, Noon CDT
Submit: Turn in your Defragment.java source file (and any other helper Java source files you devise) using the turnin command on morbius.mscs.mu.edu.
Work may be completed in teams of two.
Be certain to include both partner's names in your file. Try to avoid both partners submitting code -- we have to grade that twice, and only the lower grade will be kept.
You may submit multiple times, but only the last turnin will be kept. The automatic submission system will not accept work after the deadline.

The Truth About Our Fragmented Internet

In COSC 4300 - Networks and Internets, we learn that data is sent over the Internet in discrete chunks of bytes called packets, following a scheme known as the Internet Protocol (version 4), or just IPv4 for short.

IPv4 packets can be up to 64KB (65,536 bytes) in length, but the underlying networking hardware often can only support smaller sizes. Traditional Ethernet, for example, sends only about 1500 bytes of data at a time. As a result, IPv4 packets on the Internet can often be fragmented, which simply means that they are chopped into smaller pieces for transmission.

Adding to the complexity of this system, IPv4 is what is called a best effort system. Travelling through a complex web of interconnected hosts and routers, packets on the Internet may arrive late, out of order, duplicated, or not at all.

Internetworking is a complex topic beyond the scope of our current course, but we're going to build a data structure that models parts of what every computer connected to the Internet must do to correctly reassemble IPv4 packet fragments.

Defragmenter

Build a Defragment class with two public methods: addFrag and toString. The addFrag method will be called each time a new packet fragment arrives. Each fragment will come with four pieces of information:

• Packet ID. Each fragment will have a packet ID number. This number will identify the original packet that the fragment came from. You can use the Packet ID to group fragments together as you reassemble them.
• Fragment Offset. The Fragment Offset is the number of bytes this fragment is from the beginning of the original packet. A Fragment Offset of zero indicates the first fragment of a packet; a Fragment Offset of 65,535 would indicate a fragment that starts at the very last byte of a packet. On the real Internet, the Fragment Offset must always be a multiple of 8; for this assignment, you should not make that assumption.
• Fragment Length. Each fragment will contain a positive number of bytes. On the real Internet, fragments lengths are frequently about 1500 bytes, but the length could be as small as 1 or as large as 65,536.
• More Fragments Bit. Each fragment includes a bit (zero or one) indicating whether there are more fragments from the original packet. The very last fragment of a packet will always contain a More Fragments value of zero; all previous fragments will have a one.

Your declaration for the addFrag method will thus be:

public void addFrag(int id, int froff, int length, boolean morefrag);

Your implementation should make use of several instances of the List ADT from the textbook -- a list of fragments for a given packet that is currently being reassembled; you could be reassembling several packets at once, so you will need a list of such lists; and a list of packets that have been completely reassembled. Several of these lists could be sorted and/or indexed; it is up to you whether to use linked- or array-based implementations. Do not rely on the built-in Java collection class libraries, such as ArrayList, Vector, and their friends.

Getting simple testcases to work for this program should be quite straightforward. Working on a single Packet ID, with only a single fragment should be the second testcase (after empty input.) A single packet where the fragments all arrive, in order, is the next simplest.

More complex testcases quickly reveal themselves, however. Each fragment you receive could be part of some new, previously unseen packet. You should be able to have an arbitrary number of packet reassemblies in progress, with fragments from various different packets interleaved randomly. Use unbounded data structures that will grow with the size of the input -- there is no bound on the number of packets this should be able to defragment.

Packet fragments may arrive in any order -- so you may see the middle or the end of a packet before you see any other parts. You will not know how long a packet was until you receive a fragment that has the More Fragments Bit set to zero.

Packets can be duplicated, so you may receive fragments that contain all or part of data that you have already received. Duplicate packets will not necessarily start with the same offset or ending point as previous fragments.

Fragments may not arrive at all. When the simulation ends (your program reaches the end of input), you should discard any packet fragments that do not belong to a fully reassembled packet. You will want a helper method to determine when all of the fragments of a given packet have been recieved.

When the program ends, a call to the toString method should return a String with a line for each reassembled packet, listed in ascending order by Packet ID. Each line must consist of a Packet ID and the final byte length of the packet.

Input

Input to the Defragment simulator will consist of a single header line (which you can ignore,) followed by packet fragment descriptions. Each packet fragment description line will have a Packet ID, Fragment Offset, Fragment Length, and a More Fragments Bit.

Example Run #1

A 2000-byte packet with ID 1234, in three chunks.
Input:

Output: