Data Link Layer

Concerned with the tranmission of "frames" between two directly connected IMP's. We follow [Tannenbaum]. Note that (prove for ec) -> +5 pts on next quiz!

IMP = interface message processor (nod or station)

DLL doesn't worry about which other IMP [network layer]

DLL doesn't worry about how to xmit bits [physical layer]

frame = block of data

frame -> sync bits, header, info field, error checking.

header -> kind, seq, ack.

seq = sequence number.

kind = classification

ack = acknowledge (used in two way communications)

DLL is layer 2

The DLL gets packets from the net layer (getp). It sends frames to the other DLL (sendf). The other DLL gets the frames (recf) and returns them to the higher net layer (givep). The receiver has a procedure called wait.

An unrestricted simplex protocol (protocol 1)->problem: could swamp the reciever, no error recovery A simplex stop-and-wait protocol (protocol 2)

With networks you must have distributed algorithms. The problem with simplex stop and wait, the return channel may have an error. Let s=sender, r=receiver
s, sends a frame to r.
r sends an ack to s but it is not recieved by s.
s times out and retransmits
r obtains 2nd copy of the frame
This is known as a duplication error!

To stop duplication errors we add sequence number, e.g. 0,1,2,3...

What is the smallest frame identifier we can use? We would like to use the min. number of sequence numbers. Could use 0,1,0,1... because of the stop and wait protocal.

Known as a "positive%20acknowledgement/retransmission%20protocal%20(par)" [Tanenbaum 89], or sometimes called "complete%20stop%20and%20wait" . This allows data to be transmitted in one direction (half duplex) over a noisy communication channel that garbles and loses frames.

If frame m is lost of damaged, the receiver will not ack and the sender keeps trying.

If the receiver gets the wrong seq number, it is rejected as a duplicate.

The sender waits for a positive ack before advancing to the next frame. It requires the timeout to be long enough to prevent premature times outs, to prevent dups.

The only ambiguity is between frame m and m+1. If the sender times out too early, while an ack is on the way a dup frame will be sent. The ack arrives and the sender is fooled into thinking the ack is for the frame just sent (not the dup). If the next frame is is lost, the sender will not try to retransmit and the protocol fails. PAR can deadlock if the sender times out too early.

Protocol 3 (par) postive ack/rexmit protocol

Sliding window Protocols

For TFTP [Stevens] the frames and acks are numbered. timeouts occur for any frame, frames are transmitted continuously. No deadlocks can occur. Sliding window protocols remain synchronized in the face of garbled or lost frames. They can handle premature timeouts.

In TFTP a seperate ACK is always sent when a frame arrives. This is a half-duplex xmission. If transmission were full-duplex, we could improve throughput via piggy backing.

This involves adding a frame ack code to the next outgoing frame. This means hold up the xmission of the ack till the next frame is ready. If we wait beyond the timeout, the rexmission occurs.

TFTP takes (with comments and command line processing) 2000 lines of C code.

The max sequence number is , where n=length of the ack field in the frame. For TFTP packets, an ACK takes 4 bytes. Two bytes for the op-code, two bytes for the sequence number. Data blocks may be 512 bytes long.

TFTP will run out of sequence numbers after bytes are sent without ack.

Stop-and-wait uses n=1 so that sequence number are 0 and 1.

A one Bit Sliding Window Protocol. This is stop-and-wait since the sender transmits a frame and waits for its ack. Protocal 4 withstands errors and timeouts

1-bit sliding window protocol. ack=#of last frm rcvd.

protocol fails if both xmit at same time, half the frames contain dups.

Go Back N Protocol

Suppose the transmission time required for a frame to arrive at the receiver plus the transmission time for the ack to come back is non-trivial.

E.g. a 50 kbps satellite channel could have a 500 ms round trip time. To xmit a 1000 bit frame takes 20 ms, but it is not until 520 ms that the sender gets an ack and so is blocked 500/520 = 96% of the time.

Let w=#of frames to xmit before blocking.

at 20 ms per frame and 500 ms/ack we should set w=(500+20)/20=26 frames (at least)

This is known as pipelining

let

b= channel capacity (bps)

l = frame size (bits)

R=round-trip propagation time (sec)

l/b=time to xmit a frame (sec)

U=channel utilization (efficiency)

In stop-and-wait, the line is busy for l/b seconds and idle for R seconds.

U varies in inverse proportion to the bR product.

The reciever in the data link layer is required to hand packets to the network layer IN SEQUENCE. If you pipe line then there may be problems:

* A frame is damaged...or lost
* Many frames may fall on the floor w/o feedback to the sender
* What should be done with frames following a damaged frame?

We have seen that TFTP can have 30MB in a pipe w/o repeating a sequence number...should I drop the pipe if I get a bad frame?

Go back N and Selective repeat are two solutions to these problems.

With go back n, the receiver lets all the bits coming out of the pipe fall on the floor, sending no acks. This corresponds to a window size of 1.

With selective repeat, only the bad frame falls on the floor, the rexmit takes a while, but when it does happen, an assembled in-order sequence is passed to the net layer. This corresponds to a window size of larger than 1. If the window is large (e.g. tftp) the buffer can be big (30 MB) esp if the time out time is long.

This is an example of trading space for bandwidth.

If MaxSeq=7 then
1. The sender sends frames 0-7
2. a piggyback ack for frm 7 arrives at the sender
3. the sender sends another 8 frms, again with seq#'s0-7
4. Now another ack for frame 7 comes in.

Question: did all 8 frames in the 2nd batch arrive, or get lost? There is no way to tell, so the number of outstanding frames must be <= MaxSeq.

Multiple timers are needed for multiple frames.

Selective Repeat

If the line is poor, the pipe line is big (like TFTP) and the timeouts large, you waste bandwidth.

To save the pipe, we rexmit selective frames. A list of frames is kept by the recvr. New frame are admitted. Dups are discarded. Frames arrive in any order, up to MaxSeq.

Problem: the sender sends MaxSeq frames, the rcvr acks are all lost...the sender rexmits and the rcvr gets dups.

Fix: let the window size = (MaxSeq+1)/2.

Only frames within the window are accepted.

If we piggyback on the reverse channel and traffic is light ack length will be long. In protocal 5, after MaxSeq frames, the protocol blocks. Protocal 6 sends a NAK to indicate chksum err.

In either net TCP does the flow control, connections, checkums, ack, timeouts, dup detecting and sequencing.

IP establishes message boundaries. UDP does this too.

IP and UDP are connectionless, unreliable datagram services. Therefore you choose TCP/IP or TCP/UDP [Stevens].

Protocol performance

Performance of the Stop-and-wait Protocol

An unrestricted simplex protocol has U=1 since sender runs flat out.

Suppose stop-and-wait has fixed-length frames and no piggybacking like Protocol 3 (par) postive ack/rexmit protocol.

NOTATION

Assume that the channel is perfect ( )

It takes F/C seconds to xmit a frame and F/C+I seconds for the frame to arrive and get serviced. In F/C + A/C +2I seconds the sender has finished processing the ACK.

Only D data bits were sent in 2I + (F+A)/C seconds.

for a perfect channel. Therefore H+A+2CI are the overhead in the protocol (which contribute nothing if the channel is error free).

Channels have errors, however. The sender timesout in F/C + T seconds, this uses F+CT bits of bandwidth.

Total channel cap. for R (=avg #bad frames) and 1 good one is

where

(1)

(2)

(3)

since . The avg number of transmissions per frame is

proof:

(3a)

(3b)

subst. (3b) into (3a)

(3c)

Q.E.D.

The average number of retransmissions per frame is one less, or:

(4)

using (4) and the fact that: Total channel cap. for R (=avg #bad frames) and 1 good one is

(5)

if the variance of I is low then

(6)

subst (6) into (5) gives:

(6a)

subst

(2)

into (6A) (prove for ec)

(7)

represents loss due to the header.

represents loss due to the errors

represents loss due to the stop-and-wait

To proceed further we need to make more assumptions.

Assume that the prob. of a bit error is independent and that it is E. Assume that the size of the ACK is the same as the size of the header A=H.

Then channel utilization is:

(8)

= prob of no errors for H=A bits in a row

= prob of no errors for F=D+H bits in a row

To maximize the channel utilization, we need to be given: header size (H), error rate (E), raw bandwidth (C) and timeout interval (T).

(9)

solve (9) for D to obtain:

(10)

For a small E,, , since D is an integer, we will round off at the end anyway. E.g.,

(11)

also, a small E means that both the 1 under the radical and the 1 following the radical can be ignored

(prove for ec)

(12)

=overhead from headers and timeouts. E.g., let H+CT=11, then plot D=f(E)

Here, x=E, as the line get better, D opt gets longer.

A high error rate lowers D to avoid the rexmission of long frames.

Let and

subst into

You get

prove (for ec)

(13)

Sample quiz question:

Frames of 1500 bits are send over a 2Mbps channel. Acks are piggybacked onto data frames, Headers are short and use 3 bit sequence numbers. Find the max U for stop-and-wait, protocol 5 and protocol 6.

Performance of the sliding window protocol

Assume that acks are piggybacked onto reverse traffic, so that the can be ignored. Assume that interrupt processing time is negligible so that interrupt and service time+prop. delay= .

Assume that the channel is error-free (E=0)

Case 1: The window is big enough to allow acks to return before the window is full. Frame xmit time = F/C, W= window size so in WF/C seconds an ack should return.

2I=time it takes to make a round trip so that F/C+2I= time it takes and ack to come back. So

and U is limited by the size of the Header

Case 2: The window is not big enough to allow acks to return before it is full. The sender must stop-and-wait for the first ack. It may then send one more frame, at which time the next ack arrives. Each cycle takes F/C+2I (which uses up F+2CI bits of bandwidth) and is carries WD data bits. Therefore:

if then (small window, no errors)

(prove for ec)

Case 3: Assume E!=0 (i.e. there are errors) and that the window is big enough to allow continuous xmission (with dups for correction) = 1/(1-L), L=prob that a frame or ACK is lost. To get W frames w/o error, you expect to xmit W/(1-L) of them.

If

Case 4: E!=0 and the window is small and so U drops by the retransmission factor (1-L).

If (small window, with errors)

* The length of a cable (in bits) is CI.

* CI/F = cable length in frames.

* Case boundary occurs if W=1+2IC/F.

* F=H+D

E.g. H=20, D= 80, W=1 (stop-and-wait), L=.01 and W=7

For a given window size, U is better for short cables.

Framing

In order for the DLL to group bits into frames it uses the techniques of
* character counting,
* starting and ending characters, with character stuffing,
* starting and ending flags, with bit stuffing
* physical layer coding violations

Character counting uses a field in the header to indicate the number of characters in a frame. Problem: xmission error changes the char count. A checksum error will not indicate where the next frame begins and so Character counting is not usually used.

Starting and ending characters with character stuffing is a framing method that gets around the resynchronization problem. Each frame starts with the ASCII DLE STX and ends with DLE ETX (DLE=Data Link Escape, STX= Start of text). The problem with this is that binary data may contain a DLE STX or ETX sequence in it. A solution is to send each DLE in the binary data twice. This is called character stuffing. The problem with character stuffing is that it is 8-bit ASCII code tied.

Bit stuffing allows n-bit per character. Each frame begins and ends with 01111110. If the data contains 5 1's the sender stuffs in a 0 bit. E.g. 01111110->011111010. The receiver removes the 0 following 5 1's.

* physical layer coding violations-This works when the physical layer uses redundancy in the coding (i.e. Manchester encodes a 1 as a high-low pair and a 0 as a low-high pair). Since high-high and low-low are not used for data they can be used for framing and so no stuffing is needed. This is a part of the 802 standard (Ethernet).

Many data link protocols use some combination of physical layer coding, counting, character and bit stuffing.

Summary

Layer 2 (DLL) is also known as MAC (media access control) layer. Bridges are devices which join LANs at the MAC layer.[1]%20

" * Bridges treat all packets in the same way, regardless of networking protocol.
* Bridges can connect local and remote LANs
* Bridges can connect LANs of different types (ether to FIDDI bridge)

There are 3 kinds of bridges in the world: transparent, spanning tree and source routing.

Transparent - copies all MAC frames
Spanning tree - Uses a broadcast/discovery process to determine the path a packet must take to reach a destination LAN
Source routing bridges - allow packets to take different paths across an internetwork.

Transparent bridges cannot be used if there are multiple paths to a subnet...loops mean dups!

Spanning tree bridges can work on mesh nets since they compute the path (using the spanning tree algorithm) by broadcasting messages to one another. Spanning tree disables any bridge which provides a redundant path in an internetwork. These bridges are activated if a path fails.

Source routing bridges - "poor%20man's%20routing" - routing is static, once the path info is set, a packet will not take an alternative route.

* If a link fails, the packet does not get through.
* The packet header has the path encoded into it. As each packet traverses an internetwork, it stores info about the path it is taking (bridge and LAN). The info is used to route later packets.
* Typically used in token ring nets.

The Network Layer[2]

Layer 3 (network layer) is where the routers operate.

internetworking-Connection of multiple network together

* Routers can distinguish between protocols
* Routers can filter packets by protocol type.
* Routers can perform dynamic switching.

Dynamic switching -> compute the best path =f(traffic)

Routers use router protocols:
* RIP (routing information protocol)
* OSPF (open shortest path first)
* IGRP[3]%20(interior%20gateway%20routing%20protocol)%20
*%20IS-IS" (intermediate system to intermediate system)

Each router-to-router protocol determines the best path differently.

Access routers are internetworking devices. A few WAN ports (leased line, auto dial-up or microwave or...) link remote LAN's.

Lots of router companies around, Ascom Timeplex, Coral Network corp, Crosscomm corp, proteon Inc, Retix, Cisco... Each offer routers with different features (throughput, hot-swappable components, redundant power supplies, redundant cooling fans, various protocol recognition etc.).

* Router throughput is measured in packets per second
* typically 150k pps or higher is needed (for high end stuff)

Network Layer Design Issues

* service provided to the transport layer
* routing of packets
* congestion control
* internetworking

Services Provided to the Transport Layer

Some services (ARPANET, X.25 etc..) the network layer runs in the IMPs and the transport layer runs in the hosts.

There is controversy regarding what services are provided.

There is agreement about the following:
* services should be independent of the subnet technology
* The transport layer should be shielded from the number, type and topology of the subnets present
* The network addresses made available tot he transport layer should use a uniform numbering plan, even across LANs and WANs.

Controversy: connectionless service vs. connection oriented
post office vs. telephones

ARPA Internet community (20 years experience) says that the subnet is unreliable -> hosts do error and flow control and connectionless service is provided. Each packet must carry the full destination address.

Carriers say that the network layer and subnet should be reliable, connection-oriented serivce with the features:
* set-up a connection (dial-ring-ans-talk-hangup)
* negotiation about service parameters (quality, speed, cost)
* Error and flow control
* correct sequencing
* charge for connect time!

Multimedia requires connection oriented services, letters do not. Some applications may require lossy transforms to obtain on-time arrival (not permitted in other applications).

Connection-orientation becomes a part of the network infrastructure, it is expensive. Can we trust the carriers to provide reliability?

Design by Committee: OSI took a vote, connection-oriented supporters won then ISO modifies the OSI model so that both services are available (make everybody happy).

The same issue arises in all layers. The fight was resolved using the same technique as before, every layer from network up can be either connection oriented or not.

At the top of each layer (except for the application layer) are SAPs (service access points). The SAP enables the layer above to access the service. Each SAP has its own address.

The OSI Network Service Primitives

International Standard 8348 provides connectionless primitives and connection oriented primitives.

There are 4 kinds of OSI connection-oriented primitives:
establishing, releasing, using and resetting connections.

establishing

N-connect.request sets up a connection using the NSAP (network service access point, net address).
It provides for option negotiation
* acks_wanted,
* expedited data (allowing the user to break a stream),
* quality of service
* throughput
* delay
* error rate
* secrecy
* cost and more!!

releasing

N-disconnect.request, N-disconnect.indication
N-DISCONNECT.request rejects it (reason field)

using

N-data.request(user_data)

N-data.indication(user_data)
* responds to an N-data.request arrival

N-data-acknowledge.request()
* if ack has been agreed upon, this will send an ack

N-data-acknowledge.indication()
* responds to an N-data.acknowledge arrival (acks the ack)

acks are counted and unlabeled, the error control is usually in other layers anyway.

N-Expedited-data.request(user_data)

N-expedited-data.indication(user_data)
* responds to an N-data.expedited arrival

resetting

N-reset.request(originator,reason)
reports catastrophes (crashes of trasport layer, service provided ..) The transport layer must recover from N-resets (all queues are erased).

N-reset.indication(originator,reason)
* responds to an N-data.reset arrival

The basic data unit is 64,512 bytes long (2**16 -1k) the 1K is used for overhead.

N-reset.response()

N-reset.confirm()

Internal Organization of the Network Layer[4]

" OSI model does not provide a spec of the algorithm for
* routing
* congestion control

virtual circuit - like the telephone, connection oriented
datagrams - like telegrams, connectionless

virtual circuits are used in subnets with a connection-oriented goal. When a connection is released, the virtual curcuit is discarded. For each VC the IMP must remember where to forward the packets and use a table to keep track. Each packet has a VC number field in the header. VC numbers must be unique.

datagrams have no routes set in advance (unlike VC). Each packet is routed independently. This is more robust in the presents of failure and congestion.

For a VC a unique number assignment can be a problem. for example:

How do we get from A to D? ABCD, ABCEFD, ABFD,ABECD