[SOLVED] R algorithm Scheme graph network

part 1 Static routing
Static routing is a type of routing algorithm that makes use of manually configured routing
table entries, in contrast to dynamic routing algorithms which use network messages to determine the best routes. When failures happen in the network, static routes will not get updated. They have to be manually updated to use a different route. This already highlight one of the drawbacks of static routing schemes.
Advantages:
Little resource usage
Secure (Administrators have a lot of control over the routing)
Great for small networks (less complexity)
Disadvantages:
Human errors
Fault tolerance
For more information see section 5.6.2 of the book.
Routing tables
A router uses its routing table to decide where to forward incoming packets. A typical routing table may contain the following columns:
Network destination: The range of destination IPs that can be reached on this network.
Subnet mask: This separates the destination IP into its network address and host address components.
Gateway: The IP address of the next router to which to send the packet.
When the router receives a packet, it checks which network destination(s) correspond(s) to the packets destination address. (If there are multiple network destinations possible, the one with the longest prefix match is preferred.) It then forwards the packet to the appropriate gateway. Programming exercise
In this programming exercise, you will implement a static routing table. A template will be provided with the correct function signatures. A basic test case can be found under the Test tab, but you are highly encouraged to write your own test cases to make sure your implementation is correct.
You are given two functions (exact method signatures can be found in the code template):
Add Route (Network Prefix: int, Subnet Mask: int, Gateway: int) -> void
This function is used to add route entries to your static routing table.
Arguments:
Network prefix: Network address of the subnet.
Subnet Mask: Mask corresponding to the subnet.
Gateway: Router that can handle traffic belonging to the subnet.
All arguments use the same format: an ip address in the form of a 32-bit binary sequence. We provide a function for you in the Library to convert from a decimal IP address representation to a binary one.
255.255.0.0: str -> 11111111 11111111 00000000 00000000: int
We use this function in our tests to add entries to your routing table.
Returns: This function should not return anything
Lookup Route (Address: int) -> int
This function is used to lookup the route for a specific IP address.
Arguments:
Address: The IP address that we want to route to.
All arguments use the same format: an ip address in the form of a 32-bit binary sequence. We provide a function for you in the Library to convert from a decimal IP address representation to a binary one.
255.255.0.0: str -> 11111111 11111111 00000000 00000000: int
We use this function in our tests to check if your routing logic is correct.
Returns: This function should return the gateway of the matched route as a binary sequence. If no valid route can be found the function should return ERROR_NO_ROUTE, which is mapped to -1 in the code.
Assumptions
You can assume that our input is valid and non-malicious.

You can assume that the routing table does not change after the intial filling.
part 2 Dynamic Routing Distance Vector
Dynamic routing makes use of messages to learn where to route packets to get them to their destination. There are two different types of dynamic routing algorithms: Distance Vector and Link State. Distance vector routing algorithms only gather data from their neighbour (directly connected) routers, while link state gathers data from all routers in the network. Because of this difference both types of algorithms have different advantages and disadvantages.
Distance Vector
Distance vector algorithms only know the state of their neighbours. They use propagation to spread knowledge about distant routers. Each router slowly learns more about the network by gossiping newly discovered routers.
Advantages compared to link state algorithms:
Low bandwidth requirements due to local sharing
Small packets
No flooding
Disadvantages compared to link state algorithms:
Based on local knowlegde instead of global
Converges slowly e.g. takes longer to propegate broken links
An example of a distance vector algorithm is RIP.
Programming exercise
In this programming exercise, you will implement a distance vector routing table. A template will be provided with the correct function signatures. A basic test case can be found under
the Testtab, but you are highly encouraged to write your own test cases to make sure your implementation is correct.
You are given the following functions (exact method signatures can be found in the code template):
Constructor (Router Identifier: str) -> void
This function is used to store the router indentifier.
Arguments:
Router Identifier: Name of the router. This argument is a 4 character hexadecimal string. Returns: This function should not return anything
Process Packet (Packet: str) -> str
This function is given to parse the raw packet and detect the type of packet and subsequently call the corresponding function .e.g Process Data Packet or Process Routing Packet. We provide this function because learning how to parse strings is not an objective of this course. You shouldnt have to touch or understand this function to complete the assignment.
Arguments:
Packet: Incoming network packet. The format of the packet is specified below.
Network packet format: (For explanation only)
D
Where:
Source: The original source of the packet. (4 character hexadecimal string)
Destination: The destination of the packet. (4 character hexadecimal string)
Message: The actual message. (arbitrary length hexadecimal string)
R
Where:
identifier: The identifier of the neighbour router. (4 character hexadecimal string)
latency: The network latency to the neighbour router measured from your router. (number)
n: The number of route entries in the neighbours routing table. (number)
identifier-n: The identifier of the router in the routing table. (4 character hexadecimal string)
latency-n: The latency of the router in the routing table measured from the neighbour router. (number)
Examples of valid packets are:
D aaaa bbbb 1234567890abcdef
R cccc 20 2 bbbb 5 2222 25

Returns: This function should return the output from either the Process Data Packet function or the Process Routing Packet function. If an invalid type is provided the function should return ERROR_INVALID_TYPE, which is mapped to INVALID TYPE in the code.
Process Data Packet (Source: str, Destination: str, Message: str) -> str
This function processes data packets and looks up the route and latency in the routing table(s) and returns these. If a message is directed to the current router, the router should return MESSAGE_THANK_YOU, which is mapped to THANK YOU in the code.
Arguments:
Source: Original source of message. This argument is a 4 character hexadecimal string.
Destination: Final destination of message. This argument is a 4 character hexadecimal string.
Message: Fake message.
Returns: This function should return the neighbour router which can route to the desired destination and the total latency to the final destination (format provided below). If no valid route can be found the function should return ERROR_NO_ROUTE, which is mapped to NO ROUTE in the code. If a message is directed to the current router, the router should return MESSAGE_THANK_YOU, which is mapped to THANK YOU in the code.

cccc 25
Process Routing Packet (Router Identifier: str, Latency: int, Routes: List[Route]) -> str
This function processes routing packets and updates the routing table(s) with new information. Arguments:
Router Identifier: Name of the neighbour router. This argument is a 4 character hexadecimal string.
Latency: The network latency to the neighbour router measured from your router.
Routes: List of routes from the neighbour router.
Route (Router Identifier: str, Latency: int)
Where:
Router Identifier: The identifier of the router in the routing table of your neighbour. This argument is a 4 character hexadecimal string.
Latency: The latency of the router in the routing table of your neighbour measured from the neighbour router.
Returns: This function should return MESSAGE_ROUTE_RECEIVED (which is mapped to RECEIVED in the code) for every routing packet received
Pointers
If two routes have the same total latency return the one which is the newest.
New routing information can be provided at any time.
Routers can update their latency or the latency of their neighbours. Since this makes the
exercise more complex, we have designed the spec tests in such a way that it is possible to pass the assignment (score 90/100) without having this functionality. If you do want to go for the full 100/100, here are some hints for different datastructures that can be used:
Less efficient, but easier (work is done on Data Packet instead of Routing Packet) Map[Destination: str, Map[Forwarding Router: str, Latency: int]] (Routes table) Map[Forwarding Router: str, Latency: int] (Neighbours table)
More efficient, but harder (work is done on Routing Packet instead of Data Packet) Map[Destination: str, Route (Forwarding Router: str, Total latency: int)] (Routing table lookup) Map[Destination: str, Map[Forwarding Router: str, Latency: int]] (Routes table) Map[Forwarding Router: str, Latency: int] (Neighbours table)
Assumptions
You can assume that our input is valid and non-malicious.
You can assume that the network graph stays static, but new nodes can still be discovered,
since you dont have a view of the entire network.
You can assume the latency is the same in both directions
Part 3 Dynamic Routing Link State
Dynamic routing makes use of messages to learn where to route packets to get them to their destination. There are two different types of dynamic routing algorithms: Distance Vector and Link State. Distance vector routing algorithms only gather data from their neighbour (directly

connected) routers, while link state algorithms gather data from all routers in the network. Because of this difference both types of algorithms have different advantages and disadvantages. Link State
Link state algorithms work on global state. Every router gathers information about its neighbours and floods this through the network. This approach leads to a very fast converging time, but also creates network overhead.
An example of a distance vector algorithm is OSPF.
Programming exercise
In this programming exercise, you will implement a link state routing table. A template will be provided with the correct function signatures. A basic test case can be found under the Test tab, but you are highly encouraged to write your own test cases to make sure your implementation is correct.
You are given four functions (exact method signatures can be found in the code template): Constructor (Router Identifier: str, Neighbours: Map[Neighbour Identifier: str, latency: int]) -> void This function is used to store the router identifier.
Arguments:
Router Identifier: Name of the router. This argument is a 4 character hexadecimal string.
Neighbours: Map of directly connected neighbours
Returns: This function should not return anything
Process Packet (Packet: str) -> str
This function is given to parse the raw packet and detect the type of packet and subsequently call the corresponding function, .e.g Process Data Packet or Process Routing Packet. We provide this function because learning how to parse strings is not an objective of this course. You do not have to touch or understand this function to complete the assignment.
Arguments:
Packet: Incoming network packet. The format of the packet is specified below.
Returns: This function should return the output from either the Process Data Packet function or the Process Routing Packet function. If an invalid type is provided the function should return ERROR_INVALID_TYPE, which is mapped to INVALID TYPE in the code.
Network packet format: (For explanation only)
D
Where:
Source: The original source of the packet. (4 character hexadecimal string)
Destination: The destination of the packet. (4 character hexadecimal string)
Message: The actual message. (arbitrary length hexadecimal string)
Example of a valid data packet is:
D aaaa bbbb 1234567890abcdef
R
Where:
identifier: The identifier of the neighbour router. (4 character hexadecimal string)
n: The number of route entries in the neighbours routing table. (number)
identifier-i: The identifier of the i-th router in the routing table, where i is a number between 1 to n (inclusive). (4 character hexadecimal string)
latency-i: The latency of the i-th router in the routing table measured from the neighbour router, where i is a number between 1 to n (inclusive). (number)
Example of a valid routing packet is:
R cccc 2 bbbb 5 2222 25
Process Data Packet (Source: str, Destination: str, Message: str) -> str
This function processes data packets and looks up the route and latency in the routing table(s) and returns these. If a message is directed to the current router, the router should
return MESSAGE_THANK_YOU, which is mapped to THANK YOU in the code.
Arguments:
Source: Original source of message. This argument is a 4 character hexadecimal string.
Destination: Final destination of message. This argument is a 4 character hexadecimal string.
Message: Fake message.
Returns: This function should return the neighbour router which can route to the desired destination and the total latency to the final destination (format provided below). If no valid route can be found the function should return ERROR_NO_ROUTE, which is mapped to NO ROUTE in

the code. If a message is directed to the current router, the router should
return MESSAGE_THANK_YOU, which is mapped to THANK YOU in the code.
note: If 2 routes are equal it should pick the one that has been most recently updated. Example of such a return message is:

cccc 25
Process Routing Packet (Router Identifier: str, Latency: int, Routes: List[Route]) -> str
This function processes routing packets and updates the routing table(s) with new information. Arguments:
Router Identifier: Name of the neighbour router. This argument is a 4 character hexadecimal string.
Latency: The network latency to the neighbour router measured from your router.
Routes: List of routes from the neighbour router.
Route (Router Identifier: str, Latency: int)
Where:
Router Identifier: The identifier of the router in the routing table of your neighbour. This argument is a 4 character hexadecimal string.
Latency: The latency of the router in the routing table of your neighbour measured from the neighbour router.
Returns: This function should return MESSAGE_ROUTE_RECEIVED (which is mapped to RECEIVED in the code) for every routing packet received
Assumptions
You can assume that our input is valid and non-malicious.
You can assume that the network graph stays static, but new nodes can still be discovered,
since you dont have a view of the entire network from the beginning.
You can assume the latency is the same in both directions