A Simplified Flooding Phase Scheme Based on OSPF Routing Protocol
draft-wu-lsr-simplified-00
Document | Type | Active Internet-Draft (individual) | |
---|---|---|---|
Authors | Mingzhen Wu , Ying Zhou , Liang Wang , Yuyin Ma | ||
Last updated | 2024-03-19 | ||
RFC stream | (None) | ||
Intended RFC status | (None) | ||
Formats | |||
Stream | Stream state | (No stream defined) | |
Consensus boilerplate | Unknown | ||
RFC Editor Note | (None) | ||
IESG | IESG state | I-D Exists | |
Telechat date | (None) | ||
Responsible AD | (None) | ||
Send notices to | (None) |
draft-wu-lsr-simplified-00
LSR Mingzhen Wu
Internet Draft Ying Zhou
Intended status: Informational Liang Wang
Expires: July 10, 2024 Yuyin Ma
Beijing Jiaotong University
March 20, 2024
A Simplified Flooding Phase Scheme Based on OSPF Routing Protocol
draft-wu-lsr-simplified-00
Abstract
This distributed routing protocol aims to facilitate information
exchange and path calculation between routers to ensure efficient
data transmission in the network. Each router initializes adjacency
matrices, neighbor tables, routing tables, and flood flags during
setup. In operation, routers periodically broadcast Hello packets to
update neighbor tables and detect changes in neighbor relationships,
broadcasting update packets accordingly. Nodes receiving update
packets process them based on flood flags, optimizing network
performance through scheduled flood flag resets, controlling link
occupancy rates, and utilizing Dijkstra's algorithm to compute
shortest paths when adjacency matrices are complete, storing results
in routing tables for optimal path selection.
Status of this Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six
months and may be updated, replaced, or obsoleted by other
documents at any time. It is inappropriate to use Internet-Drafts
as reference material or to cite them other than as
"work in progress."
This Internet-Draft will expire on July 10, 2024.
Wu, et al. Expires July 10, 2024 [Page 1]
Internet-Draft Simplified Routing Protocol March 2024
Copyright Notice
Copyright (c) 2024 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction
2. Preparation Stage
3. Actual Operational Process
3.1. Periodic Broadcast of Hello Packets
3.2. Handling Hello Packets
3.3. Broadcasting Update Packets
3.4. Receiving Update Packets
3.5. Flood Processing Stage
4. Optimization Measures
4.1. Periodic Flood Flag Resets
4.2. Dijkstra's Algorithm for Shortest Paths
4.3. Effective Link Occupancy Management
4.4. Shortest Path Computation Using Dijkstra's Algorithm
5. Unresolved Issues
6. Security Considerations
7. References
8. Acknowledgments
Wu, et al. Expires July 10, 2024 [Page 2]
Internet-Draft Simplified Routing Protocol March 2024
1. Introduction
The distributed routing protocol is designed to facilitate
information exchange and path calculation among routers in a
network, ensuring the efficient transmission of data. Each router
initializes adjacency matrices, neighbor tables, routing tables, and
flood flags during the setup phase. During operation, routers
periodically broadcast Hello packets and process received Hello and
acknowledgment packets to update neighbor tables. When all data in
the neighbor table is not -1, routers assess if there are any
changes in neighbor relationships; if changes occur, update packets
are broadcasted. Upon receiving update packets, other nodes process
them based on flood flags and sequence numbers, executing flood
operations to update local information.
To optimize network performance, the protocol implements timed flood
flag resets and flood operations to control link utilization rates.
Additionally, when the adjacency matrix is complete, it utilizes
Dijkstra's algorithm to compute the shortest paths and stores the
results in the routing table to achieve optimal path selection in
the network. Through these optimization measures, the protocol
effectively enhances network efficiency and performance.
2. Preparation Stage
Each router possesses the following information:
An n*n adjacency matrix representing the network topology.
A 1*n neighbor table (-1 indicates the initial state, 1 indicates a
connection, INT_MAX indicates no connection).
A routing table (containing the address and ID of all routers, the
next hop information to reach destinations, and the sequence number
for receiving information from each router).
A flood flag (1 indicates that at least one update packet has been
received, 0 indicates that the corresponding update packet has not
been received yet).
3. Struct Definitions
3.1. Transmission Phase
Hello Packet Structure:
⚫ Self ID
⚫ Self Address
Wu, et al. Expires July 10, 2024 [Page 3]
Internet-Draft Simplified Routing Protocol March 2024
⚫ Flag set to 0
Ack Packet Structure:
⚫ Self ID
⚫ Self Address
⚫ Flag set to 1
Link State Update Packet Structure:
⚫ Self ID
⚫ Self Address
⚫ Flag set to 2
⚫ Packet Sequence Number
⚫ Self Neighbor State
3.2. Reception Phase
Unified structure for simplifying processing in the reception phase,
incorporating the following parameters:
⚫ ID
⚫ Address
⚫ Flag
⚫ Data
This approach streamlines the reception phase by eliminating the
need for a separate identification stage for each structure.
4. Actual Operational Process
4.1. Periodic Broadcast of Hello Packets
Each router broadcasts Hello packets at regular intervals.
After a fixed interval, nodes that have not yet received
acknowledgment packets have their corresponding neighbor table
entries set to INT_MAX.
Wu, et al. Expires July 10, 2024 [Page 4]
Internet-Draft Simplified Routing Protocol March 2024
4.2. Handling Hello Packets
Upon receiving a Hello packet, an acknowledgment packet is formed
and sent back along the original path.
Upon receiving an acknowledgment packet, the corresponding entry in
the neighbor table is set to 1.
4.3. Broadcasting Update Packets
When all data in the neighbor table is not -1, compare the neighbor
table with the previous neighbor relationship.
If they are inconsistent, increment the sequence number and compose
and broadcast an update packet.
4.4. Receiving Update Packets
Upon receiving an update packet, other nodes first check if the
flood flag is 0. If it is, they enter the flood processing stage.
If it is 1, they continue to check if the sequence number is the
latest. If already received, they ignore it; if it is the latest,
they enter the flood processing stage.
4.5. Flood Processing Stage
Add the neighbor relationship to their own adjacency matrix at the
corresponding position, update the sequence number, and then forward
the update packet.
5. Optimization Measures
5.1. Periodic Flood Flag Resets
Implement periodic resets of the flood flag to enable timed flooding
and efficient control of link occupancy.
5.2. Dijkstra's Algorithm for Shortest Paths
When the detection indicates that the adjacency matrix is complete,
execute Dijkstra's algorithm. Determine the next hop for the
shortest path from this node to other nodes and store the
information in the routing table. This step guarantees the
calculation of optimal paths within the network.
Wu, et al. Expires July 10, 2024 [Page 5]
Internet-Draft Simplified Routing Protocol March 2024
5.3. Effective Link Occupancy Management
By periodically resetting the flood flag, this method ensures timed
flooding, effectively controlling link occupancy and optimizing
network performance.
5.4. Shortest Path Computation Using Dijkstra's Algorithm
Each node is empowered to compute the shortest paths to other nodes
through the implementation of Dijkstra's algorithm. This contributes
to the overall efficiency of the network while maintaining an
appropriate level of flooding.
6. Unresolved Issues
The plan does not address considerations for network security. In
practical applications, it is essential to take into account the
security of the network, including aspects such as authentication,
data encryption, and protection against network attacks.
Furthermore, improper flood frequency settings or changes in network
topology may still result in network congestion or instability..
7. Security Considerations
This document does not contain any security considerations.
8. References
Flooding Topology Minimum Degree Algorithm [draft-ietf-lsr-flooding-
topo-min-degree-08].
IS-IS Fast Flooding [draft-ietf-lsr-isis-fast-flooding-06]
Applicability of IS-IS Multi-Topology (MT) for Segment Routing based
Network Resource Partition (NRP) [draft-ietf-lsr-isis-sr-vtn-mt-07
]
9. Acknowledgments
Many thanks to all who discussed this with us in DINRG in 2023 and
2024.
This document was prepared using 2-Word-v2.0.template.dot.
Wu, et al. Expires July 10, 2024 [Page 6]
Internet-Draft Simplified Routing Protocol March 2024
Authors’ Addresses
Mingzhen Wu
Beijing Jiaotong University (BJTU)
Beijing, 100044, P.R.China
Email: 23125063@bjtu.edu.cn
Ying Zhou
Beijing Jiaotong University (BJTU)
Beijing, 100044, P.R.China
Email: 22110019@bjtu.edu.cn
Liang Wang
Beijing Jiaotong University (BJTU)
Beijing, 100044, P.R.China
Email: wangliang1@bjtu.edu.cn
Yuyin Ma
Beijing Jiaotong University (BJTU)
Beijing, 100044, P.R.China
Email: mayuyin@bjtu.edu.cn
Wu, et al. Expires July 10, 2024 [Page 7]