|
论文题目：Routing performance analysis
论文语言：英语论文 English
指导价格：0
论文专业：IT
字数：3 pages
学校国家：澳大利亚
是否有数据处理要求：否
您的学校：
论文用于：BA assignment 本科课程作业
Page 1 of 8
COMP 3331/9331: Computer Networks & Applications
Programming Assignment: Routing Performance Analysis
Due Date: Friday 25 Oct 2013, 11:59 pm (Week 12)
Change Log
a. Version 1.0 released on September 17th, 2013
b. Version 1.1 released on September 19th, 2013
A missing link in Figure 1 was added.
Additional notes changed: Assignment can be done in a group of two.
Assessment: 60 marks (towards the Practical component)
Goal: The purpose of this assignment is to gain insights into the performance of different network-layer routing algorithms. Your task is to develop a program that will evaluate the performance of 3 different routing protocols over a virtual circuit network (i.e. a network with a connection-based network layer, unlike the Internet)
Learning Objectives: On completing this assignment you will gain sufficient expertise in the following skills:
• Understanding and developing routing protocols
• Performance analysis
Specification:
You will implement the following program:
Routing_Performance
• The routing_performance program will accept the following command line arguments:
o ROUTING_SCHEME: this specifies the routing scheme that will be evaluated.
Your program should implement 3 routing protocols, which are essentially variants of Dijkstra’s algorithm, as explained later in the specification. This argument will take on one of the following values: SHP, SDP and LLP corresponding to the 3 routing protocols: Shortest Hop Path (SHP), Shortest Delay Path (SDP) and Least Loaded Path (LLP), respectively.
o TOPOLOGY_FILE: this file contains the network topology specification.
o WORKLOAD_FILE: this file contains the virtual circuit requests in the network.
• The network topology that will be used for the evaluation will be specified in the
TOPOLOGY_FILE (the second argument). We will be using a virtual circuit network (unlike the connection-less network layer of the Internet) to evaluate the performance of the routing protocols. Recall that a routing protocol is still required in a virtual-circuit network to determine the path between the source and destination of the circuit during Page 2 of 8the circuit establishment phase. A simple example of a network topology specification for a network with 4 routers (routers will be referred to as nodes in the rest of the specification), labelled A, B, C and D is as follows:
A B 10 19
A C 15 20
B C 20 20
B D 30 70
C D 8 20
This example network topology has 5 links connection the 4 nodes as shown in the figure below (Figure 1 on the next page). Each line in this file defines a point-to-point link. For example, the first line specifies a link from node A to node B, with a one-way propagation delay of 10 这个例子的网络拓扑结构有5个环节，连接4个节点，在下面的图（下页图1）所示。在这个文件中的每一行定义一个点至点链接。例如，第一行指定一个链接从节点A到节点B，用一个单向传播延迟为10milliseconds and a capacity that can accommodate up to 19 simultaneous virtual circuits at any given time. All links are assumed to be bi-directional, with identical propagation delay in both directions (hence, the ordering of the names of the two endpoints of the point-to-point link does not matter, i.e. the first line in the example above could have been replaced with “B A 10 19”). Further, each virtual circuit is also assumed to be bi-directional and consumes unit resource (i.e. a resource of 1). 所有链路被认为是双向的，在两个方向上具有相同的传播延迟（因此，在点对点链路的两个端点的名称的顺序并不重要，即在上面的例子中可以在第一行已取代与“ BA 10月19日” ） 。另外，每个虚拟电路也假定为双向的，消耗单元资源（即资源的1 ） 。
将有至多有一个图中的任意两个节点之间的直接联系。你可以假设，即将不会有孤立节点的拓扑结构将形成一个连通图。
你的程序的第一个任务是读取拓扑文件和使用合适的数据结构，构造一个合适的网络拓扑结构，内部表示。你可能想咨询的标准数据结构无向图，这将是一个合适的方法来模拟网络标准声明教科书。你可以假设所有的节点名称是大写字母（即从A到Z ，最多26个节点） ，所有的传播延迟d是正整数（ 0 <D < 200 ） ，并表示以毫秒为单位，所有链接容量C为正整数（ 0 <C < 100 ） ，表示虚拟电路可以得到的链接数量。一个更复杂的网络拓扑结构，用于测试你的代码，你可以使用分配的网页（ topology.txt ）上。
There will be at most one direct link between any two nodes in the graph. You may assume that the topology will form a connected graph i.e. there will be no isolated nodes.
The first task for your program is to read in the topology file and construct a suitable internal representation of the network topology, using an appropriate data structure. You may want to consult standard data structures textbooks for standard representations of undirected graphs, which would be an appropriate way to model the network. You may assume that all node names are single upper-case alphabetic characters (i.e., a maximum of 26 nodes from A to Z), all propagation delays d are positive integers (0 < d < 200) and expressed in milliseconds, and all link capacities C are positive integers (0 < C < 100) and indicate the number of virtual circuits that can be supported by a link. A more complex network topology, which you may use for testing your code is available on the assignment webpage (topology.txt).
Figure 1: Topology for the above example
• The network is initially empty, i.e., there are no virtual circuits established. The virtual circuit requests that arrive in the network will be specified in the WORKLOAD_FILE (third argument), which is ordered by time. The next step for your program is to read in the arriving virtual circuit request workload (from the file), one request at a time, in timestamp order, and attempt to establish the circuit in the network according to the routing algorithm in use (routing algorithms are explained later). The virtual circuit workload for the network is specified in a simple four-column format as follows:Page 3 of 8
0.123456 A D 12.527453
7.249811 B C 48.129653
8.975344 B D 6.124743
10.915432 A C 106.724339
15.817634 B C 37.634569
Each line of this file describes one virtual circuit request. The first column specifies the time (in seconds) at which the request arrives to the network. You may assume that time starts at 0 seconds and that time values will be represented up to 6 decimal digits (i.e. microseconds). The second column specifies the originator (source node) for the request, and the third column specifies the recipient (destination node) for the request. The final
column specifies the time duration for which this virtual circuit remains active if the circuit is successfully established. As an example, the first line in the above file contains a request that originated at time 0.123456 seconds for a virtual circuit to be established from node A to node D. This circuit if established will be active for a duration of 12.527453 seconds. A more comprehensive virtual circuit workload, which you may use for testing your program, is available on the assignment webpage in the workload.txt file. (Note that, this workload is consistent with the topology specified in topology.txt)
• For each virtual circuit request in the above workload, your program must use the specified routing algorithm to determine if the circuit can be established. To be more specific, your program must select the “best” route depending on the routing protocol in use (routing protocols are explained in the next bullet point) from the source to the destination of the circuit and then determine if there is sufficient capacity along each link of this end-to-end path to accommodate the circuit. Recall that each virtual circuit uses unit capacity on each link. You may assume that the routing decision for each request can be made in zero processing time. A virtual circuit that is successfully established must be counted as such, and the network resources associated with that circuit marked as "busy" for the duration of the circuit. For this purpose, assume that each circuit consumes exactly one unit (i.e., one "circuit") of link capacity on each link. Of course, recall that virtual circuits are bidirectional. When a circuit terminates, the resources (i.e.
unit capacity) along the individual links of the end-to-end path are released, and become available for subsequent circuits that are established in the network. A circuit request that is not routed successfully is said to be "blocked". A blocked request means that there is no physical path currently available from the specified source to the specified destination #p#分页标题#e#
(according to the routing protocol in use). Such requests must be immediately discarded from further consideration by your program. Your program must count and report the number of blocked requests. A list of performance metrics that your program mustmeasure and report is specified later in the specification.
• Your program should implement the following three routing protocols to determine the least cost path between the source and destination. The first argument in the argument list (as explained earlier) will determine which protocol should be used for a particular run of your program. The algorithms are essentially variants of Dijkstra’s algorithm (i.e. link-state routing) with each scheme using a different “cost” metric.
(1) Shortest Hop Path (SHP): This algorithm tries to find the shortest path currently available from the source to the destination, where the length of a path refers to the number of hops (i.e. links) traversed. In essence this is Dijkstra’s algorithm with the cost of each link set to 1. Note that, this algorithm ignores the delay and load associated with each link.Page 4 of 8
(2) Shortest Delay Path (SDP): This algorithm tries to find the shortest path currently available from the source to the destination, where the length of the path refers to the cumulative propagation delay for traversing the chosen links in the path. In other words, this is Dijktra’s algorithm with the cost of each link set to the propagation delay. Recall that the network topology file specifies the delay along each link in the network. Note that, this algorithm ignores the number of hops and the load associated with each link.
(3) Least Loaded Path (LLP): This algorithm tries to find the least loaded path currently available from the source to the destination, where the load of a path is defined to be the maximum load on any link in the path. The load on a link is defined as the ratio of its current number of active virtual circuits to the capacity, C, of that link for carrying virtual circuits. Note that, this algorithm ignores the number of hops and the delay associated with each link. There are two main differences between LLP and the other two algorithms (SHP and SDP). Firstly, the path cost in LLP is not an additive function, as is the case with the other two algorithms (in SHP and SDP the cost of the path is simply the sum of the cost along each individual link that constitutes the path). Secondly, link costs (i.e. the link load) change with time, whereas in both SHP and SDP the link costs are static over the entire lifetime.
• 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 circuit request in case the path selected by the routing protocol results in a blocked request. Simply count this as a blocked request and move on to the next request.
• Your program will need to keep track of time. You may assume that time starts at 0.
Recall that the workload file specifies the time at which each virtual circuit request originates in the network and the duration of each circuit (provided it is established). As discussed earlier the routing decision for each 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 circuit requests read from the workload file.
o The number (and percentage) of successfully routed virtual circuits.
o The number (and percentage) of blocked requests.
o The average number of hops (i.e. links) consumed per successfully routed virtual circuit.
o The average source-to-destination cumulative propagation delay per successfully routed circuit request.
• The following illustrates an example initiation of your program:java routing_performance SHP topology.txt workload.txt (for JAVA)routing_performance SHP topology.txt workload.txt (for C)Page 5 of 8
• 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:
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.
Moreover, you MUST write the above output format in the standard output. The above strict output format can help us to assess your assignment by using some autoassessment tools.
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.
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 Friday, 27th September 2013, 11:59 pm. We are
unable to help you choose a group member nor would be accept more than 2 people in a group. However, you are encouraged to use messageboard. Marking criteria will remain the same. 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 http://www.ukassignment.org/azdxassignment/ problems post submission will be hard to manage. Please keep a log of your contributions/meetings. This is not a group assignment. You are expected to work on this individually. Non-programming assignment is allowed as an exception to non-CSE and non-EE&T students who do not have experience with programming (e.g: Mechatronic’s). Note that non-CSE students also have the option of choosing the non-programming assignment. Check details about this on the assignment webpage. You must send an email to class account indicating that you are opting for non-programming assignment by Friday, 27th September 2013,
11:59 pm. If we DO NOT receive e-mail from such students, we will assume that theyhave opted for the programming assignment. Students cannot change their decision past the deadline.
• 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).
total number of virtual circuit requests: 200
number of successfully routed requests: 100
percentage of successfully routed request: 50
number of blocked requests: 100
percentage of blocked requests: 50
average number of hops per circuit: 5.4
average cumulative propagation delay per circuit: 120.5Page 6 of 8
• 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 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).
• Language and Platform: You are free to use either C or JAVA 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).#p#分页标题#e#
• Submission: We will inform you about the details of submission 1 week before the deadline (check the notice board closer to submission date). You really need only one file: routing_performance.c (or routing_performance.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. A link on how to create a makefile is available on the course website. If you are using Java and have multiple files, a makefile will not be necessary (javac *.java should work here). In addition 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 under consideration. This comparison MUST be carried out using the provided topology and workload files (topology.txt and workload.txt). Your table must contain 7 columns (one each for the 7 performance metrics) and 3 rows (one each for the 3 routing protocols).
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.
• Late Submission Penalty: Late penalty will be applied as follows:
o 1 day after deadline: 10% reductionPage 7 of 8
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 30, then your final mark will
be 30 – 3 (10% penalty) = 27.
• 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.
• Forum Use: You are free to discuss (and are in fact strongly encouraged to do so) issues relevant to the assignment on the course forum. However, refrain from posting large code-fragments on the forum. Students will be heavily penalised for doing so.
Sequence of Operation for Marking
The following shows the sequence of events that will be involved in marking your
assignment:
1) We will first test your program with the network topology and workload files that are provided on the assignment webpage (topology.txt and workload.txt). All 3 routing protocols will be tested.
2) 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 the webpage.
3) Finally, your report will be marked.
Marking Guidelines:
The marking will consist of the following sequence of tests:
Test 1:Correct Compilation
Correct compilation of all files: 2 markPage 8 of 8
Test 2: Shortest Hop Path (SHP) TestWe will first evaluate the SHP routing protocol. 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. 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. 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: 4 marks
• Explanation of the performance results observed: 8 marksIMPORTANT 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.
Consultation:
Please note that Mr. Mohsen Rezvani in-charge of this assignment (he will also be marking this assignment) and all queries should be directed to him via cs3331@cse.unsw.edu.au with subject heading Assignment Query. Additionally, Mr. Rezvani will also provide weekly Consultation. The consultation timing and venue would be 4:00PM -5:00PM on Friday in Room 508, Building K-17. The consultation sessions will be started from Friday, October 4, 2013.
|
 |
|||
| 网站地图 |
