[go: up one dir, main page]

Kim et al., 2004 - Google Patents

Robustness in large-scale random networks

Kim et al., 2004

View PDF
Document ID
14730987250357881953
Author
Kim M
Médard M
Publication year
Publication venue
IEEE INFOCOM 2004

External Links

Snippet

We consider the issue of protection in very large networks displaying randomness in topology. We employ random graph models to describe such networks, and obtain probabilistic bounds on several parameters related to reliability. In particular, we take the …
Continue reading at dspace.mit.edu (PDF) (other versions)

Classifications

    • 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/30958—Graphs; Linked lists
    • 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/02—Topology update or discovery
    • 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
    • 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
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F15/00—Digital computers in general; Data processing equipment in general
    • G06F15/16—Combinations of two or more digital computers each having at least an arithmetic unit, a programme unit and a register, e.g. for a simultaneous processing of several programmes
    • G06F15/163—Interprocessor communication
    • G06F15/173—Interprocessor communication using an interconnection network, e.g. matrix, shuffle, pyramid, star, snowflake
    • 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/50—Computer-aided design
    • 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
    • H04L41/00—Arrangements for maintenance or administration or management of packet switching networks
    • H04L41/06—Arrangements for maintenance or administration or management of packet switching networks involving management of faults or events or alarms
    • 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
    • H04Q—SELECTING
    • H04Q3/00—Selecting arrangements
    • H04Q3/0016—Arrangements providing connection between exchanges
    • H04Q3/0062—Provisions for network management
    • H04Q3/0075—Fault management techniques
    • 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
    • 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/22—Arrangements for maintenance or administration or management of packet switching networks using GUI [Graphical User Interface]

Similar Documents

Publication Publication Date Title
Hsieh et al. Hamiltonian‐laceability of star graphs
Tseng et al. Fault-tolerant ring embedding in a star graph with both link and node failures
US7631222B2 (en) Method and apparatus for correlating events in a network
Barrett et al. Gardens of Eden and fixed points in sequential dynamical systems
Chen et al. Nearly optimal one-to-many parallel routing in star networks
Hsieh et al. Longest fault-free paths in star graphs with vertex faults
Kim et al. Robustness in large-scale random networks
Hsieh Embedding longest fault-free paths onto star graphs with more vertex faults
Imai et al. Computational investigations of all-terminal network reliability via BDDs
Cheng et al. Increasing the connectivity of the star graphs
Cidon et al. New models and algorithms for future networks
Latifi et al. Incomplete star: an incrementally scalable network based on the star graph
Fu Fault-free Hamiltonian cycles in twisted cubes with conditional link faults
Lai Optimal construction of all shortest node-disjoint paths in hypercubes with applications
Fu Hamiltonicity of the WK-recursive network with and without faulty nodes
Sung et al. Fault tolerant token ring embedding in double loop networks
CN118200228A (en) An adaptive fault-tolerant routing method for data center networks based on a two-layer security model
Lai Two conditions for reducing the maximal length of node-disjoint paths in hypercubes
Wu et al. A limited-global-information-based multicasting scheme for faulty hypercubes
Qiu An efficient disjoint shortest paths routing algorithm for the hypercube
Chang et al. Ring embedding in faulty (n, k)-star graphs
Goldberg et al. A parallel algorithm for reconfiguring a multibutterfly network with faulty switches
Karaata A stabilizing algorithm for finding biconnected components
Kim et al. A self-stabilizing algorithm for constructing a maximal (1, 1)-directed acyclic mixed graph
CN119544584B (en) A protection routing method based on dual completely independent spanning trees