Background. Problem. Arrange two machines to talk to each other. What do we need to accomplish this? A.

Must have a physical medium (phone lines, cables, wireless) transmitting analog signals. B. Need converter from bits p analog signals and the reverse. Modulation/demodulation. C. How do we send bits across? As a stream? As a sequence of frames? D. Environment is noisy. Thered be bit inversions at the reception end. We need a way to detect errors (Error detection). What do we do next after error is detected? Options: (1)Discard the chunk thats damaged. (2) Request for a new chunk. (3) Correct the damaged chunk if possible (Error correction).

E. What if we want to connect more than two machines in a networked mode? Shared access of a single medium (Multiple Access problem). Who gets access to the medium? When and how? How do we resolve contention problem? Modulation/Demodulation problem: An encoding issue. How to encode bits 0 and 1as analog signals? Some sample schemes. Scheme 1: NRZ (Non-Return to Zero)

A zero is sent as a low voltage pulse and a 1 as a high voltage pulse. Used in RS-232. Biggest problem: DC component and practically no clock recovery. Sensitive to polarity. Scheme 2: NRZI (Non-Return to Zero Inverse)

A 0 = No change in the level (maintain previous level)

A 1= If the current state is low, encode 1 as a high. If the current state is high, encode 1 as a low. Used in USB and FDDI. Differential code on adjacent transitions. Better noise immunity. Insensitive to polarity. Scheme 3: Manchester Encoding

A 0 = high to low transition as [10] 1 = low to high transition as [01] Used in Ethernet. Provides mid-pulse clocking transition, hence, self-clocking code. No DC component. Error detection is easier.

Scheme 4: 4B/5B encoding.

4 consecutive bits of data byte 5 bits of p transmission characters. In this encoding, long sequences of 0s or 1s does not occur in transmitted stream through extra redundancy. There are other similar encodings such as IBMs 8B/10B encoding (used in ATM, 10 Gigabit Ethernet, Fiber channels, ..) Framing Problem: Transmit a stream of bits (such as a file) over a noisy medium. Options. 1. Transmit one bit per frame. (Unacceptable. Heavy overhead) 2. Transmit n bits per frame. Find the optimal n. Every frame must have
Flag Address Control Data CRC Flag

Examples of framing protocols PPP (Point-to-Point Protocol), HDLC (High-level Data Link Control). Flags serve as BEGIN/END markers and are typically the bit string 0111 1110 Bit-stuffing problem. Every time a sequence of 5 1s is observed in the text to be transmitted, sender inserts a 0. Symmetrical response from the receiver. Error detection. Error detection encoding allows us to detect one or more errors in the received data. Some typical approaches. Single Parity check codes. How efficient is it? Note that we can always detect a single bit error with an added parity code. Assume BER p ! 10 4 . p(single bit error) ! p p(no error in transmitted bit) ! 1  p

p(undetected error in a 8-bit transmission) ! 1  ( 1  p )8 ! 7.9 v 10  4

Now, we add 1 parity bit and transmit 9 bits as a bunch. Now,

p(no error in single bit) ! 1  p p(no error in 9-bit bunch) ! ( 1  p )9 p(single error in 9-bit bunch) = 9 p(1-bit error) p(other 8 bits ok) ! 9 p( 1  p )8 p(undetected error in a 9-bit bunch) = = 1 p(no error in 9-bit bunch) p(single error in 9-bit bunch) ! 1  ( 1  p )9  9 p( 1  p )8 ! 3.6 v10 7 At least three-fold improvement. Single parity bits are used for asynchronous, character oriented transmissions. Block parity codes provide additional protection. To compute Hamming Code for a given bit-stream check
http://www.cs.fiu.edu/~downeyt/cop3402/hamming.html

Cyclic-Redundancy Check bits (CRC bits). Just the raw mechanics here. Figure out the rest of it. Given a bit string, we obtain its equivalent polynomial representation first. e.g. message string: 1 0 0 1 0 0 1 1 1 0 1 is equivalent to x 10  x7  x 4  x 3  x 2  1 . Let this be M(x). Let the G(x) be a given generating polynomial agreed by both sides (protocol issue). Let R(x) be the remainder polynomial if M(x) is divided in a modulo2 arithmatic by G(x). Then, transmitter obtains R(x) such that
M Message : G ( x ) | M ( x )  R( x )

and transmits the relevant bits corresponding to R(x) in addition to M(x). Thus, the protocol requires

Sender Transmit M(x), R(X)

Receiver

Try to divide M(x)+R(x) by G(x) No error. If no remainder upon division,

What if it cant be exactly divided? Error detected. Explore the implications. y A single bit error is always detected. y For burst error of length k e r = degree of G(x) It is detected so long x is not a factor of G(x) Note that T ( x ) ! M ( x )  R( x ) is always divisible by G(x) Suppose, the transmitted error is E(x) i.e. T ( x )  E ( x ) is transmitted. How do you handle this case? What if its not divisible by G( x )? To detect and correct? Hamming code. Or some other clever coding technique. Ideal coding is the one that

provides max distance between any two acceptable codewords. Notion of Hamming distance. Here, one inserts multiple parity bits in the codeword before sending. An example. Transmit: P P2 m1P3 m2 m3 m4 P4 .. (a 7-4 code) 1 mi : message bit Pk : parity bit Each parity bit checks some specific message bits. How do we consistently discover which parity bits influence which message bits? Take a message bit occurring in he position i. Express the decimal i in binary. Any 1 appearing in the kth position of the binary string suggests that the corresponding Pk parity component influences it. e.g. m1 appears in position 3. Since 3 = 1+2, P P2 m1 (read the arrow as the verb 1 affect) similarly, m2 in position 5 is P P3 m2 1 also,

P2 P3 m3 P P2 P3 m4 1 and, so on. Combining all these we get in modulo-2 arithmetic (for a 7-4 code, for instance)

P ! m1 m2 m4 1
P2 ! m1 m3 m4 P3 ! m2 m3 m4

Read Tanenbaum more for polynomial and CRC codes. ARQ/FEC Simplest form of error recovery: via ACK(nowledgement)/NACK Stop & Wait protocol: If a packet P is not ACKed by the receiver in time (timeout), resend a copy of the packet. ARQ = Automatic receive ReQuest. Needs sequence number to discern duplicates.

ARQ efficiency = 1 packet/d secs. (Too slow) Where d= packet transmission time + propagation time + Latency at the receiver + ACK transmission time + propagation time = RTT (Round Trip time) Ideally, one should send as many packets possible within d (keeping them unacknowledged). If B is the effective channel bandwidth, best case scenario is to keep the pipeline filled with B v d bits. If the packet Bd size is S bits, we should send n ! pkts before S seeking ACK return. In that case max throughput is B/ S. This extended to Sliding Window Protocol. See Tanenbaum. We fill up the window with pkts and then let it slide by one notch after ACK is recvd. The receiver makes the complementary move. Interesting issue: ARQ is not always feasible. Take the case of a submarine when its hiding. In that case, FEC may be the only approach other than discarding damaged pkts. This calls for a mixed, adaptive protocol. Indiscriminate FEC may be too expensive.

Shared Media Access Core issue in networking. Access may be contention free (CF) or contention based (CB). A contention free access when traffic load is heavy, a contentionbased access when traffic load is light. Ideal situation: Instead of having a dedicated CF or CB network, how about making it adaptive so that it automatically switches to CF when traffic is light and to CB when traffic is heavy? Protocols that allows access to a common medium to a set of participating stations is a MAC protocol. See Tannenbaum (pp ) Medium access via contention A. Aloha Protocol. Simplest of all. Transmit when you need to transmit. If collisions with other transmissions, try again. Truly a random access!
Station 1 Station 2 Station k Station M

A Single passive channel. Radio-channel or a Coaxial cable

Assume, an infinite population of stations transmitting frames.

propagation time over the channel) a frame. S = average number of successful frame transmission per frame transmission time X e 1.0 G = average number of offered frame transmissions per frame transmission time X . Usually u 1.0 G comprises new frame transmissions + retransmissions.
frame frame frame

frame

frame

frame

frame

frame

frame

frame

Not all frames survive! A frame is vulnerable for a period of 2X period in Pure Aloha after it is transmitted. Therefore, for a frame to survive (in Pure Aloha) there mustnt be any transmission within this period.

t0  X
A frame A frame A frame

t0 t0  X

A frame A frame
Vulnerability Period =

2X

Given that G frames is the load (number of attempted transmissions),

where P0 ! prob (no other frame is transmitted during its vulnerable period) Now, as per Poisson arrival of frames into the network, probability of k frames appearing in one frame time X is G k e G (substitute G for PX ) p( k frames in X ) ! k! Therefore, p( 0 frame in one X period) ! e-G

Probability P0 of 0 frame in two frames time =

e  2G .
Thus for a Pure-Aloha, throughput equation is

S ! Ge  2G

S max ! 0.184

G=0.5

B. Slotted-Aloha Protocol. Attempt to transmit only when a time-slot appears. Time-slot width is X secs. Vulnerability period in slotted-Aloha: X secs. Therefore, P0 ! probability of a zero frame transmitted during its vulnerable period = e G Slotted-Aloha throughput: S ! GeG

0.367 Slotted Aloha

0.184 Pure Aloha

On average frame-delay. On pure-Aloha , number of attempts per successful frame transmission is G ! e 2G S G 1 S For each retransmission attempt, there would be a random back-off period B units plus a transmission delay of X units. Therefore, every frame suffers an average transmission delay of Number of retransmissions per frame is

T ! X  ( e2G  1 )( X  B ) B depends on back-off strategy. On no back-off (persistent scheme) policy Tno _ backoff ! X e2G In terms of unit frame transmission time, the normalized delay is ! e 2G  ( e 2G  1 ) B T X C. Carrier-sense protocols. Sense the medium first. If a transmission is in progress, do not transmit. Reschedule transmission till the cable appears idle. This is a single-hop CSMA strategy. Some more texture. Assume medium access is through available time-slots of duration X . Several transmission strategies: 1-persistent CSMA: If a time-slot is sensed idle or found idle, transmit on the next slot with absolute certainty.

p-persistent CSMA: If a time-slot is sensed idle or found idle, transmit on the next slot with probability p. 0-persistent CSMA: If a time-slot is sensed idle or found idle, do not transmit on the next slot. Let this one go. Attempt to transmit on the next one if sensed idle. Non-persistent CSMA: Just like 0-persistent, but the Station doesnt monitor the channel. Itd attempt to transmit on the second coming slot.

Used

Used

Used

Idle

???

Train of time-slots What do you do now? Grab it?

On a multihop CSMA, one may discover an idle channel even though it may not be (hidden terminal problem) truly idle. Rude-CSMA is one possible alternative.

Nelson & Kleinrock, Rude-CSMA: A multihop channel-access protocol, IEEE Trans. On Communications, vol. com 33, August 1985
Station 1 Station 2 Station 3

Station 3 is invisible to Station 1

Station 1 may sense Station 2 idle, but in reality .

Hidden terminal problem decreases CSMA throughput on a multihop net. Rude-CSMA attempts to recover the lost throughput by attempting to transmit it sometimes even if the channel is sensed busy. Motivation: Busy channel around the transmitter doesnt always mean the intended receiver is busy. So, lets be rude and it might pay!

Station 1

Station 2

Station 3

Station 4

Station 1 may sense a lot of traffic between Station 3 and station 4. But that does not mean Station 2s neighborhood is busy. Carrier sense multiple access degrades to that of the ALOHA protocol in ad hoc networks because of this.