1use std::{
5 collections::{HashMap, HashSet},
6 sync::{Arc, atomic::AtomicBool},
7 time::{Duration, Instant},
8};
9
10use futures::{FutureExt, StreamExt};
11use futures_time::stream::StreamExt as TimeStreamExt;
12use hopr_utils::network_types::crossfire_sink::{CrossfireSink, bounded_sink_channel};
13use tracing::{Instrument, instrument::WithSubscriber};
14
15use crate::{
16 errors::SessionError,
17 flow_control::DeliveryTap,
18 processing::types::FrameInspector,
19 protocol::{FrameAcknowledgements, FrameId, Segment, SegmentId, SegmentRequest, SeqIndicator, SessionMessage},
20 socket::{SocketState, state::SocketComponents},
21 utils::{
22 RetriedFrameId, RingBufferProducer, RingBufferView, next_deadline_with_backoff, searchable_ringbuffer,
23 skip_queue::{Skip, SkipDelaySender, skip_delay_channel},
24 },
25};
26
27#[derive(Clone, Copy, Debug, PartialEq, Eq, Default)]
29pub enum AcknowledgementMode {
30 Partial,
33 Full,
36 #[default]
44 Both,
45}
46
47impl AcknowledgementMode {
48 #[inline]
50 fn is_partial_ack_enabled(&self) -> bool {
51 matches!(self, Self::Partial | Self::Both)
52 }
53
54 #[inline]
56 fn is_full_ack_enabled(&self) -> bool {
57 matches!(self, Self::Full | Self::Both)
58 }
59}
60
61#[derive(Debug, Clone, Copy, PartialEq, smart_default::SmartDefault)]
63pub struct AcknowledgementStateConfig {
64 pub mode: AcknowledgementMode,
68
69 #[default(Duration::from_millis(20))]
73 pub expected_packet_latency: Duration,
74
75 #[default(1.2)]
79 pub backoff_base: f64,
80
81 #[default(3)]
85 pub max_incoming_frame_retries: usize,
86
87 #[default(3)]
91 pub max_outgoing_frame_retries: usize,
92
93 #[default(Duration::from_millis(50))]
97 pub acknowledgement_delay: Duration,
98
99 #[default(16384)]
104 pub lookbehind_segments: usize,
105
106 #[default(None)]
113 pub max_frame_age: Option<Duration>,
114
115 #[default(None)]
125 pub min_frame_retransmission_interval: Option<Duration>,
126
127 #[default(0)]
135 pub max_frame_retransmission_services: usize,
136
137 #[default(0)]
144 pub max_frame_retransmission_burst: usize,
145
146 #[default(None)]
151 pub frame_retransmission_refill_interval: Option<Duration>,
152}
153
154impl AcknowledgementStateConfig {
155 fn normalize<const C: usize>(self) -> AcknowledgementStateConfig {
156 let expected_packet_latency = self.expected_packet_latency.max(Duration::from_millis(1));
159
160 Self {
161 mode: self.mode,
162 expected_packet_latency,
163 backoff_base: self.backoff_base.max(1.0),
164 max_incoming_frame_retries: self.max_incoming_frame_retries,
165 max_outgoing_frame_retries: self.max_outgoing_frame_retries,
166 acknowledgement_delay: self.acknowledgement_delay.max(Duration::from_millis(1)),
167 lookbehind_segments: self.lookbehind_segments.max(1024),
168 max_frame_age: self.max_frame_age.filter(|age| !age.is_zero()),
170 min_frame_retransmission_interval: Some(
175 self.min_frame_retransmission_interval
176 .filter(|interval| !interval.is_zero())
177 .unwrap_or_else(|| expected_packet_latency / 2),
178 ),
179 max_frame_retransmission_services: if self.max_frame_retransmission_services == 0 {
184 self.max_incoming_frame_retries
185 .max(1)
186 .saturating_mul(SegmentRequest::<C>::MAX_MISSING_SEGMENTS_PER_FRAME)
187 } else {
188 self.max_frame_retransmission_services
189 },
190 max_frame_retransmission_burst: if self.max_frame_retransmission_burst == 0 {
193 2 * SegmentRequest::<C>::MAX_ENTRIES
194 } else {
195 self.max_frame_retransmission_burst
196 },
197 frame_retransmission_refill_interval: Some(
198 self.frame_retransmission_refill_interval
199 .filter(|interval| !interval.is_zero())
200 .unwrap_or(expected_packet_latency),
201 ),
202 }
203 }
204}
205
206#[derive(Debug, Clone, Copy)]
208struct FrameServices {
209 served: usize,
210 last: Instant,
211}
212
213#[derive(Debug)]
225struct RetransmissionBudget {
226 min_interval: Duration,
228 max_services: usize,
230 refill_interval: Duration,
232 max_tokens: usize,
234 tokens: usize,
236 last_refill: Instant,
238 services: HashMap<FrameId, FrameServices>,
243 capacity: usize,
245 throttled: u64,
247}
248
249impl RetransmissionBudget {
250 fn new(min_interval: Duration, max_services: usize, refill_interval: Duration, max_tokens: usize) -> Self {
251 let refill_interval = if refill_interval.is_zero() {
254 Duration::from_millis(1)
255 } else {
256 refill_interval
257 };
258 Self {
259 min_interval,
260 max_services,
261 refill_interval,
262 max_tokens,
263 tokens: max_tokens,
264 last_refill: Instant::now(),
265 services: HashMap::with_capacity(max_tokens.min(1024)),
266 capacity: max_tokens.saturating_mul(16).max(1024),
267 throttled: 0,
268 }
269 }
270
271 fn refill(&mut self, now: Instant) {
282 if self.tokens >= self.max_tokens {
285 self.last_refill = now;
286 return;
287 }
288
289 let interval_nanos = self.refill_interval.as_nanos();
290 if interval_nanos == 0 || self.max_tokens == 0 {
291 return;
292 }
293
294 let elapsed_nanos = now.saturating_duration_since(self.last_refill).as_nanos();
295 let earned = (elapsed_nanos.saturating_mul(self.max_tokens as u128) / interval_nanos) as usize;
296 if earned == 0 {
297 return;
298 }
299
300 let consumed_nanos = interval_nanos.saturating_mul(earned as u128) / (self.max_tokens as u128);
303 self.last_refill += Duration::from_nanos(consumed_nanos.min(u64::MAX as u128) as u64);
304 self.tokens = self.max_tokens.min(self.tokens.saturating_add(earned));
305 }
306
307 fn admit(&mut self, frame_id: FrameId, now: Instant) -> bool {
313 self.refill(now);
314
315 let admitted = self.tokens > 0
316 && self.services.get(&frame_id).is_none_or(|s| {
317 now.saturating_duration_since(s.last) >= self.min_interval && s.served < self.max_services
318 });
319
320 if admitted {
321 self.tokens -= 1;
322 } else {
323 self.throttled = self.throttled.saturating_add(1);
324 }
325
326 admitted
327 }
328
329 fn record(&mut self, frame_id: FrameId, now: Instant) {
334 if self.services.len() >= self.capacity && !self.services.contains_key(&frame_id) {
337 self.services.clear();
338 }
339
340 let entry = self
341 .services
342 .entry(frame_id)
343 .or_insert(FrameServices { served: 0, last: now });
344 entry.served = entry.served.saturating_add(1);
345 entry.last = now;
346 }
347
348 fn take_throttled(&mut self) -> u64 {
350 std::mem::take(&mut self.throttled)
351 }
352}
353
354#[derive(Clone)]
355struct AcknowledgementStateContext<const C: usize> {
356 rb_tx: RingBufferProducer<Segment>,
357 rb_rx: RingBufferView<Segment>,
358 incoming_frame_retries_tx: SkipDelaySender<RetriedFrameId>,
359 outgoing_frame_retries_tx: SkipDelaySender<RetriedFrameId>,
360 ack_tx: CrossfireSink<FrameId>,
361 inspector: FrameInspector,
362 ctl_tx: CrossfireSink<SessionMessage<C>>,
363 retransmission_budget: Arc<parking_lot::Mutex<RetransmissionBudget>>,
365}
366
367#[cfg_attr(doc, aquamarine::aquamarine)]
368#[derive(Clone)]
457pub struct AcknowledgementState<const C: usize> {
458 id: String,
459 cfg: AcknowledgementStateConfig,
460 context: Option<AcknowledgementStateContext<C>>,
461 started: std::sync::Arc<AtomicBool>,
462 delivery_tap: Option<DeliveryTap>,
466}
467
468impl<const C: usize> AcknowledgementState<C> {
469 pub fn new<I: std::fmt::Display>(session_id: I, cfg: AcknowledgementStateConfig) -> Self {
470 Self {
471 id: session_id.to_string(),
472 cfg: cfg.normalize::<C>(),
473 context: Default::default(),
474 started: std::sync::Arc::new(AtomicBool::new(false)),
475 delivery_tap: None,
476 }
477 }
478
479 pub fn with_delivery_tap(mut self, tap: DeliveryTap) -> Self {
484 self.delivery_tap = Some(tap);
485 self
486 }
487}
488
489fn is_running(started: &AtomicBool) -> bool {
494 started.load(std::sync::atomic::Ordering::Acquire)
495}
496
497impl<const C: usize> SocketState<C> for AcknowledgementState<C> {
498 fn session_id(&self) -> &str {
499 &self.id
500 }
501
502 #[tracing::instrument(name = "AcknowledgementState", skip(self, socket_components))]
503 fn run(&mut self, socket_components: SocketComponents<C>) -> Result<(), SessionError> {
504 if self.started.load(std::sync::atomic::Ordering::Relaxed) && self.context.is_some() {
505 return Err(SessionError::InvalidState("state is already running".into()));
506 }
507
508 let (incoming_frame_retries_tx, incoming_frame_retries_rx) = skip_delay_channel();
509 let (outgoing_frame_retries_tx, outgoing_frame_retries_rx) = skip_delay_channel();
510 let (rb_tx, rb_rx) = searchable_ringbuffer(self.cfg.lookbehind_segments);
511
512 let (ack_tx, ack_rx) = bounded_sink_channel::<FrameId>(2 * self.cfg.lookbehind_segments);
514
515 let retransmission_budget = Arc::new(parking_lot::Mutex::new(RetransmissionBudget::new(
517 self.cfg
518 .min_frame_retransmission_interval
519 .unwrap_or_else(|| self.cfg.expected_packet_latency / 2),
520 self.cfg.max_frame_retransmission_services,
521 self.cfg
522 .frame_retransmission_refill_interval
523 .unwrap_or(self.cfg.expected_packet_latency),
524 self.cfg.max_frame_retransmission_burst,
525 )));
526
527 let context = self.context.insert(AcknowledgementStateContext {
528 rb_tx,
529 rb_rx,
530 incoming_frame_retries_tx,
531 outgoing_frame_retries_tx,
532 ack_tx,
533 ctl_tx: socket_components.ctl_tx,
534 inspector: socket_components
535 .inspector
536 .ok_or(SessionError::InvalidState("inspector is not available".into()))?,
537 retransmission_budget,
538 });
539
540 if self.cfg.mode.is_partial_ack_enabled() {
541 let mut incoming_frame_retries_tx_clone = context.incoming_frame_retries_tx.clone();
544 let ctl_tx_clone = context.ctl_tx.clone();
545 let frame_inspector_clone = context.inspector.clone();
546 let cfg = self.cfg;
547 let (started_1, started_2) = (self.started.clone(), self.started.clone());
548 hopr_utils::runtime::prelude::spawn(incoming_frame_retries_rx
549 .filter_map(move |rf| {
550 let frame_id = rf.frame_id;
551 let missing_segments = frame_inspector_clone.missing_segments(&frame_id).unwrap_or_default();
552 if !missing_segments.is_empty() {
553 if let Some(next) = rf.next() {
555 let retry_at = next_deadline_with_backoff(next.retry_count, cfg.backoff_base, cfg.expected_packet_latency);
557 if let Err(error) = incoming_frame_retries_tx_clone.send_one((next, retry_at)) {
558 if is_running(&started_1) {
559 tracing::error!(frame_id, %error, "failed to register next resend of incoming frame");
560 } else {
561 tracing::debug!(frame_id, %error, "state stopped, next resend of incoming frame not registered");
562 }
563 } else {
564 tracing::debug!(frame_id, retry_in = ?retry_at.saturating_duration_since(Instant::now()), "next resend request of incoming frame segments");
565 }
566 } else {
567 tracing::debug!(frame_id, "last request of incoming frame segments");
568 }
569
570 futures::future::ready(Some((frame_id, missing_segments)))
571 } else {
572 tracing::debug!(frame_id, "no more missing segments in frame");
573 futures::future::ready(None)
574 }
575 })
576 .ready_chunks(SegmentRequest::<C>::MAX_ENTRIES)
577 .inspect(|r| tracing::trace!(req = ?r, "requesting segments resend"))
578 .map(|a| Ok(SessionMessage::<C>::Request(a.into_iter().collect())))
579 .forward(ctl_tx_clone)
580 .map(move |res| match res {
581 Ok(_) => tracing::debug!("incoming frame resends processing done"),
582 Err(error) if is_running(&started_2) => tracing::error!(%error, "error while processing incoming frame resends"),
583 Err(error) => tracing::debug!(%error, "incoming frame resends ended after the state stopped")
584 })
585 .instrument(tracing::debug_span!("incoming_frame_retries_sender"))
586 .with_current_subscriber()
587 );
588 }
589
590 let ctl_tx_clone = context.ctl_tx.clone();
592 let ack_delay = self.cfg.acknowledgement_delay;
593 hopr_utils::runtime::prelude::spawn(
594 ack_rx
595 .buffer(futures_time::time::Duration::from(ack_delay))
596 .flat_map(|acks| futures::stream::iter(FrameAcknowledgements::<C>::new_multiple(acks)))
597 .filter(|acks| futures::future::ready(!acks.is_empty()))
598 .inspect(|acks| tracing::trace!(?acks, "acknowledgements sent"))
599 .map(|acks| Ok(SessionMessage::<C>::Acknowledge(acks)))
600 .forward(ctl_tx_clone)
601 .map(move |res| match res {
602 Ok(_) => tracing::debug!("acknowledgement forwarding done"),
603 Err(error) => tracing::debug!(%error, "acknowledgement forwarding failed"),
604 })
605 .instrument(tracing::debug_span!("acknowledgement_sender"))
606 .with_current_subscriber(),
607 );
608
609 let mut outgoing_frame_retries_tx_clone = context.outgoing_frame_retries_tx.clone();
611 let ctl_tx_clone = context.ctl_tx.clone();
612 let rb_rx_clone = context.rb_rx.clone();
613 let cfg = self.cfg;
614 let delivery_tap = self.delivery_tap.clone();
615 let (started_1, started_2) = (self.started.clone(), self.started.clone());
616 hopr_utils::runtime::prelude::spawn(
617 outgoing_frame_retries_rx
618 .filter_map(move |rf: RetriedFrameId| {
619 let frame_id = rf.frame_id;
620
621 if cfg.max_frame_age.is_some_and(|max_age| rf.age() >= max_age) {
625 tracing::trace!(frame_id, age = ?rf.age(), "outgoing frame exceeded max age; retiring as lost");
626 if let Some(tap) = &delivery_tap {
627 tap.on_lost_frame();
628 }
629 return futures::future::ready(None);
630 }
631
632 if let Some(next) = rf.next() {
634 let retry_at =
636 next_deadline_with_backoff(next.retry_count, cfg.backoff_base, cfg.expected_packet_latency);
637 if let Err(error) = outgoing_frame_retries_tx_clone.send_one((next, retry_at)) {
638 if is_running(&started_1) {
639 tracing::error!(frame_id, %error, "failed to register next retry of frame");
640 } else {
641 tracing::debug!(frame_id, %error, "state stopped, next retry of frame not registered");
642 }
643 } else {
644 tracing::debug!(frame_id, retry_in = ?retry_at.saturating_duration_since(Instant::now()), "next resend of outgoing frame");
645 }
646 } else {
647 tracing::debug!(frame_id, "last outgoing retry of frame");
648 if let Some(tap) = &delivery_tap {
652 tap.on_lost_frame();
653 }
654 }
655 tracing::trace!(frame_id, "going to re-send entire frame");
656 futures::future::ready(Some(frame_id))
657 })
658 .flat_map(move |frame_id| {
659 futures::stream::iter(
661 rb_rx_clone
662 .find(|s: &Segment| s.id().0 == frame_id)
663 .into_iter()
664 .inspect(|s| tracing::trace!(seg_id = %s.id(), "segment retransmit"))
665 .map(|s| Ok(SessionMessage::<C>::Segment(s))),
666 )
667 })
668 .forward(ctl_tx_clone) .map(move |res| match res {
670 Ok(_) => tracing::debug!("outgoing frame retries processing done"),
671 Err(error) if is_running(&started_2) => {
672 tracing::error!(%error, "error while processing outgoing frame retries")
673 }
674 Err(error) => tracing::debug!(%error, "outgoing frame retries ended after the state stopped"),
675 })
676 .instrument(tracing::debug_span!("outgoing_frame_retries_sender"))
677 .with_current_subscriber(),
678 );
679
680 tracing::debug!("acknowledgement state has been started");
681 self.started.store(true, std::sync::atomic::Ordering::Relaxed);
682
683 Ok(())
684 }
685
686 #[tracing::instrument(name = "AcknowledgementState::stop", skip(self))]
687 fn stop(&mut self) -> Result<(), SessionError> {
688 if let Some(mut ctx) = self.context.take() {
689 self.started.store(false, std::sync::atomic::Ordering::Release);
692 ctx.outgoing_frame_retries_tx.force_close();
693 ctx.incoming_frame_retries_tx.force_close();
694 tracing::debug!("state has been stopped");
698 } else {
699 tracing::debug!("state already stopped");
702 }
703
704 Ok(())
705 }
706
707 #[tracing::instrument(name = "AcknowledgementState::incoming_segment", skip(self), fields(frame_id = seg_id.0))]
708 fn incoming_segment(&mut self, seg_id: &SegmentId, _ind: SeqIndicator) -> Result<(), SessionError> {
709 tracing::trace!("segment received");
710
711 let ctx = self
712 .started
713 .load(std::sync::atomic::Ordering::Relaxed)
714 .then_some(self.context.as_mut())
715 .flatten()
716 .ok_or(SessionError::StateNotRunning)?;
717
718 if self.cfg.mode.is_partial_ack_enabled() {
720 if let Err(error) = ctx.incoming_frame_retries_tx.send_one((
723 RetriedFrameId::with_retries(seg_id.0, self.cfg.max_incoming_frame_retries),
724 self.cfg.expected_packet_latency, )) {
726 tracing::error!(%error, "failed to register incoming retry for frame");
727 }
728 }
729 Ok(())
730 }
731
732 #[tracing::instrument(name = "AcknowledgementState::incoming_retransmission_request", skip(self, request))]
733 fn incoming_retransmission_request(&mut self, request: SegmentRequest<C>) -> Result<(), SessionError> {
734 tracing::trace!(count = request.len(), "segment retransmission requested");
737
738 let ctx = self
739 .started
740 .load(std::sync::atomic::Ordering::Relaxed)
741 .then_some(self.context.as_mut())
742 .flatten()
743 .ok_or(SessionError::StateNotRunning)?;
744
745 let now = Instant::now();
746
747 let admitted_frame_ids: Vec<FrameId> = {
751 let mut budget = ctx.retransmission_budget.lock();
752 request
753 .frames()
754 .filter(|frame_id| budget.admit(*frame_id, now))
755 .collect()
756 };
757
758 if admitted_frame_ids.is_empty() {
759 let throttled = ctx.retransmission_budget.lock().take_throttled();
761 if throttled > 0 {
762 tracing::debug!(throttled, "retransmission request entirely throttled");
763 }
764 return Ok(());
765 }
766
767 let mut requested_seg_ids: HashSet<SegmentId> = request
770 .into_iter()
771 .filter(|seg_id| admitted_frame_ids.binary_search(&seg_id.0).is_ok())
772 .collect();
773
774 let segments = ctx.rb_rx.find(|s| requested_seg_ids.remove(&s.id()));
776
777 tracing::trace!(
778 found = segments.len(),
779 requested = admitted_frame_ids.len(),
780 "found matching segments to be retransmitted"
781 );
782
783 let mut served_frame_ids: Vec<FrameId> = Vec::with_capacity(admitted_frame_ids.len());
792 let queued = segments.into_iter().try_for_each(|s| {
793 tracing::trace!(seg_id = %s.id(), "retransmit segment on request");
794 let frame_id = s.frame_id;
795 ctx.ctl_tx
796 .try_send(SessionMessage::Segment(s))
797 .map(|_| served_frame_ids.push(frame_id))
798 });
799 served_frame_ids.sort_unstable();
800 served_frame_ids.dedup();
801
802 {
807 let mut budget = ctx.retransmission_budget.lock();
808 served_frame_ids
809 .iter()
810 .for_each(|frame_id| budget.record(*frame_id, now));
811 let throttled = budget.take_throttled();
813 if throttled > 0 {
814 tracing::debug!(throttled, "throttled peer-driven retransmission requests");
815 }
816 }
817
818 queued.map_err(|e| SessionError::ProcessingError(e.to_string()))?;
819
820 if self.cfg.mode.is_full_ack_enabled()
830 && !served_frame_ids.is_empty()
831 && let Err(error) = ctx.outgoing_frame_retries_tx.send_many(
832 served_frame_ids
833 .into_iter()
834 .map(|frame_id| (RetriedFrameId::no_retries(frame_id), Skip).into()),
835 )
836 {
837 tracing::error!(%error, "failed to cancel frame resend of partially acknowledged frames");
838 }
839
840 Ok(())
841 }
842
843 #[tracing::instrument(name = "AcknowledgementState::incoming_acknowledged_frames", skip(self))]
844 fn incoming_acknowledged_frames(&mut self, ack: FrameAcknowledgements<C>) -> Result<(), SessionError> {
845 tracing::trace!(count = ack.len(), "frame acknowledgements received");
846
847 let tap = self.delivery_tap.clone();
850 let full_ack = self.cfg.mode.is_full_ack_enabled();
851
852 let ctx = self
853 .started
854 .load(std::sync::atomic::Ordering::Relaxed)
855 .then_some(self.context.as_mut())
856 .flatten()
857 .ok_or(SessionError::StateNotRunning)?;
858
859 if let Some(tap) = &tap {
864 (0..ack.len()).for_each(|_| tap.on_acked_frame());
865 }
866
867 if full_ack
869 && let Err(error) = ctx.outgoing_frame_retries_tx.send_many(
870 ack.into_iter()
871 .inspect(|frame_id| tracing::trace!(frame_id, "frame acknowledged"))
872 .map(|frame_id| (RetriedFrameId::no_retries(frame_id), Skip).into()),
873 )
874 {
875 tracing::error!(%error, "failed to cancel frame resend");
876 }
877
878 Ok(())
879 }
880
881 #[tracing::instrument(name = "AcknowledgementState::frame_complete", skip(self))]
882 fn frame_complete(&mut self, frame_id: FrameId) -> Result<(), SessionError> {
883 tracing::trace!("frame complete");
884
885 let ctx = self
886 .started
887 .load(std::sync::atomic::Ordering::Relaxed)
888 .then_some(self.context.as_mut())
889 .flatten()
890 .ok_or(SessionError::StateNotRunning)?;
891
892 if let Err(error) = ctx.ack_tx.try_send(frame_id) {
894 tracing::error!(%error, "failed to acknowledge frame");
895 }
896
897 if self.cfg.mode.is_partial_ack_enabled() {
898 if let Err(error) = ctx
900 .incoming_frame_retries_tx
901 .send_one((RetriedFrameId::no_retries(frame_id), Skip))
902 {
903 tracing::error!(%error, "failed to cancel retry of acknowledged frame");
904 }
905 }
906
907 Ok(())
908 }
909
910 #[tracing::instrument(name = "AcknowledgementState::frame_emitted", skip(self))]
911 fn frame_emitted(&mut self, id: FrameId) -> Result<(), SessionError> {
912 tracing::trace!("frame emitted");
913 let _ = self
914 .started
915 .load(std::sync::atomic::Ordering::Relaxed)
916 .then_some(self.context.as_mut())
917 .flatten()
918 .ok_or(SessionError::StateNotRunning)?;
919 Ok(())
920 }
921
922 #[tracing::instrument(name = "AcknowledgementState::frame_discarded", skip(self))]
923 fn frame_discarded(&mut self, frame_id: FrameId) -> Result<(), SessionError> {
924 tracing::trace!("frame discarded");
925
926 let ctx = self
927 .started
928 .load(std::sync::atomic::Ordering::Relaxed)
929 .then_some(self.context.as_mut())
930 .flatten()
931 .ok_or(SessionError::StateNotRunning)?;
932
933 if self.cfg.mode.is_partial_ack_enabled() {
934 if let Err(error) = ctx
936 .incoming_frame_retries_tx
937 .send_one((RetriedFrameId::no_retries(frame_id), Skip))
938 {
939 tracing::error!(%error, "failed to cancel retry of acknowledged frame");
940 }
941 }
942
943 Ok(())
944 }
945
946 #[tracing::instrument(name = "AcknowledgementState::segment_sent", skip(self, segment), fields(frame_id = segment.frame_id, seq_idx = segment.seq_idx))]
947 fn segment_sent(&mut self, segment: &Segment) -> Result<(), SessionError> {
948 tracing::trace!("segment sent");
949
950 let ctx = self
951 .started
952 .load(std::sync::atomic::Ordering::Relaxed)
953 .then_some(self.context.as_mut())
954 .flatten()
955 .ok_or(SessionError::StateNotRunning)?;
956
957 if !ctx.rb_tx.push(segment.clone()) {
960 tracing::trace!(
961 frame_id = segment.frame_id,
962 seq_idx = segment.seq_idx,
963 "ring buffer full: new segment enqueued, oldest buffered segment overwritten"
964 );
965 }
966
967 if segment.is_last() && self.cfg.mode.is_full_ack_enabled() {
970 tracing::trace!("last segment of frame sent");
971
972 if let Err(error) = ctx.outgoing_frame_retries_tx.send_one((
973 RetriedFrameId::with_retries(segment.frame_id, self.cfg.max_outgoing_frame_retries),
974 self.cfg.expected_packet_latency * (segment.seq_flags.seq_len() + 1) as u32,
979 )) {
980 tracing::error!(%error, "failed to insert outgoing retry of a frame");
981 }
982 }
983
984 Ok(())
985 }
986}
987
988#[cfg(test)]
989mod tests {
990 use anyhow::Context;
991
992 use super::*;
993 use crate::{
994 MAX_SESSION_MTU,
995 processing::types::{FrameBuilder, FrameDashMap, FrameMap},
996 protocol::SeqNum,
997 utils::segment,
998 };
999
1000 const FRAME_SIZE: usize = MAX_SESSION_MTU;
1002
1003 const MTU: usize = 1000;
1004
1005 #[test_log::test(tokio::test)]
1006 async fn ack_state_sender_must_acknowledge_completed_frames() -> anyhow::Result<()> {
1007 let cfg = AcknowledgementStateConfig {
1008 expected_packet_latency: Duration::from_millis(10),
1009 acknowledgement_delay: Duration::from_millis(2),
1010 ..Default::default()
1011 };
1012
1013 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1014 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1015
1016 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1017 state.run(SocketComponents {
1018 inspector: inspector.into(),
1019 ctl_tx,
1020 })?;
1021
1022 let acked_frame_ids = [1, 2, 3];
1023
1024 for &frame_id in &acked_frame_ids {
1025 state.frame_complete(frame_id)?;
1026 }
1027
1028 tokio::time::sleep(cfg.acknowledgement_delay * 2).await;
1029
1030 state.stop()?;
1031
1032 let ctl_msgs = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1033 .await
1034 .context("timeout receiving Control messages")?;
1035
1036 assert_eq!(1, ctl_msgs.len());
1037
1038 assert_eq!(
1039 ctl_msgs[0],
1040 SessionMessage::Acknowledge(acked_frame_ids.to_vec().try_into()?)
1041 );
1042
1043 Ok(())
1044 }
1045
1046 #[parameterized::parameterized(num_frames = { 1, 2, 3 })]
1047 #[parameterized_macro(test_log::test(tokio::test))]
1048 async fn ack_state_sender_must_resend_unacknowledged_frames(num_frames: usize) -> anyhow::Result<()> {
1049 const NUM_RETRIES: usize = 2;
1050
1051 let cfg = AcknowledgementStateConfig {
1052 mode: AcknowledgementMode::Full,
1053 expected_packet_latency: Duration::from_millis(2),
1054 max_outgoing_frame_retries: NUM_RETRIES,
1055 ..Default::default()
1056 };
1057
1058 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1059 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1060
1061 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1062 state.run(SocketComponents {
1063 inspector: inspector.into(),
1064 ctl_tx,
1065 })?;
1066
1067 let mut expected_frame_segments = Vec::new();
1068 let num_segments_in_frame = FRAME_SIZE / MTU + 1;
1069 for i in 1..=num_frames {
1070 let expected_segments = segment(
1071 hopr_types::crypto_random::random_bytes::<FRAME_SIZE>(),
1072 MTU,
1073 i as FrameId,
1074 )?;
1075 for segment in &expected_segments {
1076 state.segment_sent(segment)?;
1077 }
1078 expected_frame_segments.push(expected_segments);
1079 }
1080
1081 let expected_frame_delivery = cfg.expected_packet_latency * (num_segments_in_frame + 1) as u32;
1082 tokio::time::sleep(2 * expected_frame_delivery).await;
1083 state.stop()?;
1084
1085 let ctl_msg = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1086 .await
1087 .context("timeout receiving Control message")?;
1088
1089 let retransmitted_segments = ctl_msg
1090 .into_iter()
1091 .map(|m| m.try_as_segment().ok_or(anyhow::anyhow!("must be segment")))
1092 .collect::<Result<Vec<_>, _>>()?;
1093
1094 assert_eq!(
1095 NUM_RETRIES * num_segments_in_frame * num_frames,
1096 retransmitted_segments.len()
1097 );
1098
1099 let total_segments = expected_frame_segments.iter().map(|m| m.len()).sum::<usize>();
1100 let expected_segments = expected_frame_segments
1101 .into_iter()
1102 .flatten()
1103 .cycle()
1104 .take(total_segments * NUM_RETRIES)
1105 .collect::<Vec<_>>();
1106 assert_eq!(expected_segments, retransmitted_segments);
1107
1108 Ok(())
1109 }
1110
1111 async fn retransmissions_with_max_frame_age(max_frame_age: Option<Duration>) -> anyhow::Result<usize> {
1114 let cfg = AcknowledgementStateConfig {
1116 mode: AcknowledgementMode::Full,
1117 expected_packet_latency: Duration::from_millis(5),
1118 max_outgoing_frame_retries: 20,
1119 max_frame_age,
1120 ..Default::default()
1121 };
1122
1123 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1124 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1125
1126 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1127 state.run(SocketComponents {
1128 inspector: inspector.into(),
1129 ctl_tx,
1130 })?;
1131
1132 for segment in &segment(hopr_types::crypto_random::random_bytes::<FRAME_SIZE>(), MTU, 1)? {
1133 state.segment_sent(segment)?;
1134 }
1135
1136 tokio::time::sleep(Duration::from_millis(500)).await;
1138 state.stop()?;
1139
1140 let ctl_msgs = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1141 .await
1142 .context("timeout receiving Control messages")?;
1143
1144 Ok(ctl_msgs.into_iter().filter_map(|m| m.try_as_segment()).count())
1145 }
1146
1147 #[test_log::test(tokio::test)]
1148 async fn ack_state_sender_should_stop_resending_a_frame_that_exceeded_the_max_age() -> anyhow::Result<()> {
1149 let unbounded = retransmissions_with_max_frame_age(None).await?;
1150 let bounded = retransmissions_with_max_frame_age(Some(Duration::from_millis(50))).await?;
1151
1152 assert!(
1153 unbounded > 0,
1154 "the retry pipeline must retransmit at all without an age bound"
1155 );
1156 assert!(
1157 bounded < unbounded,
1158 "an age bound must cut retransmissions short: got {bounded} bounded vs {unbounded} unbounded"
1159 );
1160
1161 Ok(())
1162 }
1163
1164 #[test_log::test(tokio::test)]
1165 async fn ack_state_sender_must_not_resend_unacknowledged_frame_when_full_resend_disabled() -> anyhow::Result<()> {
1166 const NUM_RETRIES: usize = 2;
1167
1168 let cfg = AcknowledgementStateConfig {
1169 mode: AcknowledgementMode::Partial,
1170 expected_packet_latency: Duration::from_millis(2),
1171 max_outgoing_frame_retries: NUM_RETRIES,
1172 ..Default::default()
1173 };
1174
1175 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1176 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1177
1178 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1179 state.run(SocketComponents {
1180 inspector: inspector.into(),
1181 ctl_tx,
1182 })?;
1183
1184 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<FRAME_SIZE>(), MTU, 1)?;
1185 for segment in &expected_segments {
1186 state.segment_sent(segment)?;
1187 }
1188
1189 let expected_frame_delivery = cfg.expected_packet_latency * (expected_segments.len() + 1) as u32;
1190 tokio::time::sleep(2 * expected_frame_delivery).await;
1191 state.stop()?;
1192
1193 assert!(ctl_rx.collect::<Vec<_>>().await.is_empty());
1195
1196 Ok(())
1197 }
1198
1199 #[tokio::test]
1200 async fn ack_state_sender_must_not_resend_acknowledged_frame() -> anyhow::Result<()> {
1201 let cfg = AcknowledgementStateConfig {
1202 mode: AcknowledgementMode::Full,
1203 expected_packet_latency: Duration::from_millis(2),
1204 max_outgoing_frame_retries: 1,
1205 ..Default::default()
1206 };
1207
1208 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1209 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1210
1211 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1212 state.run(SocketComponents {
1213 inspector: inspector.into(),
1214 ctl_tx,
1215 })?;
1216
1217 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ FRAME_SIZE * 2 }>(), MTU, 1)?;
1218 for segment in &expected_segments {
1219 state.segment_sent(segment)?;
1220 }
1221
1222 state.incoming_acknowledged_frames(vec![1].try_into()?)?;
1224
1225 tokio::time::sleep(10 * cfg.expected_packet_latency).await;
1226
1227 state.stop()?;
1228
1229 assert!(ctl_rx.collect::<Vec<_>>().await.is_empty());
1231
1232 Ok(())
1233 }
1234
1235 #[test_log::test(tokio::test)]
1236 async fn ack_state_sender_must_not_resend_entire_frame_when_already_partially_acknowledged() -> anyhow::Result<()> {
1237 let cfg = AcknowledgementStateConfig {
1238 mode: AcknowledgementMode::Full,
1239 expected_packet_latency: Duration::from_millis(2),
1240 ..Default::default()
1241 };
1242
1243 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1244 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1245
1246 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1247 state.run(SocketComponents {
1248 inspector: inspector.into(),
1249 ctl_tx,
1250 })?;
1251
1252 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ FRAME_SIZE * 2 }>(), MTU, 1)?;
1253 let seq_len = expected_segments.len();
1254
1255 for segment in &expected_segments {
1257 state.segment_sent(segment)?;
1258 }
1259
1260 state.incoming_retransmission_request(SegmentRequest::from_iter([(1, [0b10000000].into())]))?;
1262
1263 tokio::time::sleep(cfg.expected_packet_latency * (seq_len as u32 + 2)).await;
1270
1271 state.stop()?;
1272
1273 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1275 assert_eq!(1, ctl_msgs.len());
1276 assert_eq!(ctl_msgs[0], SessionMessage::Segment(expected_segments[0].clone()));
1277
1278 Ok(())
1279 }
1280
1281 #[test_log::test(tokio::test)]
1282 async fn ack_state_sender_must_retransmit_segments_when_requested() -> anyhow::Result<()> {
1283 let cfg = AcknowledgementStateConfig {
1284 mode: AcknowledgementMode::Full,
1285 expected_packet_latency: Duration::from_millis(2),
1286 max_outgoing_frame_retries: 1,
1287 max_frame_retransmission_services: usize::MAX,
1294 ..Default::default()
1295 };
1296
1297 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1298 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1299
1300 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1301 state.run(SocketComponents {
1302 inspector: inspector.into(),
1303 ctl_tx,
1304 })?;
1305
1306 let expected_segments_1 = segment(hopr_types::crypto_random::random_bytes::<{ FRAME_SIZE * 2 }>(), MTU, 1)?;
1307 for segment in &expected_segments_1 {
1309 state.segment_sent(segment)?;
1310 }
1311
1312 let expected_segments_2 = segment(hopr_types::crypto_random::random_bytes::<{ FRAME_SIZE * 2 }>(), MTU, 2)?;
1313 for segment in &expected_segments_2 {
1315 state.segment_sent(segment)?;
1316 }
1317
1318 tokio::time::sleep(cfg.expected_packet_latency).await;
1319
1320 state.incoming_retransmission_request(SegmentRequest::from_iter([
1322 (1, [0b11100000].into()),
1323 (2, [0b11100000].into()),
1324 ]))?;
1325 tokio::time::sleep(cfg.expected_packet_latency).await;
1326
1327 state.incoming_retransmission_request(SegmentRequest::from_iter([(2, [0b11000000].into())]))?;
1328 tokio::time::sleep(cfg.expected_packet_latency).await;
1329
1330 state.incoming_retransmission_request(SegmentRequest::from_iter([(2, [0b01000000].into())]))?;
1331 tokio::time::sleep(cfg.expected_packet_latency).await;
1332
1333 state.stop()?;
1334
1335 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1336
1337 assert_eq!(9, ctl_msgs.len());
1338 assert_eq!(ctl_msgs[0], SessionMessage::Segment(expected_segments_1[0].clone()));
1340 assert_eq!(ctl_msgs[1], SessionMessage::Segment(expected_segments_1[1].clone()));
1341 assert_eq!(ctl_msgs[2], SessionMessage::Segment(expected_segments_1[2].clone()));
1342 assert_eq!(ctl_msgs[3], SessionMessage::Segment(expected_segments_2[0].clone()));
1344 assert_eq!(ctl_msgs[4], SessionMessage::Segment(expected_segments_2[1].clone()));
1345 assert_eq!(ctl_msgs[5], SessionMessage::Segment(expected_segments_2[2].clone()));
1346
1347 assert_eq!(ctl_msgs[6], SessionMessage::Segment(expected_segments_2[0].clone()));
1349 assert_eq!(ctl_msgs[7], SessionMessage::Segment(expected_segments_2[1].clone()));
1350
1351 assert_eq!(ctl_msgs[8], SessionMessage::Segment(expected_segments_2[1].clone()));
1353
1354 Ok(())
1355 }
1356
1357 #[tokio::test]
1358 async fn ack_state_receiver_must_request_missing_frames_when_partial_acks_are_enabled() -> anyhow::Result<()> {
1359 let cfg = AcknowledgementStateConfig {
1360 mode: AcknowledgementMode::Partial,
1361 expected_packet_latency: Duration::from_millis(2),
1362 max_incoming_frame_retries: 1,
1363 ..Default::default()
1364 };
1365
1366 let mut inspector = FrameInspector(FrameDashMap::with_capacity(10));
1367 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1368
1369 let segments = segment(hopr_types::crypto_random::random_bytes::<FRAME_SIZE>(), MTU, 1)?;
1370
1371 inspector
1372 .0
1373 .entry(1)
1374 .try_as_vacant()
1375 .ok_or(anyhow::anyhow!("frame 1 must be vacant"))?
1376 .insert(FrameBuilder::from(segments[0].clone()));
1377
1378 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1379 state.run(SocketComponents {
1380 inspector: inspector.into(),
1381 ctl_tx,
1382 })?;
1383
1384 state.incoming_segment(&segments[0].id(), (segments.len() as SeqNum).try_into()?)?;
1385
1386 tokio::time::sleep(cfg.expected_packet_latency * 2).await;
1387
1388 state.stop()?;
1389
1390 let ctl_msgs = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1391 .await
1392 .context("timeout receiving Control messages")?;
1393
1394 assert_eq!(1, ctl_msgs.len());
1395 assert_eq!(
1396 ctl_msgs[0],
1397 SessionMessage::Request(SegmentRequest::from_iter([(1, [0b01000000].into())]))
1398 );
1399
1400 Ok(())
1401 }
1402
1403 #[tokio::test]
1404 async fn ack_state_receiver_must_not_request_missing_frames_when_partial_acks_are_disabled() -> anyhow::Result<()> {
1405 let cfg = AcknowledgementStateConfig {
1406 mode: AcknowledgementMode::Full,
1407 expected_packet_latency: Duration::from_millis(2),
1408 max_incoming_frame_retries: 1,
1409 ..Default::default()
1410 };
1411
1412 let mut inspector = FrameInspector(FrameDashMap::with_capacity(10));
1413 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1414
1415 let segments = segment(hopr_types::crypto_random::random_bytes::<FRAME_SIZE>(), MTU, 1)?;
1416
1417 inspector
1418 .0
1419 .entry(1)
1420 .try_as_vacant()
1421 .ok_or(anyhow::anyhow!("frame 1 must be vacant"))?
1422 .insert(FrameBuilder::from(segments[0].clone()));
1423
1424 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1425 state.run(SocketComponents {
1426 inspector: inspector.into(),
1427 ctl_tx,
1428 })?;
1429
1430 state.incoming_segment(&segments[0].id(), (segments.len() as SeqNum).try_into()?)?;
1431
1432 tokio::time::sleep(cfg.expected_packet_latency * 2).await;
1433
1434 state.stop()?;
1435
1436 let ctl_msgs = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1437 .await
1438 .context("timeout receiving Control messages")?;
1439
1440 assert!(ctl_msgs.iter().all(|m| !matches!(m, SessionMessage::Request(_))));
1441
1442 Ok(())
1443 }
1444
1445 #[tokio::test]
1446 async fn ack_state_receiver_must_continue_requesting_missing_frames_when_frame_not_completed() -> anyhow::Result<()>
1447 {
1448 let cfg = AcknowledgementStateConfig {
1449 mode: AcknowledgementMode::Partial,
1450 expected_packet_latency: Duration::from_millis(2),
1451 max_incoming_frame_retries: 3,
1452 ..Default::default()
1453 };
1454
1455 let mut inspector = FrameInspector(FrameDashMap::with_capacity(10));
1456 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1457
1458 let segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * FRAME_SIZE }>(), MTU, 1)?;
1459
1460 inspector
1461 .0
1462 .entry(1)
1463 .try_as_vacant()
1464 .ok_or(anyhow::anyhow!("frame 1 must be vacant"))?
1465 .insert(FrameBuilder::from(segments[0].clone()));
1466
1467 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1468 state.run(SocketComponents {
1469 inspector: inspector.clone().into(),
1470 ctl_tx,
1471 })?;
1472
1473 state.incoming_segment(&segments[0].id(), (segments.len() as SeqNum).try_into()?)?;
1474
1475 tokio::time::sleep(cfg.expected_packet_latency * 2).await;
1476
1477 inspector
1478 .0
1479 .entry(1)
1480 .try_as_occupied()
1481 .ok_or(anyhow::anyhow!("frame 1 must be occupied"))?
1482 .get_mut()
1483 .add_segment(segments[1].clone())?;
1484
1485 state.incoming_segment(&segments[1].id(), (segments.len() as SeqNum).try_into()?)?;
1486
1487 tokio::time::sleep(cfg.expected_packet_latency * 2).await;
1488
1489 state.stop()?;
1490
1491 let ctl_msgs = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1492 .await
1493 .context("timeout receiving Control messages")?;
1494
1495 assert_eq!(2, ctl_msgs.len());
1496 assert_eq!(
1497 ctl_msgs[0],
1498 SessionMessage::Request(SegmentRequest::from_iter([(1, [0b01100000].into())]))
1499 );
1500
1501 assert_eq!(
1502 ctl_msgs[1],
1503 SessionMessage::Request(SegmentRequest::from_iter([(1, [0b00100000].into())]))
1504 );
1505
1506 Ok(())
1507 }
1508
1509 #[tokio::test]
1510 async fn ack_state_receiver_must_continue_requesting_missing_frames_and_acknowledge_once_complete()
1511 -> anyhow::Result<()> {
1512 let cfg = AcknowledgementStateConfig {
1513 mode: AcknowledgementMode::Partial,
1514 expected_packet_latency: Duration::from_millis(2),
1515 max_incoming_frame_retries: 3,
1516 acknowledgement_delay: Duration::from_millis(5),
1517 ..Default::default()
1518 };
1519
1520 let mut inspector = FrameInspector(FrameDashMap::with_capacity(10));
1521 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1522
1523 let segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * FRAME_SIZE }>(), MTU, 1)?;
1524
1525 inspector
1527 .0
1528 .entry(1)
1529 .try_as_vacant()
1530 .ok_or(anyhow::anyhow!("frame 1 must be vacant"))?
1531 .insert(FrameBuilder::from(segments[0].clone()));
1532
1533 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1534 state.run(SocketComponents {
1535 inspector: inspector.clone().into(),
1536 ctl_tx,
1537 })?;
1538
1539 state.incoming_segment(&segments[0].id(), (segments.len() as SeqNum).try_into()?)?;
1541
1542 tokio::time::sleep(cfg.expected_packet_latency * 2).await;
1543
1544 inspector
1545 .0
1546 .entry(1)
1547 .try_as_occupied()
1548 .ok_or(anyhow::anyhow!("frame 1 must be occupied"))?
1549 .get_mut()
1550 .add_segment(segments[1].clone())?;
1551
1552 state.incoming_segment(&segments[1].id(), (segments.len() as SeqNum).try_into()?)?;
1553
1554 tokio::time::sleep(cfg.expected_packet_latency * 2).await;
1555
1556 inspector
1558 .0
1559 .entry(1)
1560 .try_as_occupied()
1561 .ok_or(anyhow::anyhow!("frame 1 must be occupied"))?
1562 .get_mut()
1563 .add_segment(segments[2].clone())?;
1564
1565 state.incoming_segment(&segments[2].id(), (segments.len() as SeqNum).try_into()?)?;
1566 state.frame_complete(1)?;
1567
1568 tokio::time::sleep(cfg.acknowledgement_delay * 2).await;
1569
1570 state.stop()?;
1571
1572 let ctl_msgs = tokio::time::timeout(Duration::from_millis(100), ctl_rx.collect::<Vec<_>>())
1573 .await
1574 .context("timeout receiving Control messages")?;
1575
1576 assert_eq!(3, ctl_msgs.len());
1577 assert_eq!(
1578 ctl_msgs[0],
1579 SessionMessage::Request(SegmentRequest::from_iter([(1, [0b01100000].into())]))
1580 );
1581
1582 assert_eq!(
1583 ctl_msgs[1],
1584 SessionMessage::Request(SegmentRequest::from_iter([(1, [0b00100000].into())]))
1585 );
1586
1587 assert_eq!(ctl_msgs[2], SessionMessage::Acknowledge(vec![1].try_into()?));
1588
1589 Ok(())
1590 }
1591
1592 fn request_for(frame_id: FrameId, missing: u8) -> SegmentRequest<MTU> {
1594 SegmentRequest::from_iter([(frame_id, [missing].into())])
1595 }
1596
1597 #[test_log::test(tokio::test)]
1598 async fn ack_state_receiver_must_not_service_a_replayed_request_twice_within_the_interval() -> anyhow::Result<()> {
1599 let cfg = AcknowledgementStateConfig {
1601 expected_packet_latency: Duration::from_millis(50),
1602 ..Default::default()
1603 };
1604
1605 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1606 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1607
1608 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1609 state.run(SocketComponents {
1610 inspector: inspector.into(),
1611 ctl_tx,
1612 })?;
1613
1614 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, 1)?;
1615 for segment in &expected_segments {
1616 state.segment_sent(segment)?;
1617 }
1618
1619 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1620 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1622
1623 tokio::time::sleep(Duration::from_millis(100)).await;
1624 state.stop()?;
1625
1626 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1627 assert_eq!(2, ctl_msgs.len(), "replayed request must not be served again");
1628 assert_eq!(SessionMessage::Segment(expected_segments[0].clone()), ctl_msgs[0]);
1629 assert_eq!(SessionMessage::Segment(expected_segments[1].clone()), ctl_msgs[1]);
1630
1631 Ok(())
1632 }
1633
1634 #[test_log::test(tokio::test)]
1635 async fn ack_state_receiver_must_service_the_same_frame_again_after_the_interval_elapses() -> anyhow::Result<()> {
1636 let cfg = AcknowledgementStateConfig {
1637 expected_packet_latency: Duration::from_millis(50),
1638 ..Default::default()
1639 };
1640
1641 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1642 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1643
1644 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1645 state.run(SocketComponents {
1646 inspector: inspector.into(),
1647 ctl_tx,
1648 })?;
1649
1650 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, 1)?;
1651 for segment in &expected_segments {
1652 state.segment_sent(segment)?;
1653 }
1654
1655 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1656 tokio::time::sleep(cfg.expected_packet_latency).await;
1658 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1659
1660 tokio::time::sleep(Duration::from_millis(100)).await;
1661 state.stop()?;
1662
1663 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1664 assert_eq!(
1665 4,
1666 ctl_msgs.len(),
1667 "frame must be servable again once the interval elapses"
1668 );
1669 for (i, expected_segment) in expected_segments.iter().cycle().take(4).enumerate() {
1670 assert_eq!(SessionMessage::Segment(expected_segment.clone()), ctl_msgs[i]);
1671 }
1672
1673 Ok(())
1674 }
1675
1676 #[test_log::test(tokio::test)]
1677 async fn ack_state_receiver_must_throttle_a_frame_past_the_service_cap() -> anyhow::Result<()> {
1678 let cfg = AcknowledgementStateConfig {
1679 max_frame_retransmission_services: 2,
1681 max_frame_retransmission_burst: usize::MAX,
1683 frame_retransmission_refill_interval: Some(Duration::from_secs(60)),
1684 min_frame_retransmission_interval: Some(Duration::from_millis(1)),
1685 ..Default::default()
1686 };
1687
1688 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1689 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1690
1691 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1692 state.run(SocketComponents {
1693 inspector: inspector.into(),
1694 ctl_tx,
1695 })?;
1696
1697 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, 1)?;
1698 for segment in &expected_segments {
1699 state.segment_sent(segment)?;
1700 }
1701
1702 for _ in 0..2 {
1704 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1705 tokio::time::sleep(Duration::from_millis(10)).await;
1706 }
1707 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1709
1710 tokio::time::sleep(Duration::from_millis(100)).await;
1711 state.stop()?;
1712
1713 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1714 assert_eq!(4, ctl_msgs.len(), "exactly two services must have been served");
1715 for (i, expected_segment) in expected_segments.iter().cycle().take(4).enumerate() {
1716 assert_eq!(SessionMessage::Segment(expected_segment.clone()), ctl_msgs[i]);
1717 }
1718
1719 Ok(())
1720 }
1721
1722 #[test_log::test(tokio::test)]
1723 async fn ack_state_receiver_must_bound_total_service_while_frames_are_cycled() -> anyhow::Result<()> {
1724 let cfg = AcknowledgementStateConfig {
1725 max_frame_retransmission_burst: 3,
1728 frame_retransmission_refill_interval: Some(Duration::from_secs(60)),
1729 max_frame_retransmission_services: usize::MAX,
1730 min_frame_retransmission_interval: Some(Duration::from_millis(1)),
1731 ..Default::default()
1732 };
1733
1734 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1735 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1736
1737 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1738 state.run(SocketComponents {
1739 inspector: inspector.into(),
1740 ctl_tx,
1741 })?;
1742
1743 let expected_segments = (1..=2)
1744 .map(|i| segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, i))
1745 .collect::<Result<Vec<_>, _>>()?;
1746 for expected_segment in &expected_segments {
1747 for segment in expected_segment {
1748 state.segment_sent(segment)?;
1749 }
1750 }
1751
1752 for i in 0..6 {
1754 state.incoming_retransmission_request(request_for(1 + (i % 2) as FrameId, 0b10000000))?;
1755 tokio::time::sleep(Duration::from_millis(10)).await;
1756 }
1757
1758 tokio::time::sleep(Duration::from_millis(100)).await;
1759 state.stop()?;
1760
1761 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1762 assert_eq!(
1763 3,
1764 ctl_msgs.len(),
1765 "the burst cap must bound the total number of services"
1766 );
1767 for (i, expected_frame) in expected_segments.iter().cycle().take(3).enumerate() {
1768 assert_eq!(SessionMessage::Segment(expected_frame[0].clone()), ctl_msgs[i]);
1769 }
1770
1771 Ok(())
1772 }
1773
1774 #[test_log::test(tokio::test)]
1775 async fn ack_state_receiver_must_still_cancel_our_full_frame_resend_when_it_serves_a_frame() -> anyhow::Result<()> {
1776 let cfg = AcknowledgementStateConfig {
1777 mode: AcknowledgementMode::Full,
1778 expected_packet_latency: Duration::from_millis(100), ..Default::default()
1780 };
1781
1782 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1783 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1784
1785 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1786 state.run(SocketComponents {
1787 inspector: inspector.into(),
1788 ctl_tx,
1789 })?;
1790
1791 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, 1)?;
1792 for segment in &expected_segments {
1793 state.segment_sent(segment)?;
1794 }
1795
1796 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1799
1800 tokio::time::sleep(4 * cfg.expected_packet_latency).await;
1802 state.stop()?;
1803
1804 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1805 assert_eq!(
1806 2,
1807 ctl_msgs.len(),
1808 "only the requested segments must be sent, no full-frame resend"
1809 );
1810 assert_eq!(SessionMessage::Segment(expected_segments[0].clone()), ctl_msgs[0]);
1811 assert_eq!(SessionMessage::Segment(expected_segments[1].clone()), ctl_msgs[1]);
1812
1813 Ok(())
1814 }
1815
1816 #[test_log::test(tokio::test)]
1817 async fn ack_state_receiver_must_not_cancel_our_full_frame_resend_when_it_throttles_a_frame() -> anyhow::Result<()>
1818 {
1819 let cfg = AcknowledgementStateConfig {
1820 mode: AcknowledgementMode::Full,
1821 expected_packet_latency: Duration::from_millis(100), max_outgoing_frame_retries: 1,
1824 max_frame_retransmission_burst: 1,
1827 frame_retransmission_refill_interval: Some(Duration::from_secs(60)),
1828 max_frame_retransmission_services: usize::MAX,
1829 min_frame_retransmission_interval: Some(Duration::from_millis(1)),
1830 ..Default::default()
1831 };
1832
1833 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1834 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1835
1836 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1837 state.run(SocketComponents {
1838 inspector: inspector.into(),
1839 ctl_tx,
1840 })?;
1841
1842 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, 1)?;
1843 for segment in &expected_segments {
1844 state.segment_sent(segment)?;
1845 }
1846
1847 tokio::time::sleep(Duration::from_millis(10)).await;
1848
1849 state.incoming_retransmission_request(request_for(2, 0b10000000))?;
1851 tokio::time::sleep(Duration::from_millis(10)).await;
1852
1853 state.incoming_retransmission_request(request_for(1, 0b11000000))?;
1856
1857 tokio::time::sleep(4 * cfg.expected_packet_latency).await;
1859 state.stop()?;
1860
1861 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1862 assert_eq!(
1863 2,
1864 ctl_msgs.len(),
1865 "no segments must be sent on the throttled request, but the full-frame resend must fire"
1866 );
1867 assert_eq!(SessionMessage::Segment(expected_segments[0].clone()), ctl_msgs[0]);
1868 assert_eq!(SessionMessage::Segment(expected_segments[1].clone()), ctl_msgs[1]);
1869
1870 Ok(())
1871 }
1872
1873 #[test_log::test(tokio::test)]
1874 async fn ack_state_receiver_must_not_cancel_our_full_frame_resend_when_it_admits_but_cannot_serve_a_frame()
1875 -> anyhow::Result<()> {
1876 let cfg = AcknowledgementStateConfig {
1877 mode: AcknowledgementMode::Full,
1878 expected_packet_latency: Duration::from_millis(100), max_outgoing_frame_retries: 1,
1881 max_frame_retransmission_services: usize::MAX,
1885 max_frame_retransmission_burst: usize::MAX,
1886 frame_retransmission_refill_interval: Some(Duration::from_secs(60)),
1887 min_frame_retransmission_interval: Some(Duration::from_millis(1)),
1888 ..Default::default()
1889 };
1890
1891 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1892 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1893
1894 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1895 state.run(SocketComponents {
1896 inspector: inspector.into(),
1897 ctl_tx,
1898 })?;
1899
1900 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 2 * MTU }>(), MTU, 1)?;
1901 for segment in &expected_segments {
1902 state.segment_sent(segment)?;
1903 }
1904
1905 tokio::time::sleep(Duration::from_millis(10)).await;
1906
1907 state.incoming_retransmission_request(request_for(1, 0b00000010))?;
1912
1913 tokio::time::sleep(4 * cfg.expected_packet_latency).await;
1915 state.stop()?;
1916
1917 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1918 assert_eq!(
1919 2,
1920 ctl_msgs.len(),
1921 "nothing must be sent on the unservable request, but the full-frame resend must fire"
1922 );
1923 assert_eq!(SessionMessage::Segment(expected_segments[0].clone()), ctl_msgs[0]);
1924 assert_eq!(SessionMessage::Segment(expected_segments[1].clone()), ctl_msgs[1]);
1925
1926 Ok(())
1927 }
1928
1929 #[test_log::test(tokio::test)]
1930 async fn ack_state_receiver_must_not_charge_a_frame_whose_segments_could_not_be_queued() -> anyhow::Result<()> {
1931 let cfg = AcknowledgementStateConfig {
1932 mode: AcknowledgementMode::Partial,
1934 min_frame_retransmission_interval: Some(Duration::from_secs(60)),
1936 max_frame_retransmission_burst: usize::MAX,
1937 frame_retransmission_refill_interval: Some(Duration::from_secs(60)),
1938 ..Default::default()
1939 };
1940
1941 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1942 let (ctl_tx, mut ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1);
1944
1945 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1946 state.run(SocketComponents {
1947 inspector: inspector.into(),
1948 ctl_tx,
1949 })?;
1950
1951 let frame_1 = segment(hopr_types::crypto_random::random_bytes::<MTU>(), MTU, 1)?;
1952 let frame_2 = segment(hopr_types::crypto_random::random_bytes::<MTU>(), MTU, 2)?;
1953 for segment in frame_1.iter().chain(frame_2.iter()) {
1954 state.segment_sent(segment)?;
1955 }
1956
1957 let both = SegmentRequest::from_iter([(1, [0b10000000].into()), (2, [0b10000000].into())]);
1959 assert!(matches!(
1960 state.incoming_retransmission_request(both),
1961 Err(SessionError::ProcessingError(_))
1962 ));
1963
1964 let msg = tokio::time::timeout(Duration::from_millis(100), ctl_rx.next())
1965 .await
1966 .context("timeout receiving Control message")?;
1967 assert_eq!(Some(SessionMessage::Segment(frame_1[0].clone())), msg);
1968
1969 state.incoming_retransmission_request(request_for(2, 0b10000000))?;
1972 state.incoming_retransmission_request(request_for(1, 0b10000000))?;
1973
1974 state.stop()?;
1975
1976 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
1977 assert_eq!(
1978 vec![SessionMessage::Segment(frame_2[0].clone())],
1979 ctl_msgs,
1980 "only the unqueued frame must be servable again"
1981 );
1982
1983 Ok(())
1984 }
1985
1986 #[test_log::test(tokio::test)]
1987 async fn ack_state_receiver_must_service_an_honest_request_unchanged() -> anyhow::Result<()> {
1988 let cfg = AcknowledgementStateConfig::default();
1990
1991 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
1992 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
1993
1994 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
1995 state.run(SocketComponents {
1996 inspector: inspector.into(),
1997 ctl_tx,
1998 })?;
1999
2000 let expected_segments = segment(hopr_types::crypto_random::random_bytes::<{ 8 * MTU }>(), MTU, 1)?;
2001 assert_eq!(8, expected_segments.len());
2002 for segment in &expected_segments {
2003 state.segment_sent(segment)?;
2004 }
2005
2006 state.incoming_retransmission_request(request_for(1, 0b11111111))?;
2008
2009 tokio::time::sleep(Duration::from_millis(100)).await;
2010 state.stop()?;
2011
2012 let ctl_msgs = ctl_rx.collect::<Vec<_>>().await;
2013 assert_eq!(
2014 8,
2015 ctl_msgs.len(),
2016 "all requested segments must be sent under the default config"
2017 );
2018 for (i, expected_segment) in expected_segments.iter().enumerate() {
2019 assert_eq!(SessionMessage::Segment(expected_segment.clone()), ctl_msgs[i]);
2020 }
2021
2022 Ok(())
2023 }
2024
2025 #[tokio::test]
2026 async fn retransmission_budget_must_not_grow_on_unserved_frame_ids() -> anyhow::Result<()> {
2027 let cfg = AcknowledgementStateConfig {
2028 max_frame_retransmission_burst: 2 * SegmentRequest::<MTU>::MAX_ENTRIES,
2029 frame_retransmission_refill_interval: Some(Duration::from_secs(3600)),
2031 ..Default::default()
2032 };
2033
2034 let inspector = FrameInspector(FrameDashMap::with_capacity(10));
2035 let (ctl_tx, ctl_rx) = bounded_sink_channel::<SessionMessage<MTU>>(1024);
2036
2037 let mut state = AcknowledgementState::<MTU>::new("test", cfg);
2038 state.run(SocketComponents {
2039 inspector: inspector.into(),
2040 ctl_tx,
2041 })?;
2042
2043 let bogus_request = (1..=SegmentRequest::<MTU>::MAX_ENTRIES)
2046 .map(|i| (i as FrameId, [0b11111111].into()))
2047 .collect::<SegmentRequest<MTU>>();
2048 state.incoming_retransmission_request(bogus_request)?;
2049
2050 let budget = state
2052 .context
2053 .as_ref()
2054 .context("state must be running")?
2055 .retransmission_budget
2056 .clone();
2057
2058 state.stop()?;
2059
2060 assert!(ctl_rx.collect::<Vec<_>>().await.is_empty());
2061
2062 let budget = budget.lock();
2063 assert!(
2064 budget.services.is_empty(),
2065 "unserved frame ids must not allocate bookkeeping"
2066 );
2067 assert_eq!(
2068 budget.max_tokens - SegmentRequest::<MTU>::MAX_ENTRIES,
2069 budget.tokens,
2070 "every bogus frame must have been admitted and charged one token"
2071 );
2072
2073 Ok(())
2074 }
2075
2076 #[test]
2077 fn retransmission_budget_must_refill_a_full_allowance_within_one_refill_interval() {
2078 const TOKENS: usize = 10;
2082 let interval = Duration::from_millis(100);
2083 let t0 = Instant::now();
2084
2085 let drained = || {
2088 let mut budget = RetransmissionBudget::new(
2089 Duration::from_millis(1), usize::MAX, interval,
2092 TOKENS,
2093 );
2094 for _ in 0..TOKENS {
2095 assert!(budget.admit(1, t0), "the initial allowance must be spendable");
2096 }
2097 assert!(!budget.admit(1, t0), "an exhausted bucket must refuse");
2098 budget
2099 };
2100
2101 fn drain_to(budget: &mut RetransmissionBudget, at: Instant) -> usize {
2103 let mut admitted = 0;
2104 while budget.admit(1, at) {
2105 admitted += 1;
2106 assert!(admitted <= TOKENS, "must never exceed the allowance");
2107 }
2108 admitted
2109 }
2110
2111 let mut budget = drained();
2113 assert_eq!(TOKENS / 2, drain_to(&mut budget, t0 + interval / 2));
2114
2115 let mut budget = drained();
2117 assert_eq!(
2118 TOKENS,
2119 drain_to(&mut budget, t0 + interval),
2120 "a full refill interval must restore the whole allowance"
2121 );
2122
2123 let mut budget = drained();
2125 assert_eq!(
2126 TOKENS,
2127 drain_to(&mut budget, t0 + Duration::from_secs(3600)),
2128 "the bucket must cap at max_tokens"
2129 );
2130
2131 let mut budget = drained();
2134 let mut admitted = 0;
2135 for step in 1..=TOKENS as u32 {
2136 admitted += drain_to(&mut budget, t0 + interval * step / TOKENS as u32);
2137 }
2138 assert_eq!(
2139 TOKENS, admitted,
2140 "sub-token calls must not discard the elapsed remainder"
2141 );
2142 }
2143
2144 #[test]
2145 fn ack_state_config_should_derive_retransmission_budget_defaults() {
2146 use hopr_protocol_app::prelude::ApplicationData;
2147
2148 assert_eq!(3238, ApplicationData::PAYLOAD_SIZE);
2150 assert_eq!(646, SegmentRequest::<{ ApplicationData::PAYLOAD_SIZE }>::MAX_ENTRIES);
2151 assert_eq!(
2152 8,
2153 SegmentRequest::<{ ApplicationData::PAYLOAD_SIZE }>::MAX_MISSING_SEGMENTS_PER_FRAME
2154 );
2155
2156 let derived = AcknowledgementStateConfig::default().normalize::<{ ApplicationData::PAYLOAD_SIZE }>();
2157 assert_eq!(
2158 Some(Duration::from_millis(10)),
2159 derived.min_frame_retransmission_interval
2160 );
2161 assert_eq!(3 * 8, derived.max_frame_retransmission_services);
2162 assert_eq!(2 * 646, derived.max_frame_retransmission_burst);
2163 assert_eq!(
2164 Some(Duration::from_millis(20)),
2165 derived.frame_retransmission_refill_interval
2166 );
2167
2168 let explicit_zero = AcknowledgementStateConfig {
2170 min_frame_retransmission_interval: Some(Duration::ZERO),
2171 max_frame_retransmission_services: 0,
2172 max_frame_retransmission_burst: 0,
2173 frame_retransmission_refill_interval: Some(Duration::ZERO),
2174 ..Default::default()
2175 }
2176 .normalize::<{ ApplicationData::PAYLOAD_SIZE }>();
2177 assert_eq!(derived, explicit_zero);
2178
2179 let explicit = AcknowledgementStateConfig {
2181 min_frame_retransmission_interval: Some(Duration::from_millis(5)),
2182 max_frame_retransmission_services: 7,
2183 max_frame_retransmission_burst: 9,
2184 frame_retransmission_refill_interval: Some(Duration::from_millis(11)),
2185 ..Default::default()
2186 }
2187 .normalize::<{ ApplicationData::PAYLOAD_SIZE }>();
2188 assert_eq!(
2189 Some(Duration::from_millis(5)),
2190 explicit.min_frame_retransmission_interval
2191 );
2192 assert_eq!(7, explicit.max_frame_retransmission_services);
2193 assert_eq!(9, explicit.max_frame_retransmission_burst);
2194 assert_eq!(
2195 Some(Duration::from_millis(11)),
2196 explicit.frame_retransmission_refill_interval
2197 );
2198 }
2199}