Question? Leave a message!




Review of Networking and Design Concepts

Review of Networking and Design Concepts 31
Review of Networking and Design Concepts (I) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 1Overview  Connectivity:  direct (ptpt, Nusers),  indirect (switched, internetworked)  Concepts: Topologies, Framing, Multiplexing, Flow/Error Control, Reliability, Multipleaccess, Circuit/Packet switching, Addressing/routing, Congestion control  Data link/MAC layer:  SLIP, PPP, LAN technologies …  Interconnection Devices  Chapter 1,2,11 in Doug Comer book  Reading: Saltzer, Reed, Clark: "EndtoEnd arguments in System Design"  Reading: Clark: "The Design Philosophy of the DARPA Internet Protocols": Shivkumar Kalyanaraman Rensselaer Polytechnic Institute  Reading: RFC 2775: Internet Transparency: In HTML 2Connectivity...  Building Blocks links: coax cable, optical fiber... nodes: generalpurpose workstations...  Direct connectivity: pointtopoint multiple access Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 3Connectivity… (Continued)  Indirect Connectivity switched networks = switches internetworks = routers Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 4What is “Connectivity”  Direct or indirect access to every other node in the network  Connectivity is the magic needed to communicate if you do not have a link. Tradeoff: Performance characteristics worse Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 5Connectivity …  Internet: Besteffort (no performance guarantees) Packetbypacket  A ptpt link: Alwaysconnected Fixed bandwidth Fixed delay Zerojitter Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 6PointtoPoint Connectivity Issues A B  Physical layer: coding, modulation etc  Link layer needed if the link is shared bet’n apps; is unreliable; and is used sporadically  No need for protocol concepts like addressing, names, routers, hubs, forwarding, filtering … Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 7Link Layer: Serial IP (SLIP)  Simple: only framing = Flags + bytestuffing  Compressed headers (CSLIP) for efficiency on low speed links for interactive traffic.  Problems:  Need other end’s IP address a priori (can’t dynamically assign IP addresses)  No “type” field = no multiprotocol encapsulation  No checksum = all errors detected/corrected by higher layer.  RFCs: 1055, 1144 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 8Link Layer: PPP  Pointtopoint protocol  Frame format similar to HDLC  Multiprotocol encapsulation, CRC, dynamic address allocation possible key fields: flags, protocol, CRC  Asynchronous and synchronous communications possible Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 9Link Layer: PPP (Continued)  Link and Network Control Protocols (LCP, NCP) for flexible control peerpeer negotiation  Can be mapped onto low speed (9.6Kbps) and high speed channels (SONET)  RFCs: 1548, 1332 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 10Reliability Mechanisms  Mechanisms:  Checksum: detects corruption in pkts acks  ACK: “packet correctly received”  Duplicate ACK: “packet incorrectly received”  Sequence number: identifies packet or ack 1bit sequence number used both in forward reverse channel  Timeout only at sender  Reliability capabilities achieved:  An errorfree channel  A forward reverse channel with biterrors  Detects duplicates of packets/acks  NAKs eliminated  A forward reverse channel with packeterrors (loss) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 11Stop and Wait Flow Control t frame U= 2t +t prop frame t Data frame 1 = t prop 2 + 1 U Ack Data  Light in vacuum Ack = 300 m/s Light in fiber t Distance/Speed of Signal prop  = = = 200 m/s Frame size /Bit rate t frame Electricity Distance  Bit rate = 250 m/s = Frame size Speed of Signal Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 12Sliding Window Protocols Nt frame U= 2t +t prop frame t frame Data N t prop 2+1 = 1 if N2+1 Ack Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 13List of Issues  Connectivity (direct/indirect)  PtPt connectivity: Framing Error control/Reliability (optional) Flow control (optional) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 14Connecting N users: Directly… A B  Ptpt: connects only two users directly…  How to connect N users directly . . . Bus Full mesh  What are the costs of each option  Does this method of connectivity scale Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 15Multiplexing vs Have it all  Multiplexing = sharing  Allows system to achieve “economies of scale”  Cost: waiting time (delay), buffer space loss  Gain: Money () = Overall system costs less Full Mesh Bus Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 16Virtualization  The multiplexed shared resource with a level of indirection will seem like a unshared virtual resource  I.e. Multiplexing + indirection = virtualization A B . . . = A B Physical Bus Virtual PtPt Link  We can “refer” to the virtual resource as if it were the physical resource. Eg: virtual memory, virtual circuits…  Connectivity: a virtualization created by the Internet  Indirection requires binding and unbinding… Eg: use of packets, slots, tokens etc Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 17Statistical Multiplexing  Reduce resource requirements (eg: bus capacity) by exploiting statistical knowledge of the system.  Eg: average rate = service rate = peak rate  If service rate average rate, then system becomes unstable First design to ensure system stability  Then, for a stable multiplexed system: Gain = peak rate/service rate. Cost: buffering, queuing delays, losses.  Useful only if peak rate differs significantly from average rate.  Eg: if traffic is smooth, fixed rate, no need to play games with capacity sizing… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 18Stability of a Multiplexed System Average Input Rate Average Output Rate = system is unstable How to ensure stability 1. Reserve enough capacity so that demand is less than reserved capacity 2. Dynamically detect overload and adapt either the demand or capacity to resolve overload Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 19What’s a performance tradeoff • A situation where you cannot get something for nothing • Also known as a zerosum game.  R=link bandwidth (bps)  L=packet length (bits)  a=average packet arrival rate Traffic intensity = La/R Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 20What’s a performance tradeoff  La/R 0: average queuing delay small  La/R 1: delays become large  La/R 1: average delay infinite (service degrades unboundedly = instability) Summary: Multiplexing using bus topologies has both direct resource costs and intangible costs like potential instability, buffer/queuing delay. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 21Connecting N users: Directly ...  Bus: Low cost vs broadcast/collisions, MAC complexity  Full mesh: High cost vs simplicity  New concept:  Address to identify nodes.  Needed if we want the receiver alone to consume the packet . . . Bus Full mesh  Problem: Direct connectivity does not “scale”…. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 22How to build Scalable Networks  Scaling: system allows the increase of a key parameter. Eg: let N increase… Inefficiency limits scaling …  Direct connectivity is inefficient hence does not scale Mesh: inefficient in terms of of links Bus architecture: 1 expensive link, N cheap links. Inefficient in bandwidth use Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 23Filtering, forwarding …  Filtering: choose a subset of elements from a set  Don’t let information go where its not supposed to…  Filtering = More efficient = more scalable Filtering is the key to efficiency scaling  Forwarding: actually sending packets to a filtered subset of link/node(s)  Packet sent to one link/node = efficient  Solution: Build nodes which focus on filtering/forwarding and achieve indirect connectivity “switches” “routers” Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 24Connecting N users: Indirectly  Star: Onehop path to any node, reliability, forwarding function  “Switch” S can filter and forward Switch may forward multiple pkts in parallel for additional efficiency Star Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 25 SConnecting N users: Indirectly …  Ring: Reliability to link failure, nearminimal links  All nodes need “forwarding” and “filtering”  Sophistication of forward/filter lesser than switch Ring Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 26Topologies: Indirect Connectivity Ring Star Tree Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 27 SMultiAccess LANs  Hybrid topologies:  Uses directly connected topologies (eg: bus), or  Indirectly connected with simple filtering components (switches, hubs). Limited scalability due to limited filtering  Medium Access Protocols:  ALOHA, CSMA/CD (Ethernet), Token Ring …  Key: Use a single protocol in network  Concepts: address, forwarding (and forwarding table), bridge, switch, hub, token, medium access control (MAC) protocols Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 28MAC Protocols: a taxonomy Three broad classes:  Channel Partitioning divide channel into smaller “pieces” (time slots, frequency) allocate piece to node for exclusive use  Random Access allow collisions “recover” from collisions  “Taking turns”: Tokenbased tightly coordinate shared access to avoid collisions Goal: efficient, fair, simple, decentralized Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 29Channel Partitioning MAC protocols. Eg: TDMA TDMA: time division multiple access  Access to channel in "rounds"  Each station gets fixed length slot (length = pkt trans time) in each round  Unused slots go idle  Example: 6station LAN, 1,3,4 have pkt, slots 2,5,6 idle Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 30Review: Multiple Access Protocols  Aloha at University of Hawaii: Transmit whenever you like Worst case utilization = 1/(2e) =18  CSMA: Carrier Sense Multiple Access Listen before you transmit  CSMA/CD: CSMA with Collision Detection Listen while transmitting. Stop if you hear someone else.  Ethernet uses CSMA/CD. Standardized by IEEE 802.3 committee. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 3110Base5 Ethernet Cabling Rules  Thick coax  Length of the cable is limited to 2.5 km, no more than 4 repeaters between stations  No more than 500 m per segment  “10Base5” Terminator Repeater 2.5m Transceiver 500 m Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 3210Base5 Cabling Rules (Continued)  No more than 2.5 m between stations  Transceiver cable limited to 50 m Terminator Repeater 2.5m Transceiver 500 m Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 33Interconnection Devices  Repeater: Layer 1 (PHY) device that restores data and collision signals: a digital amplifier  Hub: Multiport repeater + fault detection  Note: broadcast at layer 1  Bridge: Layer 2 (Data link) device connecting two or more collision domains.  Key: a bridge attempts to filter packets and forward them from one collision domain to the other.  It snoops on passing packets and learns the interface where different hosts are situated, and builds a L2 forwarding table  MAC multicasts propagated throughout “extended LAN.”  Note: Limited filtering intelligence and forwarding capabilities at layer 2 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 34Interconnection Devices (Continued)  Router: Network layer device. IP, IPX, AppleTalk. Interconnects broadcast domains.  Does not propagate MAC multicasts.  Switch:  Key: has a switch fabric that allows parallel forwarding paths  Layer 2 switch: Multiport bridge w/ fabric  Layer 3 switch: Router w/ fabric and perport ASICs These are functions. Packaging varies. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 35Interconnection Devices Extended LAN =Broadcast LAN= domain B H H H H Collision Router Domain Application Application Gateway Transport Transport Network Network Router Datalink Datalink Bridge/Switch Physical Physical Repeater/Hub Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 36Ethernet (IEEE 802) Address Format (Organizationally Unique ID) OUI 10111101 G/I bit G/L bit (Group/Individual) (Global/Local)  48bit flat address = no hierarchy to help forwarding  Hierarchy only for administrative/allocation purposes  Assumes that all destinations are (logically) directly connected.  Address structure does not explicitly acknowledge indirect connectivity = Sophisticated filtering cannot be done Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 37Ethernet (IEEE 802) Address Format (Organizationally Unique ID) OUI 10111101 G/I bit G/L bit (Group/Individual) (Global/Local)  G/L bit: administrative  Global: unique worldwide; assigned by IEEE  Local: Software assigned  G/I: bit: multicast  I: unicast address  G: multicast address. Eg: “To all bridges on this LAN” Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 38Ethernet 802.3 Frame Format IP IPX AppleTalk  Ethernet Dest. Source Size in Type Info CRC Address Address bytes 4 6 6 2 IP IPX AppleTalk  IEEE 802.3 Dest. Source Length LLC Info Pad CRC Address Address 6 6 2 Length 4 • Maximum Transmission Unit (MTU) = 1518 bytes • Minimum = 64 bytes (due to CSMA/CD issues) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 39“Taking Turns” MAC protocols 1 Channel partitioning MAC protocols: share channel efficiently at high load inefficient at low load: delay in channel access, 1/N bandwidth allocated even if only 1 active node Random access MAC protocols efficient at low load: single node can fully utilize channel high load: collision overhead “Taking turns” protocols look for best of both worlds Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 40“Taking Turns” MAC protocols 2 Polling: Token passing:  Master node “invites”  Control token passed from one slave nodes to transmit node to next sequentially. in turn  Token message  Request to Send, Clear  Concerns: to Send messages  Concerns: token overhead polling overhead latency latency single point of failure single point of (token) failure (master) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 41“Taking Turns” Protocols –3 Reservationbased a.k.a Distributed Polling:  Time divided into slots  Begins with N short reservation slots  reservation slot time equal to channel endend propagation delay  station with message to send posts reservation  reservation seen by all stations  After reservation slots, message transmissions ordered by known priority Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 42Additions to List of Issues  Filtering techniques: Learning, routing  Multiple access How to share a wire Partitioning, Random Access, Taking Turns  Switching, bridging, routing  Addressing, Packet Formats Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 43InterNetworks: Networks of Networks …… = Internet …… Our goal is to design this black box on the right Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 44InterNetworks: Networks of Networks  What is it “Connect many disparate physical networks and make them function as a coordinated unit … ” Douglas Comer Many = scale Disparate = heterogeneity  Result: Universal connectivity The internetwork looks like one large switch, User interface is subnetwork independent Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 45InterNetworks: Networks of Networks  Internetworking involves two fundamental problems: heterogeneity and scale  Concepts:  Translation, overlays, address name resolution, fragmentation: to handle heterogeneity  Hierarchical addressing, routing, naming, address allocation, congestion control: to handle scaling  Two broad approaches: circuitswitched and packet switched Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 46How to design large internetworks CircuitSwitching  Divide link bandwidth into “pieces”  Reserve pieces on successive links and tie them together to form a “circuit”  Map traffic into the reserved circuits  Resources wasted if unused: expensive. – Mapping can be done without “headers”. – Everything inferred from timing. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 47How to design large internetworks PacketSwitching Chop up data (not links) into“packets” Bandwidth division into “pieces” Dedicated allocation Packets: data + meta Resource reservation data (header) “Switch” packets at intermediate nodes  Storeandforward if bandwidth is not immediately available. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 48Packet Switching 10 Mbs statistical multiplexing C Ethernet A 1.5 Mbs B queue of packets 45 Mbs waiting for output link D E  Cost: selfdescriptive header perpacket, buffering and delays due to statistical multiplexing at switches.  Need to either reserve resources or dynamically detect and adapt to overload for stability Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 49Spatial vs Temporal Multiplexing  Spatial multiplexing: Chop up resource into chunks. Eg: bandwidth, cake, circuits…  Temporal multiplexing: resource is shared over time, I.e. queue up jobs and provide access to resource over time. Eg: FIFO queueing, packet switching  Packet switching is designed to exploit both spatial temporal multiplexing gains, provided performance tradeoffs are acceptable to applications.  Packet switching is potentially more efficient = potentially more scalable than circuit switching Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 50Scalable Forwarding, Structured Addresses  Address has structure which aids the forwarding process.  Address assignment is done such that nodes which can be reached without resorting to L3 forwarding have the same prefix (network ID)  A simple comparison of network ID of destination and current network (broadcast domain) identifies whether the destination is “directly” connected  I.e. Reachable through L2 forwarding only  Within L3 forwarding, further structure can aid hierarchical organization of routing domains (because routing algorithms have other scalability issues) Network ID Host ID Demarcator Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 51Flat vs Structured Addresses  Flat addresses: no structure in them to facilitate scalable routing  Eg: IEEE 802 LAN addresses  Hierarchical addresses:  Network part (prefix) and host part  Helps identify direct or indirectly connected nodes Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 52The Congestion Problem  i  i  •Problem: demand outstrips available capacity  1 Demand Capacity  n  If information about  , and  is known in a i central location where control of  or  can be i effected with zero time delays,  the congestion problem is solved Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 53The Congestion Problem (Continued)  Problems: Incomplete information (eg: loss indications) Distributed solution required Congestion and control/measurement locations different Timevarying, heterogeneous timedelay Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 54Additions to Problem List  Internetworking problems: heterogeneity, scale.  Circuit Switching vs Packet Switching  Heterogeneity:  Overlay model, Translation, Address Resolution, Fragmentation  Scale:  Structured addresses, hierarchical routing  Naming, addressing  Congestion control Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 55Summary: Laundry List of Problems  Basics: Direct/indirect connectivity, topologies  Link layer issues:  Framing, Error control, Flow control  Multiple access Ethernet:  Cabling, Pkt format, Switching, bridging vs routing  Internetworking problems: Naming, addressing, Resolution, fragmentation, congestion control, traffic management, Reliability, Network Management Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 56