CN notes 前情提要：傳送門
目錄：
• What are the basic components of a router?
• Explain the forwarding (or switching) function of a router.
• The switching fabric moves the packets from input to output ports. What are the functionalities performed by the input and output ports?
• What is the purpose of the router’s control plane?
• What tasks occur in a router?
• List and briefly describe each type of switching. Which, if any, can send multiple packets across the fabric in parallel?
• What are two fundamental problems involving routers, and what causes these problems?
• What are the bottlenecks that routers face, and why do they occur?
• What is CIDR, and why was it introduced?
• Name 4 takeaway observations around network traffic characteristics. Explain their consequences.
• Why do we need multibit tries?
• What is prefix expansion, and why is it needed?
• What are the benefits of variable-stride versus fixed-stride multibit tries?What are the basic components of a router?
- Input/output ports
- The switching fabric
- The routing processor
Explain the forwarding (or switching) function of a router.
這是路由器將數據包從輸入鏈路接口傳輸到適當的輸出鏈路接口的操作。轉發發生在非常短的時間範圍內（通常為幾 nanoseconds ），並且通常在硬件中實現。
The switching fabric moves the packets from input to output ports. What are the functionalities performed by the input and output ports?
Inside the forwarding data plane (hardware) we have three main components:
- Input ports — first they physically terminate the incoming links to the router, then they decapsulate packets, and finally (most importantly) they perform the
lookupfunction by consulting the forwarding table to forward the packet to the appropriate output port through the switching fabric. - Switching fabric — moves packets from input to output ports. 分為三種類型：
memory,bus, andcrossbar - Output ports — receive and queue packets from the switching fabric and send them over to the outgoing link
What is the purpose of the router’s control plane?
Inside the control plane (software), we have the routing processor which implements the routing protocols, maintains the routing tables, and computes the forwarding tables.
What tasks occur in a router?
- Lookup — router looks at destination IP and consults forwarding table (FIB,
Forwarding Information Base) to determine output link using the longest prefix matching algorithms - Switching — aka forwarding this is the most important task of a router where the router transfers the packet from the input link to the output link.
- Queuing — after the packet has been switched to a specific output port, it needs to be queued if the link is congested
- Header validation and checksum — router checks the packet’s version number, decreases
time-to-live (TTL)field, and recalculates the header checksum - Route processing — routing processor uses routing protocols (such as OSPF/RIP/BGP) to build the forwarding tables
- Protocol processing — routers need to use some protocols to implement their functions including SNMP (Simple Network Management Protocol), TCP and UDP, and ICMP (Internet Control Message Protocol).
List and briefly describe each type of switching. Which, if any, can send multiple packets across the fabric in parallel?
- via
memory— routing processor controls this method which involves the packet being copied to the processor’s memory, consulting the forwarding table, and copied the packet to the output’s port buffer. One packet at a time. - via
bus— no routing processor involved — the input port puts an internal header which designates the output port and sends the packet to the shared bus. All output ports receive the packet but only the designated one keeps it. One packet at a time. - via
interconnection network— crossbar switch used so that multiple packets can be carried at the same time as long as they are using different input and output ports.
What are two fundamental problems involving routers, and what causes these problems?
- Bandwidth and Internet population scaling — caused by the increasing number of devices that connect to the Internet, heavier traffic from new apps, new technologies such as optical links that can handle higher volumes of traffic.
- Services at high speeds — new apps may require new services such as protection against delays in presence of congestion and protection during attacks/failures. Offering these services at very high speeds is a challenge for routers.
What are the bottlenecks that routers face, and why do they occur?
Many bottlenecks including exact lookups, prefix lookups, packet classification, switching limitations, and security. Most are caused by scaling issues — the need for high speed and service guarantees.
What is CIDR, and why was it introduced?
Classless Internet Domain Routing — introduced to help with scaling as we ran out of IP addresses so it allows IP addresses of arbitrary-length prefixes. This helped decrease router table size but introduced the longest-matching-prefix lookup problem.
Name 4 takeaway observations around network traffic characteristics. Explain their consequences.
- There are a large number of concurrent flows of short duration — therefore a caching solution would not work efficiently.
- Lookup speed is very important, a large part of the computational cost for lookup is in accessing memory.
- An unstable/inefficient routing protocol can lead to time increases
- Memory usage trade-off — either use fast, expensive memory (cache in software/SRAM) or cheaper but slower memory (DRAM)
Why do we need multibit tries?
Unibit tries require too many memory accesses while multibit tries solve this by using a stride. A stride is the number of bits that we check at each step.
What is prefix expansion, and why is it needed?
Expanding a given prefix to more prefixes so that we don’t miss out on any prefixes. Gives more speed with a cost of increased database size.
What are the benefits of variable-stride versus fixed-stride multibit tries?
- More optimized — takes up less space in prefix database, less memory access, more flexible.
關於 Variable Stride一些要點：
- 每個節點可以有不同數量的要探索的 bits。
- 每個節點的步長優化都是為了節省內存和最少的內存訪問。
- 使用動態規劃選擇最佳變量步幅
