CS计算机代考程序代写 algorithm database Packet-Switching Networks

Packet-Switching Networks
Routing in Packet Networks

Routing in Packet Networks
1
3
4
2
 1-3-6, 1-4-5-6, 1-2-5-6  Which is “best”?
 Min delay? Min hop? Max bandwidth? Min cost? Max reliability?
5
 Three possible (loopfree) routes from 1 to 6:
Node (switch or router)
6

Creating the Routing Tables
 Need information on state of links
 Link up/down; congested; delay or other metrics
 Need to distribute link state information using a routing protocol
 What information is exchanged? How often?  Exchange with neighbors; Broadcast or flood
 Need to compute routes based on information  Single metric; multiple metrics
 Single route; alternate routes

Routing Algorithm Requirements
 Responsiveness to changes
 Topology or bandwidth changes, congestion
 Rapid convergence of routers to consistent set of routes  Freedom from persistent loops
 Optimality
 Resource utilization, path length
 Robustness
 Continues working under high load, congestion, faults,
equipment failures, incorrect implementations  Simplicity
 Efficient software implementation, reasonable processing load

Routing in Virtual-Circuit Packet Networks
1278
13B A53165
VCI
Host
C
3
42
4
5
5
Switch or router
D
2
6
 Route determined during connection setup
 Tables in switches implement forwarding that realizes selected route
2

Routing Tables in VC Packet Networks
Incoming Node VCI
A1
A5
32 33
Outgoing Node VCI
32
33
A1 A5
Incoming Node VCI
12 13
42 67 61 44
Node 3
Node 1
Node 6
Outgoing Node VCI
Incoming Node VCI
Outgoing Node VCI
37 31 B5 B8
B8 B5 31 37
67 44
61 12 42 13
Node 4
Incoming Node VCI
Outgoing Node VCI
23
32
34
55
32 55
23 34
Node 2
Node 5
Incoming Node VCI
Outgoing Node VCI
C6 43
43 C6
Incoming Node VCI
45
D2
Outgoing Node VCI
D2
45
 Example: VCI from A to D From → → → →
A & VCI 5
3 & VCI 3
4 & VCI 4
5 & VCI 5
D & VCI 2

Routing Tables in Datagram Packet Networks
Node 3
Destination
Next node
1 2 4 5 6
1 4 4 6 6
Node 1
Node 6
Destination
Next node
1 2 3 4 5
3 5 3 3 5
Destination
2 3 4
5
6
Destination
1 3 4
5
6
Next node
2 3 4
2
3
Next node
1 1 4
Node 4
Destination
Next node
1 2 3 5 6
1 2 3 5 3
Node 2
Node 5
5
5
Destination
1 2 3 4 6
Next node
4 2 4 4 6

Non-Hierarchical Addresses and Routing
0000 0111 1010 1101
0011 0110 1001 1100
1
R1 25
0001 0100 1011 1110
0011 0101 1000 1111
4 3
R2
0001 0100 1011 …
4 4 4 …
0000 0111 1010 …
1 1
1

 No relationship between addresses & routing proximity
 Routing tables require 16 entries each

Flooding
Send a packet to all nodes in a network
 No routing tables available
 Need to broadcast packet to all nodes (e.g. to propagate link state information)
Approach
 Send packet on all ports except one where it arrived
 Exponential growth in packet transmissions

1
3
6
4
2
5
Flooding is initiated from Node 1: Hop 1 transmissions

1
3
6
4
2
5
Flooding is initiated from Node 1: Hop 2 transmissions

1
3
6
4
2
5
Flooding is initiated from Node 1: Hop 3 transmissions

Limited Flooding
 Time-to-Live field in each packet limits number of hops to certain diameter
 Each switch adds its ID before flooding; discards repeats
 Source puts sequence number in each packet; switches records source address and sequence number and discards repeats

Deflection Routing
 Network nodes forward packets to preferred port
 If preferred port busy, deflect packet to another port
 Works well with regular topologies  Manhattan street network
 Rectangular array of nodes
 Nodes designated (i,j)
 Rows alternate as one-way streets
 Columns alternate as one-way avenues
 Bufferless operation is possible
 Proposed for optical packet networks  All-optical buffering currently not viable

0,0 0,1
1,0
2,0
3,0
0,2 0,3
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3
Tunnel from last column to first column or vice versa

Example: Node (0,2)→(1,0)
0,0 0,3
busy
0,1
0,2
1,1
1,2
1,3
2,1
2,2
2,3
3,1
3,2
3,3
1,0
2,0
3,0

Packet-Switching Networks
Shortest Path Routing

Shortest Paths & Routing
 Many possible paths connect any given source and to any given destination
 Routing involves the selection of the path to be used to accomplish a given transfer
 Typically it is possible to attach a cost or distance to a link connecting two nodes
 Routing can then be posed as a shortest path problem

Routing Metrics
Means for measuring desirability of a path
 Path Length = sum of costs or distances
 Possible metrics
 Hop count: rough measure of resources used
 Reliability: link availability; BER
 Delay: sum of delays along path; complex & dynamic  Bandwidth: “available capacity” in a path
 Load: Link & router utilization along path
 Cost: $$$

Shortest Path Approaches
Distance Vector Protocols
 Neighbors exchange list of distances to destinations  Best next-hop determined for each destination
 Ford-Fulkerson (distributed) shortest path algorithm Link State Protocols
 Link state information flooded to all routers  Routers have complete topology information  Shortest path (& hence next hop) calculated  Dijkstra (centralized) shortest path algorithm

Distance Vector
Do you know the way to San Jose?
San Jose 392
San Jose 596

Distance Vector
Local Signpost
 Direction  Distance
Routing Table
For each destination list:  Next Node
 Distance
Table Synthesis
 Neighbors exchange table entries
 Determine current best next hop
 Inform neighbors  Periodically
 After changes
dest
next
dist

Shortest Path to SJ
Focus on how nodes find their shortest path to a given destination node, i.e. SJ
San Jose
Cij i
Dj j
Di
If Di is the shortest distance to SJ from i and if j is a neighbor on the shortest path, then Di = Cij + Dj

But we don’t know the shortest paths
i only has local info from neighbors
San Jose
Dj’ Cij
j’
Cij’
i
Di
j
Dj
Cij”
Dj”
Pick current shortest path
j”

Why Distance Vector WorksSJ sends accurate info
3 Hops From SJ
2 Hops From SJ
1 Hop From SJ
San Jose
Accurate info about SJ ripples across network,
Hop-1 nodes calculate current (next hop, dist), & send to neighbors
Shortest Path Converges

Bellman-Ford Algorithm
 Consider computations for one destination d  Initialization
 Each node table has 1 row for destination d
 Distance of node d to itself is zero: Dd=0
 Distance of other node j to d is infinite: Dj=, for j d
 Next hop node nj = -1 to indicate not yet defined for j  d
 Send Step
 Send new distance vector to immediate neighbors across local link
 Receive Step
 At node j, find the next hop that gives the minimum distance to d,
Minj { Cij + Dj }
 Replace old (nj, Dj(d)) by new (nj*, Dj*(d)) if new next node or distance
 Go to send step

Bellman-Ford Algorithm
 Now consider parallel computations for all destinations d  Initialization
 Each node has 1 row for each destination d
 Distance of node d to itself is zero: Dd(d)=0
 Distance of other node j to d is infinite: Dj(d)=  , for j  d  Next node nj = -1 since not yet defined
 Send Step
 Send new distance vector to immediate neighbors across local link
 Receive Step
 For each destination d, find the next hop that gives the minimum
distance to d,
 Minj { Cij+ Dj(d) }
 Replace old (nj, Di(d)) by new (nj*, Dj*(d)) if new next node or distance found
 Go to send step

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
1
2
3
Table entry @ node 1 for dest SJ
1
Table entry
@ node 3
for dest SJ
2
52 4
3
1
San
Jose
3
245
6 2
13

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
1
(-1, )
(-1, )
(6,1)
(-1, )
(6,2)
2
3
D3=D6+1 n3=6
1
3
2 31 D6=0 521
4 13
0 San
6 2
25 4
2
Jose
D6=0
D5=D6+2 n5=6

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
1
(-1, )
(-1, )
(6, 1)
(-1, )
(6,2)
2
(3,3)
(5,6)
(6, 1)
(3,3)
(6,2)
3
3 2 31 1
532 34
245
1
0
6 2
San Jose
13
62

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(-1, )
(-1, )
(-1, )
(-1, )
(-1, )
1
(-1, )
(-1, )
(6, 1)
(-1, )
(6,2)
2
(3,3)
(5,6)
(6, 1)
(3,3)
(6,2)
3
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
3
2
1
3
1
1
532
0
6 2
San Jose
3
4 13
245
642

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
1
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
2
3
315 23
11 532 0
San Jose
346 13
245
2
2
4
Network disconnected; Loop created between nodes 3 and 4

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
1
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
2
(3,7)
(4,4)
(4, 5)
(5,5)
(6,2)
3
37 1
3
245
42
2
5532 4
0
6 2
San Jose
5
3
1
13
Node 4 could have chosen 2 as next node because of tie

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
Initial
(3,3)
(4,4)
(6, 1)
(3,3)
(6,2)
1
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
2
(3,7)
(4,4)
(4, 5)
(5,5)
(6,2)
3
(3,7)
(4,6)
(4, 7)
(5,5)
(6,2)
7
1
2 552
57 3
1
4 San
0
3136
Jose
25
4
2
46
Node 2 could have chosen 5 as next node because of tie
2

Iteration
Node 1
Node 2
Node 3
Node 4
Node 5
1
(3,3)
(4,4)
(4, 5)
(3,3)
(6,2)
2
(3,7)
(4,4)
(4, 5)
(2,5)
(6,2)
3
(3,7)
(4,6)
(4, 7)
(5,5)
(6,2)
4
(2,9)
(4,6)
(4, 7)
(5,5)
(6,2)
79 1
2
552 4
37
1
3
245
0
6 2
San Jose
13
62
Node 1 could have chose 3 as next node because of tie

Counting to Infinity Problem
(a) 1 1 2 1 3 1 4
Nodes believe best path is through each other
(Destination is node 4)
(b)
11213X4
Update
Node 1
Node 2
Node 3
Before break
(2,3)
(3,2)
(4, 1)
After break
(2,3)
(3,2)
(2,3)
1
(2,3)
(3,4)
(2,3)
2
(2,5)
(3,4)
(2,5)
3
(2,5)
(3,6)
(2,5)
4
(2,7)
(3,6)
(2,7)
5
(2,7)
(3,8)
(2,7)



Problem: Bad News Travels Slowly
Remedies
 SplitHorizon
 Do not report route to a destination to the neighbor from which route was learned
 PoisonedReverse
 Report route to a destination to the neighbor from which route was learned, but with infinite distance
 Breaks erroneous direct loops immediately
 Does not work on some indirect loops

Split Horizon with Poison Reverse
(a) 1 1 2 1 3 1 4
(b)
Nodes believe best path is through each other
11213X4
Update
Node 1
Node 2
Node 3
Before break
(2, 3)
(3, 2)
(4, 1)
After break
(2, 3)
(3, 2)
(-1, )
Node 2 advertizes its route to 4 to node 3 as having distance infinity; node 3 finds there is no route to 4
1
(2, 3)
(-1, )
(-1, )
Node 1 advertizes its route to 4 to node 2 as having distance infinity; node 2 finds there is no route to 4
2
(-1, )
(-1, )
(-1, )
Node 1 finds there is no route to 4

Link-State Algorithm
 Basic idea: two step procedure
 Each source node gets a map of all nodes and link metrics
(link state) of the entire network
 Find the shortest path on the map from the source node to all destination nodes
 Broadcast of link-state information
 Every node i in the network broadcasts to every other node
in the network:
ID’s of its neighbors: Ni=set of
neighbors of i
Distances to its neighbors: {Cij | j Ni}  Flooding is a popular method of broadcasting packets

Dijkstra Algorithm: Finding shortest paths in order
Find shortest paths from source s to all other destinations
w’
w
s
w”
Closest node to s is 1 hop away 2nd closest node to s is 1 hop
away from s or w”
3rd closest node to s is 1 hop
away from s, w”, or x z
x
z’ x’

Dijkstra’s algorithm
 N: set of nodes for which shortest path already found
 Initialization: (Start with source node s)
 N = {s}, Ds = 0, “s is distance zero from itself”
 Dj=Csj for all j  s, distances of directly-connected neighbors
 Step A: (Find next closest node i)  Find i  N such that
 Di = min Dj for j  N
 Add i to N
 If N contains all the nodes, stop
 Step B: (update minimum costs)
 For each node j  N  Dj = min (Dj, Di+Cij)  Go to Step A
Minimum distance from s to j through node i in N

Execution of Dijkstra’s algorithm
2  3
1 2
5 3
1
2
 4
1
6
1
1
6

3 3
2
3
5
2
4  3
4
3
2 2
1
2 2
5
2
5
4
Iteration
N
D2
D3
D4
D5
D6
Initial
{1}
3
2
5


1
{1,3}
3
2
4

3
2
{1,2,3}
3
2
4
7
3
3
{1,2,3,6}
3
2
4
5
3
4
{1,2,3,4,6}
3
2
4
5
3
5
{1,2,3,4,5,6}
3
2
4
5
3

Shortest Paths in Dijkstra’s Algorithm
231 231 16136
52 52
3434 132 132
2525 44
231 231 16136
52 52
3434 132 132
2525 44
1 2 3 1 6 1 2 3 1 6 52 52
34 34 132 132
2525 44

Reaction to Failure
 If a link fails,
 Router sets link distance to infinity & floods the
network with an update packet
 All routers immediately update their link database & recalculate their shortest paths
 Recovery very quick
 But watch out for old update messages
 Add time stamp or sequence # to each update message
 Check whether each received update message is new
 If new, add it to database and broadcast
 If older, send update message on arriving link

Why is Link State Better?
 Fast, loopless convergence
 Support for precise metrics, and multiple metrics if necessary (throughput, delay, cost, reliability)
 Support for multiple paths to a destination
 algorithm can be modified to find best two paths

Source Routing
 Source host selects path that is to be followed by a packet
 Strict: sequence of nodes in path inserted into header  Loose: subsequence of nodes in path specified
 Intermediate switches read next-hop address and remove address
 Source host needs link state information or access to a route server
 Source routing allows the host to control the paths that its information traverses in the network
 Potentially the means for customers to select what service providers they use

Example
3,6,B
1
6,B
1,3,6,B
A
Source host
2
3
4
5
B
B
Destination host
6

Multicasting
G1
G1
3 241243
2
1553 23G1
172
2 S11
G1
418 4
242 1213163
3 4G2
3
3 54
G3
 Source S sends packets to multicast group G1
G3

Multicast Routing
 Multicast routing useful when a source wants to transmits its packets to several destinations simultaneously
 Relying on unicast routing by transmitting each copy of packet separately works, but can be very inefficient if number of destination is large
 Typical applications is multi-party conferencing over the Internet
 Example: Multicast Backbone (MBONE) uses reverse path multicasting

Reverse-Path Broadcasting (RPB)
 Fact: Set of shortest paths to the source node S forms a tree that spans the network
 Approach: Follow paths in reverse direction
 Assume each router knows current shortest path to S
 Upon receipt of a multicast packet, router records the packet’s source address and the port it arrives on
 If shortest path to source is through same port (“parent port”), router forwards the packet to all other ports
 Else, drops the packet
 Loops are suppressed; each packet forwarded a router exactly
once
 Implicitly assume shortest path to source S is same as shortest path from source
 If paths asymmetric, need to use link state info to compute shortest paths from S

Example: Shortest Paths from S
G1
172 234
G1
24123
1 553 23G1
418 4
242 1213163
3 4G2
3
G3
 Spanning tree of shortest paths to node S and parent ports are shown in blue
1
2 13
S
54
G1
G3

Example: S sends a packet
G1 G1
172 234
24123
1 553 23G1
418 4
242 1213163
3 4G2
3
G3
 S sends a packet to node 1
 Node 1 forwards to all ports, except parent port
1
2 13
S
54
G1
G3

Example: Hop 1 nodes broadcast

G1 G1
172 234
24123
1 553 23G1
418 4
242 1213163
3 4G2
3
G3
 Nodes 2, 3, 4, and 5 broadcast, except on parent ports  All nodes, not only G1, receive packets
1
2 13
S
54
G1
G3

Example: Broadcast continues
G1
172 234
G1
24123
1 553 23G1
418 4
242 1213163
3 4G2
3
G3
 Truncated RPB (TRPB): Leaf routers do not broadcast if none of its attached hosts belong to packet’s multicast group
1
2 13
S
54
G1
G3

Internet Group Management
Protocol (IGMP)
 Internet Group Management Protocol:
 Host can join a multicast group by sending an IGMP
message to its router
 Each multicast router periodically sends an IGMP query message to check whether there are hosts belonging to multicast groups
 Hosts respond with list of multicast groups they belong to  Hosts randomize response time; cancel response if other
hosts reply with same membership
 Routers determine which multicast groups are associated with a certain port
 Routers only forward packets on ports that have hosts belonging to the multicast group

Reverse-Path Multicasting
(RPM)
 Reverse Path Multicasting (RPM) relies on IGMP to identify multicast group membership
 The first packet to a given (source, group), i.e. (S,G) is transmitted to all leaf routers using TRPB
 Each leaf router that has no hosts that belong to this group on any of its ports, sends a prune message to its upstream router to stop sending packets to (S, G)
 Upstream routers that receive prune messages from all their downstream routers, send prune messages upstream
 Prune entries in each router have finite lifetime
 If a host requests to join a group, routers can cancel previous pruning with a graft message

Example: Pruning for G1
G1
172 234
G1
24123
1 553 23G1
418 4
242 1213163
3 4G2
3
G3
 Routers 3, 4, and 6 send prune messages upstream
1
2 13
S
54
G1
G3

Example: RPM Multicast Tree
G1
172 234
G1
24123
1 553 23G1
418 4
242 1213163
3 4G2
3
G3
 RPM multicast tree after pruning
1
2 13
S
54
G1
G3

Example: Graft from Router 6
G1
172 234
G1
24123
1 553 23G1
1
2 13
418 4
S
54
G1
Graft
242 1213163
3 4G1
3
G3
 Graft message flows upstream to router 1
G3

Example: RPM Tree after Graft
G1
172 234
G1
24123
1 553 23G1
418 4
242 1213163
3 4G1
1
2 13
S
54
G1
3
G3
G3

Network Address Translation (NAT)
 Class A, B, and C addresses have been set aside for use within private internets
 Packets with private (“unregistered”) addresses are discarded by routers in the global Internet
 NAT (RFC 1631): method for mapping packets from hosts in private internets into packets that can traverse the Internet
 A device (computer, router, firewall) acts as an agent between a private network and a public network
 A number of hosts can share a limited number of registered IP addresses
 Static/Dynamic NAT: map unregistered addresses to registered addresses
 Overloading: maps multiple unregistered addresses into a single registered address (e.g. Home LAN)

NAT Operation (Overloading)
Address Translation Table:
192.168.0.10; x 192.168.0.13; w
128.100.10.15; y 128.100.10.15; z
128.100.10.15;y
Public Network
128.100.10.15; z
192.168.0.10;x
Private Network
192.168.0.13;w
NAT Device
 Hosts inside private networks generate packets with private IP address & TCP/UDP port #s
 NAT maps each private IP address & port # into shared global IP address & available port #
 Translation table allows packets to be routed unambiguously