Bufferless transmission in complex networks

Cunlai Pu, Wei Cui, Jiexin Wu, Jian Yang

Abstract

Complex bufferless networks such as on-chip networks and optical burst switching networks haven't been paid enough attention in network science. In complex bufferless networks, the store and forward mechanism is not applicable, since the network nodes are not allowed to buffer data packets. In this paper, we study the data transmission process in complex bufferless networks from the perspective of network science. Specifically, we use the Price model to generate the underlying network topological structures. We propose a delivery queue based deflection mechanism, which accompanies the efficient routing protocol, to transmit data packets in bufferless networks. We investigate the average deflection times, packets loss rate, average arrival time, and how the network topological structure and some other factors affect these transmission performances. Our work provides some clues for the architecture and routing design of bufferless networks.

Introduction

Most research in network science focuses on "store-and-forward" networks, such as the Internet, where nodes utilize memory buffers to manage traffic congestion. However, many modern high-speed architectures, including Networks-on-Chip (NoC) and optical burst switching systems, are increasingly bufferless due to stringent constraints on energy, physical space, and real-time latency. In these environments, packets cannot wait at a node; they must be forwarded immediately or dropped if a collision occurs.

Traditional routing algorithms often fail in bufferless systems because they assume buffers will smooth out traffic spikes. This study bridges the gap by applying complex network theory to bufferless environments, focusing on managing "forwarding competition" without traditional memory buffers.

Methodology

The study employs synthetic scale-free network topologies generated via the Price model, allowing for tunable power-law degree distributions. To manage traffic flow, two integrated techniques are proposed:

  1. Efficient Routing Protocol: A static routing protocol governed by a tunable parameter, $\alpha$. When $\alpha = 0$, the protocol follows standard shortest-path routing. Increasing $\alpha$ inflates the "cost" of high-degree nodes (hubs), encouraging packets to bypass central bottlenecks.
  2. Delivery Queue-Based Deflection Mechanism: To handle port collisions, a custom deflection strategy is introduced. Each node has a delivery capacity proportional to its degree. If a packet's intended next-hop is at capacity, it "deflects" to a random neighboring node. If all neighbors are full, the packet is discarded.

Performance is evaluated using average deflection times ($\omega$), packet loss rate ($\eta$), and average arrival time ($T_a$).

Impact of Packet Generation Rate

The packet generation rate ($\rho$) is a critical factor in network stability. Simulations reveal that when $\rho$ exceeds a threshold (approximately 0.2 to 0.3), both deflection times and packet loss rates spike abruptly as the network becomes congested.

Transmission performance metrics vs. packet generation rate ρ.

Interestingly, at very high generation rates, the average arrival time ($T_a$) actually begins to decrease. This counterintuitive result is attributed to "survivor bias": packets that are heavily deflected are eventually discarded, meaning the measured $T_a$ only accounts for the "lucky" packets that reached their destination quickly.

Optimizing Routing Strategy

A key finding is that strictly following the shortest path ($\alpha = 0$) is highly suboptimal in bufferless networks, as it leads to immediate hub congestion and high packet loss. By varying the routing control parameter $\alpha$, the researchers identified a distinct performance optimum.

Average arrival time Ta vs. routing parameter α for different network topologies (γ).

As shown in the figure above, an optimal point exists at $\alpha \approx 0.4$. At this value, traffic is balanced across the network by slightly diverting packets through smaller-degree nodes, which minimizes deflection times, packet loss, and overall arrival times across various network topologies (represented by different $\gamma$ values).

Conclusion

This research highlights the non-monotonic behaviors inherent in bufferless networks. Factors like node capacity and network homogeneity have complex effects on performance. While this theoretical study uses synthetic models and uniform traffic, it provides essential insights for designing more resilient bufferless architectures. Future work will focus on applying these principles to real-world bursty traffic patterns and physical hardware constraints.

Summary updated

Abstract

Complex bufferless networks such as on-chip networks and optical burst switching networks haven't been paid enough attention in network science. In complex bufferless networks, the store and forward mechanism is not applicable, since the network nodes are not allowed to buffer data packets. In this paper, we study the data transmission process in complex bufferless networks from the perspective of network science. Specifically, we use the Price model to generate the underlying network topological structures. We propose a delivery queue based deflection mechanism, which accompanies the efficient routing protocol, to transmit data packets in bufferless networks. We investigate the average deflection times, packets loss rate, average arrival time, and how the network topological structure and some other factors affect these transmission performances. Our work provides some clues for the architecture and routing design of bufferless networks.
BibTeX
@article{pu2018bufferless,
  author = {Cunlai Pu and Wei Cui and Jiexin Wu and Jian Yang},
  title = {{Bufferless transmission in complex networks}},
  journal = {IEEE Trans. Circuits Syst. II Express Briefs},
  year = {2018},
  doi = {10.1109/tcsii.2017.2775622},
}
Figure