Lab 1: Getting to Know Your Neighbours

Assigned: 26 Jul 2021 (Monday)
Due: 8 Aug 2021 (Sunday) for Part(a) - capture files, topology files, and source code for Part (a);
5 Sep 2021 (Sunday) for Part(b) - capture files, and source code for Part (b) and report for both parts;
SUBMISSION OF REASONABLE ATTEMPTS FOR BOTH PARTS ARE MANDATORY.
Value: 20%

Problem

One of the most fundamental protocols in computer networks is neighbor discovery -- getting to know the identities of other nodes that are directly reachable or belong to the same subnet. To understand how these fundamental protocols work, this lab will ask you to implement: (a) the address resolution function for IPv4; and (b) a learning switch to deal with unknown traffic. The lab is divided into two (2) parts, as explained below.

Part (a) - Address Resolution

This is used to resolve link layer addresses based on a prior known network layer address; it is a critical function in multiple-access networks. This protocol can be considered a method of routing within a single hop network segment such as Ethernet, Wifi, Zigbee, etc. Address Resolution Protocol (ARP) is the protocol used in IPv4.

Part (b) - Learning Switch

Switches are used to connect several machines with a local area network and prevent link-layer traffic from being sent to all hosts on the LAN by learning which machines are connected via which ports.

Both Part (a) and Part (b) will be implemented within the CORE network emulation environment. You will be provided with scaffolding code so that you will only need to focus on implementing the core logic of your design. The scaffolding code are written in the C programming language, and the points where you need to insert your own code are indicated. Before diving to implement the requirements, familiarise yourself with the given code, as well as the available functions that you can use to implement your ideas.

tip icon.jpg

This lab handout is in no way a complete or accurate reference to the protocols you will be implementing. Do your own research, find out as much as you can about the protocols and use that as the basis of your implementation. Remember to credit, i.e. cite, the source(s) of your information.

Resizing Disk Size

The size of the virtual disk used by the VM file system needs to be resized. (You can skip this part if you have already done this in Lab 0.) To do this, just connect a terminal to the running VM, then execute the following commands:
$ sudo lvm
lvm> lvextend -l +100%FREE /dev/ubuntu-vg/ubuntu-lv
lvm> exit


$ sudo resize2fs /dev/ubuntu-vg/ubuntu-lv 

For the changes to take effect, you need to restart the VM. You can do this by executing the following commands:
$ sudo shutdown -r now

Install Wireshark

You will be using Wireshark in the lab to capture and examine packets. Wireshark is a packet capture tool similar to tcpdump but with a user-friendly graphical interface. Keep in mind however that Wireshark requires more memory than tcpdump. To install Wireshark in the VM, just type the following command on the terminal

$ sudo apt install wireshark

When asked, allow normal (non-root or non-superusers) users to run Wireshark.

Lab Setup

You will need to copy the scaffolding code and other relevant files to the running VM. These files are all included in the archive nwen302-lab1-1.1.tar.gz. Create a directory in the VM where you want to copy the file. After you have copied the file, connect a terminal to the VM, then execute the following commands to extract the files from the archive:

$ cd to_where_you_copied_the_file
$ tar zxvf nwen302-lab1-1.1.tar.gz

Check the contents of the directory. It should contain three directories:

arp
lswitch
core

You may want to take some time to examine the contents of the two directories.

tip icon.jpg

Once you start editing the files, it is good practice to regularly backup these files somewhere outside the VM. When you need to pause the exercise and resume it later, always stop your CORE session, exit CORE, and shutdown the VM gracefully. Do not just exit VirtualBox. To gracefully shutdown the VM, you can either select Machine -> ACPI Shutdown on the VM Window, or type sudo poweroff on a terminal connected to the VM.

The scaffolding code may contain errors and bugs. If you found one, please alert the tutor or e-mail the course coordinator about it. We will release updated versions of the scaffolding code should we (or you) discover major bugs. You will receive an e-mail in case such updated versions are released.

HINT: You can download the required files to your VM by using the program wget. On the VM use the command 'wget https://link-to-lab-files.tar.gz' to download the files. You can right click on nwen302-lab1-1.1.tar.gz and select 'copy link' to find the correct link to use with wget.

The latest release of the scaffolding code is: nwen302-lab1-1.1.tar.gz
  • This update contains bug fixes to Part(b) and an additional bigger testbed network that you can use for testing in Part(b).

Part (a): Address Resolution

In this part of the lab, you will be guided on how to create your first network in CORE. You will use this simple network to observe how the Address Resolution Protocol (ARP) works. After that, you will then write C code to implement your own version of ARP, using the observations you have made, and by consulting appropriate sources.

General advise when researching for sources: prefer books and published academic papers over regular Internet articles or Wikipedia. Published academic papers (from IEEE, ACM, Springer and Elsevier) underwent rigorous peer-review and should therefore be more reliable and accurate.

Building A Simple Network

One of the key advantages of using CORE is that you can create your own testbed network at no cost. Creating and maintaining a physical testbed network can cost thousands of dollar$. So let us begin by launching CORE. Once the canvas is ready, create a simple LAN which consists 3 hosts connected to an Ethernet hub, as shown below:

lab1 net1.png

Note that the hosts are labeled n1, n2 and n3 whereas the hub is labeled n4. Save the network as lab1-net1.imn.

Start the network emulation session by clicking the play button in CORE. Wait for the session to be ready. Once the session is ready, start a Wireshark on nodes n2 and n3. To run Wireshark on a node, right-click on the node, then select Wireshark. Select the interface that you want to observe (which should be eth0 in this case). In both Wireshark instances, type ip || arp in the filter expression textbox to only show IPv4 and ARP packets. Make sure to apply the filter by clicking the right arrow as shown in the picture below.

lab1 wshark1.png

Open a terminal to node n1 (you can do this by double-clicking on the node). Type the command ping -c 2 10.0.0.21 . This command will send exactly two ping messages to node n2 . Observe the packets captured at the interfaces of both n2 and n3 . Understand the sequence of events by answering the following questions:

  • Qa1: What triggered the ARP query "Who has 10.0.0.21? Tell 10.0.0.20"?
  • Qa2: What is the link layer destination address of the ARP query "Who has 10.0.0.21? Tell 10.0.0.20"? Why?
  • Qa3: Which node generated the ARP reply "10.0.0.21 is at 00:00:00:aa:00:01"? Why?
  • Qa4: What is the link layer destination address of the ARP reply "10.0.0.21 is at 00:00:00:aa:00:01"? Why did node n3 receive the reply as well?
  • Qa5: What triggered the ARP query "Who has 10.0.0.20? Tell 10.0.0.21"?
  • Qa6: Compare the delays encountered by the first ping and second ping. Explain why the delays are different.
Now, let us observe the behaviour of ARP if a node is trying to send a packet to a non-existent node. To do this, type the command ping -c 1 10.0.0.100. This will try to send one ping request to a non-existent node (10.0.0.100 is not in your network!).

  • Qa7: How many ARP requests are sent by the sender before it gives up?
Save the Wireshark packet capture as lab1-net1-node2.pcapng (for the node n2 capture) and lab1-net1-node3.pcapng (for the node n3 capture). Close Wireshark and stop the network emulation session.

Using tcpdump Instead of Wireshark

If for some unknown reason your setup is not able to launch Wireshark, you may use tcpdump instead. But you will need to run tcpdump manually from a terminal so that you can specify the filter and output capture file. To run tcpdump with filter ip || arp on interface eth0 and output the capture file to some_capture.pcapng, just type the following command on a terminal (that is connected to the appropriate node):

tcpdump "ip || arp" -i eth0 -w some_capture.pcapng

tip icon.jpg

Thanks to Duncan, we have recently discovered that if you are using Windows and having issues launching Wireshark, you can solve it by (1) uninstalling Xming and (2) installing VcXsrv which you can download from here. After installing VcXsrv, remember to start XLaunch again.

Using an Ethernet Switch

The above network uses a hub which is not an intelligent network device. In this task, you will re-create the above network, but replacing the hub with an Ethernet switch. Save the network as lab1-net2.imn. Repeat the above experiment to observe the packets captured at nodes n2 and n3 when two ping messages are sent from node n1. Answer these questions:

  • Qa8: Did you notice any difference in the packets captured at the two nodes? Explain your observation.
Save the Wireshark packet capture as lab1-net2-node2.pcapng (for the node n2 capture) and lab1-net2-node3.pcapng (for the node n3 capture). Close Wireshark and stop the network emulation session.

Implementing Your Own ARP

With the above observations on how ARP operates, you will now implement your own version of ARP. Note that you will not be implementing ARP from scratch. You will be implementing the functions in the file arp/my_arp.c. Your implementation can use any functions from the standard C library, socket library, as well as the functions defined in arp/arp_functions.h. Your implementation should satisfy the requirements shown in the table below:

Category Details
Core A node requiring a target MAC address is able to obtain the target's MAC address and insert it in the node's ARP cache.
Completion A node is able to handle an ARP request and send back a correct ARP reply.
Challenge Entries in the node's ARP cache that are unused since a pre-defined time interval should be deleted. Note that the kernel will not remove the entries that your program inserted into the ARP cache, so it is your program's responsibility to maintain suitable data structure to monitor the age/expiration time of the entries, and remove expired entries accordingly. Use a default expiration time of 30 seconds.
To compile your code, change directory to where the file arp/my_arp.c is. Then just type make on the command line. Fix the errors as appropriate. make will automatically compile all source code and do the necessary linking to generate the executable file my_arp.

tip icon.jpg

You can enter the command make clean to remove old object files and the executable file. Then run make again to re-compile. This approach will ensure that the latest changes are compiled into the executable file.

To test your code, open the network lab1-net2.imn in CORE. Start the network emulation session. To simplify testing, you only need to run your code in node n1.

When the session is ready, double-click n1 to open a terminal. Assuming that my_arp is in /home/nwen302/lab1/arp, you can enter the following command
/home/nwen302/lab1/arp/my_arp

You will need to open another terminal on node n1 to run ping and other commands. You can follow the steps in "Building A Simple Network" and observe the packets captured at nodes n2 and n3. You can also type the arp command on the terminal connected to node n1 to see if your program is able to insert/delete entries into the ARP cache. You can try out different testing scenarios to make sure that your implementation is correct.

One possible issue that you might observe is that the first ping message is not getting through. This is normal and due to your code taking over the ARP functionality from the kernel.

tip icon.jpg

For node n1 to successfully ping either node n2 or n3, you will need to have implemented the Core and Completion requirements correctly.

Part (b): Learning Switch

In the exercise above involving an Ethernet switch, you should have noticed one distinct behaviour regarding the packets captured at nodes n2 and n3. A switch essentially is an "intelligent" device that "learns" the ports on which hosts can be reached. This allows the switch to transmit a frame on the port where the destination host can be reached instead of transmitting the frame on all ports. This technique therefore allows more nodes to transmit at the same time, thereby improving the network throughput.

In this part of the lab, you will be provided with a simple network that you will use to observe the behaviour of a learning switch and test your own learning switch implementation. So to begin the exercise, run CORE and open the file lab1-lswitch.imn (which you can find under the core/ directory). The network topology should look like this:

lab1 net5.png

A few remarks about this network: Node n4 is not a typical link layer switch. It is actually a Linux host that is configured to have a transparent bridge that links all the three nodes n1, n2 and n3. It is this bridge that your program will be trying to control. Before commencing your learning switch implementation, let us first study the behaviour of the switch. By default, the switch is configured not to learn.

Open a terminal on node n4. To view the switch table (also known as forwarding database in the Linux networking community), type the command

brctl showmacs br0
  • Qb1: What are the entries of the table? Provide a brief explanation of the columns.
Run Wireshark on nodes all the interfaces (eth0, eth1 and eth2) of n4. In all Wireshark instances, type ip || arp in the filter expression textbox to only show IPv4 and ARP packets. Make sure to apply the filter.

Open a terminal on node n1 and type the command ping -c 1 10.0.0.22.
  • Qb2: What did you notice about the packets captures at the 3 interfaces of n4? Explain.
Let us now enable learning on n4. To do this, type the command

brctl setageing br0 1000

Again, type the command ping -c 1 10.0.0.22 at node n1.
  • Qb3: What did you notice about the packets captured at the 3 interfaces of n4? Explain.
Show the switch table of n4 by entering the command brctl showmacs br0.
  • Qb4: What are the new entries in the table?
Save the packet capture as as lab1-n4-eth0.pcapng (for the eth0 capture), lab1-n4-eth1.pcapng (for the eth1 capture), and lab1-n4-eth2.pcapng (for the eth2 capture). Close Wireshark and stop the network emulation session.

Implementing Your Own MAC Learning Algorithm

The behaviour that you have observed above is due to the MAC learning of the switch. You will now implement your own learning algorithm. As in the ARP implementation, you will not be implementing the algorithm from scratch. You will be implementing the functions in lswitch/my_lswitch.c. Your implementation can use any functions from the standard C library, sockets library, as well as the functions defined in lswitch/lswitch_functions.h. Your implementation should satisfy the requirements shown in the table below:

Category Details
Core A node is able to know the location (port) of hosts by looking at frames passing through the node and insert it in the kernel switch table
Completion Entries in the kernel switch table that are unused since a pre-defined time interval should be deleted. Note that the kernel will not remove the entries that your program inserted into the switch table, so it is your program's responsibility to maintain suitable data structure to monitor the age/expiration time of the entries, and remove expired entries. Use a default expiration time of 30 seconds.
Challenge The number of entries in the kernel switch table should not exceed a pre-defined value. Note that the kernel will not monitor the number of entries in the table, so it is your program's responsibility to to maintain suitable data structure monitor the number of entries. If a new needs to be inserted and the table is full, you will need to decide which entry to delete. Provide justification(s) to your implementation decision. Use a default limit of 3 entries.
To compile your code, change directory to where the file lswitch/my_lswitch.c is. Then just type make on the command line. Fix the errors as appropriate. make will automatically compile all source code and do the necessary linking to generate the executable file my_lswitch.

To test your code, open the network lab1-lswitch.imn in CORE. Start the network emulation session. When ready, open a terminal on node n4. Assuming that my_lswitch is in /home/nwen302/lab1/lswitch, you can enter the following command
/home/nwen302/lab1/lswitch/my_lswitch

To know whether your switch is learning, you can monitor all the interfaces of n4 using Wireshark. You can always enter the command brctl showmacs br0 at n4 to show the contents of the switch table.

To test your code in a bigger network, you can load the network lab1-lswitch-8hosts.imn which you can find under the core directory. (There is a bug in the lab1-lswitch-8hosts.imn that came with the package, so please download the separate file manually here: https://ecs.wgtn.ac.nz/foswiki/pub/Courses/NWEN302_2021T2/Lab1/lab1-lswitch-8hosts.imn). Note however that when using this network, you will need to invoke my_lswitch with a parameter 8, i.e.
/home/nwen302/lab1/lswitch/my_lswitch 8

Suggested References

Linux network programming can be difficult so you may want to consult the book by Benvenuti entitled "Understanding Linux Network Internals" which is available online thru the VUW library.

For advanced systems programming in Linux (setting up timers, etc), you may consult the book by Love entitled "Linux System Programming" which is also available online thru the VUW library.

What to Hand in

Due on 8 Aug 2021 (Sunday) for Part(a) - capture files, topology files, and source code for Part (a);

Due on 5 Sep 2021 (Sunday) for Part(b) - capture files, and source code for Part (b) and report for both parts;

SUBMISSION OF REASONABLE ATTEMPTS FOR BOTH PARTS ARE MANDATORY.

  • All relevant code. i.e. all the supplied files and any new ones you’ve added.
    • If you have "borrowed" code from on-line resources and/or other sources, say so in your code comments.
  • All Wireshark packet capture files
  • All CORE topology files
  • A short report (around 1,000 ± 100 words - be concise) describing your development process for BOTH Part (a) and Part (b).
    • Answers to all questions asked in this handout
    • Description of your ARP and learning switch implementation
    • Reflect on what you found easy, what caused you problems and how you overcame those issues.
    • If you believe you have a particularly sophisticated or original implementation, state why you think this is the case.
  • Create either a ZIP or TAR.GZ archive to contain all your files. Please do not submit the files individually. You can organize the contents of the archive to have the following directories:
    • core: to contain all imn files
    • capture: to contain all capture files
    • arp: to contain all ARP code (you need to submit the given files as well)
    • lswitch: to contain all learning switch code (you need to submit the given files as well)
    • report: contain your report

Grading Scheme

Does it work? (70%)

  • Requirements
    • Core - Part (a): 20% and Part (b): 20%
    • Completion - Part (a): 10% and Part (b): 10%
    • Advanced - Part (a): 5% and Part (b): 5%

Are the required files submitted? (5%)

  • Aside from the source code and report, the following files must be submitted
    • Packet capture files (pcapng format)
    • Network topology files (imn format)

Is the code well written? (10%)

  • Part (a): 5% and Part (b): 5%
  • Marks awarded for:
    • Compilation free of errors and/or warnings.
    • Providing documentation to improve clarity of the code.
    • Giving credit to on-line resources you “borrowed" code segments from.
    • Evidence of original work (i.e. not simply having copied other peoples code).
  • Marks deducted for:
    • Not giving credit to on-line resources you “borrowed" code segments from.

Did you understand what you were doing? (15%)

  • The code partially show this, but the report is where you convince me.
  • Marks awarded for:
    • Providing answers to the questions asked in this handout.
    • Clearly stating which functions were implemented and which were not (and why).
    • Description of development process and justifications for implementation decisions.
    • Details of testing methodology.
    • Observations of what was easy, what was hard, where problems arose, how they were overcome.
    • Reflection on how you might improve or extend your solution.
That's the end of this lab. If you have any issues, attend any of the Helpdesk sessions, or e-mail nwen302-staff@ecs.vuw.ac.nz.