[go: up one dir, main page]

EP1762060A1 - Efficient calculation of routing tables for a routing operation using target addresses - Google Patents

Efficient calculation of routing tables for a routing operation using target addresses

Info

Publication number
EP1762060A1
EP1762060A1 EP05754546A EP05754546A EP1762060A1 EP 1762060 A1 EP1762060 A1 EP 1762060A1 EP 05754546 A EP05754546 A EP 05754546A EP 05754546 A EP05754546 A EP 05754546A EP 1762060 A1 EP1762060 A1 EP 1762060A1
Authority
EP
European Patent Office
Prior art keywords
routing
node
routes
nodes
central
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
EP05754546A
Other languages
German (de)
French (fr)
Inventor
Thomas Engel
Christoph Reichert
Joachim Charzinski
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.)
Nokia Solutions and Networks GmbH and Co KG
Fraunhofer Gesellschaft zur Foerderung der Angewandten Forschung eV
Original Assignee
Siemens AG
Nokia Siemens Networks GmbH and Co KG
Fraunhofer Gesellschaft zur Foerderung der Angewandten Forschung eV
Siemens 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 Siemens AG, Nokia Siemens Networks GmbH and Co KG, Fraunhofer Gesellschaft zur Foerderung der Angewandten Forschung eV, Siemens Corp filed Critical Siemens AG
Publication of EP1762060A1 publication Critical patent/EP1762060A1/en
Withdrawn legal-status Critical Current

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
    • 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/42—Centralised routing

Definitions

  • the invention relates to a method and a device for calculating a routing table for routing within a communication network formed with nodes and links.
  • next node determines from the routing table present to the node, which relates the destination addresses contained in the packets to next hops.
  • the routing tables are set up or calculated by means of routing protocols. Examples of such routing protocols are the Open Shortest Path First (OSPF) protocol used on the Internet and used in conjunction with the IP (Internet Protocol) protocol and the IS / IS (Intermediate System to Intermediate System) protocol , Routing based on destination addresses specified in the packets is also referred to as "destination-based routing" or routing based on destination addresses.
  • OSPF Open Shortest Path First
  • IP Internet Protocol
  • IS / IS Intermediate System to Intermediate System
  • the object of the invention is to optimize the calculation of routing tables for communication networks formed with nodes and links.
  • the object is achieved by the subject matters of the independent claims 1 and 10.
  • the invention is based on the idea of carrying out part of the calculations for setting up routing tables on a server.
  • the following is a simplified assumption of a server and its calculations are called central calculations, although the
  • a central calculation of routes is carried out between in each case one network-internal start and end node.
  • start and end nodes are nodes of the network, that is, edge nodes or inner nodes.
  • For traffic which is routed to a destination outside the communication network it makes sense to use one of the edge nodes of the communication network as the end node, from which the traffic is transmitted in the direction of the destination to another network.
  • Information about the centrally calculated routes are communicated to a node of the network, for example by means of a communication protocol. This information consists e.g. from the specification of the next hop for the routing to an edge node.
  • the node calculates by means of a routing protocol, for example the OSPF protocol or the IS / IS protocol, the entries for a Routingtabel ⁇ le.
  • a routing protocol for example the OSPF protocol or the IS / IS protocol
  • destination addresses learned via the routing protocol of packets to be transported are assigned to the centrally calculated network-internal routes.
  • This mapping can be done using unique router IDs, such as the 32-bit router ID described in the OSPF Standard RFC2328.
  • the information transmitted to the router does not necessarily include complete routes. In principle, the information about the calculated routes can be limited to the information needed for an assignment of
  • Destination addresses to routes is necessary. How extensive the information is in the individual case depends on the routing used. In conventional IP networks, e.g. the next hops are routed to an end node within the network (e.g., an edge node from which a further route to another network occurs) and the respective end node is specified.
  • an end node within the network e.g., an edge node from which a further route to another network occurs
  • the invention has the advantage that the calculation of the routes takes place centrally and thus the information relating to the routes can be forwarded to a plurality of nodes, for example all nodes of the network, so that the corresponding computational effort is only once and not for all nodes using the routes are incurred.
  • the invention is particularly advantageous in the use of multipath routing, because in this case the route calculation is considerably more complex and thus more computational effort can be saved. Information that is used only for route calculation, for example a traffic matrix, does not need to be distributed to the individual nodes in this way. In the case of multipath routing, a central determination of traffic distribution weights can also be carried out.
  • the traffic distribution weights serve to control the distribution of the traffic to the alternative routes of the multipath routing and can be used at the router for the determination or calculation of routing tables.
  • each node can continue to react autonomously in the event of a fault, ie Thus, from a failed connection to a neighbor, the remaining routes of the multipath routing have to be changed, that is, they do not depend on a quick reaction of the central calculations.
  • the invention also encompasses a device for calculating a routing table within a communication network formed with nodes and links, which has a central device (eg a server) with means for calculating routes between end nodes of a network and at least one node
  • a central device eg a server
  • Means for creating a routing table by means of a routing protocol are provided for communication between the central device and the respective node, which comprise, for example, a communication protocol. If the network works with multipath routing, means for determining traffic distribution weights in the central device and means for transmitting the distribution weights to the nodes can also be provided.
  • NCS Network Control Server
  • routers or nodes A through G are shown which form part of a network.
  • the figure describes how the router D computes a part of its routing table with the aid of routing information provided by the central device NCS.
  • Routers A, F, G and E represent next hops or nodes directly connected to router D.
  • Routers B and C are edge routers of the network over which traffic is routed to other networks.
  • the dotted links connecting these two edge routers B and C to the other illustrated routers of the network indicate dropped network elements (roughness). ter and links) via which traffic can be forwarded to the edge nodes.
  • the table T1 contains information which is transmitted from the central device NCS to the node D. This information is intended for multipath routing, which provides at least two alternative next hops of D for the transmission of traffic to a destination.
  • the central device specifies to the node that traffic to be transmitted to the edge node B is to be transmitted 20% over the next hop F and 80% over the next hop G. Traffic to edge node C is to be transferred 60% over the next hop E and 40% over the next hop G.
  • addresses Pl to P3 of networks are shown, which are accessible via the edge router or edge node C.
  • the addresses P4 to P6 of networks which can be reached via the edge router B are shown in the table T3.
  • the representation of the addresses follows the usual convention for the representation of IP addresses, whereby the address and the mask (behind the slash) necessary for the interpretation of the address as network address are specified.
  • the information about the networks which can be reached via respective edge routers is propagated through the network.
  • the router D learns which networks it can reach via the edge routers B and C, respectively. It therefore assigns these network addresses to next hops in accordance with the information transmitted by the central device.
  • the resulting routing table FIB (FIB: stands for forwarding information base) is shown in the figure.
  • the network addresses Pl to P3 are assigned the next hops E and G and the network addresses P4 to P6 the next hops F and G.
  • the table FIB shown in the figure shows only a very small section of a realistic routing table. Actual routing tables are far more extensive.
  • the invention requires only a simple assignment of the network addresses available to the edge routers the central device are made predetermined next hops or vor ⁇ given routes. There is no need to complete route calculation at each of the nodes.

Landscapes

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

Abstract

The invention relates to a method and a device (NCS) allowing the distributed calculation of routing tables for routing in a communication network containing nodes (A,..,G) and links. The calculation of routes to be used is carried out in centrally. Data relating to the routes to be used are transmitted to a node (D) which, based on said information, generates a routing table (FIB) by assigning packet addresses to the routes. The central calculation of the routes results in an increased efficiency of resources while requiring less calculation effort which is particularly advantageous in the context of networks comprising multipath routing where the calculation of routing tables (FIB) is very complex. A further reduction in effort can be achieved by means of the central calculation of the distribution weightings.

Description

Effiziente Berechnung von Routingtabellen für ein Routing an¬ hand von ZieladressenEfficient calculation of routing tables for routing an¬ hand of destination addresses

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zur Berechnung einer Routingtabellen für ein Routing innerhalb eines mit Knoten und Links gebildeten Kommunikationsnetzes.The invention relates to a method and a device for calculating a routing table for routing within a communication network formed with nodes and links.

Der Transport von Verkehr in Datennetzen, vor allem im Hin¬ blick auf Einhaltung von Dienstgüteparametern, ist ein aktu¬ elles Arbeitsgebiet für Netzwerkspezialisten und Internet¬ fachleute.The transport of traffic in data networks, above all with regard to compliance with quality of service parameters, is an ongoing field of work for network specialists and Internet experts.

Der Großteil heutiger Datennetze ist mit Knoten bzw. Routern und Links bzw. Kanten gebildet, wobei der Verkehr paketweise von Knoten zu Knoten übermittelt wird. Üblicherweise bestimmt sich der nächste Knoten (oder der "next hop") aus der dem Knoten vorliegenden Routingtabelle, welche die in den Paketen enthaltenen Zieladressen mit nächsten Hops in Beziehung setzt. Üblicherweise werden die Routingtabellen mittels Rou¬ tingprotokollen aufgestellt bzw. berechnet. Beispiele für derartige Routingprotokolle sind das OSPF (Open Shortest Path First)-Protokoll, welches in dem Internet verwendet wird und zusammen mit dem IP (Internet Protocol)—Protokoll eingesetzt wird, sowie das IS/IS (Intermediate System to Intermediate System)-Protokoll. Das Routing anhand von in den Paketen spe¬ zifizierten Zieladressen wird auch als "Destination Based Routing" oder Routing anhand von Zieladressen bezeichnet.The majority of today's data networks are formed with nodes or routers and links or edges, whereby the traffic is transmitted in packets from node to node. Usually, the next node (or "next hop") determines from the routing table present to the node, which relates the destination addresses contained in the packets to next hops. Usually, the routing tables are set up or calculated by means of routing protocols. Examples of such routing protocols are the Open Shortest Path First (OSPF) protocol used on the Internet and used in conjunction with the IP (Internet Protocol) protocol and the IS / IS (Intermediate System to Intermediate System) protocol , Routing based on destination addresses specified in the packets is also referred to as "destination-based routing" or routing based on destination addresses.

Herkömmliches Routing in Datennetzen ist ein "Best Effort"- Routing, das heißt, es werden keine Garantien für die Dienst¬ güte beziehungsweise die Einhaltung von Dienstgüteparametern gegeben. Neue Entwicklungen gehen dahin, das Routingkonzept von Datenpaketen für die Übertragung von Echtzeitdaten, wieConventional routing in data networks is a "best effort" routing, which means that there are no guarantees for the quality of service or compliance with quality of service parameters. New developments go there, the routing concept of data packets for the transmission of real-time data, such as

Sprache, Video- oder Audioinformationen zu erweitern, wozu es 'der Einhaltung von Dienstgüteparametern bedarf. Ein zentraler Ansatz für die Verbesserung der Übertragungsqualität bei Da¬ tenübertragung über ein Datennetz ist die Verwendung von Mehrwegerouting, d.h. zu einem Ziel werden alternative Routen zur Verfügung gestellt, wodurch der Ausfall von Links oder ÜberlastSituationen abgefangen werden können.Extend voice, video or audio information, which requires compliance with quality of service parameters. A central The approach for improving the transmission quality in the case of data transmission over a data network is the use of multipath routing, ie alternative routes are made available to a destination, whereby the failure of links or overload situations can be intercepted.

Der Aufwand bei der Berechnung von Routingtabellen nimmt mit der Zunahme möglicher Ziele und vor allem - bei Mehrwegerou— ting - möglicher Routen erheblich zu.The effort involved in the calculation of routing tables increases considerably with the increase in possible destinations and, above all, with multipath routing - possible routes.

Die Erfindung hat zur Aufgabe, die Berechnung von Routingta¬ bellen für mit Knoten und Links gebildete Kommunikationsnetze zu optimieren.The object of the invention is to optimize the calculation of routing tables for communication networks formed with nodes and links.

Die Aufgabe wird durch die Gegenstände der unabhängigen An¬ sprüche 1 und 10 gelöst. Die Erfindung beruht auf dem Gedan¬ ken, einen Teil der Berechnungen für die Aufstellung von Rou¬ tingtabellen auf einem Server durchzuführen. Im folgenden wird vereinfacht von einem Server ausgegangen und werden sei- ne Berechnungen zentrale Berechnungen genannt, obwohl zurThe object is achieved by the subject matters of the independent claims 1 and 10. The invention is based on the idea of carrying out part of the calculations for setting up routing tables on a server. The following is a simplified assumption of a server and its calculations are called central calculations, although the

Verbesserung der Verfügbarkeit auch ein Verbund mehrerer Ser¬ ver genutzt werden kann. Erfindungsgemäß wird eine zentrale Berechnung von Routen zwischen jeweils einem netzinternen An¬ fangs- und Endknoten vorgenommen. Dabei ist netzintern so zu verstehen, dass Anfangs- und Endknoten Knoten des Netzes sind, das heißt, Randknoten oder innere Knoten. Für Verkehr, welcher zu einem Ziel außerhalb des Kommunikationsnetzes ge¬ leitet wird, ist es sinnvoll, als Endknoten einen der Rand¬ knoten des Kommunikationsnetzes zu verwenden, von dem der Verkehr in Richtung Ziel in ein anderes Netz übertragen wird. Informationen über die zentral berechneten Routen werden - beispielsweise mittels eines Kommunikationsprotokolls - einem Knoten des Netzes mitgeteilt. Diese Informationen bestehen z.B. aus der Angabe des nächsten Hops für das Routing zu ei- nem Randknoten.Improved availability and a combination of Ser¬ ver can be used. According to the invention, a central calculation of routes is carried out between in each case one network-internal start and end node. It is to be understood internally in the network that start and end nodes are nodes of the network, that is, edge nodes or inner nodes. For traffic which is routed to a destination outside the communication network, it makes sense to use one of the edge nodes of the communication network as the end node, from which the traffic is transmitted in the direction of the destination to another network. Information about the centrally calculated routes are communicated to a node of the network, for example by means of a communication protocol. This information consists e.g. from the specification of the next hop for the routing to an edge node.

Auf Grundlage dieser Informationen berechnet der Knoten mit¬ tels eines Routingprotokolls, zum Beispiel dem OSPF-Protokoll oder dem IS/IS-Protokoll, die Einträge für eine Routingtabel¬ le. Dabei werden über das Routingprotokoll gelernte Zielad¬ ressen von zu transportierenden Paketen den zentral berechne¬ ten netzinternen Routen zugeordnet. Diese Zuordnung kann an- hand von eindeutigen Router-IDs erfolgen, zum Beispiel anhand der im OSPF Standard RFC2328 beschrieben 32-Bit Router-ID. Die an den Router übermittelten Informationen müssen nicht notwendigerweise vollständige Routen beinhalten. Im Prinzip können die Informationen über die berechneten Routen auf die Informationen beschränkt werden, die für eine Zuordnung vonOn the basis of this information, the node calculates by means of a routing protocol, for example the OSPF protocol or the IS / IS protocol, the entries for a Routingtabel¬ le. In this case, destination addresses learned via the routing protocol of packets to be transported are assigned to the centrally calculated network-internal routes. This mapping can be done using unique router IDs, such as the 32-bit router ID described in the OSPF Standard RFC2328. The information transmitted to the router does not necessarily include complete routes. In principle, the information about the calculated routes can be limited to the information needed for an assignment of

Zieladressen zu Routen notwendig ist. Wie umfangreich die In¬ formationen im Einzelfall sind, hängt von dem verwendeten Routing ab. Bei herkömmlichen IP Netzen können z.B. die nächsten Hops für das Routing zu einem Endknoten innerhalb des Netzes (z.B. einem Randknoten, von dem aus ein Weiterrou¬ ten in ein anderes Netz erfolgt) und der jeweilige Endknoten spezifiziert werden.Destination addresses to routes is necessary. How extensive the information is in the individual case depends on the routing used. In conventional IP networks, e.g. the next hops are routed to an end node within the network (e.g., an edge node from which a further route to another network occurs) and the respective end node is specified.

Die Erfindung hat den Vorteil, dass die Berechnung der Routen zentral erfolgt und so die die Routen betreffenden Informati¬ onen einer Vielzahl von Knoten, zum Beispiel allen Knoten des Netzes, weitergegeben werden können, so dass der entsprechen¬ de Rechenaufwand nur einmal und nicht für alle die Routen verwendenden Knoten anfällt. Die Erfindung ist besonders vor- teilhaft bei der Verwendung von Mehrwegerouting, weil in die¬ sem Fall die Routenberechnung deutlich aufwändiger ist und so mehr Rechenaufwand eingespart werden kann. Informationen, die nur zur Routenberechnung verwendet werden, beispielsweise ei¬ ne Verkehrsmatrix, braucht so nicht an die einzelnen Knoten verteilt zu werden. Bei Mehrwegerouting kann zudem eine zent¬ rale Bestimmung von Verkehrsverteilgewichten vorgenommen wer¬ den Verkehrsverteilgewichte dienen zur Steuerung der Auftei¬ lung des Verkehrs auf die alternativen Routen des Mehrwege¬ routings und können am Router für die Bestimmung bzw. Berech- nung von Routingtabellen verwendet werden. Trotz der zentra¬ len Berechnungen kann bei Mehrwegerouting jeder Knoten im Fehlerfall weiterhin selbständig reagieren, dass heißt Ver- kehr von einer ausgefallenen Verbindung zu einem Nachbarkno¬ ten auf die verbleibenden Routen des Mehrwegeroutings umlei¬ ten, ist also nicht auf eine schnelle Reaktion der zentralen Berechnungen angewiesen.The invention has the advantage that the calculation of the routes takes place centrally and thus the information relating to the routes can be forwarded to a plurality of nodes, for example all nodes of the network, so that the corresponding computational effort is only once and not for all nodes using the routes are incurred. The invention is particularly advantageous in the use of multipath routing, because in this case the route calculation is considerably more complex and thus more computational effort can be saved. Information that is used only for route calculation, for example a traffic matrix, does not need to be distributed to the individual nodes in this way. In the case of multipath routing, a central determination of traffic distribution weights can also be carried out. The traffic distribution weights serve to control the distribution of the traffic to the alternative routes of the multipath routing and can be used at the router for the determination or calculation of routing tables. Despite the central calculations, in multipath routing each node can continue to react autonomously in the event of a fault, ie Thus, from a failed connection to a neighbor, the remaining routes of the multipath routing have to be changed, that is, they do not depend on a quick reaction of the central calculations.

Die Erfindung umfasst auch eine Vorrichtung zur Berechnung einer Routingtabelle innerhalb eines mit Knoten und Links ge¬ bildeten Kommunikationsnetzes, welche eine zentrale Vorrich¬ tung (z.B. ein Server) mit Mitteln zur Berechnung von Routen zwischen Endknoten eines Netzes, sowie wenigstens einen Kno¬ ten mit Mitteln zum Erstellen einer Routingtabelle mittels eines Routingprotokolls umfasst. Dabei sind Mittel zur Kommu¬ nikation zwischen der zentralen Vorrichtung und dem bezie¬ hungsweise den Knoten gegeben, welche zum Beispiel ein Kommu- nikationsprotokoll umfassen. Falls das Netz mit Mehrwegerou¬ ting arbeitet, können auch Mittel zur Bestimmung von Ver¬ kehrsverteilgewichten in der zentralen Vorrichtung und Mittel zur Übermittlung der Verteilungsgewichte zu den Knoten gege¬ ben sein. • The invention also encompasses a device for calculating a routing table within a communication network formed with nodes and links, which has a central device (eg a server) with means for calculating routes between end nodes of a network and at least one node Comprises means for creating a routing table by means of a routing protocol. In this case, means are provided for communication between the central device and the respective node, which comprise, for example, a communication protocol. If the network works with multipath routing, means for determining traffic distribution weights in the central device and means for transmitting the distribution weights to the nodes can also be provided. •

Im Folgenden wird der Erfindungsgegenstand im Rahmen eines Ausführungsbeispiels anhand einer Figur näher erläutert.In the following, the subject invention is explained in more detail in the context of an embodiment with reference to a figure.

In der Figur ist eine zentrale Vorrichtung NCS (NCS: steht für Network Control Server) dargestellt, welche erfindungsge¬ mäß einen Teil der Berechnungen für die Erstellung von Rou¬ tingtabellen vornimmt. Weiter sind Router bzw. Knoten A bis G gezeigt, welche Teil eines Netzwerks bilden. Anhand der Figur wird beschrieben, wie der Router D einen Teil seiner Routing- tabelle mit Hilfe von durch die zentrale Vorrichtung NCS be¬ reitgestellter Routinginformationen berechnet. Die Router A, F, G und E stellen nächste Hops bzw. unmittelbar dem Router D verbundene Knoten dar. Die Router B und C sind Randrouter des Netzes, über welche Verkehr zu anderen Netzen weitergeleitet wird. Die punktierten Verbindungen, mit denen diese beiden Randrouter B und C mit den anderen dargestellten Routern des Netzes verbunden sind, deuten ausgelassene Netzelemente (Rou- ter und Links) an, über welche Verkehr zu den Randknoten wei¬ tergeleitet werden kann. In der Tabelle Tl ist Information enthalten, welche von der zentralen Vorrichtung NCS dem Kno¬ ten D übermittelt wird. Diese Information ist bestimmt für ein Mehrwegerouting, welches für die Übertragung von Verkehr zu einem Ziel wenigstens zwei alternative nächste Hops von D vorsieht. Durch die zentrale Vorrichtung wird dem Knoten vor¬ gegeben, dass zu dem Randknoten B zu übermittelnder Verkehr zu 20% über den nächsten Hop F und zu 80% über den nächsten Hop G zu übertragen sind. Verkehr zu dem Randknoten C soll zu 60% über den nächsten Hop E und zu 40% über den nächsten Hop G übertragen werden. In der Tabelle T2 sind Adressen Pl bis P3 von Netzwerken dargestellt, welche über den Randrouter bzw. Randknoten C erreichbar sind. In entsprechender Weise sind in der Tabelle T3 die Adressen P4 bis P6 von Netzwerken dargestellt, welche über den Randrouter B erreichbar sind. Die Darstellung der Adressen folgt der üblichen Konvention für die Darstellung von IP-Adressen, wobei die Adresse und die für die Interpretation der Adresse als Netzwerkadresse notwendige Maske (hinter dem Schrägstrich) angegeben ist.In the figure, a central device NCS (NCS: stands for Network Control Server) is shown, which according to the invention performs a part of the calculations for the creation of routing tables. Further, routers or nodes A through G are shown which form part of a network. The figure describes how the router D computes a part of its routing table with the aid of routing information provided by the central device NCS. Routers A, F, G and E represent next hops or nodes directly connected to router D. Routers B and C are edge routers of the network over which traffic is routed to other networks. The dotted links connecting these two edge routers B and C to the other illustrated routers of the network indicate dropped network elements (roughness). ter and links) via which traffic can be forwarded to the edge nodes. The table T1 contains information which is transmitted from the central device NCS to the node D. This information is intended for multipath routing, which provides at least two alternative next hops of D for the transmission of traffic to a destination. The central device specifies to the node that traffic to be transmitted to the edge node B is to be transmitted 20% over the next hop F and 80% over the next hop G. Traffic to edge node C is to be transferred 60% over the next hop E and 40% over the next hop G. In the table T2 addresses Pl to P3 of networks are shown, which are accessible via the edge router or edge node C. In a corresponding manner, the addresses P4 to P6 of networks which can be reached via the edge router B are shown in the table T3. The representation of the addresses follows the usual convention for the representation of IP addresses, whereby the address and the mask (behind the slash) necessary for the interpretation of the address as network address are specified.

Mittels des OSPF-Protokolls werden die Informationen über die über jeweilige Randrouter erreichbaren Netzwerke durch das Netz propagiert. Auf diese Weise erfährt der Router D, welche Netzwerke er über die Randrouter B bzw. C erreichen kann. Er ordnet deshalb diesen Netzwerkadressen nach Maßgabe der durch die zentrale Vorrichtung übermittelten Informationen nächste Hops zu. Die resultierende Routingtabelle FIB (FIB: steht für forwarding Information base) ist in der Figur gezeigt. Den Netzwerkadressen Pl bis P3 werden die nächsten Hops E und G und den Netzwerkadressen P4 bis P6 die nächsten Hops F und G zugeordnet. Die in der Figur dargestellte Tabelle FIB zeigt nur einen sehr kleinen Ausschnitt aus einer realistischen Routingtabelle. Tatsächliche Routingtabellen sind weit um¬ fangreicher.By means of the OSPF protocol, the information about the networks which can be reached via respective edge routers is propagated through the network. In this way, the router D learns which networks it can reach via the edge routers B and C, respectively. It therefore assigns these network addresses to next hops in accordance with the information transmitted by the central device. The resulting routing table FIB (FIB: stands for forwarding information base) is shown in the figure. The network addresses Pl to P3 are assigned the next hops E and G and the network addresses P4 to P6 the next hops F and G. The table FIB shown in the figure shows only a very small section of a realistic routing table. Actual routing tables are far more extensive.

Durch die Erfindung muss nur eine einfache Zuordnung der den Randroutern zur Verfügung stehenden Netzwerkadressen zu durch die zentrale Vorrichtung vorgegebenen nächsten Hops bzw. vor¬ gegebenen Routen gemacht werden. Es braucht keine vollständi¬ ge Routenberechnung bei jedem der Knoten stattzufinden. The invention requires only a simple assignment of the network addresses available to the edge routers the central device are made predetermined next hops or vor¬ given routes. There is no need to complete route calculation at each of the nodes.

Claims

Patentansprüche claims 1. Verfahren zur Berechnung einer Routingtabelle (FIB) für ein Routing innerhalb eines mit Knoten (A, ..,G) und Links ge- bildeten Kommunikationsnetzes, bei dem1. A method for calculating a routing table (FIB) for routing within a communication network formed with nodes (A,..., G) and links, in which - eine zentrale Berechnung von Routen zwischen jeweils einem netzinternen Anfangs- und Endknoten vorgenommen wird,a central calculation of routes is made between in each case one in-net start and end node, - wenigstens einem Knoten (D) des Netzes Informationen über die berechneten Routen kommuniziert werden, - durch den Knoten (D) mittels eines Routingprotokolls eine Routingtabelle (FIB) für das Routing von Paketen aufgebaut wird, indem Zieladressen von zu transportierenden Paketen den berechneten Routen zugeordnet werden.- information about the calculated routes is communicated to at least one node (D) of the network, - a routing protocol (FIB) for the routing of packets is established by the node (D) by assigning destination addresses of packets to be transported to the calculated routes become. 2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, dass die Informationen über die berechneten Routen eine eindeutige Kennzeichnung für Endknoten (B,C) und für das Routing zu die¬ sen Endknoten (B,C) zu verwendende nächste Knoten umfassen.2. The method according to claim 1, characterized in that the information about the calculated routes include a unique identifier for end nodes (B, C) and for the routing to die¬ sen end nodes (B, C) to be used next node. 3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, dass zumindest der Anfangsknoten oder Endknoten (B,C) ein Randkno¬ ten ist.3. The method according to claim 1 or 2, characterized in that at least the initial node or end node (B, C) is a Randkno¬ th. 4. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass4. The method according to any one of the preceding claims, characterized in that - es sich bei dem Routing um ein Mehrwegerouting handelt und zwischen dem Anfangs- und Endknoten eine Mehrzahl von Routen berechnet werden.- The routing is a Mehrwegerouting and between the start and end nodes a plurality of routes are calculated. 5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, dass5. The method according to claim 4, characterized in that - eine zentrale Bestimmung von Verkehrsverteilgewichten zur Steuerung der Aufteilung von Verkehr auf alternativ verfügba¬ re Routen vorgenommen wird, - dem Knoten (D) die Verkehrsverteilgewichte kommuniziert werden, unda central determination of traffic distribution weights is carried out to control the distribution of traffic on alternatively available routes, - the nodes (D) the traffic distribution weights are communicated, and - die Routingtabelle (FIB) nach Maßgabe der Verkehrsverteil¬ gewichte aufgebaut wird.- The routing table (FIB) is constructed in accordance with the Verkehrsverteil¬ weights. 6. Verfahren nach Anspruch 4 oder 5, dadurch gekennzeichnet, dass es sich bei dem Mehrwegerouting um ein Routing handelt, bei dem die Anzahl der alternativen abgehenden Links für das Rou- ting zu dem Endknoten (B,C) für eine maximale Anzahl von in¬ neren Knoten gleich oder größer zwei ist.6. Method according to claim 4 or 5, characterized in that the multipath routing is a routing in which the number of alternative outgoing links for the routing to the end node (B, C) for a maximum number of times in ¬ neren node is equal to or greater than two. 7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, dass - der Knoten (D) ein inneren Knoten des Kommunikationsnetzes ist, für den nur ein abgehender Link zu dem Endknoten (B,C) gegeben ist,Method according to claim 6, characterized in that - the node (D) is an internal node of the communication network for which there is only one outgoing link to the end node (B, C), - zentral eine Verbindung des inneren Knoten zu einem weite¬ ren Knoten bestimmt wird, welche im regulären Betrieb vom in- neren Knoten nicht als alternativer Link im Sinne von Mehrwe¬ gerouting verwendet wird,a connection of the inner node to a further node is determined centrally, which in regular operation is not used by the inner node as an alternative link in the sense of multiple routing; - die Verbindung zentral für den Fall eines Ausfalls des von dem inneren Knoten abgehenden Links als von dem inneren Kno¬ ten abgehender Link für das Routing von Paketen zu dem End- knoten (B,C) bestimmt wird (Joker-Link),the connection is determined centrally in the event of a failure of the outgoing link from the inner node as a link originating from the inner node for the routing of packets to the end node (B, C) (Joker link), - der Joker-Link dem Knoten kommuniziert wird und bei dem Aufbau der Routingtabelle berücksichtigt wird.- The joker link is communicated to the node and taken into account in the structure of the routing table. 8. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass8. The method according to any one of the preceding claims, characterized in that - das Routingprotokoll" durch das OSPF (open shortest path first) oder das IS-IS (intermediate System to intermediate System) gegeben ist.- the routing protocol "is given by the OSPF (Open Shortest Path First) or the IS-IS (Intermediate System to Intermediate System). 9. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass - das Verfahren für eine Vielzahl von Knoten des Kommunikati¬ onsnetzes durchgeführt wird.9. The method according to any one of the preceding claims, characterized in that - The method for a plurality of nodes of the kommunikati¬ onsnetzes is performed. 10. Verfahren nach einem der vorhergehenden Ansprüche, dadurch gekennzeichnet, dass10. The method according to any one of the preceding claims, characterized in that - das die zentrale Berechnung bzw. Bestimmung durch eine de- dizierte Vorrichtung (NCS) erfolgt.- The central calculation or determination by a de- scribed device (NCS) takes place. 11. Vorrichtung zur Berechnung einer Routingtabelle (FIB) für ein Routing innerhalb eines mit Knoten (A, ..,G) und Links ge¬ bildeten Kommunikationsnetzes, welche11. Device for calculating a routing table (FIB) for routing within a ge with nodes (A, .., G) and links formed communication network, which - eine zentrale Vorrichtung (NCS) mit Mitteln zur Berechnung von Routen zwischen jeweils einem netzinternen Anfangs- und Endknoten umfasst, - einen Knoten (D) mit Mitteln zum Aufbau einer Routingtabel¬ le (FIB) mittels eines Routingprotokolls umfasst, unda central device (NCS) comprising means for calculating routes between in each case an in-net start and end node, a node (D) having means for establishing a routing tabel (FIB) by means of a routing protocol, and - Mittel zur Kommunikation zwischen der zentralen Vorrichtung (NCS) und dem Knoten (D) umfasst.- Means for communication between the central device (NCS) and the node (D) comprises. 12. Vorrichtung nach Anspruch 11, dadurch gekennzeichnet, dass12. The device according to claim 11, characterized in that - die Mittel zur Kommunikation zwischen der zentralen Vor¬ richtung (NCS) und dem Knoten (D) durch ein Kommunikations¬ protokoll gegeben sind.- The means for communication between the central Vor¬ direction (NCS) and the node (D) are given by a Kommunikations¬ protocol. 13. Vorrichtung nach Anspruch 11 oder 12, dadurch gekennzeichnet, dass13. Device according to claim 11 or 12, characterized in that - es sich bei dem Routing um eine Mehrwegerouting handelt und die zentrale Vorrichtung (NCS) Mittel zur Bestimmung von Ver- teilungsgewichten umfasst.- The routing is a Mehrwegerouting and the central device (NCS) comprises means for determining distribution weights. 14. Vorrichtung nach einem der Ansprüche 11 bis 13, dadurch gekennzeichnet, dass14. Device according to one of claims 11 to 13, characterized in that - durch das Kommunikationsprotokoll Routen oder Verteilungs- gewichte von der zentralen Vorrichtung (NCS) an den Knotenby the communication protocol, routes or distribution weights from the central device (NCS) to the node (D) kommunizierbar sind. (D) are communicable.
EP05754546A 2004-06-30 2005-06-28 Efficient calculation of routing tables for a routing operation using target addresses Withdrawn EP1762060A1 (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE102004031717A DE102004031717A1 (en) 2004-06-30 2004-06-30 Efficient calculation of routing tables for routing based on destination addresses
PCT/EP2005/053017 WO2006003141A1 (en) 2004-06-30 2005-06-28 Efficient calculation of routing tables for a routing operation using target addresses

Publications (1)

Publication Number Publication Date
EP1762060A1 true EP1762060A1 (en) 2007-03-14

Family

ID=34971473

Family Applications (1)

Application Number Title Priority Date Filing Date
EP05754546A Withdrawn EP1762060A1 (en) 2004-06-30 2005-06-28 Efficient calculation of routing tables for a routing operation using target addresses

Country Status (5)

Country Link
US (1) US20100329154A1 (en)
EP (1) EP1762060A1 (en)
CN (1) CN1998196A (en)
DE (1) DE102004031717A1 (en)
WO (1) WO2006003141A1 (en)

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8811158B1 (en) * 2012-02-29 2014-08-19 Juniper Networks, Inc. Fast reroute for common network routes
US9479437B1 (en) * 2013-12-20 2016-10-25 Google Inc. Efficient updates of weighted cost multipath (WCMP) groups
GB201706475D0 (en) 2017-04-24 2017-06-07 Microsoft Technology Licensing Llc Communications network node
US10411990B2 (en) * 2017-12-18 2019-09-10 At&T Intellectual Property I, L.P. Routing stability in hybrid software-defined networking networks

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6041049A (en) * 1997-05-06 2000-03-21 International Business Machines Corporation Method and apparatus for determining a routing table for each node in a distributed nodal system
JP3623680B2 (en) * 1999-01-11 2005-02-23 株式会社日立製作所 Network system having path verification function, path management apparatus, and exchange
US6363319B1 (en) * 1999-08-31 2002-03-26 Nortel Networks Limited Constraint-based route selection using biased cost
GB2371944B (en) * 1999-09-06 2003-10-29 Ericsson Telefon Ab L M System and method for internodal information routing within a communications network
CA2310872A1 (en) * 1999-12-22 2001-06-22 Nortel Networks Corporation Automatic protection switching using link-level redundancy supporting multi-protocol label switching
EP1133112B1 (en) * 2000-03-10 2005-02-09 Siemens Aktiengesellschaft Method for balancing the data transfer load of a communication network and corresponding communication network
JP3479834B2 (en) * 2000-09-04 2003-12-15 日本電気株式会社 Wireless access network routing control system and method
WO2002046947A1 (en) * 2000-12-04 2002-06-13 Rensselaer Polytechnic Institute System for proactive management of network routing
US7111074B2 (en) * 2001-07-24 2006-09-19 Pluris, Inc. Control method for data path load-balancing on a data packet network
US20040006640A1 (en) * 2002-07-03 2004-01-08 Inderieden Daniel W. Notification to routing protocols of changes to routing information base
JP2004129156A (en) * 2002-10-07 2004-04-22 Ntt Docomo Inc Route control system, route control device, transfer device, and route control method

Non-Patent Citations (1)

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

Also Published As

Publication number Publication date
WO2006003141A1 (en) 2006-01-12
US20100329154A1 (en) 2010-12-30
CN1998196A (en) 2007-07-11
DE102004031717A1 (en) 2006-01-26

Similar Documents

Publication Publication Date Title
DE60022602T2 (en) Method, device and computer program for keeping topology data of a link state routing network up to date
DE112005002142B4 (en) A system and method for associating different types of nodes with access point nodes in a wireless network for routing data in the wireless network
DE69727930T2 (en) SUMMARY OF CONNECTIONS IN COMMUNICATION COMMUNICATION NETWORKS
DE60035969T2 (en) Method and arrangement for handling the information packets by user-selectable relay nodes
DE60026238T2 (en) Dial-up based on pre-specified quality of service through a communication network
DE60312355T2 (en) DYNAMIC PEER TUNNELING WITH PERFORMANCE OPTIMIZATION
DE102011112852B4 (en) Access network Doppelwegkonnektivität
DE60028018T2 (en) Methods and arrangements in a telecommunication system
EP1623541B1 (en) Method and network node for self-regulating, autonomous, and decentralized traffic distribution in a multipath network
DE602005002382T2 (en) Distributed dynamic routing
DE202013012482U1 (en) Identify an exit point to a network location
DE102020120554A1 (en) Group-based policy multicast forwarding
EP3577871B1 (en) Method and device for the modular orientation of an avb stream
WO2008125516A1 (en) Method for determining a path distance value and network nodes
EP1532780B1 (en) Efficient intra-domain routing in packet-switched networks
WO2005013564A1 (en) Inter-domain multipath routing method
WO2006003141A1 (en) Efficient calculation of routing tables for a routing operation using target addresses
DE202019006196U1 (en) Scope abstraction extensions for redirection protocols
EP1588531A1 (en) Method for adapting link-weights in relation to optimised traffic distribution
DE602005000724T2 (en) Route guidance in a communication network
EP1992127B1 (en) Communication system, computer, and method for determining a communication protocol to be used in a communication system
EP1597872B1 (en) Method and network node for determining multi-path transmission paths in a packet-switched communication network
EP1894363B1 (en) Method and independent communications subnet for determining label-switched routes in a communications subnet of this type
DE10047131B4 (en) Method for operating an access network
DE10328620B4 (en) Method and network node for routing in a packet-switched communication network

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

17P Request for examination filed

Effective date: 20061207

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IS IT LI LT LU MC NL PL PT RO SE SI SK TR

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: FRAUNHOFER-GESELLSCHAFT ZUR FOERDERUNG DER ANGEWAN

Owner name: NOKIA SIEMENS NETWORKS GMBH & CO. KG

DAX Request for extension of the european patent (deleted)
RAP3 Party data changed (applicant data changed or rights of an application transferred)

Owner name: NOKIA SIEMENS NETWORKS S.P.A.

Owner name: FRAUNHOFER-GESELLSCHAFT ZUR FOERDERUNG DER ANGEWAN

RAP3 Party data changed (applicant data changed or rights of an application transferred)

Owner name: FRAUNHOFER-GESELLSCHAFT ZUR FOERDERUNG DER ANGEWAN

Owner name: NOKIA SIEMENS NETWORKS GMBH & CO. KG

17Q First examination report despatched

Effective date: 20080717

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