Switching and Forwarding

Switching and Forwarding
Dr.GriffinWood Profile Pic
Dr.GriffinWood,United Kingdom,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Comment
' COMPUTER NETWORKS CS 45201 CS 55201 CHAPTER 3 Switching and Forwarding H. Peyravi Department of Computer Science Kent State University Kent, Ohio 44242 peyravimcs.kent.edu http://mars.mcs.kent.edu/peyravi Fall 2001 & % CS 4/55201: Computer Networks Fall 2001' Contents  Switching and Forwarding  Routing  Bridges and LAN switches  Asynchronous Transfer Mode (ATM)  Switching Hardware  A Brief Summary of INs & % CS 4/55201: Computer Networks Fall 2001Chapter 3: Switching and Forwarding Switching and Forwarding ' Switching and Forwarding Scalable Networks  Switch: Forwards packets from input port to output port; port selected based on destination address in packet header. T3 T3 T3 Switch T3 STS−1 STS−1 Input Output Ports Ports  Can build networks that cover large geographic area  Can build networks that support large numbers of hosts  Can add new hosts without a ecting performance of existing hosts & % CS 4/55201: Computer Networks Fall 2001 1 of 52Chapter 3: Switching and Forwarding Switching and Forwarding ' Routing Techniques Elements  Performance criterion =) Number of hops =) Distance =) Speed =) Delay =) Cost  Decision time =) Packet Session  Decision place =) Distributed =) Centralized =) Source  Information sources =) None =) Local =) Adjacent nodes =) Nodes along route =) All nodes  Routing strategy =) Fixed =) Adaptive =) Random =) Flooding  Adaptive routing update time =) Continuous =) Periodic =) When topology changes =) Major load changes & % CS 4/55201: Computer Networks Fall 2001 2 of 52Chapter 3: Switching and Forwarding Switching and Forwarding ' Source Routing  Address contains a sequence of ports on path from source to destination. 0 Switch 1 0 3 1 3 1 Switch 2 2 2 3 1 2 1 3 0 3 0 1 0 Host A 0 1 3 Switch 3 0 1 3 Host B 2 & % CS 4/55201: Computer Networks Fall 2001 3 of 52Chapter 3: Switching and Forwarding Switching and Forwarding ' Virtual Circuit Switching  Explicit connection setup (and tear-down) phase  Subsequent packets follow same circuit  Analogy: phone call  Sometimes called connection-oriented model  Each switch maintains a VC table. 0 Switch 1 3 1 Switch 2 2 2 3 1 5 11 0 Host A 7 Switch 3 0 1 3 4 Host B 2 & % CS 4/55201: Computer Networks Fall 2001 4 of 52Chapter 3: Switching and Forwarding Switching and Forwarding ' Datagrams  No connection setup phase  Each packet forwarded independently  Analogy: postal system  Sometimes called connectionless model  Each switch maintains a forwarding (routing) table Host D Host E 0 Switch 1 Host F 3 1 Switch 2 2 Host C 2 3 1 0 Host A Switch 3 0 Host G Host B 1 3 2 Host H & % CS 4/55201: Computer Networks Fall 2001 5 of 52Chapter 3: Switching and Forwarding Switching and Forwarding ' Virtual Circuit vs. Datagram  Virtual Circuit Model: I Typically wait full RTT for connection setup before sending rst data packet. I While the connection request contains the full address for destination, each data packet contains only a small identi er, making the per-packet header overhead small. I If a switch or a link in a connection fails, the connection is broken and a new one needs to be established. I Connection setup provides an opportunity to reserve resources.  Datagram Model: I There is no round trip time delay waiting for connection setup; a host can send data as soon as it is ready. I Source host has no way of knowing if the network is capable of delivering a packet or if the destination host is even up. I Since packets are treated independently, it is possible to route around link and node failures. I Since every packet must carry the full address of the destination, the overhead per packet is higher than for the connection-oriented model. & % CS 4/55201: Computer Networks Fall 2001 6 of 52Chapter 3: Switching and Forwarding Switching and Forwarding ' Performance  Switches can be built from a general-purpose workstations; will consider special-purpose hardware later. I/O Bus CPU Interface 1 Interface 2 Interface 3 Main Memory  Aggregate bandwidth I 1/2 of the I/O bus bandwidth I capacity is shared among all hosts connected to switch I Example: 800Mbps bus can support 8 T3 ports  Packets-per-second I Must be able to switch small packets I 100,000 packets-per-second is an achievable number I Example: 64-byte packets implies 51.2Mbps & % CS 4/55201: Computer Networks Fall 2001 7 of 52Chapter 3: Switching and Forwarding Routing ' Routing  Forwarding versus Routing I forwarding: selects an output port based on destination address and routing table I routing: process by which routing table is built  Network as a Graph A 6 1 3 F 2 1 E B 4 1 9 D C  Problem: Find the lowest cost path between any two nodes  Factors: I Static: topology I Dynamic: load & % CS 4/55201: Computer Networks Fall 2001 8 of 52Chapter 3: Switching and Forwarding Routing '  Interior Gateway Protocols (IGP)  used for Intra-domain routing e.g. between routers within Kent campus  Two major approaches I Diatance Vector: Each router sends a vector of distances to its neighbors. The vector contains distances to all nodes in the network I Example: RIP (Routing Information Protocol) I Link State: Each router sends a vector of distances to all nodes. The vector contains only distances to neighbors =) newer method used in Internet I Example: OSPF (Open Shortest Path First)  We will discuss RIP and OSPF later in Chapter 4 together with inter-domain routing using BGP & % CS 4/55201: Computer Networks Fall 2001 9 of 52Chapter 3: Switching and Forwarding Routing ' Distance Vector  Each node maintains a set of triples: (Destination, Cost, NextHop)  Each node sends updates to (and receives updates from) its directly connected neightbors I periodically (on the order of several seconds) I whenever its table changes (called triggered update)  Each update is a list of pairs: (Destination, Cost)  Update local table if receive a \better" route I smaller cost I came from next-hop  Refresh existing routes; delete if they time out  How do you tell a node is down? I send test packet e.g. ping I don't see periodic update & % CS 4/55201: Computer Networks Fall 2001 10 of 52Chapter 3: Switching and Forwarding Routing ' Example B C A D E F G  Routing table at node B Destination Cost NextHop A 1 A C 1 C D 2 C E 2 A F 2 A G 3 A & % CS 4/55201: Computer Networks Fall 2001 11 of 52Chapter 3: Switching and Forwarding Routing ' Routing Loops  Example 1 I F detects that link to G has failed I F sets distance to G to in nity and sends update to A I A sets distance to G to in nity since it uses F to reach G I A receives periodic update from C with 2-hop path to G I A sets distance to G to 3 and sends update to F I F decides it can reach G in 4 hops via A  Example 2 I Link from A to E fails I A advertises distance of in nity to E I B and C advertise a distance of 2 to E I B decides it can reach E in 3 hops; advertises this to A I A decides it can reach E in 4 hops; advertises this to C I C decides that it can reach E in 5 hops......  Heuristics to break routing loops I set in nity to 16 I split horizon - don't send back to origin i.e. don't send (E,2) I split horizon with poison reverse - send (E,1) I only works for 2 node loops & % CS 4/55201: Computer Networks Fall 2001 12 of 52Chapter 3: Switching and Forwarding Routing ' Link State  Strategy: Send to all nodes (not just neighbors) information about directly connected links (not entire routing table).  Link State Packet (LSP) I id of the node that created the LSP I cost of link to each directly connected neighbor I sequence number (SEQNO) I time-to-live (TTL) for this packet  Reliable Flooding I store most recent LSP from each node I forward LSP to all nodes but one that sent it I generate new LSP periodically (hours) or on topology change; increment SEQNO I start SEQNO at 0 when reboot I decrement TTL of each stored LSP before ooding and also by \ageing"; re ood and discard when TTL=0 & % CS 4/55201: Computer Networks Fall 2001 13 of 52Chapter 3: Switching and Forwarding Routing ' Route Calculation (in theory)  Dijkstra's shortest path algorithm  N denotes set of nodes in the graph  l(i; j) denotes non-negative cost (weight) for edge (i; j)  s2 N denotes this node  M denotes the set of nodes incorporated so far  C(n) denotes cost of the path from s to node n M =fsg for each n in Nfsg C(n) = l(s; n) while (N = 6 M) M = M unionfwg such that C(w) is the minimum for all w in (N M) for each n in (N M) C(n) = MIN(C(n); C(w) + l(w; n)) & % CS 4/55201: Computer Networks Fall 2001 14 of 52Chapter 3: Switching and Forwarding Routing ' Route Calculation (in practice)  Forward search algorithm  Each switch maintains two lists: Tentative and Confirmed  Each list contains a set of triples: (Destination, Cost, NextHop) B 3 5 10 C A 11 2 D 1. Initialized Confirmed with entry for me; cost = 0. 2. For the node just added to Confirmed (call it Next) select its LSP. 3. For each Neighbor of Next, calculate the Cost to reach this Neighbor as the sum of the cost from me to Next and from Next to Neighbor. & % CS 4/55201: Computer Networks Fall 2001 15 of 52Chapter 3: Switching and Forwarding Routing ' 3.1. If Neighbor is currently in neither Confirmed or Tentative, add (Neighbor, Cost, NextHop) to Tentative, where NextHop is the direction to reach Next. 3.2. If Neighbor is currently in Tentative and Cost is less that current cost for Neighbor, then replace current entry with (Neighbor, Cost, NextHop), where NextHop is the direction to reach Next. 4. If Tentative is empty, stop. Otherwise, pick entry from Tentative with the lowest cost, move it to Confirmed, and return to step 2. & % CS 4/55201: Computer Networks Fall 2001 16 of 52Chapter 3: Switching and Forwarding Routing ' Step Confirmed Tentative 1. (D,0,-) 2. (D,0,-) (B,11,B) (C,2,C) 3. (D,0,-) (B,11,B) (C,2,C) 4. (D,0,-) (B,5,C) (C,2,C) (A,12,C) 5. (D,0,-) (A,12,C) (C,2,C) (B,5,C) 6. (D,0,-) (A,10,C) (C,2,C) (B,5,C) 7. (D,0,-) (C,2,C) (B,5,C) (A,10,C) & % CS 4/55201: Computer Networks Fall 2001 17 of 52Chapter 3: Switching and Forwarding Routing ' Metrics  Original ARPANET metric I measured number of packets enqueued on each link I took neither latency or bandwidth into consideration  New ARPANET metric I stamp each incoming packet with its arrival time (AT) I record departure time (DT) I when link-level ACK arrives, compute Delay = (DT - AT) + Transmit + Latency I if timeout, reset DT to departure time for retransmission I link cost = average delay over some time period  Problems with \New" metric I under low load, static factors dominated cost; worked OK I under high load, congested links had very hight costs; packets oscillated between congested and idle links I range of costs too large; prefered path of 126 lightly loaded 56Kbps links to a 1-hop 9.6Kbps path  Revised ARPANET metric I replaced delay measurement with link utilization I average to surpress sudden changes  compressed dynamic range (see Fig 4.21) & % CS 4/55201: Computer Networks Fall 2001 18 of 52

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.