Loading...
墨滴

董亦杨

2021/04/23  阅读:70  主题:自定义主题1

【计算机网络笔记04】What's Inside a Router

What's Inside a Router?

Key Words:
-- Router Architecture
-- Switching Fabrics
-- Forwarding with Longest Prefix Matching
-- Buffer Management
-- Scheduling

1. Router Architecture Overview

Input Ports perform several key functions:

  • physical layer function of terminating an incoming physical link at a router
  • link-layer function to interoperate with the link layer at the other side of the incoming link
  • A look-up function that the forwarding table determines the router output port
    • to which an arriving packet will be forwarded via the switching fabric

Switching Fabric connects the router's input ports to its output ports,

  • is completely contained within the router
  • a network inside of a network router!

Output Ports store packets received from the switching fabric and transmits these packets on the outgoing link

  • by performing the necessary link-layer and physical-layer functions

Routing Processor performs control-plane functions:

  • it executes the routing protocols (Sec5.3, 5.4)
  • maintains routing tables and attached link state information
  • computes the forwarding table for router
  • performs the network management functions (Sec5.7)

2.2 Input Port Processing

Line Termination is a physical-layer function:

  • for receiving the bit-level transmissions
  • over the physical medium such as copper, fiber or Wireless

Link-Layer Function assembles bits into link-layer frames

  • e.g. Ethernet Frames (chapter 6)

Lookup, Forwarding and Queueing are network-layer functions

  • Lookup and Forwarding: Routers determine the appropriate Output Port to which the arriving packet will be forwarded via the switching fabric by using header field values and forwarding table in input port memory
    • "match plus action"
  • Destination-based Forwarding: based ONLY on destination IP address (traditional)
  • Generalized Forwarding: based on any set of header field values (i.e. source IP address, header length, seq #...)
  • Decentralized Switching: The forwarding table is copied from the Routing Processor to the Input Line Cards over a separate bus
    • Goal: Forwarding decisions can be made locally, complete Input Port Processing at line speed to avoid a centralized processing bottleneck
  • Queueing: if datagrams arrive faster than forwarding rate into switch fabric

Destination-Based Forwarding with Longest Prefix Matching

In the case of 32-bit IP addresses, a brute-force implementation of the forwarding table would have one entry for every possible destination address

  • there are more than 4 billion possible addresses and we need Link Interfaces to manage

Longest Prefix Matching is used to match destination address when looking for forwarding table entry for given destination address

  • Ternary Content Addressable Memories (TCAMs) are often used for lookup
    • a 32-bit address is presented to the memory, which returns the content of the forwarding table entry for that address in essentially constant time, regardless of table size
  • Cisco Catalyst Routers and Switches can hold upwards of a million TCAM forwarding table entries

2.3. Switching

Switching Fabrics forward packets from a Input Link to an appropriate Output Link

  • switching rate is often measured as multiple of input/output line rate R and N inputs/outputs
  • Rate => NR ideally

Switching via Memory

The simplest, earliest routers were traditional computers

  • with switching under direct control of the CPU (routing processor)

Input and output ports functioned as Traditional I/O Devices in a traditional Operating System

  • an input port with an arriving packet first signaled the routing processor via an interrupt
  • then the packet wass copied from the input port into processor memory

The routing processor extracted the destination address from the header,

  • looked up the appropriate output port in the forwarding table
  • and copied the packet to the output port's buffers

Speed Limited by memory bandwidth

  • if the memory bandwidth is a maximum of B packets/sec can be written into or read from,
  • then the overall forwarding throughput must be less than B/2 since ONLY ONE memory read/write can be done at a time over the shared system bus

Switching via a Bus

An input port transfers a packet directly to the output port via a shared bus

Only ONE packet can cross the bus at a time, the switching speed of the router is limited to the bus speed

  • Roundabout Analogy: the roundabout could only contain one car at a time.
  • Nonetheless, switching via a bus is often sufficient for routers that operate in small local area and enterprise networks

Switching via an Interconnection Network

A crossbar switch is an interconnection network consisting of 2N buses that connect N input ports to N output ports

  • each vertical bus intersects each horizontal bus at a crosspoint, which can be opened or closed at any time by the switch fabric controller

A crossbar switch is Non-Blocking

  • a packet being forwarded to an output port will NOT be blocked from reaching that output port as long as NO other packet is currently being forwarded to that output port
  • however if two packets from different input ports are destined to the same output port, one will have to wait at the input since ONLY ONE packet can be sent over any given bus at a time

More sophisticated interconnection networks use multiple stages of switching elements

  • to allow packets from different input ports to proceed towards the same output port at the same time
  • through the multi-stage switching fabric.

A router's switching capacity can also be scaled by running multiple switching fabrics in parallel

  • an input port breaks a packet into K smaller chunks, and sends("sprays") the chunks though K of N switching fabrics to the selected output port,
  • which reassembles the K chunks back into the original packet

2.3. Queuing

As the queues grow large, the router's memory can eventually be exhausted and packet loss will occur when NO memory is available to store arriving packets.

Input Port Queuing

If switch fabric slower than input line speeds

  • => queuing may occur at input queues
  • queuing delay and loss due to input buffer overflow

Head-of-the-line(HOL) Blocking: Queued datagram at front of queue prevents others in queue from moving forward

Output Port Queuing

Buffering required when datagrams arrive from fabric faster than link transmission rate.

  • queueing delay and loss due to output port buffer overflow
  • Drop Policy: which datagrams to drop if NO free buffers?
    • tail drop: drop arriving packet
    • priority: drop/remove on priority basis
  • Marking Policy: which packets to mark to signal congestion
    • ECN: Explicit Congestion Notification (Recall Sec 3.7.2)
    • RED: Random Early Detection

Scheduling Discipline chooses among queued datagrams for transmission

How much Buffering is Enough

RFC 3429 Rule of Thumb: average buffering equal to "typical" RTT (= 250 msec) times link capacity C

  • e.g. C = 10 Gbps link => Amount of Buffering B = RTT x C = 2.5 Gbits of buffer

More recent recommendation: with N TCP flows, the amount of buffering equal to

Larger Buffers decrease the router's packet loss rate

  • but increase queueing delays
    • Increased RTT make TCP senders less responsive and slower to respond to incipient congestion and/or packet loss
  • Delay-Based congestion control: keep bottleneck link just full enough(busy) but NO fuller

2.4 Packet Scheduling

To decide which packet to send next on link

  • FIFO
  • Priority
  • Round Robin
  • Weighted Fair Queueing

First-in-First-Out (FIFO)

Under FIFO discipline, packets leave in the same order in which they arrived.

Priority Queuing

Under priority queuing, packets arriving at the output link are classified into priority classes upon arrival at the queue

  • any header fields can be used for classification
  • send packet from highest priority queue that has buffered packets
  • FIFO within priority class

Round Robin

Under the round robin queuing discipline, packets are sorted into classes as with priority queuing.

  • a work-conserving queuing discipline looks for a packet of a given class but finds NONE will immediately check the next class in the round robin sequence

Weighted Fair Queueing

WFQ is a generalized form of Round Robin queuing that has been widely implemented in routers

  • each class, i, is assigned a weight, , and gets weighted amount of service in each cycle:

Minimum Bandwidth Guarantee

  • for a link with transmission rate R, class i will always achieve a throughput of at least

2.5 Network Neutrality

Three "clear, bright line" rules:

  • NO Blocking: shall not block lawful content, applications, services, or non-harmful devices, subject to reasonable network management
  • NO Throttling: shall not impair or degrade lawful internet traffic on the basis of internet content, application, or service, or use of a non-harmful device, subject to reasonable network management
  • NO Paid Prioritization: shall not engage in paid prioritization

Are Internet Service Providers(ISPs) telecommunications or information services?

  • the answer really matters from a regulatory standpoint!

References:
[1]http://gaia.cs.umass.edu/kurose_ross/index.html

董亦杨

2021/04/23  阅读:70  主题:自定义主题1

作者介绍

董亦杨