CCF 202104-3 DHCP服务器
------------恢复内容开始------------
报文格式
为了便于实现，我们简化地规定 DHCP 数据报文的格式如下：
<发送主机> <接收主机> <报文类型> <过期时刻> DHCP 数据报文的各个部分由空格分隔，其各个部分的定义如下：
- 发送主机：是发送报文的主机名，主机名是由小写字母、数字组成的字符串，唯一地表示了一个主机；
- 接收主机：当有特定的接收主机时，是接收报文的主机名；当没有特定的接收主机时，为一个星号（
*）； - 报文类型：是三个大写字母，取值如下：
DIS：表示 Discover 报文；OFR：表示 Offer 报文；REQ：表示 Request 报文；ACK：表示 Ack 报文；NAK：表示 Nak 报文；
- IP 地址，是一个非负整数：
- 对于 Discover 报文，该部分在发送的时候为 0，在接收的时候忽略；
- 对于其它报文，为正整数，表示一个 IP 地址；
- 过期时刻，是一个非负整数：
- 对于 Offer、Ack 报文，是一个正整数，表示服务器授予客户端的 IP 地址的过期时刻；
- 对于 Discover、Request 报文，若为正整数，表示客户端期望服务器授予的过期时刻；
- 对于其它报文，该部分在发送的时候为 0，在接收的时候忽略。
服务器配置
为了 DHCP 服务器能够正确分配 IP 地址，DHCP 需要接受如下配置：
- 地址池大小
：表示能够分配给客户端的 IP 地址的数目，且能分配的 IP 地址是 、
- ：表示运行 DHCP 服务器的主机名。
分配策略
当客户端请求 IP 地址时，首先检查此前是否给该客户端分配过 IP 地址，且该 IP 地址在此后没有被分配给其它客户端。如果是这样的情况，则直接将 IP 地址分配给它，否则，
总是分配给它最小的尚未占用过的那个 IP 地址。如果这样的地址不存在，则分配给它最小的此时未被占用的那个 IP 地址。如果这样的地址也不存在，说明地址池已经分配完毕，因此拒绝分配地址。
实现细节
在 DHCP 启动时，首先初始化 IP 地址池，将所有地址设置状态为未分配，占用者为空，并清零过期时刻。
其中地址的状态有未分配、待分配、占用、过期四种。
处于未分配状态的 IP 地址没有占用者，而其余三种状态的 IP 地址均有一名占用者。
处于待分配和占用状态的
IP
地址拥有一个大于零的过期时刻。在到达该过期时刻时，若该地址的状态是待分配，则该地址的状态会自动变为未分配，且占用者清空，过期时刻清零；否则该地址的状态会由占用自动变为过期，且过期时刻清零。处于未分配和过期状态的
IP 地址过期时刻为零，即没有过期时刻。
对于收到的报文，设其收到的时刻为
。处理细节如下：
- 判断接收主机是否为本机，或者为
*，若不是，则判断类型是否为 Request，若不是，则不处理； - 若类型不是 Discover、Request 之一，则不处理；
- 若接收主机为
*，但类型不是 Discover，或接收主机是本机，但类型是 Discover，则不处理。
对于 Discover 报文，按照下述方法处理：
- 检查是否有占用者为发送主机的 IP 地址：
- 若有，则选取该 IP 地址；
- 若没有，则选取最小的状态为未分配的 IP 地址；
- 若没有，则选取最小的状态为过期的 IP 地址；
- 若没有，则不处理该报文，处理结束；
- 将该 IP 地址状态设置为待分配，占用者设置为发送主机；
- 若报文中过期时刻为 0 ，则设置过期时刻为
- ；否则根据报文中的过期时刻和收到报文的时刻计算过期时间，判断是否超过上下限：若没有超过，则设置过期时刻为报文中的过期时刻；否则则根据超限情况设置为允许的最早或最晚的过期时刻；
- 向发送主机发送 Offer 报文，其中，IP 地址为选定的 IP 地址，过期时刻为所设定的过期时刻。
对于 Request 报文，按照下述方法处理：
- 检查接收主机是否为本机：
- 若不是，则找到占用者为发送主机的所有 IP 地址，对于其中状态为待分配的，将其状态设置为未分配，并清空其占用者，清零其过期时刻，处理结束；
- 检查报文中的 IP 地址是否在地址池内，且其占用者为发送主机，若不是，则向发送主机发送 Nak 报文，处理结束；
- 无论该 IP 地址的状态为何，将该 IP 地址的状态设置为占用；
- 与 Discover 报文相同的方法，设置 IP 地址的过期时刻；
- 向发送主机发送 Ack 报文。
这题本身没有太大的难度，主要困难在于静下心来读题。
注意：每次处理报文时要先更新IP的状态。
1 #include2 #include 3 #include <string> 4 using namespace std; 5 int t[10010];//接收到报文的时刻 6 int N, T_def, T_max, T_min; 7 string H = "";//主机名 8 void settings() 9 { 10 char tmp; 11 12 while ((tmp = getchar()) != ' ') 13 { 14 N *= 10; 15 N += (tmp - '0'); 16 } 17 18 while ((tmp = getchar()) != ' ') 19 { 20 T_def *= 10; 21 T_def += (tmp - '0'); 22 } 23 24 while ((tmp = getchar()) != ' ') 25 { 26 T_max *= 10; 27 T_max += (tmp - '0'); 28 } 29 30 while ((tmp = getchar()) != ' ') 31 { 32 T_min *= 10; 33 T_min += (tmp - '0'); 34 } 35 36 37 while ((tmp = getchar()) != '\n') 38 { 39 //printf("%d\n", H.size()); 40 H = H + tmp; 41 } 42 } 43 44 int cnt; 45 string S_H, R_H, kind;//发送主机、接收主机、报文类型 46 int overdue_T; 47 int IP; 48 int overdue_IP[10010];//某IP地址的过期时刻 49 int state[10010];//IP状态 未分配、待分配、占用、过期————0、1、2、3 50 string occupation[10010];//IP占用者 51 52 void get_message()//接收报文 53 { 54 char tmp; 55 56 //接收时刻 57 while ((tmp = getchar()) != ' ') 58 { 59 t[cnt] *= 10; 60 t[cnt] += (tmp - '0'); 61 } 62 63 //发送主机 64 S_H = ""; 65 while ((tmp = getchar()) != ' ') 66 { 67 S_H += tmp; 68 } 69 70 //接收主机 71 R_H = ""; 72 while ((tmp = getchar()) != ' ') 73 { 74 R_H += tmp; 75 } 76 77 //报文类型 78 kind = ""; 79 while ((tmp = getchar()) != ' ') 80 { 81 kind += tmp; 82 } 83 84 //IP 85 IP = 0; 86 while ((tmp = getchar()) != ' ') 87 { 88 IP *= 10; 89 IP += (tmp - '0'); 90 } 91 92 //过期时刻 93 overdue_T = 0; 94 while ((tmp = getchar()) != '\n') 95 { 96 overdue_T *= 10; 97 overdue_T += (tmp - '0'); 98 } 99 100 //printf("%d %s %s %s %d %d\n", t[cnt], S_H.c_str(), R_H.c_str(), kind.c_str(), IP, overdue_T[cnt]); 101 } 102 103 //更新IP的状态 104 void update() 105 { 106 for (int i = 1; i <= N; i++) 107 { 108 if (state[i] == 1 && overdue_IP[i] <= t[cnt]) 109 { 110 state[i] = 0; 111 overdue_IP[i] = 0; 112 occupation[i] = ""; 113 } 114 else if (state[i] == 2 && overdue_IP[i] <= t[cnt]) 115 { 116 state[i] = 3; 117 overdue_IP[i] = 0; 118 } 119 } 120 } 121 void discover() 122 { 123 update(); 124 IP = 0; 125 int IP_0 = 0, IP_3 = 0;//最小未分配、最小过期 126 for (int i = 1; i <= N; i++) 127 { 128 if (occupation[i] == S_H) 129 { 130 IP = i; 131 break; 132 } 133 if (!IP_0 && state[i] == 0) 134 IP_0 = i; 135 if (!IP_3 && state[i] == 3) 136 IP_3 = i; 137 } 138 if (!IP) 139 { 140 if (!IP_0 && !IP_3) 141 return;//不处理该报文 142 if (IP_0) 143 IP = IP_0; 144 else 145 IP = IP_3; 146 } 147 148 state[IP] = 1; 149 occupation[IP] = S_H; 150 151 if (!overdue_T) 152 overdue_IP[IP] = t[cnt] + T_def; 153 else 154 { 155 if (overdue_T > t[cnt] + T_max) 156 overdue_IP[IP] = t[cnt] + T_max; 157 else if (overdue_T < t[cnt] + T_min) 158 overdue_IP[IP] = t[cnt] + T_min; 159 else 160 overdue_IP[IP] = overdue_T; 161 } 162 163 //向发送主机发送 Offer 报文 164 cout << H << " " << S_H << " OFR " << IP << " " << overdue_IP[IP] << endl; 165 } 166 167 void request() 168 { 169 update(); 170 if (R_H != H) 171 { 172 for (int i = 1; i <= N; i++) 173 { 174 if (occupation[i] == S_H && state[i] == 1)//找到占用者为发送主机的所有 IP 地址 175 { 176 //对于其中状态为待分配的，将其状态设置为未分配，并清空其占用者，清零其过期时刻 177 state[i] = 0; 178 occupation[i] = ""; 179 overdue_IP[i] = 0; 180 } 181 } 182 return; 183 } 184 if (IP <= N && occupation[IP] == S_H)//检查报文中的 IP 地址是否在地址池内，且其占用者为发送主机 185 { 186 state[IP] = 2; 187 188 if (!overdue_T) 189 overdue_IP[IP] = t[cnt] + T_def; 190 else 191 { 192 if (overdue_T > t[cnt] + T_max) 193 overdue_IP[IP] = t[cnt] + T_max; 194 else if (overdue_T < t[cnt] + T_min) 195 overdue_IP[IP] = t[cnt] + T_min; 196 else 197 overdue_IP[IP] = overdue_T; 198 } 199 //向发送主机发送 Ack 报文 200 cout << H << " " << S_H << " ACK " << IP << " " << overdue_IP[IP] << endl; 201 } 202 else 203 { 204 //cout << overdue_T << ' ' << overdue_IP[IP] << endl; 205 //向发送主机发送 Nak 报文 206 cout << H << " " << S_H << " NAK " << IP << " 0" << endl; 207 } 208 } 209 210 int main() 211 { 212 //printf("%s", H.c_str()); 213 int n; 214 settings(); 215 //printf("%d %d %d %d %s\n", N, T_def, T_max, T_min, H.c_str()); 216 cin >> n; 217 getchar(); 218 219 for (cnt = 1; cnt <= n; cnt ++) 220 { 221 get_message(); 222 if (R_H != H && R_H != "*" && kind != "REQ" || R_H == "*" && kind != "DIS" || R_H == H && kind == "DIS") 223 continue; 224 if (kind == "DIS") 225 discover(); 226 else if(kind == "REQ") 227 request(); 228 } 229 return 0; 230 }