Nothing Special   »   [go: up one dir, main page]

Spira, 1977 - Google Patents

Communication complexity of distributed minimum spanning tree algorithms

Spira, 1977

View PDF
Document ID
670595167304015391
Author
Spira P
Publication year
Publication venue
Proceedings of the second Berkeley conference on distributed data management and computer networks

External Links

Snippet

In very large computer communication networks it is unacceptable to transmit a broadcast message by replicating a copy of the message for each destination. Rather, it is desirable to- have a spanning tree defined such that every node knows which of its arcs belong to the …
Continue reading at escholarship.org (PDF) (other versions)

Classifications

    • 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
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5619—Network Node Interface, e.g. tandem connections, transit switching
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/02—Details
    • H04L12/26—Monitoring arrangements; Testing arrangements
    • H04L12/2602—Monitoring arrangements
    • 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
    • H04Q—SELECTING
    • H04Q3/00—Selecting arrangements
    • H04Q3/64—Distributing or queueing
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. local area networks [LAN], wide area networks [WAN]
    • 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
    • H04Q—SELECTING
    • H04Q3/00—Selecting arrangements
    • H04Q3/0016—Arrangements providing connection between exchanges
    • 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
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L43/00—Arrangements for monitoring or testing packet switching networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L29/00—Arrangements, apparatus, circuits or systems, not covered by a single one of groups H04L1/00 - H04L27/00 contains provisionally no documents
    • H04L29/02—Communication control; Communication processing contains provisionally no documents
    • H04L29/06—Communication control; Communication processing contains provisionally no documents characterised by a protocol
    • 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

Similar Documents

Publication Publication Date Title
Humblet A distributed algorithm for minimum weight directed spanning trees
JP2505064B2 (en) Route selection method
Awerbuch et al. A new distributed algorithm to find breadth first search trees
Rouskas et al. Multicast routing with end-to-end delay and delay variation constraints
Doar et al. How bad is naive multicast routing?
Torrieri Algorithms for finding an optimal set of short disjoint paths in a communication network
Jenq Performance analysis of a packet switch based on single-buffered banyan network
Raghavan et al. A rearrangeable algorithm for the construction of delay-constrained dynamic multicast trees
JPH0241054A (en) Method of selecting route with minimum weight in communication network
Kompella et al. Two distributed algorithms for multicasting multimedia information
Mashreghi et al. Broadcast and minimum spanning tree with o (m) messages in the asynchronous CONGEST model
Spira Communication complexity of distributed minimum spanning tree algorithms
Cidon et al. New models and algorithms for future networks
US5125076A (en) System for routing messages in a vertex symmetric network by using addresses formed from permutations of the transmission line indicees
Townsend et al. Simulation of rare events in communications networks
Gerla Deterministic and adaptive routing policies in packet-switched computer networks
Shaikh et al. Localized multicast routing
Gafni et al. Election and traversal in unidirectional networks
Novak et al. Steiner tree based distributed multicast routing in networks
Yener et al. Combinatorial design of congestion-free networks
Rotem et al. Shout echo selection in distributed files
Tel Total algorithms
Ahuja et al. A distributed algorithm for minimum weight spanning trees based on echo algorithms
Lavault et al. A distributed approximation algorithm for the minimum degree minimum weight spanning trees
Lien A new node-join-tree distributed algorithm for minimum weight spanning trees