doc: Add RFC documents

1 files changed, 1235 insertions, 0 deletions

diff --git a/doc/rfc/rfc2174.txt b/doc/rfc/rfc2174.txt
new file mode 100644
index 0000000..dc4c9bb
--- /dev/null
+++ b/doc/rfc/rfc2174.txt
@@ -0,0 +1,1235 @@
+
+
+
+
+
+
+Network Working Group                                    K. Murakami
+Request for Comments: 2174                               M. Maruyama
+Category: Informational                             NTT Laboratories
+                                                           June 1997
+
+
+          A MAPOS version 1 Extension - Switch-Switch Protocol
+
+Status of this Memo
+
+   This memo provides information for the Internet community.  This memo
+   does not specify an Internet standard of any kind.  Distribution of
+   this memo is unlimited.
+
+Authors' Note
+
+   This memo documents a MAPOS (Multiple Access Protocol over SONET/SDH)
+   version 1 extension, Switch Switch Protocol which provides dynamic
+   routing for unicast, broadcast, and multicast. This document is NOT
+   the product of an IETF working group nor is it a standards track
+   document.  It has not necessarily benefited from the widespread and
+   in depth community review that standards track documents receive.
+
+Abstract
+
+   This document describes a MAPOS version 1 extension, SSP (Switch
+   Switch Protocol).  MAPOS is a multiple access protocol for
+   transmission of network-protocol packets, encapsulated in High-Level
+   Data Link Control (HDLC) frames, over SONET/SDH. In MAPOS network, a
+   SONET switch provides the multiple access capability to end nodes.
+   SSP is a protocol of Distance Vector family and provides unicast and
+   broadcast/multicast routing for multiple SONET switch environment.
+
+1. Introduction
+
+   This document describes an extension to MAPOS version 1, Switch
+   Switch Protocol, for routing both unicast and broadcast/multicast
+   frames.  MAPOS[1], Multiple Access Protocol over SONET (Synchronous
+   Optical Network) / SDH (Synchronous Digital Hierarchy) [2][3][4][5],
+   is a link layer protocol for transmission of HDLC frames over
+   SONET/SDH. A SONET switch provides the multiple access capability to
+   each node. SSP is a dynamic routing protocol designed for an
+   environment where a MAPOS network segment spans over multiple
+   switches.  It is a protocol of Distance Vector family. It provides
+   both unicast and broadcast/multicast routing. First, this document
+   describes the outline of SSP. Next, it explains unicast and
+   broadcast/multicast routing algorithms. Then, it describes the SSP
+   protocol in detail.
+
+
+
+Murakami & Maruyama          Informational                      [Page 1]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+2. Constraints in Designing SSP
+
+   SSP is a unified routing protocol supporting both unicast and
+   broadcast/multicast. The former and the latter are based on the
+   Distance Vector [6][7] and the spanning tree[8] algorithm,
+   respectively. In MAPOS version 1, a small number of switches is
+   assumed in a segment.  Thus, unlike DVMRP(Distance Vector Multicast
+   Routing Protocol)[8], TRPB(Truncated Reverse Path Broadcasting) is
+   not supported for simplicity. This means that multicast frames are
+   treated just the same as broadcast frames and are delivered to every
+   node.
+
+   In MAPOS version 1, there are two constraints regarding design of the
+   broadcast/multicast routing algorithm;
+
+     (1) there is no source address field in MAPOS HDLC frames
+
+     (2) there is no TTL(Time To Live) field in MAPOS HDLC frames to
+     prevent forwarding loop.
+
+   To cope with the first issue, VRPB(Virtual Reverse Path Broadcast)
+   algorithm is introduced. In VRPB, all broadcast and multicast frames
+   are assumed to be generated by a node under a specific switch called
+   VSS(Virtual Source Switch). VSS is the switch which has the smallest
+   switch number in a MAPOS network. Each switch determine its place in
+   the spanning tree rooted from VSS independently. Whenever a switch
+   receives a broadcast/multicast frame, it forwards the frame to all
+   upstream and downstream switches except for the one which has sent
+   the frame to the local switch.
+
+   To cope with the second issue, the forward delay timer is introduced.
+   Even if a switch finds a new VSS, it suspends forwarding for a time
+   period. This timer ensures that all the switches have a consistent
+   routing information and that they are synchronized after a topology
+   change.
+
+3. Unicast Routing in SSP
+
+   This section describes the address structure of MAPOS version 1 and
+   the SSP unicast routing based on it.
+
+
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 2]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+3.1 Address Structure of MAPOS version 1
+
+   In a multiple switch environment, a node address consists of the
+   switch number and the port number to which the node is connected. As
+   shown in Figure 1, the address length is 8 bits and the LSB is always
+   1, which indicates the end of the address field. A MSB of 0 indicates
+   a unicast address. The switch and the port number fields are
+   variable-length. In this document, a unicast address is represented
+   as "0 <switch-number> <port number>".  Note that a port number
+   includes EA bit.
+
+   MSB of 1 indicates multicast or broadcast. In the case of broadcast,
+   the address field contains all 1s (0xff in hex). In the case of
+   multicast, the remaining bits indicate a group address.  The switch
+   number field is variable-length. A multicast address is represented
+   as "1 <group address>".
+
+
+           Switch Number(variable length)
+               |
+               |      +--- Port Number
+               |      |
+               V      V
+             |<->|<------->|
+           +-------------+-+
+           | | | | | | | | |
+           | |           |1|
+           +-+-----------+-+
+            ^             ^
+            |             |
+            |             +------- EA bit (always 1)
+            |
+            1 : broadcast, multicast
+            0 : unicast
+
+                        Figure 1 Address Format
+
+   Figure 2 shows an example of a SONET LAN that consists of three
+   switches.  In this configuration, two bits of a node address are used
+   to indicate the switch number. Node N1 is connected to port
+   0x03(000011 in binary) of the switch S2 numbered 0x2.  Thus, the node
+   address is 01000011 in binary. Node N4 has an address 01101001 in
+   binary since the connected switch number is 0x3 and the port number
+   is 0x09.
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 3]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+                        01000011
+                        +------+
+                        | node |
+                        |  N1  |
+                        +------+
+           01000101         |0x03              |0x03       00101001
+           +------+     +---+----+         +---+----+      +------+
+           | node +-----+ SONET  +---------+ SONET  +------+ node |
+           |  N2  | 0x05| Switch |0x09 0x05| Switch |0x09  |  N3  |
+           +------+     |   S2   |         |   S1   |      +------+
+                        |  (0x2) |         |  (0x1) |
+                        +---+----+         +---+----+
+                            |0x07              |0x07
+                            |                  |
+                            |                  |0x03      01101001
+                            |              +---+----+     +------+
+                            +--------------+ SONET  +-----+ node |
+                                       0x05| Switch |0x09 |  N4  |
+                                           |   S3   |     +------+
+                                           |  (0x3) |
+                                           +---+----+
+                                               |0x07
+
+               Figure 2 Multiple SONET Switch Environment
+
+3.2 Forwarding Unicast Frames
+
+   Unicast frames are forwarded along the shortest path. For example, a
+   frame from node N4 destined to N1 is forwarded by switch S3 and S2.
+   These SONET switches forwards an HDLC frame based on the destination
+   switch number contained in the destination address.
+
+   Each switch keeps a routing table with entries for possible
+   destination switches. An entry contains the subnet mask, the next hop
+   to the adjacent switch along the shortest path to the destination,
+   the metric measuring the total distance to the destination, and other
+   parameters associated with the entry such as timers. For example, the
+   routing table in switch S1 will be as shown in Table 1. The metric
+   value 1 means that the destination switch is an adjacent switch. The
+   value 16 means that it is unreachable. Although the values between 17
+   and 31 also mean unreachable, they are special values utilized for
+   split horizon with poisoned reverse [8].
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 4]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+     +-------------------------+----------+--------+------------+
+     | destination |   subnet  | next hop | metric |   other    |
+     |   switch    |   mask    |   port   |        | parameters |
+     +-------------+-----------+----------+--------+------------+
+     |  01000000   | 11100000  | 00000101 |    1   |            |
+     +-------------+-----------+----------+--------+------------+
+     |  01100000   | 11100000  | 00000111 |    1   |            |
+     +-------------+-----------+----------+--------+------------+
+
+                 Table 1  An Example of a Routing Table
+
+   When a switch receives a unicast frame, it extracts the switch number
+   from the destination address. If it equals to the local switch
+   number, the frame is sent to the local node through the port
+   specified in the destination address.  Otherwise, the switch looks up
+   its routing table for a matching destination switch number by masking
+   the destination address with the corresponding subnet mask. If a
+   matching entry is found, the frame is sent to an adjacent switch
+   through the next hop port in the entry. Otherwise, it is silently
+   discarded or sent to the control processor for its error processing.
+
+3.4 Protocol Overview
+
+   This subsection describes an overview of the unicast routing protocol
+   and its algorithm.
+
+3.4.1 Route Exchange
+
+   SSP is a distance vector protocol to establish and maintain the
+   routing table. In SSP, each switch sends a routing update message to
+   every adjacent switches every FULL_UPDATE_TIME (10 seconds by
+   default). The update message is a copy of the routing table, that is,
+   routes.
+
+   When a switch receives an update message from an adjacent switch
+   through a port, it adds the cost associated with the port, usually 1,
+   to every metric value in the message. The result is a set of new
+   metrics from the receiving switch to the destination switches. Next,
+   it compares the new metrics with those of the corresponding entries
+   in the existing routing table. A smaller metric means a better route.
+   Thus, if the new metric is smaller than the existing one, the entry
+   is updated with the new metric and next hop. The next hop is the port
+   from which the update message was received. Otherwise, the entry is
+   left unchanged. If the existing next hop is the same as the new one,
+   the metric is updated regardless of the metric value.  If no
+   corresponding route is found, a new route entry is created.
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 5]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+3.4.2 Route Expiration
+
+   Assume a route to R is advertised by a neighboring switch S. If no
+   update message has been received from switch S for the period
+   FULL_UPDATE_TIME * 3 (30 seconds by default) or the route is
+   advertised with metric 16 by switch S, the route to R is marked as
+   unreachable by setting its metric to 16. In other words, the route to
+   R is kept advertised even if the route is not refreshed up-to 30
+   seconds.
+
+   To process this, each routing table entry has an EXPIRATION_TIMER (30
+   seconds by default, that is, FULL_UPDATE_TIME *3). If another switch
+   advertises a route to R, it replaces the unreachable route. Even if a
+   route is marked unreachable, the entry is kept in the routing table
+   for the period of FULL_UPDATE_TIME * 3.  This enables the switch to
+   notify its neighbors of the unreachable route by sending update
+   messages with metric 16. To process this, each routing table entry
+   has a garbage collection timer GC_TIMER (30 seconds by default). The
+   entry is deleted on expiration of the timer. Figure 3 shows this
+   transition.
+
+         The Last Update           Expiration         Garbage Collection
+               |                       |                       |
+    Routing    V   T       T       T   V   T       T       T   V
+    Table      +-------+-------+-------+-------+-------+-------X
+    Entry             metric < 16      |       metric = 16     |
+
+               ----------------------->|---------------------->|
+                   EXPIRATION_TIMER            GC_TIMER
+                                                       Stop Advertising
+                                                               |
+    Advertised                                                 V
+    Metric     --   metric <16   ------+--  metric = 16 -------X
+
+                                                    T: FULL_UPDATE_TIME
+
+                       Figure 3. Route Expiration
+
+3.4.3 Slow Convergence Prevention
+
+   To prevent slow convergence of routing information, two techniques,
+   split horizon with poisoned reverse, and triggered update are
+   employed.
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 6]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+           Sn <------------- S3 <- S2 <- S1
+
+                   (i) Before Outage
+
+                                ->
+           Sn <--    X    -- S3 <- S2 <- S1
+
+                   (ii) After Outage
+
+                Figure 4 An Example of Slow Convergence
+
+   Figure 4 shows an example of slow convergence[6]. In (i), three
+   switches, S1, S2, and S3, are assumed to have a route to Sn. In (ii),
+   the connection to Sn has disappeared because of an outage, but S2
+   continue to advertise the route since there is no means for S2 to
+   detect the outage immediately and it has the route to Sn in its
+   routing table. Thus, S3 misunderstand that S2 has the best route to
+   Sn and S2 is the next hop. This results in a transitive loop between
+   S2 and S3. S2 and S3 increments the metric of the route to Sn every
+   time they advertise the route and the loop continues until the metric
+   reaches 16. To suppress the slow convergence problem, split horizon
+   with poisoned reverse is used.
+
+   In split horizon with poisoned reverse, a route is advertised as
+   unreachable to the next hop. The metric is the received metric value
+   plus 16. For example, in Figure 4, S2 advertises the route to Sn with
+   the metric unreachable only to S3. Thus, S3 never considers that S2
+   is the next hop to Sn. This ensures fast convergence on disappearance
+   of a route.
+
+   Another technique, triggered update, forces a switch to send an
+   immediate update instead of waiting for the next periodic update when
+   a switch detects a local port failure, or when it receives a message
+   that a route has become unreachable, or that its metric has
+   increased. This makes the convergence faster.
+
+4. Broadcast/multicast Routing in SSP
+
+   This section explains VRPB algorithm and the outline of
+   broadcast/multicast routing protocol.
+
+
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 7]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+4.1 Virtual Reverse Path Broadcast/Multicast Algorithm
+
+   SSP provides broadcast/multicast routing based on a spanning tree
+   algorithm.  As described in Section 2, the routing is based on the
+   VRPB(Virtual Reverse Path Broadcast) algorithm.  In VRPB, each switch
+   assumes that all broadcast and multicast frames are generated by a
+   specific switch, VSS(Virtual Source Switch). Thus, unlike DVMRP, a
+   MAPOS network has only one spanning tree at any given time.
+
+   The frames are forwarded along the reverse path by computing the
+   shortest path from the VSS to all possible recipients.  VSS is the
+   switch which has the lowest switch number in the network.  Because
+   the routing table contains all the unicast destination addresses
+   including the switch numbers, each switch can identify the VSS
+   independently by searching for the smallest switch number in its
+   unicast routing table.
+
+   In Figure 2, switch S1 is the VSS.  Each switch determines its place
+   in the spanning tree, relative to the VSS, and which of its ports are
+   on the shortest path tree.  Thus, the spanning tree is as shown in
+   Figure 5. Except for the VSS, each switch has one upstream port and
+   zero or more downstream ports. VSS have no upstream port, since it is
+   the root of the spanning tree. In Figure 2.  switch S2's upstream
+   port is port 0x09 and it has no downstream port.
+
+                   S1 (VSS)
+                  /  \
+                 /    \
+                /      \
+               S2      S3
+
+                      Figure 5  VRPB Spanning Tree
+
+   When a switch receives a broadcast/multicast frame, it forwards the
+   frame to all of the upstream switch, the downstream switches, and the
+   directly connected nodes. However, it does not forward to the switch
+   which sent the frame to it. For that purpose, a bit mapped
+   broadcast/multicast routing table may be employed.  The
+   broadcast/multicast routing process marks all the bits corresponding
+   to the ports to which frames should be forwarded. The forwarding
+   process refers to it and broadcasts a frame to all the ports with its
+   corresponding bit marked.
+
+4.2 Forwarding Broadcast/multicast Frames
+
+   When a switch forwards a broadcast/multicast frame, (1) it first
+   decides the VSS by referring to its unicast routing table. Then, (2)
+   it refers to its broadcast/multicast routing table corresponding to
+
+
+
+Murakami & Maruyama          Informational                      [Page 8]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+   the VSS. A cache may be used to reduce the search overhead. (3) Based
+   on the routing table, the switch forwards the frame.
+
+   Figure 6 shows an example of S2's broadcast/multicast routing table
+   for the VSS S1. It is a bit map table and each bit corresponds to a
+   port. The value 1 indicates that frames should be forwarded to a node
+   or a switch through the port.  If no bit is marked, the frame is
+   silently discarded. In the example of Figure 6, port 0x09 is the
+   upstream port to its VSS, that is, S1. Other ports, ports 0x05 and
+   0x03 are path to N2 and N1 nodes, respectively.
+
+             0F  0D  0B  09  07  05  03  01   ---   port number
+           +---+---+---+---+---+---+---+---+
+           | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 |  ---   1: forward
+           +---+---+---+---+---+---+---+---+        0: inhibit
+
+            Figure 6 Broadcast/Multicast Routing Table of S2
+
+4.3 Forwarding Path Examples
+
+   Assume that a broadcast frame is generated by N2 in Figure 2. The
+   frame is received by S2.
+
+   Then, S2 passes it to all the connected nodes except for the source
+   N2. That is, only to N1. At the same time, it also forwards the frame
+   to all its upstream and downstream switches. Since S2 has no
+   downstream switch, S2 forwards the frame to S1 though its upstream
+   port 0x09.
+
+   S1 is the VSS and it passes the frame to all the local nodes, that
+   is, only to N3. Since it has no upstream switch and S2 is the switch
+   which sent the frame to S1, the frame is eventually forwarded only to
+   a downstream switch S3.
+
+   S3 passes the frame to its local node, N4. Since S3 has only an
+   upstream and the frame was received through that port, S3 does not
+   forward the frame to any switch.
+
+   The resulting path is shown in Figure 7. Although this is not the
+   optimal path, VRPB ,at least, ensures that broadcast/multicast frames
+   are delivered all the nodes without a loop. Figures 8 and 9 show the
+   forwarding path for frames generated by a node under S3 and S4,
+   respectively.
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                      [Page 9]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+                             +-> N3
+                             |
+             N2 -> S2 +-> S1 +-> S3 -> N4
+                      |
+                      +-> N1
+
+                   Figure 7  Forwarding Path from N2
+
+                             +-> N1
+                             |
+             N3 -> S1 +-> S2 +-> N2
+                      |
+                      +-> S3 --> N4
+
+                   Figure 8  Forwarding Path from N3
+
+
+                             +-> N3
+                             |
+             N4 -> S3 +-> S1 +-> S2 +-> N1
+                                    |
+                                    +-> N2
+
+                   Figure 9  Forwarding Path from N4
+
+4.4 Suppressing Routing Loop
+
+   To suppress transitive routing loop, forward delay is employed. A
+   switch suspends broadcast/multicast forwarding for a period after a
+   new VSS is found in the routing table. This prevents transitive
+   routing loop by waiting for all the switches to have the same routing
+   information and become synchronized. In addition to controlling
+   sending of frames by forward delay, another mechanism is employed to
+   prevent transitive routing loop by controlling reception of frames.
+   That is, broadcast/multicast frames received through ports other than
+   the upstream and downstream ports are discarded.
+
+4.5 Upstream Switch Discovery
+
+   The upstream port is determined by the shortest reverse path to the
+   VSS.  It is identified by referring to the next hop port of the route
+   to VSS in the local unicast routing table. When a new next hop to the
+   VSS is discovered, the bit corresponding to the old next hop port is
+   cleared, and the bit corresponding to the new one is marked as the
+   upstream port in the broadcast/multicast routing table.
+
+
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 10]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+4.6 Downstream Switch Discovery
+
+   To determine the downstream ports, split horizon with poisoned
+   reverse is employed. When a switch receives a route with a metric
+   poisoned by split horizon processing through a port as described in
+   Section 3.4.3, the port is considered to be a downstream port. In
+   Figure 2, S1 is the VSS and the route information is sent back from
+   S2 to S1 with metric unreachable based on the split horizon with
+   poisoned reverse. Thus, S1 knows that S2 is one of its downstreams.
+
+4.7 Downstream Port Expiration
+
+   When a poison reversed packet is newly received from a port, the
+   local switch knows that a new downstream switch has appeared. Then,
+   it marks the bit corresponding to the port and starts
+   FORWARD_DELAY_TIMER (30second by default, that is, FULL_UPDATE_TIME *
+   3) for the port. The forwarding of broadcast/multicast frames to the
+   port is prohibited until the timer expires.  Every time the local
+   switch receives a poison reversed packet through a port, it
+   initializes PORT_EXPIRATION_TIMER(30 seconds by default, that is,
+   FULL_UPDATE_TIME *3) corresponding to the port. A continuous loss of
+   poison reversed packets or a failure of downstream port results in
+   expiration of PORT_EXPIRATION_TIMER, and the corresponding bit is
+   cleared.
+
+               First Update               Last Update
+                   |                           |
+                   V T   T   T   T   T   T   T V
+                   +---+---+---+---+---+---+---+---+---+---+---+---+---
+   A bit in
+   the routing      0   0   0   1   1   1   1   1   1   1   0   0   0
+   table                       ^                           ^
+                    <--------->|                <--------->|
+                        ^   route up                 ^ route down
+                        |                            |
+                  FORWARD_DELAY               PORT_EXPIRATION
+
+                                           T: FULL_UPDATE_TIME
+
+                       Figure 10. Port Expiration
+
+   When a downstream switch discovers another best path to the VSS or a
+   new VSS, it stops split horizon with poison reverse and sends
+   ordinary update messages. Whenever the local switch receives an
+   ordinary update message from its downstream switch, it SHOULD
+   immediately clear the corresponding bit in the routing table and stop
+   forwarding of broadcast/multicast frames.
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 11]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+4.8 Node Discovery
+
+   When a NSP[9] packet, requesting a node address from a port, is
+   received, the local switch considers that a new node is connected,
+   and marks the corresponding bit in the broadcast/multicast routing
+   table. When the local switch detects that the port went down as
+   described in [9], it clear the corresponding bit.
+
+4.9 Invalidating The Broadcast/multicast Routing Table
+
+   When a new VSS is discovered or when the VSS becomes unreachable, the
+   entire broadcast/multicast routing table is invalidated. That is, a
+   change of upstream port affects the entire broadcast/multicast
+   routing. However, a change of a downstream port does not affect
+   forwarding to other downstream ports, its upstream port, and nodes.
+
+5. Detailed Protocol Operation
+
+   This section explains SSP packet format and protocol processing in
+   detail.
+
+5.1 Packet Format
+
+   This subsection describes the packet encapsulation in HDLC frame and
+   the packet format.
+
+5.1.1 Packet Format and Its Encapsulation
+
+   SSP packet format is designed based on RIP[6] and its successor, RIP2
+   [7]. Figure 11 shows the packet format. A SSP packet is encapsulated
+   in the information field of a MAPOS HDLC frame. The HDLC protocol
+   field of SSP is 0xFE05 in hex as defined by the "MAPOS Version 1
+   Assigned Numbers" [10]. The packet is sent encapsulated in a unicast
+   packet with the destination address 0000 0001, which indicates the
+   control processor of an adjacent switch.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 12]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+(MSB)                                                       (LSB)
+7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0 7 6 5 4 3 2 1 0
++-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ -----
+|    Command    |   Version     |           unused              |SSP header
++---------------+---------------+-------------------------------+ -----
+| Address Family Identifier     |            All 0              |
++-------------------------------+-------------------------------+
+|                         HDLC Address                          | an SSP
++---------------------------------------------------------------+ route
+|                         Subnet Mask                           | entry
++---------------------------------------------------------------+
+|                         All 0                                 |
++---------------------------------------------------------------+
+|                         Metric                                |
++---------------+---------------+-------------------------------+ ----
+| Address Family Identifier     |            All 0              |
+
+                      Figure 11 SSP packet format
+
+   The maximum packet size is 512 octet. The first four octets is the
+   SSP header. The remainder of the message is composed of 1 - 25 route
+   entries. Each entry is 20 octets long.
+
+5.1.2 SSP Header
+
+   SSP header consists of a command field and a version field. The
+   command field is one octet long and holds one of the following
+   values;
+
+     1 - request     A request to send all or part of SSP routing table.
+
+     2 - response    A message containing all, or a part of the sender's
+                     SSP routing table.  This message may be sent in
+                     response to a request, or it may be an update
+                     message generated by the sender.
+
+   The Version field indicates the version of SSP being used. The
+   current version number is 1.
+
+5.1.3 SSP Route Entries
+
+   Each entry has an address family identifier. It indicates an
+   attribute of the entry. SSP routing protocol uses 2 as its identifier
+   by default. The identifier 0 indicates unspecified. This value is
+   used when a switch requests other switches to send the entire SSP
+   routing table. A recipient of the message SHOULD ignore all entries
+   with unknown value.
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 13]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+   The HDLC address is a destination address. It may be a switch address
+   or a node address. The subsequent subnet mask is applied to the HDLC
+   address to yield the switch number portion. The field is 4 octet long
+   and the address is placed in the least significant position.
+
+   Metric indicates the distance to the destination node. That is, how
+   many switches a message must go through en route to the destination
+   node. The metric field must contain a value between 1 and 31. The
+   metric of 16 indicates that the destination is not reachable and is
+   ignored by recipients. The values between 17 and 31 are utilized for
+   poisoned reverse with split horizon and also means unreachable. The
+   metric 0 indicates the local switch itself.
+
+5.2 Routing Table
+
+   Every switch has an SSP routing table. The table is a collection of
+   route entries - one for every destination. An entry consists of the
+   following information;
+
+    (1) destination : A unicast destination address.
+
+    (2) subnet mask : A mask to extract the switch address by applying
+    bitwise AND with the destination address
+
+    (3) next hop port : The local port number connected to the adjacent
+    switch along the path to the destination.
+
+    (4) metric : Distance to the destination node. The metric of an
+    adjacent switch is 1 and that of local switch is 0.
+
+    (5) timers for unicast routing : Timers associated with unicast
+    routing such as EXPIRATION_TIMER and GC_TIMER.
+
+    (6) flags : Various flags associated with the route such as route
+    change flag to indicate that the route has changed recently or it
+    has timed out.
+
+    (7) bit map routing table for broadcast/multicast : Each bit
+    corresponding to the port to an upstream or a downstream switch of
+    the spanning tree is marked in addition to the ports to end nodes.
+    Broadcast/multicast frames are forwarded only through those ports
+    with their corresponding bit set. Since only one spanning tree
+    exists at a time in a network, each route entry does not necessarily
+    have to have this field.
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 14]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+    (8) timers for broadcast/multicast routing : Timers associated with
+    broadcast/multicast routing such as FORWARD_DELAY_TIMER and
+    PORT_EXPIRATION_TIMER. These timers are prepared for each bit of
+    broadcast/multicast routing table.
+
+5.3 Sending Routing Messages
+
+5.3.1 Packet Construction
+
+   Because of the split horizon with poisoned reverse, a routing message
+   differs depending on the adjacent switch to which the message is
+   being sent. The upstream switch of a route, that is next hop,
+   receives a message which contains the corresponding route with a
+   metric between 17 and 31. Switches that are not the upstream switch
+   of any route receive the same message. Here, we assume that a packet
+   for a routing message is constructed for an adjacent switch which is
+   connected through the local port N.
+
+   First, set the version field to 1, the current SSP version. Then, set
+   the command to "response". Set other fields which are supposed to be
+   zero to zero.  Next, start filling in entries.
+
+   To fill in the entries, perform the following for each route. The
+   destination HDLC address, netmask, and its metric are put into the
+   entry in the packet.  Routes must be included in the packet even if
+   their metrics are unreachable(16).  If the next hop port is N, 16 is
+   added to the metric for split horizon with poisoned reverse.
+
+   Recall that the maximum packet size is 512 bytes.  When there is no
+   more space in a packet, send the current message and start a new one.
+   If a triggered update is being generated, only entries whose route
+   change flags are set need be included.
+
+5.3.2 Sending update
+
+   Sending update may be triggered in any of the following ways;
+
+    (1) Initial Update
+
+    When a switch first comes up, it SHOULD send to all adjacent
+    switches a request asking for their entire routing tables. The
+    destination address is 00000001. When a port comes on-line, the
+    request packet is sent to the port. The packet, requesting the
+    entire routing table, MUST have at least an entry with the address
+    family identifier 0 meaning unspecified.
+
+    When a switch receives a request packet, it first checks the version
+    number of the SSP header. If it is not 1, the packet is silently
+
+
+
+Murakami & Maruyama          Informational                     [Page 15]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+    discarded. Otherwise, the address family identifier is examined.  If
+    the value is 0, the entire SSP routing table is returned in one or
+    more response packets destined to 00000001. Otherwise, the request
+    is silently discarded.  Although the original RIP specification
+    defines the partial routing table request, SSP routing protocol
+    omits it for the sake of simplicity.
+
+    (2) Periodic Update
+
+    Every switch participating in the routing process sends an update
+    message (response message) to all its neighbor switches once every
+    FULL_UPDATE_TIME (10 seconds). For the periodic update, a response
+    packet(s) is used. The destination address is always 00000001. An
+    update message contains the entire SSP routing table. The maximum
+    packet size is 512byte. Thus, an update message may require several
+    packets to be packed.
+
+    (3) Triggered Update
+
+    When a route in the unicast routing table is changed or a local port
+    goes down, the switch advertises a triggered update packet without
+    waiting for the full update time. The difference between triggered
+    update and the other update is that triggered updates do not have to
+    include the entire routing table. Only changed entries should be
+    included. Triggered update may be suppressed if a regular periodic
+    update is due.
+
+    Note that when a route is advertised as unreachable (metric 16) by
+    an adjacent switch, update process is triggered as well as
+    expiration of the route in the local switch.
+
+    (4) On Termination
+
+    When a switch goes down, it is desirable to advertise all the routes
+    with metric 16, that is, unreachable.
+
+5.4 Receiving Routing Messages
+
+   When a switch receives an update, it first checks the version number.
+   If it is not 1, the update packet is silently discarded. Otherwise,
+   it processes the entries in it one by one.
+
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 16]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+   For each entry, the address family identifier is checked. If it is
+   not 2, the entry is ignored. Otherwise, the metric is checked. The
+   value should be between 0 and 31.  An entry with illegal metric is
+   ignored. Next, the HDLC address and the subnet mask is checked. An
+   entry with an invalid address such as broadcast is ignored. If the
+   entry passed all these validation checks, it is processed according
+   to the following steps;
+
+   Step 1 - Process Poisoned Reverse
+
+   If the metric value is between 0 and 16, it is an unicast
+   information. Go ahead to Step 2.
+
+   If the metric value is between 17 and 31, it indicates poisoned
+   reverse, that the local switch has been chosen as the next hop for
+   the route. However, if the corresponding entry is not included in the
+   current routing table or the message is from a port connected to its
+   upstream switch, the message is illegal -- ignore it and return to
+   Step 1 to process the next entry. Otherwise,
+
+
+      (1) Initialize the PORT_EXPIRATION_TIMER corresponding to the
+          downstream port.
+      (2) Operate the FORWARD_DELAY_TIMER as follows;
+          (2-1) If the broadcast/multicast forwarding was already
+                enabled, go to (3).
+          (2-2) If the FORWARD_DELAY_TIMER corresponding to the
+                downstream port was already started, increment the
+                timer. If the timer expires, mark the bit in the
+                broadcast/multicast routing table corresponding to the
+                port and stop the timer.
+          (2-2) Otherwise, start the FORWARD_DELAY_TIMER.
+      (3) Return to Step 1 to process the next entry.
+
+    Step 2 - Process Unicast Routing Information
+
+    First, add the cost associated with the link, usually 1, to the
+    metric. If the result is greater than 16, 16 is used. Then, look up
+    the unicast routing table for the corresponding entry. There are two
+    cases.
+
+     Case 1  no corresponding entry is found
+
+       If the new metric is 16, return to step 1 to process the next
+       entry.  Otherwise,
+       (1) Create a new route entry in the routing table
+       (2) Initialize EXPIRATION_TIMER and GC_TIMER
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 17]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+       (3) The port corresponding to the new route is the next_hop port
+           for the route. Thus, mark the bit in the broadcast/multicast
+           routing table corresponding to the new next_hop port and
+           start FORWARD_DELAY_TIMER. If this new route is for the
+           switch with the minimum switch number, select it as the VSS
+           and use its broadcast/multicast routing table. (See NOTE 1.)
+       (4) Set the route change flag and invoke triggered update process
+       (5) Return to step 1 to process the next entry.
+
+           [NOTE 1]
+             There are two implementations;
+              (1) Prepare a spanning tree for each route and use
+                  only one corresponding to the current VSS. In this
+                  case, each unicast route entry has a broadcast/unicast
+                  routing table.
+              (2) Prepare only one spanning tree corresponding to the
+                  current VSS. In this case, a switch has only one
+                  broadcast/multicast routing table.
+              In this document, the former is assumed.
+
+      Case 2. A corresponding entry is found
+
+       In this case, the update message is processed differently
+       according to the new metric value.
+
+       (a) new_metric < 16 & new_metric > current_metric
+
+          (1)If and only if the update is from the same port(next_hop
+             port) as the existing one,
+            (1-1) Update the entry
+            (1-2) Initialize EXPIRATION_TIMER and GC_TIMER
+
+          (2) If the corresponding bit to the port, which the update
+              message is received, is marked in the broadcast/multicast
+              routing table, clear the bit.
+          (3) Return to Step 1 and process the next entry.
+
+       (b) new_metric < 16 & new_metric < current_metric
+
+          (1) Update the entry and clear the bit in the
+              broadcast/multicast routing table corresponding to the old
+              next_hop port.
+          (2) Initialize EXPIRATION_TIMER, GC_TIMER, and
+              PORT_EXPIRATION_TIMER for the new next_hop port.
+          (3) Mark a bit in the broadcast/multicast routing table
+              corresponding to the new next_hop port and start
+              FORWARD_DELAY_TIMER.
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 18]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+          (4) Set the route change flag and invoke triggered update with
+              poisoned reverse for the new next_hop.
+          (5) Return to Step 1 to process the next entry.
+
+       (c) new_metric < 16 & new_metric = current_metric
+
+          If a new route with the same metric value as the existing
+          routing table entry is received, use the old one as follows;
+
+          (1) If the new next hop is equal to the current one,
+              initialize EXPIRATION_TIMER and GC_TIMER. Otherwise,
+              ignore this update.
+          (2) If the bit corresponding to the port, from which the
+              update message was received, is marked in the
+              broadcast/multicast routing table, clear the bit.
+          (3) Return to Step 1 to process the next entry.
+
+       (d) the new metric = 16 & the new next hop = the current one
+
+          If the current metric is not equal to 16, this is a new
+          unreachable information. Then,
+          (1) Update the entry and clear the bit in the
+              broadcast/multicast routing table corresponding to the old
+              next_hop port.
+          (2) If this route is for the current VSS, select a new VSS in
+              the valid routing table entries. Valid means that the
+              destination is reachable.
+          (3) Set the route change flag and invoke triggered update
+              process to notify the unreachable route.
+          Otherwise,
+              do nothing and return to Step 1 to process the next entry.
+
+       (e) the new metric = 16 & the new next hop /= the current one
+
+          (1) If the bit corresponding to the port, from which the
+              update message was received, is marked in the
+              broadcast/multicast routing table, clear the bit.
+          (2) Return to Step 1 to process the next entry.
+
+
+
+
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 19]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+5.5 Timers
+
+   The timer routine increments the following timers and executes its
+   associated process on their expiration.
+
+    (1) EXPIRATION_TIMER and GC_TIMER
+
+    The EXPIRATION_TIMERs and GC_TIMERs of each entry in the unicast
+    routing table are incremented every FULL_UPDATE_TIME (10 seconds by
+    default). When a EXPIRATION_TIMER expires, the metric is changed to
+    unreachable(16), update process is triggered, and GC_TIMER is
+    started. When a GC_TIMER expires, the entry is deleted from the
+    local routing table. EXPIRATION_TIMER and GC_TIMER are cleared every
+    time a switch receives a routing update.
+
+    (2) FORWARD_DELAY_TIMER
+
+    FORWARD_DELAY_TIMER is completely handled in the receive process and
+    has no relation to the timer routine.
+
+    (3) PORT_EXPIRATION_TIMER
+
+    PORT_EXPIRATION_TIMERs associated with each bit in the
+    broadcast/multicast routing table are incremented every
+    FULL_UPDATE_TIME (10 seconds by default).  When the timer expires,
+    the corresponding downstream switch is considered to be down and the
+    corresponding bit in the broadcast/multicast routing table is
+    cleared. This timer is cleared by the receive process every time a
+    poisoned reverse packet is received from the corresponding switch.
+
+6. Further considerations on implementation
+
+6.1 Port State
+
+   A switch assumes that every port is connected to a switch initially.
+   Thus, it sends update packets to every port. When a node is connected
+   to a port, the switch recognizes it by receiving an NSP request
+   packet, and stops sending SSP packets to the port. Whenever a switch
+   detects a connection failure such as loss of signal and out-of-
+   synchronization, it should clear the internal state table
+   corresponding of the port.
+
+6.2 Half way connection problem
+
+   A port consists of two channels, transmit and receive. Although it is
+   easy for a node or a switch to detect a receive channel failure,
+   transmit channel failure may not be detected, causing half way
+   connection.  This results in a black hole.
+
+
+
+Murakami & Maruyama          Informational                     [Page 20]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+   Thus, whenever a switch receives a SSP update packet from a port, it
+   SHOULD check the status of the corresponding transmit channel.
+   SONET/SDH has a feedback mechanism for that purpose. The status of
+   the local transmit channel received at the remote end can be sent
+   back utilizing the overhead part, FEBE(Far End Block Error) and
+   FERF(Far End Receive Failure), of the corresponding receive channel.
+   If the signals indicates that the transmit channel has a problem, the
+   SSP packet received from the remote end should be silently discarded.
+   However, some SONET/SDH services do not provide path overhead
+   transparency.
+
+   Although, SONET/SDH APS(Automatic Protection Switching) can be
+   utilized to switch service from a failed line to a spare line, the
+   function is out of scope of this protocol.
+
+7. Security Considerations
+
+   Security issues are not discussed in this memo.
+
+References
+
+   [1]   Murakami, K. and M. Maruyama, "MAPOS - Multiple Access Protocol
+         over SONET/SDH Version 1," RFC2171, June 1997.
+
+   [2]   CCITT Recommendation G.707: Synchronous Digital Hierarchy Bit
+         Rates, 1990.
+
+   [3]   CCITT Recommendation G.708: Network Node Interface for
+         Synchronous Digital Hierarchy, 1990.
+
+   [4]   CCITT Recommendation G.709: Synchronous Multiplexing Structure,
+         1990.
+
+   [5]   American National Standard for Telecommunications - Digital
+         Hierarchy - Optical Interface Rates and Formats Specification,
+         ANSI T1.105-1991.
+
+   [6]   Hedrick, C., "Routing Information Protocol", STD 34, RFC 1058,
+         Rutgers University, June 1988.
+
+   [7]   Malkin, G., "RIP Version 2 - Carrying Additional Information ",
+         RFC1723, Xylogics, Inc., November 1994.
+
+   [8]   Pusateri, T., "Distance Vector Multicast Routing Protocol",
+         September 1996, Work in Progress.
+
+   [9]   Murakami, K. and M. Maruyama, "A MAPOS version 1 Extension -
+         Node Switch Protocol," RFC2173, June 1997.
+
+
+
+Murakami & Maruyama          Informational                     [Page 21]
+
+RFC 2174                         MAPOS                         June 1997
+
+
+   [10]  Maruyama, M. and K. Murakami, "MAPOS Version 1 Assigned
+         Numbers," RFC2172, June 1997.
+
+Acknowledgements
+
+   The authors would like to acknowledge the contributions and
+   thoughtful suggestions of John P. Mullaney, Clark Bremer, Masayuki
+   Kobayashi, Paul Francis, Toshiaki Yoshida, Takahiro Sajima, and
+   Satoru Yagi.
+
+Authors' Address
+
+             Ken Murakami
+             NTT Software Laboratories
+             3-9-11, Midori-cho
+             Musashino-shi
+             Tokyo 180, Japan
+             E-mail: murakami@ntt-20.ecl.net
+
+             Mitsuru Maruyama
+             NTT Software Laboratories
+             3-9-11, Midori-cho
+             Musashino-shi
+             Tokyo 180, Japan
+             E-mail: mitsuru@ntt-20.ecl.net
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Murakami & Maruyama          Informational                     [Page 22]
+