[go: up one dir, main page]

WO2008016861A3 - Link inference in large networks based on incomplete data - Google Patents

Link inference in large networks based on incomplete data Download PDF

Info

Publication number
WO2008016861A3
WO2008016861A3 PCT/US2007/074679 US2007074679W WO2008016861A3 WO 2008016861 A3 WO2008016861 A3 WO 2008016861A3 US 2007074679 W US2007074679 W US 2007074679W WO 2008016861 A3 WO2008016861 A3 WO 2008016861A3
Authority
WO
WIPO (PCT)
Prior art keywords
networks based
incomplete data
large networks
lowenkamp
partitions
Prior art date
Application number
PCT/US2007/074679
Other languages
French (fr)
Other versions
WO2008016861A2 (en
Inventor
Rajesh Balasubramaniam
James Mark Shaw
Original Assignee
Rajesh Balasubramaniam
James Mark Shaw
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Rajesh Balasubramaniam, James Mark Shaw filed Critical Rajesh Balasubramaniam
Publication of WO2008016861A2 publication Critical patent/WO2008016861A2/en
Publication of WO2008016861A3 publication Critical patent/WO2008016861A3/en

Links

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/14—Routing performance; Theoretical aspects
    • 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. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H04L12/46—Interconnection of networks
    • H04L12/4641—Virtual LANs, VLANs, e.g. virtual private networks [VPN]
    • 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/48—Routing tree calculation
    • H04L45/488—Routing tree calculation using root node determination

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Small-Scale Networks (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

discovery of network topology based on incomplete switch forwarding tables AFT, layer 2 information. To reduce complexity of topology computation according to the known Lowenkamp algorithm, the set of nodes is first divided into partitions, according to the known simply connected nodes algoritm, the partitions are discovered according to the Lowenkamp, and after the partial partition discovery is done, the discovered network topologies are merged.
PCT/US2007/074679 2006-08-01 2007-07-29 Link inference in large networks based on incomplete data WO2008016861A2 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US82102206P 2006-08-01 2006-08-01
US60/821,022 2006-08-01

Publications (2)

Publication Number Publication Date
WO2008016861A2 WO2008016861A2 (en) 2008-02-07
WO2008016861A3 true WO2008016861A3 (en) 2008-07-10

Family

ID=38997783

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US2007/074679 WO2008016861A2 (en) 2006-08-01 2007-07-29 Link inference in large networks based on incomplete data

Country Status (1)

Country Link
WO (1) WO2008016861A2 (en)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7430592B2 (en) 2004-04-21 2008-09-30 Dell Products L.P. Method for heterogeneous system configuration
US8625457B2 (en) 2007-12-03 2014-01-07 International Business Machines Corporation Method and apparatus for concurrent topology discovery
GB2464125A (en) * 2008-10-04 2010-04-07 Ibm Topology discovery comprising partitioning network nodes into groups and using multiple discovery agents operating concurrently in each group.

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5706440A (en) * 1995-08-23 1998-01-06 International Business Machines Corporation Method and system for determining hub topology of an ethernet LAN segment
WO1998018306A2 (en) * 1996-10-28 1998-05-07 Switchsoft Systems, Inc. Method and apparatus for generating a network topology
US6628623B1 (en) * 1999-05-24 2003-09-30 3Com Corporation Methods and systems for determining switch connection topology on ethernet LANs
US20040255184A1 (en) * 2003-05-27 2004-12-16 Lucent Technologies Inc. System and method for determining the physical topology of a network having multiple subnets
US20060133297A1 (en) * 2004-12-17 2006-06-22 Quist Daniel A Network topology mapper

Patent Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5706440A (en) * 1995-08-23 1998-01-06 International Business Machines Corporation Method and system for determining hub topology of an ethernet LAN segment
WO1998018306A2 (en) * 1996-10-28 1998-05-07 Switchsoft Systems, Inc. Method and apparatus for generating a network topology
US6628623B1 (en) * 1999-05-24 2003-09-30 3Com Corporation Methods and systems for determining switch connection topology on ethernet LANs
US20040255184A1 (en) * 2003-05-27 2004-12-16 Lucent Technologies Inc. System and method for determining the physical topology of a network having multiple subnets
US20060133297A1 (en) * 2004-12-17 2006-06-22 Quist Daniel A Network topology mapper

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
BREITBART Y ET AL: "TOPOLOGY DISCOVERY IN HETEROGENEOUS IP NETWORKS: THE NETINVENTORY SYSTEM", IEEE / ACM TRANSACTIONS ON NETWORKING, IEEE / ACM, NEW YORK, NY, US, vol. 12, no. 3, 1 June 2004 (2004-06-01), pages 401 - 414, XP001198226, ISSN: 1063-6692 *
LOWEKAMP B ET AL: "TOPOLOGY DISCOVERY FOR LARGE ETHERNET NETWORKS", COMPUTER COMMUNICATION REVIEW, ACM, NEW YORK, NY, US, vol. 31, no. 4, 1 October 2001 (2001-10-01), pages 237 - 248, XP001115760, ISSN: 0146-4833 *
YANTAO SUN ET AL: "The physical topology discovery for switched ethernet based on connections reasoning technique", COMMUNICATIONS AND INFORMATION TECHNOLOGY, 2005. ISCIT 2005. IEEE INTE RNATIONAL SYMPOSIUM ON BEIJING, CHINA OCT. 12-14, 2005, PISCATAWAY, NJ, USA,IEEE, vol. 1, 12 October 2005 (2005-10-12), pages 42 - 45, XP010875543, ISBN: 978-0-7803-9538-1 *

Also Published As

Publication number Publication date
WO2008016861A2 (en) 2008-02-07

Similar Documents

Publication Publication Date Title
US8559341B2 (en) System and method for providing a loop free topology in a network environment
CN101268658B (en) System and method for generating symmetrical spanning trees
CN104579728B (en) Network element equipment configuration and management method, device and network element equipment
US8982733B2 (en) System and method for managing topology changes in a network environment
Allan et al. Shortest path bridging: Efficient control of larger ethernet networks
CN100586079C (en) A Data Link Layer Oriented Network Topology Discovery Method
CN105393511B (en) A switch mode switching method, device and system
WO2006110370A3 (en) Arrangement for providing optimized connections between peer routers in a tree-based ad hoc mobile network
WO2004102983A3 (en) Network topology and packet routing method using low voltage power wiring
WO2014008826A1 (en) Method, device, and system for establishing bi-directional multicast distribution tree based on interior gateway protocol
ATE535871T1 (en) NETWORK TOPOLOGIES RECOVERY MECHANISM
CN102546391B (en) energy efficient networking
CN107370536A (en) Satellite network multi-broadcast routing method and system based on minimum connected dominating set
CN105072040B (en) Efficient satellite SpaceWire plug and play network topological construction methods
WO2005057863A1 (en) Data transmission apparatus
CN105357132B (en) A kind of multiple domain ASON damages based on hypergraph model perceive multicast route method
CN103200089B (en) Message forwarding method and device in virtual private local area network service network
WO2008016861A3 (en) Link inference in large networks based on incomplete data
CN103905221A (en) General topological link accurate discovery method
CN106533777B (en) Method and system are determined based on the intelligent transformer substation information flow path of matrix ranks
CN105207995B (en) A kind of VLAN dynamic registration method based on SDN
US8824338B2 (en) Distributed spanning tree protocol
CN202679422U (en) Cloud computing network architecture
US8830875B1 (en) System and method for providing a loop free topology in a network environment
CN104796345B (en) The sending control method and equipment of a kind of message

Legal Events

Date Code Title Description
NENP Non-entry into the national phase

Ref country code: DE

NENP Non-entry into the national phase

Ref country code: RU

122 Ep: pct application non-entry in european phase

Ref document number: 07813511

Country of ref document: EP

Kind code of ref document: A2