CS 313 Introduction to Computer Networking & Telecommunication Chapter 5 Network Layer Chi-Cheng Lin, Winona State University Topics Design Issues Routing Algorithms Congestion Control Internetworking
2 Network Layer Design Issues Concern: How to get packets from source to destination Issues
Store-and-forward packet switching Services provided to transport layer Implementation of connectionless service Implementation of connection-oriented service Comparison of virtual-circuit and datagram networks 3 Store-and-Forward Packet Switching
The environment of the network layer protocols ISPs equipment 4 Services Provided to Transport Layer Designing goals Independent of subnet technology Transport layer shielded from number,
type, and topology of subnets Uniform network address numbering Even across LANs and WANs Two Types of Services Connectionless, e.g., IP Connection-oriented, e.g., ATM 5 Implementation of Connectionless Service Routing within a diagram subnet
ISPs equipment As table (initially) As table (later) Cs Table Es Table 6 Implementation of Connection-Oriented Service
Routing within a virtual-circuit subnet. ISPs equipment As table Cs Table Es Table 7 Implementation of Connection-Oriented Service
Routing within a virtual-circuit subnet. 8 Comparison of Virtual-Circuit and Datagram Subnets 9 Routing Algorithms Network layer software
Deciding which output line an incoming packet should be transmitted to Datagram: made for each packet VC: made for new VC setup 10 Routing Algorithms Desirable Properties
Correctness Simplicity Robustness Stability Fairness Optimality 11 Routing Algorithms - Optimality What to optimize? Minimizing mean packet delay
Maximizing total network throughput Problem The above two are in conflicts (see next slide) Compromise Minimizing number of hops a packet must take from source to destination 12 Fairness vs. Efficiency Network with a conflict between fairness
and efficiency. Classes of Routing Algorithm Two major classes Non-adaptive Adaptive 14 Two Major Classes of Routing Algorithm Adaptive
Algorithms differ in where to get information, e.g., Locally From adjacent routers From all routers when to change routes, e.g., Every T sec When the load changes When the topology changes what metric used for optimization, e.g., Distance Number of hops
Estimated transit time 15 Routing Algorithms to be Studied Static (i.e., nonadaptive) routing Shortest path routing Flooding
Dynamic (i.e., adaptive) routing Distance vector routing Link state routing 16 Optimality Principle If router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. Proof?
K I J L 17 Sink Tree Direct consequence of optimality principle Network graph
Node/vertice: router Edge: link The set of optimal routes from all sources to a given destination form a tree rooted at the destination Might not be unique Goal of routing algorithms Discover and use the sink tree for all routers 18 Sink Tree
Example Distance metric: number of hops Network Sink tree 19 Shortest Path Algorithm Given a pair of routers, find the shortest path between them Network graph
Node/vertice: router Edge: link Labels of edges Function of factors Weighting function changed for different criteria 20 Dijkstra's Algorithm Each node labeled with
(distance from source, best known path) Initially distance: infinity best known path: unknown Label might change to reflect better paths Node is either tentative or permanent Initially tentative As a path from source to that node discovered, label becomes permanent and never gets changed 21
First six steps to compute shortest path from A to D 22 Dijkstra's Algorithm How do we find the path? The algorithm given in the book works from destination to source
Why? 23 Flooding Every incoming packet is sent out on every outgoing line except for the input line Problem Large number of packets are generated
Solutions Hop counter Avoiding duplicates Selective flooding 24 Flooding - Conclusion Optimal Shortest path is always chosen No other algorithm can produce a shorter
delay Robust Easy to set up Only need to know its neighbors Not practical in most applications Useful in some applications Military application: robustness Wireless networks
Metric of other routing algorithms 25 Distance Vector Routing Table in each router Giving Best known distance to each destination Which line to use to get there Indexed by each router Each entry contains two parts
Preferred outgoing line to use for that destination Estimate of "distance" to go there Best known distance to each destination Updated by exchanging information with neighbors 26 Distance Vector Routing Router Knows "distance" to each neighbor Sends list to each neighbor every T msec
Receives lists from neighbors every T msec If neighbor X knows Distance from X to I is XI, and Distance from the router to X is m then delay from router to I via X is (XI + m) Performs calculation for each neighbor to find the best Old table not used in calculation 27 A network. Input from A, I, H, K, and
the new routing table for J. 28 Distance Vector Routing Count-to-Infinity Problem Good news spread fast, bad news leisurely Infinity has to be defined 29
Link State Routing A router 1. Discovers its neighbors and learn their network addresses - HELLO 2. Measures the delay or cost to each neighbor - ECHO 3. Constructs a packet telling all it has just learned link state packet 4. Sends this packet to all other routers flooding w/ duplicate avoidance 5. Computes the shortest path to every other router Dijkstras algorithm
30 Link State Routing In effect Complete topology and all delays are experimentally measured and distributed to every router Construct network topology from link state packets Dijkstra's algorithm is applied to find the shortest path
31 Building Link State Packets (a) A network. (b) The link state packets for this network. Hierarchical Routing Problem Network size grows Routing tables grow
Solution Hierarchical routing Idea Routers are divided into "regions" Router knows detail about routing within its region Router knows nothing about internal structure of other region 33
Path length from 1A to 5C? 34
