计算机网络复习-计算机网课件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子网掩码:28目的主机：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（路由聚合）:能以更少的表项表达R0的路由表吗?目标网络子网掩码下一站IP地址离出接口名字RIP距离I001I001I001I001R1R3/16/19/19/19I02I01I0017R0//16.1.1一般不对直连路由进行聚合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“link

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补充：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

“linkstate

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复杂度

(Complexity)–O(n2)注意:计算所有的最短路径和计算一条最短路径具有相同的复杂度。输出结果给出了网络上的一棵生成树

(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)协议中的特殊处理对相同路由开销的的处理对过时路由的处理布局改变时的处理对相同路由开销的的处理当修改报文中的路由开销和路由数据库的路由开销相同时，不修改路由数据库中的路由。在这种情况下，采用先入为主的原则，即采用以前的路由。这符合处理方式的简单性和实用性。对过时路由的处理根据V-D算法，一条路由只在出现一条更优路由时才被刷新，否则，将继续保留在路由数据库中。保留120s自动删除（RFC)布局改变时的处理(a)图，从G1可直接到达网络Net1，从G2经G1(距离为1)可到达Net1.(1,G1,1).（b）图，G1一旦检测到不可达,会立即将原来的路由 (将距离改为16).然后会出现两种可能:第一种,在收到来自G2的V-D报文之前,G1将修改后的路由信息广去,于是G2将修改其路由数据库,将原来去往Net1的路由(1,G1,1)删除.这是完全正常的.第二种,在G1发送新的报文之前,G2广播自己的V-D报文.该报文中必然有一条路由(1,1)表目,说明从G2出发,经1个驿站可以到达Net1.G1收到该报文后,显然会根据此表目更改自己的路由表,产生关于Net1的新路由(1,G2,2).于是G1与G2间产生寻径环。出现第二种情况 文再环中来回传送，当路由长度变为16.路由环才能解除.这就是所谓慢收敛问题.解决慢收敛，方法一：减少不可达跳数（<16）,但这会限制网点的规模,无疑是不行的.方法二：在本协议的实现中,用的是水平分割(Split

Horizon)和毒性逆转法(PoisonReverse),并在毒性逆转时采用触发刷新(Triggered Update).具体实现是这样的:水平分割:当路由器从某个网络接口发送RIP路由刷 文时,其中不包含从该接口获取的路由信息.水平分割是在RIP协议的实现中是必不可少的。毒性逆转:某路径 后,最早广播此路由的路由器将原路由继续保留在若干报文中,但指明该路由为无限长.cisco也称路由保持法触发刷新:一旦检测到路由 ,立即广播路由刷

文,而不等到下一刷新周期.根据路由环产生的过程,可知通过水平分割法对解决两路由器之间形成的路由环是极为有效的方法.毒性逆转法可解决多路由器之间的路由环问题.使用触发刷新,显然可以加快新路由的有效刷新.Period

update：也称update

timer,一般为30S，定时触发，向所有邻居发送全部RIP路由（

response报文）；实际使用+/-0to5seconds，这样实际在发送自动更新的时间就变为25～35秒，从而很好的避免了泛洪的发生。Timeout：每增加一条新路由，相应设置一个新时钟。如果在收到的V-D报文中有关于此路由的表目，则将时钟清零，重新计时，但是如果在一定的时间（Timeout）内没有收到更新，那么系统就把这条路由标记为无效并认为该路由不可达，同时把该路由的跳数设置为16，但是并不把该路由从路由表中删除。一般的他它是6倍的UPDATE时间，也就是180S。有些厂家也把该时间称呼为Invalid

timer。Garbage-Collection：当路由被标记为无效后，RIP会启动另外一个定时器，就是Garbage-Collection，有些厂家也称呼为FLSUH

timer,默认值Garbage-collection定时器的实际时长是Period

update定时器的3～4倍。如果在Garbage-Collection时间内，不可达路由没有收到来自同一邻居的更新，则该路由被从路由表中删除。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: