Data Communications and Networks



Assignment 3 -  Neighbor Discovery (25 points)

Due Date:  November 13, 2003 Before 6:00 PM


Revision 1:   October 23, 2003

Revision 2:   October 24, 2003

·      Made definition of “neighbor” more precise.

·      Added permission to use supplied code to trace link state events (see 3 g).

Revision 3:   October 28, 2003

·      Correct name of function in 2.4d to getLinkState()

Revision 4:   October 30, 2003

·      Added link to topology file

·      Eliminated allowed use of  CnetLinkinfo.propagationdelay.

Revison 5:    October 31, 2003

·      Explain in more detail how the required functions are to be used.

Revison 6:    November 2, 2003

·      Define how to handle EV_LINKDOWN error on CNET_write_physical_reliable.

Revison 76:   November 8, 2003

·      Change time requirement for initial discovery from 5 to 10 seconds.

·      Replace topology file



1.  Overview.


One of the functions that concern the network layer in a packet switching system is the problem of neighbor discovery (also known as neighbor reachability).  At startup, a node needs to discover which node, if any, is at the other end of each of its links.  As time passes, the node also needs to keep track of which of its neighbors still exist, and whether any new nodes have joined the neighborhood.


Your task is to develop a simple protocol that allows each node to discover who its neighbors are at the end of each link.   Your protocol must also keep track of the 'reachability" of each node by periodically making sure that links to each of your neighbors are "up". 


Since the information you develop will be used by other protocols (namely, routing protocols), you should also maintain an average round trip time value for each of your neighbors.  You can consolidate your list of neighbors, their status (reachable/not reachable) and the average rtt in a single table.


 This "discovery protocol" must run concurrently with other protocols over the same links.  This means that you will need to identify the protocol in your network level packets.




2.  Specification.


Your system will be composed of four layers, as follows:


·  application

·  network

·  link

·  physical


The application and physical layers are provided by cnet.  You will write the link and network layers.




2.1  Network Layer Interface.


You must provide two interface functions that will be used by the application layer to send messages to the network, and by the link layer to pass messages received from the physical layer up to the network layer.


The application layer will use the following function to send application messages:


void downToNetwork(CnetEvent ev, CnetTimer timer, CnetData data)


You must tell cnet to call downToNetwork when you set your EV_APPLICATIONREADY event handler.



Your link layer must call the following function when it receives a frame from the physical layer:


void upToNetwork(int link, char *packet, int length)


     When upToNetwork() is called, it must process the received packet by calling the appropriate protocol service function (see section 2.2)




2.2  Multiple Protocol Support.


The discovery process is but one function of the network layer.  In a future project, you will be asked to add a routing function to your network layer that must run concurrently with the discovery layer.  To meet this requirement, your network packet must contain a protocol identifier, and your upToNetwork() function must distribute each packet received from the link layer to the appropriate protocol.


You can assign integer protocol identifiers as follows:


Discovery    1

Routing       2

Transport     3


Protocol values will not exceed 127.


The idea here is that when your upToNetworkLayer() function is called, it will have to decide, based upon the value in the protocol field of the network packet, which protocol service function to call.


There are two basic ways to do this:


(1)  Define a specific interface for each protocol and hard code it into the network layer.  For example, the network layer could assume the existence of three (external) functions: doDiscovery(), doRouting(), and doTransport() (of course, passing the packet and other appropriate information to each of these “hard coded” functions).


Initially, the functions doRouting() and doTransport() will be empty (stub) functions.  You should create these functions as place holders for future code.

Since all three of these functions must process a received network packet, they should take the network packet payload as input argument.  That is:


void doDiscovery(char *data)

void doRouting(char *data)

void doTransport(char *data)


Where data is a pointer to the received packet data.


It would be good programming practice if you defined these functions in separate files.  Can you tell me why?


(2)  Provide for call back registration.  This technique requires that the network layer provide a “register service” function that takes two arguments: a protocol number and a pointer to a function.   The passed function pointer is the function that would be called by network layer when a packet is received for the indicated protocol number.


This is harder to do, and is not necessary for this project, although it is the way that it would be done in practice.  If you do want to follow this approach, then define a structure as follows:


struct dispatchTable {

    void (* discovery) (char *);

    void (* routing) (char *);

    void (* transport) (char *);

 } services;


               To provide for  protocol handler registration, define the following function:


void registerProtocol(int protocol, void (*handler)(char *)) {


    switch (protocol) {

        case Discovery:

            services.discovery = handler;


        case Routing:

            services.routing = handler;


        case Transport:

            services.transport = handler;



            fprintf(stderr, "invalid protocol identifier: %d\n", protocol);







           To register a function named myDiscoveryhandler as the handler for discovery protocol packets, execute


              registerProtocol(Discovery, myDiscoveryHandler);



           To call the discovery protocol handler and pass a buffer (char *) named data, execute:





         The routing and transport services are similarly dispatched.


         If you don’t understand this code, you SHOULD, so get a copy of K&R and read about function pointers.



2.3  Error Free Transmission


You may assume a completely reliable link layer, therefore you do not need to implement network layer error detection.  That is, IF a link is up, then a transmitted packet will be delivered to the remote node without error.




2.4  Discovery Protocol Operation.


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


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


c.  Round trip times (rtt) are expressed in milliseconds.  The maximum value for any rtt is 106 – 1 (999,999 msec).   The minimum value is 1.  A value of zero (0) is considered “infinite”.  This value of “infinity” may be used in the link state table structure as an indicator of the up or down state of the link.


d.    Provide a function getLinkState() that returns  the link state table by value


LinkStateTable getLinkState()


e.     Print a message whenever a link state changes.  The message format should be:


Node <addr1>: Link <link> to <addr2> <up/down> at <time>: RTT = <rtt>


Where:  <addr1>       is the cnet address of the node reporting the link state change.

           <link>          is the affected link number.

           <addr2>       is the cnet address of the node whose link has changed state.

           <up/down>   is either the text “up” or “down” refelecting the link’s state.

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

           <rtt>            is the current value of this link’s average round trip time.


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


#ifdef DEBUG

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



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.



2.5  Link State Table.


You should maintain a Link State Table that contains an entry for each link.  The fields in each entry are:


typedef struct {

CnetUint32 linkno;   /* cnet link number */

CnetUint32  address; /* cnet address */

CnetUint32 rtt;     /* average round trip time in msec */

} LinkStateEntry, *pLinkStateEntry;



The link state table should be defined as follows:


typedef struct {

CnetUint32 nlinks;            /* from nodeinfo.nlinks */

LinkStateEntry states[MAXLINKS]; /* order by link number-1 */

} LinkStateTable; *pLinkStateTable;


Where MAXLINKS is the maximum number of neighbors that can exist for any node.  For this project define MAXLINKS as 16 (please use a symbolic definition!).




2.6  Link Layer Interface.


You must provide two interface functions that will be used by the network layer to send messages to the node on the specified link and by the physical layer to pass frames received by the physical layer up to the link layer.


When the the network layer has a packet to send,  it will call the following function:


void downToLink(int link, char *packet, int length)




link   is the outbound link to which the packet must be written

packet is a buffer that contains the network packet

length is the size of the buffer (that is, the numjber of bytes in the packet)


You will write the downToLink function as part of your link layer.  When downToLink Lyaer is called, it will add (if necessary) a link level header to the network data and use the cnet function CNET_write_physical_reliable to send the frame over the specified link.


You must use the following code to write frames to the physical layer in your downToLink() function:


/* write Frame to on target link */

result = CNET_write_physical_reliable(link, frame, &len);

if (result == -1) {

   if (cnet_errno == ER_LINKDOWN)



     CNET_perror("on CNET_write_physical_reliable");




len   is an int containing the length of the data in the buffer.

frame is the buffer (char *) holding the data to write.


You may use your own variables here - I just want you to implement the exact same error checking

logic that is specified.


 This code is designed so that we ignore ER_LINKDOWN errors, thereby simulating what happens in practical situations wherein we cannot determine that a link is down by simply writing to it.  More realistically, we determine that a link (or remote node) has failed because we fail to get responses (or ACKs) to messages that we transmit on the link.  This is how we want our simulation to work.




The  physical layer will call the following function when it receives a frame over a link:


void upToLink(CnetEvent event, CnetTimer timer, CnetData data)


You must tell cnet to call upToLink when you set your EV_PHYSICALREADY event handler.




3.  Performance Requirements


a.  The physical links will not drop or corrupt packets, so your link layer can use the cnet function CNET_write_physical_reliable().


b.    Nodes will not fail following initial reboot sequence.


c.    Links can and will fail.


d.    Your protocol must develop a complete list of all of its neighbors within 10 seconds the reboot_node event.


e.    Your protocol must detect a failed or recovered link within 15 seconds of link state change.


f.     You may NOT reference ANY fields in the CnetLinkinfo structure other than:





g.    You may use the supplied code to trace the actual link state changes (fail/recover). Instructions and the code are here.


h.    Separate your code by layer and structure.


·      Link layer (linklayer.c)

·      Network protocol switching and packet generation (network.c)

·      Discovery protocol (discovery.c)

·      Linkstate data definitions (linkstate.h)

·      Link layer data definitions (link.h)

·      Network layer data definitions (network.h)


         This requirement is asking you to follow good practice in design and modularization:


Separate data definitions from code

Separate code into functional modules.


In a future project we will ask you to add a routing protocol to your existing code a WITHOUT any changes to the existing source code in your link layer or routing protocol, existing data structures, or the function upToNetwork.  We do expect that code will be added to downToNetwork to handle application data.


i.  Make certain that you provide descriptive comments that describe each function, structure, and variable.




4.  How to Test.


We will supply you with a SAMPLE topology file that you may use as a basis for testing.  But, be warned that if the only testing that you do is to run with just this topology, you run the risk that you may not test all of the requirements of the assignment.  I suggest that you methodically vary the parameters in the topology file and verify that your program handles the new topology and run-time conditions correctly.


Make certain that you vary things like:

·      Propagation delay on different nodes

·      Which links fail (linkmtbf)

·      How long links are down (linkmttr)

·      Number of neighbors at a node (make sure you test MAXLINKS)

·      Node Address (not the same as link number!)



      The topology file for testing is DSCVRYTEST


It is part of this assignment for you to figure out how to thoroughly test your protocol.




5.  What to Submit.


·  A text file named README that lists the names of the files in your program.  Include your name and ID in the README file.


·  A text file named METHOD that describes your discovery protocol.  Please be thorough. Include your name and ID in the METHOD file.


·  Your source files.




6.  How we will evaluate your program


Your program will be graded against the following criteria:


6.1  Program Structure  (10 Points)


We will assess how well you separated data and code, and how well you isolated functions by layer.  The key criteria that should guide you is the layering principle.  The code and data between layers must be isolated to the point that only an interface (service functions) and data specifications (input/output formats supported by the service functions) are required for layers to communicate. We will also assess your method of support for multiple network protocols.  (8 points)


We will judge how well your comments describe the associated section of code.  As a guide, presume that you are writing the code to send to someone who has to understand everything about the code and the algorithm you used to implement discovery without the need to ever speak to you. (2 points)



6.2  Performance      (15 Points)


We will verify that your program satisfies all of the performance and functional requirements in this specification, including:


·      Efficiency of discovery algorithm (3 points)

o     number of messages exchanged to detect correct state

o     size of messages

·      Correctness of discovery algorithm (3 points)

·      Correctness of RTT calculation (3 points)

·      Correctness of Link State information (3 points)

·      Timeliness of link state change detection. (3 points)


If you violate 3(f) we will automatically deduct 5 points.