互联网设计中有一种美丽(或至少是一个成功的抽象):路由器从不考虑 TCP、ARP 或以太网帧。路由器甚至不知道链路层是什么样的。路由器只考虑互联网数据报,并且只通过网络接口抽象与链路层交互。当涉及到诸如“链路层地址是如何解析的?”、“链路层是否有自己与 IP 不同的地址方案?”、“链路层帧的格式是什么?”或“数据报的有效载荷是什么意思?”等问题时,路由器就不关心了。
Q & A
什么数据结构应该用来记录路由表?
这取决于你!但请不要太复杂。对于每个数据报需要 O(N) 的工作量是完全可以接受的,其中 N 是路由表中的条目数。如果你想做一些更高效的事情,我们鼓励你先实现一个工作版本,然后再优化,并且仔细记录和注释你选择实现的任何内容。
如何将以 Address 对象形式出现的 IP 地址转换为我可以写入 ARP 消息的原始 32 位整数?
使用 Address::ipv4_numeric() 方法。
如何将以原始 32 位整数形式出现的 IP 地址转换为 Address 对象?
使用 Address::from_ipv4_numeric() 方法。
如何比较一个 32 位 IP 地址的最重要的 N 位(其中 0 ≤ N ≤ 32)与另一个 32 位 IP 地址的最重要的 N 位?
这可能是这个作业中最“棘手”的部分——得到正确的逻辑。编写一个小的 C++ 测试程序(一个简短的独立程序)或在 Minnow 中添加一个测试来验证你对相关 C++ 操作符的理解并仔细检查你的逻辑可能是值得的。 记住,在 C 和 C++ 中,将一个 32 位整数移位 32 位可能会产生未定义行为。测试会在你的代码下运行检测器来尝试检测这一点。你可以通过在 minnow 目录下运行 ./build/tests/router 直接运行路由器测试。
for ( auto i = 1; i <= prefix_length; i++ ) { auto bit = route_prefix & ( 1 << ( 32 - i ) ); if (bit){ if (cur->right == nullptr){ cur->right = make_unique<TrieNode>(); } cur = cur->right.get(); } else { if (cur->left == nullptr){ cur->left = make_unique<TrieNode>(); } cur = cur->left.get(); } if ( i == prefix_length ){ cur->interface_num = interface_num; if ( next_hop.has_value() ) cur->next_hop = next_hop; } }
查找
1 2 3 4 5 6 7 8 9 10 11
for ( auto i = 1; i <= 32; i++ ) { auto bit = ip & ( 1 << ( 32 - i ) ); cur = bit ? cur->right.get() : cur->left.get(); if ( cur == nullptr ) { break; } if ( cur->interface_num.has_value() ) { infce = cur->interface_num; addr = cur->next_hop; } }
auto cur = root_.get(); if ( prefix_length == 0 ) { if (!root_){ root_ = make_unique<TrieNode>(); } root_->interface_num = interface_num; if ( next_hop.has_value() ) root_->next_hop = next_hop; return; } for ( auto i = 1; i <= prefix_length; i++ ) { auto bit = route_prefix & ( 1 << ( 32 - i ) ); if (bit){ if (cur->right == nullptr){ cur->right = make_unique<TrieNode>(); } cur = cur->right.get(); } else { if (cur->left == nullptr){ cur->left = make_unique<TrieNode>(); } cur = cur->left.get(); } if ( i == prefix_length ){ cur->interface_num = interface_num; if ( next_hop.has_value() ) cur->next_hop = next_hop; } } }
// Go through all the interfaces, and route every incoming datagram to its proper outgoing interface. voidRouter::route() { for ( auto& i : _interfaces ) { while ( !i->datagrams_received().empty() ) { datagram_buffer_.push( i->datagrams_received().front() ); i->datagrams_received().pop(); } } queue<InternetDatagram> datagram_buffer_copy; while ( !datagram_buffer_.empty() ) { InternetDatagram& d = datagram_buffer_.front(); if (d.header.ttl == 0){ datagram_buffer_.pop(); continue; } if ( !match( d ) ) { d.header.ttl--; datagram_buffer_copy.push( d ); } datagram_buffer_.pop(); } datagram_buffer_ = move(datagram_buffer_copy); }
boolRouter::match( InternetDatagram& d ) { auto ip = d.header.dst; auto cur = root_.get(); optional<size_t> infce; optional<Address> addr; if (root_->interface_num.has_value()) { infce = root_->interface_num; addr = root_->next_hop; } for ( auto i = 1; i <= 32; i++ ) { auto bit = ip & ( 1 << ( 32 - i ) ); cur = bit ? cur->right.get() : cur->left.get(); if ( cur == nullptr ) { break; } if ( cur->interface_num.has_value() ) { infce = cur->interface_num; addr = cur->next_hop; } } if (!infce.has_value()){ returnfalse; } d.header.ttl--; if( d.header.ttl == 0 ){ returntrue; } d.header.compute_checksum(); if (addr.has_value()){ interface(infce.value())->send_datagram( d, addr.value() ); } else { interface(infce.value())->send_datagram( d, Address::from_ipv4_numeric( d.header.dst )); } returntrue; }