計(jì)算機(jī)網(wǎng)絡(luò)復(fù)習(xí)-計(jì)算機(jī)網(wǎng)課件chapterip

NetworkLayer

4-1Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv64.5

RoutingalgorithmsLink

stateDistance

VectorHierarchical

routing4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingaddtition1,routetabledestination

,

mask

,

interface

,gatewayinterface

and

gateway

are

in

the

same

subnet.

8

8route

print;

netstat

-r[RouterA]int

e0/0[RouterA-Ethernet0/0]ip

addr

24[RouterA-Ethernet0/0]int

s0[RouterA-Serial0/0]ip

addr

30[RouterB]int

e0[RouterB-Ethernet0]ip

addr

24[RouterB-Ethernet0]int

s0[RouterB-Serial0]ip

addr

30Question:

how

to

configure

pc1

and

pc2

so

that

theycancommunicate?Configure

static

route[RouterA]ip

route-static

[RouterB]ip

route-static

[Router

b]dis

ip

routing-tableDestination/MaskProtocolPreCostNexthopInterface/24STATIC600Serial0/0/30DIRECT00Serial0/0/32DIRECT00InLoopBack0/32DIRECT00Serial0/0/24DIRECT00Ethernet0/0/32DIRECT00InLoopBack0/8DIRECT00InLoopBack0/32DIRECT00InLoopBack00destinationsubmaskNexthop28inter

02828Inter

1R23H1subnet1：netaddress

mask

28R1

route

tableR1Subnet

2：net

28mask

28H238H330

10

29R21

Subnet

3：net

mask

22,

How

to

route

a

datagram?0destinationsubmaskNexthop28inter

02828Inter

1R23H1subnet1：et

mask

28R1Subnet

2：net

28mask

28H23830

10

29R21 128

30

36

2Dest

ip:

38:

direct

delivery?Else:

deliver

to

R1.H1子網(wǎng)掩碼:28目的主機(jī)：128.30.

33.138128

→138

→1100000000001010:10000000*

128255.255.255128.

30.

33.1.12838128.

30.

33.128

H1

network

address:

direct

delivery?

NO!

why?Else:

deliver

to

R1.0destmasknext28inter

02828inter1R23H1R1H238H330

10

29R21

Subnet

3：net

mask

2subnet1：net

mask

28Subnet

2：net

28mask

280destmasknext2828

28接口0接口1R23H1subnet1：net

mask

255.255.255.

28R12：

2828H23830

10

29R228

and

38

=

28Not

match!：38not0destmasknext282828接口0接口1R23H1R1H23830

10

29R228

and

38

=

28yes!dest

IP

：382：28255.255.255

yes!subnet1：net

mask

28（路由聚合）:能以更少的表項(xiàng)表達(dá)R0的路由表嗎?目標(biāo)網(wǎng)絡(luò)子網(wǎng)掩碼下一站IP地址離出接口名字RIP距離I001I001I001I001R1R3/16/19/19/19I02I01I0017R0//16.1.1一般不對(duì)直連路由進(jìn)行聚合R3R2/16I01:/16

/19I00:R0

I02:I10:20R1/19I11:/191/16:I12I20:

2/16/19.:I21I22:/19I23:/19I30:/19I31:/16questionNetworkLayer

4-15Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv64.5

RoutingalgorithmsLink

stateDistance

VectorHierarchical

routing4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingNetwork

Layer

4-161230111value

inarrivingpacket’s

headerrouting

algorithmlocal

forwarding

tableheader

valueoutput

link01003010120111210011Interplay

between

routing,forwardinguwz21311y2535v2xGraph:

G

=

(N,E)Graph

ionN

=

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 ion

is

useful

in

other

network

contextsExample:

P2P,

where

N

is

set

ofpeers

andE

is

set

ofTCP

connectionsNetworkLayer

4-17Graphion:

costsuNetworkLayer

4-18wz21311y2535v2xc(x,x’)

=

cost

of

link

(x,x’)-

e.g.,

c(w,z)

=

5costcould

always

be

1,orinversely

related

to

bandwidth,or

inversely

related

tocongestionCostof

path

(x1,x2,

x3,…,

xp)=

c(x1,x2)

+

c(x2,x3)+

…

+

c(xp-1,xp)Question:

What’s

theleast-cost

path

between

u

and

z

?Routing

algorithm:

algorithm

that

findsleast-cost

pathNetworkLayer

4-19Routing

Algorithm

classificationGlobal

or

decentralizedinformation?Global:all

routers

have

completetopology,

link

cost

info“l(fā)ink

state”

algorithmsDecentralized:router

knows

physically-connected

neighbors,

linkcosts

to

neighborsiterative

process

ofcomputation,

exchange

ofinfo

with

neighbors“distance

vector”

algorithmsStatic

or

dynamic?Static:routes

change

slowlyover

timeDynamic:routes

change

morequicklyperiodic

updatein

response

tolinkcost

changes補(bǔ)充：Static

configuration[Quidway]

[undo]

ip

route-static

ip-address

{

mask

|

masklen

}{

interface-type

interface-name

|

nexthop-address

}

[

preference

value

][Quidway]

ip

route-static

16

[Quidway]

ip

route-static

[Quidway]

ip

route-static

16

Serial

2/16E0S0Quidway

A

Quidway

B

S0在路由器Quidway

A上配置：ip

route-static

ip

route-static

16

ip

route-static

16 s

0Default

routeQuidway

AS0

S0

Quidway

BPrivate

NetworkPublic

NetworkQuidway

A：ip

route-static

0

Network

Layer

4-23Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv64.5

Routing

algorithmsLink

stateDistance

VectorHierarchical

routing4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingNetwork

Layer

4-24A

Link-State

RoutingAlgorithmDijkstra’s

algorithmnet

topology,

link

costsknown

to

all

nodesplished

via

“l(fā)inkstate

broadcast”all

nodes

have

same

infocomputes

least

cost

pathsfrom

one

node

(‘source”)

toall

other

nodesgives

forwarding

tablefor

that

nodeiterative:

after

kiterations,

know

least

costpath

to

k

dest.’sNotation:c(x,y):

link

cost

fromnodex

to

y; =

∞

if

not

directneighborsD(v):current

value

of

costof

path

from

source

todest.

vp(v):

predecessor

nodealong

path

from

source

to

vN':

set

of

nodes

whoseleast

cost

path

definitivelyknownDijsktra’s

Algorithm1

Initialization:2 N'

=

{u}for

all

nodes

vif

v

adjacent

to

uthen

D(v)

=

c(u,v)else

D(v)

=

∞7Loopfind

w

not

in

N'

such

that

D(w)

is

a

minimumadd

w

to

N'update

D(v)

forall

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

knownshortest

path

cost

to

w

plus

cost

fromw

to

v

*/until

all

nodes

in

N'Network

Layer

4-25Dijkstra’s

algorithm:

exampleStep0123N'uuxuxyuxyvuxyvw45

uxyvwzD(v),p(v)2,u2,u2,uD(w),p(w)5,u4,x3,y3,yD(x),p(x)1,uD(y),p(y)∞2,xD(z),p(z)∞∞4,y4,y4,yuwz21311y2535v2xNetwork

Layer

4-26Dijkstra’s

algorithm:

example

(2)uyxwvzResulting

shortest-path

tree

from

u:vx

(u,x)y

(u,x)w

(u,x)z

(u,x)Network

Layer

4-27destinationlink(u,v)Resulting

forwarding

table

in

u:Dijkstra

algorithm

illustrationceasbd1223311425[0

/

s][2

/s][1

/

s][∞

/

][5

/s][∞

/

]Dijkstra

algorithm

illustrationceasbd1223311425[0

/

s][2

/s][4

/c][∞

/

][2

/c][1

/

s]Dijkstra

algorithm

illustrationceasbd1223311425[0

/

s][2

/s][4

/c][∞

/

][2

/c][1

/

s]Dijkstra

algorithm

illustrationceasbd1223311425[0

/

s][2

/s][3

/d][4

/d][2

/c][1

/

s]Dijkstra

algorithm

illustrationceasbd1223311425[0

/

s][2

/s][3

/d][4

/d][2

/c][1

/

s]Dijkstra

algorithm

illustrationceasbd1223311425[0

/

s][2

/s][3

/d][4

/d][2

/c][1

/

s]Dijkstra

algorithm

summary復(fù)雜度

(Complexity)–O(n2)注意:計(jì)算所有的最短路徑和計(jì)算一條最短路徑具有相同的復(fù)雜度。輸出結(jié)果給出了網(wǎng)絡(luò)上的一棵生成樹

(Spanning

Tree)。easbcd1223311425Dijkstra’s

algorithm,

discussionAlgorithm

complexity:

nnodeseach

iteration:

need

to

check

allnodes,

w,

not

in

Nn(n+1)/2

comparisons:

O(n2)more

efficient

implementations

possible:

O(nlogn)Oscillations

possible:e.g.,

link

cost

=

amount

of

carried

trafficADCB11+ee0e1100D2+e000A

AB

DB02+eC

1+e11+e

1

0

0CADB2+e0e01+e

1Cinitially…pute

…routingpute…puteNetwork

Layer

4-35Network

Layer

4-36Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv64.5

Routing

algorithmsLink

stateDistance

VectorHierarchical

routing4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingDistance

Vector

AlgorithmBellman-Ford

Equation

(dynamic

programming)Definedx(y)

:=

cost

of

least-cost

path

from

x

to

yThendx(y)

=

min

{c(x,v)

+

dv(y)

}where

min

is

taken

over

all

neighbors

v

of

xvNetwork

Layer

4-37Bellman-Ford

examplewu

21311y5z235v2xu

vd

(z)

=min

{

c(u,v)

+d

(z),c(u,x)

+

dx(z),c(u,w)

+

dw(z)

}=min

{2

+

5,1

+3,5

+3} =

4Node

th hieves

minimum

is

nexthop

in

shortest

path

?

forwarding

tableClearly,

dv(z)

=

5,

dx(z)

=

3,dw(z)

=

3B-F

equationsays:Network

Layer

4-38Network

Layer

4-40Distance

Vector

AlgorithmDx(y)

=

estimate

of

least

cost

from

x

to

yNode

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

vectorsFor

each

neighbor

v,

x

maintainsDv

=[Dv(y):

y

?

N

]NetworkLayer

4-41Distance

vector

algorithm

(4)Basic

idea:From

time-to-time,

eachnodesends

its

owndistance

vector

estimate

to

neighborsAsynchronousWhen

anode

xreceives

newDVestimate

fromneighbor,

it

updates

its

own

DV

using

B-F

equation:Dx(y)

←

minv{c(x,v)

+

Dv(y)} for

each

node

y?

NUnder

minor,

natural

conditions,

the

estimateDx(y)

converge

to

the

actual

least

cost

dx(y)Distance

Vector

Algorithm

(5)Iterative,

asynchronous:each

local

iteration

causedby:local

link

cost

changeDV

update

message

fromneighborDistributed:each

node

notifiesneighbors

only

when

its

DVchangesneighbors

then

notifytheir

neighbors

ifnecessaryEachnode:wait

for

(change

in

local

linkcost

or

msg

from

neighbor)pute

estimatesif

DV

to

any

dest

haschanged,

notify

neighborsNetwork

Layer

4-42z

∞

∞

∞fromcost

tox

y

zx 0

2

7y

∞

∞

∞fromfromfromcost

tox

y

zx

y

zx

∞

∞

∞y

20

1y

2z

71z2x7ynode

x

tablenode

y

tablceost

toz

∞

∞

∞node

z

tablecost

tox

y

zx ∞

∞

∞y

∞

∞

∞z

7

1

0Dx(y)

=

min{c(x,y)+

Dy(y),

c(x,z)

+

Dz(y)}=

min{2+0

,

7+1}

=

2Dx(z)

=

min{c(x,y)

+Dy(z),

c(x,z)

+Dz(z)}=

min{2+1

,

7+0}

=3x

0

2

30

11

0timeNetwork

Layer

4-43z

∞

∞

∞fromcost

tox

y

zx 0

2

7y

∞

∞

∞fromfromx 0

2

3yzfromcost

tox

y

zzx 0

2

3fromcost

tox

y

zx

y

zz

∞

∞

∞yzfromcosttox

y

zx 0

2

7yfromcosttox

y

zfromcost

tox

y

zyzx 0

2

7fromcost

tox

y

zcost

tox

y

zx

∞

∞

∞y

20

1x ∞

∞

∞y

∞

∞

∞z

7

1

0y

200x 0

2

3y 2

0

1z

3

1

0x 0

2

30

1z 3

1

0xz127ynode

x

tablenode

y

tablceost

tonode

z

tableDx(y)

=

min{c(x,y)+

Dy(y),

c(x,z)

+

Dz(y)}=

min{2+0

,

7+1}

=

2Dx(z)

=

min{c(x,y)

+Dy(z),

c(x,z)

+Dz(z)}=

min{2+1

,

7+0}

=3timeNetwork

Layer

4-44Distance

Vector:

link

cost

changesLinkcost

changes:node

detects

local

link

cost

changeupdates

routing

info,

recalculatesdistance

vectorif

DV

changes,

notify

neighbors“goodnewstravelsfast”1z50y14xAt

time

t0,

y

detectsthe

link-cost

change,

updates

its

DV,and

informs

its

neighbors.Attime

t1,

z

receives

the

update

from

y

and

updates

its

table.It

computes

a

new

least

cost

to

x

and

sends

its

neighbors

its

DV.At

timet2,

y

receivesz’s

update

and

updates

its

distance

table.d

anyy’s

least

costs

do

not

change

and

hence

y

does

nomessage

to

z.初始：x->y

4；y->z

1;z->y

1；z->x

5;Network

Layer

4-45Network

Layer

4-46Distance

Vector:

link

cost

changesLink

cost

changes:good

news

travels

fastbad

news

travels

slow

-“count

to

infinity”

problem!44

iterations

beforealgorithm

stabilizes:

seetextPoisoned

reverse:If

Z

routes

through

Y

toget

to

X

:Z

ls

Y

its

(Z’s)

distanceto

X

is

infinite

(so

Y

won’troute

to

X

via

Z)will

this

comple

y

solvecount

to

infinity

problem?1z50y604xNetwork

Layer

4-47Comparison

of

LS

and

DV

algorithmsMessagecomplexityLS:

with

n

nodes,

E

links,O(nE)

msgs

sentDV:

exchange

betweenneighbors

onlyconvergence

time

variesSpeed

of

ConvergenceLS:

O(n2)

algorithm

requiresO(nE)

msgsmay

have

oscillationsDV:

convergence

time

variesmay

be

routing

loopscount-to-infinity

problemRobustness:

whathappensif

router

malfunctions?LS:node

can

advertiseincorrect

link

costeach

node

computes

onlyits

own

tableDV:DV

node

can

advertiseincorrect

path

costeach

node’s

table

used

byotherserror

propagate

thrunetworkNetwork

Layer

4-48Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv64.5

Routing

algorithmsLink

stateDistance

VectorHierarchical

routing4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingNetwork

Layer

4-49Hierarchical

Routingscale:

with

200

milliondestinations:can’t

store

all

dest’s

inrouting

tables!routing

table

exchangewould

swamp

links!administrative

autonomyinternet

=

network

ofnetworkseach

network

admin

maywant

to

control

routing

in

itsown

networkOur

routing

study

thus

far

-

idealizationall

routers

identicalnetwork“flat”…

not

true

in

practiceNetwork

Layer

4-50Hierarchical

Routingaggregate

routers

intoregions,

“autonomoussystems”

(AS)routers

in

same

AS

runsame

routing

protocol“intra-AS”

routingprotocolrouters

in

different

AScan

run

different

intra-AS

routing

protocolGateway

routerDirect

link

to

router

inanother

ASNetworkLayer

4-513a1c1d2a3b

AS3AS11a2cAS22b1bIntra-ASRoutingalgorithmInter-ASRoutingalgorithmForwardingtable3cInterconnected

ASesforwarding

tableconfigured

bybothintra-

andinter-ASrouting

algorithmintra-AS

se

triesfor

internal

destsinter-AS

&

intra-Asse triesforexternal

dests3aNetwork

Layer

4-521c1d2a3b

AS3AS11a2cAS22b1b3cInter-AStaskssuppose

router

in

AS1receives

datagramdestined

outside

ofAS1:router

shouldforward

packet

togateway

router,

butwhich

one?AS1

must:learn

which

dests

arereachable

throughAS2,

which

throughAS3propagate

thisreachability

info

to

allrouters

in

AS1Job

of

inter-AS

routing!Example:

Setting

forwarding

tablein

router1dsuppose

AS1

learns

(via

inter-AS

protocol)

that

subnetx

reachable

v 3

(gateway

1c)

but

not

v

2.inter-AS

protocol

propagates

reachabilityinfoto

allinternal

routers.router

1d

determines

from

intra-AS

routing

info

thatits

interface

I

is

on

the

least

cost

path

to1c.installs

forwarding

table

entry

(x,I)3a1c1d2a3b

AS3AS1AS21a2c2b1b3cxNetwork

Layer

4-53Example:

Choosing

among

multiple

ASesnow

suppose

AS1

learns

from

inter-AS

protocol

thatsubnetx

is

reachable

from

AS3

and

from

AS2.to

configure

forwarding

table,

router

1d

mustdetermine

towards

which

gateway

it

should

forwardpackets

for

dest

x.this

is

alsojob

of

inter-AS

routing

protocol!3aNetwork

Layer

4-541c1d2a3b

AS3AS11a2cAS22b1b3cxLearn

from

inter-ASprotocol

that

subnetx

is

reachable

viamultiple

gatewaysUse

routing

infofrom

intra-AS

protocol

to

determinecosts

of

least-costpaths

to

eachof

the

gatewaysHot

potato

routing:Choose

the

gatewaythat

has

the

smallest

least

costDetermine

fromforwarding

table

theinterface

I

that

leadsto

least-cost

gateway.Enter

(x,I)

inforwarding

tableExample:

Choosing

among

multiple

ASesNetwork

Layer

4-55now

suppose

AS1

learns

from

inter-AS

protocol

thatsubnetx

isreachable

from

AS3

andfrom

AS2.to

configure

forwarding

table,

router

1d

mustdetermine

towards

which

gateway

it

should

forwardpackets

for

dest

x.this

is

also

job

of

inter-AS

routing

protocol!hot

potato

routing:

send

packet

towards

closestoftwo

routers.Intra-AS

Routingalso

known

as

Interior

Gateway

Protocols

(IGP)most

common

Intra-AS

routing

protocols:RIP:

Routing

Information

ProtocolOSPF:

Open

Shortest

PathIGRP:

Interior

Gateway

Routing

Protocol

(Ciscoproprietary)Network

Layer

4-56Network

Layer

4-57Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv64.5

Routing

algorithmsLink

stateDistance

Vector4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingIntra-AS

Routingalso

known

as

Interior

Gateway

Protocols

(IGP)most

common

Intra-AS

routing

protocols:RIP:

Routing

Information

ProtocolOSPF:

Open

Shortest

PathIGRP:

Interior

Gateway

Routing

Protocol

(Ciscoproprietary)Network

Layer

4-58R1H1H2IGP（RIP）AS:

CIGPIGPIGPIGPIGPAS:

AIGPIGPIGPIGPIGPAS:BIGPEGPEGPEGPIGP（OSPF）EGP（BGP-4）IGPR3R2

IGP4.5

Routing

algorithmsLink

stateDistance

VectorHierarchical

routing4.6

Routing

in

theInternetRIPOSPFBGP4.7

Broadcast

andmulticast

routingNetwork

Layer

4-60Chapter

4:

Network

Layer4.

1

Introduction4.2

Virtual

circuit

anddatagram

networks4.3

What’s

inside

arouter4.4

IP:

InternetProtocolDatagram

formatIPv4

addressingICMPIPv6NetworkLayer

4-61RIP

(

Routing

Information

Protocol)DCBAuvwxyzdistance

vector

algorithmincluded

in

BSD-UNIX

Distribution

in

1982distance

metric:

#

of

hops(max

=

15

hops)From

router

A

to

subnets:destination

hops

u

1v

2w

2x

3y

3z

2Network

Layer

4-62RIPadvertisementsdistance

vectors:

exchanged

amongneighbors

every

30

sec

via

ResponseMessage

(also

called

advertisement)each

advertisement:

list

of

up

to

25destination

subnets

within

ASRIP:ExampleDestination

Network

Next

Routerw

ANum.

of

hops

to

dest.2yB2zB7x--1….….....wxyzACDBRouting/Forwarding

table

in

DNetwork

Layer

4-63RIP:

ExampleDestination

Network

Next

Router Num.

of

hops

to

dest.w

A

2yB2zB

A7

5x--1….….....wxyzACDBNext

hopsDestwx

z….-

1-

1C

4…

...Advertisementfrom

A

to

DRouting/Forwarding

table

in

DNetwork

Layer

4-64Update

s:1，if

the

destination

does

not

exit,

this

entry

will

beadded.2，if

the

dest

is

the

same

and

the

cost

c’

is

less

thanthe

old

cost

–

1,

the

entry

will

be

change.

The

cost

willbe

c’

+

1.3，if

the

dest

must

be

via

the

same

neighbor.a:

if

the

dest

is

unreachable,

the

corresponding

entrywill

be

deleted.b:

if

the

cost

is

c’

,

the

cost

of

the

entry

will

be

c’

+

1.Destcost0direct7Gn3Gj4GL5Gj10Gm6Gj(a)A:

Gi’s

route

tableB:

from

Gj’s

route

tabledestcost180.

0.0.044235(b)Destcost0direct5Gj3Gj4Gj4Gl6Gj10Gm(c)協(xié)議中的特殊處理對(duì)相同路由開銷的的處理對(duì)過時(shí)路由的處理布局改變時(shí)的處理對(duì)相同路由開銷的的處理當(dāng)修改報(bào)文中的路由開銷和路由數(shù)據(jù)庫的路由開銷相同時(shí)，不修改路由數(shù)據(jù)庫中的路由。在這種情況下，采用先入為主的原則，即采用以前的路由。這符合處理方式的簡(jiǎn)單性和實(shí)用性。對(duì)過時(shí)路由的處理根據(jù)V-D算法，一條路由只在出現(xiàn)一條更優(yōu)路由時(shí)才被刷新，否則，將繼續(xù)保留在路由數(shù)據(jù)庫中。保留120s自動(dòng)刪除（RFC)布局改變時(shí)的處理(a)圖，從G1可直接到達(dá)網(wǎng)絡(luò)Net1，從G2經(jīng)G1(距離為1)可到達(dá)Net1.(1,G1,1).（b）圖，G1一旦檢測(cè)到不可達(dá),會(huì)立即將原來的路由 (將距離改為16).然后會(huì)出現(xiàn)兩種可能:第一種,在收到來自G2的V-D報(bào)文之前,G1將修改后的路由信息廣去,于是G2將修改其路由數(shù)據(jù)庫,將原來去往Net1的路由(1,G1,1)刪除.這是完全正常的.第二種,在G1發(fā)送新的報(bào)文之前,G2廣播自己的V-D報(bào)文.該報(bào)文中必然有一條路由(1,1)表目,說明從G2出發(fā),經(jīng)1個(gè)驛站可以到達(dá)Net1.G1收到該報(bào)文后,顯然會(huì)根據(jù)此表目更改自己的路由表,產(chǎn)生關(guān)于Net1的新路由(1,G2,2).于是G1與G2間產(chǎn)生尋徑環(huán)。出現(xiàn)第二種情況 文再環(huán)中來回傳送，當(dāng)路由長(zhǎng)度變?yōu)?6.路由環(huán)才能解除.這就是所謂慢收斂問題.解決慢收斂，方法一：減少不可達(dá)跳數(shù)（<16）,但這會(huì)限制網(wǎng)點(diǎn)的規(guī)模,無疑是不行的.方法二：在本協(xié)議的實(shí)現(xiàn)中,用的是水平分割(Split

Horizon)和毒性逆轉(zhuǎn)法(PoisonReverse),并在毒性逆轉(zhuǎn)時(shí)采用觸發(fā)刷新(Triggered Update).具體實(shí)現(xiàn)是這樣的:水平分割:當(dāng)路由器從某個(gè)網(wǎng)絡(luò)接口發(fā)送RIP路由刷 文時(shí),其中不包含從該接口獲取的路由信息.水平分割是在RIP協(xié)議的實(shí)現(xiàn)中是必不可少的。毒性逆轉(zhuǎn):某路徑 后,最早廣播此路由的路由器將原路由繼續(xù)保留在若干報(bào)文中,但指明該路由為無限長(zhǎng).cisco也稱路由保持法觸發(fā)刷新:一旦檢測(cè)到路由 ,立即廣播路由刷

文,而不等到下一刷新周期.根據(jù)路由環(huán)產(chǎn)生的過程,可知通過水平分割法對(duì)解決兩路由器之間形成的路由環(huán)是極為有效的方法.毒性逆轉(zhuǎn)法可解決多路由器之間的路由環(huán)問題.使用觸發(fā)刷新,顯然可以加快新路由的有效刷新.Period

update：也稱update

timer,一般為30S，定時(shí)觸發(fā)，向所有鄰居發(fā)送全部RIP路由（

response報(bào)文）；實(shí)際使用+/-0to5seconds，這樣實(shí)際在發(fā)送自動(dòng)更新的時(shí)間就變?yōu)?5～35秒，從而很好的避免了泛洪的發(fā)生。Timeout：每增加一條新路由，相應(yīng)設(shè)置一個(gè)新時(shí)鐘。如果在收到的V-D報(bào)文中有關(guān)于此路由的表目，則將時(shí)鐘清零，重新計(jì)時(shí)，但是如果在一定的時(shí)間（Timeout）內(nèi)沒有收到更新，那么系統(tǒng)就把這條路由標(biāo)記為無效并認(rèn)為該路由不可達(dá)，同時(shí)把該路由的跳數(shù)設(shè)置為16，但是并不把該路由從路由表中刪除。一般的他它是6倍的UPDATE時(shí)間，也就是180S。有些廠家也把該時(shí)間稱呼為Invalid

timer。Garbage-Collection：當(dāng)路由被標(biāo)記為無效后，RIP會(huì)啟動(dòng)另外一個(gè)定時(shí)器，就是Garbage-Collection，有些廠家也稱呼為FLSUH

timer,默認(rèn)值Garbage-collection定時(shí)器的實(shí)際時(shí)長(zhǎng)是Period

update定時(shí)器的3～4倍。如果在Garbage-Collection時(shí)間內(nèi)，不可達(dá)路由沒有收到來自同一鄰居的更新，則該路由被從路由表中刪除。3.4.1

Dealing

with

changesin

topology

RFC24531)

Suppose

the

current

route

for

network

N

uses

router

G.

If

we

don'thear

from

G

for

180

seconds,

we

can

assume

that

either

the

routerhas

crashed

or

the

network

connecting

us

to

it

has e

unusable.Thus,

we

mark

the

route

as

invalid.

When

we

hear

from

anotherneighbor

that

has

a

validroute

to

N,

the

validroute

will

replace

theinvalid

one.

Note

that

we

wait

for

180

secondsbefore

timing

out

aroute

even

though

we

expect

to

hear

from

each

neighbor

every

30seconds.

Unfortuna y,messages

are

occasionally

lost

by

networks.Thus,

it

is

probably

not

a

good

idea

to

invalidate

a

route

based

on

asingle

missed

message.Read

more:Timers1,The

30-second

updates

aretriggered

by

aclock

and

a

packet

contains

the

completerouting

table

to

every

neighboring

router.The

30-secondtimeris

offsetby

a

smallrandom

time

(+/-0

to

5

seconds)

eachtimeit

isset.There

are

twotimers

associated

with

each

route,

a"timeout"

anda

"garbage-collection"

time.

Uponexpiration

of

the

timeout,

the

route

is

nolonger

valid;however,

it

is

retained

in

the

routing

tablefor

ashorttime

so

that

neighbors

canbe

notified

that

the

routehas

been

dropped.

Upon

expiration

of

the

garbage-collection

timer,

the

route

is

finally

removed

from

therouting

table.

The

timeout

is

initialized

when

a

route

isestablished,

and

any

time

an

update

message

is

receivedfor

the

route.

If

180

seconds

elapse

from

the

lasttimethe

timeout

was

initialized,

the

route

is

considered

tohave

expired,

andthe

deletion

process

described

belowbegins

for

that

route.The

garbage-collection

timer

is

set

for

120

seconds.RIP

historyLate

1960s

:

fist

used

in

ARPANET1988:

RIP-1

(RFC

1058)1993:Sum1998:RIP-2

(RFC

1388)，supporting

CIDR

&

Routeggregationthe

newest

RIP-2

(RFC

2453)Router

A:Destination/Mask Protocol

Pre

CostNexthopInterface/8

RIP

100

1Serial0/0The

version

of

rip??[RouterA]rip

version

2

multicast[RouterB]rip

version

2

multicast[RouterA]dis

ip

routing-table

Routing

Table:

public

netDestination/Mask Protocol

Pre

Cost/24

RIP

100

1Nexthop

Interface

Serial0/0Network

Layer

4-90RIP: