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 source file (and any other helper Java source files you devise) using the turnin command on
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.


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:

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 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.
ID    FrOff   Len  MF
1234      0  1000   1
1234   1000   500   1
1234   1500   500   0

Packet 1234, 2000 bytes

[Revised 2014 Oct 29 11:35 DWB]