Fault Adaptive Routing in Metasurface Controller Networks

Taqwa Saeed, Constantinos Skitsas, Dimitrios Kouzapas, Marios Lestas, Vassos Soteriou, Anna Philippou, Sergi Abadal, Christos Liaskos, Loukas Petrou, Julius Georgiou, Andreas Pitsillides

TL;DR

This paper introduces lightweight, fault-tolerant routing algorithms designed for the "HyperSurface"—a reconfigurable metasurface controlled by an embedded network of tiny, asynchronous controllers. By adapting traditional XY routing to handle hardware-constrained, irregular Manhattan topologies, the authors provide a path toward reliable "software-defined" control of electromagnetic waves even when individual controller nodes fail.

What Problem Does This Paper Address?

Metasurfaces are planar structures that can manipulate electromagnetic waves (e.g., for beam steering or perfect absorption). The next frontier is the HyperSurface (HSF): a metasurface where these properties are software-controllable via an embedded network of miniaturized controllers (ASICs).

However, building this control network (CN) is a massive engineering challenge. Unlike standard Networks-on-Chip (NoC), these networks are:

  1. Asynchronous: To avoid electromagnetic interference from a global clock.
  2. Resource-Constrained: Tiny meta-atoms leave little room for complex buffers or routing tables.
  3. Irregular: They use a "Manhattan-like" topology but often lack edge wrap-around links due to hardware complexity.
  4. Fault-Prone: In a dense array of thousands of tiny controllers, some will inevitably fail.

Traditional fault-tolerant routing is too "heavy" (requiring expensive virtual channels or large headers) for this environment. This paper seeks a "lightweight" alternative that ensures data reaches its destination despite node or link failures.

Methods

The authors propose two fault-adaptive routing schemes based on the classic XY routing (where a packet moves horizontally then vertically):

  • Loop-Free Algorithm (LFA): This is a reactive approach. A packet starts with XY routing. If it hits a faulty link, it switches to YX routing. To prevent infinite loops (live-locks), the algorithm uses "turn prevention" rules—restricting certain 90-degree turns in the vicinity of a fault to break potential cycles.
  • Reliable Delivery Algorithm (RDA): This is a proactive approach designed for high reliability. It identifies two disjoint paths (one clockwise, one counter-clockwise) between any two nodes. If the primary path is blocked by a fault, the packet is rerouted to the alternative path that does not overlap with the first.

To test these, the authors developed a custom tool: the HSF CN Asynchronous Simulator (HCNAS), built on the AnyLogic platform. This simulator specifically models the four-way handshake protocol required for asynchronous communication between controllers.

Datasets

The paper does not use external datasets. Instead, it evaluates the algorithms using a synthetic simulation environment:

  • Topology: A 24 × 24 grid of controller nodes.
  • Fault Model: A random fault model where each node has a probability of failure ($P_f$) ranging from 0.0 to 0.08.
  • Traffic: Packets are sent from an input Gateway (GW) to various destinations, with Acknowledgement (ACK) packets sent back to a dedicated ACK Gateway.

Key Insights and Ideas

  • The Deadlock Dilemma: Standard XY routing, which is usually deadlock-free in 2D meshes, can actually cause deadlocks in this specific HSF topology because of the interaction between data packets and ACK packets. The authors had to develop an "orientation-aware" variant of XY routing to fix this.
  • Asynchrony as a Constraint: Because there is no global clock, the routing must rely on local handshakes. This makes traditional "look-ahead" routing much harder.
  • Distance Matters: Success rates are not uniform across the surface. Nodes further from the Gateway (the "Fourth Quarter") show significantly lower delivery success as the probability of encountering a fault increases along the longer path.
  • Simplicity is Key: By avoiding virtual channels and complex routing tables, the proposed algorithms keep the ASIC area and power consumption low enough to fit within the tiny footprint of a meta-atom.

Key Results

  • RDA Performance: The Reliable Delivery Algorithm achieved over 98% successful delivery at a node failure probability of 0.01.
  • Resilience Threshold: Success rates for RDA remained relatively high but dropped below 90% once the failure probability exceeded 0.04.
  • LFA Effectiveness: In scenarios with a single fault along the path, the LFA achieved a 100% success rate, demonstrating its ability to successfully navigate around isolated failures without entering loops.
  • Gateway Sensitivity: The discrepancy between data delivery and ACK delivery (shown in Figure 7) highlights that the return path is often the "weak link" in reliable communication.

Limitations and Future Work

  • Single Fault Optimization: The current version of the Loop-Free Algorithm (LFA) is primarily evaluated and optimized for single-fault scenarios. Its performance in high-density "fault clusters" needs further study.
  • Simplified Fault Models: The authors acknowledge the need for more sophisticated fault models that better reflect real-world ASIC failures.
  • Hardware Validation: While the simulations are promising, the next step is testing these protocols on the physical HSF hardware prototype currently under development.
  • Guaranteed Livelock Freedom: Future work aims to refine these algorithms to provide mathematical guarantees of both deadlock and livelock freedom in even more irregular topologies.

Summary updated

Abstract

HyperSurfaces are a merge of structurally reconfigurable metasurfaces whose electromagnetic properties can be changed via a software interface, using an embedded miniaturized network of controllers, thus enabling novel capabilities in wireless communications. Resource constraints associated with the development of a hardware testbed of this breakthrough technology necessitate network controller architectures different from traditional regular Network-on-Chip architectures. The Manhattan-like topology chosen to realize the controller network in the testbed under development is irregular, with restricted local path selection options, operating in an asynchronous fashion. These characteristics render traditional fault-tolerant routing mechanisms inadequate. In this paper, we present work in progress towards the development of fault-tolerant routing mechanisms for the chosen architecture. We present two XY-based approaches which have been developed aiming to offer reliable data delivery in the presence of faults. The first approach aims to avoid loops while the second one attempts to maximize the success delivery probabilities. Their effectiveness is demonstrated via simulations conducted on a custom developed simulator.
BibTeX
@inproceedings{saeed2018fault,
  author = {Taqwa Saeed and Constantinos Skitsas and Dimitrios Kouzapas and Marios Lestas and Vassos Soteriou and Anna Philippou and Sergi Abadal and Christos Liaskos and Loukas Petrou and Julius Georgiou and Andreas Pitsillides},
  title = {{Fault Adaptive Routing in Metasurface Controller Networks}},
  booktitle = {NoCArc@MICRO},
  year = {2018},
  url = {https://openreview.net/forum?id=0kIY4xwjhf},
}

Loading related content...

Figure