辅导program课程、C++程序辅导
- 首页 >> Java编程 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 [-f ] [-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
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
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