[go: up one dir, main page]

EP0631413A2 - Méthode de routage à traject minimal - Google Patents

Méthode de routage à traject minimal Download PDF

Info

Publication number
EP0631413A2
EP0631413A2 EP94304323A EP94304323A EP0631413A2 EP 0631413 A2 EP0631413 A2 EP 0631413A2 EP 94304323 A EP94304323 A EP 94304323A EP 94304323 A EP94304323 A EP 94304323A EP 0631413 A2 EP0631413 A2 EP 0631413A2
Authority
EP
European Patent Office
Prior art keywords
link
network
initial
routing
shortest paths
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.)
Granted
Application number
EP94304323A
Other languages
German (de)
English (en)
Other versions
EP0631413A3 (fr
EP0631413B1 (fr
Inventor
Kajamalai Gopalaswamy Ramakrishnan
Manoel Alberto Rodrigues
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.)
AT&T Corp
Original Assignee
AT&T Corp
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 AT&T Corp filed Critical AT&T Corp
Publication of EP0631413A2 publication Critical patent/EP0631413A2/fr
Publication of EP0631413A3 publication Critical patent/EP0631413A3/fr
Application granted granted Critical
Publication of EP0631413B1 publication Critical patent/EP0631413B1/fr
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Images

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/12—Shortest path evaluation
    • H04L45/123—Evaluation of link metrics
    • 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

Definitions

  • the invention relates to a method and apparatus for improved routing in data networks.
  • the invention discloses a method and apparatus for routing in shortest path networks that utilize a centralized assignment of link metrics.
  • FIG. 1 illustrates the structure of a typical computer network.
  • the first part of the network typically comprises a collection of Machines 102, called hosts, intended for running application programs.
  • the network also includes Communication Subnet 104 linking the hosts.
  • the subnet's job is to carry messages from host to host.
  • the subnet typically comprises two basic components: Routers (also called Switching Elements, Nodes or Interface Message Processors) 106 and Links (also called Transmission Lines) 108.
  • Routers also called Switching Elements, Nodes or Interface Message Processors
  • Links also called Transmission Lines
  • routing The role of routing is to set up paths between nodes of the network for the efficient utilization of network services and for the efficient transfer of data.
  • a datagram network is made of a set of hosts and a set of store-and-forward routers interconnected by a set of links.
  • the main characteristics of a datagram network is that the functions that require knowledge about a "session" (e.g., session duration) or service requirements (e.g., reliable delivery of packets) are relegated to an end-to-end transport protocol, established between the communicating hosts.
  • a "session” e.g., session duration
  • service requirements e.g., reliable delivery of packets
  • each router is a function (routing table) that associates an incoming packet with an outgoing port, and a routing algorithm that fills in the routing table entries such that the ensemble of routers operates in a coordinated way.
  • a function routing table
  • the routing table is a deterministic mapping between the incoming packet destination address and the outgoing port number.
  • the routing table can be changed as a function of time, its entries have a long lifetime.
  • the deterministic mapping translates into single-path routing. Consequently, flow from an origin-destination pair cannot be randomized among several paths, which constitutes single-path routing. Second, only the destination address is used for determining routing. Consequently, once two flows merge towards a common destination, they cannot be subsequently separated. This is called destination-based routing. Thus, datagram routing corresponds to the general routing problem with the additional constraints of single-path routing and destination-based routing.
  • shortest-path routing as a distributed routing algorithm is one of the outcomes of the ARPANET project. Shortest-path routing is just like datagram routing but with the additional constraint that all routes (i.e., routing table entries) are calculated based on a "distance" metric. In static or quasi-static shortest-path networks (dynamic routing schemes are not considered), a "distance" or link metric is assigned to each link in the network by the network manager. These link metrics are assigned so as to yield good overall network performance as determined by a performance measure. In some instances, this metric assignment is distributed, i.e. each node assigns a metric to its outgoing link.
  • the "distance” metrics are then disseminated among all routers in the network and each router calculates the shortest paths to every other router in the network.
  • the resulting shortest paths determine the routing table entries.
  • the shortest-path constraint is more subtle than the others and it has the effect of "coupling" entries in the routing table.
  • link state protocols the routers exchange among themselves information about the topology of the network, including information about which links are currently up or down and the "distance" metric associated to each link. See , John Moy, "The OSPF Specification, Version 2," IETF Draft, January 1991; and ISO 10589 for detailed information on distributed link-state protocols.
  • each router After receiving complete information on network topology and on link "distance" metrics, each router then calculates the shortest paths to every other router in the network.
  • the routing tables of all routers in the network have entries that are consistent and they all synthesize the shortest path routes.
  • the routers exchange with their neighbors information about the distance to every other node in the network.
  • the routing in all routers in the network eventually converges to the shortest path routing. That is accomplished by each router applying the triangle inequality between its distances to each destination and its distance to each neighbor plus each neighbor's distance to each destination, and always selecting the shortest path.
  • shortest-path routing with respect to datagram routing is easier to manage and more effective upon failures. It is easier to manage since the network manager only has to manage L (i.e., the number of links in the network) values as opposed to N ( N -1) values (i.e., the number of routers times the number of entries on each router). It is more robust to configuration errors since if the network manager makes a mistake while assigning a "distance" metric, routing in the network may not be as optimal as it could be; on the other hand, if the network manager makes a mistake while assigning routing table entries, it could have very disruptive effects in the network operation (e.g., looping).
  • the existing methods for assigning link metrics have two main features. First, the assignment is distributed, i.e. each node in the network assigns the link metric to its outgoing link or data path. Second, each node looks at the current load in the line to assign a link metric. See J. M. McQuillan, G. Falk and I. Richer, "A Review of the Development and Performance of the ARPANET Routing Algorithm" IEEE Trans. Comm. , pp. 1802-1811, Dec. 1978; J. M. McQuillan, I. Rider, and E. C. Rosen, "The New Routing Algorithm for the ARPANET," IEEE Trans. Comm. , Vol. COM-28, No. 5, 711-719, May 1980; A.
  • the present invention in typical embodiment relates to a method and apparatus for assigning "distance" or link metrics in a shortest-path routing network that avoid many of the disadvantages of prior methods.
  • the method and apparatus advantageously assign link metrics in a centralized way.
  • the method and apparatus assign the metrics so as to improve network performance, e.g. reduce the average network delay.
  • FIG. 2 presents an illustrative embodiment of the invention in which Network Manager Processor 210 advantageously assigns distance or link metrics to the links in a shortest path routing data network.
  • the data network comprising Machines 202, a Communications Subnet 204, Routers 206 and Links 208, is similar to that shown in FIG. 1.
  • Network Manager Processor 210 employs a quasi-static link metric assignment strategy in which Network Manager Processor 210 centrally determines the link metric assignments and sends signals to Routers 206 containing information about the assignments.
  • Network Manager Processor 210 queries from Routers 206 information about origin-destination traffic (i.e. traffic between pairs of nodes in the network).
  • Network Manager Processor 210 then redetermines the link metrics for the network based on the information and sends signals comprising information about the redetermined link metrics to Routers 206.
  • Section II presents an overview of the general routing problem which forms a basis for characterizing and measuring the performance of a shortest path routing method.
  • Section III presents a detailed description of the proposed method and apparatus for link metric assignment.
  • Section IV illustrates the use of the method in an example.
  • the general routing problem can be described in terms of a non-linear multicommodity flow problem.
  • a link will be interchangeably referred to by its link number l or by the ordered node pair (or origin-destination pair) it connects ( n 1, n2 ).
  • C l denote the capacity of link l ⁇ L .
  • a characteristic of typical graphs in data networks is that a given directed link between nodes n i 1 and n i 2 , there also exists a directed link in the opposite direction (i.e., between nodes n i 2 and n i 1 ).
  • K ⁇ k 1, k 2, . . . ,k K ⁇ denote the set of commodities to be carried by this network, which usually is equal to all origin-destination pairs N ( N - 1).
  • a pair of nodes is designated as the origin-destination (OD) pair with the required flow ⁇ k of that commodity.
  • OD origin-destination
  • P k is the set of all simple paths connecting OD pair.
  • MFP Multicommodity Flow Problem
  • Z is a non-linear objective function of flow vectors for commodities k ⁇ K
  • H ( i ) ⁇ n ⁇ N ( n,i ) ⁇ L ⁇ (set of nodes in which node i is a neighbor)
  • J ( i ) ⁇ n ⁇ N ( i , n ) ⁇ L ⁇ (set of nodes that are neighbor of node i )and is the routing variable at node i determining the fraction of the flow from commodity k that is routed to neighbor j .
  • Network performance may be measured in a variety of ways.
  • a typical performance measure may be based on objective functions whose values depend on the flows only through the total flow at each link f l .
  • the objective function or performance measure is a convex function of the flows f l , such as average network delay, where Note that if we sum both sides of (2) with respect to j ⁇ J ( i ) and substitute constraint (3) in the equation, we would get the usual flow conservation equations.
  • H. Soroush and P.B. Mirchandani "The Stochastic Multicommodity Flow Problem," Networks , Vol. 20, No. 2, pp. 121-155, March 1990.
  • constraint (3) For a given node i ⁇ N and commodity k ⁇ K , the difference between supply and demand should be zero unless node i is either an origin (+ ⁇ k ) or destination ( - ⁇ k ) of commodity k .
  • the role of constraint (3) is to specify precisely how flows should be divided among the neighbors of node i. Although this extra constraint has no effect on the solution of the MFP, it is an important constraint when considering the problem with additional constraints (e.g., of single path routing and destination based routing). Furthermore, solving for for all i , j ⁇ N determines the flows f k for all k ⁇ K and vice versa.
  • each commodity corresponds to the flow towards destination node k .
  • This new constraint can be described as follows: when two or more flows from any origin node that are destined towards a common destination node k merge at an intermediate node i , these flows cannot be given differential treatment.
  • N-Commodity Multicommodity Flow Problem MFP
  • N-Commodity a non-linear function of the flows f l
  • H ( i ) ⁇ n ⁇ N ( n , i ) ⁇ L ⁇
  • J ( i ) ⁇ n ⁇ N ( i , n ) ⁇ L ⁇ .
  • Equation (8) is the usual flow conservation constraint at a given node i ⁇ N for commodity k .
  • the sum of all flows in a given link l has to be smaller than capacity C l .
  • the problem formulated as above is a linearly constrained convex programming problem. Since the objective function is convex and the feasible solution space is compact, there exists a unique global minimum of problem (7)-(10).
  • the shortest path (SP) routing problem has destination based routing. However, unlike the N-Commodity general routing problem, randomizing the routing is not permitted. All data from a source to a destination should follow the same path. In addition, the path should be the shortest path between the origin and destination nodes as measured by the link metrics.
  • a necessary condition for a solution to conform with the shortest-path constraint is that, if two nodes (i.e., n1 and n 2) belong to two (or more) different paths (i.e., path a ⁇ i,...,n 1, . . . , n2, . . . , j and path b ⁇ k,..., n1, . . . ,n2 , . . . , m ) then the two paths (i.e., a and b ) have to be identical between those two nodes.
  • the shortest path routing problem can be stated as follows: define the link metrics for all links l ⁇ L with respect to a given set of demands such that the resulting set of shortest paths achieves the best overall network performance.
  • the crucial element of the problem is the assignment of link metrics.
  • the effect of the shortest-path routing constraint is that of introducing coupling between paths.
  • This coupling manifests itself is as follows: if two paths intersect at two points, they must be identical between those two points.
  • the above characteristic can be viewed as a necessary condition for a set of routes to be realized through shortest path algorithms (i.e., longest path algorithms also have this characteristic).
  • FIG. 3 illustrates the steps in the method for assigning link metrics.
  • Network Manager Processor 110 in FIG. 2 may advantageously use this method to send signals comprising link metric assignment information to Routers 206.
  • the basic idea of the proposed method is to perform a local search in a well defined neighborhood. The neighborhood considered here is that of a minimal route change.
  • the objective function or performance measure is that of equation (6).
  • a point P 0 which denotes a set of shortest paths obtained from a given initial distance link metric vector D 0 ⁇ R L .
  • distance link metric values that are the inverse of the link capacity may be selected.
  • V ( P 0) ⁇ P ⁇
  • ⁇ P ⁇ is a set of points, where each point is a set of shortest paths, such that only a minimum number of paths are changed with respect to P 0 as a consequence of an increase in a single component of D 0.
  • p l denote the set of origin-destination (OD) pairs that have paths through l .
  • a suitable increase in the distance of link l is sought such that only the minimum number of paths are diverted from link l . This is achieved by first diverting all paths that go through that link (setting its distance to infinity). Then sort the OD pairs in increasing order with respect to the difference between their path distances after and before all paths were diverted from link l .
  • the paths that suffered the least increase in distance correspond to the ones to divert and the suitable increase, ⁇ l , in the distance of link l is any value larger than the least increase and the next-to-least increase in distance experienced by those paths. In the method, the midpoint between those two values may typically be selected.
  • the method converges in bounded time. Since there is a bounded number of points P , the number of spanning trees in the network can be shown to be an upper bound to the cardinality of the set of possible P .
  • the method never visits a point P twice since the search is strictly descending in Z ( f ). Therefore, the method cannot possibly have more iterations than the size of the state space, and thus the method converges in bounded time.
  • the complexity of a step is O (
  • Table 1 depicts all OD pairs, their shortest path costs and their shortest path cost when each one of the links is removed.
  • Table 2 depicts all links, the OD pair the and the Thus, there are four neighbors of P 0 each resulting from perturbations of D 0, namely (1.5+ ⁇ C 1,1.3,2.4,1.0,1.0), where 0.6 ⁇ C 1 ⁇ 1.2, (1.5,1.3+ ⁇ C 2,2.4,1.0,1.0), where 0.6 ⁇ C 2 ⁇ 3.6, (1.5,1.3,2.4+ ⁇ C 3,1.0,1.0), where 1.4 ⁇ C 3 ⁇ 2.8, (1.5,1.3,2.4,1.0+ ⁇ C 4,1.0), where 1.2 ⁇ C 4 ⁇ 4.2.
  • link cost is a continuous variable
  • all the link cost vectors that map into the same set of shortest paths correspond to the same discrete point in the neighborhood V. Note that there is no neighbor resulting from an increase of l 5 cost since no path can be diverted from there (i.e., leading to a reduction in state space).
  • This disclosure deals with a method and apparatus for link metric assignment in shortest path networks.
  • the method and apparatus have been described without reference to specific hardware or software. Instead, the method and apparatus have been described in such a manner that those skilled in the art can readily adapt such hardware and software as may be available or preferable for particular applications.

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Computer And Data Communications (AREA)
EP94304323A 1993-06-28 1994-06-15 Méthode de routage à traject minimal Expired - Lifetime EP0631413B1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US8382293A 1993-06-28 1993-06-28
US83822 1993-06-28

Publications (3)

Publication Number Publication Date
EP0631413A2 true EP0631413A2 (fr) 1994-12-28
EP0631413A3 EP0631413A3 (fr) 1995-11-02
EP0631413B1 EP0631413B1 (fr) 2001-07-04

Family

ID=22180923

Family Applications (1)

Application Number Title Priority Date Filing Date
EP94304323A Expired - Lifetime EP0631413B1 (fr) 1993-06-28 1994-06-15 Méthode de routage à traject minimal

Country Status (5)

Country Link
US (1) US5596719A (fr)
EP (1) EP0631413B1 (fr)
JP (1) JP3115769B2 (fr)
CA (1) CA2124974C (fr)
DE (1) DE69427618T2 (fr)

Cited By (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1995034981A2 (fr) * 1994-06-13 1995-12-21 Telefonaktiebolaget Lm Ericsson Amelioration du fonctionnement et des performances d'un reseau
US6069894A (en) * 1995-06-12 2000-05-30 Telefonaktiebolaget Lm Ericsson Enhancement of network operation and performance
EP1072126A1 (fr) * 1998-04-17 2001-01-31 Dynarc Inc. doing business as Dynamic Network Architecture, Inc. Procede et dispositif pour mode de transfert synchrone dynamique dans une topologie a double anneau
GB2379355A (en) * 2001-08-31 2003-03-05 Roke Manor Research Method of deriving a metric for a link in a network
EP1303944A2 (fr) * 2000-06-07 2003-04-23 Radiant Networks Plc Algorithme dynamique multivoies de routage
US6735178B1 (en) * 2000-05-10 2004-05-11 Ricochet Networks, Inc. Method for maximizing throughput for multiple links using directional elements
WO2007025853A1 (fr) * 2005-08-29 2007-03-08 Siemens Aktiengesellschaft Procede de routage iteratif a metrique de routage dependante de la charge
EP2071776A1 (fr) * 2007-11-27 2009-06-17 Alcatel Lucent Procédé de routage de trafic de données sur un réseau
US9258199B2 (en) 2003-03-24 2016-02-09 Strix Systems, Inc. Node placement method within a wireless network, such as a wireless local area network
US9664752B2 (en) 2013-05-24 2017-05-30 Allegro Microsystems, Llc Magnetic field sensor for detecting a magnetic field in any direction above thresholds
US9733106B2 (en) 2013-05-24 2017-08-15 Allegro Microsystems, Llc Magnetic field sensor to detect a magnitude of a magnetic field in any direction

Families Citing this family (99)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5564021A (en) * 1994-05-31 1996-10-08 Us West Technologies, Inc. Method for assigning inter-nodal traffic loads to channels in sonet rings
US6269398B1 (en) * 1993-08-20 2001-07-31 Nortel Networks Limited Method and system for monitoring remote routers in networks for available protocols and providing a graphical representation of information received from the routers
JP3084066B2 (ja) * 1993-12-24 2000-09-04 インターナシヨナル・ビジネス・マシーンズ・コーポレーシヨン 情報ネットワークにおける帯域幅予約接続の経路指定
US6185619B1 (en) 1996-12-09 2001-02-06 Genuity Inc. Method and apparatus for balancing the process load on network servers according to network and serve based policies
GB2305811A (en) * 1995-09-26 1997-04-16 Northern Telecom Ltd Traffic routing in a telecommunications network
JPH09219702A (ja) * 1996-02-14 1997-08-19 Nec Corp メッシュ構成の空き経路の検索方法
US5978364A (en) * 1996-02-29 1999-11-02 Philips Electronics North America Corporation Method for routing data packets within a wireless, packet-hopping network and a wireless network for implementing the same
US5870564A (en) * 1996-03-01 1999-02-09 Novell, Inc. Near-optimal path apparatus and method
US5913921A (en) * 1996-07-12 1999-06-22 Glenayre Electronics, Inc. System for communicating information about nodes configuration by generating advertisements having era values for identifying time reference for which the configuration is operative
GB9616801D0 (en) * 1996-08-09 1996-09-25 Madge Networks Ltd Data communication network
US6016307A (en) 1996-10-31 2000-01-18 Connect One, Inc. Multi-protocol telecommunications routing optimization
US6473404B1 (en) * 1998-11-24 2002-10-29 Connect One, Inc. Multi-protocol telecommunications routing optimization
US6067572A (en) * 1996-11-07 2000-05-23 Novell, Inc. Extrinsically influenced near-optimal path apparatus and method
US5838660A (en) * 1996-11-14 1998-11-17 Mci Communications Corporation Dynamic restoration process
US7054271B2 (en) 1996-12-06 2006-05-30 Ipco, Llc Wireless network system and method for providing same
US8982856B2 (en) 1996-12-06 2015-03-17 Ipco, Llc Systems and methods for facilitating wireless network communication, satellite-based wireless network systems, and aircraft-based wireless network systems, and related methods
US6233327B1 (en) 1997-02-14 2001-05-15 Statsignal Systems, Inc. Multi-function general purpose transceiver
US6412004B1 (en) * 1997-03-27 2002-06-25 Microsoft Corporation Metaserver for a multimedia distribution network
US6097727A (en) * 1997-04-29 2000-08-01 International Business Machines Corporation Methods, systems and computer program products for end-to-end route selection in compound wide/local area networks
US6064654A (en) * 1997-06-18 2000-05-16 Dialogic Corporation Internet facsimile timing technique
US6553002B1 (en) * 1997-08-29 2003-04-22 Ascend Communications, Inc. Apparatus and method for routing data packets through a communications network
EP0913965A1 (fr) * 1997-11-03 1999-05-06 Canon Kabushiki Kaisha Réduction du trafic de messages dans un réseau distribué
EP0935368A1 (fr) 1997-11-03 1999-08-11 Canon Kabushiki Kaisha Détection de chemin dans un réseau distribué
US6108710A (en) * 1997-11-26 2000-08-22 International Business Machine Corp. Method and apparatus for optimizing route generation in a connection oriented network
US6002670A (en) * 1997-12-12 1999-12-14 Nortel Networks Corporation Optimization and recovery techniques in IMA networks
US6553420B1 (en) * 1998-03-13 2003-04-22 Massachusetts Institute Of Technology Method and apparatus for distributing requests among a plurality of resources
US6430618B1 (en) 1998-03-13 2002-08-06 Massachusetts Institute Of Technology Method and apparatus for distributing requests among a plurality of resources
US6192404B1 (en) * 1998-05-14 2001-02-20 Sun Microsystems, Inc. Determination of distance between nodes in a computer network
US6914893B2 (en) 1998-06-22 2005-07-05 Statsignal Ipc, Llc System and method for monitoring and controlling remote devices
US6437692B1 (en) 1998-06-22 2002-08-20 Statsignal Systems, Inc. System and method for monitoring and controlling remote devices
US6891838B1 (en) * 1998-06-22 2005-05-10 Statsignal Ipc, Llc System and method for monitoring and controlling residential devices
US8410931B2 (en) 1998-06-22 2013-04-02 Sipco, Llc Mobile inventory unit monitoring systems and methods
US6646989B1 (en) * 1998-06-29 2003-11-11 Lucent Technologies Inc. Hop-by-hop routing with node-dependent topology information
US6377551B1 (en) * 1998-08-17 2002-04-23 Nortel Networks Limited QoS based route determination method for communications networks
US6611874B1 (en) * 1998-09-16 2003-08-26 International Business Machines Corporation Method for improving routing distribution within an internet and system for implementing said method
WO2000019680A2 (fr) * 1998-09-17 2000-04-06 Tod Mcnamara Systeme et procede d'optimisation d'intensite de trafic sur un reseau, au moyen de classes de trafic
US5943317A (en) * 1998-10-15 1999-08-24 International Business Machines Corp. Sub-network route optimization over a shared access transport facility
US6310881B1 (en) * 1998-10-20 2001-10-30 Terabeam Corporation Method and apparatus for network control
US6909700B1 (en) * 1998-11-24 2005-06-21 Lucent Technologies Inc. Network topology optimization methods and apparatus for designing IP networks with performance guarantees
US6321271B1 (en) * 1998-12-22 2001-11-20 Lucent Technologies Inc. Constrained shortest path routing method
WO2000039967A2 (fr) * 1998-12-23 2000-07-06 Nokia Wireless Routers, Inc. Plan d'acheminement unifie pour l'interconnexion de reseaux ad hoc
US6873616B1 (en) * 1998-12-28 2005-03-29 Nortel Networks Limited Quasi-deterministic gateway selection algorithm for multi-domain source routed networks
US6711137B1 (en) 1999-03-12 2004-03-23 International Business Machines Corporation System and method for analyzing and tuning a communications network
US7650425B2 (en) 1999-03-18 2010-01-19 Sipco, Llc System and method for controlling communication between a host computer and communication devices associated with remote devices in an automated monitoring system
US20030130977A1 (en) * 1999-08-06 2003-07-10 Oommen B. John Method for recognizing trees by processing potentially noisy subsequence trees
US6836463B2 (en) * 1999-10-15 2004-12-28 Nokia Corporation System for communicating labeled routing trees to establish preferred paths and source routes with local identifiers in wireless computer networks
US6683865B1 (en) 1999-10-15 2004-01-27 Nokia Wireless Routers, Inc. System for routing and switching in computer networks
US6721899B1 (en) * 2000-01-12 2004-04-13 Lucent Technologies Inc. Fault-tolerant non-flooding routing
US6816460B1 (en) * 2000-03-14 2004-11-09 Lucent Technologies Inc. Location based routing for mobile ad-hoc networks
IL151636A0 (en) * 2000-03-15 2003-04-10 Infosim Informationstechnik Gm Method and system for communication of data via an optimum data path in a network
US6762997B1 (en) * 2000-03-29 2004-07-13 Lucent Technologies Inc. Method for finding shortest network routing paths subject to system constraints
US7111073B1 (en) * 2000-05-30 2006-09-19 Cisco Technology, Inc. Apparatus for estimating delay and jitter between network routers
US7035537B2 (en) * 2000-06-29 2006-04-25 Corvis Corporation Method for wavelength switch network restoration
AU2001267746A1 (en) * 2000-07-06 2002-01-21 British Telecommunications Public Limited Company Packet routing
US7111163B1 (en) 2000-07-10 2006-09-19 Alterwan, Inc. Wide area network using internet with quality of service
FI112148B (fi) * 2000-07-24 2003-10-31 Stonesoft Oyj Tietoliikenteen ohjausmenetelmä
US6912203B1 (en) * 2000-07-31 2005-06-28 Cisco Technology, Inc. Method and apparatus for estimating delay and jitter between many network routers using measurements between a preferred set of routers
US6996064B2 (en) 2000-12-21 2006-02-07 International Business Machines Corporation System and method for determining network throughput speed and streaming utilization
US7116639B1 (en) 2000-12-21 2006-10-03 International Business Machines Corporation System and method for determining network discrete utilization
US6952700B2 (en) * 2001-03-22 2005-10-04 International Business Machines Corporation Feature weighting in κ-means clustering
US7139242B2 (en) * 2001-03-28 2006-11-21 Proficient Networks, Inc. Methods, apparatuses and systems facilitating deployment, support and configuration of network routing policies
US20020141378A1 (en) * 2001-03-28 2002-10-03 Bays Robert James Methods, apparatuses and systems facilitating deployment, support and configuration of network routing policies
US6937569B1 (en) * 2001-05-21 2005-08-30 Cisco Technology, Inc. Method and system for determining a relative position of a device on a network
US7359966B2 (en) * 2001-10-16 2008-04-15 Bbn Technologies Corp. Methods and systems for passive information discovery using Lomb periodogram processing
US7263479B2 (en) * 2001-10-19 2007-08-28 Bbn Technologies Corp. Determining characteristics of received voice data packets to assist prosody analysis
US7574597B1 (en) 2001-10-19 2009-08-11 Bbn Technologies Corp. Encoding of signals to facilitate traffic analysis
US8489063B2 (en) 2001-10-24 2013-07-16 Sipco, Llc Systems and methods for providing emergency messages to a mobile device
US7480501B2 (en) 2001-10-24 2009-01-20 Statsignal Ipc, Llc System and method for transmitting an emergency message over an integrated wireless network
US7424527B2 (en) * 2001-10-30 2008-09-09 Sipco, Llc System and method for transmitting pollution information over an integrated wireless network
US20040049595A1 (en) * 2001-12-04 2004-03-11 Mingzhou Sun System for proactive management of network routing
US7146000B2 (en) * 2002-01-25 2006-12-05 Level (3) Communications Routing engine for telecommunications network
US7251221B2 (en) * 2002-01-25 2007-07-31 Level 3 Communications, Llc Automated installation of network service in a telecommunications network
AU2003214168A1 (en) * 2002-03-12 2003-09-29 Wavemarket, Inc. Search-limited least-cost routing system
US20030202473A1 (en) * 2002-04-25 2003-10-30 General Instrument Corporation Traffic network flow control using dynamically modified metrics for redundancy connections
US7099341B2 (en) * 2002-05-03 2006-08-29 International Business Machines Corporation Traffic routing management system using the open shortest path first algorithm
US20040006640A1 (en) * 2002-07-03 2004-01-08 Inderieden Daniel W. Notification to routing protocols of changes to routing information base
US7941514B2 (en) 2002-07-31 2011-05-10 Level 3 Communications, Llc Order entry system for telecommunications network service
US7391732B1 (en) * 2002-08-05 2008-06-24 At&T Corp. Scheme for randomized selection of equal cost links during restoration
CN1235369C (zh) * 2002-09-17 2006-01-04 华为技术有限公司 一种实现光同步数字传送网多业务优化中路由分配的方法
US7280481B2 (en) * 2002-10-10 2007-10-09 Guangyi David Rong Shortest path search method “Midway”
US7260064B2 (en) * 2002-10-11 2007-08-21 Lucent Technologies Inc. Method and apparatus for performing network routing based on queue lengths
US7289520B2 (en) * 2002-11-20 2007-10-30 Hewlett-Packard Development Company, L.P. Method, apparatus, and system for expressway routing among peers
US7318105B1 (en) 2003-03-11 2008-01-08 Bbn Technologies Corp. Dynamically detecting topology and egress nodes in communication networks
WO2004086667A2 (fr) * 2003-03-24 2004-10-07 Strix Systems, Inc. Systeme de reseau de secteur local, sans fil, a auto-configuration et a auto-optimisation
US7664806B1 (en) * 2003-04-22 2010-02-16 At&T Corp. Routing XML queries
US7346706B2 (en) * 2003-05-02 2008-03-18 Alcatel Equivalent multiple path traffic distribution in communications networks
CN1599487A (zh) * 2003-09-19 2005-03-23 皇家飞利浦电子股份有限公司 用于无线通信体系中的路由选择方法以及执行该方法的移动终端
ITMI20040052A1 (it) * 2004-01-16 2004-04-16 Marconi Comm Spa Metodo per la selezione di una strategia per il re-instradamento di circuiti in una rete di comunicazione e rete con tale metodo
US8031650B2 (en) 2004-03-03 2011-10-04 Sipco, Llc System and method for monitoring remote devices with a dual-mode wireless communication protocol
US7756086B2 (en) 2004-03-03 2010-07-13 Sipco, Llc Method for communicating in dual-modes
US7414978B2 (en) * 2004-12-30 2008-08-19 Massachusetts Institute Of Technology Minimum-cost routing with network coding
US9439126B2 (en) 2005-01-25 2016-09-06 Sipco, Llc Wireless network protocol system and methods
US8392737B2 (en) * 2009-06-17 2013-03-05 Hewlett-Packard Development Company, L. P. System for controlling power consumption of a network
US8095684B2 (en) * 2009-09-15 2012-01-10 Symantec Corporation Intelligent device and media server selection for optimized backup image duplication
US20110087771A1 (en) * 2009-10-05 2011-04-14 Vss Monitoring, Inc. Method, apparatus and system for a layer of stacked network captured traffic distribution devices
JP5716587B2 (ja) * 2011-07-19 2015-05-13 富士通株式会社 経路決定装置，経路決定方法，管理プログラム及び管理装置
WO2013042207A1 (fr) * 2011-09-20 2013-03-28 富士通株式会社 Dispositif de nœud et procédé de communication
CN106780069A (zh) * 2016-12-24 2017-05-31 广东技术师范学院 一种基于节点社团重要度的局部动态路径选择机制方法
US11601357B2 (en) * 2020-12-22 2023-03-07 Arteris, Inc. System and method for generation of quality metrics for optimization tasks in topology synthesis of a network

Family Cites Families (10)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US4905233A (en) * 1987-11-23 1990-02-27 Harris Corporation Multiple path routing mechanism for packet communications network
US4912656A (en) * 1988-09-26 1990-03-27 Harris Corporation Adaptive link assignment for a dynamic communication network
US5115495A (en) * 1988-10-18 1992-05-19 The Mitre Corporation Communications network system using full-juncture and partial-juncture station status information for alternate-path distance-vector routing
US4974224A (en) * 1989-11-07 1990-11-27 Harris Corporation Distributed split flow routing mechanism for multi-node packet switching communication network
US5404451A (en) * 1990-02-06 1995-04-04 Nemirovsky; Paul System for identifying candidate link, determining underutilized link, evaluating addition of candidate link and removing of underutilized link to reduce network cost
US5253161A (en) * 1990-02-06 1993-10-12 Paul Nemirovsky Method for routing data in a near-optimal manner in a distributed data communications network
US5272638A (en) * 1991-05-31 1993-12-21 Texas Instruments Incorporated Systems and methods for planning the scheduling travel routes
US5233604A (en) * 1992-04-28 1993-08-03 International Business Machines Corporation Methods and apparatus for optimum path selection in packet transmission networks
US5289462A (en) * 1992-08-19 1994-02-22 International Business Machines Corp. Traffic management in packet communications networks
US5347511A (en) * 1993-06-07 1994-09-13 International Business Machines Corp. Traffic management in packet communications networks

Non-Patent Citations (10)

* Cited by examiner, † Cited by third party
Title
A. KHANNA; J. ZINKY: "The Revised ARPANET Routing Metric", COMPUTER COMM. REVIEW, SIGCOMM, October 1989 (1989-10-01)
ANDREW S. TANENBAUM: "Computer Networks", 1981, PRENTICE HALL, INC.
D. G. CANTOR; M. GERLA: "Optimal Routing in Packet Switched Computer Network", IEEE TRANSACTIONS COMPUTERS, vol. C-23, October 1974 (1974-10-01), pages 1062 - 1069
H. FRANK; W. CHOU: "Routing in Computer Networks", NETWORKS, vol. 1, 1971, pages 99 - 122
H. SOROUSH; P.B. MIRCHANDANI: "The Stochastic Multicommodity Flow Problem", NETWORKS, vol. 20, no. 2, March 1990 (1990-03-01), pages 121 - 155
J. M. MCQUILLAN; G. FALK; I. RICHER: "A Review of the Development and Performance of the ARPANET Routing Algorithm", IEEE TRANS. COMM., December 1978 (1978-12-01), pages 1802 - 1811
J. M. MCQUILLAN; I. RIDER; E. C. ROSEN: "The New Routing Algorithm for the ARPANET", IEEE TRANS. COMM., vol. 28, no. 5, May 1980 (1980-05-01), pages 711 - 719
JOHN MOY: "The OSPF Specification, Version 2", IETF DRAFT, January 1991 (1991-01-01)
ROBERT G. GALLAGER: "A Minimum Delay Routing Algorithm Using Distributed Computation", IEEE TRANSACTIONS ON COMMUNICATIONS, vol. COM-25, no. 1, January 1977 (1977-01-01), pages 73 - 85, XP000783811, DOI: doi:10.1109/TCOM.1977.1093711
THOMAS E. STERN: "A Class of Decentralized Routing Algorithms Using Relaxation", IEEE TRANSACTIONS ON COMMUNICATIONS, vol. COM-25, no. 10, October 1977 (1977-10-01), pages 1092 - 1102, XP000978611, DOI: doi:10.1109/TCOM.1977.1093750

Cited By (17)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1995034981A3 (fr) * 1994-06-13 1996-02-08 Ericsson Telefon Ab L M Amelioration du fonctionnement et des performances d'un reseau
AU692884B2 (en) * 1994-06-13 1998-06-18 Telefonaktiebolaget Lm Ericsson (Publ) Enhancement of network operation and performance
WO1995034981A2 (fr) * 1994-06-13 1995-12-21 Telefonaktiebolaget Lm Ericsson Amelioration du fonctionnement et des performances d'un reseau
US6069894A (en) * 1995-06-12 2000-05-30 Telefonaktiebolaget Lm Ericsson Enhancement of network operation and performance
EP1072126A1 (fr) * 1998-04-17 2001-01-31 Dynarc Inc. doing business as Dynamic Network Architecture, Inc. Procede et dispositif pour mode de transfert synchrone dynamique dans une topologie a double anneau
EP1072126A4 (fr) * 1998-04-17 2001-12-19 Dynarc Inc Doing Business As D Procede et dispositif pour mode de transfert synchrone dynamique dans une topologie a double anneau
US6735178B1 (en) * 2000-05-10 2004-05-11 Ricochet Networks, Inc. Method for maximizing throughput for multiple links using directional elements
EP1303944A4 (fr) * 2000-06-07 2007-09-12 Intel Corp Algorithme dynamique multivoies de routage
EP1303944A2 (fr) * 2000-06-07 2003-04-23 Radiant Networks Plc Algorithme dynamique multivoies de routage
GB2379355B (en) * 2001-08-31 2003-07-16 Roke Manor Research A method of deriving a metric for link in a network
GB2379355A (en) * 2001-08-31 2003-03-05 Roke Manor Research Method of deriving a metric for a link in a network
US9258199B2 (en) 2003-03-24 2016-02-09 Strix Systems, Inc. Node placement method within a wireless network, such as a wireless local area network
WO2007025853A1 (fr) * 2005-08-29 2007-03-08 Siemens Aktiengesellschaft Procede de routage iteratif a metrique de routage dependante de la charge
EP2071776A1 (fr) * 2007-11-27 2009-06-17 Alcatel Lucent Procédé de routage de trafic de données sur un réseau
US9664752B2 (en) 2013-05-24 2017-05-30 Allegro Microsystems, Llc Magnetic field sensor for detecting a magnetic field in any direction above thresholds
US9733106B2 (en) 2013-05-24 2017-08-15 Allegro Microsystems, Llc Magnetic field sensor to detect a magnitude of a magnetic field in any direction
US9897464B2 (en) 2013-05-24 2018-02-20 Allegro Microsystems, Llc Magnetic field sensor to detect a magnitude of a magnetic field in any direction

Also Published As

Publication number Publication date
EP0631413A3 (fr) 1995-11-02
US5596719A (en) 1997-01-21
DE69427618D1 (de) 2001-08-09
JP3115769B2 (ja) 2000-12-11
EP0631413B1 (fr) 2001-07-04
CA2124974A1 (fr) 1994-12-29
DE69427618T2 (de) 2002-05-29
CA2124974C (fr) 1998-08-25
JPH07177143A (ja) 1995-07-14

Similar Documents

Publication Publication Date Title
EP0631413B1 (fr) Méthode de routage à traject minimal
US6574669B1 (en) Method and apparatus for routing traffic within a network utilizing linear optimization
Chen et al. An efficient multipath forwarding method
EP1579716B1 (fr) Logique d'acheminement sur la base d'une representation d'espace virtuel
US5497368A (en) Routing method for a hierarchical communications network, and a hierarchical communications network having improved routing
US6023733A (en) Efficient path determination in a routed network
KR100544008B1 (ko) 효율적인 경로 코스트 집합 도출 방법 및 장치
US8289982B2 (en) Efficient discovery and verification of paths through a meshed overlay network
US5274643A (en) Method for optimizing a network having virtual circuit routing over virtual paths
Bressoud et al. Optimal configuration for BGP route selection
US7334047B1 (en) Method and system for selective link state advertisement blocking over a data network area
US6823395B1 (en) Arrangement and method relating to routing in a network
US20060133282A1 (en) Systems and methods for multipath routing
Ramakrishnan et al. Optimal routing in shortest‐path data networks
US20070053300A1 (en) Methods, systems, and computer program products for multi-path shortest-path-first computations and distance-based interface selection for VoIP traffic
WO2007126616A2 (fr) Procédé et dispositif pour routage amélioré dans des réseaux sans connexion
Ben-Ameur et al. Routing strategies for IP networks
Chiang et al. A multipath transmission scheme for the improvement of throughput over SDN
RU2680764C1 (ru) Способ, устройство и система для оптимизации транспортной сети связи
US11070472B1 (en) Dynamically mapping hash indices to member interfaces
Komajwar et al. SPRM: Source path routing model and link failure handling in software-defined networks
Cisco IP Enhanced IGRP Commands
Qin et al. Minimum cost multi-path parallel transmission with delay constraint by extending openflow
Garcia-Luna-Aceves et al. Area-based, loop-free internet routing
JP3622672B2 (ja) パケット転送中継装置および転送制御方法

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: A2

Designated state(s): DE ES FR GB IT SE

PUAL Search report despatched

Free format text: ORIGINAL CODE: 0009013

AK Designated contracting states

Kind code of ref document: A3

Designated state(s): DE ES FR GB IT SE

17P Request for examination filed

Effective date: 19960418

GRAG Despatch of communication of intention to grant

Free format text: ORIGINAL CODE: EPIDOS AGRA

GRAG Despatch of communication of intention to grant

Free format text: ORIGINAL CODE: EPIDOS AGRA

GRAH Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOS IGRA

17Q First examination report despatched

Effective date: 20001120

GRAH Despatch of communication of intention to grant a patent

Free format text: ORIGINAL CODE: EPIDOS IGRA

GRAA (expected) grant

Free format text: ORIGINAL CODE: 0009210

AK Designated contracting states

Kind code of ref document: B1

Designated state(s): DE ES FR GB IT SE

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: IT

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRE;WARNING: LAPSES OF ITALIAN PATENTS WITH EFFECTIVE DATE BEFORE 2007 MAY HAVE OCCURRED AT ANY TIME BEFORE 2007. THE CORRECT EFFECTIVE DATE MAY BE DIFFERENT FROM THE ONE RECORDED.SCRIBED TIME-LIMIT

Effective date: 20010704

REF Corresponds to:

Ref document number: 69427618

Country of ref document: DE

Date of ref document: 20010809

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: SE

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20011004

ET Fr: translation filed
REG Reference to a national code

Ref country code: GB

Ref legal event code: IF02

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: ES

Free format text: LAPSE BECAUSE OF FAILURE TO SUBMIT A TRANSLATION OF THE DESCRIPTION OR TO PAY THE FEE WITHIN THE PRESCRIBED TIME-LIMIT

Effective date: 20020131

PLBE No opposition filed within time limit

Free format text: ORIGINAL CODE: 0009261

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

Free format text: STATUS: NO OPPOSITION FILED WITHIN TIME LIMIT

26N No opposition filed
PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: GB

Payment date: 20130619

Year of fee payment: 20

Ref country code: DE

Payment date: 20130620

Year of fee payment: 20

PGFP Annual fee paid to national office [announced via postgrant information from national office to epo]

Ref country code: FR

Payment date: 20130703

Year of fee payment: 20

REG Reference to a national code

Ref country code: FR

Ref legal event code: TP

Owner name: ALCATEL-LUCENT USA INC., US

Effective date: 20130823

Ref country code: FR

Ref legal event code: CD

Owner name: ALCATEL-LUCENT USA INC., US

Effective date: 20130823

REG Reference to a national code

Ref country code: GB

Ref legal event code: 732E

Free format text: REGISTERED BETWEEN 20140102 AND 20140108

REG Reference to a national code

Ref country code: GB

Ref legal event code: 732E

Free format text: REGISTERED BETWEEN 20140109 AND 20140115

REG Reference to a national code

Ref country code: FR

Ref legal event code: GC

Effective date: 20140410

REG Reference to a national code

Ref country code: DE

Ref legal event code: R071

Ref document number: 69427618

Country of ref document: DE

REG Reference to a national code

Ref country code: GB

Ref legal event code: PE20

Expiry date: 20140614

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: GB

Free format text: LAPSE BECAUSE OF EXPIRATION OF PROTECTION

Effective date: 20140614

PG25 Lapsed in a contracting state [announced via postgrant information from national office to epo]

Ref country code: DE

Free format text: LAPSE BECAUSE OF EXPIRATION OF PROTECTION

Effective date: 20140617

REG Reference to a national code

Ref country code: FR

Ref legal event code: RG

Effective date: 20141015