[go: up one dir, main page]

EP1127430A1 - Procedes et systemes permettant de determiner la topologie d'un reseau - Google Patents

Procedes et systemes permettant de determiner la topologie d'un reseau

Info

Publication number
EP1127430A1
EP1127430A1 EP99963744A EP99963744A EP1127430A1 EP 1127430 A1 EP1127430 A1 EP 1127430A1 EP 99963744 A EP99963744 A EP 99963744A EP 99963744 A EP99963744 A EP 99963744A EP 1127430 A1 EP1127430 A1 EP 1127430A1
Authority
EP
European Patent Office
Prior art keywords
message
node
link
topology
probe
Prior art date
Legal status (The legal status 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 status listed.)
Withdrawn
Application number
EP99963744A
Other languages
German (de)
English (en)
Inventor
Magnus Danielson
Mattias Holmlund
Stéphane TESSIER
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Net Insight AB
Original Assignee
Net Insight AB
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 Net Insight AB filed Critical Net Insight AB
Publication of EP1127430A1 publication Critical patent/EP1127430A1/fr
Withdrawn legal-status Critical Current

Links

Classifications

    • 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/42—Loop networks
    • H04L12/427—Loop networks with decentralised control
    • H04L12/43—Loop networks with decentralised control with synchronous transmission, e.g. time division multiplex [TDM], slotted rings
    • 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/4637—Interconnected ring systems
    • 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/42—Loop networks
    • H04L12/423—Loop networks with centralised control, e.g. polling
    • 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/26—Route discovery packet

Definitions

  • One way of providing each node with information on the network topology is to use a centralized scheme in which a central source will provide a map of the network to all other nodes of the network, for example as described in U.S. Pat. No. 5,654,958 (Natarajan) .
  • a disadvantage of this solution is that each change in the network topology has to be brought to the attention of the cent- ral source and has to be addressed by the central source if said change is to come to the other nodes attention, automatically adding signaling overhead between the central source and the network nodes. Also, if the central source is down, updating of network topology is tempora- rily rendered impossible.
  • a disadvantage with the above-mentioned prior art schemes is that they reliy on the limitation that nodes in each case are interconnected using a predifined type of links, for example requiering that the nodes of the netowrk are interconnected via bidirectional point-to- point connections only or requiering that the nodes of the network are connected via ring links only.
  • Such limitations has the advantage of simplifying the design of each scheme, but also has the negative effect of limiting the applicability of the schemes. In networks in which several different kinds of link types may exist, the task of automatically determining network topology becomes more difficult.
  • this will include distributing information as to which nodes, and which ports thereof, that form part of said network loop, wherein generation and distribution of such information is pre- ferrably performed using message forwarding. According to another embodiment, it will include informing a neighbor node on the existens of a valid connection thereto.
  • a node having two or more outgoing ports, and having not yet been able to determine which one of said output ports that is part of a specific network loop is arranged to transmit two or more respective messages from respective output ports, each message identifying the respective output port (sometimes referred to herein as "reply ports"), used for transmission thereof and thereby enabling subsequent determination of which one of said two or more output ports of said node that forms part of said network loop.
  • the sending of such two or more different messages may be initiated by the reception of a topology discovery message (probe message) or may be initiated by the sending node itself.
  • a specific example of this embodiment comprises the steps of: transmitting a message from an output port of a first node; receiving said message, as such or in a forwarded version, at an input port of a second node; transmitting two or more modified versions (forward version or reply version) of said message from respective two or more output ports of said second node, each modified version identifying the respective output port used for transmission thereof; receiving at least one of said modified versions of said message at said first node, thereby identifying which one of said two or more output ports that forms part of said network loop; and transmitting a message from said first node to said second node, said message identifying the output port of said second node that forms part of said network loop.
  • An advantage of the invention is thus that a first node may determine the existence of a valid connection to second node without knowing in advance what kind of link the connection forms part of. Similarly, the second node will gain information on the valid connection and is able to reply to the first node without knowing in advance how to reach the first node nor the exact type of the links concerned in the message exchange.
  • an interface is generally defined by an input port and an output port of a node.
  • a node When a node is connected to a multi-acces ring or bus link, it is connected to the link using the input port and the output port of the same interface.
  • two connections connected to the same interface is generally considered herein to form part of the same link, such as a bidirectional point-to-point link, a unidirectional bus link, or a unidirectional ring link.
  • a unidirectional single bus link may generally as such (i.e.
  • node 10 connection 101 from output port 11 of node 10 to input port 22 of node 20, node 20, and connection 104 from output port 23 of node 20 to input port 14 of node 10 together may be viewed as forming a network loop, as indicated by a semi-circular, dotted arrow.
  • node 20, connection 102 from node 20 to node 30, node 30, and connection 103 from node 30 to node 20 together may be viewed as forming another network loop 32.
  • the double bus link may thus be viewed as being built up by three consecutive network loops 31- 33.
  • said second double bus link may be said to be built up by two consecutive network loops 34 and 35.
  • the content of the received probe message is mapped into the transmitted message.
  • the content of the forwarded probe message will essentially be a copy of the content of the received probe message, thus identifying output port of the node that originated the probe message.
  • the distribution of probe messages is limited by a hop-count mechanism that limits the number of hops that a probe message is forwarded over. (For simplicity, in the illustrated example, it is assumed that the number of hops that a message is allowed to travel is set to four.)
  • a node When a node receives one of its own probe message from another node, it will determine that a loop exists, and it will know which one of its input ports and output ports that forms part of this new loop. The node then becomes a so-called build-up master for the new loop and continues to the master announce step for the new loop.
  • the master announce message is forwarded by the same rules as the probe messages and serves two purposes.
  • the first purpose is to inform other nodes about the existence of a new loop and to assign an identifier to the new loop, typically being the MAC address as mentioned above.
  • This loop identifier is contai- ned in all subsequent messages concerning the new loop and allows several loops to be discovered simultaneously without risking mix up of messages referring to different new loops.
  • the other nodes Upon receiving the master announce message, the other nodes become so called build-up slaves for the new loop and automatically know which of its input ports that are part of the loop.
  • the second purpose of the master announce message is that it provides a mechanism for build-up master arbitration. If two nodes simultaneously receive their own probe messages, they will both try to take on the role as build-up master.
  • the split-point reduction step is started by the build-up master, which will send out a so called split- point announce message on the output port where it previously sent out the probe and master announce messages.
  • the split-point announce message is provided with an identifier of the output port that it was sent on.
  • the master node 10 therefore informs the split-point node 40 about this by transmitting a split-point reduce message SPR(41) identifying the output port 41, said message being transmitted/ forwarded the same way as the previous messages.
  • node 40 receives the split-point reduce message SPR(41) identifying its output port 41, it knows that port 41 is part of the new loop.
  • Node 40 then sends out a release branch message RB on the remaining output port 43.
  • node 50 and 60 then receive the release branch message RB, they cease to be build-up slaves and may start searching for other loops.
  • the same message format is used to distribute the list as was used during the loop list build-up phase.
  • the build- up master transmits the list LD on the output port where the new loop has been established.
  • Each build-up slave node that receives a loop list under distribution must forward the list to the output port belonging to the same loop that the list arrived on.
  • the build-up master that has originated the loop list must make sure that the list comes back via the input port belonging to the same loop as the output port that the list was originated on. If the loop list does not arrive within a configured time interval, or if an error is detected by a node during the loop list distribution, the list is re-originated.
  • the topology discovery algorithm comprises a loop detection step S110, a link announce step S120, a link list distribution step S130, and a route table computation step S140.
  • the process will now be described in detali with reference to an exemplifying network illustrated in Figs, la-lc , said network comprising three nodes 10, 20, and 30, interconnected to form a dual bus link, i.e. in similar to the network described above with reference to Fig. la.
  • the description will in this case exemplify topology determining actions taken by the nodes in the network, each action being discribed in relation to the event that causes the action.
  • the actions described below will be decided upon by one or more control functions in each node .
  • a node When a node receives a probe reply, it will first of all determine, using the Link Identifier included in the probe reply message, whether or not the probe reply is a reply to a probe message that the node itself has was the sender of, i.e. if the Link Idenifier included in the probe reply message identifies an output port of the node. If the answere is no, the node will forward the probe reply on the output port of the same interface as it was received on. The reason for not forwarding the probe reply on all output ports in this embodiment, is that if the node itself wasn't the intended recipient, the path back to the intended recipient, given the allowed topologies, should be along the same unidirectional link that the message was received on. However, an embodiment wherein the probe reply is forwarded on all output ports could also be used, but then some kind of mechanism would preferably be addedd to avoid messages from being forwarded forever within the network. If however the node determines, using the Link Identifier included in the probe reply message, whether or not the
  • the node will include, in the link detected message, a flag identifying that the receiver shall not originate a link toplogy message, the reason for which being described below.
  • a node When a node receives a link detected message it will: a) conclude that a valid connection/link exists from an upstream node to the input port at which the link detected message is received; b) conclude that the up- stream neighbor node identifies its ouput port for this link using the Link Identifier included in the link detected message; c) determine, using the Reply Port Identifier included in the link detected message, which output port, referred to below as reply port, that shall be used when sending control messages to the upstream neighbor node regarding the the connection/ link; e) transmit a link detected acknowledgement message from the reply port to reach the upstream neighbor node, said link detected acknowledgement message including the Link Identifier, as illustrated by the message ACK(ll) in Fig. 7b.
  • node 20 when node 20 receives the downstream topology message from node 10 identifying the topology (10) known to node 10, node C will be updated on that the entire known link now comprises nodes 10, 20 and 30 (the existence of node 30 was assumed already known to node 20), and will transmit a link topology message with this topology information (10-20-30) to its downstream neighbor node 30, as is illustrated by the messag LT (21:10,20,30) .
  • each intefaces as such will typically also be provided with means for bypassing/- switching data from its own input port to its own output port.
  • the control processor typically provides the above mentioned control function that handles tranmitted and received messages of the kind described above, and uses information in the message to update a memory 117 that stores topology information. Note, however, that such a control function and memory need not be centralized within the node, handling topology discovery operation with respect to all interfaces of the node.
  • the control fucntion and/or memory storage could just as be implemen- ted a several parallel control functions, each for example operating in relateion to a respective interface of the node.

Landscapes

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

Abstract

L'invention concerne un procédé et un système qui permettent de déterminer la topologie d'un réseau de noeuds interconnectés via des connexions unidirectionnelles. Selon l'invention, pour déterminer l'existence d'une boucle dans un réseau, on transmet un message de façon à le faire passer d'un noeud à l'autre, ce qui permet de transmettre à tous les noeuds contenus dans ledit réseau les informations concernant l'existence de ladite boucle.
EP99963744A 1998-11-24 1999-11-23 Procedes et systemes permettant de determiner la topologie d'un reseau Withdrawn EP1127430A1 (fr)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
SE9804023A SE514430C2 (sv) 1998-11-24 1998-11-24 Förfarande och system för bestämning av nättopologi
SE9804023 1998-11-24
PCT/SE1999/002169 WO2000031925A1 (fr) 1998-11-24 1999-11-23 Procedes et systemes permettant de determiner la topologie d'un reseau

Publications (1)

Publication Number Publication Date
EP1127430A1 true EP1127430A1 (fr) 2001-08-29

Family

ID=20413394

Family Applications (1)

Application Number Title Priority Date Filing Date
EP99963744A Withdrawn EP1127430A1 (fr) 1998-11-24 1999-11-23 Procedes et systemes permettant de determiner la topologie d'un reseau

Country Status (6)

Country Link
EP (1) EP1127430A1 (fr)
JP (1) JP2002531003A (fr)
KR (1) KR20010082312A (fr)
AU (1) AU2011700A (fr)
SE (1) SE514430C2 (fr)
WO (1) WO2000031925A1 (fr)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114221859A (zh) * 2022-01-06 2022-03-22 烽火通信科技股份有限公司 一种租户网络物理链路连通性拓扑生成方法及系统

Families Citing this family (20)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7599360B2 (en) 2001-12-26 2009-10-06 Cisco Technology, Inc. Methods and apparatus for encapsulating a frame for transmission in a storage area network
US7499410B2 (en) 2001-12-26 2009-03-03 Cisco Technology, Inc. Fibre channel switch that enables end devices in different fabrics to communicate with one another while retaining their unique fibre channel domain—IDs
US7616637B1 (en) 2002-04-01 2009-11-10 Cisco Technology, Inc. Label switching in fibre channel networks
US7406034B1 (en) 2002-04-01 2008-07-29 Cisco Technology, Inc. Methods and apparatus for fibre channel frame delivery
AU2003223508A1 (en) * 2002-04-08 2003-10-27 Airmagnet, Inc. Monitoring a local area network
US8605623B2 (en) * 2002-05-31 2013-12-10 Koninklijke Philips N.V. Determining and configuring a communication path in a network
US7206288B2 (en) * 2002-06-12 2007-04-17 Cisco Technology, Inc. Methods and apparatus for characterizing a route in fibre channel fabric
US7433326B2 (en) 2002-11-27 2008-10-07 Cisco Technology, Inc. Methods and devices for exchanging peer parameters between network devices
US7593324B2 (en) 2004-10-25 2009-09-22 Cisco Technology, Inc. Graceful port shutdown protocol for fibre channel interfaces
CN1321530C (zh) * 2005-04-12 2007-06-13 四川汇源科技发展股份有限公司 用于确定有线电视hfc网络拓扑结构的方法
WO2007073627A1 (fr) * 2005-12-29 2007-07-05 Zte Corporation Procede permettant de retransmettre rapidement un message et systeme correspondant
CN101064631A (zh) * 2006-04-25 2007-10-31 华为技术有限公司 拓扑结构扫描方法和扫描系统
CN101399757B (zh) * 2007-09-25 2011-02-02 华为技术有限公司 跟踪时钟源的方法和装置
US7940029B2 (en) 2008-07-02 2011-05-10 American Superconductor Corporation Static VAR corrector
US10861504B2 (en) 2017-10-05 2020-12-08 Advanced Micro Devices, Inc. Dynamic control of multi-region fabric
US10558591B2 (en) 2017-10-09 2020-02-11 Advanced Micro Devices, Inc. Method and apparatus for in-band priority adjustment forwarding in a communication fabric
US11196657B2 (en) * 2017-12-21 2021-12-07 Advanced Micro Devices, Inc. Self identifying interconnect topology
US11507522B2 (en) 2019-12-06 2022-11-22 Advanced Micro Devices, Inc. Memory request priority assignment techniques for parallel processors
US11223575B2 (en) 2019-12-23 2022-01-11 Advanced Micro Devices, Inc. Re-purposing byte enables as clock enables for power savings
CN112671890B (zh) * 2020-12-21 2023-04-07 深圳云天励飞技术股份有限公司 一种网络连接装置和网络系统

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4287592A (en) * 1979-05-23 1981-09-01 Burroughs Corporation Method and apparatus for interfacing stations in a multiloop communications system
BE895438A (nl) * 1982-12-22 1983-06-22 Bell Telephone Mfg Communicatiestelsel met meerdere ringen
JPH0767112B2 (ja) * 1983-12-23 1995-07-19 株式会社日立製作所 通信ネツトワ−クシステム
US5440540A (en) * 1992-03-26 1995-08-08 Kremer; Wilhelm Ring interworking between a bidirectional line-switched ring transmission system and another ring transmission system
US5732086A (en) * 1995-09-21 1998-03-24 International Business Machines Corporation System and method for determining the topology of a reconfigurable multi-nodal network
AUPN573795A0 (en) * 1995-10-02 1995-10-26 Telefonaktiebolaget Lm Ericsson (Publ) Transmitting data between multiple computer processors
GB9601692D0 (en) * 1996-01-27 1996-03-27 Newbridge Networks Corp Network with ring architecture

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See references of WO0031925A1 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114221859A (zh) * 2022-01-06 2022-03-22 烽火通信科技股份有限公司 一种租户网络物理链路连通性拓扑生成方法及系统
CN114221859B (zh) * 2022-01-06 2023-12-01 烽火通信科技股份有限公司 一种租户网络物理链路连通性拓扑生成方法及系统

Also Published As

Publication number Publication date
KR20010082312A (ko) 2001-08-29
JP2002531003A (ja) 2002-09-17
SE9804023D0 (sv) 1998-11-24
AU2011700A (en) 2000-06-13
WO2000031925A1 (fr) 2000-06-02
SE514430C2 (sv) 2001-02-26
SE9804023L (sv) 2000-06-06

Similar Documents

Publication Publication Date Title
WO2000031925A1 (fr) Procedes et systemes permettant de determiner la topologie d'un reseau
US5732086A (en) System and method for determining the topology of a reconfigurable multi-nodal network
EP0752795B1 (fr) Réservation de liaison dans des réseaux de communications
EP1942604B1 (fr) Procédé de commutation de service et noeud de réseau associé
US6529301B1 (en) Optical switch and protocols for use therewith
EP0566610B1 (fr) Procede et appareil permettant d'etablir un pont transparent de trafic par-dessus des reseaux longue portee
EP1263173B1 (fr) Un procédé adaptative de recherche de chemin pour le routage de paquets de données dans un réseau multinodal
US6961319B2 (en) Methods and arrangements for distribution tree development
EP0843942B1 (fr) Reperage de voie dans des reseaux de telecommunications
US8315188B2 (en) Topology database synchronization
EP1035685A2 (fr) Système de communication de données avec multi-diffusion distribuée
US20030142680A1 (en) Device, network, and system for forwarding frames between geographically dispersed user networks
JPH02149039A (ja) マルチキャスト・メッセージ分配方式
US7366112B2 (en) Communication network control system, control method, node and program
JP2002057697A (ja) パケット転送経路制御装置及びそれに用いるパケット転送経路制御方法
CN101997735A (zh) 单环网络拓扑重建方法及系统
EP0843941B1 (fr) Routage dans les réseaux de télécommunications
WO1997050215A1 (fr) Systeme et procede de transfert de paquets dans un reseau 'sans connexion'
US6122282A (en) Route finding in communication networks
JP3395703B2 (ja) ポイントツウポイント通信ネットワークシステム及びその通信制御方法
AU695859C (en) Route finding in communications networks

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE CH CY DE DK ES FI FR GB GR IE IT LI LU MC NL PT SE

AX Request for extension of the european patent

Free format text: AL;LT;LV;MK;RO;SI

17P Request for examination filed

Effective date: 20010817

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 20040602