辅导网络路由器、讲解Network

• For all the above algorithms, whenever ties occur, they should be broken arbitrarily. In

other words, if a particular routing algorithm determines that there are two or more paths

between the source and destination with exactly similar costs then the algorithm should

choose one of these paths randomly.

• Your program MUST NOT look for alternate paths between the source and destination of

a virtual circuit request in case the path selected by the routing protocol results in a blocked

request. Simply count this as a blocked request (packet) and move on to the next one.

• Your program will need to keep track of time. You may assume that time starts at 0. Recall

that the workload file specifiesthe time at which each virtual connection request originates

in the network and the duration of each virtual circuit (provided it is established). Clearly,

in the case of virtual packet network, you must extract the starting time and duration for

each packet and then make a virtual circuit request per each packet. Note that when the

connection request is divided into the packets in the virtual packet network, your program

Page 6 of 11

must be careful about the order of the starting time of the packets of different connection

requests. As discussed earlier the routing decision for each circuit request can be processed

in zero time. Remember to free up the resources dedicated for a circuit once the duration

of the circuit elapses.

• Your program should maintain the following statistics:

o The total number of virtual connection requests.

o The total number of packets.

o The number (and percentage) of successfully routed packets.

o The number (and percentage) of blocked packets.

o The average number of hops (i.e. links) consumed per successfully routed circuit.

o The average source-to-destination cumulative propagation delay per successfully

routed circuit.

Note that in the case of virtual circuit network, your program make one circuit for all

packets of a requested connection, thus the program should cascade the results of the

virtual circuit over all packets in the corresponding connection. For example, in this

case, if a connection has been blocked, it means that all packets of the connection are

blocked.

• The following illustrates an example initiation of your program:

java RoutingPerformance CIRCUIT SHP topology.txt workload.txt (for JAVA)

RoutingPerformance CIRCUIT SHP topology.txt workload.txt (for C)

• Once your program has read through the entire workload file and finished processing all

virtual circuit requests, it should output all of the above statistics to the terminal and then

exit. A sample output from one run of the program is as follows:

Page 7 of 11

You output format MUST be exactly same as the above sample output. You need only to

change the above 7 performance metrics values according to your program results. Also,

the maximum number of decimal places for real performance values must be set to 2.

Moreover, you MUST write the above output format in the standard output.

We will wait for reasonable amount of time (3 - 4 minutes) for your output to appear (with

the provided workload.txt file). If you observe that your program is taking longer than 4

minutes to execute the workload file then please indicate this in your report so that we

know that your program is not in an infinite loop.

Additional Notes

• You may choose to work either individually or in a group of two. If you form a group,

please send an email with the names/student-id of your group members to the class account

(cs3331@cse.unsw.edu.au) by Sunday, 24th September 2017, 11:59 pm. You must

use the email title “Programming Assignment 2: Group”. Confirmations for

groups will be sent out by 12:00 PM (noon) of 25th of September 2017. WE CANNOT

ACCEPT EMAILS FOR GROUPS AFTER THIS DATE.

• We neither are able to help you choose a group member nor would be accepting more than

2 people in a group. We may make facilities available on OpeanLearning for this. Please

check assignment 2 page and class announcement for this.

total number of virtual circuit requests: 200

total number of packets: 4589

number of successfully routed packets: 2000

percentage of successfully routed packets: 43.58

number of blocked packets: 2589

percentage of blocked packets: 56.42

average number of hops per circuit: 5.42

average cumulative propagation delay per circuit: 120.54

Page 8 of 11

• Marking criteria will remain the same for groups. Unless advised otherwise, contribution

from each member will be considered equal. If there is any problem with group members

not cooperating, this must be reported to the LIC immediately as dealing with group

problems post submission will be hard to manage. Please keep a log of your

contributions/meetings.

• While you are encouraged to adopt good programming practices, your coding style is NOT

subject to marking.

• The programs will be tested on CSE Linux machines. So please make sure that your

program runs correctly on these machines. This is especially important if you plan to

develop and test the programs on your personal computers (which may possibly use a

different OS or version). We are unable to accommodate the request to have you

demonstrate it on your laptop/desktop machines. Please plan ahead for any porting issues.

• Tips on how to get started:

o Focus first on making sure that your program can read in and model the network

topology. The 4-node example discussed earlier is a good one to start with.

o Next focus on getting ONE routing algorithm working. The Shortest Hop Path (SHP)

is the easiest one, since it entails implementing Dijkstra’s algorithm using a link cost

of 1 for each hop traversed. Spend a lot of time testing your Dijkstra’s algorithm to

make sure that it is working properly. This will definitely pay off in the long run.

o The Shortest Delay Path (SDP) is a simple variant of SHP and will involve a simple

modification (i.e. changing the link cost) to your implementation of SHP. The Least

Loaded Path (LLP) will require reasonable modifications but is still relatively easy

to implement.

o Test your routing algorithm(s) with a SMALL network topology and a SMALL

virtual circuit workload file. Links with very low capacity (e.g. 1) are useful in initial

testing. Make sure that the routing is working, and that your program is able to

compute the required statistics.

o Extend your program for the virtual packet network case and repeat all tests for all

three routing algorithms.

o Once you are fairly confident that your program is working correctly for a small

topology, and then move on to the provided sample topology. It may be useful to

initially test out the workload file incrementally (e.g.: first 10 requests, first 50

requests, first 100 requests and so on).

Non-programming assignment is allowed as an exception to non-CSE and nonEE&T

students who do not have experience with programming

(e.g: Mechatronics).Note that non-CSE students are encouraged to attempt the

programming assignment. Check details about this on the alternate assignment

page on OpenLearning. You must send an email to class account indicating that

you are opting for non-programming assignment by 22nd of September 2017,

12:00 PM (noon). If no emails is received, you are assumed to have opted for

standard version of the assignment.

Page 9 of 11

• Language and Platform: You are free to use either C or C++ or JAVA or Python to

implement this assignment (you can choose only one of these languages for the entire

assignment, not a combination of them). Your assignment will be tested on the Linux

Platform. Make sure you develop your code under Linux (check the version on CSE

machines).

• Plagiarism: You are to write all of the code for this assignment yourself. All source codes

are subject to strict checks for plagiarism, via highly sophisticated plagiarism detection

software. These checks may include comparison with available code from Internet sites

and assignments from previous semesters. In addition, each submission will be checked

against all other submissions of the current semester. Please note that we take this matter

quite seriously. The LIC will decide on appropriate penalty for detected cases of

plagiarism. The most likely penalty would be to reduce the assignment mark to ZERO

and reported to school plagiarism register. We are aware that a lot of learning takes place

in student conversations, and don't wish to discourage those. However, it is important, for

both those helping others and those being helped, not to provide/accept any programming

language code in writing, as this is apt to be used exactly as is, and lead to plagiarism

penalties for both the supplier and the copier of the codes. Write something on a piece of

paper, by all means, but tear it up/take it away when the discussion is over.

• Submission: includes 3 main components:

1. Your program file

2. A 3-page report

3. A maximum of 5 min screencast of your program as specified in page 9 of this

document.

1: You really need only one file: RoutingPerformance.c (or RoutingPerformance.java).

If you are using C and if you are going to use any other files besides these two such as

header files or other .c files then you will have to submit a Makefile along with your code.

This is because we need to know how to resolve the dependencies among all the files that

you have provided. If you are using Java and have multiple files, a makefile will not be

necessary if your program doesn’t need any CLASPATH settings (javac *.java usually

work here).

2: You should submit a report, report.pdf (no more than 3 pages) including the following

3 items:

o An explanation on the data structure(s) that you have used for the internal

representation of the network topology.

o A tabulated summary of the comparison of the performance metrics for the 3 routing

protocols over the virtual circuit network. This comparison MUST be carried out

using the provided topology and workload files (topology.txt and workload.txt).

Your table must contain 8 columns (one each for the 8 performance metrics) and 6

rows (one each for the 3 routing protocols for two networks).

o An analysis of the results, i.e., where possible you MUST provide reasons for the

performance results that you observe. In particular comment on the reason behind

the differences in the following metrics for the 3 protocols: percentage of blocked

requests, average number of hops and the average propagation delay.

o Performance evaluation of the virtual packet network with respect to the packet rate

and different routing protocols. To this end, you need to collect the values of three

Page 10 of 11

performance metrics percentage of successfully routed packets, average number of

hops per circuit, average cumulative propagation delay per circuit by varying the

packet rates in the range of 1 - 5 and changing the routing protocols over the

topology.txt and workload.txt files. Then, you will create three plots corresponding

to each performance metric. In each plot, the x-axis is the different values of packet

rates and the y-axis is the performance values. Also, in each plot you draw three line

charts corresponding to each routing protocol. Finally, try to describe the plots and

the reason of the results by one paragraph for each plot.

3: A maximum of 5 min video must be included with your submission. This video is your

program DEMO and must start from Test 1 and finish by Test 4 in Marking Guide lines

specified in the following section. This is mandatory and it’s like DEMO for assignment 1.

We cannot mark your work without this.

• Marking Guidelines:

The marking will consist of the following sequence of tests:

➢ Test 1: Correct Compilation

Correct compilation of all files: 2 mark

➢ Test 2: Shortest Hop Path (SHP) Test

We will first evaluate the SHP routing protocol for both networks. We will first verify the

performance for the provided topology and workload files and then test with a different

topology and associated workload: 12 marks

➢ Test 3: Shortest Delay Path (SDP) Test

We will next evaluate the SDP routing protocol for both networks. The same topology and

workload files as in the SHP test will be used for this evaluation: 14 marks

➢ Test 4: Least Loaded Path (LLP) Test

Next we will evaluate the LLP routing protocol for both networks. The same topology and

workload files as in the SHP test will be used for this evaluation: 18 marks

Test 5: Report

Your report is worth 14 marks. Your report will be evaluated as follows:

• Description of the data structure used to create the internal representation of the network

topology: 2 marks

• Tabulated comparison of the performance metrics of the 3 routing protocols for the

provided topology and workload files: 2 marks

• Explanation of the performance results observed: 2 marks

• Plots for performance evaluation of the virtual packet network: 4 marks

• Explanation of the plots: 4 marks

Page 11 of 11

• Link to Mandatory Screencast Demo (Test 5)

Test 5: Mandatory Screencast Demo

The screencast demo must go through Test 1 until Test 4 (inclusive). You may describe your

program during this or just run the tests within a maximum of 5 minutes. You must show your

code during the screencast and you must be logged in to your own CSE account while doing

this. We will compare the submitted program with the DEMO and any cheating will result in

ZERO mark.

The screencast must be uploaded on YouTube before the deadline and a link must be included

for this in your report. Videos changed after submission date, will be ignored.

The screencast is mandatory and it’s like DEMO for Assignment 1. Your work cannot

be marked without it and your mark will be severely penalized with no exceptions

whatsoever.

Final Mark: The final mark out of 50 is then scaled to 15.

• Late Submission Penalty: Late penalty will be applied as follows:

o 1 day after deadline: 10% reduction

o 2 days after deadline: 20% reduction

o 3 days after deadline: 30% reduction

o 4 days after deadline: 40% reduction

o 5 or more days late: NOT accepted

NOTE: The above penalty is applied to your final total. For example, if you submit your

assignment 1 day late and your score on the assignment is 60, then your final mark will be

60 – 6 (10% penalty) = 54.

• Tutors Marking Procedure:

The following shows the sequence of events that will be involved in marking your

assignment:

1) We will start from your Screencast DEMO.

2) We will then test your program with the network topology and workload files that are

provided on the assignment page on OpenLearning (topology.txt and workload.txt). All 3

routing protocols and two networks will be tested.

3) We will repeat the tests for a different topology and associated workload file. Note that,

the format of the topology and workload files will be consistent with those provided on

OpenLearning.

4) Finally, your report will be marked.

IMPORTANT NOTE: We will not read through your code to evaluate your coding style, etc.

For assignments that fail to execute all of the above tests, we will be unable to award you a

substantial mark.