Background

After supporting the link layer and the network layer, the router immediately received countless packets. Although Pengpeng was drowned by a huge amount of data, he calmly remembered what the textbook said: there are two kinds of messages that network devices can handle, namely control messages and data messages. For a router, data messages are what need to be forwarded, while control messages are used to manage its forwarding direction (routing table). To interact with other real routers, you need to implement the simple routing protocol RIP. After the forwarding table is established, you need to start “hot potato routing”, correctly sending traffic from other hosts to the corresponding next router.

Problem Description

Based on the relevant knowledge in the “Study Manual”, you need to process the following two types of messages.

One type is the control message of the RIP routing protocol, encapsulated in a UDP datagram. You will only receive RIP Response messages, with destination IP address 224.0.0.9 and destination MAC address 01:00:5E:00:00:09, which indicate routing table updates. You need to determine, from the source IP address, which of your IP addresses is in the same subnet as it, thus obtaining the corresponding outgoing interface number in the routing table. For each received route entry, you need to properly maintain your own routing table according to the given rules (see the “Study Manual”), recording the next-hop information (including IP and MAC) for each reachable network prefix. For control messages, you never need to reply.

The other type is a data message, encapsulated in an IP packet. You need to forward packets whose destination IP address is not owned by the local machine. If the routing table can find the next hop corresponding to the destination IP address, you should construct a valid IP packet, fill in the correct source and destination information, and update related fields (such as TTL and checksum). If no routing information can be found, you should construct a correct ICMP Destination Network Unreachable message and send it back to the source host. If the packet’s TTL is decremented to 0, you should construct a correct ICMP Time Exceeded message and send it back to the source host. For these two kinds of error messages, you must fill the corresponding payload as required by the “Study Manual”, infer the source IP address from the receiver MAC address, and, in the Ethernet frame, use (receiver MAC address, sender MAC address) as the (sender MAC address, receiver MAC address) of the corresponding datagram in the input. If both “no route information found” and “TTL decremented to 0” happen at the same time, you should construct an ICMP Destination Network Unreachable. In all cases, for a data message whose destination IP address does not belong to the local machine, the router you implement will always produce one outgoing Ethernet frame.

Since forwarding requires filling in the next hop’s MAC address and we do not provide an active ARP query interface, in this task you must obtain the MAC address of the corresponding destination router only from the Ethernet frame header of RIP messages, and use the most recently obtained one before forwarding.

We guarantee that, in the normal traffic fragments (i.e., fragments that pass validation) provided in this problem, there are exactly the above two types of messages and no others. Also, for all packets that need to be forwarded, you can obtain the corresponding destination router’s MAC address from RIP messages using the method above. Similar to the previous problem, Wireshark will show a UDP checksum error; just ignore it.

Input Format

The input contains at most $n$ traffic fragments, with total size at most $m$ bytes. Based on the input, the routing table you need to build has at most $k$ entries. The messages that require routing-table lookup for forwarding account for about $p_{query}\%$ of all messages.

Output Format

Your output will be compared byte by byte with the answer file. Please do not output any extra information, to avoid unnecessary loss of points.

Hint

【Subtasks】

【Sample 1】

See the attached files 1.in/ans.

【Sample Explanation 1】

The sample input has ten Ethernet frames, including eight RIP packets and two IP packets that need to be forwarded.

For the first four RIP Responses, the following routing table can be obtained.

After receiving the first Response:

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
13.115.192.0/18 via 10.2.7.2 if 7 metric 9
224.0.0.0/3 via 10.2.7.2 if 7 metric 15

After receiving the second Response:

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
13.115.192.0/18 via 10.2.7.2 if 7 metric 9

After receiving the third Response:

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
13.115.192.0/18 via 10.2.7.2 if 7 metric 9
88.128.0.0/10 via 10.2.6.2 if 6 metric 13

After receiving the fourth Response:

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
88.128.0.0/10 via 10.2.6.2 if 6 metric 13

Next come two UDP packets. For the address 77.147.142.166, there is no corresponding entry in the routing table, so it responds with ICMP Destination unreachable. For the address 107.28.70.129, it is within the range 104.0.0.0/6, so TTL is decremented by one and the packet is forwarded to 10.2.7.2. Its MAC address can be obtained from the first RIP Response.

After receiving the fifth Response:

104.0.0.0/6 via 10.2.7.2 if 7 metric 7
88.128.0.0/10 via 10.2.6.2 if 6 metric 13
130.127.0.0/17 via 10.2.4.2 if 4 metric 3

After receiving the sixth Response:

130.127.0.0/17 via 10.2.4.2 if 4 metric 3

After receiving the seventh Response:

130.127.0.0/17 via 10.2.4.2 if 4 metric 3
160.245.176.0/20 via 10.2.5.2 if 5 metric 9

After receiving the eighth Response:

130.127.0.0/17 via 10.2.4.2 if 4 metric 3
160.245.176.0/20 via 10.2.5.2 if 5 metric 9
90.32.0.0/15 via 10.2.5.2 if 5 metric 8

【Hint】

Since forwarding each data message requires a routing-table lookup, you need an efficient data structure to store the key information in the routing table, and you must also pay attention to space efficiency. For efficient implementation, you may refer to the papers and materials attached to the “Study Manual”.

When forwarding IP packets, only a few fields in the header are modified. Therefore, the IP checksum may not need to be recomputed; in many cases, only minimal changes are needed. However, if you want to simplify in any way, you must ensure that your operations are exactly equivalent to the operations we describe. Intuitive ideas often miss some edge cases, so be sure to pay attention.

Translated by ChatGPT 5