程序代写代做代考 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

Hierarchical routing

scale: with 600 million
destinations:

v  can’t store all dest’s in
routing tables!

v  routing table exchange
would swamp links!

administrative
autonomy

v  internet = network of
networks

v  each network admin may
want to control routing in
its own network

our routing study thus far – idealization
v  all routers identical
v  network “flat”
… not true in practice

Network Layer 4-4

v  aggregate routers
into regions,
“autonomous
systems” (AS)

v  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:
v  at “edge” of its own AS
v  has link to router in

another AS

Hierarchical routing

Network Layer 4-5

3b

1d

3a
1c

2a AS3

AS1
AS2

1a

2c
2b

1b

Intra-AS
Routing
algorithm

Inter-AS
Routing
algorithm

Forwarding
table

3c

Interconnected ASes

v  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

Network Layer 4-6

Inter-AS tasks
v  suppose router in AS1

receives datagram
destined outside of
AS1:
§  router should forward

packet to gateway
router, but which
one?

AS1 must:
1.  learn which dests are

reachable through
AS2, which through
AS3

2.  propagate this
reachability info to all
routers in AS1

job of inter-AS routing!

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

Network Layer 4-7

Example: setting forwarding table in router
1d
v  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
v  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)

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

x …

Network Layer 4-8

Example: choosing among multiple ASes
v  now suppose AS1 learns from inter-AS protocol that

subnet x is reachable from AS3 and from AS2.
v  to configure forwarding table, router 1d must determine

which gateway it should forward packets towards for
dest x
§  this is also job of inter-AS routing protocol!

AS3

AS2

3b

3c
3a

AS1

1c
1a

1d
1b

2a
2c

2b
other
networks

other
networks

x …

?

Network Layer 4-9

learn from inter-AS
protocol that subnet
x is reachable via
multiple gateways

use routing info
from intra-AS

protocol to determine
costs of least-cost

paths to each
of the gateways

hot potato routing:
choose the gateway

that has the
smallest least cost

determine from
forwarding table the
interface I that leads

to least-cost gateway.
Enter (x,I) in

forwarding table

Example: choosing among multiple ASes

v  now suppose AS1 learns from inter-AS protocol that
subnet x is reachable from AS3 and from AS2.

v  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!

v  hot potato routing: send packet towards closest of two
routers.

Network Layer 4-10

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

Outline

Network Layer 4-11

Intra-AS Routing

v  also known as interior gateway protocols
(IGP)

v  most common intra-AS routing protocols:
§ RIP: Routing Information Protocol
§ OSPF: Open Shortest Path First
§  IGRP: Interior Gateway Routing Protocol

(Cisco proprietary)

Network Layer 4-12

RIP (Routing Information Protocol)
v  included in BSD-UNIX distribution in 1982
v  distance vector algorithm

§  distance metric: # hops (max = 15 hops), each link has cost 1
§  DVs exchanged with neighbors every 30 sec in response

message (aka advertisement)
§  each advertisement: list of up to 25 destination subnets (in IP

addressing sense)

D C

B A
u v

w

x

y
z

subnet hops
u 1
v 2
w 2
x 3
y 3
z 2

from router A to destination subnets:

Network Layer 4-13

RIP: example

destination subnet next router # hops to dest
w A 2

y B 2
z B 7

x — 1
…. …. ….

routing table in router D

w x y
z

A

C

D B

Network Layer 4-14

w x y
z

A

C

D B

destination subnet next router # hops to dest
w A 2

y B 2
z B 7

x — 1
…. …. ….

routing table in router D

A 5

dest next hops
w – 1
x – 1
z C 4
…. … …

A-to-D advertisement
RIP: example

Network Layer 4-15

RIP: link failure, recovery
if no advertisement heard after 180 sec –>

neighbor/link declared dead
§  routes via neighbor invalidated
§  new advertisements sent to neighbors
§  neighbors in turn send out new advertisements (if

tables changed)
§  poison reverse used to prevent ping-pong loops

(infinite distance = 16 hops)

Network Layer 4-16

RIP table processing

v  RIP routing tables managed by application-
level process called route-d (daemon)

v  advertisements sent in UDP packets,
periodically repeated

physical
link

network forwarding
(IP) table

transport
(UDP)

routed

physical
link

network
(IP)

transprt
(UDP)

routed

forwarding
table

Network Layer 4-17

OSPF (Open Shortest Path First)
v  “open”: publicly available
v  uses link state algorithm

§  LS packet dissemination
§  topology map at each node
§  route computation using Dijkstra’s algorithm

v  OSPF advertisement carries one entry per
neighbour

v  advertisements flooded to entire AS
§  carried in OSPF messages directly over IP (rather

than TCP or UDP

Network Layer 4-18

OSPF “advanced” features (not in
RIP)

v  security: all OSPF messages authenticated (to
prevent malicious intrusion)

v  multiple same-cost paths allowed (only one path
in RIP)

v  for each link, multiple cost metrics for different
TOS (e.g., satellite link cost set “low” for best
effort ToS; high for real time ToS)

v  hierarchical OSPF in large domains.

Network Layer 4-19

Hierarchical OSPF
boundary router

backbone router

area 1
area 2

area 3

backbone
area
border
routers

internal
routers

Network Layer 4-20

v  two-level hierarchy: local area, backbone.
§  link-state advertisements only in area
§  each node has detailed area topology

v  area border routers: “summarize” distances to
nets in own area, advertise to other Area Border
routers.

v  backbone routers: run OSPF routing limited to
backbone.

v  boundary routers: connect to other AS’s.

Hierarchical
OSPF

Network Layer 4-21

Summary

v  Hierarchical routing
v  Intra-AS routing in the Internet

§  RIP
§  OSPF