Transcript L h

William Stallings
Data and Computer
Communications
7th Edition
Chapter 12
Routing
Routing Table
Routing Table
12.2 Routing in Packet
Switched Network
• Characteristics required
—Correctness
—Simplicity
—Robustness
—Stability
—Fairness
—Optimality
—Efficiency
正确
简洁
稳健
稳定
公平
最优
高效
P370
Table 12.1 Elements of Routing Techniques for
Packet-Switching Networks
P371
• Performance Criteria 性能评估标准
—Number of hops ---Minimum hop
—Cost ---Least cost
—Delay
—Throughput
• Time
—Packet or virtual circuit basis 数据报或虚电路
• Place
—Distributed: Made by each node
分布式
—Centralized: Collect info from all nodes 集中式
—Source
源节点
Table 12.1 Elements of Routing Techniques for
Packet-Switching Networks
P371
• Update timing
—When is network info held by nodes updated
节点拥有的网络信息 何时更新
—Fixed - never updated
固定的
—Adaptive - regular updates
自适应
Routing Strategies
路由选择策略
•
•
•
•
(1)
(2)
(3)
(4)
Fixed Routing
Flooding
Random Routing
Adaptive Routing
P374
固定式路由选择
洪泛式路由选择
随机路由选择
自适应路由选择
(1) Fixed Routing
P374
• Single permanent route for each source to
destination pair
• Determine routes using a least cost algorithm
• Route fixed, until a change in network topology
Fixed Routing
Tables
出发节点
到达节点
节点1的路由表
节点2的路由表
中央路由表
(2) Flooding
P375
• No network info required
• Packet sent by node to every neighbor
• Incoming packets retransmitted on every link except
incoming link
• Eventually a number of copies will arrive at destination
• Each packet is uniquely numbered so duplicates can be
discarded
• Nodes can remember packets already forwarded to keep
network load in bounds（限度）
• Can include a hop count in packets
Flooding
Example
Properties of Flooding
• All possible routes are tried
—Very robust
• At least one packet will have taken minimum
hop count route
—Can be used to set up virtual circuit
• All nodes are visited
—Useful to distribute information (e.g. routing)
(3) Random Routing
• Node selects one outgoing path for
retransmission of incoming packet
• Selection can be random or round robin
• Can select outgoing path based on probability
calculation
• No network info needed
• Route is typically not least cost nor minimum
hop
(4) Adaptive Routing
• Used by almost all packet switching networks
• Routing decisions change as conditions on the
network change
—Failure; Congestion
• Requires info about network
• Decisions more complex
• Tradeoff（折衷，权衡） between quality of
network info and overhead
• Reacting too quickly can cause oscillation
• Too slowly to be relevant （相关）
12.3 Least Cost Algorithms
P385
• Dijkstra’s Algorithm
• Bellman-Ford Algorithm
 Two basic algorithms: the Bellman-Ford (RIP) and the
Dijkstra algorithms (OSPF).
 RIP (Routing information Protocol 路由信息协议 ) is a
distance-vector protocol that allows routers to exchange
information about destinations for computing routes throughout
the network.
 OSPF (Open Shortest Path First 开放最短路径优先) is a
dynamic routing protocol for use in Internet Protocol (IP)
networks.
Dijkstra’s Algorithm- Introduction of Dijkstra
 E. W. Dijkstra. A note on two problems in
connections with graphs. Numerische Mathematik
(计算数学), 1:269–271, 1959.
Edsger Wybe Dijkstra(May 11, 1930 – August 6,
2002) (pronunciation: [ˈɛtsxər ˈwibə ˈdɛɪkstra]) was a
Dutch 荷兰computer scientist.
He received the 1972 Turing Award 图灵奖for fundamental
contributions to developing programming languages, and was the
Schlumberger Centennial Chair of Computer Sciences at The
University of Texas at Austin from 1984 until 2000.
Dijkstra studied theoretical physics at Leiden University, but he
quickly realized he was more interested in computer science.
Originally employed by the Mathematisch Centrum in Amsterdam, he
held a professorship at the Eindhoven University of Technology in
the Netherlands(荷兰), worked as a research fellow for Burroughs
Corporation in the early 1970s.
Dijkstra’s Algorithm Definitions
• Find shortest paths from given source node to all other
nodes, by developing paths in order of increasing path
length
• N = set of nodes in the network
• s = source node
• T = set of nodes so far incorporated by the algorithm
• w(i, j) = link cost from node i to node j
—w(i, i) = 0
—w(i, j) =  if the two nodes are not directly connected
—w(i, j)  0 if the two nodes are directly connected
• L(n) = cost of least-cost path from node s to node n
currently known
S=1
The values in each circle are the current L(x) for each node x.
A node is shaded when it is added to T.
The shaded edges define the spanning tree for the graph.
Dijkstra’s Algorithm Method
• Step 1 [Initialization]
—T = {s} Set of nodes consists of only source node
—L(n) = w(s, n) for n ≠ s
• Step 2 [Get Next Node]
—Find neighboring node not in T with least-cost path from s
—Incorporate node into T
L(x)=min L(j) j  T
—Also incorporate the last hop in the path
• Step 3 [Update Least-Cost Paths]
— L(n) = min[ L(n), L(x) + w(x, n) ] for all n  T
—If latter term is minimum, path from s to n is path from s
to x concatenated with edge from x to n
• Algorithm terminates when all nodes have been added to T
Example of Dijkstra’s Algorithm
循环
Ite
rat
ion
Results of Example Dijkstra’s Algorithm
T
L(2)
Path
L(3)
Path
L(4)
Path
L(5)
Path
L(6)
Path
1
{1}
2
1–2
5
1-3
1
1–4

-

-
2
{1,4}
2
1–2
4
1-4-3
1
1–4
2
1-4–5

-
3
{1, 2,
4}
2
1–2
4
1-4-3
1
1–4
2
1-4–5

-
4
{1, 2, 4,
5}
2
1–2
3
1-4-5–
3
1
1–4
2
1-4–5
4
1-4-5–6
5
{1, 2, 3,
4, 5}
2
1–2
3
1-4-5–
3
1
1–4
2
1-4–5
4
1-4-5–6
6
{1, 2, 3,
4, 5, 6}
2
1-2
3
1-4-53
1
1-4
2
1-4–5
4
1-4-5-6
Bellman-Ford Algorithm
 （1） L. R. Ford, Jr. Network flow theory. Technical
Report P-923, RAND, Santa Monica, CA, August, 14
1956.
（小L.R.Ford，网络流理论。技术报告P - 923，
兰德公司，圣莫尼卡，加州）Jr.=junior
 Book: L. R. Ford, D. R. Fulkerson, Flows in Networks,
Princeton University Press (1962).
 （2）Richard Bellman. On a routing problem. Quarterly
Applied Mathematics, XVI(1):87–90, 1958. （关于路由
问题。应用数学季刊，十六）
Bellman
RAND --
Paul Baran
 A young engineer named Paul Baran proposed
sending messages via phone lines and changing
words into numbers to avoid noise and distortion.
 Baran also decided that any content relayed should be divided
into “packets,” or discrete bundles of data.
Baran tried to convince AT&T to install the system, but the phone
giant refused to create something that could become its worst
competitor.
Instead, the creation of a worldwide packet-switching system
was left to the Pentagon, which devised ARPANET, the
predecessor to the Internet.
 Baran 在1964年提出热土豆（Hot Potato）路由选择算法。
当一个分组到来时，节点必须尽快脱手，将其放入输出列
最短的方向上排队，而不管该方向通向何方。
Bellman-Ford Algorithm Definitions
• Find shortest paths from given source node subject to
constraint约束 that paths contain at most one link
• Then ,find the shortest paths with a constraint of paths of
at most two links , and so on.
• And so on
• s = source node
• w(i, j) = link cost from node i to node j
—w(i, i) = 0
—w(i, j) =  if the two nodes are not directly connected
—w(i, j)  0 if the two nodes are directly connected
• h = maximum number of links in path at current stage of
the algorithm
• Lh(n) = cost of least-cost path from s to n under constraint
of no more than h links
Bellman-Ford Algorithm Method
• Step 1 [Initialization]
—L0(n) = , for all n  s
—Lh(s) = 0, for all h
• Step 2 [Update]
• For each successive h  0
—For each n ≠ s, compute
—Lh+1(n)=minj [Lh(j)+w(j,n)]
• Connect n with predecessor node j that achieves
minimum
Bellman-Ford Algorithm Notes
• For each iteration of step 2 with h=K (链路长度,
即有几段链路)and for each destination node n,
algorithm compares paths from s to n of length
K+1 with path from previous iteration
• If previous path shorter it is retained 保留
• Otherwise new path of length K+1 is defined,
which consists of a path of length K, plus a hop
from node j to node n.
Example of Bellman-Ford Algorithm
Results of Bellman-Ford Example
h Lh(2) Path Lh(3) Path
Lh(4) Path Lh(5) Path
Lh(6) Path
0 
-

-

-

-

-
1 2
1-2
5
1-3
1
1-4

-

-
2 2
1-2
4
1-4-3
1
1-4
2
1-4-5 10
1-3-6
3 2
1-2
3
1-4-5-3 1
1-4
2
1-4-5 4
1-4-5-6
4 2
1-2
3
1-4-5-3 1
1-4
2
1-4-5 4
1-4-5-6