Saturday, March 31, 2012

Part III: Packet Switching and Network Technologies



Chapter 13: Local Area Networks - Packets, Frames and Topologies

  • Circuit switching provides the illusion of an isolated physical path between a pair of communicating entities; a path is created when needed, and discontinued after use.
    • Three general properties define a circuit switched paradigm:
      • Point-to-point communications
      • Separate steps for circuit creation, use and termination
      • Performance equivalent to an isolated physical path
  • Packet switching, which forms the basis of the internet, is a form of statistical multiplexing that permits many-to-many communication. A sender must divide a message into a set of packets; after transmitting a packet, a sender allows other senders to transmit before transmitting a successive packet.
    • Three general properties define a switched paradigm:
      • Arbitrary, asynchronous communication
      • No set-up required before communication begins
      • Performance varies due to statistical multiplexing among packets
  • Local and Wide Area Packet Networks
    • Local Area Network (LAN) - least expensive, spans a single room or building
    • Metropolitan Area Network (MAN) - medium expense, spans a major city or metroplex
    • Wide Area Network (WAN) - most expensive, spans sites in multiple cities
  • Standards for Packet Format and Identification
    • Each standards organization focuses on particular layers of the protocol stack.
      • IEEE standards focus on specification for the lowest two layers of the stack and LAN technologies, data link and physical
        • IEEE 802 Model and Standards
          • Divides layer 2 into two conceptual sublayers
            • Logical Link Control (LLC) - Used for addressing and multiplexing
            • Media Access Control (MAC) - Used for access to shared media
      • W3C standards focus on the application layer
      • IETF standards focus on the transport and internet layer
      • Textbooks present all five as equally important: Application, Transport, Internet, Data Link, Physical
  • Networks are classified into broad categories according to their topology
    • Bus - all computers connected to a single cable, any computer can send data to any other but must coordinate traffic to be sure only one computer sends a signal at a time, line must also be terminated to prevent reflected electrical signals along the cable
    • Ring - all computers connect to a circular bus that forms a closed loop
    • Star - all computers connected to a central hub, which in practice tends to vary in distance to each computer
    • Mesh - every computer connected to every other computer but is disadvantaged by cost.
      • Connections in a mesh network = (n^2 - n)/2
  • Unicast, Broadcast and Multicast Addresses
    • Unicast - uniquely identifies a single computer, and specifies that only the identified computer should receive a copy of the packet
    • Broadcast - corresponds to all computers, and specifies that each computer on the network should receive a copy of the packet
    • Multicast - idenifies a subset of the computers on a given network, and specifies that each computer in the subset should receive a copy of the packet
  • Frames and Framing
    • Framing refers to the structure added to a sequence of bits or bytes that allows the sender and receiver to agree on the exact format of the message.
    • In a packet switched network each frame corresponds to a packet and consists of two conceptual parts:
      • Header the contains metadata, such as an address
      • Payload that contains the data being sent
    • In the ASCII character set the Start of Header (SOH) character marks the beginning of a frame, and the End of Transmission (EOT) character marks the end of a frame
  • Byte and Bit Stuffing (aka Data Stuffing and Character Stuffing)
    • To avoid conflicts with a payload that includes the SOH or EOT character, the sender replaces the control bytes (or bits) with a character sequence and the receiver replaces that sequence with the original value.


Chapter 14: The IEEE MAC Sub-layer

  • Static and Dynamic Channel Allocation
    • Static channel allocation suffices when the set of communicating entities is known in advance and does not change; most networks require a form of dynamic channel allocation
  • Channelization Protocols
    • Frequency Division Multi-Access (FDMA)
    • Time Division Multi-Access (TDMA)
    • Code Division Multi-Access (CDMA)
  • Controlled Access Protocols
    • Polling - centralized controller repeatedly polls stations and allows each to transmit one packet
      • Two general polling policies include:
        • Round Robin Order - each station has equal opportunity to transmit packets
        • Priority Order - some stations have more opportunity to send
    • Reservation - stations submit a request for the next round of data transmission
      • Often used with satellite transmission, employs a two-step process in which each potential sender identifies whether it has a packet to send during the next round and the controller transmits a list of the stations that will be transmitting. The stations then use this list to know when they should be transmitting.
    • Token passing - stations circulate a token; each time it receives the token, a station transmits one packet
      • Most often associated with ring topologies in which the order of circulation is defined by the ring and a token is pass in sequence to allow each station to transmit. In other topologies, each station is assigned a position in a logical sequence and the token is passed according to this assigned sequence.
  • Random Access Protocols
    • ALOHA - historic protocol used in an early radio network in HI; popular in textbooks and easy to analyze, but not used in real networks
      • Uses two carrier frequencies, one for inbound one for outbound. Station transmits on the inbound frequency then listens to confirm that the central transmitter repeats the transmission on the outbound frequency. If a copy arrives the station moves to the next packet, if no copy arrives the station waits a short time (randomized to reduce the probability of interference) and retransmits the original signal.
    • CSMA/CD - Carrier Sense Multi-Access with Collision Detection; the basis for Ethernet and the most widely used random access protocol
      • Ethernet offers three innovations in the handling of collisions:
        • Carrier Sense - each station is required to monitor the cable to detect whether another transmission is already in progress which prevents the most obvious collision problems.
        • Collision Detection - each station monitors the cable during transmission, if the signal on the cable differs from the signal that the station is sending a collision has occurred. When a collision is detected the sending station aborts transmission.
          • Following transmission all stations must wait for an interpacket gap to ensure that all stations sense an idle network and have a chance to transmit
        • Binary Exponential Backoff - to prevent secondary collisions Ethernet requires each computer to double the duration of a random delay after each collision.
    • CSMA/CA - Carrier Sense Multi-Access with Collision Avoidance; the basis for Wi-Fi wireless networks
      • Because computers on a wireless LAN can span distances greater than a signal can propagate, wireless LANs use CSMA/CA in which the sending and receiving computers each send a control message before packet transmission occurs.


Chapter 15: Wired LAN Technology (Ethernet and 802.3)

  • Ethernet Frame Format (8-bit bytes)
    • Header: 6-byte destination address, 6-byte source address, 2-byte type
    • 46-1500 bytes of payload
    • 4-byte cyclic redundancy check (CRC)
  • Ethernet Type Field and Demultiplexing
    • Allows a given computer to have multiple protocols operating simultaneously
      • Type 0800 - IP datagrams
      • Type 0806 - ARP messages
  • IEEE's Version of Ethernet (802.3)
    • Header: 48-bit destination addresss, 48-bit source address, 16-bit length
    • IEEE LLC/SNAP Header: 24-bit LLC, 24-bit OUI, 16-bit Type
      • Logical link control/sub-network attachment point 
    • If bytes 13-14 of an Ethernet frame contain a numeric value less than 1500, the field is interpreted as a packet length and the 802.3 standard applies; otherwise, the field is interpreted as a type field and the original Ethernet standard applies.
  • Twisted Pair Ethernet Wiring and Hubs
    • Twisted pair Ethernet wiring uses an electronic devices known as a hub in place of a shared cable.
  • Physical and Logical Ethernet Topology
    • Distinguishing between logical and physical topologies allows us to understand that twisted pair Ethernet uses a start physical topology, but logically acts like a bus.
    • Twisted pairs reduce EM interference on the transmission lines by canceling out between the two wires.
  • Variants of Twisted Pair Ethernet and Speeds
    • 10BaseT - Twisted Pair Ethernet - 10 Mbps - Cat 5
    • 100BaseT - Fast Ethernet - 100 Mbps - Cat 5E
    • 1000BaseT - Gigabit Ethernet - 1 Gbps - Cat 6


Chapter 16: Wireless Networking Technologies

  • Personal Area Networks (PANs)
    • Bluetooth - communication over a short distance between a small peripheral device such as a headset or mouse and a system such as a cell phone or a computer
    • Infrared - line-of-sight communication between a small device, often a hand-held controller, and a nearby system such as a computer or entertainment center
    • ISM wireless - communication using frequencies set aside for Industrial Scientific and Medical devices, an environment where electromagnetic interference may be present.
      • ISM wireless bands: 902-928 Mhz, 2.4-2.484 GHz, 5.725-5.850 GHz
  • Spread Spectrum Techniques - can help wireless LANs function in noisy environments
    • Direct Sequence Spread Spectrum (DSSS) - similar to CDMA where a sender multiplies the outgoing data by a sequence to form multiple frequencies and the receiver multiplies by the same sequence to decode
    • Frequency Hopping Spread Spectrum (FHSS) - a sender uses a sequence of frequencies to transmit data, and a receiver uses the same sequence of frequencies to extract data
    • Orthogonal Frequency Division Multiplexing (OFDM) - a frequency division multiplexing scheme where the transmission band is divided into many carriers in such a way that the carriers do not interfere
  • Other Wireless LAN Standards
    • Many exist (802.11e-s) each offering some advantage
  • Wireless LAN Architecture
    • Ad hoc - wireless hosts communicate among themselves without a base station
    • Infrastructure - a wireless host only communicates with an access point, and the access point relays all packets
      • Most wireless LANs use an infrastructure architecture in which a wireless computer communicates through an access point (base station).
  • Overlap, Association, and 802.11 Frame Format
    • CTL, DUR, Destination Address, Source Address, Router's Address, SEQ, Address 4 (used in Ad Hoc mode), Payload, CRC
  • Coordination Among Access Points
    • Two basic approaches exist:
      • Complex access points coordinate to ensure smooth handoff 
      • Lower cost access points operate independently and rely on wireless computers to change their association from one access point to another.
  • Contention and Contention-Free Access
    • Point Coordinated Function (PCF) for contention-free service
      • An access point controls stations in the basic service set (BSS) to ensure that transmissions do not interfere with each other
    • Distributed Coordinate Function (DCF) for contention-based service
      • Arranges for each station in a BBS to run a random access protocol
      • The CSMA/CA technique used in Wi-Fi networks includes timing parameters that specify how long a station waits before sending an initial packet and how long a station waits before sending a reply. 802.11 standard defines three timing parameters:
        • SIFS - Short Inter-Frame Space of 10 microseconds
        • DIFS - Distributed Inter-Frame Space of 50 microseconds
        • Slot time of 20 microseconds
  • Wireless MAN Technology and WiMax
    • Main features:
      • Uses licensed spectrum offered by carriers
      • Each cell can cover a radius of 3-10 Km
      • Uses scalable orthogonal FDM
      • Guarantees quality of services for voice or video
      • Can transport 70 Mbps in each direction at short distances
      • Provides 10 Mbps over a long distance (10 Km)
    • Two main versions of WiMax are commonly referred to as:
      • Fixed WiMax - refers to systems built using IEEE standard 802.16-2004 (802.16d); this technology does not provide for handoff among access points. Designed to provide connections between a service provider and a fixed location.
      • Mobile WiMax - refers to systems built according to standard 802.16e-2005 (802.16e); provides handoff among access points and can be used with portable devices.
    • Another proposed type is called Backhaul
      • Access
        • Last mile alternative to DSL or cable modems
        • High-speed interconnection for nomadic users
        • Unified data and telecommunications access
        • As a backup for a site's Internet connection
      • Interconnect
        • Backhaul from Wi-Fi access points to a provider
        • Private connections among sites of a company
        • Connection between small and large ISPs
  • PAN Technologies and Standards
    • Bluetooth
      • Wireless data replacement for cables
      • Uses 2.4 GHz band
      • Short distance (up to 5 meters, with variations that extend the range to 10-50 m)
      • Device is master or slave
      • Master grants permission to slave
      • Data rate is up to 721 Kbps
    • Ultra Wideband (UWB)
      • Uses wide spectrum of frequencies
      • Consumes very low power
      • Short distance (2 to 10 meters)
      • Signal permeates obstacles such as walls
      • Data rate of 110 at 10 meters and up to 500 Mbps at 2 meters
      • IEEE unable to resolve disputes and form a single standard
    • Zigbee (802.15.4)
      • Wireless standard for remote control, not data
      • Target is industry as well as home automation
      • Three frequency bands used (868 Mhz, 915 MHz, 2.4 GHz)
      • Data rate of 20, 40, or 250 Kbps, depending on frequency band
      • Low power consumption
      • Three levels of security being defined
  • Other Short Distance Communication Strategies
    • InfraRED (IrDA) - has widely accepted standards and the chief characteristics include:
      • Family of standards for various speeds and purposes
      • Practical systems have range of one to several meters
      • Directional transmission with a cone covering 30 degrees
      • Data rates between 2.4 Kbps (control) and 16 Mbps (data)
      • Generally low power consumption with very-low power versions
      • Signal may reflected from surfaces, but cannot penetrate solid objects
    • Radio Frequency Indentication (RFID) - small tags contain identification that a receiver can pull from the tag
      • Over 140 RFID standards exist for a variety of applications
      • Passive RFIDs draw power from the signal sent by the reader
      • Active RFIDs contain a battery, which may last up to 10 years
      • Limited distance, although active RFIDs extend further than passive
      • Can use frequencies from less than 100 MHz to 868-954 MHz
      • Used for inventory control, sensors, passports, and other applications
  • Wireless WAN Technologies can be divided into two categories:
    • Cellular communication systems
      • Architecture: each cell contains a tower, and a group of cells is connected to a mobile switching station which tracks a mobile user and manages the handoff as the user passes from one cell to another
      • Idealized coverage is modeled on hexagonal cells that fit together in a honeycomb shape, in practice there are overlaps and gaps between cells.
        • Practical systems vary cell size according to the density of cell phones and obstructions that cause coverage to be irregular.
      • Follows a key principle: interference can be minimized if an adjacent pair of cells do not use the same frequency
      • Generations of Cellular Technology
        • 1G - first generation from 1970s-1980s, uses analog signals
        • 2G/2.5G - second generation began in early 1990s and continues to be used, uses digital signals to carry voice (2.5G includes some 3G features)
          • GSM includes GPRS, EDGE (EGPRS), EDGE Evolution, HSCSD
          • CDMA includes IS-95A, IS-95B
          • TDMA includes iDEN, IS-136, PDC
        • 3G/3.5G - third generation began in 2000s and focuses on the addition of higher-speed data services (DL rates of 400 Kbps - 2 Mbps) to support applications such as web browsing and photo sharing. Allows for roaming across North America, Japan and Europe.
          • WCDMA includes UMTS and HSDPA (successors to IS-136, IS-95A, EDGE, PDC, UMTS)
          • CDMA 2000 includes 1xRTT (successor to IS-95B), EVDO and EVDV (successors to 1xRTT) 
        • 4G - fourth generation began around 2008 and focuses on support for real-time multimedia such as television or high-speed video download, uses multiple connection technologies (such as Wi-Fi and satellite) that phone automatically monitors to choose the best connection available.
    • Satellite communication systems
      • Very Small Aperture Terminal (VSAT) - uses dishes less than three meters in diameter
        • Uses three frequency ranges that differ in the strength of the signal delivered, sensitivity to rain, and coverage area
          • C Band, 3-7 GHz, Low strength, Medium sensitivity, Large footprint
          • Ku, 10-18 GHz, Medium strength, Moderate sensitivity, Medium footprint
          • Ka, 18-31 GHz, High strength, Severe sensitivity, Small footprint
      • Global Position System (GPS) Satellites
        • Not used as part of computer communication, but provides accurate time and location information. Key features include:
          • Accuracy between 20 and 2 meters (military versions have higher accuracy)
          • 24 total satellites orbit the Earth
          • Satellites arranged in six orbital planes
          • Provides time synchronization that is used in some communication networks
  • Software Radio and the Future of Wireless
    • Traditional radios are being replaced by radios that follow a programmable paradigm in which features are controlled by software running on processor. These features include:
      • Frequency - the exact set of frequencies used at a give time
      • Power - the amount of power the transmitter emits
      • Modulation - the signal and channel coding and modulation
      • Multiplexing - any combination of CDMA, TDMA, FDMA and others
      • Signal direction - antennas can be tuned for a specific direction
      • MAC protocol - all aspects of framing and MAC addressing


Chapter 17: LAN Extensions - Fiber Modems, Repeaters, Bridges and Switches

  • Distance Limitation and LAN Design
    • A maximum length specification is a fundamental part of LAN technology
    • LAN hardware will not work correctly over wires that exceed the bound.
  • Fiber Modem Extensions
    • A pair of fiber modems and optical fibers can be used to provide a connection between a computer and a remote LAN such as an Ethernet.
  • Repeaters
    • An analog hardware device used to extend a LAN
    • Amplify and send all incoming signals to the other side
  • Bridges and Bridging
    • A mechanism that connects two LAN segments and forward frames form one segment to another.
    • Computers cannot tell whether they are on a single segment or a bridged LAN.
  • Learning Bridges and Frame Filtering
    • An adaptive bridge uses the source MAC address in a packet to record the location of the sender, and uses the destination MAC address to determine whether to forward the frame.
  • Why Bridging Works Well
    • Because a bridge permits simultaneous activity on attached segments, a pair of computers on one segment can communicate at the same time as a pair of computers on another segment.
  • Distributed Spanning Tree (DST)
    • Computed from an algorithm implemented by bridges to prevent a cycle from causing an endless loop.
      • Views bridges as nodes in a graph and imposes a tree on the graph.
      • Ethernet bridges communicate among themselves using a multicast address this is reserved for spanning tree: 01:80:C2:00:00:00
    • Original approach called Spanning Tree Protocol (STP) consists of three steps:
      • Root election
      • Shortest path computation
      • Forwarding
  • Switching and Layer 2 Switches
    • An Ethernet switch (aka Layer 2 Switch) is a digital device with multiple ports, each for a single computer, that forwards packets by simulating a bridged network with one port per LAN segment.
      • Uses an intelligent interface attached to each port and a central fabric that provides simultaneous transfer between pairs of interfaces.
        • An interface contains a processor, memory, and other hardware needed to accept an incoming packet, consult a forwarding table, and send the packet across the fabric to the correct output port.
          • Because it has memory it is able to buffer arriving packets when an output computer is busy.
      • Chief advantage over a hub is that a switch permits multiple transfers to occur at the same time, provided the transfers are independent.
        • A switch with N ports can transfer up to N/2 packets simultaneously.
    • Virtual Local Area Network (VLAN) Switches
      • Extension to switches that includes virtualization, allowing a single switch to be configured to emulate multiple, independent switches with separate broadcast domains.
    • Bridging Used with Other Devices
      • Vendors no longer sell stand-alone bridge devices, the concept of bridging has been incorporated in network devices such as modems used in access technologies.


Chapter 18: WAN Technologies and Dynamic Routing

  • Large Spans and Wide Area Networks
    • Networking technologies can be classified according to the distance they span:
      • PAN - a region near and individual
      • LAN - a building or campus
      • MAN - a large metropolitan area
      • WAN - multiple cities or countries
    • Traditional WAN Architecture
      • Developed before LAN technologies, WANs used packet switches
        • Provide local connections for computer at the site as well as connections for data circuits that lead to other sites.
      • A traditional WAN is formed by interconnecting packet switches
        • The topology and capacity of connections are chosen to accommodate expected traffic and need for redundancy.
    • Store and Forward Paradigm
      • Wide area packet switching systems use the store-and-forward technique in which packets arriving at a packet switch are placed in a queue until the packet switch can forward them on toward their destination. 
        • The technique allows a packet to switch to buffer a short burst of packets that arrive simultaneously.
    • Addressing in a WAN
      • Hierarchical addressing
        • Divides each address into Site and Computer at the site
    • Next Hop Forwarding
      • Only the first part of a destination address is used when forwarding a packet across a WAN. Once the packet reaches the switch to which the destination computer attaches, the second part of the address is used to forward the packet to the correct local computer.
      • Source Independence
        • Allows the forwarding mechanism in a computer to be compact and efficient
          • Only one table is required
          • Only the destination address needs to be extracted from a packet
          • Uses a uniform process for packets from directly connected computers and those from another packet switch.
    • Dynamic Routing Updates in a WAN
      • Each switch must have a forwarding table whose value guarantee:
        • Universal communication - must contain a valid next-hop route for each possible destination address
        • Optimal routes - the next-hop value for a given destination must point to the shortest path to the destination
      • Default Routes
        • A mechanism used to eliminate duplicate entries by using a single default route to replace a long list of entries with the same next-hop value
    • Forwarding Table Computation
      • Two basic approaches:
        • Static Routing - a program computes and installs routes when a packet switch boots; the routes do not change.
        • Dynamic Routing - a program builds an initial forwarding table when a packet switch boots; the program then alters the table as conditions in the network change.
    • Distributed Route Computation
      • Rather than one centralized program computing all shortest paths, each packet switch must computer its own forwarding table locally. There are two general forms:
        • Link-State Routing (LSR), using Dijkstra's algorithm
          • Also known as Shortest Path First (SPF) Routing
          • Packet switches periodically send messages across the network (to all switches) that carry the status of a link between two packet switches. Each switch runs software that collects incoming status messages and uses them to build a graph of the network and then Dijkstra's algorithm to build a forwarding table by choosing itself as the source.
            • Dijkstra's algorithm computers R, a next-hop forwarding table, and D, the distance to each node form the specified source node.
          • Able to adapt to hardware failures.
        • Distance-Vector Routing (DVR)
          • Also arranges for packet switches to exchange messages periodically, but requests a complete list of destinations and the current cost of reaching each.
          • DVR messages are not broadcast, each packet switch periodically sends a DVR message to its neighbors containing pairs of destination/distance
          • When a message arrives at packet switch from neighbor N, the packet switch updates its forwarding table if the neighbor has a shorter path to some destination D.
          • One of the primary problems with DVR comes from backwash (packet switch receives information that it sent) which creates a routing loop
            • Routing mechanisms contain constraint and heuristics to prevent problems like routing loops, one such technique is split horizon
              • Specifies that a switch does not send information back to its origin
            • Other systems include hysteresis that prevents software from making many changes in a short time
              • This can cause routing problems in a large network where many link fail and recover frequently.
        • Shortest Path Computation in a Graph
          • Because it uses weights on links when computing shortest paths, Dijkstra's algorithm can be used with measures other than geographic distance.
          • The algorithm requires four data structures to store:
            • Information about the graph
            • Current distance to each node
            • Next-hop for the shortest path
            • Information about the remaining set of nodes


Chapter 19: Networking Technologies Past and Present

  • Connection and Access Technologies
    • Synchronous Optical Network or Digital Hierarchy (SONET/SDH)
      • Originally designed as a system to carry digital voice telephone calls, it has become the standard for digital circuits used throughout the internet. Permits a physical ring to be constructed for the purpose of redundancy. Hardware can detect and correct problems.
      • Add-Drop multiplexor is used to connect a site to a SONET ring. Uses TDM. 
      • SDH provides standards for circuits such as T3 that can be configured across a SONET ring.
    • Optical Carrier (OC)
      • OC standards specify signaling used on an optical fiber SONET ring. Offer higher data rates than the T-series standard provided by SDH
    • Digital Subscriber Line (DSL) and Cable Modems
      • These technologies are the principle means of providing broadband internet to private residences and small businesses. DSL offers 1-6 Mbps rates, depending on the distance between the central office and the subscriber; Cable modems offer up to 52 Mbps.
    • WiMAX and Wi-Fi
      • Wireless technology is widely used and has continued to increase data rates. WiMAX uses fixed or mobile optimization.
    • Very Small Aperture Satellite (VSAT)
      • Has high data rates but long delays, delivers Internet access via satellite
    • Power Line Communication (PLC)
      • Uses existing infrastructure to deliver Internet services across power lines at high frequencies.
  • LAN Technologies
    • IBM Token Ring
      • Major LAN technology for many years in corporate applications. Began at 4 Mbps and ultimately reformulated as 16 Mbps. Pricey.
    • Fiber and Copper Distributed Data Interconnect (FDDI and CDDI)
      • Developed in the late 1980s to address data rate issues with early Ethernet and Token Rings. Introduced one of the earliest LAN switches, but was ultimately abandoned due to the rise of fast Ethernet.
    • Ethernet
      • Although Ethernet dominates the LAN market, the original Ethernet (10 Mbps) has disappeared completely, replaced by new technology (100 Mbps - 1 Gbps) still called Ethernet.
  • WAN Technologies
    • ARPANet
      • Advanced Research Projects Agency (ARPA) funded networking research in the late 1960s for the USDOD to determine if wide area networks and packet switching would be valuable for the military. Connected researchers from academia and industry. Operated at 56K. Its concepts, algorithms and terminology are still in use today as APRANet formed the first Internet backbone in 1983 when ARPA began using Internet protocols.
    • X.25
      • invented before personal computers became popular used to connect ASCII terminals; this technology captured key strokes, placed each in an X.25 packet and transmitted them across the network
    • Frame Relay
      • developed by long distance carriers to transport data; designed to accept and deliver blocks of data (up to 8K octets); designed to run at 4-100 Mbps, but high cost drove much business to less expensive, slower connection technologies
    • Switched Multi-megabit Data Services (SMDS)
      • high-speed (>1 Mbps) wide area data service offered by long distance carriers; designed to carry data rather than voice using a special connectionless hardware interface
    • Asynchronous Transfer Mode (ATM)
      • Introduced as an alternative to the Internet in the 1990s it offered high data rates that could accommodate video; used label switching to change address each time a packet passed through a switch. Hardware was complex and expensive.
    • Multi-Protocol Label Switching (MPLS)
      • Resulted from ATM efforts; adapted label switching for use in Internet routes
    • Integrated Services Digital Network (ISDN)
      • 128 Kbps, advance over dial-up modems but by the time it was available seemed slow for the price.

Monday, March 5, 2012

Part II: Data Communications

Chapter 5: Overview of Data Communications
Although it includes concepts from physics and mathematics, data communications provides a foundation that is used to construct practical communication systems. 

  • Three main topics define the scope of data communications:
    • Sources of data can be arbitrary types
    • Transmission uses a physical system
    • Multiple sources of information can share the underlying medium
  • Data communications has subtopics:
    • Information sources. Analog or digital
    • Source encoder and decoder. Data compression.
    • Encryptor and decryptor. Cryptographic techniques and algorithms.
    • Channel encoder and decoder. Detect and correct transmission errors.
    • Multiplexor and demultiplexor. Multiple sources combine data for transmission. Simultaneous sharing and turn-taking techniques.
    • Modulator and demodulator. Analog and digital modulation schemes, and modems.
    • Physical channel and transmission. Transmission media and modes. Bandwidth, noise and interference, channel capacity, modes such as serial or parallel.


Chapter 6: Information Sources and Signals
Throughout the study of data communications, it is important to remember that the source of information can be arbitrary and includes devices other than computers.

Sine waves are fundamental to input processing because many natural phenomena produce a signal that corresponds to a sine wave as a function of time.

  • Four important characteristics of signals relate to sine waves:
    • Frequency. Oscillations per unit time.
    • Amplitude. Difference between maximum and minimum signal heights.
    • Phase. Shift of the sine wave start position from reference time
    • Wavelength. Length of a cycle as a signal propagates across a medium.
  • The importance of composite signals and sine functions:
    • Modulation usually forms a composite signal.
    • Can decompose a composite signal into its constituent parts: a set of sine functions each with frequency, amplitude and phase.
      •  Discovered by Fourier
  • The bandwidth of an analog signal is the difference between the highest and lowest frequency of its components. 
    • If the signal is plotted in the frequency domain, the bandwidth is trivial to compute.
  • Digit signals and signal levels
    • A communication system that uses two signal levels can only send one bit at a given time.
      • A system that supports 2^n signal levels can send n bits at a time.
  • An alternative method of increasing the amount of data that can be transferred in a given time consists of decreasing the amount of time that the system leaves a signal at a given level.
    • bits per second = baud x [log sub2(levels)]
  • Converting from digital to analog
    • Approximating an analog signal from a digital one using Fourier results in an infinite set of sine waves, so approximation is used in practice.
      • As few as three are necessary.
      • A digital signal has infinite bandwidth.
    • Line coding
      • A variety of coding techniques are available that differ in how they handle synchronization as well as other properties such as the bandwidth used.
        • Manchester Encoding - detecting a transition in the signal level is easier than measuring the  signal level. 1 corresponds to the transition from 0V to a positive voltage level. Similarly, 0 corresponds to the transition from a positive voltage level to zero.
        • Differential Manchester Encoding (Conditional DePhase Encoding) - uses relative transitions rather than absolute. Transition always occurs in the middle of the bit time. The logical value of the bit is represented by the presence or absence of a transition at the beginning of the bit time. 0 = transition, 1=no transition.
  • Converting from analog to digital
    • Two basic approaches:
      • Pulse code modulation (PCM)
        • PCM encoder consists of a sequence of sampling (recording), quantization (converting recording into small integer values) and encoding (onto a specific format).
        • Used in data systems that expect data values to be lost or changed during transmission.
      • Delta modulation
        • Also takes samples, but instead of quantization for each sample, delta modulation sends one quantization value followed by a string of values that give the difference between the previous value and the current value.
          • Transmitting differences requires fewer bits than full values, particularly if the signal does not vary rapidly.
          • Drawback is in the propagation of errors. One lost or damaged item will call all successive values to be misinterpreted.
    • Nyquist Theorem and Sampling Rate
      • Too few samples is undersampling (results in crude oversimplification of the original signal), too many is oversampling (generates unnecessary data which uses more bandwidth).
      • Ideal sampling rate = 2 x highest frequency in the composite signal
        • Digitized voice call = 8K samples/second x 8 bits/second = 64K bits/second
    • Encoding and data compression
      • Lossy - some information is lost during compression
        • JPG, MP3
      • Lossless - all information is retained in the compressed version.
        • Most implementations use the dictionary approach where compression finds repeated strings and compresses by building and referencing a dictionary of those strings.


Chapter 7: Transmission Media

  • Guided and unguided transmission:
    • By type of path
      • Communication can follow an exact path such as a wire, or can have no specific path, such as a radio transmission.
    • By form of energy
      • Electrical energy is used on wires, radio transmission is used for wireless, and light is used for optical fiber.
  • Background radiation and electrical noise
    • The random electromagnetic radiation generated by devices such as electric motors can interfere with communication that uses radio transmission or electrical energy sent over wires.
      • Random electromagnetic radiation (noise) permeates the environment
      • When it hits metal, electromagnetic radiation induces a small signal
      • Because it absorbs radiation, metal acts as a shield.
    • Twisted pair copper wire
      • Unshielded Twisted Pair (UTP)
        • Twisting eliminates the potential difference that builds up along parallel wires.
      • Coaxial cable
        • Heavy shielding and symmetry make coaxial cable immune to noise, capable of carrying high frequencies, and prevent signals on the cable from emitting noise to surrounding cables.
      • Shielded Twisted Pair (STP)
        • Cat 7 = 600 Mbps
  • Media using light energy and optical fibers
    • Optical fibers
      • Angle of incidence is:
        • Less than the critical angle = refraction
        • Equal to the critical angle = absorption
        • Greater than the critical angle = reflection
      • Types of fiber and light transmission
        • Multimode, Step Index: least expensive because boundary between fiber and cladding is abrupt causing frequent reflection and signal dispersion.
        • Mutimode, Graded Index: slightly more expensive than step index, fiber density increased near the edge, reducing reflection and lowering dispersion.
        • Single Model: most expensive, least dispersion. Small diameter and other properties to reduce reflection. Used for long distances and higher bit rates.
      • Transmission:
        • Light Emitting Diode (LED)
        • Injection Laser Diode (ILD)
      • Reception
        • Photo-sensitive cell
        • Photodiode
      • Compared to copper wire
        • Immune to electrical noise
        • Less signal attenuation
        • Higher bandwidth
        • Higher cost
        • More expertise and equipment required
        • More easily broken
    • InfraRed transmission
      • Best suited for indoors in situation where the path between sender and receiver is short and free from obstruction.
    • Point-to-point lasers
      • Transmitter and receive must be aligned precisely
        • Typical installations affix the equipment to a permanent structure.
  • Electromagnetic (Radio) Communication
    • Signal propagation
      • Low frequency, <2Mbps, waves follow Earth's curvature but can be blocked by unlevel terrain.
      • Medium frequency, 2-30Mbps, wave can reflect from layers of the atmosphere
      • High frequency, >30Mbps, wave travels in a direct line and will be blocked by obstructions.
    • Wireless technologies are classified into two broad categories:
      • Terrestrial. Communication uses equipment such as radio or microwave transmitters, is relatively close to the Earth's surface.
      • Nonterrestrial. Some of the equipment used in communication is outside the Earth's atmosphere.
        • Types of satellites:
          • Low Earth Orbit (LEO): low delay, moves across the sky
            • A cluster of LEO satellites work together to forward messages.
          • Medium Earth Orbit (MEO): elliptical orbit, polar communications
          • Geostationary Earth Orbit (GEO): fixed position but further away (so more delay)
            • Distance required = 35,785 km (1/10th distance to the moon)
            • Radio wave to the GEO satellite and back = 0.238 seconds
            • Can cover the whole earth with three satellites at 120 degrees from one another.
  • Tradeoffs Among Media Types
    • Cost: materials, installation, operation and maintenance
    • Data rate
      • Channel capacity = the maximum data rate that the medium can support
      • Claude Shannon's Theorem determines the maximum data rate that could be achieved over a transmission system that experiences noise. C= data rate in bps, B=hardware bandwidth, S/N=signal to noise ratio or average signal power divided by the average noise power.
        • C = B log sub2(1 + S/N)
        • S/N often expressed in dB
          • dB=10 log sub10[P2/P1]
    • Delay: time required for signal propagation or processing
      • Propagation delay = the time required for a signal to traverse the medium
    • Affect on signal: attenuation or distortion
    • Environment: susceptibility to interference and electrical noise
    • Security: susceptibility to eavesdropping
  • Significance of Channel Capacity
    • Nyquist's Theorem encourages engineers to explore ways to encode bits on a signal because a clever encoding allows more bits to be transmitted per unit time.
    • Shannon's Theorem informs engineers that no amount of clever encoding can overcome the laws of physics that place a fundamental limit on the number of bits per second that can be transmitted in a real communications system.


Chapter 8: Reliability and Channel Coding

  • There are three main sources of transmission errors:
    • Interference - electromagnetic radiation emitted from devices or from background cosmic radiation
    • Distortion - all physical systems distort signals. Wires have properties of capacitance and inductance that block signals at some frequencies while admitting signals at other frequencies.
    • Attenuation - as a signal passes across a medium, the signal becomes weaker.
  • Although transmission errors are inevitable, error detection mechanisms add overhead. A designer must choose which error detection and compensation mechanisms will be used.
  • Effect of Transmission Errors on Data
    • Single bit error - only a single bit in a block of bits is changed. Often results from very short duration interference.
    • Burst error - multiple bits in a block of bits are changed. Results from longer duration interference.
    • Erasure (ambiguity) - signal that arrives at the receiver is ambiguous, not clearly a logical 1 or 0. Can result from distortion or interference.
  • Two strategies for handling channel errors:
    • Forward Error Correction (FEC) mechanisms
      • Block Error Codes: block code divides the data to be sent into sets of blocks and attaches extra information known as redundancy to each block. The encoding for a given block depends only on the bits themselves, not on bits that were sent earlier. Block error codes are memoryless in the sense that the encoding mechanism does not carry state information from one block of data to the next.
        • Single parity checking (SPC) is a basic form of channel coding in which a sender adds an extra bit to each byte to make an even (or odd) number of 1 bits and a receiver verifies that the incoming data has the correct number of 1 bits.
      • Convolutional Error Codes: convolutional code treats data as a series of bits, and computes a code over a continuous series. Thus, the code computed for a set of bits depends on the current input and some of the previous bits in the stream. Convolutional codes are said to be codes with memory.
    • An ideal channel coding scheme is one where any changes to bits in a valid codeword produces an invalid combination. There is a tradeoff between error detection and overhead
      • Hamming Distance measures a code's strength and can be used on strings in a codebook.
        • To find the maximum number of bit changes that can transform a valid codeword into another valid codeword, compute the minimum Hamming distance between all pairs in a codebook.
      • Row and Column (RAC) encoding
        • Allows a receiver to correct any single bit error and to detect errors in which two or three bits are changed.
      • 16-bit Checksum Used in the Internet
        • Two forms of zero:
          • All 0s, meaning unused
          • All 1s, represents a checked all 0s
      • Cyclic Redundancy Codes (CRCs)
        • Three key properties:
          • Arbitrary message length
          • Excellent error detection
          • Fast hardware implementation
        • Many disciplines have studied CRC.
    • Automatic Repeat reQuest (ARQ) mechanisms
      • Requires the sender and receiver to communicate metainformation
        • Receiving side sends a short acknowledgement message back
        • If no acknowledgement received after T time units, the sender retransmits a copy assuming the original message has been lost.


Chapter 9: Transmission Modes

  • Taxonomy of transmission modes:
    • Serial - one bit sent at a time
      • Advantages:
        • Can be extended over long distances without timing problems
        • Less expensive (fewer physical wires and intermediate electronic components are less expensive)
      • Transmission order
        • Most significant bit (MSB or big-endian)
        • Least significant bit (LSB or little-endian)
        • Bit order and byte order are independent of one another
          • Ethernet uses byte big-endian bit little-endian
      • Timing of Serial Transmission
        • Asynchronous - can occur at any time with an arbitrary delay between the transmission of two data items.
          • Sends extra information before each transmission that allows a receiver to synchronize with the signal
          • EIA RS-232-C is an accepted standard for asynchronous, serial communication over short distances and precedes each character with a start bit, sends each bit of the character, and follows each character with an idle period at least one bit long (stop bit).
        • Synchronous - occurs continuously with no gap between the transmission of two data items.
          • When compared to synchronous transmission an asynchronous RS-232 mechanism has 25% overhead per character.
          • Framing
            • Although the underlying mechanism transmits bits continuously, the use of an idle sequence and framing permits a synchronous transmission mechanism to provide a byte-oriented interface and to allow idle gaps between blocks of data.
        • Isochronous - at regular intervals with a fixed gap between the transmission of two data items.
          • Designed to provide a steady bit flow for multimedia applications like video.
          • Accepts data at a fixed rate
          • For an isochronous connection operating at fixed rate R, there is an underlying synchronous mechanism that operates at slightly more than R bps
    • Parallel - multiple bits sent at the same time
      • Two chief advantages:
        • High speed
        • Matches the communication mode of the underlying hardware
  • A communication channel is classified a one of three types depending on the direction of transfer:
    • Simplex - unidirectional data transfer
    • Full-Duplex - concurrent bidirectional data transfer
    • Half-Duplex - shared transmission mechanism that allows bidirectional data transfer where only one side transmits at a given time
  • Data Communications Equipment (DCE) is equipment owned by the phone company, while Data Terminal Equipment (DTE) is equipment owned by the subscriber.



Chapter 10: Modulation and Modems

  • Analog modulation schemes
    • Modulation refers to changes made in a carrier according to the information being sent
    • Three primary techniques exist to modulate an electromagnetic carrier according to a signal:
      • Amplitude modulation
        • Varies the amplitude of a carrier in proportion to the information being sent (the signal). Frequency stays constant.
        • In practice modulation only changes the amplitude of a carrier slightly depending on the modulation index constant.
          • Prevents amplitude from reaching zero, where Shannon's theorem predicts the signal to noise ration would also approach zero. The larger the signal to noise ratio the more bits per second can be transferred.
      • Frequency modulation
        • Varies the frequency of a carrier in proportion to the information being sent. Amplitude of the carrier is unaltered (continues as a sine wave).
      • Phase Shift modulation
        • Phase is the offset from a reference time at which the sine wave begins. It is possible to represent a signal by using changes in phase.
        • This technique seldom used with an analog signal. For analog signal phase shift modulation is essentially a special case of frequency modulation.
  • Modulation, Digital Input and Shift Keying
    • Shift keying is the digital equivalent of Analog modulation
      • Amplitude Shift Keying (ASK)
      • Frequency Shift Keying (FSK)
      • Phase Shift Keying (PSK)
        • Changes the phase of the carrier abruptly to encode data. Each change is called a phase shift.
          • The chief advantage of mechanisms like phase shift keying arises from the ability to represent more than one data bit at a given change. 
            • A constellation diagram shows the assignment of data bits to phase changes.
            • Although many variations of phase shift keying exist, noise and distortion limit the ability of practical systems to distinguish among arbitrarily small differences in phase changes.
        • Quadrature Amplitude Modulation (QAM)
          • Uses both change in phase and change in amplitude to represent values to increase the data rate.


Chapter 11: Multiplexing and Demultiplexing (Channelization)

  • There are four basic approaches to multiplexing:
    • Frequency Division Multiplexing
      • Because carrier waves on separate frequencies do not interfere, FDM provides each sender and receiver pair with a private communication channel over which any modulation scheme can be used.
        • Long-lived (since early experiments with radio)
        • Widely used (radio, TV, cable, AMPS cellular telephone)
        • Analog (accepts and delivers analog signals, even if the carrier is modulated to contain digital information FDM treats the carrier as an analog wave; also makes it susceptible to noise and distortion)
        • Versatile (filters on ranges of frequencies without examining other aspects of the signals)
      • Can use a range of frequencies in FDM to:
        • Increase the data rate
        • Increase the immunity to interference
      • Hierarchical FDM
        • It is possible to build a hierarchy of frequency division multiplexing in which each stage accepts as inputs the outputs from the previous stage
    • Wavelength Division Multiplexing
      • When frequency division multiplexing is applied to optical fiber, prisms are used to combine or separate individual wavelengths of light, and the result is known as wavelength division multiplexing.
    • Time Division Multiplexing
      • Means simply transmitting an item from one source, then transmitting an item from another source, etc.
      • Broad concept that appears in many forms 
      • Synchronous TDM
        • The synchronous TDM mechanism used for digital telephone calls includes a framing bit at the beginning of each round. The framing sequence of alternating 1s and 0s insures that a demultiplexor either remains synchronized or detects the error.
    • Inverse Multiplexing
      • When the only connection between two points consists of multiple transmission media, but no single medium has a sufficient bit rate, inverse multiplexing allows one to spread high-speed digital input over multiple lower-speed circuits for transmission and combine the results on the receiving end.
    • Code Division Multiplexing
      • Relies on mathematical idea: values from orthogonal vector spaces can be combined and separated without interference.
      • CDM incurs lower delay than TDM when a network is highly utilized.


Chapter 12: Access and Interconnection Techniques
A typical residential subscriber receives much more information than the subscriber sends, Internet access technologies are designed to transfer more data in one direction than the other.



  • Internet access technologies can be divided into two broad categories based on the data rate they provide:
    • Narrowband
      • Generally <= 128 kbps
      • Dialup telephone connections, leased circuit using modems, fractional T1 data circuits, ISDN and other telco data services
    • Broadband
      • Delivers >=128 kbps, though some professionals suggest broadband is really >1Mbps
      • DSL, cable modem, wireless access technologies, data circuits at T1 or higher
        • Because it uses FDM, ADSL and plain old telephone service (POTS) can use the same wires simultaneously.
        • VDSL=52Mbps
        • ADSL uses an adaptive technology in which a pair of modems probe many frequencies on the line between them, and select frequencies and modulation techniques that yield optimal results on the line.
        • Cable modems use FDM, so a cable modem can be easily attached directly to existing cable wiring without a splitter.
      • Access technologies the employ optical fiber
        • FTTC - Fiber to the Curb. Uses twisted copper for feeder circuits that cover the final distance to building or home.
        • FTTB - Fiber to the Building. Business subscribers.
        • FTTH - Fiber to the Home. Residential subscribers.
        • FTTP - Fiber to the Premises. Encompasses FTTB and FTTH
      • Wireless Access Technologies
        • 3G services - third generation cellular telephone services for data
        • WIMAX - wireless access technology up to 155 Mbps using radio frequencies
        • Satellite - data services over satellite
      • High Capacity Connections at the Internet Core
        • Digital circuits leased from common carriers form the fundamental building blocks for long-distance data communications. The cost depends on the circuit capacity and distance.
        • A digital circuit needs a device known as a DSU/CSU at each end. The DSU/CSU translates between the digital representation used by phone companies and the digital representation used by the computer industry.
      • Synchronous Optical NETwork (SONET)
        • Although the SONET standard defines a technology that can be used to build a high-capacity ring network with multiple data circuits multiplexed across the fibers that constitute the ring, most data networks only use SONET to define framing and encoding on a leased circuit.