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.