CSCI 4550/8556 Computer NetworksIntroductionCharacterizations of NetworksDifferences between LAN and WANPacket SwitchesConnections to Packet SwitchesPacket Switches as Building BlocksStore and ForwardPhysical Addressing in a WANNext-Hop ForwardingChoosing the Next HopSource IndependenceHierarchical Addresses and RoutingWAN Architecture and CapacityRouting in a WANModeling a WANRoute Computation with a GraphRedundant Routing InformationDefault RoutesBuilding Routing TablesComputation of Shortest Path in a GraphGraphs with Weighted EdgesSynopsis of Dijkstra’s AlgorithmDistance MetricsDynamic Route ComputationDistributed Route ComputationVector Distance AlgorithmVector Distance Algorithm (Cont’d)Link State RoutingComparisonExamples of WAN Technology (1)Examples of WAN Technology (2)Examples of WAN Technology (3)SummaryCSCI 4550/8556Computer NetworksComer, Chapter 13:WAN Technologies and RoutingIntroduction-LANs can be extended using techniques described in the previous chapter -But they cannot be extended arbitrarily far or to handle arbitrarily many computers -Distance limitations even with extensions -Broadcast communication is a problem -We need other technologies for larger networksCharacterizations of Networks-Local Area Network (WAN) - single building -Metropolitan Area Network (MAN) - single city -Wide Area network (WAN) - country, continent, planetDifferences between LAN and WANSatellite bridge can extend LAN across large distances Still cannot accommodate arbitrarily many computers WAN must be scalable to long distances and many computersPacket SwitchesTo span long distances or many computers, a network must replace the shared medium with packet switches Each switch moves an entire packet from one connection to another A packet switch is just a small computer with several network interfaces, memory and program dedicated to the packet switching functionConnections to Packet SwitchesPackets switches may connect to computers and to other packet switches Typically high speed connections are to other packets switches, lower speed to computers Technology details depend on desired speedPacket Switches as Building BlocksPacket switches can be linked together to form WANs WANs need not be symmetric or have regular connections Each switch may connect to one or more other switches and one or more computersStore and ForwardData delivery from one computer to another is accomplished through store-and-forward technology Packet switch stores incoming packet ... and forwards the packet to another switch or computer Packet switch has internal memory Can hold packet if outgoing connection is busy Packets for each connection held on queuePhysical Addressing in a WANPhysical addressing in a WAN is similar to LAN Data transmitted in packets (equivalent to frames) Each packet has format with header Packet header includes destination and source addresses Many WANs use hierarchical addressing for efficiency One part of address identifies destination switch Other part of address identifies port on switchNext-Hop ForwardingPacket switch must choose outgoing connection for forwarding If destination is local computer, packet switch delivers computer port If destination is attached another switch, this packet switch forwards to next hop through connection to another switch Choice based on destination address in packetChoosing the Next HopPacket switch doesn't keep complete information about all possible destination Just keeps next hop So, for each packet, packet switch looks up destination in table and forwards through connection to next hopSource IndependenceThe next hop to the destination does not depend on the source of a packet.This is called source independence .It allows fast, efficient routing.A packet switch need not have complete information, just information about the next hop. This… reduces the total information needed by a packet switch, andincreases the dynamic robustness of the network - it can continue to function even if the topology changes without notifying all nodes in the entire network.Hierarchical Addresses and RoutingThe process of forwarding a packet is called routing .Information is kept in a routing table .Many entries in the table may have same next hop address.In particular, all destinations on same switch have same next hop address.Thus, the routing table can be collapsed (simplified):WAN Architecture and CapacityMore computers on a network means more traffic.We can add capacity to a WAN by adding more links and packet switches. Packet switches need not have computers attached. Interior switch - no attached computers Exterior switch - attached computersRouting in a WANBoth interior and exterior switches…forward packets, and need routing tables We must have: Universal routing – there must be a next hop address for each possible destination.Optimal routes – the next hop identified by the table must be on shortest path to destination.Modeling a WANTo model a WAN, use a graph: Nodes model switches Edges model direct connections between switches The graph captures the essence of the network, ignoring the attached computers.Route Computation with a GraphWe can represent a routing table with edges: Graph algorithms can be applied to find routes.Redundant Routing InformationNotice the duplication of information in routing table for node 1: Switch 1 has only one outgoing connection; all traffic must traverse that connection This can easily be extrapolated to UNO’s campus networks and the Internet.Default RoutesWe can possibly summarize many routing table entries with a default route .If a destination does not have an explicit routing table entry, we use the default route: The use of a default route is optional (see node 3) Consider most of the individual computers in PKI.Building Routing TablesHow to enter information into routing tables: Manual entry - initialization file Dynamically - through runtime interface How to compute routing table information: Static routing - at boot time Dynamic routing - allow automatic updates by a program Static is simpler; it doesn't accommodate changes to the network topology.Dynamic requires additional protocol(s); it can work around network failures.Computation of Shortest Path in a GraphAssume the graph representation of a network at each node. Use Dijkstra's algorithm to compute shortest path from each node to every other node. Extract next-hop information from resulting path information. Insert next-hop information into routing