Robust transport of IP traffic over wdm using optical burst switching

[0001] This application claims the benefit of the filing date of U.S. Provisional Application Ser. No. 60/161,518, filed Oct. 26, 1999.

[0002] 1. Field of the Invention

[0003] The present invention relates to the routing of Internet Protocol (IP) traffic using optical burst switching and more particularly the present invention relates to selecting the offset between a control packet and a data burst to optimize the network performance.

[0004] 2. Description of the Related Art

[0005] Rapid growth in the volume of Internet traffic over the last decade has generated a considerable amount of interest in devising new high-speed transmission and switching technologies. Wavelength division multiplexing can support a number of simultaneous high-speed channels on a single optical fiber and can thereby provide an enormous bandwidth at the physical layer. In order to exploit this bandwidth to meet the future traffic requirements, higher layer communication protocols must be developed to make efficient use of the transmission capacity of such optical fiber arrangements.

[0006] Presently, wavelength division multiplexing deployment comes in two varieties, namely, wavelength routing and SONET/SDH framing on wavelengths. In wavelength routing, a complete wavelength (or a sequence of wavelength segments joined by wavelength converters is assigned to a communication path between the two end-points. Such wavelength paths are preconfigured, and there is no need for optics-electronics-optics conversion at the intermediate nodes. However, such a provisioning of a complete wavelength tends to be inefficient when there is not enough traffic between the two end-points or when the traffic between them is bursty. In SONET/SDH framing on wavelengths, a time slot structure is created on the wavelength. An end-to-end communication path is established by assigning time slots on wavelengths of successive hops. The intermediate nodes extract/insert data into appropriate time slots. In this approach, the intermediate nodes have to perform optics-electronics-optics conversion for extracting/inserting data (also called multiplexing) into time slots. Since the operating speed of electronic devices is considerably slower than the transmission speed provided by the optical wavelength division multiplexing, the optic-electronics-optic conversion at the intermediate nodes in the data path should be eliminated.

[0007] Ideally, an all-optical packet eliminates the electronics entirely, thus removing the speed bottleneck as well as overcoming the shortcomings of the wavelength routing approach. In an all-optical packet switch, the data packets arriving on an incoming optical fiber are switched to an outgoing fiber in an entirely optical domain.

[0008] As a presently implementable alternative to all-optical packet switches, optical burst switching still allows the switching of data bursts in the optical domain by performing resource allocation in the electronic domain. In optical burst switching, a control packet precedes every data burst and the control packet and the corresponding data burst are launched at the source at points in time separated by an offset. The offset is determined at the time that the control packet is launched at the source. The control packet includes information required to route the data burst through the network and also includes the length of the corresponding data burst and its offset value. The control packet is processed electronically at each of the intermediate nodes for making routing decisions and the switching fabric at each node is configured accordingly to switch to the data burst that is expected to arrive after a time interval corresponding to the offset field of the control packet. Thus, the data burst is entirely optically switched to eliminate the electronic bottleneck.

[0009] The present invention provides for the determination of the offset between the control packet and the data burst. While the offset must be at least as large as the (worst-case) sum of the processing times for the control packet at each of the intermediate nodes, the present invention determines an offset which can reduce the contention among reservations requested by control packets of different flows (originating at possibly geographically dispersed end points) that traverse a given intermediate node so as to significantly improve the performance of the optical burst switching arrangement. That is, the present invention determines the offsets of successive data bursts of any given flow from their control packets which results in the reliable operation of the optical burst switching wavelength division multiplexing network. The determination is made for any flow independently of other flows. In the present invention, the data bursts of any given flow are effectively released into the network at systematically random times. Further, the release times are uncorrelated across the flows. These effects improve the burst blocking performance at intermediate nodes in the optical burst switching wavelength division multiplexing backbone.

[0019] Before beginning a detailed description of the subject invention, mention of the following is in order. When appropriate, like reference numerals and characters may be used to designate identical, corresponding or similar components in differing drawing figures. Furthermore, in the detailed description to follow, example sizes/models/values/ranges may be given, although the present invention is not limited thereto. Still furthermore, the clock and timing signal figures are not drawn to scale, and instead, exemplary and critical time values are mentioned when appropriate. In addition, well-known power connections to the components have not been shown within the drawing figures for simplicity of illustration and discussion and so as not to obscure the invention.

[0020] FIG. 1 is a block diagram of an output interface in an optical burst switching node. Nodes 150, 151, 152, and 153 are the intermediate nodes in an end-to-end path of the data burst. When the data burst 160 is ready to be transmitted at the source, first, a control packet 170 is launched, and the data burst is launched after an offset 180 from the start of the control packet 170. In the control unit 100 of an output interface of the given intermediate node, the control packet 170 is first converted from an optical signal into an electrical signal by an optical-electrical converter 110. The control packet is processed in an electronic domain by routing module 120 which performs label swapping for taking routing decisions (i.e., determining the outgoing fiber over which the control packet, and hence the impending data burst, is to be forwarded) and a wavelength scheduler 130 to determine the particular wavelength in the outgoing fiber over which the impending data burst is to be forwarded. The optical cross-connect is configured to switch the data burst corresponding to that control packet that is expected to arrive after the time equal to offset field in the control packet, onto the outgoing fiber and wavelength in that fiber as determined by the routing and wavelength scheduler modules. The control packet is then converted from electrical domain into an optical domain in an electrical-optical converter 140 and is forwarded on the control channel of the outgoing fiber as determined by the routing module above.

[0021] FIG. 2 is a block diagram of a transporting network Internet Protocol (IP) traffic over an optical burst switching wavelength division multiplexing transmission backbone using multiprotocol label switching.

[0022] Internet Protocol (IP) routers 201,202, and 203 are disposed at the ingress of the optical backbone and Internet Protocol routers 230 and 240 are disposed at the egress of the backbone. Intermediate optical cross-connects (nodes) 210, 211, and 212 are disposed between the ingress routers and the egress routers. Data bursts are assembled at the ingress routers and delivered to the egress routers via the intermediate nodes using optical burst switching. It is assumed that there is no buffering of data bursts at the intermediate nodes. Semi-permanent data pipes can be set up between different ingress-egress pairs using multiprotocol label switching (MPLS).

[0023] An Internet Protocol routing engine causes a major bottleneck at high transmission speeds due to its processing requirements. Multiprotocol label switching (MPLS) is a forwarding technique which uses the labels associated with packets to make packet forwarding decisions at the network nodes rather than by conventional destination-based hop-by-hop forwarding arrangements. In multiprotocol label switching (MPLS), the space of all possible forwarding options is partitioned into forwarding equivalence classes. For example, all of the packets destined for a given egress node which have the same quality of service requirement may belong to the same forwarding equivalence class. The packets are labeled at the ingress in accordance with the forwarding equivalence class with which they belong. Each of the intermediate nodes uses the label of an incoming packet to determine its next hop and also performs label swapping, that is, it replaces the incoming label with the new outgoing label which identifies the respective forwarding equivalence class for the downstream node. Such a label-based forwarding technique reduces the processing overhead required for routing at the intermediate nodes, thereby improving their packet forwarding performance and scalability. Furthermore, the label swapping used by multiprotocol label switching can be used to create a multipoint to point routing tree rather than a routing mesh used in conventional networks. Multiprotocol label switching also provides constraint-based routing in which the ingress node can establish an explicit route through the network rather than inefficiently carrying the explicit route in each packet. Instead, multiprotocol label switching allows the explicit route to be carried only at the time that the label switched path is set up. The subsequent packets traversing this path are forwarded using packet labels.

[0024] The control packets that precede the data bursts can be used to carry multiprotocol label switching (MPLS) labels. The intermediate nodes use the labels in incoming control packets in addition to offset and length of data burst fields to set up the switch fabric for the data burst. The data bursts do not need to carry any labels. Multiprotocol label switching (MPLS) allows the establishment of data pipes through an optical burst switching wavelength division multiplexing domain between different ingress-egress router pairs. These data pipes will be referred to hereinafter as optical LSP's (label switched paths).

[0025] FIG. 3 is a block diagram that comprehensively depicts various operations occurring in the end-to-end data path. Note that the operations occurring in the control path have already been discussed in relation to FIG. 1. A medium access control interface 350 is shown as being disposed between the Internet Protocol (IP) layer 300 and the optical layer 370. The medium access control layer 350, which includes a burst assembly 313 and a burst scheduler 324 and shaper 335. The burst assembly module 313 assembles data bursts from the packets generated by the Internet Protocol (IP) layer 300 for each optical LSP. It is possible for the burst assembly module to assemble a plurality of data bursts simultaneously. The burst schedule module 324 determines the sequence in which the assembled data bursts are to be released onto the optical LSP. The stream of data bursts at the output of the burst scheduler 324 is inputted to the shaper 335. For every data burst, the shaper 335 determines the value of the offset to be maintained between that data burst and its corresponding control packet. The shaper 335 then forms the control packet and transmits it over the control channel of the optical LSP. The control packet includes information such as the offset value between the data burst and itself, the length of the data burst and the routing label. The shaper 335 causes the data burst to be outputted to the optical LSP after being delayed a period of time equal to the offset value after the control packet has been transmitted. Note that all the processing in the data path occurs at the source and the destination of the optical LSP, while the intermediate nodes are transparent to the data path. This transparency is due to the processing that occurs in the control path at every intermediate node.

[0026] Various quality of service and priority considerations can be used at the Internet Protocol (IP) layer 300, at the burst assembly module 313, and at the burst scheduler module 324. Examples are DiffServ at the Internet Protocol (IP) layer 350, a timer-based burst assembly for delay-sensitive data at the burst assembly module 313 and prioritized burst scheduling at the burst scheduler module 324.

[0027] An output interface of a node in the optical burst switching wavelength division multiplexing domain receives traffic from different optical LSP's. This creates the potential for contention among the data bursts of different optical LSP'S. When the control packets from different optical LSP's request reservations for their data bursts on a particular wavelength of a given output fiber for time intervals which overlap each other, hereinafter referred to as burst blocking, only one of these requests can be granted. Accordingly, some control packets must be dropped at that interface; and this, in turn, results in the loss of data bursts corresponding to the dropped control packets.

[0028] The data loss rate due to burst blocking will be large if the reservation requests arriving at a given output interface from different optical LSP's are time correlated. Such time correlation often arises due to transmission control protocol (TCP) that is widely used in the Internet for end-to-end data transport reliability, and congestion and flow control. Furthermore, due to the unpredictability of traffic, it is difficult to always guarantee a low burst blocking probability.

[0029] In accordance with a present invention, a shaping mechanism, including the shaper 335, for example, is incorporated in the medium access control layer 350 at the ingress thereof which facilitates the determination of offsets of the successive data bursts of a particular optical LSP from their corresponding control packets so as to maintain a low burst blocking probability at all times in the optical burst switching wavelength division multiplexing layer. The shaping mechanism removes proactively the time correlation among the reservation requests of different optical LSP's and enforces predetermined statistics on the data stream entering the optical burst switching wavelength division multiplexing layer, irrespective of the statistics of packet arrivals from the Internet Protocol (IP) layer that resides over it. Due to the bufferless operation of the optical burst switching wavelength division multiplexing layer, this statistic is invariant, even if the burst stream traverses multiple nodes in the optical burst switching wavelength division multiplexing domain. The knowledge of statistics (enforced by the shaper) of burst arrivals from different optical LSP's that share an outgoing interface at any intermediate node allows for the computation of the burst blocking probability at that output interface. This computation can be combined with the admission control scheme so as to maintain a low burst blocking probability.

[0030] The offset between a data burst and its corresponding control packet has two parts, namely, a constant part to account for the processing time of the control packet at the intermediate nodes and a variable part which is varied from burst to burst to lower the probability of burst blocking. The variable part of the offset for the i th data burst, denoted by δ_i, is determined as follows:

[0031] Let T0=0, T₁, T₂, . . . denote the times of occurrences of points of a random point process in which the time periods between the occurrences of successive points (i.e., Ti-Ti-1, for i≧1) are independently and identically distributed according to the probability distribution F(.). Let T0(ω)=0,T₁(ω), T2(ω), . . . denotes a particular realization (sample path) of this random point process. If the i th data burst arrives at the shaper at time ai, and that the (i−1)th data burst is released at T_ki−1(ω), then the i th burst is released at time
T_k(i−1)
where T_ki(ω) is the first point after T_k(i−1)(ω) satisfying the following inequality:
T_ki(ω)−T_k(i−1)(ω)≧L_i−1 and T₁(ω)≧α_i.

[0032] Hence, the offset between the i th data burst and the control packet corresponding to it is determined by the following equation:
δ_i=T_ki(ω)−α_i.

[0033] The shaping scheme described above (see FIG. 4) is equivalent to leaky bucket regulator with no buffering provided for tokens, and in which tokens arrive at T0(ω),T1(ω), T2(ω), . . . .

[0034] FIG. 4 is a timing diagram of the data bursts of a given optical LSP before and after shaping and the control packets. FIG. 4(A) illustrates the data bursts of sizes L1, L2, L3, and L4 before shaping by the shaper 335. They arrive at the shaper at times a1, a2, a3, and a4, respectively. FIG. 4(B) illustrates the arrival of the tokens T0, T1, T2, T3, T4 and T5. FIG. 4(C) illustrates the completion times d1, d2, d3,d4 of data bursts release at the output of the shaper. FIG. 4(D) illustrates the control packets corresponding to the data bursts of FIG. 4(A).

[0035] As illustrated in FIG. 4, the data bursts are of an arbitrary length. As noted above, the token arrivals have been chosen so as to be randomly distributed. The first data burst of size L1 is inputted to the shaper at time a1. The control packet for that burst is formed and immediately launched. The shaper 335 releases the data burst into the optical LSP at time T1(ω) by having its transmission beginning at the arrival of token T1 which occurs at a time δ1 after the start of the control packet corresponding to the data burst L1. Thus, δ1 is also the offset value in the offset field of the control packet. Similarly, after shaping, the second shaped data burst of size L2 has its transmission beginning at the arrival of the token T2(ω) which occurs at a time δ2 after the start of the control packet corresponding to the data burst L2. Shaped data burst of length L3, on the other hand, has its transmission beginning at the arrival of token T4(ω) which occurs at a time δ3 from the start of the control packet corresponding to that data burst. This is due to the fact that the token T3(ω) arrives during the pendency of the shaped data burst L2, which terminates at d2. Since the shaped data burst L3 can not commence prior to the completion of the shaped data burst L2, token T3(ω) is not used. Shaped data burst L4 has its transmission beginning at the arrival of token T5(ω) which occurs at a time δ4 from the start of the control packet corresponding to the data burst L4.

[0036] The type of shaping described above regulates the average rate at which data bursts of a given optical LSP are released into the optical burst switching wavelength division multiplexing layer. This rate is equal to the reciprocal of the mean of the probability distribution F(.) used to generate the tokens. Furthermore, the randomized generation of tokens prevents synchronization among the data burst streams of different optical LSP's. This is significant in that if the data burst streams of two optical LSP's traversing the same output interface of a particular node in the optical burst switching wavelength division multiplexing network happen to be synchronized, the probably of burst blocking at that interface will be high, thereby causing excessive data losses. Note that, with deterministic offsets, such a synchronization will often arise especially when transmission control protocol (TCP) is used for end-to-end data transport.

[0037] Another crucial benefit of the proposed shaping scheme is that it imposes the following property on the stream of data bursts of any optical LSP. Let {A(t)}_t□0 denote total data arriving over an optical LSP until time t at any node (ingress or intermediate) in the optical burst switching wavelength division multiplexing network. Then,
A(t)−A(s)≦A_x(t)−A_x(s), a.s., (almost surely), for all t≧s,  (1)
where {A_x(t)}_t≧0 denotes total data that would have arrived on that LSP until time t at that node, if data bursts were arriving at T0, T1, T2, . . .

[0038] It is easy to see that the domination as in Eq. 1 holds at the output of the shaper of every optical LSP, by virtue of the shaping scheme. As data bursts traverse various nodes in the optical backbone, some of them can only be discarded, due to contention. Furthermore, due to inherently bufferless forwarding, the relative positions of the data bursts of any optical LSP remain unchanged even after these data bursts traverse a number of nodes. Hence, the domination as in Eq. 1 holds at the output interface of every node that a given optical LSP traverses.

[0039] A framework for traffic engineering, based on the above noted shaping scheme, is provided below and in addition, the role of this shaping scheme in improving the performance of an optical burst switching wavelength division multiplexing layer will be demonstrated below via simulations for the case of TCP/IP traffic.

[0040] The following is a description of one example of how the shaping scheme can be used for traffic engineering in an optical burst switching wavelength division multiplexing network. Consider an output interface of any node in an optical burst switching wavelength division multiplexing network. Suppose that this node is being traversed by N optical LSP's with the provisional data rates of r₁, . . . ,r_N, respectively. If the data bursts entering into these LSP's are shaped at the ingress using Poisson shapers (this means that the probability distribution for the time interval between the successive tokens of the i th optical LSP, denoted by F_i(.), is chosen to be exponential), the following holds for their data arriving at the output interface under consideration. For all t≧s,
Ai(t)−Ai(s)≦AP(r₁)(t)−AP(r₁)(s),
a s, for all 1≦i≦N ,and  (2)
$\begin{array}{cc}A\left(t\right)-A\left(s\right)=\sum _{i=1}^N{A}_i\left(t\right)-A_i\left(s\right))\le A_{P\left(r\right)}\left(t\right)-A_{P\left(r\right)}\left(s\right),a.s.& \left(3\right)\end{array}$
Here, Ai(t) denotes the total data arriving over the i th optical LSP until time t, AP(r)(t) denotes the data that would arrive if the data bursts were arriving according to a Poisson process of rate r, and $r=\sum _{i=1}^N{r}_i.$

[0041] Now, if p_actual(r₁, . . . ,r_N) denotes the actual burst blocking probability at the given output interface, it is intuitively appealing to say that
p_actual(r₁, . . . ,r_N)≦p_Poisson(r),  (4)
where p_Poisson(r) denotes the burst blocking probability at that interface if the bursts were arriving according to the Poisson process of rate r. The right hand side of Inequality 4 is given by the well known Erlang loss formula, $\begin{array}{cc}{p}_{\mathrm{Poisson}}\left(r\right)=\frac{{\left(r/\mu \right)}^c/c!}{\sum _{i=0}^c{\left(r/\mu \right)}^c/c!}& \left(5\right)\end{array}$
where c is the total number of wavelengths at the output interface, and 1/μ is the average burst transmission time.

[0042] If the establishment of a new optical LSP, requiring a data rate of r_N+1 and a burst blocking probability of p_N+1, is requested through a given output interface, it can be admitted if and only if $\begin{array}{cc}{p}_{\mathrm{Poisson}}\left(r\right)\le p_{N+1},\mathrm{with}r=\sum _{i=1}^{N+1}{r}_i& \left(6\right)\end{array}$

[0043] By virtue of the shaping scheme and the connection admission control procedure described above, the burst blocking performance of every optical LSP is guaranteed. It is also possible to render some end-to-end delay characteristics to optical LSP as follows.

[0044] As seen from FIG. 3, the various elements in the MAC layer 350 such as the burst assembler 313, the burst scheduler 324 and the shaper 335, introduce some amount of delay at the ingress of an optical LSP. Since the former two are not discussed in detail herein, the following is a description of how to control the component of end-to-end delay that is due to shaper 335. Assume that the establishment of an optical LSP, requiring a data rate of r_N+1, a burst blocking probability of P_N+1 and an end-to-end delay guarantee of D_N+1, is requested between a chosen ingress-egress pair. The actual token rate may be chosen such that:
Prob[Time interval between successive tokens>
D₁]≦□, and Token rate>r_N+1.  (7)
This value token rate is then used in Eq. 6 in place of r_N+1 to take admission control decision.

[0045] FIG. 6 shows how IP DiffServ classes can be mapped onto optical LSP's that are now reliable, as well as have certain delay characteristics.

[0046] Another quality of service dimension is to provide a number of optical LSP's in the optical backbone, each providing different levels of reliability given in terms of burst blocking probability. The reliability of different optical LSP's can then be mapped onto some cost function. This, in turn, can be used by the routing protocols to forward IP packets to appropriate edge routers depending on their quality of service needs (now in terms of loss rate). This is depicted in FIG. 7.

[0047] The bottleneck output interface (fiber) of a node in an OBS WDM network supporting three OC12 wavelengths (622 Mb/s per wavelength) per output interface has been simulated. This interface is traversed by a number of optical LSP's. Ten such optical LSP's each carrying ingress-to-egress data traffic supported on TCP/IP are assumed. There are (forward paths of) 4 TCP sessions in each of these optical LSP's. The acknowledgment paths (or reverse paths) of these TCP's are taken to be lossless, and they introduce only a constant delay. Simulations were run with a simulation tool.

[0048] Each of the 40 TCP sessions is started at time instant sampled from the uniform distribution over (0 s, 1 s). Once started, all TCP sources always have data to send. For simplicity, every data burst that is assembled at the MAC layer is taken to be precisely one IP packet. The delay introduced by the reverse path of every TCP session is sampled from the uniform distribution as explained in the next section.

[0049] As shown in FIG. 5, the burst traffic offered to each LSP is shaped at the ingress. The probability distribution Fi(.) used in shaping the burst traffic of the i th optical LSP is taken to be exponential with a mean l/r1. This causes the data burst arrivals at the output of each shaper to be dominated by the Poisson process of rate r1, and the total process of data bursts at the bottleneck output interface to be dominated by the Poisson process of rate $r=\sum _{i=1}^{10}{r}_i.$
Simple greedy and exhaustive wavelength selection policy may be used to assign the reservations to the control packets arriving at the bottleneck output interface. Simulation experiments have been run in different regimes of the target burst blocking probability, namely, 10⁻², 10⁻³ and 10⁻⁴. For each of these values, the total allowable load rat that output interface is calculated using Erlang loss formula (Eq. 5), with c=3. r_i is then taken to be r/10, for i=1, . . . , 10. For the target burst blocking probabilities of 10⁻², 10⁻³ and 10⁻⁴, the delay introduced by the reverse path of every TCP session is sampled from the uniform distribution over [0 ms, 1 ms), [0 ms, 25 ms) and [0 ms, 50 ms), respectively. This is done so that the actual aggregate load offered by all TCP's is not much lower than the designed throughput value. For example, 40 TCP's fail to offer an average load as large as about 311 Mb/s at the packet loss probability of 10⁻² in the end-to-end path, if their round trip times are larger than about 1 ms. It is as fundamental fact that the TCP throughput significantly deteriorates if the end-to-end packet loss probability is much larger than the inverse square of the product of the bottleneck bandwidth and the round trip delay. And, it is clearly trivial to establish Inequality 4 if the offered average load itself is much lower than the designed value for the load. The results are shown in the Table 1 below.

[0050]

	Throughput (MB/s)	Burst blocking probability
Simulation	With shaping	Without	With shaping	Without
experiment	Observed	Designed	shaping	Observed	Designed	shaping
1	302.29	311.00	10.64	0.73 × 10−2	1.72 × 10−2	1.57 × 10−1
2	146.68	155.0	29.05	1.17 × 1010−3	2.00 × 10−3	0.97 × 10−1
3	62.20	62.20	26.97	0.7 × 10−5	1.51 × 10−4	0.93 × 10−1

[0051] This concludes the description of the example embodiments. Although the present invention has been described with reference to a number of illustrative embodiments thereof, it should be understood that numerous other modifications and embodiments can be devised by those skilled in the art that will fall within the spirit and scope of the principles of this invention. More particularly, reasonable variations and modifications are possible in the component parts and/or arrangements of the subject combination arrangement within the scope of the foregoing disclosure, the drawings, and the appended claims, without departing from the spirit of the invention. In addition to variations and modifications in the component parts and/or arrangements, alternative uses will also be apparent to those skilled in the art.