Posts Tagged ‘interleaving’

Jan
25

The need for fragmentation

We are going to briefly discuss Layer2 fragmentation schemes, their purpose and configuration examples. Let’s start with a general discussion. Usually, Layer2 fragmentation is used to accomplish one of two goals:

a) Link aggregation, e.g. making a number of physical channels look like one logical link from Layer2 standpoint. A good example is PPP Multilink, which breaks large packets into smaller pieces, and send them other multiple physical links simulataneously. Another example is FRF.16 (Multilink Frame-Relay).

b) Decrease large packets serialization delay on slow links. By “slow link”, we mean a link with “physical” speed (e.g. clock-rate) less than 1 Mbps. The issue is usually to have a mix of bulk data and delay-sensitive traffic (e.g. voice) on the same link. This is because large bulky packets (say 1500 bytes in size) may block the interface transmission queue for a long time (with slow links), making small voice packets (e.g. 60 bytes) to wait for more than maximum tolerable threshold (say 10ms).

For example, if physical interface has clock rate of 384000bps, large 1500 byte packet would take 1500*8/384000 > 30ms to serialize. So here comes the solution: break large packets into small pieces at layer2, to decrease the serialization delay. Say if we break one 1500 packet into 3×500 byte frames on a 384Kpbs link, we’ll get 10ms transmission delay for each fragment. Look at the following picture ([V] is a voice packet, and [D] is a data packet)


Before fragmentation:

--[DDD][V][DDD][V][V][DDD]--->

After fragmentation:

--[D][D][D][V][D][D][D][V][V][D][D][D]--->

There is still something wrong here: Small pieces of a large packet are being sent in a row, effectively blocking the transmission qeueue the same way it was before. So just fragmenting alone is not enough – we need a way to make sure the fragments of large packets are “mixed” with voice packets. The technique is called “interleaving”, and it always accompanies fragmentation. With interleaving we get a picture like this:


---[D][V][D][V][V][D][D][D][D]--->

That is, voice packets are not separated by large “islands” of data packets.

So how does interleaving work? Usually, it is accomplished by inserting a special “interleaving” queue before interface transmission (FIFO) queue. Interleaving queue usually has two parts: “high” and “low” FIFO queues. Small packets (packets smaller than configured fragment size) go to “high” queue, and large packets are first fragmented, and then assigned to “low” queue. With this strategy, “high” queue is a priority queue – it’s always get emptied first, and only then the “low” queue gets served.


[Interface Software Queue, e.g. WFQ] --> 

If(Packet.Size lt FRAGMENT_SIZE) 

then 

{ put to High_Queue } 

else 

{ Fragment and put fragments to Low_Queue } 

--> { Service (High_Queue) then Service(Low_Queue) } --> [Interface Xmit Queue]

We are not over yet! You’ve probably noticed “Interface Software Queue” on the diagram above. It plays an important role too. Say, if this is a simple FIFO queue, and a bunch of large data packets sit there ahead of small voice packets. The data packets will get dequeud first, fragmented, and since “high” interleaving queue is empty, will be sent in line on their own. Therefore, the last component to make fragmentation and interleaving work properly, is a software interface queue that give voice packets priority treatment. This could be legacy WFQ or modern CBWFQ/LLQ – just remember that voice packets should be taken from software queue first!

So here are the important things to remember about fragmentation:

1) Fragmentation is not effective without interleaving
2) Interleaving is accomplished by use of additional priority queue
3) Decision on where to put a packet to “high” interleaving queue is based on packet size solely
4) Interleaving is inefficient without a software queue that gives small (e.g. voice) packets priority treatment

Situation becomes more complicated, when we have multiple logical channels (e.g. PVCs) multiplexed over the same physical channel. For example, with a number of Frame-Relay PVCs, assigned to the same physical interface, we get multiple software queues – one per each PVC. They all share the same interleaving queue at physical interface level. Due to the fact that large packets of one PVC may affect small packets serialization delay of the other PVC, fragmentation should be turned on for all PVCs simultaneously.

Tags: , , , , ,

Categories

CCIE Bloggers