Communication Network I



Communication Network I

Lecture 4, Sept 10, 1998

Instructor: Roy Yates

Summary by: Nan FENG

Main content:

2.4.4 APRANET ARQ: Configuration; Bits of header for ARQ control; Operations.

2.5 Framing:

2.5.1 Character-Based Framing

2.5.2 Bit Oriented Framing: Flags

2.5.5 Maximum Frame Size

APRANET ARQ

APRANET achieves efficiency by using eight stop-and-wait strategies in parallel, multiplexing the bit pipe between the eight.

Fig 1.1 Eight multiplexed, stop-and-wait virtual channels in APRANET ARQ

Each incoming packet is assigned to one of eight virtual channels if it’s idle; otherwise the packet has to wait outside of DLC. The busy virtual channels are multiplexed on the bit pipe. When a given virtual channel gets its ack received, it will be idle until new incoming packets.

Fig 1.2 Bits in header for ARQ control

The overhead for APRANET ARQ is more than basic stop–and-wait protocol. As basic stop–and-wait protocol, it includes 1 bit SN. Each frame also carries 3 bit virtual channel number ([pic]) and one bit RN for each virtual channel, which gives the number modulo 2 of awaited packet for each virtual channel.

1. Framing

Framing is very important and necessary for DLC to detect, correct errors. When DLC receives bit streams, it breaks it up into discrete frames and compute checksum for each frame. Then it needs to know what’s the start and end of each frame. It’s too risky to count on timing to mark the start and end of frames because in the networks. Two methods are introduced in the lecture: character-based framing and bit-oriented framing with flags. Furthermore, the expected overhead for the latter method is obtained.

1. Character-Based Framing

Character codes provide binary representation for communication control characters. Four main ASCII used in framing are as follows:

SYN (SYNchronous idle): string of SYN provides idle fills, used for synchronization of old modems or to bridge delays in supplying characters;

STX (Start of TeXt): marking the start of frame;

ETX (End of TeXt): marking the end of frame;

DLE (Data Link Escape): inserting to enter transparent mode. (When the packets contain an arbitrary binary string, ETX might be in it, which will end the frame in advance. DLE is inserted before ETX and STX to double guarantee the start and end of the frame. If DLE is in the packet, another DLE is inserted).

Fig 2.1 Character-based framing in a transparent mode

2. Bit-Oriented Framing: Flags

This method has very similar idea with above method. Flags are used to replace DLE ETX in the transparent mode to mark the end of each frame. Flag is a special bit sequence like 01j0 (1j means a string of j 1’s). To avoid abnormal termination of frames when there are 01j0 in the frame, it uses bit stuffing technique. Bit stuffing is to insert extra 0 after each 01j-1, which guaranteed that except flags , there would be no j consecutive 1’s in the frame except the flags.

In order to see how necessary the bit stuffing is, fig 2.2 gives an example of use of bit stuffing in bit-oriented framing.

Stuffed bits

0 0 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0

Fig 2.2 Bit stuffing: A 0 is stuffed after each consecutive 5 1’s. The flag is 01111110. If without bit stuffing, the frame will terminate in advance.

Because flags and bit stuffing will incur the overhead, follows are simple calculation assuming the frame consists of independent, identically distributed binary variables with equal probability of 0 or 1. If the frame length is K, and the random variable xi is defined as:

[pic]

It’s obvious that for i=1,2,…j-1, xi=0 because bit stuffing will add after the j 1’s.

Define random variable N as the total number of stuffed bits,

[pic] (2.2)

1) For [pic], an insertion occurs from i-j+1 to i if this j consecutive string is like 01j-1, with probability of 2-j

2) For i=j-1, an insertion occurs when the first j-1 bits are all 1’s. The probability of this case is 2-(j-1).

3) For other cases, the probability of insertion of 0 is negligible.

From above reasoning, it’s easy to obtain the expected number of insertions E[N]:

E[N] = (E[K]-j+3)2-j (2.3)

The overhead caused by this kind of framing consists of stuffed bits and the flag. The length of flag is j+1 (flag: 01j).

E[overhead]= (E[K]-j+3)2-j +j+1 [pic]E[K]2-j +j+1 (2.4)

In the RHS of above equations, we have the approximation based on the fact that usually the frame length is much larger than j.

For a given expected frame length, if we increase j from 1, the expected overhead will increase first and then decrease. For the smallest optimum j, the overhead will be less than the overhead with flag 01j+1.

E[K]2-j + j + 1 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download