Please enable JavaScript.
Coggle requires JavaScript to display documents.
NWC201 - 4 - Network Layer (The Internet Protocol - IP (IPv4 Addressing…
NWC201 - 4 - Network Layer
Introduction
Network Service Model
defines the characteristics
of end-to-end transport of packets between sending and receiving end systems
Examples
Functions of layer
Routing
determine route taken by packets from source to dest.
Routing agorithms
routing algorithm determines
end-end-path through network
process of planning trip from source to dest
Forwarding
move packets from router’s input to appropriate router output
process of getting through single interchange
Forwarding Table
forwarding table determines
local forwarding at this router
Connection Setup
3rd important function in some network architectures:
before datagrams flow, two end hosts and intervening routers establish virtual connection
What is Network Layer
on sending side encapsulates segments into datagrams
on receiving side, delivers segments to transport layer
transport segment from sending to receiving host
network layer protocols in every host, router
router examines header fields in all IP datagrams passing through it
Virtual Circuit and Datagram networks
Introduction
No choice
Network provides one of two
Virtual Circuit Networks
Computer networks that provide only a connection service at the network layer
Datagram Networks
computer networks that provide only a connectionless service
at the network layer
Implementation
In Network Core
Service
Host-to-host
Details
Virtual Circuit (VC)
Introduction
Include
VC numbers,
More on VC number
Because a virtual circuit may have a different VC number on each link,
each intervening router must replace the VC number of each traversing packet with a new VC number.
The new
VC number is obtained from the forwarding table.
A packet belonging to a virtual circuit will carry a VC number in its header
one number for each link along the
path,
entries in the forwarding table in each router along the path
a path (that is, a series of links and routers) between the
source and destination hosts
Charateristics
each packet carries VC identifier (not destination host address)
every router on source-dest path maintains “state” for each passing connection
call setup, teardown for each call before data can flow
link, router resources (bandwidth, buffers) may be allocated to VC (dedicated resources = predictable service)
Implementation
Include
VC numbers
Entries in forwarding table
Paths
3 Phases
VC Setup
Data transfer
VC teardown
Forwarding Table
the network’s routers must maintain connection state information
for the ongoing connections
each time a new connection is established across a router, a new connection entry must be added to the router’s forwarding table;
and each time a connection is released, an entry must be removed from the table.
Signaling Protocols
Signaling Messages
The messages that the end systems send into the network to initiate or terminate a VC, and the messages passed between the routers to set up the VC (that is, to modify connection state in router tables) are known as signaling messages
the protocols used to exchange these Signaling Messages
Datagram Networks
Introduction
No call setup at network layer
Router
no state about end-to-end connections like VC Network
each router has a forwarding table that maps destination
addresses to link interfaces;
packets forwarded using destination host address
Longest Prefix Matching
when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.
Datagram Forwarding Table
A entry in forwarding table map a
Destination Address Range
to a
Link Interface
the router matches a
prefix
of the
packet’s destination
address
with the
entries in the table
;
if there’s a match, the router forwards
the packet to a link associated with the match.
Application
VC network
human conversation:
need for guaranteed service
strict timing, reliability requirements
“dumb” end systems
complexity inside network
telephones
evolved from telephony
Examples
ATM
Telephone
Datagram Network
many link types
different characteristics
uniform service difficult
“smart” end systems (computers)
can adapt, perform control, error recovery
simple inside network, complexity at “edge”
data exchange among computers
“elastic” service, no strict timing req.
What's inside a router?
Funtions
Input Port
Link Layer Protocol
Data Link Layer
Look-up, Forwarding, and Queuing
given datagram dest., lookup output port using forwarding table in input port memory (“match plus action”)
goal: complete input port processing at ‘line speed
queuing:
queueing delay and loss due to input buffer overflow!
if datagrams arrive faster than forwarding rate into switch fabric
Head-of-the-Line (HOL) blocking
queued datagram at front of queue prevents others in queue from moving forward
Line termination
Physical layer
bit-level reception
Switching Farbrics
Function
transfer packet from input buffer to appropriate output buffer
switching rate
rate at which packets can be transfer from inputs to outputs
often measured as multiple of input/output line rate
N inputs: switching rate N times line rate desirable
Three type of
Memory
This is first generation of router
traditional computers with switching under direct control of CPU
packet copied to system’s memory
speed limited by memory bandwidth (2 bus crossings per datagram)
Bus
Bus contention
switching speed limited by bus bandwidth
32 Gbps bus, Cisco 5600
sufficient speed for access and enterprise routers
datagram from input port memory
to output port memory via a shared bus
Crossbar
Interconnection Network
overcome bus bandwidth limitations
Cisco 12000
switches 60 Gbps through the interconnection network
banyan networks, crossbar, other interconnection nets initially developed to connect processors in multiprocessor
Advanced Design
fragmenting datagram into fixed length cells, switch cells through the fabric
Output Port
Buffering
required when datagrams arrive from fabric faster than the transmission rate
queueing (delay) and loss due to output port buffer overflow!
Scheduling Discipline
chooses among queued datagrams for transmission
Router Architecture
Farbric Switching
The switching fabric connects the router’s input ports to its
output ports
This switching fabric is completely contained within the router—
a network inside of a network router!
Output Port
An output port stores packets received from the switching fabric and transmits these packets on the outgoing link by performing the necessary link-layer and physical-layer functions.
Input Ports
An input port also performs link-layer functions needed to interoperate with the link layer at the other side of the incoming link;
It performs the
physical layer function of terminating an incoming physical link at a router;
the lookup function is also performed at the input port;
this will occur in the rightmost box of the input port.
Routing Processor
The routing processor executes the routing protocols
maintains routing tables and attached link state information,
and computes the forwarding table for the router
The Internet Protocol - IP
The Internet Network Layer
IP Protocol
Datagram Format
Packet Handling Conventions
Addressing Convention
ICMP Protocol
Error Reporting
Router Signaling
Routing Protocols
Path selection
RIP, OSPF, BGP
Forwarding Table
IP Datagram Format
IP Datagram Fragmentation
large IP datagram divided
“reassembled” only at final destination
IP header bits used to identify, order related fragments
one datagram becomes several datagrams
MTU
Maximum Transmission Unit
network links have MTU (max.transfer size) - largest possible link-level frame
different link types, different MTUs
IPv4 Addressing
Introduction
Interface
router’s typically have multiple interfaces
host typically has one or two interfaces (e.g., wired Ethernet, wireless 802.11)
connection between host/router and physical link
IP addresses associated with each interface
IP Address
32-bit identifier for host, router interface
Subnets
IP Address
subnet part - high order bits
host part - low order bits
What is a Subnet
device interfaces with same subnet part of IP address
can physically reach each other without intervening router
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
CIDR
Classless InterDomain Routing
subnet portion of address of arbitrary length
address format: a.b.c.d/x, where x is # bits in subnet portion of address
200.23.16.0/23
DHCP
Dynamic Host Configuration Protocol
Goal
can renew its lease on address in use
allows reuse of addresses (only hold address while connected/“on”)
support for mobile users who want to join network (more shortly)
allow host to dynamically obtain its IP address from network server when it joins network
Overview
DHCP server responds with “DHCP offer” msg [optional]
host requests IP address: “DHCP request” msg
host broadcasts “DHCP discover” msg [optional]
DHCP server sends address: “DHCP ack” msg
Return message contains
name and IP address of DNS sever
network mask (indicating network versus host portion of address)
address of first-hop router for client
allocated IP address on subnet
NAT
Network Address Translation
Pros
can change addresses of devices in local network without notifying outside world
can change ISP without changing addresses of devices in local network
range of addresses not needed from ISP: just one IP address for all devices
devices inside local net not explicitly addressable, visible by outside world (a security plus)
local network uses just one IP address as far as outside world is concerned
Implementation
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
Outgoing Datagram
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 Traversal Problems
ICMP
Internet Control Message Protocol
Functions
used by hosts & routers to communicate network-level information
echo request/reply (used by ping)
error reporting: unreachable host, network, port, protocol
ICMP message
ICMP msgs carried in IP datagrams
type, code plus first 8 bytes of IP datagram causing error
Traceroute
IPv6
Datagram Format
Changes from IPv4
Options
allowed, but outside of header, indicated by “Next Header” field
ICMPv6
new version of ICMP
additional message types, e.g. “Packet Too Big”
multicast group management functions
Checksum
removed entirely to reduce processing time at each hop
Tunneling
Reasons
not all routers can be upgraded simultaneously
how will network operate with mixed IPv4 and IPv6 routers?
no “flag days”
Solutions
IPv6 datagram carried as payload in IPv4 datagram among IPv4 routers
Goals
Understand principles
How a router works
Routing
Forwarding versus Routing
Broadcast, Multicast
Network Layer Service Models
Instantiation, Implementation in the internet
Routing Algorithm
Classifications
Global
all routers have complete topology, link cost info
“
link state
” algorithms
Decentralized
iterative process of computation, exchange of info with neighbors
“
distance vector
” algorithms
router knows physically-connected neighbors, link costs to neighbors
Dynamic
routes change more quickly
periodic update
in response to link cost changes
Static
routes change slowly over time
Link-State Routing Algorithm
Dijkstra's Algorithm
computes least cost paths from one node (‘source”) to all other nodes
iterative: after k iterations, know least cost path to k dest.’s
net topology, link costs known to all nodes
accomplished via “link state broadcast”
all nodes have same info
Distance Vecter Algorithm
Bellman-Ford Equation
Dynamic Programming
Hierarchical Routing
Our Routing Study so far
all routers identical
network “flat”
Idealization
:red_flag:Not true in practice
problems in practice
Scale
can’t store all dest’s in routing tables!
routing table exchange would swamp links!
with 600 million destinations:
Administrative Autonomy
each network admin may want to control routing in its own network
internet = network of networks
Solution
routers in same
AS
run same routing protocol
“
intra-AS
” routing protocol
routers in different
AS
can run different
intra-AS
routing protocol
Gateway Router
at “edge” of its own
AS
has link to router in another
AS
aggregate routers into regions, “
autonomous systems
” (
AS
)
Characteristics
forwarding table
configured by both
intra-
and
inter-AS
routing algorithm
intra-AS
sets entries for internal dests
inter-AS
&
intra-AS
sets entries for external dests
Routing in the internet
Intra-AS Routing Protocol
interior gateway protocols (IGP)
Common intra-AS protocols
OSPF
Open Shortest Path First
IGRP
Interior Gateway Routing Prorocol
RIP
Routing Infomation Protocol
Inter-AS Protocols
BGP
Boder Gateway Protocol
RIP
Introduction
distance vector algorithm
DV
DV
s exchanged with neighbors every 30 sec in response message (aka advertisement)
each advertisement: list of up to 25 destination subnets (in IP addressing sense)
distance metric
number of
hops (max = 15 hops), each link has cost 1
included in BSD-UNIX distribution in 1982
Intra-AS Routing
Link Failure, 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
OSPF
Introduction
OSPF advertisement carries one entry per neighbor
uses
link state
algorithm
topology map at each node
route computation using Dijkstra’s algorithm
LS packet dissemination
advertisements flooded to entire AS
carried in OSPF messages directly over IP (rather than TCP or UDP
“open”: publicly available
IS-IS routing protocol: nearly identical to OSPF
Intra-AS Routing
BGP
Border Gateway Protocol
inter-AS routing
Broadcast and Multicast Routing
Broadcast Routing
Introduction
source duplication is inefficient:
source duplication: how does source determine recipient addresses?
deliver packets from source to all other nodes
In-network Duplication
Controlled Flooding
node keeps track of packet ids already broadacsted
or reverse path forwarding (RPF): only forward packet if it arrived on shortest path between node and source
node only broadcasts pkt if it hasn’t broadcast same packet before
Spanning Tree
no redundant packets received by any node
Flooding
when node receives broadcast packet, sends copy to all neighbors
problems: cycles & broadcast storm
Multicast Routing
Problems
Tree
not all paths between routers used
Shared Tree
same tree used by all all group members
Goal
find a tree (or trees) connecting routers having local mcast group members
packet is delivered to only a subset of
network nodes
Source Based
different tree from each sender to rcvrs
