cs398 Lecture Notes
Spring 2000
Week 3, Thursday

For today you schould have made a second pass through Sections 2.1
through 2.5.

You should also have skimmed 2.6 through 2.8 so you have an idea
how media access control works.

And, you should have written answers to questions
2, 3, 4, 5, 8a and 15 on pages 156-158.

For next Tuesday, you should read the rest of the Chapter
and write answers for Questions 19, 20 and 26(a)

You should also read and think about questions 22 and 23.

We will have an exam next Thursday!


Error detection
---------------

How does the network detect bit and burst errors?

    (as opposed to what?)

parity checking:  count the number of 1s.  bit-stuff its parity

checksum: byte-stuff the sum (modulo 2^k) of each n bytes

	  (Page 96: add the word "not")


CRC
---

What you need to know:

1) mapping back and forth between messages and polynomials

M(x) contains n+1 bits, maps to nth order polynomial.

C(x) is a kth order polynomial (k+1 bits)

The thing we send is P(x), an (n+k+1)th order polynomial that
is divisible by C(x).

Receiver checks that P'(x) is still divisible by C(x).


Given M and C, how do we construct P?

1) The remainder of B/C is B-C (if B and C are the same order)

2) B-C is B XOR C (same condition)


Given these rules we can figure out how to do long division
on binary polynomials.


Now we have an algorithm for the sender:

1) T = multiply M by x^k

2) find the remainder when T/C

3) subtract the remainder from T to get P


Why does this work?

Choose C such that the probability that P+E is divisible by C
is small for common forms types of E.

P+E is divisible only if E is divisible.

For example, if E = x^i, then E cannot be divisible by C,
provided that the kth and 0th terms are 1.

Similar results:

1) if C has a factor with at least three terms, then we
catch all E = x^i + x^j

2) if C contains the factor (x+1), we catch any odd number
of errors

3) for any C we can catch an error burst with fewer than k bits
   (and most with more)


(Let's do problem 15 on page 158)


Error correction
----------------

Pros and cons of error detection vs. error correction.

Link characteristic that determines preference?


Reliable transmission
---------------------

How does the network deal with errors when it finds them?

Basic tool: automatic repeat request

1) receiver sends acknowledgements

2) sender retransmits after timeout (that's the "automatic" part)


Stop and wait
-------------

Sender sends one frame, waits for ACK.

What are the possible outcomes?

a) one frame, one ack (total = 2 RTT)

b) frame lost, resend after timeout (total = timeout + 2 RTT)

c) frame received, ACK lost, packet resent

d) frame or ACK delayed, received after timeout


How long should the timeout be?

In both (c) and (d) the receiver gets the same packet twice
in a row.  How does it know whether it is a resend or a
genuine duplicate?

What is the primary problem with Stop and Wait?

How can we calculate the number of frames necessary to
keep the pipe full?

What if frames are variable size?


Sliding window
--------------

Assume:

1) we know how many frames it takes to fill the pipe,
   and we want to make sure that under normal circumstances
   (no recent errors) it is full

2) the link delivers frames in order  (cf. TCP reliable delivery)


Sender:  window consists of packets that have been sent,
	 most of which have not been acknowledged

LAR = last acknowledged frame
LFS = last frame sent


Start by sending enough frames to fill the pipe.

When acknowledgements come in, tick them off.

If the LAR gets incremented, we can send another frame.


Receiver: window consists of the packets that we expect
	  are probably in flight

LFR: last frame received
LAF: largest acceptable frame


If we get a packet that is out of the acceptable window,
we drop it:

Primary reason: it might be a resend of a packet we already received

Secondary reason: we want to maintain the invariant that there
		  are at most SWS unacked packets in flight


Variations:

1) selective ACKS: dumb name... ACK it when you get it

   (what's the advantage?)

2) cumulative ACKS:  ACK 9 means we have received everything up to 9

   (what's the advantage?)

3) negative ACKS: if we get 7 before 6, we NACK 6

   (what's the advantage?)


Handling of sequence numbers.  Interesting.  Read all about it.


Concurrent Logical Channels
---------------------------

I think this is very cool.  The book's description is very
terse.

Assume that the bandwidth-delay product is 8 frame sizes.

We want to be able to have 8 frames in flight at a time.

We keep 8 stop-and-wait channels at the server.

Each keeps track of

1) busy or idle: that is, have you sent an unACKed frame?

2) sequence number of the current packet


For each frame that needs to be sent

1) find an idle channel

2) send the packet with the channel number and the sequence
   number for that channel

3) set the channel to busy


Receiver sends back and ACK with the channel and sequence numbers

When the ACK comes in

1) check the sequence number for the appropriate channel

2) if it matches, set the channel to idle


Overview of MAC
---------------

1) Ethernet: shared medium

   collision detection and probablistic, exponential backoff

2) Token ring: not physically a shared medium, but logically it is

   pass the conch

3) Wireless: definitely shared

   similar to Ethernet except collision detection is harder!

   hidden node problem