English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The problem of detecting loops in a forwarding network is known to beNP-complete when general rules such as wildcard expressions are used. Yet,network analyzer tools such as Netplumber (Kazemian et al., NSDI'13) orVeriflow (Khurshid et al., NSDI'13) efficiently solve this problem in networkswith thousands of forwarding rules. In this paper, we complement suchexperimental validation of practical heuristics with the first provablyefficient algorithm in the context of general rules. Our main tool is acanonical representation of the atoms (i.e. the minimal non-empty sets) of thefield of sets generated by a collection of sets. This tool is particularlysuited when the intersection of two sets can be efficiently computed andrepresented. In the case of forwarding networks, each forwarding rule isassociated with the set of packet headers it matches. The atoms then correspondto classes of headers with same behavior in the network. We propose analgorithm for atom computation and provide the first polynomial time algorithmfor loop detection in terms of number of classes (which can be exponential ingeneral). This contrasts with previous methods that can be exponential, even insimple cases with linear number of classes. Second, we introduce a notion ofnetwork dimension captured by the overlapping degree of forwarding rules. Thevalues of this measure appear to be very low in practice and constantoverlapping degree ensures polynomial number of header classes. Forwarding loopdetection is thus polynomial in forwarding networks with constant overlappingdegree.

Efficient Loop Detection in Forwarding Networks and Representing Atoms in a Field of Sets