程序代写代做代考 algorithm Network Layer

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-2

v  introduction
v  virtual circuit and datagram networks
v  what’s inside a router
v  IP: Internet Protocol

§  datagram format
§  IPv4 addressing (NAT)
§  ICMP, IPv6

v  routing algorithms
§  link state, distance vector
§  hierarchical routing

v  routing in the Internet
§  RIP, OSPF
§  BGP

v  broadcast routing

Outline

Network Layer 4-3

Internet inter-AS routing: BGP
v  BGP (Border Gateway Protocol): the de facto

inter-domain routing protocol
§  “glue that holds the Internet together”

v  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.
v  allows subnet to advertise its existence to

rest of Internet: “I am here”

Network Layer 4-4

BGP basics

v  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

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

v  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

BGP
message

Network Layer 4-5

BGP basics: distributing path
information

AS3

AS2

3b
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

v  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
v  when router learns of new prefix, it creates entry for

prefix in its forwarding table.

eBGP session

iBGP session

Network Layer 4-6

Path attributes and BGP
routes
v  advertised prefix includes BGP attributes

§  prefix + attributes = “route”
v  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.
v  gateway router receiving route advertisement

uses import policy to accept/decline
§  e.g., never route through AS x
§  policy-based routing

Network Layer 4-7

BGP route selection
v  router may learn about more than 1 route to

destination AS, selects route based on:
1.  local preference value attribute: policy decision
2.  shortest AS-PATH
3.  closest NEXT-HOP router: hot potato routing
4.  additional criteria

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

v  Answer is complicated!

v  Ties together hierarchical routing (Section
4.5.3) with BGP (4.6.3) and OSPF (4.6.2).

v  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
1.  Router becomes aware of prefix
2.  Router determines output port for prefix
3.  Router enters prefix-port in forwarding table

How does entry get in forwarding
table?

Router becomes aware of
prefix

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

BGP
message

v  BGP message contains “routes”
v  “route” is a prefix and attributes: AS-PATH, NEXT-HOP,

v  Example: route:
v  Prefix:138.16.64/22 ; AS-PATH: AS3 AS131 ;

NEXT-HOP: 201.44.13.125

Router may receive multiple
routes

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

BGP
message

v  Router may receive multiple routes for same
prefix

v  Has to select one route

v  Router selects route based on shortest AS-
PATH

Select best BGP route to
prefix

v  Example:

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

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

select

Find best intra-route to BGP
route

v  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.
v  Example:

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

to 111.99.86.55

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

111.99.86.55

Router identifies port for route

v  Identifies port along the OSPF shortest path
v  Adds prefix-port entry to its forwarding table:

§  (138.16.64/22 , port 4)

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

router
port

1
2 3

4

Hot Potato Routing
v  Suppose there two or more best inter-routes.
v  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 AS201 since it is closer

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

Summary
1.  Router becomes aware of prefix

§  via BGP route advertisements from other routers
2.  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
3.  Enter prefix-port entry in forwarding table

How does entry get in forwarding
table?

Network Layer 4-18

BGP routing policy

v  A,B,C are provider networks
v  X,W,Y are customer (of provider networks)
v  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 4-19

BGP routing policy (2)

v  A advertises path AW to B
v  B advertises path BAW to X
v  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 4-20

Why different Intra-, Inter-AS
routing ?
policy:
v  inter-AS: admin wants control over how its traffic

routed, who routes through its net.
v  intra-AS: single admin, so no policy decisions

needed
scale:
v  hierarchical routing saves table size, reduced

update traffic
performance:
v  intra-AS: can focus on performance
v  inter-AS: policy may dominate over performance

Network Layer 4-21

v  introduction
v  virtual circuit and datagram networks
v  what’s inside a router
v  IP: Internet Protocol

§  datagram format
§  IPv4 addressing (NAT)
§  ICMP, IPv6

v  routing algorithms
§  link state, distance vector
§  hierarchical routing

v  routing in the Internet
§  RIP, OSPF
§  BGP

v  broadcast routing

Outline

Network Layer 4-22

R1

R2

R3 R4

source
duplication

R1

R2

R3 R4

in-network
duplication

duplicate
creation/transmission duplicate

duplicate

Broadcast routing
v  deliver packets from source to all other nodes
v  source duplication is inefficient:

v  source duplication: how does source determine
recipient addresses?

Network Layer 4-23

In-network duplication
v  flooding: when node receives broadcast

packet, sends copy to all neighbors
§  problems: cycles & broadcast storm

v  controlled flooding: node only broadcasts pkt
if it hasn’t broadcast same packet before
§  node keeps track of packet ids already

broadcasted
§  or reverse path forwarding (RPF): only forward

packet if it arrived on shortest path between node
and source

v  spanning tree:
§  no redundant packets received by any node

Reverse Path Forwarding

Network Layer 4-24

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

v  Some redundant packets

Network Layer 4-25

A

B

G

D
E

c

F

A

B

G

D
E

c

F

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

Spanning tree
v  first construct a spanning tree
v  nodes then forward/make copies only along

spanning tree

Network Layer 4-26

A

B

G

D
E

c

F
1

2

3

4

5

(a) stepwise construction of
spanning tree (center: E)

A

B

G

D
E

c

F

(b) constructed spanning
tree

Spanning tree: creation
v  center node
v  each node sends unicast join message to

center node
§  message forwarded until it arrives at a node

already belonging to spanning tree

Network Layer 4-27

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, ICMP, IPv6

4.5 routing algorithms
§  link state, distance

vector, hierarchical
routing

4.6 routing in the Internet
§  RIP, OSPF, BGP

4.7 broadcast and
multicast routing

Network Layer: done!

v  understand principles behind network layer services:
§  network layer service models, forwarding versus

routing how a router works, routing (path selection),
broadcast, multicast

v  instantiation, implementation in the Internet