Data Communications and Networks

G22.2262-001

 

Assignment 5 -  Distance Vector Routing (35 points)

Due Date:  December 18, 2003 no later than 11:59 PM

 

NOTE: There is no late period for the final assignment.  It must be submitted by 11:59 PM on Dec 18 without exception.

 

 

Revision 1:   November 18, 2003

Revision 2:   November 21, 2003  fix typos, change ININITY, and allow student code

Revision 3:   November 24, 2003  fix declaration for registerProtocol()

Revision 4:    December 10, 2003   use fprintf(stdout) for debugging.

Revision 5:   December 11, 2003   add new functions isNeighbor() and isNeighborUp()

 

1.Overview.

 

There are a number of algorithms and that can be used to route packets in a packet switch network (PSN) network.  One of the most widely implemented of these is the distance vector algorithm, which is a distributed implementation of the Bellman-Ford algorithm.  Your task is to add a packet routing capability based on a subset of the Routing Information Protocol described in RFC 1058 to the simulated protocol stack you developed in assignment 3.

 

We will provide you with a framework of code that fully implements the link, network, discovery, and transport protocols.  We will also supply a stub for the routing functions (routing.c).  You will fill in the missing code in routing.c.  You may also choose to use your own code that you developed for assignment3.  If you choose to use your own code, you are required to implement the operational, functional, and performance requirements given in this specification.

 

In this assignment, we provide the discovery protocol to simplify your development.  The supplied discovery protocol uses an initial (one time) discovery process to learn the addresses of each node's neighbors and establish the cost metric (propagation delay) for each neighbor.

 

Following the initial discovery process, the discovery protocol uses the EV_LINKSTATE event to detect link state changes.  The discovery module is responsible for alerting the routing module when Nodes (that is, their links) complete their reboot, fail, and recover.

 

The transport layer will format a transport layer packet when it gets a message from the application layer, then call a route() function in routing.c.  The route() function will use a distance vector table to choose the appropriate neighbor, make a network layer packet that encapsulates the transport packet, and send it through the network by calling the sendPacket() function in network.c.

 

 

2.Specification.

 

2.1.Network Layer Interface.

 

The network layer (network.c) provides the following function to send messages down to the appropriate link:

 

void sendPacket(int addr, NetPacket *pkt)

 

where:     addr                                is the cnet address of the node to which the packet is written.

              pkt                                  is a pointer to a NetPacket.

 

NOTE: addr is NOT the final destination node.  It is the address of first-hop node derived from your routing table.  The network layer will determine the link number from the address.  The NetPacket contains the actual destination address.

 

The network layer also provides two functions to allocate and release NetPackets:

 

The allocNetPacket function returns a completely formatted NetPacket that may be used directly in a call to SendPacket().  The hopCount field is initialized to MAX_HOP_COUNT (15).

 

pNetPacket allocNetPacket(int prot, int src, int dest, char *p, int len)

 

where:   pNetPacket   is a returned pointer to a dynamically allocated NetPacket.

           prot             is the protocol identifier (ROUTING )

           src              is the source node address

           dest            is the destination node address

           p                is the payload

           len              is the payload length

 

If you allocated a NetPacket dynamically, you MUST release the NetPacket after has it been transmitted to a neighbor.  Use the following function:

 

void freeNetPacket(pNetPacket p)

 

where:   p is a pointer to a NetPacket allocated by allocNetPacket().

 

These two functions are provided as a convenience.  You are not required to use them.

 

 

2.2.Routing Layer Interface

 

If you use the framework, then your routing layer (routing.c) MUST provide these functions, and their signatures MUST be implemented as described.  If you use your own code, you MUST provide route() as specified, and you MUST provide a mechanism to update your routing tables when a link  state event occurs (EV_LINKSTATE).

 

2.2.1.  initRouting()

 

This function called when the node is rebooted.  You MUST register your handlers for routing and transport packets with the network layer here, and start any timers and initialize any data structures that the routing algorithm needs before packets are transmitted.

 

2.2.2.  route(int node, char * tPkt, int len)

 

The transport layer will call this function when it gets a message from the application layer.

 

Where:  node  is the address of the destination node.

            tPkt      is a pointer to a buffer containing the transport packet.

            len     is the length of the transport packet.

 

You must use your routing table to choose a first-hop node, then format a NetPacket with tPkt as the payload, and send it using sendPacket().

 

2.2.3.  takeLinkStateChange(int addr, int state)

 

where:     addr   is the address of the neighbor  node.

            state is 0 (zero) if the neighbor is down (has failed) or 1 (one) if the neighbor has recovered (is up).

 

The network layer (network,c) will call this function when a neighbor:

 

o  Has been discovered by the discovery protocol. It is at this point that the node address of the neighbor is known.  The routing layer should use this information to add the node to it's routing information.

 

o  Has failed or recovered.  The value of state is 0 (zero) if the neighbor is down (has failed) or 1 (one) if the neighbor has recovered (is up).

 

The routing layer MUST register two callback functions to handle routing and transport packets from the network layer.  The names of the functions are not fixed, but their signature is.  If you are using your own code, then you must provide a mechanism so that the routing function handles both routing and transport messages.

 

You register your callback functions with the network layer by calling:

 

void registerProtocol(int protocol, void (*handler)(int, NetPacket *))

 

       where:      protocol         is the protocol identifier (ROUTING or TRANSPORT)

                 handler    is a function be called when a NetPacket arrives for the protocol,

 

The handlers must implement the following interface:

 

void handler (int link, NetPacket *pkt)

 

where:   handler is the name of your handler.

           link       is link number on which the packet was received.

           pkt       is a pointer to a NetPacket.

 

The NetPacket contains the sending protocol, the source and destination node addresses, the packet hop count, a payload that is specific to the protocol, and the length of the payload.  The handlers should use this information to process the received payload.

 

If you use the framework code then you MUST insert the code to register your handlers in the initRouting() function (in routing.c).

 

 

2.3.Transport Interface

 

The transport.c file includes a handler for messages received from the application layer on remote nodes.  This function is defined as:

 

void upToTransport(int addr, char *p, int len);

 

where:   addr is the address of the node that sent this packet.

p is a pointer to the payload contained in the network packet.

           len is the length of the payload.

 

The routing function MUST use upToTransport() to pass transport packets addressed to the local node up to the transport layer.

 

2.4.LinkState Information

 

A complete set of link state information is provided for you to use in your routing procedures.  The LinkStateTable we developed in assignment 3 is initialized by the discovery protocol.  If you use the framework code, there are several procedures that you MUST use to obtain the cost metric for each of your neighbors (cost metric for nodes that are NOT connected to you must be learned from your routing update messages).

 

int getMetricByAddr(int addr)

int getMetricByLink(int link)

 

where   addr is the address of the neighbor whose metric you want.

           link is the link number of the neighbor whose metric you want.

 

The metric returned is the propagation delay for this link in milliseconds. It is stable in that it will not change after initial discovery, even if the link fails.

 

The LinkStateTable rtt value is no longer needed to express the up or down state of a neighbor.  You will reflect the up or down state of any node by setting the cost metric in your routing table to the value “INFINITY”, which is defined in routing.h as 999.  We guarantee that the cost metric you get from the LinkStateTable or compute from your distance vector algorithm will never be as large as this value.

 

The following functions may be of use to you, and you may use them if you wish.

 

int getLinkByAddr(int addr)

int getAddrByLink(int link)

 

where    addr is the address of the neighbor whose link number you know.

           link is the link number of the neighbor whose address  you know.

 

Both of these functions return a nonzero value (link or address), or -1 if the link or address input is not listed in the LinkStateTable.  If you get –1 as a return value, either you passed an incorrect value, or you executed these functions BEFORE discovery completed.

 

The following two functions, also defined in linkstate.c, may be used to determine if a given address is a neighbor or if the given address is a neighbor whose link to your node is up:

 

int isNeighbor(int addr)

int isNeighborUp(int addr)

 

              where  addr is the address of the node in question.

 

The function isNeighbor()  returns 1 (true) if the input address is a neighbor  or  0 (false) if the input address is not a neighbor  (regardless of the state of the link to that neighbor, and 0 (false) if the condition is false.

 

The function isNeighborUp()  returns 1 (true) if the input address is a neighbor  AND the link between you and the neighbor is up or  0 (false) if the input address is not a neighbor OR the link to that neighbor is down.

 

The discovery process will complete within the first 2 seconds of the simulation.

 

Your takeLinkStateChange() function will be called for each neighbor as it is discovered.  You may query the LinkStateTable for any neighbor that has been discovered.

 

 

2.5.   RIP

 

2.5.1.  Definition changes from RFC 1058:

 

2.5.1.1.  Wherever the term “IP Address” is used, substitute “cnet Node Address”.

2.5.1.2.  Wherever the term “UDP Datagram” or “Datagram” is used, substitute NetPacket.

 

Implement ALL of the items described in RFC 1058 EXCEPT as indicated in the following:

 

2.5.2.  Dealing with changes in topology (Section 2.1)

 

RIP asks that if a node fails to receive ANY update messages from a given neighbor in 180 seconds, then it should mark all routes through that neighbor as invalid.  We will not use this timer.  Instead, we will use the EV_LINKSTATE event, which is indicated by a call to takeLinkStateChange() (see 2.2 above) rather than the 180 second timer.

 

2.5.3.  Split horizon (Section 2.2.1)

 

You MUST implement split horizon with poisoned reverse.

The negative effect that  “poisoned reverse” has on a broadcast topology does not apply to our network, which is a network of point-to-point links.

 

2.5.4.  Triggered Updates (Section 2.2.2)

 

Since we are NOT using the 180-second timer to time out updates from neighbors, triggered updates will occur when the takeLinkStateChange function is called rather than when a time out occurs.  Note:  If you are not using the framework, then you MUST insure that you generate trigger messages when a link changes state.

 

2.5.5.  Message formats (Section 3.1)

 

2.5.5.1.  You may ignore the format specified in this section and define your own format.

 

2.5.5.2.  You MUST include definitions for the following items:

2.5.5.2.1.Node Address (Destination) (int)

2.5.5.2.2.Metric (int)

 

2.5.5.3.  You may include other information that you think is appropriate.

 

2.5.6.  Addressing considerations (Section 3.2  )

 

Ignore this section in its entirety.

 

2.5.7.  Timers (Section 3.3 )

 

2.5.7.1.  The 30 second “update timer” is required.  You need ONE of these timers for each neighbor.

2.5.7.1.1.Send an update message to each of your neighbors when the timer expires.

2.5.7.1.2.Implement the second option “addition of a small random time” to prevent synchronization.

 

2.5.7.2.  Do NOT implement the “timeout” timer.

 

2.5.7.3.  DO implement the “garbage-collection timer”.

 

This timer is set when a route is invalidated (metric set to INFINITY).  You need to associate a garbage-collection timer with the route that has been invalidated.  If the route is re-established before the timer expires, you MUST stop the timer.  If the timer expires, remove the route from the routing table.

 

2.5.8.  Input processing (Section 3.4)

2.5.8.1.  Ignore reference to UDP port 520.

2.5.8.2.  Ignore Version number checking.

 

2.5.9.  Request (Section 3.4.1)

 

We do not support “Request”. Ignore this section.

 

2.5.10.  Response (Section 3.4.2)

2.5.10.1.  Ignore checks for “Address family”

2.5.10.2.  Ignore tests for valid address format and broadcast address.

2.5.10.3.  All octets (4) of the address field are valid.

2.5.10.4.  When the term “network” is used, substitute “Node”

2.5.10.5.  “Gateway” here means the node from which the message arrived.

2.5.10.6.  Do not start the time-out timer.

2.5.10.7.  “deletion” timer means “garbage-collection timer”

2.5.10.8.  If there is no change in a route, do nothing.

 

2.5.11.  Output Processing (Section 3.5)

2.5.11.1.  Ignore processing of “request”

2.5.11.2.  Ignore references to broadcast: we support only point-to-point toplogy

2.5.11.3.  DO NOT implement the triggered update delay timer.

2.5.11.4.  Ignore discussion related to “input processing” – we don’t do that.

2.5.11.5.  Ignore references to subnets

2.5.11.6.  Observe the 512 octet “datagram” size limitation.

2.5.11.7.  Ignore reference to version number.

 

2.5.12. Compatibility (Section 3.6)

 

Ignore this section.

 

2.5.13. Control Functions

 

Ignore this section.

 

 

 

2.6.  Error Free Transmission

 

You may assume a completely reliable link layer.  That is, IF a link is up, then a transmitted packet will be delivered to the remote node without error.

 

 

 

3.Operation.

 

The routing function must also handle incoming transport packets received by the network layer to decide if the packet is destined for the local transport layer or the transport layer on another node.  If the transport layer is “local”, then it will call the upToTransport() function in the transport layer.  If the packet is addressed to another node, then the routing function must choose the correct neighbor to which to forward the packet, and send it.

 

If you use the framework, a network packet is defined for you in network.h, as is the maximum hop count.   If you use your own code, then you must implement a hop count and maintain it as described here. Before any packet is forwarded, the routing function must decrement the hop count.  If a hop count is decremented to zero, then the packet is dropped.   Additional details are provided in section 2.

 

Note:  When you first create a network packet to send a new message (routing or transport), the hop count MUST be set to MAX_HOP_COUNT (15) but not decremented when first transmitted.  The decrement operation occurs ONLY when a packet is forwarded.

 

Since the routing layer must handle two types of packets: routing update messages from neighbors, and transport packets received from a neighbor, the routing function “registers” handlers for both routing and transport packets with the network layer. The interface “up” to the transport layer is defined as upToTransport() in transport.c.  You will not have to touch transport.c.

 

NOTE:  If you use your own code, you MUST use the transport.c supplied in the framework WITHOUT modification.

 

 

3.1.  Links to neighbors are identified by their cnet link numbers (1 through n) where n is given by nodeinfo.nlinks.

3.2.  Nodes (that is, neighbors) must be identified by the address given by nodeinfo.address.  Remember that neighbors are defined as our immediately adjacent nodes.  The number of neighbors at node n is equal to the number of links configured at node n.

3.3.  Link costs (metric) are computed from the cost metrics in the LinkStateTable (see 2.4).

3.4.  The hop count between neighbors is 1, that is, a packet with hop count of 1 that is  sent to a neighbor cannot be forwarded by that neighbor.

3.5.  The physical links will not drop or corrupt packets.

3.6.   The cost metrics in LinkStateTable never change following discovery, even if links fail and recover.

3.7.  Nodes will not fail following initial reboot sequence.

3.8.  Links can and will fail.

3.9.  Print a message whenever a message is routed.  The message format should be:

 

<time>  Node <addr1>  ROUTE TO <addr2> on Link <link>: cost = <metric>

 

Where:  <time>     is the current time at node <addr1> in msec (NOT usec!)

           <addr1>       is the cnet address of the node reporting making the routing decision.

           <addr2>       is the cnet address of the node for which the message is intended.

           <link>          is the link number on which the message will be sent.

           <metric>  is the current metric of the chosen route to <addr2>.

 

If there is NO ROUTE available, then print the message:

 

<time>  Node <addr1>  NO ROUTE to <addr2>.

 

If the hop count is decremented to zero, then print the message:

 

<time>  Node <addr1>  Packet for  <addr2> reaches maximum hop count

 

and discard the packet.

 

 

3.10. All “normal” output should be written to STDERR (use fprintf).  You may include conditionally compiled debug output that you write to stdout ONLY if the symbol DEBUG is defined.  For example,

 

#ifdef DEBUG

fprintf(stdout, “this is my debug message\n”);

#endif

 

This way both you and I can enable or disable your debug output by merely adding (or not)

“-DDEBUG” to the compilation string in the topology file.

 

Please use fprintf(stdout, ….) rather than printf(….) for debugging output.

 

4.Project Source Code

 

The source code that you SHOULD use is here.  The file is a WinZip file.  For further information, please read the README file and the source code, particularly the network and routing header files.

 

I used the word “SHOULD” here rather than MUST.  You are permitted to use your own code rather than thee framework code, provide you meet every performance and operational requirement of this spec, AND that you use the transport.c from the framework without modification.

 

If you do use the framework, then you are required to submit source code in the files routing.c, routing.h, or any NEW files that you wish to code.  I will test your program using EXACTLY the same code as I’ve supplied to you here, with the addition of your routing files and new files.

 

Since you have the source code to the entire “stack” you are certainly free to put in debugging code wherever you wish during your test and development, but you MUST make certain that your code works correctly with the framework as supplied before you submit.

 

Of course, if you find bugs in the framework code please send email to the class list immediately, describing the bug and any proposed solution you might have developed.

 

 

Note that these files have been edited on a Unix system so you should not see extra characters at the ends of each line.

 

 

5.What to Submit.

 

5.1   Your name that you used to register for this course, and your student ID

5.2   An email address to which I can send your grade and program evaluation.

5.3   Your source files

5.4   A file named COMPILE that contains the EXACT cnet compile string required to compile and link  your program.  I will insert this string into the test topology files.  If your string is wrong, or the referenced files are not present, I will deduct a point for every mistake that I have to fix to get your program to run.

5.5   A text file that describes any requirements that you have not implemented or known bugs in your program.  For example, if you did not or cannot implement split horizon with poisoned reverse, say so.

 

You MUST send this to me in a ZIP file. You MAY password-protect the ZIP file in the way we described earlier in the semester if you are concerned about security.

 

 

6.  How I will evaluate your program

 

I will grade your program solely on correctness.  That is,  there is no advantage or disadvantage to using the framework or your own code.  During each of the following tests, the application layer at each node will generate messages at an average rate of one message very 30 seconds.

 

6.1  Calculation of correct routes in static environment, no loops.  This test includes observations of the number of messages exchanged to reach convergence.  Please don't ask me how many messages that is.  The number of messages is based on the topology.  I will also not provide sample output from a correct implementation, so it is up to you to prove that you have implemented the algorithm correctly (20 Points).

 

I will generate a topology with no loops and no link failures.  Your program should always route messages along the least cost path.

 

6.2   Calculation of correct routes in static environment, with loops (5 Points)

 

I will generate a topology with at least one loop and no link failures.  Your program should always route messages along the least cost path and use split horizon with poisoned reverse to prevent count to infinity.

 

6.3   Calculation of correct routes in dynamic environment (10 points)

 

I will add link failure to the topology we used in both 6.1 and 6.2. and check that your program updates routes and that the routing tables converge when links become stable (either stay down or stay up).  Note: if you failed 6.2 (loops) you will not be penalized twice in this test.  You can still earn 10 points in this section.

 

Finally, I will read every source file that you submit.  I will try to return an evaluation of your project with your grade and I will include any comments about program structure/style when I think they can be improved.  It helps me if you provide a reasonable level of comment in your code.