CS461 Switching PDF

CS461 Switching Switched Networks Circuit Switching Packet Switching Circuit and Packet Switching Comparison CS461: Computer Networks HiLCoE School of Computer Science and Technology ...

CS461 Switching Switched Networks Circuit Switching Packet Switching Circuit and Packet Switching Comparison CS461: Computer Networks HiLCoE School of Computer Science and Technology  CS461 Contents Switching Switched Networks Circuit Switching Packet Switching Switched Communications Networks Comparison Circuit Switching Packet Switching Comparing Circuit and Packet Switching  CS461 Switched Communications Networks Switching Switched Networks Ihow networks used to interconnect many devices Circuit Switching Packet Switching I Switched Communication Networks Comparison I Data transmitted from source to destination through network of switching nodes I Switching nodes are not concerned with content of data I Collection of nodes referred to as communications network I Devices attached to network are called stations I Node—station links often dedicated point-to-point links I Node—node links often multiplexed I Network is often not fully connected; but desirable to have multiple paths for each pair of stations I Two technologies used in wide area switched networks: circuit switching and packet switching  CS461 Simple Switching Network Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Contents Switching Switched Networks Circuit Switching Packet Switching Switched Communications Networks Comparison Circuit Switching Packet Switching Comparing Circuit and Packet Switching  CS461 Example of Old-Style Circuit Switch Switching Switched Networks Circuit Switching Packet Switching Comparison Seattle Municipal Archives from Seattle, WA via Wikimedia Commons; CC BY 2.0  CS461 Example of Current-Style Circuit Switch Switching Switched Networks Circuit Switching Packet Switching Comparison Mudares via Wikimedia Commons; CC BY 2.5 cjwlabasst via Wikimedia Commons; Public domain  CS461 Circuit Switching Networks Switching Switched Networks I Dedicated communications path between two stations; Circuit Switching path is sequence of links between nodes Packet Switching I On each physical link, logical channel allocated to Comparison connection I Three phases: 1. Circuit establishment: Create station-to-station circuit, allocating resources as needed 2. Data transfer: Analog or digital data transmitted from station to station 3. Circuit disconnect: Circuit is terminated, de-allocation of resources  CS461 Circuit Switching Networks Switching Switched Networks I Path established before data transfer begins; channel Circuit Switching capacity must be reserved between each pair of nodes in Packet Switching path, and switching capacity allocated at each Comparison switching node I Developed to handle voice traffic, but also used for data traffic I Examples: public telephone network, private telephone networks, prviate data networks  CS461 Circuit Establishment Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Example Connection Over a Public Switching Circuit-Switching Network Switched Networks Circuit Switching Packet Switching Comparison  CS461 Issues in Circuit-Switching Switching Switched Networks Efficiency Circuit Switching Packet Switching I Resources reserved for duration of connection (capacity Comparison in all links, circuit in all switches) I Inefficient if applications do not use the capacity Quality I Data rate, delay guaranteed for duration of connection Link Speeds I End devices must be the same speed  CS461 Contents Switching Switched Networks Circuit Switching Packet Switching Switched Communications Networks Comparison Circuit Switching Packet Switching Comparing Circuit and Packet Switching  CS461 Packet Switching Switching Switched Networks I For data connections, much of the time the line is idle; Circuit Switching circuit-switching inefficient Packet Switching I Packet switching: break data into packets, sending one Comparison at a time from source to destination  CS461 Types of Packet Switching Switching Switched Networks Datagram Packet Switching Circuit Switching Packet Switching I Each packet is treated independently of all others Comparison I Packets belonging to the same message may: I Take different paths across the network I Arrive at destination out of order and may be lost I Packets need headers so switches know where to send them Virtual Circuit Packet Switching I Virtual circuit setup and teardown I Once setup, data is transferred as individual packets I Take the same path across the network I Arrive in-order at the destination, but may be lost I Packets need headers so switches know what is the next switch it must be sent to  CS461 Packet Switching: Datagram Approach: (a) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Datagram Approach: (b) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Datagram Approach: (c) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Datagram Approach: (d) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Datagram Approach: (e) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 The Use of Virtual Circuits Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Virtual-Circuit Approach: (a) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Virtual-Circuit Approach: (b) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Virtual-Circuit Approach: (c) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Virtual-Circuit Approach: (d) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Packet Switching: Virtual-Circuit Approach: (e) Switching Switched Networks Circuit Switching Packet Switching Comparison  CS461 Contents Switching Switched Networks Circuit Switching Packet Switching Switched Communications Networks Comparison Circuit Switching Packet Switching Comparing Circuit and Packet Switching  ITS323 Comparison of Communication Switching Switching Techniques Switched Networks Circuit Switching Packet Switching Comparison  CS461 Routing Design Strategies Protocols Routing CS461: Computer Networks HiLCoE School of Computer Science and Technology  CS461 Contents Routing Design Strategies Protocols Routing in Switched Networks Routing Strategies Routing Protocols and Algorithms  CS461 Routing in Switched Networks Routing Design Which path or route to take from source to destination? Strategies Protocols  CS461 Routing in Switched Networks Routing Design I Routing is a key design issue in switched networks Strategies I Question: What path (route) should be taken from Protocols source to destination? I Answer: Choose the “best” path! I What is “best”, and how to choose it? I Real networks may have 100’s to 100,000+ nodes, and many possible paths I Routing is needed in circuit-switched and packet-switched networks (we focus on packet-switched networks)  CS461 Requirements of Routing Algorithms Routing Design Correctness path must be from intended source to intended Strategies destination Protocols Simplicity easy/cheap to implement Robustness still deliver in presence of errors or overload Stability path changes should not be too frequent Optimality choose best paths Fairness ensure all stations obtain equal performance Efficiency minimise the amount of processing and transmission overhead  CS461 Routing Terminology Routing Design Link direct connection between two nodes Strategies Path a way between two nodes, via one or more links Protocols Hop to traverse a link Neighbour a node at the other end of a link Cost value assigned to link to indicate cost of using that link Topology arrangement of nodes and links in a network Least-cost routing is typically used: choose a path with least cost  CS461 Example of Network Configuration Routing Design Strategies Protocols  CS461 Elements of Routing Techniques Routing Design I Which performance criteria are used to select a path? Strategies I When is a path selected? Protocols I Which nodes are responsible for selecting path? I Which nodes provide information about network status? I topology, link costs, current usage I How often is network status information updated?  CS461 Elements of Routing Techniques Routing Design Strategies Protocols  CS461 Contents Routing Design Strategies Protocols Routing in Switched Networks Routing Strategies Routing Protocols and Algorithms  CS461 Strategy 1: Fixed Routing Routing Design I Use a single permanent route for each source to Strategies destination pair Protocols I Routes are determined using a least cost algorithm, e.g. Dijkstra, Bellman-Ford algorithms I Route is fixed I At least until a change in network topology (node/link added/deleted) I Hence cannot respond to traffic changes (e.g. overload in one portion of the network) I No difference between routing for datagrams and virtual circuits I Advantage is simplicity I You assign the routes at the start, and then nothing to do I Disadvantage is lack of flexibility I When the network is operating, changes in load may mean better routes than initially selected should be used  CS461 Fixed Routing Example Routing Design How many least-cost paths are there? What are they? Strategies Protocols  CS461 Routing Tables Routing Design I A node determines least-cost paths to all possible Strategies destinations Protocols I No need to store entire path; store only next node in path (and optionally cost of path) I Path information stored in routing table (or directory) Destination Next Path Cost Node1 Nodex c1 Node2 Nodey c2... I Routing table may be stored on central node or distributed amongst each node I Separation of routing and forwarding: Routing: strategies, protocols and algorithms are used to create routing table Forwarding: routing table used to determine where to send the data to next  CS461 Centralised Routing Table Example Routing Design Routing table stored on one node Strategies Protocols  CS461 Distributed Routing Tables Example Routing Design Each node has its own routing table Strategies Protocols  CS461 Fixed Routing Summary Routing Design I When is a decision made for a route? At network Strategies startup Protocols I Which node chooses the route? Centralised or distributed I Where does the network information come from? All nodes I When is the network information updated? Never I In practice, only used for small, stable networks (10s of nodes)  CS461 Strategy 2: Flooding Routing I Instead of choosing a route before sending the data, Design just send the data to everyone Strategies I A copy of the original packet is sent to all neighbours of Protocols the source I Each node that receives the packet, forwards a copy of the packet to all of its neighbours I Advantages: I All possible routes are tried; at least one packet will take minimum hop route, e.g. setup a virtual circuit I All nodes are visited, e.g. distributing network status (topology) information I Simple I Disadvantages: I Inefficient: need to send many copies of packet to get one packet from source to destination I Using hop limit and/or selective flooding, packet may not reach destination  CS461 Flooding Extensions Routing Design 1. Don’t send back to the node that just sent you the Strategies packet Protocols 2. Only forward packet once: nodes remember which packets they have forwarded (based on sequence number and source/destination addresses); do not forward a packet if you have previously forwarded that same packet 3. Duplicate detection: each packet has a sequence number, so if destination receives multiple copies of the same packet, it can discard the duplicates 4. Hop Limit: include a “hop counter” in the packet; decrement the counter each time the packet is forwarded—if it is 0, then discard the packet 5. Selective Flooding: send to selection of neighbours. E.g. random, round-robin, probability-based  CS461 Flooding Example Routing Design Destination is node 6; Hop limit is 3 Strategies Protocols  CS461 Flooding Example Routing Design Strategies Protocols  CS461 Flooding Example Routing Design Strategies Protocols  CS461 Flooding Example Routing Design How many packets transmitted in previous example? How Strategies much data is delivered to destination? What if hop limit was Protocols 2?  CS461 Strategy 3: Adaptive Routing Routing Design I Use a least-cost routing algorithm to determine a route, Strategies and adapt the route as network conditions change Protocols I Used in almost all packet switching networks, e.g. the Internet I Requires network status information from: 1. Local to node: route to output link that has shortest queue (rarely used) 2. Adjacent nodes: delay/link status, then least-cost routing 3. All nodes: similar to option 2  CS461 Characteristics of Adaptive Routing Routing Design Advantages Strategies Protocols I Improved performance: potentially can select the most suited paths; balance amount of traffic across the network Disadvantages I Decisions more complex (complex algorithms needed to select the best path) I Tradeoff between quality of network information and overhead I The more information required for routing decisions, and the more often updates are delivered, then the more overhead in the network I Reacting too quickly can cause oscillation I Reacting too slowly means information may be irrelevant  CS461 Contents Routing Design Strategies Protocols Routing in Switched Networks Routing Strategies Routing Protocols and Algorithms  CS461 Routing Protocols Routing Design I A routing protocol is used by nodes to automatically Strategies determine the routes in the network Protocols I A routing protocol specifies: I Routing algorithm for determining least-cost routes: e.g. Dijkstra, Bellman-Ford or variants I Routing information to be exchanged between nodes I Formats of messages used to deliver routing information I Rules as to when to send routing messages and what to do upon receiving them I Metrics to be used in routing algorithm (hop count, bandwidth,... ) I Optionally, default values of specific parameters may be given I Real routing protocols include: OSPF, RIP, BGP, IGRP, EIGRP, PNNI, IS-IS, DSDV, AODV,...  CS461 Example: Link State Routing Routing Design I Example: link state routing protocol that uses Dijkstra’s Strategies algorithm to determine the least–cost routes Protocols I Aim: Each node learns the topology of the network, then calculates the least–cost route from itself to every other node using Dijkstra’s algorithm I Steps for each node: 1. Record the state of its own links (e.g. source/destination, metric) 2. Send the state of its own links to every other node by flooding a link state packet I identity of the current node I list of links that the current node has, including their costs I sequence number (used by the flooding protocol) I hop count or age (used by the flooding protocol) 3. Form a shortest path tree from itself to every other node 4. Build a routing table based on the shortest path tree  CS461 Example: Link State Routing Routing Design What is the link state packet created by node 1? What is Strategies the routing table created by node 1? Protocols  CS461 Summary: Concepts Routing Design I Communication networks are formed by connecting Strategies devices across multiple links Protocols I Switching is the method of delivering data between source and destination across multiple links I Stations or end-user devices act as sources and destinations of data I Switches connect the links and forward data between source and destination I Circuit and Packet Switching techniques determine how to deliver data across one or more paths between source and destination I Routing determines what path to take between source and destination I There are different routing metrics, strategies, algorithms and protocols available  CS461 Summary: Practice Routing Design I Circuit switching was developed for traditional Strategies telephone networks and is still used today in those (and Protocols other) networks I Packet switching was developed to be more efficient for delivering computer generated data over networks I Packet switching is the concept used in the Internet and in almost all new Wide Area Networks (WANs) today I Adaptive routing strategies are needed for almost all WANs I Dijkstra and Bellman Ford are two of the most common algorithms for determining the shortest path between source and destination I The trade-offs between the different routing protocols often depend on the size of networks, the amount of traffic and the rate at which the network changes