proposal: Hummingbird Border Router

[juagargi]

Hummingbird QoS Protocol

• Author: Juan A. Garcia-Pardo
• Last updated: 2025-12-01
• Discussion at: -

Abstract

Hummingbird is a QoS protocol that runs on top of SCION.
It allows ASes to list part of their bandwidth in marketplaces,
and clients to purchase this bandwidth via reservations.
The protocol consists of three distinct planes:

• Control-plane.
• Marketplace.
• Data-plane.

The control-plane is inherited from the SCION control-plane,
and allows ASes and clients to find paths between source and destination pairs.
Additionally, ASes can create flyovers between an ingress and an egress interface,
with certain bandwidth and validity time (start-time and end-time of the flyover).
These flyovers are then listed in a marketplace in the form of assets,
and made available for clients to purchase.

At the marketplace, when a client purchases an asset,
it has the right to sell it again, or to convert it into a reservation.
A reservation is created from an asset via a process of redemption,
where the client contacts the owning AS with the asset and the client information,
morphing the asset into an intransferable reservation,
valid only for that particular client.
Reservations are not tradable anymore, as they work only for the client that redeemed the asset.

Once the reservation is created,
it can be used on a path that transits the owning AS using the ingress-egress pair of the reservation.
If the reservation is used following the specified parameters of bandwidth and validity time,
the packets transiting that AS are guaranteed to be forwarded without losses.

This path between a source end-host in AS A, and a destination end-host in AS D,
contains only one flyover, guaranteed transit at AS B through interfaces 1🡒2,
with bandwidth 3Mbps, and valid between 13:20 and 13:40 (full timestamp not shown for brevity).
Note that the transit through AS C does not have a reservation, thus packets may be dropped there.

The wire formats of the Hummingbird headers are available in
[TODO change to file doc/protocols/hummingbird-headers]
PR #4849.

Control-plane

The interactions with the marketplace are out of scope of both this document
and the implementation of Hummingbird for SCION in scionproto/scion.
For reference, but not authoritatively, this interaction includes the following:

• Publishing assets to the marketplace.
• Purchasing assets from the marketplace.
• Redemption of assets into reservations.

Once the reservations are obtained by the client,
they can be assembled into existing paths to create a fully or partially reserved path:
fully when all hops contain reservations, partially reserved when not.

Obtaining paths from source to destination is done by means of the SCION control-plane,
and it is typically done by the clients before obtaining the reservations.
Once a regular SCION path exists, and the reservations are obtained,
there is a process of merging both together.
This yields a reserved path, that is usable by the data-plane.

Border Router

The border router in scionproto/scion needs to be modified in order to
forward packets of Hummingbird path type.

The high level steps necessary to forward a Hummingbird packet are:

1. Check the path type.
2. Parse the packet into a Hummingbird path structure.
3. Determine if priority applies (check Flyover bit).
   1. If not priority, go to 4. Otherwise, set the priority flag in the processor for this packet.
   2. Check flyover MAC. Drop if incorrect.
   3. Check reservation validity, if outside it, unset the priority flag in the processor.
   4. Recompute SCION MAC and go to 4.
4. Check SCION MAC. Drop if incorrect.
5. Update SegID and CurrHF.
6. Check bandwidth usage. If exceeded, unset the priority flag in the processor for this packet.
7. Move to the forwarding queue Priority if the priority flag is set in the processor,
   or to the forwarding queue Best Effort otherwise.

Bandwidth Policing

The bandwidth policing is done with a token bucket algorithm,
using 8 bytes to keep a timestamp per reservation ID.
These timestamps can be stored in a border-router-available Timestamps array,
allowing for an efficient space usage,
provided that the reservation IDs present in the packets are sequential
(which we can control when we design the publishing of the assets to the marketplace).
Example in a pseudo-Go function:

// Returns true if forwarding with priority.
func BandwidthPolice(pkt, Timestamps) bool
    now := time.Now()
    TS := max(Timestamps[pkt.ResID], now) + (pkt.Len / pkt.BW)
    if TS <= now + BURST_TIME {
        Timestamps[pkt.ResID] = TS
        return true
    }
    return false

[tzaeschke]

Sorry for the brain dump, I hope it makes some sense:

• Border routers do not keep state for forwarding other than one secret key.

  Minor: What about the token bucket?

• Maybe I overlooked it, but how does the implementation distinguish normal packets from Hummingbird packets? It seems the first difference is the slightly longer CurrHF field?

• Between 1 and 64 flyover or hop fields.

  Where does 64 come from? CurrHF is incremented by a minimum of 3, that would allow 256/3 = 85?

• The segXLen is now 7 bits, why has that changed? 7bits mean 512 bytes, isn't that a bit much? Is there a concern that the old 6bit width is not sufficient?
  I think I would rather have a few more bits remaining for future flags ...?

• Packet counter: I assume the counter start from 0 for every millisecond? Or does it increment over the whole session? Can you clarify?

• Regarding question 1:

  A border router with priorities is needed. Will it be enough to add priority queues like proposed on PR border router: traffic control (scheduling) #4054 ?

  Can you say about more about the desired prioritization?
  Are Hummingbird packets always prioritized over normal packets? But below BFD packets? Where in the queue go packets that exceed the bucket? See also next point.

• "Forwarding Steps for a Hummingbird packet" & "Bandwidth Policing"

  3 If the packet was marked as guaranteed forwarding:
  - Check the bandwidth usage of its reservation. If bucket is full, mark the packet as best-effort.
  4 Check the computed guarantee class of the packet:
  - If it is guaranteed forwarding, forward it with priority.
  - Otherwise, forward it as best effort

  Let's assume a packet P1 gets "best-effort" because the bucket is empty.

  • Where does it get queued, at the end of the queue or still before "normal" traffic?
  • Now, before P1 is sent, a token comes free in the bucket, a packet P2 arrives and is scheduled with priority. I assume it should still wait for P1 to be sent first? Is P1 re-prioritized if tokens become free?

• General comment, I am not sure that the discussion on the capabilities of "Go" should be in this document, shouldn't it be language agnostic?

[juagargi]

Thanks for the review Til. Answers are online below the questions.

Sorry for the brain dump, I hope it makes some sense:

• Border routers do not keep state for forwarding other than one secret key.

  Minor: What about the token bucket?

True, the token bucket is a special state for the BR. Fixed.

• Maybe I overlooked it, but how does the implementation distinguish normal packets from Hummingbird packets? It seems the first difference is the slightly longer CurrHF field?

Hummingbird packets have their own path type.

• Between 1 and 64 flyover or hop fields.

  Where does 64 come from? CurrHF is incremented by a minimum of 3, that would allow 256/3 = 85?

CurrHF (8 bits) and SegLen[3] ($3 \times 7$bit) limit the amount of flyovers. A flyover is 5 lines ($5 \times 4 = 20$ bytes).
CurrHF thus can offset up to $2^8/5 = 51$ (52 flyovers). Each SegLen is 7 bit, can represent up to $2^7 / 5 = 25$ flyovers each, $3 \times 25 = 75$. The minimum between both CurrHF and SegLen is 52.
Fixed and clarified where the number comes from.
The former $64$ probably comes from the standard SCION path type definition, but it's incorrect.

• The segXLen is now 7 bits, why has that changed? 7bits mean 512 bytes, isn't that a bit much? Is there a concern that the old 6bit width is not sufficient?
  I think I would rather have a few more bits remaining for future flags ...?

With a SegLen of 6 bits we would have segments of maximum 12 flyovers, for a total of $3 \times 12 = 36$ flyovers on a given path. I am not aware of the whole process of why that was deemed insufficient.

• Packet counter: I assume the counter start from 0 for every millisecond? Or does it increment over the whole session? Can you clarify?

Correct. It is specifically stated: "to ensure that the tuple (BaseTimestamp, MillisTimestamp, Counter) is unique", so it is enough to set the counter to zero on every new millisecond, although not mandatory.

• Regarding question 1:

  A border router with priorities is needed. Will it be enough to add priority queues like proposed on PR border router: traffic control (scheduling) #4054 ?

  Can you say about more about the desired prioritization?
  Are Hummingbird packets always prioritized over normal packets? But below BFD packets? Where in the queue go packets that exceed the bucket? See also next point.

Hummingbird packets are always prioritized over regular traffic. BFD packets are also always prioritized over regular traffic. Note that there should be no problem here, as the operators define the maximum Hummingbird traffic taking into account their available bandwidth minus the BFD traffic. One priority queue for all priority traffic and another one for best effort, should satisfy the requirements.

• "Forwarding Steps for a Hummingbird packet" & "Bandwidth Policing"

  3 If the packet was marked as guaranteed forwarding:

  • Check the bandwidth usage of its reservation. If bucket is full, mark the packet as best-effort.
    4 Check the computed guarantee class of the packet:
  • If it is guaranteed forwarding, forward it with priority.
  • Otherwise, forward it as best effort

  Let's assume a packet P1 gets "best-effort" because the bucket is empty.

  • Where does it get queued, at the end of the queue or still before "normal" traffic?

Ideally, it would enter the queue as if it had been a best-effort packet all along,
i.e., if the best-effort queue had packet $P_i$ as the last packet when the processing of the packet started,
and during the processing of the Hummingbird packet other packets $P_j, P_k$ was added to the best-effort queue,
the best-effort queue tail would look like (in order of planned forwarding): $P_i$, $P_{Humm}$, $P_j,P_k$.
But this might prove itself to be too complex, so the demoted Hummingbird packet would enter the queue
at the last position at the moment it is discovered to be best-effort,
with the queue looking like (in order of planned forwarding): $P_i,P_j,P_k,P_{Humm}$.

• Now, before P1 is sent, a token comes free in the bucket, a packet P2 arrives and is scheduled with priority. I assume it should still wait for P1 to be sent first? Is P1 re-prioritized if tokens become free?

The P1 packet is not promoted to priority. When P2 is processed, the bandwidth usage is checked,
if at this moment there are tokens, it passes this check.

• General comment, I am not sure that the discussion on the capabilities of "Go" should be in this document, shouldn't it be language agnostic?

I don't know if the proposal template includes questions about the design of the implementation.
If it covers only the protocol, then I will move them to a different place,
a new issue that I could open to track these questions.

Note that I would refrain from discussing the Hummingbird protocol itself, not for the lack of improvements,
but mainly because Anapaya has agreed to implemented as it is currently defined.
I don't know if they want to discuss the protocol itself, as it would imply re-assessing security implications,
economic model, and possibly scalability, without the benefit of peer reviews from the broader community.
Maybe @shitz or @sgmonroy want to chime in regard to this.

[JordiSubira]

Thank you, Juan, for the proposal. Given the scope and complexity of this feature, I recommend structuring the implementation as a phased roadmap. This will help us coordinate effectively, identify dependencies early and limiting scope for changes.

First, I assume there is an overall consensus about the usability/feasability of the feature. As you say, we do not have to discuss this here. The feature (QoS via path reservation system) MUST be added and the system/protocol for implementing this feature (i.e., Hummingbird) has been already decided upon. Thus, here we will discuss how to add Hummingbird to scionproto.

Proposed Approach

I envision breaking down the implementation into clear phases:

1. Component Scoping - Define what changes where

• Identify components requiring changes within scionproto/scion
• Define API contracts between components (focus on scionproto interfaces)
  • This will allow a clear definition of what to expect at each component level.
• Map high-level components to concrete packages
  • Example: "Endhost" → changes to /pkg/snet, /daemon (or whereever we define the new endhost API (#4834))
• Clarify external dependencies
  • e.g., if we assume an external library, what's the interface for that library

2. Modular Design Proposals - Break into manageable pieces

• Each proposal addresses a comprehensible subset:
  • e.g., BR priority queues, hummingbird dataplane changes, endhost changes, etc.
• Proposals can be reviewed and refined independently

3. Specifications as Implementation Contract

• Wire format specification
• API specifications (versioned, stable contracts)
• Iterative refinement based on implementation feedback, while maintaining API stability

4. Implementation PRs - Code with clear scope

• Implementation-specific decisions deferred to PR review
  - e.g., discussion about having Go generics vs duplication
• Each PR implements a well-defined component from the specification

---

Components Requiring Changes

Some early outline for discussion:

1. Endhost ↔ Marketplace API

• Question: Is this API standardized, or marketplace-specific?
• Implementation options:
  • Marketplace client library in scionproto/snet
  • Separate scionproto/hummingbird-market package
  • External implementation (reference client only)

2. Endhost ↔ Control Plane API

• Current status: Path lookup returns SCION path segments
• Hummingbird needs: Paths with embedded reservation information (flyovers)
• Example Questions:
  • How does endhost learn about available reservations? (doesn't have to be via endhost API)
  • Where does path assembly with flyovers happen? (daemon, endhost library, control service)
  • Does this integrate with the new endhost API (#4834)?

3. Control Service ↔ Marketplace (If Applicable)

• Clarificatio: If I understood correctly, there IS NOT interaction between marketplace and control service.
• Questions
  • Is there a separate AS-level service managing marketplace interaction?
  • Flyovers advertised through beaconing (no marketplace API needed at CS level)? Do we add this? At what face?
  • What if master key has been rotated?
• Clarify control plane's role in reservation discovery/advertisement

4. Data Plane Changes

a. Wire Format

• The new wire-format introduces a significant complexity: e.g., variable-size field parsing, F-bit semantics, CurrHF increment logic
• I would create a standalone wire format specification document

b. Border Router Processing

• Changes:
  • New path type processing (processHummingbird())
  • Bandwidth policing (token bucket per ResID)
  • State management (timestamp array for ~4M reservations)
  • Cryptographic operations (A_k derivation, FlyoverMAC verification)
• Performance considerations: Sequential parsing overhead, crypto operations, cache effects

c. Priority Queues (BLOCKER)

• Status: Proposal assumes PR border router: traffic control (scheduling) #4054 (traffic control/scheduling) is merged
• Reality: PR border router: traffic control (scheduling) #4054 is CLOSED, not merged
• Action required:
  • Investigate PR border router: traffic control (scheduling) #4054 disposition (can we reuse something after BR improvements?)
  • I woudl consider standalone priority queue proposal
  • This is a prerequisite for guaranteed forwarding

5. Border Router ↔ Key Management

• Current state: For the current implementation we Forwarding secret we assume (master.key)is manually distributed and synchronized between CS and BRs. The current OS implementation does not provide any system that handles key rotation.
• The only document I am aware of that discusses an actual system to do this is Forwarding key rollover (outdated)
• Hummingbird requirements:
  • Separate secret for Hummingbird MACs
  • Key rotation with its own particularities
• We may also assume the key is there for the BR to use, without defining how the AS must managed and synchronize the keys. Is this acceptable for now?

---

Summary

1. Clarify component boundaries - Offline coordination to define what goes where. What's implemented in scionproto/scion vs external repositories?
2. Establish API contracts
3. Create modular proposals
4. Phased implementation

---

[juagargi]

Thanks Jordi for the detailed help.

I'd like to initially only focus on the data-plane changes, namely, those that affect the border-router to enable it to forward Hummingbird packets. The only affected component (at least for this step) is the border router.
Sub-components would be:

• New path type
• New forwarding steps for the new path type

Other modifications (e.g. to the control plane) can be discussed in subsequent proposals, ideally independent from this one.

I've created a PR to add documentation about the Hummingbird headers here: #4849
Additionally, I'm removing the documentation about headers from the initial Hummingbird documentation, at the moment in this issue, that would end up at doc/dev/design.

I will also add a draft PR with the current implementation of the changes to the BR, to add a bit more transparency on what is already there. I will write more details on the PR itself, but the current code is not what I expect to see merged in scionproto/scion, just an initial proposal.

I will also change the title of this proposal to better represent the fact that it affects only the Hummingbird data-plane.

Summary of changes to this proposal:

• Hummingbird headers documentation PR (Document the Hummingbird headers #4849)
• Removed headers from this proposal, referenced the PR above
• Opened draft PR (not to be merged) for transparency on the existing BR implementation ((do not merge) Hummingbird current implementation for visibility #4850)
• Title of this proposal