{'fraction_non_alphanumeric': 0.022946859903381644, 'fraction_numerical': 0.0, 'mean_word_length': 4.916666666666667, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Online algorithms for packet scheduling and buffer management

In this work, we study the problem of buffer management in network switches from an algorithmic perspective. In a typical switching scenario, packets with different service demands arrive at the input ports of the switch and are stored in buffers (queues) of limited capacity. Thereafter, they are transferred over the switching fabric to their corresponding output ports where they join other queues. Finally, packets are transmitted out of the switch through its outgoing links to their next destinations in the network. Due to limitations in the link bandwidth and buffer capacities, buffers may experience events of overflow and thus it becomes inevitable to drop some packets. In other switching models, packets that are sensitive to delay are dropped if they exceed a specific deadline inside the queue. We consider multiple models of switching with the goal of maximizing the throughput of the switch. If all packets are treated equally, i.e., corresponding to the besteffort concept of the Internet, we quantify the throughput as the number of packets that are successfully transmitted through the switch. In networks with Quality of Service (QoS) requirements, packets are assigned values that correspond to their levels of service, and the throughput in this case is equal to the total value of packets that are successfully transmitted. We present different algorithms for the problem of buffer management. In the buffering phase of these algorithms, we examine whether an arriving packet is accepted or rejected, and whether an already queued packet is preempted (dropped) to save space for more valuable packets. In the scheduling phase, we seek to answer questions of the kind “which packet to transfer from an input port to an output port in a given time step?”, and “which packet to transmit from an output buffer?”. An input instance for our algorithms is a finite sequence of packets arriving in an “online” manner, i.e., packets arrive one by one over time and an irrevocable decision has to be made on the fly before future arrivals become known. Such algorithms which need to cope with incomplete information about future and cannot undo their decisions are called online algorithms. It is known that packet arrivals do not adhere to any specific arrival distribution. In reality, packets tend to arrive “in bursts” rather than in smooth Poisson-like distributions. Thus, we do not make any prior as-