1. Problem Statement
CSE 4/589 Fall 2016 Programming Assignment 2 Routing Protocols
Due Time: 11/18/2016 @ 23:59:59
In this assignment you will implement a simplified version of the Distance Vector Protocol. The protocol will be run on top of servers (behaving as routers) using UDP. Each server runs on a machine at a pre-defined port number. The servers should be able to output their forwarding tables along with the cost and should be robust to link changes.(Note: we would like you to implement the basic algorithm: count to infinity not poison reverse. In addition, a server should send out routing packets only in the following two conditions: a) periodic update and b) the user uses command asking for one. This is a little different from the original algorithm which immediately sends out update routing information when routing table changes.
2. Getting Started
A Distance Vector Routing Algorithm – Text book: Page371 –Page377
3. Protocol Specification
The various components of the protocol are explained step by step. Please strictly adhere to the specifications.
3.1 Topology Establishment
In this programming assignment, you will use five CSE student servers – {Timberlake, Euston, Embankment, Underground, Highgate}.cse.buffalo.edu. Each server is supplied with a topology file at startup that it uses to build its initial routing table. The topology file is local and contains the link cost to the neighbors. For all other servers in the network, the initial cost would be infinity. Each server can only read the topology file for itself. The entries of a topology file are listed below:
–
–
–
num-servers: total number of servers.
server-ID, server-ID1, server-ID2: A unique identifier for a server, which is assigned by you.
cost: cost of a given link between a pair of servers. Assume that cost is an integer value. E.g., consider the topology in Figure1. We give a topology file for server 1(Timberlake).
Your topology files should only contain the Line entry part (2nd column). In each line, every two elements (e.g., server-id and corresponding IP, corresponding IP and port number) should be separated with a space. For cost values, each topology file should only contain the cost values of the host server’s neighbors (The host server here is the one which will read this topology file). You can use your own topology files to test your code. However, we will use our topology files to test your program. So please adhere to the format for your topology files.
IMPORTANT: In this environment, costs are bi-directional i.e. the cost of a link from A-B is the same for B-A. Whenever a new server is added to the network, it will read its topology file to determine who its neighbors are. Routing updates are exchanged periodically between neighboring servers. When this newly added server sends routing messages to its neighbors, they will add an entry in their routing tables corresponding to it. Servers can also be removed from a network. When a server has been removed from a network, it will no longer send distance vector updates to its neighbors. When a server no longer receives distance vector updates from its neighbor for three consecutive update intervals, it assumes that the neighbor no longer exists in the network and makes the appropriate changes to its routing table (link cost to this neighbor will now be set to infinity but not remove it from the table). This information is propagated to other servers in the network with the exchange of routing updates. Please note that although a server might be specified as a neighbor with a valid link cost in the topology
file, the absence of three consecutive routing updates from this server will imply that it is no longer present in the network.
3.2 Routing Update
Routing updates are exchanged periodically between neighboring servers based on a time interval specified at the startup. In addition to exchanging distance vector updates, servers must also be able to respond to user-specified events. There are 4 possible events in this system. They can be grouped into three classes: topology changes, queries and exchange commands. Topology changes refer to an updating of link status (update). Queries include the ability to ask a server for its current routing table (display), and to ask a server for the number of distance vectors it has received (packets). In the case of the packets command, the value is reset to zero by a server after it satisfies the query. Exchange commands can cause a server to send distance vectors to its neighbors immediately. Examples of these commands include:
– update 1 2 inf
The link between the servers with IDs 1 and 2 is assigned to infinity.
– update 1 2 8
Change the cost of the link to 8.
– step
Send routing update to neighbors right away. Note that except this, routing updates only happen periodically.
– packets
Display the number of distance vector packets this server has received since the last instance when this information was requested.
– disable server-id
Disable the link to given server. Here you need to check if the given server is its neighbor.
– crash
Emulate a server crash. Close all connections on all links. The neighboring servers must handle this close correctly and set the link cost to infinity.
– display
Display the current routing table. The display should be formatted as a sequence of lines, with each line indicating:
3.3 Message Format
Routing updates are sent using the General Message format. All routing updates are UDP unreliable messages. The message format for the data part is:
Number of update fields: (2 bytes):Indicate the number of entries that follow. – Server port: (2 bytes) port of the server sending this packet.
– Server IP: (4 bytes) IP of the server sending this packet.
– Server IP address n: (4 bytes) IP of the nth server in its routing table.
– Server port n: (2 bytes) port of the nth server in its routing table.
– Server ID n: (2 bytes) server id of the nth server on the network.
– Cost n: cost of the path from the server sending the update to the nth server whose ID is given in the packet.
Note: First, the servers listed in the packet can be any order i.e. 5, 3, 2, 1, 4. Second, the packet needs to include an entry to reach itself with cost 0 i.e. server 1 needs to have an entry of cost 0 to reach server 1.
4. Server Commands/Input Format
The server must support the following commands at startup:
– server -t
u topology-file-name: The topology file contains the initial topology configuration for the server,
e.g., timberlake_init.txt. Please adhere to the format described in 3.1for your topology files.
u routing-update-interval: It specifies the time interval between routing updates in seconds.
u port and server-id: They are written in the topology file. The server should find its port and server-id inthe topology file without changing the entry format or adding any new entries.
The following commands can be specified at any point during the run of the server:
– update
u server-ID1, server-ID2:The link for which the cost is being updated.
u Link Cost: It specifies the new link cost between the source and the destination server. Note that this command will be issued to both server-ID1and server-ID2 and involve them to update the cost and no other server.
– step
Send routing update to neighbors (triggered/force update)
– packets
Display the number of distance vector packets this server has received since the last invocation of this information.
– display
Display the current routing table. And the table should be displayed in a sorted order from small ID to big.
– disable
Disable the link to a given server. Doing this “closes” the connection to a given server with server-ID.
– crash
Close all connections. This is to simulate server crashes.
5. Server Responses/Output Format
The following are a list of possible responses a user can receive from a server:
– On successful execution of an update, step, packets, display or disable command, the server must display the following message:
where command-string is the command executed. Additional output as desired (e.g., for display,
packets, etc. commands) is specified in the previous section.
– Upon encountering an error during execution of one of these commands, the server must display the following response:
where error message is a brief description of the error encountered.
– On successfully receiving a route update message from neighbors, the server must display the following response:
RECEIVED A MESSAGE FROM SERVER
where the server-ID is the id of the server which sent a route update message to the local server. 6. Grading
Note: Please use {timberlake, euston, highgate, embankment and underground}.cse.buffalo.edu to test your program. Please use different names for different topology files. We will grade your submissions following the guidelines listedbelow:
[+10] Server startup
• Server supports the given startup command format. [+5]
• Reads the topology file correctly. [+5]
[+15] Sending distance vector updates
• Sends the distance vector updates to neighbors only.[+10]
The server receiving an update message must print out the server ID from which it receives this message. Please clearly mark (using comments) the data structure of the update message you used for your implementation and mention the line number of where you define it in your report.
• Updates are sent with an interval of specific time.[+5]
[+20] Routing table is updatedcorrectly
• Maintains a routing table. [+5]
Please clearly mark (using comments) the data structure of the routing table you used for your implementation and mention the line number of where you define it in your report.
• Server reads the updates from neighbors correctly. [+5]
• Applies the Bellman Ford equation correctly. [+10]
[+45] Supports user commands
• update command [+10]
• step [+5]
• packets [+5]
• display [+5]
• disable
• crash [+10]
• Server responses to user commands are correct. [+5]
[+10] Code documentation and Report
• Code documentation and a short report explaining the overall implementation details [+10]
Besides the implementation details, your report should mention the file name and the line number where you define the data structure of the update message and the data structure of the routing table.
7. Submission
You need to submit a working implementation of the project and a README file for that. Your submission should be a tar file – Name it as