# A Design for an Internet Router with a Digital Optical Data Plane
## 6 Optical Packet Multiplexing  
The final phase of router processing is packet multiplexing, in which packets whose destinations have been determined, hop counts have been decremented, and checksums have been updated are switched towards the output port indicated by the forwarding lookup. This step also needs to include the possibility of output port contention (competition), possibly storing one of the competing packets to help the traffic more efficiently interleave. The basic high-level structure of a router includes input and output stages that correspond to input and output links, connected by a switching fabric (Figure 12, left). One implementation variation of that structure adds a demultiplexer to each input stage and a multiplexer to each output stage, so that the switching fabric can be replaced by a fully connected internal mesh (Figure 12, center). In this architecture, output port contention is handled in the output multiplexer, in which each output port's multiplexing function can be implemented independently (Figure 12, right). We chose this latter architecture for our optical router for two reasons. First, it lets us focus on the multiplexing operation of each output independently, rather than considering that an internal function of the switching fabric. Second, the output multiplexer itself is useful as a traffic aggregator, such as would be useful in metropolitan access networks where traffic from many lower-bandwidth local networks is combined for long-distance transit. The case shown, with \(N\) inputs and outputs (assuming a symmetric capacity configuration), requires \(N^{2}\) internal bandwidth, and \(N\) output multiplexers each with \(N\) inputs, i.e., \(N^{2}\) merging elements. Other more scalable designs require only \(N\) internal bandwidth and \(N^{\prime}log^{2}N\) merging elements and are achieved by using these same output multiplexing components in multiple successive stages. Both approaches rely on the same basic output multiplexer function. In the demux-mux architecture, we can examine packets destined to each output port as independent sets [23]. Figure 13, left, shows a set of packets arriving at each of four input ports, shaded to represent their desired output port (based on lookup in the forwarding table). The numbers inside each packet indicate its length (in arbitrary units). Figure 13, right, shows only those packets destined for output port #3; in the demux-mux design, these are the only set of packets that the port #3 output multiplexer needs to coordinate. Figure 11: A single full adder implements the Internet checksum, using delayed recirculation with regeneration (indicated by the “R” boxes). Figure 12: Basic structure of a packet switch (**left**); simplified to a demux–mux (**center**); and a separate output mux (**right**). Within that set, some packets may overlap in time (the one of length 20 and the one of length 40, both starting at time _t9_), whereas other packets might not overlap (e.g., the one at length 20 starting at time _t18_). We call the set of packets that overlap the _contention set_. We measured the size of this contention set for generated traffic based on Internet characteristics [24]. Figure 14 shows various types of such traffic and the cumulative probability of a set having a given number of packets; for most distributions, most of the contention sets include 10 or fewer packets. This suggests that the output multiplexer need not coordinate arbitrarily long sequences of overlapping packets, but that natural gaps occur in the packet stream, such that it is sufficient that only a few packets need to be scheduled at a time. This presents the opportunity for batch processing, which could enable a slower electronic scheduler to manage groups of packets. We call this batch scheduling interval the _lookahead time_ because it represents the set of packets that the multiplexer needs to \"look ahead\" in time to see, so that it can coordinate them as a set. It is important to determine the limits of the effect of such batch processing.