PowerPoint 簡報
Computer Networking: A Top Down Approach
Copyright By PowCoder代写 加微信 powcoder
7th edition
April 2016
Chapter 4 & 5
Network Layer
The Powerpoint slides are from Kurose and Ross’s book’s website.
Network Layer
4.1 Overview of network layer
data plane
control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Chapter 4: outline
Network Layer
Chapter 4: goals
understand principles behind network layer services:
network layer service models
forwarding versus routing
how a router works
generalized forwarding
Internet protocol
Network Layer
Network layer
transport segments from sending to receiving host
on sending side encapsulates segments into datagrams
on receiving side, delivers segments to transport layer
network layer protocols run in every host, router
router examines header fields in all IP datagrams passing through it
application
application
Network Layer
Network layer
forwarding
host, router network layer functions:
routing protocols
path selection
RIP, OSPF, BGP
IP protocol
addressing conventions
datagram format
packet handling conventions
ICMP protocol
error reporting
router “signaling”
transport layer: TCP, UDP
link layer
physical layer
ARP & RARP
logical vs physical address mapping
Network Layer
Two key network-layer functions
network-layer functions:
forwarding: move packets from router’s input to appropriate router’s output
routing: determine the route taken by packets from source to destination
analogy: taking a trip
forwarding: process of getting through single interchange
routing: process of planning trip from source to destination
Network Layer
Network layer: data plane, control plane
Network Layer
value in arriving
packet’s header
routing algorithm
local forwarding table
header value
output link
data plane
local, per-router forwarding function
determines how datagram arriving on router input port is forwarded to router output port
control plane
network-wide routing
determines how datagram is routed among routers along end-end path from source host to destination host
Destination Address Range
11001000 00010111 00010000 00000000
11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000
11001000 00010111 00011000 11111111
11001000 00010111 00011001 00000000
11001000 00010111 00011111 11111111
Link Interface
Q: but what happens if ranges don’t divide up so nicely?
Forwarding table
forwarding table
Network Layer
Longest prefix matching
Destination Address Range
11001000 00010111 00010*** *********
11001000 00010111 00011000 *********
11001000 00010111 00011*** *********
DA: 11001000 00010111 00011000 10101010
DA: 11001000 00010111 00010110 10100001
which interface?
which interface?
when looking for forwarding table entry for given destination address, use longest address prefix that matches destination address.
longest prefix matching
Link interface
Network Layer
4.1 Overview of network layer
data plane
control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Chapter 4: outline
Network Layer
Router architecture overview
router input ports
router output ports
forwarding data plane (hardware) operates in nanosecond timeframe
routing, management
control plane (software)
operates in millisecond
time frame
high-level view of generic router architecture:
Network Layer
termination
link layer
forwarding
Input ports
decentralized switching:
according to header field values, lookup output port using forwarding table in input port memory (“match plus action”)
queuing: if datagrams arrive faster than forwarding rate into switch fabric
queueing delay and loss due to input buffer overflow!
physical layer:
bit-level reception
data link layer:
e.g., Ethernet
Network Layer
Switching fabrics
transfer packet from input buffer to appropriate output buffer
switching rate: rate at which packets can be transferred from inputs to outputs
often measured as multiple of input/output line rate
three types of switching fabrics
Network Layer
Output ports
buffering required when datagrams arrive from switch fabric is faster than the transmission rate
queueing delay and loss due to output port buffer overflow!
scheduling discipline chooses the datagram among queued datagrams for transmission
termination
link layer
Network Layer
4.1 Overview of network layer
data plane
control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Chapter 4: outline
Network Layer
IPv4 addressing: introduction
IP address: 32-bit identifier for host, router interface
interface: connection between host/router and physical link
router typically has multiple interfaces
host typically has one or two interfaces (e.g., wired Ethernet, wireless 802.11)
IP addresses are associated with each interface
223.1.1.1 = 11011111 00000001 00000001 00000001
223.1.3.27
Network Layer
IP classful addressing
an address space is the total number of addresses that can be used.
in classful addressing, the address space is divided into five classes: A, B, C, D, and E.
Network Layer
Two-level classful addressing
each IP address is made of two parts: netid and hostid.
netid defines a network
hostid identifies a host on that network
Network Layer
Special addresses
some parts of the address space in class A, B, C reserved for special addresses
Network Layer
a mask is a 32-bit binary number
it can bitwise AND with an IP address to get the network address
IP address
network address
Network Layer
What’s a subnet ?
device interfaces with same netid part of IP address
can physically reach each other without intervening router
How to determine subnets?
detach each interface from its host or router, creating islands of isolated networks
each isolated network is a subnet
223.1.3.27
network consisting of 3 subnets
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
Network Layer
How many subnets?
223.1.3.27
Network Layer
4.1 Overview of network layer
data plane
control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Chapter 4: outline
Network Layer
(variable length,
typically a TCP
or UDP segment)
16-bit identifier
32 bit source IP address
32 bit destination IP address
options (if any)
IP datagram format
IP protocol version
header length
upper layer protocol
to deliver payload to
total datagram
length (bytes)
“type” of data
fragmentation/
reassembly
max number
remaining hops
(decremented at
each router)
e.g. timestamp,
record route
taken, specify
list of routers
how much overhead?
20 bytes of TCP
20 bytes of IP
= 40 bytes + app layer overhead
Network Layer
4.1 Overview of Network layer
data plane
control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Chapter 4: outline
Network Layer
IP fragmentation, reassembly
network links have MTU (max. transfer size) – largest possible link-level frame
different link types have different MTUs
large IP datagram is divided (“fragmented”) within net
one datagram becomes several datagrams
they are “reassembled” only at final dest.
IP header bits are used to identify the order of related fragments
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
Network Layer
one large datagram becomes
several smaller datagrams
4000 byte datagram
MTU = 1500 bytes
1480 bytes in
data field
IP fragmentation, reassembly
Network Layer
4.1 Overview of network layer
data plane
control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Chapter 4: outline
Network Layer
IP addresses: how to get one?
Q: How does a host get IP address?
allocated manually and hard-coded by system administrators in a file
Windows: control-panelnetworkconfiguration tcp/ipproperties
UNIX: /etc/rc.config
OK as far as it goes but does not scale to large networks and some networks (e.g., home networks) don’t have (competent) administrators
DHCP: Dynamic Host Configuration Protocol: dynamically get address from server
“plug-and-play”
Network Layer
DHCP: Dynamic Host Configuration Protocol
Goal: allow host to dynamically obtain its IP address from network server when it joins network
DHCP has a pool of available addresses: when a request arrives, DHCP pulls out the next available address and assigns it to the client for a time period
when a request comes in from a client, DHCP server first consults the static table
DHCP is great when devices and IP addresses change
can renew its lease on address in use
allow reuse of addresses (only hold address while connected/“on”)
support for mobile users who join network at ad hoc
DHCP overview:
host broadcasts “DHCP discover” msg [optional]
DHCP server responds with “DHCP offer” msg [optional]
host requests IP address: “DHCP request” msg
DHCP server sends address: “DHCP ack” msg
Network Layer
DHCP client-server scenario
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
223.1.3.27
arriving DHCP
client needs
address in this
Network Layer
DHCP server: 223.1.2.5
DHCP discover
src : 0.0.0.0, 68
dest.: 255.255.255.255,67
yiaddr: 0.0.0.0
transaction ID: 654
DHCP offer
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 654
lifetime: 3600 secs
DHCP request
src: 0.0.0.0, 68
dest:: 255.255.255.255, 67
yiaddrr: 223.1.2.4
transaction ID: 655
lifetime: 3600 secs
src: 223.1.2.5, 67
dest: 255.255.255.255, 68
yiaddrr: 223.1.2.4
transaction ID: 655
lifetime: 3600 secs
DHCP client-server scenario
is there a DHCP server out there?
I’m a DHCP server! Here’s an IP address you can use
OK. I’ll take that IP address!
OK. You’ve got that IP address!
Network Layer
DHCP: more than IP addresses
DHCP can return more than just allocated IP address on subnet:
address of first-hop router for client
name and IP address of DNS server
network mask (indicating network versus host portion of address)
Network Layer
connecting laptop needs its IP address, addr of first-hop router, addr of DNS server: use DHCP
router with DHCP
server built into
DHCP request encapsulated in UDP, encapsulated in IP, encapsulated in 802.3 Ethernet
Ethernet frame broadcast (dest: FFFFFFFFFFFF) on LAN, received at router running DHCP server
Ethernet decapsulated to IP decapsulated to UDP decapsulated to DHCP
DHCP: example
Network Layer
DHCP server formulates DHCP ACK containing client’s IP address, IP address of first-hop router, name & IP address of DNS server
encapsulation of DHCP ACK, frame is forwarded to client and decapsulated up to DHCP at client
DHCP: example
router with DHCP
server built into
client now knows its IP address, name and IP address of DSN server, IP address of its first-hop router
Network Layer
IP addressing: the last word…
Q: how does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned
Names and Numbers (http://www.icann.org/)
allocates addresses
manages DNS
assigns domain names, resolves disputes
Network Layer
Chapter 4: summary
Question: how are forwarding tables computed?
Answer: by the control plane
4.1 Overview of network layer: data plane and control plane
4.2 What’s inside a router
4.3 IP: Internet Protocol
IPv4 addressing
datagram format
fragmentation
Network Layer
5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the Internet
5.4 routing among the ISPs: BGP
Chapter 5: outline
Network Layer
Chapter 5: goals
understand principles behind network control plane
routing algorithms
Internet routing protocols:
RIP, OSPF, BGP
Network Layer
Network-layer functions
forwarding: move packets from router’s input to appropriate router output
data plane
control plane
Two approaches to structuring network control plane:
per-router control (traditional)
logically centralized control (software defined networking)
Two network-layer functions:
routing: determine route taken by packets from source to destination
Network Layer
Per-router control plane
Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding tables
values in arriving
packet header
Network Layer
Logically centralized control plane
A distinct (typically remote) controller interacts with local control agents (CAs) in routers to compute forwarding tables
Remote Controller
values in arriving
packet header
Network Layer
5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the Internet
5.4 routing among the ISPs: BGP
Chapter 5: outline
Network Layer
Routing protocols
Routing protocol goal: determine “good” paths (equivalently, routes), from sending hosts to receiving host, through network of routers
path: sequence of routers packets will traverse in going from given initial source host to given final destination host
“good”: least “cost”, “fastest”, “least congested”
routing: a “top-10” networking challenge!
Network Layer
graph: G = (N,E)
N = set of routers = { u, v, w, x, y, z }
E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
Graph abstraction of the network
aside: graph abstraction is useful in other network contexts, e.g.,
P2P, where N is set of peers and E is set of TCP connections
Network Layer
Graph abstraction: costs
c(x,x’) = cost of link (x,x’)
e.g., c(w,z) = 5
cost could always be 1, or
inversely related to bandwidth,
or inversely related to
congestion
cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
key question: what is the least-cost path between u and z ?
routing algorithm: algorithm that finds that least cost path
Network Layer
Routing algorithm classification
Q: global or decentralized information?
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
Q: static or dynamic?
routes change slowly over time
routes change more quickly
periodic update
in response to link cost changes
Network Layer
5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the Internet
5.4 routing among the ISPs: BGP
Chapter 5: outline
Network Layer
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 forwarding table for that node
iterative: after k iterations, know least cost path to k dest.’s
c(x,y): link cost from node x to y; = ∞ if not direct neighbors
D(v): current value of cost of path from source to dest. v
p(v): predecessor node along path from source to v
N’: set of nodes whose least cost path definitively known
Network Layer
Dijsktra’s algorithm
1 Initialization:
2 N’ = {u}
3 for all nodes v
4 if v adjacent to u
5 then D(v) = c(u,v)
6 else D(v) = ∞
9 find w not in N’ such that D(w) is a minimum
10 add w to N’
11 update D(v) for all v adjacent to w and not in N’ :
12 D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N’
algorithm complexity: n nodes
each iteration needs to check all nodes, w, not in N’
n(n+1)/2 comparisons: O(n2)
Network Layer
Dijkstra’s algorithm: example
construct shortest path tree by tracing predecessor nodes
ties can exist (can be broken arbitrarily)
Network Layer
Dijkstra’s algorithm: another example
resulting shortest-path tree from u:
destination
resulting forwarding table in u:
Network Layer
5.1 introduction
5.2 routing protocols
link state
distance vector
5.3 intra-AS routing in the Internet
5.4 routing among the ISPs: BGP
5.5 broadcast and multicast routing
5.6 ICMP: The Internet Control Message Protocol
5.7 Network management and SNMP
Chapter 5: outline
Network Layer
Distance vector algorithm
Bellman-Ford equation (dynamic programming)
dx(y) := cost of least-cost path from x to y
dx(y) = min {c(x,v) + dv(y) }
cost from x to neighbor v
min taken over all neighbors v of x
cost from neighbor v to destination y
Network Layer
Bellman-Ford example
known that
dv(z) = 5, dx(z) = 3, dw(z) = 3
du(z) = min { c(u,v) + dv(z),
c(u,x) + dx(z),
c(u,w) + dw(z) }
= min {2 + 5,
5 + 3} = 4
in forwarding table, the next hop in shortest path is
set to node achieving minimum
B-F equation says:
Network Layer
Distance vector algorithm
Dx(y) = estimate of least cost from x to y
x maintains distance vector Dx = [Dx(y): y є N ]
knows cost to each neighbor v: c(x,v)
maintains its neighbors’ distance vectors. For each neighbor v, x maintains
Dv = [Dv(y): y є N ]
Network Layer
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com