Bufferless Transmission in Complex Networks

Cunlai Pu, Wei Cui, Jiexin Wu, Jian Yang

TL;DR

This paper explores data transmission in "bufferless" networks—such as networks-on-chip (NoC) and optical burst switching systems—using principles from network science. The authors propose a novel deflection routing mechanism and demonstrate that factors like packet generation rate, node capacity, and network topology have surprising, non-monotonic effects on network performance, proving that standard shortest-path routing is highly suboptimal for these environments.

What Problem Does This Paper Address?

Most research in network science focuses on "store-and-forward" networks (like the Internet), where nodes have memory buffers to hold packets during traffic congestion. However, many modern, high-speed micro-architectures are bufferless due to strict energy, physical space, and real-time constraints. In these networks, packets cannot wait at a node; they must be forwarded immediately or dropped.

Because traditional routing algorithms assume the existence of buffers to smooth out traffic spikes, they fail gracefully in bufferless environments. This paper addresses the gap in applying complex network theories to bufferless systems, specifically focusing on how to handle "forwarding competition" (when multiple packets want the same output port) without relying on traditional memory buffers.

Methods

The authors simulate bufferless networks using the Price model to generate synthetic scale-free network topologies with tunable power-law degree distributions. To manage traffic, they combine two main techniques:

  1. Efficient Routing Protocol: They use a static routing protocol governed by a tunable parameter, $\alpha$. When $\alpha = 0$, the protocol uses standard shortest-path routing. As $\alpha$ increases, the protocol artificially inflates the "cost" of high-degree nodes (hubs), encouraging packets to take slightly longer routes to avoid central bottlenecks.
  2. Delivery Queue-Based Deflection Mechanism: To handle collisions, they introduce a custom deflection strategy. Every node has a delivery capacity proportional to its degree. If a packet's intended next-hop node is "full" (its delivery queue is at capacity), the packet "deflects" by randomly checking other neighboring nodes. If all neighbors are full, the packet is permanently discarded.

The system is evaluated using three primary metrics: average deflection times ($\omega$), packet loss rate ($\eta$), and average arrival time ($T_a$).

Datasets

Not discussed in the paper. The study relies entirely on synthetic scale-free networks generated via the Price model; no real-world datasets were used.

Key Insights and Ideas

  • Non-monotonic behaviors are everywhere: The relationship between network parameters and performance isn't straightforward. For example, as node delivery capacity increases, average deflection times first increase (because nodes can accept more deflected packets instead of dropping them) and then decrease (because higher capacity means fewer packets need deflecting in the first place).
  • Shortest path is a trap: In bufferless networks, strictly routing packets via the shortest path ($\alpha=0$) leads to terrible performance. Hubs get overwhelmed instantly, resulting in massive packet loss.
  • There is a mathematical "sweet spot" for routing: Tuning the routing parameter $\alpha$ reveals an optimal point where packets are slightly diverted through smaller-degree nodes. This balances the network load, minimizing packet loss, deflection times, and overall travel time.
  • Homogeneity is a double-edged sword: Making the network's degree distribution more even (less reliant on massive hubs) initially increases deflection times and packet loss due to longer average path lengths. However, as it becomes even more homogeneous, performance improves again because traffic is distributed more fairly across the network.

Key Results

  • Packet Generation Rate ($\rho$): When the packet generation rate exceeds a critical threshold (around 0.2 to 0.3 in their simulations), deflection times and packet loss spike abruptly. Interestingly, at very high generation rates, the average arrival time actually drops. This is a survivor bias effect: heavily deflected packets are simply discarded, leaving only the "lucky" fast-arriving packets to be measured.
  • Optimal Routing Parameter: By varying the routing control parameter $\alpha$, the authors found a distinct performance optimum at $\alpha \approx 0.4$. At this value, deflection times, packet loss, and arrival times all hit their minimums.
  • Network Scaling: As the network grows in size (more nodes), the average path length increases, and more packets are injected simultaneously. If node capacities remain fixed, this leads to a strict deterioration in all transmission performance metrics.

Limitations and Future Work

The authors acknowledge this is a preliminary theoretical effort to bridge network science and bufferless communication systems. The study is entirely simulation-based using synthetic scale-free networks and uniform, randomized traffic generation. This setup may not perfectly capture the bursty, highly correlated traffic patterns of real-world on-chip or optical networks. Future work could involve applying these theoretical insights to physical hardware architectures and developing dynamic routing protocols tailored for specific, real-world bufferless environments.

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