CN103023781B - Shortest path tree and spanning tree combined energy-saving routing method - Google Patents

Abstract

The routing method combining the shortest path tree and the spanning tree belongs to the technical field in the network topology, and is characterized in that, on the basis of the standard link state routing protocol, each link connected to the router node in the network increases the dormant state, giving Select a shared spanning tree on a given network topology, and the links on it are always in the working state to ensure network connectivity. The shortest path routing table of the network path and the routing table corresponding to the spanning tree. For a data packet, the ingress router determines that the data packet adopts one of the paths according to the current link load, and adds a label identifier. The non-ingress router selects the corresponding routing table according to the label. to retweet.

Description

Energy-saving Routing Method Combining Shortest Path Tree and Spanning Tree

technical field

green network

Background technique

Green network is an important direction of today's network research, and the problem of huge energy consumption and inefficient energy use of the Internet has become increasingly prominent. In order to use energy more effectively and reduce energy waste, the research on using the link dormancy mechanism to realize network energy saving is attracting more and more attention from academia and industry. In general Internet Service Provider (ISP) networks, in order to cope with traffic peaks and potential link failures, network operators usually deploy redundant links and increase the bandwidth of redundant links during the network construction and upgrade period. Most of the time in the network, the network load is not high, resulting in low average link utilization, and the power consumption of the router is not reduced compared with the full-load operation state. These factors will cause energy waste in the network.

The link state routing protocol is a commonly used intra-domain routing protocol. The path calculated by the router of this protocol is the shortest path. Since the protocol design did not consider factors such as energy consumption at the beginning, the utilization rate of the link on the ISP network is low. , a large amount of energy wasted. The purpose of the present invention is to improve the traditional standard link state routing, and adopt the energy-saving mechanism combining the spanning tree (ST: spanning tree) and the shortest path tree (SPT: shortest path tree) to aggregate traffic to as few links as possible, The rest of the links enter the idle dormant state to achieve energy saving.

Contents of the invention

The purpose of the present invention is to use two different shortest paths and spanning tree paths to construct a new energy-saving road state routing method, gather traffic on the spanning tree, make more links enter the dormant state, and realize the purpose of energy saving. Improve average link utilization and reduce energy waste.

The present invention is characterized in that:

1. On the network topology, follow the steps below:

Step (1), network topology initialization: on the basis of the standard link state routing protocol, increase the sleep state on each link connected to each router node;

Step (2), each router node periodically detects the load conditions of all direct links, and uses the link state notification mechanism LSA of the open shortest path first protocol OSPF to flood the link load information together with the link state information. Spread to the network topology, so that each router node on the network topology has exactly the same network topology information and link load information;

Step (3), each router node calculates the shortest path and spanning tree path from itself to any other router node on the network topology according to the result obtained from step (2), and generates a routing table, and the calculation results of all router nodes are consistent of;

Step (4), each router node on the network topology selects a suitable path for each data flow according to the destination address according to the link load on the path that the data flow passes through, selects the corresponding routing table, and selects the selected The result is added to the head of the data packet as a label, and then forwarded according to "destination address + label", and the next hop of the route is determined in the routing table according to the label;

Step (5), after the downstream router node receives the message with the label forwarded by the upstream router, select the next hop according to the label, and forward it in the format of "destination address+label";

Step (6): After receiving a message, the core router node checks the link at the forwarding end. If the forwarding segment is normal, it forwards it normally according to the label. If the link at the forwarding end is found to be in a dormant state, it needs to put The link wakes up, and then the label of the datagram is modified to the label of the spanning tree for forwarding until reaching the destination router.

2. The energy-saving routing method combining the shortest path tree and spanning tree according to claim 1, characterized in that, on the spanning tree, an online subgraph for actual use is constructed, and each router node on it is in the On a certain link of the above spanning tree, the minimum number of edges should also be included to prevent single link failure.

The idea of the method proposed by the present invention is: on the basis of the standard link state routing protocol, add a dormant state to each link connected to the router node. Create a connected subgraph on a given network topology. The links on the connected subgraph are always in the working state, and other nodes outside the connected subgraph will enter the dormant state if there is no traffic passing through for a period of time. The router constructs a spanning tree on the connected subgraph, and aggregates the traffic on the spanning tree, so that more dormant links can be used to save energy.

The advantage of the method proposed by the present invention is:

1. Using a distributed algorithm, each ingress router independently makes decisions based on the collected link load information;

2. It can quickly respond to network load changes in real time, and the traffic can be quickly switched between the shortest path tree and the spanning tree;

3. Achieve a good balance between network energy saving efficiency and network load elasticity.

Description of drawings

Figure 1. Global topology and spanning tree/connected subgraph,

Figure 1.1 Global Topology,

Figure 1.2 Spanning tree/connected subgraph (thick line).

figure 2. Schematic diagram of "destination address + label" forwarding.

image 3. Schematic diagram of label reset.

Figure 4. Routing protocol flow chart,

Figure 4.1 Path selection flow chart,

Figure 4.2 Data packet forwarding flow chart.

Detailed ways

As shown in Figure 1.1, an extreme case of the contradiction between energy-saving efficiency and network resilience is when all links are in working state. At this time, the network consumes the most energy, but it is also the most reliable and resilient, and can cope with sudden traffic spikes and chain links. road failure. Another extreme situation shown in Figure 1.2 is that all links on a connected subgraph containing all nodes are in working state, and other links are in dormant state. If the online subgraph is taken as a spanning tree, the energy-saving efficiency of the network is the highest at this time, but it is also the most vulnerable. A well-considered energy-saving routing protocol should not only consider energy-saving efficiency, but also fully consider network resilience and global network performance. Furthermore, because link-state switching is based on real-time traffic demands, our energy-efficient routing protocol needs to be able to make decisions quickly and maintain topology-wide consistency. The main idea of the energy-saving routing protocol we study is to achieve as smooth a switch as possible between the two extreme cases according to the actual traffic load of the network. When the traffic demand is low, try to use the links on the spanning tree to transmit traffic to maximize the energy saving rate; when the traffic demand increases, gradually move the traffic from the spanning tree to the global topology, and wake up the necessary links to maintain Network resilience and performance, until all traffic selects the shortest path, at this time the protocol automatically converges to OSPF. The energy-saving routing protocol we study focuses on making such switching as smooth as possible, minimizing packet loss rate and out-of-sequence, so as to minimize the impact of energy-saving on upper-layer protocol applications.

work process:

i) First, each router periodically detects the load of the direct link, and floods the link load information together with the link state information to the entire network, which can be realized by using the LSA flooding mechanism of OSPF itself.

ii) So far, each router in the topology has exactly the same network topology information and link load information. Through the topology information, the router can calculate the shortest path and spanning tree path from itself to any other node in the network. The same topology, unified algorithm, so all routers calculate path results are consistent, satisfying the optimal substructure characteristics.

iii) Then, each ingress router selects an appropriate path for each flow that takes it as an ingress according to the link load status on the path that the data flow passes through, and adds the selection result as a label to the header of the data packet, and then according to "Destination address + label" for forwarding, see Figure 2.

iv) When the downstream node receives the tagged message forwarded by the upstream, it forwards it directly according to the "destination address + label".

v) When the forwarding port link is in a dormant state, in order to ensure the continuity of the flow, the forwarding node will reset the label of the data packet to forward along the label and path of the spanning tree when the link is awakened. The label will not be reset after the road wakes up, see Figure 3.

In order to improve the reliability of the network topology, the actual online subgraph should increase the redundancy to a certain extent on the basis of the spanning tree. A feasible solution is to find such a subgraph so that each node is in a certain On the ring, while containing the least number of edges, such an online subgraph can effectively cope with the failure of a single link.

We conducted experiments on three real topologies, and found that the energy-saving mechanism combined with spanning tree and shortest path tree can save 20% to 50% of line card energy consumption when the link utilization rate is low, which shows that the present invention has reached expectations the goal of.

Claims (2)

1. The energy-saving routing method that shortest path tree and spanning tree combine, it is characterized in that, on network topology, realize by following steps successively: Step (1), network topology initialization: on the basis of the standard link state routing protocol, increase the sleep state on each link connected to each router node; Step (2), each router node periodically detects the load conditions of all direct links, and uses the link state notification mechanism LSA of the open shortest path first protocol OSPF to flood the link load information together with the link state information. Spread to the network topology, so that each router node on the network topology has exactly the same network topology information and link load information; Step (3), each router node calculates the shortest path and spanning tree path from itself to any other router node on the network topology according to the result obtained from step (2), and generates a routing table, and the calculation results of all router nodes are consistent of; Step (4), each router node on the network topology selects a suitable path for each data flow according to the destination address according to the link load on the path that the data flow passes through, selects the corresponding routing table, and selects the selected The result is added to the head of the data packet as a label, and then forwarded according to "destination address + label", and the next hop of the route is determined in the routing table according to the label; Step (5), after the downstream router node receives the message with the label forwarded by the upstream router, select the next hop according to the label, and forward it in the format of "destination address+label"; Step (6), after the core router node receives a message, check the link of the forwarding end, if the link of the forwarding end is normal, then forward it normally according to the label, if it is found that the link of the forwarding end is in a dormant state, it needs to put the The link wakes up, and then the label of the datagram is modified to the label of the spanning tree for forwarding until reaching the destination router. 2. The energy-saving routing method combining shortest path tree and spanning tree according to claim 1, characterized in that, on the spanning tree, construct an online subgraph for actual use, and each router node thereon is On a certain link of the spanning tree, a minimum number of edges should also be included to prevent single link failure.