CS522 F2004 Homework#3:
Understanding Routing using UML-based Virtual Network and
Protocol Design/Verification

Goal:

Learn virtual machine and virtual network concept.
Learn basic network interface configuration and route setup commands on Linux clients and routers.
Learn the intimate relationship among routing table, gateway, and arp.
Learn how to apply reachability analysis to verify and design protocols.
Learn how time-out helps recover message loss in the alterante bit protocol.
Learn how the alternate bit protocol uses a single control bit to gurantee that one and only one msg (not duplicate msg) gets delivered to the upper layer of the receiver.

Assignment Date: 9/20/2004
Due Day: 9/29/2004
Description:

Part 1. End System and Router Configuration on a Simple UML-based Virtual Network

Exercise 1. Start up UML-bases Virtual Machines on a MS Virtual PC (VPC) 2004-based Fedora Core Virtual Machine

We will use pre-configured a virtual machine fc1uml available on any EAS 138 PC for this exercise. fc1uml was installed using Microsoft VPC 2004. fc1uml is installed with Fedora Core 1 OS with a customized kernel, patched with Separate Kernel Address Space (SKAS) mode and devanon support for running User Mode Linux more efficiently.
If you have enough disk space (3.1GB) and memory say 512MB (this virtual macine is configured to use 256MB), you can either copy the Virtual Disk File and Configuration files from any PC in the EAS 138 lab in c:\virtual machines\cs301\fc1uml directory, or check out a DVD from me. You need to download and install VPC2004 from e-academy in order to run anyh VPC-based virutal machine including fc1uml.
To start up the fc1uml, select start | programs | cs301 | shortcut to fc1uml
You will see a VPC console showing the status of the fc1uml as running, and another window will show fcluml running on a VPC window.
When Fedora Core 1 Linux login window appears, just type in root as login name and the password we announced in class.
When the desktop window appears, right click in the desktop area and select "open terminal" menu-item. This will open up a shell window. Type "cd /home/frank" to switch a directory with user model linux files.
Repat the above step four times to open four other shell windows.
In the first shell window, type the following three commands to set up three virtual switches used by the three subnets 10.0.0.0/24, 10.0.1.0/24 and 10.0.2.0/24:

uml_switch -unix /tmp/10.0.0 < /dev/null > /dev/null &
uml_switch -unix /tmp/10.0.1< /dev/null > /dev/null &
uml_switch -unix /tmp/10.0.2< /dev/null > /dev/null &

Note that these switche emulators need to be started before runnning the UML-based virtual machines.
Type the following two commands to create two Copy-On-Write root file systems using a shared root file system, root_fs:

uml_mkcow root_fs_cow_lamb root_fs
uml_mkcow root_fs_cow_frodo root_fs

ls -ls shows the actual size of the cow file systems. By usign copy-on-write and sharing hugh root file system, we can save a lot of disk space and actually improve the performance of those virtual machine through caching pages on host memory. We will use root_fs_cow_lamb as root file system for the lamb virtual machine; similar root_fs_frodo for that of frodo virtual machine.
Chow: 9/27/2004. Note that I just updated the fc1uml to include switch.sh that include those three uml_switch commands and created root_fs_cow_lamb and root_fs_cow_frodo copy-on-write file system. Therefore just "cd /home/frank" and type "./switch.sh" will start those three uml_switch emulators and you do not have recreate those two cow root file systesm.
I also changed the ifcfg-eth0 configuration file and save the root_fs so the starting time of fc1uml and those of uml virtual machines should be much faster.
I also created lamb.sh, b2b.sh, bilbo.sh, and frodo.sh to facilitate the startup of those virtual machines.
Start the following four virtual machines concurrently. Do not wait for the completion of the booting process for a machine before starting another.
- In the second shell window we run lamb virtual machine with the following command:
  /home/frank/linuxSrcE/linux ubd0=root_fs_cow_lamb umid=lamb eth0=tuntap,,,172.31.0.69 eth1=daemon,,unix,/tmp/10.0.0 mem=32M ubd2=swap
- In the third shell window we run b2b virtual machine with the following command:
  /home/frank/linuxSrcE/linux ubd0=root_fs2 umid=b2b eth0=tuntap,,,172.31.0.72 eth1=daemon,,unix,/tmp/10.0.0 eth2=daemon,,unix,/tmp/10.0.1 eth3=daemon,,unix,/tmp/10.0.2 mem=32M ubd2=swap
- In the fourthshell window we run bilbo virtual machine with the following command:
  /home/frank/linuxSrcE/linux ubd0=root_fs3 umid=bilbo eth0=tuntap,,,172.31.0.59 eth2=daemon,,unix,/tmp/10.0.1 mem=32M ubd2=swap
- In the fifth shell window we run frodo virtual machine with the following command:
  /home/frank/linuxSrcE/linux ubd0=root_fs_cow_frodo umid=frodo eth0=tuntap,,,172.31.0.74 eth1=daemon,,unix,/tmp/10.0.2 mem=32M ubd2=swap
The tuntap network interface emulator allows UML virtual machine to talk to the host or connect to Internet through the host. All eth0 here use tuntap.
For the other network interfaces, we use uml_switch with unix domain socket for virtual network and faster performance. Note that the transport type is specified as "daemon". The connections on these interfaces do not involve with hosts only allows connection among virtual machines.
You should see the typical slackware Linux booting sequence mixing with some info about tuntap and emulated uml switch. At the end of the booting sequence, you will a login prompt on the shell window and a virtual console (X windows) appears with the machine name in the title bar.
For each of the four virutal consoles, type root as login and it should allow you in without asking password.
Figure 1 shows the network interface and their IP address assignment. eth3 of b2b and eth1 of frodo need to be setup using ifconfig command. Other network interfaces are specified in /etc/rc.d/inet.conf file and will be set up during the boot time. Note that frodo and lamb share the same file system initially and therefore frodo will show the same eth0 and eth1 configuration as those of the lamb.
To change the hostname permently,
edit /etc/HOSTNAME
replace lamb.edu with frodo.edu
To change the IP address assignment on eth0 and eth1,

edit /etc/rc.d/rc.inet1.conf

replace IPADDR[0]="172.31.0.174" (instead of 172.31.0.169)
replace IPADDR[1]="10.0.2.174" (instead of 10.0.0.169)
Type "reboot" to reboot frodo. After reboot, you should see the shell prompt change the host name to frodo.
Type "ifconfig" you should see the IP addresses change to 172.31.0.174 and 10.0.2.174.

Exercise 2. Using route command to configure routing tables for allowing packets from lamb to be routed by b2b to bilbo.

For each of the virtual machine, type "netstat -rn" to see their routing table.
On lamb, check if we have a connection with b2b by "ping -c 5 10.0.0.172". Type "traceroute 10.0.0.172" and observe the result.
Question A.
A1. Are there a connection between lamb and b2b?
A2. Are there intermediate routers between lamb and b2b? Present your answer based on the execution results of the above two commands.
A3. What is the average round trip time measured by ping? The time reported in each line of ping results is measured by substracting the arrival time of ICMP echo reply packet with the departure time of the corresponding ICM echo request packet.
On lamb, try to ping bilbo with "ping -c 5 10.0.1.159".
Question B.
B1. Describe what you observe when lamb first tries to ping 10.0.1.159. What exact message appears?
B2. Does it takes long for the message to show up, i.e., does lamb need to send packets out before printing out the mesage?
B3. Try "ping 10.0.1.172". Do you get the same results as "10.0.1.159"?
Further study on the routing table of lamb indicates that there is no routing table with 10.0.1.0/24 entry. As our first try, let us add a routing entry with the folllowing route command:
route add -net 10.0.1.0/24 eth1
Now ping bilbo again with "ping -c 5 10.0.1.159".
Question C.
C1. Describe what you observe when lamb tries to ping 10.0.1.159 after a routing entry wtih 10.0.1/24 was entered. What exact message appears?
C2. Does it takes long for the message to show up, i.e., does lamb actually sends packets out?
C3. Explain why it happens this way. Hint: What protocol messages were sent but getting no results?
C4. Try "ping 10.0.1.172". Do you get the same results as "10.0.1.159"?
After consulting a network expert, it was suggested that we specify the gateway IP address to be used for routing packets to 10.0.1.0/24 subnet. Here is the new route command:
route add -net 10.0.1.0/24 gw 10.0.0.172 eth1
Now ping bilbo again with "ping -c 5 10.0.1.159".
Question D.
D1. Describe what you observe when lamb tries to ping 10.0.1.159 after a routing entry wtih 10.0.1/24 and gw 10.0.0.172 was entered. What exact message appears?
D2. Does it takes long for the message to show up, i.e., does actually sends packets out?
D3. Based on the ping result, does b2b receives the packets destined for 10.0.1.159?
After checkig with the network expert, it was diagnosed that the b2b router does not turn on ip_forward flag to allow packets to be copied/forwarded among its network interfaces. To do that on a linux router such as b2b, execute the following command on b2b:
echo 1 > /proc/sys/net/ipv4/ip_forward
Now from lamb ping bilbo again with "ping -c 5 10.0.1.159".
Question E.
Describe what you observe when lamb tries to ping 10.0.1.159 after we turn on the ip_forward flag on b2b. What exact message appears?
After checkig with the network expert, we were told that we need to check the routing table of bilbo also and make sure there is a routing table entry for 10.0.0.0/24 subnet. Indeed there is no such routing entry. Without that entry, bilbo will not know where to return the ICMP reply message. Let us add such entry with following command on bilbo:
route add -net 10.0.0.0/24 gw 10.0.1.172
Now from lamb ping bilbo again with "ping -c 5 10.0.1.159".
Question F.
Describe what you observe when lamb tries to ping 10.0.1.159 after we add the 10.0.0.0/24 routing entry on bilbo.
Let us now remove the 10.0.0.0/24 entry on bilbo with the following command:
route del -net 10.0.0.0/24 gw 10.0.1.172
Verify that the entry was removed.
Now try to enter the following command on bilbo:
route add -net 10.0.0.0/24 gw 10.0.0.172
Question G.
G1. Describe what you observe when the above comand is entered on bilbo.
G2. Why this route command is incorrect?
Try to put the correct routing entry for 10.0.0.0/24 back on bilbo.
Next we will try to set up 10.0.2.0/24 subnet.
On b2b, execute
ifconfig eth3 10.0.2.172 netmask 255.255.255.0
Now you can ping b2b from frodo with "ping 10.0.2.172".
Question H.
To allow frodo to talk to lamb and bilbo, four routing entries need to be added to three machines.
Describe what are those four entries (and on which machines).
Verify the routing table setup by issuing ping from frodo to lamb and bilbo.
Try to arrange the four virtual consoles on four corner of the fc1uml window and capture the window on the host machine by
- typing Alt-Print Screen (prt sc).
- make sure the fc1uml is the active window.
- Type right-alt to get out of fc1uml window!!!
- Save the window image by opening the MS Photo Editor or other image editing tool and hit control-v to past the image.
- Save the image file as PNG Format to reduce the file size.
- Include the image as part fo your answer.
Note that if frodo, lamb, and bilbo are all client machines and use b2b as gateway, instead of using two "route add -net" commands, we can use a single "route add default gw 10.0.2.172" on frodo, simlar command for lamb and bilbo. Try to delete the routing entries for those 10.0.x.0/24 subnets and replace them with the default gatweay entry, and see if the pings to each other still work.
To facilitate the diagnosis of the above problem, you can install the tcpdump package on those virtual machines. Follow the instructions on http://cs.uccs.edu/~cs522/hw/hwF2004/fc1uml/slackware/installpkg.htm.
Chow: 9/27/2004. Note that I have installed tcpdump and iptables on all virtual machines Sunday and I just checed they were distributed to all EAS 138 pc overnight.

Part 2.
Exercise 1. Reachability Analysis

Given the following network of two CFSMs.

Questions:

Perform the reachability analysis on the Network (M, N).
What sizes of buffers are needed for the two FIFO channels?
Are there non-executable states or transitions?
Try to fix the protocol so that there are no deadlock, no unspecified reception states, and no non-executable states or transitions. Brief explain your design.

Note you can use a tool called setool to verify your reachability analysis result. The web page for using setool is at http://cs.uccs.edu/~cs522/hw/hwF2004/setool.htm

Exercise 2. Understand the protocol behavior of Alternating Bit Protocol.

Given the alternating bit protocol,

Describe the event sequence, starting from initial states, of the alternating bit protocol, if both channels lose the even messages, i.e., they lose the 2nd, 4th, 6th,... messages appears on channels. Each event can be identified as starting global state--machine:transition->ending global state. For example, (1,1,E,E)--S:NewData-->(2,1,E,E) is the first event.

Include events up to the one that successfully delivers A1 to the Sender.

Create your solution as hw3.html

Email me the url of the hw3.html to chow@cs.uccs.edu

CS522 F2004 Homework#3: Understanding Routing using UML-based Virtual Network and Protocol Design/Verification

CS522 F2004 Homework#3:
Understanding Routing using UML-based Virtual Network and
Protocol Design/Verification