Reti di calcolatori e Sicurezza Network Layer Part of these slides are adapted from the slides of the book



Scaricare 491 b.
23.05.2018
Dimensione del file491 b.


Reti di calcolatori e Sicurezza -- Network Layer ---

  • Part of these slides are adapted from the slides of the book:

  • Computer Networking: A Top Down Approach Featuring the Internet, 2nd edition. Jim Kurose, Keith Ross Addison-Wesley, July 2002. (copyright 1996-2002

  • J.F Kurose and K.W. Ross, All Rights Reserved)


Chapter 4: Network Layer

  • Chapter goals:

  • understand principles behind network layer services:

    • routing (path selection)
    • dealing with scale
    • how a router works
    • advanced topics: IPv6, mobility
  • instantiation and implementation in the Internet



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



Network: Funzionalità

  • Trasportare pacchetti (datagram) dal sender al receiver

  • I protocolli del livello network “girano” sia sugli host che sui router

  • Funzionalità principali:

  • Determinazione del percorso dei pacchetti:. Routing

  • Switching: funzione che definisce le modalità di input/output dei pacchetti in un router

  • Call setup: attività di inizializzazione del percorso (solo in alcune architteture) (NO IP! .. Ma con QoS?)



Il modello del servizio

  • Quale è il modello di servizio offerto dal livello network?

  • Viene assicurata una determinata banda di trasmissione?

  • loss-free delivery?

  • in-order delivery?

  • congestion feedback?



Circuiti Virtuali

  • call setup: per ogni attivazione del circuto prima di poter trasmettere dati

  • Ogni pacchetto trasmesso deve avere un tag di identificazione del circuito (non importa l’indirizzo di destinazione)



Circuito Virtuale (2)

  • Ogni router lungo il cammino deve mantenere le informazioni di stato per ogni connessione che passa attraverso il router.

  • Le risorse del router (bandwidth, buffer) devono essere allocate per il circuito virtuale.



Circuito Virtuale (3)

  • Comportamento ideale di un circuto virtuale



Circuito Virtuale (conclusioni)

  • Utilizzato in particolari applicazioni (ad esempio quando si vogliono avere dei collegamenti dedicati tra intranet aziendali)

  • ATM, frame-relay, X.25 utilizzano questo modello di servizio

  • Internet: no!!



Reti Datagram: Internet

  • Nessuna azione di attivazione (call set up)

  • router: non mantengono informazioni di stato sulle connessioni

    • Network: non esiste la nozione di “connessione”
  • I pacchetti sono caratterizzati dall’indirizzo di destinazione (pacchetti di una connessione possono seguire un percorso differente)



Network:



Datagram vs VC

  • Internet

  • Scambio dei dati tra le applicazioni

    • Servizi “elastic” rispetto ai requisiti temporali
  • Host (computers)

    • Possono implementare politiche per il controllo della congestione, etc
    • Rete semplice ma applicazioni evolute
  • Eterogeneità: difficile prevedere una nozione uniforme di servizio



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

    • Link state routing
    • Distance vector routing
  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



Routing

  • Graph abstraction for routing algorithms:

  • graph nodes are routers

  • graph edges are physical links

    • link cost: delay, $ cost, or congestion level


Caratteristiche del routing

  • Switching vs Routing

    • Switching: attività che seleziona una porta del router in base alle informazioni della tabella di routing
    • routing: attività di costruzione della tabella di routing


Routing Algorithm classification

  • Global or decentralized information?

  • Global:

  • all routers have complete topology, link cost info

  • “link state” algorithms

  • Decentralized:

  • router knows physically-connected neighbors, link costs to neighbors

  • iterative process of computation, exchange of info with neighbors

  • “distance vector” algorithms



A Link-State Routing Algorithm

  • Dijkstra’s algorithm

  • net topology, link costs known to all nodes

    • accomplished via “link state broadcast”
    • all nodes have same info
  • computes least cost paths from one node (‘source”) to all other nodes

    • gives routing table for that node
  • iterative: after k iterations, know least cost path to k dest.’s



Dijsktra’s Algorithm



Dijkstra’s algorithm: example



DA: Esempio



DA: Esempio



DA: Esempio



DA: Esempio



DA: Esempio



Dijkstra’s algorithm, discussion

  • Algorithm complexity: n nodes

  • each iteration: need to check all nodes, w, not in N

  • n*(n+1)/2 comparisons: O(n**2)

  • more efficient implementations possible: O(nlogn)

  • Oscillations possible:

  • e.g., link cost = amount of carried traffic



Distance Vector Routing Algorithm

  • iterative:

  • continues until no nodes exchange info.

  • self-terminating: no “signal” to stop

  • asynchronous:

  • nodes need not exchange info/iterate in lock step!

  • distributed:

  • each node communicates only with directly-attached neighbors



Distance Table: example



Distance table gives routing table



Routing: distribuito e asincrono

  • Algoritmo di Bellmann-Ford: vettore delle distanze (distance vector)



Distance Vector Routing: overview

  • Iterative, asynchronous: each local iteration caused by:

  • local link cost change

  • message from neighbor: its least cost path change from neighbor

  • Distributed:

  • each node notifies neighbors only when its least cost path to any destination changes

    • neighbors then notify their neighbors if necessary


Distance Vector Algorithm:



Distance Vector Algorithm (cont.):



Distance Vector Algorithm: example



Distance Vector Algorithm: example



Distance Vector: link cost changes



Distance Vector: link cost changes



Distance Vector: poisoned reverse



Comparison of LS and DV algorithms

  • Message complexity

  • LS: with n nodes, E links, O(nE) msgs sent each

  • DV: exchange between neighbors only

    • convergence time varies
  • Speed of Convergence

  • LS: O(n2) algorithm requires O(nE) msgs

    • may have oscillations
  • DV: convergence time varies

    • may be routing loops
    • count-to-infinity problem


Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



Routing

  • I meccanismi di routing che abbiamo studiato sono neccanismi ideali

    • Rete è piatta
    • Tutti i router sono identici
  • Buona astrazione ma … irrealistica!!!



Internet

  • Passato recente



Internet

  • Oggi



Internet

  • scalabilità: 50 milioni di possibili host:

  • Non possono memorizzare tutte le possibili destinazioni nella tabella di routing!

  • Messaggi per la modifica delle tabelle di routing avrebbero un costo troppo elevato!



Routing Gerarchico

  • I router vengono aggregati in regioni: “autonomous systems” (AS)

  • I routers nella stessa AS eseguono lo stesso protocollo di routing

    • “intra-AS” routing
    • Router in regioni differenti possono eseguire un protocollo diverso dal protocollo intra-AS routing


Intra-AS vs Inter-AS routing



Intra-AS vs Inter-AS routing



Routing Gerarchico

  • Rete viene suddivisa in regioni

  • Router di una regione hanno informazione completa su quella regione

  • Analogia: Prefissi telefonici



Routing Gerarchico



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

    • 4.4.1 IPv4 addressing
    • 4.4.2 Moving a datagram from source to destination
    • 4.4.3 Datagram format
    • 4.4.4 IP fragmentation
    • 4.4.5 ICMP: Internet Control Message Protocol
    • 4.4.6 DHCP: Dynamic Host Configuration Protocol
    • 4.4.7 NAT: Network Address Translation
  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



The Internet Network layer

  • Host, router network layer functions:



IP Addressing: introduction

  • IP address: 32-bit identifier for host, router interface

  • interface: connection between host/router and physical link



IP Addressing

  • IP address:

    • network part (high order bits)
    • host part (low order bits)
  • What’s a network ? (from IP address perspective)

    • device interfaces with same network part of IP address
    • can physically reach each other without intervening router


IP Addressing

  • How to find the networks?

  • Detach each interface from router, host

  • create “islands of isolated networks



IP Address Classes

  • Class A:

    • For very large organizations
    • 16 million hosts allowed
  • Class B:

    • For large organizations
    • 65 thousand hosts allowed
  • Class C

    • For small organizations
    • 255 hosts allowed
  • Class D

    • Multicast addresses
    • No network/host hierarchy


Indirizzamento per classe

  • Proprietà

    • unico
    • gerarchico: network + host
  • Dot Notation

    • 10.3.2.4
    • 128.96.33.81
    • 192.12.69.77


IP addressing: CIDR

  • Indirizzamento via classi:

    • Uso poco efficiente dello spazio degli indirizzi: la classe B alloca indirizzi per 65K host anche se la rete ne richiede solamente 2k
  • CIDR: Classless InterDomain Routing

    • Reti IP hanno indirizzi di lunghezza arbitraria
    • formato: a.b.c.d/x, dove x è # di bit nella porzione dell’indirizzo che definisce la rete.


Cammino di un datagram

  • IP datagram:



Cammino di un datagram



Cammino di un datagram



Cammino di un datagram



IP datagram format



IPv4

  • Tipo del servizio:

    • Differenza tra datagram di controllo e datagram dei dati
    • Router usano questo campo per differenziare i livelli di servizio offerti
  • TTL = 0 allora il datagram deve essere abbandonato

  • Protocol (simile al numero di porta del trasporto)

    • 6 => TCP
    • 17 => UDP


Checksum

  • Perchè la suite TCP/IP (IPv4) prevede checksum sia al livello del trasporto che al livello della rete?

    • Router non è richiesto fare questo calcolo
    • TCP potrebbe basarsi su di un livello di trasporto differente (esempio ATM)


MTU

  • Quantità di dati che può trasportare un protocollo del livello link è denominata MTU (max.transfer size):

    • Link differenti possono avere, MTU distinte
      • Ethernet MTU = 1500 bytes
      • WAN MTU = 576 bytes
  • Datagram è incapsulato all’interno di un pacchetto del link

    • MTU limite alla dimensione del datagram


Problema

  • In un percorso sulla rete un datagram può passare lungo link che hanno una differente struttura del MTU

  • Soluzione: Frammentare i dati del datagram in piu’ datagram



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 at final destination
    • IP header bits used to identify, order related fragments


IP Fragmentation and Reassembly



IP: Frammentazione & Riassemblaggio

  • F&R: Carico di lavoro sui router

  • Piccola frammentazione

    • MTU almeno 576 bytes
      • MSS 536 bytes
      • 20 bytes = header del segmento
      • 20 bytes = header del datagram


Network Protocols ICMP,



ICMP: Internet Control Message Protocol

  • Protocollo utilizzato da host, router, gateway per scambiarsi in formazioni relative al livello network

    • errori: unreachable host, network, port, protocol
    • echo request/reply (ping)
    • traceroute


ICMP: Internet Control Message Protocol

  • ICMP livello sopra IP:

    • ICMP msgs sono incapsulati in datagram IP
  • ICMP struttura dei messaggi:

    • Campo type,
    • Campo code
    • Contengono inoltre i primi 8 bytes del datagram IP che ha causato l’errore.


ICMP: esempi di uso

  • Echo request reply

    • Controllo se un host è ancora “vivo”
  • Address mask request/reply

    • determinara subnet mask
  • Destination unreachable

    • Indirizzo non valido
  • TTL expired

    • … troppo lontano


Ping

  • ICMP echo request/reply

  • Source sends ICMP echo request message to the destination address

    • Echo request packet contains sequence number and timestamp
  • Destination replies with an ICMP echo reply message containing the data in the original echo request message

  • Source can calculate round trip time (RTT) of packets

  • If no echo reply comes back then the destination is unreachable



Ping (2)



Traceroute

  • Traceroute records the route that packets take

  • A clever use of the TTL field

  • When a router receives a packet, it decrements TTL

  • If TTL=0, it sends an ICMP time exceeded message back to the sender

  • To determine the route, progressively increase TTL

    • Every time an ICMP time exceeded message is received, record the sender’s (router’s) address
    • Repeat until the destination host is reached or an error message occurs


Traceroute (2)



Come si ottiene l’indirizzo IP?

  • Hosts

  • File di configurazione

      • Win: control-panel->network->configuration->tcp/ip->properties
      • Linux: /etc/rc.config
  • DHCP: Dynamic Host Configuration Protocol: ottiene l’indirizzo in modo dinamico: “plug-and-play”

      • host broadcast “DHCP discover” msg
      • DHCP server risponde “DHCP offer” msg
        • host invia la richiesta per IP address: “DHCP request” msg
      • DHCP server invia l’indirizzo: “DHCP ack” msg


DHCP: Dynamic Host Configuration Protocol

  • Goal: allow host to dynamically obtain its IP address from network server when it joins network

    • Can renew its lease on address in use
    • Allows reuse of addresses (only hold address while connected an “on”
    • Support for mobile users who want to join network (more shortly)
  • DHCP overview:

    • host broadcasts “DHCP discover” msg
    • DHCP server responds with “DHCP offer” msg
    • host requests IP address: “DHCP request” msg
    • DHCP server sends address: “DHCP ack” msg


DHCP client-server scenario



DHCP client-server scenario



NAT: Network Address Translation



NAT: Network Address Translation

  • Motivation: 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
    • 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

  • 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.
    • remember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation pair
    • 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 field:

    • 60,000 simultaneous connections with a single LAN-side address!
  • NAT is controversial:

    • routers should only process up to layer 3
    • violates end-to-end argument
      • NAT possibility must be taken into account by app designers, eg, P2P applications
    • address shortage should instead be solved by IPv6


Hierarchical addressing: route aggregation



Hierarchical addressing: more specific routes



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

    • 4.5.1 Intra-AS routing: RIP and OSPF
    • 4.5.2 Inter-AS routing: BGP
  • 4.6 What’s Inside a Router?

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



Routing in the Internet

  • The Global Internet consists of Autonomous Systems (AS) interconnected with each other:

    • Stub AS: small corporation: one connection to other AS’s
    • Multihomed AS: large corporation (no transit): multiple connections to other AS’s
    • Transit AS: provider, hooking many AS’s together
  • Two-level routing:

    • Intra-AS: administrator responsible for choice of routing algorithm within network
    • Inter-AS: unique standard for inter-AS routing: BGP


Internet AS Hierarchy



Intra-AS Routing

  • Also known as Interior Gateway Protocols (IGP)

  • Most common Intra-AS routing protocols:

    • RIP: Routing Information Protocol
    • OSPF: Open Shortest Path First
    • IGRP: Interior Gateway Routing Protocol (Cisco proprietary)


RIP ( Routing Information Protocol)

  • Distance vector algorithm

  • Included in BSD-UNIX Distribution in 1982

  • Distance metric: # of hops (max = 15 hops)

    • Can you guess why?
  • Distance vectors: exchanged among neighbors every 30 sec via Response Message (also called advertisement)

  • Each advertisement: list of up to 25 destination nets within AS



RIP: Example



RIP: Example



RIP: Link Failure and Recovery

  • If no advertisement heard after 180 sec --> neighbor/link declared dead

    • routes via neighbor invalidated
    • new advertisements sent to neighbors
    • neighbors in turn send out new advertisements (if tables changed)
    • link failure info quickly propagates to entire net
    • poison reverse used to prevent ping-pong loops (infinite distance = 16 hops)


RIP Table processing

  • RIP routing tables managed by application-level process called route-d (daemon)

  • advertisements sent in UDP packets, periodically repeated



RIP Table example (continued)

  • Router: giroflee.eurocom.fr



OSPF (Open Shortest Path First)

  • “open”: publicly available

  • Uses Link State algorithm

    • LS packet dissemination
    • Topology map at each node
    • Route computation using Dijkstra’s algorithm
  • OSPF advertisement carries one entry per neighbor router

  • Advertisements disseminated to entire AS (via flooding)

    • Carried in OSPF messages directly over IP (rather than TCP or UDP


OSPF “advanced” features (not in RIP)

  • Security: all OSPF messages authenticated (to prevent malicious intrusion)

  • Multiple same-cost paths allowed (only one path in RIP)

  • For each link, multiple cost metrics for different TOS (e.g., satellite link cost set “low” for best effort; high for real time)

  • Integrated uni- and multicast support:

    • Multicast OSPF (MOSPF) uses same topology data base as OSPF
  • Hierarchical OSPF in large domains.



Hierarchical OSPF



Hierarchical OSPF

  • Two-level hierarchy: local area, backbone.

    • Link-state advertisements only in area
    • each nodes has detailed area topology; only know direction (shortest path) to nets in other areas.
  • Area border routers: “summarize” distances to nets in own area, advertise to other Area Border routers.

  • Backbone routers: run OSPF routing limited to backbone.

  • Boundary routers: connect to other AS’s.



Inter-AS routing in the Internet: BGP



Internet inter-AS routing: BGP

  • BGP (Border Gateway Protocol): the de facto standard

  • Path Vector protocol:

    • similar to Distance Vector protocol
    • each Border Gateway broadcast to neighbors (peers) entire path (i.e., sequence of AS’s) to destination
    • BGP routes to networks (ASs), not individual hosts
    • E.g., Gateway X may send its path to dest. Z:
  • Path (X,Z) = X,Y1,Y2,Y3,…,Z



Internet inter-AS routing: BGP

  • Suppose: gateway X send its path to peer gateway W

  • W may or may not select path offered by X

    • cost, policy (don’t route via competitors AS), loop prevention reasons.
  • If W selects path advertised by X, then:

  • Path (W,Z) = w, Path (X,Z)

  • Note: X can control incoming traffic by controlling it route advertisements to peers:

    • e.g., don’t want to route traffic to Z -> don’t advertise any routes to Z


BGP: controlling who routes to you



BGP: controlling who routes to you



BGP operation

  • Q: What does a BGP router do?

  • Receiving and filtering route advertisements from directly attached neighbor(s).

  • Route selection.

    • To route to destination X, which path )of several advertised) will be taken?
  • Sending route advertisements to neighbors.



BGP messages

  • BGP messages exchanged using TCP.

  • BGP messages:

    • OPEN: opens TCP connection to peer and authenticates sender
    • UPDATE: advertises new path (or withdraws old)
    • KEEPALIVE keeps connection alive in absence of UPDATES; also ACKs OPEN request
    • NOTIFICATION: reports errors in previous msg; also used to close connection


Why different Intra- and Inter-AS routing ?

  • Policy:

  • Inter-AS: admin wants control over how its traffic routed, who routes through its net.

  • Intra-AS: single admin, so no policy decisions needed

  • Scale:

  • hierarchical routing saves table size, reduced update traffic

  • Performance:

  • Intra-AS: can focus on performance

  • Inter-AS: policy may dominate over performance



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router?

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



Router Architecture Overview

  • Two key router functions:

  • run routing algorithms/protocol (RIP, OSPF, BGP)

  • switching datagrams from incoming to outgoing link



Input Port Functions

  • Decentralized switching:

  • given datagram dest., lookup output port using routing table in input port memory

  • goal: complete input port processing at ‘line speed’

  • queuing: if datagrams arrive faster than forwarding rate into switch fabric



Input Port Queuing

  • Fabric slower that input ports combined -> queueing may occur at input queues

  • Head-of-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!



Three types of switching fabrics



Switching Via Memory

  • First generation routers:

  • packet copied by system’s (single) CPU

  • speed limited by memory bandwidth (2 bus crossings per datagram)



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

  • 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone)



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: switches Gbps through the interconnection network



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

  • buffering when arrival rate via switch exceeds output line speed

  • queueing (delay) and loss due to output port buffer overflow!



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router?

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



IPv6

  • Initial motivation: 32-bit address space completely allocated by 2008.

  • Additional motivation:

    • header format helps speed processing/forwarding
    • header changes to facilitate QoS
    • new “anycast” address: route to “best” of several replicated servers
  • IPv6 datagram format:

    • fixed-length 40 byte header
    • no fragmentation allowed


IPv6 Header (Cont)



Other Changes from IPv4

  • 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



Transition From IPv4 To IPv6

  • Not all routers can be upgraded simultaneous

    • no “flag days”
    • How will the network operate with mixed IPv4 and IPv6 routers?
  • Two proposed approaches:

    • Dual Stack: some routers with dual stack (v6, v4) can “translate” between formats
    • Tunneling: IPv6 carried as payload in IPv4 datagram among IPv4 routers


Dual Stack Approach



Tunneling



Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router?

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



Multicast: one sender to many receivers

  • Multicast: act of sending datagram to multiple receivers with single “transmit” operation

    • analogy: one teacher to many students
  • Question: how to achieve multicast



Multicast: one sender to many receivers

  • Multicast: act of sending datagram to multiple receivers with single “transmit” operation

    • analogy: one teacher to many students
  • Question: how to achieve multicast



Multicast: one sender to many receivers

  • Multicast: act of sending datagram to multiple receivers with single “transmit” operation

    • analogy: one teacher to many students
  • Question: how to achieve multicast



Internet Multicast Service Model

  • multicast group concept: use of indirection

    • hosts addresses IP datagram to multicast group
    • routers forward multicast datagrams to hosts that have “joined” that multicast group


Multicast groups

  • class D Internet addresses reserved for multicast:

  • host group semantics:

    • anyone can “join” (receive) multicast group
    • anyone can send to multicast group
    • no network-layer identification to hosts of members
  • needed: infrastructure to deliver mcast-addressed datagrams to all hosts that have joined that multicast group



Joining a mcast group: two-step process

  • local: host informs local mcast router of desire to join group: IGMP (Internet Group Management Protocol)

  • wide area: local router interacts with other routers to receive mcast datagram flow

    • many protocols (e.g., DVMRP, MOSPF, PIM)


IGMP: Internet Group Management Protocol

  • host: sends IGMP report when application joins mcast group

    • IP_ADD_MEMBERSHIP socket option
    • host need not explicitly “unjoin” group when leaving
  • router: sends IGMP query at regular intervals

    • host belonging to a mcast group must reply to query


IGMP

  • IGMP version 1

  • router: Host Membership Query msg broadcast on LAN to all hosts

  • host: Host Membership Report msg to indicate group membership

    • randomized delay before responding
    • implicit leave via no reply to Query
  • RFC 1112



Multicast Routing: Problem Statement

  • Goal: find a tree (or trees) connecting routers having local mcast group members

    • tree: not all paths between routers used
    • source-based: different tree from each sender to rcvrs
    • shared-tree: same tree used by all group members


Approaches for building mcast trees

  • Approaches:

  • source-based tree: one tree per source

    • shortest path trees
    • reverse path forwarding
  • group-shared tree: group uses one tree

    • minimal spanning (Steiner)
    • center-based trees


Shortest Path Tree



Reverse Path Forwarding

  • if (mcast datagram received on incoming link on shortest path back to center)

  • then flood datagram onto all outgoing links

  • else ignore datagram



Reverse Path Forwarding: example



Reverse Path Forwarding: pruning

  • forwarding tree contains subtrees with no mcast group members

    • no need to forward datagrams down subtree
    • “prune” msgs sent upstream by router with no downstream group members


Shared-Tree: Steiner Tree

  • Steiner Tree: minimum cost tree connecting all routers with attached group members

  • problem is NP-complete

  • excellent heuristics exists

  • not used in practice:

    • computational complexity
    • information about entire network needed
    • monolithic: rerun whenever a router needs to join/leave


Center-based trees

  • single delivery tree shared by all

  • one router identified as “center” of tree

  • to join:

    • edge router sends unicast join-msg addressed to center router
    • join-msg “processed” by intermediate routers and forwarded towards center
    • join-msg either hits existing tree branch for this center, or arrives at center
    • path taken by join-msg becomes new branch of tree for this router


Center-based trees: an example



Internet Multicasting Routing: DVMRP

  • DVMRP: distance vector multicast routing protocol, RFC1075

  • flood and prune: reverse path forwarding, source-based tree

    • RPF tree based on DVMRP’s own routing tables constructed by communicating DVMRP routers
    • no assumptions about underlying unicast
    • initial datagram to mcast group flooded everywhere via RPF
    • routers not wanting group: send upstream prune msgs


DVMRP: continued…

  • soft state: DVMRP router periodically (1 min.) “forgets” branches are pruned:

  • routers can quickly regraft to tree

    • following IGMP join at leaf
  • odds and ends

    • commonly implemented in commercial routers
    • Mbone routing done using DVMRP


Tunneling

  • Q: How to connect “islands” of multicast routers in a “sea” of unicast routers?



PIM: Protocol Independent Multicast

  • not dependent on any specific underlying unicast routing algorithm (works with all)

  • two different multicast distribution scenarios :



Consequences of Sparse-Dense Dichotomy:

  • Dense

  • group membership by routers assumed until routers explicitly prune

  • data-driven construction on mcast tree (e.g., RPF)

  • bandwidth and non-group-router processing profligate



PIM- Dense Mode



PIM - Sparse Mode

  • center-based approach

  • router sends join msg to rendezvous point (RP)

    • intermediate routers update state and forward join
  • after joining via RP, router can switch to source-specific tree

    • increased performance: less concentration, shorter paths


PIM - Sparse Mode

  • sender(s):

  • unicast data to RP, which distributes down RP-rooted tree

  • RP can extend mcast tree upstream to source

  • RP can send stop msg if no attached receivers

    • “no one is listening!”


Chapter 4 roadmap

  • 4.1 Introduction and Network Service Models

  • 4.2 Routing Principles

  • 4.3 Hierarchical Routing

  • 4.4 The Internet (IP) Protocol

  • 4.5 Routing in the Internet

  • 4.6 What’s Inside a Router?

  • 4.7 IPv6

  • 4.8 Multicast Routing

  • 4.9 Mobility



What is mobility?

  • spectrum of mobility, from the network perspective:



Mobility: Vocabulary



Mobility: more vocabulary



How do you contact a mobile friend:

  • search all phone books?

  • call her parents?

  • expect her to let you know where he/she is?



Mobility: approaches

  • Let routing handle it: routers advertise permanent address of mobile-nodes-in-residence via usual routing table exchange.

    • routing tables indicate where each mobile located
    • no changes to end-systems
  • Let end-systems handle it:

    • indirect routing: communication from correspondent to mobile goes through home agent, then forwarded to remote
    • direct routing: correspondent gets foreign address of mobile, sends directly to mobile


Mobility: approaches

  • Let routing handle it: routers advertise permanent address of mobile-nodes-in-residence via usual routing table exchange.

    • routing tables indicate where each mobile located
    • no changes to end-systems
  • let end-systems handle it:

    • indirect routing: communication from correspondent to mobile goes through home agent, then forwarded to remote
    • direct routing: correspondent gets foreign address of mobile, sends directly to mobile


Mobility: registration

  • End result:

  • Foreign agent knows about mobile

  • Home agent knows location of mobile



Mobility via Indirect Routing



Indirect Routing: comments

  • Mobile uses two addresses:

    • permanent address: used by correspondent (hence mobile location is transparent to correspondent)
    • care-of-address: used by home agent to forward datagrams to mobile
  • foreign agent functions may be done by mobile itself

  • triangle routing: correspondent-home-network-mobile



Forwarding datagrams to remote mobile



Indirect Routing: moving between networks

  • suppose mobile user moves to another network

    • registers with new foreign agent
    • new foreign agent registers with home agent
    • home agent update care-of-address for mobile
    • packets continue to be forwarded to mobile (but with new care-of-address)
  • Mobility, changing foreign networks transparent: on going connections can be maintained!



Mobility via Direct Routing



Mobility via Direct Routing: comments

  • overcome triangle routing problem

  • non-transparent to correspondent: correspondent must get care-of-address from home agent

    • What happens if mobile changes networks?


Mobile IP

  • RFC 3220

  • has many features we’ve seen:

    • home agents, foreign agents, foreign-agent registration, care-of-addresses, encapsulation (packet-within-a-packet)
  • three components to standard:

    • agent discovery
    • registration with home agent
    • indirect routing of datagrams


Mobile IP: agent discovery

  • agent advertisement: foreign/home agents advertise service by broadcasting ICMP messages (typefield = 9)



Mobile IP: registration example



Network Layer: summary

  • Next stop:

  • the Data

  • link layer!






©astratto.info 2017
invia messaggio

    Pagina principale