Future Internet lecture notes.

00_infos.md

Infos

Future Internet

01_switches.md

Switches

• IP lookup: longest prefix match
  • parallelize DRAM access to acive acceptable access times
• TDM Time Division Multiplexing
• WDM Wavelength Division Multiplexing
• POP Point of Presence
• Buffer Memory
  • SRAM Shadowed RAM -> fast but small
  • DRAM Dynamic RAM -> large but slow
• OQ Output Queueing Switch
  • no intermediate buffer
  • flows on different out port do not affect each other
  • work conserving
  • highest throughput, lowest average delay
• IQ Input Queueing Switch

  • packets are released when access to switching fabric and out port is guaranteed

  • HOL Head of Line Blocking

    Troughput is not maximized, because possibly outgoing packets can be blocked queued packets from other out ports.

    • VOQ Virtual Output Queue

      Input buffer is devided in N vitual output buffers

      • non uniform, unknown traffic

        • MWM Maximum Weight Matching

        • Maximum Size Matching

          Find largest number of edges, such that each node has at most one edge.

        • Maximal Size Matching

          Add edges until the next edge would destroy the matching property.

            |M_maximum| / 2 <= |M_maximal| <= |M_maximum|
          

        • LQF Longest Queue First

        • OCF Oldest Cell First

• Shared Memory Switch
• FIFO First In First Out Queue
  • favor the most greedy flow
• GPS Generalized Processorr Sharing
  • Weighted Bit-by-Bit Fair Queueing
  • per flow queueing with bitwise round robin
• Packetized GPS
  • calculate a packets finishing round R using GPS, serve packets in order of increased finishing time
• WFQ Weighted Fair Queueing
  • Packetized GPS with weighted flows
  • gives packets incentive to behave well, packets are lost if a source is sending to much
  • drawback: complexity O(log N) for N active flows
• DRR Deficit Round Robin
  • approximation of WFQ
  • complexity O(1)
• Hybrid Memory Architecture
  • MDQF Most Deficit Queue First
  • ECQF Earliest Critical Queue First
  • MDQFL Maximum Deficit Queue First with Latency

02_bufferspace.md

Bufferspace

• Reasons for

  • large buffers
    • smooth variation in incomming traffic
  • small buffers
    • TCP fixes the botleneck

• M/M/1 queue

• M/G/1 queue

• TCP congestion-avoidance algorithm

  • ACK clocking

    • ACK permits to inject the corresponding amount of data

  • AIMD Aidditive Increase Multiplicative Decrease

  • Loss is detected by tripple acknowledge

  • TCP Tahoe

  • TCP Reno EVENT STATE ACTION

      ACK         ss      window *= 2
                          if window > threshold: STATE = ca
      ACK         ca      window += MSS
      LOSS        -       threshold = window / 2
                          window = threshold
                          STATE = ca
      TIMEOUT     -       threshold = window / 2
                          window = MSS
                          STATE = ss
      ss slow start
      ca congestion avoidance
    

  • TCP Cubic

  • TCP Slow Start, Congestion Avoidance, Fast Retransmit

  • Paced TCP: no bursts, fixed rate at W/RTT

  • Short flow: never leaves slow start

• TCP flows will synchronize

• Rule of Thumb

  • On synchronized flows, buffer size should be at least bandwidth-delay product. B >= 2 * Tp * C
  • On asynchronous flows, buffer size should be only square root of number of flows of rule of thumb. B >= sqrt(N * 2 * Tp * C)
  • C ideal packet rate
  • RTT Round Trip Time (Tp)
    • time between SEND and ACK
  • W congestion window
  • W* packets in flight when loss detected

03_circuit_switching.md

Circuit Switching

• ATM Asynchronous Transfer Mode
  • VC Virtual Circuit
  • VCI Virtual Circuit Identifier
    • unique per switch, switch swaps the VCI using translation table
      • (InPort, InVCI) -> (OutPort, OutVCI)
  • Fixed packet size: 48 bytes payload + 5 bytes header
  • Statistical Multiplexing
  • Integrated Services (voice, data, ...)
  • evolved to MPLS
• MPLS Multi-Protocol Label Switching
  • Label instead of VCI
  • support varying payload
  • tunnel arbtrary network layer protocols
  • shim header Label, QoS, StackBit, TimeToLive
  • LSR Label Switched Router
    • replace label
    • insert label
    • remove label
    • if last header is removed, pass packet to contained protocol
  • LER Label Edge Router
    • FEC Forward Equivalent Class
      • set of packets to be treated similar, decided on arrival at LER
    • LSP Label Switched Path
      • LER insters shim header with the Label of the LSP
  • Distributed
    • LER decides on the path
  • Centralized

    • routing decissions made at central instance and distributed to routers

    • PCE Path Computation Element

      • entity that is able to compute a network path or route

      • PCC Path Computation Client (typically LER)

        1. requests path to destination
        2. computes path and returns it 3.PCC requests path

    • makes more sense in a circuit switched environment than in packet switched

    • TED Traffic Engineering Database

    • TE LSP Traffic Engineering MPLS Label Switched Path

    • Domain collections of network elements with common management

    • NMS Network Management System GMPLS Generalized MPLS

• Optical networking
  • Transmitters
    • light emitting diodes
    • simple laser
    • tunable lasers
  • Directional Coupler
    • combines/splits signal from input to output
  • Isolator
    • only one-directionla
  • Circulator
    • combination of isolators to multiple inputs/outputs
  • Multiplexer/Filter
    • based on frequency
  • MZI Mach-Zehnder Interferometer
  • AWG Arrayed Wavelength Grating
    • routes signals based on their wavelength
  • Wavelength converter
  • WDM Wavelenght Division Multiplexing
    • OADM Optical Add/Drop Multiplexer
    • OCX Optical Crossconnect
    • wavelength
      • reuse
      • conversion
  • LTD Light Path Topology Design
    • MILP problem is NP-hard
  • RWA Routing and Wavelength Assignment
    • MILP solution is linear relaxation
  • WDM Dimensioning
    • First-passage model
      • light path requests overload network at time T, how to postpone T
    • Blocking model
      • incomming requests = outgoing request, server as many as possible
  • Photonic Package Switching
    • how to buffer a photon

04_software_defined_networking.md

Software Defined Networking

• Flow

  • Microflow
    • fine grain controll
  • Aggregated
    • large number of flows
  • reactive
    • first packet creates table entry
  • proactive
    • table is populated before packet arrival

• FSL Flow Based Security Language

  • allow
  • deny
  • waypoint

• OpenFlow

  • Flow Table
    • Rule
      • Switch Port | MAC Src | MAC Dst | Eth Type | VLAN ID | IP Src | IP Dst | IP Prot | TCP Src Port | TCP Dst Port
    • Packet Action
      • Forward to port
      • Encapsulate and forward to controller
      • Drop
      • Send to normal processing pipeline
    • Statistics
      • PAcket and byte counter to determine dead flows
  • Limitations
    • No per-packet routing
    • use all tables on switch chips
    • New forwarding primitives
    • New packet format/field definitions
    • Optical circuits
    • Low-setup-timeindividual flows

• Scalability

  • Controller scalability
  • Link failure recovery
  • Onyx
    • A platform on top of which a network control plane can be implemented as a distributed system.
    • global view of the network
    • basic state distribution
    • Network information bas
      • Partitioning: partition state over multiple controllers
      • Aggregation: group network elements
      • Consistency
  • Kandoo
    • two layers of controllers
      1. bottom, local view
         • no interconnection,
         • no knowledge of the network state
      2. top, global view
         • logically centralized controller
    • Difference to Onyx: no consistency
  • DevoFlow
    • Reduce global visibility in OpenFlow to reduce overhead.
    • Only use controller for large flows (elephants)
    • Rule cloning
      • update counters on the clone
    • Local actions
      • switch between alternative ports
  • Controller placement
    • NP-hard
    • Maximum cover: greedy has the best approximation

• Programming

  • Frenetic
  • Procera

05_data_center_networking.md

Data Center Networking

• Requirements

  • Uniform high capacity
  • Performance isolation
  • Ease of management: Plug-&-Play
  • Scalable, easy manageble, fault tolerant
    1. VM migration without IP change
    2. No switch configuration before deployment
    3. Efficient communication between all end hosts
    4. No forwarding loops
    5. Rapid failure detection

• Topologies

  • ToR connects end host to one or more EoR
  • ToR Top of Rack Switch
  • EoR End of Row Switch
  • OSPF Open Shortest Path First
    • A link-state routing protocol for IP networks
  • Full Mesh Network
  • Basic Tree Topology
  • Fat Tree Topology
  • Clos Networks
    • n-Stage Clos
    • Folded Clos
  • Data Center Fabric
    • SPB Shortest Path Bridge
    • Virtual Chassis
    • MLAG Multi-chassis Link Aggregation
    • TRILL Transparent Interconnection of Lots of Links
  • PMAC Pseudo MAC
    • encodes the location of the host
  • Taxonomy
    • Fixed Topology: electrical
    • Flexible Topology: optical/hybrid
      • Switch from electrical packet switched to optical flow switched on detection of large flows

• LACP Link Aggregation Control Protocol

• Layer 3 (Network Layer)

  • IP

• Layer 2 (Data link layer)

  • MAC

• ECMP Equal-cost multi-path routing

  • packet forwarding to a single destination can occur over multiple best paths

06_information-centric_networking.md

Information-Centric Networking

• Functions of the internet

  • distribute
  • interact
  • notify

• Most volume: static content

• Internet architecture: host centric/id-centric communication style

  • bad for content distribution
  • disemination is inefficient
  • security is host-centric

• Benefits of content-centric networking

  • reduce congestion
  • improve delivery speed
  • simplify configuration
  • security at data level

• packet-level cache present at each node

• Naming objects

  • hierarchical or flat namespace

• NetInf

• Security

  • PKI Public Key Infrastructur

• CCN Content-centric networking

• ICN Information-centric networking

• NDN Named data networking