CS计算机代考程序代写 algorithm PowerPoint Presentation

PowerPoint Presentation

Network Layer
All material copyright 1996-2012
J.F Kurose and K.W. Ross, All Rights Reserved
George Parisis
School of Engineering and Informatics
University of Sussex

Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol

datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms

link state, distance vector
hierarchical routing
routing in the Internet

RIP, OSPF
BGP
broadcast routing

Outline

Network Layer

Network Layer
4-*
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): the de facto inter-domain routing protocol

“glue that holds the Internet together”
BGP provides each AS a means to:

eBGP: obtain subnet reachability information from neighboring ASs.
iBGP: propagate reachability information to all AS-internal routers.
determine “good” routes to other networks based on reachability information and policy.
allows subnet to advertise its existence to rest of Internet: “I am here”

Network Layer

Network Layer
4-*
BGP basics
when AS3 advertises a prefix to AS1:

AS3 promises it will forward datagrams towards that prefix
AS3 can aggregate prefixes in its advertisement
AS3
AS2
other
networks
other
networks
BGP session: two BGP routers (“peers”) exchange BGP messages:
advertising paths to different destination network prefixes (“path vector” protocol)
exchanged over semi-permanent TCP connections

3b

3c

3a

1c

1a

1d

1b

AS1

2a

2c

2b

BGP
message

Network Layer

Network Layer
4-*
BGP basics: distributing path information
AS3
AS2
AS1
other
networks
other
networks
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, it creates entry for prefix in its forwarding table.

eBGP session
iBGP session

3b

3a

1c

1a

1d

1b

2a

2c

2b

Network Layer

Network Layer
4-*
Path attributes and BGP routes
advertised prefix includes BGP attributes

prefix + attributes = “route”
two important attributes:

AS-PATH: contains ASs through which prefix advertisement has passed: e.g., AS 67, AS 17
Prevent loops
NEXT-HOP: indicates specific internal-AS router to next-hop AS.
gateway router receiving route advertisement uses import policy to accept/decline

e.g., never route through AS x
policy-based routing

Network Layer

Network Layer
4-*
BGP route selection
router may learn about more than 1 route to destination AS, selects route based on:

local preference value attribute: policy decision
shortest AS-PATH
closest NEXT-HOP router: hot potato routing
additional criteria

Network Layer

Putting it Altogether:
How Does an Entry Get Into a Router’s Forwarding Table?
Answer is complicated!

Ties together hierarchical routing with BGP and OSPF.

Provides nice overview of BGP!

*

1
2
3

Dest IP
routing algorithms

local forwarding table
prefix
output port
138.16.64/22
124.12/16
212/8
…………..
3
2
4

How does entry get in forwarding table?

entry
Assume prefix is
in another AS.

*

High-level overview
Router becomes aware of prefix
Router determines output port for prefix
Router enters prefix-port in forwarding table
How does entry get in forwarding table?

*

Router becomes aware of prefix
AS3
AS2
other
networks
other
networks
BGP message contains “routes”
“route” is a prefix and attributes: AS-PATH, NEXT-HOP,…
Example: route:
Prefix:138.16.64/22 ; AS-PATH: AS3 AS131 ; NEXT-HOP: 201.44.13.125

3b

3c

3a

1c

1a

1d

1b

AS1

2a

2c

2b

BGP
message

*

Router may receive multiple routes
AS3
AS2
other
networks
other
networks

Router may receive multiple routes for same prefix
Has to select one route

3b

3c

3a

1c

1a

1d

1b

AS1

2a

2c

2b

BGP
message

*

Router selects route based on shortest AS-PATH

Select best BGP route to prefix
Example:

AS2 AS17 to 138.16.64/22
AS3 AS131 AS201 to 138.16.64/22

What if there is a tie? We’ll come back to that!

select

*

Find best intra-route to BGP route
Use selected route’s NEXT-HOP attribute

Route’s NEXT-HOP attribute is the IP address of the router interface that begins the AS PATH.
Example:

AS-PATH: AS2 AS17 ; NEXT-HOP: 111.99.86.55
Router uses OSPF to find shortest path from 1c to 111.99.86.55

111.99.86.55

3b

3c

3a

1c

1a

1d

1b

AS1

2a

2c

2b

AS3
AS2

other
networks

other
networks

*

Router identifies port for route
Identifies port along the OSPF shortest path
Adds prefix-port entry to its forwarding table:

(138.16.64/22 , port 4)
router
port
1
2
3
4

3b

3c

3a

1c

1a

1d

1b

AS1

2a

2c

2b

AS3
AS2

other
networks

other
networks

Hot Potato Routing
Suppose there two or more best inter-routes.
Then choose route with closest NEXT-HOP

Use OSPF to determine which gateway is closest
Q: From 1c, chose AS3 AS131 or AS2 AS17?
A: route AS3 AS131 since it is closer

3b

3c

3a

1c

1a

1d

1b

AS1

2a

2c

2b

AS3
AS2

other
networks

other
networks

Summary
Router becomes aware of prefix
via BGP route advertisements from other routers
Determine router output port for prefix
Use BGP route selection to find best inter-AS route
Use OSPF to find best intra-AS route leading to best inter-AS route
Router identifies router port for that best route
Enter prefix-port entry in forwarding table
How does entry get in forwarding table?

Network Layer
4-*
BGP routing policy

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

A
B

C

W

X

Y

legend:

customer
network:

provider

network

Network Layer

Network Layer
4-*
BGP routing policy (2)
A advertises path AW to B
B advertises path BAW to X
Should B advertise path BAW to 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!

A
B

C

W

X

Y

legend:

customer
network:

provider

network

Network Layer

Network Layer
4-*
Why different Intra-, 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

Network Layer
4-*
introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol

datagram format
IPv4 addressing (NAT)
ICMP, IPv6
routing algorithms

link state, distance vector
hierarchical routing
routing in the Internet

RIP, OSPF
BGP
broadcast routing

Outline

Network Layer

Network Layer
4-*
Broadcast routing
deliver packets from source to all other nodes
source duplication is inefficient:

source duplication: how does source determine recipient addresses?

R1

R2

R3

R4

R1

R2

R3

R4

source
duplication

in-network
duplication

duplicate
creation/transmission
duplicate

duplicate

Network Layer

Network Layer
4-*
In-network duplication
flooding: when node receives broadcast packet, sends copy to all neighbors

problems: cycles & broadcast storm
controlled flooding: node only broadcasts pkt if it hasn’t broadcast same packet before

node keeps track of packet ids already broadcast
or reverse path forwarding (RPF): only forward packet if it arrived on shortest path between node and source
spanning tree:

no redundant packets received by any node

Network Layer

Reverse Path Forwarding
Network Layer
4-*
Some redundant packets

Network Layer

Network Layer
4-*
Spanning tree
first construct a spanning tree
nodes then forward/make copies only along spanning tree

A

B

G

D

E

c

F

A

B

G

D

E

c

F

(a) broadcast initiated at A
(b) broadcast initiated at D

Network Layer

Network Layer
4-*
1
2
3
4
5
stepwise construction of spanning tree (center: E)

(b) constructed spanning tree
Spanning tree: creation
center node – rendezvous
each node sends unicast join message to center node

message forwarded until it arrives at a node already belonging to spanning tree

A

B

G

D

E

c

F

A

B

G

D

E

c

F

Network Layer

Network Layer
4-*
Introduction
virtual circuit and datagram networks
what’s inside a router
IP: Internet Protocol
datagram format, IPv4 addressing, ICMP, IPv6
routing algorithms
link state, distance vector, hierarchical routing
routing in the Internet
RIP, OSPF, BGP
broadcast routing
Network Layer: done!
understand principles behind network layer services:
network layer service models, forwarding versus routing how a router works, routing (path selection), broadcast, multicast
instantiation, implementation in the Internet

Network Layer

packet is duplicated and forwarded to all the node’s neighbors (except the node from
which the packet has just been received). The Gnutella protocol, discussed in Chap-
ter 2, uses sequence-number-controlled flooding to broadcast queries in its overlay
network. (In Gnutella, message duplication and forwarding is performed at the
application layer rather than at the network layer.)

A second approach to controlled flooding is known as reverse path forwarding
(RPF) [Dalal 1978], also sometimes referred to as reverse path broadcast (RPB). The
idea behind RPF is simple, yet elegant. When a router receives a broadcast packet
with a given source address, it transmits the packet on all of its outgoing links (except
the one on which it was received) only if the packet arrived on the link that is on its
own shortest unicast path back to the source. Otherwise, the router simply discards
the incoming packet without forwarding it on any of its outgoing links. Such a packet
can be dropped because the router knows it either will receive or has already received
a copy of this packet on the link that is on its own shortest path back to the sender.
(You might want to convince yourself that this will, in fact, happen and that looping
and broadcast storms will not occur.) Note that RPF does not use unicast routing to
actually deliver a packet to a destination, nor does it require that a router know the
complete shortest path from itself to the source. RPF need only know the next neigh-
bor on its unicast shortest path to the sender; it uses this neighbor’s identity only to
determine whether or not to flood a received broadcast packet.

Figure 4.44 illustrates RPF. Suppose that the links drawn with thick lines repre-
sent the least-cost paths from the receivers to the source (A). Node A initially broad-
casts a source-A packet to nodes C and B. Node B will forward the source-A packet
it has received from A (since A is on its least-cost path to A) to both C and D. B will
ignore (drop, without forwarding) any source-A packets it receives from any other

402 CHAPTER 4 • THE NETWORK LAYER

A

B

D

G

C

F E

Key:
pkt will be forwarded
pkt not forwarded beyond receiving router

Figure 4.44 ! Reverse path forwarding