Advances in Photonic Packet Switching: An Overview <s> Deflection Routing <s> The achievable aggregate capacity for a variant of the basic multihop approach in which minimum distance store-and-forward routing is replaced by a hot-potato routing algorithm is determined. With hot-potato routing, all packets simultaneously arriving at a given node and not intended for reception at that node are immediately placed onto the outbound links leaving that node; if two or more packets contend for the same outgoing link to achieve a minimum distance routing, then all but one will be misrouted to links which produce longer paths to the eventual destination. Attention is confined to the development of an analytical methodology for finding the probability distribution of the number of hops with hot potato routing for symmetric networks under uniform traffic load. Results show that the maximum throughput achievable with hot-potato routing can be as low as 25% of that for store-and-forward routing, and that the relative degradation increases as the number of nodes grows larger. This implies that the link speed up needed to produce a significant overall capacity advantage with hot potato should be at least a factor of 10. > <s> BIB001 </s> Advances in Photonic Packet Switching: An Overview <s> Deflection Routing <s> A comprehensive explanation of the newest developments in optical networks in the MCGRAW-HILL COMPUTER COMMUNICATIONS series. Case studies and research projects at AT&T, Fujitsu, and NTT are considered in order to provide the reader with hands-on information which can be applied in practice. <s> BIB002
Optical buffering was, to a great extent, inspired by their conventional electronic network counterparts. In the electronic networks, the link bandwidth is much less than today's optical fiber's capacity and many efforts were put into increasing link utilization. In a network deploying optical buffers, each packet is guaranteed to arrive at its destination along the shortest possible path, and for a given connectivity the expected number of hops is minimized. Implementing optical buffers involves a great amount of hardware and complex electronic controls. Another issue that arises with optical buffer is that the optical signal suffers from power loss in the delay-lines and optical amplifiers are often used. The accumulated noise from the cascaded amplifiers can severely limit the network size at very high bit rates, unless expensive signal regeneration is applied. In deflection routing, as the name implies, contention is resolved as follows: if two or more packets need to use the same output link to achieve minimum distance routing, then only one will be routed along the desired link, while others are forwarded on paths which may lead to greater than minimum distance routing. Hence, for each source destination pair the number of hops taken by a packet is no longer fixed. Deflection routing does not necessarily exclude the use of optical buffers. Most simplification can be obtained with hot-potato routing BIB001 , which is a special case of deflection routing where buffers are not provided at all. Extensive studies on deflection routing have been carried out in regular network topologies with uniform traffic load. These logical topologies can be built upon different physical topologies such as ring, star or mesh. Fig. 11 shows two most typical logical topologies used for network performance simulation: the Manhattan Street Network (MSN) and ShuffleNet. Each node in these two topologies has two input ports and two output ports. A node has to handle both bypassing and locally generated / terminated packets. Fig.  12 shows some example of node architecture for MSN or ShuffleNet. Studies have been conducted to determine the impact of different routing strategies on network performance, such as delays, average number of hops (i.e. the number of switches a packet has to traverse between the source and destination node) for each packet, network aggregate capacity (the number of packets a network can process within a certain period of time), etc. A comparison done on the ShuffleNet topology between store-and-forward and hot-potato routing shows that the average number of hops for each packet is larger for hot-potato routing, because not all the packets take the shortest route toward their destinations BIB001 . As the number of users (or number of nodes) increases, both the average number of hops and aggregate capacities increase for both routing strategies. In multihop networks, where information from a source node to a destination node may be routed through intermediate nodes BIB002 , only a portion of the network capacity is used for newly generated traffic. A certain amount of network capacity is taken up by "bypassing traffic" as packets hop from one node to another to reach the destinations. The overall capacity of the network is inversely proportional to the average number of hops, and proportional to the number of nodes and the capacity of each link between two nodes. Store-and-forward routing can maximize the network capacity as the number of nodes increases. It has also been shown that even for networks containing several thousand nodes, the aggregate capacity of hot-potato routing is not worse than 25% of that for store-and forward routing  . Another more intuitive explanation is that in hot-potato routing the nodes use the whole network as a big buffer and route the packet in contention to the rest of the network. This type of routing trades off network throughput for simpler hardware implementation. In optical packet switched networks an all-optical path is provided between source and destination without complete regeneration, therefore at very high bit rates the propagation distance, proportional to the number of hops taken by a packet, becomes limited. The distance bit rate product is fixed if we want to keep the packet error rate (PER, the probability of a packet received in error) below a certain threshold. Given the network size and the average number of hops, the PER depends on the link bit rate. The maximum bit rate therefore determines the maximum network throughput. There are three characteristics that determine the performance of the network with deflection routing: 1) Diameter. It is the maximum distance in number of hops between any node pair in the network. The diameter is a good indicator of how compact a network is. 2) Deflection Cost. This is maximum increase in path length in number of hops due to a single deflection. 3) Don't care nodes. For a given destination, any node that has both its output links as part of the shortest path is a don't care node. A high percentage of don't care nodes helps keep the number of deflections to a low level even at high loads. The performance of ShuffleNet is better because the initial advantage in diameter of ShuffleNet over Manhattan Street Network is preserved under heavy traffic by the high percentage of don't care nodes. The expected number of hops noticeable depends on the routing algorithm. For store-and-forward with infinite buffers the average number of hops is a minimum, since the packets always take the shortest path to destination. However the queuing delay could diverge to infinity when the network approaches saturation, i.e. when probability of packet generation in each time slot approaches 1. For deflection routing the average number of hops becomes an increasing function of link load and the throughput is therefore lower than that with store-and-forward. So far, the routing strategies described above have assumed slotted (synchronous) network operation, which, as shown in the previous section, involves complex and expensive packet alignment schemes. Since we are examining deflection routing here, which means none or little optical buffer is used, what will happen if we have an asynchronous network operation? What is the network performance if we take away the packet alignment stages and use deflection routing at the same time? Asynchronous network suffers from severe congestion as the offered load increases, and its throughput would collapse completely when the load exceeds a certain threshold. The reason is that with the increasing congestion there are more and more packets starting to "wander" around in the network (due to deflection routing) and they further lower the network capacity to process newly generated packets, meanwhile more packets are being generated. The whole scenario forms a vicious cycle and as a result the network throughput will collapse completely. To avoid such total collapse the number of hops a packet traverses has to be monitored and kept under a maximum value. One way to improve the network throughput and eliminate congestion is to provide limited optical buffering to such asynchronous deflection networks. The corresponding performance improvement is very encouraging in the high-load region. Also the congestion is greatly reduced with more than one recirculating loop. One practical concern of the asynchronous deflection routing with limited optical buffer is the number of times a packet is allowed to recirculate in the loop. Optical amplification imposes noise to the signal. Network latency also increases with the number of circulations. Therefore, it is necessary to establish an optimal maximum number of recirculation for the packets. Monitoring the number of hops a packet has taken is essential to avoid congestion, which can be caused by too many packets "wandering" in the network. Having a time to live field in the packet header (like in IP packets) is hard to implement because it requires the header to be rewritten at every node. One of the possible solutions is to have the source node put a time stamp on each packet and the other nodes compare it with the local time when the packet is in transit, provided all the nodes have a globally synchronized clock. Deflection routing plays a prominent role in many optical network architectures, since it can be implemented with none or modest optical buffering. Asynchronous (unslotted) deflection routing combined with limited buffering can help to avoid complex synchronization schemes and provide a decent performance with careful design. In general, deflection routing presents more choices to the network designer, while many problems, such as packet reordering, the impact of deflection degree, etc., remain to be more thoroughly studied.