1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
|
/*
Copyright (c) 2012, Matthias Schiffer <mschiffer@universe-factory.net>
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
1. Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation
and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef _FFD_FFD_H_
#define _FFD_FFD_H_
#include "util.h"
#include "netif.h"
#include <net/if.h>
#define FFD_PACKET_MAX 1000
#define FFD_PROTO 0xffd
#define FFD_HELLO_INTERVAL 400
#define FFD_IHU_INTERVAL (3*FFD_HELLO_INTERVAL)
#define FFD_UPDATE_INTERVAL 3000
#define FFD_HELLO_TIMEOUT(interval) (16*(interval))
#define FFD_IHU_TIMEOUT(interval) ((interval)*7/2)
#define FFD_UPDATE_TIMEOUT(interval) ((interval)*7/2) /* 3.5 intervals */
#define FFD_UPDATE_REQUEST_TIMEOUT(interval) ((interval)*13/4) /* 3.25 intervals */
#define FFD_SEQNO_REQUEST_TIMEOUT 50
#define FFD_MAINTENANCE_INTERVAL FFD_HELLO_INTERVAL
#define FFD_DELAY (FFD_HELLO_INTERVAL/2)
#define FFD_URGENT_DELAY 20
#define FFD_UPDATE_WITH_DATA 0x01
typedef struct __attribute__((packed)) _ffd_node_id_t {
uint8_t id[8];
} ffd_node_id_t;
typedef struct _ffd_metric_seqno_t {
uint16_t metric;
uint16_t seqno;
} ffd_metric_seqno_t;
typedef struct _ffd_nexthop_t {
struct _ffd_nexthop_t *next;
struct _ffd_neigh_t *neigh;
ffd_metric_seqno_t metric_seqno;
struct timespec last_update;
uint16_t interval;
bool requested_update;
} ffd_nexthop_t;
typedef struct _ffd_seqno_req_t {
struct _ffd_seqno_req_t *next;
struct timespec last_req;
struct _ffd_neigh_t *neigh;
uint16_t seqno;
} ffd_seqno_req_t;
typedef struct _ffd_announce_t {
struct _ffd_announce_t *next;
ffd_node_id_t node;
uint16_t type;
uint16_t key;
ffd_metric_seqno_t metric;
uint16_t last_metric;
ffd_metric_seqno_t feasibility_distance;
ffd_seqno_req_t *seqno_req_list;
ffd_nexthop_t *selected;
ffd_nexthop_t *nexthop_list;
/* an incomplete announcement is specified by a len value of 0xff with NULL data */
uint8_t len;
uint8_t *data;
} ffd_announce_t;
typedef struct _ffd_neigh_t {
struct _ffd_neigh_t *next;
unsigned ref;
struct _ffd_iface_t *iface;
eth_addr_t addr;
uint16_t hello_log;
uint16_t hello_interval;
uint16_t last_seqno;
struct timespec last_hello;
uint16_t ihu_interval;
struct timespec last_ihu;
uint16_t txcost;
} ffd_neigh_t;
typedef struct _ffd_iface_t {
struct _ffd_iface_t *next;
unsigned ifindex;
char name[IF_NAMESIZE];
eth_addr_t addr;
netif_type_t type;
uint16_t seqno;
ffd_neigh_t *neigh_list;
} ffd_iface_t;
extern const eth_addr_t ffd_addr;
extern ffd_node_id_t self;
extern ffd_iface_t *iface_list;
extern ffd_announce_t *announce_list;
extern int sockfd;
#define FFD_NODE_ID_UNSPEC ((ffd_node_id_t){})
static inline bool ffd_is_node_id_unspec(const ffd_node_id_t *node) {
const uint8_t *id = node->id;
if (id[0]||id[1]||id[2]||id[3]||id[4]||id[5]||id[6]||id[7])
return false;
else
return true;
}
static inline bool ffd_are_node_ids_equal(const ffd_node_id_t *id1, const ffd_node_id_t *id2) {
const uint8_t *a = id1->id;
const uint8_t *b = id2->id;
return (a[0]==b[0] && a[1]==b[1] && a[2]==b[2] && a[3]==b[3]
&& a[4]==b[4] && a[5]==b[5] && a[6]==b[6] && a[7]==b[7]);
}
#define FFD_IS_INFINITY(m) ((m).metric == 0xffff)
/* returns true if ms1 is better than ms2 */
static inline bool ffd_is_metric_better(ffd_metric_seqno_t ms1, ffd_metric_seqno_t ms2) {
if (FFD_IS_INFINITY(ms1))
return false;
if (FFD_IS_INFINITY(ms2))
return true;
int16_t seqno_diff = ms2.seqno - ms1.seqno;
if (seqno_diff < 0)
return true;
if (seqno_diff == 0 && ms1.metric < ms2.metric)
return true;
return false;
}
static inline bool ffd_is_feasible(const ffd_announce_t *announce, ffd_metric_seqno_t ms) {
if (FFD_IS_INFINITY(ms))
return true;
return ffd_is_metric_better(ms, announce->feasibility_distance);
}
void ffd_announce_update(ffd_announce_t *announce);
void ffd_announce_update_nexthop(ffd_announce_t *announce, ffd_nexthop_t *nexthop, ffd_metric_seqno_t ms, uint16_t interval);
ffd_announce_t* ffd_announce_new(void);
ffd_announce_t* ffd_announce_find(const ffd_node_id_t *node, uint16_t type, uint16_t key);
ffd_announce_t* ffd_announce_get(const ffd_node_id_t *node, uint16_t type, uint16_t key);
ffd_nexthop_t* ffd_announce_nexthop_find(const ffd_announce_t *announce, ffd_neigh_t *neigh);
ffd_nexthop_t* ffd_announce_nexthop_new(ffd_announce_t *announce, ffd_neigh_t *neigh);
bool ffd_announce_seqno_request(ffd_announce_t *announce, ffd_neigh_t *neigh, uint16_t seqno);
void ffd_announce_free(ffd_announce_t *announce);
void ffd_update_enqueue(const ffd_node_id_t *node, uint16_t type, uint16_t key, ffd_neigh_t *neigh, bool urgent);
int ffd_update_timeout(void);
void ffd_update_run(void);
#endif /* _FFD_FFD_H_ */
|
