1 實驗背景與目標

在 CS144 的 Lab 6 中，我們需要在之前實現的 NetworkInterface（Lab 5）基礎上構建一個完整的 IP 路由器。路由器的主要任務是根據路由表將接收到的 IP 數據報轉發到正確的網絡接口，并發送給正確的下一跳（next hop）。

一個路由器擁有多個網絡接口，可以在任何一個接口上接收 Internet 數據報。路由器的主要職責是根據路由表確定兩件事：

• 應該使用哪個出站接口（interface）發送數據報
• 數據報的下一跳（next hop）IP 地址是什么

與前幾個實驗不同，IP 路由器的實現不需要了解 TCP、ARP 或以太網的細節，只需專注于 IP 層的轉發邏輯。

2 路由器工作原理

2.1 路由器功能概述

IP 路由器主要完成兩個關鍵功能：

1. 維護路由表：存儲一系列路由規則，每條規則包含網絡前綴、前綴長度、下一跳信息和出站接口編號
2. 轉發數據報：根據路由表中的規則，將每個接收到的數據報轉發到正確的出站接口和下一跳地址

2.2 最長前綴匹配原則

路由器使用最長前綴匹配（Longest Prefix Match）算法來選擇最佳路由。這意味著當多個路由規則匹配一個目標 IP 地址時，路由器會選擇前綴長度最長的那個規則。這樣可以實現更精確的路由控制。例如，對于目標 IP 地址 172.16.10.3，可能匹配的規則有 172.16.0.0/16 和 172.16.10.0/24，路由器會選擇前綴長度為 24 的規則，因為它提供了更精確的匹配。

3 路由器實現

3.1 數據結構設計

將路由表按前綴長度（1-32）分成32個組，方便從長到短進行最長前綴匹配。每個前綴長度組內使用哈希表存儲，表示匹配前綴與路由項的映射關系。

struct RouteEntry {size_t interface_num {};      // 出站接口編號std::optional<Address> next_hop {}; // 下一跳地址（如果有）
};// 路由表，按前綴長度分組（最多32個組，對應IPv4地址的32位，逆序表示。例如下標為0代表前綴長度32）
std::array<std::unordered_map<uint32_t, RouteEntry>, 32> routing_table_ {};

3.2 添加路由條目

add_route方法向路由表添加一條新的路由規則，具體處理邏輯：

1. 前綴計算：使用右移操作獲取有效前綴位，例如：對于 192.168.1.0/24，右移 (32-24) = 8 位，保留高 24 位作為匹配前綴。需要特別處理前綴長度為 0 的默認路由，避免右移 32 位導致的未定義行為
2. 路由條目存儲：將路由條目存入對應前綴長度的哈希表中，鍵是處理后的前綴，值是路由條目信息

void Router::add_route(const uint32_t route_prefix,const uint8_t prefix_length,const optional<Address> next_hop,const size_t interface_num) {cerr << "DEBUG: adding route " << Address::from_ipv4_numeric(route_prefix).ip() << "/"<< static_cast<int>(prefix_length) << " => " << (next_hop.has_value() ? next_hop->ip() : "(direct)")<< " on interface " << interface_num << "\n";// 截取route_prefix的前prefix_length位作為有效前綴uint32_t masked_prefix = (prefix_length == 0) ? 0 : (route_prefix >> (32 - prefix_length));// 插入到對應前綴長度的路由表中routing_table_[prefix_length][masked_prefix] = { interface_num, next_hop };
}

3.3 路由匹配查找

match 方法實現最長前綴匹配算法，為每個數據報找到最佳路由：

flowchart TDA[開始匹配] --> B[從前綴長度31開始]B --> C[計算目標IP地址的前len位]C --> D{前綴長度組中\n有匹配項?}D -->|是| E[返回匹配的路由條目]D -->|否| F[前綴長度減1]F --> G{前綴長度≥0?}G -->|是| CG -->|否| H[返回無匹配]

optional<Router::RouteEntry> Router::match(uint32_t dst_addr) const noexcept {for (int len = 31; len >= 0; --len) {uint32_t masked = (len == 0) ? 0 : (dst_addr >> (32 - len));const auto& table = routing_table_[len];auto it = table.find(masked);if (it != table.end()) {return it->second;}}return nullopt;
}

3.4 數據報轉發處理

route 方法是路由器的核心功能，負責處理所有接口收到的數據報并進行轉發。

void Router::route() {for (const auto& interface : interfaces_) {auto& datagrams_received = interface->datagrams_received();// 處理所有收到的數據報while (!datagrams_received.empty()) {InternetDatagram datagram = move(datagrams_received.front());datagrams_received.pop();// TTL ≤ 1表示不能再轉發，直接丟棄if (datagram.header.ttl <= 1) {continue;}// TTL減1并重新計算校驗和datagram.header.ttl -= 1;datagram.header.compute_checksum();// 使用最長前綴匹配查找路由條目auto routeEntry = match(datagram.header.dst);if (!routeEntry.has_value()) {continue;}// 如果沒有指定下一跳，則直接發送到目標IPAddress target = routeEntry->next_hop.value_or(Address::from_ipv4_numeric(datagram.header.dst));// 通過對應接口發送數據報interfaces_[routeEntry->interface_num]->send_datagram(datagram, target);}}
}

4 調試記錄

1. 最初在計算掩碼后的前綴時，使用了按位與操作，但這種方法對于可變長度前綴處理起來比較復雜。改用右移操作后，處理變得更簡單高效。

2. 最初的實現中，先執行路由匹配再檢查TTL，這導致一些應該被丟棄的數據報被錯誤處理。修正為先檢查TTL再進行后續處理。

3. 處理前綴長度為0的默認路由時需要特殊處理，確保將掩碼設置為0而不是嘗試右移32位（這會導致未定義行為）。

   

5 代碼倉庫

項目代碼已上傳至GitHub：https://github.com/HeZephyr/minnow