用Java实现一个网络路由协议，并模拟在各种网络条件下，各个节点在协议下的运行状态。
Goal and Learning Objectives
In this assignment your task is to implement the link state routing protocol.
Your program will be running at all nodes in the specified network. At each
node the input to your program is a set of directly attached nodes (i.e.
neighbours) and the costs of these links. Each node will broadcast link-state
packets to all other nodes in the network. Your routing program at each node
should report the least-cost path and the associated cost to all other nodes
in the network. Your program should be able to deal with failed nodes.
Learning Objectives
On completing this assignment you will gain sufficient expertise in the
following skills:
- Designing a routing protocol
- Link state (Dijkstra’s) algorithm
- UDP socket programming
- Handling routing dynamics
Assignment Specification
In this assignment, you will implement the link state routing protocol.
The program will accept the following command line arguments:
- NODE_ID, the ID for this node. This argument must be a single uppercase alphabet (e.g., A, B, etc).
- NODE_PORT, the port number on which this node will send and receive packets to and from its neighbours.
- CONFIG.TXT, this file will contain the costs to the neighbouring nodes. It will also contain the port number being used by each neighbour for exchanging routing packets. An example of this file is provided below.
Since we can’t let you play with real network routers, the routing programs
for all the nodes in the simulated network will run on a single desktop
machine. However, each instance of the routing protocol (corresponding to each
node in the network) will be listening on a different port number. If your
routing software executes correctly on a single desktop machine, it should
also work correctly on real network routers. Note that, the terms router and
node are used interchangeably in the rest of this specification.
Assume that the routing protocol is being instantiated for a node A, with two
neighbours B and C. A simple example of how the routing program would be
executed (assuming it is a Java program named Lsr.java) follows:
java Lsr A 2000 config.txt
where the config.txt would be as follows:
B 5 2001
C 7 2002
The first line of this file indicates the number of neighbours (NOT the total
number of nodes in the network). Following this there is one line dedicated to
each neighbour. It starts with the neighbour id, followed by the cost to reach
this neighbour and finally the port number that this neighbour is using for
communication. For example, the second line in the config.txt above indicates
that the cost to neighbour B is 5 and this neighbour is using port number 2001
for receiving and transmitting link-state packets. The node ids will be
uppercase alphabets and you can assume that there will be no more than 10
nodes in the test scenarios. However, do not make assumptions that the node
ids will necessarily start from the letter A or that they will always be in
sequence. The link costs should be floating point numbers (up to the first
decimal) and the port numbers should be integers. These three fields will be
separated by a single white space between two successive fields in each line
of the configuration file. The link costs will be static and will not change
once initialised. Further, the link costs will be consistent in both
directions, i.e., if the cost from A to B is 5, then the link from B to A will
also have a cost of 5. You may assume that the configuration files used for
marking will be consistent with the above description and devoid of any
errors.
Important: It is worth restating that initially each node is only aware of the
costs to its direct neighbours. The nodes do not have global knowledge (i.e.
information about the entire network topology) at start-up.
The remainder of the specification is divided into two parts, beginning with
the base specification as the first part and the subsequent part adding new
functionality to the base specification. In order to receive full marks for
this assignment you must implement both parts. If you are unable to complete
the second part, you will still receive marks for the first part. (The marking
guidelines at the end of the specification indicate the distribution of
marks).
Part 1: Base Specification
In link-state routing, each node broadcasts link-state packets to all other
nodes in the network, with each link-state packet containing the identities of
the node’s neighbours and the associated costs to reach them. You must
implement a simple broadcasting mechanism in your program. Uponinitialisation,
each node creates a link-state packet (containing the appropriate information
– see description of link-state protocol in the textbook/lecture notes) and
sends this packet to all direct neighbours. The exact format of the link-state
packets that you will use is left for you to decide. Upon receiving this link-
state packet, each neighbouring router in turn broadcasts this packet to its
own neighbours (excluding the router from which it received this link-state
packet in the first place). This simple flooding mechanism will ensure that
each link-state packet is propagated through the entire network.
It is possible that some nodes may start earlier than their neighbours. As a
result, a node might send the link-state packet to a neighbour, which has not
run yet. You should not worry about this since the routing program at each
node will repeatedly send the link-state packet to its neighbours and a slow-
starting neighbour will eventually get the information. That said, when we
test your assignment, we would ensure that all nodes are initiated
simultaneously (using a script).
Each node should periodically broadcast the link-state packet to its
neighbours every UPDATE_INTERVAL. You should set this interval to 1 second. In
other words, a node should broadcast a link state packet every second.
Real routing protocols use UDP for exchanging control packets. Hence, you MUST
use UDP as the transport protocol for exchanging link-state packets amongst
the neighbours. Note that, each router can consult its configuration file to
determine the port numbers used by its neighbours for exchanging link-state
packets. Do not worry about the unreliable nature of UDP. Since, you are
simulating multiple routers on a single machine, it is highly unlikely that
link-state packets will be dropped. Furthermore, since link-state packets are
broadcast periodically, occasional packet loss will not impact the operation
of your protocol. If you use TCP, a significant penalty will be assessed.
On receiving link-state packets from all other nodes, a router can build up a
global view of the network topology. You may want to review your class notes
and consult standard data structures textbooks for standard representations of
undirected graphs, which would be an appropriate way to model this view of the
network.
Given a view of the entire network topology, a router should run Dijkstra’s
algorithm to compute least-cost paths to all other routers within the network.
Each node should wait for a ROUTE_UPDATE_INTERVAL (the default value is 30
seconds) since start-up and then execute Dijkstra’s algorithm. Given that
there will be no more than 10 nodes in the network and a periodic link-state
broadcast frequency of 1 second, 30 seconds is a sufficiently long duration
for each node to discover the global view of the entire topology.
Once a router finishes running Dijkstra’s algorithm, it should print out to
the terminal, the least-cost path to each destination node (excluding itself)
along with the cost of this path. The following is an example output for node
A in some arbitrary network:
least-cost path to node B: ACB and the cost is 10
least-cost path to node C: AC and the cost is 2.5
We will wait for duration of ROUTE_UPDATE_INTERVAL after running your program
for the output to appear (some extra time will be added as a buffer). If the
output does not appear within this time, you will be heavily penalised. As
indicated earlier, we will restrict the size of the network to 10 nodes in the
test topologies. The default value of 30 seconds is sufficiently long for all
the nodes to receive link-state packets from every other node and compute the
least-cost paths.
Your program should execute forever (as a loop). In other words, each node
should keep broadcasting link-state packets every UPDATE_INTERVAL and
Dijkstra’s algorithm should beexecuted and the output printed out every
ROUTE_UPDATE_INTERVAL. To kill an instance of the routing protocol, the user
should type CTRL-C at the respective terminal.
Restricting Link-state Broadcasts: Note that, a naïve broadcast strategy;
wherein each node retransmits every link state packet that it receives will
result in unnecessary broadcasts and thus increase the overhead. To elaborate
this issue, consider the example topology discussed in the latter part of the
spec. The link-state packet created by node A will be sent to its direct
neighbours B, C and D. Each of these three nodes will in turn broadcast this
link-state packet to their neighbours. Let us consider Node C, which
broadcasts A’s link state packet to B, D, E and F. Note that node B has
already broadcast A’s link state packet once (when it received it directly
from A). Node B has now received this same link-state packet via node C. There
should thus be no need for node B to broadcast this packet again. You MUST
implement a mechanism to reduce such unnecessary broadcasts. This can be
achieved in several ways. You are open to choose any method to achieve this.
You must describe your method in the written report.
Part 2: Dealing with Node Failures
In this part you must implement additional functionality in your code to deal
with random node failures. Recall that in the base assignment specification it
is assumed that once all nodes are up and running they will continue to be
operational till the end when all nodes are terminated simultaneously. In this
part you must ensure that your algorithm is robust to node failures. Once a
node fails, its neighbours must quickly be able to detect this and the
corresponding links to this failed node must be removed. Further, the routing
protocol should converge and the failed nodes should be excluded from the
least-cost path computations. The other nodes should no longer compute least-
cost paths to the failed nodes. Furthermore, the failed nodes should not be
included in the least-cost paths to other nodes.
A simple method that is often used to detect node failures is the use of
periodic heartbeat (also often known as keep alive) messages. A heartbeat
message is a short control message, which is periodically sent by a node to
its directly connected neighbours. If a node does not receive a certain number
of consecutive hearbeat messages from one of its neighbours it can assume that
this node has failed. Note that, each node transmits a link-state packet to
its immediate neighbour every UPDATE_INTERVAL (1 second). Hence, this distance
vector message could also double up as the hearbeat message. Alternately, you
may wish to make use of an explicit heartbeat message (over UDP), which is
transmitted more frequently (i.e. with a period less than 1 second) to
expedite the detection of a failed node. It is recommended that you wait till
at least 3 consequent hearbeat (or link-state) messages are not received from
a neighbour before considering it to have failed. This will ensure that if at
all a UDP packet is lost then it does not hamper the operation of your
protocol.
Once a node has detected that one of its neighbours has failed, it should
update its link-state packet accordingly to reflect the change in the local
topology. Eventually, via the propagation of the updated link-state packets,
other nodes in the network will become aware that the failed node is
unreachable and it will be excluded from the link-state computations (i.e.
Dijkstra’s algorithm).
Once a node has failed, you may assume that it cannot be initialised again.
While marking, we will only fail a few nodes, so that a reasonable connected
topology is still maintained. Furthermore, care will be taken to ensure that
the network does not get partitioned. In a typical topology (recall that the
largest topology used for testing will consist of 10 nodes), at most 3 nodes
will fail. However, note that the nodes do not have to fail simultaneously.
Recall that each node will execute Dijkstra’s algorithm periodically after
ROUTE_UPDATE_INTERVAL (30 seconds) to compute the least-cost path to every
other destination. It may so happen that the updated link-state packets
following a node failure may nothave reached certain nodes in the network
before this interval expires. As a result, these nodes will use the old
topology information (prior to node failure) to compute the least-cost paths.
Thus the output at these nodes will be incorrect. This is not an error. It is
just an artefact of the delay incurred in propagating the updated link-state
information. To account for this, it is necessary to wait for at least two
consecutive ROUTE_UPDATE_INTERVAL periods (i.e. 1 minute) after the node
failure is initiated. This will ensure that all the nodes are aware of the
topology change.
While marking, we will wait for 2*ROUTE_UPDATE_INTERVAL following a node
failure before checking the output.
Additional Notes
This is not a group assignment. You are expected to work on this individually.
How to start: Sample UDP client and server programs are available on the Week
3 lecture material page. They are a good starting point to start your
development. You will also find several links to network programming resources
on that page.Language and Platform: You are free to use one of C, JAVA or
Python to implement this assignment. Please choose a language that you are
comfortable with. The programs will be tested on CSE Linux machines. So please
make sure that your entire application 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 or JVM).
Note that CSE machines support the following: gcc version 4.9.2, Java 1.7,
Python 2.7, 2.8 and 3. Note for Python: In your report, please indicate which
version of Python you have used. You may only use the basic socket programming
APIs providing in your programming language of choice. Note that, the network
will be simulated by running multiple instances of your program on the same
machine with a different port number for each node. Make sure that your
program will work appropriately under these conditions. See the sequence of
operations listed below for details.
Error Condition: Note that all the arguments supplied to the programs will be
in the appropriate format. The configuration files supplied as an argument to
each node will also be consistent with the test topology. Your programs do not
have to handle errors in format, etc.
Do not worry about the reliability of UDP in your assignment. It is possible
for packets to be dropped, for example, but the chances of problems occurring
in a local area network are fairly small. If it does happen on the rare
occasion, that is fine. Further, your routing protocol is inherently robust
against occasional losses since the link state packets are exchanged every 1
second. If your program appears to be losing or corrupting packets on a
regular basis, then there is likely a fault in your program.
Test your assignment out with several different topologies (besides the sample
topology provided).
Make sure that your program is robust to node failures by creating several
failed nodes (however make sure that the topology is still connected). You can
very easily work out the least-cost paths manually (as shown in the lecture
notes or the textbook) to verify the output of your program.
