文档介绍：Minimax Open Shortest Path First (OSPF) Routing Algorithms works Supporting the SMDS ServiceFrank Yeong-Sung Lin (林永松)Information Management DepartmentNational Taiwan UniversityTaipei, Taiwan, ?Introduction to SMDS?The default Inter-Switching System Interface (ISSI) routing algorithm?Minimax Criteria?Problem Formulation?Solution putational Results?Summary3Introduction to the SMDS Service?Switched Multi-megabit Data Service (SMDS) is a public, high-speed, connectionless (datagram), packet switched data service that the Regional Bell panies (RBOCs) have offered.?Provides LAN-like performance and features over a wide area.?Regarded as the first phase of B-ISDN?High-speed access ( Mbps to 45 Mbps)?Multicast capability4The Default ISSI Routing Algorithm?Open Shortest Path First (OSPF) routing algorithms–Each Switching System (SS) has identical information about (i) work topology and (ii) the link set metrics.–Each SS uses the link set metrics (arc weights) to calculate a shortest path spanning tree (by applying the Dijkstra’s algorithm) for each root to transmit individually addressed and group addressed (multicast) traffic.–OSPF routing protocols are also widely applied in the and other high- Default ISSI Routing Algorithm?The default link set metrics: inversely proportional to the link set capacities?Advantages–Simplicity (static)–Minimizing the total link set utilization factors?Disadvantages–Does not respond to work load fluctuation–Does not impose link set capacity constraints6Minimax Criteria?The maximum link set utilization is minimized.?Advantages:–Respond to and balance work load–Remain optimal work load grows uniformly–Robust to demand fluctuation–The difficulty of non-linearity is circumvented–Perform well with respect to other performance measures, . packet loss rate and average packet delay–Conform to the default routing algorithm (OSPF)7Problem FormulationNotation?work is modeled as a graph G(V, L).?V = {1, 2, …, N}: the set o