CS计算机代考程序代写 AI algorithm Slide 1

Slide 1

CMPT 471
Networking II

RIP
© Janice Regan, 2006-2017

© Janice Regan, 2006-2017
2
Dynamic Routing
In very simple small and stable networks static routing may be adequate.
As networks grow, become more complex, include multiple or redundant paths between hosts and routers, or change frequently, static routing becomes difficult to manage
Redundant routes are only useful if they can be used immediately on failure of the original route
In a large network the reporting of failure and response by a network manager cannot be accomplished on a short enough time scale for the redundant routes to be useful

© Janice Regan, 2006-2017
3
Dynamic Routing
A routing algorithm to update the routing tables to respond to changes and failures in the network becomes a necessary component of the system
Addition of a routing algorithm does not change the forwarding algorithm used to deliver packets, segments …
Addition of a routing algorithm allows dynamic changes to the entries in the routing table, so those entries can be updated to respond to
Changes in network topology
Changes in load through the network

© Janice Regan, 2006-2017
4
Autonomous Systems (AS)
Group of connected networks and routers, or nodes, controlled by a single administrative authority.
May contain one or more networks (need not be subnets of one network, or networks of the same hardware type)
There is at least one route between any pair of nodes in the AS
Administrative authority can specify if packets originating in their AS are permitted to pass through any other AS (Company A may not wish it’s data to pass through Company B’s routers)

© Janice Regan, 2006-2017
5
Autonomous Systems (AS)
Routers within an AS use a common routing protocol (interior routing protocol or IRP) for all members of the group
Defines mechanisms for discovering, validating, and maintaining routes within the autonomous system
Some routers in the autonomous system (those connected to the larger Internet) also support a routing protocol for propagating subset of routing information to other autonomous systems on the internet (Exterior routing protocol or ERP)

© Janice Regan, 2006-2017
7
Sample routing protocols
IRP (Internal routing protocol, within AS)
GGP: gateway to gateway protocol (no longer used)
RIP: routing information protocol (implemented using routed, for simple networks only)
OSPF: Open Shortest Path First

ERP (External routing protocol, between AS’s)
BGP: ERP usually used in the internet.

© Janice Regan, 2006-2017
8
Routing algorithm
A routing algorithm or routing protocol process determines
How much information is sent to other routers
Which information is sent to other routers
How often information is sent to other routers
Which other routers to exchange information with
best route from present router to every other router in the AS
When and on what basis to change routes due to changes in the AS

© Janice Regan, 2006-2017
9
Static Routing
All routing information specified by administrator and installed at system boot time. Details are determined by the operating system being used
For Ubuntu LINUX,
Default static routing information can be found in /etc/network/network/interfaces
To add additional static routes through the interface
up route add [-net|-host] / gw dev

© Janice Regan, 2006-2017
10
Distance-Vector Routing
Each node exchanges information only with neighbor nodes
Neighbors are both directly connected to same AS
Each node maintains vector of link costs for each directly attached node and distance and next-hop values for each destination node in the system
A node must transmit large amounts of information
Distance vector to all neighbors, Containing estimated path cost to all nodes in a configuration and possibly next hop labels

© Janice Regan, 2006-2017
11
Distance-Vector Routing
Changes take long time to propagate (count to infinity)
Used by first generation routing algorithm for ARPANET and by Routing Information Protocol (RIP, routed) RIP is an internal gateway protocol (IGP) used between routers within an AS
There is no built in mechanism to prevent routing loops

© Janice Regan, 2006-2017
12
Once every T seconds each node i, sends each of its neighbors (one hop distant) a list, of estimated delays from itself to every other node j.
Similarly each node will receive routing information from each of its neighbors every T sec.
The routing data received are used to update the routing table of the node
Distance Vector Routing

© Janice Regan, 2006-2017
13
Similarly each station will receive routing information from each of its neighbors every T sec.
Note: the existing routing table for station i at time t is not used directly to compute the routing table for station i at time t+T, the ‘distance’ to each neighbor station k, lki, and the delay vectors from each neighbor station j, dij are used
Distance Vector Routing

© Janice Regan, 2006-2017
14
Updating the routing table
Use the distributed version of the Bellman-Ford algorithm.
Di delay vector from node i
Si successor node vector
sij next node in minimum delay route from i to j
N # of nodes in network
lki current estimate of delay between neighbors k, I
The set of neighbor nodes

E
F
H
G

B
D
C

2
4
3
2
5
1
6
6
2
4
4
8
5
4
4
2
4

A
4
3
Original network and original delays

lJF
4
Delay lJi
lJI
4
lJK
3

lJF
4
Measured
Delay lJi
lJI
4
lJK
3
Delay vectors received
SF DF
SI DI
SK DK

DF+IJF
DF+4
DI+IJI
DI+4
DK+IJK
DK+3
New table for node J

SJ DJ
Later time, some routes weights have changed

© Janice Regan, 2006-2017
17
Actual Practice
The routing table is updated each time a packet of routing information arrives from a neighbor
The updating process consists of
Comparing the sum of the delay to the particular node from which the update came and the cost of propagation to that node to the present cost.
If the cost decreases replace the path for that node
If there is presently no such route add the route
Always replace the cost to the directly connected nodes if it changes

© Janice Regan, 2006-2017
18
Problems: distance vector routing
Changes take long time to propagate (count to infinity)
slow convergence
There is no built in mechanism to prevent routing loops
Oscillation and instability is possible

© Janice Regan, 2006-2017
19
Count to Infinity problem
In practice when conditions in a network change, the change will take time to propagate across the network.
Good news propagates quickly across a network
Bad news propagates slowly across the network

A is down initially and all other stations know this
A comes up, at the time of the first exchange of routing information after A comes up B learns that A is alive
At the time of the second exchange of routing information after A comes up C learns that A is alive
This pattern continues till the time of the sixth data exchange after A comes up, when F learns that A is alive. At this point all stations in the network have learned the good news

A
B
C
D
E
F

Initially B can reach A and C can reach A through B
When the link from B to A fails then B updates its routing table to indicate it cannot reach A directly.
When a update arrives at B from C, B notices that C has a route to A with a cost of 2, and adopts that route. The new route has a cost of (2+1)=3
When an update from B reaches C, C notices the cost of the route to A through B has increased to 3 so it updates it own routes cost to A to (3+1)=4
The process continues as the cost to route A counts to infinity.
In the more general network the costs increment as shown on the next slides

A
B
C

The number of iterations necessary to indicate that the link to 1 is down (cost infinite) is in fact infinite. It is clear that the delay increases as the number of iterations increase, but it is still necessary to ‘count to infinity’ to reach the correct link costs for link A-B down.

A
B
C
D
E
F

A is up initially and all other stations know this
A goes down, at the time of the first exchange of routing information after A goes down B hears nothing from A. Since there is no direct path to A, B chooses an indirect path to A through C (which actually goes through B itself, but B doesn’t know this)
The first eight exchanges are illustrated on the next slide.

A
B
C
D
E
F

1 2 3 4 5
3 2 3 4 5
3 4 3 4 5
5 4 5 4 5
5 6 5 6 5
7 6 7 6 7
7 8 7 8 7
9 8 9 8 9
9 10 9 10 9

A
B
C
D
E
F
INITIALLY
AFTER 1 EXCHANGE
AFTER 2 EXCHANGES
AFTER 3 EXCHANGES
AFTER 4 EXCHANGES
AFTER 5 EXCHANGES
AFTER 6 EXCHANGES
AFTER 7 EXCHANGES
AFTER 8 EXCHANGES

© Janice Regan, 2006-2017
25
Routing Information Protocol
RIP, The simplest dynamic distance vector routing protocol still in use, was built and adopted before a formal standard was available (RFC 1058 RIPv1, 2453 RIPv2 )
Implemented in LINUX as the routed process.
Adequate only for small and stable ASs
based on the Bellman-Ford (or distance vector) algorithm
helps control count to infinity problem by specifying a maximum hop count of 15

© Janice Regan, 2006-2017
26
Routing Information Protocol
Uses a simple metric, hop count
Not designed to deal with more complicated dynamic metrics such as delay, reliability or load (these can cause route oscillations)
Helps control oscillation between equal cost routes by retaining original route unless a route with a lower cost is found.
Helps prevent slow convergence (after changes in the topology of the network) by sending update messages immediately after updates have been completed (triggered updates)

© Janice Regan, 2006-2017
27
Routing Information Protocol
Helps prevent routing loops by
omitting routes learned from a particular neighbor in the updates sent to that neighbor or other neighbors reached through the same network interface (split-horizon)
advertising routes learned from a particular neighbor with cost 16 (∞) in the updates sent to that neighbor or other neighbors on the same broadcast network (split-horizon with poison reverse),
Nodes are either active (routers) or passive (silent hosts)
Active nodes advertise their routing information
Passive nodes listen for advertisements and update their routing tables accordingly

A learns the route to C from B
C learns the route to A from B
Initially B can reach A and C, C can reach A through B
When the link from B to A fails then B updates its routing table to indicate it cannot reach A directly.
Without split infinity: When a update arrives at B from C, B notices that C has a route to A with a cost of 2, and adopts that route. The new route has a cost of (2+1)=3
Split infinity: When an update arrives at B from C, it does not include an entry for A because C learned the route to A from B. B does not update its entry for A, it has no alternative for the broken direct route to A. Eventually, C’s route to A times out .

A
B
C

A learns the route to C from B
C learns the route to A from B
Initially B can reach A and C, C can reach A through B
When the link from B to A fails then B updates its routing table to indicate it cannot reach A directly.
Without split infinity: When a update arrives at B from C, B notices that C has a route to A with a cost of 2, and adopts that route. The new route has a cost of (2+1)=3
Split infinity with poison reverse: B sends an update with a cost of infinity to C. If C really has a route that is not through B the route sent by B will never be used, otherwise C will immediately update its path cost to A to infinity (Protects reverse routes)

A
B
C

© Janice Regan, 2006-2017
30
Nodes in RIP
Nodes can be hosts or routers
Each node keeps a routing table for every possible destination network (or active host) in the AS. Each entry in the table includes
network or host address, gateway router address, metric and interface
a timer measuring the amount of time since the entry was last updated.
Active nodes send routing information to all neighbors

© Janice Regan, 2006-2017
31
Neighbors in RIP
All hosts or routers 1 hop from a node are the neighbors of that node
This means that all hosts on a network segment, including the router or routers for that segment (with a single broadcast address) are neighbors
Directly connected routers are also neighbors
Update messages containing routing information are sent only to neighbors

© Janice Regan, 2006-2017
32
Initialization: RIP
Each node needs to know its own address
Each node must be able to identify the links (interfaces) to which it is attached.
Each node starts with a routing table that contains a single entry, its own localhost
Each router broadcasts (advertises) that single entry through its interfaces to all attached networks. The information reaches all neighbor nodes (directly connected routers)
All nodes directly connected to a network segment receive the information from all routers on that network segment, and add that information to their routing tables.

© Janice Regan, 2006-2017
33
Updating and RIP
Then tables are updated or maintained
Each router will periodically broadcast its routing table
Each router will process the received updates, adding new entries, updating entries for which a lower cost path has been located and updating entries for directly connected nodes whose cost changed
If the routing information changes during the update process the router will immediately broadcast the modified tables to its neighbors (called a triggered broadcast)

© Janice Regan, 2006-2017
34
Updating and RIP
When no further changes occur the routing table has converged to the topology of the network
When a change is made to the network topology (removing, adding, or modifying a node)
The neighbor nodes will detect the change and update their routing tables
the routing algorithm will converges to a new topology consistent with the changes

© Janice Regan, 2006-2017
35
Timers in RIP
RIP uses three timers
The first timer keeps track of the route advertisement time. Each time it expires (usually every 30 seconds) a message containing the routing information is sent
The second and third types of timers are associated with each entry in the routing table. Each route is given an expiration timer and a garbage collection timer

© Janice Regan, 2006-2017
36
Timers in RIP
RIP uses three timers
The second and third types of timers are an expiration timer and a garbage collection timer
If no update information is received before the expiration timer (usually 180 seconds) expires the route is considered unreachable and its cost is set to ∞ (16)
When the expiration timer expires a garbage collection timer is set (usually 120 seconds). When the garbage collection timer expires the routing table entry is deleted

© Janice Regan, 2006-2017
39
RIP messages
RIP messages are sent encapsulated in UDP packets (port 520). The length of the message is transmitted only by UDP
RIPv1 cannot be used for variable length subnets or for CIDR addresses (must use RIPv2). If subnets are used all receivers must be able to interpret them.
Family gives the family of protocols used (TCP/IP 2)
0.0.0.0 is address for default route

© Janice Regan, 2006-2017
40
RIP messages (RIPv1 and RIPv2)
Two types of messages request (1) and response (2)
A router may request routing information
A router may reply to a request by sending a response
Solicited responses will contain only the requested routes, not all available routes
A router may sent unsolicited responses (periodic broadcasts of routing table information for all routes)

© Janice Regan, 2006-2017
41
Improvements in RIP2
Next hop field helps eliminate “double hops” a-b-a
The netmask means that RIP2
Can handle subnet routing (not just within subnetted network, extension to RIP1 could do that)
Can deal with CIDR addresses
The route tag identifier
Used to flag external (to AS) routes

© Janice Regan, 2006-2017
42
Improvements in RIP2
Includes an authentication procedure
The first entry in a packet can be replaced by an authentication segment (command will become a 32 bit field containing the command and authentication information, packet length, key … see RFC 2453, 2082 for details )
RIP2 uses random variations on time delays
Triggered updates are delayed by 1-5 s
Periodic advertisements are randomized by adding between -5 and 5 seconds

© Janice Regan, 2006-2017
43
Why use RIP2
“With the advent of OSPF and IS-IS, there are those who believe that RIP is obsolete. While it is true that the newer IGP routing protocols are far superior to RIP, RIP does have some advantages. Primarily, in a small network, RIP has very little overhead in terms of bandwidth used and configuration and management time. RIP is also very easy to implement, especially in relation to the newer IGPs. “
Quote from RFC 2453 (RIP2)

][
min
kiij
Ai
kj
ldd 
































Ni
i
i
i
Ni
i
i
i
s
s
s
S
d
d
d
D

2
1
2
1

][
min
kiij
Ai
kj
ldd 


FIJK
AA2E3F6F7
BB4F7F8F9
CG8F11F12H12
DG6F9F10H8
EA3E2I6F8
F00F3F4F5
GG2F5F6F7
HK5J11 K7H4
II300I4J7
JJ4J400J3
KK5J7K300
LK7J9K5L2

Sheet1
A B C D E F G H I J K L
A 0 A G G A A A K E F F K
B B B C A B F K B F F K
C F C C A G C D F F H H
D F C D A G C D F H H
E E A G G A F K E I F K
F F F G G A F K F F F K
G F F G G A G G F F F K
H F F D H A K H J K H H
I F F G G I I F K I J K
J F F G G I J F K J J K
K F F D H A K F K J K K
L F F D H A K F L J K L

Sheet2
A B C D E F G H I J K L
A 0 0 A 5 G 10 G A A 2 F 4 K E 3 F 6 F 7 K
B B 5 0 0 B 6 C A B 4 F 6 K F 7 F 8 F 9 K
C F 10 C 6 C A G 8 C 6 D F 11 F 12 H 12 H
D F 8 C 10 D 4 A G 6 D 4 D F 9 F 10 H 8 H
E E 1 A 6 G 11 G A 3 F 5 K E 2 I 6 F 8 K
F F 2 F 4 G 8 G A 0 0 F 2 K F 3 F 4 F 5 K
G F 4 F 6 G 6 G A G 2 0 0 G F 5 F 6 F 7 K
H F 11 F 13 D 8 H A K 5 H 8 J 11 K 7 H 4 H
I F 3 F 7 G 11 G I I 3 F 5 K 0 0 I 4 J 7 K
J F 6 F 8 G 12 G I J 4 F 6 K J 4 0 0 J 3 K
K F 7 F 9 D 12 H A K 5 F 7 K J 7 K 3 0 0 K
L F 9 F 11 D 10 H A K 7 F 9 L J 9 K 5 L 2

Sheet3

T
kNkkK
kiij
Ai
kj
dddD
ldd
],,,[
][
min
21




AA2E5F5
BA7E10F10
CG9F13H9
DG7F11H6
EA5E2F8
F00F4F3
GG3F7F6
HK3F10H4
II400F7
JJ2J3J4
KK3J700
LK6F10L3

698F6
111413F11
131712K12
11159K9
9611I6
486F4
7119F7
7147K7
8410I4
67700
7
113
K3
10146K6

is
kj


Sheet2
A B C D E F G H I J K L
A 0 0 A 5 G 10 G A A 2 F 4 K E 5 F 6 F 5 K
B B 5 0 0 B 6 C A A 7 F 6 K E 10 F 8 F 10 K
C F 10 C 6 C A G 9 C 6 D F 13 F 12 H 9 H
D F 8 C 10 D 4 A G 7 D 4 D F 11 F 10 H 6 H
E E 1 A 6 G 11 G A 5 F 5 K E 2 I 6 F 8 K
F F 2 F 4 G 8 G A 0 0 F 2 K F 4 F 4 F 3 K
G F 4 F 6 G 6 G A G 3 0 0 G F 7 F 6 F 6 K
H F 11 F 13 D 8 H A K 3 H 8 F 10 K 9 H 4 H
I F 3 F 7 G 11 G I I 4 F 5 K 0 0 I 4 F 7 K
J F 6 F 8 G 12 G I J 2 F 6 K J 3 0 0 J 4 K
K F 7 F 9 D 12 H A K 3 F 7 K J 7 K 3 0 0 K
L F 9 F 11 D 10 H A K 6 F 9 L F 10 K 5 L 3

Sheet3

Sheet2
A B C D E F G H I J K L
A 0 0 A 5 G 10 G A I 6 F 4 K E 3 F 6 F 7 K 10 7 10 I 7
B B 5 0 0 B 6 C A B 4 F 6 K F 7 F 8 F 9 K 8 11 12 F 8
C F 10 C 6 C A G 8 C 6 D F 11 F 12 H 12 H 12 15 15 F 12
D F 8 C 10 D 4 A G 6 D 4 D F 9 F 10 H 8 H 10 13 11 F 19
E E 1 A 6 G 11 G I 5 F 5 K E 2 I 6 F 8 K 9 6 11 I 6
F F 2 F 4 G 8 G A 0 0 F 2 K F 3 F 4 F 5 K 4 7 8 F 4
G F 4 F 6 G 6 G A G 2 0 0 G F 5 F 6 F 7 K 6 9 10 F 6
H F 11 F 13 D 8 H A K 5 H 8 F 8 K 9 H 4 H 9 12 7 K 7
I F 3 F 7 G 11 G I I 3 F 5 K 0 0 I 4 J 7 K 7 4 10 I 4
J F 6 F 8 G 12 G I J 4 F 6 K J 4 0 0 J 3 K 8 8 6 K 6
K F 7 F 9 D 12 H A K 2 F 7 K F 5 K 3 0 0 K 6 9 3 K 3
L F 9 F 11 D 10 H A K 4 F 9 L F 7 K 5 L 2 8 11 5 K 5
F I K

Sheet3
6 9 8 F 6
11 14 13 F 11
13 17 12 K 12
11 15 9 K 9
9 6 11 I 6
4 8 6 F 4
7 11 9 F 7
7 14 7 K 7
8 4 10 I 4
6 7 7 0 0
7 11 3 K 3
10 14 6 K 6
F I K

/docProps/thumbnail.jpeg

Related Posts