DECnet DIGITAL Network Architecture Routing Layer Functional Specification Version 2.0.0 May 1983 .-------. `=======' .------. .---. .-------. | | .-------. `======' `===' `=======' | | `=======' \\ ..| |\ \\ \ | | / / \...| .-----. .-------------. ......| | \ \ \ .-------. .-------. o\.--------------. o `--/ /--' `---|\--' o `-----\\ \-----' o / / | \ o \\ \ o / / | \ O \\ \ O ------------. .----------------. .-----------------. /| | \ \ \ / | \ \ \ \ /.-----| \------.\ \ / `-----| \-----' \ \ --------. / .---------------------. \ .----------------------. / | | | \| \ \ | / /----' `---------------------' `--------\ \ \-------' / / \ \ \ / / \ \ \ / .------------------------ / |\ \ \ \ \ \ \ \ \ \ \ \ \ .---------------- \ | \ \| \ \ `---------\ \ Page 2 ABSTRACT This document specifies the functions, interfaces, and protocols for implementing that part of the DIGITAL Network Architecture that models the software controlling the routing of messages within DECnet communications networks. DIGITAL EQUIPMENT CORPORATION MAYNARD, MASSACHUSETTS 01754 Copyright (C) 1980, 1983 Digital Equipment Corporation, Maynard Massachusetts This material may be copied, in whole or in part, provided that the above copyright notice is included in each copy along with an acknowledgment that the copy describes the Routing Layer interfaces, algorithms and protocols developed by Digital Equipment Corporation. This material may be changed without notice by Digital Equipment Corporation, and Digital Equipment Corporation is not responsible for any errors which may appear herein. Page 3 1.0 INTRODUCTION . . . . . . . . . . . . . . . . . . . . 6 2.0 FUNCTIONAL DESCRIPTION . . . . . . . . . . . . . . . 8 2.1 Design Scope . . . . . . . . . . . . . . . . . . 10 2.2 Relationship To DIGITAL Network Architecture . . 12 2.3 Routing Layer Environment Requirements . . . . . 13 2.4 Routing Layer Characteristics . . . . . . . . . 14 2.5 Routing Layer Control Functional Organization . 15 2.5.1 Routing . . . . . . . . . . . . . . . . . . . 15 2.5.1.1 Decision Process . . . . . . . . . . . . . . 15 2.5.1.2 Update Process . . . . . . . . . . . . . . . 18 2.5.1.3 Forwarding Process . . . . . . . . . . . . . 18 2.5.1.4 Receive Process . . . . . . . . . . . . . . 18 2.5.2 Congestion Control . . . . . . . . . . . . . . 19 2.5.3 Packet Lifetime Control . . . . . . . . . . . 19 2.5.3.1 Loop Detector . . . . . . . . . . . . . . . 19 2.5.3.2 Node Listener . . . . . . . . . . . . . . . 19 2.5.3.3 Node Talker . . . . . . . . . . . . . . . . 20 3.0 INTERFACES . . . . . . . . . . . . . . . . . . . . 20 3.1 Network Management Layer Interface . . . . . . . 20 3.2 Data Link Layer Interface . . . . . . . . . . . 27 3.3 End Communications Layer Interface . . . . . . . 30 3.4 Routing Layer Initialization Interface . . . . . 32 4.0 DETAILED ROUTING SPECIFICATION . . . . . . . . . . 35 4.1 Routing Parameters . . . . . . . . . . . . . . . 35 4.2 Routing Data Base (in Level 1 And Level 2 Routers) . . . . . . . . . . . . . . . . . . . . 38 4.3 Area Routing Data Base In Level 2 Routers . . . 43 4.4 Forwarding Data Base In Level 1 And Level 2 Routers . . . . . . . . . . . . . . . . . . . . 45 4.5 Area Forwarding Data Base (level 2 Routers Only) 46 4.6 Data Base Protection . . . . . . . . . . . . . . 47 4.7 Decision Process . . . . . . . . . . . . . . . . 47 4.7.1 Decision Controller . . . . . . . . . . . . . 48 4.7.2 Decision Algorithms . . . . . . . . . . . . . 48 4.7.3 Decision Process Events And Actions . . . . . 52 4.8 Update Process . . . . . . . . . . . . . . . . . 57 4.8.1 Update Algorithm . . . . . . . . . . . . . . . 58 4.9 Forwarding Process . . . . . . . . . . . . . . . 58 4.10 Receive Process . . . . . . . . . . . . . . . . 60 4.11 Loop Detector Process . . . . . . . . . . . . . 60 5.0 DETAILED CONGESTION CONTROL SPECIFICATION . . . . 61 5.1 Square Root Limiter . . . . . . . . . . . . . . 62 5.2 Originating Packet Limiter . . . . . . . . . . . 62 5.3 Flusher . . . . . . . . . . . . . . . . . . . . 63 5.4 Packet Size Checker . . . . . . . . . . . . . . 63 6.0 ROUTING LAYER INITIALIZATION SUBLAYER . . . . . . 63 6.1 Version Skew . . . . . . . . . . . . . . . . . . 63 7.0 INITIALIZATION SUBLAYER: DDCMP OR X.25 . . . . . . 64 7.1 Node Listener Process . . . . . . . . . . . . . 64 7.1.1 Node Listener Controller . . . . . . . . . . . 65 7.1.2 Node Listener Algorithm . . . . . . . . . . . 65 7.2 Node Talker Process . . . . . . . . . . . . . . 65 7.3 Routing Layer Initialization Circuit States . . 66 7.4 Routing Layer Initialization Circuit Events . . 67 Page 4 7.5 Routing Layer Initialization Operation And Message Requirements . . . . . . . . . . . . . . 68 7.6 Routing Layer Initialization State Table And Diagram . . . . . . . . . . . . . . . . . . . . 68 7.7 Closing Down . . . . . . . . . . . . . . . . . . 71 8.0 ADDITIONAL INITIALIZATION SUBLAYER FOR X.25 . . . 71 8.1 Incoming Call Control . . . . . . . . . . . . . 71 8.2 Error Control . . . . . . . . . . . . . . . . . 71 8.3 Fragmentation, Assembly And Blocking . . . . . . 71 8.4 Closing Down . . . . . . . . . . . . . . . . . . 73 9.0 INITIALIZATION SUBLAYER: ETHERNET . . . . . . . . 74 9.1 Routers . . . . . . . . . . . . . . . . . . . . 74 9.1.1 Ethernet Router Hello Messages . . . . . . . . 74 9.1.2 Designated Router . . . . . . . . . . . . . . 75 9.1.3 When To Transmit Router Hellos . . . . . . . . 75 9.1.4 Closing Down . . . . . . . . . . . . . . . . . 75 9.1.5 Database Of Endnodes . . . . . . . . . . . . . 76 9.1.6 Multiple Areas On An Ethernet . . . . . . . . 76 9.2 Endnodes . . . . . . . . . . . . . . . . . . . . 77 9.2.1 Ethernet Endnode Hello Messages . . . . . . . 77 9.2.2 Designated Router's Ethernet Router Hello Message . . . . . . . . . . . . . . . . . . . 77 9.2.3 On-Ethernet Cache . . . . . . . . . . . . . . 77 9.2.4 Filling In "next Hop" In Packet Headers . . . 77 10.0 MESSAGES . . . . . . . . . . . . . . . . . . . . . 78 10.1 Message Format Notation . . . . . . . . . . . . 79 10.2 Reserved Fields . . . . . . . . . . . . . . . . 79 10.3 Optional Padding . . . . . . . . . . . . . . . . 80 10.4 Short Data Packet Format . . . . . . . . . . . . 81 10.5 Long Data Packet Format . . . . . . . . . . . . 82 10.6 Initialization Message . . . . . . . . . . . . . 83 10.7 Verification Message . . . . . . . . . . . . . . 85 10.8 Hello And Test Message . . . . . . . . . . . . . 86 10.9 Level 1 Routing Message . . . . . . . . . . . . 87 10.10 Level 2 Routing Message . . . . . . . . . . . . 89 10.11 Ethernet Router Hello Message . . . . . . . . . 91 10.12 Ethernet Endnode Hello Message . . . . . . . . . 93 APPENDIX A ROUTES, ADDRESSES, AND NAMES APPENDIX B ROUTING SUBSETS AND TOPOLOGIES B.1 NODE TYPES . . . . . . . . . . . . . . . . . . . . B-1 B.2 TOPOLOGICAL CONCEPTS . . . . . . . . . . . . . . . B-1 B.3 DECNET TOPOLOGICAL PRINCIPLES . . . . . . . . . . B-2 B.4 ENDNODE RESTRICTIONS . . . . . . . . . . . . . . . B-2 B.5 ETHERNET ROUTER RESTRICTIONS . . . . . . . . . . . B-3 B.6 LARGER NETWORKS . . . . . . . . . . . . . . . . . B-3 B.7 HIERARCHICAL NETWORKS . . . . . . . . . . . . . . B-4 Page 5 APPENDIX C NONROUTING OPERATION C.0.1 Receive Module . . . . . . . . . . . . . . . . . C-1 C.0.2 Interfaces . . . . . . . . . . . . . . . . . . . C-1 APPENDIX D PHASE III COMPATIBILITY APPENDIX E ROUTING LAYER COUNTERS AND EVENTS E.1 SOURCE EVENTS . . . . . . . . . . . . . . . . . . E-1 E.2 COUNTERS . . . . . . . . . . . . . . . . . . . . . E-7 E.3 EVENTS . . . . . . . . . . . . . . . . . . . . . . E-9 APPENDIX F ALGORITHMS AND MODELS F.1 CIRCUIT COST ASSIGNMENT ALGORITHM . . . . . . . . F-1 F.2 BUFFER MANAGEMENT . . . . . . . . . . . . . . . . F-2 F.3 POSSIBLE BUFFER MANAGEMENT MODEL . . . . . . . . . F-3 F.4 DETAILS OF CHARGING AND CREDITING AGAINST QUOTAS . F-4 APPENDIX G BUFFER SIZES APPENDIX H GLOSSARY APPENDIX I REVISION HISTORY I.1 CHANGES FROM PHASE III . . . . . . . . . . . . . . I-1 I.1.1 Ethernet Support . . . . . . . . . . . . . . . . I-1 I.1.2 Hierarchical Routing . . . . . . . . . . . . . . I-1 I.1.3 Segmented Routing Messages . . . . . . . . . . . I-1 I.1.4 Terminology Changes . . . . . . . . . . . . . . I-2 I.1.5 Clean-ups . . . . . . . . . . . . . . . . . . . I-2 I.1.6 Phase II Support Removed . . . . . . . . . . . . I-2 I.1.7 X.25 . . . . . . . . . . . . . . . . . . . . . . I-2 I.1.8 Miscellaneous . . . . . . . . . . . . . . . . . I-3 Introduction Page 6 1.0 INTRODUCTION This document describes the structure, functions, interfaces, protocols, and algorithms for implementing the Routing Layer. The Routing Layer is the part of the DIGITAL Network Architecture that models the software (or hardware) controlling the routing of messages, called packets, within DECnet communications networks. A DECnet network is a family of software modules, data bases, and hardware components typically used to tie DIGITAL systems together for resource sharing, distributed computation, or remote system communication. DECnet network implementations follow the DIGITAL Network Architecture (DNA) model. DNA is a layered structure. Modules in each layer perform distinct functions. Equivalent modules within the same layer in both the same and different nodes communicate using protocols. A node is an implementation of the DNA Session Control Layer. Usually a single computer is associated with one node. Protocols are the messages exchanged by modules and the rules governing the message exchanges. Modules in functionally different layers of DNA interface using either subroutine calls or a system-dependent method. This document describes these interfaces in the format of calls to subroutines. The routing described in this document is Phase IV DECnet routing. It is the major function of the Routing Layer. DIGITAL's routing is intended for users with networks consisting of any combination of point-to-point links, X.25 links, multipoint links, and Ethernets. Phase IV DECnet routing is hierarchical, in order to support large networks. A large network is partitioned by the network manager into "areas". Each node resides in exactly one area. Routing within an area is referred to as "level 1 routing". Routing between areas is referred to as "level 2 routing". Level 2 routers keep track of the paths to destination areas. Level 1 routers keep track only of the routing within their own area, and keep track of the nearest level 2 router within their area. When a level 1 router receives a packet for forwarding to a foreign area, it sends the packet to the nearest level 2 router. Then the packet travels via level 2 routing to the destination area, where it again travels via level 1 routing to the destination node. Phase IV DECnet is upwards compatible with Phase III DECnet. Thus there are the following types of nodes in Phase IV: 1. IV endnodes -- These nodes deliver packets to other nodes and receive packets from other nodes, but do not route packets through. They differ from Phase III endnodes in that they include an Initialization Sublayer for the Ethernet, and support hierarchical addressing in the layers above the Routing Layer. Introduction Page 7 2. IV level 1 routers -- These nodes deliver and receive packets from other nodes, and route packets from other source nodes through to other destination nodes. They route directly to nodes within their own area, and route towards a level 2 router when the destination node is in a different area. 3. IV level 2 routers -- These nodes act as IV level 1 routers in addition to acting as a node in the subnet consisting of level 2 routers. A node in the level 2 subnet routes towards a destination area. 4. III routers -- These nodes deliver and receive packets from other nodes within their own area, and route packets from other source nodes through to other destination nodes in their own area. These nodes do not include an Initialization Sublayer for the Ethernet, and thus cannot support the Ethernet. 5. III endnodes -- These nodes deliver packets to other nodes and receive packets from other nodes, but do not route packets through. These nodes do not include an Initialization Sublayer for the Ethernet, and thus cannot support the Ethernet. Networks that include endnodes, and/or that consist of more than one area, are restricted in how the nodes can be interconnected. In Phase IV a node's address is a 16 bit number, the top 6 bits of which define the area, and the bottom 10 bits of which give an address within an area. A glossary at the end of this document defines many Routing Layer terms. This document is intended for readers familiar with computer communications and with DECnet. The primary audience is those who are implementing DECnet systems. However, it may also be of interest to those who want to know the details of the Routing Layer design. The other current DNA functional specifications are: DNA Data Access Protocol (DAP) Functional Specification, Version 5.6.0, Order No. AA-K177A-TK DNA Digital Data Communications Message Protocol (DDCMP) Functional Specification, Version 4.1.0, Order No. AA-K175A-TK DNA Ethernet Data Link Functional Specification, Version 1.0.0, Order No. AA-Y298A-TK DNA Ethernet Node Product Architecture Specification, Version 1.0.0, Order No. AA-X440A-TK DNA Maintenance Operations Functional Specification, Version 3.0.0, Order No. AA-X436A-TK Introduction Page 8 DNA Network Management Functional Specification, Version 4.0.0, Order No. AA-X437A-TK DNA Network Services Protocol Functional Specification, Version 4.0.0, Order No. AA-X439A-TK DNA Session Control Functional Specification, Version 1.0.0, Order No. AA-K182A-TK The Ethernet - A Local Area Network - Data Link Layer and Physical Layer Specifications, Version 2.0, (Digital, Intel, and Xerox), Order No. AA-K759B-TK The DECnet DIGITAL Network Architecture (Phase IV) General Description (Order No. AA-N149A-TC) provides an overview of the network architecture and an introduction to each of the functional specifications. 2.0 FUNCTIONAL DESCRIPTION The Routing Layer routes messages in DECnet networks and manages the message packet flow. A packet is a unit of data to be routed from a source node to a destination node. The Routing Layer consists of two sublayers: 1. Control. The Control Sublayer supplies full-duplex packet transmission between any pair of nodes. It is independent of the specific Data Link Layer below it, except for knowing about two generic types of links: 1. non-broadcast links, which include DDCMP point-to-point, DDCMP multipoint, and X.25, and 2. broadcast links, which include the Ethernet. The Routing Control Sublayer masks the physical and topological characteristics of the network from higher layers. It consists of the following components: o Routing o Congestion control o Packet lifetime control 2. Initialization. The Routing Initialization Sublayer masks the characteristics of the Data Link Layers from the Routing Control Sublayer. It consists of the following components: o Initialization Functional Description Page 9 o Physical circuit monitor The Routing Initialization Sublayer controls the Data Link Layer and is Data Link Layer dependent. The Routing Layer components provide the following functions. Routing. The routing function determines packet paths. A path is the sequence of connected nodes between a source node and a destination node. When the Routing Layer receives a packet, the routing component refers to a data base that is periodically updated by Routing Layer modules in adjacent nodes. The routing component uses information in this data base to determine if a path to a destination exists, and, if so, what the next hop in the path is. The routing component then forwards the packet to its destination. If more than one path exists to a destination, the routing component ascertains the best path. The combined knowledge of all the Routing Layer modules of all the nodes in a network is used to ascertain the existence of a path, and route the packet to its destination. The routing component at a routing node has the following specific functions: o It extracts and interprets the route header in a packet. o It performs packet forwarding based on the destination. o It manages the characteristics of the path. If a node or link fails on a path, it finds an alternate route. o It interfaces with the Routing Initialization Sublayer to receive reports concerning a circuit or node that has failed or the subsequent recovery of a circuit or node. o It returns packets addressed to unreachable nodes to the End Communications Layer (ECL), if requested to do so by ECL. A node is unreachable if it is unknown, or the path to it exceeds the maximum hops of the network. A hop is the logical distance between two adjacent nodes. Maximum hops is a Routing Layer parameter that is equal to the maximum path length in the network. Congestion control. Congestion control manages the buffers at each packet switching node (that is, at each node that permits route-through). Packet lifetime control. Packet lifetime control bounds the number of nodes a packet can visit. Initialization. The Initialization component supplies the following functions: o It identifies the adjacent node and the adjacent node's Routing Layer. Functional Description Page 10 o It performs node verification, if required. Physical circuit monitor. This component monitors errors detected by the Data Link Layer. 2.1 Design Scope The Routing Layer supports the following design requirements: 1. Deliverability. It accepts and delivers packets addressed to reachable destinations and rejects packets addressed to unreachable destinations. 2. Adaptability. It adapts to topological changes, but not to traffic changes. (Topological changes are changes in the configuration of active circuits and nodes in a network. Traffic changes are changes in the load on circuits in a network.) 3. Promptness. The period of adaptation to topological changes in the network is a reasonable function of the network diameter (that is, the maximum logical distance between network nodes) and circuit speeds. 4. Efficiency. The Routing Layer is both processing and memory efficient. It does not create excessive routing traffic overhead. 5. Robustness. The Routing Layer recovers from transient errors such as lost or temporarily incorrect routing messages. It tolerates imprecise parameter settings. 6. Stability. The Routing Layer stabilizes in finite time to "good routes," provided no continuous topological changes or continuous data base corruptions occur. 7. Operator control. An operator can control many routing functions via parameter changes, and inspect parameters, counters, and routes. Routing, however, will not depend on operator input for correct behavior. 8. Simplicity. The Routing Layer is sufficiently simple to permit performance tuning and failure isolation. 9. Maintainability. The Routing Layer provides mechanisms to detect, isolate, and repair most common errors that may affect the routing computation and data bases. Functional Description Page 11 10. Verification of compatibility. The Routing Layer Initialization Sublayer prevents incompatible routing algorithms from coexisting in the network. 11. Heterogeneity. The Routing Layer operates over a mixture of network node types, communication circuits, and topologies. In particular, it supports point-to-point, multipoint, and multiaccess. 12. Support of subsets. The Routing Layer allows nodes to support a subset of the routing functions. 13. Extensibility. The Routing Layer accommodates increased routing functions, leaving earlier functions as a subset. 14. Evolution. The Routing Layer allows orderly transition from algorithm to algorithm without shutting down an entire network. 15. Deadlock Prevention. The congestion control component prevents deadlock, the condition in which the Routing Layer fails to deliver data. 16. Independence. Congestion control does not depend on routing for effective operation. 17. Duplicate message reduction. The packet lifetime control algorithm significantly reduces the risk of the user receiving duplicate messages. 18. Large networks. With hierarchical routing, the Routing Layer supports networks of several thousand nodes. The following are not within the scope of Phase IV Routing Layer: 1. Traffic adaptation. The Routing Layer does not react to traffic flow automatically. 2. Traffic service classes. The Routing Layer does not distinguish among different classes of traffic in route determination. 3. Source-destination routing. The Routing Layer does not determine routes by source as well as destination. 4. Gross operator failure. The Routing Layer does not attempt to protect the network from operator actions, such as removing a circuit or a node, that may disconnect the network. 5. Guaranteed delivery. The Routing Layer does not guarantee delivery of all offered packets. Functional Description Page 12 2.2 Relationship To DIGITAL Network Architecture The DIGITAL Network Architecture (DNA) is a model that defines the functional requirements of all DECnet implementations. The model is a layered one. The Routing Layer lies between the End Communications Layer and the Data Link Layer, as shown in Figure 1. .----------------------------. ! User Modules ! `----------------------------' ! ! ! ! ! V .- ! ------- ! -----------------------------------. .------! ! Network ! Management Modules ! ! `- ! ------- ! -----------------------------------' ! ! ! ! ! ! ! ! V V ! ! ! .- ! -------------------------------- ! ------. ! :----> ! ! Network Application Modules ! ! ! ! `- ! -------------------------------- ! ------' ! ! ! ! ! ! ! ! V V V ! ! ! .---------------------------------------. ! ! :----> ! Session Control Modules ! ! ! ! `---------------------------------------' ! ! ! ! ! ! ! V ! ! ! .----------------------------. ! ! :------------> ! End Communications Modules ! ! ! ! `----------------------------' ! ! ! ! ! ! ! V ! ! ! .--------------------------. ! ! :------------> ! Routing Layer Modules ! ! ! ! `--------------------------' ! ! ! ! ! ! ! V V V ! .-----------------------------------------. :------------> ! Data Link Modules ! ! `-----------------------------------------' ! ! ! V ! .--------------------------. `------------> ! Physical Link Modules ! `--------------------------' ! `-------------------------> Figure 1. Routing Layer Relation to DNA Functional Description Page 13 A brief description of each DNA layer follows: 1. User Layer. The highest layer, the User Layer supports user services and programs. 2. Network Management Layer. Modules in the Network Management Layer provide user control over and access to network parameters and counters. These modules also furnish up-line dumping, down-line loading, and testing functions. This layer is the only layer that has direct access to each lower layer for control purposes. 3. Network Application Layer. Modules in the Network Application Layer support network functions, such as remote file access and file transfer, used by the two higher layers. 4. Session Control Layer. The Session Control Layer defines the system-dependent aspects of logical link communication, which allows controlled data movement between network nodes. 5. End Communications Layer. The End Communications Layer defines the system-independent aspects of logical link communication. 6. Routing Layer. Modules in the Routing Layer route messages between source and destination nodes. 7. Data Link Layer. The Data Link Layer defines the protocol concerning data integrity and physical channel management. 8. Physical Link Layer. The Physical Link Layer encompasses a part of the device driver for each communications device plus the communications hardware itself. The hardware includes interface devices, modems, and the communication lines. This layer controls the end-to-end transmission of data. Each DNA layer uses the services of the layer below it. In addition, Network Management provides a control interface to all the DNA layers below it. User and Network Application Layer modules can interface directly with Session Control. 2.3 Routing Layer Environment Requirements The Routing Layer requires guarantees from the operating system, the End Communications Layer, and the Data Link Layer. The required operating system guarantees are: Functional Description Page 14 1. Priority scheduling such that the Routing Layer receives minimum processing guarantees 2. A quota of buffers to the Routing Layer sufficient to perform routing and packet lifetime control functions 3. Access to a timer or notification of specific timer expiration The End Communications Layer must guarantee the return of a buffer within a short, bounded amount of time. Otherwise, the Routing Layer may discard packets received for ECL if ECL exceeds a quota. The required Data Link Layer guarantees for point-to-point links are: 1. Provision that both source and destination nodes complete start-up before message exchange can occur 2. Detection of remote start-up 3. Provision that no old messages be received after start-up is complete 4. Masking of transient errors in order to prevent packet data corruption 5. Provision for not duplicating or corrupting packets 6. Packet sequentiality ensuring that, if a packet has been received, all previously sent packets have been received 7. Reporting of failures and degraded circuit conditions The required Data Link Layer guarantees for Ethernets are: 1. Provision for not corrupting packets 2. Packet sequentiality ensuring that, if a packet has been received, no previously sent packet will be subsequently received 2.4 Routing Layer Characteristics The Routing Layer possesses the following characteristics: o Variable delay. There is a variable delay time. Delay is defined as the time between receipt of a packet from ECL at a source node and delivery of that packet to ECL at a destination node. Functional Description Page 15 o Nonsequential delivery. The Routing Layer does not guarantee delivery of packets to ECL at the destination node in the same sequence in which they were received from ECL at the source node. o Packet integrity. The Routing Layer will not modify or misdeliver a packet. 2.5 Routing Layer Control Functional Organization The Routing Layer Control Sublayer components can be broken down into more specific functional components. These are described briefly here and in detail below. 2.5.1 Routing - The Routing processes and data bases are: o Decision Process o Update Process o Forwarding Process o Receive Process o Routing data base o Forwarding data base 2.5.1.1 Decision Process - This process selects routes to each destination in the network. It consists of a connectivity algorithm that maintains path lengths and a traffic assignment algorithm that maintains path costs. Path length is the number of hops along a path between two nodes. Circuit cost is a nonzero, positive integer value associated with using a circuit, and path cost is the sum of the circuit costs along a path between two nodes. Functional Description Page 16 When a routing node receives a Routing Message (a type of Routing Layer control message) from an adjacent node, the routing node executes the Decision Process. Execution of the Decision Process results in the determination of pairs (known as adjacencies) along which to forward packets and possibly the conclusion that one or more particular destination nodes are unreachable. The system manager must set several of the parameters in the Routing data base that the Decision Process uses. These include maximum address, maximum number of areas (in level 2 nodes), maximum cost, maximum hops, maximum circuits, circuit costs, maximum total broadcast end-node adjacencies, maximum total broadcast router adjacencies, and maximum broadcast router adjacencies for each broadcast circuit. The values of the cost parameters are arbitrary. Appendix F suggests an algorithm for determining circuit costs. The values of the other parameters depend on the specific topology of the network. If these values are not set correctly, the decision algorithms will not work correctly. The figure below shows a sample network, consisting of a single area, and depicts some of the Routing terms. The glossary contains definitions of these and other Routing Layer terms. Functional Description Page 17 .---. 2 .---. | D |----------------| E | `---' `---' / \ \ 3 / \ 7 \ 4 / \ \ / \ \ .---. 2 .---. 3 .---. | C |-------| B |---------------| F | `---' `---' `---' | 1 hop | 2 | .---. | A | `---' Legend: .---. | x | = node `---' _____ = circuit n = circuit cost .---. .---. | x |--| x | = hop `---' `---' .------------------------------------------------------------------. | Node A wants to send a packet to node D. There are three | | possible paths. | |------------------------------------------------------------------| | | | Path | | Path | Path Cost | Length | |------------------------------------------------------------------| | .-. .-. .-. .-. .-. .-. | * | | | |A|-|B| |B|-|C| |C|-|D| | 2 + 2 + 3 = 7 | 3 hops | | `-' `-', `-' `-', `-' `-' | | | |------------------------------------------------------------------| | .-. .-. .-. .-. | | | | |A|-|B| |B|-|D| | 2 + 7 = 9 | 2 hops | | `-' `-', `-' `-' | | | |------------------------------------------------------------------| | .-. .-. .-. .-. .-. .-. .-. .-. | | | | |A|-|B| |B|-|F| |F|-|E| |E|-|D| | 2 + 3 + 4 + 2 = 11| 4 hops | | `-' `-', `-' `-', `-' `-', `-' `-' | | | `------------------------------------------------------------------' * 7 is the lowest path cost; node A therefore routes the packet to node D via this path. Figure 2. Routing Terms Functional Description Page 18 2.5.1.2 Update Process - This process constructs and propagates Routing Messages. A Routing Message contains path cost and path length for all destinations. The Update Process sends Routing Messages to adjacent nodes after determining that certain conditions are met. General characteristics of the Update Process are: . Level 1 Routing Messages are sent to adjacent routing nodes within the node's home area . Level 2 Routing Messages are sent to adjacent level 2 routing nodes . Level 1 Routing Messages contain information on all nodes within the home area . Level 2 Routing Messages contain information about all areas . Routing Message transmission is event-driven with periodic backup . The routing update algorithm maintains an upper limit on routing traffic overhead 2.5.1.3 Forwarding Process - This process supplies and manages the buffers necessary to support packet route-through to all destinations. It performs a table lookup to determine the output adjacency to use for forwarding to a given destination, reformats packets between short and long format if necessary, strips off the area fields when forwarding to a Phase III node, fills in the area fields when receiving from a Phase III node, and marks intra-Ethernet packets. 2.5.1.4 Receive Process - The Receive Process inspects a packet's route header and dispatches the packet to an appropriate Routing Layer Control component or to the End Communications Layer (ECL). Functional Description Page 19 2.5.2 Congestion Control - The Congestion Control component manages buffers by limiting the maximum number of packets on the transmit queue for a circuit. Congestion Control regulates the ratio of packets received directly from ECL to route-through packets. Congestion Control also checks the packet size for each packet to be sent. 2.5.3 Packet Lifetime Control - The packet lifetime control component requires three processes: 1. Loop Detector 2. Node Listener 3. Node Talker 2.5.3.1 Loop Detector - This process prevents excessive packet looping. It counts the number of nodes a packet has visited and removes a packet when it exceeds the visit limit. 2.5.3.2 Node Listener - This process determines that a minimum amount of activity has occurred between this node and an adjacent node. It also determines if the identity of the adjacent node has changed. Violations of the minimum activity audit result in the declaration that the adjacency between the nodes is down. On non-broadcast circuits, Hello Messages need to be sent only in the absence of other traffic, to ensure that a minimum amount of activity occurs. On broadcast circuits, Hello Messages need to be sent periodically regardless of other forms of traffic. Functional Description Page 20 2.5.3.3 Node Talker - This process provides the minimum activity for each adjacent Node Listener. It places an artificial load on the adjacency so failures can be detected. The Node Talker and Listener provide for detection of adjacent Routing Layer halt and adjacent node identity change. 3.0 INTERFACES This section describes the three external Routing Layer interfaces: 1. Network Management Layer interface 2. Data Link Layer interface 3. End Communications Layer interface In addition, this section describes the single internal Routing Layer interface, Initialization Sublayer. The interfaces take the format of calls to subroutines, as follows: FUNCTION (input ; output) Each call represents a specific function. An implementation is not required to code the interface as calls to subroutines. The following symbols are used throughout the document: <> not equal to <= less than or equal to >= greater than or equal to >> much greater than SQRT(x) the square root of CEILING(x) the least integer greater than or equal to x 3.1 Network Management Layer Interface This interface allows Network Management to control and observe the Routing Layer interactively. Network Management can exert indirect control over the Routing Layer via parameter changes. The following Network Management functions form a set of primitive functions that Interfaces Page 21 can be used to construct more complex functions. READ SELF PARAMETERS (;parameters) This function gives the values of the node's parameters. Parameters are: . Routing-State -- Routing Layer operating, or terminated, requiring problem correction and initialization . Net-Management-State -- ON or OFF. Setting this parameter to "ON" from "OFF" forces Routing to initialize all its data bases. . ID, top 6 bits of which is HOMEAREA, bottom 10 bits of which is Tid, node within area . NN -- highest node number within the area . NA (in level 2 routers only), highest area number in the network . NC -- number of circuits supported by this node . NBRA -- number of Broadcast Router Adjacencies (BRAs) supported by this node . NBEA -- number of Broadcast Endnode Adjacencies (BEAs) supported by this node . Maxh -- Maximum hops possible in a path to a reachable destination within an area . Maxc -- Maximum cost possible in a path to a reachable destination within an area . AMaxh -- (in level 2 routers only), maximum hops possible in a path to a reachable area . AMaxc -- (in level 2 routers only), maximum cost possible in a path to a reachable area . Maxv -- Maximum visits allowable for a packet . T1 -- Background timer for routing updates on non-broadcast circuits . BCT1 -- Background timer for routing updates on broadcast circuits . Routing Type -- Phase IV area router, Phase IV router, Phase IV nonrouting Interfaces Page 22 . Routing Version -- the current routing version, ECO, and user ECO . BS -- Buffer size -- Six greater than the maximum buffer size for use by Routing, excluding Routing Layer Header and excluding Data Link Layer header. (Note -- the added 6 bytes are for historical compatibility with Phase III, when the Buffer size parameter included Routing Layer header, which was 6 bytes at the time.) . SS -- Segment size -- Six greater than the maximum segment size to be used by ECL. SS must be less than or equal to BS. It will usually be equal to BS. It may be less than BS while the buffer sizes in the network are being increased or decreased. . NB -- maximum number of buffers for forwarding . Subaddresses -- (in nodes with X.25 Data Link Mapping only) -- the range of local DTE subaddresses that are acceptable on an X.25 circuit for an incoming call SET SELF PARAMETER (PARAMETER, VALUE; status) This function sets the parameter PARAMETER to VALUE. The parameters supported are those enumerated above in the READ SELF PARAMETERS call. The returned status is: . success . unknown parameter . illegal value READ SELF COUNTER (; counters) This function gives the values of the node's counters, maintained by the Routing Layer. Appendix E describes these counters in detail. Counters are: . node unreachable packet loss . aged packet loss . node out-of-range packet loss Interfaces Page 23 . oversized packet loss . packet format error . partial routing update loss . verification reject READ AND CLEAR SELF COUNTERS (; counters) This function returns the same values as READ SELF COUNTERS. It zeroes all counters upon completion READ CIRCUIT PARAMETERS (CIRCUIT; status, parameters) This function gives the values of the CIRCUIT's parameters. These parameters are described more fully in Section 4.2. The returned status is one of: . success . unknown circuit Parameters are: . Type (Ethernet, X.25, DDCMP) . Net-Management-State (ON or OFF) . State (as determined by Initialization Sublayer) . Cost . Hello Timer . Recall Timer . Originating Packet Limiter (OPL) . Type Specific Information o For Ethernet, the type specific information is: - NR -- Number of BRAs allowed on this Ethernet - Priority -- the router's priority to be Designated Router Interfaces Page 24 - Designated Router -- the ID of the router currently chosen to be Designated Router on this Ethernet o For X.25, the type specific information is: - Port State -- supplied by the X.25 Data Link Layer - Blocking -- indicates if blocking can be done by this node - Negotiated Blocking -- indicates if neighbor also requested blocking - Maximum Recalls -- the maximum number of call trials permitted from the Data Link Start state before halting - Recall Count -- the number of call attempts that have been made to try to initialize a virtual circuit. This is reset by the operator turning the circuit on. - VC Type -- type of virtual circuit: . PVC (permanent virtual circuit) . incoming switched virtual circuit . outgoing switched virtual circuit - VC name. For an SVC, a network name and a DTE address. For a PVC, a PVC name. SET CIRCUIT PARAMETER (CIRCUIT, PARAMETER, VALUE; status) This function sets the parameter PARAMETER in circuit CIRCUIT to VALUE. The returned status is: . success . unknown circuit . unknown parameter . illegal value Interfaces Page 25 READ CIRCUIT COUNTERS (CIRCUIT; status, counters) This function gives the values of the counters maintained by the Routing Layer for the specified circuit. Counters are described more fully in Appendix E. The returned status is one of: . success . unknown circuit Counters are: . Transit ("Route-Through") Packets Received . Transit Packets Sent . Terminating Packets Received (packets received from other nodes addressed to this node) . Originating Packets Sent (packets from this node addressed to other nodes) . Transit Congestion Loss . Terminating Congestion Loss . Circuit Down . Initialization Failure In addition, for X.25 circuits, there is the type specific counter: . Corruption Loss -- a count of the data errors detected for this circuit READ AND CLEAR CIRCUIT COUNTERS (CIRCUIT; status, counters) This function returns the same values as READ CIRCUIT COUNTERS. It zeroes the counters upon completion. READ NODE PARAMETERS (NODE; parameters) This function gives the values of parameters maintained by Routing for the specified node. If the local node type is a level 1 router, and the specified node is in another area, the values of parameters maintained by Routing for the special destination #0, meaning "nearest level Interfaces Page 26 2 router" are given. Parameters are: . Reachability Flag . Output Circuit [and NextHop, for Ethernets only] to NODE . Hops of minimum cost path to NODE . Cost of minimum cost path to NODE READ AREA PARAMETERS (AREA; parameters) This function gives the values of the parameters maintained by Routing for the specified area. This function is implemented in level 2 routers only. Parameters are: . Reachability Flag . Output Circuit [and NextHop, for Ethernets only] to AREA . Hops of minimum cost path to AREA . Cost of minimum cost path to AREA READ ADJACENCY PARAMETERS (ADJACENCY; parameters) This function gives the values of the parameters maintained by Routing for the specified adjacency. An adjacency is a pair. The argument "adjacency" is an adjacency # in the Routing Data Base. Parameters are: . In Use Flag . Node ID . Node Type, one of: . Level 1 router . Level 2 router . Phase IV endnode . Phase III router Interfaces Page 27 . Phase III endnode . circuit . Listen Timer . neighbor's blocksize READ EVENT (; event) Return: the oldest event in the Routing Layer's internal event queue The Routing Layer maintains an internal event queue into which it places events. Events are described in Appendix E. This function reads the oldest event in the queue. CLEAR EVENTS Returns: none This function clears all events from the Routing Layer's internal event queue. 3.2 Data Link Layer Interface This interface, between the Routing Layer's Initialization Sublayer and the Data Link Layer, consists of commands to and responses from the Data Link Layer. The interface supports the exchange of data, control, and error information. Data is information to be sent or received by the Data Link Layer protocol. Its description usually consists of a starting buffer address and a length or character count, or a chain of addresses and counts. The control information starts and stops the protocol. The error information reports circuit conditions. The functions of the interface, described as calls, are as follows: Interfaces Page 28 TRANSMIT (circuit, buffer, [NextHop], [more data to follow]) Returns: none This function gives a message to the Data Link Layer for transmission. On a broadcast circuit, the parameter "NextHop" must be supplied. The parameter "NextHop" is not supplied on a non-broadcast circuit. "More data to follow" is a flag specified only on X.25 circuits. CHECK TRANSMIT BUFFER (buffer) Returns: buffer is still queued buffer is returned to the Routing Layer This function returns information about the transmit buffer. INITIALIZE CIRCUIT (circuit) Returns: none This function causes the Data Link protocol to initialize the circuit. In the case of the Ethernet, Data Link padding must be enabled. Also, Routing must tell the Data Link Layer to enable the protocol type PROT-TYPE, and the multicast ID ALL-ROUTERS (if the local node is a router), or the multicast ID ALL-ENDNODES (if the local node is an endnode). In the case of X.25, this tells the Data Link Layer that if the virtual circuit is in the UNSYNC state, send a "reset confirmation", and if the virtual circuit is in the RUNNING state, send a "reset" packet. If the virtual circuit is in the cleared state, a call must be initiated. STOP circuit (circuit) Returns: none This function halts the Data Link operation on the specified circuit. Interfaces Page 29 For X.25 circuits, this means send a "clear" packet on a Switched Virtual Circuit, and send a "reset" packet on a Permanent Virtual Circuit. STATUS (circuit; status) Returns: off running initializing This function returns the Data Link state of the circuit. If the Data Link modules provide additional states (for example, a maintenance state), they are treated as the OFF state. READ ERROR COUNTERS (circuit; error counters) Returns: error counter values (value,status) This function returns the values of the Data Link error counters, and notification if error thresholds have been exceeded. SUPPLY RECEIVE BUFFER (buffer; status) Returns: buffer accepted buffer rejected This function provides an empty buffer to the Data Link modules for receipt of the next sequential message. CHECK RECEIVE BUFFER (buffer; circuit, [PrevHop], [more data to follow], status) Returns: no packet received packet received, buffer returned This function returns the above information about the receive buffer. The PrevHop value is returned when a packet is received on a broadcast circuit. The PrevHop value is not returned when a packet is received on a non-broadcast circuit. Interfaces Page 30 The "more data to follow" flag is returned only on X.25 circuits. 3.3 End Communications Layer Interface This interface, between the End Communications Layer and the Routing Layer, consists of commands to and responses from the Routing Layer. The commands and responses exchange data and control information. Data is information that the Routing Layer sends or receives. The data description is a destination address, source address, buffer address and length of data. Destination and source addresses are two-byte integer numbers with the most significant 6 bits being the area number, and the least significant 10 bits being the address within the area. The Routing Layer uses node addresses only, not node names, which are resolved at a higher layer. Control information starts or stops transmission and reception of data and regulates the data flow to a reachable destination. The functions of the interface, described as calls, are as follows: TRANSMIT (destination, return flag, [circuit,[NextHop]], Tryhard, buffer) Returns: buffer is queued buffer is not queued and is returned to ECL This function sends a packet. The return flag indicates whether or not ECL wants the packet returned if the destination is unreachable or becomes unreachable before the Routing Layer can deliver the packet. If the flag is set to "true" (Boolean), the Routing Layer attempts to return the contents of the buffer to ECL as a "received packet." If the flag is not set, the Routing Layer discards the packet. The Routing Layer returns the buffer after ECL issues the CHECK TRANSMIT BUFFER call (described next). Circuit, selected by the End Communications Layer, is either unspecified or a valid circuit. If the circuit is a broadcast circuit, NextHop must also be specified. For circuit level loopback testing, the End Communications Layer must specify a circuit, and if required, a NextHop. Otherwise, the Routing Layer determines the adjacency. Interfaces Page 31 TryHard, if set, tells the Routing Layer to flush any cache entries for the destination. Currently the only cache entries are in endnodes attached to broadcast circuits. CHECK TRANSMIT BUFFER (buffer) Returns: buffer still queued buffer returned to ECL This function checks the status of a previously queued transmit buffer. It returns the buffer to ECL after any of the following: o The buffer is copied into a Routing Layer buffer. o The packet is transmitted. o The packet is discarded because the destination is unreachable and the return flag is not set. o The packet contents are transferred to a receive buffer because the destination is unreachable and the return flag is set. SUPPLY RECEIVE BUFFER (buffer) Returns: buffer queued for receive by the Routing Layer buffer not queued for receive by the Routing Layer This function queues a receive buffer to the Routing Layer. CHECK RECEIVE BUFFER (source, circuit, [PrevHop], buffer) Returns: buffer remains queued by the Routing Layer buffer returned to End Communications Layer with source node address (buffer contains a normal packet) buffer returned to End Communications Layer (buffer contains a "return to sender" packet -- ECL Functional Specification) This function checks the status of a previously queued receive buffer. It returns the buffer if the packet was received or if the node is unreachable and the return flag is set. The circuit variable returns a valid circuit number (or a value for an internal link) for each received packet. For packets Interfaces Page 32 received over a broadcast circuit, PrevHop is set to the node number of the node which forwarded the packet to this node. READ BLOCKSIZE (;blocksize) Returns: blocksize This function informs ECL of the maximum blocksize the Routing Layer can handle, not including routing header. ECL should not transmit any packets larger than this size. This value is equal to 6 less than the Segment Size (SS) SELF parameter set by network management. 3.4 Routing Layer Initialization Interface This interface, between the Routing Layer Control Sublayer and the Routing Layer Initialization Sublayer, supports the routing events defined in Section 4.7.3. The interface consists of commands to and responses from the Routing Layer Initialization Sublayer. TRANSMIT (adjacency, buffer) Returns: none This function transmits a buffer containing a packet. CHECK TRANSMIT BUFFER (buffer; status) Returns: buffer still queued buffer returned to user This function polls a buffer containing a packet that has been sent with the TRANSMIT function. If the packet has been transmitted, the buffer is returned to Routing Layer Control. If the packet has not yet been transmitted, a message is returned indicating that the buffer is queued. Interfaces Page 33 STATUS (circuit; status) Returns: off initializing circuit accepted by Routing Layer Initialization running; current value of circuit cost This function returns the status of the circuit. The off, initializing, and running states correspond to Data Link Layer states. For Ethernets, the only valid states are "off" and "running." STATUS (adjacency; status) Returns: unused entry in use; node ID, node type, and corresponding circuit for that adjacency This function returns the status of the adjacency. REINITIALIZE (circuit) Returns: none This function turns the circuit off and initializes the circuit in such a manner that messages previously received in the circuit will be discarded. SUPPLY RECEIVE BUFFER (buffer; status) Returns: buffer accepted buffer rejected This function provides a receive buffer to Routing Layer Initialization so that it can receive a packet. CHECK RECEIVE BUFFER (buffer; status, adjacency) Returns: no packet received packet received, buffer returned Interfaces Page 34 This function polls the status of a buffer that the Routing Layer Control has just supplied with the SUPPLY RECEIVE BUFFER function. Upon receiving a packet into the buffer, the Routing Layer Initialization returns the buffer to the Routing Layer Control. SUPPLY CIRCUIT UP COMPLETE (circuit) Returns: none This function informs the Routing Layer Initialization that the Decision Process recognizes that a circuit is up. (The process has completed its circuit up event algorithm.) SUPPLY CIRCUIT DOWN COMPLETE (circuit) Returns: none This function informs the Routing Layer Initialization that the Decision Process recognizes that a circuit is down. (The process has completed its circuit down event algorithm.) SUPPLY BROADCAST ADJACENCY UP COMPLETE (adjacency) Returns: none This function informs the Routing Layer Initialization that the Decision Process recognizes that an adjacency on a broadcast circuit is up. (The process has completed its adjacency up event algorithm.) SUPPLY BROADCAST ADJACENCY DOWN COMPLETE (adjacency) Returns: none This function informs the Routing Layer Initialization that the Decision Process recognizes that an adjacency on a broadcast circuit is down. (The process has completed its adjacency down event algorithm.) Detailed Routing Specification Page 35 4.0 DETAILED ROUTING SPECIFICATION The routing function consists of the following data bases and processes: o Routing data base o Forwarding data base o Decision Process o Update Process o Forwarding Process o Receive Process 4.1 Routing Parameters The following parameters are settable via Network Management: 1. NN -- Maximum node number within the area 2. NA -- Maximum area number (For level 2 routers only) 3. NC -- Number of circuits supported by this node 4. NBRA -- Number of broadcast router adjacencies supported by this node 5. NBEA -- Number of broadcast endnode adjacencies supported by this node 6. NR -- Number of broadcast router adjacencies allowed on a given Ethernet (settable separately for each Ethernet). The sum of all the NR for circuits in Net-Management-State ON cannot exceed NBRA. 7. Maxh -- Maximum hops possible in a path to a reachable node within the area, suggested value twice the worst-case longest path length in hops. 8. Maxc -- Maximum cost possible in a path to a reachable node within the area, suggested value Maxh*Maxl. 9. AMaxh -- (level 2 routers only) -- Maximum hops possible in a path to a reachable area, suggested value twice the worst-case longest path length in hops. Detailed Routing Specification Page 36 10. AMaxc -- (level 2 routers only) -- Maximum cost possible in a path to a reachable area, suggested value AMaxh*Maxl. 11. Maxv -- Maximum visits for a packet before Routing assumes the packet is looping, suggested value is Maxh + k, where 1 < k <=Maxh 12. T1 -- Background frequency timer for non-broadcast circuits; maximum time period for exchanging Routing Messages with adjacent node on a non-broadcast circuit. The purpose of this timer is to recover from database corruption. Suggested value is 10 minutes. 13. BCT1 -- Background frequency timer for broadcast circuits; maximum time period between broadcasted Routing Messages on the Ethernet. The purpose of this timer is to recover from lost packets on the Ethernet. Suggested value is 10 seconds. 14. T3 -- Hello timer. Settable separately for each circuit. The following are implementation parameters that are not settable via Network Management: 1. T2 -- Rate control frequency timer: minimum time period before another Routing Message can be sent. Suggested value is 1 second. 2. CACHETIMEOUT -- amount of time Ethernet endnodes leave a cache entry in the On-Ethernet Cache without traffic which confirms the entry's correctness before erasing the cache entry (See Ethernet Initialization Sublayer). Suggested value is 1 minute. The following parameters are architectural constants: 1. Infh = 31. 2. Infc = 1023. 3. Maxl -- Maximum cost assignable to a circuit, 25. 4. T3MULT -- The multiple of the neighbor's Hello Timer (on a non-broadcast circuit) at which your Listen Timer should be set (i.e., T4 <-- neighbor's T3*T3MULT). T3MULT = 2. 5. BCT3MULT -- The multiple of the neighbor's Hello Timer (on a broadcast circuit) at which your Listen Timer should be set (i.e., T4 <-- neighbor's T3*BCT3MULT). BCT3MULT = 3. Detailed Routing Specification Page 37 6. HIORD -- The 32 bit quantity to be prefixed to the 16-bit node address to form the 48 bit Ethernet physical address. HIORD = AA-00-04-00. Therefore, if the node address is A1-A2, with A1 the least significant byte, then the formed 48 bit Ethernet physical address will be AA-00-04-00-A1-A2. 7. ALL-ROUTERS -- the multicast ID "All Routers". ALL-ROUTERS = AB-00-00-03-00-00. 8. ALL-ENDNODES -- the multicast ID "All Endnodes". ALL-ENDNODES = AB-00-00-04-00-00. 9. PROT-TYPE -- the protocol type used by Routing on the Ethernet. PROT-TYPE = 60-03. 10. DRDELAY -- the number of seconds an Ethernet router waits before declaring itself Designated Router DRDELAY = 5. The following relationships exist between the above parameters: 1. NN >= actual maximum address within area NN < 1024 2. NA >= actual maximum area number (for level 2 routers only) NA < 64 3. Maxh >= actual maximum path length in an area Maxh <= 30 4. Maxc >= (actual maximum network path length) X (Maxl) Maxc <= 1022 5. Maxv >= actual maximum path length in the entire network Maxv <= 63 6. AMaxh >= actual maximum path length to any area AMaxh <= 30 7. AMaxc >= actual maximum path cost to any area AMaxc <= 1022 Detailed Routing Specification Page 38 8. T1 >> T2 9. T3 <= 8191 (to ensure that it fits into a 16-bit word when multiplied by BCT3MULT or T3MULT) 4.2 Routing Data Base (in Level 1 And Level 2 Routers) The routing data base contains routing data summarized in Table 1. The Network Management action of setting the Net-Management-State SELF parameter to ON from OFF initializes the data base. This is a prerequisite to normal node operation. Table 1 also shows the initial values of the data. Table 1 Level 1 Routing Data Base Symbol Description Initial value ------------------------------------------------------- Adj Adjacency Data Base empty Circuits Circuits Data Base empty Hop Network connectivity matrix * Cost Cost matrix * Minhop Network minimum connectivity Infh vector Mincost Minimum traffic assignment Infc vector Srm Send Routing Message flags 0 Tid Routing Layer identification ** HomeArea Home Area ** * All entries in Hop are initialized to Infh, and all entries in Cost are initialized to Infc, except Hop(Tid,0) and Cost(Tid,0) are initialized to 0. ** This value is supplied as a SELF parameter by Network Management. ------------------------------------------------------- A description of each element of the data base follows. Adjacency Vector. This contains information about each adjacency. An entry consists of Adj(i), where: Adj(i) contains the information: Detailed Routing Specification Page 39 1. state (unused entry, currently undergoing initialization, up) 2. nodeID -- neighbor ID 3. type -- neighbor node type -- Types are: . Level 1 router . Level 2 router . Phase IV endnode . Phase III router . Phase III endnode . No neighbor -- Adjacency is one of the broadcast circuits 4. circuit -- circuit corresponding to this adjacency in Circuits vector. 5. blocksize requested by neighbor 6. neighbor's Hello Timer (T3, if neighbor is Phase III) 7. time of last Hello heard from neighbor 8. priority -- (BRAs only), neighbor broadcast router's priority on that Ethernet i is an integer in the range 1- representing an adjacency. Note: NC counts all broadcast circuits plus neighbors on non-broadcast circuits, NBRA counts all router adjacencies on Ethernet, and NBEA counts all endnode neighbors on Ethernet. Adjacencies 1 through NC are in one-to-one correspondence with the circuits. Adjacencies [NC+1] through [NC+NBRA] are reserved for Broadcast Router Adjacencies. (So that columns in the Hop and Cost matrices can correspond exactly with the first NC+NBRA adjacencies.) Circuits Vector. This contains information about each circuit. An entry consists of Circuit(i), where: Detailed Routing Specification Page 40 Circuit(i) Contains the information: 1. type of circuit (Ethernet, X.25, DDCMP) 2. state (e.g. off, running, initializing, etc.) as determined by Initialization Sublayer 3. cost 4. datalink blocksize (up to and including Routing envelope) Note that on Ethernet circuits, the datalink blocksize must be greater than or equal to BS-6 (the buffer size SELF parameter set by network management minus 6) plus the overhead in the routing envelope in long data packet format. On DDCMP circuits, the datalink blocksize must be greater than or equal to BS-6 plus the overhead in the routing envelope in short data packet format. 5. Hello Timer (T3) 6. last time Hello issued on this circuit 7. Recall Timer -- Amount of time Routing should wait before reinitializing the Data Link Layer 8. OPL -- Originating Packet Limit 9. counters 10. type specific information . For Ethernet, the type specific information is: 1. NR -- Number of BRAs allowed on this Ethernet 2. Priority -- the router's priority to be Designated Router 3. Designated Router -- the ID of the router currently chosen to be Designated Router on this Ethernet . For X.25, the type specific information is: 1. Port State -- supplied by the X.25 Data Link Layer 2. Blocking -- indicates if blocking will be requested by this node Detailed Routing Specification Page 41 3. Negotiated Blocking -- indicates if neighbor also requested blocking 4. Maximum Recalls -- the maximum number of call attempts permitted from the Data Link start state before halting 5. Recall Count -- the number of call attempts that have been made to try to initialize a virtual circuit. This is reset by the operator turning the circuit on. 6. VC Type -- type of virtual circuit: . PVC (permanent virtual circuit) . incoming switched virtual circuit . outgoing switched virtual circuit 7. VC name. For an SVC, a network name and a DTE address. For a PVC, a PVC name. i is an integer in the range 1-NC representing a circuit. Network connectivity matrix (Hop). This contains information on the path length to each destination over each circuit or BRA. An entry consists of Hop(i,j), where: Hop(i,j) represents the path length from this Routing Layer to the destination, with the following values: Value Meaning 0 Self 1 Adjacent node 2-Maxh Other reachable nodes Infh Unreachable node i is an integer in the range 0-NN representing a destination address. Destination 0 is the special destination "nearest level 2 router". j is an integer in the range 0- representing self, a circuit, or an Ethernet router adjacency. Detailed Routing Specification Page 42 Value Meaning 0 Self 1-NC Circuit in Circuit(j) [NC+1]-[NC+NBRA] Broadcast Router Adjacency in Adj(j) Traffic assignment matrix (Cost). This contains information on the path cost to each destination over each adjacency. This information determines which adjacency to use for traffic to a destination. An entry consists of Cost(i,j), where: Cost(i,j) represents the path cost from this Routing Layer to the destination, with the following values: Value Meaning 0 Self 1-Maxc Path cost to other reachable nodes Infc Unreachable nodes i is an integer in the range 0-NN representing a destination address. j is an integer in the range 0- representing self, a circuit, or a Broadcast Router Adjacency as in the Hop matrix. Minimum network connectivity vector (Minhop). This summarizes the path length information contained in the Hop table. An entry consists of Minhop(i), where: Minhop(i) represents the path length via the adjacency yielding the least cost path from this Routing Layer to the destination node, with the following values: Value Meaning 0 Self 1 Path length to adjacent node 2-Maxh Path length to other reachable nodes Infh Node unreachable i is an integer in the range 0-NN representing a destination address. Detailed Routing Specification Page 43 Minimum traffic assignment vector (Mincost). This summarizes the path cost information contained in the Cost table. An entry consists of Mincost(i), where: Mincost(i) Represents the smallest cost from this Routing Layer to the destination, with the following values: Value Meaning 0 Self 1-Maxc Smallest cost to other reachable nodes Infc Unreachable node i is an integer in the range 0-NN representing a destination address. Send Routing Message flags (Srm). The Srm flags extend permission to the Update Process to send a Routing Message about a given destination on a given circuit. The Update Process determines the actual propagation rules. An entry consists of Srm(i,j), where: Srm(i,j) indicates whether or not a Routing Message should be sent about destination i to circuit j. i is an integer in the range 0-NN representing a destination j is an integer in the range 1-NC representing the circuit on which to send the message Routing Layer Identification (Tid). This contains the bottom ten bits of the value set by Network Management in the ID parameter of the SELF parameters. Home Area (HomeArea). This contains the top 6 bits of the value set by Network Management in the ID parameter of the SELF parameters. 4.3 Area Routing Data Base In Level 2 Routers The routing data base in level 2 routers contains routing data on destination areas as summarized in Table 2. This database, like the routing database described in section 4.1, is initialized by the Network Management SET NODE STATE ON function. Detailed Routing Specification Page 44 Table 2 Area Routing Data Base Symbol Description Initial value ----------------------------------------------------------------- AHop Area Hop Information * AMinhop Area Minimum Hops Infh ACost Area Cost Information * AMincost Area Minimum Cost Infc ASrm Area Send Routing Msg Flags 0 AttachedFlg Other Areas Reachable Flag False * All entries in AHop are set to Infh, and all entries in ACost are set to Infc upon initialization, except that AHop(HomeArea,0) and ACost(HomeArea,0) are initialized to 0. ----------------------------------------------------------------- A description of each element of the area database follows. Area Hop Information (AHop). This contains information on the number of hops to each destination area via each adjacency. An entry consists of AHop(i,j), where: AHop(i,j) represents the number of hops to destination area i via adjacency j i is an integer in the range 1-NA representing a destination area j is an integer in the range 0- representing the attached area (0), a circuit (1-NC), or a broadcast router adjacency ([NC+1]-[NC+NBRA]) Area Minimum Hops (AMinhop). This summarizes the information in AHop. An entry consists of AMinhop(i), where: AMinhop(i) represents the path length in hops via the adjacency along the path of least cost from this node to the destination area i is an integer in the range 1-NA representing a destination area. Area Cost Information (ACost). This contains information on the cost to each destination area via each adjacency. An entry consists of ACost(i,j), where: ACost(i,j) represents the path cost to destination area i via circuit or broadcast router adjacency j. Detailed Routing Specification Page 45 i is an integer in the range 1-NA representing a destination area j is an integer in the range 0- representing the attached area (0), a circuit (1-NC), or a broadcast router adjacency ([NC+1]-[NC+NBRA]) Area Minimum Cost (AMincost). This summarizes the information in ACost. An entry consists of AMincost(i), where AMincost(i) represents the smallest cost via any adjacency from this node to the destination area i is an integer in the range 1-NA representing a destination area. Area Send Routing Message flags (ASrm). The ASrm flags extend permission to the Update Process to send a Level 2 Routing Message about a given destination area on a given circuit. The Update Process determines the actual propagation rules. An entry consists of ASrm(i,j), where: ASrm(i,j) -- Indicates whether or not a Level 2 Routing Message should be sent about destination area i to circuit j. i is an integer in the range 1-NA representing an area j is an integer in the range 1-NC representing the circuit on which to send the message Other Areas Reachable Flag (AttachedFlg). Indicates other areas are reachable if true. 4.4 Forwarding Data Base In Level 1 And Level 2 Routers The information in this data base indicates whether or not a destination is reachable and, if reachable, what adjacency to use to get there. This data base consists of two vectors, as follows: Reachability vector (Reach). This indicates whether or not the destination is reachable. An entry consists of Reach(i), where: Reach(i) is either True (reachable) or False (unreachable) i is an integer in the range 0-NN representing the destination node address. Destination #0 is the special destination "nearest level 2 router". Detailed Routing Specification Page 46 Output adjacencies (OA). This identifies the adjacency on which to forward a packet to a destination. An entry consists of OA(i), where: OA(i) represents the adjacency to be used when forwarding a packet to destination i. OA contains one of the following values: Value Meaning 0 Deliver to a Routing Layer user at this node 1- An adjacency on which to forward a packet i is an integer in the range 0-NN representing a destination node address. Destination #0 is the special destination "nearest level 2 router". 4.5 Area Forwarding Data Base (level 2 Routers Only) The information in this data base indicates whether or not a destination area is reachable, and if reachable, what adjacency to use to get there. This data base consists of two vectors, as follows: Area Reachability Vector (AReach). This indicates whether or not the destination area is reachable. An entry consists of AReach(i), where: AReach(i) is either True (reachable) or False (unreachable) i is an integer in the range 1-NA representing a destination area Area Output Adjacencies (AOA). This indentifies the adjacency on which to forward a packet to a destination area. An entry consists of AOA(i), where AOA(i) represents the adjacency to be used when forwarding a packet to destination area i. Value Meaning 0 Home Area--Use level 1 Forwarding Information 1- An adjacency on which to forward a packet i is an integer in the range 1-NA representing a destination area. Detailed Routing Specification Page 47 4.6 Data Base Protection A memory failure, a corrupted Routing Message, or a software error can corrupt a routing data base. Such corruptions cause a transient disruption of packet delivery. If the corruption is transient, the routing data bases stabilize to correct routes. If the corruption is continuous, the routing data bases remain in a transient incorrect state. Two conditions are necessary for self-stabilization: 1. The Routing Layer must periodically propagate Routing Messages. 2. Column 0 of the Cost and Hop matrices (in other words, the values relating to self) cannot be corrupted. For level 2 routers, column 0 of the AHop and ACost matrices similarly cannot be corrupted. 4.7 Decision Process The Decision Process selects paths and maintains the routing and forwarding data bases. The following events serve as input to the Decision Process: o Operator command to set Net-Management-State to ON from OFF. o Adjacency down o Adjacency up o Circuit down o Circuit up o Routing Message received o Operator command to change circuit cost o Operator command to change parameters Maxh or Maxc o Timer expiration The Decision Process produces the following output: o Modifications to the routing data base Detailed Routing Specification Page 48 o Modifications to the forwarding data base 4.7.1 Decision Controller - The controller performs the following functions: o Performs buffer management necessary to receive Routing Messages. o Supports Routing Layer initialization (Section 7). o Checks for valid Routing Message. A valid Routing Message has: 1. A valid checksum 2. A valid Routing Layer control header If the Routing Message is not valid, then an adjacency down event on an Ethernet, or a circuit down event on a point-to-point link is generated, and the Routing Message is discarded and recorded. A valid Routing Message is processed through end of message or end of table. If the Routing Message is too long (that is, length beyond end of table), then the controller examines the overrun. The data in the overrun portion of the message must contain values corresponding to Infh in the hop fields and to Infc in the cost fields. If not, then the controller finds the highest node number for which the values are not infc/infh, and logs an event. o Updates the forwarding data base 4.7.2 Decision Algorithms - The Decision Process contains an algorithm for computing the minimum cost path. It then computes the path length of that path, and sets the reachability vector, Reach, according to whether the cost and hops of the path found are within the set limits. It also sets the output adjacency vector, OA, to the adjacency which is the next hop of the minimum cost path for each destination. The following subroutines represent the decision algorithms. They are followed by a description of the action that the decision module takes for each event received. Detailed Routing Specification Page 49 Subroutine: Rowmin(M, I, minimum, VECT) ; This routine determines the minimum for row I of ; Matrix M and stores the column number in VECT(I). Matrix M Integer I,minimum Vector VECT minimum = "big number" FOR j = 0 to NC+NBRA DO BEGIN IF (M(I,j) < minimum ), OR ((M(I,j) = minimum) AND (ADJ(j).nodeID > ADJ(VECT(I)).nodeID)) THEN minimum = M(I,j) VECT(I) = j ENDIF END Subroutine: Minimize(I,M,V,P1,P2,VECT) ; This routine determines entries for vector V, ; containing the minimum of each row of matrix M, ; and passes to Rowmin the vector VECT in which to store the ; resulting output adjacency number. Integer I Matrix M Vector V Parameters P1, P2 Vector VECT Rowmin(M,I,minimum,VECT) IF (minimum > P1) THEN minimum = P2 V(I) = minimum ENDIF Detailed Routing Specification Page 50 Subroutine: Routes(FirstDest, LastDest) ; This routine determines the reachability and output adjacency ; for each destination in the range FirstDest to LastDest ; within the area, with destination #0 the nearest level 2 router. INTEGER OLD_HOP, OLD_COST FOR i = FirstDest to LastDest DO OLD_HOP = MINHOP (i) OLD_COST = MINCOST (i) Minimize (row i, Cost, Mincost, Maxc, Infc, OA) Col = OA(i) Minhop(i) = Hop(i,Col) IF Minhop(i) > Maxh THEN Set Minhop(i) = Infh ;now set OA to adjacency rather than column IF Col <= NC AND Circuit(Col).Type=Ethernet THEN ;need ;to convert to BEA Search for BEA with node ID i set OA(i) to that BEA IF (Minhop(i) = Infh OR Mincost(i) = Infc) THEN BEGIN Reach(i) = False Minhop(i) = Infh Mincost(i) = Infc END ELSE Reach(i) = True ENDIF IF(MINHOP(i) < > OLDHOP OR MINCOST(i) < > OLDCOST THEN for each k from 1 to NC Set Srm(i,k) ENDIF ENDDO Detailed Routing Specification Page 51 Subroutine:ARoutes(FirstArea, LastArea) ; This routine determines the reachability and output adjacency ; for each area in the range FirstArea to lastArea. Integer OLD_HOP, OLD_COST FOR i = FirstArea to LastArea DO OLD_HOP = AMinhop (i) OLD_COST = AMincost (i) Minimize (row i, ACost, AMincost, AMaxc, Infc, AOA) Col = AOA(i) AMinhop(i) = AHop(i,Col) IF AMinhop(i) > AMaxh THEN Set AMinhop(i) = Infh ;note in this case Col is the Adjacency, since a BEA cannot ;be a path to a different area IF (AMinhop(i) = Infh OR AMincost (i) = Infc) THEN BEGIN AReach(i) = False AMinhop(i) = Infh AMincost(i) = Infc END ELSE AReach(i) = True ENDIF IF (AMinhop(i) <> OLD_HOP OR AMincost(i) <> OLD_COST THEN FOR j = 1 to NC IF Adj(j).Type=level 2 router OR Circuit(j).Type=Ethernet THEN Set ASrm(i,j) ENDIF ENDDO ;set value of AttachedFlg and Hop(0,0) and Cost(0,0) AttachedFlg=False Hop(0,0)=Infh Cost(0,0)=Infc FOR i = 1 to NA IF AReach(i)=True AND i < > HomeArea THEN Hop(0,0)=0 Cost(0,0)=0 AttachedFlg=True ENDIF ENDFOR CALL Routes(0,0) ;to calculate for nearest attached ;level 2 router Detailed Routing Specification Page 52 Subroutine: Check ; This routine detects any corruption of column 0 in the ; Hop, Cost, AHop and ACost matrices. BEGIN ;first check column 0 of Hop and Cost Check that Hop (Tid,0) and Cost (Tid,0) = 0 IF a level 2 router AND AttachedFlg = True Check that Hop(0,0) and Cost (0,0) = 0 IF a level 2 router AND AttachedFlg = False Check that Hop(0,0) = Infh and Cost (0,0) = Infc FOR i = 0 to NN UNLESS (i = Tid OR (i = 0 AND node is level 2 router)) Check that Hop (i,0) = Infh AND Cost (i,0) = Infc ;now check column 0 of AHop and ACost IF a level 2 router FOR I = 1 to NA IF HomeArea = i Check that AHop (i,0) = 0 and ACost (i,0) = 0 ELSE Check that AHop(i,0) = Infh and ACost(i,0) = Infc ENDIF IF any check fails, then Terminate the Routing Layer ENDIF IF both checks are successful, then EXIT ENDIF END 4.7.3 Decision Process Events And Actions - A. Operator command to set Net-Management-State to ON from OFF. 1. Tell Ethernet Data Link the physical address consisting of B1-B2-B3-B4-B5-B6, where B1-B2-B3-B4 are the four bytes of HIORD, with B1 the most significant byte, and B5-B6 is ID, with B5 the least significant byte of ID. 2. Initialize Routing databases 3. Set Hop(Tid,0)=0 and Cost(Tid,0)=0 4. IF a level 2 router, set AHop(HomeArea)=0, ACost(HomeArea)=0 5. Call Routes (0,NN) Detailed Routing Specification Page 53 6. IF a level 2 router, call ARoutes(1,NA) B. Broadcast adjacency j down (note that if j <= NC, the event is a circuit down event) 1. IF (NC+1) <= j <= (NC+NBRA), then ;adjacency j is a BRA a. Set each entry in column "j" of Hop matrix to Infh. IF a level 2 router, set each entry in column "j" of AHop matrix to Infh. b. Set each entry in column "j" of Cost matrix to Infc. IF a level 2 router, set each entry in column "j" of ACost matrix to Infc. c. IF local node type is level 2, and node type of adjacency j is level 2, call ARoutes(1,NA) d. Call Routes(0,NN) 2. IF NC+NBRA < j, THEN ;adjacency j is a BEA NODEID <-- Adj(j).NodeID k <-- circuit pointed to in Adj(j) Set Hop(NODEID,k) = Infh Set Cost(NODEID,k) = Infc Call Routes(NODEID,NODEID) 3. Supply "adjacency down complete" to Initialization Sublayer C. Broadcast adjacency j up 1. IF (NC+1) <= j <= (NC+NBRA) ;j is BRA CIRC <= Adj(j).Circuit FOR i = 0 to NN, Set Srm(i,CIRC) IF local node is a level 2 router, AND Adj(j).Type=level 2 FOR i = 1 to NA, Set ASrm(i,CIRC) 2. IF NC+NBRA < j, THEN ;j is BEA NODEID <-- Adj(j).NodeID k <-- Adj(j).Circuit Set Hop(NODEID,k) = 1 Set Cost(NODEID,k) = cost of Circuit(k) Call Routes(NODEID,NODEID) 3. Supply "adjacency up complete" to Initialization Sublayer Detailed Routing Specification Page 54 D. Circuit j down 1. Call Check. 2. Set each entry in column "j" of Hop matrix to Infh. IF a level 2 router, set each entry in column "j" of AHop matrix to Infh. 3. Set each entry in column "j" of Cost matrix to Infc. IF a level 2 router, set each entry in column "j" of ACost matrix to Infc. 4. FOR each adjacency k pointing to circuit j Declare broadcast adjacency k down 5. IF local node type is level 2 router Call ARoutes(1,NA). 6. Call Routes(0,NN). 7. Supply "circuit down complete" to Initialization Sublayer. E. Circuit j up Case 1: Circuit j is a non-broadcast circuit with k=node number as determined by Initialization Sublayer 1. Call Check. 2. IF Adj(j).Type=endnode, THEN a. Hop(k,j)=1 b. IF Circuit(j).Cost is not > 0 THEN the Routing Layer terminates. c. Cost(k,j)=Circuit(j).Cost d. Call Routes(k,k) 3. Set Srm(i,j) FOR i = 0 to NN 4. IF local node type is level 2 router, AND Adj(j).Type=level 2, set ASrm(i,j) FOR i = 1 to NA 5. Supply "circuit up complete" to Initialization Sublayer. Case 2: Circuit j is a broadcast circuit 1. Call Check Detailed Routing Specification Page 55 2. IF Circuit(j).Cost is not > 0 THEN the Routing Layer terminates. 3. FOR i = 0 to NN, set Srm (i,j) 4. IF local node type is level 2 router, set ASrm(i,j) FOR i = 1 to NA 5. Supply "circuit up complete" to Initialization Sublayer. F. Level 1 Routing Message received on adjacency j, 1 <= j <= (NC+NBRA). The Routing Message contains destinations in set S. 1. Call Check. 2. Copy hop subfield of Routing Message for each i in set S, onto row i, column "j" of Hop matrix. 3. Add 1 to Hop (i,j) for each i in set S. 4. Copy cost subfield of Routing Message for each i in set S, onto row i, column "j" of Cost matrix. 5. IF Cost of Circuit pointed to by adjacency j is not > 0, THEN the Routing Layer terminates. Otherwise, add that cost to Cost (i,j) for each i in set S. 6. FOR each i in set S, Call Routes(i,i). G. Level 2 Routing Message received on adjacency j (level 2 routers only). The Routing Message contains areas in set S. 1. Call Check. 2. Copy hop subfield of Routing Message, for each i in set S, onto row i, column "j" of AHop matrix. 3. Add 1 to AHop (i,j) for each i in set S. 4. Copy cost subfield of Routing Message, for each i in set S, onto row i, column "j" of ACost matrix. 5. IF Cost of Circuit pointed to by adjacency j is not greater than 0, then the Routing Layer terminates. Otherwise, add that cost to Cost (i,j) for each i in set S. 6. FOR each i in set S, Call ARoutes(i,i). Detailed Routing Specification Page 56 H. Circuit j cost change 1. Call Check. 2. Calculate the difference between the new cost and the old cost for circuit j. Note that the new cost and the old cost must both be greater than 0, otherwise the Routing Layer terminates. 3. Add this difference to each entry in column "j" of Cost matrix. 4. IF circuit type is broadcast, add this difference to each entry in each column k of the Cost matrix, where k is a broadcast router adjacency with circuit=j 5. Call Routes(0,NN). 6. IF local node is level 2 router, add this difference to each entry in column "j" of the ACost matrix. 7. IF local node is level 2 router and the circuit type is broadcast, add this difference to each entry of the ACost matrix for each column k, where k is a broadcast router adjacency with circuit=j 8. IF local node is level 2 router, call ARoutes(1,NA). I. Maxh, Maxc, AMaxh, or AMaxc change 1. Call Check. 2. Call Routes(0,NN) 3. IF local node type is level 2 router, Call ARoutes(1,NA) J. T1 Timer expires 1. Call Check. 2. FOR j = 1 to NC a. IF Circuit(j).Type=nonbroadcast, AND Adj(j).Type=router (level 1, level 2, or Phase III) THEN FOR i = 0 to NN, Set Srm(i,j) b. IF local node is level 2 router AND Adj(j).Type=level 2, AND Adj(j).Circuit.Type=nonbroadcast THEN FOR i = 1 to NA, Set ASrm(i,j) Detailed Routing Specification Page 57 3. Call Routes(0,NN). 4. IF local node is level 2, Call ARoutes(1,NA) K. BCT1 Timer expires 1. Call Check. 2. FOR j = 1 to NC a. IF Circuit(j).Type=broadcast, THEN FOR i = 0 to NN, Set Srm(i,j) b. IF local node is level 2 router AND IF Circuit(j).Type=broadcast, THEN FOR i = 1 to NA, Set ASrm(i,j) 4.8 Update Process The Update Process propagates Routing Messages and determines their content. It consists of an algorithm and a format module. The Update Process accepts the following as input: o The minimum hop vector, Minhop o The minimum cost vector, Mincost o The area minimum hop vector, AMinhop o The area minimum cost vector, AMincost o The Send Routing Message flags, Srm o The Area Send Routing Message flags, ASrm The Update Process produces a Routing Message for an adjacent node as output. Detailed Routing Specification Page 58 4.8.1 Update Algorithm - A Level 1 Routing Message containing a given set of destinations is sent on a circuit j when a buffer is available from the quota given to the Routing Process for Update use, AND at least T2 has elapsed since the last transmission of a Routing Message containing the same destinations on circuit j, AND some Srm(i,j) is set, for at least one i in that set of destinations. A Level 2 Routing Message is sent on a circuit j when a buffer is available from the quota given to the Routing Process for Update use, AND at least T2 has elapsed since the last transmission of a Routing Message containing those areas on circuit j, AND some ASrm(i,j) is set, for at least one i in that set of areas. Any algorithm that sends, as a minimum, all information flagged by the Srm and ASrm flags can be used. (An algorithm may send more data than this to simplify the algorithm or reduce the data storage for Srm flags.) When the circuit is of type Ethernet, the Routing Message is sent to the multicast ID "all routers". Care must be taken that no nodes, areas, or circuits are starved. For example, an algorithm that does not scan through all circuits and destination (nodes or areas) before restarting, might never reach some circuit or destination. Care must also be taken that systematic ordering of the transmitted segments does not cause the same segments to always be lost. For example, on an Ethernet, if all segments are sent, one after another, in rapid succession, the last segments might be lost with high probability. Thus, on Ethernets, each time a periodic complete Routing Message is sent, the segments should be cycled through, so that each segment gets a chance to be the first segment. The T2 timer is intended to be restarted on a circuit after all destinations with Srm or ASrm flags set during one pass through are transmitted on that circuit. On a point-to-point circuit, a Routing Message may be as long as the neighbor's blocksize. On an Ethernet circuit, a Routing Message may be as long as the minimum blocksize of all BRAs on that circuit. 4.9 Forwarding Process The Forwarding Process supplies and manages the buffers necessary for route-through. Packets are discarded if buffer thresholds are exceeded. Detailed Routing Specification Page 59 Packet formats, and names of fields, are described in Section 10. Data packets can be in one of three formats: 1. long format 2. short format 3. Phase III format Packets in long format have bit 2 of the FLAGS byte=1. Packets in short format or Phase III format have bit 2 of the FLAGS byte=0. Phase IV nodes are required to be able to receive short format on point-to-point circuits, and long format on Ethernet circuits. They should transmit short format on point-to-point circuits, and long format on Ethernet circuits. They must receive and transmit Phase III format to Phase III adjacencies. Packets in all three formats have bit 6 ("Future version")=0. Discard but do not log packets received with bit6 = 1. Discard and log (as "message format error") short packets (in other words, packets with less than a packet route header) and packets with an invalid route header (including packets in short format received on an Ethernet circuit, if this node cannot handle such packets, or packets received in long format on a point-to-point circuit, if this node cannot handle such packets). If the incoming adjacency is a Phase III endnode or router, if the top 6 bits of Destination ID=0, fill in "HomeArea" in the top 6 bits of Destination ID. If the top 6 bits of Source ID are 0, fill in "HomeArea" in the Source ID field. If the source and destination are attached Ethernet endnodes, on the same Ethernet, set the intra-Ethernet bit. If the destination is in a foreign area, and the local node type is a level 1 router, or the local node type is a level 2 router and AttachedFlg=False, then forward based on OA(0). If the destination is in a foreign area, and the local node type is a level 2 router and AttachedFlg=True, then forward based on AOA(foreign area). If the adjacency the packet is to be forwarded on has node type Phase III router or Phase III endnode, clear the area field in the Destination ID. If the area in Source ID is "HomeArea", clear that as well. If the area in Source ID is not "HomeArea", and the Destination is the next node, and the Destination's node type is "Phase III router" or "Phase III endnode", do not forward the packet. Instead drop the packet or return it to sender, as with an unreachable destination. Detailed Routing Specification Page 60 If the destination is unreachable, and "return to sender requested" is set, set "return to sender", clear "return to sender requested", switch the destination and source ID fields, and forward the packet towards the new destination (the previous source). Otherwise, drop the packet. If the circuit the packet is to be forwarded on is an Ethernet, and the packet is in short format, then reformat the packet to long format. If the "intra-Ethernet bit" is set, clear the bit unless the packet is to be forwarded onto the same circuit from which it was received. When originating a packet on an Ethernet, always set the intra-Ethernet bit. If the circuit the packet is to be forwarded on is point-to-point, and the packet is in long format, check that the first 4 bytes of D-ID and S-ID are set to HIORD. Drop the packet and log (as "message format error") if they are not. Reformat the packet to short format. 4.10 Receive Process The Receive Process receives packets from the Data Link Layer. It then passes the packet to the appropriate process, as follows: Packet Type Process Routing Message Decision Process Hello Message Node Listener Process Packet for Self End Communications Layer Packet for other Forwarding Process destination 4.11 Loop Detector Process The loop detector limits the number of nodes that a packet can visit. It increments the node visit field in the packet route header by one. The loop detector discards the packet if this number exceeds the maximum node visit limit, Maxv. Note that the parameter Maxv must always be greater than or equal to the parameter Maxh. Detailed Routing Specification Page 61 The algorithm the loop detector executes when it receives a packet is the following: Add 1 to node visit field in packet route header. IF ((node visit > Maxv) and ("return to sender" is not set)) If "return to sender requested" is set, set "return to sender" clear "return to sender requested" reverse source and destination forward the packet towards the (new) destination. Else drop the packet and record ENDIF IF ((node visit > 2 * Maxv) and ("return to sender" is set)) Discard packet and record ENDIF 5.0 DETAILED CONGESTION CONTROL SPECIFICATION The transmit management subroutine handles congestion control. Transmit management consists of the following components: o Square root limiter. Reduces buffer occupancy time per packet by using a square root limiter algorithm (Appendix F). The square root limiter also queues packets for an output circuit, and prevents buffer deadlock by discarding packets when the buffer pool is exhausted. Section 5.1 specifies the Square Root Limiter Process. o Originating packet limiter. Limits originating packet traffic when necessary to ensure that transit packets are not rejected. An originating packet is a packet from the ECL at this node. A transit packet is a packet from another node to be routed through to another destination node. o Flusher. Flushes packets queued for an adjacency that has gone down. o Packet size checker. Resolves differences between packet size and Data Link receive blocksize. Detailed Congestion Control Specification Page 62 5.1 Square Root Limiter The square root limiter discards a transit packet or rejects an originating packet when the output circuit queue exceeds the discard threshold, Ud. Ud is given as follows: Ud = CEILING (NB/ SQRT(NC)) where: NB = Number of Routing Layer buffers for all output circuits. NC = Number of active output circuits. 5.2 Originating Packet Limiter The originating packet limiter first distinguishes between originating packets and transit packets. It then imposes a limit on the number of buffers that originating packets can occupy on a per circuit basis. In times of heavy load, originating packets may be rejected while transit packets continue to be routed. This is done because originating packets have a relatively short wait, whereas transit packets, if rejected, have a long wait -- a retransmission period. The originating packet limiter accepts as input: o A packet received from End Communications Layer o A transmit complete from the Data Link Layer for an End Communications Layer packet The originating packet limiter produces the following as output: o Packet accepted o Packet rejected o Modifications to originating packet counter There is a counter, N, and an originating packet limit, OPL, for each active output circuit. Each N is initialized to 0. Each OPL is initialized to the number of buffers necessary to prevent the circuit from idling. Detailed Congestion Control Specification Page 63 5.3 Flusher The flusher ensures that no packet is queued on a circuit whose state is not RUN, or on a nonexistent adjacency. 5.4 Packet Size Checker The packet size checker checks the size of each packet that it is about to queue on an output adjacency. This includes packets from both the End Communications Layer at this node and transit packets. When the packet size exceeds the Data Link receive blocksize (established during Routing Layer initialization), the packet size checker discards the packet and records the event. Endnodes on a broadcast circuit are not required to have a packet size checker. 6.0 ROUTING LAYER INITIALIZATION SUBLAYER The Initialization Sublayer masks the characteristics of the different kinds of Data Link Layers from the Control Sublayer. The only two types of circuits the Control Sublayer sees is broadcast or non-broadcast. In Phase IV, the only type of supported broadcast circuit is the Ethernet. The only types of supported non-broadcast circuits are DDCMP point-to-point, DDCMP multipoint, and X.25. 6.1 Version Skew In initialization with an adjacent node, a node must drop and ignore Initialization Messages with higher version numbers. The version number check must be done before looking at any of the other fields in the Initialization Message, since higher version Initialization Messages might not be compatible with lower version messages. It is the responsibility of the node with the higher version number to note that it has a neighbor with a lower version number, and if the node with the higher version number knows about the earlier protocol, that node must start sending Initialization Messages with the lower version number. If the node with the higher version number does not know about the earlier protocol, an initialization failure, version skew event is logged. Routing Layer Initialization Sublayer Page 64 In comparing version numbers, the version number byte is the only byte compared. The ECO number byte and the User ECO number byte are not accessed during the comparison. 7.0 INITIALIZATION SUBLAYER: DDCMP OR X.25 The Routing Layer initialization is a start-up procedure between two adjacent nodes. The procedure involves exchanging Routing Layer Initialization Messages and possibly Routing Layer Verification Messages. This exchange identifies the nodes to each other and provides additional node information. This section describes: o The Routing Layer Initialization circuit states o The Routing Layer Initialization circuit events o The Routing Layer Initialization operation and message requirements o The Routing Layer Initialization state table and diagram 7.1 Node Listener Process The Node Listener Process detects node failures. The process consists of a controller and an algorithm module. The Node Listener accepts the following as input: o Hello Message received o Any message received on a non-broadcast circuit o Timer pulse received The Node Listener Process produces the following as output: o Modifications to the adjacency data base Initialization Sublayer: DDCMP or X.25 Page 65 7.1.1 Node Listener Controller - The Node Listener Controller manages the buffers necessary for receiving Hello Messages. It also checks for valid Hello Messages. A valid Hello Message contains a valid Routing Layer control header and valid data. If the Hello Message is not valid, then a circuit down event is generated, and the Hello Message is recorded and discarded. 7.1.2 Node Listener Algorithm - The Node Listener algorithm determines when the adjacent node is no longer talking. Such a node is considered down. Consequently, the circuit is reinitialized. The following describes the algorithm for handling each Node Listener event. A. Hello Message or any message received on adjacency j 1. Reset T4 by: Set TEMP = T3 If Adj(j).Type=Phase IV router or endnode Set TEMP = neighbor's Hello Timer Endif Set T4 = TEMP*T3MULT 2. If received message is Hello, check that TEST DATA is all octal 252 B. Timer pulse 1. Decrement T4 2. IF (T4 <= 0), then Reset T4 Set circuit state to CR ("circuit rejected.") ENDIF 7.2 Node Talker Process The Node Talker propagates Hello Messages. It sends a Hello Message to an adjacent node when: Initialization Sublayer: DDCMP or X.25 Page 66 o T3 has elapsed since the last transmission of any message. o A circuit has come up. The Node Talker can be interlocked with the Decision and Update Processes. When either Decision or Update fails, then the Node Talker ceases. 7.3 Routing Layer Initialization Circuit States The Routing Layer Initialization circuit states are: (Symbol) State Description (RU) RUN The Routing Layer can use the circuit to transmit packets between two nodes. (CR) CIRCUIT REJECTED The circuit is degraded. To avoid excessive packet delay the circuit will be declared down. The Routing Decision Process has not yet processed a circuit down event. (DS) DATA LINK START The circuit is undergoing Data Link Layer initialization. (RI) ROUTING LAYER INITIALIZE The circuit has successfully undergone Data Link initialization and is waiting to receive a Routing Layer Initialization Message. (RV) ROUTING LAYER VERIFY A valid Routing Layer Initialization Message has been received for this circuit and the circuit requires verification. (RC) ROUTING LAYER COMPLETE The Routing Layer has completed a valid exchange of Routing Layer Initialization and possibly Routing Layer Verification Messages. (OF) OFF The Routing Layer cannot use the circuit. The Routing Decision Process has not yet processed a circuit down event. (HA) HALT The Routing Layer cannot use the cir- cuit. A circuit down event is required. Initialization Sublayer: DDCMP or X.25 Page 67 7.4 Routing Layer Initialization Circuit Events The Routing Layer Initialization circuit events are as follows: (Symbol) Description (nri) The Routing Layer received a valid new Routing Layer Initialization Message. (nrv) The Routing Layer received a valid new Routing Layer Verification Message. (rt) The Routing Layer timed out. (sc) The Routing Layer received a start complete notification (in other words, a transition from the initializing state to the running state) from the Data Link Layer. (ste) The Routing Layer received a start notification (in other words, a transition from any state to the stop state) or threshold error notification from the Data Link Layer. In the case of X.25, a start notification is given by the Data Link Layer upon receipt of a "Clear Indication" or "Reset" packet, or when a data error is observed. (opo) Operator turned circuit on. (opf) Operator turned circuit off. (im) The Routing Layer received an invalid Routing Layer Initialization Message or an unexpected message. (rc) The Routing Layer received a reject complete from the circuit rejection component of the circuit monitor. (cdc) The Routing Layer Initialization received a circuit down complete event from the Decision Process in the Routing Layer Control Sublayer. (cuc) The Routing Layer Initialization received a circuit up complete event from the Decision Process in the Routing Layer Control Sublayer. When the Data Link Layer has initialized, a timer starts. If the timer expires before the circuit accepted state is reached, then the circuit is reinitialized. If the timer expires after the circuit accepted state is reached, then the timer is ignored. Initialization Sublayer: DDCMP or X.25 Page 68 7.5 Routing Layer Initialization Operation And Message Requirements The actions required of the Routing Layer Initialization in the "Routing Layer Initialization State Table" following are: 1. Issue reinitialize command to the Data Link Layer and start Recall Timer. 2. Issue stop to the Data Link Layer. 3. Send a valid Routing Layer Initialization Message. 4. Send a valid Routing Layer Verification Message. A valid Routing Layer Initialization Message has the following characteristics: o A valid Routing Layer control header with node address less than or equal to this node's NN o If this node is a level 1 router, then the neighbor's home area must match HomeArea, unless the neighbor is Phase III o If this node is a level 2 router, then the neighbor's home area must match HomeArea unless the neighbor node type is level 2 router or Phase III o A received Data Link blocksize greater than or equal to the maximum (Routing Message size of Routing Message containing NN nodes if neighbor is Phase III router, Hello Message size, 246) o An acceptable routing version (see section on Version Skew) A valid Routing Layer Verification Message has a value that agrees with the function value. 7.6 Routing Layer Initialization State Table And Diagram The following table shows all the possible state transitions from the Routing Layer's viewpoint at a single node. It also shows the events that cause the state changes and the actions the Routing Layer Initialization takes, if any, upon the occurrence of an event. The numbers in the "actions" column correspond to those in the list of actions above. Initialization Sublayer: DDCMP or X.25 Page 69 Routing Layer Initialization State Table This table shows each possible new state and action relating to the occurrence of each event in each state. The actions are shown by a slash (/) followed by the number of the action. A dash (-) signifies no action. The actions numbers are defined above. Old State RU CR DS RI RV RC OF HA Event nri CR/- CR/- DS/- * DS/1 DS/1 OF/- HA/- nrv CR/- CR/- DS/- DS/1 RC/- DS/1 OF/- HA/- rt RU/- CR/- DS/1 DS/1 DS/1 RC/- OF/- HA/- sc CR/- CR/- RI/3 DS/1 DS/1 DS/1 OF/- HA/- ste CR/- CR/- DS/1 DS/1 DS/1 DS/1 OF/- HA/- opo RU/- CR/- DS/- RI/- RV/- RC/- CR/- DS/1 opf OF/2 OF/- HA/2 HA/2 HA/2 HA/2 OF/- HA/- im CR/- CR/- DS/- DS/1 DS/1 DS/1 OF/- HA/- rc CR/- CR/- DS/- RI/- RV/- DS/1 OF/- HA/- cdc RU/- DS/1 DS/- RI/- RV/- RC/- HA/- HA/- cuc RU/- CR/- DS/- RI/- RV/- RU/- OF/- HA/- * NOTE There are four possible new state/action sets for this transition, as follows: 1. Action: 4; New state: RV; Verification requested in received message; verification required by this node. 2. Action: 4; New state: RC; Verification requested in received message; verification not required by this node. 3. Action: -; New state: RV; Verification not requested in received message; verification required by this node. 4. Action: -; New state: RC; Verification not requested in received message; verification not required by this node. Initialization Sublayer: DDCMP or X.25 Page 70 The Routing Decision Process generates circuit down events in the states CR and OF. It generates a circuit up event in the state RC. Once the Recall Timer is set, it must expire before another reinitialize command is given to the Data Link Layer. The following figure shows the Routing Layer state transitions. .---------------------------------------------------------. | | v | .---------. .----------. .-----------. | | |---------->| |---------->|