Telematik Chapter 7

Description

Flashcards on Telematik Chapter 7, created by Julian Rottenberg on 19/06/2018.
Julian Rottenberg
Flashcards by Julian Rottenberg, updated more than 1 year ago
Julian Rottenberg
Created by Julian Rottenberg almost 6 years ago
15
0

Resource summary

Question Answer
Network Layer: The Big Picture - Transport segment from sending to receiving host - On sending side encapsulates segments into datagrams - On receiving side, delivers segments to transport layer - Network layer protocols in every host, router - Router examines header files in all IP datagrams passing through it
Network Layer: The Big Picture (Bild)
Key Network-Layer Functions (Forwarding) - Move packet from router's input to appropriate router output (Analogy: - Process of getting through single interchange)
Key Network-Layer Functions (Routing) - Determine rout taken by packets from source to destination -> Routing algorithms (Analogy: -Process of planning trip from source to destination)
Forwarding (How do you get a packet from one network to another?)
Forwarding: Example
Searching the Routing Table 1.: search for a matching host address -> Flag H is set 2.: search for a matching network address -> Need to know the number of bits to use for network ID 3.: Search for a default entry -> Execute 'netstat -rn' on your machine and find the contents of the routing table -> Default entry allows for a single entry for a list of entries that have the same next-hop value
Search the Routing Table (How is the information stored in this routing / forwarding table obtained?) - This is the task of a routing algorithm
Interplay Between Routing and Forwarding (Summary)
Connection Setup (3rd important function in some network architectures) - ATM, Frame Relay, X.25
Connection Setup - Before datagrams flow, two hosts and intervening routers establish virtual connection -> Routers get involved and establish state for the virtual connection => In the Internet, there is no connection setup in the network layer
Connection Setup (Network and transport layer connection service) - Network: between two hosts - Transport: between two processes
Network Service Model (What service model for "channel" transporting datagrams from sender to receiver?) (example services for individual datagrams) - Guaranteed delivery - GUaranteed delivery with less than 40 msec delay
Network Service Model (What service model for "channel" transporting datagrams from sender to receiver?) (Example services for a flow of datagrams) - In-order datagram delivery - Guaranteed minimum bandwidth to flow - Restrictions on changes in inter-packet spacing
Network Layer Service Models
Network Layer Connection and Connectionless Service - Datagram network provides network-layer connectionless service - VC network provides network-layer connection service - Analogous to the transport-layer services but: - Service: host-to-host - No choice: network provides one or the other - Implementation: in the core
Virtual Circuits
VC Implementation (A VC consists of) - Path from source to destination - VC numbers, one number for each link along path - Entries in forwarding tables in routers along path
VC Implementation - Packet belonging to VC carries a VC number - VC number must be changes on each link -> New VC number comes from forwarding table
Forwarding Table
Virtual Circuits: Signaling Protocols - Used to setup, maintain teardown VC - Used in ATM, frame-relay, X.25 - Not used in today's Internet
Virtual Circuits: Signaling Protocols (Bild)
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 -> Packets between same source-dest pair may take different paths
Datagram Networks (Bild)
Forwarding Table
Longest Prefix Matching
Datagram or VC Network: Why? (Internet) - Data exchange among computers -> "Elastic" service, no strict timing req. - "Smart" end systems (computers) -> Can adapt, perform control, error recovery -> Simple inside network, complexity at "edge" - Many link types -> Different characteristics -> Uniform service difficult
Datagram or VC Network: Why? (ATM) - Evolved from telephony - Human conversation: -> Strict timing, reliability requirements -> Need for guaranteed service - "Dumb" end systems -> Telephones -> Complexity inside network
Router Architecture Overview (Key router functions) - Run routing algorithms/protocol (RIP, OSPF, BGP) - Forwarding datagrams from incoming to outgoing link
Router Architecture Overview (Bild)
Input Port Functions
Three Types of Switching Fabrics
Switching Via Memory (First generation routers) - Traditional computers with switching under direct control of CPU - Packet copied to system's memory - Speed limited by memory bandwidth (2 bus crossing per datagram)
Switching Via Memory (Bild)
Switching Via a Bus - Datagram from input port memory to output port memory via a shared bus - Bus contention: switching speed limited by bus bandwidth - 1Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone)
Switching Via a Bus (Bild)
Switching Via An Interconnection Network - Overcome bus bandwidth limitations - Banyan networks, other interconnection nets initially developed to connect processors in multiprocessor - Advanced design: fragmenting datagram into fixed length cells, switch cells through the fabric - Cisco 12000 series: switches Gigabits per second (Gbps) through the interconnection network -> Cisco 12816: up to 1.28 Tbps, 16 slots with 40 Gbps (full duplex)
Switching Via An Interconnection Network (Bild)
Output Ports (Buffering) - Buffering required when datagrams arrive from fabric faster than the transmission rate
Output Ports (Scheduling discipline) - Scheduling discipline chooses among queued datagrams for transmission
Output Ports (Bild)
Output Port Queueing - Buffering when arrival rate via switch exceeds output line speed - Queuing (delay) and loss due to output port buffer overflow!
Output Port Queueing (Bild)
Input Port Queueing - Fabric slower than input ports combined -> queueing may occur at input queues - Head-of0-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forward - Queueing delay and loss due to input buffer overflow!
Input Port Queueing (Bild)
The Internet Network Layer (Host & router network layer functions)
IP Packet Format (Bild)
IP Packet Format (Version) - The IP version number (currently still 4 even though 6 exists)
IP Packet Format (IHL) - IP Header Length in 32-bit-words
IP Packet Format (Type of Service) - Contains priority information, rarely used
IP Packet Format (Total Length) - The total length of the datagram in bytes (incl. header)
IP Packet Format (Identification) - When an IP packet is segmented into multiple fragments, each fragment is given the same identification; this field is used to reassemble fragments
IP Packet Format (Flag) - DF: Don't Fragment - MF: More Fragments; when a packet is fragmented, all fragments except the last one have this bit set
IP Packet Format (Fragment Offset) - The fragment's position within the original packet (specified in units of 8 octets)
IP Packet Format (Time to Live) - hop count, decremented each time the packet reaches a new router; when hop count = 0, packet is discarded
IP Packet Format (Protocol) - Identifies which transport layer protocol is being used for this packet (most of the time: either TCP or UDP)
IP Packet Format (Header Checksum) - Allow to verify the contents of the IP header (not polynomial-based)
IP Packet Format (Source and Destination Addresses) - Uniquely identify sender and receiver of the packet
IP Packet Format (Options) - Up to 40 bytes in length; used to extend functionality of IP (examples: source routing, record route)
IP Packet Format (IP addresses) - 32 bit long (4 bytes) - Each byte is written in decimal in MSB order, separated by decimals (example: 128.195.1.80) - 0.0.0.0 (lowest) to 255.255.255.255 (highest) - Address Classes: Class A, B, C, D, E, Loopback, Broadcast
IP Fragmentation & Reassembly - Network links have MTU (max.transfer size) - largest possible link level frame -> Different link types, different MTUs - Large IP datagram divided ("fragmented") within net -> One datagram becomes several datagrams -> "Reassembled" only a final destination -> IP header bits used to identify, order related fragments
IP Fragmentation & Reassembly (Bild)
IP Fragmentation and Reassembly (Example)
Addressing - Failure of Simple Addresses - Think back to the MAC/LLC layer: Each device has a globally unique MAC address
Addressing - Failure of Simple Addresses (How did spanning tree algorithm for bridges work?) - Each bridge had to store a separate entry for each device to which it was routing packets - Lot's of memory, CPU overhead (for searching) => Clearly, this does not scale to large networks
Addressing and Hierarchical Routing
"Closeness" - A note of caution: Closeness <> proximity
"Closeness" (Proximity) - Nearby physical location
"Closeness" (Closeness) - Structurally, logically within a short distance (e.g., in number of hops) -> Closeness is not a standard nomenclature
Internet Names and Addresses
IP Address Classes
IP Address Classes (Class A-E, Loopback, Broadcast)
IP Address Classes (Address Hierarchy) - Each address contains a network and a host portion, meaning two levels of hierarchy - Note that a Class A, Class B, and Class C addresses only support two levels of hierarchy - However, the host portion can be further split into "subnets" by the address class owner
IP Addressing: Introduction (IP address) - 32-bit identifier for host, router interface
IP Addressing: Introducing (Interface) - connection between host/router and physical link -> Router's typically have multiple interfaces -> Host may have multiple interfaces -> IP addresses associated with each interface
IP Addressing: Introduction (Bild)
Subnets (IP address) - Subnet part (high order bits) - Host part (low order bits)
Subnets (What's a subnet?) - Device interface with same subnet part of IP address - Can physically reach each other without intervening router
Subnets (Bild)
Subnets (Recipe) - To determine the subnets, detach each interface from its host or router, creating islands of isolated networks. Each isolated network is called a subnet.
Subnets (Recipe - Bild)
Subnets (How many?)
IP Addresses (Class-full addressing - Bild)
IP Addresses (Classful addressing) - Inefficient use of address space, address space exhaustion - E.g., class B net allocate enough addresses for 65K host, even if only 2K hosts in that network
IP Addresses (CIDR: Classless InterDomain Routing) - Network portion of addresses of arbitrary length - Address format: a.b.c.d/x, where x is # bits in network portion of address
IP Addresses (CIDR: Classless InterDomain Routing - Bild)
CIDR: Classless Interdomain Routing (Bild)
CIDR: Classless Interdomain Routing (Example) - All sites in Europe common prefix -> Only single entry in most U.S. routers
CIDR: Classless Interdomain Routing (Details) - RFC 1519: Supernet address extensions and CIDR
IP Addresses: How to Get One? (How does host get IP address?) - Hard-coded by system admin in a file -> Wintel (short for Windows/Intel): control-panel -> network -> configuration -> tcp/ip -> properties - UNIX: /etc/rc.config
IP Addresses: How to Get One? (DHCP) - Dynamic Host Configuration Protocol: dynamically get address from a server -> "plug-and-play"
IP Addresses: How to Get One? (How does network get subnet part of IP addr?) - gets allocated portion of its provider ISP's address space
IP Addresses: How to Get One? (Bild)
Hierarchical Addressing: Route Aggregation
Hierarchical Addressing: MOre Specific Routes
IP Addressing: Allocation of Addresses (How does an ISP get block of addresses?) - ICANN: Internet Corporation for Assigned Names and Numbers -> Allocates addresses -> Manages DNS -> Assigns domain names, resolves disputes
NAT: Network Address Translation (Bild)
NAT: Network Address Translation (Basic Idea) - Main Motivation: Shortage of IP addresses - Basic Idea: -> Local network uses just one IP address as far as outside word is concerned -> No need to be allocated range of addresses from ISP - just one IP address is used for all devices
NAT: Network Address Translation (Further Advantages) - Main Motivation: Shortage of IP addresses - Further Advantages -> Can change addresses of devices in local network without notifying outside world -> Can change ISP without changing addresses of devices in local network -> Devices inside local net not explicitly addressable, visible by outside world (a security plus)
NAT: Network Address Translation (Outgoing datagrams: replace...) - Implementation - NAT router must: -> Outgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #) ... remote clients/servers will respond using (NAT IP address, new port #) as destination addr.
NAT: Network Address Translation (Remember (in NAT translation table)...) - Implementation - NAT router must: - Remember (in NAT translation table) every (source IP Address, port #) to (NAT IP address, new port #) translation pair
NAT: Network Address Translation (Incoming datagrams: replace...) - Implementation - NAT router must: - Incoming datagrams: replace (NAT IP address, new port #) in dest fields of every incoming datagram with corresponding (source IP address, port #) stored in NAT table
NAT: Network Address Translation
NAT: Network Address Translation (16-bit port-number filed) - 60,000 simultaneous connections with a single LAN-side address!
NAT: Network Address Translation (NAT is controversial) - Routers should only process up to layer 3 - Violates end-to-end principles -> NAT possibility must be taken into account by app designers, e.g., P2P applications - Address shortage should instead be solved by IPv6
Bridging the Final Addressing Gap: ARP (What happens once a packet at its destination network/LAN? - How to turn an IP address (which is all that is known about the destination) into a MAC address that corresponds to the MAC address?) - Simple solution: Yell! -> Broadcast on the LAN, asking which node has IP address x -> Node answers with its MAC address -> Router can then address packet to that MAC address - Address Resolution Protocol (ARP)
ARP Protocol: Same LAN (Network)
Routing to Another LAN
Routing to Another LAN
ICMP: Internet Control Message Protocol - Used by hosts & routers to communicate network-level information -> Error reporting: unreachable host, network, port, protocol -> Echo request/reply (used by ping)
ICMP: Internet Control Message Protocol (Network-layer "above" IP) - ICMP msgs carried in IP datagrams
ICMP: Internet Control Message Protocol (ICMP message) - type, code plus first 8 bytes of IP datagram causing error
ICMP: Internet Control Message Protocol (Bild)
Traceroute and ICMP
IP Version 6 (IPv6) (motivations) - Initial motivation: -> 32-bit address space soon to be completely allocated - Additional motivation: -> Header format helps speed processing/forwarding -> Header changes to facilitate QoS
IP Version 6 (IPv6) (IPv6 datagram format) - Fixed-length 40-byte header - No fragmentation allowed
IPv6 Header (Priority) - Identify priority among datagrams in flow
IPv6 Header (Flow Label) - Identify datagrams in same "flow" (concept of "flow" not well defined)
IPv6 Header (Next header) - Identify upper layer protocol for data
IPv6 Header (Bild)
IPv6: Other Changes from IPv4 (Checksum) - Removed entirely to reduce processing time at each hop
IPv6: Other Changes from IPv4 (Options) - Allowed, but outside of header, indicated by "Next Header" field
IPv6: Other Changes from IPv4 (ICMPv6) - new version of ICMP -> Additional message types, e.g. "Packet Too Big" -> Multicast group management functions
Transition From IPv4 To IPv6 (Problems) - Not all routers can be upgraded simultaneous -> No "flag days" (= day on which all systems commit a change)
Transition From IPv4 To IPv6 (How will the network operate with mixed IPv4 and IPv6 routers?) - IPv6 carried as payload in IPv4 datagram among IPv4 routers - Drawbacks: -> Additional IPv4 header -> Processing overhead at tunnel endpoints -> No preferential QoS treatment inside IPv4 tunnel
Tunnelling (Bild)
Recall: Interplay Between Routing and Forwarding (Bild)
Overview on Routing Algorithms (What are routing algorithms for?) - A router executes a routing algorithm to decide which output line an incoming packet should be transmitted on
Overview on Routing Algorithms (connection-oriented service) - In connection-oriented service, the routing algorithm is performed only during connection setup
Overview on Routing Algorithms (connectionless service) - In connectionless service, the routing algorithm is either performed as each packet arrives, or performed periodically and the results of this execution updated in the forwarding table
Overview on Routing Algorithms (Non-adaptive routing algorithms) - Non-adaptive routing algorithms: do not base their routing decisions on the current state of the network (example: flooding)
Overview on Routing Algorithms (Adaptive routing algorithms) - Adaptive routing algorithms: take into account the current network state when making routing decisions (examples: distance vector routing, link state routing)
Overview on Routing Algorithms (Remark) - Additionally, hierarchical routing can be used to make these algorithms scale to large networks
Flooding (Basic strategy) - Every incoming packet is sent out on every outgoing line except the one it arrived on - Problem: vast number of duplicated packets
Flooding (Reducing the number of duplicated packets - Solution 1) - Have a hop counter in the packet header; routers decrement each arriving packet's hop counter; routers discard a packet with hop count=0 - Ideally, the hop counter should be initialized to the length of the path from the source to the destination
Flooding (Reducing the number of duplicated packets - Solution 2) - Require the first router hop to put a sequence number in each packet it receives from its hosts - Each router maintains a table listing the sequence numbers it has seen from each first-hop router; the router can then discard packets it has already seen
Flooding: Possible Applications (Military applications) - Large number of router is desirable (all systems act as a router) - If one router is taken out (e.g. by a bomb) flooding will still get packets to their destinations
Flooding: Possible Applications (Distributed databases) - Simultaneous updates of multiple databases can be done with a single packet transmission
Flooding: Possible Applications (Networks with frequent topology changes) - Adhoc networks
Adaptive Routing Algorithms (Problems with non-adaptive algorithms) - If traffic levels in different parts of the subnet change dramatically and often, non-adaptive routing algorithms are unable to cope with these changes - Lots of computer traffic is bursty (~ very variable in intensity), but non-adaptive routing algorithms are usually based on average traffic conditions => Adaptive routing algorithms can deal with these situations
Adaptive Routing Algorithms ( Centralized adaptive routing) - One central routing controler
Adaptive Routing Algorithms (Isolated adaptive routing) - Based on local information - Does not require exchange of information between routers
Adaptive Routing Algorithms (Distributed adaptive routing) - Routers periodically exchange information and compute updated routing information to be stored in their forwarding table
Centralized Adaptive Routing (Basic strategy) - Routing table adapts to network traffic - A routing control center is somewhere in the network - Periodically, each router forwards link status information to the control centre - Best routes are dispatched to each router
Centralized Adaptive Routing (Problems) - Vulnerability - Scalability
Centralized Adaptive Routing (Problems - Vulnerability) - If the control centre goes down, routing becomes non-adaptive
Centralized Adaptive Routing (Problems - Scalability) - The control centre must handle a great deal of routing information, especially for larger networks
Isolated Adaptive Routing Algorithms (Basic idea) - Routing decisions are made only on the basis of information available locally in each router
Isolated Adaptive Routing Algorithms (Examples) - Hot potato - Backward learning
Isolated Adaptive Routing Algorithms (Hot potato routing) - When a packet arrives, the router tries to get rid of it as fast as it can by putting it on the output line that has the shortest queue - Hot potato does not care where the output line leads - Not very effective
Backward Learning Routing (Basic idea) - Packet headers include destination and source addresses; they also include a hop counter -> Learn from the data as packets pass by - Network nodes, initially ignorant of network topology, acquire knowledge of the network state as packets are handled
Backward Learning Routing (Algorithm)
Distributed Adaptive Routing (Routing Protocol - Goal) - Determine "good" path (sequence of routers) through network from source to dest.
Distributed Adaptive Routing (Graph abstraction for routing algorithms) - Graph nodes are routers - Graph edges are physical links -> Links cost: dealy, $ cost, or congestion level -> Path cost: sum of the link costs on the path
Distributed Adaptive Routing (Graph abstraction for routing algorithms - "Good" path) - Typically means minimum cost path - Other definitions possible
Distributed Adaptive Routing (Bild)
Decentralized Adaptive Routing Algorithm Classification (Decentralized Information) - Router knows physically-connected neighbours, link costs to neighbours - Iterative process of computation, exchange of info with neighbours - "Distance vector" algorithms -> RIP protocol -> BGP protocol ("path vector")
Decentralized Adaptive Routing Algorithm Classification (Global Information) - All routers have complete topology, link cost info - "Link state" algorithms -> Dijkstra's algorithm -> OSPF protocol
Decentralized Adaptive Routing Algorithm Classification (Static) - Routes change slowly over time
Decentralized Adaptive Routing Algorithm Classification (Dynamic) - Routes change more quickly -> Periodic update -> In response to link cost changes
Distance Vector Routing Algorithm (Iterative) - Continues until no nodes exchange info - Self-terminating: no "signal" to stop
Distance Vector Routing Algorithm (Asynchronous) - Nodes need not exchange info/iterate in lock step!
Distance Vector Routing Algorithm (Distributed) - Each node communicates only with directly-attached neighbours
Distance Vector Routing Algorithm (Distance Table data structure)
Example for Distance Table
Constructing Routing Table for Distance Table
Distance Vector Routing: Overview (Iterative, asynchronous) - Each local iteration caused by: -> Local link cost change -> Message from neighbour: its least cost path change from neighbour
Distance Vector Routing: Overview (Distributed) - Each node notifies neighbour only when its least cost path to any destination changes -> Neighbours then notify their neighbours if necessary
Distance Vector Routing: Overview (Each node)
Distance Vector Algorithm: Initialization
Distance Vector Algorithm: Main Loop
Distance Vector Algorithm: Example (1)
Distance Vector Algorithm: Example (2)
Distance Vector: Reaction to Link Cost Changes (Link cost changes) - Node detects local link cost change - Updates distance table - If cost change in the least cost path, notify neighbours - Good news travels fast - Bad news travels slow - "count to infinity" problem!
Distance Vector: Reaction to Link Cost Changes (1) (Bild)
Distance Vector: Reaction to Link Cost Changes (2) (Bild)
Distance Vector: Poisoned Reverse - If Z routes through Y to get to X: -> Z tells Y its (Z's) distance to X is infinite (so Y won't route to X via Z)
Distance Vector: Poisoned Reverse (Bild)
Link-State Routing (Linke state routing usually uses Dijkstra's algorithm) (Network topology, link costs known to all nodes) - Accomplished via "link state broadcast" - All nodes have same information
Link-State Routing (Input) - Input: a graph (V, E) with -> V being the set of vertices (nodes) -> E being the set of edges (links) -> A mapping c(v, w) representing the cost of edge (v, w) if (v, w) is in E (otherwise c(v, w) = infinity)
Dijkstra's Algorithm to Compute Shortest Path (Basic algorithm idea) - State with a set N containing only the source node s and incrementally add one node at a time, to which the shortest path can be determined with the knowledge available at that point in time - Initially, the shortest path to node v is estimated to be infinity for all vertices except the source vertex s
Dijkstra's Algorithm to Compute Shortest Path (Basic algorithm idea - In each step) - Select the node v not yet in the set N that can be reached from s with the cheapest estimated cost using only nodes, that are already in N - Include v in N - Update the estimates for all direct neighbours w of v if a path over v would be cheaper than the current estimate - When updating an estimate for node w, also memorize the predecessor node v leading to this estimate
Dijkstra's Algorithm to Compute Shortest Paths
Dijkstra's Algorithm to Compute Shortest Paths (Some remarks)
Dijkstra's Algorithm to Compute Shortest Paths (Estimate upgrade procedure)
Dijkstra's Algorithm to Compute Shortest Paths (Intuition behind this procedure)
Dijkstra's Algorithm in Pseudocode
Example Run of Dijkstra's Algorithm (1)
Example Run of Dijkstra's Algorithm (2)
Example Run of Dijkstra's Algorithm (3)
Example Run of Dijkstra's Algorithm (4)
Example Run of Dijkstra's Algorithm (5)
Example Run of Dijkstra's Algorithm (6)
Further Discussion of Dijkstra's Algorithm
Link State Routing (with Dijkstra's Algorithm)
Comparison of LInk State and Distance Vector Algorithm (Message complexity) (LS) - LS: -> with n nodes, E links, O(n*E) msgs sent each
Comparison of LInk State and Distance Vector Algorithm (Message complexity) (DV) - DV -> exchange between neighbours only -> convergence time varies
Comparison of LInk State and Distance Vector Algorithm (Speed of Convergence) (LS)
Comparison of Link State and Distance Vector Algorithm (Speed of Convergence) (DV) - DV: -> convergence time varies --> may be routing loops --> count-to-infinity problem --> may have oscillations (with dynamic link weights)
Comparison of Link State and Distance Vector Algorithm (Robustness) (What happens if router malfunctions?) (LS) - Node can advertise incorrect link cost - Each node computes only its own table
Show full summary Hide full summary

Similar

ein kleines Informatik Quiz
AntonS
Informatik
Tom Kühling
Telematik Chapter 1-3
Julian Rottenberg
Telematik Chapter 4 + 10
Julian Rottenberg
Chapter 8-9
Julian Rottenberg
Chapter 9-10
Julian Rottenberg
Telematik Chapter 7 - 8
Julian Rottenberg
PHP Grundlagen
chrisi.0605
Wirtschaftsinformatik Teil 2
Sabrina Heckler
Informatik 1 - Einführung
Svenja
Codierung
Tom Kühling