JPH03139935A - Distributed carrier switching system - Google Patents

Abstract

PURPOSE:To make it possible to use an object other than serial digital data also as an object to be transmitted by sending request information of call information always together with a call request command and sending an object always together with a retention request command. CONSTITUTION:When the input commands of two ports are retention request, object transfer is allowed between the two ports, and when a release request command is inputted to at least one of the two ports, the release request commands are outputted from both ports to release both ports. A link transfers a command, call information and an object logically independently, request information in the call information is sent always together with a call request command and the object is sent always together with a retention request command. Consequently, a communication signal such as parallel digital and analog signals can be transmitted in addition to a serial digital signal and these signals can be switched.

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to a distributed transport switching system, and more particularly to a distributed transport switching system with independent control.

[Prior art] Distributed transport and exchange systems are conventionally known, for example, as disclosed in Japanese Patent Application Laid-Open No.
There is a ladder network method described in 043:19.

This is a grid-like communication network based on the analogy of biological nerve cells. More specifically, a communication network is constructed by connecting communication control elements for a large number of car output signals as nodes in a multi-connection structure, and each node transfers digital signals on a first-come, first-served basis. . A document that logically explains this is Takashi Yano et al., "Proposal of Local Area Network C: OMLAT Based on Multi-Connection Topology," Institute of Electronics and Communication Engineers Technical Report 5E86-69, No. 31-3.
6 pages + 1986), and Fouad A, T
obagi ”MultiaccessLink C
ontrol, + in Computer Ne
work Architect, ures and
Projocols, -Edited by Gre
en, P, E,, Jr,, Plenum Pre
ss, New York.

1982, pp. 145-189, the ALOHA system and the C5MA system are described in detail.

[Problem to be solved by the invention 1 However, these prior art systems.

The objects of transmission and exchange were limited to serial digital signals. In other words, it is not possible to transmit or exchange communication signals such as parallel digital signals or analog signals, or even objects such as gases, bodies, solids, etc. In this book, the communication signals and objects that must be transmitted and exchanged are collectively referred to as "objects".
It is called.

The present invention overcomes these drawbacks of the prior art.

The object of the present invention is to provide a distributed transport and switching system capable of transmitting and exchanging not only serial digital signals but also general objects.

The present invention is based on the conventional [1, A N
By expanding and generalizing what was previously called ``J'', we have developed an independent control distributed transport and switching system J (Distribu
tedCarrier Switching Sy
stem an IndependenLCont
rol, hereinafter referred to as DC3S/IC. ) is for building.

One of the objects of the present invention is to provide a method that allows objects other than serial digital data to be transferred. By expanding it, it can handle parallel digital signals, analog signals, and even the movement of objects, that is, logistics.

Another object of the present invention is to reduce the link cost by using m-direction (Simplexl) or half-duplex (l (alfDu)).
p16) (It is possible to apply l. This makes it possible to reduce the link cost.

A further object of the invention is to provide a common channel fcommon channel system for exchanging information regarding connection procedures.
The purpose of this invention is to enable the application of the Signaling System. This makes it possible to further reduce link costs.

[Means and Effects for Solving the Problems 1] In the distributed carrier switching system according to the present invention, in a network including nodes, a plurality of stations, and links connecting nodes and stations or nodes and through which objects are transferred,
The object includes at least one of a serial or parallel digital signal, an analog signal, and an object, and the station performs release procedures for the link, at least one of call origination and call termination procedures for the network, and the object in the network. The station has a transfer mode, outputs a release request command to the station's port, and then
When a release request command is input on a port, the link on the port of the station is confirmed to be released, and if the release request command is input while the station is not in the process of calling, the link on the port of the station is confirmed to be released. , the node has at least two ports, performs a release procedure, an attach procedure, and a transport path exchange including t4 If the link of port L is released, a call request command is immediately output to the port with a predetermined probability, a call is made by sending request information including at least the called station address, and the call is made in the mini-slot. If you didn't.

Repeat the calling procedure in the next mini-slot.

If the link has not been released, the call procedure will be performed until it is released, and if a call response command is input within a predetermined period, it will shift to object transfer mode,
If the call response command is not input within the predetermined period, the output of the call request command is stopped, the release request command is output, and the call procedure is repeated again, and the release request command is input during the call procedure. In object transfer mode, the station outputs a maintain request command to the port of the station, and when the maintain request command is input to the port, it is possible to transfer one object to the port. When the input of a release request is detected during object transfer mode, the release procedure is entered, and thereafter, object transfer is not performed unless the node enters object transfer mode again, and the node performs the release procedure in the connection procedure. When it finds the desired port, it outputs a release request command to the port, and then confirms that the link of the second port of the node is released by inputting the release request command on the port, and issues a call request command. The node performs a release procedure for the ports to which the release request command is input, except for the output baud 1-, and in the connection procedure, when the call request command and accompanying request information are input to that node, the node The call request command and request information are relayed to each free port corresponding to the link confirmed to be released. At this time, if there are multiple call request commands, the call request command that arrived first is output. Each node performs the connection procedure independently and relays and outputs the call request command; The node that received the call response command relays the call response command to the port to which the call request command input arrived first, and outputs the call response command to the port to which the call request command input arrived first, to the port to which the call response command input arrived first, and to the port to which the call response command input arrived first. is maintained thereafter, and the node that allows object transfer and receives the call response command selects one of the ports that relayed the call request.
Output a release request command from a port for which there was no call response command, a port for which there was a call response command but was not the first to arrive, and a port for which the call request command was not for the first arrival, perform release procedures for these ports, In the maintenance operation, the node connects the two ports for which the connection procedure has been completed and can now be maintained by outputting each input to the other port. When the input command is a maintenance request, object transfer is allowed between the two ports, and when a release request command is input to at least one of the two ports, the object is released from the empty port. A request command is output, a release procedure is performed for both ports, and the link transfers commands, call information, and objects logically independently, and for call information, request information always accompanies the call request command. The object is always sent along with a maintenance request command.

During the calling procedure of the station, at any time or when the station confirms that the link on the port is released, it outputs a call request command to the port and sends out request information including at least the called station address. When a call response command is input within a predetermined period, the system enters object transfer mode; if a call response command is not input within a predetermined period, it enters backoff; When entering bank-off, output of call request command is stopped, release request command is output, and back-off is started! ! The length of one period is random, and the calling procedure may be performed again after the period has elapsed.

[Embodiment] Next, an embodiment of the distributed transport exchange system according to the present invention will be described in detail with reference to the accompanying drawings.

Introduction Chapter 1 describes the basic principles of the generalized DC3S/IC. Multi-coupling 1 - The @Keys of LAN by Bology It will be easy to understand if you are familiar with the expansion of the target of transfer to general objects, and the introduction of the (somewhat abstracted) concept of commands. , which is characterized by the introduction of the concept of call information and the separation of information exchange related to connection procedures from objects.For important concepts (terminology), please refer to the glossary at the end.

In Chapter 2, DC3S/I (1: In order to theoretically analyze the phenomenon related to unique calls, we propose the ``ignition model J,''
Until now, various phenomena have been derived as theorems, and there has been no theoretical support regarding the optimality of calling, such as in the above-mentioned literature by Fengshi Yano et al., ``Proposal of local area network COMLAT using multi-connection topology.'' However, this mathematical model, which will be substantiated for the first time, is based on graph theory, but only the basic knowledge of graph theory is required to understand it. Note that there are various ways of using terms in graph theory, but here we will use the above-mentioned R
, G., Busacker, T.L., 5aat
y, ”Finite Graphsand Ne
works: An Introduct, io
n with Applica-tions,”
lJcGraw-11i11.1965. ” (translation: Kentabu Yano et al. [Graph Theory and Networks/Fundamentals and Applications] Baifukan, 1970).

Chapter 3 describes the time constants included in DC:SS/IC as a system. This shows that in principle there is no need to define multiple time constants.6 Chapter 4, which is related to Chapter 5, describes the single-way and double-direction object transfer paths from an economic standpoint.

Chapter 5 briefly describes possible implementations as variations on the basic principle.

Table L 1] Distributed transport exchange system with independent control 1Dcss/rc
) is a kind of distributed control switching system in which a large number of small-scale nodes each having a transport path switching function are arranged to perform a large-scale switching function as a whole network.

A network has one or more (mutually independent) nodes,
Two or more stations, two or more links connecting nodes and stations (where one station is connected to a node by one link), and connecting nodes Consists of 0 or more links. There may be multiple links between any two nodes.8 Each port of a node is connected by a link (at least logically independent of each other) to a port or station of another node. Alternatively, it is not connected to anything and is appropriately terminated. In the latter case, it is assumed that the port does not exist in the first place.

The topology of the network is not particularly limited as long as it satisfies the above two principles.

The station has the release procedure 1 call/termination procedure and object transfer function, but a special station may be one that lacks either the call procedure function or the called terminal VT function.

LL±”υ駈±1 After the station outputs a release request to a port, confirm that release requests continue to be input on that port. A link is said to be released when release requests flow in both directions.

During the call origination procedure, a station that receives an unspecified release request takes the release procedure.

LmuLmatamutotyu When a station outputs a call request, it is called a call origination.

The calling method is basically the same as ALOHA or C3MA.

As an example, if the link (port L of that station) fails to open at the beginning of a certain minislot, then the link (p-persisLent C5
MA type) Makes a call request and sends request information. If the call is not made in that minislot, repeat the process in the next minislot; if the link is not free, wait until it is released and apply the above process. The request information consists of a preamble (not essential depending on the implementation method), and a called station address; sending the calling station address and control information is optional.

When a call response is input, the two stations are connected to each other,
Object transfer is now possible. However, are you sure that it is not a misconnection? ! It is optional for the called side to send address information, control information, etc. as response information and for the calling side to confirm this. In the case of an error, the release procedure begins.

When the calling procedure fails, that is, within a certain fixed time (e.g., twice the maximum propagation delay time τ),
If t and H are not input, the release procedure is entered and the above calling procedure is repeated.

As another example, at any time (for ALOHA 11) or after ensuring that the connected link is released (1-persistent (:S&lA
4), requests a call and sends the request information.The request information includes: ・Preamble and (this is not required depending on the implementation method)
, ・Consists of the called station address. Note that sending the calling station address and control information is optional.

When a call response is input, the two stations are connected to each other,
Object transfer is now possible. However, in order to confirm that it is not an erroneous connection, it is optional for the calling party to send address information, control information, etc. as response information from the called II+ and to confirm this on the calling side. In case of error, a release procedure or backoff is entered.

If a call response is not input within a certain specified time (for example, twice the maximum propagation delay time? (2i = +1), backoff is entered. When backoff is entered (call request output is stopped). ) outputs a release request.

The backoff time is random, and the method is the same as normal (:SMA and ALOIIA).

This command is ignored even if a release request is input during the call procedure.

When a call request is input to the ``Shiyu'', ``Nimame'', and LL station, and there is an incoming call, detection of the called station address in the request information is started.

When the own station address is detected, a call response is performed, and objects can then be transferred between the two stations. (Object transfer mode) However, it is optional to send address information, control information, etc. as response information to the calling station to confirm that there is no erroneous connection. A release request is input from a calling station, and the called station that receives this command enters a release procedure.

If the own station address is not detected, the release procedure begins. When a release request input is detected, the release procedure begins.

1.2.4 Object Transfer A station outputs a maintenance request command to its port, and when the maintenance request command is input to that port, it enables object transfer at that port. This is called object transfer mode. At this time, mutual object transfer is possible between the two stations.

When an input of a release request is detected, the release procedure begins. Thereafter, one object transfer cannot be performed unless the object transfer mode is entered again.

1.3. Node A node has multiple ports and itself has a transport path switching function. From the perspective of the entire network, it performs a partial transport route switching function. The transport path exchange function consists of release procedures, connection procedures, and maintenance.

When an L-bound node finds a certain port that should undergo a release procedure, it outputs a release request to that port and confirms that release requests continue to be input on that port. Once confirmed, the link connected to that port is said to be released.

A release procedure is performed on ports to which a release request is input, except for ports outputting (relay) call requests.

When a node has at least one call request, a port on that node whose link is released is called an empty port, and the call request (and associated request information) is input to the node. When the call request is received, the node relays the call request and request information to the empty port. At this time,? ! If there are several call requests.

The request information of the port that received the first call request is relayed and output.

Each node performs this procedure independently.

Each node does not distinguish whether the port is connected to a station or another node (through a link), so when a call is made from one station, a port that can relay the call request is As long as there is a call request (relayed and output) inputted to all nodes and stations via the shortest route at that time.

This is a limited broadcast since the call will arrive at all stations as long as there is a route (stations already in object transfer mode do not have a route). Here, it is simply called broadcast.

The node that relayed the call request waits for an ay response to be input to the port that relayed the call request.

The node that has responded to the call relays the call response and the accompanying response information to the port to which the call request input arrived first. Response information is not essential here.

1.2.2. calling procedures, and 1.2.3. See section on incoming call procedures.

If a node receives multiple call responses, the port that received the first call response is advanced, and the response information of that port is relayed and output. The port to which the call request input arrived first and the port to which the call reception input arrived first are maintained thereafter, and object transfer becomes possible.

・The node that received the call response releases the ports from which there was no call response among the ports that relayed the call request, the port that was not the first to arrive, and the port from which the call request was not the first to arrive. Output the request.

Connection is made by outputting each input to the other port for the two ports that can be maintained after the L-uni 1-week connection procedure has been completed. It outputs commands to ports, one call information input outputs call information to the other port, and one object input outputs objects to the other port.

When the input command of these two ports is a maintenance request, object transfer is possible between these two ports.

When a release request is input to at least one port, release requests are output from both ports, and release procedures are performed for both ports. With two maintained ports as a set, a plurality of mutually independent sets are present on one node at the same time.

1.4. Link A link has a bidirectional transfer function for commands (release request, call request, call response, maintenance request), call information (request information, response information), and objects.

It is sufficient if these commands, call information, and object convexities can be transferred logically independently. However, in reality, there are many impossible combinations and there are restrictions on chronological combinations, so by breaking this independence to a certain extent to avoid contradictions, it is possible to greatly simplify the link Is construction. can.

Only one of the four commands can be taken at a time in one direction. Therefore, this command can be encoded in one example.

Regarding call information, request information is always sent with a call request, and response information is always sent at 1V with a call response.

Objects are always sent with maintenance requests. The form of an object is not particularly defined in principle; an object is data in the field of telecommunications. In the field of logistics, it is an object such as gas, liquid, or solid.

The data may be parallel channels or analog signals, not necessarily digital signals passing through one serial channel.

In the logistics example, the objects are the delivery of various types of fuel. Possible options include pipeline networks and belt conveyor networks. or.

It may also be something like a slip or an air shooter for transferring small documents, but these are only defined by the specific way links and nodes are created.

Here, we clarify the phenomenon peculiar to call origination and call reception in DC3S/iG based on the firing model. One direction of the link through which the call request (command) flows is treated as an arc along that direction, and the station's call is treated as a spontaneous firing of the vertex, and the call request is input to the node or station. Treated as non-spontaneous firing of the vertex.

In this chapter, let V = (1, 2, -, n) be a finite set of vertices, and let E be a finite set of arcs (i, j) going from m point iEV to r1 point jεV.

Regarding graph theory itself, which deals with (finite) directed graphs p = cv, E), see the literature mentioned in nn and Takasuke Hamada et al., ``Graph Theory Summary'', Maki Shoten, 1982.

Mumuni gohikima Definition l.

A 1-directed graph T = (V, A) is a Rooted Directed Tree on the vertex rEV if T satisfies the following two conditions, (where A
is a set of arcs. ) (I)wεV-(rl, for all r pixels W,
There is no 6 (11) circuit (Cycle) in which there is only one simple path from r to W (that is, a path consisting of 11 different points).

However, the graph T = ((r)
, φ) is considered a directed book.

This rI point r is especially called the root (Rootl).In this chapter, it is assumed that there is no arc toward the root r, but this does not cause any loss of generality; in other words,
If we reverse the direction of all the arcs.

It can be made so that there is no arc coming out from the root r.

Lemma l.

The fact that the graph T=(V, A> is a directed book on the vertex rEV is equivalent to the following three conditions.

(1) T is concatenation.

(I+ > For any EV, there exists exactly - rEV such that (k, r)gA. When V consists of one vertex, V = (r) and A = φ. .

(III) When V consists of two or more vertices, (
Regarding the 100 points wEV, (w #r) of the sign.

(k, w) E A , k s w ,
There is only one arc (k, w) such that k E:V.

Proof If T is a directed book on r, then there is a path determined by the root r and any other vertex WθV, so it is a connection (condition ①).

Now, any (7) kEV+,: about (k, r) e'A
Assume that there is no rEV such that . Then.

k such that (k, r)EA for any rEV
E V hS exists, and if we take (root) r in Definition 1 as r, there is a path from r to k, so from r passing through k, r
A circuit returns to , and if T is a directed book on r, then
Contrary to Etl. Therefore, for any kEV (k,
r) There is at least one rEV such that gA.

Now, for any kEV (k, r')9! Another r EV like A
If , then there exists a path from r to ro from the constant Jul. Since there is no arc with ro as the terminal vertex, this path clearly does not exist, and therefore ro cannot exist. Therefore, 100 points rEV such that (k, r) gA
must be unique (condition II).

If a certain r pixel wEV excluding r has two or more (one) vertices other than W u ) + u 2 g..., u
Arc from p (u + I W) + (ut, W
) t "-"' (U,,W), then define l to r to U, r to 11□
There are paths from r to U, respectively. That is, the path from r to W is u + + Ll 2
+...There are two or more (one) items that go through tup, which is contrary to the fact that tup is a directed book.

Therefore, any m point wEV except r is (k, w)EA
.

connected by only one arc (k, w) such that k#w, kEV (condition II+).

Conversely, a case will be described in which conditions (I), (II), and (I) hold.

Now, let T' be a subgraph of T consisting only of root r.

Also, T'= (V', A'l is T'-'(7) supergraph (D'-1 is a subgraph of T'), and y l
A subgraph of D such that Ao is the set of all arcs in cT with at least one endpoint being each vertex of -1, and V' is the set of all endpoints of each arc in A. Suppose that Since T is connected (condition I), T
'' converges to T.

T″ is clearly a directed tree above the constant Ml.

Now, assuming that TI is a directed book on r, it is sufficient to show that TI″1 is a directed book on rl.

From the assumption, any vertex wEV"'-V' is an arc (k,w)EA"'-A' from some vertex KEV' or/and an arc (w,k)EA"'-A' to k By the way, from the condition (Ill), there already exists an arc toward k for all the points kEV' other than r, so there can be no arc (w, k).

Furthermore, the arc to any vertex W is unique under the same conditions.

Therefore, any vertex WεVi+IQ+ has no circuit at 6T′, which is connected to a certain vertex by the only arc (k, w) from εV°, and therefore no circuit exists at T″11.

There is only one path from r to any other vertex UεV', and any vertex wEV'1-V' is connected by a unique arc (U, W) from a certain uEV. Therefore, there is only one path from the root r to any W, and T + f) l is r
This is a directed book.

A new operation called firing is defined for the call origination/call reception phenomenon in the L-input DC3S/rC, and the nature of this phenomenon is clarified.

Definition 2: Valid graph D = (V, E) is not fired if it satisfies the following four conditions.

(1) D is a concatenation.

(II) D is 6 without loops, i.e. all iEs
With respect to V, (i, i) 〆E. When (2) consists of one m point, E=φ.

(Ill) Any arc (i, j) EE, (i, jEV.

There is only one arc (, j, 1) EE for i #j). Here, the length (time) of the arc from i to j is.

(i, j)>O.

(IV) Every vertex, each arc of all C, is in the unfired state out of two possible states (fired/unfired).

Definition 3゜Unfired digraph D = Directed graph with (V, E) as initial value F = (V, A) + stuck I, here F
The set A of arcs is a function IQA=Aftl of time t, and its initial value is A (0)=E. ``firing of the rTR point with respect to F'' is defined as follows. This operation of "firing a vertex" is a transformation from E to A to obtain a fired F by removing a part of the set E of arcs of D from an unfired state. Note that this also refers to the ``ignition of the arc'', but in this case, it is simply the ``ignition of the rri point'' including both sides.
It is called.

(1) Each dot can ignite spontaneously.

When r1 point rEV fires spontaneously at time tr≧0, at the same time all arcs (r, w)E with r as the starting point Ta
A (t, 1. (r; ew6V) is fired, r
All arcs (w', r) EA(trl
, (r≠w' EV) from A.

(I!) If the vertex kEV fires involuntarily at time t〉0, then all arcs (k, w) fire simultaneously with the firing of k.
E: A (tJ, (k≠wEV) is fired, and at the same time all arcs (w, k) EA (tk
Remove l from A. Note that if (k, w) KA (t-1), (w, k) is not removed.

(Ill) When the vertex wEV is not firing, (k, w
)EA, the vertex kEv, (k≠W) fires, and then the arc (
k, w) Through the firing of EA, the vertex W can know the firing of the arc (k, w) and the vertex after fi, j1 time. An arbitrary vertex WθV that has not yet fired is a certain arc (k,,wl, (k2.w), ......, (k,
, w) is known at time Lw', (k,, Ki, . . .,) = V' EV and Zult (Each r1 point of V' has already fired at this point. )
, any one arc (k, w) EA (t,,') among those arcs that fired within a finite time.

All arcs other than kεV゛(k',w)EA(t,'),to≠'EV'
is removed from the set of arcs A, and after removal, the vertex W within a finite time
(spontaneously) to ignite.

The meaning of the definition j112.3 is as follows.

An unfired graph corresponds to a network consisting of a set of released links and a set of stations or/and nodes at both ends of the links.

In the tit-th network, a station that is already in object transfer mode cannot make a call or make an n-call.

Further, a call request (command) cannot be sent on a link that is already transferring an object. These stations and links cannot originate calls or transmit call requests;
Graph D must correspond to the network minus these stations and links. Furthermore, the resulting graph may not necessarily be connected, in which case it is treated as one connected component.

The condition R2 (Ill) is that the link receives call requests (Ill) in both directions.
command) can be transferred.

Also, it is assumed that the number of links between nodes is l, but even if there are actually multiple links, only one of them will be subject to the connection procedure due to the node connection procedure. . Therefore, it is considered sufficient to limit the model to one for investigating how a call request propagates through a network. Once that link begins to be used for object transfer, the unfired graph at the next stage corresponds to a link that is not transferring an object (a released link) from among those multiple links. The same condition also means that it takes time for the fire on the plate to spread, indicating the transmission delay of the call request in the physical system.

Process (I) in Definition 3 is called "X" when the station makes a call! j.

In addition, when a call request is received from the calling station (; indicates that the number is not 1), the process (III) in Definition 3 means that when a call request is output from a node, it is not possible to receive a call request in the opposite direction. Indicates that it is not attached.

The process (Ill) in Definition 3 corresponds to a node selecting only one of the request ports to relay the call request, and other request ports being ignored. The port selected here does not necessarily have to be the first requested port, that is, even if the fire on the plate spreads from the starting point to the ending point, the first point does not have to be ignited immediately.

Theorem 2 When at least one vertex on the unfired graph F=D fires spontaneously, all TR points will eventually fire.

Simplified proof: Since F is a finite directed graph, the process of Definition 3 (I
The repetition of step 11) ends in a finite number of times. That is,
F converges to a certain graph.

Here, in the final graph F, assuming that there is a certain non-firing vertex W, and MCV is the set of all non-firing vertices, VM is the set of firing vertices. , the initial graph of F is F=D and is connected, so the arc connecting a certain kEV-M and a certain wEM (
k, w).

(w,k) EE exists (Definition 2).

Since the vertex is fired, arc (k, w) is fired by constant R3 unless arc (k, wl has already been removed from A (before the firing of k). However, arc (k, w) is fired. k,w
) fires, the vertex W will also fire within a finite time unless that arc is removed, so the arc (k, w) must be removed from A. From Definition 3, the arc (k, w) is removed from 8 only when the rnn point reactor ignites, which contradicts the assumption. Q, E, I) The meaning of Theorem 2 is as follows.

When one station makes a call, the call request is broadcast to all nodes and stations.

Theorem 3 Unfired graph D = (V, graph F = finally obtained when p vertices (p≧1) on El spontaneously fire
(V, A) is a forest of p directed books.6 Also, one point that spontaneously fires is the root of each directed book.

Simplified proof: Here, let one connected component of the final graph F= (V, A) be '= (V', A'), and the set of all 11 spontaneously fired points in T be R and n, naturally RCV'
CV, A' CA.

According to Definition 3, any vertex wEV fires if I) the vertex W fires spontaneously, or II) (k, w)E
A, some vertex k (CV in w#) fires, arc (k,
Only if the vertex W fires (not spontaneously) through the firing of w). Here If), the arc (k
, w) remains without being removed, so it is kEV'. Therefore, if some other vertex, kEV', (k #w) does not fire before any vertex wEV' -H fires, then It won't happen. Since the initial state of all 11 points of graph T was unfired, if R = φ, none of the vertices of V can fire,
Theorem 2 (When one vertex rθV spontaneously fires, V
all vertices of fire). Therefore, T has at least one spontaneously fired rR point rERCV
゛ exists.

If any fn point rER fires spontaneously, all Wb with r as the terminal vertex from process (II) of constant R3
(k, r)EA', (kEV') are removed from A. Therefore, there is at least one TR point rεR that does not have an arc with itself as the end vertex.

By the way, the constant R3 process (II+) is such that when the Fn point W fires due to the firing of a certain arc (k, w) EA, (w≠kEV) to a certain vertex wEV, that arc (k, w
) all arcs outside u (k', w)εA, (kf, to'
EV) is removed from A. On the other hand, since the vertex W was fired by the firing of the vertex (and also through the firing of the arc (k, w)), the constant s3 process (N or (IN) causes the arc (w, k) to fire at the point TR. It is removed at the same time (that is, before the firing of vertex W).When W fires to m, arc (w, k) already does not exist, so arc (k
, w) remain without being removed. Therefore, there is only one arc to the 0 point W (which fires not spontaneously).

Now, since all TR points of T must fire, the vertices WEV'-R of Ren and Go also (not spontaneously)
must fire, therefore any ri point WεV'
There is only one arc to -R.

Next, with respect to the vertex rER to R, ]゛ to R−(r)
The subgraph T' = (V'',
Considering A-), the conditions fl), (If) of Lemma l
, (satisfies IIN, and To is a directed book of vertex rl.

In addition, V''' = V' - (R - (rl), where,
Let's assume that at 'r' there is a spontaneously firing ■α point r' ER, (r' ≠ r), in addition to the rn100 point ER. Since 1' is a connection, a certain arc (r', k)EA', (r'≠kEV") must exist.

By the way, To is rl's (■ Inland water, so m points to Ren lol
CV" - (with respect to rl (by Lemma 1) there exists only one arc whose terminal vertex is W. On the other hand, since the vertex W is spontaneously fired (firing, we make W the terminal vertex) arc is 1
It has only one stroke (l does not have one. Therefore, any one stroke point wEV
”-(arc (r', w)eA' with respect to rl.

Since ro cannot be the final vertex, there is no arc between ゛ and W, and r is also the final Tfi point and cannot be written.
There is also no arc between r and r. Therefore, T is connected C
It contradicts what happened, so ro cannot exist.

R = (must be rl, i.e. T' = T
, and T is the inner water on the point r.

From Theorem 2, all [1 points will eventually fire.

Furthermore, all connected components are directed books. Furthermore, each spontaneously firing vertex is at the root of the directed book that is each connected component. Therefore, if there are p m points that spontaneously fire, each spontaneously firing There are p independent directed books with the vertex that fired as the root. Q,
E, D.

The meaning of Theorem 3 is as follows.

When p stations make simultaneous calls (within a certain time), a call collision occurs and the entire network is divided (divided) into p parts. Within each of the divided (sub)networks, there are valleys. A call request is broadcast. Also, the propagation or broadcasting of call requests occurs in a straight line originating from the (each) calling station. In addition, F is a forest of p trees (Forest
It is called l.

Let's consider a graph in which a real number called ``length'' is connected to each of these arcs.Length here has two basic characteristics.

(1) The length of a collection of arcs is additive and is the sum of the lengths of each arc.

(2) It is a measure that it is naturally desirable to minimize within a set of arcs that are considered "acceptable."

The length of arc a is expressed as (a), a directed graph D= (V
, E), the length of all arcs aEE is (a) > 0
shall be. If D is an unfired graph, then from Theorem 3, any two m points l.

j, at least 1 from i to j with respect to (i#,j)
There are two paths.

The problem is that one path P whose length is minimum:
The purpose is to find (a + , a x , ..., ao). In particular, the purpose here is to find the maximal shortest distance tree with respect to r.

When there is a circuit C in a path P, the length of C is (C)>O since all arc lengths are assumed to be positive. Therefore, to find the shortest path, it is sufficient to consider only simple paths.

The following Lemma 4 is based on the above-mentioned R, G, Busacke.
This is a rewrite of Theorem 3-25 in the literature by R et al. (translated by Kentabe Yano et al.).

Lemma 4゜■ in one directed graph D= (V, E), r
Let be a tree with root , containing all vertices reachable from r. For any vertex k of T.

Denote the distance along T from r to k by L (k),
However, L (r)=O.

Any string (k, w) whose both ends are inside T
1, (ml≦1.fkl+kyw), and if and only if T is the shortest distance tree with respect to r.

For all circuits in the considered graph (C1≧0), Lemma 4 states that one given reference point r
One logical basis for the following operation that actually gives a maximal shortest distance tree for λ is given by −5. Conceptually, this operation is equivalent to making the length of the arc correspond to the time it takes for the fire of the fired arc to burn from the starting point to the ending point in the [firing of the vertex] of constant R3. .

Operation l.

We will deal with a directed graph F = (V, A) whose initial value is an unfired directed graph D = (V, E), where A is the function RA = A (t) at time t, and its initial value is A (
0)=E. Regarding F, "firing of a vertex that defines temporal behavior" refers to an operation that satisfies the following three conditions.

(1) Any vertex rεV spontaneously (at any time tr≧
0) can fire. When 100 points rEV fires spontaneously, all arcs (r, w) EA with r as the starting vertex
Fire (tri, (r≠wEV), and all arcs (w', r) with r as the terminal vertex EA (Ll,
(Remove raw' EVI from A. This corresponds to the station calling.

(I+) Time with respect to any vertex kEV, when k fires non-spontaneously at >0, all arcs (k, w)
EA (t-1゜(k, # w EV ) is fired, and the arc (w, k) of Zube'C in the opposite direction is fired EA (t
, l are removed from A. Note that (k, w)irA (t
k), then (w, k) is not removed.

(Ill) k, w E
), when vertex k fires at time, if vertex W has not yet fired, arc (k, w> fires, and after a time z (k, w) corresponding to the length of the arc , t, that is, at time t+τ(k, w), if rR point W has not yet fired, W fires.

If the time is before time t m +r, (k, w).

If the vertex W fires at (i.e.

tw+t (k, W)>t: then), the arc (k, w) is A
(Removed from tJ. Here too.

t, m + 'C(L, wl = tkt + t
(kg, w) = =--= tk, +τfk,,
wl = 1°kl, ni*, --, ni, E V fired arc (kl, w), (kg, w).

・・・・−1(k p 1w) EA (If the vertices W are fired simultaneously by t-1, choose any one of these arcs (k, w), and (k, w ), all arcs whose end vertex is W are removed from A.

The meaning of operation l is as follows.

This is Definition 3 with a temporal element explicitly added. In definition 3, the node selects one of the request ports and relays the call request, but in operation 1, the node selects only the first request port and relays the call request. This operation 1 models the calling/terminating of a call from one station, the selection of the first request port of the node, and the relay output of the call request. That is, this is a model of the broadcasting of a call request in the DC3S/IC.

When the starting vertex of a certain arc (k, w) fires and burns out from the starting point of the arc, the flame spreads to the end point of the arc after t (k, w) time, and if the final vertex has not yet ignited, The terminal vertex fires immediately. What is important here is that if the fire from any arc (in the direction of entry) is transferred to the vertex, the fire should be immediately transferred to another arc (in the direction of exit). It is at this point that various theorems are derived. Moreover, operations at each vertex are performed independently of each other, each without knowing the overall situation. This is very similar to how the fire spreads when a firework is ignited (spontaneously ignited) by connecting multiple fuses between the fireworks.

Theorem 5 1 on an unfired directed graph D (V, E) under operation l
When an arbitrary vertex rEV fires spontaneously, the resulting directed graph T (V, A+ is D− of
It is a tree with the maximum shortest distance with respect to r.

Abbreviated evidence: From Theorem 2, T covers all vertices on D.

Also, from Theorem 3, T is a directed book on F. Here, if Lemma 4 can be applied, it will be proven.

Now, the time when vertex r fires spontaneously is 1 = 0, and the time when εA fires (not spontaneously) at any vertex is t = t1.
．． shall be.

Process (III) of operation l is for any string (k, w) whose both ends are in T.

tw≦t, +tefkywl It shows that. because.

tw> 1 engineering + τfk, wl given that.

tw= j+++t: fk', wl> tm+t
There exists an arc (k', w) εA on T whose terminal vertex is W such as (k, wl), which violates condition (III) of operation l. Therefore, Lemma 4 is applied. Q , E, D The meaning of Theorem 5 is as follows.

If each node immediately relays the call request on the first-arriving request port, the call request will be broadcast using the shortest route 1~.

Theorem 6゜ Unfired directed graph under operation l D = p arbitrary vertices r on (V, E).

r8. ..., r, EV fires spontaneously, the resulting directed graph F= (V, A) has p connected components, = (V,, A, l, (i, = l.

2, -..., p), and each T is a tree of maximal shortest distances with respect to ri, on, and r, respectively. Here, for all,j,kEV,(,j,
k) EE, then (,j,k)εE,
= (V, , E, l.

Simplified proof: By Theorem 3, F has p each j 1 + r 2
1r, it becomes a forest of trees with EV as its root. here.

No arc (j, k) εE is removed by the spontaneous firing of r, such that r, ≠ r, for each, since if (j, k) EE+ is now removed. , at least one of j and kEV must fire, but 1. Since j, is the vertex of T1, which is a subgraph of the beam, the firing of j, cannot be due to the spontaneous firing of r. Therefore, the arc (j
, k) GE, is not removed by spontaneous firing of rq.

If we apply Theorem 5 to the original graph D, of one connected component of F, then ■, is r on D3.

becomes the tree with the maximum shortest distance with respect to . Q, E, D.

The meaning of Theorem 6 is as follows.6 If multiple stations make simultaneous calls (within a certain period of time), a call collision will occur and the network will be split. Call requests are broadcast for each (sub)network via the route with the shortest time.

Theorem 7 Regarding the unfired directed graph D= (V, E), from one arbitrary vertex rEV to one other arbitrary vertex Wε
Let the length (time) of one shortest path P to V be (P). When multiple vertices containing r for D fire spontaneously at the same time, the resulting directed graph F= (V, A) under operation 1 has a path from r to W when The length of the path (time) is limited to t (P).

Short proof: For D, p (p≧2) arbitrary vertices rItr8.・
... + r jεV spontaneously fires and the graph F= (V, A) finally obtained becomes the Ariuchi Water Forest of plW. Vertex r, EV, connected component element I=(Vl, A
, ) is a directed book on r (from Theorem 3).

Now, if r '' r r, then w i V r and WεV, then T1 and T are not connected, so the path from r to W does not exist on F. If w E V r, then T, Since is a directed book on F, there is a path from r to W on F.

From Theorem 6, r, is (j, k) EE for all j, k E V r, then (j, k) EE, = (V,, E, is maximal with respect to r on i As stated in the proof of Theorem 6, all arcs (j, k) EE, are not removed by the spontaneous firing of vertices (roots) other than r, so that r From W
If all vertices on some shortest path P to are elements of Vr, then all arcs on the path P are elements of E, and P is an element of D
i,: Since J was the shortest path from r to W, clearly there exists a shortest path P from r to W via Dr. That is, the shortest path P from r to W exists on F.

Here, the shortest path P:= (r, P+, Pz, -pm, w
), one of the points of <rn is q. That is, q
E (P+, Pi,・'-3P-1-Now, if only r fires spontaneously, let the times when r, q, and w fire respectively be jr+ t,, tw. From vertex q to vertex W The shortest length (time) along the path P of
q, w), then tw= 1q ℃ tq, stomach) == t, +
tfPl.

Now, the vertex 9 is caused by the spontaneous firing of the vertex r1 at time t,
Suppose that it is ignited at °, where q jl V
If tkq''Vl,r; 〆V and r, ,EV, (q=r+ may be), then ≦tq, because if t,'>t, then the operation Due to l, q is caused to fire at time t9 by the spontaneous firing of r. Therefore.

When q fires at time ill t 9°, the time tw at which W fires is tw = t,,' + t (q, vl
≦to”i: (q−wl=tw
It is. This is true even if there are multiple shortest paths on D from r to W.

Fn point W is due to spontaneous firing of r at time t)
cannot be fired, therefore at time 1, < 1 *
The reason why W is fired in is due to the spontaneous firing of vertices other than r. Also, the time when W is fired due to the spontaneous firing of vertices other than r is t≦t, therefore,
The time when W fires due to the spontaneous firing of r is t=1. , = t, +τIP), Q, E, D.

The meaning of Theorem 7 is as follows.

The path between the calling station and the called station is the path in which only one station makes a call, which is not detoured to take a longer path due to a call collision. Either the path has the same length (delay time) as P, or the connection fails because there is no path (at that time).

If there is a sufficient number of links, there is a good chance that some of the shortest paths (including the shortest path (1)) will be used for object transfer by other stations calling simultaneously, and the shortest path will be blocked. When this can be expected, a connection via a path of the same length as path P can be expected by calling again.

Theorem 3 shows that when only one station makes a call, a directed Kinoshita is created with the calling station r as its root, and the call request is broadcast along that T. Of course, directed woodworking is a global subgraph of network D (the set of 111 points is the same).

Now consider the strings related to directed woodworking.6 In particular, how can those strings be removed from the network D and how can they be removed from the network D?
Think about whether you got it. The operation of removing these strings is based on the "firing of vertices" in Definition 3, and this operation has the following two meanings regarding the removal of strings.

■ Call requests flowing in opposite directions on the same link are invalidated (from process (I) or (II) of Definition 3).

■If multiple call requests are input to a node, one of them
Processes of J1!3 are disabled except for one (il
l)).

(2) can be interpreted as a collision of call requests on the link. On the other hand, ■ can be interpreted as a collision of call requests on the node.

The firing model models the invalidation of a call request in the form of arc removal. The removed arc at this time is a chord related to T.

Nijito Yuko It± deep call collision has already been discussed to some extent, but I will discuss it again here. The phenomenon in which the entire network is divided into two when pflW stations make simultaneous calls (within a certain time) is called a call collision.

This is a phenomenon unique to DC5S/IC, and is shown by Theorem 3.

The phenomenon of network division is caused by the collision of call requests mentioned above. However, the difference lies in whether or not the four sources of call requests are the same.

Collision of call requests means that a call request output from one No. 67 station does not permeate the other. However, call requests from the same caller reach the other node or station via different routes (although they do not penetrate directly). 6 When a collision occurs between call requests from different callers, , does not penetrate (even indirectly) to the other side between two nodes/stations,
This is the microscopic phenomenon of call collision.

In the basic principle of L Hill Constant Problem DC5S/[, is there no time constant as much as possible? Hitoshi also thought about this.However, when you think about the timing of a call, there seems to be something that seems to be a time constant. There is no need to specify.

31. Timing of origination As shown in Theorem 5 in Chapter 2, the call request is protocast to all stations 1 and 1 through the shortest route. In this case, the network structure operates as a bus when it comes to making calls. However, the problem with conventional communication systems is that if k (k≧2) stations make calls at the same time and a call collision occurs, the network is divided into several subnetworks (in terms of call requests). That's true. In this case, if a certain source station (5source 5tation) makes a call to the intended destination station (Destination 5Lationl), and both stations are not in the same network, the call procedure will fail. It seems likely that the call procedure will be successful.

The so-called radio channel (Radio C)
1, the received signal level differs depending on the distance, and for this reason, even if multiple stations call at the same time (only the signal with the higher level 8 is received), the capture effect (Capture effect) occurs.
ture Effects are known. If we consider the fact that the calling procedure will be successful with a probability of 1/1 even if a previous call collision occurs as a kind of capture effect.

This calling procedure is typical for bus
Type ((:tent, ion Type), Random Access T
It has the same effect as echniquel. This flll
The description of the channel (bus) is detailed in the English literature mentioned above, especially in A1. The concepts of OII A and C5MA can be directly applied to the calling procedure.

As an example, p-purge stand [P-persisten]
This will be explained using the same method as t and IC3MA. Now, the maximum propagation delay time of a call request is τ. (seconds), and the size of the minislot (14inislotl) is as follows.The procedure for making a 6 call is as follows.If at the beginning of a minislot (on the port of that station) If the link is free, call immediately (with probability ■).If no call is made in that minislot, repeat this process in the first minislot; if the link is not free, Wait until it is released and apply the process of -F (call originating due to a call conflict)
If the connection fails, repeat the above call procedure.

1-persistent C5
In the same method as MA, when the call procedure fails due to a call collision, the call is re-called after a random time in the form of back-off. This random time is proportional to Lo, and is usually taken as a random (+H) integer multiple.

No matter what method you use, you can't get more than two games in a given time.
If the second party makes a call, there is a possibility that the calling procedure will fail.

On the other hand, even if a call is made, it is almost always T. If you can make it so that only one station calls within the time, 9. Failure of the calling procedure due to call collisions can be largely avoided. Therefore, T
, o is considered as one time constant.

3.2. This is a very important task.

The maximum propagation delay time t7 of a call request cannot be easily determined as in the case of normal C3MA. It is necessary to perform firing with a specified behavior and find the longest path of the resulting graph.

D has all possible candidates from the actual network. Since the links used for object transfer are not included in D, there can be various links. In some cases, multiple helmets D may exist in the network. In other words, the target topology changes dynamically, which is a major difference from conventional bus-type networks. However, τ
The upper limit of 7 is easily found.

Let n be the number of vertices. It is assumed that the propagation delay in the network occurs only due to the links and there is no propagation delay at the vertices. If there is a propagation delay at one point, the propagation delay of the link can be treated as a correspondingly large propagation delay.The worst case is a simple path passing through all Tn points. The number of arcs in the path at this time is n-1. That is, if the 0m point, which is the northern limit of the propagation delay time of n-1 links, is divided into stations and nodes, and the number of nodes is m, the path passing through all the nodes is 1 which passes through a maximum of m-1@ links. Since one link is passed from each station to a node and from a node to a station, a maximum of m+1 links are passed from one station to another. Now, if the maximum propagation delay time of the link is te, then te ≦ (m+1) τ 1. Therefore, the upper limit of τ0 is suppressed to (m+1).

By the way, τ0 is the worst case, and in normal operation (ie, in a normal unfired graph), it may be a much smaller propagation delay time. This is especially true when the entire network is grid-like and has a sufficient number of links.

In normal C5MA, when a packet collision occurs, the transmitted packet is damaged. Even if the system has a chance of surviving due to the capture effect, there is a high probability that it will be damaged. However, with DC3S/IC, even if a call collision occurs, the network is only divided, and the call request (and call (information) is not damaged, and in general, the transmission damage of communications and logistics tends to decrease as the distance increases. Although many communications here are close to that)
, the distribution of call frequency is an index of the distance between stations (approximately)
If it is inversely proportional, that is, it is (approximately) proportional to exP (-L), then even if a call collision occurs, there is a high probability that the call procedure will be successful with a relatively nearby station.
In this sense, especially when m is large, τ. =(m+1).

Even if it is small, for example, it has a maximum propagation delay time of D that is usually considered. It is considered possible to close it.

3.3. When a release request (command) is continuously issued at a link broadcast or node, and release requests on the same link continue to be input, that link is released.The time from output to input of a release request at a certain port, In other words, the round trip propagation delay time of that link is likely to become one time constant. However, it is not necessary to define this time constant (link forward (summer propagation delay time)) as a system, as will be shown below.

Assume that both ends of a certain link are ports A and B. Assume now that no release requests are flowing in either direction of this link. When a release request is output at bolt A, the release request arrives at port B after a certain propagation delay time. At port B (whether station or node) a release procedure is taken;
A release request is output from port B. The release request from baud 1-B arrives at port A after some propagation delay time.

At this stage, we can say that this link has been released because release requests are flowing in both directions of this link. At least in port A, it is possible to determine that the link is released when a release request is input.On the other hand, in port B, immediately after the release request is output, release requests are not yet flowing through the entire link. Therefore, at this point the link is not (completely) released, but at this point port B can safely interpret the link as being released, because immediately after that, a call request from port B ( Even if a command) is output, a release request and a call request are sent to port 1-A in the order of blue, and port A immediately completes the release procedure by inputting a release request and becomes able to input a call request. It is from.

If there is a time constraint, it is that port 8 must be able to reliably recognize a release request from port B. This is a question of how to implement a station, node, or junction, and is not a fundamental question.

4 In data communication for object transfer, the communication format is unidirectional fsimpiex1
0ne-wayl or half duplex a14 Duplexl
However, the methods are differentiated by ``Full Duplex'' and ``Full Duplex''. In DC3S/IC, data communication is interpreted as a form of object transfer. Conversely, even when transferring to object 1, unidirectional Duplex and full duplex can be considered.The basic principle assumes that object transfer is full duplex.゛L double and unidirectional can be shown as variations from the original principle as follows. Can be done.

Half-duplex is a method in which objects are sent to each other by switching the direction of object transfer, at one time from the calling station to the primary station, and vice versa at other times.゛Toni!
The advantage of (2) is that it is economical because the amount of object transfer paths can be halved. However, in order to switch the object transfer direction, it is necessary to give each link the transfer direction as a new command. This is a maintenance request (command)
This is possible by extending the call information and setting subcommands under it, but in maintenance mode, by transferring the subcommands as an extension of the call information.

For example, two subcommands, transmission and reception, are prepared. The source of these two subcommands is the station. Further, the two subcommands are not processed in any way by the node, but are simply relayed. At the point of contact between a vertex (station or node) and a link, when a subcommand of transmit [receive] from the apex side and receive [send] from the link side comes, the link will be sent at that contact point (as seen from the apex).
Operates in transmit [receive] mode.

Unidirectional refers to a method in which the direction of object transfer is only one direction, and the direction of the transfer cannot be changed once the connection procedure is completed between two stations.8 Therefore, the direction of object transfer is determined when setting the route. must be maintained. For example, the calling station transmits an object, and the called station receives the object. Of course, the direction of object transfer may be determined in the opposite way.
f response. Alternatively, there is a way to change the direction when setting the route so that it goes in the opposite direction, but there is also a way to set the direction from the beginning and not change it. In this case, call requests must be allowed to flow in only one direction on the link.

Although this case is not specifically dealt with in the basic principle or firing model, it is sufficient to assume that the propagation delay time in the direction in which the call request does not flow is infinite.

Unidirectional has the same economic efficiency as half-duplex. Since there is no need to switch the direction of object transfer any further, the link structure can be further simplified.

Considering the logistics, the symmetry of the transfer (at least at one time)
I don't think it's necessary, so I think this single direction is suitable. Furthermore, in data communications such as large-capacity file transfers and fax machines, the same can be said of logistics; however, in this case, the (relatively extremely) small-capacity control is performed in the upper layer. It will be necessary to be able to transfer information at least in the opposite direction of object (data) transfer; this requires 4J in half duplex.
You can use a method similar to the method of adding a command. For example,
As an extension of 01 information in maintenance mode, these controls (
This is a method of transferring wholesale information.

Although the basic principle is the same, there are various implementation methods. One of the major challenges in DSSS/C is how to realize commands and call information, and How to transfer objects and how to change transport paths, in other words, how to perform switching, will be major issues.
Book 15 does not specifically discuss the afterword, but let's talk about m-holding requests (commands), which are closely related to objects.

If we simply implement the Ji method based on the principles of DISS/IC, as shown in Figure 1, multiple nodes 88 and B are connected by links 10, and station S is linked to node t'A. It is accommodated through 12. Links 10i5 and 12 are bidirectional in this embodiment and are comprised of three channels 20, 22 and 24 for passing command information and objects in each direction, respectively, as shown in FIG. . The convex node and each station also have three channels (for each baud).

Objects should always be sent with maintenance requests (commands). Conversely, it is important to note that GT holding requests should not be issued while object transfer is not possible. In real-life links and nodes, it may not be possible to instantly switch to object transfer mode (for example, if data communication requires
5, there may be cases where it is necessary to take a peer group with a Ro link, or where an IiM-like switch is used. Also, in logistics, mechanical movements are naturally involved. In this case, the object!・The (relay) output of the maintenance request can be delayed until the transfer is possible. There are three types of gods that can be considered for this method of delay:

(1) Object 1 - When transfer becomes 11F capable in both directions (at that link, node, or station), it outputs mt holding requests (relays) in each direction.

(11) Output (relay) a maintenance request in the same direction as the direction in which object transfer is enabled.

(Ill) Output (relay) a maintenance request in the opposite direction to the direction in which object transfer is possible.

In particular, in the case of (Ill), the input of the request indicates that the object in the example can be received. In other words, the station only has to start sending objects after receiving a maintenance request.

(II 1 indicates that when a maintenance request is input, it is possible for the other party to send an e-object, and one station must immediately start -y<;1 of the object when a maintenance request is input. (I) is CII ) and (III
), the input of the maintenance request indicates that the MIF-station is capable of transmitting and receiving.

In (II), if a station sends out a 4-build object at the same time as outputting a maintenance request, the object cannot be immediately (relayed) output at the link or node, and the object may be delayed and lost or damaged. i-+7 potential remains. I need to wait at the station for an appropriate amount of time and delay the sending of the 4th episode. In this case, (I) or (Il
l) would be an arithmetical implementation method.

52 Command Channel This section describes how to implement commands and command channels.

(There are four types of 11 commands in basic principle.
If the channel signals have four levels, by assigning each command to each level, the command channel signal wires will be one set (in the case of metallic cables, there will be one pair or two wires, one for the transmission line). , and the other is a return line (in the case of an optical cable, one) is sufficient.

(2) If the signal is handled at two levels (that is, with a digital signal of -0.1), then if there are two sets of signal lines, it will be 22
=41 Commands can be transferred by combining (encoding) signals.

(:3) Or, the signal is 2 levels and the E9 line is 1
For example, repeating a logic 0.1 pattern in a certain period is a call response, repeating a 0.1 pattern in another period is a maintenance request, and any of these A continuation of "0" or [IJ for a period longer than the cycle of IJ may be regarded as a release request or a call request, respectively.

(4) As in (3) above, one set of two-level signal lines converts a one-time bit pattern into a code. While (2) is space-divisional encoding, this is time-divisional encoding.

If we look at this as time multiplexing of bits, we can naturally think of time multiplexing of codes. When multiple links are placed between two nodes, these multiple command channels can be multiplexed. This is generally the common channel signaling method (Common Ch signaling system).
This is the same concept as what is called the annelSignalling System.

(5) The command sequence for normal outgoing and incoming calls is shown in Figure 3. Here, consider reducing the number of command types.

If it is possible to transfer an object immediately after a node relays a call response (instantly), if the link is always ready to transfer the object, and if the station can receive the object at any time, then the maintenance request can be replaced by a call request or a call response. However, when a call response flows in the opposite direction to a call request on a certain port or node,
From then on, both of these are considered maintenance requests. There are now three types of No. 18 for commands. Furthermore, even if the call request and call response are expressed by the same signal, if they can be distinguished in some way, for example by temporal order, then the signals for 5 commands will be 2)! It will end up being just like that. 2
Please note that types can be expressed using only logical 0s and 1s.

The problem with =62 is that it is necessary to be able to clearly distinguish between a call response and a call request. If they cannot be distinguished and a call response is interpreted as a call request, the link on which the call response flowed (as described in 2.4.1.) The response is invalidated.A call request and a call response can be distinguished in terms of time order.

Now, if (this propagation delay time on a certain link is n+
A call request collision occurs when a call request is input from one side of the link and a call request is input from the other link within one hour. After some time, the call request is sent to the other node 7, and the node 1:7 does not send a call request to that link. Therefore, a call request collision occurs when a call request is sent out from a port connected to one side of the link.
Detected by receiving a call request to the same port within one hour. Conversely, the call response is received after 2v+ time (it may be assumed that it is the same number as the call request -XS).

Let's summarize the story, command channel signal S,
, S, is a logic O and a logic U flows. Here, 80 is a signal going from a port to a link, and Sl is a signal going from that link to that port. Set the command channel on a port as follows:
Interpreted as a release request, call request, call response, or maintenance request.

■ If -5, = 1-0, S. = Request to release 0 (output)
If S, = 1-0, 51 = 0 is considered as a release request (input).

((2) - When S, = S, = O, the link is released.

If s, = t, s, = o from the state of ■...■, then S
,=1 is regarded as a call request (output) 9 Within 2r+ hours after the state of ■...■ is reached, S
When =1, S, =1 is regarded as a call request (input) (a collision of call requests has occurred).

(S, = 2τ1 hours after entering the state of ■)
If it becomes 1, S, = 1 is considered to be a response (human power).

S from the state of ■...■. -0, S, if = 1, S
,=1 is considered as [lf request (input).

(7)...(If 8° = 1 from the state of Φ, S o
” 1 is regarded as the mouth'P response (output).

・■・・・■ or ■ If you say one sentence, it's appropriate,,f'
After a period of time, both the n/p request and the call response are called maintenance requests.

Note that a new time constant 2 t: + has now occurred. Since this 21:1 ratio is unique to each link, it is straightforward to convert between the signals on the command channel and the commands at both ends of the link, such as a transceiver.

On the other hand, it is possible to set the propagation delay time of the l-link in the system as the maximum degree (degrees Celsius) (of course, it will be smaller as the propagation delay time of the actual link is delayed), and then apply the methods described in ■ to ■ as they are. be. However, at the called station, it is necessary to provide at least 2 r + time delay between receiving the call request and transmitting the call response. This is because if the propagation delay time of the link that is not present at the called station is almost O, then the called station actively increases the delay by 2 to 8 hours hλ
Unless otherwise specified, a call response will be mistakenly interpreted as a call request.)
(See ■, ■). In this method, since 2 t + is not link-owned, the command channel L signal and command t:
It may naturally be envisaged that the conversion between No. 12 and No. 12 is performed by the station.

In addition, station 8 should confirm that there are no 4 calls (call request inputs) before making a call.7 This is because the originating 0f (within 2t from the incoming call) is not a call response. This is because it may be interpreted and cause erroneous connections. That is, as for the calling method, C5UA= is more suitable than ALOIIA type. (The basic principle is that if a call is made during an incoming call, a collision of call requests will occur, and the station will simply fail. Therefore, even if A1011A is used, the call procedure will fail at tB.) (And it does not have any negative impact on others.) The methods described in ■ to ■ above are based on the link-specific round-trip propagation delay time or the link's maximum round-trip propagation delay of 51 hours.
At the cost of introducing a new time constant fJ[2v: +, a great advantage can be obtained in that the command channel as a transmission path can be simplified.

In this section, we will discuss how to implement a call information channel. Call information includes request information and response information. The response information is not essential in principle and can be omitted. just,
Used to check the correctness of the connection.

If the response information is omitted, the link with respect to the call information may be unidirectional (at least temporarily). If you look at it, is it the call information chart? , may be semi-duplex. In other words, for a bidirectional call information channel (even if there is only one set of line 4, the transmission direction of the signal line is switched every time a call is made (to pass a call request). 5 The requested information includes at least the destination address (called station address).Call information requires relatively little information, but it requires at least a few bits, usually several tens of bits. Possible 0
Using normal communications techniques, this is transmitted in six columns of bits following an appropriate preamble (including a synchronization signal). Call! l'? In principle, it is OK not to continue transferring information during object transfer. This means that the call information channel can be used for various control channels other than its original (in principle) purpose. It means. For example, it can be used to inform each other of the status of stations, to switch the direction of object transfer in half-duplex mode as described in Section 4, to control the flow between stations for object transfer, or to use it as an acknowledgment. Can be done. If the call information channel is always used between one station and the amount of information is small (transmission speed is low), then Section 5.2 (especially (4) and (5))
In other words, the command channel and call information channel are multiplexed and transmitted on one set of signal lines.

Furthermore, it is natural to multiplex multiple links between two stations and transmit them all (per direction) on one set of signal lines.

Consider another form, if call information transfer is only used during and immediately after the origination σf-call termination procedure, and object transfer occurs afterwards, and the data is passed as that object, then call information Channels and object channels can be implemented on the same signal line.

Furthermore, it may naturally be possible to implement the command channel, call information channel, and object channel on the same signal line. In fact, this is a LAN method using a multi-connection topology.

Let us consider the case of an application where it is necessary to always complete the call procedure at high speed. Serial transmission of call information takes time, so it is better to transmit the signal line in parallel as υ numbers.With this method, the preamble can be omitted, and the , analysis) and outputting a response can be shortened.

Conclusion 0CSS/rc is i? In contrast to the conventional method described above, by expanding the transfer target to one object and introducing the concepts of command and call information, the operating principle can be generalized considerably. Also, through this generalization, DC5S/Ic
We were able to model the phenomena associated with unique calls. We named this model the ignition model. The ignition model is based on graph theory, from which various properties were derived as theorems. Since the truth of the theorem is not necessarily strict, it is mostly used as a simplified proof, but it is considered sufficient for the purpose of this application.

An important theorem is (according to the basic principle): ■ When a certain station makes a call, the call request is made via the route with the shortest time (
(If the networks are connected in terms of call requests) broadcast (Theorem 5); ■ If a feTIf' collision occurs, the network will split; even if it splits, each (Nub) network will send a call request via the route with the shortest time. is broadcast (Theorem 6), and further shows that ■ (longer distance) detours do not occur due to the occurrence of a call collision (Theorem 7). So far, S has never been proven.However, ■ can be intuitively understood, and this phenomenon is known, and C revealed the phenomena of ■ and ■ for the first time here. C3MA
etc., if the bucket i-collision occurs, the bucket i
Compared to 91 M scratches where 4J'h is not established, rlcs
s/IC has a kind of strength against call collisions due to the phenomena of ■ and ■. When multiple stations make simultaneous calls, it is determined that one of them has a high probability of succeeding in the calling procedure (sections 3 and 2).

Theorem 2.3 only requires Theorem 5.6 as long as it follows the fundamental principle, and it may seem like an unnecessary theorem. Specially shown in case there are variations that are not included. In the basic principle, each node immediately relays and outputs the first-arriving call request, but according to Theorem 2.3, it does not necessarily have to be the first to arrive, and furthermore, it does not have to immediately relay-output. This means that even if the propagation delay time of a call request varies within a certain range (for example, when call requests (commands) are transmitted multiplexed), at least the property of Theorem 2.3 is maintained. means guaranteed. Strictly speaking, the time is not the shortest, but if a certain range of variation is recognized (it can be said that theorems 5 and 6 are close), it can be interpreted as suggesting that the route has the shortest time hα.

Dfl: In deriving the basic principles of SS/IC, we will explain the extension to objects and the 8! commands and call information. ! With the introduction of inclusion, various implementation forms were considered as a result of abstraction. In particular, we showed the possibility of using a unidirectional or half-bidirectional (r!) object channel to reduce link costs.Also, for the command channel and call information channel, we demonstrated the possibility of using a common line signaling method for the command channel and call information channel. We were able to show that such a method is possible. Furthermore, it became clear that the target of object transfer is not only data communication (objects may also be used).

I won't go into detail about the application of DC3S/IC, but I would like to say a few words about its value as a numerical model. Dynamic programming is often applied to solve so-called shortest path problems. DC3S/I
(1: is another way to solve this shortest distance problem.λ,ru,
However, it is necessary to replace the measure of distance with the link (propagation) delay time. If this link delay can be freely programmed T', it may be possible to use the DCSS#C method by solving the -arithmetic shortest distance problem.

For this reason, I believe that this report has provided the minimum theoretical foundation that is necessary for everyone.

Below, the terms used in this specification will be explained.

-A- Empty Board Vacant Port When there is at least one request port on the node, the port of the node-F whose link is in a state of failure to release.

-I- It has 11et, ain, Rete
Thereafter, as long as both the first-arriving request port and the first-arriving response port continue to send one request (link connection) in the node, object transfer becomes possible.

Retentinn Request This is one of the Retentinn Request commands, and the source is the regular station and the 4111 station.

-Oh- QI answer #'4: Re5ponse In
formation Call information - 1st destination 11i K
4 is the source of 5. Although it accompanies call answering, it is not necessarily essential and may be omitted.

Response port: Nesryanded Port A port on a node where a call response was input.

Object: Ob, inject The purpose is to ultimately exchange between two stations. In the case of data transfer, digital information is digitally serial (11)), but parallel transmission is also possible in principle. Furthermore, it is possible in principle even with analog information. Furthermore, the object may be an object of physical distribution (for example, gas, a bar for transporting a Z-bundle, a line network, a belt conveyor ÷4, etc.) rather than an electrical signal. These controls depend on the configuration of links and nodes.

Object transfer: Oh, ject TransSmi
ssion maintains and requests bidirectionally on connected links (
Command) can be read bf. Through links and notes 2
Objects can be transferred to phase Tj between stations.

Release Procedure A procedure performed by a station or node to release a link connected to a port. Po of station! -Maj2 confirms that after a certain port of a node (this station or No1ζ outputs the solution 7 & request, release requests continue to be input to that port.

Release Request 1Telease One of the Request commands, originating from a station or node. If you accept this command, you will receive an answer.

-Key station: 5TAT, 1on1 port, release function, call, blue connection function and object transfer machine 1ton (7-).

Arc Arc Used in the firing mogul number, and corresponds to the link ↓j. leaf′
The direction of the next link (command) is 1
There are two arcs.

Dl'-response: (This is one of the all Re5ponse commands, and the calling station is the source. It is a response to a call request.

Kano I! iti: Ca1l Information
Two types of n and r: ・Sakaiku information, response information + [j.

source (ij source is station. node is input l jif
Simply relay f-reports.

Call request: Ca1l Request Is it one of the commands and is it sent by the station? It's bean paste.

The call request is accompanied by a τ request information.

Command There are four types of commands: release request, call request, and call response request.

The station becomes the source of all four types of irl6 nodes, and only issues automatic release requests, usually using the C command! Relay to r.

Se-f &#y'i F connecLion P
The following series of -L continuations at the roce city 11'e node.

Accepting call requests and relaying them; Accepting call responses and relaying them; Connection between i5 and first four request ports and first-arrival response ports.

First Re5ponded P
Port of node F where nrt first-arrival call response was input.

Destination W'IP request port: First Request
d Port Port on the node where the first call request was input.

-chi- Blue call: Incoming Ca11.
A call request is input to fcalled1 station.

Called station: C: alled St, ation Station 9 whose called station address in the request information was its own address when there was an incoming call 100 points: Used in the Vertex firing model to communicate between stations and nodes. Equivalent to.

Firing of Vertex station fires n! F, and abstracts and models the node functions from when a call request (command) is input until receiving an ay response (command), and whose root is a vertex that spontaneously fires from an unfired directed graph. The calls made by the six stations that act as operators that create the tree are treated as spontaneous firings of vertices.The node that selects the first port is called the firing of a vertex that specifies temporal behavior.

-De- DC5S/IC: Distributed Carr
ier Switching System on
Independent Control Independent control wholesaler and independent control unit transmission exchange system.

It is a type of distributed (wholesale type) switching system in which a large number of small-scale nodes with transport path switching functions are arranged, and the network as a whole performs a large-scale switching function.

-Network: Network One or more (mutually independent) nodes, two or more stations,
Two or more -F links connecting nodes and stations (where one station is connected to a node by one link), and zero or more links connecting nodes Consists of links.

-No-1':Mode Has multiple ports and has a conveyance path exchange function. Each port of a node is connected to a port of another node or station by a link.

-Ignition/Fire This is an abstraction and model of the origination of a call from a station, the arrival of a call request (command) to a node, and the flow of a call request to a link. This is T degrees, and when a large number of fireworks are connected in a network with fuses, 1. It's similar to when you light a firework and the fire spreads to other fireworks.

Firing Model DC3S/IC
It is a numerical model for explaining the unique phenomena related to ignition, and is based on graph theory.

Backoff: When a call is made but the connection fails, waiting for a certain random amount of time in order to call again.

Outgoing call: Calling, Outgo
ing Ca11 station outputs a call request.

From Lof station: Calling 5tatio
n Station that made the call.

Call collision: Co11ided (:allsp(p
≧2) A phenomenon in which the entire network is divided into p parts when the stations (within a certain period of time) make simultaneous calls.

-Fu- Broadcast+Broadcasting A calling station's aq request arrives at all stations as long as there is a route. Strictly speaking, this is limited broadcasting.

-I- Boat: Port There is one port on the station and multiple ports on the node, and a link is connected to port 1. It serves as an input/output port for commands, call information, and objects.

Pending request port: 1Jndecided Request
st PortRequest port (of a C node that is not the first-arrived request port).

-See- Unfired directed graph: A graph in the firing model, and corresponds to a network consisting of a set of released links and a set of stations or/and nodes at both ends of them. is a connected digraph D=(V,E) in which there is only one (i,j) EE for every (i,j) EE in which all pixel points and all arcs are not firing.

-Yo- Request information: RequestL 7nformation
This is one type of call information, and the originating station is the calling station. Call request (
It is accompanied by a command) and consists of a preamble and a called station address (the sending of the calling station address and call control information is optional).

Request Port: Request Port.

Port on the node where the call request entered.

-〇- Non-link: One side of the Link J is connected to the node port. The other is connected to a port of another node or station. It has a bidirectional transfer function for commands, call information, and objects.

Link resolution: Releasing a Li
When the nk station or node continues to output release requests and input of release requests on the same link continues, that link is said to be released.

F Effects of the Invention] According to the present invention, not only serial digital signals but also communication signals such as parallel digital signals and blog signals can be transmitted and exchanged. Furthermore, gas,
Objects such as liquids and solids can also be transmitted and exchanged. In addition, cross-over and half-duplex can be effectively applied to the object transfer path, and furthermore, a common line signaling system can be applied for exchanging information regarding connection procedures.

This reduces link costs.

[Brief explanation of the drawing]

FIG. 1 is a conceptual block diagram showing an embodiment of the distributed carrier switching system according to the present invention. FIG. 3 is an explanatory diagram showing an example of the link configuration shown in FIG. FIG. 3 is a sequence diagram showing a command sequence of f. , bureau

Claims (1)

Claims: 1. A network including a node, a plurality of stations, and a link connecting the nodes and stations or between nodes, through which an object is transferred, wherein the object is a serial or parallel digital signal, at least one of an analog signal and an object, the station having at least one of a release procedure for the link, a call origination and call termination procedure for the network, and a mode for transferring objects in the network. and the station outputs a release request command to the port of the station,
After that, when a release request command is input on the port, confirm that the link on the port of the station is released,
Among the stations, a station to which a release request command is input when it is not in a call origination procedure performs a release procedure, and the node has at least two ports and has a transport path that includes a release procedure, a connection procedure, and a maintenance procedure. In the calling procedure, if the link on the port of the station is released at the beginning of the minislot, the station immediately outputs a call request command to the port with a predetermined probability, and at least receives an incoming call. A call is made by sending request information including the station address, and if the call is not made in the minislot, the above calling procedure is repeated in the next minislot, and if the link is not released. waits until it is released and performs the calling procedure, and if a call response command is input within a predetermined period, shifts to object transfer mode, and if a call response command is not input within the predetermined period. If so, stop outputting the call request command and output a release request command, repeat the above call procedure again, and even if a release request command is input during the call procedure, ignore the release request command, In the object transfer mode, the station outputs a maintenance request command to the port of the station, enables object transfer on the port when the maintenance request command is input to the port, and releases it during the object transfer mode. When a request input is detected, the release procedure begins, and from then on,
Object transfer is not performed unless the node enters object transfer mode again. When the node finds a port to perform a release procedure during the connection procedure, it outputs a release request command to that port, and then releases a release request command on that port. Confirm that the link on the port of the node is released by inputting the request command, and perform the release procedure for the port to which the release request command was input, excluding the port outputting the call request command. , In the connection procedure, when a call request command and associated request information are input to the node, the node issues a call request command to each of the free ports corresponding to the links confirmed to be released by the node. and request information is relayed and output, and at this time,
If there are multiple call request commands, the request information of the port that received the first call request command is relayed and output, each of the nodes performs the connection procedure independently, and the node that relayed the call request command is , waits for a call response command to be input to the port that relayed and outputted the call request command, and the node that received the call response command relays and outputs the call response command to the port to which the input of the call request command arrived first, and then outputs the call request command. The port to which the command input arrived first and the port to which the call response command input arrived first are maintained from now on, and the node that allows object transfer, receives the call response command from among the ports that relayed the call request. Output a release request command from a port for which there was no call response command, a port for which there was a call response command but was not the first to arrive, and a port for which the call request command was not for the first arrival, perform release procedures for these ports, In the maintenance operation, the node performs the connection by outputting each input to the other port of the two ports for which the connection procedure has been completed and maintenance is possible, and When the input command is a maintenance request, object transfer is allowed between the two ports, and when a release request command is input to at least one of the two ports, objects are transferred from both ports. Outputs a release request command and performs release procedures for both ports; The link transfers commands, call information, and objects logically independently, and for the call information, the request information is always the call request command. A distributed transport exchange system characterized in that objects are always sent together with maintenance request commands. 2. In a network comprising a node, a plurality of stations, and links connecting the nodes and the stations or between the nodes and through which objects are transferred, the objects are serial or parallel digital signals, analog signals and objects. the station has at least one of a release procedure for the link, a call origination and call termination procedure for the network, and a mode for transferring objects in the network; Output a release request command to the port of the station,
After that, when a release request command is input on the port, confirm that the link on the port of the station is released,
Among the stations, a station to which a release request command is input when it is not in a call origination procedure performs a release procedure, and the node has at least two ports and has a transport path that includes a release procedure, a connection procedure, and a maintenance procedure. At any point in the calling procedure, or when it confirms that the link on its port is released, the station outputs a call request command to the port and at least the called station A call is made by sending request information including an address, and if a call response command is input within a predetermined period, the system transitions to object transfer mode, and if a call response command is not input within the predetermined period. enters backoff, and when it enters backoff, it stops outputting the call request command and outputs a release request command, and the length of the backoff period is random, and after the period has elapsed, the above call is resumed. performs the procedure, and even if a release request command is input during the calling procedure, the station ignores the release request command, and in the object transfer mode, the station outputs a maintenance request command to the port of the station, When a maintenance request command is input to the port, object transfer is enabled at the port, and when a release request input is detected during object transfer mode, the release procedure is entered, and from then on, object transfer is performed.
This will not be done unless the node enters object transfer mode again. When the node finds a port on which to perform the release procedure during the connection procedure, it outputs a release request command to that port, and then a release request command is input on the port. The node then confirms that the link on the port of the node is released, and performs the release procedure on the port to which the release request command was input, excluding the port that outputs the call request command, and the node , In the connection procedure, when a call request command and accompanying request information are input to the node, the call request command and request information are sent to each of the free ports corresponding to the links confirmed to be released by the node. Relay output, and at this time,
If there are multiple call request commands, the request information of the port that received the first call request command is relayed and output, each of the nodes performs the connection procedure independently, and the node that relayed the call request command is , waits for a call response command to be input to the port that relayed and outputted the call request command, and the node that received the call response command relays and outputs the call response command to the port to which the input of the call request command arrived first, and then outputs the call request command. The port to which the command input arrived first and the port to which the call response command input arrived first are maintained from now on, and the node that allows object transfer, receives the call response command from among the ports that relayed the call request. Output a release request command from a port for which there was no call response command, a port for which there was a call response command but was not the first to arrive, and a port for which the call request command was not for the first arrival, perform release procedures for these ports, In the maintenance operation, the node performs the connection by outputting each input to the other port of the two ports for which the connection procedure has been completed and maintenance is possible, and When the input command is a maintenance request, object transfer is allowed between the two ports, and when a release request command is input to at least one of the two ports, objects are transferred from both ports. Outputs a release request command and performs release procedures for both ports; The link transfers commands, call information, and objects logically independently, and for the call information, the request information is always the call request command. A distributed transport exchange system characterized in that objects are always sent together with maintenance request commands.