精华内容
下载资源
问答
  • 文章目录题目输入输出样例1样例2样例3解答 ...第二轮,直接驱动让缓存数据包继续转发。求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包缓存包按丢弃处理) 1 <=k<=40 1 <=

    题目

    有k个节点的转发队列,每个节点转发能力为m,缓存能力n (表示此节点可立即转发m个包,剩余的缓存,最多缓存n个包,再剩余的丢弃,缓存的包在下一轮继续转发)。另外, 此队列中某些节点可能因故障需要直接跳过转发,但不会有两个连续故障的节点。

    现分两轮操作,第一轮向此队列发送a个数据包让其转发;第二轮,直接驱动让缓存的数据包继续转发。求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包,缓存包按丢弃处理)
    1 <=k<=40
    1 <= m,n<= 1000
    1 <=a<= 1000
    例如:有两个节点,节点1(转发能力m:50,缓存能力n:60)和节点2(m:30,n:25),发送包数为120,
    在没有节点故障时:

    输入

    第一行队列长度K
    第二行为k个节点转发能力数组,以空格分隔。m,n以逗号分隔,例如:
    10,20 11,21 12,22
    第三行数据包个数a
    输出

    输出

    最少收到的包个数

    样例1

    输入: 2
         50,60 30,25
         120
    输出: 55
    解释: 参见题目中的图例,当第一个节点故障时,仅第二个节点转发,此时收到的包最少。
    

    样例2

    输入: 5
         50,50 20,20 40,10 30,5 10,5
         100
    输出: 20
    解释:第一轮跳过一个节点转发20缓存20。转发的20到最后一个节点转发10缓存5。
         第二轮缓存的20转后转发的20到最后一个节点,加上此节点已经缓存的5,共25,但此节点只能转发10。
         因此最后收到包个数最少为20个。
    

    样例3

    输入: 1
         30,30
         100
    输出: 60
    解释: 第一轮经过首节点转发30缓存30,第二轮缓存的转发30,两轮总共为60。
         如果首节点故障直接跳过,则收到100, 因此最后最少值为60。
    

    解答

    典型的动态规划问题,最主要的是需要理解题目。

    在这里插入图片描述

    Python解决方案:

    k = int(input())
    nodes = input()
    nodes = [[int(i) for i in x.split(",")] for x in nodes.split(" ")]
    a = int(input())
    
    a = [a, a] # 当前节点第一轮收到的转发量, a[0]表示上一节点不发生故障, a[1]表示上一节点发生故障
    x = [0, 0] # 当前节点第一轮最小转发量
    y = [0, 0] # 当前节点第二轮最小转发量
    for node in nodes:
        temp = y[0]
    
        # 当前节点不发生故障(分上一节点不发生故障和发生故障两种情况,取两轮转发总量最小为该节点输出)
        x0 = min(a[0], node[0])
        y0 = min(min(a[0] - x0, node[1]) + y[0], node[0])
        
        x1 = min(a[1], node[0])
        y1 = min(min(a[1] - x1, node[1]) + y[1], node[0])
        
        if (x0 + y0 < x1 + y1):
            x[0], y[0] = x0, y0
        else:
            x[0], y[0] = x1, y1
    
        # 当前节点发生故障(只有上一节点不发生故障一种情况)
        x[1], y[1] = a[0], temp
        a = x.copy() #特别注意
    
    res = min(x[0]+y[0], x[1]+y[1])
    print(res)
    

    The End.

    展开全文
  • 现分两轮操作,第一轮向此队列发送a个数据包让其转发第二轮,直接驱动让缓存数据包继续转发。 求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包缓存包按丢弃处理) 1<=k<=40 1<=m,n<=...

            有k个节点的转发队列,每个节点转发能力为m,缓存能力n(表示此节点可立即转发m个包,剩余的缓存,最多缓存n个包再剩余的丢弃,缓存的包在下轮继续转发)。另外,此队列中某些节点可能因故障需要直接跳过转发,但不会有两个连续故障的节点。
    现分两轮操作,第一轮向此队列发送a个数据包让其转发第二轮,直接驱动让缓存的数据包继续转发。
            求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包,缓存包按丢弃处理)
            1<=k<=40
            1<=m,n<=1000
            1<=a<=1000
            例如:有两个节点,节点1(转发能力m:50,缓存能力n:60)和节点2(m:30,n:25),发送包数为120。

    # -*- coding: utf-8 -*-
    
    import numpy as np
    num_k = int(input("节点数k:"))
    m_n = input("节点转发数m,缓存数n:")
    m_n_list = m_n.split(' ') #各节点参数拆分
    
    m = np.zeros(num_k,dtype=np.int)
    n = np.zeros(num_k,dtype=np.int)
    for i in range(num_k):
        temp = m_n_list[i].split(',') #各节点m,n拆分
        m[i] = int(temp[0])
        n[i] = int(temp[1])
    
    tm = m.copy() #中间变量存储,必须用copy,否则则会出现同步变化的故障
    tn = n.copy()
    a = int(input("接收数:"))
    
    def f(m, n):
        # 第一轮
        rec_num1 = a; #第一轮外部接收
        send_m = np.zeros(num_k,dtype=int)
        res_n = np.zeros(num_k,dtype=int)
        for i in range(num_k):    
            if m[i] == 0: continue #故障节点直接跳过
            
            if rec_num1 > m[i]: #接收大于转发
                temp = rec_num1 - m[i] #节点剩余数
                send_m[i] = m[i] #节点发送数
                if temp > n[i]:
                    res_n[i] = n[i] #超缓存,节点缓存数
                else:
                    res_n[i] = temp #不超缓存,节点缓存数
            else: #接收小于转发
                send_m[i] = rec_num1 #节点发送数
                
            rec_num1 = send_m[i] #下节点接收数,最终节点发送数
        
        # 第二轮
        rec_num2 = 0 #第二轮外部接收
        for i in range(num_k):    
            if m[i] == 0: continue #故障节点直接跳过
        
            rec_num2 = res_n[i] + rec_num2 #缓存加接收
            if rec_num2 > m[i]: #接收大于转发
                temp = rec_num2 - m[i] #节点剩余数
                send_m[i] = m[i] #节点发送数
                if temp > n[i]:
                    res_n[i] = n[i] #超缓存,节点缓存数
                else:
                    res_n[i] = temp #不超缓存,节点缓存数
            else: #接收小于转发
                send_m[i] = rec_num2 #节点发送数
            rec_num2 = send_m[i] #下节点接收数,最终节点发送数
        
        send_total = rec_num1 + rec_num2 #两轮最后节点发送总数
        return send_total
    
    # 生成最大故障
    for i in range(num_k): #生成最大故障节点组,此时转发最少
        if i % 2 == 0: # 偶数故障
            m[i] = 0
            n[i] = 0
    min_even = f(m,n)
    m = tm.copy()
    n = tn.copy()
    for i in range(num_k): #生成最大故障节点组,此时转发最少
        if (i+1) % 2 == 0: # 奇数故障,必须加括号
            m[i] = 0
            n[i] = 0
    min_odd = f(m,n)
    if min_even > min_odd:
        print("最少收包数:",min_odd)
    else:
        print("最少收包数:",min_even)

    展开全文
  • 缓存转发数据包统计

    2021-10-19 01:48:48
    有k个节点的转发队列,每个节点...第二轮,直接驱动让缓存数据包继续转发。求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包缓存包按丢弃处理) 1 <=k<=40 1 <= m,n<= 1000 1 <=a&l

    有k个节点的转发队列,每个节点转发能力为m,缓存能力n (表示此节点可立即转发m个包,剩余的缓存,最多缓存n个包,再剩余的丢弃,缓存的包在下一轮继续转发)。另外, 此队列中某些节点可能因故障需要直接跳过转发,但不会有两个连续故障的节点。

    现分两轮操作,第一轮向此队列发送a个数据包让其转发;第二轮,直接驱动让缓存的数据包继续转发。求两轮最后可能收到的最少数据包总个数(如果第二轮缓存仍有数据包,缓存包按丢弃处理)
    1 <=k<=40
    1 <= m,n<= 1000
    1 <=a<= 1000


    输入
    第一行队列长度K
    第二行为k个节点转发能力数组,以空格分隔。m,n以逗号分隔,例如:
    10,20 11,21 12,22
    第三行数据包个数a
    输出

    输出
    最少收到的包个数

    输入: 2
         50,60 30,25
         120
    输出: 55

    输入: 5
         50,50 20,20 40,10 30,5 10,5
         100
    输出: 20

    输入: 1
         30,30
         100
    输出: 60

    int minPacks(int[] trans, int[] caches, int pks) {
            int len = trans.length;
            int[] dp = new int[len + 1]; //第一轮转发的数目
            int[] dp2 = new int[len + 1]; //第二轮转发的数目
            dp[0] = pks;
            dp2[0] = 0;
    
            dp[1] = Math.min(trans[0], dp[0]);
            dp2[1] = Math.min(trans[0], Math.min(caches[0], Math.max(0, dp[0] - trans[0])));
            for (int i = 2; i <= len; i++) {
                //i-1故障时
                dp[i] = Math.min(dp[i - 2], trans[i - 1]);
    
                if (dp[i - 2] >= trans[i - 1]) {
                    dp[i] = trans[i - 1];
                    dp2[i] = Math.min((dp2[i - 2] + Math.min(dp[i - 2] - trans[i - 1], caches[i - 1])), trans[i - 1]);
                } else {
                    dp[i] = dp[i - 2];
                    dp2[i] = Math.min(dp2[i - 2], trans[i - 1]);
                }
    
                //i-1不故障时
                if (dp[i - 1] >= trans[i - 1]) {
                    dp[i] = Math.min(dp[i], trans[i - 1]);
                    int tmp = Math.min((dp2[i - 1] + Math.min(dp[i - 1] - trans[i - 1], caches[i - 1])), trans[i - 1]);
                    dp2[i] = Math.min(dp2[i], tmp);
                } else {
                    dp[i] = Math.min(dp[i], dp[i - 1]);
                    int tmp = Math.min(dp2[i - 1], trans[i - 1]);
                    dp2[i] = Math.min(dp2[i], tmp);
                }
    
            }
            int res = dp[len] + dp2[len];
            return res;
        }

    public static void main(String[] args) {
            DataPackProblem dp = new DataPackProblem();
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNext()) {
    
                int k = scanner.nextInt();
                int[] dt1 = new int[k];
                int[] dt2 = new int[k];
                scanner.nextLine();
                String data = scanner.nextLine();
                String[] sAry = data.split(" ");
                for (int i = 0; i < sAry.length; i++) {
                    String str = sAry[i];
                    String[] splits = str.split(",");
                    dt1[i] = Integer.parseInt(splits[0]);
                    dt2[i] = Integer.parseInt(splits[1]);
                }
                int pks = scanner.nextInt();
                dp.minPacks(dt1, dt2, pks);
            }
    
        }

    展开全文
  • 求两轮最后可能收到的最少数据包个数(第二轮的缓存被忽略)。 思路类似于打家劫舍;有两点需要注意: 1 不可能有连续两个节点是坏的,就是不能偷两家; 2 两次转发可以看出一次,即节点的发送量等于输出量+缓存量...

    有K个节点的转发队列,每个节点的转发能力为m,缓存能力为n,输入大于m+n时剩余包被丢弃。此队列中某些节点因故障需要直接跳过转发,但不会有两个连续故障的节点。

    现分两轮操作,第一轮发送a个数据进行转发;第二轮转发每个节点的缓存数据。

    求两轮最后可能收到的最少数据包个数(第二轮的缓存被忽略)。

    思路类似于打家劫舍;有两点需要注意:

    1 不可能有连续两个节点是坏的,就是不能偷两家;

    2 两次转发可以看出一次,即节点的发送量等于输出量+缓存量。

    可以推知:如定义dp[i] 为当前节点的最小输出量,则dp[i] = min( min(dp[i-2],out[i]),dp[i-i])。

    out[I] 为当前节点的发送量。上述公式中,前部分代表选择当前点,后部分代表不选当前点。

    仅代表自身的思路,如有问题,欢迎指正,万分感谢。

    #include<iostream>
    #include<vector>
    
    using namespace std;
    
    int main() {
    	int num;
    	while(cin>>num)
    	{
    		vector<int> out;
    		while (num--) {
    			int a = 0, b = 0;
    			char m = ',';
    			cin >> a>>m>>b;
    			out.push_back(a + b);
    		}
    		int pre;
    		cin >> pre;
    		int cur = out[0];
    		for (int i = 1; i < out.size(); i++) {
    			int temp = pre;
    			pre = cur;
    			cur = min(cur, min(temp, out[i]));
    		}
    		cout << cur << endl;
    	}
    	return 0;
    }

    展开全文
  • 运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),...
  • cacheVisit cv=new cacheVisit(); cv.sysno=sysno; cv.reurl=reurl; cv.ip=GetIpV4AndV6(); cv.moduleclass=moduleclass; ...
  • 套接口发送缓存长度统计sk_wmem_queued,记录了当前套接口的发送队列与重传队列所占用空间的大小值。套接口创建时,发送与重传缓存都为空,将其值初始化为0。 struct sock *sk_clone_lock(const struct sock *sk, ...
  • 1、定义要抓取的内容acl 2000rule permit source 36.111.130.192 0.0.0.31可按实际数据包流向增加acl rule2、定义类traffic classifier testif-match acl 20003、定义行为traffic behavior testpermitstatistic ...
  • 本人参加华为笔试,时间两个小时没来得及调试,结束后总结了本次的题目并给出了可行性的python代码,此为华为真题,一共三道题,目前给出出两题的代码。希望对于进华为的小伙伴有帮助。
  • 华为笔试题专辑(含答案),包括研发类、软件、通信等
  • 1.查找路由,决定对报文进行本地接收还是转发,赋值skb_dst()->input(),发往本地为ip_local_deliver,转发为ip_forward()。 2.对IP的选项进行处理 //linux/net/ipv4/ip_input.c static int ip_rcv_finish...
  • ip flow-export 将NETFLOW审计的数据包转发到指定设备.   5 Cisco Express Forwarding   思科CEF是最为高效的一种三层协议,很多人容易对CEF产生误解,所以我们仍然要说明它的来原.   CEF采用了基于...
  • 面试专题:Linux运维精华面试题

    千次阅读 多人点赞 2019-03-14 15:31:53
    Nginx: 是WEB服务器,缓存服务器,又是反向代理服务器,可以做七层的转发 区别: LVS由于是基于四层的转发所以只能做端口的转发 而基于URL的、基于目录的这种转发LVS就做不了 工作选择: HAproxy和Nginx由于...
  • Tomcat面试题+http面试题+Nginx面试题+常见面试题

    千次阅读 多人点赞 2019-12-12 15:04:43
    LVS: 是基于四层的转发 HAproxy: 是基于四层和七层的转发,是专业的代理服务器 Nginx: 是WEB服务器,缓存服务器,又是反向代理服务器,可以做七层的转发 区别: LVS由于是基于四层的转发所以只能做端口的转发 而...
  • Linux运维面试题

    千次阅读 2019-08-02 12:57:30
    Nginx: 是WEB服务器,缓存服务器,又是反向代理服务器,可以做七层的转发 区别: LVS由于是基于四层的转发所以只能做端口的转发 而基于URL的、基于目录的这种转发LVS就做不了 工作选择: HAproxy和Nginx由于...
  • 无线传感器网络复习大纲

    千次阅读 多人点赞 2019-04-30 10:31:40
    ①、计算能力不高:无线传感器节点分布非常密集,大量节点决定了每个节点的成本不高,在限定的成本下采用的处理器处理速度就比较低,只能处理相对简单的数据,并且节点的队列缓存存储长度也非常有限,不适用于特别...
  • 华为秋招机试三道编程题(2021-09-01)

    千次阅读 多人点赞 2021-09-01 23:39:02
    文章目录第一道:缓存转发数据包统计(100%)题目描述参考代码:第二道: 查找知识图谱中的实例知识(100%)题目描述参考代码第三道:湖泊连通(100%)题目描述参考代码 第一道:缓存转发数据包统计(100%) 题目...
  • Linux实用教程(第三版)

    万次阅读 多人点赞 2019-08-27 22:55:59
    在存储和文件系统方面,RHEL 7使用LIO内核目标子系统,支持快速设备为较慢的块设备提供缓存,引进了LVM缓存,将xfs作为默认的文件系统。 引进网络分组技术作为链路聚集的捆绑备用方法,对NetworkManager进行大量...
  • 再谈数据包排队(二进制和半导体)

    千次阅读 2019-05-26 07:09:18
    数据包怎么排队?从存储转发网络看芯片: https://blog.csdn.net/dog250/article/details/90542988 时间仓促,今天继续。 共享介质以太网是分布式仲裁的网络,执行的CSMA/CD说白了就是为了达成某种共识而运行的一种...
  • 首先,我觉得BBR统计最小RTT的方式在移动网络要有所改变,这是最必要的,其次,计算cwnd的算法必须要有所改变,不能仅仅是乘以2,因为ACK聚合会导致空窗期,这个已经在BBRv2里解决了,甚好。 接下来,我也不知道会...
  • Linux转发性能评估与优化(转发瓶颈分析与解决方案)

    万次阅读 多人点赞 2015-06-28 00:22:26
    数据包进入路由器或者交换机,存在一个核心延迟操作,这就是选路,对于路由器而言,就是路由查找,对于交换机而言,就是查询MAC/端口映射表,这个延迟是无法避开的,这个操作需要大量的计算机资源,所以不管是路由器...
  • IPv4之接收数据包流程

    千次阅读 2018-10-19 01:23:34
    输入接口定义 /* * IP protocol layer initialiser ... //IP层的数据包类型为ETH_P_IP,当设备接口层收到该类型的数据包,就会递交给IP层处理 .type = __constant_htons(ETH_P_IP), //设备接口层通过调用ip_r...
  • 上周在一次偶然的谈话中,我无意中听到一位同事说:Linux的网络堆栈太慢了!你不能指望它在每个核每秒处理超过5万个数据包!这引起了我的思考。虽然我同意每个核50kpps可能是任何实际应用...
  • dpdk接收数据包原理分析

    万次阅读 2018-08-19 21:24:48
    dpdk接收数据包原理分析 摘要 本文对dpdk数据包捕获技术原理进行了分析,对其优缺点进行了介绍。 对使用基于EAL的应用程序进行了分析,作出了程序流程图。 引言 背景浅析 随着云计算产业的异军突起,网络...
  • ARP原理与IP数据包

    2020-03-06 18:13:53
    IP数据包格式 ICMP协议介绍 ARP攻击原理 1.网络层功能 定义了基于IP协议的逻辑地址 连接不同的媒介类型 选择数据通过网络的最佳路径 2.ICMP协议(Internet 控制消息协议) ICMP协议是一个"错误侦测与回馈机制" 通过IP...
  • Linux内核网络UDP数据包发送系列:Linux内核网络UDP数据包发送(一)Linux内核网络UDP数据包发送(二)——UDP协议层分析Linux内核网络UDP数据包发送(三)——IP...
  • XDP-内核可编程数据包处理方案

    千次阅读 2020-10-29 10:58:12
    高速数据包处理的挑战 XDP设计 性能评估 XDP应用 总结 高速数据包处理的挑战 高速数据包处理 How to drop 10 million packets per second 解决方案 kernel bypass: DPDK, 完全绕过内核协议栈,由专门的网络应用...
  • Linux flow offload提高路由转发效率

    万次阅读 2019-12-07 08:38:52
    凡是正确的东西,该来的最终还是会来的。 (当然了,经理可能也有同感。) 来看看几年前我写的文章: ...在Linux的连接跟踪(nf_conntrack)中缓存私有数据省去每次查找: https://blog.csdn.net/dog...
  • 运维面试笔试题

    千次阅读 2019-09-25 10:36:27
    2.统计ip访问情况,要求分析nginx访问日志,找出访问页面数量在前十位的ip cat access.log|awk’{print$1}’|uniq -c|sort -rn|head -10 3.使用tcpdump监听主机为192.168.1.1,tcp端口为80的数据,同时将输出结果...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,567
精华内容 3,826
关键字:

缓存转发数据包统计