辅导program、辅导C/C++程序课程

日期：2021-11-30 11:49

Computer Networking, Fall 2021

Assignment 3: Routing Simulation

2021.11.20

1 Introduction

In this assignment, you will implement the distance vector routing protocol. You are

asked to writing two programs: router and agent. A router program represents a router

process. You may need to invoke multiple router programs. On the other hand, the

agent program is a centralized control agent that triggers the route updates of the

routers.

2 Protocol Description

2.1 Configuration files

We need to prepare two configuration files in advance before we start the router and

agent programs. They are the router location file and the topology configuration file.

2.1.1 Router location file

The router location file maps a unique router ID to a router process. Each router is

defined by a 3-tuple:

<router IP,router port,router id>

Each router is assigned a unique identifier router id. It runs on IP router IP,

and listens on port router port for two pieces of information: (i) commands from the

agent and (ii) messages from other routers. For example, the router location file can

be represented as follows:

6

137.189.88.101,13001,1

1

137.189.88.101,13002,2

137.189.88.101,13003,3

137.189.88.102,13001,4

137.189.88.102,13002,5

137.189.88.102,13003,100

Both the routers and the agent need to parse the router location file. The first

line denotes the number of routers in the network, while the following lines define the

configuration of each router. Note that the router IDs may not be consecutive. For

instance, it is possible to have a network composed of routers with IDs 1, 2, and 4

without the ID 3. For simplicity, we make the following assumptions:

? The router location file is error-free, in the sense that (i) there is no formatting

error, (ii) the router ID in each row is unique, (iii) there is no conflict of router

port numbers, and (iv) the IP addresses and port numbers are actually used by

the corresponding router (the details of how we invoke a router are discussed

later).

? Router IDs are all integers.

? The network has at most 10 routers.

2.1.2 Topology configuration file

The topology configuration file specifies the router topology. Here, the distance between

two neighboring routers is unidirectional, i.e., the distance from router 1 to router 2 may

be different from the distance from router 2 to router 1. The topology configuration

file is a text file composed of a number of topology tuples. The format of a topology

tuple is shown below:

<RouterID1,RouterID2,weight>

Each term is an integer. The following example topology configuration file is for a

network of four routers with the following link weights.

12

1,2,15

1,3,9

1,4,-1

2,1,15

2,3,4

2

2,4,8

3,1,9

3,2,4

3,4,7

4,1,-1

4,2,8

4,3,12

The first line of the file specifies the number of links we are going to define. If the

weight is equal to -1, it means that the link does not exist (e.g., the links (1,4) and (4,1)

are gone). Alternatively, if we do not specify the weight for a link, then it means that

the link does not exist. Note that only the router programs need to read the topology

configuration file. Furthermore, we make the following assumptions:

? The topology configuration file is error-free.

? If router A can reach router B, then router B must be able to connect to router

A, although the links (A,B) and (B,A) may have different link weights (see links

(3,4) and (4,3) in the above examples). In other words, if router A cannot reach

router B, then router B cannot reach router A.

? All link weights are positive (except if the links are disconnected). Also, the

maximum link weight is 1000. Thus, if you find that the link weight is greater

than 1000, you may assume that the link is disconnected.

? Router A and router B are neighbors of each other if link(A,B) and link(B,A) are

well-defined and are positive.

2.2 The router program

Each router program will first read and parse the configuration files. After parsing the

configuration files, the router program will listen on the router port. It can also use the

specified IP addresses or port numbers in the configuration files to set up connections

to the neighboring routers.

Each router can receive commands from the agent. The agent can send commands,

which can be classified as one of the following types: (i) link-weight updates, (ii) route

updates, (iii) information maintained by a router. We will define the formats of the

commands in later discussion.

In this assignment, the routers will not execute periodic updates. Also, they will

not send distance vectors until being triggered by the agent. After being triggered by

the agent, they will continue to transmit distance vectors to neighboring routers until

3

the least-cost paths are determined (note that a router does not send DVs to another

router if they are not neighbors). If there is more than one path with the same cost,

we pick the one that has the smaller router ID.

Note that you do not need to implement poisoned reverse. You would expect that

the count-to-infinity problem could easily happen.

Note that routers must be ready to receive distance vectors from their neighbors.

Each router must also count the number of distance vector packets it has received.

You may invoke each of the router programs as follows:

# .router <router location file> <topology conf file> <router id>

The router ID is the ID associated with the router process, and it correctly reflects

the IP address and the port numbers.

2.3 The agent program

The agent program will send commands to routers. Table 1 defines the commands using

examples. For the routing table of a router, it should show (i) the next hop and (ii) the

path cost for each of the destinations (including itself) specified in router location file.

If there is no path to a router, you don’t need to display it. For example, the routing

table of router 1 may look something like:

Dest: 1, next: 1, cost: 0

Dest: 2, next: 2, cost: 15

Dest: 3, next: 2, cost: 20

Dest: 4, next: 3, cost: 13

It is recommended that you format your routing table following this example. Note

that there is only one space character after each colon and comma.

4

Table 1: Commands available for the agent.

Name Example of commands Description

dv dv All routers are triggered to propagate distance

vectors to neighboring routers until

the link costs become stable.

update update:1,6,4 Change the link weight of link (1,6) to 4. If

the link weight is -1, then it means that the

link is deleted. If the link is absent before,

then it means that the link is added with

the update command.

show show:2 Display the routing table of router 2.

reset reset:2 Reset the number of distance vectors of

router 2 to zero. This helps us easily debug

your assignment.

Note that the commands might be sent to all routers, a single router, or a subset of

routers. You may design the protocol of how to respond to each of the commands.

The commands are read from the console inputs. If the agent program receives

anything that is not one of the above commands, it should display an error message.

You may invoke the agent program as follows:

.agent <router location file>

2.4 Protocol Messages

There are two main types of protocol messages: (i) messages shared between the agent

and a router, and (ii) messages shared between the routers.

? Messages between the agent and a router. The agent will send a command

request to an individual router. For the commands dv, update, and reset, the

router do not need to reply anything; for the command show, the router replies a

command response that contains the necessary information.

? Messages between two routers. The routers will exchange distance vectors.

The distance vector of a router is the list of the estimated costs of the paths from

the router to all other nodes in the network. Also, the maximum link weight is

1000. Thus, if you find that the link weight is greater than 1000, you may assume

that the link is disconnected.

5

You only need to write a single-threaded router program to handle the above

messages. Each router program listens on the router port for the messages. When it

receives a mes- sage, the router program makes the responses accordingly and waits for

another message. In particular, if a router receives a dv command from the agent, it

sends the distance vectors to its neighbors. If the router receives a distance vector from

one of its neighbors, it updates its routing table and checks whether there is any cost

change; if yes, then it sends distance vectors to its neighbors.

You may come up with your own format of the protocol messages for the command

requests/responses as well as the distance vectors.

Make sure that the sender calls htonl() to convert the length into the network-byte

order before you send out the message, and the receiver calls ntohl() to convert back

the length into the host-byte order.

3 Grading (100%)

We will use a certain number of test cases to verify your programs. One week before

the deadline, we will publish all test cases and the score for each case.

For each test case, your score will be based on the correctness of the following

functions:

? The dv command can trigger the distance vector routing protocol. (15%)

? The show command correctly shows the routing table and the number of distance

vectors. (10%)

? The distance vector routing protocol runs correctly for a static topology. (15%)

? The distance vector routing protocol runs correctly when the topology changes

(60%)

4 Submission Guidelines

You must at least submit the following files, though you may submit additional files

that are needed:

? common.h: the header file that includes all definitions shared by the router and

the agent (e.g., message format)

? agent.c: the agent program

? router.c: the router program

6

? M akef ile: a makefile to compile both agent and router programs

Your programs must be implemented in C/C++. They must be compilable on

Unix/Linux machines.

The assignment is due on December 19 (Sunday), 23:59:59.

5 Remarks

? Our test cases ensure that each update:a,b,w command is followed by a update:b,a,w

command. In other words, every update is mirror symmetric.

? Refer to section 2.3 to format the output of your show command. The routing

table should be arranged in ascending order by router ids.

7