Please enable JavaScript.

Coggle requires JavaScript to display documents.

NWC202-5-LINK LAYER (Introduction (Services (framing, link access (channel…

- - - - communication channels that connect adjacent nodes along communication path
      - Wired Link
      - LANs
      - Wireless Link
    - - layer-2 packet
      - encapsulates datagram
    - - hosts and routers
  - - - channel access if shared medium
      - “MAC” addresses used in frame headers to identify source, dest
      - encapsulate datagram into frame, adding header, trailer
    - - seldom used on low bit-error link (fiber, some twisted pair)
      - wireless links: high error rates
      - we learned how to do this already (chapter 3)!
    - - pacing between adjacent sending and receiving nodes
    - - errors caused by signal attenuation, noise.
      - receiver detects presence of errors:
        
        signals sender for retransmission or drops frame
    - - receiver identifies and corrects bit error(s) without resorting to retransmission
    - - with half duplex, nodes at both ends of link can transmit, but not at same time
  - - - implements link, physical layer
      - Ethernet card, 802.11 card; Ethernet chipset
  - - - adds error checking bits, rdt, flow control, etc.
      - encapsulates datagram in frame
    - - extracts datagram, passes to upper layer at receiving side
      - looks for errors, rdt, flow control, etc
- - - - Error Detection and Correction bits (redundancy)
    - - Data protected by error checking, may include header fields
  - - - total number of 1s
      - For odd parity schemes, the parity bit value is chosen such that there is an odd number of 1s
  - - - detect “errors” (e.g., flipped bits) in transmitted packet
    - - checksum: addition (1’s complement sum) of segment contents
      - sender puts checksum value into UDP checksum field
      - treat segment contents as sequence of 16-bit integers
    - - compute checksum of received segment
      - check if computed checksum equals checksum field value:
        
        NO - error detected
        
        YES - no error detected. But maybe errors nonetheless?
  - - - choose r+1 bit pattern (generator), G
      - choose r CRC bits, R, such that
        
        <D,R> exactly divisible by G (modulo 2)
        
        receiver knows G, divides <D,R> by G. If non-zero remainder: error detected!
        
        can detect all burst errors less than r+1 bits
      - view data bits, D, as a binary number
- - - - Point-to-Point
        
        PPP for dial-up access
        
        point-to-point link between Ethernet switch, host
      - Broadcast
        (Shared wire or Medium)
        
        upstream HFC
        
        802.11 wireless LAN
        
        old-fashioned Ethernet
  - - - two or more simultaneous transmissions by nodes: interference
      - collision if node receives two or more signals at the same time
      - single shared broadcast channel
    - - distributed algorithm that determines how nodes share channel, i.e., determine when node can transmit
      - communication about channel sharing must use channel itself!
        
        no out-of-band channel for coordination
  - - - no special node to coordinate transmissions
      - no synchronization of clocks, slots
  - - - Characteristics
        
        “recover” from collisions
        
        when node has packet to send
        
        no a priori coordination among nodes
        
        transmit at full channel data rate R.
        
        two or more transmitting nodes ➜ “collision”,
      - random access MAC protocol specifies:
        
        how to detect collisions
        
        how to recover from collisions (e.g., via delayed retransmissions)
      - Examples
        
        Slotted ALOHA
        
        CSMA, CSMA/CD, CSMA/CA
        
        ALOHA
      - Slotted ALOHA
        
        Assumptions
        
        nodes start to transmit only slot beginning
        
        nodes are synchronized
        
        time divided into equal size slots (time to transmit 1 frame)
        
        if 2 or more nodes transmit in slot, all nodes detect collision
        
        all frames same size
        
        Operation
        
        if no collision: node can send new frame in next slot
        
        if collision: node retransmits frame in each subsequent slot with prob. p until success
        
        when node obtains fresh frame, transmits in next slot
        
        Pros
        
        highly decentralized: only slots in nodes need to be in sync
        
        simple
        
        single active node can continuously transmit at full rate of channel
        
        Cons
        
        idle slots
        
        nodes may be able to detect collision in less than time to transmit packet
        
        collisions, wasting slots
        
        clock synchronization
      - Pure ALOHA (unslotted)
        
        when frame first arrives
        
        transmit immediately
        
        collision probability increases:
        
        frame sent at t0 collides with other frames sent in [t0-1,t0+1]
        
        unslotted Aloha: simpler, no synchronization
        
        Collision
        
        If a transmitted frame experiences a collision
        
        with one or more other transmissions, the node will then immediately (after
        
        completely transmitting its collided frame) retransmit the frame with probability p
      - CSMA
        
        Collisions
        
        collisions can still occur:
        
        propagation delay means two nodes may not hear each other’s transmission
        
        collision:
        
        entire packet transmission time wasted
        
        distance & propagation delay play role in in determining collision probability
        
        Characteristics
        
        if channel sensed idle: transmit entire frame
        
        if channel sensed busy, defer transmission
        
        listen before transmit:
        
        human analogy: don’t interrupt others!
        
        CSMA/CD
        
        Characteristics
        
        carrier sensing, deferral as in CSMA
        
        collisions detected within short time
        
        colliding transmissions aborted, reducing channel wastage
        
        collision detection:
        
        easy in wired LANs: measure signal strengths, compare transmitted, received signals
        
        difficult in wireless LANs: received signal strength overwhelmed by local transmission strength
        
        human analogy: the polite conversationalist
        
        binary (exponential) backoff:
        
        after mth collision, NIC chooses K at random from {0,1,2, …, 2^m-1}. NIC waits K·512 bit times, returns to Step 2
        512 bit times mean time to send all those 512 bits
        
        longer backoff interval with more collisions
    - - nodes take turns, but nodes with more to send can take longer turns
      - Polling
        
        typically used with “dumb” slave devices
        
        concerns:
        
        Polling Overhead
        
        Latency
        
        Single of Point Failure (master node)
        
        master node “invites” slave nodes to transmit in turn
      - Token-Passsing
        
        token message
        
        concerns:
        
        latency
        
        Single Point of Failure (Token)
        
        token overhead
        
        control token passed from one node to next sequentially.
      - Cable Access Network
        
        Components
        
        Downstream
        
        40Mbps downstream (broadcast) channels
        
        single CMTS transmits into channels
        
        Upstream
        
        30 Mbps upstream channels
        
        multiple access: all users contend for certain upstream channel time slots (others assigned)
        
        DOCSIS
        
        Data Over Cable Service Interface Specification
        
        FDM downstream
        
        downstream frequency channels
        
        TDM upstream
        
        downstream MAP frame: assigns upstream slots
        
        request for upstream slots (and data) transmitted random access (binary backoff) in selected slots
        
        some slots assigned, some have contention
    - - Characteristics
        
        allocate piece to node for exclusive use
        
        divide channel into smaller “pieces” (time slots, frequency, code)
      - Examples
        
        TDMA
        
        Time Division Multiple Access
        
        Characteristics
        
        access to channel in "rounds"
        
        each station gets fixed length slot (length = pkt trans time) in each round
        
        unused slots go idle
        
        FDMA
        
        Frequence Division Multiple Access
        
        Characteristics
        
        each station assigned fixed frequency band
        
        unused transmission time in frequency bands go idle
        
        channel spectrum divided into frequency bands
- - - - network-layer address for interface
      - used for layer 3 (network layer) forwarding
    - - 48 bit MAC address (for most LANs) burned in NIC ROM, also sometimes software settable
      - 1A-2F-BB-76-09-AD
      - Function
        
        used ‘locally” to get frame from one interface to another physically-connected interface (same network, in IP-addressing sense)
      - MAC address allocation administered by IEEE
      - manufacturer buys portion of MAC address space (to assure uniqueness)
      - Analogy
        
        MAC address: like Social Security Number
        
        IP address: like postal address
      - MAC flat address ➜ portability
        
        can move LAN card from one LAN to another
      - IP hierarchical address not portable
        
        address depends on IP subnet to which node is attached
    - - Address Resolution Protocol
      - ARP table
        
        IP/MAC address mappings for some LAN nodes:
        
        < IP address; MAC address; TTL>
        
        TTL (Time To Live): time after which address mapping will be forgotten (typically 20 min)
        
        each IP node (host, router) on LAN has table
      - Translates IP address to MAC address and vice-versa
  - - - simpler, cheaper than token LANs and ATM
      - kept up with speed race: 10 Mbps – 10 Gbps
      - first widely used LAN technology
      - cheap $20 for NIC
    - - Bus
        
        all nodes in same collision domain (can collide with each other)
      - Star
        
        active switch in center
        
        each “spoke” runs a (separate) Ethernet protocol (nodes do not collide with each other)
        
        Prevails today
    - - Preamble
        
        7 bytes with pattern 10101010 followed by one byte with pattern 10101011
        
        used to synchronize receiver, sender clock rates
      - Addresses
        
        if adapter receives frame with matching destination address, or with broadcast address (e.g. ARP packet), it passes data in frame to network layer protocol
        
        otherwise, adapter discards frame
        
        6 byte source, destination MAC addresses
      - Type
        
        indicates higher layer protocol (mostly IP but others possible, e.g., Novell IPX, AppleTalk)
      - CRC
        
        cyclic redundancy check at receiver
        
        error detected: frame is dropped
      - Connectionless
        
        no handshaking between sending and receiving NICs
      - Unreliable
        
        receiving NIC doesnt send acks or nacks to sending NIC
        
        data in dropped frames recovered only if initial sender uses higher layer rdt (e.g., TCP), otherwise dropped data lost
      - Ethernet 's MAC protocol
        
        unslotted CSMA/CD wth binary backoff
    - - Characteristics
        
        plug-and-play
        
        switches do not need to be configured
        
        link-layer device
        
        store, forward Ethernet frames
        
        examine incoming frame’s MAC address, selectively forward frame to one-or-more outgoing links when frame is to be forwarded on segment, uses CSMA/CD to access segment
        
        Transparent
        
        hosts are unaware of presence of switches
      - Multiple Stimutaneous Transmission
        
        switches buffer packets
        
        Ethernet protocol used on each incoming link, but no collisions; full duplex
        
        hosts have dedicated, direct connection to switch
      - Switching Forwarding Table
      - Filtering/Forwarding
      - Interconnection Switch
  - - - Dynamic Mebership
        
        ports can be dynamically assigned among VLANs
      - Forwarding between VLAN
        
        done via routing (just as with separate switches)
        
        in practice vendors sell combined switches plus routers
      - Traffic Isolation
    - - Trunk Port
        
        carries frames between VLANS defined over multiple physical switches
        
        frames forwarded within VLAN between switches can’t be vanilla 802.1 frames (must carry VLAN ID info)
        
        802.1q protocol adds/removed additional header fields for frames forwarded between trunk ports