代写program代做、C++程序代写

日期：2021-10-02 10:56

Fall 2021

Programming Assignment 2

Weight: 1.2x

1 Introduction

In this assignment you will implement distance vector routing. You will implement a virtual network

on top of UDP. In this virtual network, Unix processes will be network nodes, and links will be

created using UDP.

The format to define our network is specified using a scenario file. An example scenario file

and associated network is shown in Figure 1. Since nodes in our virtual network are just Unix

processes, multiple nodes may reside on the same (physical) host. This is shown in Figure 1 —

virtual node 0 and 1 both reside on physical node fireball.

fireball frostbolt

icelance

(After Event Set #1)

(Scenario Configuration File)

Figure 1: Sample scenario configuration file and the two relevant states of the network after the

respective event set is executed. Shaded rectangles correspond to physical nodes and the solid

circles correspond to specific virtual nodes. All lines represent virtual links between nodes, which

are labeled by their link name and cost.

1

1.1 What is in a scenario file?

The scenario file defines the set of nodes and a set of event sets. An event set consists a set of

events that affect the links in the network1

. There are three types of events: establishment of a

link, tear-down of a link and updating the of cost of a link. All events in an event set are executed

sequentially without any delay. How event sets are ordered is configurable — for this assignment,

your task is to run the distance vector algorithm for a fixed amount of time before executing events

in the next event set. Thus, your code can be structured as follows:

boolean nextSET ← true ; Global variable

alarmHandler() { ; Called every timeout number of seconds

nextSET ← true;

}

. . .

do

if (nextSET is true)

es ← h next event set i

h dispatch all events in es i ; This will cause changes to the links in the network

nextSET ← false;

h execute Distance Vector protocol i

while h there are more event sets to process i

Obviously, you don’t have to follow this blueprint, this is just one possible way. You may also

wish to use an event queue to keep track of the next event to process (i.e., ‘run DV algorithm’ or

‘dispatch event set’) along with the time it should be processed, using the remaining time until the

event needs to be processed to set an appropriate timeout to poll or select.

2 Implementation

2.1 Scenario Configuration File

The format of the scenario file is as follows:

? The scenario file begins by listing all the virtual nodes in the network and may contain up to

256 virtual nodes. Virtual nodes are declared as follows:

node h node-id i hostname

The node id is an unsigned integer and corresponds to the virtual node identifier (must be

unique) and the hostname is the host on which the process corresponding to this virtual node

resides.

? After the virtual nodes are defined, the scenario file consists of a set of event sets. Event sets

themselves consist of events and are delimited by “(“ and “)”. Thus, the rest of the scenario

file looks like this:

( h set of events i ) . . . ( h set of events i )

1Unless otherwise noted, we mean the virtual network when we say network

2

? There are three types of events in an event set. An event set may contain an arbitrary number

of events of any given type in any given order. (Of course, the events must be consistent,

i.e. an event cannot refer to a node or a link that does not exist.) Specifics of events are as

follows:

– The establish event establishes a new link in the network. The syntax is as follows:

establish node h node-id i port h integer i node h node-id i port h integer i

cost h integer i name h string i

This command will establish a link between the two nodes (and associated port numbers)

whose node ids are specified. These nodes must already exist and the port numbers must

not have been used before to define a link. The link has a cost given as an unsigned

integer and a “name” specified as a string. All subsequent actions on this link will just

use this string to identify the link. Hence, link names must be globally unique.

– The following event is used to tear down an existing link: following following

tear-down h string i

Once again, the named link must already exist.

– Lastly, the cost of a link can be changed:

update h string i cost h integer i

The string should identify an existing link and the cost should be positive.

? A scenario file can also contain comments guarded by “;”.

2.2 Route Dissemination Packets

Routes are disseminated using an advertisement packet with the following structure:

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| type | version | Num. Updates |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| dest_0 | min_cost_0 |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| dest_1 | min_cost_1 |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| .............. |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

| dest_n | min_cost_n |

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: Set to 0x7 for this assignment.

Version: Set to 0x1.

Num. Updates: Number of distance vector pairs in this advertisement. This must be more than zero

for all legal advertisements.

Dest: Assume the advertisement is from node a to node b and the Dest field is c. Node c is the final

destination to which node a is advertising the min. cost to node b through node a.

Cost: Using the terminology from above, the cost field correspond to the actual cost of the route to

destination c as advertised by node a (to node b).

3

2.3 Source Code

A substantial part of the source code will be given to you so you can concentrate on developing the distance

vector part. This code can be found in the ‘assignment2’ directory of the ‘materials’ repository, which you

either cloned for earlier projects or can be cloned by the following command:

git clone fall417git@poole.cs.umd.edu:materials

You are required to use either the select or poll system calls to multiplex reading from multiple

descriptors. Since your virtual process will have multiple links incident upon it, it can receive a message

from any link. If the node just does a read or recvfrom from any link, the process will be blocked till

something actually arrives on that link. The UNIX (system) calls select and poll allow you to wait on

multiple descriptors, and you should use this facility to implement your virtual node.

2.3.1 Parser

You will be given a flex and bison2 parser which will parse the configuration file and automatically create a

global node-to-hostname mapping and a two-dimensional local event structure that maps to the set of event

sets. The interface is in the form of the ruparse() function. You must call the parser init function before

calling ruparse as shown below.

char *sc_file;

extern int ruparse();

int main (int argc, char *argv[]) {

parse_arg(argc, argv);

parser_init(sc_file); // sc_file contains the name of the scenario file

ruparse();

........

}

The ruparse function creates a two-dimensional event list. Each column in the 2-D event list corresponds

to a event set in the scenario file. Note that once you call the parser using ruparse, you never have to

bother with the scenario file again and you never have to call ruparse again. All the information in the

scenario file has been read into the event list.

Each element of the event set is an struct es (struct event set). The definition of the event set is as

follows:

struct es{

struct es *next; // to create the 2-d list

struct es *prev;

e_type ev; // ev is one of establish, tear_down or update

int peer0, port0, peer1, port1;

int cost;

char *name;

};

Eventually, you will have to dispatch these events. We discuss dispatching events in Section 2.3.4. The

parser resides in *ru* files, and the event set is defined in the es.[c|h] files.

2

If you don’t know anything about parsing, don’t worry, you will not be required to do anything with flex or

bison for this assignment.

4

2.3.2 Nodes and Links

As the parser runs, it also creates a set of nodes to hostname mappings. This mapping can be accessed by

using the (char*) gethostbynode(int node) function defined in n2h* files. The node id must be defined

in order for gethostbynode to return anything meaningful.

In each dispatch of an event set (column), the local link set should be updated when necessary. Your

routing algorithm then use it to collect distance vector information, update its routing table. The local link

set has the following structure:

struct link {

struct link *next; // next entry

struct link *prev; // prev entry

node peer0, peer1; // link peers

int port0, port1;

int sockfd0; // if peer0 is itself, local port is bound

int sockfd1; // if peer1 is itself, local port is bound

cost c; // cost

char *name; // name of the link

};

The methods to access the link set are:

int create_ls(); // initialization

int add_link(node peer0, int port0, node peer1, int port1,

cost c, char *name);

int del_link(char *n);

struct link *ud_link(char *n, int cost);

struct link *find_link(char *n);

void print_link(struct link* i); // print info about a single link

void print_ls(); // prints entire link set

You must call create ls to initialize the link set at a node. The add link, del link, ud link functions

mutate the link set. The print link and print ls print information about a given link or the entire set at

the node.

Note well: When a link is added into the local link set, socket(s) corresponding to the link are not

automatically allocated. You must write the code to associate the sockets yourself. Note that you can obtain

a link structure using the find link function.

Link sets are defined in ls.*.

2.3.3 Routing Table

We provide a set of routines to manipulate routing tables. The methods to maintain routing tables are:

int create_rt();

int add_rte(node n, cost c, node nh);

int update_rte(node n, cost c, node nh);

int del_rte(node n);

struct rte *find_rte(node n);

5

void print_rte(struct rte* i);

void print_rt();

The function create rt must be called to create a routing table at a node. The functions add rte,

update rte, and del rte are used to add, update, and delete individual routing table entries. The logging

functions print rte and print rt print individual table entries and the entire table, respectively.

The function find rte is used to find an entry for a specific destination .

2.3.4 Dispatching events

After the event list is created, you have to dispatch functions for each event in the event sets. As we said

before, all the functions in a single event set will be executed sequentially. (Note that the event set at a

node will only contain events that pertain to this node — events at remote nodes that are in the scenario

file are not added to the event set at the local node). The event set code defines the walk el function that

traverses the event list and the dispatch event function that modifies the link set as appropriate.

3 Command-line options and logging

You executable should take in the following three command-line options:

rt -n <node_id> [-f <scenario_file>] [-u update-time] [-t time-between-event-sets] [-v]

The -n option is mandatory and specifies the node id; the optional -f parameter specifies a scenario

file (default config), and the optional -t parameter specifies how long to wait between executing event

sets (default 30 seconds). The -u option specifies how long to wait (in seconds) before sending out distance

vector updates; this should default to 3 seconds.

If the -v (verbose) option is not present, your code should print the following to stdout: 1) each event

in the event set that it acts upon using print event, 2) the routing table entry after it was changed in

response to processing a routing update using print rte, and 3) the full routing table after dispatching the

entire event set using print rt.

If the -v option is present, then the full routing table should additionally be printed after processing

every routing update (whether or not it changed any entries) using print rt.

4 Additional Requirements

1. Your code must be submitted as a series of commits that are pushed to the origin/master branch of

your Git repository. We consider your latest commit prior to the due date/time to represent your

submission.

2. The directory for your project must be called ‘assignment2’ and be located at the root of your Git

repository.

3. You must provide a Makefile that is included along with the code that you commit. We will run

‘make’ inside the ‘assignment2’ directory, which must produce a ‘rt’ also located in the ‘assignment2’

directory.

4. You must submit code that compiles in the provided VM, otherwise your assignment will not be

graded.

5. Your code must be -Wall clean on gcc/g++ in the provided VM, otherwise your assignment will not

be graded. Do not ask the TA for help on (or post to the forum) code that is not -Wall clean, unless

getting rid of the warning is the actual problem.

6. You are not allowed to work in teams or to copy code from any source.

6