Comparison of Link State and Distance Vector Algorithms
(Robustness)
(What happens if router malfunctions?)
(DV)

Hierarchical Routing
(Our routing study so far is an idealization)

Hierarchical Routing
(Scale (50 million destinations!))

Hierarchical Routing
(Administrative autonomy)

Hierarchical Routing: Autonomous Systems

Hierarchical Routing: Autonomous Systems
(Gateway Routers)

Inter-AS and Intra-AS Routing

Routing in the Internet
(The Global Internet consists of Autonomous Systems (AS) interconnected with each other)
(Stub AS)

Routing in the Internet
(The Global Internet consists of Autonomous Systems (AS) interconnected with each other)
(Multihomed AS)

Routing in the Internet
(The Global Internet consists of Autonomous Systems (AS) interconnected with each other)
(Transit AS)

Routing in the Internet
(Two-level routing)
(Intra-AS)

Routing in the Internet
(Two-level routing)
(Intra-AS)
(RIP)

Routing in the Internet
(Two-level routing)
(Intra-AS)
(OSPF)

Routing in the Internet
(Two-level routing)
(Intra-AS)
(IGRP)

Routing in the Internet
(Inter-AS)

Routing in the Internet
(Inter-AS)
(BGP)

Why Having Different Inter- and Intra-Domain Routing?
(Policy)
(Inter-AS)

Why Having Different Inter- and Intra-Domain Routing?
(Policy)
(Intra-AS)

Why Having Different Inter- and Intra-Domain Routing?
(Scale)

Why Having DIfferent Inter- and Intra-Domain Routing?
(Performance)
(Intra-AS)

Why Having DIfferent Inter- and Intra-Domain Routing?
(Performance)
(Inter-AS)

Interconnected Autonomous Systems

Inter-AS Tasks

Example: Setting Forwarding Table in Router 1d
(refers to picture at "Inter-AS Tasks")

Example: Choosing Among Multiple ASes
(refers to picture at "Inter-AS Tasks")

Example: Choosing Among Multiple ASes
(refers to picture at "Inter-AS Tasks")

Intra-AS Routing

Intra-AS Routing
(Most common Intra-AS routing protocols)

RIP (Routing Information Protocol)
(Basic characteristics)

RIP (Routing Information Protocol)
(Bild)

RIP Advertisements
(Distance vectors)

RIP Advertisement
(Each advertisement)

RIP: Example
(1)

RIP: Example
(2)

RIP: Link Failure and Recovery
(If no advertisement heard after 180 sec => neighbour/link declared dead)

RIP Table Processing

OSPF (Open Shortest Path First)
(Uses Link State algorithm)

OSPF (Open Shortest Path First)
(OSPF advertisement carries one entry per neighbour router)

OSPF "Advanced" Features (not in RIP)
(Security)

OSPF "Advanced" Feature (not in RIP)

OSPF "Advanced" Features (not in RIP)
(Integrated uni- and multicast support)

Hierarchical OSPF
(Bild)

Hierarchical OSPF
(Two-level hierarchy)

Hierarchical OSPF
(Area border routers)

Hierarchical OSPF
(BAckbone routers)

Hierarchical OSPF
(Boundary routers)

Internet Inter-AS Routing: BGP

Internet Inter-AS Routing: BGP
(BGP provides each AS a means to)

BGP Basics

BGP Basics
(Bild)

Distributing Reachability Info

Path Attributes & BGP Routes

Path Attributes & BGP Routes
(AS-PATH)

Path Attributes & BGP Routes
(NEXT-HOP)

BGP Route Selection

BGP Route Selection
(Elimination rules)

BGP Messages

BGP Messages
(BGP Messages)
(OPEN)

BGP Messages
(BGP Messages)
(UPDATE)

BGP Messages
(BGP Messages)
(KEEPALIVE)

BGP Messages
(BGP Messages)
(NOTIFICATON)

BGP Routing Policy
(1)

BGP Routing Policy
(2)

Routing Table Sizes for Internet AS

Network Layer: Summary

Transport Services and Protocols

Transport Services and Protocols
(Sending side)

Transport Services and Protocols
(Receiving side)

Transport Services and Protocols
(Bild)

Transport vs. Network Layer
(Network layer)

Transport vs Network Layer
(Transport layer)

Transport vs. Network Layer
(Household analogy)

Internet Transport-Layer Protocols
(Reliable)

Internet Transport-Layer Protocols
(Unreliable)

Internet Transport-Layer Protocols
(Services not available)

Internet Transport-Layer Protocols
(Bild)

Addressing and Multiplexing

Addressing and Multiplexing
(e.g. "port numbers")

Addressing and Multiplexing
(Bild)

Multiplexing/Demultiplexing
(Multiplexing at send host)

Multiplexing/Demultiplexing
(Demultiplexing at rcv host)

Multiplexing/Demultiplexing
(Bild)

How Demultiplexing Works
(Host receives IP datagrams)

How Demultiplexing Works

How Demultiplexing Works
(Bild)

Connectionless Demultiplexing
(1)

Connectionless Demultiplexing
(2)

Connection-Oriented Demultiplexing
(1)

Connection-Oriented Demultiplexing
(2)

Connection-Oriented Demux: Threaded Web Server

Connection Control
(two types of communication)

Connection Control
(phases of a connection)

Connection Control
(When talking about the service of a specific layer, we usually add a layer specific prefix to the primitives, e.g.)

Transport Connections and End-System "Connectivity"

Transport Connection Establishment (OSI Terminology)
(Primitive)

Transport Connection Establishment (OSI Terminology)
(Parameters)
(Destination Address)

Transport Connection Establishment (OSI Terminology)
(Parameters)
(Source Address)

Transport Connection Establishment (OSI Terminology)
(Parameters)
(Responding Address)

Transport Connection Establishment (OSI Terminology)

Transport Layer Services in a Message Sequence Chart

Data Transfer Service

Connection Release
(Unconfirmed release service)

Connection Release
(Usage)

Connection Release
(Primitives)

Connection Release
(Parameters)
(Cause of the teardown, e.g.)

Connection Release
(Parameters)
(User Data)

Connection Release
(Bild)

State Diagram for a Transport Service Access Point
(Bild)

Error during Connection Establishment

Three-Way Handshake

Is Three-Way Handshake Sufficient?
(Problem)

Is Three-Way Handshake Sufficient?
(Solution)

Three-Way Handshake + Sequence Numbers
(Two examples for critical cases (which are handled correctly))
(Connection request appears as an old duplicate)

Three-Way Handshake + Sequence Numbers
(Two examples for critical cases (which are handled correctly))
(Connection request & confirmation appear as old duplicates)

Connection Rejection

Connection Release
(Normal Release)

Connection Release
(Normal Release)
(Variants)
(Implicit)

Connection Release
(Normal Release)
(Variants)
(Explicit)

Connection Release
(Bild)

Connection Release

Connection Release
(Problem)

Connection Release
(Analogy)

Two Army Problem
(Coordinated attack)

Two Army Problem
(Bild)

Connection Release in Practice

Connection Release in Practice
(Bild)

Problem Cases for Connection Release with 3WHS

Motivation: Controlling Overload Situations
(usually, multiple systems are involved in a communication taking place)

Motivation: Controlling Overload Situations
(In order to avoid overload situations)

Bottlenecks in Communication Systems

Bottleneck in Receiver
(Assumption)

Bottleneck in Receiver
(Reasons for bottleneck in receiver)

Bottleneck in Receiver
(Consequences)

Bottleneck in Receiver
(Bild)

Example: Buffer Overflow in a Point-to-Point Connection

Flow Control
(Task)

Flow Control
(Where provided)

Flow Control
(But, flow control in transport layer is more complicated)

Flow Control - Buffer Allocation

Flow Control - Buffer Allocation
(How does sender have buffer assurance?)

Flow Control with Stop and Continue Messages
(Easiest solution)

Flow Control with Stop and Continue
(Example: XON/XOFF Protocol)

Flow Control with Stop and Continue Messages
(Bild)

Implicit Flow Control
(Idea)

Implicit Flow Control
(Drawback)

Implicit Flow Control
(Bild)

Credit Based Flow Control
(Idea)

Credit Based Flow Control
(Implementation alternatives)
(Absolute credit)

Flow Control - Permits and Acknowledgements
(Distinguish)

Flow Control - Permits and Acknowledgments

Credit Based Flow Control: Sliding Window

One More Example of Flow Control with ACK/Permit Separation

Why Congestion Control?
(Recall overload in network)

Why Congestion Control?

Why Congestion Control?
(Bild)

Causes/Costs of Congestion: Scenario 1

Causes/Costs of Congestion: Scenario 2
(1)

Causes/Costs of Congestion: Scenario 2
(2)

Causes/Costs of Congestion: Scenario 2
("Costs" of congestion)

Causes/Costs of Congestion: Scenario 3
(1)

Causes/Costs of Congestion: Scenario 3
(2)

Intermediate Summary: Need For Congestion Control

Adapt Sending Rate to Network Capacity

Adapt Sending Rate to Network Capacity
(Global Issue)

Adapt Sending Rate to Network Capacity
(Bild)

Desirable Properties of Congestion Control

Desirable Properties of Congestion Control
(Fairness)

Desirable Properties of Congestion Control
(Bild)

Design Options for Congestion Control Mechanisms
(Open loop)

Design Options for Congestion Control Mechanisms
(Closed loop)

Design Options for Congestion Control Mechanisms
(Explicit feedback)

Design Options for Congestion Control Mechanisms
(Implicit feedback)

Design Options for Congestion Control Mechanisms
(Bild)

Possible Actions
(Increase capacity)

Possible Actions
(Reservations)

Possible Action
(Reduce load at smaller granularity)

Possible Actions - Taxonomy
(Router-centric vs. host-centric)
(Where is/are information gathered, decisions made, actions taken?)

Possible Actions - Taxonomy
(Window-based vs. rate-based)
(How is the allowed amount of traffic injected into the network described?)

Possible Actions - Taxonomy
(Window-based vs. rate-based)

Router Actions: Dropping Packets

Router Actions: Dropping Packets
(One candidate: the newly arriving packet)

Router Actions: Dropping Packets
(Other option: a packet that is already in the queue for quite some time)

Dropping Packets = Implicit Feedback
(Dropping a packet constitutes an implicit feedback action)

Dropping Packets = Implicit Feedback

Avoiding Full Queues - Proactive Actions?

Avoiding Full Queues - Proactive Actions?
(Provide proactive feedback! (Congestion avoidance))

Proactive Action: Choke PAckets

Proactive Action: Warning Bits

Proactive Actions: Random Early Detection (RED)

Proactive Actions: Random Early Detection (RED)
(Bild)

What Happens After Feedback Has Been Received?

What Happens After Feedback Has Been Received?
(Rate-based protocols)

What Happens After Feedback Has Been Received?
(Window-based protocols)

UDP: User Datagram Protocol [RFC 768]

UDP: User Datagram Protocol [RFC 768]
(Connectionless)

UDP: User Datagram Protocol [RFC 768]
(Why is there a UDP?)

User Datagram Protocol

UDP Checksum
(Goal)

UDP Checksum
(Sender)

UDP Checksum
(Receiver)