EP4393132A1 - Un mécanisme robuste de saturation de l'âge pour l'arbitrage basé sur l'âge dans les réseaux de paquets - Google Patents

Un mécanisme robuste de saturation de l'âge pour l'arbitrage basé sur l'âge dans les réseaux de paquets

Info

Publication number
EP4393132A1
EP4393132A1 EP22830978.7A EP22830978A EP4393132A1 EP 4393132 A1 EP4393132 A1 EP 4393132A1 EP 22830978 A EP22830978 A EP 22830978A EP 4393132 A1 EP4393132 A1 EP 4393132A1
Authority
EP
European Patent Office
Prior art keywords
age
data packet
queue
data
time
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
EP22830978.7A
Other languages
German (de)
English (en)
Inventor
Brian TOWLES
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Google LLC
Original Assignee
Google LLC
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Priority claimed from US17/704,677 external-priority patent/US12068971B2/en
Application filed by Google LLC filed Critical Google LLC
Publication of EP4393132A1 publication Critical patent/EP4393132A1/fr
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Queue scheduling implementing delay-aware scheduling
    • H04L47/564—Attaching a deadline to packets, e.g. earliest due date first
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/56—Queue scheduling implementing delay-aware scheduling
    • H04L47/564—Attaching a deadline to packets, e.g. earliest due date first
    • H04L47/566—Deadline varies as a function of time spent in the queue
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria

Definitions

  • An aspect of the technology is directed to a method of routing data packets in an interconnection network.
  • the method may include receiving a plurality of data packets at a node in the interconnection network, the node including a set of queues, wherein each received packet of the plurality of data packets includes an age; inputting a set of received data packets of the plurality of data packets to a first queue in the set of queues; and for each data packet in the set of received data packets: replacing the age of the data packet with an injection time corresponding to a local time of the first queue when the data packet was input into the first queue and the age of the data packet; determining an updated age based on the local time of the first queue when the data packet was transmitted from the first queue and the injection time of the data packet; and replacing the injection time of the data packet with the updated age.
  • an arbiter receives a first data packet transmitted from the first queue and at least one other data packet transmitted from one or more of the other queues of the set of queues. In some examples, the arbiter determines an oldest data packet from the first data packet and the at least one other data packet; and transmits the oldest data packet.
  • FIG. 1 illustrates an example interconnection network, in accordance with aspects of the disclosure.
  • FIG. 6 a flow diagram illustrating a data transmission technique for transmitting data to truly wireless devices according to aspects of the disclosure.
  • the age of the data packet By converting the age of the data packet to a time value when added to the aging FIFO, the age of the data packet can again be determined when, or before, it is transmitted from the aging FIFO, thereby avoiding the need to continuously update the age of the data packet as it traverses the FIFO.
  • nodes of the interconnection network may be connected to other nodes via interconnects, such as interconnects 121 and 122.
  • interconnects such as interconnects 121 and 122.
  • interconnects may be any type of connection between nodes, such as wires, cables, traces, etc.
  • each interconnect is shown as a single line, each interconnect may represent any number of connections between nodes.
  • Fig. 1 illustrates a 4x4x4 interconnection network 100
  • the interconnection network can include any number of nodes in any arrangement.
  • an interconnection network may include nodes in a one dimensional array, nodes in a two-dimensional array, independent nodes not included in an array, collection of nodes in any arrangement connected to other nodes, etc.
  • each node may be connected to some or all of the other nodes with any number of interconnects.
  • Fig. 1 is merely an example layout of an interconnection network and the technology described should not be considered limited to the interconnection network shown in Fig. 1.
  • Fig. 2 illustrates an example router 200 configured to control the flow of data packets throughout at least a portion of an interconnection network, such as interconnection network 100.
  • Router 200 includes aging FIFOs 210, 211 which receive data packets directly from a node.
  • the aging FIFOs 210, 211 may receive data packets from the same node or a different node. For instance, aging FIFO 210 may receive data packets from a first node as illustrated by arrow 212 and aging FIFO 211 may receive data packets from a second node as illustrated by arrow 213.
  • Each aging FIFO 210, 211 may transmit data packets to an arbiter 220, as illustrated by arrows 214 and 215, respectively.
  • the arbiter 220 may determine the oldest data packets, based on the age of the data packet and transmit the data packet to another node 230, as illustrated by arrow 231.
  • the data packet 410 may be output by the aging FIFO 411 as illustrated by arrow 451 and input into additional logic 441, as illustrated by arrow 452.
  • Logic 441 may convert the time back to age data representing the current age of the data packet 441 and send the data packet to its next destination, which may be an arbiter, as illustrated by arrow 453. In some instances the time data of the data packet 410 may be changed before it is output by the aging FIFO 411.
  • Figs. 4 A, 4B, and 5 illustrate discrete logic converting the age and time data
  • the logic 440 may be implemented by a processor.
  • the resulting value is a “push_time,” also referred to as an “injection time.”
  • the push_age data of the data packet is replaced with the “push_time” when the data packet is inserted into the aging FIFO.
  • the “push_time” data of the packet is converted to an age value “pop_age” that represents the age of the data packet when it is transmitted from the aging FIFO.
  • the logic represented by an adder, substract the “pop_time” from the current local_time. Pop_time is the same value as the injection time.
  • the age data of the data packet is then updated with the “pop_age,” which indicates the current age of the data packet.
  • pop_age 15(local_time) - 8 (injection time).
  • injection times i.e., push_times
  • the injection time may be converted back to an age using the current value of the local clock.
  • a drawback of age-time-age conversion is that it may be difficult to bound the age of a data packet when it is transmitted from the FIFO. As such, the bit widths required for push and pop times may be larger than provided by the data packet.
  • the push time of a data packet may be modified so it is a bounded amount below the largest push time of data packets that arrived before it to the queue (i.e., aging FIFO). This modification is expected to be minimal and similar to the priority inversion encountered within the FIFO.
  • Age -based arbitration prioritizes older data packets or, equivalently, prioritizes data packets with earlier injection times. If a data packet with an earlier push time arrives at the FIFO after a data packet with a later push time, the earlier data packet will be blocked behind the later packet, essentially inheriting its lower priority. This is the priority inversion.
  • the push time of the data packet may be determined.
  • the push time of the data packet may be determined by calculating the aging FIFO’s local_time minus the packet’s push_age.
  • max_push_time is replaced with the value of push_time previously determined.
  • the various times can all be represented using the same number of bits as the packet ages. M may be considered the bit width of these quantities. In some instances, the M-bit representations can wrap around (i.e., go past the maximum value back to a lower value). In general, this problem may be avoided by comparing differences of times and relying on the properties of the aging FIFO to ensure these differences are always in the range [0, 2 A M).
  • the push_time may be compared to the max_push_time. Instead of comparing them directly, the comparison may be transformed such that it is between differences known to be in [0, 2 A M): push_time ⁇ max_push_time
  • T is a threshold parameter that determines the maximum decrease.
  • the value of the data packet at the head of the FIFO is reviewed and the age of the next entry to be popped (i.e., transmitted) is determined. This age is referred to herein as the pop age.
  • the local time may then be incremented each cycle that the pop_age plus T is less than the maximum age. By doing such, no age of a queued packet can overflow because the bounded decrease ensures that there is no packet in the queue whose age is more than T greater than the age of the head packet. Thus, all times may be represented as M-bit quantities, ignoring wrapping because the pop ages will be within [0, 2 A M].
  • the aging rate is reduced as data packets approach the maximum age. For instance, the aging rate of a data packet may be reduced by factors of two depending on the current age. If the age is less than half the maximum, the aging rate matches the previous section. If the age is between half and three quarters of the maximum, the aging rate is halved, and so on as illustrated in table 1 :
  • Table 1 [0059] For an M-bit age field, age slowing increases the effective maximum age to M2 M .
  • the aging rate values in Table 1 are merely examples, and other rates may be used.
  • the number of bits needed to store the age of a data packet may be determined using the following equation:
  • Figure 6 illustrates a flow diagram for routing data packets in an interconnection network.
  • a plurality of data packets are received at a node in the interconnection network.
  • the node may include a set of queues, wherein each received packet of the plurality of data packets includes an age.
  • the age of the data packet may be replaced with an injection time corresponding to a local time of the first queue when the data packet was input into the first queue and the age of the data packet;
  • an updated age may be determined based on the local time of the first queue when the data packet was transmitted from the first queue and the injection time of the data packet;

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

L'invention concerne des systèmes et procédé d'acheminement de paquets de données dans un réseau d'interconnexion. Les paquets de données transmis par le réseau d'interconnexion comprennent chacun des données relatives à l'âge. Les routeurs positionnés dans le réseau d'interconnexion peuvent commander le flux des paquets de données en utilisant des files d'attente FIFO (premier entré, premier sorti) vieillissantes et des arbitres basés sur l'âge. Les arbitres basés sur l'âge au sein des routeurs sont configurés pour donner la priorité aux paquets de données plus anciens par rapport aux paquets de données plus récents provenant des files d'attente FIFO. Chaque paquet de données inséré dans les files d'attente FIFO peut être mis à jour de manière à ce que les données d'âge du paquet de données soient converties d'un âge à un temps d'injection. Lorsque le paquet de données est lu à partir de la FIFO, les données d'âge du paquet de données sont reconverties en âge.
EP22830978.7A 2022-02-25 2022-10-31 Un mécanisme robuste de saturation de l'âge pour l'arbitrage basé sur l'âge dans les réseaux de paquets Pending EP4393132A1 (fr)

Applications Claiming Priority (3)

Application Number Priority Date Filing Date Title
US202263314067P 2022-02-25 2022-02-25
US17/704,677 US12068971B2 (en) 2022-02-25 2022-03-25 Robust age-saturation mechanism for age-based arbitration in packet networks
PCT/US2022/048395 WO2023163759A1 (fr) 2022-02-25 2022-10-31 Un mécanisme robuste de saturation de l'âge pour l'arbitrage basé sur l'âge dans les réseaux de paquets

Publications (1)

Publication Number Publication Date
EP4393132A1 true EP4393132A1 (fr) 2024-07-03

Family

ID=84688555

Family Applications (1)

Application Number Title Priority Date Filing Date
EP22830978.7A Pending EP4393132A1 (fr) 2022-02-25 2022-10-31 Un mécanisme robuste de saturation de l'âge pour l'arbitrage basé sur l'âge dans les réseaux de paquets

Country Status (3)

Country Link
EP (1) EP4393132A1 (fr)
JP (1) JP2025506593A (fr)
WO (1) WO2023163759A1 (fr)

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7372865B2 (en) * 2003-07-09 2008-05-13 Fujitsu Limited Processing data packets using time stamped marker packets

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20130286825A1 (en) * 2012-04-30 2013-10-31 Derek Alan Sherlock Feed-forward arbitration

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7372865B2 (en) * 2003-07-09 2008-05-13 Fujitsu Limited Processing data packets using time stamped marker packets

Also Published As

Publication number Publication date
WO2023163759A1 (fr) 2023-08-31
JP2025506593A (ja) 2025-03-13

Similar Documents

Publication Publication Date Title
Karim et al. On-chip communication architecture for OC-768 network processors
US7558197B1 (en) Dequeuing and congestion control systems and methods
US7457296B2 (en) Method and apparatus for sorting packets in packet schedulers using a connected trie data structure
US8335158B2 (en) Systems and methods for dropping data using a drop profile
US8681681B2 (en) Dequeuing and congestion control systems and methods for single stream multicast
EP2453612A1 (fr) Dispositif de commande de bus
US7382793B1 (en) Systems and methods for determining the bandwidth used by a queue
WO2020142867A1 (fr) Procédé de mise en forme de trafic et dispositif associé
EP4109853B1 (fr) Filtre à amortissement conçu pour un routage adaptatif à grain fin équilibré en charge dans une interconnexion des systèmes à haute performance
Li et al. Determinism enhancement of AFDX networks via frame insertion and sub-virtual link aggregation
Dridi et al. Design and multi-abstraction-level evaluation of a noc router for mixed-criticality real-time systems
US12068971B2 (en) Robust age-saturation mechanism for age-based arbitration in packet networks
WO2023163759A1 (fr) Un mécanisme robuste de saturation de l'âge pour l'arbitrage basé sur l'âge dans les réseaux de paquets
Daneshtalab et al. CARS: Congestion-aware request scheduler for network interfaces in NoC-based manycore systems
CN116360998A (zh) 片上网络的处理方法、装置及片上网络
CN118661409A (zh) 包网络中基于年龄的仲裁的稳健的年龄饱和机制
CN107018095B (zh) 基于离散事件的交换单元仿真系统及方法
Benacer et al. Design of a low latency 40 Gb/s flow-based traffic manager using high-level synthesis
Li et al. Delay bound analysis for heterogeneous multicore systems using network calculus
CN115514685A (zh) Arinc664终端基于传输表模式的延迟分析方法
US20160103710A1 (en) Scheduling device
Phing et al. Towards high performance network-on-chip: A survey on enabling technologies, open issues and challenges
Acevedo et al. Towards optimal design of avionics networking infrastructures
Joseph et al. Simulation environment for link energy estimation in networks-on-chip with virtual channels
Ebrahimi et al. Partitioning methods for unicast/multicast traffic in 3D NoC architecture

Legal Events

Date Code Title Description
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: UNKNOWN

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE INTERNATIONAL PUBLICATION HAS BEEN MADE

PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: REQUEST FOR EXAMINATION WAS MADE

17P Request for examination filed

Effective date: 20240326

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LI LT LU LV MC ME MK MT NL NO PL PT RO RS SE SI SK SM TR

DAV Request for validation of the european patent (deleted)
DAX Request for extension of the european patent (deleted)
STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: EXAMINATION IS IN PROGRESS

17Q First examination report despatched

Effective date: 20260313