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.
Here is a simple DefragmentRunner.java with main program to run the project.
Packet 1234, 2000 bytes
[Revised 2018 Oct 22 10:50 DWB]