blob: e8ea4f6059c454f4fb5df7ce8a1a7c5249730337 [file] [log] [blame]
Yingdi Yuf7ede412014-08-30 20:37:52 -07001/* -*- Mode: C++; c-file-style: "gnu"; indent-tabs-mode:nil -*- */
2/*
3 * Copyright (c) 2012-2014 University of California, Los Angeles
4 *
5 * This file is part of ChronoSync, synchronization library for distributed realtime
6 * applications for NDN.
7 *
8 * ChronoSync is free software: you can redistribute it and/or modify it under the terms
9 * of the GNU General Public License as published by the Free Software Foundation, either
10 * version 3 of the License, or (at your option) any later version.
11 *
12 * ChronoSync is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
13 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
14 * PURPOSE. See the GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License along with
17 * ChronoSync, e.g., in COPYING.md file. If not, see <http://www.gnu.org/licenses/>.
18 *
19 * @author Zhenkai Zhu <http://irl.cs.ucla.edu/~zhenkai/>
20 * @author Chaoyi Bian <bcy@pku.edu.cn>
21 * @author Alexander Afanasyev <http://lasr.cs.ucla.edu/afanasyev/index.html>
22 * @author Yingdi Yu <yingdi@cs.ucla.edu>
23 */
24
25#ifndef CHRONOSYNC_LOGIC_HPP
26#define CHRONOSYNC_LOGIC_HPP
27
28#include "boost-header.h"
29#include <memory>
Qiuhan Ding8c095fd2014-11-19 17:38:32 -080030#include <unordered_map>
Yingdi Yuf7ede412014-08-30 20:37:52 -070031
32#include <ndn-cxx/face.hpp>
33#include <ndn-cxx/util/scheduler.hpp>
34#include <ndn-cxx/security/key-chain.hpp>
Yingdi Yucd339022014-11-05 17:51:19 -080035#include <ndn-cxx/security/validator.hpp>
Yingdi Yuf7ede412014-08-30 20:37:52 -070036
37#include "interest-table.hpp"
38#include "diff-state-container.hpp"
39
40namespace chronosync {
41
42/**
43 * @brief The missing sequence numbers for a session
44 *
45 * This class is used to notify the clients of Logic
46 * the details of state changes.
47 *
48 * Instances of this class is usually used as elements of some containers
49 * such as std::vector, thus it is copyable.
50 */
Qiuhan Ding8c095fd2014-11-19 17:38:32 -080051class NodeInfo {
52public:
53 Name userPrefix;
54 Name signingId;
55 Name sessionName;
56 SeqNo seqNo;
57};
58
Yingdi Yuf7ede412014-08-30 20:37:52 -070059class MissingDataInfo
60{
61public:
62 /// @brief session name
63 Name session;
64 /// @brief the lowest one of missing sequence numbers
65 SeqNo low;
66 /// @brief the highest one of missing sequence numbers
67 SeqNo high;
68};
69
70/**
71 * @brief The callback function to handle state updates
72 *
73 * The parameter is a set of MissingDataInfo, of which each corresponds to
74 * a session that has changed its state.
75 */
76typedef function<void(const std::vector<MissingDataInfo>&)> UpdateCallback;
77
78/**
79 * @brief Logic of ChronoSync
80 */
81class Logic : noncopyable
82{
83public:
Qiuhan Ding8c095fd2014-11-19 17:38:32 -080084 class Error : public std::runtime_error
85 {
86 public:
87 explicit
88 Error(const std::string& what)
89 : std::runtime_error(what)
90 {
91 }
92 };
93
94public:
Yingdi Yuf7ede412014-08-30 20:37:52 -070095 static const time::steady_clock::Duration DEFAULT_RESET_TIMER;
96 static const time::steady_clock::Duration DEFAULT_CANCEL_RESET_TIMER;
97 static const time::milliseconds DEFAULT_RESET_INTEREST_LIFETIME;
98 static const time::milliseconds DEFAULT_SYNC_INTEREST_LIFETIME;
99 static const time::milliseconds DEFAULT_SYNC_REPLY_FRESHNESS;
100
101 /**
102 * @brief Constructor
103 *
104 * @param syncPrefix The prefix of the sync group
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800105 * @param defaultUserPrefix The prefix of the first user added to this session
Yingdi Yuf7ede412014-08-30 20:37:52 -0700106 * @param onUpdate The callback function to handle state updates
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800107 * @param defaultSigningId The signing Id of the default user
Yingdi Yucd339022014-11-05 17:51:19 -0800108 * @param validator The validator for packet validation
Yingdi Yuf7ede412014-08-30 20:37:52 -0700109 * @param resetTimer The timer to periodically send Reset Interest
110 * @param syncReplyFreshness The FreshnessPeriod of sync reply
111 * @param resetInterestLifetime The lifetime of sync interest
112 * @param resetInterestLifetime The lifetime of Reset Interest
113 * @param cancelResetTimer The timer to exit from Reset state
114 */
115 Logic(ndn::Face& face,
116 const Name& syncPrefix,
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800117 const Name& defaultUserPrefix,
Yingdi Yuf7ede412014-08-30 20:37:52 -0700118 const UpdateCallback& onUpdate,
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800119 const Name& defaultSigningId = DEFAULT_NAME,
Yingdi Yucd339022014-11-05 17:51:19 -0800120 ndn::shared_ptr<ndn::Validator> validator = DEFAULT_VALIDATOR,
Yingdi Yuf7ede412014-08-30 20:37:52 -0700121 const time::steady_clock::Duration& resetTimer = DEFAULT_RESET_TIMER,
122 const time::steady_clock::Duration& cancelResetTimer = DEFAULT_CANCEL_RESET_TIMER,
123 const time::milliseconds& resetInterestLifetime = DEFAULT_RESET_INTEREST_LIFETIME,
124 const time::milliseconds& syncInterestLifetime = DEFAULT_SYNC_INTEREST_LIFETIME,
125 const time::milliseconds& syncReplyFreshness = DEFAULT_SYNC_REPLY_FRESHNESS);
126
127 ~Logic();
128
129 /// @brief Reset the sync tree (and restart synchronization again)
130 void
131 reset();
132
133 /**
134 * @brief Set user prefix
135 *
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800136 * This method will also change the default user and signing Id of that user.
Yingdi Yuf7ede412014-08-30 20:37:52 -0700137 *
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800138 * @param defaultUserPrefix The prefix of user.
Yingdi Yuf7ede412014-08-30 20:37:52 -0700139 */
140 void
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800141 setDefaultUserPrefix(const Name& defaultUserPrefix);
Yingdi Yuf7ede412014-08-30 20:37:52 -0700142
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800143 /// @brief Get the name of default user.
Yingdi Yuf7ede412014-08-30 20:37:52 -0700144 const Name&
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800145 getDefaultUserPrefix() const
Yingdi Yuf7ede412014-08-30 20:37:52 -0700146 {
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800147 return m_defaultUserPrefix;
Yingdi Yuf7ede412014-08-30 20:37:52 -0700148 }
149
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800150 /**
151 * @brief Add user node into the local session.
152 *
153 * This method also reset after adding
154 *
155 * @param userPrefix prefix of the added node
156 * @param signingId signing Id of the added node
157 */
158 void
159 addUserNode(const Name& userPrefix, const Name& signingId = DEFAULT_NAME);
160
161 /// @brief remove the node from the local session
162 void
163 removeUserNode(const Name& userPrefix);
164
165 /**
166 * @brief Get the name of the local session.
167 *
168 * This method gets the session name according to prefix, if prefix is not specified,
169 * it returns the session name of default user.
170 *
171 * @param prefix prefix of the node
172 */
173 const Name&
174 getSessionName(Name prefix = EMPTY_NAME);
175
176 /**
177 * @brief Get current seqNo of the local session.
178 *
179 * This method gets the seqNo according to prefix, if prefix is not specified,
180 * it returns the seqNo of default user.
181 *
182 * @param prefix prefix of the node
183 */
Yingdi Yuf7ede412014-08-30 20:37:52 -0700184 const SeqNo&
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800185 getSeqNo(Name prefix = EMPTY_NAME);
Yingdi Yuf7ede412014-08-30 20:37:52 -0700186
187 /**
188 * @brief Update the seqNo of the local session
189 *
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800190 * The method updates the existing seqNo with the supplied seqNo and prefix.
Yingdi Yuf7ede412014-08-30 20:37:52 -0700191 *
192 * @param seq The new seqNo.
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800193 * @param updatePrefix The prefix of node to update.
Yingdi Yuf7ede412014-08-30 20:37:52 -0700194 */
195 void
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800196 updateSeqNo(const SeqNo& seq, const Name& updatePrefix = EMPTY_NAME);
Yingdi Yuf7ede412014-08-30 20:37:52 -0700197
198 /// @brief Get root digest of current sync tree
199 ndn::ConstBufferPtr
200 getRootDigest() const;
201
202 /// @brief Get the name of all sessions
203 std::set<Name>
204 getSessionNames() const;
205
Yingdi Yu906c2ea2014-10-31 11:24:50 -0700206CHRONOSYNC_PUBLIC_WITH_TESTS_ELSE_PRIVATE:
Yingdi Yuf7ede412014-08-30 20:37:52 -0700207 void
208 printState(std::ostream& os) const;
209
210 ndn::Scheduler&
211 getScheduler()
212 {
213 return m_scheduler;
214 }
215
216 State&
217 getState()
218 {
219 return m_state;
220 }
221
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800222
Yingdi Yuf7ede412014-08-30 20:37:52 -0700223private:
224 /**
225 * @brief Callback to handle Sync Interest
226 *
227 * This method checks whether an incoming interest is a normal one or a reset
228 * and dispatches the incoming interest to corresponding processing methods.
229 *
230 * @param prefix The prefix of the sync group.
231 * @param interest The incoming sync interest.
232 */
233 void
234 onSyncInterest(const Name& prefix, const Interest& interest);
235
236 /**
237 * @brief Callback to handle Sync prefix registration failure
238 *
239 * This method does nothing for now.
240 *
241 * @param prefix The prefix of the sync group.
242 * @param msg The error message.
243 */
244 void
245 onSyncRegisterFailed(const Name& prefix, const std::string& msg);
246
247 /**
248 * @brief Callback to handle Sync Reply
249 *
250 * This method calls validator to validate Sync Reply.
251 * For now, validation is disabled, Logic::onSyncDataValidated is called
252 * directly.
253 *
254 * @param interest The Sync Interest
255 * @param data The reply to the Sync Interest
256 */
257 void
258 onSyncData(const Interest& interest, Data& data);
259
260 /**
261 * @brief Callback to handle reply to Reset Interest.
262 *
263 * This method does nothing, since reply to Reset Interest is not useful for now.
264 *
265 * @param interest The Reset Interest
266 * @param data The reply to the Reset Interest
267 */
268 void
269 onResetData(const Interest& interest, Data& data);
270
271 /**
272 * @brief Callback to handle Sync Interest timeout.
273 *
274 * This method does nothing, since Logic per se handles timeout explicitly.
275 *
276 * @param interest The Sync Interest
277 */
278 void
279 onSyncTimeout(const Interest& interest);
280
281 /**
282 * @brief Callback to invalid Sync Reply.
283 *
284 * This method does nothing but drops the invalid reply.
285 *
286 * @param data The invalid Sync Reply
287 */
288 void
289 onSyncDataValidationFailed(const shared_ptr<const Data>& data);
290
291 /**
292 * @brief Callback to valid Sync Reply.
293 *
294 * This method simply passes the valid reply to processSyncData.
295 *
296 * @param data The valid Sync Reply.
297 */
298 void
299 onSyncDataValidated(const shared_ptr<const Data>& data);
300
301 /**
302 * @brief Process normal Sync Interest
303 *
304 * This method extracts the digest from the incoming Sync Interest,
305 * compares it against current local digest, and process the Sync
306 * Interest according to the comparison result. See docs/design.rst
307 * for more details.
308 *
309 * @param interest The incoming interest
310 * @param isTimedProcessing True if the interest needs an immediate reply,
311 * otherwise hold the interest for a while before
312 * making a reply (to avoid unnecessary recovery)
313 */
314 void
315 processSyncInterest(const shared_ptr<const Interest>& interest,
316 bool isTimedProcessing = false);
317
318 /**
319 * @brief Process reset Sync Interest
320 *
321 * This method simply call Logic::reset()
322 *
323 * @param interest The incoming interest.
324 */
325 void
326 processResetInterest(const Interest& interest);
327
328 /**
329 * @brief Process Sync Reply.
330 *
331 * This method extracts state update information from Sync Reply and applies
332 * it to the Sync Tree and re-express Sync Interest.
333 *
334 * @param name The data name of the Sync Reply.
335 * @param digest The digest in the data name.
336 * @param syncReplyBlock The content of the Sync Reply.
337 */
338 void
339 processSyncData(const Name& name,
340 ndn::ConstBufferPtr digest,
341 const Block& syncReplyBlock);
342
343 /**
344 * @brief Insert state diff into log
345 *
346 * @param diff The diff .
347 * @param previousRoot The root digest before state changes.
348 */
349 void
350 insertToDiffLog(DiffStatePtr diff,
351 ndn::ConstBufferPtr previousRoot);
352
353 /**
354 * @brief Reply to all pending Sync Interests with a particular commit (or diff)
355 *
356 * @param commit The diff.
357 */
358 void
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800359 satisfyPendingSyncInterests(const Name& updatedPrefix, ConstDiffStatePtr commit);
Yingdi Yuf7ede412014-08-30 20:37:52 -0700360
361 /// @brief Helper method to send normal Sync Interest
362 void
363 sendSyncInterest();
364
365 /// @brief Helper method to send reset Sync Interest
366 void
367 sendResetInterest();
368
369 /// @brief Helper method to send Sync Reply
370 void
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800371 sendSyncData(const Name& nodePrefix, const Name& name, const State& state);
Yingdi Yuf7ede412014-08-30 20:37:52 -0700372
373 /**
374 * @brief Unset reset status
375 *
376 * By invoking this method, one can add its own state into the Sync Tree, thus
377 * jumping out of the reset status
378 */
379 void
380 cancelReset();
381
382 void
383 printDigest(ndn::ConstBufferPtr digest);
384
Yingdi Yucd339022014-11-05 17:51:19 -0800385public:
386 static const ndn::Name DEFAULT_NAME;
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800387 static const ndn::Name EMPTY_NAME;
Yingdi Yucd339022014-11-05 17:51:19 -0800388 static const ndn::shared_ptr<ndn::Validator> DEFAULT_VALIDATOR;
389
Yingdi Yuf7ede412014-08-30 20:37:52 -0700390private:
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800391 typedef std::unordered_map<ndn::Name, NodeInfo> NodeList;
Yingdi Yuf7ede412014-08-30 20:37:52 -0700392
393 static const ndn::ConstBufferPtr EMPTY_DIGEST;
394 static const ndn::name::Component RESET_COMPONENT;
395
396 // Communication
397 ndn::Face& m_face;
398 Name m_syncPrefix;
399 const ndn::RegisteredPrefixId* m_syncRegisteredPrefixId;
400 Name m_syncReset;
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800401 Name m_defaultUserPrefix;
Yingdi Yuf7ede412014-08-30 20:37:52 -0700402
403 // State
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800404 NodeList m_nodeList;
Yingdi Yuf7ede412014-08-30 20:37:52 -0700405 State m_state;
406 DiffStateContainer m_log;
407 InterestTable m_interestTable;
408 Name m_outstandingInterestName;
409 const ndn::PendingInterestId* m_outstandingInterestId;
410 bool m_isInReset;
411 bool m_needPeriodReset;
412
413 // Callback
414 UpdateCallback m_onUpdate;
415
416 // Event
417 ndn::Scheduler m_scheduler;
418 ndn::EventId m_delayedInterestProcessingId;
419 ndn::EventId m_reexpressingInterestId;
420 ndn::EventId m_resetInterestId;
421
422 // Timer
423 boost::mt19937 m_randomGenerator;
424 boost::variate_generator<boost::mt19937&, boost::uniform_int<> > m_rangeUniformRandom;
425 boost::variate_generator<boost::mt19937&, boost::uniform_int<> > m_reexpressionJitter;
426 /// @brief Timer to send next reset 0 for no reset
427 time::steady_clock::Duration m_resetTimer;
428 /// @brief Timer to cancel reset state
429 time::steady_clock::Duration m_cancelResetTimer;
430 /// @brief Lifetime of reset interest
431 time::milliseconds m_resetInterestLifetime;
432 /// @brief Lifetime of sync interest
433 time::milliseconds m_syncInterestLifetime;
434 /// @brief FreshnessPeriod of SyncReply
435 time::milliseconds m_syncReplyFreshness;
436
Yingdi Yucd339022014-11-05 17:51:19 -0800437 // Security
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800438 ndn::Name m_defaultSigningId;
Yingdi Yuf7ede412014-08-30 20:37:52 -0700439 ndn::KeyChain m_keyChain;
Yingdi Yucd339022014-11-05 17:51:19 -0800440 ndn::shared_ptr<ndn::Validator> m_validator;
Yingdi Yuf7ede412014-08-30 20:37:52 -0700441
Qiuhan Ding8c095fd2014-11-19 17:38:32 -0800442
Yingdi Yuf7ede412014-08-30 20:37:52 -0700443#ifdef _DEBUG
444 int m_instanceId;
445 static int m_instanceCounter;
446#endif
447};
448
449
450} // namespace chronosync
451
452#endif // CHRONOSYNC_LOGIC_HPP