CS计算机代考程序代写 algorithm dns DHCP assembly Chapter 4 Network Layer

Chapter 4 Network Layer
A note on the use of these ppt slides:
We’re making these slides freely available to all (faculty, students, readers). They’re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following:
❑ If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we’d like people to use our book!)
❑ If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material.
Thanks and enjoy! JFK/KWR
All material copyright 1996-2007
J.F Kurose and K.W. Ross, All Rights Reserved
Computer Networking: A Top Down Approach , 6th edition.
Jim Kurose, Keith Ross
Network Layer 4-1

Chapter 4: Network Layer
Chapter goals:
understand principles behind network layer services:
 network layer service models  forwarding versus routing
 how a router works
 routing (path selection)
 dealing with scale
instantiation, implementation in the Internet
Network Layer 4-2

Chapter 4: Network Layer
 4. 1 Introduction  4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-3

Network layer
 transport segment from sending to receiving host
 on sending side encapsulates segments into datagrams
 on rcving side, delivers segments to transport layer
 network layer protocols in every host, router
 router examines header fields in all IP datagrams passing through it
network
network
data link physical
application
transport
network
data link
physical
network
network
data link
data link
network
data link
physical
physical
network
physical
network
data link
data link
physical
physical
data link physical
network
data link
physical
network
network
data link
transport
network
network
data link
physical
data link
physical
data link
physical
physical
application
Network Layer 4-4

Two Key Network-Layer Functions
forwarding: move packets from router’s input to appropriate router output
routing: determine route taken by packets from source to dest.
routing algorithms
analogy:
routing: process of planning trip from source to dest
forwarding: process of getting through single interchange
Network Layer 4-5

Interplay between routing and forwarding
routing algorithm
local forwarding table
header value
output link
0100 0101 0111 1001
3 2 2 1
value in arriving packet’s header
0111
3
1 2
Network Layer 4-6

Forwarding table
Destination Address Range
11001000 00010111 00010000 00000000 through
11001000 00010111 00010111 11111111
11001000 00010111 00011000 00000000 through
11001000 00010111 00011000 11111111
11001000 00010111 00011001 00000000 through
11001000 00010111 00011111 11111111 otherwise
Link Interface 0
1
2
3
4 billion possible entries
Network Layer 4-7

Longest prefix matching
Prefix Match 11001000 00010111 00010
11001000 00010111 00011000 11001000 00010111 00011
otherwise
Examples
Link Interface 0
1 2 3
DA: 11001000 00010111 00010110 10100001 DA: 11001000 00010111 00011000 10101010
Which interface? Which interface?
Network Layer 4-8

Router Architecture Overview
Two key router functions:
 run routing algorithms/protocol (RIP, OSPF, BGP)
 forwarding datagrams from incoming to outgoing link
Network Layer 4-10

Three types of switching fabrics
Network Layer 4-11

Output port queueing
 buffering when arrival rate via switch exceeds output line speed
 queueing (delay) and loss due to output port buffer overflow!
Network Layer 4-12

How much buffering?
RFC 3439 rule of thumb: average buffering equal to “typical” RTT (say 250 msec) times link capacity C
 e.g., C = 10 Gps link: 2.5 Gbit buffer Recent recommendation: with N flows,
buffering equal to
RTT. C
N
Network Layer 4-13

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-14

The Internet Network layer
Host, router network layer functions:
Transport layer: TCP, UDP
Routing protocols
•path selection •RIP, OSPF, BGP
forwarding table
ICMP protocol
•error reporting •router “signaling”
IP protocol
•addressing conventions •datagram format
•packet handling conventions
Link layer
physical layer
Network layer
Network Layer 4-15

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-16

IP datagram format
IP protocol version number header length (bytes)
“type” of data
max number remaining hops
(decremented at each router)
upper layer protocol to deliver payload to
32 bits
total datagram length (bytes)
for fragmentation/ reassembly
ver
head. len
type of service
length
fragment offset
16-bit identifier
time to live
upper layer
32 bit destination IP address
Options (if any)
flgs
data (variable length,
typically a TCP or UDP segment)
header checksum
32 bit source IP address
E.g. timestamp, record route taken, specify list of routers to visit.
how much overhead with TCP?
 20 bytes of TCP
 20 bytes of IP
 = 40 bytes + app layer overhead
Network Layer 4-17

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-18

IP Addressing: introduction
 IP address: 32-bit identifier for host, router interface
 interface: connection between host/router and physical link
 router’s typically have multiple interfaces
 host typically has one interface
 IP addresses associated with each interface
223.1.1.1 223.1.1.2
223.1.2.1 223.1.1.4 223.1.2.9
223.1.1.3
223.1.3.1
223.1.3.27
223.1.2.2
223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1
223.1.3.2
Network Layer 4-19

Subnets  IP address:
 subnet part (high order bits)
 host part (low order bits)
 What’s a subnet ?
 device interfaces with same subnet part of IP address
 can physically reach each other without intervening router
223.1.1.1 223.1.1.2
223.1.2.1 223.1.1.4 223.1.2.9
223.1.1.3
223.1.3.1
223.1.3.27 223.1.2.2
subnet
223.1.3.2
network consisting of 3 subnets
Network Layer 4-20

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.
223.1.1.0/24
223.1.2.0/24
223.1.3.0/24
Subnet mask: /24
Network Layer 4-21

Subnets How many?
223.1.1.2
223.1.1.1
223.1.1.4
223.1.1.3
223.1.9.2
223.1.7.0
223.1.9.1
223.1.2.6
223.1.8.1
223.1.2.2
223.1.8.0
223.1.3.1
223.1.7.1
223.1.3.27 223.1.3.2
223.1.2.1
Network Layer 4-22

IP addresses: how to get one?
Q: How does host get IP address?  hard-coded by system admin in a file
 Wintel: control-panel->network->configuration- >tcp/ip->properties
 UNIX: /etc/rc.config
 DHCP: Dynamic Host Configuration Protocol:
dynamically get address from as server  “plug-and-play”
Network Layer 4-23

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
Network Layer 4-24

DHCP client-server scenario
A
B
223.1.3.1
223.1.2.1
223.1.1.1 223.1.1.2
DHCP server
223.1.1.4 223.1.2.9
223.1.1.3
223.1.3.27
223.1.2.2 E 223.1.3.2
arriving DHCP client needs address in this network
Network Layer 4-25

DHCP client-server scenario
DHCP server: 223.1.2.5
arriving client
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
time
DHCP ACK
src: 223.1.2.5, 67
dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs
Network Layer 4-26

IP addresses: how to get one?
Q: How does network get subnet part of IP addr?
A: gets allocated portion of its provider ISP’s address space
ISP’s block
Organization 0 Organization 1 Organization 2
… Organization 7
11001000 00010111 00010000 00000000
11001000 00010111 00010000 00000000 11001000 00010111 00010010 00000000 11001000 00010111 00010100 00000000
….. …. 11001000 00010111 00011110 00000000
200.23.16.0/20
200.23.16.0/23 200.23.18.0/23 200.23.20.0/23
…. 200.23.30.0/23
Network Layer 4-27

Hierarchical addressing: route aggregation
Hierarchical addressing allows efficient advertisement of routing information:
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2 .
“Send me anything with addresses beginning 200.23.16.0/20”
200.23.20.0/23
. Fly-By-Night-ISP .
ISPs-R-Us
. . .
200.23.30.0/23
Internet
Organization 7
“Send me anything with addresses beginning 199.31.0.0/16”
Network Layer 4-28

Hierarchical addressing: more specific routes
ISPs-R-Us has a more specific route to Organization 1
Organization 0
200.23.16.0/23
Organization 2 .
“Send me anything with addresses beginning 200.23.16.0/20”
200.23.20.0/23
. Fly-By-Night-ISP .
ISPs-R-Us
. . .
200.23.30.0/23
Organization 1
200.23.18.0/23
Internet
Organization 7
“Send me anything with addresses beginning 199.31.0.0/16 or 200.23.18.0/23”
Network Layer 4-29

IP addressing: the last word…
Q: How does an ISP get block of addresses?
A: ICANN: Internet Corporation for Assigned Names and Numbers
 allocates addresses
 manages DNS
 assigns domain names, resolves disputes
Network Layer 4-30

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-31

Interplay between routing, forwarding
routing algorithm
local forwarding table
header value
output link
0100 0101 0111 1001
3 2 2 1
value in arriving packet’s header
0111
3
1 2
Network Layer 4-32

Graph abstraction
5
u2v3w5 231z
1xy2 Graph: G = (N,E) 1
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) }
Remark: Graph abstraction is useful in other network contexts
Network Layer 4-33

Graph abstraction: costs
u2 1
5
v
2 x
3
3 1
w 5 1
z
• 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
y 2
Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Question: What’s the least-cost path between u and z ?
Routing algorithm: algorithm that finds least-cost path
Network Layer 4-34

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
Static or dynamic?
Static:
 routes change slowly over time
Dynamic:
 routes change more quickly
 periodic update
 in response to link
cost changes
Network Layer 4-35
 “distance vector” algorithms

Chapter 4: Network Layer
 4. 1 Introduction
 4.2 Virtual circuit and
datagram networks
 4.3 What’s inside a router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 RIP  OSPF  BGP
Network Layer 4-36

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
Notation:
 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 4-37

Dijsktra’s Algorithm
1 Initialization: 2 N’={u}
3 4 5 6 7 8 9 10 11 12 13 14 15
for all nodes v
if v adjacent to u
then D(v) = c(u,v) else D(v) = ∞
Loop
find w not in N’ such that D(w) is a minimum add w to N’
update D(v) for all v adjacent to w and not in N’ :
D(v) = min( D(v), D(w) + c(w,v) )
/* new cost to v is either old cost to v or known shortest path cost to w plus cost from w to v */
until all nodes in N’
Network Layer 4-38

Dijkstra’s algorithm: example
Step N’ D(v),p(v) D(w),p(w)
D(x),p(x) D(y),p(y) D(z),p(z) 1,u ∞ ∞
0 u 1 ux 2 uxy 3 uxyv 4 uxyvw 5 uxyvwz
2,u 5,u 2,u 4,x 2,u 3,y
3,y
5 v3w5
231z x1y2
2,x
∞
4,y 4,y 4,y
u2 1
Network Layer 4-39

Dijkstra’s algorithm: example (2)
Resulting shortest-path tree from u:
vw u
z xy
Resulting forwarding table in u:
destination
v x
y w z
link
(u,v) (u,x)
(u,x) (u,x) (u,x)
Network Layer 4-40

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(n2)
Network Layer 4-41

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-42

Distance Vector Algorithm
Bellman-Ford Equation (dynamic programming)
Define
dx(y) := cost of least-cost path from x to y
Then
dx(y) = min {c(x,v) + dv(y) }
v
where min is taken over all neighbors v of x
Network Layer 4-43

Bellman-Ford example
u2 1
5 v3w5
231z
xy2 1
Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3
B-F equation says:
du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z),
c(u,w) + dw(z) } = min {2 + 5,
1 + 3, 5+3} =4
Node that achieves minimum is next
hop in shortest path ➜ forwarding table
Network Layer 4-44

Distance Vector Algorithm
Dx(y) = estimate of least cost from x to y Node x knows cost to each neighbor v:
c(x,v)
 Node x maintains distance vector Dx = [Dx(y): y є N ]
Node x also maintains its neighbors’ distance vectors
 For each neighbor v, x maintains Dv = [Dv(y): y є N ]
Network Layer 4-45

Distance vector algorithm (4)
Basic idea:
 Each node periodically sends its own distance vector estimate to neighbors
 When a node x receives new DV estimate from neighbor, it updates its own DV using B-F equation:
Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N  Under minor, natural conditions, the estimate
Dx(y) converge to the actual least cost dx(y)
Network Layer 4-46

Distance Vector Algorithm (5)
Iterative, asynchronous:
each local iteration caused by:
 local link cost change
 DV update message from
neighbor
Distributed:
 each node notifies neighbors only when its DV changes
 neighbors then notify their neighbors if necessary
Each node:
wait for (change in local link cost or msg from neighbor)
recompute estimates if DV to any dest has
changed, notify neighbors
Network Layer 4-47

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
cost to cost to xyz xyz
x027 x023
Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
node x table
node y table
y∞∞∞ y z∞∞∞ z
201 710
cost to
xyz 2y1
node z table
x∞∞∞ x
z
y201 7
z∞∞∞
cost to xyz
x ∞∞ ∞
y z
∞∞∞ 710
time
Network Layer 4-48
from from from
from

Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)}
= min{2+1 , 7+0} = 3
cost to xyz
x023
y201 z310
cost to
xyz 2y1
x023 x y201 7
node x table
Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2
cost to xyz
x027
cost to xyz
x023
y201 z710
cost to xyz
x027
y201 z710
cost to xyz
node y table
y∞∞∞ z∞∞∞
cost to xyz
x∞∞∞
y201
z
node z table
cost to xyz
z∞∞∞
z310
cost to xyz
x027 x023 y201 y201
z310 z310 time
x ∞∞ ∞
y∞∞∞ z710
Network Layer 4-49
from from from
from from from
from
from from

Comparison of LS and DV algorithms
Message complexity
 LS: with n nodes, E links,
O(nE) msgs sent
 DV: exchange between neighbors only
Robustness: what happens if router malfunctions?
LS:
 node can advertise incorrect link cost
 each node computes only its own table
DV:
 DV node can advertise incorrect path cost
 each node’s table used by others
• error propagate thru network
 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
Network Layer 4-50

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-51

Hierarchical Routing
Our routing study thus far – idealization  all routers identical
 network “flat”
… not true in practice
scale: with 200 million destinations:
 can’t store all dest’s in routing tables!
 routing table exchange would swamp links!
administrative autonomy
 internet = network of networks
 each network admin may want to control routing in its own network
Network Layer 4-52

Hierarchical Routing
 aggregate routers into regions, “autonomous systems” (AS)
 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
 Direct link to router in another AS
Network Layer 4-53

Interconnected ASes
3c 3a
3b AS3 1c 2a
1a1d 1bAS1
2c AS2 2b
 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
Intra-AS Routing algorithm
Inter-AS Routing algorithm
Forwarding table
Network Layer 4-54

Inter-AS tasks
 suppose router in AS1 receives datagram dest outside of AS1
 router should forward packet to gateway router, but which one?
AS1 must:
1. learn which dests reachable through AS2, which through AS3
2. propagate this reachability info to all routers in AS1
Job of inter-AS routing!
2c AS2 2b
3c 3a 3b AS3
1c
1a1d 1bAS1
2a
Network Layer 4-55

Example: Setting forwarding table in router 1d
 suppose AS1 learns (via inter-AS protocol) that subnet x reachable via AS3 (gateway 1c) but not via AS2.
 inter-AS protocol propagates reachability info to all internal routers.
 router 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c.
 installs forwarding table entry (x,I) x
3c 3a 3b AS3
1c 1a 1d
2a 1b AS1
2c
2b
AS2
Network Layer 4-56

Example: Choosing among multiple ASes
 now suppose AS1 learns from inter-AS protocol that subnet x is reachable from AS3 and from AS2.
 to configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x.
 this is also job of inter-AS routing protocol!
 hot potato routing: send packet towards closest of two routers.
Determine from forwarding table the interface I that leads to least-cost gateway. Enter (x,I) in
forwarding table
Learn from inter-AS protocol that subnet x is reachable via
multiple gateways
Hot potato routing: Choose the gateway that has the smallest least cost
Use routing info from intra-AS protocol to determine costs of least-cost paths to each
of the gateways
Network Layer 4-58

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-59

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
Network Layer 4-60

Chapter 4: Network Layer
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-61

Internet inter-AS routing: BGP
 BGP (Border Gateway Protocol): the de facto standard
 BGP provides each AS a means to:
1. Obtain subnet reachability information from
2. Propagate reachability information to all AS- internal routers.
3. Determine “good” routes to subnets based on reachability information and policy.
 allows subnet to advertise its existence to rest of Internet: “I am here”
neighboring ASs.
Network Layer 4-62

BGP basics
 pairs of routers (BGP peers) exchange routing info over semi-permanent TCP connections: BGP sessions
 BGP sessions need not correspond to physical links.
 when AS2 advertises prefix to AS1:
 AS2 promises it will forward any addresses
datagrams towards that prefix.
 AS2 can aggregate prefixes in its advertisement
3c
3a
3b AS3 1c
eBGP session iBGP session
2c AS2 2b
Network Layer 4-63
2a
1a1d 1b AS1

Distributing reachability info
 using eBGP session between 3a and 1c, AS3 sends prefix reachability info to AS1.
 1c can then use iBGP do distribute new prefix info to all routers in AS1
 1b can then re-advertise new reachability info to AS2 over 1b-to-2a eBGP session
 when router learns of new prefix, creates entry for prefix in its forwarding table.
3c
3a
3b AS3 1c
eBGP session iBGP session
2c AS2 2b
Network Layer 4-64
2a
1a1d 1b AS1

BGP route selection
 router may learn about more than 1 route to some prefix. Router must select route.
 elimination rules:
1. local preference value attribute: policy
decision
2. shortest AS-PATH
3. closest NEXT-HOP router: hot potato routing
4. additional criteria
Network Layer 4-65

BGP routing policy
W
B
A
C
legend: X
Y
provider network
customer network:
 A,B,C are provider networks
 X,W,Y are customer (of provider networks)  X is dual-homed: attached to two networks
X does not want to route from B via X to C .. so X will not advertise to B a route to C
Network Layer 4-66

BGP routing policy (2)
legend: X
Y
 A advertises path AW to B
 B advertises path BAW to X
 Should B advertise path BAW to C?
provider network
customer network:
W
B
A
C
 No way! B gets no “revenue” for routing CBAW since neither W nor C are B’s customers
B wants to force C to route to w via A
 B wants to route only to/from its customers!
Network Layer 4-67

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
Network Layer 4-68

Chapter 4: summary
 4. 1 Introduction
 4.3 What’s inside a
router
 4.4 IP: Internet Protocol
 Datagram format  IPv4 addressing
 4.5 Routing algorithms  Link state
 Distance Vector
 Hierarchical routing
 4.6 Routing in the Internet
 OSPF  BGP
Network Layer 4-69

Related Posts