CSS334 — Router Architecture, Routing & Network Management Cheat Sheet

Exam-ready summary | Lecture 9 | All topics included

0. Quick Revisit: Data Plane vs Control Plane

1. Router Architecture Overview

        ┌──────────────────────────────────┐
        │        Routing Processor         │  ← Control Plane (software, ms)
        │  (runs routing algorithms/SDN)   │
        └──────────────────┬───────────────┘
                           │
  Input Ports ────► [Switching Fabric] ────► Output Ports
  (line cards)                               (line cards)
       ↑                                          ↑
   Data Plane (hardware, ns)              Data Plane (hardware, ns)

• Routing Processor → runs routing algorithms, manages routing table (control plane)
• Switching Fabric → physically moves packets from input to output (data plane)
• Input/Output Ports → interface with the physical links (data plane)

Ideal switching rate = $N \times R$ where $N$ = number of input ports, $R$ = line rate
e.g., 4 × 10 Gbps input ports → switching fabric should handle ≥ 40 Gbps

$\boxed{\text{Ideal switching rate} = N \times R}$

2. Input Port Functions

Pipeline (left to right):

Line Termination → Link Layer Protocol → Lookup/Forwarding/Queueing → Switch Fabric
     (L1)               (L2, e.g. Ethernet)          (L3 — the brain)

• Physical layer: Bit-level reception
• Link layer: e.g., Ethernet frame handling
• Lookup / Forwarding (the important part):
  • Read header field value → match against forwarding table in input port memory
  • "Match plus action" paradigm
  • Goal: complete input port processing at line speed
  • If datagrams arrive faster than fabric can handle → input port queue builds up

Two Forwarding Modes

3. Destination-Based Forwarding

• Forwarding table maps destination address ranges → link interfaces
• Example: packets destined anywhere in 200.23.16.0 – 200.23.23.255 → interface 3

Problem: What if ranges don't divide neatly? → Longest Prefix Match

4. Longest Prefix Match (LPM)

$\boxed{\text{Most specific (longest matching prefix) route wins}}$

Rule: When multiple forwarding table entries match a destination IP, use the entry with the longest prefix (most bits matched).

Example Forwarding Table:

Algorithm:

1. Try to match all 32 bits
2. If no match, try 31 bits, 30 bits… down to 0 bits (default route 0.0.0.0/0)
3. Use the first (longest) match found

Practical examples:

• /32 → matches exactly one specific IP — most specific possible
• /0 (0.0.0.0/0) → matches everything — default route (least specific)
• 128.143.71.21 with entry 128.143.71.0/24 → 24-bit match → sent to R4

Analogy: Like a phonebook — search "John Smith Jr." first (most specific). Only fall back to "John" if the full name isn't found.

5. Switching Fabrics

Purpose: Physically move packets from input port to output port.

Three Types (in order of speed/complexity)

Type 1: Switching via Memory (Slowest)

• Classic first-gen routers — CPU controls everything
• Packet copied into system RAM, then copied out to output port
• 2 memory bus crossings per packet → bottleneck
• Speed limited by memory bandwidth
• Used by cheap consumer routers today

Input Port → [RAM] → Output Port    (through CPU/memory bus twice)

Analogy: A secretary who walks to the filing room, copies the letter, walks back and sends it. Slow because everything goes through one person.

Type 2: Switching via Shared Bus (Medium)

• Packet transferred directly from input to output over a shared bus
• Only one packet at a time (bus contention)
• Speed limited by bus bandwidth (bus size in bits × clock speed)
• Example: Cisco 5600 — 32 Gbps bus — good for access routers

Input Port → [Shared Bus] → Output Port    (one at a time)

Analogy: A single hallway — only one person can walk through at a time.

Type 3: Switching via Interconnection Network (Fastest)

• Uses crossbar or Clos (multistage) network
• Exploits parallelism — multiple packets can traverse simultaneously via different paths
• Fragments datagrams into fixed-length cells on entry, reassembles at exit
• Data-center grade — used in high-end/enterprise routers

$\text{e.g., } 60 \times 60 \text{ crossbar} = \text{simultaneous parallel transfers}$

Analogy: A highway interchange with multiple lanes — many cars travel simultaneously on different paths.

6. Input Port Queuing & HOL Blocking

When the switching fabric is slower than combined input port speed → queue builds at input ports

Head-of-Line (HOL) Blocking

$\boxed{\text{HOL Blocking: front packet blocks packets behind it, even if their output port is free}}$

Input 1: [Pkt→Out2] [Pkt→Out3]   ← Out3 is FREE, but blocked by Pkt→Out2 waiting
Input 2: [Pkt→Out2]               ← Out2 is busy

• The packet at the head of queue is waiting for its output port
• Packets behind it (destined for free output ports) are stuck waiting → wasted capacity

7. Output Port Queuing & Buffer Management

When packets arrive from fabric faster than the link can transmit → queue builds at output ports

[Switch Fabric] → [Output Queue Buffer] → [Line/Link] → out
                         ↑
                  (packets wait here if link is busy)

How Much Buffer?

RFC 3439 rule of thumb: $\boxed{B = \text{RTT} \times C}$ e.g., $C = 10$ Gbps, RTT = 250 ms → $B = 2.5$ Gbit

Modern recommendation (with $N$ flows): $\boxed{B = \frac{\text{RTT} \times C}{\sqrt{N}}}$

⚠️ Too much buffering = bad! Long queues → high latency → poor real-time apps, sluggish TCP.
Goal: "Keep bottleneck link just full enough, but no fuller."

Drop Policies (when buffer is full)

8. Packet Scheduling

Deciding which packet to send next on the output link.

1. FCFS / FIFO

• First-Come, First-Served — packets sent in order of arrival
• Simple, no priority differentiation

2. Priority Scheduling

• Traffic classified into priority classes (based on any header field)
• Always send from highest-priority non-empty queue
• FCFS within each class
• ⚠️ Starvation risk: low-priority queue may never get served if high-priority is always busy

High Priority Queue:  [P] [P] [P] ──────────────────► Link
Low Priority Queue:   [p] [p]     (only served when high queue empty)

Analogy: Airline boarding — first class boards first regardless of arrival time.

3. Round Robin (RR)

• Traffic classified into classes
• Server cycles through classes in order
• Sends one complete packet per class per cycle
• Fair — no starvation

Cycle: [Class 1 pkt] → [Class 2 pkt] → [Class 3 pkt] → [Class 1 pkt] → …

Analogy: Teacher calling on each student in order — everyone gets a turn.

4. Weighted Fair Queueing (WFQ)

• Generalized Round Robin — each class gets service proportional to its weight

$\boxed{\text{Class } i \text{ gets } \frac{w_i}{\sum_j w_j} \text{ of the bandwidth}}$

• Provides minimum bandwidth guarantee per class
• Most common in commercial routers
• Example weights: TCP (high) > UDP (medium) > ICMP (low)

Why does traceroute sometimes show decreasing RTTs? Some routers assign very low priority to ICMP(used by traceroute) → processing delayed → apparent RTT fluctuates, not just based on physical distance.

Analogy: Splitting a pizza proportionally — each person gets slices based on how much they "paid for".

9. Routing Fundamentals

• Routing = selecting the path along which data travels from source to destination
• Performed by routers using routing algorithms
• Routing protocols use a metric to determine the best path:
  • Hop count (RIP)
  • Bandwidth
  • Delay
  • Cost

10. Three Types of Routing

Static Routing (Nonadaptive)

• Admin manually configures routes in the routing table
• Routes do not change when topology changes — if link fails, route stays broken until manually fixed

Advantages: No CPU overhead, no extra bandwidth, predictable, secure
Disadvantages: Doesn't scale, requires admin expertise, fails silently

Cisco commands:

ip route 172.16.3.0 255.255.255.0 172.16.2.1
ip route 192.168.2.0 255.255.255.0 192.168.1.1

Key insight: Directly connected networks are auto-added to the routing table. You only manually add routes for indirect (non-directly-connected) networks.

Default Routing

• A catch-all route — if no specific route matches, send to this next-hop
• Used for single exit point networks (e.g., stub network with only one way out)
• In routing table: destination 0.0.0.0, mask 0.0.0.0
• If a specific route exists, it wins over the default route (LPM rule)

Cisco command:

ip route 0.0.0.0 0.0.0.0 172.16.3.1

Analogy: "If you don't know where to deliver this, just send it to headquarters."

Dynamic Routing (Adaptive)

• Router automatically discovers and updates routes when topology changes
• If a link goes down → routing protocol detects it and finds an alternative path automatically

Static vs Dynamic:

11. Dynamic Routing Protocol Hierarchy

Dynamic Routing
├── IGP (Interior Gateway Protocol) — within one AS
│   ├── Distance Vector → RIP, IGRP
│   ├── Link State     → OSPF
│   └── Hybrid         → EIGRP
└── EGP (Exterior Gateway Protocol) — between ASes
    └── Path Vector    → BGP

IGP = within your own organisation's network
EGP/BGP = between organisations (e.g., your ISP ↔ another ISP)

12. Configure Routing — Step-by-Step Process

4 Steps:

1. Design subnet/IPs — count subnets (don't forget WAN links!), pick CIDR/VLSM
2. Assign IPs to interfaces — each router interface + each host
3. Set routing table — static/default/dynamic routes
4. Test connectivity — ping hop by hop

Exam reminder: In logical diagrams, clouds show network addresses. In physical diagrams, label interface names (eth0, eth1) AND their IPs on each device.

13. Routing Configuration: 2-Network Example

A ──── [Network A: 172.16.101.0/29] ──── R1 ──── [Network B: 192.168.216.12/30] ──── C
       A: 172.16.101.201/29        eth1: 172.16.101.202/29  eth2: 192.168.216.13/30   C: 192.168.216.14/30

On Host A:

sudo ifconfig eth1 172.16.101.201/29
sudo route add default gw 172.16.101.202    # default = R1's eth1

On Host C:

sudo ifconfig eth1 192.168.216.14/30
sudo route add default gw 192.168.216.13    # default = R1's eth2

On Router R1:

sudo ifconfig eth1 172.16.101.202/29
sudo ifconfig eth2 192.168.216.13/30
sudo sysctl -w net.ipv4.ip_forward=1        # CRITICAL: enable routing!
# No static routes needed — both networks are directly connected

net.ipv4.ip_forward=1 — without this, Linux drops packets that arrive on one interface destined for another (acts as host, not router). Must be set explicitly!

14. Routing Configuration: 3-Network Example

Network A (192.168.10.0/24) ── R1 ── Network B (192.168.20.0/24) ── R2 ── Network C (192.168.30.0/24)

R1: eth1=192.168.10.1/24, eth2=192.168.20.1/24
R2: eth1=192.168.20.2/24, eth2=192.168.30.1/24
Host A: 192.168.10.8/24
Host B: 192.168.30.8/24

Routing Table Summary:

Key rule: Directly connected networks appear automatically. Only add static routes for indirect (remote) networks. R1 is directly connected to Net A and Net B → no static route needed for those.
R1 is not directly connected to Net C → must add static route.

Commands:

# Host A
sudo ifconfig eth1 192.168.10.8/24
sudo route add default gw 192.168.10.1
 
# Host B
sudo ifconfig eth1 192.168.30.8/24
sudo route add default gw 192.168.30.1
 
# R1
sudo ifconfig eth1 192.168.10.1/24
sudo ifconfig eth2 192.168.20.1/24
sudo sysctl -w net.ipv4.ip_forward=1
sudo route add -net 192.168.30.0/24 gw 192.168.20.2   # route to Net C via R2
 
# R2
sudo ifconfig eth1 192.168.20.2/24
sudo ifconfig eth2 192.168.30.1/24
sudo sysctl -w net.ipv4.ip_forward=1
sudo route add -net 192.168.10.0/24 gw 192.168.20.1   # route to Net A via R1

Verification strategy: Test hop by hop — A→R1, then A→R2, then A→B. Don't jump straight to end-to-end.

ping -c 5 192.168.20.2    # A → R2 (next router)
ping -c 5 192.168.30.8    # A → B  (end-to-end)

Counting Subnets (Exam Classic ⚠️)

Always count the router-to-router WAN link as a separate subnet!

• 3 host networks + 1 router link = 4 subnets total
• If there are 2 routers with 2 links between them = 5 subnets

15. Network Management

What Is It?

Network management = deploying, integrating, and coordinating hardware, software, and humans to monitor, test, configure, analyse, evaluate, and control network elements to meet performance and QoS requirements.

Key Components

Two Access Methods

16. SNMP — Simple Network Management Protocol

Two Operation Modes

Trap = device sends an unsolicited alert to the manager when something happens (e.g., link goes down, memory overloaded).

SNMP Message Types

Generic Trap Types (7 types, 0–6)

0 = coldStart       (device rebooted from scratch)
1 = warmStart       (device restarted but config preserved)
2 = linkDown        (interface went down)
3 = linkUp          (interface came back up)
4 = authenticationFailure  (wrong community string)
5 = egpNeighborLoss (BGP neighbor lost)
6 = enterpriseSpecific     (vendor-defined)

SNMP Message Formats

GET / SET / RESPONSE (PDU Type 0–3):

TRAP (PDU Type 4):

Example SNMP command:

snmpget -v2c -c public 192.168.1.1 1.3.6.1.2.1.1.1.0
# → SNMPv2-MIB::sysDescr.0 = STRING: Cisco IOS Software, C2960

17. MIB — Management Information Base

• MIB = database of all manageable variables on a device (counters, config, status)
• ~400 standard MIB modules defined in RFCs; many more vendor-specific
• Each variable identified by an Object ID (OID) — a hierarchical dotted number

OID Tree Structure

Root → iso(1) → org(3) → dod(6) → internet(1)
                                    ├── mgmt(2)
                                    │   └── mib-2(1)
                                    │       ├── system(1)
                                    │       ├── interfaces(2)
                                    │       └── ip(4)
                                    └── private(4)
                                        └── enterprise(1)
                                            ├── cisco(9)
                                            ├── microsoft(311)
                                            └── juniperMIB(2636)

Example MIB Variables (UDP Module)

snmpwalk — Walk an OID Subtree

snmpwalk -v2c -c public localhost .1.3.6.1.4.1.2021.4
# Returns all variables under that OID (e.g., memory info: memTotalReal, memAvailReal, etc.)

snmpwalk returns every variable under the given OID prefix — useful for exploring device state.

Example Trap Data (Real-World)

Trap: lvAlarmMemoryOverload
OID:  1.3.6.1.4.1.48200.2.1.4
Bindings:
  lvTrapTimestamp:      2016-10-06 04:33:42
  lvTrapSeverity:       MINOR
  lvTrapProbableCause:  SYSTEM MEMORY OVERLOAD EXCEEDS THRESHOLD
  lvTrapSpecificProblem: system memory utilization exceeds threshold of 60%
  Community: public

Quick Reference Summary