Test 2 Flashcards
What is the Sliding Window Algorithm: Sender- Variables
Variables:
send window size (SWS) : the upper bound on the no. of un-ACK frames the sender can trans
- last ACK received (LAR) :
- last frame sent (LFS) :
- expiry timer : one for each frame sent, starts decr-ing when sender trans
- Relationship between variables : LFS - LAR <= SWS
What is the Sliding Window Algorithm: Sender-Process
Process:
- Sender assigns a sequence number (seqNum) to each frame
- When an ACK arrives, sender incr LAR. Sender can now send another frame
- If a frame expiry timer expires, sender retrans frame and re-starts timer
- requires buffer size of (frame_size x SWS)
To prevent To prevent network congestion and not to over-run the receiver, there can be
at most how many outstanding messages, for Sliding window?
SWS (Sender Window Size)
What is the Sliding Window Algorithm: Receiver- Variables
Receiver keeps the following vars:
- receive window size (RWS) : the upper bound on the no. of out-of-order frames the receiver is willing to accept
- largest acceptable frame (LAF) :
- last frame received (LFR) :
- Relationship between variables : LAW - LFR <= RWS
- seqNumToACK : the largest seq no. not yet ACK by receiver (aka ALL frames <= this have been received and ACK)… when sent by receiver, the receiver is ACK the receipt of all frames up to that seq num… this is a cumulative acknowledgement
What is the Sliding Window Algorithm: Receiver-Process
- When receiver gets a frame and seqNum <= LFR or seqNum > LAF [aka frame is outside the receiver’s window], the receiver will discard the frame
- When receiver gets a frame and LFR < seqNum <= LAF [aka the frame is within window], frame is accepted.
- After a frame is accepted, receiver will send a seqNumToACK in an cumACK to sender. Then sets LFR = seqNumToACK and LAF = (LFR + RWS)
- actually, this step may be skipped sometimes
Sliding Window: When timing out, should the sender retransmit everything from LAR+1 up
to LFS, or just retransmit LAR+1?
Both things will work, however, the general consensus is just to retransmit LAR+1 if RWS =
SWS.
If RWS = 1, then you might as well retransmit everything from LAR+1
up to LFS.
Sliding Window (cumulative ack)-- Sender Event : if LFS < LAR + SWS What is the response?
resp: LFS := LFS + 1; send frame(LFS) to receiver
Sliding Window (cumulative ack)- Sender Event: receive ack(i) from receiver What is the response?
resp: LAR := max(LAR, i)
Sliding Window (cumulative ack)-- Sender Event: if LAR < LFS What is the response?
resp: send frame(LAR + 1) to receiver
Sliding Window (cumulative ack)-- Receiver Event: receive frame(j) from sender What is the response?
if j < NFE
then akn := true {old message}
elseif j ≥ NFE + RWS
then skip {no buffer space}
elseif NFE ≤ j < NFE + RWS
then rcvd[j mod RWS] := true; {place data in buffer}
while rcvd[NFE mod RWS] do
{deliver frame(NFE) }
rcvd[NFE mod RWS] := false;
NFE := NFE + 1;
akn := true
end while
end ifCumulative acknowledgment with small sequence number and message reorder in the Sliding Window protocol:
Does not work.
Individual Acknowledgment with small sequence number and message reorder in the Sliding Window Protocol:
Does Work.
In Cumulative Acknowledgement, at all times:
within(LAR+r1, NFE, LFS+r1) AND within(LAR, LFS, LAR+rSWS)
For Cumulative Acknowledgement w/ bounded seq Nos.,
to prevent confusion at the receiver:
r >= SWS + RWS
ALOHA: Maximum Propagation Time equation:
Tp = (maxDistanceBetweenStations)/(SignalPropagationSpeed)
ALOHA: Back-off time equation:
TB = (ARandomNumber:R)x Tp
or
R x Tfr(Average transmission time for a frame).
ALOHA: Average Frame Transmission Tim Equation:
NumOfBitsperFrame/kbps of the channel.
ALOHA: Throughput for Pure ALOHA
S = G x e^(-2G) G = the average number of frames generated during an interval of size Tfrs
ALOHA: Throughput for slotted ALOHA
S = G x e^(-G) G = the average number of frames generated during an interval of size Tfrs
Ethernet: What does a repeater do?
Amplifies digital signals.
Ethernet: How many repeaters are allowed between nodes?
4
Ethernet: What is the maximum number of nodes per ethernet?
1024
In Ethernet, why can you almost immediately detect a collision?
Because the channel is being listened to while transmitting.
IEEE 802.11 Addressing: 1. ToDS = FromDS = 0
No APs are involved
A1 = DA
A2 = SA
IEEE 802.11 Addressing:
2.
ToDS = 1
FromDS = 0
from the station to its AP
A1 = R-APA
A2 = SA
A3 = DA
IEEE 802.11 Addressing:
3.
ToDS = 1
FromDS = 1
from one AP to another, in case AP’s are connected also via wireless A1 = R-APA A2 = T-APA A3 = DS A4 = SA
IEEE 802.11 Addressing:
4.
ToDS = 0
FromDS = 1
from the AP to one of its stations A1 = DA A2 = T-APA A3 = SA A4 =
IEEE 802.11: Frequency Hopping Spread Spectrum
Transmit of a random sequence of frequencies, hopping from on frequency to another I a random way.
Synchrony is maintained because send and receiver know a pseudorandom number generator and Speed.
First 802.11 standard used 79 1MHz-wide frequency bands.
IEEE 802.11: Direct Sequence Spread Spectrum (DSSS)
For each bit, send XOR of that bit and n random bits(n-bit chipping code). 802.11 defined an 11-bit chipping code.
IEEE 802.11: Direct Sequence Spread Spectrum (DSSS)
For 1Mbps data rate:
Ouput: 11 Mbaud/sec
Modulation - 2 phases BPSK, 11Mbits/sec (physical bits)
11 chips/bit - output 1 Mbit/sec (data bits).
IEEE 802.11: Direct Sequence Spread Spectrum (DSSS)
For 2 Mbps data rate:
Ouput: 11 Mbaud/sec
Modulation - 4 phases, QPSK, 2 bits/baud. i.e. 22 Mbits/sec(physical)
11 chips/bit - output is thus 2 Mbits/sec(data)
Common Switching Methods:
Datagram
Source Routing
Virtual Circuits
Datagram Switching Facts
Also known as connectionless model
no connection setup phase.
Switches maintain forwarding/routing tables.
Uses routing protocols to learn routing tables.
Fault tolerant against line/node failures
Source Routing Facts
Sources provide info for switching at every switch.
Disadvantages:
The source needs to know the network topology
headers can be very long.
Virtual Circuit Switching
Connection-oriented Model
Explicit connection setup/tear-down phase
Packets follow the same route as setup message.
Switches maintain a table of:
VC in use?
Output port
Output VCID
Is there a way to determine which connection a datagram belongs to?
NO
Which type of switching is it easier to guarantee throughput to each connection, VC or datagram
VC. Serve each VC on an output line using round-robin.
In Datagram Switching, is there a mechanism to inform the switch o the QoS desired.
NO.
IEEE 802.11: What is the basic idea behind Spread Spectrum and what are the general methods.
spread signal over wider frequency band than required
originally designed to thwart jamming (now used to minimize interference from other devices)
Two general methods:
Frequency Hopping
Direct Sequence
Why is the Spanning Tree Algorithm implemented in Extended LANS
To prevent loops in the network.
Ethernet Switching uses what kind of routing?
Datagram Switching.
Why is the Spanning Tree Algorithm implemented in Extended LANs?
To prevent loops in the network.
Ethernet Switching uses what kind of routing?
Datagram Switching.
How are Designated Bridges(DB) selected in the Spanning Tree Algorithm?
The bridge that is the closest to the root. In case of tie, smallest ID bridge wins.
