Question? Leave a message!




Introduction to Telephony, Cable and Internet Technologies

Introduction to Telephony, Cable and Internet Technologies 2
Introduction to Telephony, Cable and Internet Technologies Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 1Overview  Connectivity:  direct (ptpt, Nusers),  indirect (switched, internetworked)  Telephony, Internet, Cable Networks: Basic Concepts  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  S. Keshav book (Chapter 2), Opt Nets (Sec 11.1, 13.1, 13.2) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 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 what you get instead of a direct physical link Key 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 6Telephony Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 7Telephone Network: What is It  Specialized to carry voice traffic  Aggregates like T1, SONET OCN can also carry data  Also carries  Telemetry, video, fax, modem calls  Internally, uses digital samples  Switches and switch controllers are special purpose computers Pieces: 1. End systems 2. Transmission 3. Switching 4. Signaling Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 8Telephone Network: What is It  Single basic service: twoway voice  low endtoend delay  guarantee that an accepted call will run to completion  Endpoints connected by a circuit, like an electrical circuit  Signals flow both ways (full duplex)  Associated with reserved bandwidth and buffer resources Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 9Telephone Network Design  Fully connected core  simple routing  telephone number is a hint about how to route a call  But not for 800/888/700/900 numbers: these are pointers to a directory that translates them into regular numbers  hierarchically allocated telephone number space Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 10Telephone Network Design Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 11Telephone Pieces: End Systems Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 12Telephone Pieces: End Systems  Transducers: key to carrying voice on wires  Dialer  Ringer  Switchhook Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 13LastMile Transmission Environment  Wire gauges:19, 22, 24, 26 gauge(smaller better)  Diameters: 0.8, 0.6, 0.5, 0.4 mm (larger better)  Various forms of noise: (twisting reduces noise)  Bridgedtap noise: bitenergy diverted to extension phone sockets  Crosstalk  Ham radio  AM broadcast  Insertion loss: 140 dBm noise floor  100 million times more sensitive than normal modems  Bandwidth range = 600 kHz  Notch effects in insertion loss due to bridgedtaps  Transmission PSD = 40dBm = 90 dBm budget Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 142wire vs 4wire: Sidetones and Echoes  Both trans reception circuits need two wires  4 wires from every central office to home  Alternative: Use same pair of wires for both transmission and reception  Signal from transmission flows to receiver: sidetone  Reverse Effect: received signal at endsystem bounces back to CO (esp if delay 20 ms): echo  Solutions: balance circuit (attenuate sidetone) + echo cancellation circuit (cancel echoes). Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 15Dialing  Pulse  sends a pulse per digit  collected by central office (CO)  Interpreted by CO switching system to place call or activate special features (eg: call forwarding, prepaid calls etc)  Tone  key press (feep) sends a pair of tones = digit  also called Dual Tone Multifrequency (DTMF)  CO supplies the power for ringing the bell.  Standardized interface between CO and endsystem = digital handsets, cordless/cellular phones Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 16Telephone Pieces: Transmission Muxing  Trunks between central offices carry hundreds of conversations  Can’t run thick bundles Instead, send many calls on the same wire  Multiplexing (a.ka. Sharing)  Analog multiplexing  Bandlimit call to 3.4 KHz and frequency shift onto higher bandwidth trunk  obsolete  Digital multiplexing  first convert voice to samples  1 sample = 8 bits of voice  8000 samples/sec = call = 64 Kbps Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 17Transmission Multiplexing (contd)  How to choose a sample  256 quantization levels, logarithmically spaced (why)  sample value = amplitude of nearest quantization level  Two choices of levels ( law and A law)  Time division multiplexing  Trunk carries bits at a faster bit rate than inputs  n input streams, each with a 1byte buffer  Output interleaves samples  Need to serve all inputs in the time it takes one sample to arrive = output runs n times faster than input  Overhead bits mark end of frame (why) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 18Transmission Multiplexing  Multiplexed trunks can be multiplexed further  Need a standard (why)  US/Japan standard is called Digital Signaling hierarchy (DS) Digital Signal Number of Number of voice Bandwidth Number previous level circuits circuits DS0 1 64 Kbps DS1 24 24 1.544Mbps DS2 4 96 6.312 Mbps DS3 7 672 44.736 Mbps Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 19Telephone Pieces: Switching Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 20Telephone Pieces: Switching  Problem:  each user can potentially call any other user  can’t have (a billion) direct lines  Switches establish temporary circuits  Switching systems come in two parts: switch and switch controller Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 21Switching System Components Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 22Switch: What does it do  Transfers data from an input to an output  many ports (up to 200,000 simultaneous calls)  need high speeds  Some ways to switch:  1. space division switching: eg: crossbar  if inputs (or crosspoints) are multiplexed, need a schedule (why) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 23Crossbar Switching Elements Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 24Switching (Contd)  Another way to switch time division (time slot interchange or TSI) also needs a service schedule (why)  To build larger switches we combine space and time division switching elements Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 25Telephone pieces: Signaling  A switching system has a switch and a switch controller  Switch controller is in the control plane does not touch voice samples  Manages the network call routing (collect dialstring and forward call) alarms (ring bell at receiver) billing directory lookup (for 800/888 calls) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 26Signaling  Switch controllers are special purpose computers  Linked by their own internal computer network  Common Channel Interoffice Signaling (CCIS) network  Earlier design used inband tones, but was hacked  Also was very rigid (why)  Messages on CCIS conform to Signaling System 7 (SS7) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 27Signaling (contd)  One of the main jobs of switch controller: keep track of state of every endpoint  Key is state transition diagram Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 28Telephony Routing of Signaled Calls  Circuitsetup (I.e. the signaling call) is what is routed.  Voice then follows route, and claims reserved resources.  3level hierarchy, with a fullyconnected core  ATT: 135 core switches with nearly 5 million circuits  LECs may connect to multiple cores Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 29Telephony Routing algorithm  If endpoints are within same CO, directly connect  If call is between COs in same LEC, use onehop path between COs  Otherwise send call to one of the cores  Only major decision is at toll switch  onehop or twohop path to the destination toll switch.  Essence of telephony routing problem: which twohop path to use if onehop path is full (almost a static routing problem… ) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 30Features of telephone routing  Resource reservation aspects:  Resource reservation is coupled with path reservation Connections need resources (same 64kbps) Signaling to reserve resources and the path  Stable load Network built for voice only. Can predict pairwise load throughout the day Can choose optimal routes in advance  Technology and economic aspects:  Extremely reliable switches Why Endsystems (phones) dumb because computation was nonexistent in early 1900s. Downtime is less than a few minutes per year = topology does not change dynamically Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 31Features of telephone routing Source can learn topology and compute route Can assume that a chosen route is available as the signaling proceeds through the network Component reliability drove system reliability and hence acceptance of service by customers  Simplified topology: Very highly connected network Hierarchy + full mesh at each level: simple routing High cost to achieve this degree of connectivity  Organizational aspects:  Single organization controls entire core  Afford the scale economics to build expensive network  Collect global statistics and implement global changes = Sourcebased, signaled, simple alternatepath routing Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 32Telecommunications Regulation History  FCC regulations cover telephony, cable, broadcast TV, wireless etc  “Common Carrier”: provider offers conduit for a fee and does not control the content  Customer controls content/destination of transmission assumes criminal/civil responsibility for content  Local monopolies formed by ATT’s acquisition of th independent telephone companies in early 20 century  Regulation forced because they were deemed natural monopolies (only one player possible in market due to enormous sunk cost)  FCC regulates interstate calls and state commissions regulate intrastate and local calls  Bells + 1000 independents interconnected expanded  FCC rulemaking process:  Intent to act, solicitation of public comment etc… Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 33Deregulation of telephony  1960s70s: gradual deregulation of ATT due to technological advances  Terminal equipment could be owned by customers (CPE) = explosion in PBXs, fax machines, handsets  Modified final judgement (MFJ): breakup of ATT into ILECs (incumbent local exchange carrier) and IXC (interexchange carrier) part  Longdistance opened to competition, only the local part regulated…  Equal access for IXCs to the ILEC network  1+ longdistance number introduced then…  800number portability: switching IXCs = retain 800 number  1995: removed price controls on ATT Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 34Telecom Act of 1996  Required ILECs to open their markets through unbundling of network elements (UNEP), facilities ownership of CLECs….  Today UNEP is one of the most profitable for ATT and other longdistance players in the local market: due to apparently belowcost regulated prices…  ILECs could compete in longdistance after demonstrating opening of markets  Only now some ILECs are aggressively entering long distance markets  CLECs failed due to a variety of reasons…  But longdistance prices have dropped precipitously (ATT’s customer unit revenue in 2002 was 11.3 B compared to 1999 rev of 23B)  ILECs still retain over 90 of local market  Wireless substitution has caused ILECs to develop Shivkumar Kalyanaraman Rensselaer Polytechnic Institute wireless business units 35US Telephone Network Structure (after 1984) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 36Exchange Area Network Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 37Cable TV Networks Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 38Cable Technology  Coaxial cable RF distribution networks.  Attributes:  Broadcast, lowband reverse channels  Mainly oneway video channels  Reasonably secure network (private conduit to home)  Free from freespace interferences  Good signal capacity (over 1 GHz) and flexibility  Multiple signaling channels  Significant attenuation that increases proportional to frequency = (active) RF amplification (every 1000 ft)  Freq responses of deployed amps and filters limit practical usage of frequencies 1 GHz Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 39Cable Building Blocks Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 40Cable Spectrum: Upto 750 Mhz Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 41Cable Technology Architecture  Headend: signal processing center  Each carrier: Baseband analog or digital modulation  Carriers multiplexed w/ freqselective diplex filters: allows simultaneous info transfer in both directions  Treeandbranch architecture:  Wellsuited for oneway broadcast video transmission (same signals to every customer)  Accumulates noise distortions (amplifiers)  Affects plant reliability and received signal quality  Limits on the number of amplifiers cascaded  Limits on bandwidth in operation (few 100s of MHz): below cable potential…  Makes delivery of “switched” services (separate stream Shivkumar Kalyanaraman for each customer) difficult Rensselaer Polytechnic Institute 42TreeandBranch Architecture Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 43Fiber Optics For Cable Networks  Key: Leave the laser ON and intensitymodulate with the analog signal  Such analog modulated lasers are very different from their digital counterparts  Low internal noise and high linearity in the range  Receiver: simple photodetector back to RF spectrum  Result: Hybrid fibercoax infrastructure, with fiber closer to headend  Coax plant serves smaller range (segmentation), but overall HFC reach dramatically increased  Also, it allows the economical support of remote, smaller clusters of homes  Each part could also provide different services to area (micro market segmentation)  Assign different portions of HFC spectrum to diff uses: many virtual networks: sustained investments possible Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 44Hybrid Fiber Coax (HFC) Networks Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 45Multiple Services over HFC Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 46Future Potential of HFC Broadband  Due to smaller loops, the region from 900MHz – 1 GHz can be used for data. Reduced noise in this region = increased bit rate (200 Mbps) per segment…  Future: fiber moves closer, smaller coax segments, reduced homes per coax run (60 homes), use of frequencies above 1 Ghz using new electronics Latest DOCSIS 2.0 spec: 256 QAM (= 8 bits/Hz) or SCDMA on cable for more robust transmissions Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 47Cable Regulation  Very different from telephony: not commoncarrier  Able to control content AND the conduit  Grew by providing an alternative (and extension) to broadcast TV and had initial growth troubles  Did not have to offer service on a nondiscriminatory basis (unlike common carriers)  Asserted firstamendment rights to maintain control over content  Not required to provide access to their distribution system to other providers (some portion of capacity required to be offered to unaffiliated players: eg: CNN)  But they reserve rights to appropriately bundle these channels  Limited regulation: basic tier is rateregulated by local authorities till 1999 based upon FCC rules Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 48Cable regulation (contd)  Cable networks limited in horizontal expansion, and from vertically integrating w/ CNN etc  Note: ILECs like Bell Atlantic in contrast merged with IXCs like GTE  ATT’s cable acquisitions were interesting (and will be explored later…)  Cable service is multifaceted and varied from area to area = regulation formulation more complicated  Overbuilders (satellite providers) got access to independent content providers: otherwise regulation achieved little for cable  Local authorities get revenue from cable regulation  HFC dominates franchise regulation talks, but cable providers are not obligated to provide broadband Shivkumar Kalyanaraman Rensselaer Polytechnic Institute access.. 49Data Networking and the Internet Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 50Recall: Indirect Connectivity…  Indirect Connectivity switched networks = switches internetworks = routers Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 51InterNetworks: Networks of Networks …… = Internet …… The internet is just a big switch providing indirect connectivity Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 52Recall: Connecting 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 53PointtoPoint 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 54Link 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 55Link 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  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) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 56Connecting 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 57How 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 58Filtering, 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 59Connecting 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 60 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 61Topologies: Indirect Connectivity Ring Star Tree Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 62 SProtocol Issues in Data Networks  PtPt connectivity: Framing Error control/Reliability Flow control Windowing protocols  Multiplexing, Virtualization Circuit vs Packet Switching: a muxing view  MAC arbitration schemes: Random access/CSMA, TDMA, CDMA  Interconnection components: repeater, hub, bridge, switch, router Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 63Reliability: Types of errors effects  Forward channel biterrors (garbled packets)  Forward channel packeterrors (lost packets)  Reverse channel biterrors (garbled status reports)  Reverse channel biterrors (lost status reports)  Protocolinduced effects:  Duplicate packets  Duplicate status reports  Outoforder packets  Outoforder status reports  Outofrange packets/status reports (in windowbased transmissions) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 64Temporal Redundancy Model Packets • Sequence Numbers • CRC or Checksum Timeout • ACKs Status Reports • NAKs, • SACKs • Bitmaps Retransmissions • Packets • FEC information Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 65Reliability 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 66Stop 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 67Sliding 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 68Multiplexing: The Method of Sharing Costly Resources  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 69Virtualization  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 70Statistical 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 71Stability 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 72What’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 73What’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 74How 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 75How 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 76Packet 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 77Spatial 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 78Protocol Issues in Data Networks (Contd)  PtPt connectivity: Framing Error control/Reliability Flow control Windowing protocols  Multiplexing, Virtualization Circuit vs Packet Switching: a muxing view  MAC arbitration schemes: Random access/CSMA, TDMA, CDMA  Interconnection components: repeater, hub, bridge, switch, router Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 79MultiAccess 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 80MAC Protocols: a taxonomy Three broad classes:  Channel Partitioning divide channel into smaller “pieces” (time slots, frequency) allocate piece to node for exclusive use  “Taking turns”: Tokenbased tightly coordinate shared access to avoid collisions  Random Access allow collisions “recover” from collisions Goal: efficient, fair, simple, decentralized Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 81Channel 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 82“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 83“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 84“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 85Random 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 8610Base5 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 8710Base5 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 88Interconnection 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 89Interconnection 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 90Interconnection 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 91Ethernet (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 92Ethernet (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 93Ethernet 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 94Network/Transport Layer Issues  Internetworking: heterogeneity, scale  Routing  Congestion control  Quality of Service (QoS) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 95InterNetworks: 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 96InterNetworks: 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 97Scalable 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 98Flat 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 99Internet Routing Drivers  Technology and economic aspects:  Internet built out of cheap, unreliable components as an overlay on top of leased telephone infrastructure for WAN transport. Cheaper components = fail more often = topology changes often = needs dynamic routing  Components (including endsystems) had computation capabilities. Distributed algorithms can be implemented  Cheap overlaid internetworks = several entities could afford to leverage their existing (heterogeneous) LANs and leased lines to build internetworks. Led to multiple administrative “clouds” which needed to interconnect for global communication. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 100Internet Routing Model  2 key features:  Dynamic routing  Intra and InterAS routing, AS = locus of admin control  Internet organized as “autonomous systems” (AS).  AS is internally connected  Interior Gateway Protocols (IGPs) within AS.  Eg: RIP, OSPF, HELLO  Exterior Gateway Protocols (EGPs) for AS to AS routing.  Eg: EGP, BGP4 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 101IntraAS and InterAS routing C.b Gateways: B.a •perform interAS A.a routing amongst A.c b c themselves a a C •perform intraAS b a B routers with other d routers in their AS c b A network layer interAS, link layer intraAS physical layer routing in gateway A.c Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 102IntraAS and InterAS routing: Example InterAS routing C.b between B.a A and B A.a Host b h2 c A.c a a C b a B Host d IntraAS routing c h1 b A within AS B IntraAS routing within AS A Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 103Requirements for IntraAS Routing  Should scale for the size of an AS.  Low end: 10s of routers (small enterprise)  High end: 1000s of routers (large ISP)  Different requirements on routing convergence after topology changes  Low end: can tolerate some connectivity disruptions  High end: fast convergence essential to business (making money on transport)  Operational/Admin/Management (OAM) Complexity  Low end: simple, selfconfiguring  High end: Selfconfiguring, but operator hooks for control  Traffic engineering capabilities: high end only Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 104Requirements for InterAS Routing  Should scale for the size of the global Internet.  Focus on reachability, not optimality  Use address aggregation techniques to minimize core routing table sizes and associated control traffic  At the same time, it should allow flexibility in topological structure (eg: don’t restrict to trees etc)  Allow policybased routing between autonomous systems  Policy refers to arbitrary preference among a menu of available options (based upon options’ attributes)  In the case of routing, options include advertised AS level routes to address prefixes  Fully distributed routing (as opposed to a signaled approach) is the only possibility.  Extensible to meet the demands for newer policies. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 105The 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  Unfortunately, we have incomplete info, require a distributed solution with timevarying time delays Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 106Congestion: A Closeup View packet knee cliff loss  knee – point after which  throughput increases very congestion slowly collapse  delay increases fast  cliff – point after which  throughput starts to Load decrease very fast to zero (congestion collapse)  delay approaches infinity  Note (in an M/M/1 queue)  delay = 1/(1 – utilization) Load Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 107 Delay ThroughputCongestion Control vs. Congestion Avoidance  Congestion control goal stay left of cliff  Congestion avoidance goal stay left of knee knee cliff  Right of cliff: congestion Congestion collapse collapse Load Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 108 ThroughputGoals of Congestion Control  To guarantee stable operation of packet networks Subgoal: avoid congestion collapse  To keep networks working in an efficient status Eg: high throughput, low loss, low delay, and high utilization  To provide fair allocations of network bandwidth among competing flows in steady state For some value of “fair”  109 Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 109CC Techniques: Selfclocking P r P b Sender Receiver A b A s A r  Implications of ackclocking:  More batching of acks = bursty traffic  Less batching leads to a large fraction of Internet traffic being just acks (overhead) Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 110CC Techniques: Additive Increase/Multiplicative Decrease (AIMD) Policy Fairness Line x 1 x 0 User 2’s Allocation x 2 x 2 Efficiency Line User 1’s Allocation x 1  Assumption: decrease policy must (at minimum) reverse the load increase overandabove efficiency line  Implication: decrease factor should be conservatively set to account for any congestion detection lags etc Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 111Quality of Service: What is it Multimedia applications: network audio and video QoS network provides application with level of performance needed for application to function. Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 112Fundamental QoS Problems Scheduling Discipline FIFO B B  In a FIFO service discipline, the performance assigned to one flow is convoluted with the arrivals of packets from all other flows  Cant get QoS with a “freeforall”  Need to use new scheduling disciplines which provide “isolation” of performance from arrival rates of background traffic Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 113Fundamental QoS Problems  Conservation Law (Kleinrock): (i)W (i) = K q  Irrespective of scheduling discipline chosen:  Average backlog (delay) is constant  Average bandwidth is constant  Zerosum game = need to “setaside” resources for premium services Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 114QoS Big Picture: Control/Data Planes Control Plane: Signaling + Admission Control or SLA (Contracting) + Provisioning/Traffic Engineering Router Workstation Router Router Workstation Internetwork or WAN Data Plane: Traffic conditioning (shaping, policing, marking etc) + Traffic Classification + Scheduling, Buffer management Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 115Internet Regulation  FCC has largely had a handsoff policy  Early development of internet in part was influenced by high cost of telecom links  Packet switching developed as better multiplexing technology  Commoncarriage regulation has affected Inet:  Eg: modems were like fax machine for the common carrier  Use of basic service (eg: telephony) to provide enhanced service (eg: internet access) = not subject to FCC or state jurisdiction  Led to community bulletinboards, ISPs, valueadded networks (framerelay)…  HometoISP treated as local call (even if crossed state boundaries)  ILECs prohibited from offering interLATA services rd  DSL viewed as basic service = must unbundle DSL to allow 3 parties to offer internet access over ILEC DSL Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 116Summary: List of Internet 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 117Additional Reading  Internet Design Philosophy:  Saltzer, Reed, Clark: "EndtoEnd arguments in System Design"  Clark: "The Design Philosophy of the DARPA Internet Protocols":  RFC 2775: Internet Transparency: In HTML Shivkumar Kalyanaraman Rensselaer Polytechnic Institute 118
Website URL
Comment