Chapter 2 Flashcards
Shannon-Hartley Thm.
Upper bound to capacity of a link in terms of bits per second as a function of signal to noise ratio
C = B * log2(1 + S/N)
* S = Signal power
* N = Average noise
* B = Bandwidth of channel
Medium - Characterise
- Copper wire
- Optical / fibre
- Air
Frequency - Characterise
Hz
Wavelength
Distance min and max of wave in metres
Encoding
Binary data on a signal
* Bits travel between adaptors
* Signal travel between signalling components
Problems of Non Return to Zero
- Baseline wander
- Receiver keeps average of signals seen
- uses average to distinguish 0 or 1
- Too many 0s or 1s could lead to inaccuracy
- Clock recovery
- Frequenct transtions are needed for clock recovery
- Sending & decoding done by clock
- Every clock clock cyle a sender transmits a bit and receiver bit
- Sender and receiver has to be insync
Non Return to Zero Inverted
- Sender makes a transition from current signal to encode 1 and stay at 1
- Solves consecutive 1s
Manchester encoding
- Merge clock XOR of NRZ
- for clock: one high and low pair is a cycle
- 0 : low to high
- 1: high to low
Problems with Manchester
Doubles the rate at which signal transitions are made
* The receiver has 1/2 the time to detect each pulse
Baud rate
The rate of change in signal
4B/5B encoding
- Insert extra bits into bit stream to break up long 0s or 1s
- Every 4 bits are encoded in 5 bits
- Each 5B has no more than 1 leading 0
- Each 5B has no more than 2 trailling 0s
- No pair of 5 bit codes have more than 3 consecutive 0s
Idle line 4B/5B
11111
Dead Line 4B/5B
00000
Halt Line
00100
Frames
Blocks of data
Byte Oriented Protocol
View each frame as a collection of bytes rather than bits
Binary Synchronous Communication (BISYNC)
- SYN Character - 8 bits
- SYN Character - 8
- Start of Header (SOH) - 8
- Header
- Start of Text (STX) - 8
- Body
- End of text (ETX) - 8
- Cyclic Redundancy Check (CRC) 16
Point-to-Point Protocol (PPP)
Commonly used over internet links which use sentinel approach
* Special start character: 01111110 : Flag - 8
* Address - 8
* Control - 8
* Protocol for demux: IP/IPX - 16
* Payload
* Checksum - 16
* Flag - 8
Digital Data Communication Message Protocol (DDCMP)
Byte counting approach
If count is corrputed - framing error
* SYN - 8
* SYN - 8
* Class - 8
* Count - 14
* Header - 42
* Body
* CRC - 16
High Level Data Link Control (HDLC)
- Beginning and ending sequences
- 01111110
- Frame:
- Beginning Sequence - 8
- Header - 16
- Body
- CRC - 16
- Ending Sequence - 8
- On sender side
- If 5 1 bits are being sent a 0 is inserted
- On receiver side
- if 5 bits read
- if next bit is a 0 = body
- if next bit is 1 = either end sequence or error and must discard
Two dimensional Parity
- Based on parity
- Adding 1 bit for 7 bits to make it even or odd
- Catches 1, 2, 3 and most 4 bit errors
- Each 7 bits has a parity bit, and there is an additional parity byte at the end
Internet Checksum Algorithm
- Add up all words transmitted & transmit sum
- Sender & receiver do the same calculation then compare
- If different then there is an error
- Data checksummed as a sequence of 16 bit integers
- Add them together using complement arithemetic
- 16 bit number is the checksum
Cyclical Redundancy Check (CRC)
- Reduce the number of bits
- Maximise protection
- Uses bit string that represent polynomials
- M(X) is the message polynomial
- C(X) is the generator polynomial
- If M % C produces a remainder then there is an error
- M comes from the message itself
- C has to be agreed on between sender and receiver
Error handling with CRC
- if M % C does produce a remainder of 0, a bit error could have just gone unnoticed
- For single bit errors: X^k and X^0 must have non zero coefficients
- Double bit: C(X) has a factor of at least 3 terms
- Any odd number of errors : C(x) contains (k+1)
- Any burst error < k bits
Acknowledgement (ACK)
a small control frame that a protocol sends back to its peer saying that it has received an earlier frame
Timeout
If the sender does not receive an ACK after a reasonable amount of time, then it retransmits the original frame. This action of waiting a reasonable amount of time is called a timeout.
Automatic Repeat Request (ARQ)
The general strategy of using acknowledgements and timeouts to implement reliable delivery is sometimes called automatic repeat request
Stop and Wait Protocol
- After transmitting one frame, the sender waits for an ACK before transmitting the next frame.
- If the ACK does not arrive after a certain period of time, the sender times out and retransmits the original frame.
Problems with Stop and Wait
- If the receiver receives the a frame but the ACK does not return in time or simply does not return, a copy of the frame will be sent
- A 1 bit header is required to say whether or not the frame is a copy or not
- Only allows for one outstanding frame which results in a severe misuse of the link capacity
Sliding Window Sender
First, a sender assigns a sequence number, denoted SeqNum, to each frame. The sender maintains three variables:
1. Send window size (SWS), gives the upper bound on the number of outstanding (unacknowledged) frames that the sender can transmit.
2. LAR denotes the sequence number of the last acknowledgement received.
3. LFS denotes the sequence number of the last frame sent.
The sender also maintains the invariant:
LFS - LAR <= SWS
- When an acknowledgement arrives, the sender moves LAR to the right, thereby allowing the sender to transmit another frame.
- Also, the sender associates a timer with each frame it transmits, and it retransmits the frame should the timer expire before an ACK is received.
- Notice that the sender has to be willing to buffer up the SWS frames since it must be prepared to retransmit them until they are acknowledged.
Sliding window Receiver
The receiver maintains the following three variables:
1. RWS, receive window size, which gives the upper bound on the number of out-of-order frames that the receiver is willing to accept.
2. LAF denotes the sequence number of the largest acceptable frame
3. LFR denotes the last frame received.
The receiver also maintains the following invariant:
LAF - LFR <= RWS
- If SeqNum ≤ LFR or SeqNum > LAF, then the frame is outside the receiver’s window and it is discarded.
- If LFR < SeqNum ≤ LAF, then the frame is within the receiver’s window and it is accepted.
Issues with Sliding Window Protocol
- Timeout = Amount of data in transit decreases
- Packet Loss = Pipe is no longer fulle
Solutions to Sliding Window Protocol
Negative ACK
* Sends ACK for packets received in order when out of order frame arrives
Additonal ACK
* Send additonal ACK for frame before the one are looking for = Packet Los
Selective ACK
* ACK Frames Received
* Sender knows packet lost
* Can keep the pipe full
Ethernet
- Uses CSMA/CD tech
- A multiple access network
- “Carrier Sense” means that nodes can distinguish between a busy and an idle link
- “Collision Detect” means that a node listens as it transmits and can therefore detect when a frame it is transmitting has collided
Transceiver
- A small device directly attched to the line
- Detects when the line is idle and then drives the signal
- Connects to an ethernet adaptor
Repeater
- Multiple ethernet segments can be joined together by repeaters
- Forwards signals like an amplifier
- Understands only bits
- No more than 4 repeaters are allowed in between hosts
Multiway repeater
- Also known as a hub
- Repeats whatever it hears onto other ports
Ethernet Adaptor
Protocol implemented here
Directly connects to the host
Physical Properties of Ethernet
- Any signal placed on ethernet is broadcast to all other nodes
- Signal is also propagated both ways
- Terminators attach to the end of each segment to absorb the signal
- Uses Manchester encoding
- 4B/5B or 8B/10B scheme used today for faster speeds
10Base2
- Thinner cable that coaxial
- 10 : Operates at 10Mbps
- Base : Baseband system
- 2 : Segment no longer than 200m
10BaseT
- T: Twister pair
- Limited to 100m
- Normally used for coming out of hubs
Media Access Control (MAC)
- Algo. that controls access to a shared Ethernet link
- Usually implemented on the hardware on the network adaptor
Frame Format - Ethernet
- Preamble: Allows receivedr to sync with the signal - 64
- Host & Dest Addr. - 48 each
- Packet Type - 16
- Body - 46-1500B
- CRC - 32
Ethernet Addresses
- Each host on Ethernet has a unique address
- Belongs to the adaptor
- 6 pairs of hexadecimal numbers
- Each manufacturer has a unique prefix
Sending frames on Ethernet
- Each frame sent on Ethernet is received by every other adaptor
- Each adaptor only passes the frames sent to it onto the host
Unicast
- Consists of all ones
- All adaptors send this message to host
Multicast
- First bit is a 1
- Host can program its adaptor to accept same set of multicast addresses
Ethernet Transmitter Algorithm
- When a frame needs to be sent, if the line is in idle, send immediately
- When busy, wait for idle
- Since no central control, collisions can exist
- The moment an adaptor realises there has been a collision it stops transmission
- Sends 96 bit runt frame if the two hosts are close
- Worst case is 512 bits
Transmitter Algorithm
- begins send at time t
- d denotes the one link latency
- Just before A’s frame arrives at time t + d
- B’s frame will cloos with A’s
- B will will detect this
- B will send the jamming sequence
- A will not know about the collision until it reaches it
- This will happen at t + 2d
- A must continue to transmit to pick up the collision
Exponential BackOff
Once an adaptor has detected a collision & stopped its transmission it waits and tries again. The wait time doubles every time
Experience with Ethernet
- Work best under light load
- Used in a conservative way 200/1024 hosts
- RTT time usually much faster than the max 51.2 micro seconds
- Easy to administer and maintain
- Inexpensive
- Each to add new host
- No switches that can fail
Wireless Links
- All share the same medium
- Share efficiently without interfering
- Specific bound with freq. ranges etc
- Allocated use cases
- Government
- Radio
- Individual
- License Exempt
Spread Spectrum
The idea behind spread spectrum is to spread the signal over a wider frequency band, so as to minimize the impact of interference from other devices.
Frequency Hopping
is a spread spectrum technique that involves transmitting the signal over a random sequence of frequencies.
The sequence of frequencies are not truly random but is instead computed algorithmically by a pseudorandom number generator. The receiver uses the same algorithm as the sender and initializes it with the same seed; hence, it is able to hop frequencies in sync.
Direct Sequence
- Adds redundancy for greater tolerance of interference.
- Each bit of data is represented by multiple bits in the transmitted signal so that, if some of the transmitted bits are damaged by interference, there is usually enough redundancy to recover the original bit.
- For each bit the sender wants to transmit, it actually sends the exclusive-OR of that bit and n random bits.
- As with frequency hopping, the sequence of random bits is generated by a pseudorandom number generator known to both the sender and the receiver.
- The transmitted values, known as an n-bit chipping code, spread the signal across a frequency band that is n times wider than the frame would have otherwise required.
Base Station
- Usually has no mobility but has a wired connection to the Internet or other networks.
- The node at the other end of the link relies on its link to the base station for all its communication with other nodes.
Mesh
- In a wireless mesh, nodes are peers; that is, there is no special base station node. Messages may be forwarded via a chain of peer nodes as long as each node is within range of the preceding node.
- This allows for shorter-range technology to extend its range and potentially compete with a longer-range technology.
- Meshes also provide fault tolerance due to the multiple routes for a message to get from one point to the other.
802.11
- Known as wifif
- Made for limited geographical area
- Has secuirty mechanisms
Physical Properties of 802.11
- standard defined two radio-based physical layers standards, one using frequency hopping (over 79 1-MHz-wide frequency bandwidths)
- the other using direct sequence spread spectrum (with an 11-bit chipping sequence).
- Both provided data rates in the 2 Mbps range
Physical Properties of 802.11b
- Using a variant of direct sequence, 802.11b provides up to 11 Mbps.
- These three standards operated in the license-exempt 2.4-GHz frequency.
Physical Properties of 802.11a
- Delivers up to 54 Mbps using a variant of FDM called orthogonal frequency division multiplexing (OFDM);
- 802.11a runs in a license-exempt 5-GHz band.
- On one hand, this band is less used, so there is less interference.
- On the other hand, there is more absorption of the signal and it is limited to almost line of sight.
Physical Properties of 802.11g
- Also uses OFDM,
- delivers up to 54 Mbps, and is backward compatible with 802.11b but returns to the 2.4-GHz band.
Physical Properties of 802.11n
- achieves considerable advances in maximum possible data rate using multiple antennas
- allowing greater wireless channel bandwidths.
- The use of multiple antennas is often called MIMO for multiple-input, multiple-output.
Exposed Node Problem
- Over ethernet, all nodes are aware of other nodes
- Over wireless they are not
- If not, they cannot detect collisions properly
- Two nodes can send a frame but unknowingly cause a collision and not know about it
CSMA/CA - WiFI
- Collision Avoidance
- Uses Multiple Access CA
- Sender & Receiver first exchange frames before sending data
- Sender sends a Request to Send
- How long the medium should be held for
- Receiver replies with CTS
- Echoes the length back
- If a node sees the CTS it is too close and must wait
- If it sees the RTS and not the CTS it is not close enough = safe to trasnmit
- Use ACK to be able to see if a collisions has happened, wait for ACK, otherwise collision
Distribution System
- Not all nodes are equal
- Some are allowed to roam
- Others are called access points
- Joined by a DS
Scanning
- The node sends a Probe frame.
- All APs within reach reply with a Probe Response frame.
- The node selects one of the access points and sends that AP an Association Request
frame. - The AP replies with an Association Response frame.
Whenever a node acquires a new AP, the new AP notifies the old AP of the change
Active Scanning
- Node constantly sends Probe frame to choose best AP
Passive Scanning
- AP sends BEACON frame that advertises the capabilites of the AP
- Node changes AP by sending an Association Request
Frame Format -WiFi
- Source and Destination Addr. - 48 each
- Data - up to 2312 bytes
- CRC - 32
- Control Field - 16
- RTS/CTS : Used by scanning - 6
- ToDS - 1
- FromDS - 1
- ToDS and fromDS used to allow for frames to pass through the DS from one AP to the next
Bluetooth
- Operates on license exempt
- Very short range
- Uses PAN (Personal Area Network)
- Any communication is between master and slave
- Uses frequency hopping
ZigBee
- Like Bluetooth
- Very low power and low bandiwdth
Cellular Networks
Use base stations connected to a wired network called Broadband Base Units
User equipment
Mobile devices that connect to cellular
Evolved packet core
Set of BBU’s anchored at an APC
Contains:
* Mobility Management Entity
* Home Subscriber Server
* Session/Packet Gateway
Radio Access Network
The wireless network served by the EPC
Mobility Management Entity
Tracks and manages the movement of UEs throuhgout the Radio Access Network
Home Subscriber Line
Database for subscriber related info
Session/Packet gateway
Pair processes & forwards packets between the Radio Access Network and the internet
Cell
The BBU’s antenna Area
Handoff
From one BBU to another BBU
Passive Optical Network
- used to deliver fibre based broadband to houses & businesses
- Uses point-to-multipoint
- ISP - 1024 homes
- Uses splitters
Optical Line Terminal (OLT)
Framing happens at the ISP on an OLT
Optical Network Unit
The end points are ONUs
Downstream from PON
- Starts at OLT
- Send to ONU
- Dropped if not meant for it
Upstream from PON
- Each ONU gets time to transmit periodically
- A single OLT is in charge of round robin time allocating for each ONU
