Flow-Level Packet Loss Detection via Sketch Decomposition and Matrix Optimization Zhenyu Ming1 Wei Zhang2 and Yanwei Xu1

2025-05-06 0 0 1.33MB 9 页 10玖币

侵权投诉

Flow-Level Packet Loss Detection via Sketch

Decomposition and Matrix Optimization

Zhenyu Ming1, Wei Zhang2, and Yanwei Xu1

1Theory Lab, Central Research Institute, 2012 Labs, Huawei Technologies Co., Ltd.,

Hong Kong

2Department of Mathematical Sciences, Tsinghua University, Beijing 100084, China

Abstract

For cloud service providers, ﬁne-grained packet loss detection across data centers is crucial in

improving their service level and increasing business income. However, the inability to obtain suﬃcient

measurements makes it diﬃcult owing to the fundamental limit that the wide-area network links

responsible for communication are not under their management. Moreover, millisecond-level delay

jitter and clock synchronization errors in the WAN disable many tools that perform well in data center

networks on this issue. Therefore, there is an urgent need to develop a new tool or method. In this

work, we propose SketchDecomp, a novel loss detection method, from a mathematical perspective

that has never been considered before. Its key is to decompose sketches upstream and downstream

into several sub-sketches and builds a low-rank matrix optimization model to solve them. Extensive

experiments on the test bed demonstrate its superiority.

keywords: packet loss; sketch decompostion; matrix optimization

1 Introduction

Packet loss is common in various networks, and its rate is an important metric that characterizes network

performance [1]. For cloud service providers(CSPs) with multiple data centers, suﬃcient knowledge of

packet loss, especially in the forward path between data centers, contributes to improving the quality of

service and avoiding violating service-level agreements with customers. Hence, reliable, ﬁne-grained packet

loss detection, that is, knowing the packet loss of each ﬂow in each short time window, is increasingly valued

and has been desired by them for a long time. However, restricted by the non-visibility of communication

links, it is usually a challenging task. Because of the long geographical distance, the data centers are

typically connected by a backbone network managed by Internet service providers. It means communication

on network links is not under the control of CSPs. They have only access to monitor traﬃc on egress and

ingress devices in their own data centers, not at any point on the wide area network link. The incomplete

measurements fundamentally limit the generation and development of solutions.

Many popular monitoring tools proposed before are not up to the task, at least not as ﬁne-grained.

EverFlow [2] and s-Flow [3] mirror packets as they pass through the switching device to record information

and then compare those mirrored upstream and downstream to identify packet loss. The high bandwidth

and storage overhead force them to sample only some packages for mirroring and thus fail to meet the

accuracy requirements. NetFlow [4] maintains a counter for each ﬂow on the switching device to realize

ﬂow-level measurements. FlowRadar [5], on top of NetFlow, introduces encoded ﬂow sets to save the

arXiv:2210.12808v1 [cs.NI] 23 Oct 2022

memory overhead of switches and sets up a remote collector to decode the ﬂows and counters network-

wide. They both ignore the misalignment of upstream and downstream time windows caused by clock oﬀset

and variable transmission delay, leading to biased packet loss analysis in a short time window. LossRadar

[6] is a seminal work, which marks the time window ID in the packet header upstream to identify the

source of packets and thus counter the impact of time window misalignment. Despite its success in data

center networks, it is not applicable and uneconomic to the backbone network we focus on. Speciﬁcally, the

data center’s egress devices and ingress devices are often non-programmable commercial switches, hard to

add packet headers eﬃciently. Moreover, routers beyond the control of CSPs may not support forwarding

non-standard packets with headers added.

This paper proposes SketchDecomp, a novel detection method for packet loss between data centers.

Based on sketch decomposition and matrix optimization, it does a high-accuracy job at the ﬂow level

without modiﬁcation of packets or other hardware operations. Thus, it is easy to deploy and economical

compared to previous methods. Concretely, in SketchDecomp, several count-min sketches [7], a particular

data structure represented as a matrix, are deployed upstream and downstream to count ﬂows in the

send and receive windows. Given that packets sent may be branched to multiple receive windows due to

delay jitter, we regard the sketches as the sum of several unknown sub-sketches. After some equality and

inequality constraint are derived, a matrix optimization model following low-rank property is subsequently

developed to solve these sub-sketches. In particular, we design a symmetric Gauss–Seidel alternating

direction method in order to solve it eﬃciently. Finally, SketchDecomp identiﬁes the packet loss and

computes the loss rate by comparing the sub-sketches recovered and sketches observed.

The rest of the paper is organized as follows: In Section 2, we give the precise problem statement and

detail the deployment and optimization problem modeling of SketchDecomp. In Section 3. we present the

sGS-ADMM algorithm to solve the optimization model and cover its convergence. Extensive experiments

in Section 4 highlight the eﬃciency and accuracy of SketchDecomp. Finally, we conclude the work in

Section 5.

2 SketchDecomp

In this section, we brieﬂy describe the packet loss detection problem to be solved and then develop our

proposed method.

2.1 Problem Statement

Consider communication between two data centers DC1and DC2, bridged by a WAN link L. Their clocks

have been synchronized using certain synchronization methods of the WAN. In a certain period, streaming

data consisting of several types of ﬂows are continuously sent from upstream DC1to downstream DC2

through L. The forward delay varies with time, and its rough range is known. Dividing the upstream time

into multiple windows of length T, we aim to check for each ﬂow whether the packet loss occurs in each

window and estimate the packet loss rate accurately.

2.2 Count-min Sketch

The count-min sketch (CM sketch) is a particular data structure to count and record the frequency of each

type of ﬂow in stream data, with a certain conﬁdence level. Unlike traditional hash tables, it utilizes mul-

tiple, say d, mutually independent hash functions {hi}d

i=1 to against the overcounting caused by collisions.

Basically, CM-Sketch is a d×wmatrix denoted as C, whose i-th row is the count created by hi. There is

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

Flow-LevelPacketLossDetectionviaSketchDecompositionandMatrixOptimizationZhenyuMing1,WeiZhang2,andYanweiXu11TheoryLab,CentralResearchInstitute,2012Labs,HuaweiTechnologiesCo.,Ltd.,HongKong2DepartmentofMathematicalSciences,TsinghuaUniversity,Beijing100084,ChinaAbstractForcloudserviceproviders,ne-grain...

展开>> 收起<<

Flow-Level Packet Loss Detection via Sketch Decomposition and Matrix Optimization Zhenyu Ming1 Wei Zhang2 and Yanwei Xu1.pdf

共9页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Flow-Level Packet Loss Detection via Sketch Decomposition and Matrix Optimization Zhenyu Ming1 Wei Zhang2 and Yanwei Xu1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: