热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

IP组播协议

组播协议概述组播基本架构IGMPIGMPv1的工作机制IGMPv2的工作机制IGMPv3的工作机制总结各版本的差异组播IP地址组播MAC地址组播配置IGMPSnooping的工作机

组播协议

  • 概述
  • 组播基本架构
  • IGMP
    • IGMPv1的工作机制
    • IGMPv2的工作机制
    • IGMPv3的工作机制
    • 总结各版本的差异
  • 组播IP地址
  • 组播MAC地址
  • 组播配置
  • IGMP Snooping的工作机制
    • 补充:二层转发数据帧的原理
  • 案例配置
  • 思考题
  • PIM
    • PIM-DM
    • PIM-SM
      • RPT建立过程
      • SPT的建立过程
  • SSM + C-BSR C-RP 实验
  • 组播综合实验



前言:

若采用单播方式,网络中传输的信息量域需要改信息的用户量成正比。多份内容相同的信息发送给不同用户,对信源及网络带宽都将造成巨大压力。若采用广播方式,无需接收信息的主机也将收到该信息,这样不仅信息安全得不到保障,且会造成同一网段中信息泛滥。

单播方式所存在的问题:重复流量过多、消耗设备和链路带宽资源、难以保证传输质量
广播方式所存在的问题:地域范围限制、安全性无法保障、有偿性无法保障
组播方式的优势:无重复流量、节省设备与带宽资源、安全性高、有偿性有保障
 

概述

IP组播技术有效地解决了单播和广播在点到多点应用中的问题。组播源只发送一份数据,数据在网络节点间被复制、分发(PIM),且只发送给需要该信息的接收者。

单播(Unicast)是在一台源 IP 主机和一台目的 IP 主机之间进行。
广播(Broadcast)是在一台源 IP 主机和网络中所有其它的 IP 主机之间进行
组播(Multicast)是在一台源 IP 主机和多台(一组)IP 主机之间进行,中间的
交换机和路由器根据接收者的需要,有选择性地对数据进行复制和转发。

组播基本架构

组播源到路由器:组播源生成组播数据,完成数据封装并发送给网关路由器。
路由器到路由器:路由器根据接收者的分布情况有选择地对数据进行复制和转发。
路由器到接收端:路由器收到组播数据并发送给相应的接收者。

PIM是路由器和路由器。 IGMP是PC和路由器
在这里插入图片描述
IP组播常见模型
ASM 全称为 Any-Source Multicast,译为任意源组播 。SSM 全称为 Source-Specific Multicast,译为指定源组播。

IGMP

IGMP(Internet Group Management Protocol,因特网组管理协议) ,是TCP/IP协议簇中负责IP组播成员管理的协议,它用来在接收者和与其直接相邻的组播路由器之间建立、维护组播组成员关系。

IGMP协议运行于主机与组播路由器之间。
IGMP协议的作用:
主机侧:通过IGMP协议向路由器通告组成员关系
路由器侧:通过IGMP协议维护组成员关系

IGMP 有 3 个版本,分别 是 IGMPv1、IGMPv2、IGMPv3.

IGMPv1 主要基于查询和响应机制来完成组播组的管理。主机通过发送 report 消息加入到某组播组,主机离开组播时不发送离开报文,离开后再收到路由器发送的查询消息时不反馈 report 消息,待维护组成员关系的定时器超时后,路由器会自动删除该主机的成员记录。

IGMPv2 与 IGMPv1 基本相似,主机的不同点在于 IGMPv2 具有某些报文 抑制机制,可以减少不必要的 IGMP 重复报文,从而节省网络带宽资源,另外,
主机离开组播组时,会主动向路由器发送离开报文。

IGMPv1 和 IGMPv2 报文中都只能携带组播组的信息,不能携带组播源的信息, 所以主机只能选择加入某个组,而不能选择组播源,这一问题在 IGMPv3 中得 到了解决。运行 IGMPv3 时,主机不仅能够选择组,还能根据选择组播源。主 机发送的 IGMPv3 报文中可以包含多个组记录,每个组记录中可以包含多个
组播源。

熟悉点到多点应用的特点
传统点到点:服务提供端以单个用户为单位提供服务。
不同用户与服务供端的通信数据存在差异。

新型点到多点:服务提供端以一组用户为单位提供服务
同组用户与服务提供端的通信数据无差异

IGMPv1的工作机制

(通用组查询 224.0.0.1,即使G2没有接收者 也会源源不断发 Query)
在这里插入图片描述 
Graft嫁接报文,相当于插班生
在这里插入图片描述 
IGMPv1组成员离开 —— 静默离开
60*2(健壮系数)+10(最大响应时间) = 130s
在这里插入图片描述

IGMPv1的查询器选举
在这里插入图片描述先看优先级,默认是1. 再看IP地址,谁大

IGMPv2的工作机制

IGMPv1缺点:
130s有点长,而且不发送leave报文。
IGMPv1没有独立的查询机制,要依附于组播协议

IGMPv2对IGMPv1的改进:组成员离开
特定组即 组播地址是什么,特定组就是什么 例如224.1.1.1
224.0.0.2 网段中所有路由器

如果组播组G2不存在成员,则会在 下游接口剪掉
在这里插入图片描述 

IGMPv2对IGMPv1的改进:查询器选举 IP地址最小的获胜
在这里插入图片描述

IGMPv3的工作机制

IGMPv1和v2是任意源,不关心是哪个源 ASM
IGMPv3关心源,特点组播源 SSM (研发部只能看学习视频)。只支持sm模式,直接可以携带多个组播源
在这里插入图片描述

总结各版本的差异

在这里插入图片描述查询器选举:IP地址大,IP地址小,IP地址小
成员离开:130秒,两次离开报文,两次离开报文

五元组(源IP,源MAC,目的IP,目的MAC,协议号)

 

组播IP地址

一个组播IP地址并不是表示具体的某台机主机,而是一组主机的集合,主机声明加入某组播即标识自己需要接收目的地址为该组播地址的数据。

224.0.0.1 地址(表示同一网段内所有主机和路由器)
224.0.0.2 地址(本地网段内的所有组播路由器)
224.0.0.13 地址( PIM 路由器)
在这里插入图片描述

组播源无法判断具体接收者的网络位置在哪,接受者自己根据组播源距离知道的


组播MAC地址

组播MAC地址与单播MAC地址的区别:
XXXX XXX1 组播MAC地址,第一个字节的最后一位为1
XXXX XXX0 单播MAC地址,第一个字节的最后一位为0

组播IP与 MAC的映射
需要组播IP地址与组播MAC地址的自动映射
1110 XXX.X ——》01-00-5E

在这里插入图片描述
在这里插入图片描述

组播IP的前9位(其中的5位不是固定的),对应组播MAC的25位,会造成2的5次方个地址 映射成一个MAC地址
IANA规定:IPV4组播MAC地址的高24位为0x01005e,第25位固定为0

 

组播配置

(配置之前先安装VLC media player)
第一步:配置组播源
在这里插入图片描述

IGMP Snooping的工作机制

组播数据在二层(交换机)会被泛洪,造成:网络资源浪费、存在安全隐患
二层交换的特性:转发、泛洪、丢弃

补充:二层转发数据帧的原理

第一步: 交换机收到了数据帧,先会存入交换机的缓存并检查数据帧是否完整,CRC的校验是否正确。
如果是BPDU(桥协议数据单元),则交给CPU处理;如果缓存存满则丢弃数据帧
丢弃数据帧有以下4种情况:缓存存满CRC校验错误过小,小于64字节过长,大于1518字节第二步: 根据vlan进入规则,判断是否丢弃如果数据帧有TAG头,但是该端口不接受此VLAN,丢弃如果有有TAG头,该端口接收次VLAN,进入下一个流程如果没有TAG头,打上该端口的缺省PVID,进入下一个流程 第三步:学习MAC地址 —— 数据帧的源端口和源MAC地址
交换机中有一张名为MAC地址表的表,当交换机收到一个数据帧后,他会首先记录这个数据帧的源端口和源MAC地址的映射。 (目的的话都不是自己连接的。乱套了)
如果这个MAC地址表已经存在这个映射项,则更新这个映像的老化时间,如果没有,则保存这个映射项。
然后判断这个数据帧属于广播还是单播,如果是广播帧则向所有端口(除了接收该数据帧的端口)转发数据帧;如果是单播帧则查找MAC地址表,根据MAC地址表中存在对应映射项进行数据转发,如果没有,交换机就会广播这个数据帧,有对应接收者回消息时,它便会记住对应的MAC地址与端口的映射,以便下次的转发。·广播地址不能作为源出现,能作为源地址的只能是单播地址第四步: 数据帧进入主交换引擎,根据VLAN Table表把数据帧发送到属于相应VLAN的端口(VLAN Table表,记录VID和它的端口成员).第五步:交换机在该VLAN内的所有端口查找目的MAC地址,查找到了就发送到相应的端口,查不到就发送到所有端口;
如果配置了组播的话,就要看看有没有IGMP Snooping,如果开启了这个功能就会把组播数据发送到对应端口,如果没有就发送到所有端口;第六步:到达对应端口之后,交换机对数据帧进行出规则管处理,带不带Tag出去
access端口:将VLAN的信息剥离,发出去
trunk端口:比较PVID和将要发送的VLAN信息,如果两者相等则剥离VLAN信息在发送;如果不想等则直接发送。
Hybrid端口:判断该VLAN在本端口的属性(看该端口对那些VLAN是Untag,那些VLAN是Tag)。如果是Untag则剥离Vlan信息在发送,如果是Tag则直接发送补充:
PVID(port-base vlan ID):端口的虚拟局域网ID号,关系到端口收发数据帧时候的VLAN TAG标记。

在这里插入图片描述

案例配置

两个组播服务器 组播源地址都是224.1.1.1
source-1存放一些娱乐视频,source-2存放一些学习视频。
情况1:人事部只想看娱乐,且不在意带宽资源问题,所以在PC-1上配置的是IGMPv1
情况2:市场部希望尽量节约带宽资源,所以需要在PC-2上配置IGMPv2
情况3:研发部不允许观看娱乐视频,所以需要在PC-3上配置IGMPv3
…后期补充

 

思考题

思考题:
①IGMPv1,当最后一个组播成员离开该组后,组播路由器将在多长时间删除所对应的组播转发表项? 130秒 60*2+10
②IGMPv2中,特定组查询的目的IP是224.0.0.1吗?不是,普遍组查询才是224.0.0.1
③IGMP Snooping的实现原理是什么?交换机侦听,通过路由器和PC之间查询和应答报文的交互 来识别哪些接口有组成员,交换机根据该对应关系将收到组播数据包只转给具有组成员的接口。如果没有组成员,就不发送。

 

PIM

前言:如果像单播路由一样通过多种路由算法动态生成组播路由,会带来不同路由协议间互相引入时操作繁琐的问题。
PIM: Protocol Independent Multicast 协议无关组播。目前常用版本是PIMv2,PIM 报文直接封装在 IP 报文中,协议号为 103,PIMv2 组播地址为224.0.0.13。

PIM直接利用单播路由表的路由信息进行组播报文RPF检查,创建组播路由表项,转发组播报文。

RPF(反向路径查找):路由器收到组播数据报文后,只有确认这个数据报文是从自己到组播源的出接口上到来的,才会进行转发,否则丢弃报文
RPF检查:
入接口有且只有一个。多个入接口会进行RPF check RPF check,路由器四个接口,有三个接口都是进来的话,会进行RPF check,回去找最佳路径。


如果该路由的出接口就是组播报文的入接口,RPF成功。 否则RPF失败,报文丢弃

组播分发树是指从组播源到接收者之间形成的一个单向无环数据传输路径。组播分发树有两类:SPT 和 RPT

发送Hello的组播地址:224.0.0.13
Hello时间:30秒
Hold time时间:105秒
DR优先级默认为1。 如果优先级一样,IP地址大的为DR

 

PIM-DM

( Protocol Independent Multicast Dense Mode)

PIM-DM :采用“推(Push)模式”转发组播报文。
PIM-DM的关键任务:建立SPT 最短路径树

PIM-DM 假设网络中的组成员分布非常稠密,每个网段都可能存在组成员。
缺点:在组播成员分布较为稀疏的网络中,组播流量的周期性扩散会给网络带来较大负担。

PIM-DM的工作机制:邻居发现,扩散与剪枝,状态刷新,嫁接,断言
首先将组播数据报文扩散到各个网段。然后再裁剪掉不存在组成员的网段。
通过周期性的“扩散—剪枝”,构建并维护一棵连接组播源和组成员的单向无环SPT。

邻居发现:
在 PIM-DM 网络中,路由器周期性发送 Hello 消息来发现、建立并维护邻居关系。
发送Hello的组播地址:224.0.0.13
Hello消息默认周期:30秒
Hold time时间:105秒
DR优先级默认为1。 如果优先级一样,IP地址大的为DR
int g0/0/1
pim hello-option dr-priority 配置优先级
pim timer hello interval 在接口视图下配置发送 Hello 消息的时间间隔
pim hello-option holdtime interval,在接口视图下配置 Hello 消息超时时间值。默认情况超时时间值为 105 秒

在这里插入图片描述
 
扩散与剪枝:
会生成一个 (S,G)表
组播数据的转发中会出现上游接口和下游接口这两个概念,路由器收到组播数据的接口称为上游接口,转发组播数据的接口称为下游接口

  • 有源树 SPT,路径最优,延迟最小
    (S,G)
    S表示组播源,G表示组播组, * 表示任意。

PIM-DM 也会选举DR,但是这个DR不起作用
只认SPT 有源树
在这里插入图片描述 

状态刷新
周期性地刷新剪枝状态 60秒
在这里插入图片描述 
Graft机制
不等待周期刷新,主动加入(插班生)。为了新的组成员加入组播组后,快速得到组播报文
在这里插入图片描述 
Assert机制
在多台路由器中选出唯一的转发者,根据Assert机制选。
到组播源的单播路由协议优先级较小者获胜。
如果优先级相同,则到组播源的路由协议开销较小者获胜。
如果以上都相同,则连接到接受者 MA 网络接口 IP 地址最大者获胜。
在这里插入图片描述
在这里插入图片描述 
PIM-DM 配置实现

配置命令:
multicast routing-enable
int g0/0/0
pim dm如果路由器是连接PC的,还要配置igmp enable
int g0/0/1pim dmigmp enabledis pim neighbor
dis pim routing-table 可以看到 (S,G)和上游接口,下游接口
dis pim interface

在这里插入图片描述

 
 

PIM-SM

PIM-SM :使用“拉(Pull)模式”转发组播报文。 (告诉大家感兴趣你就来领取,客户端主动来)

PIM-SM 假设网络中的组成员分布非常稀疏,几乎所有网段均不存在组成员,直到某网段出现组成员时,才构建组播路由,向该网段转发组播数据。一般应用于组播组成员规模相对较大、相对稀疏的网络。

PIM-SM的关键任务:建立RPT(汇聚点树也称共享树)、建立SPT(最短路径树)

PIM-SM 的关键机制:邻居建立、DR 竞选、RP 发现、RPT 构建、组播源注册、SPT 切换、Assert

汇聚点 RP(Rendezvous Point)
RP 的作用:
RP 是 PIM-SM 域中的核心路由器,担当 RPT 树根节点。
共享树里所有组播流量都要经过 RP 转发给接收者。
所有PIM路由器都要知道RP的位置

运行 PIM-SM 的网络,都会进行 DR(Designated Router)的选举。其中有两种 DR 分别称为接收者侧 DR 和组播源侧 DR。
组播接收者侧 DR:与组播组成员相连的 DR,负责向 RP 发送(*,G)的 Join加入消息。
组播源侧 DR:与组播源相连的 DR,负责向 RP 发送单播的 Register 消息。

RPT建立过程


  • 当用户端通过IGMP加入某组播组G时,发送IGMP成员通告,用户端DR(最后一跳路由器) 向RP 发送Join报文,逐跳创建(*,G)表项,建立以RP为根的共享树RPT,

在这里插入图片描述思考: 不会发送,因为会选举DR

在这里插入图片描述Register和Graft都是单播报文。

  • 运行 PIM-SM 的网络,都会进行 DR(Designated Router)的选举。其中有两种 DR 分别称为接收者侧 DR 和组播源侧 DR。
    组播接收者侧 DR:与组播组成员相连的 DR,负责向 RP 发送(*,G)的 Join加入消息。
    组播源侧 DR:与组播源相连的 DR,负责向 RP 发送单播的 Register 消息。
    PIM-SM协议中,与组播接受者相连的DR负责向RP发送join消息。
    源端DR发送Register消息

     

SPT的建立过程

在共享树中,第一跳是用PIM-DM方式发的

  • 当网络中出现活跃的组播源(组播源向组播组发送第一个组播报文),源DR发送注册单播报文(告诉RP,源活跃了),RP收到 注册单播报文(提取组播报文),将该组播报文沿RPT分支给接收者。
    另一方面,RP向源端DR发送(S ,G)join消息,沿途路由器上会生成相应的(S,G)表项,建立由组播源至RP的有源树SPT。

在这里插入图片描述
在这里插入图片描述

Switchover机制
RPT树会存在非最优路径,于是就有了Switchover机制
在这里插入图片描述

PIM-SM 配置
在这里插入图片描述dis pim routing-table
dis pim neighborr

综合实验:
在这里插入图片描述
环回口比物理口稳定,物理口down了就down了。
在这里插入图片描述在这里插入图片描述

RP详解
RP 有两种形式:静态 RP 和动态 RP。
静态 RP 是由人工选定的,PIM 网络中的所有 PIM 路由器上都需要逐一进行配置。通过配置,每台路由便知道了静态 RP 的地址。

动态 RP 的确定过程相对比较复杂一些,在 PIM 网络中人工选定并配置若干台PIM 路由器,使得它们成为 C-RP( Candidate-RP ),RP 将从 C-RP 中选举产生。如果 C-RP 只有一个,则 RP 就是这个 C-RP。如果有多个 C-RP ,则优先级最高者(优先级数值越小优先级超高,缺省值是 0)将会被选举为 RP,如果通过优先级比较无法选举出 RP,则依靠 Hash 算法算出的数值来决定 RP,数值最大者将成为 RP(Hash 算法参数:组地址、掩码长度、C-RP 地址),如果通过 Hash 数值也无法确定出 RP ,则拥有最高 IP 地址的 C-RP 将成为RP 。

选定和配置 C-RP 时,还必须同时选定和配置 C-BSR (Candidate-BootStrap Router),并由 C-BSR 选举产生出一个 BSR。如果有多个 C-BSR,则拥有最高IP 地址的 C-BSR 将成为 BSR。BSR 是 PIM-SM 网络的管理核心,它负责收集网络中 C-RP 发出的 Advertisement 宣告 信息,并计算出与每个组播组对应的 RP ,然后将 RP 的信息发布到整个 PIM-SM 网络中。BSR 动态映射组播组与 RP 的关系

静态 RP
pim
static-rp 11.11.11.11

动态 RP
int LoopBack 0
pim sm
pim
c-rp LoopBack 0

BSR配置
pim
c-bsr LoopBack 0

SSM + C-BSR C-RP 实验

SSM地址(保留给SSM使用的):232.0.0.0/8
SSM是一种在IGMPv3协议支持的情况下,能够在用户侧IGMP接口上指定组播源的传输服务。但有时组播组成员主机却只能运行IGMPv1或IGMPv2,这时就可以通过在交换机上配置SSM Mapping功能,向运行IGMPv1或IGMPv2的组成员提供SSM服务。

在这里插入图片描述在这里插入图片描述

配置命令:所有路由器都要这样配置,对应具体的接口
multicast routing-enable
int g0/0/xpim sm路由器连接用户侧的接口
连接用户侧的:
int g0/0/1pim smigmp enabledis pim routing-table
dis pim neighbor

有了源的信息 不需要汇聚点RP,不需要建立共享树

源信息和组地址 对应。为了让他知道IGMPV3有什么内容

R1,R2,R3,R4:
igmpssm-mapping 239.0.0.1 32 192.168.1.1

dis igmp ssm-mapping group 239.0.0.1 看组和源地址的对应关系
在这里插入图片描述
只有最后一跳连接用户的路由器的接口才要配置
连接用户侧:

int g0/0/1igmp version 3igmp ssm-mapping enable

dis igmp ssm-mapping int g0/0/1
在这里插入图片描述
dis pim routing-table
在这里插入图片描述
RP为NULL,因为已经有源了,不需要有RP

组播综合实验

在这里插入图片描述
实验需求:

  1. 域内有两台组播源服务器:
    MCS1使用组播地址:239.0.0.1/8
    MCS2使用特定源组播地址 232.0.0.1/8
  2. 域内使用OSPF路由协议,全网通讯正常
  3. PC1和PC3接收239.0.0.1组播流
  4. PC2和PC4接收特定源组播流
  5. AR1是RP,使用静态RP技术通告全网。

全网OSPF。直接区域0,通告,测试全网连通性。这里主要就是要看组播实验的

踩过的坑:注意要点击目的MAC那一栏哦,不然全0是通不了的
PC的组播项和组播源都需要自己去点击
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

注意连接用户侧的要配置 igmp enable配置所有接口包括loopback 0接口并pim sm后
multicast routing-enable
int g0/0/x loopback 0
pim sm所有路由器(通告全网,万一PC2突然要接受MCS1的呢。。。。。看个人)
都要配置有static-RP: R2也要配,做冗余
acl 2000
rule 5 permit source 239.0.0.0 0.255.255.255
#
multicast routing-enable
pim
static-rp 1.1.1.1 2000

特定源 只有最后一跳连接用户的路由器的接口才要配置
连接用户侧的MCS2

int g0/0/1igmp version 3igmp ssm-mapping enable

源信息和组地址 对应。为了让他知道IGMPV3有什么内容
R2\R4\R6 所有经过特定源的路由器都要配置

igmpssm-mapping 232.0.0.1 8 192.168.2.1

验证:
dis pim rp-info
dis pim routing-table
dis pim neighbor
dis igmp ssm-mapping group 232.0.0.1
dis igmp ssm-mapping interface

冗余 R1怎么配的,R2就再配一个一样的,反之。 互相冗余
R2 做R1的冗余

acl 2000
rule 5 permit source 239.0.0.0 0.255.255.255
#
multicast routing-enable
pim
static-rp 1.1.1.1 2000

R1 做R2的冗余

igmpssm-mapping 232.0.0.1 8 192.168.2.1

抓包验证(路由器的用户侧g0/0/1):
在这里插入图片描述


推荐阅读
  • 在多线程并发环境中,普通变量的操作往往是线程不安全的。本文通过一个简单的例子,展示了如何使用 AtomicInteger 类及其核心的 CAS 无锁算法来保证线程安全。 ... [详细]
  • 这篇文章 | 夕阳下的防火墙命令全解 ... [详细]
  • H3C防火墙自动构建安全隧道
    实验拓扑结构:两端采用静态IP地址配置。H3C防火墙能够自动构建IPSec安全隧道,确保数据传输的安全性。通过配置防火墙的非信任区域,实现自动化安全连接的建立与维护,有效提升网络防护能力。 ... [详细]
  • 近期在研究逆向工程,因此尝试了一些CTF题目。通过合天网络安全实验室的CTF实战演练平台(http://www.hetianlab.com/CTFrace.html),我对Linux逆向工程的掌握还不够深入,因此暂时跳过了RE300题目。首先从逆向100开始,将文件后缀名修改为.apk进行初步分析。这一过程不仅帮助我熟悉了基本的逆向技巧,还加深了对Android应用结构的理解。 ... [详细]
  • 优化后的标题:Apache Cassandra数据写入操作详解
    本文详细解析了 Apache Cassandra 中的数据写入操作,重点介绍了 INSERT 命令的使用方法。该命令主要用于将数据插入到指定表的列中,其基本语法为 `INSERT INTO 表名 (列1, 列2, ...) VALUES (值1, 值2, ...)`。通过具体的示例和应用场景,文章深入探讨了如何高效地执行数据写入操作,以提升系统的性能和可靠性。 ... [详细]
  • 深入解析CAS机制:全面替代传统锁的底层原理与应用
    本文深入探讨了CAS(Compare-and-Swap)机制,分析了其作为传统锁的替代方案在并发控制中的优势与原理。CAS通过原子操作确保数据的一致性,避免了传统锁带来的性能瓶颈和死锁问题。文章详细解析了CAS的工作机制,并结合实际应用场景,展示了其在高并发环境下的高效性和可靠性。 ... [详细]
  • POJ 2482 星空中的星星:利用线段树与扫描线算法解决
    在《POJ 2482 星空中的星星》问题中,通过运用线段树和扫描线算法,可以高效地解决星星在窗口内的计数问题。该方法不仅能够快速处理大规模数据,还能确保时间复杂度的最优性,适用于各种复杂的星空模拟场景。 ... [详细]
  • 在探讨P1923问题时,我们发现手写的快速排序在最后两个测试用例中出现了超时现象,这在意料之中,因为该题目实际上要求的是时间复杂度为O(n)的算法。进一步研究题解后,发现有选手使用STL中的`nth_element`函数成功通过了所有测试点。本文将详细分析这一现象,并提出相应的优化策略。 ... [详细]
  • 链栈虽然通常以数组作为底层实现,但也可以采用链表来构建Stack类。在这种情况下,空堆栈通过NULL指针表示。当新元素被压入堆栈时,它会被添加到链表的头部,从而实现高效的入栈操作。此外,出栈操作则通过移除链表头部的节点来完成,确保了操作的时间复杂度为O(1)。这种设计不仅简化了内存管理,还提高了动态数据处理的灵活性。 ... [详细]
  • 在洛谷 P1344 的坏牛奶追踪问题中,第一问要求计算最小割,而第二问则需要找到割边数量最少的最小割。通过为每条边附加一个单位权值,可以在求解最小割时优先选择边数较少的方案,从而同时解决两个问题。这种策略不仅简化了问题的求解过程,还确保了结果的最优性。 ... [详细]
  • 本文探讨了利用JavaScript实现集合的对称差集算法的方法。该算法旨在处理多个数组作为输入参数,同时保留每个数组中元素的原始顺序。算法不会移除单个数组内的重复元素,但会删除在不同数组之间出现的重复项。通过这种方式,能够有效地计算出多个数组的对称差集。 ... [详细]
  • 本文深入解析了Java 8并发编程中的`AtomicInteger`类,详细探讨了其源码实现和应用场景。`AtomicInteger`通过硬件级别的原子操作,确保了整型变量在多线程环境下的安全性和高效性,避免了传统加锁方式带来的性能开销。文章不仅剖析了`AtomicInteger`的内部机制,还结合实际案例展示了其在并发编程中的优势和使用技巧。 ... [详细]
  • Golomb 编码是一种高效的变长编码技术,专门用于整数的压缩。该方法通过预定义的参数 \( M \) 将输入整数分解为商 \( q \) 和余数 \( r \) 两部分。具体而言,输入整数除以 \( M \) 得到商 \( q \) 和余数 \( r \),其中商 \( q \) 采用一元编码表示,而余数 \( r \) 则使用二进制编码。这种编码方式在数据压缩和信息传输中具有显著的优势,特别是在处理具有特定概率分布的数据时表现出色。 ... [详细]
  • 在HDU 1166敌军布阵问题中,通过运用线段树数据结构,可以高效地计算指定区间的敌军数量。该算法不仅能够在限定的时间和内存条件下快速求解,还能够灵活应对动态变化的战场局势,为实时决策提供支持。 ... [详细]
  • 本文探讨了基于端口的ACL访问控制列表与NAT网络地址转换功能的整合优化。基本ACL主要针对源IP地址进行匹配,而高级ACL则能同时匹配源IP、目标IP、源端口及目标端口等多层字段,提供更精细的流量管理。此外,NAT技术的核心优势在于实现宽带共享,通过将内部私有IP地址转换为外部公共IP地址,有效解决了IP地址资源紧张的问题,并增强了网络安全。 ... [详细]
author-avatar
月逝彼山
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有