A Little Queueing Math

Introduction

Figure 1: Model of a Fiber-To-The-Home Network.

Figure 1: Model of a Fiber-To-The-Home Network.

Queues arise naturally in many circumstances and networking products are no exception. We use queues for many tasks in our networking products and this post discusses our need to store packets while we wait to be granted access to our fiber network. This post will show you a simple queueing problem and how its solution perfectly modeled the performance we measure during testing.

The basic problem discussed here is a common one. When a home PC needs to transmit information onto the Internet (e.g. email), it starts by sending its data to the home's Internet gateway, which is often a DSL or cable modem. In the case of a Fiber-to-the-Home network, that gateway is called an Optical Network Terminal (ONT). The ONT must place the data it receives from the PC onto its FTTH Passive Optical Network (PON) network, but it cannot do that until it receives a receives an allotment of transmit time from the FTTH network manager called the Optical Line Termination (OLT). This allotment of time is required because FTTH systems share the fiber between multiple homes and only one ONT can transmit at a time (see Figure 1). While the ONT is waiting for its time allotment on the network, it must store the data it is receiving from the PC so that no data is lost. This storage drives the number of queued packets which our system must manage, which is one of the cost drivers of the ONT.

The analysis I present here was performed by an engineer in my group, Chris Bernard, and I am presenting it here as an example of how little bit of analysis can provide insight into the performance we see in data networks.

Background

Definitions

It is helpful to begin with a couple of definitions.

bandwidth request
A request for fraction of a network's available transmit time.
packet drop
A packet drop occurs when a packet arrives at the ONT and there are no resources available to store or transfer it, so it must ignored and its information is lost. The PC must retransmit it, which is inefficient and slows the PC's operation.

Objective

I want to compute the maximum number of packets that I will need to manage when holding data at the ONT while we request and are granted transmission time on the PON. You want to provide all the resources you need to manage the maximum number of packets so that the PC's data can be transferred without dropping any. Allocating any resources above the maximum you need is wasteful and results in unnecessary costs.

Process for Transmitting Data

Figure 2 illustrates the six-step process for a PON bandwidth request.

Figure 2: Bandwidth Request Process

Figure 2: Bandwidth Request Process

If define the six-step bandwidth request process as follows:

  1. PC begins transferring data to the ONT at 1 Gigabit Per Second (Gbps)

    Most PCs support 1000BaseT Ethernet and its data rate is 109 bits per second, which we call 1 Gbps.

  2. The ONT begins queueing the PC data coming in.

    A PON is a fiber network that is shared between many subscribers – as many as 64 – and only one subscriber can transmit at a time. To ensure that only one subscriber can transmit at at a time, ONTs must request from the OLT  an allotment of time to transmit its data. We refer the request ONT's request for transmit time as a request for bandwidth.

  3. The ONT requests permission to transmit on PON – because the speed of light is finite, the signal takes time to get to the OLT (τ Flight).

    The fiber can be as long as 40 km and the light must travel on the fiber from the ONT to the OLT. The ONT transmits to the OLT using 1310 nanometer (nm) light.

  4. The OLT must recognize the ONT is requesting bandwidth (τSampling).

    The OLT creates an opportunity for every ONT to request a time allotment on the PON once every millisecond (msec). Since the PC can start to transmit at any time, the ONT may have to store as much as 1 msec of data before the OLT even considers its request for bandwidth.

  5. The OLT must determine how to allot the ONT time for transmitting data (τDBA).

    There is an algorithm in the system referred to as Dynamic Bandwidth Allocation (DBA). This algorithm requires a fixed unit of time to determine the ONT's bandwidth allotment.

  6. Because the speed of light of light is finite, the bandwidth allotment takes time to get to the ONT (τ Flight).

    The transmission time from the OLT to the ONT is roughly the same as from the ONT to the OLT (step 3). The difference in time is because the speed of light on a fiber varies slightly with its wavelength. The OLT transmits to the ONT at 1490 nm, which is a slightly longer wavelength the ONT's 1310 nm value.

The ONT now has time allocated to it and it can begin transmitting data and emptying its queue, which will shrink the queues size and the number of packets in storage.

Analysis

Figure 3 shows the analysis for number of packets that we must be able to queue so that we do not have to drop any data arriving from the PC.

Figure M: Maximum Number of Queued Packets Calculation.

Figure 2: Maximum Number of Queued Packets Calculation.

We need to be able to manage as many as 2973 packets to ensure that we do not need to drop any packets from the PC.

Conclusion

It turns out that we needed the ability to store 2973 packets, otherwise we began to drop data coming from PCs. While this was a simple analysis, it turned out to be very accurate.

This entry was posted in Fiber Optics, Networking. Bookmark the permalink.