Implementation

In this section, we delve into the implementation detail of Unison. The implementation is based on ns-3.36.1 and consists of approximately 3100 lines of code. Applying Unison to other network simulators based on DES (e.g., OMNeT++) is straightforward and is undergoing(正在进行的). We also address several practical challenges during the implementation.

在本节中，我们将深入研究 Unison 的实现细节。该实现基于 ns-3.36.1，包含大约 3100 行代码。将 Unison 应用于基于 DES 的其他网络模拟器（例如 OMNeT++）非常简单，并且正在进行中。我们还解决了实现过程中的几个实际挑战。

The first challenge is to resolve thread-safety issues while minimizing the overhead. To achieve this, Unison has been carefully implemented to ensure lock-free execution, allowing the recording of global statistics seamlessly (无缝的) (§5.1).

第一个挑战是解决线程安全问题，同时尽量减少开销。为此，Unison经过精心实现，确保了无锁执行，从而能够无缝记录全局统计信息（§5.1）。

The second challenge is to achieve determinism and scalability. We introduce a tie-breaking rule of simultaneous events for deterministic (确定性的), reproducible (可重复的) simulation. We also implement a hybrid simulation kernel with Unison for scalable, distributed simulation (§5.2).

第二个挑战是实现确定性和可扩展性。我们引入了同时事件的决策规则，以确保仿真的确定性和可重复性。此外，我们还与Unison实现了一个混合仿真内核，用于可扩展的分布式仿真（§5.2）。

Lock-Free Execution

The objective of the lock-free execution is to allow threads to process LPs in a lock-free manner, either through the use of atomic operations or by circumventing (规避) the need for synchronization. Using such a manner can reduce 𝑃 by alleviating the cost of accessing shared data, which happens frequently during the simulation. It can also reduce 𝑆 by reducing the overhead of the scheduler, and reduce 𝑀 by reducing the overhead of cross-LP event insertion.

锁无执行的目标是允许线程以锁无的方式处理LP，要么通过使用原子操作，要么通过避免同步需求。使用这种方式可以通过减少访问共享数据的成本来降低𝑃，这在仿真过程中经常发生。它还可以通过减少调度程序的开销来降低𝑆，并通过减少跨LP事件插入的开销来降低𝑀。

To achieve this objective, Unison divides each round into four phases as depicted in Figure 7. During phase changes, a barrier or a thread release is required, which are both implemented using atomic operations.

为了实现这一目标，Unison将每轮划分为四个阶段，如图7所示。在阶段切换期间，需要使用屏障或线程释放，这两者都通过原子操作实现。

Lock-free execution 并发技术

Lock-free execution 是一种并发编程技术，旨在避免使用传统的锁机制来 管理多线程环境中的共享资源访问。传统的锁机制（如互斥锁、信号量等）虽然能确保线程安全，但 往往会导致线程阻塞，从而带来性能开销，特别是在高并发环境下。

在 lock-free execution 中，通过使用原子操作（如比较并交换，compare-and-swap，CAS）或者设计巧妙的算法，多个线程可以同时访问和修改共享资源，而不会因为锁定资源而阻塞其他线程。这种方式不仅提高了并发度，还减少了上下文切换和锁争用带来的开销，进而提升系统的整体性能和可扩展性。

换句话说，lock-free execution 通过尽量避免线程在访问共享资源时的阻塞，使得系统在高并发情况下能够更高效地执行任务。这种技术在高性能计算、实时系统、分布式系统等对性能和响应时间有较高要求的场景中尤为重要。

Processing events. In this phase, Unison first runs the scheduler to assess the priority of LPs and assign LPs to threads as described in §4.3. However, when scheduling interLP events, thread-safety issues arise as the FEL of the target LP can be manipulated by multiple threads. To avoid this situation, Unison uses mailboxes as a cache for inter-LP events. Before the simulation starts, each LP creates a mailbox for any LP it has a connection with. Inter-LP events are first stored in one of the mailboxes of the target LP. These cached events will be subsequently（随后的） inserted into the FEL during the receiving event phase, making the whole event scheduling process asynchronous and lock-free.

处理事件。在这一阶段，Unison首先运行调度器，以评估LP（逻辑进程）的优先级，并按照§4.3所述将LP分配给线程。然而，在调度跨LP事件时，会出现线程安全问题，因为目标LP的FEL（未来事件列表）可能会被多个线程操作。为避免这种情况，Unison使用邮箱（mailboxes）作为跨LP事件的缓存。在仿真开始之前，每个LP都会为其连接的任何LP创建一个邮箱。跨LP事件首先被存储在目标LP的某个邮箱中。这些缓存的事件将在接收事件阶段插入到FEL中，使整个事件调度过程是异步且无锁的。

My Opinion

其实mailbox这个观点非常简单，就是维护了一个queue，保证在并行发送的同时，实现线性处理 :)

In addition to inter-LP event scheduling, the underlying architecture of ns-3 is not thread-safe as well. We perform the following modifications to ns-3 for thread safety:

除了跨LP事件调度之外，ns-3的底层架构本身也不是线程安全的。为确保线程安全，我们对ns-3进行了以下修改：

• Reference counting. Reference counting [19] is used for automatic memory management. We replace the reference counter of ns-3 objects, packet tags and packet buffers with an atomic integer counter. We also disable the lookup cache of aggregated objects.

Explanation

1. 引用计数的作用：

   • 在ns-3中，每个对象都有一个引用计数器，记录当前有多少个地方在使用这个对象。例如，如果一个对象被两个不同的函数使用，那么它的引用计数就是2。当一个函数不再需要这个对象时，它会将引用计数减1。当引用计数降到0时，意味着没有任何地方在使用这个对象，系统就会释放这个对象的内存。

2. 线程安全问题：

   • 在多线程环境中，如果多个线程同时访问和修改一个对象的引用计数，可能会导致竞争条件（race condition），从而引发不一致或崩溃等问题。例如，两个线程可能同时试图减少引用计数，但由于缺乏同步机制，引用计数器可能会被错误地更新，从而导致对象在仍然被使用时被释放，或者永远不会被释放。

3. 使用原子操作解决线程安全问题：

   • 为了避免上述的线程安全问题，Unison系统将ns-3中对象的引用计数器替换为“原子整型计数器” (atomic integer counter)。原子操作是一种底层机制，能够确保即使在多线程环境下，某个操作（如增加或减少引用计数）也能在没有中断的情况下完整执行。通过这种方式，多个线程可以安全地同时操作同一个计数器，而不会引发数据不一致问题。

4. 禁用查找缓存 (lookup cache)：

   • 在ns-3中，某些对象（特别是聚合对象）会使用查找缓存来加速数据访问。然而，查找缓存可能会在多线程环境中引发竞争条件或数据不一致问题。为了避免这些问题，Unison禁用了这些对象的查找缓存，从而确保系统在多线程环境下的稳定性。

• Buffer recycling. Packet buffers and metadata are recycled via a global linked list to reduce memory allocation calls. We disable this mechanism by allocating/freeing memory every time a new buffer is created/deleted.

Explanation

Buffer Recycling（缓冲区回收） 是一种内存管理技术，通常用于减少频繁的内存分配和释放操作，以提高性能。在网络仿真中，数据包缓冲区和元数据（如包头信息）会被频繁创建和销毁。为了避免每次都进行昂贵的内存分配操作，一种常见的方法是使用全局链表来回收和重用这些缓冲区。

1. 缓冲区回收机制的工作原理：

   • 在传统的缓冲区回收机制中，当一个数据包缓冲区或相关的元数据不再使用时，它不会立即被系统释放，而是被放入一个全局链表中。这个链表中保存了一些已经被使用过但可以重复使用的缓冲区。
   • 当系统需要新的缓冲区时，它首先检查这个全局链表。如果链表中已经有可用的缓冲区，那么它会直接重用这些缓冲区，而不是进行新的内存分配。这样做可以减少频繁的内存分配和释放操作，从而提升系统性能。

2. 禁用缓冲区回收的原因：

   • 在多线程环境中，多个线程可能同时访问和修改这个全局链表，容易引发竞争条件（race condition）和数据不一致问题。为了保证线程安全性，通常需要使用锁（locks）或其他同步机制来保护这个链表。然而，使用锁会引入额外的开销，并可能导致性能下降。
   • 为了避免这些复杂性和潜在的线程安全问题，Unison选择禁用缓冲区回收机制。每当需要新的缓冲区时，系统都会直接分配新的内存，而不是从链表中重用旧的缓冲区。同样地，当缓冲区不再需要时，系统会立即释放其内存，而不会将其放入链表中。

3. 禁用的效果：

   • 虽然禁用了缓冲区回收机制可能会增加内存分配和释放的次数，但这样做简化了内存管理逻辑，并确保了线程安全性，避免了由全局链表引发的复杂同步问题。

为了减少线程安全性方面的复杂性和避免可能的性能问题，Unison选择禁用了缓冲区回收机制。每次创建或删除缓冲区时，都直接分配或释放内存，而不依赖全局链表来回收和重用缓冲区。

• Flow monitor. The flow monitor is widely used for flow tracking [6]. It saves statistics of tracked packets and flows into maps shared across nodes. Since new flows and packets can be inserted into the map concurrently, we use atomic operations to make these maps thread-safe.

Explanation

Flow Monitor（流量监控器） 是一种用于网络仿真中的工具，用于跟踪和记录数据包和流量（flow）的统计信息。在网络仿真中，流量监控器会保存和处理大量的统计数据，这些数据通常以映射（map）的形式存储，这些映射在整个仿真系统中的不同节点之间共享。

1. 流量监控器的工作原理：

   • 在网络仿真中，每个数据包和流量（flow）都有特定的统计信息，例如数据包的到达时间、流量的字节数、延迟等。流量监控器负责跟踪这些信息，并将它们保存到一个共享的映射结构中。
   • 这些映射通常是键值对（key-value pairs），键可以是流量或数据包的标识符，值是与该流量或数据包相关的统计信息。由于仿真中会有许多节点，这些映射数据通常是跨多个节点共享的。

2. 线程安全问题：

   • 在多线程环境中，可能有多个线程同时处理不同的数据包或流量。当新数据包或流量被插入到映射中时，如果没有适当的同步机制，不同线程的操作可能会冲突，导致数据不一致或仿真错误。例如，一个线程可能在另一个线程还没有完成其操作之前修改了共享映射，这可能会导致统计信息的丢失或错误。

3. 原子操作的使用：

   • 为了避免这些线程安全问题，Unison在处理这些共享映射时使用了原子操作（atomic operations）。原子操作是指那些可以在不被其他操作打断的情况下执行的基本操作，确保对共享数据的访问是安全的。
   • 通过使用原子操作，可以确保即使多个线程同时试图插入新流量或数据包，操作也是安全的，不会导致数据不一致。这使得流量监控器在多线程环境中更加可靠和稳定。

流量监控器用于追踪网络仿真中的数据包和流量统计信息，这些信息存储在跨节点共享的映射结构中。为了在多线程环境中避免数据冲突和保持数据一致性，Unison使用原子操作来保证这些映射的线程安全性。这种方法确保了新流量和数据包在并发插入时不会导致仿真错误。

• NIx-vector routing. NIx-vector routing speeds up route decisions with a neighbor index cache [33]. The cache is shared globally and will be re-calculated if it is dirty. We replace the dirty state variable with a boolean atomic variable and use atomic operations to protect the cache.

Explanation

NIx-vector routing 是一种加速路由决策的机制，主要通过使用一个邻居索引缓存（neighbor index cache）来实现。这个缓存被全局共享，并且当缓存中的数据不再准确（即缓存变“脏”时），需要重新计算缓存内容。

1. NIx-vector routing 的工作原理：

   • NIx-vector routing 使用了一种称为“邻居索引缓存”的机制来加速路由决策。在网络仿真中，路由决策是指确定数据包从一个节点到达另一个节点所需要的路径。通常，这涉及查找和计算路径，这个过程可能非常耗时。
   • 邻居索引缓存 存储了节点之间的路径信息，这样可以在需要进行路由决策时快速查找，而不必每次都重新计算路径。因此，缓存的使用可以显著加快路由决策过程。

2. 缓存的“脏”状态：

   • 在路由过程中，网络拓扑可能发生变化，例如节点之间的连接断开或新的连接建立。这些变化会使当前缓存中的路径信息变得不再准确，称为缓存“脏”了。
   • 当缓存变脏时，系统需要重新计算和更新缓存中的数据，以确保后续的路由决策是基于最新的网络拓扑信息。

3. 原子操作的使用：

   • 为了确保缓存的一致性和线程安全，Unison 在处理缓存“脏”状态时，引入了一个布尔类型的原子变量来表示缓存是否“脏”。
   • 使用原子操作来保护这个缓存和管理“脏”状态，意味着当多个线程同时访问和更新缓存时，能够确保缓存状态的改变是安全的，不会导致数据不一致或竞态条件（race condition）。
   • 例如，如果一个线程在缓存更新过程中将缓存标记为“脏”，另一个线程在读取缓存状态时，通过原子操作可以确保它读取到的状态是准确的，避免了可能的同步问题。

NIx-vector routing 利用邻居索引缓存来加速路由决策，并且这个缓存是全局共享的。当缓存变“脏”时，需要重新计算其内容。为了解决多线程环境下的同步问题，Unison 使用了布尔类型的原子变量来表示缓存的“脏”状态，并通过原子操作确保缓存更新过程的线程安全性。这样可以保证路由决策的准确性和缓存的一致性。

Handling global events. In this phase, Unison checks the public LP for any global events at the current time and processes them with the main thread. Unison will recompute the lookahead value if a topology change occurs when processing global events as discussed in §4.2.

处理全局事件 在这个阶段，Unison 会检查公共 LP 是否在当前时间有任何全局事件，并使用主线程处理这些事件。如果在处理全局事件时发生拓扑变化，Unison 会重新计算预取值（lookahead value），如第4.2节所述。

Receiving events. In this phase, LPs are reallocated to threads according to their priority in the first phase. Each LP then retrieves all events from its mailboxes and inserts them into the FEL. The FEL orders the inserted events automatically by their timestamps. In the case of two events having the same timestamp, they are ordered using the tie-breaking rule (§5.2) for deterministic simulation.

接收事件 在这个阶段，LP 会根据它们在第一阶段的优先级重新分配给线程。每个 LP 然后从其邮箱中检索所有事件，并将它们插入到 FEL 中。FEL 会根据事件的时间戳自动对插入的事件进行排序。如果两个事件具有相同的时间戳，它们将使用第5.2节中描述的决策规则进行排序，以确保仿真的确定性。

Updating the window. The last phase is to calculate and update the LBTS of every LP of the next round according to Equation (2). If there are no more events to be executed for all LPs, the simulation terminates.

更新时间窗口 最后一个阶段是根据公式(2)计算并更新下一轮中每个 LP 的 LBTS（最低边界时间戳）。如果所有 LP 都没有更多的事件需要执行，仿真将终止。

Improving Usability

Deterministic simulation. To address the indeterminacy caused by simultaneous events, Unison introduces the following tie-breaking rule. When scheduling an inter-LP event, the timestamp of the sender LP and the event ID (which indicates the number of events created in the current LP) are sent along with the event itself.

struct Event {
    int timeStamp;
    eventID_t eventID; // the number of events created in the current LP
    string content; // event itself
};

If the timestamps of two events are the same, the event with a smaller timestamp of the sender LP is processed first. If the sending timestamps are still the same, the event from the LP with the smaller ID will be processed first. If two events are still scheduled by the same LP, then the event with a smaller event ID will be processed first. As all events in the mailboxes have a total order, Unison is guaranteed to have a deterministic result.

确定性仿真。为了解决由同时发生的事件引起的不确定性，Unison 引入了以下决策规则。当调度一个跨 LP 的事件时，发送方 LP 的时间戳和事件 ID（指示当前 LP 中创建的事件数量）会与事件一起发送。如果两个事件的时间戳相同，则先处理发送方 LP 时间戳较小的事件。如果发送方的时间戳仍然相同，则先处理 ID 较小的 LP 发送的事件。如果两个事件仍然由同一个 LP 调度，则先处理事件 ID 较小的事件。由于邮箱中的所有事件都有一个全序，Unison 可以保证获得确定性的仿真结果。

Scalable hybrid simulation. For scalability across multiple hosts, we also implemented a hybrid simulation kernel with Unison. In this approach, the network topology is first divided into several large partitions according to the barrier synchronization algorithm (§2.3) to map each host. Each host then runs its large partition using Unison for further fine-grained partition as illustrated in Figure 6.

可扩展的混合仿真。为了在多主机间实现可扩展性，我们还使用 Unison 实现了一个混合仿真内核。在这种方法中，首先根据屏障同步算法（§2.3）将网络拓扑划分为几个大的分区，以映射到每个主机。然后，每个主机使用 Unison 在其大的分区内进行进一步的细粒度划分，如图 6 所示。

For correct synchronization, the receiving event stage is modified to handle inter-host events. After intra-host events are received from the mailboxes, inter-host events are then received by the main thread. When updating the window, the smallest timestamp of the next event of every local LP is calculated first, followed by an all-reduce operation to calculate the global smallest timestamp. Given the global smallest timestamp, the time window of the next round is finally updated using Equation (2).

为了正确同步，接收事件阶段被修改为处理主机间的事件。首先从邮箱接收主机内部的事件，然后由主线程接收主机间的事件。在更新窗口时，首先计算每个本地主机逻辑进程（LP）下一个事件的最小时间戳，接着执行一次全规约操作以计算全局最小时间戳。根据全局最小时间戳，最终使用方程 (2) 更新下一轮的时间窗口。