Energy Efficient Ethernet - Performance Analysis

N.B: I am posting by revising something I wrote for academic purposes. So it doesn't look like a blog article.

Energy Efficient Ethernet was a recent development in the field of computer networks that aims at minimizing the use of energy over networks. The idea for saving energy in communication systems was proposed as early as 2003 and its implementation in Ethernet links was officially made as a standard by the IEEE 802.3az task force. It is estimated that the internet core is consuming about 6 TWh of power each year and it keeps growing. One of the major power consumption is in Ethernet links. Since links can be physically long significant power would be needed to transmit information through the wires. IEEE standard defines a low power mode for idle links and thereby encourages saving energy.

Description of IEEE standard

EEE concept is described in figure (1) as seen in the Reviriego et al. 2009. The link is made active when a packet arrives and when no packets are left link enters into a low power mode. Periodically link is made active for a short time to make sure that it is working. This is denoted as a refresh cycle in the figure. Table (1) shows the proposed mean sleep time, wake-up time from Reviriego et al 2009.

Simulation experiments

Simulation of EEE was done using the CSIM. CSIM is a simulation library from Mesquisite software. It provides the facility for simulating queues. It is believed that the arrival of packets in Ethernet networks follows an exponential distribution and therefore EEE can be simulated as a Poisson process. Coincidentally packet arrivals and leaving on Ethernet links can be modeled as an M/M/1 queue. The service center would be link and queue will be packets arrived on the link. The simulation was done with 5000 packets each for 100Mbps, 1Gbps, and 10 Gbps. Energy consumption for the link was calculated using the following known formula.

P  = P_{low power}  · (1 − load) + P_active · load

 P_{low power} is the power consumed in low power mode and P_active  is the power consumed when the link is active. The load was increased from 0 to 100 at intervals of 5. It is assumed that both forward and backward packet transfer between the links are independent of each other. I also neglected the refresh cycle since it has little effect on performance. Further bulk arrivals were simulated using a geometric distribution with their means equivalent to the desired burst length. In this experiment, I used mean burst lengths of 2, 5, and 10 to find its effect on power consumption. Finally, I did experiments on real-world packet traces collected from a personal computer. Trace files used in this experiment were collected from a 100 Mbps Ethernet link. Trace files were collected when the user did typical browsing, downloading, and surfing on the internet.

Simulation Results

Results of the simulation on the regular EEE model are plotted in the graphs shown in figures (2), (3), and (5).

Results for the simulation on regular EEE were as expected. For burst arrivals, we notice that the performance is improved when the burst length is increased. Table II shows results for real-world packet trace analysis.

Results Analysis

Graphs for regular EEE at various loads show that performance is as expected. Energy consumption is proportional to the traffic of the packets as inferred from results. In 100Mbps, results are close to the proportional (ideal) case. However, in 1Gbps and 10 Gbps links, results are not good especially when traffic is high. It appears that the link is spending more time sleeping and waking up at higher traffic.

When packets appear as burst, performance is improved as expected. This is because the link is made to wake up and sleep only for the whole burst packet length. More the burst arrivals, more the performance getting close to the ideal case.

For real-world data, power consumption in EEE looks very low when compared to that of normal Ethernet. This might be because the packet arrival rate in the real world is higher than that of simulation models and hence link is in sleep most of the time.

Enhancing EEE

Improving EEE using predictive packet arrival

From our results, we see that the performance is affected in high-speed links when the packets arrive at high speed because the link would be spending more time sleeping and waking up. To overcome this issue I propose to make use of a predictive sleep method in which we sleep only if the queue is empty and mean arrival delay till the last packet is greater than sleep time. By doing so we could overcome the overhead issue due to continuous sleep and wake up in high-speed networks; however, we would be incurring a penalty if the prediction was wrong. If a packet did not arrive within the mean delay time we would need to sleep. Therefore penalty for a failed prediction, in that case, would be

Penalty = Mean packet arrival delay + TS

However, before making any judgments it is better to analyze the proposed model using simulation.

Simulation experiments

Experiments were conducted for the proposed enhancement method using CSIM Software. When each packet is leaving the system we check if the queue is empty. If the queue is empty we next verify that the mean delay for past packet arrivals is less than sleep time. If that is the case then we continue without sleeping, otherwise, we would sleep. If a packet arrives before the predicted mean delay we gain a power loss for the time equivalent to the difference between sleep time and mean packet delay time. If a packet did not arrive before the predicted mean delay time we incur the penalty described above. 

Simulation Results

The result of the proposed simulation model is shown in Figures (8), (9) & (10).

Result Analysis

The simulation results of the proposed model show that it could improve the performance without any packet loss. It also shows that the proposed method would work better for 100Mbps. The graph gets skewed toward the ideal case. Notice that a slight variation could produce increased cost benefits, and therefore this method looks better than the original proposal theoretically. There is no packet loss in this suggested improvement.

Summary

In this post, we reproduced the results of the IEEE simulation. We found that when burst arrivals are high performance in EEE is enhanced. It is also noteworthy that given the round trip time on typical internet servers is in milliseconds, the small delay in terms of microseconds in the Ethernet links is negligible when compared with the significant economic benefit. We also proposed a method to improve the performance of EEE without packet loss. However, we need more testing of the proposed system using real data before assuring its enhanced performance.

Link to Program used for simulation using CSIM in Git

Edge and circle detection

Edge detection is an important application of Image processing. As the name indicates the idea is to detect edges in an input image and to highlight them using image processing algorithms. Different methods exist today to detect edges and the most commonly used algorithm is Sobel edge detection. Sobel edge detection is a direct application of differential calculus. Circle detection is an extension of edge detection in which we aim to find circle-like edges in the input image. Hough transform is an important geometric method to find circles from edges in an image. In this article, we will discuss both the concepts and their implementation, both in gray-scale and color images.

Edge detection

As we know a digitized image is represented in a computer as an array of two-dimensional pixels. A pixel is the smallest unit inside an image that can be uniquely captured using the camera. The number of pixels in an image depends on the resolution capacity of the camera. In a grayscale image, each pixel corresponds to the intensity level in that particular pixel and its value ranges from zero to 255. In color images, each pixel has red, green, and blue color levels with values ranging from zero to 255. Theoretically, a mixture of these three colors can generate any visually identifiable colors of human perception.

In edge detection, our aim is to identify portions of the image where information is densely populated. This means we are interested in identifying those pixels which form edges in an image. Edges in the image are identified by comparing them with the pixel intensity of neighboring pixels. Larger the difference or variation in brightness of pixel values, the larger the likelihood that it is an edge pixel. Therefore our interest is to identify those pixels which significantly differ from their neighboring pixels. 

The application of calculus comes into play here. We know that calculus is the study of change just like geometry is the study of shapes. Assuming that the pixel values in an image form a discrete function, our aim is to find the points in the discrete function whose slope is higher. Since an image is a 2-D function, operators describing edges can be expressed by using partial differential equations. The points that lie on an edge can be detected by detecting the local maxima or minima of the first derivative or by detecting zero-crossing of the second derivative. The idea is described in figure (1) for 1-D analysis. However, since noise in an image often forms pseudo-edges we have to pre-process the image. Therefore edge detection can be described in four steps as below.

(a)   Smoothing – to reduce noise without destroying true edges
(b)   Enhancement – improve the quality of the edges (eg. by improving sharpness)
(c)   Detection: find the edge pixels
(d)   Localization: find the exact location of the edge. (eg. linking edges together)

Figure (1) - Idea of edge detection in 1-D intensity signal function. Changes in edge can be detected using local maxima or minima of the first derivative or using the zero-crossing in the second derivative. (Source here)

The derivative of a 1-D signal can be computed by approximating the derivative by finite differences. 

Therefore








Mask for 1D signal: [-1 0 1] (centered about x)

Computing the second derivative gives,









Mask for 1-D signal using second derivative: [1 -2 1] (centered about x)

Based on the 1-D theoretical analysis, the same idea can be extended to two-dimensional pixel planes, and one such extension is known as the Sobel operator. The Sobel operator performs an accurate approximation to calculate the derivative of a two-dimensional image by computing the spatial gradient measurement of an image. Sobel detector uses a pair of 3 x 3 convolution masks, one for x-direction and the other for y-direction. Sobel operator for a two-dimensional image is as follows and it slides over the image.

Figure (2) – Sobel operator for edge detection in images.

The magnitude of the gradient is calculated using the resultant formula:

The direction is calculated by using the inverse tangent of the gradients in each direction.

.

Figure (3) – Gradient edge and direction (source)

Some of the results of applying the Sobel operator in grayscale images and color images are shown below. In color images, we compute the intensity and use it for edge detection.

Intensity  I = (red + green + blue) / 3

After computing the edges, thresholding is applied to highlight edges that are highly likely. Again we can highlight those edges which are in a particular direction by thresholding edge intensity image using computed direction information.

Figure (4) Original Image, Edge image, Thresholded edge image and direction thresholded edge image (clockwise). ROI (x,y,sx,sy) = (10,10,450,620), threshold value = 80 and direction threshold value = 80 to 90 degrees.

Figure (5) Original Image, Edge image, Thresholded edge image and direction thresholded edge image. The ROI (x,y,sx,sy) = (10,10,450,620), threshold value = 80 and direction threshold value = 70 +- 10  degrees.

Figure (6) Original Image, Edge image, Thresholded edge image and direction thresholded edge image. The ROI (x,y,sx,sy) = (10,10,550,550), threshold value = 80 and direction threshold value = 45 +- 10 degrees.

Circle detection using Hough transform

Circle detection in image processing is done using Hough transform. Hough transform is a feature extraction technique to find imperfect instances of objects within a certain class or shape. This is done by parameterization and then voting the parameter space to find local maxima. First, we compute the edges of the image using edge detection. Then we threshold the edge image so that we can find significant edges. Now we have to find those edges which form a circle. Note that after edge detection circumference of the circles might not be connected clearly. So we apply Hough transform.

A circle can be described completely with three pieces of information: the center (a, b) and the radius R.

x = a + Rcosθ
y = b + Rsinθ

When the θ varies from 0 to 360, a complete circle of radius R is generated. We note that for a circle the parameters (a, b, R) are constant. In the parameter space, we plot the coordinates with (a, b) boundary equivalent to the set of all possible centers in a given image where θ ranges from 0 to 360. For each edge point that correspond to (x, y, R) of a particular circle in real space we draw the sphere in the corresponding (a, b, R) parameter space. If we are looking for circles of a particular radius R then we have a 2D parameter space. 

Figure (7) – Each point in the geometric space (left) generates a circle in parameter space (right). The circles in the parameter space intersect at (a,b) the center of the circle in geometric space. (source)

Rearranging the equations we get

a = x₁ – Rcosθ

b = y₁ – Rsinθ

After plotting the circles in parameter space, we will note that the points at which circles in parameter space intersect correspond to the center of the circle in real space. To find circles that are more likely true we compute intersections that have a high density. This is done by sampling the parameter space with a suitable bin size. Once we compute the local maxima we highlight the circle in the original space. Some results for both greyscale and color images are shown below.

Figure (8) Original Image, Edge image, Thresholded edge image, PSpace image and Resulted circle. The ROI (x,y,sx,sy) = (10,10,300,300), threshold value = 80 and radius = 33 px.

Figure (10) Original Image, Edge image, Thresholded edge image, PSpace image and Resulted circle. The ROIs (x,y,sx,sy) = (110 10 200 200)(110 280 200 200), threshold value = 80 and radius = 90 px.

Figure (11) Original Image, Edge image, Thresholded edge image, PSpace image and Resulted circles. The ROIs (x,y,sx,sy) = (180 220 80 80) (180 320 80 80), threshold value = 80 and radius = 11 px.

I have included sample code in c++ for edge detection and Hough transform. Code for classes ROI, Images are excluded.

I posted my code used in this article in Git.

Histogram Equalization

A histogram is a graphical representation of the tonal values of an image. In a greyscale image, we have only one channel, and its value range from 0 to 255. Based on the number of pixels falling under a particular tonal value we plot the histogram graph. 

Grey histogram Equalization

In Grey histogram equalization we enhance the contrast of images by using usable pixel values in the image to the close contrast values of the display device. This is accomplished by spreading out the most frequent intensity values to the neighboring intensities. First, we compute the cumulative distributive function of the histogram. Then we use the general histogram formula to accomplish this.

The general histogram equalization formula is:

Where cdf_min is the minimum value of the cumulative distribution function, M × N gives the image's number of pixels and L is the number of grey levels used. Some sample results are shown below. Note that equalization is done within the two regions of interest.

(a)   Original Image

(b)   Histogram for ROI 1 before and after equalization ( x = 10, y = 10, sx = 300, sy = 300)

(c)    Histogram for ROI 2 before and after equalization ( x =315, y =315, sx = 400, sy = 400)

(d) Result - equalized image

Color Histogram Generation (RGB)

In color images, we have three channels namely red, green and blue. Therefore in order to generate the histograms, we apply the same principle for greyscale images separately for each channel.

Color Histogram Equalization (RGB)

In color histogram normalization we apply the same method used for grey-scale equalization for each of the three channels separately. The results are shown below.

(a)   Original Image

(b) Histogram for ROI 1 – Before and after equalization - RGB ( x = 10, y = 10, sx = 300, sy = 300)

(c)   Result - equalized image (all channels together)

(d)   Equalization separately - Original and  RGB channels respectively (Clockwise)

               

HSI histogram generation

HSI is a color model which is more intuitive and perceptually relevant to co-ordinate space. It has wide applications in the field of computer graphics and vision. Like RGB it has three channels namely Hue (H), Saturation(S), and Intensity (I). Hue falls from 0 to 360 degrees, and the other two fall from 0 to 1. For the sake of calculations, we make saturation fall between 0 to 99 and Intensity fall from 0 to 255 respectively. For HSI histogram generation we need to convert the RGB color model to HSI. We then generate a histogram for the three channels separately. The formula for HSI to RGB and from RGB to HSI is below from the Gonzales and Woods text.

HSI histogram equalization

After generating HSI histogram we then compute the equalized histogram from it. For that, we make use of the same histogram formula we used before. After equalization, we then convert it back to RGB image for display. The resulted images are shown below.

(a)   HSI histogram for I channel – Before and after equalization (x = 10, y =10, sx = 300, sy = 300)

(b)    HSI equalization (original and I channel respectively)

Program

Some of the functions I used to do the above operations in C++ are in Git here. Note that the custom class Image and ROI are not included here. However, this code is enough for explaining the main logic.

Image thresholding and smoothing

Thresholding helps to visualize the useful portion of the image, whereas smoothing helps to remove noise from the image.  The images captured through a camera are generally in analog format and therefore it is digitized by sampling. The digitized image is stored in a computer in the form of pixel arrays. Each pixel contains information such as the color or intensity of that portion of the image. Pixel size depends on the sample size of the digitization process. In image thresholding, each pixel value is either set to black or white depending on a user-defined threshold value. In smoothing the pixel values are set based on the values of the neighboring pixels.

Image Scaling in Grayscale images

Image scaling is the process of incrementing the pixel values based on the user-defined scaling factor. Image scaling helps to increase the brightness of the image. In greyscale image scaling the user-defined value is added to the pixel value. Below is the image scaling result with a scaling factor 25, 50 in the Region of interest (ROI) one and two respectively. The brightness and hence the quality of the image are increased by scaling. The original image is shown on the left side and the scaled image on the right side.

Image thresholding in Grayscale images

Thresholding in the Grayscale images is done by setting the pixel values to 0 or 256 based on a threshold value defined by the user. For example, if the threshold value is 125 then all pixel values below 125 are set to 0 and all pixel values above 125 are set to 256. In this way, the image features are more easily identifiable. Below is the image thresholding result on a greyscale image with thresholding values 100, 150 for ROI one and two respectively.

Image thresholding in Color Images

In color thresholding, the distance between the RGB pixels of the image with the user-defined color values is then compared with a user-defined threshold TC. If the distance falls below the threshold then those pixels are set to white and all other pixels are set to black. A sample result with RGB (25,25,25) with TC = 205 and TC = 100 for ROI one and two are shown below respectively.

Adaptive Weighted thresholding in Grayscale images

In normal thresholding, the parameter provided by the user affects the entire image. Hence it might give undesirable results in images that have wide variability in intensity. Adaptive weighted thresholding helps to overcome this issue by using a weight factor W which is compared with the mean of the pixels falling inside the odd-sized window with the current pixel as the center. The result of such thresholding with Window size 3, 5 and threshold factor 15, 20 on ROI one and two are shown below respectively.

One dimensional Smoothing in Grayscale Images

In one-dimensional smoothing, the pixel values are averaged along one dimension of the two-dimensional pixel plane. The result of one-dimensional smoothing in X and Y direction separately is shown below with windows size 3, 5 on ROI one and two respectively. The window size should be selected reasonably so that blurring is kept to the minimal level possible.

Two-dimensional Smoothing in Grayscale images

In two-dimensional smoothing, the mean of the whole window in the two-dimensional plane is used as the pixel value. The result of two-dimensional smoothing with window sizes 3 and 5 on ROIs one and two is shown below.

Program

Some of the functions I used to do the above operations in C++ are in Git here. Note that the custom class Image and ROI are not included here. However, this code is enough for explaining the main logic.