JP2015057879A - Packet multipath routing device and method for using thereof in computer networking - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a packet multipath routing device and a method for a computer network.SOLUTION: A device (router) maintains a flow forwarding table (FFT) accommodating an identifier of an active flow and an originating interface identifier of a related router. When a first packet representing a new flow reaches the router, the originating interface identifier is selected using the existing method using a routing table. Next, the packet is led to an originating interface according to the FFT. The routing table is used to form relationship between the flow identifier in the FFT and the originating interface.

Description

  The present invention introduces a multipath routing device for packets in a multipath IP (Internet Protocol) network and a method of using the same. The proposed solution can intelligently determine the transmission path for traffic taking into account the current link throughput level. In this way, resources can be allocated in a more effective manner.

Conventional technology

  The main element of the device proposed by the present invention is a router. The router sets up a path to the destination node for the IP packet and forwards the packet to the proper outgoing interface. In currently used routers, a routing table is used to determine the outgoing interface for the delivered packet. This table contains information stored in the router's memory, such as a list of nodes, through which the destination network can be viewed.

  The routing table contains entries that allow packets that reach the router to be forwarded to each destination network or subnetwork. The routing table is set up and maintained in the router's physical memory. A typical entry in the routing table contains the destination subnetwork address, metric, and outgoing interface identifier or address, which makes the subnetwork available. In most cases there is only one interface per destination subnet in the routing table, ie the most preferred interface.

  It is undesirable for computer network congestion to occur. Congestion is observed when more information has to be processed than can be sent. Load balancing is one way to relieve congestion, and its main goal is to send traffic through various paths to the destination node.

  Load balancing allows maintaining various interfaces in the routing table with the same or different metrics for the same destination subnetwork. Based on the current load, traffic is sent to each of the available outgoing interfaces according to the assigned weight. In other words, the router sends the packet to the destination network via a different outgoing interface. Using load balancing, packets of one flow may come to the destination node through different paths and in different orders. Furthermore, this can lead to inefficiencies in the load on the network. Some elements may be congested and others may not.

  When groups of packets are sent between the same nodes and have the same value for the selected field in the packet header, these may be considered “flows”. These fields are typically source and destination addresses, port numbers (source and destination), and transport layer protocol (open system interconnect, according to OSI / ISO model) identifiers.

  Currently, multipath transmission is possible under the MPLS (Multiprotocol Label Switching) protocol. The MPLS standard is defined in RFC3031. Routers using the MPLS protocol send packets based on labels placed between layer 2 and layer 3 headers. In short, a router using the MPLS protocol constitutes an MPLS domain. Packets that reach an MPLS domain border router, known as a provider edge router (PE router), are given an MPLS label and are sent to the appropriate outgoing interface. Within the MPLS domain, the router uses only MPLS labels for packet forwarding. Such a router is known as a provider router (P router). Each router on the packet path has its own label switching table. Outgoing packets at the border of the MPLS domain are stripped of their MPLS label by the PE router or by a router outside the MPLS domain in front of the PE router, and the packet is served according to IP routing rules. The The use of MPLS labels allows the creation of un-equivalent paths and the subsequent sending of packets through different paths.

  The label switching rules at the router must be set before the packet is sent. This is because a special protocol is used for label distribution in the network. The path through which the packet is sent also needs to be set in advance. It is possible to distribute labels in such a way that the assigned path is different from the path estimated from the routing table, which becomes an element of traffic design. Usually, the path different from the path set in the routing table is statistically set by a human operator, and in most cases, the resource reservation protocol described in RFC 3209 (updated and extended in RFC5151). -Follow traffic design (RSVP-TE). MPLS does not allow dynamic path creation and removal based on the current traffic load of the network and is permanently set by the operator. Also, MPLS does not consider finding an alternative optimal path in the operator's network. However, the router proposed in the present invention can find an alternative optimal path.

  A method by which a router selects a route to a destination node is introduced in US Pat. No. 61147, published in 2012, which takes into account metrics such as throughput, delay, and jitter. In this patent, various paths are established between two nodes, written to the routing table and periodically updated. As a result, the most effective path can be selected at any given time.

  An equivalent method for multipath packet routing in IP networks was introduced in US Patent No. CN2011124418. Here, the central control system that holds information about the entire network determines which path should be selected. In this way, an optimal path can be selected based on the actual network state. Its main advantages are minimizing delay, increasing the amount of traffic transmitted over the network, and suppressing jitter. However, the centralized control system may cause a lack of scalability.

  A method for multipath transmission of packets grouped together is described in US Patent No. WO2006EP65975. Aggregates are selected based on a traffic matrix and are sent through a path selected by a central point in the network, with the goal of increasing the total traffic transmitted. Again, one of the drawbacks is a central controller that offers a focal point for faults.

  A method for directing packets in a mobile network was proposed in US Pat. No. 7,242,678 published in 2007. This patent, sometimes referred to as “Edge Mobility Architecture (EMA)”, has demonstrated “Mobile Improved Routing (MER)” for packets forwarded in a mobile network. Signaling overhead resulting from changing the IP address of the mobile device is reduced. This is enabled by creating a unicast package to update the status of the mobile device between the old and new access routers.

  A packet routing method in an IP network using multiple protocols in one domain was introduced in US Pat. No. 7,177,646 and published in 2007. The present invention introduces a method for using various types of routing updates in one domain.

  A balanced routing method for IP packets based on the collection and analysis of traffic characteristics on selected transmission paths was introduced in US Pat. No. 7,136,357. The collected information is then distributed to other routers in the network, which then determine whether or not to add paths to their routing tables. If there are several paths between the same nodes in the routing table, traffic is evenly distributed between them (each path has the same weight).

  A data stream routing method and system in a network with multiple topologies was proposed in US Pat. No. 8,320,277. In this proposed solution, resources are allocated proportionally according to the weight for the data stream. In addition, the link metrics for a particular topology are also considered. A separate routing table is maintained for each topology.

  A method for intelligent routing of packets in a flow-aware network is disclosed in Polish patent application P.A. Proposed in No. 398761. This describes how to send a packet to the selected outgoing interface based on the contents of the protection flow list. When the first packet of the flow reaches the router, the outgoing interface identifier is written to the protected flow list. An outgoing interface is then selected based on the routing table.

  The EIGRP protocol is described in detail in a Cisco document called “Enhanced Interior Gateway Routing Protocol”, ID = 16406, in which various parameters are used to determine the link cost. Most important is link bandwidth and delay. The current load on the link can also be observed. However, in such cases, the cost of the link can change frequently, so that the routing table is updated more frequently. It is also undesirable to allow an increase in the number of loops created in the network. However, the present invention is based on a mechanism that protects the network from loops.

  The table of flow information also provides instructions on how to handle these, and is implemented in the OpenFlow switch (a 1.4 version of the documentation for this switch is available at www.opennetworking.org). It was. The devices introduced in this document use a similar table, but operate in different ways. In an OpenFlow switch, flow instructions are generated by a central controller, which is responsible for managing all devices in the network. The devices introduced herein operate independently and create their own new registrations in the flow table. Thus, the present invention operates similarly to the OpenFlow switch, but does not require a central controller. As a result, decentralized control is possible, costs are reduced, less network resources are consumed, single failure points are not featured, and are reasonably scalable .

  An object of the present invention is to add a flow forwarding table (FFT) to the router, so that the router handles and steers packets based on the contents of the FFT. The content of the FFT itself is updated based on the routing table.

  The invention introduced herein uses a new routing method designed for IP networks, FAMTAR (Flow-Aware Multi-Topology Adaptive Routing). Incoming packets representing the flow are analyzed by the router. These are then transferred to the outgoing interface according to a flow transfer table (FFT). The flow forwarding table is a new element unique to the invention to be submitted. If there is no entry corresponding to the flow represented by the incoming packet, the router adds the ID of that flow to the FFT, but the outgoing interface for this flow is taken from the current routing table.

  FAMTAR uses the currently popular notion of identifying network traffic by flow concept. The term “flow” is already known from the literature, but this is rather ambiguously interpreted. However, this is always a stream of information belonging to one connection between two end users or two applications. The flow ID can be determined according to one of the established methods without affecting the present invention.

  For example, in a flow aware networking (FAN) architecture, a “flow” is defined as a flight of packets that are time and space identifiable and have the same unique identifier. The identifier is calculated as a hash of five header fields: IP address, transport layer port number, and the ID of the transport layer protocol used (eg, TCP or UDP).

  The novelty of the present invention resides in the method used to control the flow in the network. For each packet, the outgoing interface is elected from the FFT (not from the routing table) and as soon as a new flow packet appears, an FFT entry is added and remains unchanged even if the routing table changes.

  A router is a network device that operates in the third layer of the OSI model and is used to connect computer networks. This acts as a switching node.

FIG. 1 is a layout of a FAMTER router. FIG. 2 shows the structure of a flow transfer table (FFT). FIG. 3 is a block diagram of the output interface selector.

  The invention to be submitted is shown in FIG. This also represents a usage example.

  The router is composed of an input interface, an output interface selector, a switching matrix, a routing table, a CPU, and an output interface. Each incoming packet is analyzed. The output interface selector determines the proper output interface based on information from the routing table and passes this information to the switching matrix. The switching matrix is responsible for physically forwarding the packet to the proper outgoing interface. The operation of the outgoing port selector and switching matrix is controlled by the CPU.

  One element of each router is its routing table, which contains information about the interface to which each packet should be forwarded based on the destination IP address found in the packet header. Therefore, the routing table is referenced for each incoming packet. When a change occurs in the network (eg, after a failure, after a new network, link, device, routing policy change, etc.), the routing tables of all routers in the network are updated. Updating the routing table affects all packets that arrive after this update.

  A new element in the router architecture proposed in the present invention and shown in FIG. 1 is the aforementioned flow forwarding table (FFT). The FFT contains the identifier of the outgoing interface to which packets belonging to a given flow are forwarded and is referenced by the outgoing port selector. Based on the flow identifier, an outgoing interface identifier is obtained. If the FFT contains information about the flow, the routing table is not referenced by the outgoing interface selector. This is a significant novelty over the current state of the art. This is because current routers refer to the routing table for each packet. In the present invention, if a flow does not exist in the FFT, a new entry is created in the FFT and the outgoing interface is picked from the current routing table.

  Unlike the routing table, the FFT is static. Once created, the entry does not change, with one exception being time stamps. The time stamp is the time when the last packet of the flow appears and is updated for each packet. Based on the time stamp, it is possible to determine the elapsed time from the appearance of the last packet of each flow.

  In the present invention, when congestion occurs on the link, the link cost increases in the routing protocol and takes a maximum cost value or a special value indicating the congestion. As a result, the applied routing protocol propagates the cost change information and recalculates the route using the new cost. Although the routing table at the router can change, in the present invention, the FFT remains unchanged. This means that only new flows with identifiers that are not present in the FFT during the update are affected by the routing table change. Active flows that exist on the FFT list during the update are not affected by the change. Because of this behavior, during the time of congestion, new flows are directed along the alternative path, while all existing traffic travels through the existing path without modification.

  FIG. 2 shows the structure of the FFT. The FFT is stored in the physical memory of the router and includes at least the following fields.

-Flow identifier-Router outgoing interface identifier. Packets belonging to each flow are sent through this interface.

  An entry in a table that allows an indication of the exact time interval between the arrival of the last delivered packet belonging to a flow and the arrival packet belonging to this flow. If no new packet belonging to this flow appears for a predetermined time period t, the FFT entry is removed. If a packet belonging to the removed flow appears after the time t has elapsed, it is treated as a new flow.

The operating scheme for the outgoing interface selector used by the router is shown in FIG. A flow identifier is determined based on each field of the IP packet header. Next, it is determined whether or not this identifier exists in the FFT ( A ). If the flow identifier is present in the FFT, it reads the outgoing interface number at the router ( B ) and directs the packet to it. Next, the “last packet arrival time” value is updated (E) (can be represented by the current time). The router's switching matrix is used to send the packet to the interface indicated by the FFT (F). If no flow is found in the FFT, then read each outgoing interface from the router's routing table (C). The identifier of this flow is added to the FFT together with the number of the outgoing interface to which the packet belonging to this flow is to be directed (D). The rest of this procedure is the same as before. That is, the “last packet arrival time” value is updated (E) (the current time may be registered), and the packet is sent to the interface indicated by the FFT using the router switching matrix (F).

  The essence of the proposed invention is that for network operation and information transfer in the network, place the entry first in the FFT and then send the packet to the outgoing interface, or first send the packet to the outgoing interface and then the relevant entry in the FFT The fact is that it doesn't matter if you write to.

  The order of information transfer and the placement of entries in the FFT is generally irrelevant, but it is better to send the packet first and then add the entry to the FFT, which minimizes the packet transfer delay.

  In the IPv4 protocol, the time to live (TTL) field contains a numerical value of the maximum number of hops that a packet can take in its path. Subsequent routers along this path decrement the value of the TTL field of each preceding packet by one. If the router gets a packet with a TTL equal to 0, this packet is dropped and removed from the network. This procedure helps to avoid congestion when the routing path includes routers that have failed to configure, or when other failures occur. In IPv6, the field called hop limit plays the same role.

  When adding a new flow to the FFT, it is beneficial to store the TTL value from the IPv4 packet header or the hop limit from the IPv6 packet header (depending on which protocol is used). Next, for each incoming packet, the router checks whether the TTL (or hop limit) in the packet header matches the value stored in the FFT for the corresponding flow. If both values are the same, the packet is transferred according to the procedure introduced earlier. If the values do not match, the flow represented by the packet is erased from the FFT and the packet processing procedure is resumed. Thus, after observing a TTL (or hop limit) mismatch, the path for a given flow may be changed. This is because the record of this flow is erased from the FFT (with the recorded packet forwarding interface) and then recreated, but the outgoing interface is picked from the current routing table.

  This represents another advantage of FAMTAR. This is because it eliminates the appearance of loops. Since the routing protocol takes some time to update the respective routing table at the time of failure or after any link cost changes, the loop in FAMTER is more than in a standard network. May also appear frequently. Flows that appear in the network before the change occurs are tied to the correct interface, and these interfaces are never changed without checking the TTL (or hop limit) field. In this way, loops can occur that cannot be resolved with simple changes in the routing table.

Claims (12)

A dedicated router,
A dedicated router, wherein the router comprises physical memory for FFT storage, and the FFT itself stores the flow identifier and the router interface through which outbound traffic is sent.   The router of claim 1, wherein the memory that functions in a particular way and stores the FFT is accessed each time a packet enters the router, and the memory records the outgoing interface of the packet. The router used.   The router of claim 1, characterized by the fact that if the FFT does not include an entry for the analyzed packet, the entry for it is determined from an existing routing table at the router.   2. The router according to claim 1, further comprising: a memory storing the FFT including at least two dedicated fields for the flow identifier and the outbound interface identifier for a package belonging to the flow. .   5. The router of claim 4, further characterized in that the FFT includes an additional field that enables time interval identification, the time interval being an elapsed time since arrival of the last package in a given flow. Represents a router.   A flow control method, comprising selecting a router port for a given outgoing packet using information stored in an FFT.   The router of claim 1, further comprising: the FFT includes an additional field for a value of a TTL field from an IPv4 protocol packet header or a hop limit field from an IPv6 protocol packet header. And router.   7. The flow control method according to claim 6, wherein the TTL field value from the IPv4 protocol packet header (or the hop limit field value from the IPv6 protocol packet header) is sent to the FFT for the corresponding flow. The flow control method, wherein the flow is removed from the FFT if it does not match the stored value.   The router of claim 1, wherein if the router analyzes the traffic characteristics (eg, load) of its outgoing link and exceeds a specified threshold, the router determines the cost in the routing protocol for each interface: A router, characterized in that it increases to a specified value and distributes the information to all other routers in the network, thus prompting a routing table change in subsequent routers.   The router according to claim 1, wherein the change of the routing table does not affect the path of the outgoing flow.   2. The router of claim 1, wherein the routing table change caused by a change in traffic characteristics affecting link cost does not change the path of the outgoing flow.   7. The flow control method in a network according to claim 6, wherein a change in a routing table caused by a change in traffic characteristics affecting link cost does not change a path of an outgoing flow.

Images