% !TEX root = ../bachelor-thesis.tex

\chapter{相关工作}

\section{覆盖网络隧道技术}

覆盖网络的实现依赖于隧道封装技术，其基本原理是将原始的二层或三层报文封装在另一种网络协议中进行传输，从而在底层的IP网络上构建虚拟的二层网络。当前主流的Overlay隧道技术主要包括VXLAN\cite{rfc7348vxlan}、NVGRE\cite{rfc7637nvgre}和Geneve\cite{rfc8926geneve}等，它们在封装格式、协议机制和适用场景上各有特点。

VXLAN（Virtual eXtensible Local Area Network，虚拟可扩展局域网）\cite{rfc7348vxlan}是由IETF制定的虚拟网络技术之一，广泛应用于在数据中心和云网络中。VXLAN通过MAC over UDP的方式，将二层的以太网帧封装在UDP报文中通过公网传递，对虚拟的二层网络在三层网络的基础上进行扩展。VXLAN使用24比特的虚拟网络标识（VXLAN Network ID, VNI）来区分不同的虚拟以太网，可以突破传统VLAN的4096个虚拟网络数量限制，提供约1600万个各自独立的虚拟局域网。VXLAN协议将普通的二层网络数据帧添加上VXLAN的包头，之后再将数据包装上外层的以太网、IP和UDP报文头后发送至公网。VXLAN包的封装和解封装由VXLAN隧道端点（VXLAN Tunnel End Point）进行，VTEP负责将从虚拟机进入隧道的包进行封装，也负责将从隧道接收到的包进行解封装后交付给虚拟机。这使得VXLAN隧道对虚拟机透明，便于与其他网络系统集成。VXLAN利用已有的UDP传输机制在网络中建立隧道，成熟度高，当前已广泛应用于数据中心。

NVGRE（Network Virtualization using Generic Routing Encapsulation，基于路由封装的网络虚拟化）\cite{rfc7637nvgre}是另一种主要的虚拟隧道协议。该协议主要应用于微软的Hyper-V虚拟环境中\cite{microsoft_nvgre}。NVGRE将二层的MAC包封装在GRE隧道包内通过公网传递，利用GRE协议中的Key字段传递包所属的虚拟子网标识（Virtual Subnet ID, VSID）以及流标识（FlowID）。NVGRE同样以24比特标识虚拟网络的名称，因此也可以支持最多约1600万个虚拟子网。同时，NVGRE支持在同一子网内进一步通过流标识来区分不同的数据流，为更精细地管理流量和流量均衡提供了支撑。然而，这要求物理网络设备具备识别和处理这些字段的能力，对在公网部署带来了一定的挑战。

Geneve（Generic Network Virtualization Encapsulation，通用虚拟化网络封装技术）\cite{rfc8926geneve}是IETF新提出的通用网络虚拟化封装协议，旨在以单一、可扩展的封装格式取代碎片化的VXLAN、NVGRE等多种隧道协议，以维持生态统一。Geneve也采用MAC over UDP的封装，通过灵活配置的元数据传递机制满足多种网络虚拟化需求。Geneve也使用24比特的虚拟网络标识（Virtual Network Identifier, VNI）来区分不同的虚拟网络，支持的网络数量与VXLAN、NVGRE等协议相当。与VXLAN等协议不同，Geneve允许在头部后添加可变长度和数量的控制位和控制信息，可以有效满足不同虚拟网络的需求，增强了可扩展性。Geneve协议通过设计可选的元数据空间，允许在不修改协议的前提下引入新功能，自推出以来已经逐步得到各类虚拟网络平台的支持\cite{ovn_geneve,vmware_nsxt_geneve}，但是协议较为复杂，适配难度较大。

\section{链路质量优化}

低质量的互联网链路由于负载较大出现拥塞或部分设备运行故障，容易出现丢包或者延迟波动。在这些低质量的链路上进行传输时，即使链路还有可用的传输带宽，也会出现丢包或是延迟波动。即使TCP\cite{rfc9293tcp}等可靠传输协议通过重传确保了所有数据都能可到送达，但性能较差。这是因为TCP协议依靠超时重传来在确保所有数据都最终送达至接收端，即使使用了基于重复ACK的快速重传机制，如图\ref{fig:TCP丢包恢复缓慢}，恢复单个丢失的包也至少要经历接收端检测丢包——请求发送端重传——发送端重传包送达恢复的过程，至少需要一个往返时延（Round Trip Time, RTT）才能恢复。对于一条在云网络中的跨域链路，往返时延可能达到\SI{300}{ms}或更长，如此缓慢的丢包恢复不仅会阻塞后续数据包的发送，也会极大地影响实时媒体服务如影视直播、视频通话等应用的用户体验。

\begin{figure}[H]
    \centering
    \includegraphics[width=\linewidth]{tcp_slow_recovery.drawio.pdf}
    \caption{即使启用了快速重传机制，TCP仍旧需要一个往返时延才能恢复丢包}
    \label{fig:TCP丢包恢复缓慢}
\end{figure}

针对此问题，研究者们提出了多种解决方案，其中前向纠错编码（Forward Error Correction, FEC）被广泛地用于应对链路传输中的丢包。其基本思想是，在发送数据时直接加入一部分冗余信息，以确保在部分信息丢失时，接收端无需请求发送端重新传送任何信息，而可以利用已经接收到的信息配合冗余信息推算出丢失的信息。使用前向纠错编码进行丢包恢复时，与重传机制需要经历一整个往返时延的长时间反馈路径不同，利用前向纠错编码的冗余包进行恢复只需要等待后续冗余包送达后即可进行，错误恢复时间短，能更好地适应延迟敏感型应用如视频通话等应用的需求。

为了实现高效地前向纠错编码，研究者们提出了多种编码方式，它们针对不同的目标进行了设计和优化。

\subsection{简单复制冗余}

早期的FEC工作主要通过对时间敏感的数据包进行简单地复制和多次传输进行错误恢复。如图\ref{fig:早期FEC}所示，通过将每个数据包复制多份，每次发送新的数据的同时，在同一个数据包中同时捎带发送之前已经发送过的一些数据包，这样可以在一部分数据包丢失的同时仍旧确保接收端收到了所有数据。Bolot等人\cite{bolot1999adaptivefec}基于此思路提出可以利用实时语音通话应用中已经存在的平均丢包率监控字段对传输链路的丢包模式和丢包律进行估计，从而动态地选重复发送包的发送间隔和次数，优化通话用户的用户体验。之后Gandikota等人\cite{gandikota2008multipathfec}在此基础上提出可以通过多路径传输，进一步提升冗余包和原始数据包中至少有一个送达的概率。Gandikota等人在工作中提出通过估算网络中的丢包率，动态地调整冗余参数以实现对语音流中的重要子流进行保护，同时再将编码后的数据包以及其他次要子流经过两个最大程度节点不相交路径在网络上与重要数据流分开传输，以降低数据传输丢失概率、提升用户体验。Huang等人\cite{huang2010skypefec}通过测量Skype应用在不同丢包网络条件下的行为，印证了相关冗余编码在提升实时语音通话用户体验方面的积极作用。

\begin{figure}[H]
    \centering
    \includegraphics[width=\linewidth]{fec_copy_based.drawio.pdf}
    \caption{早期FEC工作将冗余信息附加在后续发出的包中进行发送}
    \label{fig:早期FEC}
\end{figure}

\subsection{分组冗余码}

通过重复发送数据包的方式添加冗余虽然简单，但是会带来较高的冗余开销，为了提高冗余信息的恢复效率，研究者们进一步提出了基于分组冗余码的前项纠错机制。XOR码和R-S码是较为主要的冗余纠错恢复机制。如图\ref{fig:分组码示意}，这两种编码都是线性分组码，将原始数据分为$n$个数据包一组，对于每一组数据再加入$k$个冗余数据包并将$n + k$个数据一并发送，接收端同样以组为单位进行丢包的恢复。

\begin{figure}[H]
    \centering
    \includegraphics[width=.7\linewidth]{grouped_code.drawio.pdf}
    \caption{分组码为$n$个数据包附加$k$个冗余包}
    \label{fig:分组码示意}
\end{figure}

在XOR编码中，$n$可以为任意值，而固定$k = 1$，冗余包通过将所有组内的数据包按位进行异或运算得到。如果接收端只接收到了一组数据包共$n + 1$个包中的$n$个，则丢失的包可以通过对已经接收到的包按位进行异或运算恢复得到。XOR编码可以在一组数据共$n + 1$个包丢失任意一个时通过剩余的$n$个包将丢失的包恢复，但是如果丢失了两个或更多包，则完全不能恢复丢失的数据。XOR码的计算简单，冗余包生成和丢失数据包恢复都只需要使用异或运算即可完成，运算开销小，但是只能恢复固定模式的少量丢包，面对组内多个丢包的情况效果有限。

为应对XOR编码的缺点，在1960年，Reed与Solomon提出了R-S编码\cite{reed1960rscode}。R-S编码保证，对于$n$个数据包和$k$个在有限域上计算出的冗余包共$n + k$个数据包，接收端只要接收到了其中的任意$n$个，就能完整地恢复出所有的原始数据包。相较于XOR编码，R-S编码的恢复能力有较大的提升，能够在同一个编码组里出现较多的丢包的恶劣情况下进行恢复，从能承受最多1个丢包增加至能承受最多$k$个丢包。RS编码被广泛用于传输音视频流媒体，Lin等人\cite{lin2012apfec}通过在无线局域网链路上对数据包进行FEC编码，提升了视频传输的效果。更多的其他研究者选择结合视频编码自身以帧和画面组（Group of Pictures, GOP）进行编码的特性，进行FEC编码以提升视频传输质量。Shih等人\cite{shih2016framefec}通过对视频中的关键帧进行FEC保护，提升了关键帧以及后续多个依赖关键帧的画面质量，有效提升了视频传输质量。Xiao等人\cite{xiao2012subgopfec}使用贪心算法动态决定每个冗余组需要包含的帧数量及冗余度，在不牺牲延迟的情况下提升了视频质量。Yang等人\cite{yang2003qualitygopfec}通过估算不同的数据包丢包后对解码视频的影响时间，动态选择FEC参数以提升用户的视频观看体验。Kurdoglu等人\cite{kurdoglu2017fecwithquantation}则将FEC冗余率与编码帧率、编码量化参数及编码方式等联合优化，以最佳化用户观看体验而非追求更高的单一量化指标。总体而言，XOR码和R-S编码相比简单复制冗余具有更高的冗余恢复效率，因此被广泛应用于实时音视频传输等场景。

然而，R-S编码通常以数据组为单位进行编码与恢复，其恢复能力依赖于单个编码组中的丢包数量不超过冗余包数量$k$。实际网络上的丢包并不是独立的，在部分链路上可能由于链路拥塞、无线信号衰减等原因出现连续的突发丢包。在这些场景下如果使用R-S编码进行丢包恢复，为了能成功恢复数据，必须按照最差的可能情况决定$n$与$k$的相对取值，而这通常使得算法对网络的状况产生过于悲观的估计，为了应对短暂出现的连续丢包而将$k$的值始终维持在较高水平。这导致在其他未遭遇连续丢包的数据组中，大量的冗余包被浪费，占用了传输带宽而未能有效地提升传输质量。为解决此问题，研究者们提出了交织（Interleave）技术。如图\ref{fig:交织示意图}所示，交织技术将多个编码组交替地在网络上发出，使得当传输过程中出现了连续丢包时，丢包被分散在多个不同的编码组中分别应对，使得单个编码组需要应对的丢包比例大大下降，从而降低了整体需要的冗余率。

\begin{figure}[H]
    \centering
    \includegraphics[width=.7\linewidth]{interleaved_fec.drawio.pdf}
    \caption{交织编码示意}
    \label{fig:交织示意图}
\end{figure}

Liu等人\cite{liu2017opticalinterleave}提出了一种在开放光通信场景下利用交织应对连续丢包的方法。该方法通过马尔科夫链对网络的状态进行建模，通过测量信道的“开启时间”和“中断时间”，估计信道的连续丢包长度和数据包接收时间特性，同时综合考虑缓冲区大小、FEC恢复丢包数量上限等因素，联合优化交织参数和FEC参数。Yin等人\cite{yin2021intrablockfec}将FEC交织编码应用于多跳无线网络的物联网场景中，在每一跳的转发设备上都利用上游设备的FEC编码对发送内容进行恢复后再重新编码发送至下游。作者提出了一种利用力学中势能概念衡量交织性能的方法，同时提出了一种基于此指标对交织参数进行优化的算法。

分组冗余码通过设计比简单复制更复杂的冗余信息计算和丢失包解算机制，允许通过调整参数动态变化冗余率以适应不同丢包率的网络环境。结合交织技术，可以有效地应对真实网络中存在的连续丢包等特性，得到了广泛的应用。

\subsection{流式冗余码（Streaming码）}

XOR、R-S等分组码结合交织已经能较好地应对网络中的丢包问题，但是这些编码仍旧不能满足一些实时性需求高的应用。如图\ref{fig:RS编码等待恢复延迟}，由于分组码的冗余包通常是通过对所有的组内的数据包进行计算得到，因此冗余信息必须在所有数据包已经发出后才能够计算并在网络中发出，这导致如果接收端在接收数据包时如果检测到了丢包且需要利用冗余信息进行恢复，为了保证数据包数据包按发送顺序连续交付至上层应用，接收端通常需要暂停后续数据的解码输出，直至对应的冗余包到达并完成恢复。由此产生的恢复等待时间会显著增加端到端时延。对于实时性要求较高的应用，即使最终能够恢复出丢失数据，其对应的视频帧或音频数据也可能已经错过播放时限，从而无法有效改善用户体验。

\begin{figure}[H]
    \centering
    \includegraphics[width=.7\linewidth]{rs_code_slow_recovery.drawio.pdf}
    \caption{分组码需要暂停解码输出等待冗余包到来才能恢复丢包并继续解码过程}
    \label{fig:RS编码等待恢复延迟}
\end{figure}

基于此，Martinian等人提出了流式编码（Streaming Code）\cite{martinian2004streamingcode}。与传统基于固定编码块的FEC不同，流式编码采用跨时间窗口的卷积式编码结构，将同一时刻数据包的冗余信息分散嵌入到后续多个时刻发送的数据包中，从而在时间维度上持续提供保护。例如，某一时刻$t=0$发送的数据，其相关冗余不仅存在于当前数据包中，还会被逐步附加到$t=1,2,3$等后续时刻发送的数据包内。当$t=0$时刻的数据包发生丢失时，接收端可以利用后续若干时刻收到的数据包逐步恢复其内容，并在预设的有限解码时延内完成恢复，而无需等待整个编码块全部发送完成。该机制能够在保证连续突发丢包恢复能力的同时，显著降低恢复延迟，更适用于实时流媒体等低时延传输场景。Martinian等人进一步证明了，在给定码率与突发丢包长度条件下，流式编码能够达到理论上的最小恢复时延下界。已经有一些研究工作\cite{emara2021streamingcodevoip,rudow2023tambur}尝试将流式编码应用于实时音视频通信领域，获得了一定的效果提升。

前向纠错技术逐渐从早期基于简单重复发送的冗余机制，发展到结合有限域运算的分组纠删码，并进一步演化出结合交织技术与时间维度编码的低时延流式编码结构。不同类型的FEC机制在冗余开销、连续丢包恢复能力以及恢复时延等方面各有侧重：简单复制具有实现简单、恢复迅速的特点，但冗余效率较低；XOR码与R-S码等分组码能够显著提高冗余恢复效率，但通常需要等待整个编码组完成后才能进行恢复；而流式编码则通过跨时间窗口的连续冗余保护，在保证突发丢包恢复能力的同时进一步降低了解码等待时延，更适用于实时音视频通信等低时延场景。因此，如何在冗余率、恢复能力与恢复时延之间取得平衡，已经成为当前链路质量优化与实时媒体传输中的重要研究方向。

尽管现有FEC技术已经能够有效提升低质量网络环境中的数据恢复能力，但大多数研究主要关注编码结构本身的恢复性能、冗余效率以及恢复时延等问题，通常默认数据传输路径已经固定，而较少进一步考虑不同网络链路之间的质量差异与成本差异。在跨域云网络场景下，不同链路可能同时具有显著不同的传输性能与租赁成本，如何结合链路状态动态选择冗余保护策略，并进一步联合流量调度共同优化整体传输性能与网络成本，仍然是值得进一步研究的问题。

\section{软件定义网络与网络调度}

软件定义网络（Software defined networking, SDN）指的是将网络中各个转发设备的数据平面与控制平面解耦，集中进行控制的网络。SDN网络大大简化了网络的管理和控制流程。对于跨域云网络及其中部署的虚拟网络，尽管有部分的网络设备由SDN统一控制，但是各个设备间的跨域互联通常仍仍旧由传统的网络设备提供连接，形成了混合形软件定义网络（hybrid SDN network），如图\ref{fig:混合SDN网络}\cite{amin2018hybridsdnsurvey}。

\begin{figure}[H]
    \centering
    \includegraphics[width=.8\linewidth]{sdn_overview.drawio.pdf}
    \caption{混合SDN网络}
    \label{fig:混合SDN网络}
\end{figure}

随着云计算与实时互联网应用的发展，现代云网络中的跨域流量规模持续增长，用户对于传输质量与服务稳定性的要求也不断提高。在跨地域云网络场景中，不同节点之间通常并非只存在单一的物理连接路径，而是可能存在多种不同质量、不同价格的传输链路。例如，许多云服务商同时提供公网链路互联与专线链路互联\cite{azure_bandwidthcost,gcp_bandwidthcost}。其中，专线链路通常具有更稳定的传输性能、更低的丢包率与时延，但部署成本与使用成本较高；而公网链路虽然成本较低，却容易受到网络拥塞、跨域路由波动等因素影响，出现高丢包、时延抖动等问题\cite{kataria2024titan}。与此同时，链路质量与网络负载往往还会随着时间动态变化，使得不同链路在不同时间段内呈现出不同的性能特征。

在这种场景下，仅依赖传统网络静态地选择固定传输路径，难以同时满足不同业务对吞吐、时延、可靠性以及成本控制等方面的需求。相比之下，基于SDN的覆盖网络能够通过集中控制的方式，对网络中的链路状态、节点负载以及业务需求进行统一管理，并动态地对流量进行调度与路径选择，从而更灵活地利用不同网络资源，在传输性能、可靠性与成本之间取得平衡。因此，如何基于覆盖网络与SDN架构实现高效的网络调度，逐渐成为跨域云网络与实时媒体传输领域的重要研究方向。

最初的一些工作主要集中在覆盖网络的建立与路由绕行方面。覆盖网络的概念最初由Anderson等人提出\cite{andersen2001RON}，该工作中介绍了RON这一实验性覆盖网络。该工作提出了将公网中并不直接相连的一些节点重新抽象为一个覆盖网络中的相邻节点，称为RON节点。各个RON节点之间通过公网建立连接，形成Overlay网络中的虚拟链路。除了转发功能，RON节点间还可以通过主动探测的方式，对建立虚拟链路所依靠的物理链路质量进行实时测量，并将测量结果汇总至控制器。当客户端希望通过RON网络进行连接时，控制器将将综合考虑覆盖网络中所有可用的连接的质量，选择最符合客户端的传输需求的链路对流量进行调度。Roy等人\cite{roy2009relayplacement}根据路由可靠性和TCP性能建立指标，并以此为标准优化转发节点的选择。作者提供了多种不同的算法，包括贪心算法、随机算法及两者的混合算法，分别对两种指标存在不同的侧重，供用户灵活根据需要选择。

之后的一些研究进一步研究了通过流量调度实现对资源利用的优化。CRONets\cite{cai2016cronets}提出了利用云网络服务商提供的虚拟机网络网络链路建立覆盖网络的方案，并利用多路径TCP在覆盖网络节点间提升性能。在覆盖网络资源规模进一步扩大的背景下，研究者开始关注如何通过集中式调度提升资源利用效率。B4\cite{jain2013b4}则提出了通过流量调度和流量工程，有效分配不同链路的负载以最大化链路使用率的方法。BDS\cite{zhang2018bds}使用统一的中央控制器持续监控不同覆盖网络间节点的可用资源，动态调度传输路径以实现对链路的带宽的充分利用。除了单纯追求更高链路利用率，一些研究开始进一步联合考虑性能与部署成本之间的平衡。Skyplane\cite{jain2023skyplane}则观察到云网络提供商不同地域资源的定价差异，将追求文件传输最大吞吐量与追求更低租赁成本建模为一个线性优化问题，给定其中一个指标的限制，利用算法最优化另一个指标。Titan\cite{kataria2024titan}则针对持续运行的流媒体服务将租用云网络互联资源成本纳入考量，在维持用户体验在一定水平之上的前提下，动态调度流量与计算资源，降低整体的网络部署成本。与此同时，随着实时媒体等对服务连续性要求更高的应用出现，部分工作开始关注链路状态变化时的快速恢复能力。Troia等人\cite{troia2022sdnfastrecovery}利用eBPF技术实时检测各个覆盖网络节点的传输状态，并在检测到链路拥塞或其他链路质量变化事件时，快速重新触发流量调度算法以维持高质量连接。XRON\cite{wu2023xron}则同时结合链路成本优化、资源利用与快速恢复，主动探测可用的公网链路与专线链路质量，结合未来用户流量需求预测，持续计算和更新成本最佳的流量调度策略。为保持所承载音视频通话的服务质量，计算多个备用调度方案以确保故障条件的快速恢复。

