Looking up address bits in an arriving datagram header in the forwarding table

Analogous to TCP/UDP connecton-oriented / connectionless transport-layer services, but: - service: host-to-host - no choice: network provides one or the other - implementation: in network core

Virtual Circuits

source-to-dest path behaves much like telephone circuit

A VC consists of

1. path from source to destination
2. VC numbers, one number for each link along path
3. entries in forwarding tables in routers along path

packet belonging to VC carries VC number (rather than dest address)

VC number can be changed on each link. - new VC number comes from forwarding table

Signaling protocols

• used to serup maintian and teardown VC
• used in ATM, frame-relay
• not used in today's Internet

Datagram Networks

• no call setup at network layer
• routers: no state about end-to-end connections
  • no network-level concept of “connection”
• packets forwarded using destination host address

Datagram forwarding table

• Longest prefix matching: when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.

Router

There are two key router functions: - run routing algorithms/protocol (RIP, OSPF, BGP) - forwarding datagrams from incoming to outgoing link

Input port functions

Switching fabrics

Switching fabrics transfer packet from input buffer to appropriate output buffer.

Switching rate: rate at which packets can be transfer from inputs to outputs - often measured as multiple of input/output line rate - N inputs: switching rate N times line rate desirable

• Switching via memory: speed limited by memory bandwidth (2 bus crossings per datagram)
• bus contention: switching speed limited by bus bandwidth
• Switching via interconnection network: overcome bus bandwidth limitations

Output ports

• Buffering required when datagrams arrive from fabric faster than the transmission rate
• Scheduling discipline chooses among queued datagrams for transmission

Output port queueing

Fabric slower than input ports combined -> queueing may occur at input queues - queueing (delay) and loss due to output port buffer overflow!

Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forward

IP: Internet Protocol

IP datagram format

IPv4 Datagram Format.

IP fragmentation

Maximum Transmission Unit (MTU): largest possible link-level frame.

• different link types have different MTUs

large IP datagram divided (“fragmented”) within net

• one datagram becomes several datagrams
• “reassembled” only at final destination
• IP header bits used to identify, order related fragments

e.g. We have a 4000 byte datagram with MTU = 1500 bytes

FragmentsLengthIDOffsetFragflat11500x0121500x185131020 (=3980-1480-1480)x3700

IP addressing

Classless InterDomain Routing (CIDR) - subnet portion of address of arbitrary length - address format: a.b.c.d/x, where x is # bits in subnet portion of address

Subnets

• What's a subnet?
  • device interfaces with same subnet part of IP address
  • can physically reach each other without intervening router

How does a host get IP address?

• Dynamic Host Configuration Protocol (DHCP): dynamically get address from as server
• DHCP can return more than just allocated IP address on subnet:
  • address of first-hop router for client
  • name and IP address of DNS sever
  • network mask (indicating network versus host portion of address)

NAT: network address translation

motivation: local network uses just one IP address as far as outside world is concerned - range of addresses not needed from ISP - can change addresses of devices in local network without notifying outside world - can change ISP without changing addresses of devices in local network

ICMP: Internet Control Message Protocol

ICMP is used by hosts and routers to communicate network level information. - error reporting - echo request

ICMP message: type, code plus first 8 bytes of IP datagram causing error.

ICMP TypeCodeDescription00Response31Dest host not reachable..........

IPv6

Motivation

• initial motivation: 32-bit address space soon to be completely allocated.
• additional motivation:
  • header format helps speed processing/forwarding
  • header changes to facilitate QoS

Format

• fixed-length 40 byte header
• no fragmentation allowed
• priority: identify priority among datagrams in flow
• flow Label: identify datagrams in same “flow.”
• checksum: removed entirely to reduce processing time at each hop
• options: allowed, but outside of header, indicated by “Next Header” field
• ICMPv6: new version of ICMP

Tunneling

Tunneling: IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers

Routing ALgorithm

Routing algorithm classification

global vs decentralized

• global routing algorithm
  • all routers have complete topology, link cost info
  • “link state” algorithms
• decentralized routing algorithm
  • router knows physically-connected neighbors, link costs to neighbors
  • “distance vector” algorithms

static or dynamic

• statistic: routes change slowly over time
• dynamic: routes change more quickly

Link-State Routing Algorithm

Dijkstra’s algorithm

• Algorithm complexity:
• n(n+1)/2 comparison: \(O(n^2)​\)

StepN'vwxyz0u2, u5, u1, u++++1ux2, u4, x2, x++2uxy2, u3, y4, y3uxyv3, y4, y4uxyvw4, y5uxyvwz

Distance vector

\(d_x(y)=\min\{c(x,v)+d_v(y)\}\)

link cost changes: - node detects local link cost change - bad news travels slow - “count to infinity” problem! - 44 iterations before algorithm stabilizes

Hierarchical Routing

• We have scale with 600 million destinations, and we cannot store all dest's in routing tables.
• administrative autonomy: each network admin may want to control routing in its own network

Autonomous systems (AS): aggregate routers into regions - intra-AS routing protocol is routers in same AS run same routing protocol. - routers in different AS can run different intra-AS routing protocol

** Gateway router** has link to router in another AS.

Routing in the Internet

RIP (Routing Information Protocol)

It uses distance vector algorithm - distance metric: # hops (max = 15 hops), each link has cost 1 - DVs exchanged with neighbors every 30 sec in response message (aka advertisement) - each advertisement: list of up to 25 destination subnets (in IP addressing sense)

RIP routing tables managed by application-level process called route-d (daemon) - sent in UDP packets, periodically repeated.

OSPF (Open Shortest Path First)

It uses link state algorithm - LS packet dissemination - topology map at each node - route computation using Dijkstra’s algorithm

advertisements flooded to entire AS - carried in OSPF messages directly over IP (rather than TCP or UDP

IS-IS routing protocol: nearly identical to OSPF

BGP (Border Gateway Protocol)

BGP provides each AS a means to: - eBGP: obtain subnet reachability information from neighboring ASs. - iBGP: propagate reachability information to all AS-internal routers.

Where in a router is the destination IP address looked up in a forwarding table to determine the appropriate output port to which the datagram should be directed?

What is the role of the forwarding table within a router?

What are three IP datagram header fields that Cannot be matched in OpenFlow?

What helps us to get the network layer address for a host?