Synchronous Optical Hypergraph Papers

(See also Ph.D. Thesis)

Yoram Ofek, "The Conservative Code for Bit Synchronization," IEEE Trans. on Communications, Volume: 38, Number: 7, Pages: 1107-1113, July 1990.

ABSTRACT

A novel coding scheme for bit synchronization the conservative code, is presented and analyzed in this paper. Each codeword is characterized by having a predefined number of transitions, with a known delimiting transition at the end, i.e., the number of transitions is conserved. As a result, it is possible to decode the incoming serial bit-stream without explicitly recovering the receiving clock with a phase-locked loop. Thus, it is possible to receive messages from asynchronous sources without any training period. This code can be extremely useful in communication over a passive optical star.
In the analysis, the efficiency or capacity of the code is computed with two additional constraints (i) limited run-length and (ii) balancing. It will be shown that this coding scheme is efficient when both constraints are applied. The importance of this analysis is to show, that the additional constraints imposed on the encoding, do not cause a significant reduction in its efficiency. Hence, the realization of the encoder and decoder is possible with current technology.
The design of a serial electronic interface is described. Its goal is to maximize the interface bandwidth (greater than 1 gigabit/sec with GaAs technology), which is usually the bottleneck of an optical communication system. It is achieved by reducing the critical timing path to one flip-flop and one NOR gate, and by having a hierarchical interface design of four levels.

Yoram Ofek, "Integration of Voice Communication on a Synchronous Optical Hypergraph," IEEE INFOCOM'88, 1988. Also published in: IBM Research Report: RC 13341, December 1987.

ABSTRACT

The optical hypergraph is a novel network architecture in which each edge of the hypergraph is a multiple-access broadcast medium constructed as a passive optical star coupler. Access to each net (edge) is time-slotted, and the system maintains global slot synchronization. The integration of voice into the system is done by reserving time slots in a periodic manner. A packet which contains several voice parcels from different phone conversations is transferred in these slots. These parcels may have different destinations on the optical net. As a result of the global end to end synchronization, the delay from the source to the destination is a known constant, with accuracy of plus or minus half a time slot.
In the analysis, it is shown that the system improves its operation as the communication bandwidth increases. In other words, the algorithms and protocols improve in performance as the communication bandwidth increases. Two criteria are used to exhibit this phenomenon (i) the utilization efficiency and (ii) the end to end delay.

Yoram Ofek, Michael Faiman, "Distributed Global Event Synchronization in a Fiber Optic Hypergraph Network," The 7th International Conference on Distributed Computing Systems, IEEE, Pages: 307-314, 1987.

ABSTRACT

The principles and the design of global event synchronization in a large area network (about 10,000 nodes within 1000$km sup 2$), are presented and nalyzed in this paper. The network architecture is a hypergraph, its edges are nets or buses, and its vertices are nodes.

Yoram Ofek, Moshe Sidi, "Design and Analysis of a Hybrid Access Control to an Optical Star using WDM," Journal of Parallel and Distributed Computing, Volume 17, Pages: 259-265, April 1993. Also published in: IEEE INFOCOM'91. Also published in: IBM Research Report: RC 16059, August 1990.

ABSTRACT

A passive optical star is an ideal shared medium, from both fault tolerant and access synchronization point of views. The communication over an optical star merges to a single point in space and then broadcast back to all the nodes. This circular symmetry facilitates the solution for two basic distributed synchronization problems, which are presented in this work: (i) generating global event clock for synchronizing the nodes' operation, and (ii) distributed scheduling for accessing the shared passive medium, which is a hybrid (deterministic and random) technique.
We present, prove and analyze this hybrid scheduling algorithm which is equivalent to a distributed queue, and therefore, is also algorithmically fair. Furthermore, our solution has two additional properties: destination overflow prevention and destination fairness. The effective solution of these problems can be used for efficiently implementing a local area network based on a passive optical star.

Yoram Ofek, "The Partial Hypergraph as a Centralized Switch," ICCC'88, Tel-Aviv Israel, November 1988. Also published in: IBM Research Report: RC 13860, July 1988.

ABSTRACT

The optical hypergraph is a novel distributed network in which each edge of the hypergraph is a multiple-access broadcast medium constructed as a passive optical star coupler. In this work, the partial optical hypergraph is viewed as a centralized switching network. The nodes with two ports (switch nodes) are centered in one building, and the nodes with one port (external nodes) are distributed within an area of 0-20 kilometers around the switch.
The main result of this work is a flow control protocol for an arbitrary traffic pattern, which includes algorithms for preventing overflows, while maintaining the maximum switching capability of the switch nodes. Overflow prevention may cause dead-locks, so an algorithm for avoiding dead-locks is presented. These algorithms are realized at the network interface, and therefore, can operate in real-time at a traffic rate of over a gigabit/sec per link. This network architecture demonstrates the close relationship between centralized and distributed systems.

Yoram Ofek, "Passive Optical Star as a Building Block of a Distributed System," IBM Research Report: RC 13247, November 1987.

ABSTRACT

The objective of this report is to propose and justify a new architecture for a metropolitan area network. The basic building block of this system is a passive optical star, which operates with a bandwidth of more than one gigabit/second. The system is completely distributed with a protocol for periodic exchange of state information among nodes. Based on this state information algorithms for access control and synchronization algorithm are implemented.
A new coding scheme, the conservative code, for bit synchronization is presented and analyzed. The code is characterized by having predefined number of transitions in every codeword, with a known delimiting transition at the end of each codeword. As a result, it is possible to decode the incoming bit-stream without explicitly recovering the receiving clock with a phase-locked loop. Thus, it is possible to receive messages from asynchronous sources without any training period.
The architecture is compared with the dual ring topology and the active star network. It is shown that the proposed architecture has advantages both in performance and reliability. Further, this architecture is shown to exploit unique properties of the fiber optic communication-the ability to construct very large passive network with a very high bandwidth. Using the passive star it is possible to implement a larger network, by enabling the nodes access more than one optical star. In this way a network of thousands nodes can be constructed, with aggregate bandwidth of hundreds of gigabit/second. The extended network is called synchronous optical hypergraph, and a complete discussion of its properties is beyond the scope of this report.

Yoram Ofek, "Optical Hypergraph Construction Using a Single Optical Star With Wavelength-Division Multiplexing," DISCLOSR TDB, ORDER 89A 60470, 03-89, p.310-312, DOCKET YO8880037, Yorktown

ABSTRACT

A technique is described whereby a systematic method is used for constructing an optical hypergraph, by using a single optical star with wavelength-division multiplexing. The concept is an improvement over previous optical hypergraph techniques which used multiple optical stars, since all used the same wavelength. The concept of creating an optical hypergraph by using a single optical star with wavelength-division multiplexing provides two objectives:

1. Provides a means of exploiting the maximum energy distribution potential of the passive optical star by maximizing the number of nodes.
2. Provides enough communication capacity for the nodes, by using several wavelengths.

If the hypergraph is connected, a message can be forwarded between any two nodes which belong to arbitrary subsets.

Yoram Ofek, "Flow Control and Dead-lock Avoidance on the Partial Hypergraph," Computer Communications, Volume: 13, Number: 5, Pages: 283-289, June 1990.

ABSTRACT

The optical hypergraph is a distributed network in which each edge of the hypergraph is a multiple-access broadcast medium constructed as a passive optical star coupler. The partial optical hypergraph can be also viewed as a centralized switching network. The nodes with two ports (switch nodes) are centered in one location, and the nodes with one port (external nodes) are distributed within an area of 0-20 kilometers around the switching nodes.
The main result of this work is a flow control protocol for an arbitrary traffic pattern, which includes algorithms for preventing overflows, while maintaining the maximum switching capability of the switch nodes. Overflow prevention may cause dead-locks, so an algorithm for avoiding dead-locks is shown. These algorithms are realized at the network interface and therefore, can operate in real-time at a traffic rate of over a gigabit/sec per link. This network architecture demonstrates a close relationship between centralized and distributed systems. Potential applications of the partial optical hypergraph are varied and include large distributed databases, metropolitan area networks, factory automation, fault tolerant and real-time networks.

Yoram Ofek, "Passive Optical Star With Tunable Receiverfor Hybrid Access Control and Overflow Prevention," DISCLOSR TDB, ORDER 89A 61984, 09-89, p.331-338, DOCKET YO8880883, Yorktown

ABSTRACT

This article describes a hybrid access control for a slotted passive optical star. Each node uses a tunable receiver and two fixed-wavelength transmitters for realizing the following control functions: (i) hybrid (random/reservation) access control with collision resolution and (ii) destination overflow prevention. Given a passive optical star with one shared or multiple access data channel, we describe how to construct a control channel. The control channel makes an implicit use of multiple wavelengths. Each node has two transmitters with fixed wavelengths and one tunable receiver. The tunable receiver is used for scanning the spectrum of the transmitters in order to detect the transmitters that are active. The signaling, with the different wavelengths, over the control channel is not decoded explicitly with a serial-to-parallel converter. Therefore, very simple digital electronic hardware is required for the control channel. The objective of this design is to exploit the abandon fiber-optic spectrum, in order to simplify the control of a multiple access data channel. Only the transmission over the data channel is explicitly decoded, i.e., recovering the transmitter clock with a phase-locked loop for the serial-to-parallel conversion.
Using the two fixed-wavelength transmitters, the following functions are implemented in the control channel: (i) hybrid - random/deterministic access control with collision resolution and optimal throughput of 1 (even if only one node is loaded), and (ii) destination overflow prevention which assures no packet loss as a result of an overflow.
The Passive Optical Star: Fig 1 depicts the structure of a passive optical star. The optical star is an array of single-mode star couplers organized as a perfect shuffle. It is assumed that the optical star array is built in a small area in space, so the communication over the star merges to one point in space (called the center of the star), and then broadcasts back to all its nodes. The passive star coupler is a device with two inputs and two outputs, and is usually characterized so that it splits an input signal equally between the two outputs (3 dB attenuation). On the receiving side of each node there is a tunable filter or receiver which is used for detecting the control information. Synchronization and Timing: The center of the star serves as a single point-of-time reference to all the n nodes of the network. All nodes are synchronized and the transmission over the passive optical star is divided into equal intervals or time slots, Ts . The Synchronization Procedure:
Let Wi be the delay of nodei from the star's center. An imaginary circle with radius R (such that TR B Wi, 1&i&n) is drawn around all the n nodes of the star. Each nodei knowing its delay from the center, can place itself on this imaginary circumference by delaying the information it receives or transmits by TR - Wi, as shown in Fig. 2. As a result, all nodes can synchronize the beginning of their time slots, and can execute distributed algorithms that use the same state information. The Time Slot: The round trip delay from the imaginary circumference to the center of the optical star, 2TR, is divided into f time slots of equal duration, i.e., f(Ts) = 2TR . The Control Channels: The control channel is used for access and flow control of the shared data channel. Over the data channel using a distinct wavelength, a node can transmit one data packet for the duration of one time slot.
Implicit wavelength signalling is used over the control channel, which means that those signals are not decoded explicitly. Receiving over the control channel just requires the ability to determine, at every time slot, whether or not a specific control wavelength was active. The advantage of implicit signalling is that it does not require to recover the receiving clock from the serial bit stream, thus requiring very simple hardware. The existence or absence of a specific wavelength at a certain time slot constitutes one bit of information.
The control channel adds very little to the complexity of the serial interface. It does not require any buffering capability, only to store some state variables and to count the reservation requests. For the following algorithms each node needs two bits of information. Therefore, two distinct wavelengths are assigned to each node. That is, node i will signal its control information using gi1 and gi2. The signals are interpreted as shown in the table in Fig. 3. The control wavelengths used by node i have the following meaning: gi1 - access request or reservation for one packet. gi2 - overflow indication; it is active as long as the node is in an overflow condition. It is asserted before an overflow occur, so there is no loss of information. All other nodes will not transmit data to node i when its overflow signal is asserted. Access and Flow Control Algorithm: The algorithms for access and flow controls are combined together. Since the optical star is a broadcast medium and the nodes are synchronized (i.e., effectively place themselves on the imaginary circumference of Fig. 2) they all receive the same state information. As a result, at every instant of time, all nodes have the same global state information. Data Structure and Variables: For the algorithm the following data structure and variables are used: OR(t), OR(t-1), ... , OR(t-f) - are f+1 variables which record the number of .us outstanding requests at the f+1 most recent time slots. Request Queue - Each time a node receives its own packet reservation signal, it will put in the request queue the time its request should be granted. Note that the requests are granted using first-come, first-serve policy. SCi - is the slot counter value at node i. This is the node's local copy of the global clock, and at every instant of time t=SCi RSV-FLG - Reservation flag indicates that the node receives its own reservation signal. OVF1, OVF2, ... , OVFn, are n verflow flags, one for each node. The above variables change their values according to the state information that is detected by the tunable receiver. The tunable receiver scans the control spectrum from g11 to gn2, and it does so every time slot.
The Algorithm for Node i for Time Slot t:
Receive gj1 = 1 and OR(t-f) > 0 - OR(t)=OR(t)+1
If j=i, then write t+OR(t) into the Request Queue
Receive gj2=1 and OR(t-f) = 0 - OR(t)=OR(t)+1
If j=i, then RSV-FLG=t+R(t)
Receive gj2 - OVFj = gj2
Receive END of time slot t (after scanning gn2) -
If OR(t-f)=0, then COLLISION-RESOLUTION
If OR(t)>0 and OR(t-f) >t0, then OR(t)=OR(t)-1
RSV-FLG=0; For k=f to 1, DO OR(t-k)=OR(t-k+1)
SCi = SCi + 1; t = Sci; If (HEAD of Request Queue = t), then MY-TURN
Request to send a data packet - If Request Queue not FULL, then signal in the next with gi1; Buffer Overflow Hazard - Signal with gi1 as long as the overflow hazard exists

COLLISION-RESOLUTION Procedure:
If OR(t)-OR(t-1) = 1, then OR(t)=OR(t)-1
If OR(t)-OR(t-1) >1 and RSV-FLG >0, then
write RSV-FLG into the Request Queue

• MY-TURN Procedure: Destination overflow flag is not set - Send packet at the next time slot
• Read Request Queue; Destination overflow flag is set - Read Request Queue
• Reserve the transmission of this packet again after the destination overflow flag is de-asserted

Reference: Y. Ofek and M. Faiman, "Distributed Global Event Synchronization in a Fiber Optic Hypergraph Network," The 7th International Conference on Distributed Computing Systems, IEEE, pp. 307-314 (1987)

Philip Mckinley, Yoram Ofek, "Resource Sharing on an Optical Hypergraph Using Open Loop Locking," ????????

ABSTRACT

An optical hypergraph is a network architecture in which each edge of the hypergraph, a net, is a multiple-access broadcast medium constructed as a passive optical star. Access to each net is time-slotted, and slots are of fixed length. The major operational principle of the system is global synchronization which enables total event ordering. The network may have thousands of nodes which are distributed over an area of thousands of square kilometers.
This paper describes a mechanism for sharing independent, replicated data base objects among collections of cooperating processes in an optical hypergraph. Locks are used to provide mutual exclusion. By including lock requests as part of control information transmitted at the beginning of each slot, and by exploiting the fact that such control information pervades a hypergraph in short, bounded time. Locking a resource can proceed in an open loop fashion, i.e., locking without explicit acknowledgement messages, but with negative acknowledgement in the case of a failure. The basic functionality of the protocol is presented, with emphasis on adaptation to high network loads, either by aborting requests or by scheduling requests in two broadcast phases.

Yoram Ofek, "Passive Optical Star With WDM Couplers," DISCLOSR TDB, ORDER 89A 62035, 09-89, p.477-483, DOCKET YO8880884, Yorktown

ABSTRACT

This article describes a hybrid access control for a slotted passive optical star. The invention exploits commercially available technological advances in the construction of (i) single-mode passive star couplers and (ii) wavelength division multiplexing (WDM) couplers, which can efficiently merge and split two distinct wave lengths. One wavelength, g1, constitutes the data channel, and the other wavelength, g2, is used for network control. The following solution has two components: (i) hybrid - random/deterministic access control with collision resolution and optimal throughput of 1 (even if only one node is loaded), and (ii) destination overflow prevention which assures no packet loss as a result of an overflow. Passive Optical Star with WDM Couplers Fig. 1 depicts a passive optical star with WDM couplers. The optical star is an array of single-mode star couplers organized as a perfect shuffle. It is assumed that the optical star array is built in a small area in space, so the communication over the star merges to one point in space (called the center of the star), and then broadcasts back to all its nodes. The passive star coupler is a device with two inputs and two outputs, and usually characterized so that it splits an input signal equally between the two outputs (3dB attenuation).
Synchronization and Timing: The center of the star serves as a single point of time reference to all the n nodes of the network. All nodes are synchronized and the transmission over the passive optical star is divided into equal intervals or time slots, Ts. The Synchronization Procedure: Let Wi be the delay of node i from the star's center. An imaginary circle with radius R (such that TR / Wi, 1 <= i <= n) is drawn around all the n nodes of the star. Each node i knowing its delay from the center can place itself on this imaginary circumference, by delaying the information it receives or transmits by TR - Wi, as shown in Fig. 3. As a result, all nodes can synchronize the beginning of their time slots, and can execute distributed algorithms that use the same state information. The Time Slot: The round trip delay from the imaginary circumference to the center of the optical star, 2TR, is divided into f time slots of equal duration, i.e., f(Ts) = 2TR, The Control and Data Channels The transmission of control and data over the star is separated into two channels. Over the data channel, using g1, a node can transmit one data packet for the duration of one time slot. Over the control channel, the nodes are using implicit signaling for access control, collision resolution and destination overflow avoidance. Implicit signaling means that the receiving signal is not decoded explicitly. Receiving over the control channel just requires the ability to determine, at every instant of time, if the channel is active or not. The advantage of implicit receiving is that it does not require to recover the receiving clock from the serial bit stream (very simple hardware). Therefore, asynchronous nodes can send a very short control message (signal) without a long synchronization preamble. The disadvantage of implicit signaling is that the amount of information is very limited. The existence or absence of a signal at a certain time constitutes one bit of information. The control channel adds very little to the complexity of the serial interface. It does not require any buffering capability, only to store some state variables and to count reservation requests. For the following algorithms each node needs two bits of information. Therefore, the control slot, of duration Ts, is divided into 2n mini-slots, as shown in Fig. 3. Each node can signal its state information by using its two predefined control mini-slots.
The signals are interpreted as shown in the table in Fig. 3. The control minislots that are used by node i have the following meaning: msi1 - access request or reservation for one packet. msi2 - overflow indication; it is active as long as the node is in an overflow condition. It is asserted before an overflow occurs, so there is no loss of information. All other nodes will not transmit data to node i when its overflow signal is asserted. Access and Flow Control Algorithm: The algorithms for access and flow controls are combined together. Since the optical star is a broadcast medium and the nodes are synchronized (i.e., effectively place themselves on the imaginary circumference of Fig. 3), they all receive the same state information. As a result, at every instant of time all nodes have the same global state information. Data Structure and Variables: For the algorithm the following data structure and variables are used:
OR(t), OR(t-1), ... , OR(t-f) - are f+1 variables which record the number of outstanding requests at the f+1, most recent time slots. Request Queue - each time a node receives its own packet reservation signal, it will put in the request queue the time its request should be granted. Note that the requests are granted using first-come, first-serve policy. SCi - is the slot counter value at node i. This is the node's local copy of the global clock, and at every instant of time t=SCi . RSV-FLG - reservation flag indicates that the node receives its own reservation signal. OVF1, OVF2, ... , OVFn - are n overflow flags one for each node. The above variables change their values according to the state information in the control minislots.

The Algorithm for Node i
Receive msi1 = 1 and OR(t-f) > 0.
OR(t) = OR(t)+1
If j=i, then write t+OR(t) into the Request Queue
Receive msj2 =1 and OR(t-f) = 0 -
OR(t)=OR(t)+1
If j=i, then RSV-FLG=t+R(t)
Receive msj2 -

DATA BASE : TDBS - PAGE 15
OVFj = msj2
Receive END of control slot (after msn) -
If OR(t-f)=0, then COLLISION-RESOLUTION
If OR(t) >0 and OR(t-f) >0, then OR(t)=OR(t)-1
RSV-FLG=0
For k=f to 1, DO OR(t-k)=OR(t-k+1)
SCi = SCi + 1
t = SCi
If (HEAD of Request Queue = t), then MY-TURN
Request to send a data packet -
If Request Queue not FULL, then
signal with the next ms1i1
Buffer Overflow Hazard -
Signal with msi2 = 1 as long as the overflow
hazard exists

COLLISION-RESOLUTION Procedure:
If OR(t)-OR(t-1) = 1, then
OR(t)=OR(t)-1
If OR(t)-OR(t-1) > 1 and RSV-FLG >0, then
write RSV-FLG into the Request Queue

MY-TURN Procedure:
Destination overflow flag is not set
Send packet at the next time slot
Read Request Queue
Destination overflow flag is set
Read Request Queue
Reserve the transmission of this packet again after the
destination overflow flag is deasserted

Discussion: The proposed passive optical star system, with the access/flow control algorithm, has the following properties: The algorithm will operate correctly and efficiently also when the propagation delay is much larger than the packet delay (i.e., f > 1). The system can achieve maximum throughput even if only one node is loaded. The random-access mode enables very short response time. If collision occurs, the involved packets are rescheduled deterministically. Thus, a packet may be involved in a collision, at most, once. The system can be in the random-access mode only for the period of time it takes for the state information to propagate through the optical star (<2TR). Collision is resolved by the algorithm in a very simple way, and can be performed in real-time. Fair and stable performance - the algorithm implemented the system as a distributed queue, and, therefore, the service is a fair - "first-come, first- serve." The mechanism described in this disclosure can serve for assigning additional wavelengths to users, according to a higher level protocol. In other words, the proposed mechanism can serve as the control layer of a large WDM system.

References:
1 C. M. Lawson, P. M. Kopera, T. Y. Hsu and V. J. Tekippe, "In-Line Single Mode Wavelength Division Multiplexer/Demultiplexer," Electronic Letters 20, 963 (1984).
2 Y. Ofek and M. Faiman, "Distributed Global Event Synchronization in a Fiber Optic Hypergraph Network," The 7th International Conference on Distributed Computing Systems, IEEE, pp. 307-314 (1987).