Building Link State Packets


The packet starts with the identity of the sender, followed by a sequence number and age, and a list of dual items( neighbor, the delay to it ). The hard part is when to build them, at regular intervals or when some significant event occurs? Practice shows that once an hour is often enough.
计算机网络
The Network Layer
The Network Layer
Topics
Network Layer Design Issues
Store-and-Forward Packet Switching
Implementation of Connectionless Service
Routing Algorithm Basics



The routing algorithm is that part of the network layer software responsible for deciding which output line an incoming packet should be transmitted on. If the subnet uses datagrams internally, this decision must be made anew for every arriving data packet since the best route may have changed since last time. If the subnet uses virtual circuits internally, routing decisions are made only when a new virtual circuit is being set up.
Flooding


Basic idea: Forward an incoming packet across every outgoing line, except the one it came through.������ Basic problem: how to avoid ―drowning by packets‖?������ Use a hop counter: after a packet has been forwarded across N routers, it is discarded.������ Be sure to forward a packet only once (i.e. avoid directed cycles). Requires sequence numbers per source router.������ Flood selectively: only in the direction that makes sense.������ Flooding makes sense only when robustness is needed, e.g. in military applications
or Static: the routing table is computed in advance, off-line, and downloaded to the routers when the network is booted. Adaptive or Dynamic: change their routing decisions to reflect changes in the topology, and usually the traffic as well.
Yes:
the timer should be started when the ECHO packet is queued. You may redirect traffic in such a way that the alternative route is unloaded. No: the timer should be started when the ECHO packet reaches the front of the queue. The shortest path you choose may be overloaded.
Shortest Path Routing



Idea: build a graph of the subnet, with each node of the graph representing a router and each arc of the graph representing a communication line. To choose a route between a given pair of routers, the algorithm just finds the shortest path between them on the graph. the labels (weights) on the arcs could be computed as a function of the distance, bandwidth, average traffic, communication cost, measured delay, and other factors. Shortest Path Criteria: sum of the weights all the way, or, the number of hops.
Distributing the Link State Packets



Use a flooding algorithm, and dam the flood through sequence numbers: all routers maintain a list of (source, seq number)-pairs.������ To safeguard against old data, down links, etc. an age is added to an LSP. The age is decremented once a second, and every time it is forwarded by a router. When the age hits zero, the LSP is discarded. To guard against errors on the router-router lines, all link state packets are acknowledged.
Distance Vector Routing
Bellman-Ford or Ford-Fulkerson algorithm



Distance Vector Routing Algorithms:each router maintains a table (i.e, a vector) giving the best known distance to each destination and which line to use to get there, which are updated by exchanging information with the neighbors periodically. Updating Process: Take a look at the costs that your direct neighbors are advertising to get a packet to the destination. Select the neighbor whose advertised cost, added with the cost to get to that neighbor, is the lowest. Advertise that new cost to the other neighbors. In DVR, there is the problem of count-to-infinity in the presence of node crashes.
Routing Algorithm Basics(3)

Metrics used for optimization
Distance Number
of hops Time delay

Two major classes of routing algorithms
Nonadaptive
DVR Example

(a)A subnet. (b)Input from A, I, H, K, and the new routing table for J
Link State Routing


Link State Routing: broadcast info on the entire network topology to all routers, and let each of them calculate a sink tree to the other routers. Each router must do the following:
Implementation of Connection-Oriented Service
Comparison of Virtual-Circuit and Datagram Subnets