NETWORKING AND DISTRIB OPERATING SYSTEMS
NETWORKING AND DISTRIB OPERATING SYSTEMS CS 471G
Popular in Course
verified elite notetaker
Popular in ComputerScienence
This 57 page Class Notes was uploaded by Juvenal Beahan on Friday October 23, 2015. The Class Notes belongs to CS 471G at University of Kentucky taught by Staff in Fall. Since its upload, it has received 9 views. For similar materials see /class/228217/cs-471g-university-of-kentucky in ComputerScienence at University of Kentucky.
Reviews for NETWORKING AND DISTRIB OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/23/15
Chapter 13 WAN Technologies and Routing Introduction 0 Repeaters and Bridges help extend LANs 0 However they cannot be extended arbitrarily far and they cannot handle an arbitrary number of com puters 0 Problems include Distance limitations signal strength and cor rectness Congestion Broadcast and Multicast traffic Privacy 0 We need to use some other type of technology to scale to larger networks CS 4717 Spring 2002 Jim Gri ioen 1 Terminology Networks are often classified as being of one of the following types 0 DAN a Desktop Area Network connects units on a single desktop 0 SAN a System Area Network connects ma chines in close proximity to one another a single room 0 LAN a Local Area Network connects local machines eg a single building 0 MAN a Metropolitan Area Network connects machines in a single city 0 WAN a Wide Area Network connects machines across the country continents or planets CS 4717 Spring 2002 Jim Gri ioen 2 LANS VS WANS o Repeaters only a tiny bit useful Bridges are bet ter 0 A satellite bridge can extend LAN across large distances 0 Still cannot accommodate arbitrarily many com puters o WAN must be scalable to long distances and many computers CS 4717 Spring 2002 Jim Gri ioen 3 WAN Requirements 0 To span large distances and support many com puters the network must 1 maintain signal strength and packet correct ness as the distance between nodes increases 2 move away from totally shared mediums more machines means more competition for the medium congestion channel allocation does not scale eg CSMA Token Ring o The above two requirments imply Packet Switch ing CS 4717 Spring 2002 Jim Gri ioen Packet Switching o A Packet Switch is a small computer with two or more network interfaces memory and a pro gram that forwards packets based on routing ta bles 0 Packet Forwarding is the task of retransmitting a packet toward the destination on the sender s behalf ie storenforward reads in an entire packet and stores it copies it to a queue of packets waiting to be sent on the outgoing interface has limited amount of memory to buffer in coming and outgoing packets each network interface on the switch has a queue for incoming and outgoing packets 0 Packet Routing refers to the task of determining the best path to the destination 0 A Packet Switched Network is a network that uses packet switches to route and forward pack ets from the source to the destination 0 Do bridges qualify as packet switches Dumb bridges do not Learning bridges do CS 4717 Spring 2002 Jim Gri ioen 5 The Final Requirment 0 Routing Scalability Must know the route to every possible desti na on o Forwarding Scalability Need to forward packets quickly need to pro cess the packet and find the best route fast CS 4717 Spring 2002 Jim Gri ioen 6 WAN Topology WANs use a twolevel topology o Switches connect to Switches to form the inter connect Hosts and LANs connect to some Switches III In H m H Figure 1 Detailed WAN topology View III III Packet Switched Network H m H Figure 2 Logical WAN topology CS 4717 Spring 2002 Jim Gri ioen 7 WAN Addressing Flat Address Space 0 Flat Addressing refers to the fact that each ma chine has a unique id as its address 0 Any id can be assigned to any machine as long as it is unique Packet Switched Network HH Figure 3 Each machine need a unique id CS 4717 Spring 2002 Jim Gri ioen 8 WAN Addressing Hierarchical Addressing 0 Consider the following topology Figme 4 Hialemchicel Addiessing 0 Each host can be uniquely labelled addressed by 7 the switch to which it connects and 7 the interface port on that switch 0 The advantages of hierarchical addressing will become evident in just a minute cs 4713p1mg 2002 7 Jun Gn iuen 9 Routing Tables o The Routing Table stored in each switch defines the route that a packet should take to get to the destination 0 Need one entry in the table per destination ie per machine on the WAN 1 How does this affect routing Routing Table size at each switch is propor tionate to the number of hosts connected to the WAN May require a lot of memory space to store entire table Must learn all these routes somehow 2 How does this affect forwarding May take a long time to look up the host in the routing table CS 4717 Spring 2002 Jim Gri ioen 10 Next Hop Routing 0 We said that a packet switch must know the best route to the destination for all destinations o Storing the entire path to each destination will consume a lot of memory 0 How can you reduce the amount of space needed to store the best route to a destination need to separate the gtllt problem of learningchoosing the best route from the gtllt problem of remembering the route that was chosen Once you know the best route you only need to remember the next hop along the route 0 Using next hop routing each routing table entry has the form DstAddr NextHop or DstAddr Outgoinglnterface CS 4717 Spring 2002 Jim Gri ioen 11 Addressing and Routing o By combining hierarchical addressing and next hop routing we can reduce the size of the routing table even further 0 With next hop routing the routing tablejust records the interface to use to get to the destination 0 All destinations on the same switch will use the same interface 0 Aside Terminology Exterior Switch has computers attached Interior Switch no computers attached just switches 0 80 only remember routes to exterior switches not hosts 0 So given a host address we need a way to figure out which switch it is attached to o Hierarchical addressing provides the necessary information 0 As a result we only need to store one routing table entry per exterior switch switch packets based on the switch number that the host attaches to CS 471 Spring 2002 Jim Gri ioen 12 Reducing Routing Table Size 0 Note that a switch must learn the best route to every possible destination 0 For example consider the following network Figure 5 An Example Network Topology 0 Routing info maintained at switches and hosts Host A Switch 1 Switch 2 Dest Route Dest Route Dest Route CS 4717 Spring 2002 Jim Gri ioen Reducing Routing Table Size continued o Nexthop routing reduces table size by forgetting all but the next hop 0 For example consider the following network 0 Next Hop Routing Tables Figure 6 An Example Network Topology Host A Switch 1 Switch 2 Dest Route Dest Route Dest Route CS 4717 Spring 2002 Jim Gri ioen o If you don t know the best route how will you decide if a better route comes along E how will you know if a new route is better or worse than the existing route CS 4717 Spring 2002 Jim Gri ioen 15 Reducing Routing Table Size continued o Hierarchical Routing reduces the number of en tries in the table 0 For example consider the following network Figure 7 An Example Network Topology 0 Routing Tables look like Host A Switch 1 Switch 2 Dest Route Dest Route Dest Route CS 4717 Spring 2002 Jim Gri ioen Reducing Routing Table Size continued 0 Default Routes further reduce table size 0 Particularly useful for Host Machines 0 For example consider the following network Figure 8 An Example Network Topology 0 Routing Tables look like Host A Switch 1 Switch 2 Dest Route Dest Route Dest Route CS 4717 Spring 2002 Jim Gri ioen Src Dependent VS Src Independent 0 Using Source Dependent routing the next hop to the destination depends on the source of the packet 0 Source Dependent routing allow packets from dif ferent machines to travel different routes Figure 9 An Example Network Topology 0 Using Source Independent routing the next hop to the destination does not depend on the source of the packet 0 Source Independent routing helps reduce table size CS 4717 Spring 2002 Jim Gri ioen 18 What if the Topology Changes Figure 10 An Example Network Topology o If each machineswitch records the complete path to every destination then every machineswitch must be changed 0 With nexthop routing don t need to notify entire network CS 4717 Spring 2002 Jim Gri ioen 19 Example Routing Tables o What does the routing table look like on your lap top 0 What does the routing table look like on the cslab machines 0 What does the routing table look like on the sac machine 0 Which of the above machines has the most effi cient routing tables CS 4717 Spring 2002 Jim Gri ioen 2O Building Routing Tables o How to enter information into routing tables Manual entry initialization file Dynamically through runtime interface 0 How to compute routing table information Static routing at boot time Dynamic routing allow automatic updates by a program 0 Static is simpler but doesn t accommodate changes to network topology 0 Dynamic requires additional complex protocols but can work around network failures 0 The above assumes we already know or can dis cover the best routes and then enter them into the tables CS 4717 Spring 2002 Jim Gri ioen 21 Routing Decisions 0 Who decides the route and When is the routing decision made 0 Three popular approaches Source Routing as route defined by the source of the packet as route defined when the packet is sent Virtual Circuits as route defined by the switches in the net work as route defined when the circuit is first estab Hshed as only the connection packet must worry about finding a route Datagram Routing as route defined by the switches in the net work as route defined on the fly for each packet as every switch involved in the routing deci sion for every packet CS 4717 Spring 2002 Jim Gri ioen 22 Source Routing o sending host must know the complete route from the sender to the receiver 0 sender puts the list of hops in the header of the packet 0 intermediate switches read the nexthop from the packet and forward the packet to the nexthop 0 this puts all the work or routing on the senders o switches are dumb don t need to know anything about routes CS 4717 Spring 2002 Jim Gri ioen 23 Source Routing continued 0 Three methods for placing the source route in the header 1 Stripping strip the next hop from the packet before forwarding no routing information left when it gets to the destination 2 Rotation read the next hop then shift all hops one forward and place the next hop just read at the tail of the list the packet received will be the same as the packet sent 3 Pointer add a pointer field to the beginning of the packet the pointer should always point at the next hop before forwarding the packet adjust the next hop pointer less copying than the rotation method CS 4717 Spring 2002 Jim Gri ioen 24 Source Routing Example Stripping Rotation Pointer s s s i i i WBicW NBCR HPWBWW V V U v A A i i wlt lt wlt 0 6 lt olt we xlt we Figure 11 Source Routing Implementations CS 4717 Spring 2002 Jim Gri ioen Virtual Circuits 0 Each switch remembers all circuits connections that currently pass through the switch 0 A circuit must be established between two ma chines before any data can be sent between the two machines 0 The circuit must be torndown after the data is sent 0 All data sent between the sender and receiver travels the same route 0 Packets are sent to addressed to a circuit con nection ID 0 Routing Tables have the following format Input Port Circuit ID Output Port o or if the VCI can change from switch to switch like ATM Input Port Circuit ID Output Port CircuitlD CS 4717 Spring 2002 Jim Gri ioen 26 Virtual Circuits Example Figure 12 Three Virtual Circuits Switch 1 s VC Table nput utput CS 4717 Spring 2002 Jim Gri ioen 27 Datagram Routing o A Datagram is an independently routed packet o Sender can send data without establishing a con nection 0 Every datagram carries the destination address in the header 0 Each switch makes a routing decision on the fly ie each packet is routed independently 0 Two packets sent from A to B need not travel the same route CS 4717 Spring 2002 Jim Gri ioen 28 Routing Model Comparison Source Routing Virtual Circuits Datagram Routing Each pkt has Each pkt has Each pkt has then snd data all hops VCI identifier destination addr Pkt routed All pkts routed Each pkt routed at source the same independently Can send data 1 RTT to set Can send data immediately up connection immediately Know there is Know there is Don t know there reestablish a path a path is a path Don t know rcv Know receiver Don t know rcv is up is up is up Header is long Hdr is short Hdr is medium Link failure Link Failures Link Failure causes pkts to cause circuit can be routed be lost to fail must around CS 4717 Spring 2002 Jim Gri ioen Static Routing 0 Routing table constructed manually or from a file at boot time 0 Not good if the network topology changes fre quen y new network links may be added other network links may fail new host added and others removed 0 Cannot change a route based on link loads 0 Most frequently used on hosts on a LAN with just one default route CS 4717 Spring 2002 Jim Gri ioen 30 Dynamic Routing 0 want to create routing tables automatically 0 want to react to topology changes 0 want to be able to choose best route based on dynamic characteristics like link loads link error rates 0 two popular approaches 1 Distance Vector Routing 2 Link State Routing CS 4717 Spring 2002 Jim Gri ioen 31 Distance Vector Routing 0 Why the name Distance Vector Distance distancecost to the destination Vector the direction vector to go to get to the destination 0 Basic Idea Each switch remembers the shortest known route next hop to every possible destination If a switch learns of a shorter route replace the old information with the new Periodically tell your neighbors the routes you know about CS 4717 Spring 2002 Jim Gri ioen 32 Distance Vector Routing Tables 0 Each host maintains a routing table of the form Destination Cost Next Hop 0 Initially each switch starts off with a incomplete routing table filled with information about directly connected neighbors o The distancecost to unknown nodes starts as oo 0 Consider the following network Figure 13 Example network 0 The routing Table at A starts out as CS 4717 Spring 2002 Jim Gri ioen 33 Distance Vector Example Figure 14 Example network 0 Initially each node only knows directly connected neighbors 0 Each node then sends its table to its neighbors 0 When the neighbor receives a routing table it updates its routes to use the best know routes CS 4717 Spring 2002 Jim Gri ioen 34 Distance Vector Example continued Figure 15 Example network 0 Initial routing tables each row a table 0 After the first exchange of update messages A B D E A B E o How long will it take before all nodes know all routes CS 4717 Spring 2002 Jim Gri ioen 35 In two more iterations of the algorithm A s mes sage needs to go to C and then D CS 4717 Spring 2002 Jim Gri ioen 36 Remaining Problems o How often should a node send updates periodically when triggered o What if a route becomes longer Or a link Fails What if the link between B and E goes down Must replace routes if the neighbor tells you a higher value later on 0 Will packets get where they are going at all times No Takes the algorithm some amount of time to stablize There is no globally consistent state where routes are guaranteed to work Only guaranteed that if links stay stable algo rithm will converge assuming no loops 0 What about graphs with loops Can get routing loops show simple twonode loop A BxC Need splithorizon poison reverse countto infinity limits CS 471 Spring 2002 Jim Gri ioen 37 Algorithm Outline a Wait for next update message Iterate through entries in message c If entry has shorter path to destination 0quot 1 Insert source as next hop to destination Record distance as distance from next hop to destination PLUS distance from this switch to next hop 3 trigger an update with the new information CS 4717 Spring 2002 Jim Gri ioen 38 Link State Routing o Is a 2 part algorithm 1 Tell everyone the entire topology and keep telling them the entire topology 2 Determine the best routes knowing the entire topology 0 Note that DV routing has no idea what the topol ogy looks like CS 4717 Spring 2002 Jim Gri ioen 39 Determining The Topology 0 Each machine finds out who its directly connected neighbors are How 0 Broadcast a packet that tells who your neighbors are 1 send your packet out on all links 2 if you receive a linkstate packet LSP for ward it on all links except the incoming link unless you have seen this LSP before 0 Eventually all nodes will know who is connected to who CS 4717 Spring 2002 Jim Gri ioen 4O Determining the Best Route 0 We know the entire topology from the linkstate messages 0 Can apply any graph algorithm to find the short est path from any source to any destination o Typically use Djikstra s Shortest Path Algorithm SPF Basic Idea as two sets of nodes 1 known shortest paths 2 unknown shortest paths as always add the next node from 2 with the smallest link cost as then recomputer shortest paths for all nodes in the set CS 4717 Spring 2002 Jim Gri ioen 41 DV VS LS Distance Vector Routing Link State Routing Send packets only to neighbors Send by fboding to everyone May trigger other xmissions Message size depends on the Message size depends on the number of hosts in the network number of neighbors Thus msg size does not scale Thus msg does scale well Depends on intermediate nodes Does not depend on routes computing routes correctly calculated by other machines Routing msgs change as they Link status msgs propagate across the net propagate unchanged Loops can arise that must be Since each node computes handled routes independently loops are not a problem May take a while to stablize Stabalizes quickly after a after a link goes down link goes down CS 4717 Spring 2002 Jim Gri ioen 42 Chapter 5 Local PointtoPoint Communication Translating Energy to Bits 0 Recall that data transmission requires Encoding bits as energy Transmitting energy through medium Decoding energy back into bits 0 Need to decide how to encode 1 and 0 bits as energy 0 Transmitter and receiver must agree on encoding scheme CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen Basic Idea 0 change the voltage over time to encode the desired bits 0 use one voltage to represent 1 another to represent 0 0 maybe use a third voltage to represent no data Voltage 1 1 1 Time Figure 1 Example Waveform CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen Missing Details o How many voltages will we use 0 What should the voltage settings be 0 How long does the voltage need to stay at a level 0 How do we encode bits with voltages o How do we know when a bit begins 0 So how do we begin answering these questions CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen Baud Rate 0 One way to define the speed of a line is to measure its Baud rate 0 The Baud rate ofa line defines the maximum number of signal changes that can occur per second 0 The Baud rate is typically measured as cycles per second or Hertz Figure 2 Baud Rate Illustration CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 4 Baud Rate VS Bit Rate 0 Another measure of a line s speed is its Bit Rate 0 Bit Rate measure the number of data bits the line can transmit per second measured in bits per second bps o The Bit Rate depends on o HOWEVER Voltage Time Figure 3 Example CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 5 Asynchronous Communication 0 Two problems regarding synchronization of the senderreceiver 0 an Asynchronous Line allows the sender to transmit data only when it has data to send CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 6 Timing Synchronization 0 So the sender and receiver must agree on the timing of each voltage duration Baud Rate 0 Then the sender and receiver must agree on an encoding scheme 0 The encoding scheme can also help CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 7 Need Standards 0 so senderreceiver agree 0 so different vendor s equipment can interoperate 0 example standards organizations International Telecommunications Union ITU Electronic Industries Association EIA Institute for Electrical and Electronics Engineers IEEE o We will look at a standard call RS 232 C CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen RS 232C o RS 232 is an EIA standard to send ASCI characters bytes across copper Wire 0 RS 232 is 7 Local 7 Serial 7 Asynchronous o RS 232 uses a 25pin connector most pins not used Fxgme 4 R5232 D325 wnneccoz cs we prmg 20047 rmmcwz my Mumm Nam hm Gn oen a Full Half Duplex Lines o A Full Duplex line 0 A Half Duplex line 0 RS 232 uses full duplex communication one line for each direction 0 RS 232 only uses 5 of the 25 pins Pin 2 Receive RxD Pin 3 Transmit TxD Pin 4 Ready to send RTS Pin 5 Clear to send CTS Pin 7 Ground CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 10 23 Swap o RS 232 requires a 2 3 Swap to exchange the 2nd and 3rd wire so that the send line is connected to the receive ine o However a version of RS 232 used to connect computers to periph erals such as modems avoids the 2 3 swap 0 Modems xmit on 2 rcv on 3 CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 11 Encoding and Synchronization in RS 232 o Voltages 15v 0 15V 1 15v idle o The sender indiciates the start of next character by transmitting a zero bit called the start bit The receiver uses the start bit to synchronize and start receiving the character 0 When done the sender cannot immediately begin sending the next character There must be an idle cycle so that the start bit of the next char acter will be detected by the receiver So the sender transmits a one bit called the stop bit after each character 0 The start and stop bits are called framing bits o RS 232 allows both 7 and 8 bit ASCII characters to be tranmitted requiring 9 and 10 bits respectively CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 12 idle start1 0 1 1 0 1 0 stopi idle Voltage idlestart1 0 0 1 1 0 0 stopi idle CS 471G7 Spring 2004 Instructor Billy Mullins Notes Jim Gri ioen 13 RS 2 32 cable breakout box May need to test RS232 connections Breakoutbox gives access to signals cs ma spungzom 7 1mm Bulky mum my Jim Grimm m Limitations of Real Hardware 0 Effects of wire mean waveforms look like the picture below 0 May become worse with 1 longer wires 2 interference 0 Standards specify how tolerant the receiver must be of imprecise wave forms CS 471G Spring 2004 e Instructor Billy Mullins 7 Notes Jim Gri ioen 15