程序代写 PowerPoint 簡報

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-panelnetworkconfiguration tcp/ipproperties
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