COMP/ELEC 429/556 Project 3: Intra-Domain Routing Protocols for Bisco GSR9999
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
COMP/ELEC 429/556 Project 3: Intra-Domain Routing Protocols for Bisco GSR9999
Assigned: Tue, 8 March
Due: 11:55pm, Thu, 7 April
1 Introduction
You have just joined Bisco Systems, a networking equipment company, as a Design Engineer. Your first project is to design and implement intradomain routing protocols for Bisco’s upcoming product, the GSR9999 router.
In particular, you are required to design and implement a variant of the distance vector routing protocol (DV). Senior engineers (those enrolled in COMP/ELEC 556) are also required to design and implement a variant of the link-state routing protocol (LS). Junior engineers (those enrolled in COMP/ELEC 429) are encouraged to design and implement LS for extra credit. The functional specifications of the DV and LS protocols are provided (see Section 4 and 5) and your implementation must follow these specifications. You are also given the GSR9999’s system interfaces (see Section 2) which you must use to implement the routing protocols.
You will implement your designs in a GSR9999 simulator. The simulator essentially provides the GSR9999 system interfaces as described in Section 2. The simulator is written in C++, so you should use C++ for your implementation. You may use any C++ library. Details on the simulator is given in Section 7.
Note that the routing protocols you are going to implement and the network model in this project are simplified. The DV and LS protocols have only a limited set of features. Every node in the network is assumed to be a router and is identified by a unique ID. No hierarchical addressing is used. Each node has a number of ports, which may or may not be connected to a neighbor router. Figure 1 illustrates a simple network example.
The source code of the simulator and some input/output files for testing purpose are available from http://www.clear.rice.edu/comp429/projects/project3/project3.tar. To ex- tract the individual files from the archive, run tar xf project3.tar.
The expected simulator output for 2 trivial scenarios for the DV protocol is provided (see simpletest*). You may want to begin by implementing the DV protocol first. No expected sim- ulator output for the LS protocol is provided.
The majority of the provided source code is for the simulator and you do not need to study this code. To complete this project, you only need to understand how to use the simulator to run tests, how to invoke the GSR9999 system interfaces defined in Node.h, how to extend the
p1
p2
p0 n3
p0
n1 p3
p2 p1
p0
n0
p1
n2 p0
p1
Figure 1: Simple network example. RoutingProtocolImpl.[h,cc] files to implement your routing software, and use the constants
already defined in global.h. In summary, the code files you need to look at are:
• Node.h for the GSR9999 system interfaces
• global.h for the defined constants that you must use
• RoutingProtocolImpl.[h,cc]where you should begin your implementation
The RoutingProtocolImpl C++ class in the provided code is the abstract interface for your routing protocol software. It defines the set of interfaces that your routing protocol software must handle (i.e. init(), handle alarm(), recv(), just like the specification in Section 2). You will implement these interfaces as well as the functions of the DV and LS protocols.
Your implementation code must be contained in the files RoutingProtocolImpl.h, RoutingProtocol- Impl.cc, and additional files of your own creation. Other than RoutingProtocolImpl.[h,cc] and the Make- file, you are not allowed to modify any other parts of the provided code. In fact, during grading, any changes that you make to the other provided code files will be completely ignored. Your implementation must also compile with no warning on a CLEAR machine based on the given Makefile.
Grading: Here is how various aspects of your project will contribute to your total grade:
• Conformancetospecifications(35pointsforDV,7pointsforLS).Correctnessofmessageformats,
message contents, message timing, etc.
• Behavioral correctness (35 points for DV, 7 points for LS). Correctness of DV/LS update handling, link status detection, route computation, and packet forwarding, etc.
• Robustness (10 points for DV, 6 points for LS). Able to handle topologies of varying sizes, lack of memory leakage/hogging, simulator crash, etc. To check for memory leakage, if you run the simulator, then run the tool top, you should be able to see the memory usage of your simulator process. If the simulator’s memory usage keeps increasing, then you almost surely have a memory leak or have implemented something wrong.
• Testing strategy (15 points). You should include a test.txt file with your submission to de- scribe your testing strategy (both at the component level and at the system level) and provide test cases that you have developed to convince yourself that your routing protocols are working properly.
• Style (5 points). Lack of compilation warnings on CLEAR based on the given Makefile, appropri- ate division of functions, appropriate organization of code into files, documentation/commenting of source code, appropriate use of data structures, etc.
Working in groups: You may work in groups of up to four students. If you have trouble finding partners, please contact the instructor.
Submission: Put your source code files, the test.txt file, test case files, and a README file that specifies the names of the students in your group and anything else you want the TAs to know about your project under a single directory such as project3/. Submit a tar archive file of this directory (e.g. created by running tar cf project3.tar project3) to Canvas by 11:55pm on the due date.
2 Bisco GSR9999 System Interfaces
You can assume that the GSR9999 operating system has only a single thread of execution for all running software. That is, a function call to your routing protocol software will be executed without interruption by the system. Everything happens sequentially on a router. This assumption will greatly reduce the complexity of any code you write. An implication of this is that any pending alarm will be set off only after a function call is completed and control has been returned to the operating system. You can assume your functions will take negligible amount of time to execute, so the impact on the timing of scheduled alarm is negligible.
2.1 Initialization
On bootup, the system will initialize your routing software by calling your init() function with the fol- lowing information:
• Number of ports
• Your router ID
• Routing protocol used (P DV or P LS)
Note that ports on each router are numerically identified and can range from 0 to 216 − 2. 216 − 1 or 0xffff is treated as a special value as explained below. Router ID can range from 0 to 216 − 1.
2.2 System Call Interfaces
The following system calls are provided by the GSR9999 system.
•
set alarm(this, duration, *d) - Set an alarm. You specify an amount of time (with the parameter duration, in milliseconds) that the system should wait before setting off an alarm. When an alarm is set off, your handle alarm() function will be invoked (see Section 2.3). d is a pointer to a piece of arbitrary data that is associated with the alarm, it is passed to your handle alarm() function so that you can use d to figure out what the alarm is meant for. “this” is a reference to the router itself. Multiple alarms can be set.
When setting an alarm using set alarm(), you can pass a piece of memory “data” to the system. This data memory should not be freed or modified by your code until the corresponding alarm has been delivered via “handle alarm()”, and the control over the data memory has been returned to you.
send(p, *pkt, s) - Send a packet pkt of size s bytes out on the port number p. send() in the GSR9999 always completely send the entire packet of s bytes as a single packet. Note that this behavior is unlike the Linux socket send().
On sending a packet, the memory storing the packet is “owned” by the underlying system, so you should not free or modify a packet’s memory after passing it to send(). This also implies that packet memory must be dynamically allocated. On the other hand, on receiving a packet, once your recv() function is called, the packet memory is owned by your routing software, so it is your routing software’s duty to free packet memory after a receive if the packet memory is no longer needed.
time() - Return the current time of the system in milliseconds since bootup.
Handler Interfaces You Must Implement
init(num ports, router id, protocol type) - This function is called to pass configuration parameters to your routing protocol, including the total number of ports on this router, the ID of this router, and the protocol type (P DV or P LS) to be used. Suppose num ports is 5, then the ports are numerically identified by IDs 0, 1, 2, 3, 4.
handle alarm(*d) - When an alarm is set off, the system will call your handle alarm() function. Your function should inspect the associated data pointer d to determine the correct course of ac- tion.
recv(p, *pkt, s) - When a packet pkt of size s arrives via port number p, your recv() function is called. Your function should inspect the content of pkt to determine the correct course of action. recv() in the GSR9999 always receive a whole packet as sent by the origin. Note that this behavior is unlike the Linux socket recv().
When a DATA packet is originating at a router (the DATA packet will be created by the simulator’s xmit event), it will be received by your RoutingProtocolImpl’s recv() function with a special incoming port number of 0xffff. This indicates that the DATA packet is originating locally rather than received from a neighbor.
When a DATA packet has been received by its destination, the packet memory should be freed.
•
2.3
•
•
•
•
2.4 General Packet Format
Figure 2: General packet format.
Figure 2 illustrates the general packet format that you must use. Network byte order is Big Endian. So you must use byte order conversion functions (e.g. htons() and ntohs()) to transmit all numeric values with the proper byte ordering. Packet type is an 8 bit number corresponding to the 5 packet types defined below. The Reserved section is unused. Size is the size of the entire packet in number of bytes. You may assume that the content needed to be carried by a protocol message never exceeds 216 − 1 bytes. That is, the simulated network will never be so big that your protocol message does not fit inside a single packet. Source ID is the node that generated the packet. Destination ID is the node that the packet is destined to.
2.5 Packet Type
There are five packet types in the system:
3
• DATA - Regular data packet that needs to be forwarded by a router.
• PING - A packet sent only to an immediate neighbor.
• PONG - A packet sent immediately in response to a PING packet to a neighbor. This allows you to detect the existence of a neighbor as well as measure the round-trip delay (i.e. link cost).
• DV - A distance vector routing update packet.
• LS - A link-state routing update packet.
Neighbor Status Detection
You will use the PING and PONG packet types to periodically check the status of a port and discover whether a neighbor exists and if so the neighbor’s ID and the round-trip delay to the neighbor. The checks should be performed on every port once every 10 seconds. PING and PONG packets have a 32bit payload, which stores the time (as returned by time()) when the PING packet was sent. A PING
Figure 3: DV update packet format.
packet’s destination ID is unused; a router uses the corresponding PONG packet’s source ID to discover the ID of its current neighbor.
To determine port status using PING/PONG, you must use an embedded timestamp in the PING/PONG messages and use the following procedures. When a router generates a PING packet, it must store the current time in the PING message payload, then sends the PING message to a neighbor with the correct source ID (the destination ID is unused in the PING packet). When the neighbor router receives the PING message, it must update the received message’s type to PONG, copy the source ID to the destination ID, update the source ID to its own, then send the resulting PONG message (with the original timestamp still in the payload) immediately back to the neighbor. When the PONG message is received, the timestamp in the message is compared to the current time to compute the RTT. This is in fact how the ping tool measures RTT.
Since PING messages are generated every 10 seconds, a port’s status is refreshed by PONG messages approximately once every 10 seconds. A link should be declared dead when the status has not been refreshed for 15 seconds. The port status should be properly changed within 1 second of the expiration. That is, if you implement a 1-second periodic check on all the state’s freshness, that’s sufficient.
4 Specifications of the DV Protocol 4.1 DV Routing Update Packet Format
See Figure 3. You must construct your DV routing update messages according to this format.
4.2 Behavioral Specifications
You must implement the following features:
• You must implement the poison reverse variant of distance vector protocol. • The cost to reach a node is the round-trip delay (in ms) to reach that node.
5 5.1
Figure 4: LS update packet format.
• DV periodic updates are sent every 30 seconds.
• DV entry that is not refreshed within 45 seconds are timed out and removed. You should remove the expired state within 1 second of the expiration time. That is, if you implement a 1-second periodic check on all the state’s freshness, that’s sufficient.
• DV triggered updates are sent as soon as a local DV change occurs.
• Your DV protocol should update the forwarding table to always reflect the current known best
paths.
Specifications of the LS Protocol LS Routing Update Packet Format
See Figure 4. You must construct your LS routing update messages according to this format.
5.2 Behavioral Specifications
You must implement the following features:
• You must implement flooding of LS update packets.
• You must use sequence number to correctly implement flooding of LS update.
• You do not need to implement reliable flooding. That is, you do not need to send acknowledgement or retransmission for LS update packets.
• The link cost is the round-trip delay (in ms) of a link.
• LS periodic updates are sent every 30 seconds.
• LS entry that is not refreshed within 45 seconds are timed out. You should remove the expired state within 1 second of the expiration time. That is, if you implement a 1-second periodic check on all the state’s freshness, that’s sufficient.
• LS triggered updates are sent as soon as a neighbor status change is detected.
• The Dijkstra’s algorithm must be used to compute the correct shortest paths based on the most
current link-state knowledge.
• Your LS protocol should update the forwarding table to always reflect the most current computed shortest paths.
6
Your design must address the technical issues described below. Note that this is certainly not meant to
Design Issues
be an exhaustive list of issues. These issues are provided to help stimulate and organize your thoughts.
Common System Design Issues - Below are design issues that are common to both DV and LS routing protocols.
• Router ID - At bootup time, your routing software is initialized with a unique 16-bit identifier of the router. This ID does not change over time. So your design needs to remember this system configuration.
• Routing Protocol Selection - At bootup time, your routing software is initialized with the routing protocol that should be used in the system (either P DV or P LS). Once initialized, this configura- tion does not change over time. So your design needs to remember this system configuration.
• Port Status Data Structure - At bootup time, your routing software is initialized with the total number of ports on the router. The total number of ports does not change over time. A port may be connected to a neighbor router separated by a non-zero, positive round-trip delay, or may be unconnected. A neighbor router is uniquely identified by its 16-bit identifier, the round-trip delay to a neighbor router is used as the link cost in your routing protocols. Therefore, you need a suitable data structure for maintaining such port status information.
• Port Status Monitoring - In the GSR9999 router, port status information (i.e. neighbor router ID and link round-trip delay, if connected) must be detected dynamically by software. You need a port status detection algorithm that attempts to test port status once every 10 seconds and updates the port status data structure accordingly. You need to use the PING and PONG packet types and the time() and set alarm() system calls specified in Section 2 to periodically learn the neighbor router ID and measure the round-trip delay. You need to decide (1) how to generate PING packets peri- odically, (2) how to construct PING packets, (3) how PING packets are processed when received, (4) how PONG packets are processed when received.
• Forwarding Table Data Structure - You need a suitable data structure for maintaining the forward- ing table. Note that at bootup time, a router in the network does not know exactly how many
routers are in the network. The number of routers in the network can also change dynamically. Your data structure must support insertion and deletion of forwarding table entries. This forward- ing table structure should be generic such that it can be used by your packet forwarding function no matter which routing protocols (DV or LS) is being used.
• Packet Forwarding - You need to decide how to handle the forwarding of regular DATA packets. DV Protocol Design Issues - See Section 4 for the specification of the protocol you need to implement.
Below are a set of issues you must address.
• Distance Vector Data Structure - You need a suitable data structure for maintaining the distance vector at a router. Note that an entry in the distance vector must be refreshed periodically or else it must be removed after a timeout. Your data structure should support dynamic insertion and deletion.
• Distance Vector Entry Freshness Check - You need to decide how you will implement a periodic check of the freshness of the distance vector entries.
• Direct Neighbors Maintenance - You need to decide how to insert, delete, and refresh direct neigh- bors of a router in the distance vector structure.
• DV Announcement - You need to decide how to send DV routing update packets.
• DV Routing Update Packet Construction - You need to decide how a DV routing update packet
can be constructed. Your protocol should implement the poison reverse DV variant.
Link cost (i.e. round-trip time) should be represented in unit of milliseconds in routing update
messages as an unsigned short.
The DV update packet should contain as few entries as possible. That is, if a destination D is not reachable from router N, then router N’s DV update packets should not include an entry for D. As a result, the size of the DV updates is minimized, and the withdrawal of a route is implicit. In other words, you should not have (ID, INFINITY COST) pairs in your DV update packets except when it’s for implementing poison reverse.
• DV Packet processing - You need to decide how to process DV routing update packets and update the distance vector data structure.
• Forwarding Table Maintenance - You need to decide how to update the forwarding table based on information in the distance vector data structure.
• DV update packets are generated periodically every 30 seconds. Triggered updates should be considered as additional updates separate from the periodic updates. That is, triggered updates should not affect the schedule of the normal 30 second periodic updates. For example, suppose periodic updates are sent at time 0, 30, 60, 90, 120... etc. Even if a triggered update occurs at time 42, the regular updates should still occur at time 60, 90, 120, etc and not be interrupted.
LS Protocol Design Issues - See Section 5 for the specification of the protocol you need to implement. Below are a set of issues you must address.
7
• Link-state data structure - You need a suitable data structure for storing link-state information col- lected from other routers in the network. Note that link-state information must be periodically refreshed or else it is removed after a timeout. Your data structure should support dynamic in- sertion and deletion. This link-state information will also be used by the Dijkstra’s algorithm for computing shortest paths.
• Link-state Entry Freshness Check - You need to decide how you will implement a periodic check of the freshness of the link-state entries.
• LS Announcement - You need to decide how to generate LS routing update packets.
• LS routing Update Packet Construction - You need to decide how to construct a LS routing update
packet.
Link cost (i.e. round-trip time) should be represented in unit of milliseconds in routing update
messages as an unsigned short.
The LS update packet should also be as small as possible. You should never have (ID, INFIN-
ITY COST) pairs in your LS update packets.
• LS Packet processing - You need to decide how to process LS routing update packets and update the link-state data structure.
• Forwarding Table Maintenance - You need to decide how to update the forwarding table based on information in the link-state data structure and the Dijkstra’s shortest path algorithm.
• LS update packets are generated periodically every 30 seconds. Triggered updates should be con- sidered as additional updates separate from the periodic updates. That is, triggered updates should not affect the schedule of the normal 30 second periodic updates. For example, suppose periodic updates are sent at time 0, 30, 60, 90, 120... etc. Even if a triggered update occurs at time 42, the regular updates should still occur at time 60, 90, 120, etc and not be interrupted.
The Simulator
Get the simulator at http://www.clear.rice.edu/comp429/projects/project3/project3.tar. After you compile the code using the provided Makefile, you will have the executable Simulator,
with the RoutingProtocolImpl object included in the executable. When you add additional files,
you will need to update the Makefile accordingly to include them.
The simulator executable can be run as follows: SimulatorconfigfileDV|LS. The config file specifies the topology of the simulated network and certain network events, it is ex- plained in Section 7.1. The DV|LS switch is used to indicate whether the simulator should use the DV protocol or the LS protocol.
7.1 Configuration File
See the configuration files simpletest{1,2} include in the code as examples. A configuration file contains 3 sections. The first section is [nodes], which simply lists the IDs of the routers/nodes in the
network. The second is the [links] section, where each link in the network is specified. For example, (1,2) delay 0.010 prob 0.0 means that a link exists between routers 1 and 2, the delay is 0.010 second (i.e. 10ms), and the packet loss probability is 0.0 (i.e. no packet loss). Using [nodes] and [links] declarations, you can create arbitrary network topologies.
The final section is [events], which specifies what should happen to the network in the middle of a simulation. There are 5 kinds of valid events in the configuration file.
• xmit. 0.01 xmit (2,4) means that at time 0.01 second, a DATA packet is generated at router ID 2 destined for router ID 4.
• linkdying. 450.00 linkdying (3,4) means that at time 450 seconds, the link between router ID 3 and 4 will fail. No packet can be delivered over a link that has failed.
• linkcomingup. 750.00 linkcomingup (3,4) means that at time 750 seconds, the link be- tween router ID 3 and 4 will be healed. Once a link is back up, delivery of packets resumes as normal.
• changedelay. 850.00 changedelay (3,4)0.080 means that at time 850 seconds, the link between router ID 3 and 4 will have a new delay of 0.08 second.
• end. 1000.00 end means that the simulation should terminate at time 1000 seconds. If this event is not specified, the simulator can run indefinitely.
You should familiarize yourself with the provided configuration files simpletest{1,2} and try to create some configuration files of your own. The supplied configuration files are only meant to get you started. You will need to create additional configuration files of your own to help test your routing protocols. In particular, none of the providing configuration files exercises the changedelay event.
2026-02-23