exponential backoff algorithm「建议收藏」
exponential backoff algorithm「建议收藏」
全栈程序员站长
发布于 2022-07-04 09:16:39
发布于 2022-07-04 09:16:39
文章被收录于专栏：全栈程序员必看
大家好，又见面了，我是你们的朋友全栈君。
在看NDN的默认转发策略BestRoute Strategy中提到了指数退避算法，回忆了一下，即为：
在一个共享信道的情况下，当网络上的节点在发生冲突时，每个节点节点等待一定的时间后重新发送。在二进制指数退避算法中，等待时间随着以二为底的指数增长。如果重试失败，那么下次的等待时间将会是上次的等待时间二倍。如果重试次数大于最大重试次数，那么包将从包队列中去除。
BestRoute Strategy：把Interest发给具有最小cost的下一跳，没收到要重传时选择次小cost的下一跳
This strategy forwards a new Interest to the lowest-cost nexthop (except downstream). After that, if consumer retransmits the Interest (and is not suppressed according to exponential backoff algorithm), the strategy forwards the Interest again to the lowest-cost nexthop (except downstream) that is not previously used. If all nexthops have been used, the strategy starts over with the first nexthop.
This strategy returns Nack to all downstreams with reason NoRoute if there is no usable nexthop, which may be caused by: (a) the FIB entry contains no nexthop; (b) the FIB nexthop happens to be the sole downstream; (c) the FIB nexthops violate scope.
This strategy returns Nack to all downstreams if all upstreams have returned Nacks. The reason of the sent Nack equals the least severe reason among received Nacks.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
26 #include "best-route-strategy2.hpp"
27 #include "core/logger.hpp"
28
29 namespace nfd {
30 namespace fw {
31
32 NFD_LOG_INIT("BestRouteStrategy2");
33
34 const Name BestRouteStrategy2::STRATEGY_NAME("ndn:/localhost/nfd/strategy/best-route/%FD%04");
35 NFD_REGISTER_STRATEGY(BestRouteStrategy2);
36
37 const time::milliseconds BestRouteStrategy2::RETX_SUPPRESSION_INITIAL(10);
38 const time::milliseconds BestRouteStrategy2::RETX_SUPPRESSION_MAX(250);
39
40 BestRouteStrategy2::BestRouteStrategy2(Forwarder& forwarder, const Name& name)
41 : Strategy(forwarder, name)
42 , m_retxSuppression(RETX_SUPPRESSION_INITIAL,
43 RetxSuppressionExponential::DEFAULT_MULTIPLIER,
44 RETX_SUPPRESSION_MAX)
45 {
46 }
47
55 static inline bool
56 predicate_NextHop_eligible(const shared_ptr<pit::Entry>& pitEntry,
57 const fib::NextHop& nexthop, FaceId currentDownstream,
58 bool wantUnused = false,
59 time::steady_clock::TimePoint now = time::steady_clock::TimePoint::min())
60 {
61 shared_ptr<Face> upstream = nexthop.getFace();
62
63 // upstream is current downstream
64 if (upstream->getId() == currentDownstream)
65 return false;
66
67 // forwarding would violate scope
68 if (pitEntry->violatesScope(*upstream))
69 return false;
70
71 if (wantUnused) {
72 // NextHop must not have unexpired OutRecord
73 pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(*upstream);
74 if (outRecord != pitEntry->getOutRecords().end() &&
75 outRecord->getExpiry() > now) {
76 return false;
77 }
78 }
79
80 return true;
81 }
82
86 static inline fib::NextHopList::const_iterator
87 findEligibleNextHopWithEarliestOutRecord(const shared_ptr<pit::Entry>& pitEntry,
88 const fib::NextHopList& nexthops,
89 FaceId currentDownstream)
90 {
91 fib::NextHopList::const_iterator found = nexthops.end();
92 time::steady_clock::TimePoint earliestRenewed = time::steady_clock::TimePoint::max();
93 for (fib::NextHopList::const_iterator it = nexthops.begin(); it != nexthops.end(); ++it) {
94 if (!predicate_NextHop_eligible(pitEntry, *it, currentDownstream))
95 continue;
96 pit::OutRecordCollection::const_iterator outRecord = pitEntry->getOutRecord(*it->getFace());
97 BOOST_ASSERT(outRecord != pitEntry->getOutRecords().end());
98 if (outRecord->getLastRenewed() < earliestRenewed) {
99 found = it;
100 earliestRenewed = outRecord->getLastRenewed();
101 }
102 }
103 return found;
104 }
105
106 void
107 BestRouteStrategy2::afterReceiveInterest(const Face& inFace,
108 const Interest& interest,
109 shared_ptr<fib::Entry> fibEntry,
110 shared_ptr<pit::Entry> pitEntry)
111 {
112 const fib::NextHopList& nexthops = fibEntry->getNextHops();
113 fib::NextHopList::const_iterator it = nexthops.end();
114
115 RetxSuppression::Result suppression = m_retxSuppression.decide(inFace, interest, *pitEntry);
116 if (suppression == RetxSuppression::NEW) {
117 // forward to nexthop with lowest cost except downstream
118 it = std::find_if(nexthops.begin(), nexthops.end(),
119 bind(&predicate_NextHop_eligible, pitEntry, _1, inFace.getId(),
120 false, time::steady_clock::TimePoint::min()));
121
122 if (it == nexthops.end()) {
123 NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " noNextHop");
124
125 lp::NackHeader nackHeader;
126 nackHeader.setReason(lp::NackReason::NO_ROUTE);
127 this->sendNack(pitEntry, inFace, nackHeader);
128
129 this->rejectPendingInterest(pitEntry);
130 return;
131 }
132
133 shared_ptr<Face> outFace = it->getFace();
134 this->sendInterest(pitEntry, outFace);
135 NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
136 << " newPitEntry-to=" << outFace->getId());
137 return;
138 }
139
140 if (suppression == RetxSuppression::SUPPRESS) {
141 NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
142 << " suppressed");
143 return;
144 }
145
146 // find an unused upstream with lowest cost except downstream
147 it = std::find_if(nexthops.begin(), nexthops.end(),
148 bind(&predicate_NextHop_eligible, pitEntry, _1, inFace.getId(),
149 true, time::steady_clock::now()));
150 if (it != nexthops.end()) {
151 shared_ptr<Face> outFace = it->getFace();
152 this->sendInterest(pitEntry, outFace);
153 NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
154 << " retransmit-unused-to=" << outFace->getId());
155 return;
156 }
157
158 // find an eligible upstream that is used earliest
159 it = findEligibleNextHopWithEarliestOutRecord(pitEntry, nexthops, inFace.getId());
160 if (it == nexthops.end()) {
161 NFD_LOG_DEBUG(interest << " from=" << inFace.getId() << " retransmitNoNextHop");
162 }
163 else {
164 shared_ptr<Face> outFace = it->getFace();
165 this->sendInterest(pitEntry, outFace);
166 NFD_LOG_DEBUG(interest << " from=" << inFace.getId()
167 << " retransmit-retry-to=" << outFace->getId());
168 }
169 }
170
175 inline lp::NackReason
176 compareLessSevere(lp::NackReason x, lp::NackReason y)
177 {
178 if (x == lp::NackReason::NONE) {
179 return y;
180 }
181 if (y == lp::NackReason::NONE) {
182 return x;
183 }
184 return static_cast<lp::NackReason>(std::min(static_cast<int>(x), static_cast<int>(y)));
185 }
186
187 void
188 BestRouteStrategy2::afterReceiveNack(const Face& inFace, const lp::Nack& nack,
189 shared_ptr<fib::Entry> fibEntry,
190 shared_ptr<pit::Entry> pitEntry)
191 {
192 int nOutRecordsNotNacked = 0;
193 Face* lastFaceNotNacked = nullptr;
194 lp::NackReason leastSevereReason = lp::NackReason::NONE;
195 for (const pit::OutRecord& outR : pitEntry->getOutRecords()) {
196 const lp::NackHeader* inNack = outR.getIncomingNack();
197 if (inNack == nullptr) {
198 ++nOutRecordsNotNacked;
199 lastFaceNotNacked = outR.getFace().get();
200 continue;
201 }
202
203 leastSevereReason = compareLessSevere(leastSevereReason, inNack->getReason());
204 }
205
206 lp::NackHeader outNack;
207 outNack.setReason(leastSevereReason);
208
209 if (nOutRecordsNotNacked == 1) {
210 BOOST_ASSERT(lastFaceNotNacked != nullptr);
211 pit::InRecordCollection::const_iterator inR = pitEntry->getInRecord(*lastFaceNotNacked);
212 if (inR != pitEntry->getInRecords().end()) {
213 // one out-record not Nacked, which is also a downstream
214 NFD_LOG_DEBUG(nack.getInterest() << " nack-from=" << inFace.getId() <<
215 " nack=" << nack.getReason() <<
216 " nack-to(bidirectional)=" << lastFaceNotNacked->getId() <<
217 " out-nack=" << outNack.getReason());
218 this->sendNack(pitEntry, *lastFaceNotNacked, outNack);
219 return;
220 }
221 }
222
223 if (nOutRecordsNotNacked > 0) {
224 NFD_LOG_DEBUG(nack.getInterest() << " nack-from=" << inFace.getId() <<
225 " nack=" << nack.getReason() <<
226 " waiting=" << nOutRecordsNotNacked);
227 // continue waiting
228 return;
229 }
230
231
232 NFD_LOG_DEBUG(nack.getInterest() << " nack-from=" << inFace.getId() <<
233 " nack=" << nack.getReason() <<
234 " nack-to=all out-nack=" << outNack.getReason());
235 this->sendNacks(pitEntry, outNack);
236 }
237
238 } // namespace fw
239 } // namespace nfd发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/148775.html原文链接：https://javaforall.cn
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
