- Distance Vector Routing Algorithm Program In Java
- Distance Vector Routing Algorithm Program In Java Free
- Distance Vector Routing Algorithm Program In Java With Example
- Distance Vector Routing Algorithm Program In Java Example
ProgrammingAssignment 2 (5 points)
Distance Vector Routing Algorithm Program In Java 10/3/2019 Distance vector routing is an asynchronous algorithm in which node x sends the copy of its distance vector to all its neighbors. The sendMsg function is already implemented in node.h; you must complete the recvMsg function in order to process a routing table update from a neighbor at a given node. The recvMsg function will run the Bellman Ford update algorithm of the distance vector routing protocol, and update its routing table as required.
Descriptions of distance-vector and link-state routing algorithms. Cormen, Leiserson, and Rivest, Introduction to Algorithms, pp. 465, 470, and 527. Graph representation, breadth-first searches, and Dijkstra's shortest-path algorithm. Javadoc API documentation for the routing simulator. Nov 06, 2019 Distance Vector Algorithm – A router transmits its distance vector to each of its neighbors in a routing packet. Each router receives and saves the most recently received distance vector from each of its neighbors. A router recalculates its distance vector when.
Implementing aDistance Vector Routing Algorithm
This assignment is identical to theprogramming assignment given in Chapter 4 of Kurose-Ross's text'Computer Networking: A Top-Down Approach Featuring the Internet', 3rdedition. A few minor changes have been made for our course.Overview
In this lab, you will be writing a 'distributed' set of proceduresthat implement a distributed asynchronous distance vector routing forthe network shown in Figure Lab.4-1.
Figure Lab.4-1: Network topology andlink costs for DV routing lab
The Basic Assignment
The routines you will write For the basic part of theassignment, you are to write the following routines which will``execute' asynchronously within the emulated environment that theauthors have provided for this assignment.
For node 0, you will write the routines:
- rtinit0() This routine will be called once at thebeginning of the emulation. rtinit0() has no arguments. Itshould initialize the distance table in node 0 to reflect the directcosts of 1, 3, and 7 to nodes 1, 2, and 3, respectively. In Figure 1,all links are bi-directional and the costs in both directions areidentical. After initializing the distance table, and any other datastructures needed by your node 0 routines, it should then send itsdirectly-connected neighbors (in this case, 1, 2 and 3) the cost of itminimum cost paths to all other network nodes. This minimum costinformation is sent to neighboring nodes in a routing packet bycalling the routine tolayer2(), as described below. The formatof the routing packet is also described below.
- rtupdate0(struct rtpkt *rcvdpkt). This routine will becalled when node 0 receives a routing packet that was sent to it by oneif its directly connected neighbors. The parameter *rcvdpktis a pointer to the packet that was received.
rtupdate0() is the 'heart' of the distance vector algorithm.The values it receives in a routing packet from some other node icontain i's current shortest path costs to all other networknodes. rtupdate0() uses these received values to update its owndistance table (as specified by the distance vector algorithm). If itsown minimum cost to another node changes as a result of the update, node0 informs its directly connected neighbors of this change in minimumcost by sending them a routing packet. Recall that in the distancevector algorithm, only directly connected nodes will exchange routingpackets. Thus nodes 1 and 2 will communicate with each other, but nodes1 and 3 will node communicate with each other.
As we saw in class, the distance table inside each node is theprincipal data structure used by the distance vector algorithm. You willfind it convenient to declare the distance table as a 4-by-4 array of int's,where entry [i,j] in the distance table in node 0 is node0's currently computed cost to node i via direct neighbor j. If 0 is notdirectly connected to j, you can ignore this entry. We will usethe convention that the integer value 999 is ``infinity.'
Figure Lab.4-2 provides a conceptual view of the relationship of theprocedures inside node 0.
Similar routines are defined for nodes 1, 2 and 3. Thus, you willwrite 8 procedures in all: rtinit0(), rtinit1(), rtinit2(),rtinit3(),rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3()
Figure Lab.4-2: Relationship between proceduresinside node 0
Software Interfaces
Distance Vector Routing Algorithm Program In Java
The procedures described above are the ones that you will write. Authors Kurose and Ross have written the following routines that can becalled by your routines:
- tolayer2(struct rtpkt pkt2send)
- where rtpkt is the following structure, which is alreadydeclared for you. The procedure tolayer2() is defined in thefile prog2.c Note that tolayer2() is passed a structure, not a pointer toa structure.
- printdt0()
- will pretty print the distance table for node 0. It is passed apointer to a structure of type distance_table.printdt0()and the structure declaration for the node 0 distance table aredeclared in the file node0.c. Similar pretty-print routines aredefined for you in the files node1.c, node2.c node3.c.
The simulated network environment
Your procedures rtinit0(), rtinit1(), rtinit2(), rtinit3()and rtupdate0(), rtupdate1(), rtupdate2(), rtupdate3() sendrouting packets (whose format is described above) into the medium. Themedium will deliver packets in-order, and without loss to the specifieddestination. Only directly-connected nodes can communicate. The delaybetween is sender and receiver is variable (and unknown).
When you compile your procedures and Kurose-Ross's procedurestogether and run the resulting program, you will be asked to specifyonly one value regarding the simulated network environment:
- Tracing. Setting a tracing value of 1 or 2 will print outuseful information about what is going on inside the emulation (e.g.,what's happening to packets and timers). A tracing value of 0 will turnthis off. A tracing value greater than 2 will display all sorts ofodd messages that are for my own emulator-debugging purposes.
A tracing value of 2 may be helpful to you in debugging your code.You should keep in mind that real implementors do not haveunderlying networks that provide such nice information about what isgoing to happen to their packets!
The Basic Assignment (3 points)
You are to write the procedures rtinit0(), rtinit1(),rtinit2(), rtinit3() and rtupdate0(), rtupdate1(), rtupdate2(),rtupdate3() which together will implement a distributed,asynchronous computation of the distance tables for the topology andcosts shown in Figure 1.
You should put your procedures for nodes 0 through 3 in files callednode0.c, .... node3.c. You are NOT allowed to declare any globalvariables that are visible outside of a given C file (e.g., any globalvariables you define in node0.c. may only be accessed inside node0.c).This is to force you to abide by the coding conventions that you wouldhave to adopt is you were really running the procedures in four distinctnodes. To compile your routines: cc prog2.c node0.c node1.cnode2.c node3. Prototype versions of these files are here: node0.c, node1.c, node2.c, node3.c. You can pick up a copy of the file prog2.cat http://inst.eecs.berkeley.edu/~ee122/sp06/ProgAsgns/prog2.c.
This assignment can be completed on any machine supporting C. Itmakes no use of UNIX features.
For your sample output, your procedures should print out a messagewhenever your rtinit0(), rtinit1(), rtinit2(), rtinit3() or rtupdate0(),rtupdate1(), rtupdate2(), rtupdate3() procedures are called, givingthe time (available via the global variable clocktime). For rtupdate0(),rtupdate1(), rtupdate2(), rtupdate3() you should print the identityof the sender of the routing packet that is being passed to yourroutine, whether or not the distance table is updated, the contents ofthe distance table (you can use the pretty-print routines), and adescription of any messages sent to neighboring nodes as a result of anydistance table updates.
The sample output should be an output listing with a TRACE value of2. Highlight the final distance table produced in each node. Yourprogram will run until there are no more routing packets in-transit inthe network, at which point our emulator will terminate.
The Advanced Assignment (2 points)
You are to write two procedures, rtlinkhandler0(int linkid, intnewcost) and rtlinkhandler1(int linkid, int newcost),which will be called if (and when) the cost of the link between 0 and 1changes. These routines should be defined in the files node0.cand node1.c, respectively. The routines will be passed the name(id) of the neighboring node on the other side of the link whose costhas changed, and the new cost of the link. Note that when a link costchanges, these routines will have to update the distance table and may(or may not) have to send updated routing packets to neighboring nodes.
In order to complete the advanced part of the assignment, you willneed to change the value of the constant LINKCHANGES (line 3 in prog2.c)to 1. FYI, the cost of the link will change from 1 to 20 at time 10000and then change back to 1 at time 20000. Your routines will be invokedat these times.
We would STRONGLY recommend that you first implement thebasic assignment and then extend your code to implement the advancedassignment. It will not be time wasted.
What to submit
Please submit a tar file (as in programming assignment 1) electronically, that contains:
- the source file(s) (EXCEPT prog2.c which will be our own unchanged version)
- a README file that describes your implementations of thesubroutines, and special instructions (if any) for running the code.
- a sample output -- more on this below.
For your sample output, your procedures should print out a messagewhenever your rtinit0(), rtinit1(), rtinit2(), rtinit3() or rtupdate0(),rtupdate1(), rtupdate2(), rtupdate3() procedures are called, givingthe time (available via the global variable clocktime). For rtupdate0(),rtupdate1(), rtupdate2(), rtupdate3() you should print the identityof the sender of the routing packet that is being passed to yourroutine, whether or not the distance table is updated, the contents ofthe distance table (you can use the pretty-print routines), and adescription of any messages sent to neighboring nodes as a result of anydistance table updates.
The sample output should be an output listing with a TRACE value of2. Highlight the final distance table produced in each node. Yourprogram will run until there are no more routing packets in-transit inthe network, at which point our emulator will terminate.
Please email your submission to the TAs at ee122-ta[AT]imail.eecs.berkeley.edu and ee122-tb[AT]imail.eecs.berkeley.edu with the subject line as PROG ASGN 2.
GOOD LUCK
- Related Questions & Answers
- Selected Reading
The Distance-Vector routing algorithm is known by other names. Bellman-Ford routing algorithm and the Ford-Fulkerson algorithm are generally distributed after the researchers create it (Bellman 1957, and Ford and Fulkerson, 1962).
Features
Following are the features of the distance vector routing are −
The routers send the knowledge of the whole autonomous framework.
Sharing of data takes place only with the neighbours.
Sending of data holds place at constant, ordinary intervals, declared every 30 seconds.
In this algorithm, each router evaluates the distance between itself and every achievable destination. This is accomplished by assessing the distance between a router and all of its immediate router neighbours and adding each neighbouring routers computations for the distance between that neighbour and its close neighbours.
Three keys to learn how this algorithm works are as follows −
Knowledge about the entire network
Each router sends its knowledge about the entire network. It communicates all of its connected knowledge about the network to its neighbours.
Routing only to the neighbours
Each route repeatedly shares its knowledge about the network only to those routers with the explicit connection. It transmits whatever knowledge it has about the complete network by all of its parts. This data is taken and stored by each neighbouring router and can upgrade the routers own data about the network.
Information sharing at regular intervals
In distance vector routing, each router repeatedly sends its knowledge about the whole network with its neighbours. For example, after 30 seconds, each router shares its data about its neighbour's entire network.
In this, the rectangular box represents LANs. The number inside each rectangular box is the LANs Network ID. These LANs are linked by a router, described by the boxes such as A, B, C, D, E. The square boxes denote the connection of the routers to their neighbours.
Distance Vector Routing Algorithm Program In Java Free
Routing table creation and updating
This table has three columns which contain the information about network id, cost & Next Hop. Let the original tables for each router be.
For router A
| Network id | Cost | Next Hop |
|---|---|---|
| 24 | 1 | B |
| 23 | 1 | E |
| 88 | 1 | F |
For router B
| Network id | Cost | Next Hop |
|---|---|---|
| 24 | 1 | A |
| 65 | 1 | C |
For router E
| Network id | Cost | Next Hop |
|---|---|---|
| 23 | 1 | A |
| 18 | 1 | D |
For router D
| Network id | Cost | Next Hop |
|---|---|---|
| 18 | 1 | E |
| 76 | 1 | C |
When A can send his packet or routing table information to B router, E & C directly.
Similarly, B can send routing table information to router A & C and so on.
When A receivers are routing tables from B, E & F, it can update its table. Similarly, B receives A and C updates itself and so on, as shown in the new table.
New routing table for router A
| Network id | Cost | Next Hop |
|---|---|---|
| 23 | 1 | E |
| 24 | 1 | B |
| 88 | 1 | F |
| 23 | 2 | D |
| 38 | 2 | C |
New routing table for router B
| Network id | Cost | Next Hop |
|---|---|---|
| 13 | 2 | A |
| 24 | 1 | A |
| 28 | 1 | C |
| 35 | 2 | C |
| 38 | 2 | C |
Similarly, every router will update itself and so on. The updating algorithm checks that the router first adds Hop to the Hop count field for each advertised route. The router should apply these rules.
If the displayed destination is not in the routing table, the router must insert that displayed data into the table.
If the displayed destination is in the routing table, then two things can happen.
Distance Vector Routing Algorithm Program In Java With Example
If the next-hop field is similar, the router must restore the table's entry with the displayed one.
Distance Vector Routing Algorithm Program In Java Example
If the next-hop field is not a similar
If the displayed hop count is lesser than the one on the table, the router must restore the entry in the table with the new one.
If the displayed hop count is not lesser, the router must do nothing.