[go: up one dir, main page]

Castañeda et al., 2016 - Google Patents

Compact routing messages in self-healing trees

Castañeda et al., 2016

View HTML
Document ID
16418343234359475780
Author
Castañeda A
Dolev D
Trehan A
Publication year
Publication venue
Proceedings of the 17th International Conference on Distributed Computing and Networking

External Links

Snippet

Existing compact routing schemes, eg, Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. This paper presents, to our knowledge, the first self-healing compact routing scheme …
Continue reading at www.sciencedirect.com (HTML) (other versions)

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/02—Topology update or discovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/48—Routing tree calculation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/04—Interdomain routing, e.g. hierarchical routing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G06F17/30961—Trees
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/12—Shortest path evaluation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/46—Cluster building
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H04L12/16—Arrangements for providing special services to substations contains provisionally no documents
    • H04L12/18—Arrangements for providing special services to substations contains provisionally no documents for broadcast or conference, e.g. multicast
    • H04L12/1886—Arrangements for providing special services to substations contains provisionally no documents for broadcast or conference, e.g. multicast with traffic restrictions for efficiency improvement, e.g. involving subnets or subdomains
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/74—Address processing for routing
    • H04L45/745—Address table lookup or address filtering
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F11/00—Error detection; Error correction; Monitoring
    • G06F11/07—Error detection; Error correction; Monitoring responding to the occurence of a fault, e.g. fault tolerance
    • G06F11/16—Error detection or correction of the data by redundancy in hardware
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/12—Arrangements for maintenance or administration or management of packet switching networks network topology discovery or management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/28—Route fault recovery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/16—Multipoint routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/22—Alternate routing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L45/00—Routing or path finding of packets in data switching networks
    • H04L45/54—Organization of routing tables
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L67/00—Network-specific arrangements or communication protocols supporting networked applications
    • H04L67/10—Network-specific arrangements or communication protocols supporting networked applications in which an application is distributed across nodes in the network

Similar Documents

Publication Publication Date Title
Xiang et al. Scalable maximum clique computation using mapreduce
Garcia-Luna-Aceves et al. Distributed, scalable routing based on vectors of link states
US7673069B2 (en) Strong routing consistency protocol in structured peer-to-peer overlays
Korman et al. Distributed verification of minimum spanning trees
US9338086B2 (en) Hierarchal label distribution and route installation in a loop-free routing topology using routing arcs at multiple hierarchal levels for ring topologies
Awerbuch et al. Compact distributed data structures for adaptive routing
Chen Pose determination from line-to-plane correspondences: existence condition and closed-form solutions
US9264243B2 (en) Flooding and multicasting in a loop-free routing topology using routing arcs
Korzun et al. Structured peer-to-peer systems: fundamentals of hierarchical organization, routing, scaling, and security
Hayes et al. The forgiving graph: a distributed data structure for low stretch under adversarial attack
Castañeda et al. Compact routing messages in self-healing trees
Liang et al. Service composition for advanced multimedia applications
Mokhtarian et al. Minimum-delay multicast algorithms for mesh overlays
Chlebus et al. Disconnected agreement in networks prone to link failures
JP5756049B2 (en) Multicast route calculation method and apparatus
CN111385200B (en) Control method and device for data block repair
Avresky Embedding and reconfiguration of spanning trees in faulty hypercubes
Reichert et al. A fast heuristic for genetic algorithms in link weight optimization
Castañeda et al. Fully compact routing in low memory self-healing trees
Dahan Distributed Spanning Tree algorithms for large scale traversals
Krioukov et al. Efficient navigation in scale-free networks embedded in hyperbolic metric spaces
Avin et al. Distributed computing on core-periphery networks: Axiom-based design
Gilbert et al. How fast can you update your MST?(Dynamic algorithms for cluster computing)
Imani et al. Properties of a hierarchical network based on the star graph
CN109818864B (en) Method and device for updating data flow path in software defined network