Created by Julian Rottenberg
over 6 years ago
|
||
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 |
Want to create your own Flashcards for free with GoConqr? Learn more.