UM EECS 489 Winter 2007 (Background for PA2)

1 The Virtual Network

Our virtual network consists of two parts: a virtual host (vrouter henceforth) and a topology seeder. To construct your own private virtual network, you run one copy of seeder and one or more copies of vrouter. The seeder must be run before the vrouter's. Aside from seeding the topology of the virtual network, the seeder also sends some test messages on the virtual network. You might want to start with testing one instance of the vrouter. To do so, log yourself into two Solaris machines, say a.engin and b.ummu. On the respective machines you type:

         a.engin% seeder -n 1
          b.ummu% vrouter -S a.engin

Once you have tried the single instance of your vrouter, you can experiment with multiple instances of it. For example, to create a 4-node virtual network consisting of b.ummu, c.eecs, d.engin, and e.ummu, with the seeder running on a.engin, you do:

         a.engin% seeder -n 4
          b.ummu% vrouter -S a.engin
          c.eecs% vrouter -S a.engin
         d.engin% vrouter -S a.engin
          e.ummu% vrouter -S a.engin

The seeder will consider the first vrouter connected as vrouter 0, the second as vrouter 1, and so on. For this assignment, the seeder will only generate a simple linked-list topology.

2 Addressing on the Virtual Network

Each of your vrouters is addressed by the IPv4 address of the machine they run on and a well-known port number. The default well-known port number is VROUTER_PORT defined in vnet.h. In case you need to share a machine with someone else running vrouter, you can choose a different port number with the -p option of vrouter. All of your vrouter's must use the same well-known port. For example, to use port number 7896 in the above 4-node scenario, do:

         a.engin% seeder -n 4
          b.ummu% vrouter -S a.engin -p 7896
          c.eecs% vrouter -S a.engin -p 7896
         d.engin% vrouter -S a.engin -p 7896
          e.ummu% vrouter -S a.engin -p 7896

In case your seeder conflicts with another seeder on the same machine, the well-known port number of the seeder can also be changed. To use port number 8707 with your seeder, you do:

         a.engin% seeder -n 4 -p 8707
          b.ummu% vrouter -S a.engin -P 8707 -p 7896
          c.eecs% vrouter -S a.engin -P 8707 -p 7896
         d.engin% vrouter -S a.engin -P 8707 -p 7896
          e.ummu% vrouter -S a.engin -P 8707 -p 7896

To address each other, vrouter's use the virtual internetwork address (vin_addr_t henceforth) depicted in Fig. 1, where the IPv4 Address is the IPv4 address of the machine the vrouter runs on, the Port Number is the well-known port number the vrouter listens on, and the Metric the cost of the link (to be interpreted by higher level protocols). The port number and metric in a vin_addr_t must be kept in network byte-order at all times.

**Figure 1:** `vin_addr_t`

3 Virtual Links

Upon start up, each vrouter registers itself with the given seeder. The seeder then determines the connectivity of the virtual network, i.e. which vrouter connects to which other. With prompting from the seeder, each vrouter opens a virtual link (vif) to its designated neighbors. Each vif is assumed to be a bidirectional (full-duplex) link. The virtual link layer is provided to you. In the file vif.c you will find the definition of the following APIs for the vif layer:

int vif_pullup(vif_t *vif, char *buf, int len);
int vif_pullupn(vif_t *vif, char *buf, int len);
int vif_output(vif_t *vif, u_short prot, vmbuf_t *vbp);

When a packet arrives for your vrouter, the vif on which the packet arrives parses the vif header of the packet and calls the appropriate upper layer protocols' APIs. The upper layer protocol calls vif_pullup to pull up its data from the virtual link just like you use recv(3N). Or it can call vif_pullupn to pull up n bytes. The function vif_pullupn tries to pull up n bytes of data in one call. However, it doesn't guarantee that it will always succeed pulling up that many bytes. One should always check the return value of calls to both function to make sure they are not returning error. If vif_pullupn returns error, it usually means there's something wrong in your code, so just dump core and abort.

You call vif_output to put data on the virtual wire. You still need to call htons(), ntohs(), and friends whenever you transmit/receive an integer. See the function definitions in vif.c. (In case you wonder at the choice of the API names and programming style, I try to make them as similar as possible to what one sees in the BSD kernel, so you get an experience of writing kernel code without most of the hassle usually associated with it.) Read the comments in vif.c to find out more fully how to use these vif related functions.

4 Virtual Buffer Chain

One obvious way to encapsulate a higher layer message into a lower layer message is for each layer to allocate enough space for the lower layer header and the upper layer message, and copy the upper layer packet into it. Unfortunately, message copying is very expensive. Actually, memory copy has been identified as one of the most expensive operations in networking code. We would like to reduce copying to a minimum. For that purpose, I have defined a virtual buffer chain (vmbuf_t). Each vmbuf_t element points to a chunk of bytes and records the size of the chunk (in bytes). As a message traverses down the protocol layer stack, each layer creates a new vmbuf_t element for its header and prepends the new element to the virtual buffer chain before passing the chain down to the next lower layer. Fig. 2 depicts the vmbuf chain of a message going down the VTP, VIP, and VIF layers. The virtual link layer at the bottom transmits each vmbuf_t element without making extra copies.

**Figure 2:** `vmbuf` Chain Traversing the Protocol Stack.

5 Virtual Router

Our virtual router (vrouter) speaks 4 protocols:

VIP:: Virtual Internetwork Protocol, a connectionless internetwork protocol.
VCMP:: Virtual Control Message Protocol, an error reporting control message protocol.
VRP:: Virtual Routing Protocol, a distance-vector protocol that implements split-horizon with poisonous reverse, path hold-down, and route poisoning.
VTP:: Virtual Transport Protocol, currently does nothing but prints out the data it receives on the screen.

5.1 VIP: Virtual Internetwork Protocol

**Figure 3:** VIP Packet Header Format.

VIP is a connectionless internetwork protocol. Fig. 3 depicts the packet header format of VIP. The Version field contains the version number, currently set to VIP_VERSION defined in vip.h . Packets with version number different from VIP_VERSION should be discarded. The Hop Limit field contains the number of hops a packet has traversed. At every host, except the packet's destination host, this field should be decremented by one and the packet should be discarded if this field is <= 0. The Pkt Length field contains the size of the packet in bytes, excluding the header. The Protocol field specifies whether this is a vcmp, vrp, or vtp packet. The protocol numbers of VCMP, VRP, and VTP are VIP_PROTOVCMP, VIP_PROTOVRP and VIP_PROTOVTP respectively, as defined in vip.h. There is also a protocol number VIF_PROTOVIP for VIP defined in vif.h. VIP identifies a host by its vin_addr_t as described in Section 2.

5.2 VCMP: Virtual Control Message Protocol

When a non-VCMP packet encounters one of the following errors, the vrouter holding the packet should report the error back to the packet's sender.

VCMP_EHOPS: Hop count exceeded.
VCMP_EHOST: Host unreachable: no route to host.
VCMP_ELINK: Link down: route found but error in transmission.
VCMP_EPROT: Unknown protocol.

The above error codes and messages are defined in vcmp.h and vcmp.c. The format of a VCMP packet is depicted in Fig. 4.

**Figure 4:** VCMP Packet Header Format.

The version should be VCMP_VERSION and the error code one of the above listed. The VIP header of the packet encountering error is returned along with the error code. In generating a VCMP packet, you may find the macro VRP_INFINITY defined in vrp.h useful. No error should be generated when VCMP packets themselves encounter errors.

5.3 VRP: Virtual Routing Protocol

VRP will be the subject of the next programming assignment. For this programming assignment, you may find the following functions useful:

vrp_self(vrt_t *vrt): returns a pointer to the vin_addr_t of this vrouter as stored in the route table vrt.
vrp_isself(vrt_t *vrt, vin_addr_t *vad): returns one if the address in vad is the address of this vrouter as stored in the route table vrt, else returns 0.
vrp_route(vrt_t *vrt, vin_addr_t *vad, u_short *cost): returns a pointer to the vif_t that goes towards the destination vad. If a route is not found, returns NULL. If a route is found, cost points to the hop count towards the destination.
vrp_rand_dest(vrt_t *vrt): returns a random index into the routing table with valid entry. Used mainly to randomly pick a destination to send test packets to. See usage in vtp_test for an example.

Read the comments in vrp.c to find out more fully how to use these functions.

5.4 VROUTER: A Virtual Router

**Figure 5:** Design of the virtual router `vrouter`.

The design of the virtual host (vrouter) is depicted in Fig. 5. In the figure, data structures are enclosed in rounded boxes and functions in square boxes. Files with comments suggesting what the functions could contain are available in the assignment directory. (This figure shows vif_input() calling vip_input(). In the code, vif_input() actually returns the VIF and the main() routine in vrouter.c calls vip_input().)