Router Packet Processing Simulation

This problem simulates the packet processing of a router based on the knowledge from the study manual. The router receives two types of packets:

• RIP Response Packets: These are control packets encapsulated in UDP datagrams with a destination IP address of 224.0.0.9 and a destination MAC address of 01:00:5E:00:00:09. Each RIP packet carries a routing update for a network prefix expressed in the form \(A.B.C.D/E\). When a RIP packet is received, the router determines which of its own IP addresses (provided as input) is in the same subnet as the packet’s source IP (assume a /24 subnet for simplicity). It then records (or updates) the routing table entry for the advertised network prefix with the next hop information (the source IP and the latest received source MAC for that outgoing port). Note that RIP packets do not generate any output.
• IP Datagram Packets: These packets are encapsulated in IP packets. For every IP packet whose destination IP is not one of the router's local IP addresses, the router must process the packet as follows:
  1. Perform a longest prefix match lookup in the routing table for the destination IP. If a matching network prefix is found and the packet's TTL is greater than 1, decrement the TTL by 1 and forward the packet. In the forwarded Ethernet frame, the next hop MAC address is taken from the latest RIP packet corresponding to that port.
  2. If a matching route is found but the TTL is less than or equal to 1 (i.e. TTL would become 0 after decrement), generate an ICMP Time Exceeded error.
  3. If no route is found for the destination IP, generate an ICMP Destination Network Unreachable error.
  4. If both conditions (no route and TTL reduction to 0) are triggered, the router should generate an ICMP Destination Network Unreachable error.
  For error cases, the error packet is constructed by swapping the MAC addresses from the input datagram’s Ethernet header (i.e. use the datagram's destination MAC as the source, and its source MAC as the destination) and including the corresponding error string in the output.

Note: All IP addresses are in dotted decimal notation. The network prefix is provided in the format A.B.C.D/E. The matching condition uses the mask \( \text{mask} = 2^{32} - 2^{32-E} \), and a destination IP \(ip\) matches a network prefix with base address \(base\) and prefix length \(E\) if

\( (ip \mathbin{\&} \text{mask}) = (base \mathbin{\&} \text{mask}) \)

inputFormat

The input begins with an integer M on the first line, the number of local IP addresses. The second line contains M local IP addresses separated by spaces. The third line contains an integer N, the number of packets. Each of the next N lines describes a packet.

For a RIP packet, the line format is: RIP src_ip dst_ip src_mac dst_mac network_prefix port

For an IP datagram packet, the line format is: IP src_ip dst_ip src_mac dst_mac TTL

Note: It is guaranteed that the valid packet set contains only the two types described above.

outputFormat

For each IP datagram packet whose destination IP is not one of the local IP addresses, output one line representing the outgoing Ethernet frame.

• If the packet is successfully forwarded, output: Forwarded packet: new TTL = X, Next Hop MAC = Y where X is the decremented TTL and Y is the next hop MAC obtained from the corresponding RIP update.

• If an error is to be generated, output: Error packet: , src MAC: , dst MAC: The is either "ICMP Time Exceeded" (if TTL decrements to 0) or "ICMP Destination Network Unreachable" (if no matching route exists or if both conditions occur).

There is no output for local IP packets or for RIP packets.

sample

2
192.168.1.1 10.0.0.1
5
RIP 192.168.1.2 224.0.0.9 AA:AA:AA:AA:AA:AA 01:00:5E:00:00:09 172.16.0.0/16 1
IP 8.8.8.8 172.16.5.5 BB:BB:BB:BB:BB:BB CC:CC:CC:CC:CC:CC 5
IP 8.8.4.4 192.168.1.1 DD:DD:DD:DD:DD:DD EE:EE:EE:EE:EE:EE 10
IP 9.9.9.9 172.16.123.123 FF:FF:FF:FF:FF:FF 00:00:00:00:00:00 1
IP 1.2.3.4 10.10.10.10 11:11:11:11:11:11 22:22:22:22:22:22 8

Forwarded packet: new TTL = 4, Next Hop MAC = AA:AA:AA:AA:AA:AA
Error packet: ICMP Time Exceeded, src MAC: 00:00:00:00:00:00, dst MAC: FF:FF:FF:FF:FF:FF
Error packet: ICMP Destination Network Unreachable, src MAC: 22:22:22:22:22:22, dst MAC: 11:11:11:11:11:11