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]